前言：本篇文章除了能夠讓你了解到虛擬機的作業原理外，還可以讓你了解到較低級別的編程程序，
由于我喜歡在較低級別（Low-level）的應用中（編譯器，解釋器，決議器，虛擬機等等）作業，所以我覺得寫一篇關于用C編程語言構建虛擬機的文章，是非常有必要的，我認為這篇文章除了能夠讓你了解到虛擬機的作業原理外，還可以讓你了解到較低級別的編程程序，
準備內容
·使用的編譯器型別：我正在使用的是clang，它是輕量級編譯器，但你可以使用任何現代編譯器；
·文本編輯器：我建議當撰寫C語言時，通過IDE編輯文本編輯器，我將使用Emacs;
·基本的編程知識：比如什么是變數，流量控制，函式，結構等；
· GNU Make：GNU Make主要用于自動化構建可執行程式（庫檔案），這樣我們就不需要在終端中一遍又一遍地撰寫相同的命令來編譯代碼，Make的功能包括:自動化構建和安裝；增量編譯及自動更新；適用于多語言，比如c/c++、java、php等；支持自定義功能擴展（只要有意義，都是可以放到makefile中），
為什么你應該寫一個虛擬機？
以下是你應該撰寫虛擬機的一些原因：
1.你需要更深入地了解計算機的作業方式，本文將幫助你了解你的計算機在較低級別的環境中是如何運行作業的？而虛擬機則提供了一個非常簡單的抽象層；
2.順便了解一些虛擬機的知識；
3.深入了解一下編程語言的作業原理，現在的各種語言都針對虛擬機，比如JVM，Lua VM，FaceBook 的 Hip—Hop VM（PHP/Hack）等，
指令集
指令集會相對簡單，我將簡要介紹一下，例如如何從暫存器中移動值或跳轉到其他指令，
假設我們的虛擬機有一組暫存器：A，B，C，D，E和F，且這些都是通用暫存器，這意味著它們可以用于存盤任何東西，這與專用暫存器不同，例如在x86上，ip,
flag, ds,
…程式是只讀指令集，如果虛擬機是一個基于堆疊的虛擬機，這意味著它有一個我們可以壓堆疊和彈出值的堆疊，另外，該虛擬機還有一些我們也可以使用的暫存器，基于堆疊的虛擬機比基于暫存器的虛擬機實作起來要簡單得多，
下面是我將要實施的一個指令集的示例：
PSH 5 ; pushes 5 to the stack
PSH 10 ; pushes 10 to the stack
ADD ; pops two values on top of the stack, adds them pushes to stack
POP ; pops the value on the stack, will also print it for debugging
SET A 0 ; sets register A to 0
HLT ; stop the program
以上就是我的指令集，請注意，POP指令將列印我們彈出的指令，其中很多是除錯用的，ADD會將結果壓堆疊到堆疊，所以我們可以從堆疊中的彈出值來驗證它是否存在，我還在其中包含了一條SET指令，這樣你就可以了解如何訪問和寫入暫存器了，你也可以嘗試執行像MOV
A，B（將值A移至B）的指令， HLT是顯示我已經完成程式執行的指令，
虛擬機如何作業？
其實虛擬機比你想象的要簡單，它的作業模式遵循一個簡單的規律，即“指令周期（instruction cycle）”，整個程序包括讀取、解碼、執行三大塊，首先，你要讀取指令集，然后才能解碼指令并執行解碼后的指令，
專案結構
在我開始編程之前，需要做一些準備作業，我需要一個檔案夾來放置專案，我喜歡將專案放置于~/Dev下，另外，我需要一個C編譯器（我使用的是
clang 3.4），以下是我在終端中設定我的專案的程序，假設你已經擁有一個?/ dev /目錄，不過你可以把它放到任何你想要的位置，
$ cd ~/dev/
$ mkdir mac
$ cd mac
$ mkdir src
上面就是我把cd放到我的~/dev目錄的程序，首先，我會創建一個目錄（我稱之為VM“mac”），然后，我進入該目錄并創建我的src目錄，這個目錄被用于存放代碼，
Makefile檔案
我的makefile相對比較簡單，由于該檔案不需要將任何東西分隔成多個檔案，所以其中也不會包含任何東西，我只需要用一些標志來編譯檔案即可，
SRC_FILES = main.c
CC_FLAGS = -Wall -Wextra -g -std=c11
CC = clang
all:
${CC} ${SRC_FILES} ${CC_FLAGS} -o mac
現在這應該足夠了，你以后可以隨時改進它，但只要它能完成這項作業，我們應該沒問題，
指令編程
現在就可以開始撰寫虛擬機的代碼了，首先，為了解釋指令編程，我必須用到一個列舉，因為我們的指令基本上是從0到X的數字，事實上，匯編程式將獲取你的匯編檔案，并將所有操作轉換為對應的數字，例如，如果你為mac撰寫一個匯編程式，它將把所有MOV操作轉換為數字0，
typedef enum {
PSH,
ADD,
POP,
SET,
HLT
} InstructionSet;
現在我可以將測驗程式存盤為一個陣列，然后寫一個簡單的程式用于測驗，比如將5和6相加，然后將它們用POP指令列印出來，如果你愿意，你可以定義一個指令將堆疊頂的值列印出來，
指令應該存盤成一個陣列，我將在檔案的頂部定義它，但你可以把它放在一個頭檔案中，以下是我的測驗程式，
const int program[] = {
PSH, 5,
PSH, 6,
ADD,
POP,
HLT
};
上面的程式會將5和6壓堆疊入堆疊，執行add指令，該指令將彈出堆疊中的兩個值，將它們加在一起并將結果壓堆疊回堆疊，然后會彈出結果，出于除錯目的，我的彈出指令將列印這兩個值，
最后，HLT指令意味著終止程式，如果我們要控制流程，可以隨時終止程式，不過，如果我們沒有任何指示，我們的虛擬機最后也將自然終止，
現在我實作了虛擬機的讀取、解碼、執行的程序，但是要記住，我沒有解碼任何東西，因為我給出的是原始指令，
獲取當前指令
因為我已將程式存盤為一個陣列，所以獲取當前指令很簡單，虛擬機有一個計數器，通常稱為程式計數器，不過有時也叫做指令指標等，通常它們分別縮寫為PC或IP，
現在，我只需在代碼頂部創建一個名為ip的變數，并將其設定為0，
int ip = 0;
這個ip代表指令指標，由于我已經將程式本身存盤為一個整數陣列，故ip變數作為陣列中的索引，表示當前正在執行的指令，
int ip = 0;
int main() {
int instr = program[ip];
return 0;
}
如果列印變數instr，則PSH將顯示為0，因為變數instr是我們列舉里的第一個值，不過，我們也可以寫一個取回函式，如下所示：
int fetch() {
return program[ip];
}
該函式在被呼叫時將回傳當前指令，那么，如果我們想要下一條指令呢？我們只要增加指令指標即可，
int main() {
int x = fetch(); // PSH
ip++; // increment instruction pointer
int y = fetch(); // 5
}
那么我們該如何實作自動化呢？我們知道程式只有執行通過HLT指令時，才會停止，所以該程式本身就是一個無限回圈，
#include <stdbool.h>
bool running = true;
int main() {
while (running) {
int x = fetch();
if (x == HLT) running = false;
ip++;
}
}
我目前要做的是回圈遍歷每條指令，檢查指令的值是否為HLT，如果是，則停止回圈，否則就不斷重復，
一條指令的評估
這是虛擬機的運行要點，其實虛擬機非常簡單，你可以撰寫一個巨大的switch陳述句，而這么做就是為了加快運行速度，與之相對的是，對于所有指令和使用execute方法的某個抽象類或介面，都要使用HashMap，
switch陳述句中的每個case都是我們在列舉中定義的指令，這個eval函式將使用一個簡單的指令引數來評估指令，除非你正在使用運算元，否則不要在此函式中執行任何指令指標增量，
void eval(int instr) {
switch (instr) {
case HLT:
running = false;
break;
}
}
我會將此函式添加回虛擬機的主回圈中：
bool running = true;
int ip = 0;
// instruction enum
// eval function
// fetch function
int main() {
while (running) {
eval(fetch());
ip++; // increment the ip every iteration
}
}
堆疊
不過在添加其他指令之前，我們需要一個堆疊，堆疊是一個非常簡單的資料結構，我們將使用這個陣列而不是一個鏈表，因為我的堆疊是固定大小的，所以不必擔心大小的調整，使用陣列而不是連接串列，在快取效率方面會更占優勢，
與我們如何擁有一個用于索引程式陣列的ip類似，現在我們需要一個堆疊指標（sp）來顯示我們在堆疊陣列中的位置，
下面是我的一個堆疊的資料結構的詳細串列：
[] // empty
PSH 5 // put 5 on **top** of the stack
[5]
PSH 6 // 6 on top of the stack
[5, 6]
POP // pop the 6 off the top
[5]
POP // pop the 5
[] // empty
PSH 6 // push a 6...
[6]
PSH 5 // etc..
[6, 5]
讓我們按照堆疊來分解我們的程式:：
PSH, 5,
PSH, 6,
ADD,
POP,
HLT
首先我把5壓堆疊到堆疊上：
[5]
然后把6壓堆疊到堆疊上：
[5, 6]
然后add指令將彈出這些值并將它們加在一起，最后將結果壓堆疊到堆疊上，
[5, 6]
// pop the top value, store it in a variable called a
a = pop; // a contains 6
[5] // stack contents
// pop the top value, store it in a variable called b
b = pop; // b contains 5
[] // stack contents
// now we add b and a. Note we do it backwards, in addition
// this doesn't matter, but in other potential instructions
// for instance divide 5 / 6 is not the same as 6 / 5
result = b + a;
push result // push the result to the stack
[11] // stack contents
你看出來了嗎，我的堆疊指標在哪里起了作用？堆疊指標被設定為-1，這意味著它是空的，陣列在C中為零索引，所以如果sp為0，它將被設定為C編譯器在其中引發的亂數，因為陣列的記憶體未被清零，
如果現在我壓堆疊3個值，則sp將為2.因此，這里是一個包含3個值的陣列：
-> sp -1
psh -> sp 0
psh -> sp 1
psh -> sp 3
sp points here (sp = 2)
|
V
[1, 5, 9]
0 1 2 <- array indices or "addresses"
現在我從堆疊上出堆疊一次，就需要減小堆疊頂指標，比如我接下來要把9出堆疊，那么堆疊頂將變為5，
sp points here (sp = 1)
|
V
[1, 5]
0 1 <- these are the array indices
所以，當我想知道堆疊頂內容的時候，只需要查看sp的當前值，希望你現在應該知道堆疊是如何作業的，
現在我們用C語言實作它，用C語言實作一個堆疊是很簡單的，和ip一樣，我們也應該定義sp變數和陣列，這個陣列就是堆疊，
int ip = 0;
int sp = -1;
int stack[256];
...
現在，如果我們想將壓堆疊一個值，就要增加堆疊指標，然后在當前sp中設定該值，
這個命令的順序是非常重要的，如果你先設定值，再增加sp，那你會得到一些不好的行為，因為我們在索引-1處寫入了記憶體，
// sp = -1
sp++; // sp = 0
stack[sp] = 5; // set value at stack[0] -> 5
// top of stack is now [5]
在我們的eval函式中，可以像以下這樣進行壓堆疊，
void eval(int instr) {
switch (instr) {
case HLT: {
running = false;
break;
}
case PSH: {
sp++;
stack[sp] = program[++ip];
break;
}
}
}
可以很明顯看到，這與以前的eval函式有一些區別，首先，我們把每個case陳述句塊放到大括號里，你可能不理解這樣做的用意，它可以讓你在每條case的作用域里定義變數，雖然現在不需要定義變數，但將來會用到，并且這樣做可以很容易得讓所有的case陳述句塊保持一致的風格，
其次，是program[++ip]
運算式，該運算式是負責PSH指令所需的運算元，因為我們的程式存盤在一個陣列里，PSH指令需要獲得一個運算元，運算元本質是一個引數，就像當你呼叫一個函式時，你可以給它傳遞一個引數，這種情況我們稱作壓堆疊數值5（PSH,
5），我們可以通過增加指令指標ip來獲取運算元，當ip為0時，這意味著執行到了PSH指令，接下來我們希望取得壓堆疊的數值，這可以通過ip自增的方法實作，實作后，就需要跳到下一條指令否則會引發奇怪的錯誤，當然我們也可以把sp++簡化到stack[++sp]里，
program = [ PSH, 5, PSH, 6, ]
0 1 2 3
when pushing:
ip starts at 0 (PSH)
ip++, so ip is now 1 (5)
sp++, allocate some space on the stack
stack[sp] = program[ip], put the value 5 on the stack
POP指令非常簡單，只需對堆疊指標進行遞減操作即可，但是，如果你想讓pop指令列印剛剛彈出的值即出堆疊值,還要做很多作業，
case POP: {
// store the value at the stack in val_popped THEN decrement the stack ptr
int val_popped = stack[sp--];
// print it out!
printf("popped %d\n", val_popped);
break;
}
最后是添加ADD指令，ADD指令,是一種計算機指令,含義為兩數相加(不帶進位)，這可能會讓你覺得有點棘手，而這正是case陳述句塊放到大括號里的技巧所在，因為我們現在要引入了一些變數了，
case ADD: {
// first we pop the stack and store it as 'a'
int a = stack[sp--];
// then we pop the top of the stack and store it as 'b'
int b = stack[sp--];
// we then add the result and push it to the stack
int result = b + a;
sp++; // increment stack pointer **before**
stack[sp] = result; // set the value to the top of the stack
// all done!
break;
}
在具體操作之前，請注意，這里的某些操作的順序很重要！
5 / 4 != 4 / 5
堆疊是LIFO，全稱First in, First out，先進先出，也就是說，如果先進堆疊5再進堆疊4，就會先出堆疊4，然后出堆疊5，如果我們確實執行了pop() / pop()，那么這將會給我們錯誤的運算式，因此，確保順序正確是至關重要的，
暫存器
暫存器是虛擬機中的選配件，很容易實作，之前提到過我們可能需要六個暫存器：A，B，C，D，E和F，和實作指令集一樣，我們也用一個列舉來實作它們，
typedef enum {
A, B, C, D, E, F,
NUM_OF_REGISTERS
} Registers;
不過這里有一個小技巧，列舉的最后會出現NUM_OF_REGISTERS，通過這個函式可以獲取暫存器的大小，即便你又添加了其它的暫存器，也可以獲得它們的大小，
我會將我的暫存器存盤在一個陣列中，這是因為我要使用列舉，A = 0，B = 1，C = 2等，所以當我想設定暫存器A時，就想說register [A] = some_value一樣簡單，
int registers[NUM_OF_REGISTERS];
列印暫存器A中的值：
printf("%d\n", registers[A]); // prints the value at the register A
指令指標
記住有一條分支指令的指標是要指向當前指令的，由于現在是虛擬機源代碼，所以最好的辦法是將指令指標作為一個暫存器，這樣你就可以從虛擬機程式中進行讀取和各種操作，
typedef enum {
A, B, C, D, E, F, PC, SP,
NUM_OF_REGISTERS
} Registers;
現在我需要移植代碼來實際使用這些指令和堆疊指標，最快的方法是洗掉堆疊頂的sp和ip變數，并用以下的定義替換它們，
#define sp (registers[SP])
#define ip (registers[IP])
這樣你就不必重寫很多代碼了，就能完美地運行了，不過缺點是，不能很好地擴展，并且它會混淆一些代碼，所以我建議不要使用這種方法，但對于一個簡單的虛擬機來說，用一下也無妨，
當涉及到分支代碼時，我會給你一個提示，有了新的IP暫存器后，我們可以通過向這個IP寫入不同的值來進行分支，試試下面這個例子，看看它能做什么，
PSH 10
SET IP 0
這類似于很多人都熟悉的基本程式:
10 PRINT "Hello, World"
20 GOTO 10
但是，由于我們不斷地進行進堆疊，所以一旦進堆疊的量超過空間量，就將發生堆疊溢位，
請注意，每個 ‘word’是一個指令，所以程式以下所示，
; these are the instructions
PSH 10 ; 0 1
PSH 20 ; 2 3
SET IP 0 ; 4 5 6
如果我們想跳到第二組指令，我們將IP暫存器設定為2而不是0，
總結
閱讀完本文后，如果你在專案根目錄中運行make，則可以執行虛擬機：./mac，
你可以在這里查看github上的源代碼，如果你想用MOV和SET指令來看虛擬機的更新版本，那么檢查一下mac-improved目錄，我們在本文中實作的虛擬機的源代碼位于mac.c中
點擊了解更多資料，更有免費開源專案和課程等你觀看哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/187632.html
標籤：其他
下一篇：記一次flink入門學習筆記