• 目錄
• 第二章
  2.1_1進程的定義、組成、組成形式、特征
  2.1_2進程的狀態與轉換
  2.1_3進程的控制
  2.1_4進程通信
  2.1_5線程概念和多線程模型
  2.2_1處理機調度的概念層次
  2.2_2處理機調度的時機、切換與過程、方式
  2.2_3調度算法的評價指標
  2.2_4FCFS、SJF、HRRN調度算法
  2.2_5時間片輪轉、優先級調度多級反饋隊列調度算法
  2.3_1進程同步、進程互斥
  2.3_2進程互斥軟件的實現方法
  2.3_3進程互斥的硬件實現方法
  2.3_4信號量機制
  2.3_5用信號量機制實現進程互斥、同步、前驅關系
  2.3_6生產者-消費者問題
  2.3_7多生產者-多消費者問題
  2.3_8讀者-寫者問題
  2.3_9哲學家進餐問題
  2.3_10管程
  2.4_1死鎖的概念
  2.4_2死鎖的處理策略-預防死鎖
  2.4_3死鎖的處理策略-避免死鎖
  2.4_4死鎖的處理策略-檢測和解除

第二章

2.1_1進程的定義、組成、組成形式、特征

重點：

（1） PCB：PCB是進程存在的唯一標志，每個進程都有且僅有一個PCB，其內存放著進程描述信息、進程控制和管理信息、資源分配清單、處理機相關信息。
（2）進程與程序的區別
程序是靜態的，進程是動態的，程序是存儲在某種介質上的二進制代碼，進程對應了程序的執行過程，系統不需要為一個不執行的程序創建進程，一旦進程被創建，就處于不斷變化的動態過程中，對應了一個不斷變化的上下文環境。
程序是永久的，進程是暫時存在的。程序的永久性是相對于進程而言的，只要不去刪除它，它可以永久的存儲在介質當中。

2.1_2進程的狀態與轉換

重點：

**（1）三個重要狀態：
①運行態：占用CPU，其他信息資源具備
②就緒態：不占用CPU，但是其他資源具備，等待CPU
③阻塞態：不占用CPU，其他資源不具備
（2）進程狀態間的轉換（重點：阻塞態不能直接轉化為運行態）
①就緒態->運行態：當有空閑的CPU時，處于就緒態的進程將轉換為運行態
②運行態->就緒態：時間片到，或者CPU被其他高優先級的進程搶占
③運行態->阻塞態：等待系統資源分配，或者等待某事件發生（如i\o中斷，等待輸入）
④阻塞態->就緒態：資源分配到位，或等待的事件發生
**

2.1_3進程的控制

重點：

（1）原語：原語是只能一氣呵成的特殊的程序，任何中斷都不能使之暫停，實現方式是關/開中斷。
相關的原語有：進程的切換、創建、終止、阻塞、喚醒

2.1_4進程通信

重點：

（1）共享存儲：同一時間只能允許一個進程訪問

（2）管道通信：只能單向傳輸，且個進程要互斥的訪問管道

（3）消息傳遞：有消息頭和消息體

2.1_5線程概念和多線程模型

重點：

（1）什么是線程：

（2）引入線程后的系統開銷

（3）線程的屬性

（3）線程的實現方式：用戶級線程和內核級線程（重點內核級線程才是處理機分配的單元）

2.2_1處理機調度的概念層次

2.2_2處理機調度的時機、切換與過程、方式

重點：

（1）進程在操作系統內核臨界區中不能進行調度與切換，但在普通臨界區中能進行調度；（補充：臨界區）

2.2_3調度算法的評價指標

2.2_4FCFS、SJF、HRRN調度算法

重點：

（1）先來先服務（FCFS/First Come First Serve）
**規則：**顧名思義，先來先服務

（2）短作業優先（SJF/Shortest Job First）
①非搶占式的短作業優先算法
**規則：**每次調度時選擇當前已到達且運行時間最短的作業/進程

②搶占式的短作業優先算法
**規則：**每當有進程加入就緒隊列改變時就需要調度,如果新到達的進程剩余時間比當前運行的進程剩余時間更短,則由新進程搶占處理機,當前運行進程重新回到就緒隊列。另外,當一個進程完成時也需要調度

