操作系統(tǒng)概論課件

18:51:391操作系統(tǒng)概論18:51:3921.1操作系統(tǒng)的概念1.2操作系統(tǒng)的歷史回顧1.3操作系統(tǒng)的類型1.4操作系統(tǒng)的特征1.5操作系統(tǒng)與用戶的接口1.6操作系統(tǒng)的結(jié)構(gòu)1.7操作系統(tǒng)的硬件環(huán)境第一章引言18:51:3931.1操作系統(tǒng)的概念一、操作系統(tǒng)的地位裸機(jī)（BareMachine）:沒(méi)有任何的軟機(jī)支持的計(jì)算機(jī)。它僅僅構(gòu)成了計(jì)算機(jī)系統(tǒng)的物質(zhì)基礎(chǔ)。一個(gè)完整的計(jì)算機(jī)系統(tǒng)由兩大部分組成：計(jì)算機(jī)硬件和計(jì)算機(jī)軟件。

18:51:394

(一)計(jì)算機(jī)的硬件1.硬件的概念

指計(jì)算機(jī)系統(tǒng)中由電子、機(jī)械和光電元件等組成的各種計(jì)算機(jī)部件和計(jì)算機(jī)設(shè)備。2.計(jì)算機(jī)硬件系統(tǒng)的基本組成①運(yùn)算器②控制器③存儲(chǔ)器中央處理器④輸入設(shè)備⑤輸出設(shè)備18:51:395(二)計(jì)算機(jī)的軟件1.軟件的概念

軟件是由計(jì)算機(jī)硬件執(zhí)行以完成一定任務(wù)的所有程序及其數(shù)據(jù)。2.軟件的分類分為系統(tǒng)軟件和應(yīng)用軟件18:51:396其中,系統(tǒng)軟件由操作系統(tǒng)、程序設(shè)計(jì)語(yǔ)言、語(yǔ)言處理程序、數(shù)據(jù)庫(kù)管理系統(tǒng)、網(wǎng)絡(luò)系統(tǒng)和常用服務(wù)系統(tǒng)等組成。

應(yīng)用軟件是指專門為某一應(yīng)用目的而用系統(tǒng)軟件編制的軟件系統(tǒng)。18:51:397計(jì)算機(jī)系統(tǒng)的層次結(jié)構(gòu)用戶應(yīng)用軟件其他系統(tǒng)軟件裸機(jī)操作系統(tǒng)操作系統(tǒng)系統(tǒng)軟件的核心將文件存到磁盤(pán)上遵命！遵命文件正確保存將文件存盤(pán)報(bào)告長(zhǎng)官：文件保存完成18:51:3910二、操作系統(tǒng)的目標(biāo)：公司的管理部門，要提高經(jīng)濟(jì)效益，至少需要實(shí)現(xiàn)三個(gè)管理目標(biāo)：

(1)為客戶提供種種方便，以爭(zhēng)取接到盡量多的訂單；(2)制定生產(chǎn)計(jì)劃，組織加工流程，提高生產(chǎn)效率，保證產(chǎn)品質(zhì)量；(3)及時(shí)獲取并管理好所需各種資源，充分發(fā)揮資源作用，盡量消除浪費(fèi)資源現(xiàn)象。

舉例18:51:3911操作系統(tǒng)的目標(biāo)是：1.方便性（用戶的觀點(diǎn)）：提供良好的、一致的用戶接口，彌補(bǔ)硬件系統(tǒng)的類型和數(shù)量差別2.有效性（系統(tǒng)管理人員的觀點(diǎn)）：管理和分配硬件、軟件資源，合理地組織計(jì)算機(jī)的工作流程.3.

可擴(kuò)充性隨著VLSI技術(shù)和計(jì)算機(jī)技術(shù)的迅速發(fā)展，計(jì)算機(jī)硬件和體系結(jié)構(gòu)也隨之發(fā)展，對(duì)OS提出了更高的功能和性能要求。4.開(kāi)放性：各種類型的計(jì)算機(jī)硬件系統(tǒng)，出自不同的廠家，要使之通過(guò)網(wǎng)絡(luò)加以集成化并能協(xié)調(diào)工作，實(shí)現(xiàn)應(yīng)用程序的可移植性和互操作性。要求具有同一的開(kāi)放環(huán)境。18:51:3912操作系統(tǒng)的五大管理功能：處理機(jī)管理、存儲(chǔ)器管理、設(shè)備管理、文件管理和作業(yè)管理。打開(kāi)一個(gè)word處理程序，OS需要作什么？系統(tǒng)需要為word處理程序進(jìn)行存儲(chǔ)資源的分配＝》進(jìn)程的管理＝》將結(jié)果輸出到外部設(shè)備系統(tǒng)還需要有極強(qiáng)的容錯(cuò)性和穩(wěn)定性，能夠避免由于應(yīng)用程序的不穩(wěn)定，而影響整個(gè)應(yīng)用程序的不穩(wěn)定18:51:3913操作系統(tǒng)的定義操作系統(tǒng)是合理組織計(jì)算機(jī)的工作流程，有效控制和管理計(jì)算機(jī)系統(tǒng)的各類資源，并方便用戶使用計(jì)算機(jī)的程序集合。（補(bǔ)充：是用戶和計(jì)算機(jī)的接口）18:51:39141.2操作系統(tǒng)的歷史回顧“需求推動(dòng)發(fā)展”(1)提高資源的利用率和系統(tǒng)性能(2)方便用戶：用戶上機(jī)、調(diào)試程序(3)

分散計(jì)算時(shí)的事務(wù)處理和非專業(yè)用戶（商業(yè)和辦公、家庭）(4)

器件的發(fā)展18:51:3915＝》1946年到50年代

第一代電子管計(jì)算機(jī)

工作方式：用戶既是程序員，又是操作員；編程語(yǔ)言：為機(jī)器語(yǔ)言；

輸入輸出：紙帶或卡片；

工作特點(diǎn)：用戶獨(dú)占全機(jī),資源不共享CPU利用率低；主要矛盾：計(jì)算機(jī)處理能力的提高，手工操作的低效率（造成浪費(fèi)）；

提高效率的途徑：專門的操作員，批處理

18:51:3916＝》50年代末~60年代中單道批處理系統(tǒng)

(simplebatchprocessing)

（晶體管）

利用磁帶把若干個(gè)作業(yè)分類編成作業(yè)執(zhí)行序列，每個(gè)批作業(yè)由一個(gè)專門的監(jiān)督程序（Monitor）自動(dòng)依次處理。可使用匯編語(yǔ)言開(kāi)發(fā)。

存在問(wèn)題：CPU和I/O設(shè)備使用忙閑不均（取決于當(dāng)前作業(yè)的特性）。對(duì)計(jì)算為主的作業(yè)，外設(shè)空閑；對(duì)I/O為主的作業(yè)，CPU空閑。人機(jī)矛盾仍然存在。18:51:3917＝》操作系統(tǒng)的完善通道技術(shù)和中斷技術(shù)的出現(xiàn)使監(jiān)督程序在負(fù)責(zé)作業(yè)運(yùn)行的同時(shí)提供I/O控制功能。通道：專用的I/O處理器，可與CPU并行工作，使I/O聯(lián)機(jī)處理。

中斷：是指CPU在收到外部中斷信號(hào)后，停止原來(lái)工作，轉(zhuǎn)去處理該中斷事件，完畢后回到原來(lái)斷點(diǎn)繼續(xù)工作。18:51:391860年代中多道程序批處理系統(tǒng)：為進(jìn)一步提高資源的利用率和系統(tǒng)的吞吐量，引入多道程序批處理系統(tǒng)操作系統(tǒng)終于代替人工成了計(jì)算機(jī)系統(tǒng)的“管家”，其發(fā)展進(jìn)入了成熟期，UNIX是這個(gè)時(shí)期的典型代表。18:51:3919＝》操作系統(tǒng)的發(fā)展從1980年至今建立在大規(guī)模集成電路基礎(chǔ)上的第四代計(jì)算機(jī)蓬勃發(fā)展。從個(gè)人計(jì)算機(jī)到并行機(jī)，再到網(wǎng)絡(luò)，計(jì)算機(jī)體系結(jié)構(gòu)也不斷發(fā)展變化。微機(jī)操作系統(tǒng)、并行操作系統(tǒng)、分布式操作系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)和嵌入式操作系統(tǒng)等相繼產(chǎn)生。操作系統(tǒng)的使用界面也從字符界面變成了圖形界面。操作系統(tǒng)的結(jié)構(gòu)除了有序分層的模塊化結(jié)構(gòu)外，還出現(xiàn)了虛擬機(jī)結(jié)構(gòu)和客戶/服務(wù)器加微內(nèi)核結(jié)構(gòu)等。DOS、OS/2、Windows和Linux等是這一時(shí)期的典型代表。18:51:39201.3操作系統(tǒng)的類型*

※按機(jī)器硬件的結(jié)構(gòu)與規(guī)?？煞譃椋?/p>

大型機(jī)操作系統(tǒng)、中型機(jī)操作系統(tǒng)、小型機(jī)操作系統(tǒng)、微型機(jī)操作系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)、嵌入式操作系統(tǒng)※按系統(tǒng)能同時(shí)響應(yīng)的用戶與任務(wù)個(gè)數(shù)分為：

單用戶單任務(wù)操作系統(tǒng)、單用戶多任務(wù)操作系統(tǒng)多用戶多任務(wù)操作系統(tǒng)等

按系統(tǒng)處理任務(wù)的方式分為：多道批處理操作系統(tǒng)、分時(shí)操作系統(tǒng)、實(shí)時(shí)操作系統(tǒng)、分布式操作系統(tǒng)18:51:3921一、批處理操作系統(tǒng)(OS/360MVT)

多道批處理系統(tǒng)(multiprogrammingsystem)多道：內(nèi)存中同時(shí)存放幾個(gè)作業(yè)

1。運(yùn)行方式：宏觀上并行運(yùn)行：都處于運(yùn)行狀態(tài)，但都未運(yùn)行完；微觀上串行運(yùn)行：各作業(yè)交替使用CPU；18:51:39222。多道批處理系統(tǒng)的特征：

優(yōu)點(diǎn)：（1）資源利用率高

（2）作業(yè)吞吐量大（3）系統(tǒng)開(kāi)銷小缺點(diǎn)：（1）用戶交互性差（2）作業(yè)平均周轉(zhuǎn)時(shí)間長(zhǎng)18:51:3923二、分時(shí)操作系統(tǒng)

(Time-sharingOperatingSystem)

主機(jī)終端終端終端………分時(shí)系統(tǒng)示意圖18:51:39241．分時(shí)的概念與實(shí)現(xiàn)

