程序、線程概念
程序：一個程序就是一個正在執行的程式的執行個體。
程序轉換：
程序3個狀态：運作态，阻塞态，就緒态。
1.程序為等待輸入而阻塞。
2.排程程式選擇另一個程序。
3.排程程式選擇這個程序。
4.出現有效輸入。
線程：輕量級程序。
作業排程：按照某種原則，從後備作業隊列中選取作業進入記憶體，并為作業做好運作前的準備工作以及作業完成後的善後處理工作。
主要排程算法：
First Come First Serve （FCFS）先來先服務：按到達時間先後排序。
Shorted Job First (nonpreemptive & preemptive ) 最短作業優先：按作業的運作時間排序，由短到長。
Round robin 輪轉排程：每個程序執行一個時間片後移到隊列末尾，把CPU交給下一個程序。
Priority Scheduling (nonpreemptive & preemptive ) 優先級排程：執行目前實時優先級最高的程序。動态優先級是在建立程序時賦予該程序一個初始優先級，然後其優先級随着程序的執行情況的變化而改變。
Multiple Queues 多級隊列：
1.程序在進入待排程的隊列等待時，首先進入優先級最高的Q1等待。
2.首先排程優先級高的隊列中的程序。若高優先級中隊列中已沒有排程的程序，則排程次優先級隊列中的程序。
3.對于同一個隊列中的各個程序，按照時間片輪轉法排程。
4.在低優先級的隊列中的程序在運作時，又有新到達的作業，那麼在運作完這個時間片後，CPU馬上配置設定給新到達的作業（搶占式）。
多級隊列算法運作過程示例：
假設系統中有3個回報隊列Q1,Q2,Q3，時間片分别為2，4，8。
現在有3個作業J1,J2,J3分别在時間 0 ，1，3時刻到達。而它們所需要的CPU時間分别是3，2，1個時間片。
1、時刻0 J1到達。于是進入到隊列1 ， 運作1個時間片 ， 時間片還未到，此時J2到達。
2、時刻1 J2到達。 由于時間片仍然由J1掌控，于是等待。 J1在運作了1個時間片後，已經完成了在Q1中的2個時間片的限制，于是J1置于Q2等待被排程。現在處理機配置設定給J2。
3、時刻2 J1進入Q2等待排程，J2獲得CPU開始運作。
4、時刻3 J3到達，由于J2的時間片未到，故J3在Q1等待排程，J1也在Q2等待排程。
5、時刻4 J2處理完成，由于J3，J1都在等待排程，但是J3所在的隊列比J1所在的隊列的優先級要高，于是J3被排程，J1繼續在Q2等待。
6、時刻5 J3經過1個時間片，完成。
7、時刻6 由于Q1已經空閑，于是開始排程Q2中的作業，則J1得到處理器開始運作。 J1再經過一個時間片，完成了任務。于是整個排程過程結束。
周轉時間 作業完成時刻減去作業到達的時刻：作業完成時刻-作業到達時刻
平均周轉時間 用周轉時間總時間除以作業個數：所有作業的周轉時間/作業總數
甘特圖 一種作業執行情況描述圖，如下SJF（最短作業排程）。
臨界區：每個程序中通路臨界資源的那段代碼稱為臨界區（Critical Section）（臨界資源是一次僅允許一個程序使用的共享資源）。每次隻準許一個程序進入臨界區，進入後不允許其他程序進入。不論是硬體臨界資源，還是軟體臨界資源，多個程序必須互斥地對它進行通路。
信号量：在多線程環境下使用的一種設施，是可以用來保證兩個或多個關鍵代碼段不被并發調用。在進入一個關鍵代碼段之前，線程必須擷取一個信号量；一旦該關鍵代碼段完成了，那麼該線程必須釋放信号量。其它想進入該關鍵代碼段的線程必須等待直到第一個線程釋放信号量。
信号量有兩種操作：down,up，也就是所謂的P,V操作
down:如果信号量大于0，則繼續，等于0則程序将睡眠，将信号量減1。
up:将信号量加1，如果信号量大于0，則繼續，若小于或等于0，則喚醒一阻塞在該信号量上的程序。
例如：Semaphore的初值為n, m個程序使用該semaphore通路關鍵區，那麼semaphore值的變化範圍是多少？
每個程序進入關鍵區時都會使Semaphore減1，離開時又使Semaphore加1，是以範圍是n-m到n。
信号量可以用來解決一些程序同步的問題，例如：
用P、V操作說明互斥量，定出司機與售票員之間的同步算法，司機與售票員活動如下圖所示。
在汽車行駛過程中，司機活動與售票員活動之間的同步關系為：售票員關車門後向司機發開車信号，司機接到開車信号後啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停後開車門讓乘客下車。是以司機啟動車輛的動作必須與售票員關車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步。
是以在本題中，應設定兩個信号量s1、s2，s1表示是否允許司機啟動汽車，其初值為0；s2表示是否允許售票員開車門，其初值為0。
是以解答為：（可以将P操作看成是wait--等待信号，V操作看成是signal--發出信号）
Semaphore s1,s2=0;
Driver() Saler()
{ {
while(true) while(true)
{ {
p(s1); 關車門；
啟動車輛； v(s1);
正常行車； 售票；
到站停車； p(s2);
v(s2); 開車門；
} 上下乘客；
} }
}
幾個利用信号量和線程解決的IPC（程序間通信）經典問題：
1.生産者與消費者問題
在同一個程序位址空間内執行的兩個線程生産者線程生産物品，然後将物品放置在一個空緩沖區中供消費者線程消費。消費者線程從緩沖區中獲得物品，然後釋放緩沖區。當生産者線程生産物品時，如果沒有空緩沖區可用，那麼生産者線程必須等待消費者線程釋放出一個空緩沖區。當消費者線程消費物品時，如果沒有滿的緩沖區，那麼消費者線程将被阻塞，直到新的物品被生産出來。
C解決此問題的源碼：
1 #define N 100 //緩沖區的槽數目
2 typedef int semaphore;
3 semaphore mutex = 1 ; //臨界區（緩沖區）信号量，以互斥各線程的進入
4 semaphore empty = N; //緩沖區的空槽數目
5 semaphore full = 0; //緩沖區的滿槽數目
6 void producer(void)
7 {
8 int item;
9 while (TRUE) {
10 item = produce_item( );
11 down( &empty); //空槽減1
12 down( &mutex); //進入臨界區
13 inserUtem(item); //加入資料
14 up( &mutex); //離開臨界區
15 up( &full); //滿槽加1
16 }
17 }
18 void consumer(void)
19 {
20 int item;
21 while (TRUE) {
22 down( &full);
23 down( &mutex);
24 item = remove_ item( );
25 up( &mutex);
26 up( &empty);
27 consume_item(item); //消費一個資料項
28 }
29 } 2.哲學家就餐問題
假設有五位哲學家圍坐在一張圓形餐桌旁，做以下兩件事情之一：吃飯，或者思考。吃東西的時候，他們就停止思考，思考的時候也停止吃東西。餐桌中間有一大碗意大利面，每兩個哲學家之間有一隻餐叉。因為用一隻餐叉很難吃到意大利面，是以假設哲學家必須用兩隻餐叉吃東西。他們隻能使用自己左右手邊的那兩隻餐叉。哲學家就餐問題有時也用米飯和筷子而不是意大利面和餐叉來描述，因為很明顯，吃米飯必須用兩根筷子。
C解決此問題源碼：
PS：philosopher函數未完整，應該修改為下圖：
值得注意的是，philosopher函數會有不同的5個程序來調，參數為 0 到 N-1 。
3.讀者寫者的問題
有一個被許多程序共享的資料區，這個資料區可以是一個檔案，或者主存的一塊空間，甚至可以是一組處理器寄存器。有一些隻讀取這個資料區的程序（reader）和一些隻往資料區中寫資料的程序（writer）。以下假設共享資料區是檔案。這些讀者和寫者對資料區的操作必須滿足以下條件：讀—讀允許；讀—寫互斥；寫—寫互斥。這些條件具體來說就是：
（1）任意多的讀程序可以同時讀這個檔案；
（2）一次隻允許一個寫程序往檔案中寫；
（3）如果一個寫程序正在往檔案中寫，禁止任何讀程序或寫程序通路檔案；
（4）寫程序執行寫操作前，應讓已有的寫者或讀者全部退出。這說明當有讀者在讀檔案時不允許寫者寫檔案。
C語言解決此問題源碼：寫者優先算法
死鎖
資源死鎖的4個條件：
1）互斥條件：在一段時間内某資源隻由一個程序占用，如果此時還有其它程序請求資源，則請求者隻能等待，直至占有資源的程序用畢釋放。
2）占有和等待條件：已經得到了某個資源的程序可以再請求新的資源。
3）不可搶占條件：指程序已獲得的資源，在未使用完之前，不能被剝奪，隻能在使用完時由自己釋放。
4）環路等待條件：指在發生死鎖時，必然存在一個程序——資源的環形鍊，即程序集合{P0，P1，P2，···，Pn}中的P0正在等待一個P1占用的資源；P1正在等待P2占用的資源，……，Pn正在等待已被P0占用的資源。
不發生死鎖的判斷：
m個資源，n個程序，每個程序最大需求w。
滿足 (w-1)*n+1<m 則不會發生死鎖。
避免死鎖的方法：通過設定某些限制條件，去破壞産生死鎖的四個必要條件中的一個或者幾個，來預防發生死鎖。
銀行家算法：。一種避免死鎖的算法。
銀行家算法基本思想：配置設定資源之前，判斷系統是否是安全的；若是，才配置設定。
安全狀态：如果沒有死鎖發生，并且即使所有程序突然請求對資源的最大需求，也仍然存在某種排程次序能夠使每一個程序運作完畢。
例如：
現在有5個程序A、B、C、D、E，有4種類型的資源R1、R2、R3、R4。在T0時刻系統狀态如下。R1、R2、R3、R4的剩餘資源數依次為3、3、0、3。
回答下面問題：
（1）T0時刻是否為安全狀态？
（2）若這時D提出申請（1,2,0,3），是否能實施資源配置設定？
虛位址到實位址的翻譯過程
幾種主要的頁面置換算法：
FIFO(First In First Out)先進先出：按照先進先出順序淘汰頁面。（ps:頁面替換時，出現重複頁面，此頁面的順序按照之前的頁面順序算）
LRU( Least Recently Used ) 最近最少使用：将前一段時間内沒使用的頁面置換。
OPT( Optimal )最佳頁面置換算法：
1、如果頁框中的某個頁面P以後永不使用，則該頁面為淘汰頁面Pt。
2、如果每個P都會再次被通路，那麼其中最長未來時間内不再被通路的頁面為淘汰頁面Pt。
（ps:此算法不可能實作，因為當缺頁中斷發生時，作業系統接下來頁面的通路順序。）
其實LRU在置換某頁面時就是向前看，距離這個置換頁面最遠的頁面被置換。
FIFO就是按照最先放入的頁面或者說順序在前的頁面置換掉。
OPT隻需要看置換頁面位置後面的頁面，按照出現順序，不出現或者最晚出現的被置換掉。如果都沒出現就任意置換，一般置換第一個。
磁盤排程算法
FCFS (First Come First Served) 先來先服務：和程序排程一樣。
最短尋道優先算法（Shortest Seek First）：以磁頭位置尋找下一個距離最近的磁道。
SCAN（掃描算法 又稱 電梯算法）：第一個磁道選擇離磁頭最近的磁道，然後按照磁頭移動方向依次選擇最近磁道，當此方向上磁道都選擇完畢時，反向選擇最近磁道。
Inode
檔案儲存在硬碟上，硬碟的最小存儲機關叫做"扇區"（Sector）。每個扇區儲存512位元組（相當于0.5KB）。
作業系統讀取硬碟的時候，不會一個個扇區地讀取，這樣效率太低，而是一次性連續讀取多個扇區，即一次性讀取一個"塊"（block）。這種由多個扇區組成的"塊"，是檔案存取的最小機關。"塊"的大小，最常見的是4KB，即連續八個 sector組成一個 block。
檔案資料都儲存在"塊"中，那麼很顯然，我們還必須找到一個地方儲存檔案的元資訊，比如檔案的建立者、檔案的建立日期、檔案的大小等等。這種儲存檔案元資訊的區域就叫做inode，中文譯名為"索引節點"。
Directory
記錄了一個檔案/目錄名稱對應的Inode number。
PS：
1.目錄檔案的讀權限（r）和寫權限（w），都是針對目錄檔案本身。由于目錄檔案内隻有檔案名和inode号碼，是以如果隻有讀權限，隻能擷取檔案名，無法擷取其他資訊，因為其他資訊都儲存在inode節點中，而讀取inode節點内的資訊需要目錄檔案的執行權限（x）。
2.每個inode都有一個号碼，作業系統用inode号碼來識别不同的檔案。Unix/Linux系統内部不使用檔案名，而使用inode号碼來識别檔案。對于系統來說，檔案名隻是inode号碼便于識别的别稱或者綽号。
3.Unix/Linux系統允許多個檔案名指向同一個inode号碼。
HardLink 硬連結
可以用不同的檔案名通路同樣的内容；對檔案内容進行修改，會影響到所有檔案名；但是，删除一個檔案名，不影響另一個檔案名的通路。這種情況就被稱為"硬連結"（hard link）。
SoftLink 軟連結
檔案A和檔案B的inode号碼雖然不一樣，但是檔案A的内容是檔案B的路徑。讀取檔案A時，系統會自動将通路者導向檔案B。是以，無論打開哪一個檔案，最終讀取的都是檔案B。這時，檔案A就稱為檔案B的"軟連結"（soft link）或者"符号連結"（symbolic link）。
這意味着，檔案A依賴于檔案B而存在，如果删除了檔案B，打開檔案A就會報錯："No such file or directory"。這是軟連結與硬連結最大的不同：檔案A指向檔案B的檔案名，而不是檔案B的inode号碼，檔案B的inode"連結數"不會是以發生變化。
Block devices & Character devices 塊裝置&字元裝置
I/O裝置大緻分為兩類：塊裝置和字元裝置。塊裝置将資訊存儲在固定大小的塊中，每個塊都有自己的位址。資料塊的大小通常在512位元組到32768位元組之間。塊裝置的基本特征是每個塊都能獨立于其它塊而讀寫。磁盤是最常見的塊裝置。
FAT (File Allocation Table 檔案配置表)
一個分區分成同等大小的簇，也就是連續空間的小塊。簇的大小随着FAT檔案系統的類型以及分區大小而不同，典型的簇大小介于2KB到32KB之間。每個檔案根據它的大小可能占有一個或者多個簇；這樣，一個檔案就由這些這些（稱為單連結清單）簇鍊所表示。然而，這些鍊并不一定一個接着一個在磁盤上存儲，它們經常是在整個資料區域零散的儲存。
檔案配置設定表（FAT）是映射到分區每個簇的條目清單。每個條目記錄下面五種資訊中的一種：
1.鍊中下一個簇的位址
2.一個特殊的檔案結束符（EOF）
3.符号訓示鍊的結束
4.一個特殊的符号标示壞簇
5.一個特殊的符号标示保留簇 ( 0來表示空閑簇 )
Memory mapped I/O : 就是把磁盤上的file映射到記憶體上，當我們從記憶體上fetch byte時，對應的file就被讀取。同樣的，當我們在記憶體上存儲位元組的時候，對應的file就被寫入。這就讓我們不需通過read和write系統調用而去操作I/O。
裝置獨立性：指作業系統把所有外部裝置統一當作成檔案來看待，隻要安裝它們的驅動程式，任何使用者都可以像使用檔案一樣，操縱、使用這些裝置，而不必知道它們的具體存在形式。
三種I/O實作方式：
1.Programmed I/O （程式控制I/O）是指用特定的IO指令實作從裝置到CPU的資料傳輸，CPU需要做全部操作。
2.DMA （Direct Memory Access 直接存儲器通路）
DMA傳輸将資料從一個位址空間複制到另外一個位址空間。CPU 初始化這個傳輸動作，傳輸動作本身是由 DMA 控制器來實行和完成。典型的例子就是移動一個外部記憶體的區塊到晶片内部更快的記憶體區。像是這樣的操作并沒有讓處理器工作拖延，反而可以被重新排程去處理其他的工作。
3.Interrupt-Driven I/O （ 中斷驅動I/O ）：當某程序要啟動某個I/O裝置工作時，便由CPU向相應的裝置控制器發出一條I/O指令，然後立即傳回繼續執行原來的任務，裝置控制器則按照該指令的要求去控制指定I/O裝置。此時，CPU與I/O裝置并行操作。
Disk Formatting ( 磁盤格式化 )
磁盤格式化是在實體驅動器（磁盤）的所有資料區上寫零的操作過程，格式化是一種純實體操作，同時對硬碟媒體做一緻性檢測，并且标記出不可讀和壞的扇區。
Domain（保護域/域）:一對（對象、權限）組合。
每個檔案可以在不同的域中有不同的權限，每個域也能切換到其他域，此時檔案的權限改變，例如UNIX的程序有2個部分，使用者部分和核心部分，當執行系統調用時，程序從使用者部分切換到核心部分，核心部分可以通路與使用者部分不同的對象集。
ACL（Access Control List）通路控制連結清單