（3）高響應比優先算法（HRRN/Highest Response Ratio Next）
**規則：**非搶占式的調度算法，只有當前運行的進 程主動放棄CPU時（正常/異常完成，或主動阻塞），才需要進 行調度，調度時計算所有就緒進程的響應比，選響應比最高的 進程上處理機。

2.2_5時間片輪轉、優先級調度多級反饋隊列調度算法

重點：

（1）時間片輪轉
**規則：**輪流讓就緒隊列中的進程依次執行一個時間片（每次選擇的都是排在就緒隊列隊頭的進程）

（2）優先級調度
**補充：優先級：**靜態優先級：創建進程時確定，之后一直不變。
動態優先級：創建進程時會有一個初始值，之后會根據情況動態的調整優先級。
**通常：**系統進程優先級高于用戶進程、前臺進程優先級高于后臺進程優先級、操作系統更偏好I/O型設備
優先級越大或者越小時優先級越高，具體根據題目判斷
**①非搶占式的優先級調度算法
規則：**每次調度時選擇當前已達到且優先級最高的進程。當前進程主動放棄處理機時發生調度

**②搶占式的優先級調度算法
規則：**每次調度時選擇當前已達到且優先級最高的進程。當前進程主動放棄處理機時發生調度，另外，當就緒隊列發生改變時也需要檢查是否會發生搶占。

（3）多級反饋隊列調度算法
規則：

2019 王道考研 操作系統

2.3_1進程同步、進程互斥

重點：

（1）進程互斥

（2）進程互斥遵循的四個原則：空閑讓進、忙則等待、有限等待、讓權等待。

2.3_2進程互斥的軟件實現方法

重點：

（1）單標志法

缺點：

（2）雙標志先檢查法
缺點：

（3）雙編制后檢查法
缺點：

（4）Peterson算法

后客氣的等待

2.3_3進程互斥的硬件實現方法

重點：中斷屏蔽過程

**原理：**在某進程開始訪問臨界區到訪問結束都不允許被中斷，也就不能發生過程切換，因此也不可能發生兩個同事訪問臨界區的情況（但是不適用于多處理機，因為在另一個處理機中臨界區并沒有中斷，因此可以訪問臨界區）

（2）TestAndSetLock指令適用于多處理機

（3）Swap指令

2.3_4信號量機制

重點：

（1）P、V原語
wait、signal原語常簡稱為P、V原語
C語言描述：

（2）整形信號量
**概念：**用一個整型變量作為信號量，數值便是某種資源的數量，當變量為零時表明所有資源都已被占用。
**實現過程：**若S的初始值為1，若第一個進程要占用打印機，則執行wait原語，將S–，此時S=0，之后去占用打印機，此時若另一個進程2請求使用打印機，則進程2會先執行wait原語，檢查S是否等于0，若等于0則說明打印機正在占用，進程2會循環執行while（S <= 0），直到進程1使用結束并調用signal原語將S++、
**缺點：**會忙等，而且有一點bug，因為進程2在循環執行wait原語中的while（S <= 0）語句，那么是不是一直沒法中斷，沒法切換到其他程序呢

（3）記錄型信號量
**概念：**與整形信號量不同，記錄型信號量的wait原語不僅將信號量減一，而且還會檢查信號量減一后是否小于零，若小于零則說明在減一之前臨界區已經被占用完，然后會將當前請求訪問臨界區的進程掛到等待隊列并將此進程從運行態轉為阻塞態。

2.3_5用信號量機制實現進程互斥、同步、前驅關系

重點：

**（1）進程互斥：**設置互斥信號mutex（例：semaphore mutex = n）（semaphore：信號量）

**（2）進程同步：**設置同步信號量S，初始為0，如果需要實現a代碼在b代碼之前執行，則在a代碼后加V(S),使得S = 1，
在b代碼前加P(S),這樣就會使得當a未執行時S為0，b代碼被阻塞，當a執行完，S++，b可以運行。

（3）前驅關系

2.3_6生產者-消費者問題

