第一章操作系統概述

1.1、操作系統的概念、特征、功能和

結構

1、操作系統的概念

在信息化時代，軟件被稱為計算機系統的靈魂。而作為

軟件核心的操作系統，已經與現代計算機系統密不可分、融

為一體。計算機系統自下而上可粗分為四個部分：硬件、操

作系統、應用程序和用戶。操作系統管理各種計算機硬件,

為應用程序提供基礎，并充當計算機硬件和用戶的中介。

硬件，如中央處理器、內存、輸入輸出設備等，提供了

基本的計算資源。應用程序，如字處理程序、電子制表軟件、

編譯器、網絡瀏覽器等，規定了按何種方式使用這些資源來

解決用戶的計算問題。操作系統控制和協調各用戶的應用程

序對硬件的使用。

綜上所述，操作系統是指控制和管理整個計算機系統的

硬件和軟件資源，并合理的組織調度計算機的工作和資源的

分配，以提供給用戶和其他軟件方便的接口和環境集合。計

算機操作系統是隨著計算機研究和應用的發展逐步形成并

發展起來的，它是計算機系統中最基本的系統軟件。

2、操作系統的特征

操作系統是一種系統軟件，但與其他的系統軟件和應用

軟件有很大的不同，他有自己的特殊性即基本特征，操作系

統的基本特征包括并發、共享、虛擬和異步。這些概念對理

解和掌握操作系統的核心至關重要，將一直貫穿于各章節中。

(1)并發

并發是指兩個或多個事件在同一時間間隔內發生，在多

道程序環境下，一段時間內宏觀上有多個程序在同時執行，

而在同一時刻，單處理器環境下實際上只有一個程序在執行,

故微觀上這些程序還是在分時的交替進行。操作系統的并發

是通過分時得以實現的。操作系統的并發性是指計算機系統

中同時存在多個運行著的程序，因此它具有處理和調度多個

程序同時執行的能力。在操作系統中，引入進程的目的實施

程序能并發執行。

(2)共享

資源共享即共享，是指系統中的資源可供內存中多個并

發執行的進程共同使用。共享可以分為以下兩種資源共享方

式。

1）互斥共享方式

系統中的某些資源，，如打印機、磁帶機，雖然他們可

以提供給多個進程使用，但為使所打印的內容不致造成混淆,

應規定在同一段時間內只允許一個進程方位該資源。

為此，當進程a訪問某資源時，必須先提出請求，如果

此時該資源空閑，系統便可將之分配給進程a使用，伺候若

再有其他進程也要訪問該資源（只要a未用完）則必須等待。

僅當進程a訪問完并釋放該資源后，才允許另一進城對該資

源進行訪問。計算機系統中的大所屬物理設備，以及某些軟

件中所用的棧、變量和表格，都屬于臨界資源，他們都要求

被互斥的共享。

2）同時訪問方式

系統中還有一種資源，允許在一段時間內由多個進程

“同時”對它進行訪問。這里所謂的“同時”往往是宏觀上

的，而在微觀上，這些進程可能是交替的對該資源進行訪問

即“分時共享二典型的可供多個進程同時訪問的資源是磁

盤設備，一些用重入碼編寫的文件也可以被“同時”共享，

即若干個用戶同時訪問該文件。

并發和共享是操作系統兩個最基本的特征，這兩者之間

又是互為存在條件的：1資源共享是以程序的并發為條件的，

若系統不允許程序并發執行，則自然不存在資源共享的問題;

2若系統不能對資源共享實施有效地管理，也必將影響到程

序的并發執行，甚至根本無法并發執行。

(3)虛擬

虛擬是指把一個物理上的實體變為若干個邏輯上的對

應物。物理實體是實的，即實際存在的；而后者是虛的，是

用戶感覺上的事物。相應的，用于實現虛擬的技術，成為虛

擬技術。在操作系統中利用了多種虛擬技術，分別用來實現

虛擬處理器、虛擬內存和虛擬外部設備。

在虛擬處理器技術中，是通過多道程序設計技術，讓多

道程序并發執行的方法，來分時使用一臺處理器的。此時，

雖然只有一臺處理器，但他能同時為多個用戶服務，是每個

終端用戶都認為是有一個中央處理器在為他服務。利用多道

程序設計技術，把一臺物理上的CPU虛擬為多臺邏輯上的CPU,

稱為虛擬處理器。

類似的，可以通過虛擬存儲器技術，將一臺機器的物理

存儲器變為虛擬存儲器，一邊從邏輯上來擴充存儲器的容量。

當然，這是用戶所感覺到的內存容量是虛的，我們把用戶

所發哦絕倒的存儲器程序虛擬存儲器。

還可以通過虛擬設備技術，將一臺物理10設備虛擬為

多臺邏輯上的10設備，并允許每個用戶占用一臺邏輯上的

10設備，這樣便可使原來僅允許在一段時間內有一個用戶訪

問的設備，變為在一段時間內允許多個用戶同時訪問的共享

設備。

因此操作系統的虛擬技術可歸納為：時分復用技術和空

分復用技術。

(4)異步

在多道程序環境下，允許多個程序并發執行，但由于資

源有限，進程的執行不是一貫到底，而是走走停停，以不可

預知的速度向前推進，這就是進程的異步性。

異步性使得操作系統運行在一種隨機的環境下，可能導

致進程產生于時間有關的錯誤。但是只要運行環境相同，操

作系統必須保證多次運行進程，都獲得相同的結果。

3、操作系統的目標和功能

為了給多道程序提供良好的運行環境，操作系統應具有

幾方面的功能：處理器管理、存儲器管理、設備管理和文件

管理。為了方便用戶使用操作系統，還必須向用戶提供接口。

同時操作系統可用來擴充機器，以提供更方便的服務、更高

的資源利用率。

（1）操作系統作為計算機系統資源的管理者

1）處理器管理

在多道程序環境下，處理器的分配和運行都是以進程為

基本單位，因而對處理器的管理可歸結為對進程的管理。進

程管理的主要功能有：進程控制，進程同步，進程通信，死

鎖處理，處理器調度等。

2）存儲器管理

存儲器管理的主要任務是位多通道程序的運行提供良

好的環境，方便用戶使用以及提高內存的利用率。因此，存

儲器管理應具備：內存分配、地址映射、內存保護與共享和

內存擴充等。

3）文件管理

文件管理主要包括文件的存儲空間管理、目錄管理及文

件讀寫管理及保護等。

4）設備管理

設備管理的主要任務就是完成用戶的10請求，方便用

戶使用各種設備，并提高設備的利用率，主要包括混充管理、

設備分配、設備處理和虛擬設備等功能。

（2）操作系統作為用戶與計算機硬件系統之間的接

口

為方便用戶使用操作系統，操作系統還提供了用戶接口。

操作系統提供的接口主要分為兩類：一類是命令接口，用戶

利用這些操作命令來組織和控制作業的執行；另一類是程序

接口，編程人員可以使用它們來請求操作系統服務。

1）命令接口

使用命令接口進行作業控制的主要方式有兩種：按作業

控制方式的不同，可以將命令接口分為聯機命令接口和脫機

命令接口。

2）程序接口

程序接口由一組系統調用命令組成。用戶通過在程序中

使用這些系統調用命令拉i請求操作系統提供的服務。用戶

在程序中可以直接使用這組系統調用命令向系統提出各種

服務請求，如使用各種外部設備，進行有關磁盤文件的操作，

申請分配和收回內存以及其他各種控制要求。

所謂系統調用就是用戶在程序中調用操作系統所提供