分時(shí)：指若干并發(fā)程序?qū)PU時(shí)間的共享，通過(guò)系統(tǒng)軟件實(shí)現(xiàn)。指多個(gè)用戶分享使用同一臺(tái)計(jì)算機(jī)。兩個(gè)或多個(gè)事件按時(shí)間劃分輪流使用計(jì)算機(jī)系統(tǒng)中的某一資源。

實(shí)現(xiàn)分時(shí)的基本方法是設(shè)立一個(gè)時(shí)間分享單位——時(shí)間片(timeslice)。它是系統(tǒng)規(guī)定進(jìn)程一次使用處理機(jī)的最長(zhǎng)時(shí)間。時(shí)間片的長(zhǎng)短可以因不同系統(tǒng)而異，通常100ms左右。18:51:3925實(shí)現(xiàn)思想如下：每個(gè)用戶在各自的終端上以問(wèn)答方式控制程序運(yùn)行，系統(tǒng)把中央處理器的時(shí)間劃分成時(shí)間片，輪流分配給各個(gè)聯(lián)機(jī)終端用戶，每個(gè)用戶只能在極短時(shí)間內(nèi)執(zhí)行，若時(shí)間片用完，而程序還未做完，則掛起等待下次分得時(shí)間片。

18:51:39262．分時(shí)系統(tǒng)的引入

分時(shí)系統(tǒng)的產(chǎn)生則是為了滿足用戶的需求在批處理系統(tǒng)中，用戶不能干預(yù)自己程序的運(yùn)行，無(wú)法得知程序運(yùn)行情況，對(duì)程序的調(diào)試和排錯(cuò)不利。

CTSS是最早的分時(shí)操作系統(tǒng)，Unix是目前廣泛使用的一個(gè)分時(shí)操作系統(tǒng)18:51:39273．分時(shí)系統(tǒng)的特征

（1）交互性。有人把分時(shí)系統(tǒng)稱為交互系統(tǒng)。（2）及時(shí)性。終端用戶的請(qǐng)求能在很短的時(shí)間內(nèi)獲得響應(yīng)，通常為2～3秒鐘。（3）獨(dú)占性。每個(gè)用戶各占一個(gè)終端，彼此獨(dú)立操作，互不干擾，感覺(jué)好象自己獨(dú)占主機(jī)一樣。（4）同時(shí)性（也叫多路性）提高了系統(tǒng)資源利用率，節(jié)省了開(kāi)支。18:51:3928三、實(shí)時(shí)操作系統(tǒng)

(RealTimeOperatingSystem)

實(shí)時(shí)系統(tǒng)則是指系統(tǒng)對(duì)特定輸入做出反應(yīng)的速度足以控制發(fā)出實(shí)時(shí)信號(hào)的對(duì)象，或者說(shuō)計(jì)算機(jī)能夠?qū)崟r(shí)地響應(yīng)外部事件的請(qǐng)求，在規(guī)定的短時(shí)間內(nèi)完成對(duì)該事件的處理，并控制所有實(shí)時(shí)設(shè)備和實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。18:51:39291．實(shí)時(shí)系統(tǒng)的類型

實(shí)時(shí)控制系統(tǒng)和實(shí)時(shí)信息處理系統(tǒng)(信息查詢系統(tǒng)和事務(wù)處理系統(tǒng))。

導(dǎo)彈制導(dǎo)系統(tǒng)，飛機(jī)自動(dòng)駕駛系統(tǒng)，火炮自動(dòng)控制系統(tǒng)？？？氣象預(yù)報(bào)系統(tǒng)、飛機(jī)訂票系統(tǒng)和股票交易系統(tǒng)

情報(bào)檢索系統(tǒng)？？18:51:39302．實(shí)時(shí)系統(tǒng)的特征

除了多路性，獨(dú)占性外，還有下面的特征（1）稍弱的交互性

它僅允許操作人員訪問(wèn)系統(tǒng)中某些特定的專用服務(wù)程序，一般不許寫(xiě)入或修改現(xiàn)有程序，不象分時(shí)系統(tǒng)那樣能向終端用戶提供數(shù)據(jù)處理和資源共享等服務(wù)。（2）實(shí)時(shí)性

對(duì)及時(shí)性的要求比分時(shí)系統(tǒng)要高，常以控制對(duì)象所能接受的延遲時(shí)間來(lái)確定，可以是秒級(jí)，也可以是毫秒級(jí)，甚至是微秒級(jí)。（3）可靠性

常采用多級(jí)容錯(cuò)措施，以保證系統(tǒng)的安全可靠。18:51:3931說(shuō)明：批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)是三種基本的操作系統(tǒng)類型。而一個(gè)實(shí)際的操作系統(tǒng)，可能兼有三者或其中兩者的功能。例如，在VAX－11系列機(jī)上所配置的VMS操作系統(tǒng)，便是一個(gè)兼有分時(shí)、實(shí)時(shí)和批處理功能的操作系統(tǒng)。18:51:3932四、單用戶操作系統(tǒng)

單用戶單任務(wù)操作系統(tǒng)：

在同一段時(shí)間內(nèi)僅為一個(gè)用戶提供服務(wù)。由于一個(gè)用戶獨(dú)占整個(gè)計(jì)算機(jī)系統(tǒng)，操作系統(tǒng)資源管理的任務(wù)變得不重要，為用戶提供良好的工作環(huán)境成了這類操作系統(tǒng)最主要的目標(biāo)。如MS-DOS、CP/M等。

單用戶多任務(wù)操作系統(tǒng)：只允許一個(gè)用戶上機(jī)，但允許將一個(gè)用戶程序分為若干任務(wù)，使他們并發(fā)執(zhí)行。Windows9x就是圖形用戶界面的單用戶多任務(wù)操作系統(tǒng)的典型代表。

18:51:3933五、網(wǎng)絡(luò)操作系統(tǒng)

將地理上分散的自主計(jì)算機(jī)通過(guò)通信系統(tǒng)的線路互連而成計(jì)算機(jī)網(wǎng)絡(luò)。網(wǎng)絡(luò)操作系統(tǒng)是在通常操作系統(tǒng)功能的基礎(chǔ)上提供網(wǎng)絡(luò)通信和網(wǎng)絡(luò)服務(wù)功能的操作系統(tǒng)。網(wǎng)絡(luò)操作系統(tǒng)為網(wǎng)上計(jì)算機(jī)進(jìn)行方便而有效的網(wǎng)絡(luò)資源共享，提供網(wǎng)絡(luò)用戶所需各種服務(wù)的軟件和相關(guān)規(guī)程的集合。三大陣營(yíng)：UNIX、WindowsNT、Netware

等18:51:3934

六、分布式操作系統(tǒng)*

集中式計(jì)算機(jī)系統(tǒng)：

以往的計(jì)算機(jī)系統(tǒng)中，其處理和控制功能都高度地集中在一臺(tái)計(jì)算機(jī)上，所有的任務(wù)都由它完成

分布式計(jì)算機(jī)系統(tǒng)

指由多臺(tái)分散的計(jì)算機(jī)，經(jīng)互連網(wǎng)絡(luò)連接而成的系統(tǒng)。每臺(tái)計(jì)算機(jī)高度自治，又相互協(xié)同，能在系統(tǒng)范圍內(nèi)實(shí)現(xiàn)資源管理，任務(wù)分配、能并行地運(yùn)行分布式程序。

18:51:39351．分布式操作系統(tǒng)與網(wǎng)絡(luò)操作系統(tǒng)比較

（1）分布性：系統(tǒng)中的若干臺(tái)機(jī)器可以互相協(xié)作來(lái)完成同一個(gè)任務(wù)（2）并行性：它的任務(wù)分配程序可將多個(gè)任務(wù)甚至單一應(yīng)用分配到多個(gè)處理單元并行執(zhí)行

（3）統(tǒng)一性：

每個(gè)計(jì)算機(jī)共享一個(gè)統(tǒng)一的分布式操作系統(tǒng)，它們都裝有這個(gè)操作系統(tǒng)內(nèi)核的副本，內(nèi)核對(duì)該計(jì)算機(jī)系統(tǒng)進(jìn)行基本的控制

（4）透明性：

將所有的軟件和硬件集合成單系統(tǒng)，使用戶感覺(jué)這樣一群機(jī)器與一臺(tái)單處理機(jī)分時(shí)系統(tǒng)是一樣的

（5）可靠性：可靠性與健壯性非常好

18:51:39362．分布式系統(tǒng)的主要優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：性價(jià)比高、可靠性高、可擴(kuò)展性強(qiáng)、適合分布式的應(yīng)用等。缺點(diǎn)：需要復(fù)雜的軟件、存在潛在的通信瓶頸、數(shù)據(jù)安全性較弱等。

真正實(shí)用的分布式操作系統(tǒng)：荷蘭Virije大學(xué)研制的Amoeba和美國(guó)CarnegieMello研制的Mach、X樹(shù)系統(tǒng)、Plan9

等

18:51:39371.4操作系統(tǒng)的特征

一、并發(fā)性二、共享性三、虛擬性四、異步性

18:51:3938并發(fā)與并行并發(fā)：Concurrence是指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。并行：Parallel是指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生。單處理機(jī)系統(tǒng)中采用多道程序技術(shù)后，可以實(shí)現(xiàn)硬件之間的并行操作和程序之間的并發(fā)執(zhí)行。18:51:3939程序A請(qǐng)求I/O程序B請(qǐng)求I/O程序C請(qǐng)求I/O

C完成I/OB完成I/OA完成I/OC再次被調(diào)度

A再次被調(diào)度

A完成

程序A程序C程序B調(diào)度程序

時(shí)間軸t多道程序并發(fā)執(zhí)行示意圖單線表示程序占用cpu，雙線表示外設(shè)在執(zhí)行相應(yīng)程序的I/O請(qǐng)求18:51:3940小注：在單處理機(jī)中，有沒(méi)有并行（并發(fā)）運(yùn)行的程序？在單處理機(jī)中，有沒(méi)有并行運(yùn)行的情況？?jī)傻莱绦蚍謩e在兩個(gè)處理機(jī)（多CPU）或兩套處理部件中獨(dú)立運(yùn)行，可以實(shí)現(xiàn)并行。并發(fā)程序要達(dá)到“在同一時(shí)間間隔內(nèi)進(jìn)行”，也需要相應(yīng)的硬件或軟件支持。例如，兩道程序分別在一個(gè)處理機(jī)或一套處理部件上運(yùn)行，由于每一時(shí)刻僅能執(zhí)行一道程序，所以微機(jī)上這兩道程序是交替和順序執(zhí)行的，但從宏觀上看，在一段時(shí)間間隔內(nèi)這兩道程序同時(shí)運(yùn)行。所以，并發(fā)和并行都需要多道程序技術(shù)的支持。18:51:3941二、共享性

