計(jì)算機(jī)操作系統(tǒng)講義與測試題

操作系統(tǒng)

講義

第一部分：操作系統(tǒng)引論⑴

一、操作系統(tǒng)基本常識(shí)

1.計(jì)算機(jī)是由硬件和軟件兩部分組成的，而操作系統(tǒng)（OperatingSystem）是配置在計(jì)算

機(jī)硬件之上的第一層軟件，是對計(jì)算機(jī)硬件的第一次擴(kuò)充。操作系統(tǒng)是系統(tǒng)軟件的基礎(chǔ)，

其他的系統(tǒng)軟件，例如編譯程序、匯編程序、數(shù)據(jù)庫管理系統(tǒng)、診斷程序等，都是在操

作系統(tǒng)的支持下工作的，都要依賴于操作系統(tǒng)，取得操作系統(tǒng)提供的各類服務(wù)。

2.操作系統(tǒng)的目標(biāo)是什么？

1）方便性：計(jì)算機(jī)硬件只能識(shí)別。或1,即只能識(shí)別機(jī)器代碼，因此沒有配置操作系

統(tǒng)的計(jì)算機(jī)是難以使用的；如果配置了操作系統(tǒng)，則可以使用OS提供的各種命令

來使用計(jì)算機(jī)系統(tǒng)，從而方便了用戶，也使計(jì)算機(jī)變得易學(xué)易用。

2）有效性：操作系統(tǒng)可以管理CPU.I/O設(shè)備等系統(tǒng)資源，從而避免各種資源使用無

需而引起的資源浪費(fèi)現(xiàn)象。配置了OS的計(jì)算機(jī)可有效改善系統(tǒng)的資源利用率和提

高系統(tǒng)吞吐量。

3）可擴(kuò)充性：OS采用模塊化設(shè)計(jì)，可適應(yīng)計(jì)算機(jī)硬件和體系結(jié)構(gòu)的迅速發(fā)展，可方

便增加新的功能模塊和修改舊的功能模塊。

4）開放性：為了適應(yīng)不同的硬件系統(tǒng)和軟件系統(tǒng)，實(shí)現(xiàn)硬件設(shè)備正確、有效地協(xié)同

工作，以及實(shí)現(xiàn)應(yīng)用程序地可移植性和互操作性，要求OS具有開放性。

說明：方便性和有效性是OS最重要的兩個(gè)目標(biāo)。當(dāng)前更重視OS使用上的方便性。

3.操作系統(tǒng)的作用有哪些？

1）從一般用戶的觀點(diǎn)看，OS是用戶和計(jì)算機(jī)硬件系統(tǒng)之間的接口；用戶可以通過命

令方式或者系統(tǒng)調(diào)用方式來使用計(jì)算機(jī)。

2）從資源管理的觀點(diǎn)看，OS是計(jì)算機(jī)資源的管理者。計(jì)算機(jī)的資源分為四類：處理

器、存儲(chǔ)器、I/O設(shè)備和信息（數(shù)據(jù)和程序），相應(yīng)地，OS系統(tǒng)的主要功能也是對

這四類資源的管理，即：處理機(jī)管理、存儲(chǔ)器管理、I/。設(shè)備的管理、文件管理。

這也是本課程要介紹的主要內(nèi)容。

3）OS可用作擴(kuò)充機(jī)器。沒有任何軟件支持的計(jì)算機(jī)，稱為裸機(jī)，覆蓋了軟件的機(jī)器

稱為虛擬機(jī)（Virtualmachine）；每多覆蓋一層軟件，則虛擬機(jī)的功能就越強(qiáng)。

4.操作系統(tǒng)可以用一種層次結(jié)構(gòu)模型描述：底層是OS對象，中間層是對對象進(jìn)行的操作

和管理的軟件的集合；最高層是OS提供給用戶的用戶接口。

二、操作系統(tǒng)發(fā)展歷程

1.無操作系統(tǒng)時(shí)代：

1）人工操作方式：主要發(fā)生在第一代計(jì)算機(jī)到上世紀(jì)50年代中期，此時(shí)的程序員通過

人工操作方式直接操作計(jì)算機(jī)硬件系統(tǒng)；用戶獨(dú)占全槌口CPU等待人工操作是這種

方式的主要缺點(diǎn)。

人工操作方式嚴(yán)重影響了計(jì)算機(jī)資源的利用率，引起了所謂的“人機(jī)矛盾,后

來出現(xiàn)了“通道技術(shù)"和"緩沖技術(shù)"，用于緩和此矛盾，但是效果不好，再后來引

入了“脫機(jī)輸入輸出方式"，獲得了良好的效果。

2）脫機(jī)輸入輸出方式：該方式最突出的方式是增加了外圍機(jī)。外圍機(jī)的作用在于脫機(jī)

控制輸入設(shè)備和輸出設(shè)備。因?yàn)檩斎牒洼敵龆际窃诿摍C(jī)狀態(tài)下進(jìn)行的，因此可有效

減少CPU的空閑時(shí)間，從而緩和了人機(jī)矛盾。該中方式的優(yōu)點(diǎn)是：減少了CPU的

空閑時(shí)間；提高了I/。的速度。

2.操作系統(tǒng)時(shí)代

1）單道批處理系統(tǒng)（SimpleBatchSystem）:是為提高系統(tǒng)資源利用率和系統(tǒng)吞吐量而

提出的，配有監(jiān)督程序（Monitor）。首先將一批作業(yè)以脫機(jī)輸入輸出方式（Off-LineI/O）

輸入道磁帶上，然后在監(jiān)督程序的監(jiān)督之下順序執(zhí)行。此種方式可保證系統(tǒng)對作業(yè)

的處理是成批進(jìn)行的，目內(nèi)存中總保持一道作業(yè)。其效果并不好，目前已經(jīng)很少使

用。其特點(diǎn)是：自動(dòng)性（無需人工干預(yù)I順序性、單道性?？梢哉J(rèn)為SBS是OS的

前身。

說明：系統(tǒng)吞吐量是指系統(tǒng)在單位時(shí)間內(nèi)完成的總工作量。

2）多道批處理系統(tǒng)：為進(jìn)一步提高系統(tǒng)資源的利用率和系統(tǒng)吞吐量，引入了多道程序

設(shè)計(jì)技術(shù)，增加了作業(yè)調(diào)度程序。用戶提交的作業(yè)都存放在外存上，排成一個(gè)隊(duì)列

（后備隊(duì)列）；然后，由專門的作業(yè)調(diào)度程序按照一定的算法（？）從后備隊(duì)列中選

擇若干個(gè)作業(yè)調(diào)入內(nèi)存，這些作業(yè)共享內(nèi)存和處理機(jī)等資源，可并發(fā)運(yùn)行。優(yōu)點(diǎn)：

提高CPU的利用率（有效避免I/。等待）；提高內(nèi)存和I/O設(shè)備的利用率；增加系統(tǒng)

吞吐量。缺點(diǎn)：平均周轉(zhuǎn)時(shí)間長；無交互能力。特征：多道性、無序性（作業(yè)完成

順序同進(jìn)入順序無關(guān)1調(diào)度性（作業(yè)調(diào)度和進(jìn)程調(diào)度\

說明：作業(yè)調(diào)度是將作業(yè)從外存調(diào)入內(nèi)存，但是不一定占有處理機(jī)；進(jìn)程調(diào)度是從

已在內(nèi)存中的作業(yè)選擇一個(gè)作業(yè)，將處理機(jī)分配給它，使其運(yùn)行。

平均周轉(zhuǎn)時(shí)間：從作業(yè)進(jìn)入系統(tǒng)開始，指導(dǎo)其完成并退出系統(tǒng)所經(jīng)歷的時(shí)間。

3）分時(shí)系統(tǒng)（Time-SharingSystem）：是一臺(tái)主機(jī)+多個(gè)終端的系統(tǒng)。推動(dòng)分時(shí)系統(tǒng)

形成和發(fā)展的動(dòng)力是用戶的需要。用戶使用計(jì)算機(jī)時(shí)，希望實(shí)現(xiàn)“人機(jī)交互"，以

便能對錯(cuò)誤進(jìn)行修改，并且希望能獨(dú)占主機(jī)；但是在19世紀(jì)60年底，計(jì)算機(jī)^常

