深入理解 Linux 進程原理及實現機制

普通人的視角，進程就是正在運行着的程序。進程是計算機中正在運行的程序的實例，每個進程都有自己的獨立內存空間和執行上下文，包括程序計數器、寄存器、棧等，進程的創建通過操作系統的調度器完成。當一個程序被執行時，操作系統會爲它分配一塊內存空間，並將程序加載到這塊內存中。這樣，該程序就成爲一個獨立的進程了。

進程之間是相互獨立運行的，它們不會直接訪問其他進程的內存空間。爲了實現不同進程之間的通信，操作系統提供了各種機制，如管道、共享內存、消息隊列等，每個進程都有自己的優先級和調度策略，操作系統根據這些信息來決定對哪個進程進行調度，以便公平地分配處理器時間，進程還可以擁有子進程，這是通過 fork() 函數實現的。子進程在創建後會複製父進程的代碼和數據，並開始獨立運行。

從程序員的視角來看，認知要複雜得多。進程是程序正在運行的一個實例。它由程序指令，和從文件、其它程序中讀取的數據或系統用戶的輸入組成。它也是應用層運行、佔據着內存、與內核時常交互的動態運行實體。

進程是由內核定義的抽象的實體，內核爲進程分配用來執行程序的各項系統資源。

從內核 的層面來看，進程由用戶內存空間和一系列內核數據結構組成。其中，用戶內存空間包含了程序代碼和代碼使用的變量，內核數據結構用於維護進程的狀態信息。這些記錄在內核數據結構的信息有：進程標識號 IDs、虛擬內存表、打開文件描述符表、信號傳遞及處理的相關信息、進程資源使用和限制、當前工作目錄、環境變量、命令行等等大量的相關信息。

一、Linux 進程

1.1 進程概論

進程是執行中的程序，一個程序加載到內存中後就變爲進程。進程 = 程序 + 執行。爲了提高 CPU 利用率，人們想起將多個程序同時加載到計算機裏，併發執行。進程讓每個用戶感覺自己獨佔 CPU。

(1) 進程模型

從物理內存的分配來看，每個進程佔用一片內存空間。

在物理層面上，所有進程共用一個程序計數器。

從邏輯層面上看，每個進程有着自己的計數器，記錄其下一條指令所在的位置。

從時間上看，每個進程都必須往前推進。

進程不一定必須終結。事實上，許多系統進程是不會終結的，除非強制終止或計算機關機。

對於操作系統來說，進程是其提供的一種抽象，目的是通過併發來提高系統利用率，同時還能縮短系統響應時間。

(2) 多道編程的好處

人們發明進程是爲了支持多道編程，而進行多道編程的目的則是提高計算機 CPU 的效率，或者說系統的吞吐量。

除了提高 CPU 利用率外，多道編程更大的好處是改善系統響應時間，即用戶等待時間。多道編程帶來的好處到底有多少與每個程序的性質、多道編程的度數、進程切換消耗等均有關係。但一般來說，只要度數適當，多道編程總是利大於弊。

(3) 進程的產生與消亡

造成進程產生的主要事件有：

造成進程消亡的事件：

1.2 進程的層次結構

一個進程在執行過程中可以通過系統調用創建新的進程，這個新進程就稱爲子進程，而創建子進程的進程稱爲父進程。子進程又可以創建子進程，這樣子子孫孫創建下去就形成了所謂的進程樹。

Unix 稱這個進程樹裏所有的進程爲一個進程組，進程組裏面的進程分佈在不同的層次上，從而形成一個層次架構。Windows 沒有進程組的概念，而是所有進程均地位平等。

(1) 進程的狀態

進程可以在 CPU 上執行，也可以處於掛起狀態。掛起的原因有：

操作系統在進程調度時就只需要查看第二種類型的掛起，而非第一類自身原因造成的掛起。

進程分爲 3 種狀態：執行、阻塞和就緒。

進程：一個程序加載到內存後就變爲進程，即進程 = 程序 + 執行。每個進程佔用一片內存空間。因爲一個進程的執行過程中只佔用其生命週期的一部分來使用 CPU，因而可以實現多道編程，從而提高 CPU 的效率。隨進程數增加，也就是隨着多道編程的度的增加，CPU 利用率會逐步提升，直到某個臨界點爲止。

阻塞：阻塞操作即讀寫磁盤、收發數據包等，此時進程訪問的數據尚未就緒，是直接返回還是等待就緒。

阻塞等待：進程進入阻塞態後，會交出 CPU

繁忙（循環）等待：進程雖然沒做什麼有意義的事，但一直佔用着 CPU

掛起：將任務掛起的實質就是：

就緒：將任務改爲就緒狀態的實質就是將對應任務就緒表對應位設置爲 1 並將任務控制塊狀態標誌改爲就緒狀態

阻塞與掛起的區別：掛起是主動的，需要調用掛起函數來進行，若沒有 resume 操作則此任務一直不會 ready；而阻塞是因爲資源被其他任務搶佔而處於休眠態。兩者的表現方式都是從就緒態裏 “清掉”，即對應標誌位清零，只不過實現方式不一樣。

進程的狀態：進程既可以在 CPU 上執行，也可以處於掛起狀態。掛起的原因分兩種：1）由於執行到阻塞操作（如讀寫磁盤），此時需要等待結果後方能繼續執行，故這種是由於自身原因的掛起；2）由於執行時間過長，爲了公平，操作系統將其掛起。由此，進程可分爲三種狀態：執行態——阻塞態——就緒態

多道編程：在內存中同時存放幾道相互獨立的程序，使它們在管理程序控制下，相互穿插運行，兩個或兩個以上程序在計算機系統中同處於開始到結束之間的狀態, 這些程序共享計算機系統資源。在多道程序環境下，當某個程序等待 I/O 操作時，CPU 可以執行其他程序，從而大大提高 CPU 的利用率。對於一個單 CPU 系統來說，程序同時處於運行狀態只是一種宏觀上的概念，他們雖然都已經開始運行，但就微觀而言，任意時刻，CPU 上運行的程序只有一個。

進程管理的核心問題：公平和效率。

狀態轉換：

爲何沒有以下狀態轉換

阻塞 -> 執行：阻塞進程即使給予 CPU，也無法執行，因此操作系統在調度時並不會從阻塞隊列裏挑選。

就緒 -> 阻塞：處於就緒狀態的進程並沒有執行，自然無法進入阻塞狀態。

這裏闡述的進程的 3 種典型狀態並不是唯一的分類方式。事實上，許多商業操作系統的進程狀態不止 3 個。不管是多少個，其目的都是便於操作系統管理進程。

(2) 進程與地址空間

進程與地址空間演技丶主要內容是如何讓多個進程空間共享一個物理內存。具體來說，就是高效、安全地讓所有進程共享這片物理內存。

1.3 進程管理

(1) 進程管理所需要的手段

當一個進程產生時，操作系統需要爲其創建記錄。操作系統用於維護進程記錄的結構就是進程表或進程控制塊（Process Control Block）。顯然，不同的操作系統維護的進程記錄不同。但一般來說，應當包括寄存器、程序計數器、狀態字、棧指針、優先級、進程 ID、信號、創建時間、所耗 CPU 時間、當前持有的各種句柄等。而採納的數據結構主要是線性表、鏈表和結構體，當然也可能使用樹和圖結構。

(2) 進程的創建過程

  1. 分配進程控制塊

  2. 初始化機器寄存器

  3. 初始化頁表

  4. 將程序代碼從磁盤讀進內存

  5. 將處理器狀態設置爲用戶態

  6. 跳轉到程序的起始地址（設置程序計數器）

裏一個最大的問題是，跳轉指令是內核態指令，而在第 5 步時處理器狀態已經被設置爲用戶態。硬件必須將第 5 步和第 6 步作爲一個步驟一起完成。

進程創建在不同操作系統裏方法也不一樣：

Unix 的創建進程要靈活一點，因爲我們既可以自我複製，也可以啓動新的程序。而自我複製在很多情況下是很有用的。而在 Windows 下，複製自我就要複雜一些了。而且共享數據只能通過參數傳遞來實現。

進程管理要處理的問題

進程管理的最大問題是資源分配。除了公平之外，還要考慮效率最優。每個進程分配同樣的資源肯定不行，不如讓部分人先富起來，給他們使用資源的優先權。

1.4 線程

雖然進程已經能提供進程級別的並行，但有時候，我們在一個進程裏也有並行的需求。比如我們打開 word 這個進程，我們希望即使在這個進程中，也能同時處理多件事（比如輸入文字和移動窗口是兩個獨立的並行事件）。這就要求我們在進程層面上進一步實現併發。

線程實現方式：線程管理既可由進程自己來（即用戶態線程實現），也可以交給操作系統（即內核態線程實現）。現代操作系統的做法是將這兩種方法結合起來：用戶態的執行系統負責進程內部線程在非阻塞時的切換；內核態的操作系統負責阻塞線程的切換。

多線程資源共享：兩個根本的問題是 “通信（溝通）” 和“同步（協調）”。

原子操作（atomic operation）：指不會被線程調度機制打斷的操作；這種操作一旦開始，就一直運行到結束，中間不會有任何 context switch。