的一些子功能。具體的講，系統調用就是通過系統調用命令

中斷現行程序，而轉去執行響應的子程序，以完成特定的系

統功能；系統調用完成后，返回程序的斷點以繼續執行。

系統調用命令是作為擴充機器命令提供的，目的是增強

系統功能，方便用戶使用。而起通過系統調用的方式來使用

系統功能，可以保證系統的穩定性和安全性，防止用戶隨意

更改或訪問系統的數據或命令。因此，在一些計算機系統中，

把系統調用命令成為廣義指令。廣義指令與機器指令在性質

上是不同的，機器指令使用硬件電路直接實現的，而廣義命

令則是由操作系統提供的一個或多個子程序模塊實現的。顯

然，系統調用屬于核心態指令。

(3)操作系統做擴充機器

沒有任何軟件支持的計算機成為裸機，它僅構成計算機

系統的物質基礎，而實際呈現在用戶面前的計算機系統是經

過若干層軟件改造的計算機。裸機在最里層，他的外面是操

作系統，有操作系統提供的資源管理功能和方便用戶的各種

服務功能，將裸機改造成功能更強、使用更方便的機器，通

常把覆蓋了軟件的機器成為擴充機器，又稱之為虛擬機。

4操作系統的結構

像現在操作系統這樣龐大而復雜的系統，為了能正常工

作且容易修改和維護，在實現前必須認真設計操作系統的結

構。操作系統發展至今，其設計結構可以分成以下幾類：

(1)簡單結構。

(2)模塊化結構

(3)分層式結構

(4)微內核結構

1.2、操作系統的發展與分類

1、手工操作階段

2、脫機輸入輸出階段

3、批處理階段

批處理技術是指計算機系統對一批作業自動進行處理

的一種技術。批處理階段的特點是：用戶不用與計算機直接

打交道，而是通過專門的操作員來完成作業的輸入輸出。隨

著外圍設備的迅速發展，后來又出現了脫機批處理系統，即

主機直接與磁盤通信。

(1)單道批處理系統

主要特點：自動性、順序性、單道性。

(2)多道批處理系統

多道程序設計技術是指在計算機內存中同時存放幾道

相互獨立的程序，它們在管理程序的控制下相互交替的運行。

其特征是：多道，宏觀上并行，微觀上串行。

4、分時操作系統

所謂分時系統就是把處理器的運行時間分成很短的時

間片，按時間片輪流把處理器分配給各聯機作業使用。若某

個作業再分配給他的時間片內不能完成其計算，則改作業暫

時停止運行，把處理器讓給其他作業使用，等待下一輪再繼

續運行，由于計算機速度很快，作業運行輪轉的很快，給每

個用戶的感覺好像是自己獨占一臺計算機。

分時操作系統十多個用戶通過終端同事共享一臺主機,

這些終端連接在主機上，用戶可以同時與主機進行交互操作

而不互相干擾。所以，實現分時系統最關鍵的問題，是如何

使用戶能與自己的作業進行交互，即當用戶在自己的中斷上

輸入命令時，系統應能及時接收并及時處理該命令，再將結

果返回用戶。分時系統也是支持多道程序設計的系統，但它

不同于多道批處理系統。多道批處理是實現作業自動控制而

無需人工干預的系統，而分時系統是實現人機交互的系統,

這使得分時系統具有與批處理系統不同的特征，其主要特征

如下：

同時性，交互性，獨立性，及時性。

5、實時操作系統

實時系統的主要特點是：實時性和可靠性。

6、網絡操作系統和分布式計算機系統

7、個人計算機操作系統

1.3、操作系統的運行環境

1、操作系統的運行機制

計算機系統中，通常CPU執行兩種不同性質的程序，一

種是操作系統內核程序；另一種是用戶自編程序或系統外城

的應用程序。對操作系統而言，這兩種程序的作用不同，前

者是后者的管理者和控制者，因此“管理程序”要執行一些

特權指令，而“被管理程序”出于安全性考慮，不能執行這

些指令。所謂特權指令，是指計算集中不允許用戶直接使用

的指令，如10指令、置中斷指令。

操作系統在具體實現上劃分了用戶態和核心態，以嚴格

區分兩種類程序。

一些與硬件關聯交緊密的模塊，諸如時鐘管理程序、中

斷處理程序、設備驅動程序等處于最底層。其次是運行頻率

較高的程序，諸如金城關里、存儲器管理和設備管理等。這

兩部分內容構成了操作系統的內核。這部分內容的指令操作

工作在核心態。

內核是計算機上配置的最底層軟件，是計算機功能的眼

神。不同系統對內核的定義稍有區別，大多數操作系統內核

包括四個方面的內容。

(1)時鐘管理

在計算機外部設備中，時鐘是最關鍵的設備。時鐘的第

一功能是計時，操作系統需要通過時鐘管理，向用戶提供標

準的系統時間。另外，通過時鐘中斷的管理，可以實現京城

的切換。諸如：在分時操作系統中，采用時間片輪轉調度的

實現；在實時系統中，按截止時間控制運行的實現；在批處

理系統中，通過時鐘管理來衡量一個作業的運行程度等。因

此，系統管理的方方面面無不依賴于它。

(2)中斷機制

引入中斷技術的初衷是提高多道程序運行環境中CPU的

利用率，而且主要是針對外部設備的。后來的到發展，形成

了多種類等，成為操作系統各項操作的基礎。例如鍵盤或鼠

標信息的輸入、進程的管理和調度、系統功能的調用、設備

驅動、文件訪問等，無不依賴于中斷機制。可以說，現代計

算機系統是靠中斷驅動的軟件。

(3)原語

按層次結構涉及的操作系統，底層必然是一些可被調用

的公用小程序，他們各自完成一個規定的操作。其特點是:

1.他們處于操作系統的最底層，是最接近硬件的部分。2.這

些程序的運行具有原子性一一其操作只能一起合成。3.這些

程序的運行時間都較短，而且調用頻繁。

通常把具有這些特點的程序成為原語。定義源于的直接

方法是關閉中斷，讓她的所有動作不可分割的進行完再打開

中斷。

系統中的設備驅動、CPU切換、進程通信等功能中的部

分操作都可以定義為原語，是他們呢成為內核的組成部分。

(4)系統控制的數據結構及處理

系統中用來登記狀態信息的數據結構很多。比如作業控

制塊、進程控制塊、設備控制塊、各類鏈表、消息隊列、緩

沖區、空閑區登記表、內存分配表等。為了實現有效地管理，

系統需要一些基本的操作，常見的操作有以下三種：

1)進程管理：進程狀態管理、進程調度和分配、創建與

撤掉進程控制塊的隊列維護操作等。

2)存儲器管理：存儲器的空間分配和回收管理、內存信

息保護程序、代碼對換程序等。

3)設備管理：緩沖區管理、設備分配和回收等。

從上述內容可以了解，核心態指令實際上包括系統調用

類指令和一些針對時鐘、中斷和原語的操作指令。

2、中斷和異常的概念

在操作系統中引入核心態和用戶態這兩匯總工作狀態

后，就需要考慮這兩種狀態之間如何切換。操作系統內核工

作在核心態，而用戶程序工作在用戶態。但系統不允許用戶

程序實現核心態的功能，而它們又必須使用這些功能。

中斷(interruption)也成為外中斷，指來自CPU執行指

令以外的事件發生，如設備發出的10結束中斷，表示設備

輸入輸出處理已經完成，希望處理器能夠像設備發出下一個

輸入輸出請求，同事讓王成輸入輸出后的程序繼續進行。時