昂貴，又不可能每個(gè)用戶獨(dú)占一臺(tái)主機(jī)，所以“共享主機(jī)"是一個(gè)不錯(cuò)的選擇；同

時(shí)，如果每個(gè)用戶各自占用一臺(tái)終端設(shè)備，則可以方便地將自己的作業(yè)通過終端設(shè)

備傳輸?shù)接?jì)算機(jī)上處理。

分時(shí)系統(tǒng)的定義：是指一臺(tái)主機(jī)上連接了多個(gè)帶有顯示器和鍵盤的終端，同時(shí)

允許多個(gè)用戶共享主機(jī)的資源，每個(gè)用戶都可以通過自己的終端以交互的方式使用

計(jì)算機(jī)。

分時(shí)系統(tǒng)需要解決的問題：

a.及時(shí)接收：指的是主機(jī)要及時(shí)接收用戶輸入的命令和數(shù)據(jù)

b.及時(shí)處理：指用戶通過終端鍵入命令后能及時(shí)控制自己的作業(yè)運(yùn)行或修改

自己的作業(yè)。在分時(shí)系統(tǒng)中，所有用戶的作業(yè)都直接進(jìn)入內(nèi)存，且在較短

短時(shí)間內(nèi)（例如3秒之內(nèi)）保證每個(gè)作業(yè)都運(yùn)行一次（一個(gè)時(shí)間片I

說明：

時(shí)間片：指的是一段很短的時(shí)間，例如0.1秒，用于進(jìn)程調(diào)度時(shí)的時(shí)間段表示。

分時(shí)系統(tǒng)的實(shí)現(xiàn)方法：

a.單道分時(shí)系統(tǒng)：系統(tǒng)內(nèi)存中只駐留一道程序（作業(yè)），其余作業(yè)都在外存上。

當(dāng)內(nèi)存中的一個(gè)作業(yè)運(yùn)行一個(gè)時(shí)間片后，便被調(diào)至致外存（稱為調(diào)出），再

從外存上選一個(gè)作業(yè)裝入內(nèi)存（稱為調(diào)入）并運(yùn)行一個(gè)時(shí)間片，如此往返。

特點(diǎn)：每個(gè)用戶的作業(yè)都可以輪流調(diào)入內(nèi)存接受CPU的服務(wù)，但是由于每

道作業(yè)都是頻繁的調(diào)入調(diào)出多次，開銷大，CPU空閑較多，系統(tǒng)性能較差。

b.具有"前臺(tái)"和"后臺(tái)"的分時(shí)系統(tǒng)：為充分利用CPU,將內(nèi)存分為前臺(tái)

區(qū)和后臺(tái)區(qū)，前臺(tái)區(qū)存放按時(shí)間片"調(diào)入"和"調(diào)出"的作業(yè)流，后臺(tái)區(qū)

存放批處理作業(yè)。只有前臺(tái)在調(diào)入/調(diào)出過程中，或者前臺(tái)已經(jīng)無作業(yè)可運(yùn)

行時(shí)，方才可運(yùn)行后臺(tái)區(qū)的作業(yè)。該類型分時(shí)系統(tǒng)能在一定程度提高了系

統(tǒng)的性能。

c.多道分時(shí)系統(tǒng)：內(nèi)存中可同時(shí)存放多道作業(yè)（程序），每道程序在內(nèi)存中沒

有固定的位置。系統(tǒng)將具備運(yùn)行條件的作業(yè)排成一個(gè)隊(duì)列，這些作業(yè)可以

輪流獲得時(shí)間片來運(yùn)行。該類系統(tǒng)的特點(diǎn)是：切換作業(yè)是在內(nèi)存中進(jìn)行，

不要花費(fèi)調(diào)入、調(diào)出開銷，具有較好的性能。現(xiàn)代的分時(shí)系統(tǒng)多屬于多道

分時(shí)系統(tǒng)。

分時(shí)系統(tǒng)的特點(diǎn)：

⑴多路性：一臺(tái)主機(jī)上連接多臺(tái)終端，系統(tǒng)按照分時(shí)原則輪流為每個(gè)用戶

服務(wù)。多路性也稱為同時(shí)性。

（2）獨(dú)立性：是從用戶的角度考慮的，每個(gè)用戶獨(dú)占一個(gè)終端，各自獨(dú)立操

作，互補(bǔ)干擾，因此，用戶感到是他一個(gè)人占用主機(jī)。

(3)及時(shí)性：用戶的請求能在很短短時(shí)間內(nèi)獲得響應(yīng)。人所能接受的等待時(shí)

間是2~3秒，因此，分時(shí)系統(tǒng)中讓用戶等待的時(shí)間也限定在該范圍內(nèi)。

(4)交互性：用戶通過終端可以同主機(jī)進(jìn)行廣泛的對話，以實(shí)現(xiàn)人機(jī)交互。

.4)實(shí)時(shí)系統(tǒng)(Real-TimeSystem):多道批處理系統(tǒng)和分時(shí)系統(tǒng)雖然已經(jīng)獲得了較

好的資源利用率和響應(yīng)時(shí)間，但是無法解決"實(shí)時(shí)控制"和"實(shí)時(shí)信息處理"

兩個(gè)領(lǐng)域的應(yīng)用。

計(jì)算機(jī)作為控制系統(tǒng)的中心設(shè)備，用于生產(chǎn)過程的控制，能保證實(shí)時(shí)采集

現(xiàn)場數(shù)據(jù)，并對數(shù)據(jù)進(jìn)行及時(shí)處理和自動(dòng)控制，例如高爐溫度控制、武器控制、

自動(dòng)駕駛系統(tǒng)等。"實(shí)時(shí)"是"及時(shí)"或"即時(shí)"的意思，而"實(shí)時(shí)系統(tǒng)”是

指能及時(shí)響應(yīng)外部時(shí)間的請求，在規(guī)定的時(shí)間內(nèi)完成對該時(shí)間的處理，并控制

所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。

實(shí)時(shí)任務(wù)：控制系統(tǒng)中要求在規(guī)定時(shí)間內(nèi)完成的任務(wù)稱為實(shí)時(shí)任務(wù)，它們都帶

有某種程度的緊迫性。分類如下：

(1)按照是否呈現(xiàn)周期性劃分

?周期性實(shí)時(shí)任務(wù)：任務(wù)按照制定的周期循環(huán)執(zhí)行；

?非周期性實(shí)時(shí)任務(wù)：任務(wù)的執(zhí)行無明顯得周期性，但是都同一個(gè)截

止時(shí)間相聯(lián)系。截止時(shí)間(deadline)分為開始截止時(shí)間和完成截止

時(shí)間。所謂開始截止時(shí)間，是指任務(wù)在某時(shí)間之前，必須開始執(zhí)行；

所謂完成截止時(shí)間，是指某任務(wù)必須在某時(shí)間之前完成。

(2)按照對截止時(shí)間的要求嚴(yán)格程度劃分

?硬實(shí)時(shí)任務(wù)：系統(tǒng)必須滿足對截止時(shí)間的要求，否則可能出現(xiàn)難以

預(yù)料的后果；

?軟實(shí)時(shí)任務(wù)：系統(tǒng)也有也一個(gè)截止時(shí)間，但是對截止時(shí)間的要求不

嚴(yán)格。若錯(cuò)過了截止時(shí)間，對系統(tǒng)產(chǎn)生的影響也不會(huì)很大。

說明：實(shí)時(shí)系統(tǒng)和分時(shí)系統(tǒng)的比較

(1)多路性：都具有多路性。分時(shí)系統(tǒng)的多路性指的是系統(tǒng)按照分時(shí)原則為

多個(gè)用戶服務(wù)，實(shí)時(shí)系統(tǒng)的多路性是指系統(tǒng)經(jīng)常對現(xiàn)場的多路信息進(jìn)行

采集及對多個(gè)對象進(jìn)行控制。

(2)獨(dú)立性：都具有獨(dú)立性。分時(shí)系統(tǒng)的獨(dú)立性體現(xiàn)在每個(gè)終端用戶向系統(tǒng)

提出服務(wù)時(shí)是獨(dú)立的操作，彼此不相干，實(shí)時(shí)系統(tǒng)的獨(dú)立性體現(xiàn)在系統(tǒng)