（1）問題描述
①系統中有一組生產者進程和一組消費者進程
②生產者進程每次生產一個產品放入緩沖區（即貨架），消費者進程每次從緩沖區（貨架）中取出一個產品并使用。(注: 這里的“產品”理解為某種數據)
③生產者、消費者共享一個初始為空、大小為n的緩沖區（即初始貨架上現有產品為0，容量為n）。
④**兩個同步關系：只有緩沖區沒滿時，生產者才能把產品放入緩沖區，否則必須等待。只有緩沖區不空時，消費者才能從中取出產品，否則必須等待。
⑤一個互斥關系：**緩沖區（貨架）是臨界資源，各進程互斥使用
（2）問題解決步驟

（3）解決問題

（4）易錯問題（能否改變相鄰P或者V的順序）

將此代碼中的相鄰的P語句互換的話 producer() { consumer() {while(1) { while (1) {P (empty); P (full) ;P (mutex) ; P (mutex) ;V (mutex) ; V (mutex) ;V (full) ; V (empty) ;} } } } 得到如下代碼 producer() { consumer() {while(1) { while (1) {P (mutex) ; P (mutex) ;P (empty); P (full) ;V (mutex) ; V (mutex) ;V (full) ; V (empty) ;} } } } 分析：換完之后，若當緩沖區（貨架）已滿，且臨界緩沖區無人占用，此時生產進程執行P(mutex)，進入緩沖區執行P(empty)，由于緩沖區已滿，生產者進程阻塞。只有等待消費者進程消費一個產品，但是消費者進程執行P(mutex)，發現臨界緩沖區已經被占用，同樣進入阻塞狀態，這樣就會發生死鎖

可知，P不可以互換，同樣可以證明V可以互換

2.3_7多生產者-多消費者問題

本章重要內容：
①其核心思想在于設置了一個計數器count用來記錄當前正在訪問共享文件的讀進程數。我們可以用count的值來判斷當前進入的進程是否是第一個/最后一個讀進程，從而做出不同的處理。
②另外，對count變量的檢查和賦值不能一氣呵成導致了一些錯誤，如果需要實現“一氣呵成”，自然應該想到用互斥信號量。
③最后，還要認真體會我們是如何解決“寫進程饑餓”問題的。

（1）問題描述
桌子上有一一只盤子，每次只能向其中放入一-個水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，兒子專等著吃盤子中的橘子，女兒專等著吃盤子中的蘋果。只有盤子空時，爸爸或媽媽才可向盤子中放-一個水果。僅當盤子中有自己需要的水果時，兒子或女兒可以從盤子中取出水果。
用PV操作實現上述過程。

（2）解決問題
思路：
dad代碼：首先要看plate是否為一，若為一則將plate減一，互斥信號量減一，并進行放蘋果操作，然后互斥信號量加一，Apple加一，喚醒女兒進程，女兒進程首先看Apple數量，若Apple為一，則先Apple–，然后互斥信號量減為0，進行取出蘋果操作，再講互斥信號量++，將plate++

（3）拓展問題
當plate初值為一的時候，可以通過分析發現不用設置互斥信號量。
但是大于一的時候，必須設置以免兩個生產者同時訪問臨界區進而發生數據覆蓋的問題。

2.3_7讀者-寫者問題

（1）問題描述
有讀者和寫者兩組并發進程，共享一個文件，當兩個或兩個以上的讀進程同時訪問共享數據時不會產生副作用，但若某個寫進程和其他進程(讀進程或寫進程)同時訪問共享數據時則可能導致數據不一致的錯誤。因此要求:
①允許多個讀者可以同時對文件執行讀操作;
②只允許一個寫者往文件中寫信息;
③任一 寫者在完成寫操作之前不允許其他讀者或寫者工作;
④寫者執行寫操作前，應讓已有的讀者和寫者全部退出。

（2）一步步解決問題
第一步代碼：

semaphore rw=1;//用于實現對文件的互斥訪問。表示當前是否有進程在訪問共享文件 int count = 0;//記錄當前有幾個讀進程在訪問文件 writer() {while (1) {P (rw) ;//寫之前“加鎖"寫文件.V (rw) ;//寫之后“解鎖”} } reader() {while(1) {if (count==0)P(rw); //第一個讀進程負責“加鎖”count++;//訪問文件的讀進程數+1讀文件....count- - - ;//訪問文件的讀進程數-1if (count==0)V(rw);//最后一個讀進程負責“解鎖”} }

