文章目錄

• 1 緒論
• 2 進程管理

1 緒論

【實時操作系統】

實時的含義是指計算機對于外來信息能夠以足夠快的速度進行處理，并在被控制對象允許的時間范圍內做出快速反應

實時操作系統的主要特點是提供 及時響應 和 高可靠性

【分時操作系統】

分時系統是必須有交互功能的，不存在不一定全部提供人機交互功能的情況。另外，分時系統只是給每個用戶感覺好像是自己獨占了一臺計算機，而不存在真正的獨占整個計算機。實時系統對響應的要求比分時系統高，兩者對于響應的要求是不相似的

【微內核】

微內核的優點：可靠性好（某個服務器產生問題不會引起系統其它服務器的崩潰）、靈活（只要接口規范，可以方便地增刪服務功能）、便于維護、適合分分布式處理環境

缺點：效率不高（尤其通信頻繁的系統）

△?▽

分析：A，理論如上描述

【多道程序設計】

所謂多道程序設計，是指將一個以上的作業放入內存，并且同時處于運行狀態。這些作業共享處理器的時間和外設及其他資源

多道程序設計下，宏觀上進程是同時運行的，但是在微觀上，單處理器某時刻只能處理一個進程

【批處理系統】

批處理系統中，將作業依次以脫機輸入方式輸入到磁帶上，監督程序依次執行磁帶上的作業，作業執行時用戶無法干預其運行。批處理系統按照發展歷程可分為單道批處理系統和多道批處理系統，主要區別為內存中同時存在單個或多個作業。多道批處理系統中的一道程序因 I/O 請求而暫停執行時，借助中斷技術 CPU轉而運行另一道程序

△?▽（2016 年真題）

分析：A，理論如上所述

【中斷處理程序】

中斷處理程序只能是操作系統程序，不可能是應用程序

【接口方式】

操作系統有如下3種接口方式提供給用戶使用：

• 命令接口（交互式命令接口：控制臺或終端；批處理命令接口：由一組作業控制命令組成，事先寫成一份作業操作書，如類似DOS的批命令文件或者UNIX的shell文件）
• 程序接口，也稱為系統調用
• 圖形接口，也稱為圖形界面

【核心態 / 用戶態執行】

1）只能在核心態執行

• 缺頁處理和時鐘中斷都屬于中斷，要修改中斷寄存器，因此只能在核心態執行
• 進程調度（切換） 屬于系統的一部分，也只能在核心態執行
• 常見的特權指令：
  ① 有關對 I/O 設備使用的指令；
  ② 有關訪問程序狀態的指令（如對程序狀態字PSW的指令）；
  ③ 存取特殊寄存器指令（如存取中斷寄存器、時鐘寄存器等指令）
  （注，關中斷指令 為特權指令）

△?▽（2014 年真題）

分析：D，理論如上所述

2）可以在用戶態執行

• 命令解釋程序屬于命令接口，是操作系統提供給用戶所使用的接口，因此可以在用戶態執行
• trap 指令、跳轉指令和壓棧指令 均可以在用戶態執行，其中 trap 指令負責由用戶態轉換成為內核態

△?▽（2011 年真題）

分析：A，理論如上所述

3）發生在用戶態、處理在核心態（換言之，進程從用戶態切換到內核態）

• 系統調用是系統提供給用戶程序調用內核函數的，雖然系統調用執行過程中 CPU 需要切換至核心態，但是系統調用是在用戶態發生的， 如 read、write、open等
• 外部中斷是指由外部事件引起的中斷，比如單擊鼠標或鍵盤輸入等操作引起的中斷、進程缺頁產生的缺頁中斷 等

總結： 系統調用和中斷的發生是在用戶態，處理是在核心態

△?▽（2012 年真題）

分析：C，理論如上所述

△?▽（2013 年真題）

分析：B，理論如上所述

△?▽（2015 年真題）

分析：C，A. 如果除數為 0 的話會引發中斷；B. 軟中斷在內核態執行；D. 涉及訪存，需要進入內核態

【中斷處理和子程序調用】

中斷處理和子程序調用的區別：

中斷的發生通常是突然的，往往是系統無法預知的。由于處理中斷時 CPU 可能會切換狀態（如果是核心態發生中斷則始終為核心態，不需要切換），因此中斷處理返回時就需要還原當時的程序狀態，這就用到了程序狀態字寄存器所存儲的內容

子程序調用是系統能夠預知的，而且子程序調用通常是在進程內部進行的，不會更改程序狀態，即便更改程序狀態，只要更新寄存器就行，而不需要保存，因為一切都是系統預料到的，不需要保護和恢復

故而，子程序調用只需保存程序斷點，即該指令的下一條指令的地址；中斷調用不僅要保護斷點（PC 的內容），而且要保護程序狀態字寄存器的內容 PSW，在中斷處理中，最重要的兩個寄存器是 PC 和 PSWR

△?▽（2012 年真題）

分析：B，理論如上所述

【操作系統裝載】

用戶平時開機時首先啟動的是存于主板上的 ROM 中的 BIOS 程序，其次再由它去調用硬盤中的操作系統，將操作系統的程序自動加載到內存中的系統區，這段區域就是 RAM

△?▽（2013 年真題）

分析：D，理論如上所述

【外部中斷處理過程】

外部中斷處理過程，程序計數器的內容 由 中斷隱指令 自動保存，通用寄存器 的內容由操作系統保存

△?▽（2015 年真題）

【系統調用】

1）基本概念

系統調用即程序接口或應用編程接口，是應用程序同系統之間的接口

△?▽（2010 年真題）

分析：A，理論如上所述

內核提供了一系列具備預定功能的內核函數，通過一組稱為系統調用的接口呈現給用戶。系統調用把應用程序的請求傳給內核，調用相應的內核函數完成所需的處理，并將處理結果返回給應用程序

操作系統提供的系統調用通常包括：進程控制、文件系統控制、系統控制、內存管理、網絡管理、socket 控制、用戶管理以及進程間通信（信號、消息、管道、信號量和共享內存）