原語（primitive or atomic action ）：是由若干條機器指令組成的，用於完成一定功能的一個過程，具有不可分割性。即原語的執行必須是連續的，在執行過程中不允許被中斷。

線程通信

線程同步

同步：同步不是說每個線程在某段時間內一定要執行同樣多的指令，而是指所有的線程按一定規則進行。

同步的目的：爲了保證不管線程間的執行如何穿插，其運行結果都是正確的（保證結果的確定性）。

同步的手段：對線程間的穿插進行控制。

競爭（race）：多個線程爭相執行同一段代碼（代碼競爭）或訪問同一資源（數據競爭）的現象。

臨界區（critical section）：可能造成競爭的共享代碼段或資源。

互斥（mutual exclusion）：不能有兩個進程同時在臨界區內，在互斥區外不能阻止另一個進程的運行。

優先級倒掛：高優先級的線程等待低優先級的線程。這會造成一個問題：假如此時 CPU 在高優先級線程手中，而它此時又需要循環等待（不是阻塞等待）低優先級線程，那麼低優先級線程無法順利獲得 CPU，進而造成高優先級線程始終處於循環等待階段無法推進。這就叫高優先級線程被低優先級線程所阻塞

鎖：一種同步措施，使得在任何時候只能有一個人進入臨界區，以 A 和 B 餵魚的例子來說，爲了魚不被餓死或脹死，那麼一個人進入房間時需把門鎖住：

A：                                    B:
lock()                                 lock()
if(noFeed){                            if(noFeed){
   feed fish                              feed fish
}                                      }
unlock()                               unlock()

假如程序先執行到 A 這邊，此時還沒有上鎖，那麼他先把門鎖住，再進屋餵魚。若此時 B 恰好來到，看到門上了鎖，那他需要循環等待，直到鎖變爲打開狀態，然後他再閉鎖、進屋。

睡覺和叫醒（sleep&wakeup）：在上面一個線程運行到 lock() 的位置時，假如一把鎖已經被別人鎖上，則必須一直繁忙等待直到鎖打開才能繼續執行。這就很低效。爲此，我們採取另外的機制：睡覺和叫醒。就是如果鎖被對方持有，你不用等待鎖變爲打開狀態，而是睡覺去（釋放 CPU），鎖打開後再來把你叫醒。

死鎖：單純採用睡覺和叫醒機制，可能產生死鎖。以生產者 - 消費者例子爲例，假定 consumer 先來，此時 count==0，於是去睡覺，但假如在執行 sleep 語句前發生 CPU 切換，生產者開始運行，它生產一件商品後，給 count 加 1，發現 count 爲 1，因此發出叫醒消費者的信號。但此時 consumer 還沒有睡覺，故該信號沒有任何效果，浪費了。而生產者一直運行到緩衝區滿了之後也去睡覺了，此時 CPU 切換回消費者，而消費者執行的第一個操作就是睡覺。至此，兩者都進入睡覺狀態，系統死鎖發生。

上述死鎖發生的原因在於喚醒信號丟失，爲此，我們希望用某種方法將發出的信號積累起來而不是丟掉。由此，產生了所謂的 “信號量” 的機制。

信號量（semaphore）：既是通信原語，又是同步原語，還可作鎖。本質上就是計數器，取值爲當前累積的信號數量。它有兩個基本操作：

1）down 減法：減少信號量或等待（判斷信號量取值是否≥1，如果是的話就減一；0 的話即減無可減的時候就去睡覺）

2）up 加法：增加信號量並喚醒（喚醒等待在該信號量上的線程）

二元信號量（binary semaphore）：信號量取值限制爲 0 或 1，規則同上，此時其作用就是一把結合了睡覺與叫醒操作的鎖。down 操作就是獲得鎖：閉鎖（值變爲 0），或等待開鎖（鎖在別人手裏處於閉鎖狀態）；up 操作就是釋放鎖（值變爲 1）並喚醒該信號量上等待的線程。它比鎖更靈活的地方在於：等在信號量上的線程不是繁忙等待，而是去睡覺，等另一個線程執行 up 操作來叫醒。

同樣使用上面餵魚的例子，將 lock() 換爲 down()，將 unlock() 換爲 up() 即可。

typedef int semaphore
semaphore mutex = 1  /* 互斥信號量 */
A：                                    B:
down(&mutex)                           down(&mutex)
if(noFeed){                            if(noFeed){
   feed fish                              feed fish
}                                      }
up(&mutex)                             up(&mutex)

假如程序先執行到 A 這邊，此時信號量爲 1（還沒有上鎖），那麼他先把信號量減爲 0（把門鎖住），再進屋餵魚。若此時 B 恰好來到，看到信號量爲 0（門上了鎖），那他需要等待（去睡覺），直到 A 喂完魚執行 up() 操作，此時會喚醒等待在信號量 mutex 上的 B。

使用信號量的一個問題是：如果信號量太多，則需要非常小心地設計其操作的先後順序，否則很容易發生死鎖。爲了改變這一狀況解放人力，發明了所謂的 “管程” 的機制。

管程（monitor）：將需要保護的代碼放到 begin monitor 和 end monitor 之間，在任何時候只能有一個線程活躍在管程裏面。這一點由編譯器來完成。管程使用兩種同步機制：鎖 + 條件變量。條件變量是線程可在其上等待的東西，類似信號量，但沒有 down 和 up 操作。

管程的中心思想是運行一個在管程裏面睡覺的線程，但在睡覺前需要把進入管程的鎖或信號量釋放，否則在其睡覺後別的線程將無法進入管程（因爲無法獲得鎖），就會造成死鎖。

begin monitor
   integer i;
   condition c;
   procedure producer();
   ...
   end;
   
   procedure consumer();
   ...
   end;
end monitor

管程的問題是依賴於編譯器，並且只能在單臺計算機上發揮作用。爲了在多機環境（或網絡環境）下進行同步，引入了 “消息傳遞” 機制。

消息傳遞：通過同步雙方互相收發消息來實現。有 send 和 receive 兩個基本操作。同步需要的是阻塞調用：即如果一個線程執行 receive 操作，則該線程將被掛起，在收到消息後，才能轉入就緒。同樣使用上面的例子，生產者和消費者通過這樣的消息傳遞進行同步，既不會死鎖，也不會繁忙等待。而且，無需使用臨界區等機制，還能跨計算機同步。因此，消息傳遞是目前使用非常廣泛的線程同步機制。

其缺點是消息丟失和身份識別，以及效率。

柵欄：主要用於將一組線程強制停下，等柵欄去除後才能繼續往前推進

二、進程調度

2.1 進程調度的定義

在多進程併發的環境裏，雖然從概念上看，有多個進程在同時執行，但在單 CPU 下，實際上在任何時刻只能由一個進程處理執行狀態。

程序使用 CPU 的模式有 3 種：

對於不同性質的程序，調度所要達到的目的也不同：

2.2 進程調度的目標

CPU 調度就是要達到：

對於不同的系統來說，在調度目標方面也有一些細微的不同：

先來先服務調度算法 First Come First Serve

類似排隊，先來先到的原則。缺點是短的工作由可能因爲前面有很長的工作變得很慢。這樣就造成用戶的交互式體驗比較差。

2.3 時間片輪轉算法

時間片輪轉算法是對 FCFS 算法的一種改進，其主要目的是改善短程序的相應時間，其方法就是週期性地進行進程切換。

系統響應時間依賴於時間片的選擇。如果時間片過大，則越來越像 FCFS。如果時間片過小，則進程切換所用的系統消耗將太多，從而降低系統效率，並造成浪費。

那如何選擇一個合適的時間片呢？我們需要知道進行一次進程切換所用的系統消耗和我們能夠承受的整個系統消耗，就可以得出合適的時間片。還需要考慮的一個因素是有多少進程在系統裏運行。如果運行的進程多，時間片就需要短一些，不然用戶的交互體驗會很差。

2.4 短任務優先算法 Shorted Time to Completion First

這種算法的核心是短任務的優先級比長任務的高。

短任務優先算法有兩個變種：

事實上，在所有非搶佔調度算法中，STCF 算法的響應時間最優；而在所有搶佔調度算法中，搶佔式 STCF 的響應時間最優

缺點：

2.5 優先級調度算法

可以賦予重要的進程以高優先級以確保重要任務能夠得到 CPU 時間。

缺點：

2.6 混合調度算法

將所有進程分成不同的大類，每個大類爲一個優先級。如果兩個進程處於同一個大類，則採用時間片輪轉來執行。

2.7 其他調度算法

調度異常之優先級倒掛（priority inversion）：低優先級任務持有一個被高優先級認爲所需要的共享資源，這樣高優先級任務因資源缺乏處於受阻狀態，一直到低優先級任務釋放資源爲止。如果高優先級進程在等待時不是阻塞等待而是循環等待，則低優先級進程無法爭奪到 CPU 造成無法釋放資源。進而高優先級進程無法獲得資源而推進。

2.8 倒掛的解決方案

鎖的實現

在線程同步中提到的各種同步機制雖然各不相同，但有個共同特點：即同步原語均是原子操作（即不會被打斷）。任何同步原語在微指令級別上都有多個步驟，如何保證這些同步原語的原子性呢？其根本原因在於在硬件層面上已經提供了一些原子操作：中斷禁止和啓用（interrupt enable/disable），內存加載和存入（load/store），測試與設置（test&set）指令。