**此代碼缺陷：**可能前一個瞬間一個讀者操作執行到了if (count == 0)P(rw);后一個瞬間切換到了另一個讀者進程，同樣執行了if (count==0)；這樣就會出現第二個進程執行P(rw);的時候阻塞進而不能實現這兩個讀進程同時或者共同讀文件的操作，因此需要作出如下改進：

semaphore rw=1;//用于實現對文件的互斥訪問。表示當前是否有進程在訪問共享文件 int count = 0;//記錄當前有幾個讀進程在訪問文件 semaphore mutex = 1//用于將if (count==0)P(rw);語句“一氣呵成” writer() {while (1) {P (rw) ;//寫之前“加鎖"寫文件.V (rw) ;//寫之后“解鎖”} } reader() {while(1) {P(mutex);/ /改動之處用于將if (count==0)P(rw);語句“一氣呵成”if (count==0)P(rw); //第一個讀進程負責“加鎖”V(mutex);count++;//訪問文件的讀進程數+1讀文件....count- - - ;//訪問文件的讀進程數-1if (count==0)V(rw);//最后一個讀進程負責“解鎖”} }

**此代碼缺陷：**改動之后仍有缺陷，那就是很有可能讀者源源不斷，使得寫者餓死，所以需要進一步改進

semaphore rw=1;//用于實現對文件的互斥訪問。表示當前是否有進程在訪問共享文件 int count = 0;//記錄當前有幾個讀進程在訪問文件 semaphore mutex = 1//用于將if (count==0)P(rw);語句“一氣呵成” semaphore w = 1;//用于解決寫者餓死現象 writer() {while (1) {P(w);/ /P (rw) ;//寫之前“加鎖"寫文件.V (rw) ;//寫之后“解鎖”V(w);/ /} } reader() {while(1) {P(w);/ /P(mutex);if (count==0)P(rw); //第一個讀進程負責“加鎖”V(mutex);V(w);/ /count++;//訪問文件的讀進程數+1讀文件....count- - - ;//訪問文件的讀進程數-1if (count==0)V(rw);//最后一個讀進程負責“解鎖”} }

**分析：**這樣就解決了寫者餓死問題，我們來分析一下，當有讀者讀文件的時候，寫者執行P(w);
然后執行P(rw);發生堵塞，一直等待讀者進程執行V(rw);若此時有其他讀者進程將要執行，則執行P(w);會發生堵塞；
不過我認為這個w信號量用mutex替代就行，所以進行了如下改進:

semaphore rw=1;//用于實現對文件的互斥訪問。表示當前是否有進程在訪問共享文件 int count = 0;//記錄當前有幾個讀進程在訪問文件 semaphore mutex = 1//用于將if (count==0)P(rw);語句“一氣呵成”以及解決寫者餓死現象 writer() {while (1) {P(mutex );/ /P (rw) ;//寫之前“加鎖"寫文件.V (rw) ;//寫之后“解鎖”V(mutex );/ /} } reader() {while(1) {P(mutex);if (count==0)P(rw); //第一個讀進程負責“加鎖”V(mutex);count++;//訪問文件的讀進程數+1讀文件....count- - - ;//訪問文件的讀進程數-1if (count==0)V(rw);//最后一個讀進程負責“解鎖”} }

2.3_9哲學家進餐問題

（1）問題描述
一張圓桌上坐著5名哲學家，每兩個哲學家之間的桌.上擺一根筷子， 桌子的中間是一碗米飯。哲學家們傾注畢生的精力用于思考和進餐，哲學家在思考時，并不影響他人。只有當哲學家饑餓時，才試圖拿起左、右兩根筷子(一根一根地拿起)。如果筷子已在他人手上，則需等待。饑餓的哲學家只有同時拿起兩根筷子才可以開始進餐，當進餐完畢后，放下筷子繼續思考。
（2）三種解決方案
①可以對哲學家進程施加一些限制條件，比如最多允許四個哲學家同時進餐。這樣可以保證至少有一個哲學家是可以拿到左右兩只筷子的
②要求奇數號哲學家先拿左邊的筷子，然后再拿右邊的筷子，而偶數號哲學家剛好相反。用這種方法可以保證如果相鄰的兩個奇偶號哲學家都想吃飯，那么只會有其中一個可以拿起第一只筷 子，另一個會直接阻塞。 這就避免了占有一支后再等待另一只的情況。
③將拿左邊筷子和拿右邊筷子使用互斥信號量一氣呵成