對多路信息采集和控制時(shí)，也是彼此獨(dú)立的。

(3)及時(shí)性：實(shí)時(shí)信息系統(tǒng)的實(shí)時(shí)性通分時(shí)系統(tǒng)類似，都是以人所能接受的

時(shí)間來確定，而實(shí)時(shí)控制系統(tǒng)是以控制對象所要求的開始截止時(shí)間和完

成截止時(shí)間來確定的，時(shí)間要求比較嚴(yán)格。

（4）交互性：實(shí)時(shí)信息系統(tǒng)中的交互是為了訪問系統(tǒng)內(nèi)的特定資源，分時(shí)系

統(tǒng)中是系統(tǒng)向終端用戶提供各種數(shù)據(jù)處理服務(wù)、資源貢獻(xiàn)服務(wù)等。

（5）可靠性：分時(shí)系統(tǒng)要求系統(tǒng)較為可靠，但實(shí)時(shí)系統(tǒng)要求系統(tǒng)嚴(yán)格可靠。

三'操作系統(tǒng)定義、特征、服務(wù)及功能

1.操作系統(tǒng)的定義：是一組控制和管理計(jì)算機(jī)硬件和軟件資源，合理對各類作業(yè)進(jìn)行調(diào)度，

以及方便用戶的程序的集合。

批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)是三種基本的操作系統(tǒng)類型。一個(gè)實(shí)際的操作系

統(tǒng)，可能兼有三者或者其中兩者的功能。

2.操作系統(tǒng)的四大基本特征

1）并發(fā)性（Concurrence）

并發(fā)：兩個(gè)或多個(gè)事件在同一個(gè)時(shí)間間隔內(nèi)發(fā)生。

并行：兩個(gè)或多個(gè)時(shí)間在統(tǒng)一時(shí)刻發(fā)生。

程序是不能并發(fā)進(jìn)行的，是靜態(tài)實(shí)體；為使得程序能并發(fā)執(zhí)行，系統(tǒng)必須為每個(gè)

程序建立進(jìn)程。進(jìn)程，也稱任務(wù)，是系統(tǒng)中能獨(dú)立運(yùn)行且作為資源分配的基本單位，

是一個(gè)活動(dòng)實(shí)體。進(jìn)程之間可以并發(fā)執(zhí)行和交換信息。

2）共享性（Sharing）：系統(tǒng)中的資源可供內(nèi)存中的多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用。有兩

種共享資源的方式：互斥共享方式和同時(shí)訪問方式。

互斥共享方式：有的資源可以供多個(gè)進(jìn)程使用，但是在一個(gè)特定的時(shí)間段內(nèi)只能由一

個(gè)進(jìn)程占用，這樣的資源稱為臨界資源；其它希望使用該資源的進(jìn)程必須等待當(dāng)

前進(jìn)程釋放該資源。

同時(shí)訪問方式：有的資源（如磁盤）可以允許多個(gè)進(jìn)程同時(shí)訪問。注意這里的“同時(shí)"

是一個(gè)宏觀的概念，在微觀上往往是這些進(jìn)程交替對資源進(jìn)行訪問。

3）虛擬性（Virtual）:通過某種技術(shù)把一個(gè)物理實(shí)體變成若干個(gè)邏輯上的對應(yīng)物。物理

實(shí)體實(shí)實(shí)在存在的，而后者是虛擬的，是用戶感覺到的東西。例如多道分時(shí)系統(tǒng)中中

只有一個(gè)CPU，但是每個(gè)終端用戶都認(rèn)為有一個(gè)CPU在專門為他服務(wù)，此即為利用

多道程序技術(shù)把一臺(tái)物理上的CPU變成多臺(tái)邏輯的CPU。

4）異步性（Asynchronism）：多道環(huán)境中，多個(gè)進(jìn)程并發(fā)執(zhí)行，但是由于資源有限，通常

進(jìn)程的執(zhí)行并非"一氣呵成"，而是以"走走停停”的方式進(jìn)行，即進(jìn)程是以異步方

式進(jìn)行的。

說明：并發(fā)和共享是操作系統(tǒng)的兩個(gè)最基本的特征，且互為依存。

3.操作系統(tǒng)提供的服務(wù)：操作系統(tǒng)提供了其他程序執(zhí)行的環(huán)境，也為程序和用戶提供了一

些操作系統(tǒng)的服務(wù)。操作系統(tǒng)可以提供諸如程序執(zhí)行、I/O操作、文件系統(tǒng)操縱、通信以

及差錯(cuò)檢測等服務(wù)，還可以提供系統(tǒng)調(diào)用（SystemCall）服務(wù)。

4.操作系統(tǒng)的五大功能

1）存儲(chǔ)器管理功能：為多道程序的運(yùn)行提供良好的環(huán)境。這里的“存儲(chǔ)器”指的是內(nèi)存。

主要有以下功能：內(nèi)存分配（靜態(tài)分配、動(dòng)態(tài)分配1內(nèi)存保護(hù)（每道程序在自己的

內(nèi)存范圍內(nèi)，不能越界\地址映射和內(nèi)存擴(kuò)充（借助虛擬存儲(chǔ)技術(shù)）

2）處理機(jī)管理功能：實(shí)際是對進(jìn)程的管理。在多道程序環(huán)境下，對處理機(jī)的管理是以進(jìn)

程為基本單位的，因此處理機(jī)的管理可以歸結(jié)為對進(jìn)程的管理。主要有以下功能：進(jìn)

程控制、進(jìn)程同步、進(jìn)程通信和調(diào)度（作業(yè)調(diào)度和進(jìn)程調(diào)度）等。

3）設(shè)備管理功能：主要任務(wù)是完成用戶提出的各種I/O請求，為用戶分配I/O設(shè)備，提

高CPU和I/。設(shè)備的利用率，提高I/O速度，以及方便用戶使用I/O設(shè)備。主要功能

有：緩沖管理（CPU和I/。設(shè)備之間速度不匹配\設(shè)備分配（包括回收\設(shè)備處理

（設(shè)備驅(qū)動(dòng)\保證設(shè)備的獨(dú)立性和虛擬性。

4）文件管理功能：主要是對用戶文件和系統(tǒng)文件進(jìn)行管理，以方便用戶使用，并保證文

件的安全性。主要功能包括：文件存儲(chǔ)空間的管理、目錄管理、文件的讀寫管理以及

文件的貢獻(xiàn)與保護(hù)等。

5）用戶接口功能：是操作系統(tǒng)為了方便用戶使用而向用戶提供的“用戶與操作系統(tǒng)的接

口"，通常以命令和系統(tǒng)調(diào)用的形式呈現(xiàn)出來，有命令接口、程序接口（系統(tǒng)調(diào)用）

和圖形接口幾種形式。

5.常見操作系統(tǒng)：有以下幾類操作系統(tǒng)

1）微機(jī)操作系統(tǒng)：

（1）單用戶單任務(wù)操作系統(tǒng)：只允許一個(gè)用戶使用計(jì)算機(jī)，且只允許用戶程序作為一

個(gè)任務(wù)運(yùn)行，是一種最簡單的操作系統(tǒng)。例如：CP/M和MS-DOS.

（2）單用戶多任務(wù)操作系統(tǒng)：只允許一個(gè)用戶使用計(jì)算機(jī)，但允許將一個(gè)用戶程序分

為若干個(gè)任務(wù)，使它們并發(fā)執(zhí)行，可有效改善系統(tǒng)的性能。例如OS/2和Windows

系列。

（3）多用戶多任務(wù)操作系統(tǒng)：允許多個(gè)用戶通過各自的終端，使用同一臺(tái)主機(jī)，共享

主機(jī)系統(tǒng)中的各類資源，而每個(gè)用戶程序又可進(jìn)一步分為幾個(gè)任務(wù),使它們并發(fā)

執(zhí)行，從而進(jìn)一步提高了資源利用率和增加系統(tǒng)吞吐量。例如UNIXOS.

2）多處理機(jī)操作系統(tǒng)MPS（MultiProcessorSystem）：多臺(tái)處理機(jī)協(xié)調(diào)工作，可增加系統(tǒng)

吞吐量、節(jié)省開支、提高系統(tǒng)的可靠性。

3）網(wǎng)絡(luò)操作系統(tǒng)：主要有兩種模式C/S模式和對等模式（peer-to-peer）