△?▽

分析：C，用戶可以在用戶態調用操作系統的服務，但執行具體的系統調用服務程序處于內核態，故 Ⅰ 正確；顯然，Ⅱ、Ⅳ 正確；操作系統不同，底層邏輯和實現方式均不同，為應用程序提供的系統調用接口也不同，Ⅲ 錯誤

2）執行系統調用過程

用戶需要執行系統調用時，

• 首先準備并傳遞系統調用所需的參數，通過陷入（trap）指令進入操作系統的系統內核，此時從用戶態進入內核態
• 之后執行相應的系統調用函數，使用特定的系統內核功能
• 最后將處理結果返回給用戶進程，此時將從內核態返回用戶態

△?▽（2017 年真題）

分析：C，理論如上所述

3）庫函數和系統調用的區別和聯系

區別：庫函數是語言或應用程序的一部分，可以運行在用戶空間中。而系統調用是操作系統的一部分，是內核提供給用戶的程序接口，運行在內核空間中

聯系： 許多庫函數都會使用系統調用來實現功能。沒有使用系統調用的庫函數，執行的效率通常比系統調用高，因為使用系統調用時，需要上下問的切換以及狀態的轉換（從用戶態轉為核心態）

【操作系統主要功能】

操作系統的主要功能包括處理器管理 、存儲器管理 、文件管理 和 設備管理

注意，數據管理屬于文件管理的范疇，網絡管理 不是操作系統的功能

【并行執行與并發性】

并發性是指兩個或兩個以上的進程在執行時間上有重疊，即一個進程的第一個操作在另一個進程的最后一個操作完成之前開始。并發性是指宏觀上在一段時間內有多道程序在同時運行，但在單處理器系統中，每個時刻僅有一道程序在執行，故微觀上這些程序是交替執行的

△?▽（2009 年真題）

分析：D，理論如上描述

兩者的聯系和區別，

• 多重處理即并行執行，多任務處理即多個進程并發執行
• 操作系統既可以支持并發執行也可以支持并行執行
• 并行執行與并發執行不存在包含關系
• 在同一時間間隔內，系統中同時運行多個進程是并發執行的基本概念
• 一個 CPU 可以采用多核架構，可以實現并行執行

△?▽

分析：B，理論如上所述

【層次結構劃分操作系統】

【需要加以保護的指令】

△?▽

分析：2）、4）兩條指令需要加以保護，因為這兩條操作是直接對操作系統本身的內容加以修改。其他幾種指令在一般情況下也應該加以保護，但即使這些操作交由用戶操作，也不會出現像 2）、4）兩種操作那樣的破壞性

【編譯/鏈接】

核心的一句換： 編譯后的模塊需要經過鏈接才能裝載，而鏈接后形成的地址才是整個程序的完整邏輯地址空間

以 C 語言為例：C 語言經過預處理（cpp）$\to$ 編譯（ccl）$\to$ 匯編 （as）$\to$ 鏈接（ld）產生可執行文件

其中，鏈接的前一步，產生了可重定位的二進制的目標文件。C 語言采用源文件獨立編譯的方法，如程序 main.c，file1.c，file2.c，file1.h，file2.h，在鏈接的前一步也就是編譯生成了 main.o，file1.o，file2.o ，這些目標模塊采用的邏輯地址都是從 0 開始，但只是相對于該模塊的邏輯地址。鏈接階段主要完成了重定位，形成整個程序的完整邏輯地址空間

我們給出邏輯地址、線性地址和物理地址的概念：

• 邏輯地址是指在程序各個模塊中的偏移地址，它是相對于當前模塊首地址的地址
• 線性地址是指在分頁式存儲管理中單個程序所有模塊集合在一起構成的地址
• 物理地址是指出現在 CPU 外部地址總線上的尋址物理內存的地址信號，是地址變換的最終結果地址

那么，就能理解為什么說 “ 在虛擬內存管理中，地址變換機構將邏輯地址變換為物理地址，形成該邏輯地址的階段是編譯 ”。 邏輯地址指的就是段內的偏移量而不是鏈接后生成的整個程序全局的邏輯地址空間（即線性地址），所以邏輯地址是編譯時產生的

△?▽（2011 年真題）

分析：B，理論描述如上

【時鐘中斷】

時鐘中斷的主要工作是處理和時間有關的信息以及決定是否執行調度程序，和時間有關的所有信息包括系統時間、進程的時間片、延時、使用 CPU 的時間、各種定時器

△?▽

分析：D，理論如所述

【有關 CPU 利用率、總運行時間的計算】

△?▽

分析：單道，總運行時間為 260ms


多道，總運行時間為 190ms

△?▽

分析：只有當所有進程都在等待 I/O 時，CPU 才會空閑下來。因此 ，需要算出所有進程都在等待 I/O 這種情況發生的概率

設有 $n$ 個進程，則 CPU 的利用率 $u$ 可表示為$$u=1?(0.8{)}^n$$ 在內存為 $32MB$ 時，可容納 $\frac{32?2}{10}=3$ 個用戶進程，則 $$u=1?0.8^3=0.488$$ 內存再增加 $32MB$ 時，又多了 $32/10=3$ 個用戶進程，則 $$u=1?0.8^6=0.738$$

【操作系統設計】

△?▽

分析：可以設計兩個優先隊列，分時作業進入高優先級隊列，采用短時間片的時間輪轉法調度。當高優先級隊列空時，調度低優先級的成批作業，并給予較長的時間片

2 進程管理

【進程狀態的相互轉換】

執行狀態$\to$就緒狀狀態：時間片用完或在搶占式調度中有更高優先級的進程變為就緒態

進程之間的狀態轉換并非都是主動的，很多情況下都是被動的，只有從執行狀態到阻塞狀態是程序的自我行為（因事件而主動調用阻塞原語），其他都是被動的