死鎖應對

在 Lab2 中完成了內存佈局，最重要的是 mem_init() 函數的功能。這個函數在內核剛開始運行時就被調用，對整個操作系統的內存管理系統進行一些初始化設置：創建開闢一個頁表大小的空間作爲頁目錄 kern_pgdir，開闢一片內存空間用於保存 npages 個 struct PageInfo，開闢一片內存空間用於保存 NENV 個 struct Env，然後構建虛擬內存空間：將虛擬地址映射到物理地址（映射關係記錄到 kern_pgdir 中）。我們用 mem_init() 函數大致回顧下現在已經建立好的東西：

void mem_init(){
    //檢查內存還有多少
    i386_detect_memory();    
 
    //分配一個物理頁作爲頁目錄表
    //boot_alloc只是暫時的頁分配器，等我們建立好頁目錄後，將使用page_alloc函數來分配物理頁(返回對應PageInfo結構體指針)
    kern_pgdir = (pde_t *)boot_alloc(PGSIZE);    
 
    //添加第一個頁目錄表項
    kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;
 
    //分配一塊內存用於存放struct PageInfo數組，用於追蹤所有內存物理頁的使用情況
    pages = (struct PageInfo *)boot_alloc(npages*sizeof(struct PageInfo));
 
    //分配一塊內存用於存放struct Env數組，用於追蹤所有進程情況
    envs = (struct Env *)boot_alloc(NENV*sizeof(struct Env));
 
    //初始化pages數組，初始化pages_free_list鏈表
    page_init();
 
    //下面構建虛擬地址空間
    //函數原型：boot_map_region(pde_t* pgdir, uintptr_t va, size_t size, phyaddr_t pa, int perm)
    //功能是：把虛擬地址空間範圍[va, va+size]映射到物理空間[pa, pa+size]的映射關係加入到頁表pgdir中
    //注：也可以用page_insert()實現同樣的功能
    boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U);
    boot_map_region(kern_pgdir, UENVS, PTSIZE, PADDR(envs), PTE_U);
    boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);
    boot_map_region(kern_pgdir, KERNBASE, 0xffffffff-KERNBASE, 0, PTE_W);
 
    lcr3(PADDR(kern_pgdir));
}

可見，我們現在已經做好的是：建立起了虛擬地址空間（及其到物理地址的映射），在物理內存中有一個 envs 數組，可用來記錄進程情況。 那麼下面我們就要利用這個 envs 數組來構建進程管理系統了。

JOS 的進程 (環境) 管理：

JOS 內核使用 Env 結構體來追蹤用戶進程（又稱用戶環境 environment）。

一個 Env 結構體實際上是記錄了某個進程運行時的上下文，它記錄了進程類型，進程狀態，該進程的虛擬空間的映射，切換進程時需記錄的寄存器值（尤其是該進程的執行入口地址值）等。

在內核中定義瞭如下三個指針用於追蹤並調控進程：

struct Env* envs = NULL;              //指向所有進程的鏈表的指針
struct Env* curenv = NULL;            //指向當前進程
static struct Env* env_free_list;     //空閒進程結構鏈表

而 struct Env 的定義爲：

struct Env {
    struct Trapframe env_tf;   // 當進程停止運行時用於保存寄存器的值，比如當發生中斷切換到內核環境運行了或者
                               // 切換到另一個進程運行的時候需要保存當前進程的寄存器值以便後續該進程繼續執行
    struct Env *env_link;      // 指向空閒進程鏈表env_free_list中的下一個Env結構
    envid_t env_id;            // 進程ID。因爲進程ID是正數，所以符號位是0，而中間的21位是標識符，標識在
                               // 不同的時間創建但是卻共享同一個進程索引號的進程，最後10位是進程的索引號，
                               // 要用envs索引進程管理結構Env就要用ENVX(env_id)
    envid_t env_parent_id;     // 進程的父進程ID
    enum EnvType env_type;     // 進程類型，通常是 ENV_TYPE_USER，後面實驗中可能會用到其他類型
    unsigned env_status;       // 進程狀態，進程可能處於下面幾種狀態：
                               // ENV_FREE：標識該進程結構處於不活躍狀態，存在於env_free_list鏈表。
                               // ENV_RUNNABLE: 標識該進程處於等待運行的狀態。
                               // ENV_RUNNING: 標識該進程是當前正在運行的進程。
                               // ENV_NOT_RUNNABLE: 標識該進程是當前運行的進程，但是處於不活躍的狀態，
                               // 比如在等待另一個進程的IPC。
                               // ENV_DYING: 該狀態用於標識殭屍進程。在實驗4纔會用到這個狀態，實驗3不用。
    // Address space
    pde_t *env_pgdir;         // 用於保存進程頁目錄的虛擬地址
};

構建用戶進程的流程是這樣的：

1）在內存中開闢空間創建 envs（在 mem_init() 中已經完成）和 env_free_list（在靜態區），然後初始化；

2）然後調用 env_create() 創建一個新進程：從 list 上取下一個 Env 結構體用於代表新的進程（env_alloc() 函數），設置這個進程的 env_id、type、env_tf 等值，然後爲該用戶進程分配頁目錄表並調用 load_icode() 函數加載程序代碼到內存中 (包括開闢物理內存並加載代碼)；

注： 在 load_icode() 中爲進程分配頁目錄（page_alloc() 一頁空間用於構建進程頁目錄並初始化）是用於構建地址映射。進程虛擬地址是由進程代碼自身攜帶的：在 elf 的 ph->p_va 中；但具體映射加載到哪段物理地址由操作系統確定。此外，還需要將 e->env_tf.tf_eip 設爲 elfh->e_entry，即設置該進程的執行入口地址。

3）加載完程序代碼後，萬事俱備，調用 env_run(e) 函數開始執行該進程。

上述流程對應的代碼調用過程如下（運行用戶進程前的調用過程）：

start (kern/entry.S)
i386_init (kern/init.c)
    cons_init
    mem_init
    env_init
    trap_init (still incomplete at this point)
    //獲取一個新進程(設置struct Env中的狀態信息)，根據用戶elf文件開闢物理空間並建立映射，映射關係寫入e->env_pgdir，
    //再複製用戶elf到對應虛地址。本質上是env_create(_binary_obj_user_hello_start, ENV_TYPE_USER),
    //這裏的參數_binary_obj_user_hello_start是由鏈接器生成的符號
    env_create        
        //從env_free_list上獲取一個進程指針，指向一個沒內存上被使用的struct Env，並初始化這個新進程的狀態信息 
        env_alloc       
            env_setup_vm       //爲新創建的進程分配一個頁目錄，用於構建進程虛地址到物理地址的映射  
        load_icode             //用戶elf指定了運行虛地址，在這裏就把用戶代碼拷貝到
            region_alloc       //新開闢的物理地址，地址映射記錄到進程e->env_pgdir中
    env_run
        env_pop_tf

在上面，系統運行到 env_run() 之後，用戶進程會遇到 int $0x30 系統調用（即 T_SYSCALL 中斷向量，這個系統調用是輸出一個字符到命令臺），試圖開始中斷之旅。

具體地說，系統在執行 env_pop_tf() 後進入用戶態，並在用戶程序 user_hello 中調用了 cprintf 打印輸出，而 cprintf 最終要通過系統調用來實現也就是需要回到內核態，而此時系統還沒有建立起從用戶態到內核態的轉變機制。

當 CPU 發現它無法處理這一系統調用中斷時，就會拋出一個保護異常 -->然而還是不知道如何處理保護異常，就進一步拋出 “double fault exception”--> 還是不知如何處理，終於屈服了，拋出一個“triple fault”。一般如果在實際中遇到這種異常，會導致系統重啓。

注： kern 和 lib 目錄下面都有 printf.c 和 syscall.c 文件，kern 目錄下面的是內核專用的。而用戶要 cprintf 輸出，就要使用 lib 目錄下面的 printf.c 中的函數，最後經由 lib/syscall.c 的 sys_cputs()，最終通過該文件中的 syscall() 來實現輸出。

看一下 env_alloc() 做了什麼：

主要做了兩件事：1）向進程表申請空閒的進程；2）對新申請的進程的 struct Env(進程描述符) 進行初始化, 主要是段寄存器初始化。在 env_create() 中調用：env_alloc(&e, 0)。

