第一個程式HelloWorld運作背後，作業系統都在做些什麼
本文就将系統性的串聯起那些知識點，友善複習和回顧。本文适合已經有作業系統基礎的同學，一起回顧知識，本文并不詳細講解每個算法，本文意在知識串聯。
通過一個例子來串聯所有的知識點：
寫了一個C語言程式：
#include
main()
{
puts("Hello World!\n");
}
目的是希望在螢幕中看到Hello World的字樣。
那麼在運作這個C語言程式時，作業系統做了什麼呢？
1. 首先要啟動程式執行，使用者要告訴作業系統執行程式
如何告知：
- 可以滑鼠輕按兩下程式
- 指令行輸入指令
- ……
2. 作業系統知道使用者的請求之後，就會根據使用者提供的檔案名到磁盤上找到這個程式的相關資訊，找到資訊之後，會去檢查這個程式是不是一個可執行檔案，如果是可執行檔案，作業系統會根據程式首部資訊來确定代碼和資料在可執行檔案中的位置并計算出對應的磁盤塊位址。
檔案系統是指作業系統中統一管理資訊資源的一種軟體，管理檔案的存儲、檢索、更新，提供安全可靠的共享和保護手段，并且友善使用者使用。
檔案按性質和用途分類：普通檔案，目錄檔案，特殊檔案（裝置檔案），管道檔案，套接字。
檔案的存儲媒體：磁盤（包括SSD），錄音帶，CD光牒，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;
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] == true);
void leave_region(int process)
interseted[process] = false;
這裡的turn變量要注意一下，turn表示輪到誰來進入臨界區，如果兩個程序都想進入臨界區，可以發現trun變量會被後指派的程序替換到先指派的程序。
Peterson算法希望先想進臨界區的程序先進去，那麼在while循環中就産生了判斷，如果turn是目前程序号（表示該程序是後想進入臨界區的），則一直在while循環中等待，當然還需要判斷另一個程序是否想進入臨界區（interested[other]==true），如果另一個程序不想進入臨界區，就沒必要等待了。
Peterson算法Java實作：
public class Peterson implements Runnable {
private static boolean[] in = { false, false };
private static volatile int turn = -1;
public static void main(String[] args) {
new Thread(new Peterson(0), "Thread - 0").start();
new Thread(new Peterson(1), "Thread - 1").start();
private final int id;
public Peterson(int i) {
id = i;
private int other() {
return id == 0 ? 1 : 0;
@Override
public void run() {
in[id] = true;
turn = other();
while (in[other()] && turn == other()) {
System.out.println("[" + id + "] - Waiting...");
}
System.out.println("[" + id + "] - Working ("
+ ((!in[other()]) ? "other done" : "my turn") + ")");
in[id] = false;
}}
程序的同步：指系統中多個程序中發生的事件存在某種時序關系，需要互相合作，共同完成一項任務。
解決方法：
- 信号量
- 管程（信号量程式設計易出錯），Java中的synchronize
- 程序間通信IPC（由于信号量和管程隻能傳遞少量資訊，不能傳遞大量資訊，并且管程不使用與多處理器的情況），程序通信的基本方式有1.消息傳遞 2.共享記憶體 3.管道 4.套接字 5.遠端過程調用
當然還有死鎖問題：
産生死鎖的必要條件：
- 互斥使用（資源獨占）：一個資源每次隻能給一個程序使用。
- 占有且等待：程序在申請新的資源的同時保持對原有資源的占有。
- 不可搶占：資源申請者不能強行的從資源占有者手中奪取資源，資源隻能由占有者自願釋放。
- 循環等待：存在一個程序等待隊列，形成一個程序等待環路。
資源配置設定圖：用有向圖描述系統資源和程序的狀态。
如：
如果資源配置設定圖中沒有環路，則系統中沒有死鎖，如果圖中存在環路，能可能存在死鎖。
如果每個資源類中隻包含一個資源執行個體，則環路是死鎖存在的充分必要條件。
死鎖預防：
- 破壞“互斥使用/資源獨占”條件：資源轉換技術，把獨占資源變成共享資源，SPOOLING技術的引入。
- 破壞“占有且等待”條件：1.必須一次性申請所有資源，2.必須釋放資源才能申請
- 破壞“不可搶占”條件：通過優先級不同，能夠搶占。
- 破壞“循環等待”條件：資源有序配置設定法，程序在申請資源時必須嚴格按資源編号的遞增次序進行，否則作業系統不予配置設定。
死鎖避免：銀行家算法，安全狀态一定沒有死鎖發生。
銀行家算法總的來說就是，給每個使用者貸款的錢不會超過銀行錢的總量，但是所有使用者貸款的錢的總和是可以超過銀行錢的總量的。
死鎖檢測與解除：允許死鎖發生，但是作業系統會不斷監視死鎖是否真的發生。一旦死鎖發生，就會采用專門的措施，以最小代價來解除死鎖，恢複作業系統運作。
讓我們再次總結一下HelloWorld程式的運作。
當我們運作HelloWorld程式時，作業系統會根據檔案名去找檔案目錄，然後找到了FCB，通過FCB裡的實體位址找到磁盤上對應的檔案。
那麼FCB是如何得到檔案的實體位址的呢？這和檔案的實體結構有關，檔案的實體結構有連續結構、連結清單結構、索引結構，不同結構中FCB儲存的資訊不同。
得到實體位址以後，從磁盤上讀取檔案需要經過尋道，旋轉延遲，資料傳輸三部分。那麼如何高效地從磁盤上讀取檔案呢？就可以運用不同的磁盤排程算法，譬如先來先服務，最短尋道時間優先，掃描算法，旋轉排程算法等等。
得到檔案後，作業系統會建立一個新的程序去執行這個程式。程序與PCB是一一對應的，PCB中儲存了程序的各類資訊，系統為每個程序配置設定一個位址空間，這個位址空間是虛拟位址。
有了程序去運作這個程式後，就等着CPU排程這個程序了。CPU排程算法有先來先服務，最短作業優先，最短剩餘時間優先，最高響應比優先，輪換排程等等。
當CPU選擇排程了這個程式，想要運作這個程式的第一條指令時，會發生缺頁異常，因為代碼資料還沒有讀入記憶體，有的時候程式很大，一頁記憶體不夠，那麼會多次産生缺頁異常，程序必須進入記憶體才能被運作，需要通過位址重定位将程序的虛拟位址轉換成實體位址，不同的記憶體管理方式會有不同的轉換方式，比如頁式存儲管理，段式存儲管理，段頁式存儲管理，加了虛拟存儲技術以後，還有虛拟頁式存儲管理，由于使用虛拟存儲技術，在記憶體滿時，需要将一些頁面暫時調到外存，置換的算法有最佳頁面置換算法，先進先出算法，最近未使用算法，最近最少使用算法等等。