鐘中斷，表示一個固定的事件篇已到，讓處理器處理計時、

啟動定時運行的任務。這一類中斷通常是與當前運行的程序

無關。中斷可細分為硬中斷和軟中斷。硬中斷是硬件產生的;

軟中斷是軟件產生的。

異常(Exception)也成為內中斷、例外或陷入。指源自

CPU執行指令內部的時間，如程序的非法操作碼、地址越界、

算數一出、虛存系統的缺頁以及專門的陷入指令等引起的時

間。對異常的處理一般要依賴與當前程序的運行現場，而且

異常不能被屏蔽，一旦出現異常立即處理，而關于內中斷和

外中斷的聯系與區別如下：

這樣，操作系統的運行環境可以理解為：用戶通過操作

系統運行上層程序，而這個上層程序的運行以來與操作系統

的底層管理程序提供服務支持，當需要管理程序服務時，系

統則通過硬件中斷機制進入核心態，運行管理程序；另外也

可能是程序運行出現異常情況，被動的需要管理程序的服務,

這是就通過異常處理來進入核心態。當管理程序運行結束時,

用戶程序要繼續進行，則通過相應保存程序現場推出中斷處

理程序或異常處理程序，返回斷點處繼續執行。在操作系統

這一層面上，我們關心的是系統核心態和用戶態的軟件實現

和切換，對于硬件層面的具體理解，可以結合“計算機組成

原理”課程中有關中斷的內容進行學習。

下面列舉一些由用戶態轉向核心態的例子：

1）用戶程序要求操作系統的服務，即系統服務。

2）發生一次中斷

3）用戶程序中產生了一個錯誤狀態

4）用戶程序中企圖執行一條特權指令

5）從核心態轉向用戶態由一條指令實現，這條指令也

是特權指令。一般情況是中斷返回指令。

注意，由用戶態進入核心態，不僅僅是狀態需要切換，

而且，所使用的對戰也可能需要由用戶堆棧切換為系統對戰,

但這個系統對戰也是屬于該進程的。

1.4、本章疑難點

1.并行性與并發性的區別和聯系

并行性和并發性是既相似又有區別的兩個概念。并行性

是指兩個或多個事件在同一時刻發生，并發性是指兩個或多

個事件在同一時間間隔內發生。

2.分時系統與實時系統特征的比較

3.特權指令的工作機制

所謂特權指令是指有特殊權限的指令，由于這類指令的

全縣最大，如果使用不當，就會皮懷系統或其他用戶信息。

為了保證系統安全，這類指令只能用于操作系統或其他系統

軟件，不直接提供給用戶使用，主要用于系統資源的分配和

管理，包括改變系統的工作方式，檢測用戶的訪問權限，修

改虛擬存儲器管理的段表、頁表和完成人五的創建和切換等。

在某些用戶的計算機系統中，為了統一管理各種外部設備，

輸入輸出指令也作為特權指令，不允許用戶直接使用。需要

輸入輸出操作時，必須通過系統調用，經由操作系統完成。

特權指令那個必須在核心態之星，核心態又叫做特權態、系

統態。實際上，CPU在核心態的下可以執行指令系統的全集。

為了防止用戶系統中使用特權指令，用戶態下只能使用

除特權指令以外的指令，核心態下可以使用全部指令。所以

把用戶程序放在用戶態下進行，而操作系統中必須使用特權

指令的那部分程序在核心態下運行，保證了計算機系統的安

全可靠。從用戶態轉換為核心態的唯一途徑就是終端或異常。

4.系統調用產生的訪管中斷

程序員在編寫程序時，因要求操作系統提供服務而有意

識的使用“訪管指令”，從而導致程序中斷，這屬于一種自

愿性的中斷，所以又稱其為“訪管中斷”?！霸L管”中斷是由

訪管指令產生，程序員可以使用訪管指令中設置參數，當CPU

執行到訪管指令那個時，將訪管指令中的操作數存入到主存

中的約定單元，然后產生訪管中斷，引出操作系統來處理訪

管中斷中的具體要求。這種利用訪管指令來實現的指令成為

廣義指令。當初與用戶態的用戶程序使用訪管指令時，系統

根據該訪管指令的操作數執行訪管中斷處理程序，訪管中斷

處理程序將按系統調用的操作數和參數轉到響應的例行子

程序。完成服務功能后，退出中斷，返回到用戶程序斷點繼

續執行。

第二章進程管理

進程管理是操作系統的核心內容，也是每年必考的重點。

其中，進程概念、進程調度、信號量機制實現同步和互斥、

進程死鎖等更是重中之重，要求熟練掌握。此外，需要注意

的是：本章除了選擇題外還很容易考察綜合題，在最近三年

的考研綜合題有兩道題考察了本章的知識點。其中信號量實

現進程同步和互斥，進程調度算法和銀行家算法都是可能出

現的綜合題考點，需要讀者多加注意。

2.1、進程與線程

1、進程的概念和特征

(1)進程的概念

在多道程序環境下，允許多個程序并發執行，此時他們

將失去封閉性，并具有間斷性和不可再現性的特征。為此引

入了進程的概念，以便更好地描述和控制程序的并發執行,

實現操作系統的并發行和共享性。為此引入了進程的概念,

以便更好地描述和控制程序的并發執行，實現操作系統的并

發性和共享性。

為了是參與并發執行的程序能獨立的運行，必須為之配

置一個專門的數據結構，稱之為進程控制塊(process

controlblock),系統利用PCB來描述進程的基本情況和運

行狀態，進而控制和管理進程。

相應的，有程序段、相關數據段和PCB三部分構成了進

程映像（進程實體）。所謂創建進程，實質上是創建進程映

像中的PCB；而撤銷進程，實質上是撤銷進程的PCBo指的

注意的是，進程影響是靜態的，晉城市動態的。

從不同的角度，進程可以有不同的定義，比較經典的定

義有：

1）進程是程序的一次執行過程

2）進程是一個程序及其數據在處理器上順序執行時所發

生的活動。

3）進程是具有獨立功能的程序在一個數據集合上運行的

過程，他是系統進行資源分配和調度的一個獨立單位。

在引入了進程實體的概念后，我們可以吧傳統的操作系

統中的進程定義為：”進程是進程實體的運行過程，是系統

進行資源分配和調度的一個獨立單位”。

（2）進程的特征

進程是由多程序的并發執行而引出的，他和程序是兩個

截然不同的概念。進程的基本特征是對比單個程序的順序執

行提出的，也是對進程管理提出的基本要求。

1）動態性：進程是程序的一次執行，他有著創建、活動、

暫停、終止等過程，具有一定的生命周奇奇，是動態

的產生、變化和消亡的。動杰性是進程最基本的特征。

2）并發性：至多個進程實體，同存于內存中，能在一段

時間內同時運行，并發性是進程的重要特征，同時也

是操作系統的重要特征，引入進程的目的就是為了是

程序能與去其他進程的程序并發執行，以提高資源利

用率。

3）獨立性：指進程實體是一個能獨立運行、獨立獲得資

源和獨立接收調度的基本單位。范圍建立PCB的程序

都不能作為一個獨立的單位參與運行。

4）異步性：由于進程的相互制約，是進程具有執行的問

斷性。也即進程按各自獨立的、不可預知的速度向前

推進。異步性會導致執行結果不可再現性，為此，在

操作系統中必須配置相應的進程同步機制。

5）結構性：每個進程都配置一個PCB對其進行描述。從

結構上來看，進程實體是由程序段、數據段和進程控

制端三部分組成的。

2、進程的狀態與轉換