semaphore chopstick[5]={1,1,1,1,1} ; semaphore mutex = 1; / /互斥地取筷子 Pi(){//i號哲學家的進程while(1) {P (mutex) ;P (chopstick[i]) ;//拿左P (chopstick[ (i+1)85]) ;//拿右V (mutex) ;吃飯...V (chopstick[i]) ;//放左V (chopstick[ (i+1)號5]) ;//放右思考..} }

2.3_10管程

2.4_1死鎖的概念

本節大綱：什么是死鎖、死鎖產生的必要條件、死鎖的處理策略
（1）什么是死鎖
在并發環境下，各進程因競爭資源而造成的一種，== 互相等
待對方手里的資源，導致各進程都阻塞都無法向前推進的現象，就是死鎖==。發生死鎖后若無外力干涉、這些進程都將無法向前推進一步。
（2）死鎖產生的必要條件
產生死鎖必須同時滿足一下四個條件，只要其中任一條件不成立，死鎖就不會發生。
①互斥條件:只有對必須互斥使用的資源（臨界資源) 的爭搶才會導致死鎖(如哲學家的筷子、打印機設備)像內存、揚聲器這樣可以同時讓多個進程使用的資源是不會導致死鎖的(因為進程不用阻塞等待這種資源)
②不剝奪條件:進程所獲得的資源在未使用完之前，不能由其他進程強行奪走，只能主動釋放。（不可搶占其他進程的資源）
③請求和保持條件:進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進程占有，此時請求進程被阻塞，但又對自己已有的資源保持不放。
④循環等待條件:存在一種進程資源的循環等待鏈（你等我、我等他、他等你），鏈中的每一個進程已獲得的資源同時被下一個進程所請求。
（3）死鎖的處理政策
①預防死鎖（靜態策略）。破壞死鎖產生的四個必要條件中的一個或幾個。
②避免死鎖（動態策略）。用某種方法防止系統進入不安全狀態，從而避免死鎖(銀行家算法)
③死鎖的檢測和解除。允許死鎖的發生，不過操作系統會負責檢測出死鎖的發生，然后采取某種措
施解除死鎖。

2.4_2死鎖的處理策略-預防死鎖

本節大綱：預防死鎖的四個方式：破壞互斥條件、破壞不剝奪條件、破壞請求和保持條件、破壞循環等待條件（此法為靜態策略，即只需改變某些起始條件，后續無需改動）
①破壞互斥條件
**破壞互斥條件：**如果把只能互斥使用的資源改造為允許共享使用，則系統不會進入死鎖狀態。比如: SPOOLing技術。操作系統可以采用SPOOLing技術把獨占設備在邏輯上改造成共享設備。比如，用SPOOLing技 術將打印機改造為共享設備

缺點:
并不是所有的資源都可以改造成可共享使用的資源。并且為了系統安全，很多地方還必須保護這種互斥性。因此，很多時候都無法破壞互斥條件。

②破壞不剝奪條件
破壞不剝奪條件:
方案一（自行釋放所有資源）:當某個進程請求新的資源得不到滿足時，它必須立即釋放保持的所有資源，待以后需要時再重新申請。也就是說，即使某些資源尚未使用完，也需要主動釋放，從而破壞了不可剝奪條件。
方案二（搶占其他進程資源）:當某個進程需要的資源被其他進程所占有的時候，可以由操作系統協助，將想要的資源強行剝奪。這種方式一般需要考慮各進程的優先級(比如:剝奪調度方式，就是將處理機資源強行剝奪給優先級更高的進程使用)
缺點:
1.實現起來比較復雜。
2.釋放已獲得的資源可能造成前一階段工作的失效。因此這種方法一般只適用于易保存和恢復狀態的資源，如CPU。
③破壞請求和保持條件
破壞請求和保持條件
可以采用靜態分配方法（即原子分配），即進程在運行前一次申請完它所需要的全部資源，在它的資源未滿足前，不讓它投入運行。一旦投入運行后，這些資源就一直歸它所有，該進程就不會再請求別的任何資源了。
缺點:
有些資源可能只需要用很短的時間，因此如果進程的整個運行期間都一直保持著所有資源，就會造成嚴重的資源浪費，資源利用率極低。另外，該策略也有可能導致某些進程饑餓。