共享：是指計(jì)算機(jī)系統(tǒng)中的各種硬、軟件資源都可以為多個(gè)用戶同時(shí)使用。共享可分互斥共享和同時(shí)共享兩種方式?；コ夤蚕硪步许樞蚬蚕恚菏侵付鄠€(gè)進(jìn)程（進(jìn)程的定義在第二章）互斥地或者排他性地使用某個(gè)資源。同時(shí)共享又叫并發(fā)共享：是指在一段時(shí)間內(nèi)，多個(gè)程序可以同時(shí)使用系統(tǒng)中的某個(gè)資源。這里的“同時(shí)”是個(gè)宏觀概念，微觀上，這多個(gè)進(jìn)程是交替使用該資源

18:51:3942小注：并發(fā)與共享是現(xiàn)代操作系統(tǒng)的兩個(gè)最基本特征，它們之間是相輔相成、互為依存的。一方面，資源共享是以程序（進(jìn)程）并發(fā)執(zhí)行為條件的，如果系統(tǒng)不允許并發(fā)執(zhí)行，自然不存在資源共享問(wèn)題；另一方面，程序并發(fā)執(zhí)行以資源共享為基礎(chǔ)，如果系統(tǒng)不能對(duì)資源共享實(shí)施有效管理，則也必將影響到程序的并發(fā)執(zhí)行，甚至根本無(wú)法并發(fā)執(zhí)行。只有系統(tǒng)能夠高度并發(fā)，資源才能充分共享；也只有資源被充分共享，系統(tǒng)才能更好地并發(fā)。

18:51:3943三、虛擬性

在操作系統(tǒng)中所謂的虛擬：是通過(guò)某種技術(shù)物理上的一個(gè)實(shí)體映射為邏輯上的多個(gè)對(duì)應(yīng)物。前者是實(shí)際存在的，后者是虛的，是感覺(jué)性的存在。

如WINDOWS操作系統(tǒng)使用了虛擬存儲(chǔ)技術(shù)，它把外部存儲(chǔ)器映射為用戶自由使用的“無(wú)限大”的內(nèi)存空間，即虛擬內(nèi)存，這樣保證了需要內(nèi)存空間比實(shí)際內(nèi)存空間大的程序能正常運(yùn)行。

18:51:3944四、異步性

—不確定性

所謂異步是指內(nèi)存中的多個(gè)進(jìn)程都按照各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。這是由于它們共享資源、并發(fā)執(zhí)行的緣故。

內(nèi)存中的每個(gè)進(jìn)程什么時(shí)候執(zhí)行，向前推進(jìn)速度快慢，共需多少時(shí)間都是由執(zhí)行的現(xiàn)場(chǎng)所決定。很有可能先進(jìn)入內(nèi)存的作業(yè)后完成，后進(jìn)入內(nèi)存的作業(yè)先完成。但同一程序在相同的初始數(shù)據(jù)下，無(wú)論何時(shí)運(yùn)行都應(yīng)獲得同樣的結(jié)果。所以，異步運(yùn)行方式是運(yùn)行的。18:51:39451.5操作系統(tǒng)與用戶的接口

一、命令接口1、脫機(jī)命令接口2、聯(lián)機(jī)命令接口二、程序接口三、圖形用戶接口

18:51:39461.6操作系統(tǒng)的結(jié)構(gòu)

一、整體式結(jié)構(gòu)二、層次式結(jié)構(gòu)三、虛擬機(jī)系統(tǒng)四、客戶-服務(wù)器系統(tǒng)

18:51:39471.7操作系統(tǒng)的硬件運(yùn)行環(huán)境

一、通道與中斷的作用二、管態(tài)與目態(tài)三、三級(jí)存儲(chǔ)結(jié)構(gòu)四、存儲(chǔ)保護(hù)機(jī)制

18:51:39481.7.3管態(tài)與目態(tài)管態(tài)指操作系統(tǒng)的管理程序在執(zhí)行時(shí)CPU所處的狀態(tài)，又名特權(quán)態(tài)、系統(tǒng)態(tài)、核心態(tài))目態(tài)指用戶程序在執(zhí)行時(shí)CPU所處的狀態(tài)，又名用戶態(tài)。CPU處于管態(tài)時(shí)既可執(zhí)行特權(quán)指令，也可執(zhí)行非特權(quán)指令；而CPU處于目態(tài)時(shí)只可執(zhí)行非特權(quán)指令。從目態(tài)轉(zhuǎn)換為管態(tài)的唯一途徑是中斷。從管態(tài)到目態(tài)可以通過(guò)修改程序狀態(tài)字來(lái)實(shí)現(xiàn)，這將伴隨這由操作系統(tǒng)程序到用戶程序的轉(zhuǎn)換。

18:51:3949在計(jì)算機(jī)系統(tǒng)中，為什么要區(qū)分管態(tài)與目態(tài)？【解答】操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中最重要的系統(tǒng)軟件，為了能正確地進(jìn)行管理和控制，其本身是不能被破壞的。因此，系統(tǒng)采用了區(qū)分處理機(jī)狀態(tài)的辦法，為操作系統(tǒng)程序建立一個(gè)保護(hù)環(huán)境。這樣，用戶程序只能在管態(tài)下運(yùn)行，只能執(zhí)行非特權(quán)指令，只能訪問(wèn)自己的存儲(chǔ)區(qū)，從而保護(hù)了操作系統(tǒng)程序的正常運(yùn)行。502.1多道程序設(shè)計(jì)

多道程序設(shè)計(jì)是指允許多道程序同時(shí)進(jìn)入內(nèi)存，并允許它們共享資源、并發(fā)執(zhí)行的程序設(shè)計(jì)技術(shù)。采用這一技術(shù)的系統(tǒng)叫多道程序系統(tǒng)。多道程序設(shè)計(jì)技術(shù)根本性地推進(jìn)了操作系統(tǒng)技術(shù)發(fā)展。是現(xiàn)代操作系統(tǒng)所采用的最基本、最重要的技術(shù)，但它也帶來(lái)一些單道程序系統(tǒng)中沒(méi)有的新問(wèn)題，這些多道程序設(shè)計(jì)中的新問(wèn)題可以概括為進(jìn)程間的互斥與同步，另外，對(duì)系統(tǒng)各類資源的管理也都復(fù)雜了。對(duì)這些問(wèn)題的解決導(dǎo)致多道程序設(shè)計(jì)的實(shí)現(xiàn)代價(jià)比單道程序設(shè)計(jì)高，也使得現(xiàn)代操作系統(tǒng)變得日益復(fù)雜、龐大和精巧。

51一、順序程序的執(zhí)行單道系統(tǒng)中，程序是順序執(zhí)行的，即程序在執(zhí)行時(shí)，必須按照某種先后次序進(jìn)行，僅當(dāng)前一操作執(zhí)行完后，才能執(zhí)行其后續(xù)操作。因此在某一時(shí)刻，系統(tǒng)的各個(gè)部分中只有一部分在工作。

I1C1P2P1I2C2程序的順序執(zhí)行52如對(duì)于以下三條語(yǔ)句的程序段：

P1:a=x+yP2:b=a+1P3:c=b-6其中的語(yǔ)句P2必須在a被賦值后才能執(zhí)行。同樣,P3也只能在b被賦值后才能執(zhí)行。

53二、程序順序執(zhí)行時(shí)的特征1.順序性處理機(jī)的操作，嚴(yán)格按照程序所規(guī)定的順序執(zhí)行。2.封閉性程序在運(yùn)行時(shí)，它獨(dú)占全機(jī)資源，因而機(jī)內(nèi)各資源的狀態(tài)（除初始狀態(tài)外），只有本程序才能改變它。程序一旦運(yùn)行，執(zhí)行結(jié)果不受外界因素的影響。3.可再現(xiàn)性

只要程序執(zhí)行時(shí)的環(huán)境和初始條件相同，當(dāng)程序多次重復(fù)執(zhí)行，不論是“走走停停”還是“不停頓”，都獲得相同的結(jié)果。54I1I2I3I4C1C2C4C3P1P2P3P4三、程序并發(fā)執(zhí)行55四、并發(fā)程序執(zhí)行的條件1．定義程序Pi在執(zhí)行期間所需引用的諸變量ai的集合，稱為Pi的讀集，記作R(Pi)={a1,a2,a3,…,am}。程序Pi在執(zhí)行期間所需改變的諸變量bj的集合，稱為Pi的寫(xiě)集，記作W(Pi)={b1,b2,b3,…,bm}。

56寫(xiě)出下列4條語(yǔ)句的讀集、寫(xiě)集。語(yǔ)句讀集寫(xiě)集P1:a=x+yR(P1)={x,y}W(P1)={a}P2:b=z+1R(P2)={z}W(P2)=P3:c=a+bR(P3)={a,b}W(P3)={c}P4:d=c-2R(P4)={c}W(P4)=5or7otf572．定理

如果兩個(gè)程序P1和P2滿足下述條件，它們便能并發(fā)執(zhí)行，否則不能。

R(P1)∩W(P2)∪R(P1)∩W(P2)∪W(P2)∩W(P2)={}

即當(dāng)兩個(gè)程序的讀集與寫(xiě)集的交集以及寫(xiě)集與寫(xiě)集的交集都為空集時(shí)，它們可以并發(fā)執(zhí)行，否則不行。該定理是程序并發(fā)執(zhí)行的條件，是Bernstein在1966年提出的，故稱Bernstein條件。

58

p1p2p3p4畫(huà)出這四條語(yǔ)句的前趨圖

:程序并發(fā)執(zhí)行時(shí)的特征：間斷性程序在并發(fā)執(zhí)行時(shí)，由于共享資源，或者為完成同一任務(wù)而相互合作，致使在并發(fā)程序間形成了相互制約的關(guān)系。失去封閉性程序在并發(fā)執(zhí)行時(shí)，是多個(gè)程序共享系統(tǒng)中的各種資源，所以這些資源的狀態(tài)可以由多個(gè)程序來(lái)改變，，使其失去了封閉性。不可再現(xiàn)性程序在并發(fā)執(zhí)行時(shí)，由于失去了封閉性，也導(dǎo)致失去了可再現(xiàn)性。60例如：有兩個(gè)循環(huán)程序A和B，A每執(zhí)行一次時(shí)，都要作m＝m＋1操作。B每執(zhí)行一次時(shí)，先執(zhí)行print(m)操作，然后再將m置成“0”。A和B以不同速度運(yùn)行，可能出現(xiàn)以下三種情況（假定某時(shí)刻變量m的值為m）：m=m+1在print(m)和m＝0之前。此時(shí)得到的m值分別為m+1，m+1，0m=m+1在print(m)和m＝0之后。此時(shí)得到的m值分別為m，0，1m=m+1在print(m)和m＝0之間。此時(shí)得到的m值分別為m，m+1，0612.2進(jìn)程的描述