進程在其生命周期內，由于系統中個進程之間的相互制

約關系以及系統的運行環境的變化，使的進程的狀態也在不

斷地發生著變化。通常進程有以下五種狀態。前三種是進程

的基本狀態。

1）運行狀態：進程正在處理器上運行。在單處理

器的環境下，每一時刻最多只有一個進程處于

運行狀態。

2)就緒狀態：進程已處于準備運行的狀態，即進

程獲得了除CPU之外的一切所需資源，一旦得

到處理器即可運行。

3)阻塞狀態：又稱為等待狀態：進程正在等待某

一事件而暫停運行，如等待某資源為可用(不

包括處理器)，或等待輸入輸出的完成。及時處

理器空閑，該進程也不能運行。

4)創建狀態：進程正在被創建，尚未轉到就緒狀

態。創建進程通常需要多個步驟：首先申請一

個空白的PCB,并向PCB中填寫一些控制和管

理進程的信息；然后由系統為該進程分配運行

時所必須的資源；最后把該進程轉入到就緒狀

態。

5)結束狀態：進程正在從系統中消失，這可能是

進程正常結束或其他原因中斷退出運行。當進

程需要結束運行時，系統首先必須置該進程為

結束狀態，然后再進一步處理資源釋放和回收

工作。

注意區別就緒狀態和等待狀態：就緒狀態是指進程僅缺

少處理器，只要活得處理器資源就立即執行；而等待狀態是

指進程需要其他資源或等待某一事件，及時處理器空閑也不

能運行。

3、進程控制

進程控制的主要功能是對系統中所有進程實施有效地

管理，她具有創建新進程、撤銷已有進程、實現進程狀態轉

換等功能。在操作系統中，一般把進程控制用的程序段成為

原語，原語的特點是執行期間不允許中斷，他是一個不可分

割的基本單位。

（1）進程的穿件

允許一個進程創建另一個進程。

操作系統創建一個新進程的過程如下（創建原語）：

1）為新進程分配一個為我一個進程標示號，并申請一個

空白的PCB。

2）為進程分配資源，為新進程的程序和數據，以及用戶

占分配必要的空間。

3）初始化PCB,主要包括初始化標識信息、初始化處理

器狀態信息和初始化處理器控制信息，以及設置進程

的空閑及。

4）如果進程就緒隊列能夠接納新進程，就將新進程插入

到就緒隊列，等待被調度運行。

（2）進程的終止

引起進程終止的時間主要有：正常結束、表示進程的任

務已經完成和準備退出運行。異常結束是指進程在運行時,

發生了某種異常事件，是程序無法繼續運行，如：存儲區越

界、保護措、非法指令、特權指令錯、10故障等。外界干預

是指進程外界的請求而終止，如操作員或操作系統干預、父

進程請求和父進程終止。

操作系統終止進程的過程如下：（撤消原語）

1）根據被終止進程的標示符，檢索PCB,從中讀出該進

程的狀態。

2）若被終止進程處于執行狀態，立即終止該進程的執行,

將處理器資源分配給其他進程。

3）若該進程還有子進程，則應將其所有子進程終止。

4）將該進程所擁有的資源、或歸還給父進程或歸還給操

作系統。

5）將該PCB從所在隊列（鏈表）中刪除。

（3）進程的阻塞和喚醒

正在執行的進程，猶豫期待的某些時間為發生，如請求

系統資源失敗、等待某種操作的完成、新數據尚未到達或無

心工作可做等，則由系統自動執行阻塞原語，使自己由運行

狀態變為阻塞狀態?？梢?，進程的阻塞是進程自身的一種主

動行為。

阻塞原語的執行過程為：找到將要被阻射進城的標識號

對應的PCB,如果該進程為運行狀態，則保護其現場，將其

狀態改為阻塞狀態，停止運行，并把該PCB插入響應時間的

等待隊列中去；若為就緒狀態，則將其狀態改為阻塞狀態,

把它溢出就緒隊列，插入到等待隊列中去。

當阻塞進程所期待的時間出現時，如它所啟動的10操

作已完成或其所期待的數據已到達，則有關進程(比如，提

供數據的進程)，調用喚醒原語，將等待該事件的進程喚醒，

喚醒原語的執行過程是：在該事件的等待隊列中找到相應進

程的PCB,然后把該PCB插入到就緒隊列中，等待調度程序

調度。

需要注意的是，Block原語和Wakeup原語是一對作用剛

好相反的原語，必須成對使用。Block原語是由被阻塞進程

自我調用實現的，而Wakeup原語則是由一個與被喚醒進程

相合作或被其他相關進程調用實現的。

(4)進程的切換

無論什么樣的進程操作，都是在內核執行的。

進程切換是指當前正在運行的進程被轉換到其他狀態

后，再回到運行繼續執行的過程，這個過程中，進程的運行

環境產生了實質性的變化。進程切換的過程如下：

1）保存處理器上下文，包括程序計數器和其他寄存器。

2）更新PCB信息。

3）把進程的PCB移入相應的隊列，如就緒、在某時間阻

塞等隊列。

4）選擇另一個進程執行，并更新其PCBo更新內存管理

的數據結構。

5）恢復處理器的上下文。

4、進程的組織

進程是操作系統的資源分配和獨立運行的基本單位。

（1）進程控制塊

進程創建時，操作系統就新建一個PCB結構，它之后就

常駐內存，任意時刻可以存取。在進程結束時刪除。PCB是

進程實體的一部分，是進程存在的唯一標識。

PCB主要包括：進程描述信息、進程控制和管理信息、

資源分配清單和處理器相關信息等。

在一個系統中，通常存在這許多進程，有的處于就緒狀

態，有的處于阻塞狀態，而且阻塞的原因各不相同。為了方

便進程的調度和管理，需要將各進程的PCB用適當的方法組

織起來。目前，常用的組織方式有連接方式和索引方式兩種。

連接方式將同一狀態的PCB連接成一個隊列，不同狀態對應

不同的隊列，也可以把處于阻塞狀態的進程的PCB,根據其

阻塞原因的不同，排成多個阻塞隊列。索引方式是將同一狀

態的進程組織在一個索引表中，索引表的表項只想相應的

PCB,不同狀態對應不同的索引表，如就緒索引表和阻塞索

引表等。

(2)程序段

程序段就是能北京城調度程度調度到CPU執行的程序代

碼段。注意，程序可以被多個進程共享，就是說多個進程可

以運行同一個程序。

(3)數據段

一個進程的數據段，可以是進程對應的程序加工處理的

原始數據，也可以是程序執行時產生的中間或最終結果。

5、進程的通信

進程通信就是進程之間的數據交換。PV操作時低級通信

方式2,高級通信方式是指以較高的效率傳輸大量數據的通

信方式。高級通信方法可分為共享存儲、消息傳遞和管道通

信三大類。

(1)共享存儲

在通信的進程之間存在著一款可以直接訪問的共享空

見，通過對這塊共享空間的讀寫操作時間進程之間的信息交

換。在共享存儲方法中，需要使用同步互斥工具。

需要注意的是：用戶進程空間一般都是相互獨立的，要

想讓兩個用戶進程共享空間，必須通過特殊系統調用實現,

而進程內的線程是自然共享進程空間的。

(2)消息傳遞

在消息傳遞系統中，進程間的數據交換，是以格式化的

小心Message為單位的。

(3)管道通信

管道通信是消息傳遞的一種特殊方式。。所謂管道，就

是用于連接一個讀進程和一個寫進程以實現他們之間通信

的一個共享文件，又名為pipe文件。向管道或共享文件提