//分配一個新的進程並初始化。若成功，新進程被保存在*newenv_store中(*newenv_store指向新進程的struct Env)，返回0
//這裏必須使用參數struct Env**。若試圖以struct Env*作函數形參，而以外部的struct Env*作實參傳入，
//那麼由於形參是臨時變量，將無法通過它來給實參賦值。
int env_alloc(struct Env** newenv_store, envid_t parent_id){
    int32_t generation;
    int r;
    struct Env* e;
 
    if(!(e = env_free_list))
        return -E_NO_FREE_ENV;    
    //爲這個進程分配和設置頁目錄
    if((r = env_setup_vm(e)) < 0)
        return r;
    //爲這個進程生成一個env_id。這部分代碼不太理解，待有空了慢慢研究
    //ENVGENSHIFT==12(>=LOGNENV)
    generation = (e->env_id + (1 << ENVGENSHIFT)) & ~(NENV-1);
    if(generation <= 0)
        generation = 1 << ENVGENSHIFT;
    e->env_id = generation | (e-envs);
    
    //設置基本狀態變量
    e->env_parent_id = parent_id;
    e->env_type = ENV_TYPE_USER;
    e->env_status = ENV_RUNNABLE;
    e->env_runs = 0;
    
    //把所有保存的寄存器狀態清零，以防止上一個進程遺留的寄存器值影響當前進程
    memset(&e->env_tf, 0, sizeof(e->env_tf));
 
    //爲段寄存器設置合適的初值。GD_UD是GDT中用戶數據段選擇子，GD_UT是用戶代碼段選擇子。
    //每個段寄存器的低2位包含了請求優先級(RPL)；3表示用戶模式。當我們切換優先級時，硬件進行各種
    //檢查，包括RPL以及本身保存在描述符中的描述符優先級(DPL)
    e->env_tf.tf_ds = GD_UD | 3;
    e->env_tf.tf_es = GD_UD | 3;
    e->env_tf.tf_ss = GD_UD | 3;
    e->env_tf.tf_esp = USTACKTOP;
    e->env_tf.tf_cs = GD_UT | 3;
    //我們在之後再設置e->env_tf.tf_eip
 
    //完成分配
    env_free_list = e->env_link;
    *newenv_store = e;
    
    return 0;
}

從內核態進入用戶態：

總的來說，在內核態與用戶態間發生切換時，總需要恢復或保存進程的運行環境（即全部的寄存器值），這一信息是使用 env 的 Trapframe 結構來保存的。

每個進程 env 對應了一個成員是 env_tf，這是一個 struct Trapframe，用於保護 CPU 現場（在發生中斷或進程切換時保存當前進程的寄存器值）。兩種使用情景：

1）在創建新的進程時（上面的 env_alloc() 和 load_icode() 中），會爲這個新創建的進程初始化設置對應的 Trapframe 結構體。等到執行 env_run() 時，會將當前進程的 env_tf 值 pop 到寄存器中，從而準備好執行用戶進程。

2）在發生中斷陷入內核時（int 0x30 後），會先將當前進程的寄存器值按 trapframe 的結構壓入內核堆棧，並將其拷貝到當前進程的 env_tf 中，那麼之後恢復該進程時就能繼續從之前中斷的狀態開始執行了。

結構體 struct Trapframe 定義在 inc/trap.h 中：

inc/trap.h中：
 
struct Trapframe {
    struct PushRegs tf_regs;    //其中有8個通用寄存器的值
    uint16_t tf_es;
    uint16_t tf_padding1;       //這應該是用於填充內存使對齊用的
    uint16_t tf_ds;
    uint16_t tf_padding2;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding3;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding4;
} __attribute__((packed));
 
其中的PushRegs是使用命令pusha時壓入的寄存器值構成的結構體，對應8個通用寄存器：
struct PushRegs {
    uint32_t reg_edi;
    uint32_t reg_esi;
    uint32_t reg_ebp;
    uint32_t reg_oesp;    /* useless */
    uint32_t reg_ebx;
    uint32_t reg_edx;
    uint32_t reg_ecx;
    uint32_t reg_eax;
} __attribute__((packed));

爲一個新創建的進程初始化 struct Trapeframe 的主要工作是在 env_alloc() 中：

  1. 將當前 e->env_tf 結構體清零（防止之前可能的歷史進程留下的信息污染當前進程信息）

  2. 爲段寄存器設置恰當的初值，即設置 e->env_tf.tf_ds、tf_es、tf_ss 爲 GD_UD（即 GDT 中的 user data segment selector）；env_tf.tf_esp 爲 USTACKTOP；env_tf.tf_cs 爲 GD_UT（即 user text segment selector）

然後在 load_icode() 中設置好進程的執行入口地址 e->env_tf.tf_eip = elfh->e_entry。

初始化好了進程的 struct Trapframe，可以使我們在運行 env_run()、試圖從內核進入用戶態時（無論是不是第一次進入），恰當地爲用戶進程佈置好對應於這個進程的寄存器值（即恢復 Trapeframe 到寄存器中去）。注：如果是第一次從內核進入用戶態的話，實際上我們的代碼是人爲製造假象，讓系統以爲第一個進程是原來就有的，它通過中斷進入了內核，在內核處理完了相應的操作之後，才返回用戶態的。

從即將要運行的 env 的 env_tf 中恢復其保存的寄存器值到寄存器中是在函數 env_pop_tf() 中完成的：

kern/env.c中：
//調用方式：env_pop_tf(&curenv->env_tf)，這是進入用戶態前的最後一個函數
void env_pop_tf(struct Trapframe *tf)    
{
    asm volatile(
        "\t movl %0, %%esp\n"       /* %0對應後面的tf，這裏是將tf這個地址值賦給%esp，
                                       從而可以把當前進程的env_tf結構當作一段棧空間來操作 */
        "\t popal\n"                /* 彈出tf_regs到所有的通用寄存器中，
                                       按順序 DI,SI,BP,SP,BX,DX,CX,AX 彈出 */
        "\t popl %%es\n"            /* 彈出值到%es */
        "\t popl %%ds\n"            /* 彈出值到%ds */
        "\t addl $0x8, %%esp\n"     /* 跳過tf_trapno 和 tf_errcode */
        "\t iret\n"                 /* 從中斷返回，將棧中存儲數據彈出到eip, cs, eflags寄存器中 */
        : : "g"(tf) : "memory");    /* “g”表示將輸入變量tf放入eax，ebx，ecx，edx之一,或作爲內存變量, */
                                    /* "memory"告訴編譯器在執行期間會發生內存變動，以防止錯誤的代碼優化 */
    panic("iret failed");
}

此，已經把 env_tf 中保存的值彈出到寄存器中去，從而做好了運行進程代碼的準備。

在執行完 iret 指令後，回到用戶態執行進程程序。一個新創建的進程的入口是定義在 lib/entry.S 中的。在該文件中，首先會進行一些設置，然後就會調用 lib/libmain.c 中的 libmain() 函數，使它能夠初始化全局指針 thisenv，讓它指向當前用戶環境的 Env 結構體。實際上 lib/entry.S、libmain.c、umain.c 被編譯到同一個 ELF 文件中的. text 代碼段。

JOS 的中斷處理 (概念簡介)：

“保護性” 控制轉移包括如下兩種方式：

中斷（interrupt）：由處理器外部事件導致，例如外設的 I/O 請求

異常（exception）：由正在運行的進程自身導致，例如 0 作除數或非法的內存訪問

所謂保護性控制轉移，其實質就是：在實現處理器從用戶態切換到內核態時，不讓用戶進程有任何機會影響到內核區代碼或其他進程代碼，從而保護內核。

其實現方法是這樣的：當需要從用戶態進入內核態時，不能由用戶代碼來決定能否進入內核代碼區以及去到哪，而必須按照我們事先約定的規則，從若干個指定位置進入內核並執行相應的處理代碼。通過這種方式，限制了用戶代碼的權力。

爲使處理器能受保護地從用戶態回到內核態，需用到如下兩種機制：IDT (中斷描述符表) 和 TSS (任務狀態段)。

IDT（中斷描述符表：interrupt descriptor table）：

IDT 提供了進入內核的若干入口 (x86 上總共可有 256 箇中斷或異常入口點)

IDTR + 中斷向量 (interrupt vector) --> 中斷門 (位於 IDT 中) --> 中斷處理程序。簡言之，IDT 就是用於尋址中斷處理程序的。

但我們能否直接跳到中斷處理程序入口呢？答案是不能，因爲我們希望在處理完中斷異常後，還能返回用戶進程繼續之前的運行進程。那麼，這就引出了第二個關鍵工具——TSS，我們需要利用它來保留進程信息 (其實就是 CPU 狀態)。

TSS（任務狀態段：task state segment）：

用於存儲一個任務的所有狀態信息。cpu 在處理進程切換時需要 TSS 來保存舊的處理器狀態，以便在中斷返回時恢復以前的進程。本質上是存放在靜態區的一個結構體變量，在 jos 中用到的唯一功能是用於指定內核棧地址。

在用戶模式下遇到異常 / 中斷，會陷入內核並調用中斷處理函數。但在進入內核後，不是立即進入處理函數，而是先布好退路：1）處理器將用戶進程信息（用戶進程的 CS，EIP，SS，ESP，EFLAGS，以及一個可選錯誤碼）壓入內核棧，內核棧地址由 TSS 中的 SS0，ESP0 來指定；

2）處理器設置 CS，EIP 寄存器使其指向中斷處理程序，並且設置 ESP，SS 寄存器指向新的堆棧。

這樣，當執行完內核異常處理程序後，就可以從內核棧保存的這些信息中恢復用戶進程。

注：儘管 TSS 非常大，並且還有很多其他的功能，但是 JOS 僅僅使用它來定義處理器從用戶態轉向內核態所採用的內核堆棧，由於 JOS 中的內核態指的就是特權級 0，所以處理器用 TSS 中的 ESP0，SS0 字段來指明這個內核堆棧的位置，大小。

在這裏首先總述一下中斷控制流程：

從用戶態進入內核態（第一部分：中斷指令 int T_SYSCALL 之前）：