4）分布式操作系統(tǒng)：通集中式操作系統(tǒng)不同?處理和控制都集中在一臺(tái)主機(jī)上，所有的

任務(wù)都由主機(jī)來處理，這樣的系統(tǒng)稱為集中式操作系統(tǒng)。而分布式操作系統(tǒng)的處理和控

制，都是分散在系統(tǒng)的各個(gè)處理單元上。

第二部分：進(jìn)程原理(2~4)

程序是不能獨(dú)立運(yùn)行的，而只有將程序調(diào)入進(jìn)程，由系統(tǒng)為程序創(chuàng)建一個(gè)或多個(gè)進(jìn)程，

程序才可以運(yùn)行。因此，進(jìn)程才是資源分配和獨(dú)立運(yùn)行的基本單位。

進(jìn)程是操作系統(tǒng)中極為重要的概念，要深刻理解。

一、程序執(zhí)行

i.程序執(zhí)行

程序順序執(zhí)行的特征：1)順序性(保證前驅(qū)、后繼關(guān)系)；2)封閉性(程序不間斷

執(zhí)行,占有本機(jī)所有資源，資源狀態(tài)只有本程序可改變，執(zhí)行結(jié)果不受外界影響)；3)可

再現(xiàn)性(只要條件相同，不管何時(shí)、何地執(zhí)行，結(jié)果均相同)。

程序并發(fā)執(zhí)行，其特征是為了提高系統(tǒng)運(yùn)行效率，特征為：

1)間斷性(并發(fā)程序之間相互制約，例如互為輸入、輸出，程序具有"執(zhí)行一暫停

執(zhí)行一再次執(zhí)行"的活動(dòng)規(guī)律)；

2)失去封閉性(系統(tǒng)資源由多個(gè)程序共享，其狀態(tài)也受多個(gè)程序控制；某程序運(yùn)行

時(shí)，受到其他程序的影響)；

3)不可再現(xiàn)性(失去了封閉性，也將導(dǎo)致失去可再現(xiàn)性)

說明：當(dāng)多個(gè)程序共享一個(gè)資源時(shí)，由于對資源的訪問時(shí)刻不定，因此執(zhí)行結(jié)果不定。例

如：

假設(shè)有一軟件變量資源N,設(shè)當(dāng)前N=5,現(xiàn)有兩個(gè)程序A和B共享該變量，程序A

對N的操作為：N:=N+1;程序B對N的操作為：先^用Print(N)打印N,然后執(zhí)行N:

=0；由于A和B可以按照不同的速度執(zhí)行，則語句N:=N+l;Print(N);N:=0;有可能出

現(xiàn)以下幾種執(zhí)行順序：

(1)N:=N+1;Print(N);N=0;N的取值分別是6,6,0

(2)Print(N);N:=N+1;N=0;N的取值分別是5,6,0

(3)Print(N);N=0;N:=N+1;N的取值分別是5,0,1

以上結(jié)果說明，程序A中變量N的值可能是6,也可能是1,結(jié)果是可變的；同樣情況，

程序B中打印N時(shí)其值有可能是6,也可能是5,結(jié)果也是可變的。

程序并發(fā)執(zhí)行，雖然能顯著提高系統(tǒng)效率，但是出現(xiàn)了"不可再現(xiàn)性"，這顯然是不允

許的。既要保證系統(tǒng)的效率，又要保證程序執(zhí)行的"可再現(xiàn)性"，必須采取適當(dāng)?shù)拇胧?。這

些措施的根本就是要保證并發(fā)執(zhí)行的程序?qū)εR界資源的獨(dú)占性訪問。

2.程序并發(fā)執(zhí)行的條件—Bernstein條件

設(shè)程序Pi可對多個(gè)變量進(jìn)行操作(資源)，操作分為“讀操作"和"寫操作"，亦即程

序Pi在執(zhí)行過程中作為參考的所有變量的集合稱為“讀集"，在執(zhí)行過程中需要修改的所有

變量的集合稱為“寫集"，如下定義：

R(Pi)={al,a2,...,am}；R(Pi)是Pi的讀集

W(Pi)={bl,b2,...,bn}；W(Pi)是Pi的寫集

若兩個(gè)程序Pi和Pi能滿足如下條件，它們便能夠并發(fā)執(zhí)行，并具有可再現(xiàn)性：

R(Pi)nW(Pj)UW(Pi)nR(Pj)|JW(Pi)nW(Pj)={}

以上條件是由Bernstein提出的，因此稱為Bernstein條件。

理解：只有保證程序Pi的讀集和Pj的寫集不相交、Pi的寫集和Pj的讀集不相交、Pi的

寫集和Pj的寫集不相交，才能保證Pi和Pj并發(fā)執(zhí)行，且保證程序的正確執(zhí)行(可再現(xiàn)性)o

說明：兩個(gè)程序可以同時(shí)對某變量執(zhí)行"讀操作"，但只要有一個(gè)“寫操作"，則另一個(gè)

程序就不能再執(zhí)行"讀操作"，也不能再執(zhí)行"寫操作"了，即"寫操作"是獨(dú)占臨界資源

的。

二、進(jìn)程基本概念

1.進(jìn)程：是可執(zhí)行程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程，是系統(tǒng)資源分配和獨(dú)立運(yùn)行的基本

單位。其基本特征為：

1)動(dòng)態(tài)性：進(jìn)程是進(jìn)程實(shí)體的執(zhí)行過程，它"由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行、因得不到

資源而暫停執(zhí)行，以及由撤消而消亡"。動(dòng)態(tài)性是進(jìn)程最基本的特征，是同程序不同

的。

【程序：是一組指令的集合，存放在某種介質(zhì)上，無運(yùn)動(dòng)含義，是一個(gè)靜態(tài)實(shí)體】

2)并發(fā)性：是多個(gè)進(jìn)程實(shí)體同時(shí)運(yùn)行表現(xiàn)出來的特征。并發(fā)性說明的是"同一段時(shí)間”，

同并行性不同。

3)獨(dú)立性：指的是進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行和獲得資源的基本單位。如果某程序沒有

建立進(jìn)程，則不能作為一個(gè)獨(dú)立的單位參與運(yùn)行。

4)異步性：多個(gè)進(jìn)程各自獨(dú)立運(yùn)行，其運(yùn)行速度是不可預(yù)知的。該特種導(dǎo)致了程序執(zhí)行

的不可再現(xiàn)性，因此操作系統(tǒng)必須采取有效措施保證各程序(進(jìn)程)之間能協(xié)調(diào)運(yùn)行。

5)結(jié)構(gòu)特征：進(jìn)程實(shí)體是由程序段、數(shù)據(jù)段以及進(jìn)程控制塊(PCB)三部分組成的。

2.進(jìn)程基本狀態(tài)

有五個(gè)基本狀態(tài)：

1)新狀態(tài)(New)：進(jìn)程剛剛建立，還未送入就緒隊(duì)列的狀態(tài)。

2）就緒狀態(tài)（Ready）:進(jìn)程獲得了除處理機(jī)（CPU）之外的所有資源，一旦獲得了處理

機(jī)，便可立即執(zhí)行。一個(gè)系統(tǒng)中可有多個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)，這些進(jìn)程可排成一

個(gè)或多個(gè)隊(duì)列，這樣的隊(duì)列稱為就緒隊(duì)列。

3）執(zhí)行狀態(tài)（Execute）:進(jìn)程已經(jīng)獲得處理機(jī)，其對應(yīng)的程序正在執(zhí)行。單處理機(jī)系統(tǒng)

中，系統(tǒng)中只有一個(gè)進(jìn)程處于執(zhí)行狀態(tài)，而在多處理機(jī)系統(tǒng)中，可能有多個(gè)進(jìn)程同時(shí)

處于執(zhí)行狀態(tài)。

4）阻塞狀態(tài)（Block）:某進(jìn)程正在執(zhí)行重，但是因?yàn)槟承┰颍ɡ绲却齀/O）暫時(shí)停止

了執(zhí)行，此時(shí)進(jìn)程轉(zhuǎn)入阻塞狀態(tài)，處理機(jī)被剝奪。注意阻塞狀態(tài)一定是由執(zhí)行狀態(tài)轉(zhuǎn)