供輸入的發送進程，以字符流的形勢將大量的數據送入寫管

道；而接收管道輸出的接收進城，則從管道中接受數據。為

了協調雙方的通信，關到極致必須他提供以下撒按方面的協

調能力：互斥、同步和確定對方存在。

6、線程概念和多線程模型

(1)線程的基本概念

引入進程的目的，是為了是多道程序能并發執行，以提

高資源利用率和系統吞吐量；而引入線程，則是為了減小程

序在并發執行時所付出的時空開銷，提高操作系統的并發性

能。

線程最直接的理解就是“輕量級進程”，它是一個基本

的CPU執行單元，也是程序執行流的最小單元，由線程ID、

程序計數器、寄存器集合和堆棧組成。線程是進程中的一個

實體，是被系統獨立調度和分派的基本單位。進程只作為除

CPU以外的系統資源的分配單元，線程則作為處理器的分配

單元。線程也有就緒、阻塞和運行三種基本狀態。

（2）線程和進程的比較

1）調度：在引入線程的操作系統中，線程是獨立調度的

基本單位，進程是資源擁有的基本單位。

2）擁有資源：進程是擁有資源的基本單位，而線程不擁

有系統資源，單線程可以防偽其隸屬進程的系統資源。

3）并發性：在引入線程的操作系統中，不僅進程之間可

以并發執行，線程之間也可以并發執行，從而是操作

系統具有更好的并發性，大大提高了系統的吞吐量。

4）系統開銷：線程開銷極小。

5）地址空間和其他資源：進程的地址空間之間相互獨立,

同一進程的各線程間共享進程的資源，進程內的線程

對進程外的其他進程不可見。

6）通信方面：進程間通信需要進程同步和互斥手段的輔

助，以保證數據的一致性，而線程間可以直接讀寫進

程數據段來進行通信。

（3）線程的屬性

在多線程操作系統中，八仙城作為獨立運行的基本單位。

此時的進程已不是一個基本可執行的實體。線程的主要屬性

如下：

1）線程是一個輕型實體，它不擁有系統資源，但每個線

程都應有一個唯一的標識符和一個線程控制塊，線程

控制塊記錄了線程執行的寄存器和棧等現場情況。

2）不同的線程可以執行相同的程序，即同一個服務程序

被不同的用戶調用時，操作系統為他們創建不同的線

程。

3）統一進程中的各個線程共享該進程所擁有的系統資源。

4）線城市處理器的獨立調度單位，多個線程是可以并發

執行的。

5）一個縣城被創建后便開始了它的生命周期，直至終止，

線程在生命周期內會經歷等待態、就緒態和運行態等

各種狀態變化。

(4)線程的實現方法

線程的實現可以分為兩類：用戶級線程和內核級線程。

(5)多線程模型

有些系統同時支持用戶線程和內核線程，由此產生了不

同的多線程模型，即實現用戶級線程和內核級線程的連接方

式。

1)多對一模型。多對一模型將多個用戶級線程映射到一

個內核級線程。線程管理在用戶空間完成。

2)一對一模型。

3)多對多模型。

特點：克服了多對一模型的并發度不高的缺點，又克服

了一對一模型中一個用戶進程占用太多內核級線程，開銷太

大的缺點。

2.2、線程的調度

1、調度的概念

(1)調度的基本概念

在多道程序系統中，進程的數量往往多于處理器的個數,

進程爭用處理器的情況在所難免。處理器調度是對處理器進

行分配，就是從就緒隊列中，按照一定的算法，選擇一個進

程并將處理器分配給他運行，以實現進程的并發執行。

處理器調度是多道程序操作系統的基礎，它是操作系統

設計的核心問題。

（2）調度的層次

一個作業從提交開始知道完成，往往要經歷一下三級調

度：

1）作業調度。作業調度又稱高級調度：其主要任務是

按一定的原則從外存上處于后備狀態的作業中挑選一個或

多個作業，給他們分配內存、輸入輸出設備等必要的資源。

并建立相應的進程，以使他們獲得競爭處理器的權利。

多道批處理系統中大多配有作業調度，而其它系統中通

常不需要配置作業調度。作業調度的執行頻率較低，通常為

幾分鐘一次。

2）中級調度。中級調度又稱內存調度。引入中級調度

視為了提高內存利用率和系統吞吐率，為此，應使那些暫時

不能運行的進程調至外存等待，把此時的進程狀態稱為掛起

狀態。當他們已具備運行條件且內存有稍有空閑時，由中級

調度來決定，吧外存上那些已具備運行條件的就緒進程，在

重新調入內存，并修改其狀態為就緒狀態，掛在就緒隊列上

等待。

3）進程調度。進程調度又稱為低級調度，其主要任務

是按照某種方法和策略從就緒隊列中選取一個進程，將處理

器分配給它。進程調度是操作系統中最基本的一中調度，在

一般操作系統中都不需配置進程調度。進程調度的頻率很高,

一般幾十毫秒一次。

(3)三級調度的聯系

作業調度從外存的后備隊列中選擇一批作業進入內存，

為他們建立進程。這些進程被送入就緒隊列。進程調度從就

緒隊列中選出一個進程，并把其狀態改為運行狀態，把CPU

分配給它。中級調度是位于高級調度和低級調度之間的一種

調度。為了提高內存的利用率，系統將那些暫時不能運行的

進程掛起來。當內存空間寬松式，通過中級調度選擇具備運

行條件的進程，將其喚醒。

2、調度的時機、切換與過程

進程調度和切換程序是操作系統內核程序。當請求調度

的事件發生后，才可能會運行進程調度程序，當調度了新的

就緒進程后，才會去進行進程間的切換。

現在操作系統中，不能進行進程的調度與切換的情況有

以下幾種：

1)在處理中斷的過程中：中斷處理過程復雜，在

實現上很難做到，而且中斷處理時系統工作的

一部分，邏輯上不屬于某一進城，不應被剝奪

處理器資源。

2)進程在操作系統內核程序臨界區中：進入臨界

區后，需要獨占式的訪問共享數據，理論上必

須加鎖，以防止其他并行程序的進入，在解鎖

前不應該切換到其他進程，以加快該共享數據

的釋放。

3)其他需要完全屏蔽中斷的原子操作過程中：如

加鎖、解鎖、中斷現場保護、恢復等等源自操

作。在原子過程中，連中斷都要屏蔽，更不應

該進行進程的切換。

如果在上述過程中發生了引起調度的條件，并不能馬上

進行調度和切換，應置系統請求調度標志，知道上述過程結

束后才能進行相應的調度和切換。

應該進行進程的調度與切換的情況有：

1)當發生引起調度條件且當前進程無法繼續運行下去時,

可以馬上進行調度與切換。如果操作系統只在這種情

況下進行進程調度，就是非剝奪調度。

2)當中斷處理結束后或自陷處理結束后，返回被中斷進

程的用戶態程序執行現場前，若置上請求調度標志，

即可馬上進行進程調度與切換。如果操作系統支持這

種情況下的運行調度程序，就實現了剝奪方式的調度。

進程切換往往在調度完成后立刻發生，它要求保存源進

程當前切換點的縣城信息，恢復被調度進程的現場信息?，F

場切換時，操作系統內核將遠近程的現場信息推入到當前進

程的內核對戰來保存他們，并更新堆棧指針。內核完成從新

進程的內核棧中裝入新進程的縣城信息、更新當前運行進程

空間指針、重設PC寄存器等相關工作之后，開始運行新的

進程。

3、進程調度方式

所謂進程調度方式是指當某一個進程正在處理器上執