在理解中斷和系統調用這節時，要從用戶態進入，追蹤並理解在系統調用時中斷和進程切換實現的機制。所有這些機制實現的背景在 trap_init() 和 env_create() 時就已經準備好了，它實際發生的階段其實是位於進程運行階段： env_run(&envs[0])。這個函數是不會返回的，它一直運行：從內核態進入用戶態 - 執行用戶代碼 - 發生系統調用 - 中斷髮生 - 返回 - 進程終止。我們使用 cprintf() 這個例子來進行說明，首先追蹤一下函數調用過程，看看從用戶態程序是怎麼產生系統調用的。

cprintf() 的調用過程：

在用戶程序中常見如下的函數調用過程：

void umain()
{
    cprintf("hello, world\n");
}

上述的 cprintf 函數是在 lib/printf.c 中定義的：

在lib/printf.c中依次定義併發生了如下函數調用：
 
/* 
* va_list型變量是指向參數的指針。用va_start宏可以初始化一個va_list變量，該宏有兩個參數，
* 第一個是va_list變量本身，第二個是可變的參數的前面那個參數，是個固定的參數。
* 利用va_list，把可變個參數的信息歸結到一個參數ap上，便於後續函數調用
* 這些參數依次被放在用戶堆棧區，最高地址處爲可變參數n，fmt的值放在棧頂
*/         
int cprintf(const char *fmt, ...) //注：在kern/printf.c中也有一個一模一樣的cprintf函數
{
    va_list ap;               //va_list是指向可變參數的指針
    int cnt;
    
    va_start(ap, fmt);        //初始化ap，之後ap就指向fmt後面的可變參數（可變參數1）
    cnt = vcprintf(fmt, ap);  //對參數指針初始化之後，調用vcprintf函數
    va_end(ap);               //結束對可變參數的獲取
 
    return cnt;
}
 
/*
* 此時在棧區存放着所需參數，fmt是顯示字符串的指針，ap是可變參數指針。函數參數歸結爲了兩個。
* 在其中又調用vprintfmt函數，vprintfmt函數的第一個參數是個函數指針putch
* putch的功能是輸出一個字符在屏幕上
*/
int vcprintf(const char *fmt, va_list ap)          
{
    struct printbuf b;
    b.idx = 0;
    b.cnt = 0;
    vprintfmt((void*)putch, &b, fmt, ap);    //putch函數被當成了一個參數
    sys_cputs(b.buf, b.idx);
    return b.cnt;
}
 
/*
* 這個函數的功能是輸出一個指定字符到屏幕
* 參數ch代表要輸出的字符，一個int的低八位就是字符的ascii編碼
* printbuf結構體：struct printbuf{
*                   int idx;         //當前緩衝索引
*                   int cnt;         //已經打印的字節數
*                   char buf[256];
*                }
* 這個結構體的作用是最多收集256個字符到緩衝區並進行一次系統調用把它們全部打印到屏幕
*/
static void putch(int ch, struct printbuf *b)
{
    b->buf[b->idx++] = ch;
    if(b->idx == 256-1){
        sys_cputs(b->buf, b->idx);
        b->idx = 0;
    }
    b->cnt++;
}

在 vcprintf 中調用了 vprintfmt 函數，vprintfmt 以 putch 作爲它的一個參數（函數指針），putch 定義在 lib/printf.c 中；vprintfmt 是在 lib/printfmt.c 中定義的：

/*
* 第一個參數是函數指針，用於把一個指定字符輸出到屏幕————
* 而這個函數有兩個參數：第一個參數用於指定被輸出字符；第二個參數指定輸出位置。
* 第二個參數putdat是指向輸出位置地址的指針，即與putch()中第二個參數同義。
* 第三個和第四個參數就是用於指定輸出格式和內容的參數
*/
void vprintfmt(void (*putch)(int, void*), void *putdat, const char *fmt, va_list ap)
{
    ...
}

這個函數的主體部分過長，我沒有寫出來，用下面一個流程圖來表示其邏輯：

總之，在這個函數中需要打印時就調用 putch 函數 (在 lib/printf.c 中)，而 putch 就進行系統調用：調用 (lib/syscall.c 中的)sys_cputs()-->syscall()。

//在lib/syscall.c中發生如下調用：
 
/*
* 用戶態下的sys_cputs函數，正是它調用了int 0x30中斷
* 指針s指向一個buf[256]
* 這裏SYS_cputs是定義在inc/syscall.h中的系統調用號（值爲0）。
*/
void sys_cputs(const char *s, size_t len)
{
    syscall(SYS_cputs, 0, (uint32_t)s, len, 0, 0, 0);    //系統調用
}
 
/*
* 在JOS中所有系統調用通過syscall這個函數進行：執行int T_SYSCALL，把函數參數存入若干指定的寄存器
* 並指定函數返回值返回到寄存器ax中
* 用第一個參數num來確定到底是哪個系統調用
* 參數num == SYS_cputs == 0，check == 0，a1 == b->buf， a2 == b->idx，剩下a3、a4、a5都爲0
*/
static inline int32_t
syscall(int num, int check, uint32_t a1, uint32_t a2, uint32_t a3, uint32_t a4, uint32_t a5){
    int32_t ret;
    asm volatile("int %1\n"              //彙編指令模板，%1是佔位符，對應後面的T_SYSCALL
                 : "=a" (ret)            //=表示在彙編裏只能改變該C變量的值，而不能取它的值
                                         //ret值與%ax相聯繫，即指令執行完後ax的值存入變量ret
                 : "i" (T_SYSCALL),      //中斷向量T_SYSCALL，是立即數
                   "a" (num),            //輸入參數num（值爲0），指令執行前先將num變量的值存入%ax
                   "d" (a1),             //輸入參數a1（b->buf），指令執行前先將a1變量的值存入%dx
                   "c" (a2),             //輸入參數a2（b->idx）
                   "b" (a3),             //之後三個參數都爲0
                   "D" (a4),
                   "S" (a5)
                 : "cc", "memory");
    if(check && ret > 0)
       panic("syscall %d returned %d (>0)", num, ret);
    return ret;
}

經過以上一番折騰，系統進入中斷（即執行彙編命令 int T_SYSCALL）。OS 的中斷處理過程開始執行。它根據中斷號和參數調用內核的處理函數, 也是 sys_cputs 來處理。

在 int 0x30 處打斷點並查看當前寄存器的值，如下圖：

在 syscall() 中，應用程序會把系統調用號以及系統調用的參數放到寄存器中，在切換到內核態之後再將它們放到內核堆棧上。系統調用號存放到 %eax 中，參數則存放在 %edx, %ecx, %ebx, %edi, 和 %esi 中。內核會把返回值送到 %eax 中。問題：要是參數特別多，寄存器不夠放怎麼辦呢？

這個系統調用對所有的應用程序都是一樣的，區別僅在於傳進去的中斷向量值以及需要傳遞的應用程序的函數參數。

從用戶態進入內核態（第二部分：中斷指令 int T_SYSCALL 之後）：

在上面的 systcall() 後，CPU 執行 int 0x30 中斷指令，根據在 IDT 中找到的中斷函數地址，就直接跳往該中斷函數。

由前述我們知道，IDTR + 中斷向量 (interrupt vector) --> 中斷門 (位於 IDT 中) --> 中斷處理程序。大致過程如下圖所示：

我們前面提到過，中斷和進程切換機制實現的背景在 trap_init() 和 env_create() 時就已經準備好了。

start (kern/entry.S)
i386_init (kern/init.c)
    cons_init
    mem_init
    env_init
    trap_init         //中斷的初始化
        SETGATE(idt[T_SYSCALL], 0, GD_KT, t_syscall, 3);
        trap_init_percpu
    env_create
        env_alloc
            env_setup_vm
        load_icode
            region_alloc
    env_run
        env_pop_tf    //從這裏之後便從內核進入用戶進程，
                      //如果之後用戶進程又產生中斷，則利用我們在trap_init中設置好的切換機制
                      //陷入內核並跳往中斷處理函數，處理完之後再切出內核回到用戶空間

下面我們再詳細進行一下說明：

在 kern/trap.c 中的函數 void trap_init(){} 中，使用宏 SETGATE(idt[T_SYSCALL], 0, GD_KT, t_syscall, 3) 將中斷向量 T_SYSCALL 與中斷處理函數 t_syscall 的地址聯繫起來了。0 表示這個是一箇中斷門；GD_KT 是對應內核代碼段的全局描述符號；3 表示中斷描述符優先級 (用戶級)。而 t_syscall 函數是已經在 trapentry.S 中定義好了的函數，那些函數會直到發生了中斷才被運行 (儘管它們是作爲內核代碼的一部分，早就被編譯好了處在內核中)。

在 kern/trap.c 中 trap_init() 中調用了一個 trap_init_percpu() 函數：

trap_init_percpu
    {
    //
    ts.ts_esp0 = KSTACKTOP
    ts.ts_ss0 = GD_KT;
    ts.ts_iomb = sizeof(struct Taskstate);
    //
    gdt[GD_TSS0 >> 3] = SEG16(STS_T32A, (uint32_t)(&ts), sizeof(struct Taskstate)-1, 0);
    gdt[GD_TSS0 >> 3].sd_s = 0;
    //
    ltr(GD_TSS0);
    lidt(&idt_pd);
    }

