一、概述

基本特徵

1. 併發

併發是指宏觀上在一段時間內能同時執行多個程式，而並行則指同一時刻能執行多個指令。

並行需要硬體支援，如多流水線、多核處理器或者分散式計算系統。

作業系統透過引入行程和執行緒，使得程式能夠併發執行。

2. 共享

共享是指系統中的資源可以被多個併發行程共同使用。

有兩種共享方式：互斥共享和同時共享。

互斥共享的資源稱為臨界資源，例如印表機等，在同一時間只允許一個行程訪問，需要用同步機制來實現對臨界資源的訪問。

3. 虛擬

虛擬技術把一個物理物體轉換為多個邏輯物體。

主要有兩種虛擬技術：時分復用技術和空分復用技術。

多個行程能在同一個處理器上併發執行使用了時分復用技術，讓每個行程輪流佔有處理器，每次只執行一小個時間片並快速切換。

虛擬記憶體使用了空分復用技術，它將物理記憶體抽象為地址空間，每個行程都有各自的地址空間。地址空間的頁被對映到物理記憶體，地址空間的頁並不需要全部在物理記憶體中，當使用到一個沒有在物理記憶體的頁時，執行頁面置換演演算法，將該頁置換到記憶體中。

4. 非同步

非同步指行程不是一次性執行完畢，而是走走停停，以不可知的速度向前推進。

基本功能

1. 行程管理

行程控制、行程同步、行程通訊、死鎖處理、處理機排程等。

2. 記憶體管理

記憶體分配、地址對映、記憶體保護與共享、虛擬記憶體等。

3. 檔案管理

檔案儲存空間的管理、目錄管理、檔案讀寫管理和保護等。

4. 裝置管理

完成使用者的 I/O 請求，方便使用者使用各種裝置，並提高裝置的利用率。

主要包括緩衝管理、裝置分配、裝置處理、虛擬裝置等。

系統呼叫

如果一個行程在使用者態需要使用核心態的功能，就進行系統呼叫從而陷入核心，由作業系統代為完成。

Linux 的系統呼叫主要有以下這些：