行時，若有某個更為重要或緊迫的進程需要處理，既有優先

權更高的進程進入就緒隊列，此時應如何分配處理器。通常

有一下兩種進程調度方式：

（1）非剝奪調度方式

非剝奪調度方式又稱為非搶占調度方式，是指當一個進

程正在處理器上執行時，即使有某個更為重要或緊迫的進程

進入就緒狀態，仍然讓正在執行的進程繼續執行，知道該進

程完成或發生某種時間而進入阻塞狀態時，才把處理器分配

給更為重要或緊迫的進程。

（2）剝奪調度方式

剝奪調度方式又稱為搶占方式，是指當一個進程正在處

理器上執行時，若有某個更為重要或緊迫的進程需要使用處

理器，則立即暫停正在執行的進程，將處理器分配給這個更

為重要或緊迫的進程。

“剝奪”不是一種任意性行為，必須遵循一定的原貝I:

優先權原則，短進程優先原則和時間片原則。

4、調度的基本準則

不同的調度算法具有不同的特性，在選擇調度算法時,

必須考慮算法所具有的特性。為了比較處理器調度算法的性

能，人們提出很多評價準則，下面介紹主要的幾種準則：

(1)CPU利用率

CPU是計算機系統中最重要的資源之一，所以應盡可能

使CPU保持在忙狀態，是這一資源利用率最高。

(2)系統吞吐量

系統吞吐量表示單位時間內CPU完成作業的數量。長作

業需要消耗較長的處理器時間，因此會降低系統的吞吐量。

而對于短作業，他們所需要消耗的處理器時間端，因此能提

高系統的吞吐量。調度算法和方式的不同，也會對系統的吞

吐量產生較大的影響。

(3)周轉時間

周轉時間是指從作業提交到作業完成所經歷的時間，包

括作業等待、在就緒隊列中排隊、在處理器上運行以及進行

輸入輸出操作所花費的時間的總和。

作業的周轉時間二作業完成時間-作業提交時間

(4)等待時間

等待時間是指進程處于等處理器狀態時間之和，等待時

間越長，用戶滿意度越低。處理器調度算法實際上并不影響

作業執行或輸入輸出操作時間，只影響作業在就緒隊列中等

待所花的時間。因此，衡量一個調度算法優劣常常只需簡單

地考察等待時間。

(5)響應時間

響應時間是指從用戶提交請求到系統首次產生響應所

有的時間。在交互式系統中，周轉時間不可能是最好的評測

準則，一般采用響應時間作為衡量調度算法的重要準則之一。

從用戶的角度來看，調度策略應盡量降低響應時間，使響應

時間處在用戶能夠接受的范圍之內。

5、典型的調度算法

通常系統的設計目標不同，所采用的調度算法也不同。

在操作系統中存在多種調度算法，其中有的調度算法適用于

作業調度，有的調度算法適用于進程調度，有的調度算法兩

者都適用。下面介紹幾種常用的調度算法：

（1）FIFS先來先服務調度算法

特點：算法簡單，但是效率低；有利于長作業，不利于

短作業；有利于CPU繁忙型作業而不利于10繁忙型作業。

（2）SJF短作業優先調度算法

短作業（進程）優先調度算法是指對短作業禍端進程優

先調度的算法。短作業優先調度算法是從后備隊列中選擇一

個或若干個估計運算時間最短的作業，將他們呢掉入內存運

行。

SJF調度算法的缺點：

1）該算法對長作業不理。

2）該算法完全未考慮作業的緊迫程度

3）由于作業的長短只根據用戶所提供的估計執行時

間而定的，而用戶又可能會有意或無意的縮短其作

業的估計運行時間，致使該算法不一定能真正做到

算作業優先調度。

4）注意：SJF調度算法的平均等待時間、平均周轉時

間最少。

(3)優先級調度算法

(4)高響應比優先調度算法

高響應比優先調度算法主要用于作業調度。同時考慮從

每個作業的等待時間和估計需要運行的時間。

(5)時間片輪轉調度算法

時間片輪轉調度算法主要適用于分時系統。

(6)多級反饋隊列調度算法

多級反饋隊列調度算法主要是時間片輪轉調度算法和

優先級調度算法的綜合和發展。通過動態調整進程優先級和

時間片大小，多級反饋隊列調度算法可以兼顧多方面的系統

目標。

2.3、進程同步

1、進程同步的基本概念

多道程序環境下，進程是并發執行的，不同進程間存在

著不同的相互制約關系。為了協調進程之間的相互制約關系,

達到資源共享和進程協作，避免進程之間的沖突，引入了進

程同步的概念。

(1)臨界資源

多個進程可以共享系統中的各種資源，但其中許多資源

一次只能為一個進程所使用，我們把一次只允許一個進程使

用的資源成為臨界資源。

對臨界資源的訪問，必須互斥的進行。每個進程中，訪

問臨界資源的那段代碼成為臨界區。

為了保證臨界資源的正確使用，可以把臨界資源的訪問

過程分為四個部分。

1)進入區。為了進入臨界區使用臨界資源，在進入去要

檢查可否進入臨界區。

2)臨界區。進程中訪問臨界資源的那段代碼。

3)退出區。將正在訪問臨界區的標志清除。

4)剩余區。代碼中的其余部分。

do{

entrysection；

criticalsection；

exitsection；

remaindersection；

}while(true)

(2)同步

同步已成為直接制約關系，它是為完成某種任務而建立

的兩個或多個進程。這些進程因為需要在某些位置上協調他

們的工作次序而等待、傳遞信息所產生的制約關系。進程間

的直接制約關系就是它們之間的相互合作。

(3)互斥

互斥亦稱間接制約關系。當一個進程進入臨界區使用臨

界資源時，另一個進程必須等待，當占用臨界資源的進程退

出臨界區后，另一個進程才允許去訪問此臨界資源。

2、實現臨界區互斥的基本方法

(1)軟件實現方法

在進入區設置和檢查一些標志來表名是否有進程在臨

界區中，如果已有進程在臨界區，則在進入區通過循環檢查

進行等待，進程離開臨界區后則在退出區修改標志。

(3)硬件實現方法

本節對硬件實現的具體理解對后面的信號量學習很有

幫助。計算機提供了特殊的硬件指令，允許對一個字中的內

容進行檢測和修正，活著是對兩個字的內容進行交換等。通

過硬件支持實現臨界段問題的低級方法或稱為元方法。

1）中斷屏蔽方法。當一個進程正在使用處理器執行他的

臨界區代碼時，要防止去其他進程在進入其臨界區訪

問的最簡單方法就是禁止一切中斷的發生，或稱之為

屏蔽中斷、關中斷。因為CPU只有在發生中斷時引起

進程的調度和切換，這樣屏蔽中斷就能保證當前運行

進程將臨界區代碼順利的執行完，然后再開中斷。

這種方法限制了處理器交替執行程序的能力，因此執行

的效率將會明顯降低。對內核來說，當它執行更新變量或列

表的幾條指令期間關中斷是很方便的，但將關中斷的權力交

給用戶則很不明智，若一個進程關中斷之后不再打開終端,

則系統可能會因此終止。

2）硬件愛你指令法。

TestAndSet指令：這條指令是原子操作。及執行該代碼

是不允許被中斷。其功能是獨處制定標志后把該標志設置為

真。