過來的。阻塞狀態(tài)也稱為"睡眠"狀態(tài)或"等待"狀態(tài)。同就緒隊(duì)列近似，系統(tǒng)中處

于阻塞狀態(tài)的進(jìn)程也排成一個(gè)隊(duì)列，或者根據(jù)阻塞原因排成多個(gè)隊(duì)列，這些隊(duì)列稱為

阻塞隊(duì)列。

處于阻塞狀態(tài)的隊(duì)列，只有其I/O完成，或者需要的資源得到了，則從阻塞隊(duì)列

重轉(zhuǎn)出，排到就緒隊(duì)列的尾部，等待接收系統(tǒng)的重新調(diào)度。

5）終止?fàn)顟B(tài)（Terminated）：進(jìn)程結(jié)束（不管正常結(jié)束，還是異常結(jié)束），操作系統(tǒng)將它

從就緒隊(duì)列中移出，但是還沒有撤銷時(shí)的狀態(tài)。

說明：如果當(dāng)前進(jìn)程正在執(zhí)行，則它仍處于就緒隊(duì)列中，僅是其PCB中有關(guān)進(jìn)程狀態(tài)的

字段要修改為“正在執(zhí)行"狀態(tài)。之所以如此，是因?yàn)樵谶M(jìn)程并發(fā)時(shí)，進(jìn)程不可能總

占有處理機(jī)，操作系統(tǒng)會(huì)根據(jù)各種不同策略為進(jìn)程分配處理機(jī)，所以進(jìn)程的執(zhí)行過程

是"走走停停"式的，是在“就緒--執(zhí)行-----就緒"的狀態(tài)中來回切換的。

3.進(jìn)程五大基本狀態(tài)的切換

一個(gè)進(jìn)程只有一次新狀態(tài)和終止?fàn)顟B(tài)，但可有多次就緒狀態(tài)、阻塞狀態(tài)和執(zhí)行狀態(tài)。

有以下幾種狀態(tài)轉(zhuǎn)換的情況。

1）新狀態(tài)今就緒狀態(tài)：系統(tǒng)的就緒隊(duì)列允許接收新的就緒隊(duì)列時(shí)，操作系統(tǒng)就將

處于新狀態(tài)的進(jìn)程移入就緒隊(duì)列，此時(shí)完成了進(jìn)程的“新狀態(tài)"到"就緒狀態(tài)"

的轉(zhuǎn)變。

2）就緒狀態(tài)少執(zhí)行狀態(tài)：進(jìn)程調(diào)度程序?yàn)榫途w隊(duì)列中優(yōu)先（如何判斷優(yōu)先？）的

進(jìn)程分配處理機(jī)，則該進(jìn)程由就緒狀態(tài)變成了執(zhí)行狀態(tài)，該進(jìn)程稱為當(dāng)前進(jìn)程。

3）執(zhí)行狀態(tài)-阻塞狀態(tài)：當(dāng)正處于執(zhí)行狀態(tài)的進(jìn)程需要訪問臨界資源，而臨界資

源正在被其它資源訪問時(shí)，或者進(jìn)程需要等待I/O時(shí)，進(jìn)程將由執(zhí)行狀態(tài)變?yōu)?/p>

阻塞狀態(tài)，進(jìn)程也將進(jìn)入阻塞隊(duì)列。

4）執(zhí)行狀態(tài)9就緒狀態(tài):當(dāng)前進(jìn)程時(shí)間片用完，或者有更高優(yōu)先級(jí)的進(jìn)程出現(xiàn)時(shí),

當(dāng)前進(jìn)程的處理機(jī)被剝奪，執(zhí)行狀態(tài)就變?yōu)榫途w狀態(tài)。注意:僅處理機(jī)被剝奪，

而其他所有資源還占據(jù)的狀態(tài)是就緒狀態(tài)，如果資源不完備，或者進(jìn)程需要

I/O,則進(jìn)入阻塞狀態(tài)。

5）阻塞狀態(tài)玲就緒狀態(tài)：阻塞進(jìn)程獲得了所需的全部資源（除了處理機(jī)），并且I/。

也已經(jīng)完成，則可由阻塞狀態(tài)轉(zhuǎn)為就緒狀態(tài)，等待進(jìn)程處理程序的調(diào)度而重新

獲得處理機(jī)。

6）執(zhí)行狀態(tài)玲終止?fàn)顟B(tài)：進(jìn)程完成，不管是正常完成，還是異常結(jié)束，都》鼬行

狀態(tài)變?yōu)榻K止?fàn)顟B(tài)，等待系統(tǒng)撤消。

4.進(jìn)程的掛起狀態(tài)（Suspend）

是一種新引入的狀態(tài)，是一種靜止?fàn)顟B(tài)。處于此狀態(tài)的進(jìn)程，得不到處理機(jī)調(diào)度。

處于掛起狀態(tài)的進(jìn)程被調(diào)出內(nèi)存，進(jìn)入外存暫時(shí)存放。其原因可能基于：

1）終端用戶的需要；2）父進(jìn)程的要求；3）操作系統(tǒng)的需要；4）對換的需要；5）負(fù)

荷調(diào)節(jié)的需要。

【所謂對換，指的是為了緩和內(nèi)存緊張的情況，將內(nèi)存中處于阻塞狀態(tài)的進(jìn)程換至

外存上，此時(shí)進(jìn)程將處于一種有別于阻塞狀態(tài)的另一種狀態(tài)，稱為靜止阻塞狀態(tài)。該狀態(tài)

的進(jìn)程即處于掛起狀態(tài)，確切地說，該進(jìn)程處于靜止阻塞狀態(tài)，因?yàn)榧词乖撨M(jìn)程獲得了所

有資源，或者其預(yù)想的事情（例如IA））已經(jīng)發(fā)生能夠，其仍不具備運(yùn)行條件，仍不能進(jìn)

入就緒隊(duì)列】

引入掛起狀態(tài)的進(jìn)程，又增加了從掛起狀態(tài)（靜止?fàn)顟B(tài)）到非掛起狀態(tài)（活動(dòng)狀態(tài)）

的轉(zhuǎn)換，或者相反。為同原有的就緒、阻塞狀態(tài)相區(qū)別，原有的非掛起狀態(tài)下的就緒、阻

塞狀態(tài)分別稱為活動(dòng)就緒狀態(tài)、活動(dòng)阻塞狀態(tài)，而掛起狀態(tài)下的就緒、阻塞狀態(tài)稱為靜止

就緒狀態(tài)、靜止阻塞狀態(tài)。狀態(tài)轉(zhuǎn)換圖如下所示。

(1)活動(dòng)就緒玲靜止就緒(ReadyAfReadyS)：

(2)靜止就緒少活動(dòng)就緒(ReadySTReadyA)：如果利用激活原語Active將進(jìn)程激活

后，靜止就緒狀態(tài)的進(jìn)程變?yōu)榛顒?dòng)就緒狀態(tài)，此時(shí)進(jìn)程可以再調(diào)度執(zhí)行。

(3)活動(dòng)阻塞-靜止阻塞(BlockA玲Blocks)：利用掛起原語Suspend將進(jìn)程掛起時(shí),

活動(dòng)阻塞狀態(tài)的進(jìn)程變?yōu)殪o止阻塞狀態(tài)。即使該進(jìn)程所期待的事件發(fā)生了(例如I/O完成),

也不能進(jìn)入活動(dòng)就緒隊(duì)列，而只能進(jìn)入靜止就緒隊(duì)列。

(4清爭止阻塞玲活動(dòng)阻塞(Blocks〉BlockA)如果利用激活原語Active將進(jìn)程激活后,

靜止阻塞狀態(tài)的進(jìn)程變?yōu)榛顒?dòng)阻塞狀態(tài)。

5.進(jìn)程控制塊PCB

進(jìn)程控制塊是進(jìn)程實(shí)體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)，PCB中記錄

了操作系統(tǒng)所需要的，用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需的全部信息。

PCB的特征：1)常駐內(nèi)存；2)是進(jìn)程存在的唯一標(biāo)識(shí)；3)一個(gè)進(jìn)程對應(yīng)一個(gè)PCB；4)可

以被多個(gè)系統(tǒng)模塊訪問；5)OS中有專門的PCB區(qū)。

PCB中包含的信息：