大內核和微核心

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 N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(∅);
        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(∅);
    }
}

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() {

 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


//reading is performed


 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() {
  
  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


 down(&resource;);                //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource
  //writing is performed
 up(&resource;);                //release file


  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
    // 
    down(&resourceAccess;);         // request exclusive access to resource
    // 
    up(&serviceQueue;);           // let next in line be serviced

    // 
    writeResource();            // writing is performed
    // 

    // 
    up(&resourceAccess;);         // release resource access for next reader/writer
    // 
}

void reader()
{ 
    down(&serviceQueue;);           // wait in line to be serviced
    down(&readCountAccess;);        // request exclusive access to readCount
    // 
    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
    // 
    up(&serviceQueue;);           // let next in line be serviced
    up(&readCountAccess;);        // release access to readCount

    // 
    readResource();             // reading is performed
    // 

    down(&readCountAccess;);        // request exclusive access to readCount
    // 
    readCount--;                // update count of active readers
    if (readCount == 0)         // if there are no readers left:
        up(&resourceAccess;);     // release resource access for all
    // 
    up(&readCountAccess;);        // release access to readCount
}

2. 哲學家進餐問題

五個哲學家圍著一張圓桌，每個哲學家面前放著食物。哲學家的生活有兩種交替活動：吃飯以及思考。當一個哲學家吃飯時，需要先拿起自己左右兩邊的兩根筷子，並且一次只能拿起一根筷子。

下麵是一種錯誤的解法，考慮到如果所有哲學家同時拿起左手邊的筷子，那麼就無法拿起右手邊的筷子，造成死鎖。

#define N 5

void philosopher(int i) {
    while(TRUE) {
        think();
        take(i);       // 拿起左邊的筷子
        take((i+1)%N); // 拿起右邊的筷子
        eat();
        put(i);
        put((i+1)%N);
    }
}

為了防止死鎖的發生，可以設定兩個條件：

• 必須同時拿起左右兩根筷子；

• 只有在兩個鄰居都沒有進餐的情況下才允許進餐。

#define N 5
#define LEFT (i + N - 1) % N // 左鄰居
#define RIGHT (i + 1) % N    // 右鄰居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟蹤每個哲學家的狀態
semaphore mutex = 1;         // 臨界區的互斥
semaphore s[N];              // 每個哲學家一個訊號量

void philosopher(int i) {
    while(TRUE) {
        think();
        take_two(i);
        eat();
        put_two(i);
    }
}

void take_two(int i) {
    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 
int pipe(int fd[2]);

它具有以下限制：

• 只支援半雙工通訊（單向交替傳輸）；

• 只能在父子行程中使用。

2. FIFO

也稱為命名管道，去除了管道只能在父子行程中使用的限制。

#include 
int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

FIFO 常用於客戶-伺服器應用程式中，FIFO 用作匯聚點，在客戶行程和伺服器行程之間傳遞資料。

3. 訊息佇列

相比於 FIFO，訊息佇列具有以下優點：

• 訊息佇列可以獨立於讀寫行程存在，從而避免了 FIFO 中同步管道的開啟和關閉時可能產生的困難；

• 避免了 FIFO 的同步阻塞問題，不需要行程自己提供同步方法；

• 讀行程可以根據訊息型別有選擇地接收訊息，而不像 FIFO 那樣只能預設地接收。

4. 訊號量

它是一個計數器，用於為多個行程提供對共享資料物件的訪問。

5. 共享儲存

允許多個行程共享一個給定的儲存區。因為資料不需要在行程之間複製，所以這是最快的一種 IPC。

需要使用訊號量用來同步對共享儲存的訪問。

多個行程可以將同一個檔案對映到它們的地址空間從而實現共享記憶體。另外 XSI 共享記憶體不是使用檔案，而是使用使用記憶體的匿名段。

6. 套接字

與其它通訊機制不同的是，它可用於不同機器間的行程通訊。

三、死鎖

必要條件

• 互斥：每個資源要麼已經分配給了一個行程，要麼就是可用的。

• 佔有和等待：已經得到了某個資源的行程可以再請求新的資源。

• 不可搶佔：已經分配給一個行程的資源不能強制性地被搶佔，它只能被佔有它的行程顯式地釋放。

• 環路等待：有兩個或者兩個以上的行程組成一條環路，該環路中的每個行程都在等待下一個行程所佔有的資源。

處理方法

主要有以下四種方法：

• 鴕鳥策略

• 死鎖檢測與死鎖恢復

• 死鎖預防

• 死鎖避免

鴕鳥策略

把頭埋在沙子裡，假裝根本沒發生問題。

因為解決死鎖問題的代價很高，因此鴕鳥策略這種不採取任務措施的方案會獲得更高的效能。

當發生死鎖時不會對使用者造成多大影響，或發生死鎖的機率很低，可以採用鴕鳥策略。

大多數作業系統，包括 Unix，Linux 和 Windows，處理死鎖問題的辦法僅僅是忽略它。

死鎖檢測與死鎖恢復

不試圖阻止死鎖，而是當檢測到死鎖發生時，採取措施進行恢復。

1. 每種型別一個資源的死鎖檢測

上圖為資源分配圖，其中方框表示資源，圓圈表示行程。資源指向行程表示該資源已經分配給該行程，行程指向資源表示行程請求獲取該資源。

圖 a 可以抽取出環，如圖 b，它滿足了環路等待條件，因此會發生死鎖。

每種型別一個資源的死鎖檢測演演算法是透過檢測有向圖是否存在環來實現，從一個節點出發進行深度優先搜尋，對訪問過的節點進行標記，如果訪問了已經標記的節點，就表示有向圖存在環，也就是檢測到死鎖的發生。

2. 每種型別多個資源的死鎖檢測

上圖中，有三個行程四個資源，每個資料代表的含義如下：

• E 向量：資源總量

• A 向量：資源剩餘量

• C 矩陣：每個行程所擁有的資源數量，每一行都代表一個行程擁有資源的數量

• R 矩陣：每個行程請求的資源數量

行程 P₁ 和 P₂ 所請求的資源都得不到滿足，只有行程 P₃ 可以，讓 P₃ 執行，之後釋放 P₃ 擁有的資源，此時 A = (2 2 2 0)。P₂ 可以執行，執行後釋放 P₂ 擁有的資源，A = (4 2 2 1) 。P₁ 也可以執行。所有行程都可以順利執行，沒有死鎖。

演演算法總結如下：

每個行程最開始時都不被標記，執行過程有可能被標記。當演演算法結束時，任何沒有被標記的行程都是死鎖行程。

1. 尋找一個沒有標記的行程 P_i，它所請求的資源小於等於 A。

2. 如果找到了這樣一個行程，那麼將 C 矩陣的第 i 行向量加到 A 中，標記該行程，並轉回 1。

3. 如果沒有這樣一個行程，演演算法終止。

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 

int main()
{
    printf("hello, world
");
    return 0;
}

在 Unix 系統上，由編譯器把源檔案轉換為標的檔案。

gcc -o hello hello.c

這個過程大致如下：

• 預處理階段：處理以 # 開頭的預處理命令；

• 編譯階段：翻譯成彙編檔案；

• 彙編階段：將彙編檔案翻譯成可重定向標的檔案；

• 連結階段：將可重定向標的檔案和 printf.o 等單獨預編譯好的標的檔案進行合併，得到最終的可執行標的檔案。

靜態連結

靜態聯結器以一組可重定向標的檔案為輸入，生成一個完全連結的可執行標的檔案作為輸出。聯結器主要完成以下兩個任務：

• 符號解析：每個符號對應於一個函式、一個全域性變數或一個靜態變數，符號解析的目的是將每個符號取用與一個符號定義關聯起來。

• 重定位：聯結器透過把每個符號定義與一個記憶體位置關聯起來，然後修改所有對這些符號的取用，使得它們指向這個記憶體位置。

標的檔案

• 可執行標的檔案：可以直接在記憶體中執行；

• 可重定向標的檔案：可與其它可重定向標的檔案在連結階段合併，建立一個可執行標的檔案；

• 共享標的檔案：這是一種特殊的可重定向標的檔案，可以在執行時被動態載入進記憶體並連結；

動態連結

靜態庫有以下兩個問題：

• 當靜態庫更新時那麼整個程式都要重新進行連結；

• 對於 printf 這種標準函式庫，如果每個程式都要有程式碼，這會極大浪費資源。

共享庫是為瞭解決靜態庫的這兩個問題而設計的，在 Linux 系統中通常用 .so 字尾來表示，Windows 系統上它們被稱為 DLL。它具有以下特點：

• 在給定的檔案系統中一個庫只有一個檔案，所有取用該庫的可執行標的檔案都共享這個檔案，它不會被覆制到取用它的可執行檔案中；

• 在記憶體中，一個共享庫的 .text 節（已編譯程式的機器程式碼）的一個副本可以被不同的正在執行的行程共享。