在 kern/trapentry.S 中，使用宏 TRAPHANDLER_NOEC(name, num) 定義好了全局可見的 trap 處理函數。每個中斷向量都有自己的一個處理函數，但它們都先執行一些統一的操作：包括把中斷向量入棧，再跳往_alltraps 處。

在執行完中斷指令 int 0x30 後，執行的第一條指令就是在 trapentry.S 中用 TRAPHANDLER_NOEC 定義的指令：push 0x30。然後執行 jmp _alltraps。

_alltraps 處也是統一的一些操作：主要是把寄存器按照 Trapframe 結構的順序入棧。

所以從用戶態陷入內核後，中斷和系統調用過程爲：

你所實現的 _alltraps 應該：

Trapframe 用於保存當前進程的寄存器值。無論是新建一個進程還是進程中斷陷入內核時，都會設置當前進程的 env_tf 結構體，以便記錄進程的當時狀態。

struct Trapframe {
    struct PushRegs tf_regs;
    uint16_t tf_es;
    uint16_t tf_padding1;
    uint16_t tf_ds;
    uint16_t tf_padding2;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding3;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding4;
} __attribute__((packed));

我們在之前講過，從內核態進入用戶態分兩種情況：1）第一種是啓動系統後第一次進入用戶態；2）第二種是某個進程發生中斷，進入內核態執行中斷處理程序後，又從內核態恢復到用戶態。在這兩種情況中，Trapframe 的作用都是用於從內核進入用戶態時爲進程佈置好寄存器。在情況 1）中是做一些初始化工作，初始化第一個要運行進程的 Trapeframe；而在情況 2）中則是需要在發生中斷時先保留好該進程的 Trapeframe。

對於第一種情況：主要是在函數 env_alloc() 中對新建的進程的 e->env_tf 進行了初始化工作，在之後的 env_pop_tf() 函數中把該內存區域當作棧來使用；

對於第二張情況：主要是在 t_syscall 和_alltraps 中將用戶進程的寄存器值壓入內核棧，注意在陷入內核之前已經由 TSS 中的 SS0，ESP0 來指定內核堆棧區。此時，curenv->env_tf 還依然是之前的初始化值，之後，在 trap() 中需要將內核棧上的 Trap_frame 拷貝給 curenv->env_tf 從而記錄陷入內核前進程的上下文。

回到我們的 cprintf 的例子，發生中斷後，內核根據中斷向量分發到對應的中斷處理程序 syscall 處。執行：

//實參是int 0x30後首先壓入內核堆棧的通用寄存器的值，它以trapframe中tf_regs結構的順序存放在內核棧上
syscall(tf->tf_regs.reg_eax,
        tf->tf_regs.reg_edx,
        tf->tf_regs.reg_ecx,
        tf->tf_regs.reg_ebx,
        tf->tf_regs.reg_edi,
        tf->tf_regs.reg_esi);

實際上，用戶代碼是在 lib/sys_cputs() 中調用：lib/syscall(SYS_cputs, 0, (uint32_t)s, len, 0, 0, 0); ，然後在用戶態的 syscall() 中發起中斷，經一系列陷入內核操作指令後跳往執行 kern/syscall(uint32_t syscallno, uint32_t a1, a2, a3, a4, a5)，如下：

int32_t syscall(uint32_t syscallno, uint32_t a1, uint32_t a1, uint32_t a2, uint32_t a3, uint32_t a4, uint32_t a5){
    switch(syscallno){
        case (SYS_cputs):
            sys_cputs((const char*)a1, a2);
            return 0;
        case (SYS_cgets):
            return sys_cgetc();
        case (SYS_getenvid):
            return sys_getenvid();
        case (SYS_env_destroy):
            return sys_env_destroy(a1);
    }
}

再執行 sys_cputs()，而它又調用 kern/cprintf()。

注：這裏還有點混亂，有空再看一下

三、實時調度算法

實時系統是一種必須提供時序可預測性的系統。實時系統必須考慮每個具體任務的相應時間必須符合要求，即每個任務在什麼時間之前完成，而無須考慮如何降低整個系統的響應時間或吞吐率。

3.1EDF 調度算法 Earlist Deadline First

最早截止的任務先做。動態地計算每個任務的截止時間並動態調節優先級。如果需要，還會對當前進程進行搶佔。

EDF 調度算法就是 STCF 算法變化來的。如果將 STCF 算法的任務所需執行時間變爲截止時間，則搶佔式 STCF 算法就是 EDF 調度算法。

雖然 EDF 算法在理論上是最優的，但動態計算截止時間和動態搶佔 CPU 均要消耗系統資源。

3.2RMS 調度算法 Rate Monotonic Scheduling

在進行調度前先計算出所有任務的優先級，然後按照計算出來的優先級進行調度，任務執行中間既不接收新的進程，也不進行優先級的調整或進行 CPU 搶佔。

缺點是不靈活。

對於 RMS 算法來說，一個重要的任務是判斷一個任務組能否調度。而這個判斷並不是容易做的。具體來說，一個系統裏所有任務的截止時間如果想都得到滿足，則這些任務必須滿足下面的條件：

n 爲任務是數量，ci 爲第 i 個任務的執行時間，pi 爲第 i 個任務的釋放週期。當 n 趨於無窮時，U=ln2。

根據上述公式，如果 CPU 利用率在 ln2 以下時，所有任務的截止時間均可滿足。因爲此時系統還剩下約 30% 的 CPU 時間。這個時間可以用來處理一些非實時任務。

RMS 算法爲靜態最優算法。即如果任何靜態優先級算法可以滿足一組任務的截止時間，則 RMS 算法也必能滿足。

3.3 進程調度的過程

  1. 因時序或外部中斷或進程掛起而導致操作系統獲得 CPU 控制權

  2. 操作系統在所有就緒的進程中按照某種算法遴選進程

  3. 如果選中的是非當前進程，則操作系統將當前進程狀態予以保護

  4. 將選中的進程環境佈置好（設置寄存器、棧指針、狀態字等）

  5. 跳轉到選中的進程

四、進程通信

進程之間的交互稱爲進程間通信（Inter-Process Communication，IPC）。

4.1 進程對白：管道、記名管道、套接字

進程對白就是一個進程發出某種數據信息， 另外一方接收數據信息，而這些數據信息通過一片共享的存儲空間進行傳遞。

管道

在這種方式下，一個進程向這片存儲空間的一端寫入信息，另一個進程從存儲空間的另外一端讀取信息。這看上去就像管道。管道所佔的空間既可以是內存，也可以是磁盤。要創建一個管道，一個進程只需調用管道創建的系統調用即可。該系統調用所做的事情就是在某種存儲介質上劃出一片空間，賦給其中一個進程寫的權利，另一個進程讀的權利即可。

從根本上說，管道是一個線性字節數組，類似文件，可以使用文件讀寫的方式進行訪問。但卻不是文件。因爲通過文件系統看不到管道的存在。管道可以設在內存裏，而文件很少設在內存裏（當然，有研究人員在研發基於內存的文件系統，但這個還不是主流）。

創建管道在殼命令行下和在程序裏是不同的。

管道的一個重要特點是使用管道的兩個進程之間必須存在某種關係。

記名管道

如果要在兩個不相關的進程（如兩個不同進程裏面的進程）之間進行管道通信，則需要使用記名管道。顧名思義，命名管道是一個有名字的通信管道。記名管道與文件系統共享一個名字空間，即我們可以從文件系統中看到記名管道。也就是說，記名管道的名字不能與文件系統裏的任何文件名重名。

一個進程創建一個記名管道後，另外一個進程可使用 open 來打開這個管道（無名管道則不能使用 open 操作），從而與另外一端進行交流。

記名管道的名稱由兩部分組成：計算機名和管道名，例如＼＼[主機名]＼管道＼[管道名]＼。對於同一主機來講，允許有多個同一命名管道的實例並且可以由不同的進程打開，但是不同的管道都有屬於自己的管道緩衝區而且有自己的通信環境，互不影響。命名管道可以支持多個客戶端連接一個服務器端。命名管道客戶端
不但可以與本機上的服務器通信也可以同其他主機上的服務器通信。

管道和記名管道雖然具有簡單、無需特殊設計（指應用程序方面）就可以和另外一個進程進行通信的優點， 但其缺點也很明顯。首先是管道和記名管道並不是所有操作系統都支持。主要支持管道通信方式的是 UNIX 和類 UNIX（如 Linux）的操作系統。這樣，如果需要在其他操作系統上進行通信，管道機制就多半會力不從心了。其次，管道通信需要在相關的進程間進行（無名管道），或者需要知道按名字來打開（記名管道）， 而這在某些時候會十分不便。

蟲洞：套接字

套接字（socket）是另外一種可以用於進程間通信的機制。套接字首先在 BSD 操作系統中出現，隨後幾乎滲透到所有主流操作系統中。套接字的功能非常強大，可以支持不同層面、不同應用、跨網絡的通信。使用套接字進行通信需要雙方均創建一個套接字，其中一方作爲服務器方，另外一方作爲客戶方。服務器方必須先創建一個服務區套接字，然後在該套接字上進行監聽，等待遠方的連接請求。欲與服務器通信的客戶則創建 一個客戶套接字，然後向服務區套接字發送連接請求。服務器套接字在收到連接請求後，將在服務器方機器上創建一個客戶套接字，與遠方的客戶機上的客戶套接字形成點到點的通信通道。之後，客戶方和服務器方就可以通過 send 和 recv 命令在這個創建的套接字通道上進行交流了。