執行狀態只能由就緒狀態轉換過來，而無法由阻塞狀態直接轉換

區分就緒狀態和阻塞狀態，抓住很關鍵的一句話：當進程處于阻塞狀態時，即便把處理器分配給該進程，它也是無法運行的。所以區分就緒態和阻塞態的關鍵是當分配給該進程處理器時，是否能立即執行，若能立即執行，則處于就緒狀態；反之，則為阻塞狀態

進程被喚醒：進程被當進程被喚醒時，它從阻塞狀態變為就緒態，即可以重新占用 CPU（不是直接占用 CPU，區別于運行狀態）

考慮一個問題：若無進程處于運行狀態，則就緒和等待隊列均為空？

若無進程處于運行狀態，則就緒和等待隊列不一定為空，發生死鎖時，無進程處于運行狀態，而等待隊列不為空

△?▽

分析：C，Ⅲ. 轉就緒態

△?▽

分析：A，B 選項即是上題的 Ⅲ.

△?▽

分析：C，當被阻塞進程等待的某資源（不包括）為可用時，進程將會被喚醒，顯然 Ⅰ、Ⅱ 正確；對于 Ⅲ，當前進程的時間片用完后進入就緒隊列等待重新調度，優先級最高的進程將獲得處理機資源從就緒態變成執行態

【臨界資源】

• 臨界資源與臨界區是兩個不同的概念：臨界資源資源是一種系統資源，需要不同進程互斥訪問，而臨界區則是每個進程中訪問臨界資源的一段代碼，是屬于對應進程的
  （對不同的進程，臨界區的代碼可以不同，關鍵在于這個進程想怎么處理這個臨界資源）
  
• 臨界資源與共享資源的區別：臨界資源與共享資源的區別在于，在一段時間內能否允許多個進程訪問（并發使用），如磁盤即是一種共享設備，而公用隊列則是臨界資源

△?▽

分析：B，理論如上所述

【不能自身修改的代碼】

若代碼可以被多個進程在任一時刻共享，則要求每個進程在調用此代碼時都以同樣的方式運行；而且進程在運行過程中被中斷后繼續執行，其結果也不受影響，這就要求代碼不能修改自身，否則無法滿足共享要求。這種代碼就是可重入代碼，也叫純代碼，即允許多個進程同時訪問

【同步與互斥】

1）互斥的概念與要求

• 空閑讓進：當沒有進程處于臨界區時，可以允許一個請求進入臨界區的進程立即進入到自己的臨界區
• 忙則等待：當已有進程進入其臨界區時，其他試圖進入臨界區的進程必須等待
• 有限等待：對要求訪問臨界資源的進程，應保證能在有限的時間內進入自己的臨界區
• 讓權等待：當一個進程因為某些原因不能進入自己的臨界區時，應釋放處理器給其他進程

2）硬件方法

硬件方法的主要思想是用一條指令完成標志的檢查和修改這兩個操作，因為保證了檢查操作與修改操作不被打斷；或通過中斷屏蔽的方式保證檢查和修改作為一個整體執行。故硬件方法主要有兩種：一種是中斷屏蔽，另一種是硬件指令

優點：① 適用范圍廣；② 簡單，硬件方法的標志設置簡單，含義明確，容易驗證其正確性；③ 支持多個臨界區，當一個進程內有多個臨界區時，只需為每個臨界區設立一個布爾變量即可

缺點：① 進程在等待進入臨界區時要耗費處理器時間，不能實現讓權等待（需要軟件噢誒和進行判斷）；② 進入臨界區的進程的選擇算法用硬件實現有一些缺陷，可能會使一些進程一直選不上，從而導致饑餓現象

3）信號量

信號量的分類

整型信號量：存在忙等，為遵循讓權等待的準則

記錄型信號量：為解決整型信號量忙等的問題，添加了鏈表結構，用于鏈接所有等待該資源的進程，從而遵循了讓權等待的準則

△?▽

分析：C，B、D 均屬于硬件方法，根據上述理論，硬件方法不能實現讓權等待；Peterson 算法滿足有限等待但不滿足讓權等待；記錄型信號量由于引入了阻塞機制，消除了不讓權等待的情況

△?▽

分析：B
顯然根據上述第三點，當進程退出臨界區時置 lock 為 FALSE，會負責喚醒處于就緒狀態的進程，A）錯誤；讓權等待要求當進程不能進入臨界區時，應立即釋放處理器，防止進程忙等，故而 B）對、C）錯；若 while(TSL(&lock)) 在關中斷狀態下執行，當 TSL(&lock) 一直為 true 時，不再開中斷，則系統可能會因此終止，故 D）錯誤

【消息緩沖】

△?▽

（1）P、V 操作是指進程之間通過共享變量實現信息傳遞；而高級通信機制是由系統提供發送（Send）與接收（Receive）兩個操作，進程間通過這兩個操作進行通信，無需共享任何變量

（2）基本原理：操作系統管理一個用于進程通信的緩沖池，其中的每個緩沖區單元可存放一條消息。發送消息時，發送者從中申請一個可用緩沖區，接收者取出一條消息時再釋放該緩沖區。每個進程均設置一條消息隊列，任何發送給該進程的消息均暫存在其消息隊列中

（3）下面給出的是教材上消息緩沖隊列的發送原語和接收原語：

教材上對上述兩個原語的解釋如下：

【生產者-消費者問題】

△?▽

分析：

△?▽

分析：

△?▽（2009年真題）

分析：

△?▽（2014 年真題）

分析：mutex1 用于多個消費者進程之間互斥，主要是考慮在一個消費者連續取出 10 件產品的過程中是不允許被其他的消費者打斷的

【讀者-寫者問題】

讀者優先

公平情況

寫者優先

注意這里的 wmutex 不同于公平情況下的 wmutex，公平情況下的 wmutex 用于表示是否存在正在寫或者等待的寫者，這里的 wmutex 用于表示多個寫者之間互斥訪問 writecount

△?▽

分析：

