30 張圖詳解操作系統總結！

一、概述​​

基本特徵

#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. 即時系統

即時系統要求一個請求在一個確定時間內得到回應。

牛逼啊！接私活必备的 N 个开源项目！赶快收藏吧...

分為硬實時和軟實時，前者必須滿足絕對的截止時間，後者可以容忍一定的超時。

程式同步

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(&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. 哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

下面是一种错误的解法，如果所有哲学家同时拿起左手边的筷子，那么所有哲学家都在等待其它哲学家吃完并释放自己手中的筷子，导致死锁。

#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;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N];              // 每个哲学家一个信号量

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

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了
    check(RIGHT);
    up(&mutex);
}

void eat(int i) {
    down(&mutex);
    state[i] = EATING;
    up(&mutex);
}

// 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行
void check(i) {         
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

2. 读者-写者问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。另外，搜索公众号顶级算法后台回复“算法”，获取一份惊喜礼包。

一个整型变量 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&#39;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&#39;re first writer
   down(&readLock);               //if you&#39;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&#39;re leaving
  if (writecount == 0)         //checks if you&#39;re the last writer
   up(&readLock);               //if you&#39;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
}

进程通信

进程同步与进程通信很容易混淆，它们的区别在于：

• 进程同步：控制多个进程按一定顺序执行；

• 进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

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 mode);
int mkfifoat(int fd, const char *path, mode_t mode);

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

3. 訊息佇列

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

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

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

• #讀取進程可以根據訊息類型選擇性地接收訊息，而不像FIFO 那樣只能預設地接收。

4. 信號量

#它是一個計數器，用於為多個進程提供對共享資料物件的存取。

5. 共享儲存

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

需要使用信號量用來同步對共享儲存的存取。

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

6. 套接字

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

三、記憶體管理

虛擬記憶體

虛擬記憶體的目的是為了讓實體記憶體擴充成更大的邏輯內存，從而讓程式獲得更多可用的內存。

為了更好的管理內存，作業系統將記憶體抽象化為位址空間。每個程式擁有自己的位址空間，這個位址空間被分割成多個區塊，每一塊稱為一頁。這些頁被映射到物理內存，但不需要映射到連續的物理內存，也不需要所有頁都必須在物理內存中。當程式引用到不在實體記憶體中的頁時，由硬體執行必要的映射，將缺少的部分裝入實體記憶體並重新執行失敗的指令。

從上面的描述可以看出，虛擬記憶體允許程式不用將位址空間中的每一頁都映射到實體內存，也就是說一個程式不需要全部調入記憶體就可以運行，這使得有限的記憶體運行大程式成為可能。例如有一台電腦可以產生 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，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。

2. 最近最久未使用

LRU, Least Recently Used

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

4，7，0，7，1，0，1，2，1，2，6

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）：與盤面非常接近，能夠將盤面上的磁場轉換為電訊號（讀取），或將電訊號轉換為盤面的磁場（寫）；另外，搜尋公眾號Linux就該這樣學後台回覆“Linux”，取得一份驚喜禮包。

• 煞車手臂（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 節（已編譯程式的機器碼）的一個副本可以被不同的正在運行的進程共享。

#六、死鎖

必要條件

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

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

• 不可搶佔：已經指派給一個行程的資源不能強制性地被搶佔，它只能被佔有它的進程明確地釋放。

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

處理方法

主要有以下四種方法：

• #鴕鳥策略

• #死鎖偵測與死鎖恢復

• 死鎖預防

• 死鎖避免

#鴕鳥策略

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

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

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

大多數作業系統，包括 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 中。

• 重複以上兩步，直到所有行程都標記為終止，則狀態時安全的。

如果一個狀態不是安全的，需要拒絕進入這個狀態。

以上是30 張圖詳解操作系統總結！的詳細內容。更多資訊請關注PHP中文網其他相關文章！