(1)進(jìn)程標(biāo)識(shí)符信息：例如外部標(biāo)識(shí)符(字母，用戶訪問進(jìn)程時(shí)使用I內(nèi)部標(biāo)識(shí)符(整

數(shù)，系統(tǒng)使用X父進(jìn)程標(biāo)識(shí)符、子進(jìn)程標(biāo)識(shí)符以及用戶標(biāo)識(shí)符(誰擁有該進(jìn)程)

等。

(2)處理機(jī)狀態(tài)信息：現(xiàn)場保護(hù)、現(xiàn)場恢復(fù)，例如通用寄存器、PC、PSW、SP等的信

息。

(3)進(jìn)程調(diào)度信息：進(jìn)程當(dāng)前狀態(tài)、優(yōu)先級(jí)、進(jìn)程調(diào)度所需的信息以及阻塞原因(事

件)等。

(4)進(jìn)程控制信息：例如程序和數(shù)據(jù)的地址、進(jìn)程同步和通信機(jī)制、資源清單以及鏈

接指針等。

PCB的組織方式：

(1)鏈接方式：把具有相同狀態(tài)的PCB用其中的鏈接字，鏈接成一個(gè)隊(duì)列。

(2)索引方式：系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)，建立幾張索引表，索引表的每一個(gè)表項(xiàng)指

向一個(gè)PCB的物理塊。

三、進(jìn)程控制

1,處理機(jī)的執(zhí)行狀態(tài)：系統(tǒng)態(tài)和用戶態(tài)。

1)系統(tǒng)態(tài)又稱為核心態(tài)，具有較高的特權(quán)，能訪問所有寄存器和存儲(chǔ)區(qū)，能執(zhí)行一切

執(zhí)令。

2)用戶態(tài)具有較低特權(quán)的執(zhí)行狀態(tài)，只能執(zhí)行規(guī)定的指令，訪問指定的寄存器和存儲(chǔ)

區(qū)。

通常情況下，用戶程序運(yùn)行在用戶態(tài)，OS內(nèi)核通常運(yùn)行在系統(tǒng)態(tài)。進(jìn)程控制就是由OS

內(nèi)核實(shí)現(xiàn)的。

2.操作系統(tǒng)內(nèi)核

操作系統(tǒng)內(nèi)核是計(jì)算機(jī)硬件的第一次擴(kuò)充，內(nèi)核執(zhí)行OS與硬件關(guān)系密切，執(zhí)行頻率高

的模塊，它們是常駐內(nèi)存的。多數(shù)OS包括下述功能：

1）支撐功能：包括中斷處理功能、時(shí)鐘管理功能、原語操作等。

2）資源管理功能：包括進(jìn)程管理、存儲(chǔ)器管理、設(shè)備管理等。

中斷：計(jì)算機(jī)在執(zhí)行程序的過程中，當(dāng)出現(xiàn)異常情況或特殊請求時(shí)，計(jì)算機(jī)停止現(xiàn)行程

序的運(yùn)行轉(zhuǎn)向?qū)@些異常情況或特殊請求的處理處理結(jié)束后再返回到現(xiàn)行程序的間斷處。

這就是“中斷"。

3.進(jìn)程的創(chuàng)建及終止

1）進(jìn)程圖：是用于描述進(jìn)程家族關(guān)系的有向樹，表現(xiàn)進(jìn)程之間的父子關(guān)系。父進(jìn)程和子

進(jìn)程關(guān)系為：（1）父進(jìn)程創(chuàng)建子進(jìn)程；（2）子進(jìn)程繼承父進(jìn)程的資源，文件以及緩沖區(qū)；（3）

子進(jìn)程隨父進(jìn)程的撤消而撤消；（4）子進(jìn)程撤消時(shí)，其從父進(jìn)程獲得的資源全部歸還父進(jìn)程。

2）什么時(shí)候創(chuàng)建進(jìn)程？（引起創(chuàng)建進(jìn)程的事件）

（1）用戶登錄；（2）作業(yè)調(diào)度；（3）提供服務(wù)；（4）應(yīng)用請求。

3）什么時(shí)候終止進(jìn)程？（引起終止進(jìn)程的事件）

（1）正常結(jié)束；（2）異常結(jié)束（出現(xiàn)錯(cuò)誤或故障）；（3）外界干預(yù)（例如操作系統(tǒng)干預(yù)、

父進(jìn)程干預(yù)、父進(jìn)程終止等工

4）進(jìn)程創(chuàng)建步驟：

（1）申請空白PCB（為進(jìn)程分配唯一數(shù)字標(biāo)識(shí)符，從PCB集合中索取空白PCB塊）;（2）

為新進(jìn)程分配資源（為進(jìn)程的程序和數(shù)據(jù)，以及用戶棧分配內(nèi)存資源）；（3）初始化進(jìn)

程控制塊（包括初始化標(biāo)識(shí)符信息、處理機(jī)狀態(tài)信息以及處理機(jī)控制信息）；（4）將新

進(jìn)程插入就緒隊(duì)列（如就緒隊(duì)列能夠接納新進(jìn)程，則插入1

5）進(jìn)程的終止步驟：

OS調(diào)用進(jìn)程終止原語，按下述過程終止指定進(jìn)程：

(1)從PCB集合中檢索當(dāng)前進(jìn)程PCB,并從中讀出進(jìn)程狀態(tài)；(2)終止進(jìn)程的執(zhí)行(修

改其調(diào)度標(biāo)志為真，以保證終止后應(yīng)重新調(diào)度)；(3)終止子孫進(jìn)程；(4)釋放資源(或

歸還給其父進(jìn)程，或歸還給系統(tǒng))；(5)將被終止進(jìn)程的PCB從它所處的隊(duì)列中移出。

4.進(jìn)程阻塞及喚醒

1)引起進(jìn)程阻塞和喚醒的事件

(1)請求系統(tǒng)服務(wù)，如：打印服務(wù)；

(2)啟動(dòng)某種操作，如：啟動(dòng)I/O或啟動(dòng)打印機(jī)；

(3)新數(shù)據(jù)尚未到達(dá)；

(4)無新工作可做，發(fā)送一消息之后等待的時(shí)候。

2)進(jìn)程阻塞過程

(1)終止進(jìn)程的執(zhí)行，將進(jìn)程的狀態(tài)改為阻塞態(tài)；

(2)將進(jìn)程插入相應(yīng)的阻塞隊(duì)列；

(3)轉(zhuǎn)進(jìn)程調(diào)度例程，重新進(jìn)行進(jìn)程調(diào)度，以將CPU分配給其它進(jìn)程。

3)進(jìn)程喚醒過程

(1)將進(jìn)程從阻塞隊(duì)列中移出；

(2)將進(jìn)程狀態(tài)由阻塞改為就緒；

(3)將進(jìn)程插入就緒隊(duì)列。(有可能立即得到調(diào)度，也有可能在就緒隊(duì)列中等待)

【說明：進(jìn)程阻塞用Block原語，進(jìn)程激活用Active原語。需要說明，這是兩個(gè)作用相反的

原語J

5.進(jìn)程掛起與激活

1)進(jìn)程的掛起過程：調(diào)用掛起原語suspend))osuspend的執(zhí)行過程：(1)檢查被掛起的

進(jìn)程的狀態(tài)，如正處于活動(dòng)就緒狀態(tài)或執(zhí)行狀態(tài)，則將其修改為靜止就緒狀態(tài)；如正處于活

動(dòng)阻塞狀態(tài)，則將其修改為靜止阻塞狀態(tài)；(2)復(fù)制改進(jìn)程的PCB到指定的內(nèi)存區(qū)域，以

方便用戶或父進(jìn)程檢查其運(yùn)行情況；(3)如果被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)調(diào)度程序重新調(diào)

度新的進(jìn)程。

2）進(jìn)程的激活過程：調(diào)用激活原語Active（1執(zhí)行過程：（1）將進(jìn)程后外存換入內(nèi)存；

（2）檢查現(xiàn)行狀態(tài)，若是靜止就緒（阻塞）狀態(tài)，則修改為活動(dòng)就緒（阻塞）狀態(tài)；（3）

如采用搶占調(diào)度策略，且有新進(jìn)程進(jìn)入就緒隊(duì)列，則還可能轉(zhuǎn)入進(jìn)程調(diào)度程序：如當(dāng)前進(jìn)程

