本文經 CyC2018 大佬授權發表，更多技術内容請前往 https://github.com/CyC2018/CS-Notes 檢視。
一、概述
基本特征
1. 并發
并發是指宏觀上在一段時間内能同時運作多個程式，而并行則指同一時刻能運作多個指令。
并行需要硬體支援，如多流水線、多核處理器或者分布式計算系統。
作業系統通過引入程序和線程，使得程式能夠并發運作。
2. 共享
共享是指系統中的資源可以被多個并發程序共同使用。
有兩種共享方式：互斥共享和同時共享。
互斥共享的資源稱為臨界資源，例如列印機等，在同一時間隻允許一個程序通路，需要用同步機制來實作對臨界資源的通路。
3. 虛拟
虛拟技術把一個實體實體轉換為多個邏輯實體。
主要有兩種虛拟技術：時分複用技術和空分複用技術。
多個程序能在同一個處理器上并發執行使用了時分複用技術，讓每個程序輪流占有處理器，每次隻執行一小個時間片并快速切換。
虛拟記憶體使用了空分複用技術，它将實體記憶體抽象為位址空間，每個程序都有各自的位址空間。位址空間的頁被映射到實體記憶體，位址空間的頁并不需要全部在實體記憶體中，當使用到一個沒有在實體記憶體的頁時，執行頁面置換算法，将該頁置換到記憶體中。
4. 異步
異步指程序不是一次性執行完畢，而是走走停停，以不可知的速度向前推進。
基本功能
1. 程序管理
程序控制、程序同步、程序通信、死鎖處理、處理機排程等。
2. 記憶體管理
記憶體配置設定、位址映射、記憶體保護與共享、虛拟記憶體等。
3. 檔案管理
檔案存儲空間的管理、目錄管理、檔案讀寫管理和保護等。
4. 裝置管理
完成使用者的 I/O 請求，友善使用者使用各種裝置，并提高裝置的使用率。
主要包括緩沖管理、裝置配置設定、裝置處理、虛拟裝置等。
系統調用
如果一個程序在使用者态需要使用核心态的功能，就進行系統調用進而陷入核心，由作業系統代為完成。
Linux 的系統調用主要有以下這些：
| Task | Commands |
| 程序控制 | fork(); exit(); wait(); |
| 程序通信 | pipe(); shmget(); mmap(); |
| 檔案操作 | open(); read(); write(); |
| 裝置操作 | ioctl(); read(); write(); |
| 資訊維護 | getpid(); alarm(); sleep(); |
| 安全 | chmod(); umask(); chown(); |
大核心和微核心
1. 大核心
大核心是将作業系統功能作為一個緊密結合的整體放到核心。
由于各子產品共享資訊，是以有很高的性能。
2. 微核心
由于作業系統不斷複雜，是以将一部分作業系統功能移出核心，進而降低核心的複雜性。移出的部分根據分層的原則劃分成若幹服務，互相獨立。
在微核心結構下，作業系統被劃分成小的、定義良好的子產品，隻有微核心這一個子產品運作在核心态，其餘子產品運作在使用者态。
因為需要頻繁地在使用者态和核心态之間進行切換，是以會有一定的性能損失。
中斷分類
1. 外中斷
由 CPU 執行指令以外的事件引起，如 I/O 完成中斷，表示裝置輸入/輸出處理已經完成，處理器能夠發送下一個輸入/輸出請求。此外還有時鐘中斷、控制台中斷等。
2. 異常
由 CPU 執行指令的内部事件引起，如非法操作碼、位址越界、算術溢出等。
3. 陷入
在使用者程式中使用系統調用。
二、程序管理
程序與線程
1. 程序
程序是資源配置設定的基本機關。
程序控制塊 (Process Control Block, PCB) 描述程序的基本資訊和運作狀态，所謂的建立程序和撤銷程序，都是指對 PCB 的操作。
下圖顯示了 4 個程式建立了 4 個程序，這 4 個程序可以并發地執行。
2. 線程
線程是獨立排程的基本機關。
一個程序中可以有多個線程，它們共享程序資源。
QQ 和浏覽器是兩個程序，浏覽器程序裡面有很多線程，例如 HTTP 請求線程、事件響應線程、渲染線程等等，線程的并發執行使得在浏覽器中點選一個新連結進而發起 HTTP 請求時，浏覽器還可以響應使用者的其它事件。
3. 差別
Ⅰ 擁有資源
程序是資源配置設定的基本機關，但是線程不擁有資源，線程可以通路隸屬程序的資源。
Ⅱ 排程
線程是獨立排程的基本機關，在同一程序中，線程的切換不會引起程序切換，從一個程序中的線程切換到另一個程序中的線程時，會引起程序切換。
Ⅲ 系統開銷
由于建立或撤銷程序時，系統都要為之配置設定或回收資源，如記憶體空間、I/O 裝置等，所付出的開銷遠大于建立或撤銷線程時的開銷。類似地，在進行程序切換時，涉及目前執行程序 CPU 環境的儲存及新排程程序 CPU 環境的設定，而線程切換時隻需儲存和設定少量寄存器内容，開銷很小。
Ⅳ 通信方面
線程間可以通過直接讀寫同一程序中的資料進行通信，但是程序通信需要借助 IPC。
程序狀态的切換
- 就緒狀态（ready）：等待被排程
- 運作狀态（running）
- 阻塞狀态（waiting）：等待資源
應該注意以下内容：
- 隻有就緒态和運作态可以互相轉換，其它的都是單向轉換。就緒狀态的程序通過排程算法進而獲得 CPU 時間，轉為運作狀态；而運作狀态的程序，在配置設定給它的 CPU 時間片用完之後就會轉為就緒狀态，等待下一次排程。
- 阻塞狀态是缺少需要的資源進而由運作狀态轉換而來，但是該資源不包括 CPU 時間，缺少 CPU 時間會從運作态轉換為就緒态。
程序排程算法
不同環境的排程算法目标不同，是以需要針對不同環境來讨論排程算法。
1. 批處理系統
批處理系統沒有太多的使用者操作，在該系統中，排程算法目标是保證吞吐量和周轉時間（從送出到終止的時間）。
1.1 先來先服務 first-come first-serverd（FCFS）
按照請求的順序進行排程。
有利于長作業，但不利于短作業，因為短作業必須一直等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成了短作業等待時間過長。
1.2 短作業優先 shortest job first（SJF）
按估計運作時間最短的順序進行排程。
長作業有可能會餓死，處于一直等待短作業執行完畢的狀态。因為如果一直有短作業到來，那麼長作業永遠得不到排程。
1.3 最短剩餘時間優先 shortest remaining time next（SRTN）
按估計剩餘時間最短的順序進行排程。
2. 互動式系統
互動式系統有大量的使用者互動操作，在該系統中排程算法的目标是快速地進行響應。
2.1 時間片輪轉
将所有就緒程序按 FCFS 的原則排成一個隊列，每次排程時，把 CPU 時間配置設定給隊首程序，該程序可以執行一個時間片。當時間片用完時，由計時器發出時鐘中斷，排程程式便停止該程序的執行，并将它送往就緒隊列的末尾，同時繼續把 CPU 時間配置設定給隊首的程序。
時間片輪轉算法的效率和時間片的大小有很大關系：
- 因為程序切換都要儲存程序的資訊并且載入新程序的資訊，如果時間片太小，會導緻程序切換得太頻繁，在程序切換上就會花過多時間。
- 而如果時間片過長，那麼實時性就不能得到保證。
2.2 優先級排程
為每個程序配置設定一個優先級，按優先級進行排程。
為了防止低優先級的程序永遠等不到排程，可以随着時間的推移增加等待程序的優先級。
2.3 多級回報隊列
一個程序需要執行 100 個時間片，如果采用時間片輪轉排程算法，那麼需要交換 100 次。
多級隊列是為這種需要連續執行多個時間片的程序考慮，它設定了多個隊列，每個隊列時間片大小都不同，例如 1,2,4,8,..。程序在第一個隊列沒執行完，就會被移到下一個隊列。這種方式下，之前的程序隻需要交換 7 次。
每個隊列優先權也不同，最上面的優先權最高。是以隻有上一個隊列沒有程序在排隊，才能排程目前隊列上的程序。
可以将這種排程算法看成是時間片輪轉排程算法和優先級排程算法的結合。
3. 實時系統
實時系統要求一個請求在一個确定時間内得到響應。
分為硬實時和軟實時，前者必須滿足絕對的截止時間，後者可以容忍一定的逾時。
程序同步
1. 臨界區
對臨界資源進行通路的那段代碼稱為臨界區。
為了互斥通路臨界資源，每個程序在進入臨界區之前，需要先進行檢查。
// entry section
// critical section;
// exit section 2. 同步與互斥
- 同步：多個程序按一定順序執行；
- 互斥：多個程序在同一時刻隻有一個程序能進入臨界區。
3. 信号量
信号量（Semaphore）是一個整型變量，可以對其執行 down 和 up 操作，也就是常見的 P 和 V 操作。
- down : 如果信号量大于 0 ，執行 -1 操作；如果信号量等于 0，程序睡眠，等待信号量大于 0；
- up ：對信号量執行 +1 操作，喚醒睡眠的程序讓其完成 down 操作。
down 和 up 操作需要被設計成原語，不可分割，通常的做法是在執行這些操作的時候屏蔽中斷。
如果信号量的取值隻能為 0 或者 1，那麼就成為了 互斥量（Mutex） ，0 表示臨界區已經加鎖，1 表示臨界區解鎖。
typedef int semaphore;
semaphore mutex = 1;
void P1(){
down(&mutex);
// 臨界區
up(&mutex);
}
void P2(){
down(&mutex);
// 臨界區
up(&mutex);
} 使用信号量實作生産者-消費者問題
問題描述：使用一個緩沖區來儲存物品，隻有緩沖區沒有滿，生産者才可以放入物品；隻有緩沖區不為空，消費者才可以拿走物品。
因為緩沖區屬于臨界資源，是以需要使用一個互斥量 mutex 來控制對緩沖區的互斥通路。
為了同步生産者和消費者的行為，需要記錄緩沖區中物品的數量。數量可以使用信号量來進行統計，這裡需要使用兩個信号量：empty 記錄空緩沖區的數量，full 記錄滿緩沖區的數量。其中，empty 信号量是在生産者程序中使用，當 empty 不為 0 時，生産者才可以放入物品；full 信号量是在消費者程序中使用，當 full 信号量不為 0 時，消費者才可以取走物品。
注意，不能先對緩沖區進行加鎖，再測試信号量。也就是說，不能先執行 down(mutex) 再執行 down(empty)。如果這麼做了，那麼可能會出現這種情況：生産者對緩沖區加鎖後，執行 down(empty) 操作，發現 empty = 0，此時生産者睡眠。消費者不能進入臨界區，因為生産者對緩沖區加鎖了，消費者就無法執行 up(empty) 操作，empty 永遠都為 0，導緻生産者永遠等待下，不會釋放鎖，消費者是以也會永遠等待下去。
#define
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer(){
while(TRUE) {
int item = produce_item();
down(&empty);
down(&mutex);
insert_item(item);
up(&mutex);
up(&full);
}
}
void consumer(){
while(TRUE) {
down(&full);
down(&mutex);
int item = remove_item();
consume_item(item);
up(&mutex);
up(&empty);
}
} 4. 管程
使用信号量機制實作的生産者消費者問題需要用戶端代碼做很多控制，而管程把控制的代碼獨立出來，不僅不容易出錯，也使得用戶端代碼調用更容易。
c 語言不支援管程，下面的示例代碼使用了類 Pascal 語言來描述管程。示例代碼的管程提供了 insert() 和 remove() 方法，用戶端代碼通過調用這兩個方法來解決生産者-消費者問題。
monitor ProducerConsumer
integer i;
condition c;
procedure insert();
begin
// ...
end;
procedure remove();
begin
// ...
end;
end monitor; 管程有一個重要特性：在一個時刻隻能有一個程序使用管程。程序在無法繼續執行的時候不能一直占用管程，否者其它程序永遠不能使用管程。
管程引入了 條件變量 以及相關的操作：wait() 和 signal() 來實作同步操作。對條件變量執行 wait() 操作會導緻調用程序阻塞，把管程讓出來給另一個程序持有。signal() 操作用于喚醒被阻塞的程序。
使用管程實作生産者-消費者問題
// 管程
monitor ProducerConsumer
condition full, empty;
integer count := 0;
condition c;
procedure insert(item: integer);
begin
if count = N then wait(full);
insert_item(item);
count := count + 1;
if count = 1 then signal(empty);
end;
function remove: integer;
begin
if count = 0 then wait(empty);
remove = remove_item;
count := count - 1;
if count = N -1 then signal(full);
end;
end monitor;
// 生産者用戶端
procedure producer
begin
while true do
begin
item = produce_item;
ProducerConsumer.insert(item);
end
end;
// 消費者用戶端
procedure consumer
begin
while true do
begin
item = ProducerConsumer.remove;
consume_item(item);
end
end; 經典同步問題
生産者和消費者問題前面已經讨論過了。
1. 讀者-寫者問題
允許多個程序同時對資料進行讀操作，但是不允許讀和寫以及寫和寫操作同時發生。
一個整型變量 count 記錄在對資料進行讀操作的程序數量，一個互斥量 count_mutex 用于對 count 加鎖，一個互斥量 data_mutex 用于對讀寫的資料加鎖。
typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;
void reader(){
while(TRUE) {
down(&count_mutex);
count++;
if(count == 1) down(&data_mutex); // 第一個讀者需要對資料進行加鎖，防止寫程序通路
up(&count_mutex);
read();
down(&count_mutex);
count--;
if(count == 0) up(&data_mutex);
up(&count_mutex);
}
}
void writer(){
while(TRUE) {
down(&data_mutex);
write();
up(&data_mutex);
}
} 以下内容由 @Bandi Yugandhar 提供。
The first case may result Writer to starve. This case favous Writers i.e no writer, once added to the queue, shall be kept waiting longer than absolutely necessary(only when there are readers that entered the queue before the writer).
int readcount, writecount; //(initial value = 0)
semaphore rmutex, wmutex, readLock, resource; //(initial value = 1)
//READER
void reader() {
<ENTRY Section>
down(&readLock); // reader is trying to enter
down(&rmutex); // lock to increase readcount
readcount++;
if (readcount == 1)
down(&resource); //if you are the first reader then lock the resource
up(&rmutex); //release for other readers
up(&readLock); //Done with trying to access the resource
<CRITICAL Section>
//reading is performed
<EXIT Section>
down(&rmutex); //reserve exit section - avoids race condition with readers
readcount--; //indicate you're leaving
if (readcount == 0) //checks if you are last reader leaving
up(&resource); //if last, you must release the locked resource
up(&rmutex); //release exit section for other readers
}
//WRITER
void writer() {
<ENTRY Section>
down(&wmutex); //reserve entry section for writers - avoids race conditions
writecount++; //report yourself as a writer entering
if (writecount == 1) //checks if you're first writer
down(&readLock); //if you're first, then you must lock the readers out. Prevent them from trying to enter CS
up(&wmutex); //release entry section
<CRITICAL Section>
down(&resource); //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource
//writing is performed
up(&resource); //release file
<EXIT Section>
down(&wmutex); //reserve exit section
writecount--; //indicate you're leaving
if (writecount == 0) //checks if you're the last writer
up(&readLock); //if you're last writer, you must unlock the readers. Allows them to try enter CS for reading
up(&wmutex); //release exit section
} We can observe that every reader is forced to acquire ReadLock. On the otherhand, writers doesn’t need to lock individually. Once the first writer locks the ReadLock, it will be released only when there is no writer left in the queue.
From the both cases we observed that either reader or writer has to starve. Below solutionadds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.
int readCount; // init to 0; number of readers currently accessing resource
// all semaphores initialised to 1
Semaphore resourceAccess; // controls access (read/write) to the resource
Semaphore readCountAccess; // for syncing changes to shared variable readCount
Semaphore serviceQueue; // FAIRNESS: preserves ordering of requests (signaling must be FIFO)
void writer()
{
down(&serviceQueue); // wait in line to be servicexs
// <ENTER>
down(&resourceAccess); // request exclusive access to resource
// </ENTER>
up(&serviceQueue); // let next in line be serviced
// <WRITE>
writeResource(); // writing is performed
// </WRITE>
// <EXIT>
up(&resourceAccess); // release resource access for next reader/writer
// </EXIT>
}
void reader()
{
down(&serviceQueue); // wait in line to be serviced
down(&readCountAccess); // request exclusive access to readCount
// <ENTER>
if (readCount == 0) // if there are no readers already reading:
down(&resourceAccess); // request resource access for readers (writers blocked)
readCount++; // update count of active readers
// </ENTER>
up(&serviceQueue); // let next in line be serviced
up(&readCountAccess); // release access to readCount
// <READ>
readResource(); // reading is performed
// </READ>
down(&readCountAccess); // request exclusive access to readCount
// <EXIT>
readCount--; // update count of active readers
if (readCount == 0) // if there are no readers left:
up(&resourceAccess); // release resource access for all
// </EXIT>
up(&readCountAccess); // release access to readCount
} 2. 哲學家進餐問題
五個哲學家圍着一張圓桌，每個哲學家面前放着食物。哲學家的生活有兩種交替活動：吃飯以及思考。當一個哲學家吃飯時，需要先拿起自己左右兩邊的兩根筷子，并且一次隻能拿起一根筷子。
下面是一種錯誤的解法，考慮到如果所有哲學家同時拿起左手邊的筷子，那麼就無法拿起右手邊的筷子，造成死鎖。
#define
void philosopher(int{
while(TRUE) {
think();
take(i); // 拿起左邊的筷子
take((i+1)%N); // 拿起右邊的筷子
eat();
put(i);
put((i+1)%N);
}
} 為了防止死鎖的發生，可以設定兩個條件：
- 必須同時拿起左右兩根筷子；
- 隻有在兩個鄰居都沒有進餐的情況下才允許進餐。
#define
#define LEFT (i + N - 1) % N // 左鄰居
#define RIGHT (i + 1) % N // 右鄰居
#define
#define
#define
typedef int semaphore;
int state[N]; // 跟蹤每個哲學家的狀态
semaphore mutex = 1; // 臨界區的互斥
semaphore s[N]; // 每個哲學家一個信号量
void philosopher(int{
while(TRUE) {
think();
take_two(i);
eat();
put_two(i);
}
}
void take_two(int{
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}
void put_two(i){
down(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
up(&mutex);
}
void test(i){ // 嘗試拿起兩把筷子
if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
state[i] = EATING;
up(&s[i]);
}
} 程序通信
程序同步與程序通信很容易混淆，它們的差別在于：
- 程序同步：控制多個程序按一定順序執行；
- 程序通信：程序間傳輸資訊。
程序通信是一種手段，而程序同步是一種目的。也可以說，為了能夠達到程序同步的目的，需要讓程序進行通信，傳輸一些程序同步所需要的資訊。
1. 管道
管道是通過調用 pipe 函數建立的，fd[0] 用于讀，fd[1] 用于寫。
#include <unistd.h>
int pipe(int fd[2]); 它具有以下限制：
- 隻支援半雙工通信（單向交替傳輸）；
- 隻能在父子程序中使用。
2. FIFO
也稱為命名管道，去除了管道隻能在父子程序中使用的限制。
#include <sys/stat.h>
int mkfifo(const char *path, mode_t;
int mkfifoat(int fd, const char *path, mode_t; FIFO 常用于客戶-伺服器應用程式中，FIFO 用作彙聚點，在客戶程序和伺服器程序之間傳遞資料。
3. 消息隊列
相比于 FIFO，消息隊列具有以下優點：
- 消息隊列可以獨立于讀寫程序存在，進而避免了 FIFO 中同步管道的打開和關閉時可能産生的困難；
- 避免了 FIFO 的同步阻塞問題，不需要程序自己提供同步方法；
- 讀程序可以根據消息類型有選擇地接收消息，而不像 FIFO 那樣隻能預設地接收。
4. 信号量
它是一個計數器，用于為多個程序提供對共享資料對象的通路。
5. 共享存儲
允許多個程序共享一個給定的存儲區。因為資料不需要在程序之間複制，是以這是最快的一種 IPC。
需要使用信号量用來同步對共享存儲的通路。
多個程序可以将同一個檔案映射到它們的位址空間進而實作共享記憶體。另外 XSI 共享記憶體不是使用檔案，而是使用使用記憶體的匿名段。
6. 套接字
與其它通信機制不同的是，它可用于不同機器間的程序通信。
三、死鎖
必要條件
- 互斥：每個資源要麼已經配置設定給了一個程序，要麼就是可用的。
- 占有和等待：已經得到了某個資源的程序可以再請求新的資源。
- 不可搶占：已經配置設定給一個程序的資源不能強制性地被搶占，它隻能被占有它的程序顯式地釋放。
- 環路等待：有兩個或者兩個以上的程序組成一條環路，該環路中的每個程序都在等待下一個程序所占有的資源。
處理方法
主要有以下四種方法：
- 鴕鳥政策
- 死鎖檢測與死鎖恢複
- 死鎖預防
- 死鎖避免
鴕鳥政策
把頭埋在沙子裡，假裝根本沒發生問題。
因為解決死鎖問題的代價很高，是以鴕鳥政策這種不采取任務措施的方案會獲得更高的性能。
當發生死鎖時不會對使用者造成多大影響，或發生死鎖的機率很低，可以采用鴕鳥政策。
大多數作業系統，包括 Unix，Linux 和 Windows，處理死鎖問題的辦法僅僅是忽略它。
死鎖檢測與死鎖恢複
不試圖阻止死鎖，而是當檢測到死鎖發生時，采取措施進行恢複。
1. 每種類型一個資源的死鎖檢測
上圖為資源配置設定圖，其中方框表示資源，圓圈表示程序。資源指向程序表示該資源已經配置設定給該程序，程序指向資源表示程序請求擷取該資源。
圖 a 可以抽取出環，如圖 b，它滿足了環路等待條件，是以會發生死鎖。
每種類型一個資源的死鎖檢測算法是通過檢測有向圖是否存在環來實作，從一個節點出發進行深度優先搜尋，對通路過的節點進行标記，如果通路了已經标記的節點，就表示有向圖存在環，也就是檢測到死鎖的發生。
2. 每種類型多個資源的死鎖檢測
上圖中，有三個程序四個資源，每個資料代表的含義如下：
- E 向量：資源總量
- A 向量：資源剩餘量
- C 矩陣：每個程序所擁有的資源數量，每一行都代表一個程序擁有資源的數量
- R 矩陣：每個程序請求的資源數量
程序 P1 和 P2 所請求的資源都得不到滿足，隻有程序 P3 可以，讓 P3 執行，之後釋放 P3 擁有的資源，此時 A = (2 2 2 0)。P2 可以執行，執行後釋放 P2 擁有的資源，A = (4 2 2 1) 。P1 也可以執行。所有程序都可以順利執行，沒有死鎖。
算法總結如下：
每個程序最開始時都不被标記，執行過程有可能被标記。當算法結束時，任何沒有被标記的程序都是死鎖程序。
- 尋找一個沒有标記的程序 Pi，它所請求的資源小于等于 A。
- 如果找到了這樣一個程序，那麼将 C 矩陣的第 i 行向量加到 A 中，标記該程序，并轉回 1。
- 如果沒有這樣一個程序，算法終止。
3. 死鎖恢複
- 利用搶占恢複
- 利用復原恢複
- 通過殺死程序恢複
死鎖預防
在程式運作之前預防發生死鎖。
1. 破壞互斥條件
例如假脫機列印機技術允許若幹個程序同時輸出，唯一真正請求實體列印機的程序是列印機守護程序。
2. 破壞占有和等待條件
一種實作方式是規定所有程序在開始執行前請求所需要的全部資源。
3. 破壞不可搶占條件
4. 破壞環路等待
給資源統一編号，程序隻能按編号順序來請求資源。
死鎖避免
在程式運作時避免發生死鎖。
1. 安全狀态
圖 a 的第二列 Has 表示已擁有的資源數，第三列 Max 表示總共需要的資源數，Free 表示還有可以使用的資源數。從圖 a 開始出發，先讓 B 擁有所需的所有資源（圖 b），運作結束後釋放 B，此時 Free 變為 5（圖 c）；接着以同樣的方式運作 C 和 A，使得所有程序都能成功運作，是以可以稱圖 a 所示的狀态時安全的。
定義：如果沒有死鎖發生，并且即使所有程序突然請求對資源的最大需求，也仍然存在某種排程次序能夠使得每一個程序運作完畢，則稱該狀态是安全的。
安全狀态的檢測與死鎖的檢測類似，因為安全狀态必須要求不能發生死鎖。下面的銀行家算法與死鎖檢測算法非常類似，可以結合着做參考對比。
2. 單個資源的銀行家算法
一個小城鎮的銀行家，他向一群客戶分别承諾了一定的貸款額度，算法要做的是判斷對請求的滿足是否會進入不安全狀态，如果是，就拒絕請求；否則予以配置設定。
上圖 c 為不安全狀态，是以算法會拒絕之前的請求，進而避免進入圖 c 中的狀态。
3. 多個資源的銀行家算法
上圖中有五個程序，四個資源。左邊的圖表示已經配置設定的資源，右邊的圖表示還需要配置設定的資源。最右邊的 E、P 以及 A 分别表示：總資源、已配置設定資源以及可用資源，注意這三個為向量，而不是具體數值，例如 A=(1020)，表示 4 個資源分别還剩下 1/0/2/0。
檢查一個狀态是否安全的算法如下：
- 查找右邊的矩陣是否存在一行小于等于向量 A。如果不存在這樣的行，那麼系統将會發生死鎖，狀态是不安全的。
- 假若找到這樣一行，将該程序标記為終止，并将其已配置設定資源加到 A 中。
- 重複以上兩步，直到所有程序都标記為終止，則狀态時安全的。
如果一個狀态不是安全的，需要拒絕進入這個狀态。
四、記憶體管理
虛拟記憶體
虛拟記憶體的目的是為了讓實體記憶體擴充成更大的邏輯記憶體，進而讓程式獲得更多的可用記憶體。
為了更好的管理記憶體，作業系統将記憶體抽象成位址空間。每個程式擁有自己的位址空間，這個位址空間被分割成多個塊，每一塊稱為一頁。這些頁被映射到實體記憶體，但不需要映射到連續的實體記憶體，也不需要所有頁都必須在實體記憶體中。當程式引用到不在實體記憶體中的頁時，由硬體執行必要的映射，将缺失的部分裝入實體記憶體并重新執行失敗的指令。
從上面的描述中可以看出，虛拟記憶體允許程式不用将位址空間中的每一頁都映射到實體記憶體，也就是說一個程式不需要全部調入記憶體就可以運作，這使得有限的記憶體運作大程式成為可能。例如有一台計算機可以産生 16 位位址，那麼一個程式的位址空間範圍是 0~64K。該計算機隻有 32KB 的實體記憶體，虛拟記憶體技術允許該計算機運作一個 64K 大小的程式。
分頁系統位址映射
記憶體管理單元（MMU）管理着位址空間和實體記憶體的轉換，其中的頁表（Page table）存儲着頁（程式位址空間）和頁框（實體記憶體空間）的映射表。
一個虛拟位址分成兩個部分，一部分存儲頁面号，一部分存儲偏移量。
下圖的頁表存放着 16 個頁，這 16 個頁需要用 4 個比特位來進行索引定位。例如對于虛拟位址（0010 000000000100），前 4 位是存儲頁面号 2，讀取表項内容為（110 1），頁表項最後一位表示是否存在于記憶體中，1 表示存在。後 12 位存儲偏移量。這個頁對應的頁框的位址為 （110 000000000100）。
頁面置換算法
在程式運作過程中，如果要通路的頁面不在記憶體中，就發生缺頁中斷進而将該頁調入記憶體中。此時如果記憶體已無空閑空間，系統必須從記憶體中調出一個頁面到磁盤對換區中來騰出空間。
頁面置換算法和緩存淘汰政策類似，可以将記憶體看成磁盤的緩存。在緩存系統中，緩存的大小有限，當有新的緩存到達時，需要淘汰一部分已經存在的緩存，這樣才有空間存放新的緩存資料。
頁面置換算法的主要目标是使頁面置換頻率最低（也可以說缺頁率最低）。
1. 最佳
OPT, Optimal replacement algorithm
所選擇的被換出的頁面将是最長時間内不再被通路，通常可以保證獲得最低的缺頁率。
是一種理論上的算法，因為無法知道一個頁面多長時間不再被通路。
舉例：一個系統為某程序配置設定了三個實體塊，并有如下頁面引用序列：
開始運作時，先将 7, 0, 1 三個頁面裝入記憶體。當程序要通路頁面 2 時，産生缺頁中斷，會将頁面 7 換出，因為頁面 7 再次被通路的時間最長。
2. 最近最久未使用
LRU, Least Recently Used
雖然無法知道将來要使用的頁面情況，但是可以知道過去使用頁面的情況。LRU 将最近最久未使用的頁面換出。
為了實作 LRU，需要在記憶體中維護一個所有頁面的連結清單。當一個頁面被通路時，将這個頁面移到連結清單表頭。這樣就能保證連結清單表尾的頁面是最近最久未通路的。
因為每次通路都需要更新連結清單，是以這種方式實作的 LRU 代價很高。
3. 最近未使用
NRU, Not Recently Used
每個頁面都有兩個狀态位：R 與 M，當頁面被通路時設定頁面的 R=1，當頁面被修改時設定 M=1。其中 R 位會定時被清零。可以将頁面分成以下四類：
- R=0，M=0
- R=0，M=1
- R=1，M=0
- R=1，M=1
當發生缺頁中斷時，NRU 算法随機地從類編号最小的非空類中挑選一個頁面将它換出。
NRU 優先換出已經被修改的髒頁面（R=0，M=1），而不是被頻繁使用的幹淨頁面（R=1，M=0）。
4. 先進先出
FIFO, First In First Out
選擇換出的頁面是最先進入的頁面。
該算法會将那些經常被通路的頁面也被換出，進而使缺頁率升高。
5. 第二次機會算法
FIFO 算法可能會把經常使用的頁面置換出去，為了避免這一問題，對該算法做一個簡單的修改：
當頁面被通路 (讀或寫) 時設定該頁面的 R 位為 1。需要替換的時候，檢查最老頁面的 R 位。如果 R 位是 0，那麼這個頁面既老又沒有被使用，可以立刻置換掉；如果是 1，就将 R 位清 0，并把該頁面放到連結清單的尾端，修改它的裝入時間使它就像剛裝入的一樣，然後繼續從連結清單的頭部開始搜尋。
6. 時鐘
Clock
第二次機會算法需要在連結清單中移動頁面，降低了效率。時鐘算法使用環形連結清單将頁面連接配接起來，再使用一個指針指向最老的頁面。
分段
虛拟記憶體采用的是分頁技術，也就是将位址空間劃分成固定大小的頁，每一頁再與記憶體進行映射。
下圖為一個編譯器在編譯過程中建立的多個表，有 4 個表是動态增長的，如果使用分頁系統的一維位址空間，動态增長的特點會導緻覆寫問題的出現。
分段的做法是把每個表分成段，一個段構成一個獨立的位址空間。每個段的長度可以不同，并且可以動态增長。
段頁式
程式的位址空間劃分成多個擁有獨立位址空間的段，每個段上的位址空間劃分成大小相同的頁。這樣既擁有分段系統的共享和保護，又擁有分頁系統的虛拟記憶體功能。
分頁與分段的比較
- 對程式員的透明性：分頁透明，但是分段需要程式員顯示劃分每個段。
- 位址空間的次元：分頁是一維位址空間，分段是二維的。
- 大小是否可以改變：頁的大小不可變，段的大小可以動态改變。
- 出現的原因：分頁主要用于實作虛拟記憶體，進而獲得更大的位址空間；分段主要是為了使程式和資料可以被劃分為邏輯上獨立的位址空間并且有助于共享和保護。
五、裝置管理
磁盤結構
- 盤面（Platter）：一個磁盤有多個盤面；
- 磁道（Track）：盤面上的圓形帶狀區域，一個盤面可以有多個磁道；
- 扇區（Track Sector）：磁道上的一個弧段，一個磁道可以有多個扇區，它是最小的實體儲存機關，目前主要有 512 bytes 與 4 K 兩種大小；
- 磁頭（Head）：與盤面非常接近，能夠将盤面上的磁場轉換為電信号（讀），或者将電信号轉換為盤面的磁場（寫）；
- 制動手臂（Actuator arm）：用于在磁道之間移動磁頭；
- 主軸（Spindle）：使整個盤面轉動。
磁盤排程算法
讀寫一個磁盤塊的時間的影響因素有：
- 旋轉時間（主軸轉動盤面，使得磁頭移動到适當的扇區上）
- 尋道時間（制動手臂移動，使得磁頭移動到适當的磁道上）
- 實際的資料傳輸時間
其中，尋道時間最長，是以磁盤排程的主要目标是使磁盤的平均尋道時間最短。
1. 先來先服務
FCFS, First Come First Served
按照磁盤請求的順序進行排程。
優點是公平和簡單。缺點也很明顯，因為未對尋道做任何優化，使平均尋道時間可能較長。
2. 最短尋道時間優先
SSTF, Shortest Seek Time First
優先排程與目前磁頭所在磁道距離最近的磁道。
雖然平均尋道時間比較低，但是不夠公平。如果新到達的磁道請求總是比一個在等待的磁道請求近，那麼在等待的磁道請求會一直等待下去，也就是出現饑餓現象。具體來說，兩端的磁道請求更容易出現饑餓現象。
3. 電梯算法
SCAN
電梯總是保持一個方向運作，直到該方向沒有請求為止，然後改變運作方向。
電梯算法（掃描算法）和電梯的運作過程類似，總是按一個方向來進行磁盤排程，直到該方向上沒有未完成的磁盤請求，然後改變方向。
因為考慮了移動方向，是以所有的磁盤請求都會被滿足，解決了 SSTF 的饑餓問題。
六、連結
編譯系統
以下是一個 hello.c 程式：
#include <stdio.h>
int main()
{
printf("hello, world\n");
return 0;
} 在 Unix 系統上，由編譯器把源檔案轉換為目标檔案。
gcc -o hello hello.c 這個過程大緻如下：
- 預處理階段：處理以 # 開頭的預處理指令；
- 編譯階段：翻譯成彙編檔案；
- 彙編階段：将彙編檔案翻譯成可重定向目标檔案；
- 連結階段：将可重定向目标檔案和 printf.o 等單獨預編譯好的目标檔案進行合并，得到最終的可執行目标檔案。
靜态連結
靜态連結器以一組可重定向目标檔案為輸入，生成一個完全連結的可執行目标檔案作為輸出。連結器主要完成以下兩個任務：
- 符号解析：每個符号對應于一個函數、一個全局變量或一個靜态變量，符号解析的目的是将每個符号引用與一個符号定義關聯起來。
- 重定位：連結器通過把每個符号定義與一個記憶體位置關聯起來，然後修改所有對這些符号的引用，使得它們指向這個記憶體位置。
目标檔案
- 可執行目标檔案：可以直接在記憶體中執行；
- 可重定向目标檔案：可與其它可重定向目标檔案在連結階段合并，建立一個可執行目标檔案；
- 共享目标檔案：這是一種特殊的可重定向目标檔案，可以在運作時被動态加載進記憶體并連結；
動态連結
靜态庫有以下兩個問題：
- 當靜态庫更新時那麼整個程式都要重新進行連結；
- 對于 printf 這種标準函數庫，如果每個程式都要有代碼，這會極大浪費資源。
共享庫是為了解決靜态庫的這兩個問題而設計的，在 Linux 系統中通常用 .so 字尾來表示，Windows 系統上它們被稱為 DLL。它具有以下特點：
- 在給定的檔案系統中一個庫隻有一個檔案，所有引用該庫的可執行目标檔案都共享這個檔案，它不會被複制到引用它的可執行檔案中；
- 在記憶體中，一個共享庫的 .text 節（已編譯程式的機器代碼）的一個副本可以被不同的正在運作的程序共享。
End