程序并發(fā)執(zhí)行時(shí)，產(chǎn)生了一些新特征，所以一般的程序是不能并發(fā)執(zhí)行的。為了使程序在多道程序環(huán)境下能并發(fā)執(zhí)行，并能對(duì)并發(fā)執(zhí)行的程序加以控制和描述，引入“進(jìn)程”的概念?，F(xiàn)在，“進(jìn)程”已經(jīng)成為操作系統(tǒng)乃至并發(fā)程序設(shè)計(jì)中最核心的概念，它是對(duì)正在運(yùn)行的程序的抽象，操作系統(tǒng)的其他所有內(nèi)容都是圍繞著進(jìn)程展開(kāi)的。掌握進(jìn)程的概念對(duì)于理解操作系統(tǒng)的實(shí)質(zhì)以及分析、設(shè)計(jì)操作系統(tǒng)都有非常重要的意義

62一、進(jìn)程的定義

“進(jìn)程”這一術(shù)語(yǔ)，在60年代初期，首先在美國(guó)MIT的MULTICS系統(tǒng)和IBM公司的CTSS/360系統(tǒng)中引入。其中能反映進(jìn)程實(shí)質(zhì)的定義有：

（1）進(jìn)程是程序的一次執(zhí)行。（2）進(jìn)程是可以和其他計(jì)算并發(fā)執(zhí)行的計(jì)算。（3）進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)發(fā)生的活動(dòng)。（4）進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。（5）進(jìn)程是進(jìn)程實(shí)體的一次活動(dòng)。

63我國(guó)1978年在廬山召開(kāi)的全國(guó)OS研討會(huì)上將“進(jìn)程”定義為：進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。

一個(gè)程序?yàn)閷?shí)現(xiàn)不同的任務(wù)可以同時(shí)有多次運(yùn)行活動(dòng)，每個(gè)運(yùn)行活動(dòng)分別作為不同的進(jìn)程64二、進(jìn)程的特性及與程序的區(qū)別

1.進(jìn)程的五個(gè)特性

(1)動(dòng)態(tài)性：生命周期。即它由系統(tǒng)“創(chuàng)建”而誕生，因被“調(diào)度”而執(zhí)行，因得不到資源而暫停，最后因被“撤消”而消亡。

(2)并發(fā)性：是指不同進(jìn)程的動(dòng)作在時(shí)間上可以重疊，即系統(tǒng)內(nèi)的多個(gè)進(jìn)程是可以并發(fā)執(zhí)行的。

(3)獨(dú)立性：指進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行的基本單位，同時(shí)也是系統(tǒng)中獨(dú)立獲得資源和獨(dú)立調(diào)動(dòng)的基本單位。

(4)異步性：指進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)

(5)結(jié)構(gòu)特性：從結(jié)構(gòu)上看，每個(gè)進(jìn)程都由程序段、數(shù)據(jù)段和一個(gè)PCB三部分組成。2.進(jìn)程與程序的區(qū)別

(1)從定義上看，進(jìn)程是程序處理數(shù)據(jù)的過(guò)程，而程序是一組指令的有序集合；(2)進(jìn)程具有動(dòng)態(tài)性、并發(fā)性、獨(dú)立性和異步性等，而程序不具有這些特性；(3)從進(jìn)程結(jié)構(gòu)特性上看，它包含程序（以及數(shù)據(jù)和PCB）；(4)進(jìn)程和程序并非一一對(duì)應(yīng)。

66在操作系統(tǒng)中引入“進(jìn)程”概念的主要目的是（）。A．改善用戶編程環(huán)境B.描述程序動(dòng)態(tài)執(zhí)行過(guò)程的性質(zhì)C.使程序與計(jì)算過(guò)程一一對(duì)應(yīng)D.提高程序的運(yùn)行速度67三、進(jìn)程的基本狀態(tài)及其轉(zhuǎn)換

1．進(jìn)程的三種基本狀態(tài)

（1）就緒（Ready）狀態(tài)：當(dāng)進(jìn)程已分配到除CPU以外的所有必要的資源，只要能再獲得處理機(jī)，便可立即執(zhí)行

（2）執(zhí)行（Running）狀態(tài)：當(dāng)進(jìn)程已獲得處理機(jī)，其程序正在處理機(jī)上執(zhí)行，（3）阻塞（Blocked）狀態(tài)：正在執(zhí)行的進(jìn)程，由于等待某事件發(fā)生而無(wú)法執(zhí)行時(shí)，便放棄處理機(jī)而處于暫停狀態(tài)。

在不少系統(tǒng)中，又增加了兩種基本狀態(tài)：

①新?tīng)顟B(tài)

②終止（Terminated）狀態(tài)

68引入新?tīng)顟B(tài)和終止?fàn)顟B(tài)的原因：由于OS在建立一個(gè)新進(jìn)程時(shí)，通常分為2步：第一步是為新登錄的用戶程序（分時(shí)系統(tǒng)）創(chuàng)建進(jìn)程，并為他分配資源，此時(shí)進(jìn)程即處于新?tīng)顟B(tài)。第二步是把新創(chuàng)建的進(jìn)程送入就緒隊(duì)列，一旦進(jìn)程進(jìn)入就緒隊(duì)列，它便由新?tīng)顟B(tài)變?yōu)榫途w狀態(tài)。

一個(gè)結(jié)束了的進(jìn)程，其退出系統(tǒng)的過(guò)程也分為兩步：第一步是將該進(jìn)程從就緒隊(duì)列中移出，使之成為一個(gè)不可能再運(yùn)行的進(jìn)程，相應(yīng)的進(jìn)程處于終止?fàn)顟B(tài)。此時(shí)系統(tǒng)并不立即撤銷它，而是將它暫時(shí)留在系統(tǒng)中，以便其它進(jìn)程去收集該進(jìn)程的有關(guān)信息。

69新進(jìn)程就緒執(zhí)行結(jié)束阻塞接納完成I/O完成或等待的事件發(fā)生I/O請(qǐng)求或等待某事件2．進(jìn)程三種基本狀態(tài)間的轉(zhuǎn)換調(diào)度時(shí)間片用完70其他的狀態(tài)例如，在有的系統(tǒng)中，為了暫時(shí)緩和內(nèi)存的緊張狀態(tài)，或?yàn)榱苏{(diào)節(jié)系統(tǒng)負(fù)荷，又引入了掛起功能。即暫時(shí)掛起一部分進(jìn)程，把它們從內(nèi)存臨時(shí)換出到外存，使它們暫時(shí)和系統(tǒng)脫離聯(lián)系。這樣，就需要把進(jìn)程的就緒狀態(tài)進(jìn)一步細(xì)分為活動(dòng)就緒狀態(tài)（未被掛起的就緒進(jìn)程）和靜止就緒狀態(tài)（被掛起的就緒進(jìn)程）兩種。把進(jìn)程的阻塞狀態(tài)也細(xì)分為活動(dòng)阻塞狀態(tài)（未被掛起的阻塞進(jìn)程）和靜止阻塞狀態(tài)（被掛起的阻塞進(jìn)程）

71問(wèn)題：1.在進(jìn)程狀態(tài)轉(zhuǎn)換時(shí)，下列哪一種狀態(tài)轉(zhuǎn)換是不可能發(fā)生的？

A)就緒態(tài)→運(yùn)行態(tài)B)運(yùn)行態(tài)→就緒態(tài)

C)運(yùn)行態(tài)→等待態(tài)D)阻塞態(tài)→運(yùn)行態(tài)2．某進(jìn)程在運(yùn)行過(guò)程中需要等待從磁盤(pán)上讀入數(shù)據(jù)，此時(shí)該進(jìn)程的狀態(tài)將（

）。

A.從就緒變?yōu)檫\(yùn)行B.從運(yùn)行變?yōu)榫途w

C.從運(yùn)行變?yōu)樽枞鸇.從阻塞變?yōu)榫途w

72四、進(jìn)程控制塊——PCB

(ProcessControlBlock)PCB是系統(tǒng)為了描述和控制進(jìn)程的運(yùn)行而為進(jìn)程定義的一種數(shù)據(jù)結(jié)構(gòu)，它是進(jìn)程實(shí)體的一部分，是進(jìn)程存在的唯一標(biāo)志，也是操作系統(tǒng)中最重要的結(jié)構(gòu)體類型的數(shù)據(jù)結(jié)構(gòu)。PCB中存放著操作系統(tǒng)所需的用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息。731．PCB的作用（1）標(biāo)識(shí)進(jìn)程的存在：系統(tǒng)創(chuàng)建進(jìn)程時(shí)，就為之創(chuàng)建一個(gè)PCB；進(jìn)程結(jié)束時(shí)，系統(tǒng)又回收其PCB，進(jìn)程便隨之消亡。

（2）為系統(tǒng)提供可并發(fā)執(zhí)行的獨(dú)立單位：PCB使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。沒(méi)有為之建立PCB的程序是不能并發(fā)執(zhí)行的。

（3）為系統(tǒng)控制和管理進(jìn)程提供所需的一切信息。

742．PCB中的信息

（1）進(jìn)程標(biāo)識(shí)符：（2）進(jìn)程的現(xiàn)行狀態(tài)：（3）處理機(jī)的現(xiàn)場(chǎng)保留區(qū)：（4）進(jìn)程相應(yīng)的程序和數(shù)據(jù)地址：（5）進(jìn)程資源清單：（6）進(jìn)程優(yōu)先級(jí)：

（7）進(jìn)程同步與通信機(jī)制：（8）進(jìn)程所在PCB的鏈接字：（9）與進(jìn)程有關(guān)的其他信息：75五、進(jìn)程的隊(duì)列

所謂進(jìn)程隊(duì)列指的是把具有相同狀態(tài)的進(jìn)程按照某種原則鏈接在一起組成的隊(duì)列，它其實(shí)是PCB的一種組織形式，有時(shí)也稱PCB鏈

因?yàn)镻CB是系統(tǒng)中最重要也是被頻繁訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，系統(tǒng)中的許多模塊，如調(diào)度程序、資源分配程序、中斷處理程序以及監(jiān)督和分析程序等，特別是運(yùn)行頻率很高的進(jìn)程分派程序，都要對(duì)它進(jìn)行讀或?qū)懖僮?，所以PCB常駐內(nèi)存的系統(tǒng)區(qū)中，系統(tǒng)將所有的PCB以數(shù)組形式連續(xù)存放組織成若干個(gè)鏈表（或隊(duì)列），存放在操作系統(tǒng)中專門開(kāi)辟的PCB區(qū)內(nèi)。