優(yōu)先級(jí)較低，則立即剝奪其執(zhí)行，將處理機(jī)分配給剛被激活的進(jìn)程，否則就不必重新調(diào)度,

繼續(xù)原先進(jìn)程的執(zhí)行即可。

四、線程

1.線程的引入（減少時(shí)空開銷，提高系統(tǒng)的并發(fā)性）

上個(gè)世紀(jì)60年代，進(jìn)程的概念被提出，在OS中進(jìn)程一直作為資源分配合獨(dú)立運(yùn)行的

基本單位。直到80年代中期，人們又提出了比進(jìn)程更小的能獨(dú)立運(yùn)行的基本單位一線程。

提出線程的目的是為了進(jìn)一步提高系統(tǒng)內(nèi)程序并發(fā)執(zhí)行的程度，進(jìn)一步提高系統(tǒng)吞吐

量。目前新近推出的OS和DBMS中都引入了線程的概念。

引入線程的目的：為了減少程序并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，保證OS具有更好的并

發(fā)性。為保證程序能并發(fā)運(yùn)行，系統(tǒng)必須進(jìn)行以下操作：創(chuàng)建進(jìn)程、撤消進(jìn)程和進(jìn)程切換，

而這一切，系統(tǒng)都必須付出較大的時(shí)空開銷。

多個(gè)進(jìn)程進(jìn)入內(nèi)存，可保證良好的并發(fā)性，但是進(jìn)程越多，切換的頻率越大，系統(tǒng)為之

付出的時(shí)空開銷就越大，實(shí)際上系統(tǒng)的性能將有所降低。如果既要保證并發(fā)性，又要減少系

統(tǒng)時(shí)空開銷，則必須采取新的措施。由此，線程被提出了。

線程：線程是進(jìn)程的一個(gè)實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位。線程有進(jìn)程生成，

本身基本上不擁有資源，僅有一點(diǎn)自己的運(yùn)行過程中必不可少的資源（例如程序計(jì)數(shù)器、堆

棧等），但是它可以利用創(chuàng)建它的進(jìn)程的所有資源。一個(gè)進(jìn)程可以創(chuàng)建多個(gè)線程，線程也可

以創(chuàng)建或撤消另一個(gè)線程，這些線程共享進(jìn)程的資源。同一個(gè)進(jìn)程的線程之間可以并發(fā)執(zhí)行,

線程之間相互制約，也呈現(xiàn)間斷性（異步性），因此，線程也同樣擁有就緒、阻塞和執(zhí)行三

種基本狀態(tài)，有的系統(tǒng)中還有終止?fàn)顟B(tài)。

2.線程和進(jìn)程的比較

線程：輕型進(jìn)程（Light-WeightProcess）,也稱為進(jìn)程元；

進(jìn)程：重型進(jìn)程（Heavy-WeightProcess）

一個(gè)進(jìn)程都有若干個(gè)線程,至少有一個(gè)線程。線程和進(jìn)程有一些相似之處，下面我們從

調(diào)度、并發(fā)性、擁有資源、系統(tǒng)開銷等方面對它們進(jìn)行比較。

調(diào)度：傳統(tǒng)OS中，進(jìn)程是資源分配和獨(dú)立執(zhí)行的基本單位，而在引入線程的OS中，

進(jìn)程僅是資源擁有的基本單位，線程稱為調(diào)度和分派的基本單位。進(jìn)程的兩個(gè)屬性（資源分

配，獨(dú)立執(zhí)行）被分開，從而線程可輕裝上陣，可提高系統(tǒng)并發(fā)程度。

同一進(jìn)程的線程切換不會(huì)引起進(jìn)程的切換，不同進(jìn)程的線程的切換將會(huì)引起進(jìn)程切換。

并發(fā)性：在引入線程的OS中，不僅進(jìn)程之間可以并發(fā)，同一進(jìn)程之間的線程也可以并

發(fā)，從而有效提高了并發(fā)程度。

擁有資源：進(jìn)程是擁有資源的，而線程基本上不擁有資源，但是同一個(gè)進(jìn)程的線程可以

共享進(jìn)程的資源。

系統(tǒng)開銷：進(jìn)程的創(chuàng)建和撤銷，系統(tǒng)都需要為之分配和撤銷資源（如內(nèi)存空間、I/O設(shè)

備等），而系統(tǒng)創(chuàng)建線程實(shí)，沒有資源分配合撤銷的問題，因此系統(tǒng)開銷遠(yuǎn)遠(yuǎn)小于進(jìn)程；同

時(shí)，進(jìn)程切換時(shí)，系統(tǒng)需要保護(hù)舊進(jìn)程的線程、設(shè)置新進(jìn)程的初始環(huán)境,也需要很大的系統(tǒng)

開銷，而線程切換時(shí)，除了保護(hù)幾個(gè)優(yōu)先的寄存器之外，不涉及有關(guān)存儲(chǔ)器管理的有關(guān)方面，

因此系統(tǒng)開銷非常小。另外，由于同一進(jìn)程的線程占有相同的地址空間，線程同步和通訊的

開銷也常小。

線程分為用戶級(jí)線程和內(nèi)核支持線程。

五、進(jìn)程同步

OS系統(tǒng)引入進(jìn)程，提高了系統(tǒng)效率和吞吐量，但是進(jìn)程運(yùn)行的異步性，導(dǎo)致了結(jié)果的

不可再現(xiàn)性和差錯(cuò)，因此必須采取措施保證進(jìn)程執(zhí)行結(jié)果的可再現(xiàn)性和正確性。這就是進(jìn)程

同步提出的原因。

進(jìn)程同步的主要任務(wù)：使并發(fā)執(zhí)行的進(jìn)程之間能有效利用資源和相互合作，從而使程序

的執(zhí)行具有可再現(xiàn)性。

1.多道程序環(huán)境下進(jìn)程之間的關(guān)系

資源共享：進(jìn)程之間彼此無關(guān)，互不知道對方的存在。但是處在一個(gè)環(huán)境之下，運(yùn)行時(shí)

需資源共享（如共享CPU和I/O設(shè)備x進(jìn)程同步的主要任務(wù)是保證進(jìn)程能互斥地訪問臨界

資源。系統(tǒng)中的資源不是由用戶進(jìn)程直接使用的，而是由系統(tǒng)（操作系統(tǒng)）統(tǒng)一分配的。亦

即：用戶進(jìn)程要使用某資源，必須首先咨詢系統(tǒng)：資源被其他進(jìn)程占有嗎？如果占有，則當(dāng)

前進(jìn)程或等待，或進(jìn)入阻塞狀態(tài)；如果資源處于空閑狀態(tài)，則當(dāng)前進(jìn)程占有該資源，繼續(xù)執(zhí)

行，執(zhí)行完畢后，釋放資源，其他進(jìn)程方可再次占有該資源。

相互合作：如果進(jìn)程之間具有某種合作關(guān)系，例如進(jìn)程A的輸出作為進(jìn)程B的輸入。則

進(jìn)程同步的目的是保證進(jìn)程A和進(jìn)程B在執(zhí)行次序上協(xié)調(diào)一致，不會(huì)出現(xiàn)與時(shí)間有關(guān)的差

錯(cuò)。后面介紹到的"生產(chǎn)者-消費(fèi)者”問題就是一個(gè)典型的具有合作關(guān)系的進(jìn)程同步問題。

2.臨界資源和臨界區(qū)

臨界資源：一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源。臨界資源要求"獨(dú)占",即要被"互

斥"地被訪問。

臨界區(qū)：每個(gè)進(jìn)程中訪問臨界資源的代碼。如下:

repeat

entrysection

criticalrrcticn（臨界區(qū)）

exitsection

remaindersection

說明：如果每個(gè)進(jìn)程都能保證互斥地進(jìn)入自己的臨界區(qū)，則能保證互斥訪問臨界資源。

entrysection,進(jìn)入?yún)^(qū)：其作用時(shí)保證進(jìn)程進(jìn)入臨界區(qū)之前先對欲訪問的臨界資源的當(dāng)前

狀態(tài)進(jìn)程檢查，看它是否正在被訪問。如此時(shí)臨界資源未被訪問，則進(jìn)程可以進(jìn)入臨界區(qū)，