④破壞循環等待條件
可采用順序資源分配法。首先給系統中的資源編號，規定每個進程必須按編號遞增的順序請求資源，同類資源(即編號相同的資源)一次申請完。
原理分析:一個進程只有已占有小編號的資源時，才有資格申請更大編號的資源。按此規則，已持有大編號資源的進程不可能逆向地回來申請小編號的資源，從而就不會產生循環等待的現象。
缺點:
1.不方便增加新的設備，因為可能需要重新分配所有的編號;
2.進程實際使用資源的順序可能和編號遞增順序不一-致， 會導致資源
浪費;

2.4_3死鎖的處理策略-避免死鎖

本節大綱：什么是安全序列和安全狀態、銀行家算法（此法為動態策略，即一步一檢測）
（1）安全序列和安全狀態
安全序列就是指如果系統按照這種序列分配資源，則每個進程都能順利完成。只要能找出一個安全序列，系統就是安全狀態。當然，安全序列可能有多個。

（2）銀行家算法
**“銀行家算法”的核心思想：**在資源分配之前預先判斷這次分配是否會導致系統進入不安全狀態，以此決定是否答應資源分配請求。
銀行家算法步驟:
①檢查此次申請是否超過了之前聲明的最大需求數
②檢查此時系統剩余的可用資源是否還能滿足這次請求
③試探著分配，更改各數據結構
④用安全性算法檢查此次分配是否會導致系統進入不安全狀態
安全性算法步驟:
檢查當前的剩余可用資源是否能滿足某個進程的最大需求，如果可以，就把該進程加入安全序列，并把該進程持有的資源全部回收。
不斷重復上述過程，看最終是否能讓所有進程都加入安全序列。

2.4_4死鎖的處理策略-檢測和解除

本節大綱：資源分配數據結構、如何根據數據結構進行檢測和解除
（1）數據結構

（2）死鎖的檢測
檢測死鎖的算法:
1)在資源分配圖中，找出既不阻塞又不是孤點的進程Pi (即找出一條有向邊與它相連，且該有向邊對應資源的申請數量小于等于系統中已有空閑資源數量。如下圖中，R1沒有空閑資源，R2有一個空閑資源。若所有的連接該進程的邊均滿足上述條件，則這個進程能繼續運行直至完成，然后釋放它所占有的所有資源)。消去它所有的請求邊和分配邊，使之稱為孤立的結點。在下圖中，P1是滿足這一條件的進程結點，于是將P1的所有邊消去。
2)進程Pi所釋放的資源，可以喚醒某些因等待這些資源而阻塞的進程，原來的阻塞進程可能變為非阻塞進程。在下圖中，P2 就滿足這樣的條件。根據1)中的方法進行一=系列簡化后，若能消去途中所有的邊，則稱該圖是可完全簡化的。.

可完全簡化：

不可完全簡化：

（3）死鎖的解除
① 資源剝奪法。掛起(暫時放到外存上)某些死鎖進程，并搶占它的資源，將這些資源分配給
其他的死鎖進程。但是應防止被掛起的進程長時間得不到資源而饑餓。
②撤銷進程法(或稱終止進程法)。強制撤銷部分、甚至全部死鎖進程，并剝奪這些進程的資
源。這種方式的優點是實現簡單，但所付出的代價可能會很大。因為有些進程可能已經運行
了很長時間，已經接近結束了，一旦被終止可謂功虧一簣， 以后還得從頭再來。
③進程回退法。 讓一個或多個死鎖進程回退到足以避免死鎖的地步。這就要求系統要記錄進程
的歷史信息，設置還原點。

總結

以上是生活随笔為你收集整理的操作系统（王道笔记第二章）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。