76空閑PCB隊(duì)列頭指針阻塞進(jìn)程隊(duì)列頭指針就緒進(jìn)程隊(duì)列頭指針執(zhí)行進(jìn)程指針PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9430879015….77一、進(jìn)程控制機(jī)構(gòu)

1．操作系統(tǒng)的內(nèi)核

通常將一些與硬件密切相關(guān)的模塊，例如，中斷處理程序、各種常用設(shè)備的驅(qū)動(dòng)程序，以及運(yùn)行頻率較高的模塊等安排在緊靠硬件的軟件層中，并將它們常駐內(nèi)存，以提高操作系統(tǒng)運(yùn)行效率，并對(duì)它們加以特殊的保護(hù)。上述這一部分程序稱為操作系統(tǒng)內(nèi)核。操作系統(tǒng)的內(nèi)核是計(jì)算機(jī)硬件擴(kuò)充的第一層軟件，是在核心態(tài)運(yùn)行的操作系統(tǒng)程序。

2.3進(jìn)程的控制

782．內(nèi)核中與進(jìn)程控制有關(guān)的機(jī)構(gòu)

（1）原語(yǔ)操作：

原語(yǔ)本身是由若干條指令構(gòu)成、用于完成特定功能的一個(gè)過(guò)程。

原子操作：一個(gè)操作中的所有動(dòng)作，與一般過(guò)程的區(qū)別：要么全作，要么全不作。即：原子操作是不可分割的，它是機(jī)器指令的延伸。

79現(xiàn)代操作系統(tǒng)常采用屏蔽中斷的方法來(lái)保證原語(yǔ)在執(zhí)行時(shí)的不可分割性，這種原子性對(duì)于解決進(jìn)程同步互斥問(wèn)題是非常重要的。在內(nèi)核中可能有許多原語(yǔ)，常見(jiàn)的內(nèi)核原語(yǔ)有進(jìn)程控制原語(yǔ)、用于鏈表操作的原語(yǔ)和用于控制進(jìn)程互斥、同步的原語(yǔ)等。80（2）進(jìn)程管理：

進(jìn)程管理的全部或大部分功能都在內(nèi)核中，這主要是因?yàn)檫@些功能模塊的運(yùn)行頻率較高，例如，進(jìn)程調(diào)度與分派、進(jìn)程的創(chuàng)建、進(jìn)程的撤消等，或是因?yàn)樗鼈優(yōu)槎喾N功能模塊所調(diào)用，例如，實(shí)現(xiàn)進(jìn)程的同步和進(jìn)程通信的原語(yǔ)等。此外，內(nèi)核中的進(jìn)程管理，還需要管理好進(jìn)程控制塊PCB.81ABCGFEHDIJKLM二、進(jìn)程的控制原語(yǔ)

進(jìn)程樹(shù)

祖先進(jìn)程控制原語(yǔ)是對(duì)進(jìn)程生命期控制和實(shí)現(xiàn)進(jìn)程狀態(tài)轉(zhuǎn)換的原語(yǔ)。821.進(jìn)程創(chuàng)建原語(yǔ)Creat()引起創(chuàng)建進(jìn)程的事件：用戶登錄作業(yè)調(diào)度提供服務(wù)應(yīng)用請(qǐng)求進(jìn)程創(chuàng)建的主要步驟：申請(qǐng)空白PCB為新進(jìn)程分配資源初始化PCB的內(nèi)容將新進(jìn)程插入就緒隊(duì)列832.進(jìn)程撤銷原語(yǔ)Tenminat()引起創(chuàng)建進(jìn)程的事件：正常結(jié)束異常結(jié)束外界干擾進(jìn)程撤銷的過(guò)程：檢索進(jìn)程當(dāng)前的狀態(tài)，結(jié)束并置調(diào)度標(biāo)志，撤銷其所有的子進(jìn)程，歸還資源，移出隊(duì)列應(yīng)由父進(jìn)程調(diào)用進(jìn)程撤銷原語(yǔ)來(lái)撤銷，以便及時(shí)的釋放其所占的資源843.進(jìn)程阻塞原語(yǔ)Block()引起進(jìn)程阻塞的事件：請(qǐng)求系統(tǒng)服務(wù)啟動(dòng)某種操作新數(shù)據(jù)尚未到達(dá)無(wú)新工作可作進(jìn)程堵塞的過(guò)程：發(fā)現(xiàn)堵塞事件，調(diào)用阻塞原語(yǔ)把自己阻塞，停止進(jìn)程的執(zhí)行，修改PCB的狀態(tài)信息，將其插入到自己的堵塞隊(duì)列。最后轉(zhuǎn)調(diào)度程序，將處理機(jī)分配給另一個(gè)就緒進(jìn)程。進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為854.進(jìn)程喚醒原語(yǔ)Wakeup()引起進(jìn)程喚醒的事件：當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時(shí)，或者所期待的數(shù)據(jù)已經(jīng)到達(dá)。由該有關(guān)進(jìn)程調(diào)用進(jìn)程喚醒原語(yǔ)，將等待該資源而阻塞的一個(gè)進(jìn)程喚醒成……進(jìn)程喚醒的過(guò)程：把被阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出，將其PCB的現(xiàn)行狀態(tài)，由阻塞改為就緒，再將該進(jìn)程插入到PCB就緒隊(duì)列中。865.掛起原語(yǔ)Suspend():

當(dāng)出現(xiàn)了引起掛起的事件時(shí)，如為了暫時(shí)緩和內(nèi)存的緊張狀態(tài)，用戶進(jìn)程請(qǐng)求將自己掛起或者當(dāng)父進(jìn)程請(qǐng)求將自己的某個(gè)子進(jìn)程掛起時(shí)，系統(tǒng)將利用掛起原語(yǔ)suspend()將制定的進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。

6.激活原語(yǔ)Active():

將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的狀態(tài)，改為相應(yīng)的活動(dòng)狀態(tài)872.4進(jìn)程的互斥

——你要，我也要

多道程序設(shè)計(jì)帶來(lái)的問(wèn)題：

并發(fā)執(zhí)行的多個(gè)進(jìn)程可能產(chǎn)生互斥或同步的相互制約關(guān)系，不采取措施，可能導(dǎo)致結(jié)果的不可再現(xiàn)性。影響系統(tǒng)效率，而且還可以導(dǎo)致系統(tǒng)崩潰。

為此，現(xiàn)代操作系統(tǒng)都在內(nèi)核中設(shè)有進(jìn)程的互斥同步機(jī)制，以控制并發(fā)執(zhí)行的諸進(jìn)程能有效的共享資源和相互合作，同時(shí)使并發(fā)程序的執(zhí)行仍具有可再現(xiàn)性。88一、互斥的定義所謂進(jìn)程互斥，指的是對(duì)某個(gè)系統(tǒng)資源，一個(gè)進(jìn)程正在使用它，另外一個(gè)想用它的進(jìn)程就必須等待，而不能同時(shí)使用。進(jìn)程互斥是多道程序系統(tǒng)中進(jìn)程間存在的一種源于資源共享的制約關(guān)系，也稱間接制約關(guān)系，主要是由被共享資源的使用性質(zhì)所決定的。89這種限定進(jìn)程只能互斥地訪問(wèn)它的資源叫臨界資源（指一次僅允許一個(gè)進(jìn)程使用的資源）。

臨界資源限定了使用者只能互斥地使用它。操作系統(tǒng)也不能中途從搶先者手中把臨界資源搶來(lái)給其他進(jìn)程用。因此，臨界資源也是不可剝奪性資源。例：打印機(jī)、共享變量等。計(jì)算機(jī)系統(tǒng)中可剝奪性使用的資源主要有CPU、內(nèi)存和磁盤(pán)等。9091臨界區(qū)：進(jìn)程中訪問(wèn)臨界資源的那段程序代碼稱為臨界區(qū)或臨界段。使用同一臨界資源的不同進(jìn)程中的臨界區(qū)稱為同類臨界區(qū)或相關(guān)臨界區(qū)。為實(shí)現(xiàn)對(duì)臨界資源的互斥訪問(wèn)，應(yīng)保證諸進(jìn)程互斥地進(jìn)入各自的臨界區(qū)。

但無(wú)論采用何種方法，都應(yīng)遵循臨界區(qū)的使用原則，即“空則讓進(jìn)，忙則等待，等則有限，等則讓權(quán)”。

92二、上鎖和開(kāi)鎖原語(yǔ)

現(xiàn)代操作系統(tǒng)用來(lái)實(shí)現(xiàn)進(jìn)程的互斥、同步的工具有多種，如上鎖與開(kāi)鎖原語(yǔ)、信號(hào)燈機(jī)制、管程機(jī)制等。

上鎖與開(kāi)鎖是一種最簡(jiǎn)單的進(jìn)程互斥方法，它使用一個(gè)鎖變量W來(lái)表示某種臨界資源的狀態(tài)，W=0表示資源空閑可用W=1表示資源正被使用

931．上鎖原語(yǔ)：LOCK（W）L1：如果W=1那么轉(zhuǎn)向L1;否則W=1返回voidlock(鎖變量w){test:if(w為1)gototestelsew=1;/*上鎖*/}

/*lock(w)*/1.考察鎖位的值；2.如果原來(lái)的值為0，將鎖位置1；3.如果為1，則返回第一步再次考察942．開(kāi)鎖原語(yǔ)：UNLOCK（W）

W=0;返回voidunlock(鎖變量w){w=0;/*開(kāi)鎖

*/}/*unlock(w)*/當(dāng)進(jìn)程使用完資源后，它必須將鎖位置成“0”，稱為開(kāi)鎖操作。95三、用上鎖和開(kāi)鎖原語(yǔ)可以解決并發(fā)進(jìn)程的互斥

任何欲進(jìn)入臨界區(qū)的進(jìn)程，必須先執(zhí)行上鎖原語(yǔ)。若上鎖原語(yǔ)順利通過(guò)，則進(jìn)程可進(jìn)入臨界區(qū)；當(dāng)完成對(duì)臨界區(qū)資源的訪問(wèn)后再執(zhí)行開(kāi)鎖原語(yǔ)，以釋放該臨界資源。

即在相關(guān)進(jìn)程的程序里由上鎖和開(kāi)鎖原語(yǔ)緊夾著臨界區(qū)，就能保證這些進(jìn)程互斥地進(jìn)入各自的臨界區(qū)。

96例如，甲、乙兩進(jìn)程要訪問(wèn)同一類臨界資源

甲進(jìn)程：其他代碼；

LOCK（W）；甲進(jìn)程的臨界區(qū)；

UNLOCK（W）；其他代碼；乙進(jìn)程：其他代碼；

LOCK（W）；乙進(jìn)程的臨界區(qū)；