△?▽

分析：


我們對此題擴展一下，如果允許多個用戶同時查詢，當有訂票者到達時，不允許后續查詢者查詢，且多個訂票者互斥使用數據庫（即寫者優先）

△?▽

分析：

△?▽

分析：為使 F 的并發度最高，P3 先看做讀者，當其完成讀操作之后再進行寫操作

【哲學家就餐問題】

前提：5 個哲學家按照編號逆時針圍桌而坐， 0 號哲學家左手筷子為 0 號筷子，右手為 1 號筷子，以此類推

下面的代碼中已經對基礎版的哲學家就餐算法存在的死鎖問題作出改進，改進方式是奇數號的哲學家先那左邊筷子，偶數號的哲學家先拿右邊的筷子

另外一種改進方式是，至多允許 4 個哲學家就餐，實現如上圖右邊代碼

△?▽（2019年真題）

分析：傳統的哲學家問題中可以采用限制只有 $n?1$ 個哲學大家同時就餐的方法來避免死鎖的發生（如上圖右邊代碼所示），這里我們可以采用同樣的方法。但是，我們不再單獨引入信號量 $s$，而是利用對碗控制的信號量完成相應的工作。如果 $m<n$，則必然最多只有 $m$ 個哲學家同時就餐，不會發生死鎖問題；如果 $m?n$，則可以令 $m=n?1$，這樣就限制了最多只能有 $n?1$ 個哲學家同時就餐

△?▽

分析：

【理發師問題】

兩種思路：

將顧客人數、理發椅和等待用的凳子視為不同的資源

將顧客人數、理發椅和等待用的凳子視為統一的一個變量

△?▽（2011年真題）

分析：

【其他的一些互斥與同步問題】

△?▽

分析：

△?▽

分析：

△?▽

分析：A：P(mutex)，B：V(mutex)，C：P(s)，D：P(mutex)；s 的初始值為 0，mutex 的初始值為 1

△?▽

分析：我們抽象出一個機房管理員程序，當有兩個學生到達且有機器空閑則通知學生進入機房（這整道題的細節實現上都很有特點，值得學習的）


△?▽

分析：

△?▽

分析：

分析：

△?▽（2013年真題）

分析：

△?▽

分析：考慮一個問題：能用一個互斥變量來控制對 y 的操作嗎？肯定是不能的，1、2 對 y 同時可讀，1、3 和 2、3 是讀寫互斥，如果只用一個互斥變量 mutex_y 控制對 y 的操作的話，就不能滿足題意中最大程度并發的要求了

△?▽（2015 年真題）

分析：

【死鎖分析】

△?▽

分析：D，如下圖所示，左邊為死鎖發生的情況，右邊為解決死鎖的情況

分析：B，假設每個進程已經拿到了 2 臺打印機，要求死鎖不發生，至少還有 1 臺打印機可分配，于是 $N\times 2+1?11$，故 $N_{max}=5$

分析：B，(2+3+4)+1 = 11

分析：C，注意要求處于死鎖狀態的進程數最少，于是，讓 P4 先運行，之后：


則至少有 3 個進程處于死鎖狀態

分析：
（1）若不加以限制，會發生死鎖，如下所示：


（2）方法一：要求進程一次性地全部申請到它所需要的全部資源；
方法二：要求進程按照資源號遞增順序申請資源；
方法三：當一個進程生情資源時，如果無該類資源可分配，但某個用于該資源的其他進程處于阻塞態時，則允許前者搶占后者資源

分析：A，死鎖發生時，n 個進程由于爭奪拿不到資源而全部阻塞

△?▽

分析：會發生死鎖，若某時有兩個用戶 A、B 同時向對方進行轉賬，P1 先對賬戶 A 進行加鎖，再申請 B；P2 先對賬戶 B 加鎖，在申請 A，此時發生死鎖

解決方法時：可以采用資源順序分配法，將 A、B 編號，用戶轉賬時只能按照編號從小到大的順序進行加鎖

△?▽

分析：
（1）有可能產生死鎖，系統中只有 3 臺 R1 設備，要被 4 個進程共享，且每個進程需要 2 臺 R1 設備，明顯優于 R1 設備不足會導致死鎖的發生
（2）

【死鎖處理策略】

死鎖的處理采用三種策略：死鎖預防、死鎖避免、死鎖檢測和解除

防止死鎖和避免死鎖是兩種方法，實際上都是通過施加某些限制條件的方法，來預防死鎖的發生。兩者的區別在于：防止死鎖所施加的限制條件較嚴格，防止死鎖的辦法是破壞死鎖產生的必要條件；死鎖避免對系統所加的限制條件則相對寬松，銀行家算法屬于避免死鎖的算法

破壞互斥條件、不可剝奪條件、請求與保持條件、環路等待條件屬于預防死鎖

對于死鎖的檢測和解除，在系統為進程分配資源時不采取任何措施，但提供死鎖的檢測和解除的手段

△?▽

分析：B，顯然 Ⅰ、Ⅳ 正確；死鎖預防是破壞死鎖產生的 4 個必要條件之一，以確保系統不會發生死鎖，故 Ⅱ 正確；銀行家算法是一種死鎖避免算法，用于計算動態資源分配的完全性以避免系統進入死鎖狀態，不能用于判斷系統是否處于死鎖，故 Ⅲ 錯誤

【破壞死鎖產生的必要條件】

• 互斥條件： 允許多個進程同時訪問資源
• 不可剝奪條件： 對于一個已經獲得了某些資源的進程，若新的資源請求不能立即得到滿足，則它必須釋放所有已經獲得的資源，以后需要資源時再被重新申請
• 請求與保持條件： 采用預先靜態分配法，要求進程在其運行之前一次性申請所需要的全部資源，在它的資源未滿足前，不投入運行
• 環路等待條件： 可以采用有序資源分配法

△?▽

分析：D，本題相當于破壞了死鎖不可剝奪這一條件，故不會發生死鎖。但由于某進程的資源可能不斷地被剝奪，所以會出現饑餓現象

