第一個程式HelloWorld運行背後，操作系統都在做些什麼 ...
轉載地址：https://my.oschina.net/hosee/blog/673628?p=%7b%7bcurrentPage+1%7d%7d
本文就將系統性的串聯起那些知識點，方便複習和回顧。本文適合已經有操作系統基礎的同學，一起回顧知識，本文並不詳細講解每個演算法，本文意在知識串聯。
通過一個例子來串聯所有的知識點：
寫了一個C語言程式：
#include
main()
{
puts("Hello World!\n");
}
目的是希望在屏幕中看到Hello World的字樣。
那麼在運行這個C語言程式時，操作系統做了什麼呢？
1. 首先要啟動程式執行，用戶要告訴操作系統執行程式
如何告知：
- 可以滑鼠雙擊程式
- 命令行輸入命令
- ……
2. 操作系統知道用戶的請求之後，就會根據用戶提供的文件名到磁碟上找到這個程式的相關信息，找到信息之後，會去檢查這個程式是不是一個可執行文件，如果是可執行文件，操作系統會根據程式首部信息來確定代碼和數據在可執行文件中的位置並計算出對應的磁碟塊地址。
文件系統是指操作系統中統一管理信息資源的一種軟體，管理文件的存儲、檢索、更新，提供安全可靠的共用和保護手段，並且方便用戶使用。
文件按性質和用途分類：普通文件，目錄文件，特殊文件（設備文件），管道文件，套接字。
文件的存儲介質：磁碟（包括SSD），磁帶，光碟，U盤……
物理塊是信息存儲、傳輸、分配的獨立單位。存儲設備劃分為大小相等的物理塊，統一編號。
一次訪問磁碟的請求：
- 尋道：磁頭移動定位到指定磁軌。
- 旋轉延遲：等待指定扇區從磁頭下旋轉經過。
- 數據傳輸：數據在磁碟與記憶體之間的實際傳輸。
SSD沒有尋道和旋轉延遲的時間消耗，所以速度快。
文件控制塊：為管理文件而設置的數據結構，保存管理文件所需的所有有關信息。
常用屬性：文件名，文件號，文件大小，文件地址，創建時間，最後修改時間，最後訪問時間，保護，口令，創建者，當前擁有者，文件類型，共用計數，各種標誌。
文件目錄：統一管理每個文件的元數據，以支持文件名到文件物理地址的轉換。將所有文件的管理信息組織在一起，即構成文件目錄。
目錄文件：將文件目錄以文件的形式存放在磁碟上。
目錄項：構成文件目錄的基本單元，目錄項可以是FCB，目錄是文件控制塊的有序集合。
文件的物理結構：文件在存儲介質上的存放方式。
物理結構：
1. 連續結構：文件的信息存放在若幹連續的物理塊中。
FCB中保存文件塊的起始塊號和長度。
優點：支持隨機存取和順序存取，所需的尋道時間和尋道次數最少，可以同時讀入多個塊，檢索一個塊很容易。
缺點：文件不能動態增長，不利於文件插入和刪除，有外部碎片（緊縮技術）
2. 鏈接結構：一個文件的信息存放在若幹不連續的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊。
FCB只需要保存起始塊號
優點：提高了磁碟空間利用率，有利於文件的插入和刪除，有利於文件動態擴充。
缺點：存取速度慢，不適於隨機存取，可靠性問題（如指針出錯），更多的尋道次數和尋道時間，鏈接指針占有一定空間。
可以對鏈接結構進行變形：文件分配表（FAT），早期windows和U盤使用的結構。
FAT存放了所有的鏈接指針，每一個物理塊對應FAT的一行。
0表示空閑物理塊，-1表示文件最後一塊。
文件的起始塊號保存在文件的FCB中。
3. 索引結構：一個文件的信息存放在若幹不連續物理塊中，系統為每個文件建立一個專用數據結構——索引表，並將這些物理塊的塊號存放在索引表中。
索引表就是磁碟塊地址數組，其中第i個條目指向文件的第i塊。
FCB中用一個欄位保存索引表的位置。
索引結構優點：保持了鏈接結構的優點，解決了鏈接結構的缺點，既能順序存取，又能隨機存取，滿足了文件動態增長，插入刪除的要求，能充分利用磁碟。
缺點：較多的尋道時間和尋道次數，索引表本身帶來了系統開銷。
索引表有可能很大，需要多個物理塊保存，就有多級索引和綜合索引。
多級索引：
UNIX三級索引結構：
訪問一個文件：文件名->文件目錄->FCB->磁碟
提高文件系統性能：
磁碟調度：當有多個訪盤請求等待時，採用一定的策略，對這些請求的服務順序調整安排。降低平均磁碟服務時間，公平，高效。
磁碟調度演算法：
- 先來先服務（FCFS），按訪問請求到達的先後順序服務。簡單，公平，但是效率不高，相臨兩次請求可能會造成最內到最外柱面尋道，使磁頭反覆移動，增加了服務時間，對機械不利。
- 最短尋道時間優先，優先選擇距當前磁頭最近的訪問請求進行服務，主要考慮尋道優先。改善了磁碟平均服務時間，但是造成某些訪問請求長期等待得不到服務。
- 掃描演算法（SCAN），當設備無訪問請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在移動過程中對遇到的訪問請求進行服務，然後判斷該方向上是否還有訪問請求，如果有則繼續
- 單向掃描調度演算法（C-SCAN），總是從0號柱面開始向里掃描，移動到達最後一個柱面後，立即帶動讀寫磁頭快速返回到0號柱面。減少了新請求的最大延遲。
- N-step-SCAN策略，把磁碟請求隊列分成長度為N的子隊列，每一次用SCAN處理一個子隊列，剋服“磁頭臂的粘性”。
- FSCAN，使用兩個子隊列，掃描開始時，所有請求都在一個隊列中，而另一個隊列為空。掃描過程中，所有新到的請求都保存在另一個隊列中，對新請求的服務延遲到處理完所有老請求之後。
- 旋轉調度演算法，根據延遲時間來決定執行次序的調度。三種情況：1. 若幹等待訪問者請求訪問同一磁頭上的不同扇區，2. 若幹等待訪問者請求訪問不同磁頭上的不同編號的扇區，3. 若幹等待訪問者請求訪問不同磁頭上具有相同的扇區。
3. 為了執行這個helloworld程式，操作系統會創建一個新的進程，並將該程式的可執行文件格式映射到該進程結構，表示由該進程來執行這個程式。
進程是具有獨立功能的程式關於某個數據集合上的一次運行活動，是系統進行資源分配和調度的獨立單位。
PCB，進程式控制制塊，操作系統用於管理控制進程的一個專門數據結構，進程與PCB是一一對應的。
PCB中有：
進程描述信息：進程標識符（唯一），進程名，用戶標識符，進程組關係
進程式控制制信息：優先順序，代碼執行入口地址，程式的磁碟地址，運行統計信息（執行時間，頁面調度），進程間同步和通信，進程的隊列指針，進程的消息隊列指針。
所擁有的資源和使用情況：虛擬地址空間的狀況，打開文件列表
CPU現場信息：寄存器值（通用寄存器，程式計數器PC，進程狀態字PSW，棧指針），指向該進程頁表的指針。
進程表：所有PCB的集合。
進程狀態：
操作系統為每一類進程（就緒、等待……）建立一個或多個隊列，隊列元素為PCB，伴隨進程狀態改變，其PCB從一個隊列進入另一個隊列。
進程的創建：
- 給新進程分配一個唯一標識以及PCB
- 為進程分配地址空間
- 初始化PCB（設置預設值，如狀態為NEW……）
- 設置相應的隊列指針（如把新進程加到就緒隊列鏈表中）
操作系統為每個進程都分配了一個地址空間。
由於性能，開銷等考慮，引入了線程的概念。
線程的開銷小，創建新線程花費的時間少，線程間切換花費時間少，線程之間互相通信無須調用內核（同一進程的線程共用記憶體和文件）
線程是進程中的一個運行實體，是CPU的調度單位。
4. 操作系統將控制權交給調度程式，如果調度程式選中了helloworld程式，由操作系統為該程式設置CPU上下文環境，並跳到程式開始處，準備執行該程式。那麼下一個指令周期就是執行helloworld程式了。
CPU調度：按一定的調度演算法從就緒隊列中選擇一個進程，把CPU的使用權交給被選擇的進程。如果沒有就緒進程，系統會安排一個空閑進程。
CPU調度需要解決三個問題：調度演算法、調度時機、調度過程。
調度演算法：
占有CPU的方式：
搶占式和非搶占式
時間片輪轉
- 先來先服務（FCFS）
- 最短作業優先（SJF）
- 最短剩餘時間優先（SRTN）
- 最高響應比優先（HRRN）
- 多級反饋隊列（Feedback）
- 最高優先順序調度
- 輪轉調度（Round Robin），為短任務改善平均響應時間，每個進程分配一個時間片
典型系統的調度演算法：
5. 當執行helloworld程式的第一條指令時，會發生缺頁異常（只有將代碼和數據讀入記憶體才能執行程式，執行第一條指令時，還沒有將代碼數據讀入記憶體，那麼這個時候，硬體機制會捕獲出缺頁異常，並且把控制權交給操作系統）
6. 操作系統管理了電腦系統中的記憶體，（如果是頁式管理）操作系統會分配一頁物理記憶體，根據前面計算出的程式的磁碟塊地址，將helloworld程式從磁碟讀入記憶體，然後繼續執行helloworld程式。有的時候程式很大，一頁記憶體不夠，那麼會多次產生缺頁異常，然後從磁碟中讀入程式到記憶體
我們已經知道，每個進程都有自己的進程地址空間，並且進程要裝入記憶體才能運行。那麼如何將進程地址空間裝入記憶體就是一個必須解決的問題。
通過上面的描述，我們可以知道，進程中的進程地址空間的地址，並不是最終的物理地址。
因此需要地址重定位（地址轉換，從進程地址轉換成物理地址）來實驗進程的載入。
我們把進程地址稱為邏輯地址/相對地址/虛擬地址，而記憶體存儲單元中的地址稱為物理地址/絕對地址/實地址，很明顯，只有物理地址能夠直接定址。
地址重定位分為靜態重定位和動態重定位
靜態重定位：當用戶程式載入到記憶體時，一次性實現邏輯地址到物理地址的轉換。但是要求這個程式在記憶體中的位置不能改變。
動態重定位：在程式載入到記憶體中，不改變地址，仍然是邏輯地址。在程式執行過程當中再進行地址轉換，即逐條指令執行完成轉換。由MMU（記憶體管理單元）來加速重定位。
現在已經可以將程式載入到記憶體了，那麼該如何高效地分配記憶體給某個進程呢？
記憶體分配演算法：
- 首次適配（第一個滿足）
- 下次適配（從上次找到的空閑區往下找）
- 最佳適配（查找整個空閑區表，找到滿足要求的最小空閑區）
- 最差適配（總是分配滿足進程要求的最大空閑區）
當記憶體歸還後，則面臨著回收問題，將前後空閑空間合併。
一種經典的記憶體分配方案：伙伴系統
將記憶體按2的冪進行劃分，組成若幹的空閑塊鏈表，查找該鏈表找到能滿足進程需求的最佳匹配塊。
基本記憶體管理方案
進程進入記憶體的連續區域：
單一連續區，記憶體利用率低
固定分區，浪費空間
可變分區，剩餘部分導致大量外碎片，碎片解決方案，緊縮技術（移動程式，將所有小的空閑區合併成較大空閑區）
進程進入記憶體不連續區域：
頁式存儲管理：
進程地址空間被劃分為大小相等的部分，稱為頁或者頁面。記憶體地址空間按同樣大小分為大小相等的部分，稱為頁框。
記憶體分配策略：以頁為單位進行分配，並按進程需要的頁數來分配，邏輯上相鄰的頁，物理上不一定相鄰。
頁表記錄了從邏輯頁號到頁框號的映射關係。
每一個進程一個頁表，存放在記憶體。頁表的起始地址在某個寄存器中。
頁式存儲管理中的地址轉換過程：CPU取到邏輯地址，自動劃分為頁號和頁內地址，用頁號查頁表，得到頁框號，再與頁內地址拼接成物理地址。
段式存儲管理：
用戶進程地址按程式自身邏輯關係劃分為若幹個程式段，每個程式段都有一個段名。
記憶體空間被動態劃分為不等長區域。
記憶體分配策略：以段為單位進行分配，每段在記憶體中占據連續空間，但各段之間可以不相鄰。
與頁式不同的是，段號和段內地址不能自動劃分，需要顯示給出。
與頁式相同，使用段表來記錄關聯關係。
地址轉換過程與頁表也相似：CPU取到邏輯地址後，用段號查段表，得到該段在記憶體中的起始地址，與段內偏移地址拼接計算出物理地址。
段頁式存儲管理：
用戶進程按段劃分，記憶體劃分同頁式存儲管理
段頁式存儲管理需要段表和頁表
段表記錄每一段的頁表起始地址和頁表長度。
頁表與頁式存儲管理相同
一個進程被分為若幹段，需要一個段表，而每一段按照頁式存儲管理分配，又對應一張頁表，所以一個進程對應一個段表和多個頁表。
總結：
那麼當記憶體不足時該如何管理呢？
記憶體“擴容”技術：記憶體緊縮（可變分區），覆蓋技術，交換技術（將某些進程暫時移到外存），虛擬存儲技術。
虛擬存儲技術：當進程運行時，先將其一部分裝入記憶體，另一部分留在磁碟，當要執行的指令或者訪問的數據不在記憶體中時，由操作系統自動完成將它們從磁碟調入記憶體的工作。
把記憶體和磁碟結合起來，得到更大的“記憶體”，就是虛存。
虛擬存儲技術和頁式存儲管理相結合，就產生了虛擬頁式存儲管理。
虛擬頁式存儲管理基本思想：
進程開始執行之前，不是裝入全部頁面，而是裝入一個或者零個頁面，之後根據進程需要，動態裝入其他頁面，當記憶體已滿，而又需要裝入新的頁面，則根據某種演算法置換記憶體中的某個頁面，以便裝入新的頁面。
由於頁表數量太大，引入了多級頁表。
按照傳統的地址轉換方式：虛擬地址->查頁表->頁框號->物理地址，這樣每個進程都要一個頁表。頁表占據了很多空間。
解決這個問題：從物理地址出發，整個系統就建立一張頁表（因為物理地址大小固定），頁表項紀錄進程i的某虛擬地址與頁框號的映射關係。
但是仍然有一個問題存在，由於多級頁表的存在，每次訪問頁表都要去訪問記憶體，那麼需要多次訪問記憶體，由於CPU的指令處理速度與記憶體指令的訪問速度差異大，CPU的速度得不到充分利用。
為瞭解決這個問題，由於程式訪問局部性原理，從而引入了快表（TLB），用來加快地址轉換的速度。
快表由cache組成，訪問速度快。
引入快表後的地址轉換過程：
虛頁號->查快表（並行比較）
如果命中，則找到頁表項
如果沒有命中，用虛頁號查頁表得到頁表項
當得到頁表項後看到有效位，如果有效位是1，說明該頁已經在記憶體中，則運行
如果是0，則拋出缺頁異常。
當缺頁時，操作系統就要將頁面調入記憶體，如果記憶體滿了，必須要將一些頁面暫時調出到外存中。
那麼置換的策略有哪些呢？
- 最佳頁面置換演算法（OPT）（置換之後或者最遠的將來才會用到的頁面）
- 先進先出演算法（FIFO）
- 第二次機會演算法（SCR）按照FIFO選擇某一頁面，檢查其訪問位，如果訪問位為0，則置換，如果為1，說明最近被訪問過，則不置換，並將訪問位設為0
- 時鐘演算法（CLOCK）
- 最近未使用演算法（NRU），選擇最近一段時間未使用的一頁。
- 最近最少使用演算法（LRU），選擇最後一次訪問時間距離當前時間最長的一頁並置換，性能最接近OPT
- 最不經常使用演算法（NFU），選擇訪問次數最少的置換。
7. helloworld程式執行puts函數（系統調用），在顯示器上寫一字元串。
8. 由於puts函數是系統調用，控制權又交到操作系統上。操作系統找到要將字元串送往的的顯示設備，通常設備是由一個進程式控制制的，所以，操作系統將要寫的字元串送給該進程。
CPU與I/O：
減少或緩解速度差距->緩衝技術
使CPU不等待I/O->非同步I/O
讓CPU擺脫I/O操作->DMA，通道
9. 控制設備的進程告訴設備的視窗系統它要顯示字元串，視窗系統確定這是一個合法的操作，然後將字元串轉換成像素，將像素寫入設備的存儲映像區。
10. 視頻硬體將像素轉換成顯示器可以接受的一組控制/數據信號。
11. 顯示器解釋信號，激發液晶屏。
12. 在顯示器上看到hello world。
從上面的過程中，我們能發現，CPU上時而運行用戶程式，時而運行操作系統程式。運行操作系統程式，我們稱CPU處在內核態，運行用戶程式，我們稱CPU處在用戶態。
而這兩種CPU狀態之間的轉換：
從用戶態到內核態，只能通過中斷/異常/陷入進位（陷入指令是一條特殊的指令，提供給用戶程式的介面，用於調用操作系統的功能/服務，例如int,trap,syscall,sysenter/sysexit）
而內核態到用戶態，設置程式狀態字PSW.
中斷/異常機制，是操作系統的驅動力，我們可以說，操作系統是中斷驅動的。
中斷/異常的概念：CPU對系統發生的某個事件作出的反應。
CPU暫停正在執行的程式，保留現場後自動轉去執行相應事件的處理程式。處理完成後返回斷點，繼續執行剛纔被打斷的程式。
中斷和異常的區別在於，中斷是由外部引發的，而異常則是該程式自己產生的。
CPU何時去響應中斷？CPU會在每一條指令執行最後，去掃描中斷寄存器，查看是否有中斷。若有中斷，中斷硬體將該中斷觸發器內容按規定編碼送入PSW的相應位，稱為中斷碼，通過查中斷向量表引出中斷處理程式。
除此之外，當然還有進程互斥同步問題。
進程互斥：由於各進程要求使用共用資源（變數、文件等），而這些資源需要排他性使用，各進程間競爭使用這些資源。這一關係稱為進程互斥。
進程互斥軟體解決方案：
Dekker演算法：
P進程：
pturn = true;
while(qturn)
{
if(turn == 2)
{
pturn = false;
while(turn == 2);
pturn = true;
}
}
臨界區
turn = 2;
pturn = false;
Q進程：
qturn = true;
while(pturn)
{
if(turn == 1)
{
qturn = false;
while(turn == 1);
qturn = true;
}
}
臨界區
turn = 2;
qturn = false;
pturn和qturn表示對應的進程想進臨界區，如果都想進臨界區，則通過turn來判斷自己是否要讓出CPU。從而實現互斥。
Peterson演算法：
剋服了Dekker演算法強制輪流的缺點。
i表示進程號
進程i：
……
enter_region(i);
臨界區
leave_region(i);
……
int turn;//輪到誰
int interested[N];//興趣數組，初始都為false，表示某個進程想進臨界區
void enter_region(int process)//假設這裡兩個進程的進程號是0和1
{
int other;//表示另一個進程的進程號
other = 1 - process;
interested[process] = true;
turn = process;
while(turn == process && interested[other] ==