UNLOCK（W）；其他代碼；用上鎖用上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)來(lái)實(shí)現(xiàn)進(jìn)程的互斥的確很簡(jiǎn)單，但處理機(jī)效率不高，因?yàn)樯湘i原語(yǔ)中的條件測(cè)試操作可能引起CPU“忙等”。

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

荷蘭著名科學(xué)家，后來(lái)的計(jì)算機(jī)圖靈獎(jiǎng)獲得者，E.W.Dijkstra于1965年提出了用作進(jìn)程同步工具的信號(hào)量（semaphore）機(jī)制，這是一種卓有成效的進(jìn)程互斥同步工具，已被廣泛應(yīng)用于現(xiàn)代計(jì)算機(jī)系統(tǒng)中。

98信號(hào)量機(jī)制的基本原理是：

兩個(gè)或多個(gè)進(jìn)程可以利用彼此間收發(fā)的簡(jiǎn)單的信號(hào)來(lái)實(shí)現(xiàn)“正確的”并發(fā)執(zhí)行，一個(gè)進(jìn)程在收到一個(gè)指定信號(hào)前，會(huì)被迫在一個(gè)確定的或者需要的地方停下來(lái)，從而保持同步或互斥。經(jīng)典的整型信號(hào)量＝》經(jīng)記錄型信號(hào)量＝》信號(hào)量集機(jī)制CPU忙等造成死鎖不易死鎖，可能導(dǎo)致資源利用率低99一、信號(hào)量的概念

信號(hào)量，也叫信號(hào)燈，一般是由兩個(gè)成員組成的數(shù)據(jù)結(jié)構(gòu)，是一個(gè)確定的二元組（S，Q）S是個(gè)具有非負(fù)初值的整型變量，表示該信號(hào)量的值，且S的值只能由定義在信號(hào)量上的P操作原語(yǔ)和V操作原語(yǔ)來(lái)改變；Q是個(gè)初始狀態(tài)為空的隊(duì)列。

100另一定義：信號(hào)量類型是個(gè)復(fù)合類型，其一個(gè)分量是個(gè)整型分量S，另一個(gè)分量是個(gè)等待隊(duì)列指針Q（一個(gè)是指向PCB的指針，當(dāng)多個(gè)進(jìn)程都等待同一信號(hào)量時(shí)，它們就排成一個(gè)隊(duì)列，由信號(hào)量的指針項(xiàng)指出該隊(duì)列的頭。）

信號(hào)量通?？梢院?jiǎn)單反映出相應(yīng)資源的使用情況，它與P，V操作原語(yǔ)一起使用可實(shí)現(xiàn)進(jìn)程的同步和互斥。

101**信號(hào)量的整型分量S的值的物理含義：當(dāng)S≥0時(shí)，表示某類可用資源的數(shù)目，或者說(shuō)表示可以執(zhí)行P操作而不會(huì)被阻塞的進(jìn)程的數(shù)目；當(dāng)S＜0時(shí)，其絕對(duì)值表示信號(hào)量S的阻塞隊(duì)列中的進(jìn)程數(shù)，即系統(tǒng)中因請(qǐng)求該類資源而被阻塞的進(jìn)程的數(shù)目，亦即被信號(hào)燈擋住的進(jìn)程數(shù)目，這些進(jìn)程需要?jiǎng)e的進(jìn)程發(fā)出相應(yīng)的信號(hào)燈來(lái)喚醒。

另外，S的值只能由P、V操作來(lái)改變。

102二、P、V操作原語(yǔ)

P代表荷蘭語(yǔ)的proberen，意為“測(cè)試”；V代表荷蘭語(yǔ)的verhogen，意為“增加”?，F(xiàn)在很多國(guó)外的文獻(xiàn)都使用wait和signal操作（或者down和up操作）代替P、V操作。1031．定義在信號(hào)量S上的P（S）原語(yǔ)操作的算法描述為：

（1）S減1；（2）若S≥0，則調(diào)用P（S）的進(jìn)程返回，繼續(xù)執(zhí)行；（3）若S<0，調(diào)用者進(jìn)程調(diào)用阻塞原語(yǔ)Block（Q），把自己插入到信號(hào)量S的阻塞隊(duì)列Q中(把相應(yīng)的PCB連入該信號(hào)量隊(duì)列的末尾，并放棄處理機(jī)，進(jìn)入等待)。

1042．定義在信號(hào)量S上的V（S）原語(yǔ)操作的算法描述為：

（1）S加1；（2）若S>0，則調(diào)用V（S）的進(jìn)程繼續(xù)執(zhí)行，返回；（3）若S<0，調(diào)用者進(jìn)程調(diào)用喚醒原語(yǔ)Wakeup（Q）把信號(hào)量S的阻塞隊(duì)列Q中的隊(duì)首進(jìn)程移出并喚醒，返回。105P(s)入口S-1=>SS≥0Block(Q)

返回YNP(S)操作的算法描述106V(s)入口S+1=>SS>0Wakeup(Q)

返回YNV(S)操作的算法描述107注意P（S）操作和V（S）操作的物理含義：

P（S）操作表示“等信號(hào)”，即測(cè)試一個(gè)要等的信號(hào)是否到達(dá)；V（S）操作表示“發(fā)信號(hào)”。這個(gè)信號(hào)在實(shí)現(xiàn)同步時(shí)就是“合作者的伙伴進(jìn)程已完成前趨任務(wù)”，在實(shí)現(xiàn)互斥時(shí)就是“臨界資源可用”。另外，在互斥問(wèn)題中，每執(zhí)行一次P（S）操作的含義，也可理解為進(jìn)程請(qǐng)求一個(gè)單位的S類資源；每執(zhí)行一次

V（S）操作的含義，也可理解為進(jìn)程釋放一個(gè)單位的S類資源。

108三、用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥

用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥也一樣簡(jiǎn)單，只需在相關(guān)進(jìn)程的臨界區(qū)的前后分別施以P操作和V操作即可，即在相關(guān)進(jìn)程的程序里由P操作和V操作原語(yǔ)緊夾著臨界區(qū)，就能保證這些進(jìn)程互斥地進(jìn)入各自的臨界區(qū)。這里所用信號(hào)量的初值一般為1，表示臨界資源未被占用，且其可用數(shù)目為1。

用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥的效率更高一些，因?yàn)镻操作中引入了阻塞機(jī)制，所以消除了CPU忙等現(xiàn)象。109P(S)V(S)P(S)V(S)P(S)V(S)P1P2P3互斥區(qū)110一個(gè)簡(jiǎn)化的異地售票程序，假設(shè)幾乎同時(shí)兩地有兩個(gè)乘客要購(gòu)買同一班次的車票各一張

兩個(gè)終端售票程序都要訪問(wèn)存放該次車票的數(shù)據(jù)單元Pk假設(shè)它們都要對(duì)Pk做如下的訪問(wèn)操作“若Pk≥1，則將Pk的值減1，賣出一張票，返回否則打印‘無(wú)票’信息，返回”如果不加任何限制讓這兩個(gè)程序并發(fā)執(zhí)行的話，結(jié)果可能會(huì)導(dǎo)致錯(cuò)誤，甚至兩地各賣出一張重票的現(xiàn)象111例2.1試用P、V操作實(shí)現(xiàn)火車聯(lián)網(wǎng)訂票系統(tǒng)中北京、天津兩地的兩個(gè)終端售票進(jìn)程發(fā)售同一班次車票的過(guò)程。主要步驟是：

（1）分析清楚題目涉及的進(jìn)程間的制約關(guān)系。（2）設(shè)置信號(hào)量（包括信號(hào)量的個(gè)數(shù)和初值，對(duì)于同步問(wèn)題還要寫(xiě)出信號(hào)量的物理含義）。（3）給出進(jìn)程相應(yīng)程序的算法描述或流程控制，并把P、V操作加到程序的適當(dāng)處。

112北京售票終端進(jìn)程：①根據(jù)顧客訂票要求找到公共數(shù)據(jù)單元PK；②P（S）；③把PK的值讀到工作寄存器R1中；④根據(jù)顧客訂票數(shù)修改R1；⑤將R1的值回寫(xiě)到PK中；

⑥V（S）；⑦售出顧客所訂的票，返回；

113天津售票終端進(jìn)程：

①根據(jù)顧客訂票要求找到公共數(shù)據(jù)單元PK；②P（S）；③把PK的值讀到工作寄存器R2中；④根據(jù)顧客訂票數(shù)修改R2；⑤將R1的值回寫(xiě)到PK中；⑥V（S）；⑦售出顧客所訂的票，返回；1142.6進(jìn)程的同步(synchronism)：

——你等我，我也等你

多道程序系統(tǒng)中，許多進(jìn)程之間可能存在以下兩種制約關(guān)系：

1.源于資源共享的直接制約關(guān)系（互斥）

2.源于合作相互的間接制約關(guān)系（同步）后者即一種合作進(jìn)程在獨(dú)自并發(fā)執(zhí)行過(guò)程中的某些確定的時(shí)序點(diǎn)上“你等我，我也等你”的同步約束，前者可視為后者的特例（前面已經(jīng)介紹）。1151.資源共享關(guān)系很多進(jìn)程之間彼此無(wú)關(guān)，它們并不知道其它進(jìn)程的存在。例如在分時(shí)系統(tǒng)中，系統(tǒng)分別為每個(gè)用戶（終端）建立一個(gè)進(jìn)程。但這些進(jìn)程既然同處于一個(gè)系統(tǒng)中，也就必然存在著資源共享的關(guān)系，如共享CPU和I/O設(shè)備等。此時(shí)，進(jìn)程的主要任務(wù)，是保證各個(gè)進(jìn)程能互斥地訪問(wèn)臨界資源。所以，系統(tǒng)中的資源應(yīng)該不允許用戶進(jìn)程直接使用，而應(yīng)該由系統(tǒng)同一分配。例如：在僅有一臺(tái)打印機(jī)的系統(tǒng)中，兩個(gè)進(jìn)程提出打印請(qǐng)求2.相互合作關(guān)系例如輸入進(jìn)程、計(jì)算進(jìn)程、打印進(jìn)程合作完成一批數(shù)據(jù)的輸入、計(jì)算和打印時(shí)的關(guān)系；中斷響應(yīng)過(guò)程；生活中下棋、看病時(shí)等化驗(yàn)結(jié)果等等。

116一、同步的定義進(jìn)程同步：指的是兩個(gè)或多個(gè)進(jìn)程為了合作完成同一個(gè)任務(wù)，在執(zhí)行速度或某些個(gè)確定的時(shí)序點(diǎn)上必須相互協(xié)調(diào)，即一個(gè)進(jìn)程的執(zhí)行依賴于另一個(gè)進(jìn)程——其合作伙伴的消息，當(dāng)一個(gè)進(jìn)程到達(dá)了某一確定點(diǎn)而沒(méi)有得到合作伙伴發(fā)來(lái)的“已完成某些操作”的消息時(shí)必須等待，直到該消息到達(dá)被喚醒后，才能繼續(xù)向前推進(jìn)。進(jìn)程同步是多道程序系統(tǒng)中進(jìn)程之間存在的一種主要源于進(jìn)程間合作的制約關(guān)系，也稱直接制約關(guān)系。