使用套接字進行通信稍微有點複雜，我們下面以一個網頁瀏覽的例子對套接字這種通信方式予以說明。對於 一個網站來說，要想提供正常的網頁瀏覽服務，其網站服務器需要首先創建一個服務區套接字，作爲外界與本服務器的通信信道。爲了使該信道爲外人所知，我們通常將該服務區套接字與某公共主機的一個衆所周知
的端口進行綁定。

#創建一個INET的流套接字
serversocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM);
#將套接字與某公共主機的一個衆所周知的端口綁定
serversocket.bind(socket.gethostname(),80);

進行套接字和端口綁定的語句裏的 socket.gethostname() 用來將套接字向外界公開。如果將該語句的使用 socket.gethostname() 改爲＇＇或者＇localhost 或者某個具體的 IP 地址（如 120.121.4.1），則該服務區套接字將被限制在本地機器上使用。

在創建了服務區套接字並將其向外界公開後，網站服務器就可以在該套接字上進行監聽。

serversocket.listen(5); // 將套接字變爲一個服務區套接字

將端口上的等待隊列長度限制爲 5，即超過 5 個的請求將被拒絕。

到這裏，服務器方的設置就宣告結束。

對於客戶方來說，如要訪問上述網站，則需要點擊該網站的網址。在點擊網址後（我們這裏假定該網站網址爲 http://www.sjtu.edu.cn），客戶機上的網絡瀏覽器進行若干步操作：

#創建一個INET的流套接字
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM);
#將套接字與某公共主機的一個衆所周知的端口綁定
s.connect("www.sjtu.edu.cn",80);

s.connect 命令將向服務器 http://www.sjtu.edu.cn 在端口 80 打開的服務器套接字發送連接請求。而服務器端在接收到該連接請求後，將生成一個新的客戶端套接字與該客戶端套接字對接，從而建立一個套接字通信信道。
網站服務器上運行的主循環

while (true)
{
	(clientsocket, address) = serversocket.accept(); // 接收外部連接請求
	// 對clientsocket進行相關操作，例如創建一個新進程來處理客戶請求
	newct = client_thread(clientsocket);
	newct.run();
}

至此，套接字通信信道成功創建。客戶端程序可以使用套接字 s 來發送請求、索取網頁，而服務器端則使用套接字 clientsocket 進行發送和接收消息。

這裏需要指出的是服務區套接字既不發送數據，也不接收數據（指不接收正常的用戶數據，而不是連接請求數據），而僅僅生產出 “客戶” 套接字。當其他（遠方）的客戶套接字發出一個連接請求時，我們就創建一個客戶套接字。一旦創建客戶套接字 clientsocket，與客戶的通信任務就交給了這個剛剛創建的客戶套接字。而
原本的服務器套接字 serversocket 則回到其原來的監聽操作上。

套接字由於其功能強大而獲得了很大發展，並出現了許多種類。不同的操作系統均支持或實現了某種套接字功能。例如按照傳輸媒介是否爲本地，套接字可以分爲本地（UNIX 域）套接字和網域套接字。而網域套接字又按照其提供的數據傳輸特性分爲幾個大類，分別是：

套接字從某種程度上來說非常繁雜，各種操作系統對其處理並不完全一樣。因此，如要了解某個特定套接字實現，讀者需要查閱關於該套接字實現的具體手冊或相關文檔。

4.2 進程電報：信號

管道和套接字的缺點：

那麼信號是什麼呢？在計算機裏，信號就是一個內核對象，或者說是一個內核數據結構。發送方將該數據結構的內容填好，並指明該信號的目標進程後，發出特定的軟件中斷。操作系統接收到特定的中斷請求後，知道是有進程要發送信號，於是到特定的內核數據結構裏查找信號接收方，並進行通知。接到通知的進程則對信號進行相應處理。

4.3 進程旗語：信號量

在計算機裏，信號量實際上就是一個簡單整數。一個進程在信號變爲 0 或者 1 的情況下推進，並且將信號變爲 1 或 0 來防止別的進程推進。當進程完成任務後，則將信號再改變爲 0 或 1，從而允許其他進程執行。需要注意的是，信號量不只是一種通信機制，更是一種同步機制。

4.4 進程擁抱：共享內存

共享內存就是兩個進程共同擁有同一片內存。對於這片內存中的任何內容，二者均可以訪問。要使用共享內存進行通信，一個進程首先需要創建一片內存空間專門作爲通信用，而其他進程則將該片內存映射到自己的（虛擬）地址空間。這樣，讀寫自己地址空間中對應共享內存的區域時，就是在和其他進程進行通信。

與管道的區別：

缺點：

這裏需要注意的是，使用全局變量在同一個進程的進程間實現通信不稱爲共享內存。

4.5 信件發送：消息隊列

與管道的區別：

4.6 其他通信機制

除了上面介紹的主流通信方式外，有些操作系統還提供了一些其所特有的通信機制，例如 Windows 支持的進程通信方式就有所謂的剪貼板（clipboard）、COM/DCOM、動態數據交換（DDE）、郵箱（mailslots）；而 Solaris 則有所謂的 Solaris 門機制，讓客戶通過輕量級（16KB）系統調用使用服務器的服務。

雖然進程之間的通信機制繁多，且每種機制都有着自己的特性，但歸根結底都來源於 AT＆T 的 UNIX V 系統。該系統在 1983 年加入了對共享內存、信號量和消息隊列的支持。而這三者就是衆所周知的 System VIPC（POSIX IPC 也是源於該系統併成爲當前 IPC 的標準）。因此，雖然不同操作系統的 IPC 機制可能不盡相同，但其基本原理則並無大的區別。如果需要了解具體操作系統的 IPC 機制的實現，讀者可以閱讀相關的操作系統內核教程。

五、進程實現原理 (基於 linux0.11 內核)

Linux 內核是如何初始化操作系統，並開始運行第一個程序呢？

我們都知道，系統啓動過程爲：bootsect.s —>setup.s —>head.s。姑且不去討論這些彙編源程序的功能，假設操作系統的 pc 指正已經運行到了 head.s 處的部分代碼，這裏做下仔細的研究。

目標代碼如下 (linux/boot/head.s)：

17：startup_32:
18：    movl $0x10,%eax
......
48：    call check_x87
49：    jmp after_page_tables #跳轉到135行
......
135：after_page_tables:
136：    pushl $0
137：    pushl $0
138：    pushl $0
139：    pushl $L6
140：    pushl $_main
141：    jmp setup_paging #跳轉到198行
142：L6:
143：    jmp L6;
......
198：setup_paging:
199：    movl $1024*5,%ecx
......
217：    movl %eax,%cr0
218：    ret

忽略其他細節問題，當 head 程序執行到第 49 行時，將跳轉到 135 行代碼出運行。在第 135 行代碼處，便是 head.s 調用 init 中 main 函數的核心。回顧 c 函數與彙編之間相互調用的知識可知，內核棧中存在：

當代碼繼續跳轉後，會進入 198 行代碼，直到程序運行至 ret，調用返回。此時，內核棧中指向 main 函數將彈棧，pc 指正自動指向 main 函數地址入口出，從而開始執行 main 函數。其次，傳入 main 函數中的三個參數均爲 0（初始化 main 函數，無需傳參，因此這裏默認爲 0）。

目標代碼如下 (linux/init/main.c)：

void main(void){
    .......
    move_to_user_mode();//移到用戶模式下執行  什麼叫做移動到用戶模式下？未解 o(︶︿︶)o 
    if(!fork()){
        init();
    }
    for(;;)
        __asm__("int $0x80"::"a"(__NR_pause):"ax");
}

main 函數是系統創建的第一個進程，作爲第一個進程，它有自己的堆棧段，數據段，代碼段等。在進入用戶模式下後，便調用了 fork 函數來創建新的子進程，創建完進程後，立馬進入暫停態。而第二個進程將在 init() 函數下繼續運行。init() 函數中，便是用來調用 linux 的 shell 腳本程序，從而可以與用戶進行交互。那麼問題來了，fork 是如何做到進程的創建的呢？系統如何讓兩個進程或多個進程併發的執行呢？進程實現的原理是什麼？

進程實現的原理

一個最簡單的想法，或者說是最初的想法便是讓 pc 指針分時的進行地址跳轉，這的確是最核心最正確的解決辦法，可具體該怎樣實現？在用戶態下，用戶進行函數調用，是需要把函數參數，函數地址，局部變量等進行壓棧的。而函數調用其實本事就是個讓 pc 指針變化的事。請看圖：