【安全狀態與死鎖的關系】

利用銀行家算法，系統處于安全狀態時就可以避免死鎖（此時必然無死鎖產生）；當系統進入不安全狀態后便可能進入死鎖（但也不是必然的）

【銀行家算法】

基本的關系式：

$$Need[i][j]=Max[i][j]?Allocation[i][j]$$

銀行機算法流程

安全性算法流程

△?▽

分析：D，一個一個帶進去試吧

△?▽

分析：首先是死鎖檢測，其允許死鎖出現，即允許進程最大限度地申請并分配資源，直至死鎖出現，再由系統解決。其次是銀行家算法，該方法允許進程自由申請資源，只是在某個進程申請時檢測是否處于安全狀態，若是，則可立即分配；若不是，則拒絕。最后是資源預分配，因為此方法要求進程在運行之前申請所需的全部資源，這樣會使許多進程因申請不到資源而無法開始，得到資源的進程也并不是同時需要所占的全部資源，因此導致資源的浪費

【死鎖與餓死】

【代碼分析】

1）分析互斥進入臨界區、饑餓等問題

△?▽（模擬題一）

分析：B，若兩個進程同時申請資源（左邊為 P1，右邊為 P1），此時 turn = 0，則可以順序執行 ①②③④⑤⑥，顯然無法保證互斥進入臨界區；再看饑餓問題，turn = -1 時說明已經有程序進入臨界區，退出后也有 turn = 0（滿足 turn != -1），故不會產生饑餓

分析：D，本題是皮爾森算法的實際實現，能夠保證進入臨界區的進程合理安全。該算法為了防止兩個進程為進入臨界區而無限等待，設置變量 turn，表示是允許進入臨界區的編號，每個進程在先設置自己的標志后再設置 turn 標志，讓另一個進程進入，這時，再同時檢測另一個進程狀態標志和允許進入表示，這樣可以保證當兩個進程同時進入臨界區時只允許一個進程進入臨界區。turn 保存的是較晚的一次的賦值，因此較晚的進程等待，較早的進程進入。先到先入，后到等待，從而完成臨界區訪問的要求

其實這里可以想象為兩個人進門，每個人進門之前都會和對方客氣一句 “ 你先進 ”，如果進門時沒別人，就當和空氣說話，然后進門；如果兩人同時進門，就互相請先，但各自只客套一次，所以先客套的人客套完，就等著對方客套自己，然后就直接進門

△?▽

分析：上述并發執行的兩個進程共享變量 x，且共享時沒能做到互斥，因此它們的執行結果具有不確定性

若先執行 P1，并在 x:=1 后進行進程調度，執行完 P2 后再執行 P1，此時 x = y= z = 0，t = u = 2
若先執行 P1，并在 if 語句之后再調度 P2，此時 x = 0，y = z = 1，t = u = 2

2）分析并行程序運算結果

△?▽

分析：C，注意 Begin 和 End之間的內容還是順序執行的，Ⅱ：②③①②，Ⅲ：①③④②

分析：C，P1 和 P2 的變量是各自域內的變量，是不相關的，故互斥僅考慮在一個進程中的互斥，故 D 不必互斥；考慮每個線程中的變量 a，其生存域僅在該線程中，就像是兩個循環中各聲明了一個 i 變量，所以 P1 中對 a 的賦值并不影響最終的結果，故 A 不必互斥；P2 中將 x 賦給 a、b 執行順序的先后不影響 a 與 b 的結果，即兩個并發的線程同時取出 x 賦值給不同的變量，這個過程是不需要互斥的；P1 中的 x 為全局變量，Thread 1 和 Thread 2 中對 x 的操作需要互斥進行，C 正確

△?▽

分析：可將上述兩個進程分為如下的 6 個片段


于是，有前驅圖


若先執行 PS3，再執行 PS6，結果為 x = 6，y = 7，z = 10
若先執行 PS6，再執行 PS3，結果為 x = 6，y = 13，z = 10

【進程與程序的聯系】

進程是動態的，程序是靜止的

進程是暫時的，程序是永久的

進程和程序的組成是不同的

通過多次執行，一個程序可以產生多個不同放入進程；通過調用關系，一個進程可以執行多個程序進程可以創建其他進程，而程序不能形成新的程序

進程具有并行特點，程序則沒有

【并發進程的相對速度】

并發進程的相對速度受進程調度策略的影響，因為采取不同的調度策略會影響進程執行的相對速度

【中斷掃描機構】

處理器執行完一條指令之后，硬件的中斷裝置（中斷掃描機構）立即檢查有無中斷時間發生。若無中斷事件發生，則處理器繼續執行下面的指令；若有中斷事件發生，則暫停現行進程的運行

【進程處于臨界區時的調度問題】

進程在臨界區時是不允許其他相關進程進入臨界區的。但問題的關鍵在于系統中還存在著與這類進程無關的其他進程，其他進程的執行并不會受到這類進程是否處于臨界區的影響。系統可以暫停該進程的執行，先去處理其他與之無關的緊急任務，處理完之后再返回來繼續執行剩余的臨界區代碼

【調度算法】

1）各調度算法特性

FCFS算法比較有利于長作業進程，而不利于短作業進程；有利于 CPU 繁忙型的作業，而不利于 I/O 頻繁行的作業。因為 CPU 繁忙型作業，是指該類作業需要大量的 CPU 事件進行計算，而很少請求 I/O，通常的科學計算便屬于 CPU 繁忙作業。I/O 繁忙型作業是指 CPU 進行處理時又需要頻繁地請求 I/O，而每次 I/O 的操作事件卻很短

FCFS、SJF、優先級調度算法既可以用于作業調度也可以用于進程調度，時間片輪轉、多級反饋隊列用于進程調度，高響應比優先用于作業調度

FCFS 是非搶占式的；時間片輪轉法是搶占式的；優先級調度算法既可以是非搶占式的，也可以是搶占式的