117父子進(jìn)程就是典型的合作進(jìn)程：

它們之間的同步關(guān)系有時(shí)也被形象地稱為“生產(chǎn)者與消費(fèi)者”之間的關(guān)系，“產(chǎn)品”（即生產(chǎn)者進(jìn)程的輸出，亦即消費(fèi)者進(jìn)程的輸入）是它們的紐帶，它們?cè)趫?zhí)行過(guò)程中的某個(gè)或某些確定的時(shí)序點(diǎn)上有著固定的前趨后繼的同步約束，即先“生產(chǎn)”后“消費(fèi)”，這是一種“你等我”的關(guān)系。而在稍微復(fù)雜一點(diǎn)的進(jìn)程同步問(wèn)題里，合作進(jìn)程間的“生產(chǎn)者與消費(fèi)者”的關(guān)系或身份是可以經(jīng)常轉(zhuǎn)換的，因此，這些合作進(jìn)程在執(zhí)行過(guò)程中就會(huì)出現(xiàn)時(shí)而你等我，時(shí)而我等你的現(xiàn)象。

118進(jìn)程同步和互斥間的關(guān)系：相似處：進(jìn)程的互斥實(shí)際上是進(jìn)程同步的一種特殊情況；進(jìn)程的互斥和同步統(tǒng)稱為進(jìn)程同步。差別：進(jìn)程互斥是進(jìn)程間共享資源的使用權(quán)，這種競(jìng)爭(zhēng)沒(méi)有固定的必然聯(lián)系，哪個(gè)進(jìn)程競(jìng)爭(zhēng)到使用權(quán)就歸那個(gè)進(jìn)程使用，直到不需要使用時(shí)再歸還；而進(jìn)程同步則涉及共享資源的并發(fā)進(jìn)程間有一種必然的聯(lián)系，當(dāng)進(jìn)程必須同步時(shí)，即使無(wú)進(jìn)程在使用共享資源時(shí)，那么尚未得到同步消息的進(jìn)程也不能去使用這個(gè)資源。119

P、V操作也都是配對(duì)出現(xiàn)，但對(duì)同一個(gè)信號(hào)量的P、V操作卻不是同時(shí)出現(xiàn)在每一個(gè)進(jìn)程的程序里，而是分別出現(xiàn)在一個(gè)進(jìn)程和它的合作伙伴的代碼中。而且P、V操作的出現(xiàn)位置都在各個(gè)合作進(jìn)程中確定的時(shí)序點(diǎn)，即一個(gè)生產(chǎn)者進(jìn)程在完成了前趨的生產(chǎn)任務(wù)后，應(yīng)立即給合作伙伴——消費(fèi)者進(jìn)程發(fā)送一條“已完成前趨生產(chǎn)任務(wù)”的消息，這要執(zhí)行V操作；而后繼的消費(fèi)者進(jìn)程在消費(fèi)前，應(yīng)該執(zhí)行對(duì)同一個(gè)信號(hào)量的P操作，以測(cè)試其合作伙伴——生產(chǎn)者進(jìn)程“已完成前趨生產(chǎn)任務(wù)”的消息是否到來(lái)，如果到來(lái)就開(kāi)始消費(fèi)，否則就阻塞自己。

二、用P、V操作原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步120解答這類進(jìn)程同步問(wèn)題的主要步驟也是三大步：

(1)分析清楚題目涉及的進(jìn)程間的制約關(guān)系(2)設(shè)置信號(hào)量（包括信號(hào)量的個(gè)數(shù)和初值及其物理含義），合作進(jìn)程間需要收發(fā)幾條消息相應(yīng)就設(shè)置幾個(gè)信號(hào)量。同步信號(hào)量的初值一般為0，表示……

(3)給出進(jìn)程相應(yīng)程序的算法描述或流程控制，并把P、V操作加到程序的適當(dāng)處。

121＝》例2.2

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

公用緩沖池，有n個(gè)緩沖區(qū)一組生產(chǎn)者生產(chǎn)產(chǎn)品一組消費(fèi)者取走產(chǎn)品122生產(chǎn)者－消費(fèi)者問(wèn)題是相互合作進(jìn)程關(guān)系的一種抽象

輸入——計(jì)算——打印

生產(chǎn)者消費(fèi)者生產(chǎn)者消費(fèi)者系統(tǒng)中使用資源的進(jìn)程——消費(fèi)者系統(tǒng)中釋放同類資源的進(jìn)程——生產(chǎn)者123問(wèn)題分析：

①生產(chǎn)者—消費(fèi)者之間的同步關(guān)系表現(xiàn)為：一旦緩沖池中所有緩沖區(qū)均裝滿產(chǎn)品時(shí)，生產(chǎn)者必須等待消費(fèi)者提供空緩沖區(qū)；一旦緩沖池中所有緩沖區(qū)全為空時(shí)，消費(fèi)者必須等待生產(chǎn)者提供滿緩沖區(qū)。

②生產(chǎn)者—消費(fèi)者之間還有互斥關(guān)系：由于緩沖池是臨界資源，所以任何進(jìn)程在對(duì)緩沖區(qū)進(jìn)行存取操作時(shí)都必須和其他進(jìn)程互斥進(jìn)行。

124問(wèn)題解答：

①所用信號(hào)量設(shè)置如下：

Ⅰ）同步信號(hào)量empty，初值為n，表示消費(fèi)者已把緩沖池中全部產(chǎn)品取走，有n個(gè)空緩沖區(qū)可用。

Ⅱ）同步信號(hào)量full，初值為0，表示生產(chǎn)者尚未把產(chǎn)品放入緩沖池，有0個(gè)滿緩沖區(qū)可用。

Ⅲ）互斥信號(hào)量mutex，初值為1，以保證同時(shí)只有一個(gè)進(jìn)程能夠進(jìn)入臨界區(qū)，訪問(wèn)緩沖池。

125②用信號(hào)量機(jī)制解決生產(chǎn)者—消費(fèi)者問(wèn)題的算法描述如下：生產(chǎn)者i

消費(fèi)者j生產(chǎn)出一產(chǎn)品；

P（full）；P（empty）；

P（mutex）；P（mutex）；

從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；

V（mutex）；V（mutex）；

V（empty）；V（full）；

消費(fèi)該產(chǎn)品；

126如果將生產(chǎn)者的兩個(gè)P操作對(duì)調(diào)？？生產(chǎn)者i

消費(fèi)者j生產(chǎn)出一產(chǎn)品；

P（full）；P（mutex）；

P（mutex）；P（empty）

；

從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；

V（mutex）；V（mutex）；

V（empty）；V（full）

；

消費(fèi)該產(chǎn)品；127如果將消費(fèi)者的兩個(gè)P操作對(duì)調(diào)？？生產(chǎn)者i

消費(fèi)者j生產(chǎn)出一產(chǎn)品；

P（mutex）；P（empty

）；

P（full）；P（mutex

）

；

從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；

V（mutex）；V（mutex

）；

V（empty）；V（full

）

；

消費(fèi)該產(chǎn)品；128如果將兩個(gè)V操作對(duì)調(diào)？？生產(chǎn)者i

消費(fèi)者j生產(chǎn)出一產(chǎn)品；

P（full）；P（mutex）；

P（mutex）；P（empty）

；

從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；

V（mutex）；V（full）；

V（empty）；V（mutex）

；

消費(fèi)該產(chǎn)品；129＝》例2.3讀者——寫(xiě)者問(wèn)題

該問(wèn)題描述的是：一組讀者與一組寫(xiě)者循環(huán)訪問(wèn)共享的同一個(gè)數(shù)據(jù)對(duì)象。讀者：指能對(duì)共享數(shù)據(jù)對(duì)象讀的進(jìn)程，寫(xiě)者：指對(duì)共享數(shù)據(jù)對(duì)象只要求寫(xiě)的進(jìn)程。規(guī)定：多個(gè)讀者可以同時(shí)讀這個(gè)數(shù)據(jù)對(duì)象，但決不允許多個(gè)寫(xiě)者同時(shí)對(duì)這個(gè)數(shù)據(jù)對(duì)象進(jìn)行寫(xiě)操作，也不允許讀者、寫(xiě)者同時(shí)訪問(wèn)這個(gè)數(shù)據(jù)對(duì)象。

130讀者—寫(xiě)者問(wèn)題是共享數(shù)據(jù)對(duì)象的非合作進(jìn)程關(guān)系的一種抽象

如文件管理模塊中讀文件、寫(xiě)文件等許多操作進(jìn)程之間異地售票程序也可看成是寫(xiě)者與寫(xiě)者的問(wèn)題讀者—寫(xiě)者問(wèn)題是指保證一個(gè)寫(xiě)者進(jìn)程必須與其他寫(xiě)者或讀者進(jìn)程互斥地訪問(wèn)一個(gè)共享數(shù)據(jù)對(duì)象的同步問(wèn)題。131問(wèn)題分析：

①讀者—寫(xiě)者之間的互斥關(guān)系：

寫(xiě)者與寫(xiě)者的互斥、寫(xiě)者與讀者的互斥。設(shè)一個(gè)公用的初值為1的互斥信號(hào)量RW_mutex？但是實(shí)現(xiàn)了讀者與讀者的互斥。引入一個(gè)讀者計(jì)數(shù)器變量RC。②讀者—讀者之間又有了互斥關(guān)系：

再設(shè)一個(gè)讀者公用的初值為1的互斥信號(hào)量R_mutex

實(shí)現(xiàn)各個(gè)讀者間互斥的訪問(wèn)RC132問(wèn)題解答：

①所用信號(hào)量和其他變量設(shè)置如下：Ⅰ）互斥信號(hào)量RW_mutex，初值為1，用于實(shí)現(xiàn)寫(xiě)者與其他寫(xiě)者或讀者互斥地訪問(wèn)共享的數(shù)據(jù)對(duì)象。Ⅱ）互斥信號(hào)量R_mutex，初值為1，用于實(shí)現(xiàn)諸讀者互斥地訪問(wèn)讀者計(jì)0數(shù)器變量。Ⅲ）整型變量RC，初值為0，用于對(duì)讀者進(jìn)行記數(shù)。

133②用信號(hào)量機(jī)制解決讀者—寫(xiě)者問(wèn)題的算法描述如下：

讀者寫(xiě)者P（R_mutex）；

P（RW_mutex）；若RC=0則