A 函數運行一段時間後，必然會轉入 B 函數，且調用 Yield 函數，在進行地址跳轉之前，先將該程序下兩個地址進行壓棧。而一旦調 Yield 函數，做的操作便是，將 A 程序的用戶棧和將被調用的 B 程序的用戶棧進行切換。Yield 的具體實現也正是這麼做的，交換了兩個線程控制塊。由於現在 esp 指向了 C 函數的入口地址，操作系統便開始執行 C 函數了，同樣一旦運行到 D 函數，再次調用 Yield，進行用戶棧切換，這時，當前 esp=1000，當 Yield 函數調用結束，即 ret 返回，自動彈棧。PC=204，返回 A 程序執行。至此，兩個線程便能交替的執行任務了。

注意：Liunx 內核中，並沒有實現線程的機制，但爲了闡述進程的實現原理，理解線程的實現原理是必要的。也正如我們在操作系統學到的那樣：

線程是獨立調度的基本單位，用戶級線程沒有進入系統內核，調用計算機資源，僅僅在用戶態下運行即可。

進程之所以是資源分配的基本單位，除了要完成用戶態棧的切換，還需要內核棧的切換，其次進程的創建 fork 函數是系統調用，它將通過中斷進入系統，調度計算機的資源。

所以，通過上述總結，進程調度的實現原理就是在線程調度的基礎上，加上了內核棧與用戶棧的關聯步驟，並且在內核態進行兩個棧的切換，即 PCB 的切換。來分析代碼咯！

目標代碼（linux/kernel/sys_call.s）：

_system_call:  
cmpl $nr_system_calls-1,%eax # 調用號如果超出範圍的話就在eax 中置-1 並退出。  
ja bad_sys_call  
push %ds # 保存原段寄存器值。  
push %es  
push %fs  
pushl %edx # ebx,ecx,edx 中放着系統調用相應的C 語言函數的調用參數。  
pushl %ecx # push %ebx,%ecx,%edx as parameters  
pushl %ebx # to the system call  
movl $0x10,%edx # set up ds,es to kernel space  
mov %dx,%ds # ds,es 指向內核數據段(全局描述符表中數據段描述符)。  
mov %dx,%es  
movl $0x17,%edx # fs points to local data space  
mov %dx,%fs # fs 指向局部數據段(局部描述符表中數據段描述符)。  
# 下面這句操作數的含義是：調用地址 = _sys_call_table + %eax * 4。參見列表後的說明。  
# 對應的C 程序中的sys_call_table 在include/linux/sys.h 中，其中定義了一個包括72 個  
# 系統調用C 處理函數的地址數組表。  
call _sys_call_table(,%eax,4)  
pushl %eax # 把系統調用號入棧。  
movl _current,%eax # 取當前任務（進程）數據結構地址??eax。  
# 下面97-100 行查看當前任務的運行狀態。如果不在就緒狀態(state 不等於0)就去執行調度程序。  
# 如果該任務在就緒狀態但counter[??]值等於0，則也去執行調度程序。  
cmpl $0,state(%eax) # state  
jne reschedule  
cmpl $0,counter(%eax) # counter  
je reschedule

在系統調用這章，詳細討論了 sys_call_table 的作用。今天我們便要研究透這段代碼（這裏插段自己學習的經驗總結，遇到源碼看不懂的問題，沒關係，遇到知識瓶頸再正常不過了，不要花太多時間硬啃，可以放一放。隨着你每天日積月累的總結，當時看不懂不代表現在看不懂，當再次回顧代碼時，可以把新學的內容套用上，便能慢慢研究透源代碼了）。

代碼 4-9 行，進行了一系列的壓棧操作，這便是所謂的對當前操作系統狀態進行一個保存，記錄當前進程運行的信息。內核棧如下：

小夥伴可能要問了，4-9 行明明沒有 ss:sp、EFLAGS、ret 的內容啊，怎麼會出現在內核棧呢。還記得前文所述的進程與線程的區別嘛？進程是通過中斷來完成創建的，因此在調用 fork 函數時，便自動產生軟中斷，一旦中斷髮生，便由硬件自動返程 ss:sp、EFLAGS、ret 的壓棧。

仔細看上圖，ss:sp 指向的便是進程在用戶態下的用戶棧地址。這也就實現了進程的內核棧與用戶棧的關聯。

注意：

切換到內核態後，便可以執行 sys_fork 函數了。同樣在該目標代碼中：

.align 2
_sys_fork:
    call _find_empty_process
    testl %eax,%eax
    js lf
    push %gs
    pushl %esi
    pushl %edi
    pushl %ebp
    pushl %eax
    call _copy_process
    addl $20,%esp
l:  ret

首先調用 find-empty-process 函數，具體代碼不再闡述了，可以翻看 linux 內核剖析。具體位置在 linux/kernel/fork.c 下，該函數的主要作用爲: last_pid 與當前系統內的進程號進行比較，如果當前進程號 = last_pid 且當前任務處於運行狀態，則 last_pid++；直到找到一個可用的進程號，然後返回，此時 eax 存放的內容便是 last_pid。

函數返回可能會發生兩種情況：

目標代碼（linux/kernel/fork.c）：

int copy_process(int nr,long ebp,long edi,long esi,long gs,long none,
        long ebx,long ecx,long edx,
        long fs,long es,long ds,
        long eip,long cs,long eflags,long esp,long ss)
{
    struct task_struct *p;
    int i;
    struct file *f;
    p = (struct task_struct *) get_free_page();
    if (!p)
        return -EAGAIN;
    task[nr] = p;
    *p = *current;    /* NOTE! this doesn't copy the supervisor stack */
    p->state = TASK_UNINTERRUPTIBLE; //進程在建立過程中爲防止被調度，設置爲不可中斷等待。
    p->pid = last_pid; //進程的id
    p->father = current->pid; //進程的父進程id
    p->counter = p->priority; //進程的優先級，這個只能通過sys_nice來修改。
    ......
    p->tss.eax=0            //請思考作用
    ......
    set_tss_desc(gdt+(nr<<1)+FIRST_TSS_ENTRY,&(p->tss));
    set_ldt_desc(gdt+(nr<<1)+FIRST_LDT_ENTRY,&(p->ldt));
    p->state = TASK_RUNNING;    /* do this last, just in case 到此進程準備完畢，可以運行，則狀態修改爲就緒 */

    return last_pid; //返回新建子進程的ID
}

代碼請注意：p->tss.eax=0，作用是什麼？

copy_process 函數所傳入的參數對應爲當前系統內核棧的參數，即 nr=（%eax），ebp=（%ebp）…. 依此類推 ss=（%ss）。該函數的主要作用是：

創建新的 PCB，並且給該進程控制塊分配新的物理內存

初始化 PCB 的內容，並且將父進程的內核棧信息全部複製給子進程的內核棧。

函數成功調用後，最終返回系統進程調用號。至此，子進程如果不出意外便算創建成功了。函數返回後，便又回到了 sys_call 的代碼段，我們繼續分析接下來的代碼。

需要了解的是，子進程雖然被創建了，但目前處於就緒狀態，它只是存在於內存的某處，並沒有開始執行調度。因此，此時 copy-process 返回的便是子進程的 pid，顯然 eax=pid 且 ！0。值得注意的是，現在這個狀態還是父進程的運行態。它將執行一系列符合條件的進程調度操作，如果幸運的話，可能也不會執行調度，直接彈棧，中斷返回。

目標代碼如下 (linux/init/main.c)：

void main(void){
        .......
        move_to_user_mode();//移到用戶模式下執行  什麼叫做移動到用戶模式下？未解 o(︶︿︶)o 
        if(!fork()){
            init();
        }
        for(;;)
            __asm__("int $0x80"::"a"(__NR_pause):"ax");
    }

還記得操作系統初始化的這段代碼嘛，這裏便有一個 fork 調用，接着上面的分析，調用 fork 後，父進程的 pid！=0，所以將跳過 if 語句往下執行，這裏讓父進程通過 sys_pause 強制暫停了。再次進入中斷後，操作系統開始尋找內核裏存在的就緒進程，這時候發現有一個新的就緒態的子進程在默默的等待，因此通過 jne reschedule 執行函數的調度。reschedule 將接着繼續調用 schedule。

目標代碼（linux/kernel/sched.c）：

void schedule(void){
    int i,next,c;
    .......
    switch_to(next);
}

進入調度函數後，先忽略前述的某些優先級調度算法，直接轉入 switch_to 函數，你會發現它是通過建立映象來完成內核棧的切換的。而內核棧切換是進程調度的核心的核心，switch_to 代碼的工作原理是通過 TR 寄存器來找到當前的 tss 段，當寄存器存放的內容發生改變時，便會導致 TR 指向的 tss 的內容寫入 CPU 的所有寄存器當中，而將原來的寄存器的內容保存在原來的 tss 中。

代碼分析：

執行長跳轉 ljmp，ljmp 可分爲兩步：

switch_to(n) 一旦完成切換，內核棧的內容便是子進程的內容了。還記得 fork 出 p->tss.eax 爲什麼等於 0 了嘛，此時切換的子進程 tss.eax=0，那就意味着 swicth_to 後，cpu 寄存器的 eax=0，那麼等中斷返回後，！fork() 條件就變成了真！還記得子進程是複製了父進程內核棧的信息了嘛，所以當子進程中斷返回後，不就是返回到 if 後面一條語句執行嗎！so，子進程便能在操作系統開始它自己的工作了。。。o(∩_∩)o

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/7hw2sgIZ1vqY9ZpazynlDw

猜你喜歡