對資源進(jìn)行訪問，并設(shè)置臨界資源的訪問標(biāo)志為"占用"狀態(tài)；如果此時(shí)臨界資源處于占用

狀態(tài)，則說明其他進(jìn)程正在訪問它，為避免混亂，本進(jìn)程不能進(jìn)入臨界區(qū)。

exitsection，退出區(qū)：是臨界區(qū)后面的一段代碼，用于恢復(fù)剛才在臨界區(qū)中訪問的臨界

資源的標(biāo)志為“未被占用"狀態(tài)，以便于其他的進(jìn)程可進(jìn)入自己的臨界區(qū)。

remaindersection,乘!］余區(qū)：進(jìn)入?yún)^(qū)、臨界區(qū)、退出區(qū)之外的其它代碼。

3.同步四原則

1）空閑讓進(jìn)：當(dāng)臨界資源空閑時(shí)，允許進(jìn)程訪問，以有效利用臨界資源；

2）忙則等待：當(dāng)臨界資源忙時(shí)，進(jìn)程將不能進(jìn)入臨界區(qū)對臨界資源進(jìn)行訪問，只能等待，

以保證進(jìn)程互斥訪問臨界資源；

3）有限等待：不要"死等"，要保證進(jìn)程能在有限時(shí)間（可以忍受的時(shí)間）內(nèi)進(jìn)入臨界

區(qū)訪問臨界資源；

4）讓權(quán)等待：如果進(jìn)程不能進(jìn)入臨界區(qū)，即當(dāng)前無法訪問臨界資源，則應(yīng)立即釋放處理

機(jī)，讓其他符合運(yùn)行條件的進(jìn)程有機(jī)會(huì)獲得處理機(jī)，以免當(dāng)前進(jìn)程陷入“忙等"狀態(tài)。

4.互斥問題的解決

可以采用軟件方法解決進(jìn)程互斥問題，也可以用硬件方法解決進(jìn)程互斥問題。目前用軟

件方法解決進(jìn)程互斥的方法已經(jīng)很少使用，但是從理解的角度出發(fā)，利用軟件方法解決，還

是有些意義的。

經(jīng)典進(jìn)程同步問題

生產(chǎn)者--消費(fèi)者問題

1.利用記錄型信號(hào)量解決生產(chǎn)者一消費(fèi)者問題

mutex：使諸進(jìn)程互斥地訪問緩沖區(qū)(n個(gè)緩沖區(qū))

empty,full：空.滿緩沖區(qū)數(shù)量。

Varmutex,empty,full:semaphore:=l,n,0;buffer:array[O,l,…,n-1]ofitem;

in,out:integer:=0,0;

begin

parbegin

producer:begin

repeat

Produceaniteminnextp;

wait(empty);

wait(mutex);

buffer(in):=nextp;

in:=(in+l)modn;

signal(mutex);

signal(full);

Untilfalse;

End

consumer:begin

repeat

wait(full);

wait(mutex);

nextc:=buffer(out);

out:=(out+l)modn;

signal(mutex);

signal(empty);

Consumertheiteminnextc;

Untilfalse;

end

parend

end

2.利用AND信號(hào)量解決生產(chǎn)者——消費(fèi)者問題

varmutex,empty,full:semaphore:=l,n,0;

buffer:array[O,…,n-1]ofitem;

inout:integer:=0,0;

begin

parbegin

producer:begin

repeat

produceaniteminnextp;

swaitfempty,mutex);

buffer(in):=nextp;

in:=(in+l)modn;

ssingal(mutex,full);

Untilfalse;

End

Consumer:begin

repeat

swaitffull,mutex);

nextc:=buffer(out);

out:=(out+l)modn;

ssignal(mutex,empty);

consumertheiteminnextc;

untilfalse;

end

parend

end

六、信號(hào)量機(jī)制

1.整型信號(hào)量機(jī)制

wait和Signal操作(PV操作)：

Wait(s)：whiles<0dono-op

s*=s-l.

Signal(s)：s：=s+l

注：wait(s)和Signal(s)都是原子操作。

使用整型信號(hào)量的缺點(diǎn)："忙等"不停檢測，直到本次時(shí)間片用完，并未遵循“讓權(quán)等待"

的準(zhǔn)則。

2.記錄型信號(hào)量機(jī)制

特點(diǎn)：可以實(shí)現(xiàn)讓權(quán)等待。

procedurewait(s)

vars：semaphore

begin

svalue:=s.value-l;

ifs.value<0,thenblock(S.L)

end

procedureSignal(s)

vars:semaphore

begin

svalue:=s.value+l;

ifs.value<=0thenwakeup(S.L)

end

s.value>=0時(shí)，s.value的值表示資源數(shù)量；s.value<0時(shí)，|s.value|的值表示某資源的等待

隊(duì)列中進(jìn)程的數(shù)量。

每次的wait(s)操作，意味著進(jìn)程請求一個(gè)單位的資源，因此描述為s.value：^.value-1;

當(dāng)s.value<0時(shí)，表示資源已分配完畢，因而進(jìn)程調(diào)用block原語，進(jìn)行自我阻塞，放棄處理機(jī),

并插入到信號(hào)鏈表S.L中。

每次的Signals)操作,意味著進(jìn)程釋放一個(gè)資源，故s.value：=s.value+l操作表示資源數(shù)

目加1。若加1后仍是S.value<=0,則表示在該信號(hào)鏈表中，仍有等待該資源的進(jìn)程被阻塞，

故還應(yīng)該調(diào)用wakeup原語，將S.L鏈表中的第一個(gè)等待進(jìn)程喚醒。

如果S.value的初值為1,表示只允許一個(gè)進(jìn)程訪問臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥

信號(hào)量。

3.AND型信號(hào)量機(jī)制

AND型信號(hào)量集機(jī)制的目的在于解決進(jìn)程共享多個(gè)臨界資源的互斥問題。

AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過程中所需要的所有臨界資源，一次性

地全部分配給進(jìn)程，待該進(jìn)程使用完后再一起釋放，只要還有一個(gè)資源不能分配給該進(jìn)程,

其它所有可能為之分配的資源，也不分配給它。

實(shí)現(xiàn)：

SwaitfSi,S2,......Sn)

ifSi>land...andSn>lthen

fori：=1tondo

endfor

else

placetheprocessinthewaitingqueuewiththefirstSifoundwithSi<l,andsetthe

programcountofthisprocesstothebeginningofSwaitoperation

endif

SSignal.(Si,s2,……sn)

fori:=1tondo

Si=Si+1;

removealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue

endfor

4.信號(hào)量集機(jī)制

1）當(dāng)信號(hào)量必須大于一個(gè)給定值（不一定是1）而且每次分配的資源數(shù)為給定值（不一是1

個(gè)單位）的信號(hào)量集機(jī)制。

實(shí)現(xiàn)：

匕,

Swait（Si,di,……Sn,tn,dn）.

ifSi>tiand...andsn^tnthen

fori：=1tondo

Si:=Si-dj

endfor

else

PlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi<tiandsetits

programcountertothebeginningoftheSwaitOperation.

endif

Signal（Sj,d,??????;sn,dn）

fori：=1tondo

Si：=Si+dj

RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue

endfor

2)一般"信號(hào)量集”的幾種特殊情況。

(1)Swait(S,d,d)：允許每次申請d個(gè)資源。

當(dāng)資源數(shù)少于d時(shí)，不予分配。

(2)Swait(S,l,l)：S>1,記錄型信號(hào)量。

S=1時(shí),互斥型信號(hào)量。

(3)Swait(S,l,O),可控開關(guān),當(dāng)時(shí),允許進(jìn)入,S<1時(shí)，不能進(jìn)入。

信號(hào)量的應(yīng)用

1.利用信號(hào)量實(shí)現(xiàn)互斥

varmutex:semaphore:=l

begin

parbegin

processl:begin

repeat

wait(mutex);

criticalsetion

signal(mutex);

remaindersection

untilfalse;

end

process2:begin

repeat

wait(mutex);

criticalsetion

signal(mutex);

remaindersection

untilfalse;

end

parend

2.利用信號(hào)量來描述前趨關(guān)系

Vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;

Begin

parbegin

beginSI;signal(a);signal(b);en