BooleanTestAndSet(Boolean*lock){

Booleanold；

01d=*lock；

*lock=true；

Returnold；

Lock為每個臨界資源設置的共享布爾變量，true表示

正在被占用，false表示沒被占用。

WhileTestAndSet(&lock)；

進程的臨界區代碼；

Lock=false；

進程剩余代碼；

Swap指令：該指令的功能是交換兩個字的內容。

Swap(Boolean*a,Boolean*b){

Booleantemp；

Temp=*a；

*a二*b；

*b=temp；

}

以上對TestAndSet和Swap指令僅僅是功能實現，并非

軟件實現定義，事實上他們是由硬件邏輯直接實現的，不會

被中斷。

硬件方法優點：使用與任意數目的進程，不管是單處理

器還是多處理器：簡單、容易驗證其正確性?？梢灾С诌M程

內有多個臨界區，只需要為每個臨界區設立一個布爾變量。

硬件方法的缺點：進程等待進入臨界區時要耗費處理器

時間，不能實現讓權等待。從等待進程中隨機選擇一個進入

臨界區，有的進程可能一直選不上，從而導致“饑餓”現象。

3、信號量

信號量機構是一種功能較強的機制，可用來解決互斥與

同步的問題，它只能被兩個標準原語wait和signal來訪問，

也可以記作p操作和v操作。

原語是指完成某種功能且不被分割不被中斷執行的操

作序列，有時也成為原子操作，通常可用硬件來實現完成某

種功能的不可分割執行特性。

(1)整形信號量

整形信號量被定義為一個用于表示資源個數的整型量So

(2)記錄性信號量

記錄性信號量是不存在“忙等”現象的進程同步機制。

除了需要一個用于代表資源數的整型變量value外，再增加

一個進程鏈表L,用于連接所有等待該資源的進程，記錄型

信號量是由于采用了記錄型的數據結構得名。記錄型信號量

可描述為：

Typedefstruct{

Intvalue；

Structprocess*L；

}semaphore；

Wait操作，表示進程請求一個該類資源，當S.valueVO

時，表示該類資源已分配完畢，因此進程調用block原語,

進行自我阻塞，放棄處理器，并插入到S.L中，可見該機制

遵循了“讓權等待”的原則。Signal操作，表示進程釋放

一個資源，使系統中可供分配資源數增加一，故S.value++o

若加1后仍是S.value〈二0,則表示S.L中仍有等待該資源的

進程被阻塞，故還應調用wakeup原語，將S.L中的第一個

等待進程喚醒。

（3）利用信號量實現同步

信號量機構能用于解決進程間各種同步問題。

（4）利用信號量實現互斥

信號量機構能很方便的解決進程互斥問題。

互斥的實現是不同進程對同一信號量進行P操作和V操

作，一個進程在成功地對信號量執行了P操作后進入臨界區,

并在退出臨界區后，由該進程本身對該信號量執行V操作,

表示當前沒有進城進入臨界區，可讓其他進程進入。

（5）利用信號量實現前驅關系

信號量也可以用來描述程序之間或者語句之間的前驅

關系。

(6)分析進程同步或互斥問題的方法步驟

1)關系分析。找出問題中的進程數，并且分析它們之間

的同步和互斥關系。同步、互斥、前去關系直接按照

上面例子中的經典犯事改寫。

2)整體思路。找出解決問題的關鍵點，并且根據做過的

題目找出解決的思路。根據進程的操作流程確定P操

作、V操作的大致順序。

3)設置信號量。根據上面兩步，設置需要的信號量，確

定初值，完善整理。

4、管程

(1)管程的定義

管程是一組數據以及定義在這組數據之上的對這組數

據的操作組成的軟件模塊，這組操作能初始化并改變管程中

的數據和同步進程。

(2)管程的組成

1)局部與管程的共享結構數據說明

2)對該數據結構進行操作的一組過程

3)對局部于管程的共享數據設置初始值的語句

(3)管程的基本特性

1)局部于管程的數據只能被局部于管程內的過程訪問。

2)一個進程只有通過調用管程內的過程才能進入廣成

訪問的共享數據。

3)每次僅允許一個進程在管程內執行某個內部過程。

由于管程是一個語言成分，所以管程的互斥訪問完全由

編譯程序在編譯時自動添加，無需程序員關注，而且保證正

確。

5、經典同步問題

(1)生產者-消賽者問題

問題描述：一組生產者進程和一組消賽者進程共享一個

初始為空、大小為n的緩沖區，只有緩沖區沒滿時，生產者

才能把消息放入到緩沖區，否則必須等待；只有緩沖區不為

空時，消費者才能從中取出消息，否則必須等待。由于緩沖

區是臨界資源，它只允許一個生產者放入消息，或一個消費

者從中取出消息。

問題分析：

1)關系分析。生產者和消費者對緩沖區互斥訪問是互

斥關系，同時生產者和消費者又是一個相互協作的關系，只

有生產者生產之后，消費者才能消賽，他們也是同步關系。

2）整理思路。這里比較簡單，只有生產者和消賽者兩

個進程，正好是這兩個進程存在著互斥關系和同步關系。那

么需要解決的是胡吃喝同步PV操作的位置。

3）信號量的設置。信號量mutex作為互斥信號量，它

用于控制互斥訪問緩沖池，互斥信號量初始為1;信號量full

用于記錄當前緩沖池中“滿”緩沖區數，初值為0.信號量

empty用于記錄當前緩沖池中空緩沖區，初值為n。

下面再看一個較為復雜的生產者-消費者問題：

問題描述：桌子上有一只盤子，每次孩子能向其中放入

一個水果。爸爸專向盤子中放入蘋果，媽媽專向盤子中放入

橘子，女兒專等吃盤子中的蘋果，兒子專等吃盤子中的橘子。

只有盤子為空時，爸爸或媽媽就可向盤子中放一只水果2；

僅當盤子中有自己需要的水果時，兒子或女兒可以從盤子中

取出。

問題分析：

1）關系分析。這里的關系略微復雜一些，首先由每次

只能向其中放入一只水果可知爸爸和媽媽是互斥關系。爸爸

和女兒、媽媽和兒子是同步關系，而且這兩對進城必須連起

來，兒子和女兒之間沒有互斥和同步關系，因為他們是選擇

條件執行，不可能并發。

2）整理思路。這里有4個進程，實際上可以抽象為兩

個生產者和兩個消費者被連接到大小為1的緩沖區上。

3）信號量設置。首先設置信號量plate為互斥信號量，

表示是否允許想盤子放水果，初值為1,表示允許放入，且

只允許放一只。信號量apple表示盤子里是否有蘋果，初值

為0,表示盤子中無2蘋果；信號量orange表示盤子中是否

有橘子，初始量為0,表示盤子中無橘子。

（2）讀者-寫著問題

問題描述：有讀者和寫者兩組并發進程，共享一個文件,

當兩個以上的讀進程同事訪問共享數據時不會產生副作用，

但若某個寫進程和其他進程（讀進程或寫進程）同時訪問共

享數據時則可能導致數據不一致的錯誤。因此要求：1）允

許多個讀者同時對文件執行讀操作；2）只允許一個寫者往

文件中寫信息；3）任一寫者在完成寫操作之前不允許其他

讀者或寫者工作；4）寫者執行完寫操作前，應讓已有的讀

者或寫者全部退出。

問題分析：

1）關系分析。由題目分析讀者和寫者是互斥的，寫者

和寫者也是互斥的，而讀者和讀者不存在互斥關系。

2）整理思路。兩個進程，即讀者和寫者。寫者比較簡

凡，它和任何進程互斥，用互斥信號量p操作、v操作即可

解決。讀者的問題比較復雜，它必須實現與寫著互斥的關系，

還要實現和其他讀者同步的關系。因此，緊急簡單的一對PV