不會導致饑餓的調度算法：時間片輪轉法；會導致饑餓的調度算法：靜態優先級、非搶占式 SJF、搶占式 SJF

△?▽

分析：
（1）如果就緒隊列中總有優先數較小的進程時，優先數較大的進程則會一直處于等待狀態，故可能會出現饑餓現象
（2）$priority=nice+{\lambda }_{1}cpuTime?{\lambda }_{2}waitTime({\lambda }_1,{\lambda }_2>0)$
這樣設計的理由是：適當降低運行過的進程的優先級，提高長時間等待的進程的優先級。其中，$waitTime$ 可使長時間等待的進程的優先數減小，從而避免出現饑餓現象

△?▽

分析：
（1）FCFS：a → b → c → d → e；非搶占式的優先數：a → b → e → c → d
（2）


（3）

△?▽

分析：C，P1、P2 被創建后依次插入 Q1 隊列，先調度 P1，時間片用完后將 P1 插入 Q2，此時 P1 還需要 20ms；接著調度 P2，仍然時間片用完后插入 Q2，此時還需 10ms；在 Q2 隊列中根據 SJF 先運行 P2，再運行 P1，整個過程如下圖所示，虛線部分為兩進程各自等待的時間

2）時間的計算

周轉時間/（平均）：作業從提交至完成的時間間隔，包括等待時間和執行時間，$$作業i的周轉時間T_i=作業i的完成時間?作業i的提交時間$$

帶權周轉時間/(平均)：$$W_i=作業i的周轉時間/作業i的運行時間$$

分析：D
P₂：15+24+1 = 40
P₃：18+24+1+36+1 = 80
P₁：30+24+1+36+1+12+1 = 105
故平均周轉時間為 (40+80+105)/3 = 75

分析：
FCFS：
平均等待時間 = (0+9.8+10.6+12.2+13)/5 = 9.12；
平均周轉時間 = (10+10.8+12.6+13.2+18)/5 = 12.92；平均帶權周轉時間 = (10/10+10.8/1+12.6/2+13.2/1+18/5)/5 = 6.98

SJF: 1→2→4→3→5
平均等待時間 = (0+9.8+11.6+10.2+13)/5 = 8.92
平均周轉時間 = (10+10.8+13.6+11.2+18)/5 = 12.72
平均帶權周轉時間 = (10/10+10.8/1+13.6/2+11.2/1+18/5)/5 = 6.68

非搶占式優先級：1→2→5→3→4
平均等待時間 = (0+9.8+15.6+17.2+10)/5 = 10.52
平均周轉時間 = (10+10.8+17.6+18.2+15)/5 = 14.32
平均帶權周轉時間 = (10/10+10.8/1+17.6/2+18.2/1+15/5)/5 = 8.36

△?▽

分析：FCFS、SJF 和非剝奪式優先級調度三個不說，重點看下時間片為 1 的RR 的執行情況


平均周轉時間 = (19+2+7+4+14)/5 = 9.2s
平均帶權周轉時間 = (19/10+2/1+7/2+4/1+14/5) = 2.84s

【原語】

原語通常由若干條指令組成，用來實現某些特定的操作。通過一段不可分割的或不可中斷的程序實現其功能。引進原語的主要目的就是為了實現進程的通信和控制。

【并發程序執行的特點】

間斷性：并發程序具有 “執行——暫停——執行” 這種間斷性的活動規律

失去封閉性：多個程序共享系統中的各種資源，因而這些資源的狀態將由多個程序來改變，致使程序的運行失去了封閉性

不可再現性：由于失去了封閉性，程序的計算結果與并發程序的執行速度有關，從而使程序失去了可再現性

【導致一個進程去創建另外一個進程】

導致一個進程取得創建另一個進程的典型事件有 4 類：用戶登錄、作業調度、提供服務、應用請求

【互斥信號量】

互斥信號量僅能取值 1，0，-1，互斥信號量的初始值設為 1，表示同時只允許 1 個進程訪問臨界資源。當有 1 個進程提出訪問臨界資源請求時，執行 P 操作，互斥信號量 -1，變為 0，同時該進程進入臨界區。如果另外一個進程此時也請求訪問臨界資源，則同樣執行 P 操作。由于互斥信號量執行 P 操作之前的值為 0，執行 P 操作之后，信號量變為 -1

【信號量的值】

同步： 用 P、V 操作實現進程同步，信號量的初始值應根據具體情況來確定。若期望的消息未產生，則對應的初始值應設為 0；若期望的消息已經存在，則信號量應設為一個非 0 的正整數

互斥： 一般互斥信號量的初始值都設置為 1，P 操作成功則將其改成 0，V 操作成功則將其改為 1

△?▽

分析：B，理論如上所述

△?▽

分析：B，理論如上所述

△?▽（模擬題一）

分析：B，先思考一個問題，之前的 28 次 P 操作和 18 次 V 操作對后面的計算有影響嗎？沒有，為什么？在 S ≤ 0 時，表示資源申請完畢，需要等待，|S| 表示等待該資源的進程數；S > 0 時，表示有空閑資源可申請，|S| 表示可申請的空閑資源數。顯然，一對 PV 操作并不代表就有一個進程。于是，從 S = 0 時刻開始，3 次 V 操作后，S = 3 > 0 代表有 3 個空閑資源可申請，即沒有進程處于等待狀態

△?▽

分析：A，理論如上所述

△?▽

分析：B，理論如上所述

【管程】

管程定義了一個數據結構和能為并發進程所執行的一組操作，這組操作能同步進程和改變管程中的數據

管程由局部于管程的共享數據結構說明、操作這些數據結構的一組過程以及對局部于管程的數據結構設置初值的語句組成

管程有一下基本特征：

管程不僅能夠實現進程間的互斥，而且能實現進程間的同步

管程的 V 操作不同于信號量機制中的 V 操作，前者必須在 P 操作之后，而后者則沒有這個要求，只要和 P 操作配對出現即可