P（RW_mutex）；對(duì)數(shù)據(jù)對(duì)象進(jìn)行寫(xiě)操作；RC加1；

（RW_mutex）；V（R_mutex）；讀數(shù)據(jù)對(duì)象；P（R_mutex）；RC減1；若RC=0則

V（RW_mutex）；

V（R_mutex）；

134＝》例2.4試用用信號(hào)量機(jī)制描述兩人下象棋的過(guò)程。兩人下象棋的過(guò)程可以概括為：一開(kāi)始只能是“紅先黑后”，以后兩人要循環(huán)輪流走子，直至某一方獲勝或雙方和棋為止。這是個(gè)只有一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者的生產(chǎn)者——消費(fèi)者問(wèn)題，是個(gè)典型的“你等我，我也等你”的問(wèn)題。紅方是總的前趨任務(wù)——生產(chǎn)者進(jìn)程，黑方是總的后繼任務(wù)——消費(fèi)者進(jìn)程，但由于下棋過(guò)程必須輪流走子，所以紅黑雙方的生產(chǎn)者消費(fèi)者身份會(huì)輪流改變。棋盤(pán)則是生產(chǎn)者與消費(fèi)者共享的緩沖。

135二人對(duì)弈過(guò)程是個(gè)純粹的同步過(guò)程解答：①所用信號(hào)量設(shè)置如下：

Ⅰ）同步信號(hào)量hei，初值為1，表示黑方已走子,開(kāi)始時(shí)可使紅方先行不受阻。

Ⅱ）同步信號(hào)量hong，初值為0，表示紅方尚未走子，開(kāi)始時(shí)可使黑方先行受阻。136②用信號(hào)量機(jī)制描述的二人下象棋過(guò)程如下：

P（hei）；P（hong）；若被黑方將死，則投子認(rèn)負(fù)，結(jié)束；若被紅方將死則投子認(rèn)負(fù)，結(jié)束；若同意與黑方作和，則結(jié)束；若同意與紅方作和，則結(jié)束；否則，根據(jù)棋局思考后走一子；否則，根據(jù)棋局思考后走一子；V（hong）；V（hei）；137＝》例2.5某小型超級(jí)市場(chǎng)，可容納50人同時(shí)購(gòu)物。入口處有籃子，每個(gè)購(gòu)物者可拿一只籃子入內(nèi)購(gòu)物。出口處結(jié)帳，并歸還籃子（出、入口禁止多人同時(shí)通過(guò)）。試用信號(hào)量和P、V操作寫(xiě)出購(gòu)物者的同步算法。這是個(gè)典型的進(jìn)程互斥問(wèn)題138解答:①所用信號(hào)量設(shè)置如下：Ⅰ）互斥信號(hào)量S，初值為50，用以保證最多可以有50個(gè)購(gòu)物者同時(shí)進(jìn)入超市。Ⅱ）互斥信號(hào)量mutex，初值為1，用以保證同時(shí)只能有一個(gè)購(gòu)物者進(jìn)程進(jìn)入出入口拿起籃子或者結(jié)帳后放下籃子。②用信號(hào)量機(jī)制給出的每個(gè)購(gòu)物者購(gòu)物過(guò)程的算法描述如下：139購(gòu)物者i進(jìn)程（解法一）購(gòu)物者i進(jìn)程（解法二）：P（S）；P（S）；P（mutex）；P（mutex1）；從入口處進(jìn)超市，并取一只籃子；同左；V（mutex）；V（mutex1）；進(jìn)超市內(nèi)選購(gòu)商品；同左；P（mutex）；P（mutex2）；到出口結(jié)帳，并歸還籃子；同左；V（mutex）；V（mutex2）；從出口離開(kāi)超市；同左；V（S）；V（S）；

↓↓結(jié)束.結(jié)束.

140＝》例2.6桌上有個(gè)只能盛得下一個(gè)水果的空盤(pán)子。爸爸可向盤(pán)中放蘋(píng)果或桔子，兒子專等吃盤(pán)中的桔子，女兒專等吃盤(pán)中的蘋(píng)果。規(guī)定：當(dāng)盤(pán)子空時(shí)，一次只能放入一個(gè)水果供吃者取用。試用信號(hào)量和P、V操作實(shí)現(xiàn)爸爸、兒子和女兒這三個(gè)循環(huán)進(jìn)程之間的同步。

本題屬于生產(chǎn)者——消費(fèi)者問(wèn)題的變形，相當(dāng)于一個(gè)能生產(chǎn)兩種產(chǎn)品的生產(chǎn)者（爸爸）向兩個(gè)消費(fèi)者（兒子和女兒）提供產(chǎn)品的同步問(wèn)題。因此，可參考生產(chǎn)者與消費(fèi)者問(wèn)題的解法。

141解答：①所用信號(hào)量設(shè)置如下：Ⅰ）同步信號(hào)量empty，初值為1，表示盤(pán)子是空的，即兒子或女兒已把盤(pán)中的水果取走。Ⅱ）同步信號(hào)量orange，初值為0，表示爸爸尚未把桔子放入盤(pán)中。Ⅲ）同步信號(hào)量apple，初值為0，表示爸爸尚未把蘋(píng)果放入盤(pán)中。

142②使用信號(hào)量機(jī)制的三個(gè)進(jìn)程的同步描述如下：

爸爸進(jìn)程（P）：兒子進(jìn)程（C1）：女兒進(jìn)程（C2）：P（empty）；

P（orange）；P（apple）；將水果放入盤(pán)中；從盤(pán)中取出桔子；從盤(pán)中取出蘋(píng)果；若放入的是桔子，

V（empty）；V（empty）；則V（orange）；吃桔子；吃蘋(píng)果；否則，V（apple）；143＝》例2.7

設(shè)A、B兩點(diǎn)之間是一段東西向的單行車道，現(xiàn)在要設(shè)計(jì)一個(gè)AB路段自動(dòng)管理系統(tǒng)，管理規(guī)則如下：當(dāng)AB間有車輛在行駛時(shí)同方向的車可以同時(shí)駛?cè)階B段，但另一方向的車必須在AB段外等待；當(dāng)AB段之間無(wú)車輛行駛時(shí)，到達(dá)AB段的任一方向的車都可進(jìn)入AB段，但不能從兩個(gè)方向同時(shí)駛?cè)?，即只能有一個(gè)方向的車駛?cè)?；?dāng)某方向在AB段行駛的車輛駛出了AB段且暫無(wú)車輛進(jìn)入AB段時(shí)，應(yīng)讓另一方向等待的車輛進(jìn)入AB段行駛。試用信號(hào)量和P、V操作管理AB路段車輛的行駛。

144解答：①所用信號(hào)量和其他變量設(shè)置如下：

Ⅰ）整型變量Car_A，初值為0，用于對(duì)從A點(diǎn)（東）駛?cè)階B段的車輛進(jìn)行記數(shù)。Ⅱ）整型變量Car_B，初值為0，用于對(duì)從B點(diǎn)（西）駛?cè)階B段的車輛進(jìn)行記數(shù)。Ⅲ）互斥信號(hào)量mutex，初值為1，用于實(shí)現(xiàn)不同方向的第一輛車互斥駛?cè)階B路段。Ⅳ）互斥信號(hào)量ma，初值為1，用于實(shí)現(xiàn)東西向的車互斥地訪問(wèn)計(jì)數(shù)器變量Car_A。Ⅴ）互斥信號(hào)量mb，初值為1，用于實(shí)現(xiàn)西東向的車互斥地訪問(wèn)計(jì)數(shù)器變量Car_B。

145通過(guò)AB路段向西行駛的車輛i

向東行駛的車輛jP（ma）；P（mb）；若Car_A=0則P（mutex）；若Car_B=0則P（mutex）；Car_A加1；Car_B加1；V（ma）；V（mb）；車輛從A點(diǎn)通過(guò)AB路段到達(dá)B點(diǎn)；車輛從B點(diǎn)通過(guò)AB路段到達(dá)A點(diǎn)；P（ma）；P（mb）；Car_A減1；Car_B減1；Car_A=0則V（mutex）；Car_B=0則V（mutex）；

V（ma）；

V（mb）；

146總結(jié)上述幾個(gè)有趣的實(shí)例的解題過(guò)程，可以得出這樣的結(jié)論：實(shí)現(xiàn)進(jìn)程的同步互斥實(shí)際就是給進(jìn)程的并發(fā)執(zhí)行增加一定的限制，以保證被訪問(wèn)的共享數(shù)據(jù)的完整性和進(jìn)程執(zhí)行結(jié)果的可再現(xiàn)性。147用信號(hào)量機(jī)制解這類題的三個(gè)步驟：（1）分析進(jìn)程間的制約關(guān)系（2）設(shè)置信號(hào)量（3）實(shí)施P、V操作。第一步是基礎(chǔ)、關(guān)鍵，第三步是核心。掌握實(shí)現(xiàn)進(jìn)程互斥與進(jìn)程同步的第三步在形式上差異：即P、V操作總是配對(duì)出現(xiàn)的。但P,V在互斥問(wèn)題中總是出現(xiàn)在同一個(gè)進(jìn)程的代碼中，且緊緊夾著臨界區(qū)；而在同步問(wèn)題中，卻是分別出現(xiàn)在兩個(gè)合作進(jìn)程的代碼中，需要等消息的一方用P操作，相應(yīng)的對(duì)同一信號(hào)量的V操作則在發(fā)出此消息的另一方中。

148練習(xí)題：1、有兩個(gè)用戶進(jìn)程A和B，在運(yùn)行過(guò)程中都要使用系統(tǒng)中的一臺(tái)打印機(jī)輸出計(jì)算結(jié)果。試說(shuō)明A、B兩進(jìn)程之間存在什么樣的制約關(guān)系？為保證這兩個(gè)進(jìn)程能正確地打印出各自的結(jié)果，請(qǐng)用信號(hào)量和P、V操作寫(xiě)出各自的有關(guān)申請(qǐng)、使用打印機(jī)的代碼。要求給出信號(hào)量的含義和初值。

149解：(1)A、B兩進(jìn)程之間存在互斥的制約關(guān)系。因?yàn)榇蛴C(jī)屬于臨界資源，必須一個(gè)進(jìn)程使用完之后另一個(gè)進(jìn)程才能使用。（2）mutex：用于互斥的信號(hào)量，初值為1。

進(jìn)程A

進(jìn)程B...

…

...

…

P(mutex)

P(mutex)

申請(qǐng)打印機(jī)

申請(qǐng)打印機(jī)使用打印機(jī)

使用打印機(jī)

V(mutex)

V(mutex)

…

…

1502、有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一座位列一表目，包括座號(hào)和讀者姓名等，讀者離開(kāi)時(shí)要消掉登記