操作時無法解決的。那么在這里用到了一個計數器，用它來

判斷當前是否有讀者讀文件。當有讀者的時候，寫著是無法

寫文件的，此時讀者會一直占用文件，當沒有讀者的時候,

寫者才可以寫文件。同事這里不同讀者對計數器的訪問也是

互斥的。

3)信號量的設置。首先設置信號量count為計數器，

用來記錄當前讀者數量，初值為0;設置mutex為互斥信號

量，用于保護更新count變量時的互斥；設置互斥信號量rw

用于保證讀者和寫者的互斥訪問。

(3)哲學家進餐問題

問題描述：一張圓桌上坐著五個哲學家，每兩個哲學家

之間的桌子上擺著一根筷子，桌子的中間是一碗米飯。哲學

家們傾注畢生精力用于思考和進餐，哲學家在思考是，并不

影響其他人。只有當哲學家饑餓的時候，才視圖拿起左右兩

根筷子。如果筷子已經在他人手上，則需等待。饑餓的哲學

家只有同時拿到了兩根筷子才可以開始進餐，當今參悟你比

猴，放下筷子繼續思考。

問題分析：

1）關系分析。五個哲學家與左右鄰居對其中的筷子的

訪問是互斥關系。

2）整理思路。顯然這五個進程，要解決的問題有兩個：

一個是讓他們同時拿起兩個筷子；而是對每個哲學家的動作

執行規則，避免饑餓或者死鎖現象發生。

3）信號量設置。定義互斥信號組chopsticks[5]

={1,1,1,1,1}用于對五個筷子的互斥訪問。

對哲學家按順序0~4編號，哲學家i左邊的筷子編號為

i,哲學家右邊的筷子編號為（i+1）%5O

（4）吸煙者問題

問題描述：假設一個系統有三個吸煙者進程和一個供應

者進程。每個抽煙者不停的卷煙并抽調他，但是要卷起并抽

掉一支煙，抽煙者必須要有三種材料：煙草、紙和膠水。三

個抽煙者中，第一個有煙草，第二個有紙，第三個有膠水。

供應者進程無線地提供提供三種材料。

供應者每次將兩種材料放到桌子上，擁有剩下那種材料

的抽煙者卷一根煙并抽掉它，并給供應者一個信號告訴完成

了，供應者就會放另外兩種材料在桌子上，這種過程一直重

復。

問題分析：

1）關系分析。供應者與三個抽煙者分別是同步關系。

由于供應者無法同時滿足兩個或兩個以上的抽煙者，三個抽

煙者對抽煙這個動作是互斥關系。

2)整理思路。顯然這里有四個進程。供應者作為生產

者向三個抽煙者提供材料。

3)信號量設置。信號量offerl、offer2>offer3分別

表示煙草和紙組合的資源、煙草和膠水組合的資源、紙和膠

水組合的資源。信號量finish用于互斥進行抽煙動作。

2.4、死鎖

1、死鎖的概念

(1)死鎖的定義

在多道程序系統中，由于多個進程的并發執行，改善了

系統資源的利用率并提高了系統的處理能力。然而，多個進

程的并發執行也帶來了新的問題一一死鎖。所謂死鎖是指多

個進程因競爭資源而造成的一種僵局，若無外力作用，這些

進程都將無法向前推進。

(2)死鎖產生的原因

1)系統資源的競爭

通常系統中擁有的不可剝奪資源，其數量不足一滿足多

個進程運行的需要，似的進程在運行過程中會因爭奪資源而

陷入僵局。只有對不可剝奪資源的競爭才可能產生死鎖，對

可剝奪資源的競爭是不會引起死鎖的。

2）進程推進順序非法

進程在運行過程中，請求和釋放資源的順序不當，同樣

會導致死鎖。

信號量使用不當也會造成死鎖。進程間相互等待對方發

來的消息，結果也會造成某些進程間無法繼續向前推進。

3）死鎖產生的必要條件

產生死鎖必須同時滿足以下四個條件，只要其中任一個

條件不成立，死鎖就不會發生。

互斥條件：進程要求對所分配的資源進行排他性控制,

即在一段時間內某資源僅為一個進程所占用。此時若有其他

進程請求該資源，則請求進程只能等待。

不剝奪條件：進程所獲得的資源在未使用完畢之前，不

能被其他進程強行奪走，即只能由獲得該資源的進程自己來

釋放。

請求和保持條件：進程已經保持了至少一個資源，但又

提出了新的資源請求，而該資源已被其他進程占有，此時請

求進程被阻塞，但對自己已獲得的資源保持不放。

循環等待條件：存在一種進程資源的循環等待鏈，連中

每一個進程已獲得的資源同時被鏈中下一個進程所請求。

2、死鎖的處理策略

為使系統不發生死鎖，必須設法破壞產生死鎖的四個必

要條件之一，或者允許死鎖產生，但當死鎖發生時能檢測出

思索，并有能力實現恢復。

死鎖處理策略有：

(1)死鎖預防。

破壞死鎖的四個必要條件之一。

(2)死鎖避免。

用某種方式防止系統進入不安全狀態。

(3)死鎖的檢測及解除

允許進程在運行過程中發生死鎖，通過系統的檢測機構

及時地檢測出死鎖的發生，然后采取某種措施解除死鎖。

3、死鎖預防

防止死鎖發生只需要破壞死鎖產生的四個必要條件之

一即可。

(1)破壞互斥條件

允許系統資源都能共享使用。(不太可行)

(2)破壞不剝奪條件

當一個以保持了某些不可剝奪資源的進程，請求新的資

源時得不到滿足，它必須釋放已經保持的所有資源，待以后

需要時再重新申請。這種方法常用于狀態易于保存和恢復的

資源，如CPU的寄存器及內存資源，一般不能用于打印機之

類的資源。

(3)破壞請求和保持條件

采用預先靜態分配方法，即進程在運行前一次申請完

他所需要的全部資源，在他的資源未滿足前，不把它投入運

行。一旦運行后，這些資源就一直歸它所有，也不再提出其

他資源請求，這樣就可以保證系統不會發生死鎖。

這種方式實現簡單，但缺點也顯而易見，系統資源被嚴

重浪費，其中有些資源可能僅在運行初期或末期才使用，甚

至根本不使用。而且還會導致“饑餓”現象，當由于個別資

源長期被個別資源占用時，將只是等待該資源的進程遲遲不

能開始運行。

(4)破壞循環等待條件

為了破壞循環等待條件，可采用順序資源分配法。首先

給系統中的資源編號，規定每個進程，必須按編號遞增的順

序請求資源，同類資源一次申請完。也就是說，只要進程提

出申請分配資源，則該進程在以后的資源申請中，只能申請

編號比之前大的資源。

4、死鎖避免

避免思索同樣是屬于事先預防的策略，但并不是事先采

取某種限制措施破壞死鎖的必須條件，而是在資源動態分配

過程中，防止系統進入不安全狀態，以避免死鎖發生。這種

方法所施加的限制條件較弱，可以獲得較好的系統性能。

(1)系統安全狀態

避免死鎖的方法中，允許進程動態的申請資源，但系統

在進行資源分配前，應先計算此次資源分配的安全性。若此

次分配不會導致系統進入不安全狀態，則將資源你分配給進

程，否則，讓進程等待。

所謂安全狀態，是指系統能按某種進程推進順序，為每

個進程分配其所需的資源，直至滿足每個進程對資源的最大

需求，是每個進程都可以順序的完成。此時成PlP2P3oo為

安全序列，如果系統無法找到一個安全序列，則稱系統處于

不安全狀態。

并非所有的