局部于管程的數據只能被局部于管程內的過程所訪問

一個進程只有通過調用管程內的過程才能進入管程訪問共享數據

每次僅允許一個進程在管程內執行某個內部過程，即進程互斥地通過調用內部過程進入管程

在管程定義中還包含以下支持同步的設施：

局限于管程并僅能從管程內進行訪問的若干條件變量，用于區別不同的等待原因

在條件變量上進行操作的兩個函數過程 wait 和 signal，若進程執行了 x.wait() 操作，那么該進程會阻塞，并掛到條件變量 x 對應的阻塞隊列上。這樣管程的使用權就被釋放，就可以有另一個進程進入管程。如果進程執行了 x.signal() 操作，那么會喚醒 x 對應的阻塞隊列對頭進程。在 Pascal 語言的管程中，規定只有一個進程要離開管程時才調用 signal() 操作

（這里解釋一下第 2 小點最后一句話什么意思：如果一個程序主動調用 signal 操作，表示其已經使用完共享數據，要離開管程，所以說一個進程要離開管程時才調用 signal 操作。那么上面說進程執行 wait 操作管程的使用權被釋放是什么意思呢？進程執行 wait 操作被阻塞，沒有獲得共享數據的使用權，而管程中一次只能有一個進程在執行，那么被阻塞的進程不再使用管程，故其使用權被釋放，允許其他進程進入管程使用共享數據）

【操作系統各功能組成部分中一定需要專門硬件配合支持的】

地址映射需要硬件機構來實現。當進程要訪問某個邏輯地址中的數據時，分頁地址變換機構（它是硬件）會自動將有效地址（相對地址）分為頁號和業內地址兩部分，再以頁號為索引去檢索頁表。查找操作是有硬件執行的

中斷系統需要硬件機構來實現。CPU 硬件中有一條中斷請求線（IRL），CPU在執行完每條指令后，都將判斷 IRL，當 CPU 檢測到已經有中斷控制器（即中斷源）通過中斷請求線發送了信號時，CPU 將保留少量轉態，如當前指令位置，并且跳轉到內存指定位置的中斷處理程序。這里的中斷控制器是硬件。

對于系統調用是否一定需要專門的硬件呢 ？我們需要清除系統調用的過程。C 編譯程序采用一個預定義的函數庫（C 的程序庫），其中的函數具有系統調用放入名字，從而解決了在用戶程序中請求系統調用的問題。這些庫函數一般都執行一條指令，該指令將進程的運行方式變為核心態，然后使內核開始為系統執行代碼，稱這個指令為操作系統陷入。系統調用的接口是一個中斷處理程序的特例。在處理操作系統陷入時：

內核根據系統調用號查系統調用入口表，找到相應的內核子程序的地址；

內核還要確定該系統調用所要求的參數個數；

從用戶地址空間賦值參數到 U 區（UNIX V）；

保存當前上下文，執行系統調用代碼；

恢復處理器現場并返回

上述 1~3 過程和 5 過程都不需要專門的硬件，只有 4 過程可能需要專門的硬件，如顯示器輸出字符，但也可以不需要專門硬件，如打開一個已經在緩存中的文件

進程調度一般是通過使用一些調度算法來編程實現的

【線程】

1）線程的基本概念

線程是進程內一個相對獨立的、可調度的執行單元。線程自己基本上不擁有資源，只擁有一點在運行時必不可少的資源（如用于控制線程運行的線程控制塊 TCB，用于指示被執行指令序列的程序計數器，保留局部變量、少數狀態參數和返回地址等的一組寄存器和棧），但它可以與同屬于一個進程的其他線程共享進程擁有的全部資源

2）線程的實現

用戶級線程：

• 是指依賴于內核，由操作系統內核完成創建和撤銷工作的線程
• 在支持內核級線程的操作系統中，內核維護進程和線程上下文信息并完成線程切換工作
• 一個內核級線程由于 I/O 操作而阻塞時，不會影響其他線程的運行（對比用戶級線程來理解，當線程執行一個系統調用時不僅該線程被阻塞，而且進程內的所有線程會被阻塞）
• 這時，處理器時間片的分配對象是線程，所以有多個線程的進程將獲得更多處理器時間

用戶級線程：

• 是指不依賴于操作系統核心，由應用進程利用線程庫提供創建、同步、調度和管理線程的函數來控制的線程
• 由于用戶級線程的維護由應用進程完成，不需要操作系統內核了解用戶級線程的存在，因此可用于不支持內核級線程的多進程操作系統，甚至是單用戶操作系統
• 用戶級線程切換不需要內核特權，用戶級線程調度算法可針對應用優化。由于用戶級線程的調度在應用程序內部進行，通常采用非搶占式和更簡單的規則，無需用戶態/核心態切換，因此速度特別快
• 由于操作系統內核不了解用戶線程的存在，當一個線程阻塞時，整個進程都必須等待
• 這時，處理器時間片是分配給進程的，當進程內有多個線程時，每個線程的執行時間相對減少

3）細節問題上的解釋

① 對線程的時間片分配

由于用戶級線程不依賴于操作系統內核，因此，操作系統內核是不知道用戶線程的存在的，由于操作系統不知道用戶級線程的存在，所以，操作系統把 CPU 的時間片分配給用戶進程，再由用戶進程的管理器將時間片分配給用戶線程。那么，用戶進程能得到的時間片即為所有用戶線程共享。所以，該進程只占有 1 個時間片。若是內核級線程，由于內核級線程操作系統是知道的，它們與進程一樣地分配處理器時間，所以，有多少個內核級線程就可以獲得多少個時間片

② 線程可以共享進程的哪些內容？不共享哪些內容？

屬于同一進程的各個線程有屬于自己的棧空間，不允許共享

（為什么不允許共享呢？在線程運行時，經常會進行過程調用，而過程的調用通常會出現多重嵌套的情況，這樣就必須將每次過程調用中所使用的局部變量以及返回地址保存起來。為此，應為每個線程設置一個堆棧，用來保存局部變量和返回地址

另外，在線程的 TCB 中，需設置兩個指向堆棧的指針：一個指向用戶自己堆棧的指針，當線程運行在用戶態時，使用用戶自己的用戶棧來保存局部變量和返回地址；一個指向核心棧的指針，當線程運行在核心態時使用系統的核心棧）

線程共享的是進程的虛地址空間

③ 內核級線程的調度

在內核支持線程的情況下，在同一進程中，從一個線程切換到另一個線程時，需要從用戶態轉到核心態運行，這是因為用戶進程的線程是在用戶態運行，而線程調度和管理是在內核實現的

④ 在多處理機系統中內核級線程和用戶級線程的不同

在多處理器系統中，內核能夠同時調度同一進程中的多個線程并行執行；而在單純的用戶級線程實現方式中，多線程應用不能利用多處理機進行多重處理，內核每次分配給一個進程唯一的一個 CPU，因此，線程中僅有一個線程能執行

4）線程和進程的比較

• 調度：
  ① 線程是獨立調度的基本單位，進程是擁有資源的基本單位
  ② 同一進程中的線程切換不會引起進程切換
  ③ 不同進程中的線程切換換回引起進程切換
• 并發性：
  同一進程內的多個線程可以并發執行，甚至不同進程內的多個線程也可以并發執行
• 擁有資源：（沒有新內容，便不再贅述）
• 系統開銷：
  ① 創建進程時，必須為它分配除處理機以外所必須的、所有資源；撤銷進程時，必須先對其所占有資源執行收回操作，再撤銷 PCB；進程切換時，需要保留當前進程的 CPU 環境，設置新調度進程的 CPU 環境。諸如此類下來，OS 對進程所付出的系統開銷明顯大于對線程所付出的系統開銷
  ② 由于一個進程中的多個線程具有相同的地址空間，線程之間的同步和通信也比進程簡單
• 支持多處理機系統：
  ① 在多處理機系統中 ，對于傳統進程，即單線程進程，不管有多少處理機，該進程只能在一個處理機上運行
  ② 對于多線程進程，可以將一個進程中的多個線程分配到多個處理機上并行執行

5）多線程模型

• 多對一模型： 多對一模型將多個用戶級線程映射到一個內核級線程上。對于這些多個映射的線程一般屬于一個進程，運行在該進程的用戶空間，對這些線程的調度和管理也是在該進程的用戶空間中完成。僅當用戶線程需要訪問核心時，才將其映射到一個內核級線程上，且每次只允許一個線程進行映射。由于多個用戶級線程映射到同一個內核級線程，只要一個用戶級線程阻塞，就會導致整個進程阻塞。而且由于系統只能識別一個內核級線程，因此即使有多個處理器，該進程的若干個用戶級線程也只能同時運行一個，不能并行執行
• 一對一模型： 一對一模型將內核級線程與用戶級線程一一對應。這樣做的好處是當一個線程阻塞時，不影響其他線程的運行。而且這時，在多處理器上可以實現多線程并行。該模型的缺點是創建一個用戶級線程時需要創建一個相應的內核級線程
• 多對多模型： 多對多模型將多個用戶級線程映射到多個內核級線程（內核級線程數不多于用戶級線程數），這樣的模型不僅可以使多個用戶級線程真正意義上并行執行，而且不會限制用戶級線程的數量。用戶可以自由創建所需的用戶級線程，多個內核級線程根據需要調用用戶級線程，當一個用戶級線程阻塞時，可以調度執行其他線程

△?▽

分析：C，一般只有一個鍵盤，而且人為動作相對于計算機來說是十分緩慢的，故可以用一個線程來處理所有鍵盤輸入

△?▽

分析：B

對 A，強調內核級線程，故正確
對 B，在多線程模型中，用戶級線程和內核級線程的連接方式有多對一、一對一、多對多，操作系統為每個用戶線程建立一個線程控制塊屬于一對一模型，故錯誤
對 C，顯然正確
對 D，用戶級線程的管理工作可以只在用戶空間中進行，故可以在不支持內核級線程的操作系統上實現，故正確

【進程優先級改變】

進程完成 I/O 后，進入就緒隊列時，已經是優先級最低的進程，不能在降低其優先級，為了讓其及時處理 I/O 結果，應該提升優先級

進程長期處于就緒隊列，需要增加其優先級，使其不至于產生饑餓

當進程處于執行態時，不應該提高或降低其優先級

在時間片調度算法中，若進程時間片用完，則需要將其排到就緒隊列的末尾，也就是優先級最低，所以降低優先級的合理時機是時間片用完時。另外，在多級反饋調度算法中，若時間片用完，但進程還沒有結束，則放到下一級隊列中，優先級也是被降低了

【處理器的三級調度】

處理器的三級調度是指一個作業在運行過程中要遇到的高級調度（作業調度）、中級調度（進程對換）和低級調度（進程調度）。不過，不是所有操作系統都有三級調度，有些只實現了其中的一級或者兩級，但是每個操作系統都有進程調度

高級調度的主要工作是決定外存的后備隊列中哪個進程被調入內存中，并給這個作業創建進程，給分配它必要的資源；中級調度的主要工作是在內存緊張時把就緒隊列中暫時得不到執行的進程換到外存，也負責在內存比較空閑時把換到外存的進程調回內存；低級調度的主要工作是決定把 CPU 分配給就緒隊列中的哪個進程

高級調度主要在需要從外存調入一個作業到內存中時發生；中級調度主要在內存緊張需要調出一些進程，或者內存空閑時需要把一些進程調回內存時發生；低級調度主要在正在執行的進程放棄 CPU 或者被其他優先級高的進程搶占 CPU 時發生

總結

以上是生活随笔為你收集整理的408 知识点笔记——操作系统（绪论、进程管理）的全部內容，希望文章能夠幫你解決所遇到的問題。

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