操作系統(tǒng)整合復(fù)習(xí)題

1、第一章：引論1.操作系統(tǒng)的定義：操作系統(tǒng)是計算機系統(tǒng)中的系統(tǒng)軟件，是能有效地組織和管理計算機系統(tǒng)中的硬件和軟件資源，合理地組織計算機工作流程，控制程序的執(zhí)行，并向用戶提供各種服務(wù)功能，使得用戶能夠合理，方便，有效地使用計算機，使整個計算機系統(tǒng)高效運行的一組程序模塊的集合。2.操作系統(tǒng)的發(fā)展史:人工操作方式缺點：用戶獨占全機，處理機等待人工操作。為了解決人機矛盾及處理機和I/O設(shè)備之間速度不匹配的矛盾。脫機I/0方式（外圍機是核心）口單道批處理操作自動地將一個作業(yè)一個作業(yè)的進行處理，直至磁盤上的作業(yè)全部系統(tǒng)完成?？诤锰帲禾岣咛幚頇C的利用率（可同時把若干道程序裝入內(nèi)存，并且單道批處理操作系統(tǒng)替地執(zhí)

2、行。）提高內(nèi)存和I/O的設(shè)備利用率（內(nèi)存中裝入多道程序，并允許并發(fā)執(zhí)行。）增加系統(tǒng)吞吐量特征：多道性（允許并發(fā)，提高了資源利用率和增加系統(tǒng)吞吐量）無序性調(diào)度性3.分時系統(tǒng)與實時系統(tǒng)的比較:分時系統(tǒng)實時系統(tǒng)多路性為多個終端用戶服務(wù)。對多路的現(xiàn)場信息進行采集以及對多個對象或多個執(zhí)行機構(gòu)進行控制。獨立性每個用戶各占一個終端，彼此獨立操作。信息的采集和對對象的控制也彼此互不干擾。及時性用戶的請求時間通常是2-3S及時性由控制對象所要求的開始截止時間或完成截止時間來確定的。交互性用戶可以請求系統(tǒng)提供各方面的服務(wù)，如文件編輯，數(shù)據(jù)處理和資源共享。僅限于訪問系統(tǒng)中某些特定的專業(yè)服務(wù)程序。可靠性要求可靠。要求

3、高度可靠。通常采取了多級容錯措施保證數(shù)據(jù)的安全。4.操作系統(tǒng)的幾種觀點:操作系統(tǒng)軟件的觀點有作為軟件的外在和內(nèi)在特性。外在特性：即操作命令定義集和界面，完全確定了操作系統(tǒng)這個軟件的使用方式。內(nèi)在特性：具有一般軟件的結(jié)構(gòu)特點，但又具有一般軟件不具備的特殊結(jié)構(gòu)。計算機系統(tǒng)資源管理的觀點提供一些機制去協(xié)調(diào)程序間的競爭與同步，提供機制對資源進行合理使用。處理機管理：用于分配和控制處理機。存儲器管理：負責(zé)內(nèi)存的分配和回收。I/O設(shè)備管理：負責(zé)I/O設(shè)備的分配和操縱。文件管理：負責(zé)文件的存取，共享和保護。進程的觀點操作系統(tǒng)=若干個可以同時獨立運行的程序(進程)+一個對這些程序進行協(xié)調(diào)的核心(進程完成任務(wù)，

4、核心則控制盒協(xié)調(diào)這些進程的運行，解決進程之間的通信。)用戶與計算機硬件系統(tǒng)之間接口的觀點注意這個接口是軟件接口。用戶可以使用兩種方式來使用計算機：(1)命令方式(2)系統(tǒng)調(diào)用方式虛機器的觀點用戶不直接使用硬件計算機，而是通過操作系統(tǒng)來控制盒使用計算機。服務(wù)提供者觀點從用戶角度看，操作系統(tǒng)為用戶提供功能更強，服務(wù)質(zhì)量更高，使用戶更方便，靈活的虛擬計算機。包括：程序執(zhí)行，I/0操作，文件系統(tǒng)操作，通信，差錯檢測5.操作系統(tǒng)的功能:處理器管理(在多道程序環(huán)境下，處理器的分配和運行以進程為單位，故可歸結(jié)為對進程的管理。)進程控制：負責(zé)進程的創(chuàng)建，撤銷及狀態(tài)轉(zhuǎn)換。進程同步：對并發(fā)執(zhí)行的進程進行協(xié)調(diào)。進程

5、通信：負責(zé)完成進程間的信息交換。進程調(diào)度：按一定算法進行處理器分配。/A-fztXPAxVTE存儲命官理(1)內(nèi)存分配：按一定的策略為每道程序分配內(nèi)存。(2)內(nèi)存保護：保證各程序在自己的內(nèi)存區(qū)域內(nèi)運行而互不干擾。(3)內(nèi)存擴充設(shè)備管理文件管理(1)設(shè)備分配。(2)設(shè)備傳輸控制：實現(xiàn)物理的輸入輸出操作，即啟動設(shè)備，中斷處理，結(jié)束處理。(3)設(shè)備獨立性：用戶程序之間的設(shè)備與物理設(shè)備無關(guān)。有效的支持文件的存儲，檢索和修改，解決文件的共享，保密和保護問題。(1)文件存儲空間的管理。目錄管理。(3)文件操作管理。(4)文件保護。用戶接口三種用戶接口:(1)命令接口。(2)程序接口:也稱為系統(tǒng)調(diào)用。(3)

6、圖形接口:是命令接口的圖形化。并發(fā)性注意并行性跟并發(fā)性的區(qū)別：并行性：兩個或多個時間在同一時刻發(fā)生。6.操作系統(tǒng)的特征并發(fā)性：兩個或多個事件在同一時間間隔內(nèi)發(fā)生。共享性系統(tǒng)中的資源可以供多個并發(fā)執(zhí)行的進程共同使用。互斥共享：例如打印機，磁帶機。同時訪問：例如磁盤以及一些重入碼編寫的文件。虛擬性通過某種技術(shù)把一個物理實體變成若干個邏輯上的對應(yīng)物。異步性在多道程序環(huán)境下，由于資源等因素的限制，程序是以走走停停的方式運行的。系統(tǒng)中的每道程序何時執(zhí)行，多道程序間的執(zhí)行順序以及完成每道程序所需的時間都是不確定的，因而也是不可未知的。7 .微內(nèi)核特點：(1)足夠小的內(nèi)核：微內(nèi)核紙包括操作系統(tǒng)中最基本的部分

7、，是操作系統(tǒng)的小核心，它將各種操作系統(tǒng)共同需要的核心功能提煉出來，形成微內(nèi)核的基本功能。這些基本功能包括：進程管理，低級存儲器管理，中斷和陷入的處理。(2)基于客戶/服務(wù)器模式：操作系統(tǒng)最基本的部分放入內(nèi)核中，大部分放在內(nèi)核外的一組服務(wù)器(進程)中實現(xiàn)。(3)應(yīng)用機制和策略分離的技術(shù)：機制是實現(xiàn)某一功能的具體執(zhí)行機構(gòu)，而策略處于系統(tǒng)的高層。(4)面向?qū)ο蟮募夹g(shù)：微內(nèi)核是操作系統(tǒng)發(fā)展的最新成果，具有提高系統(tǒng)的擴展性，增強系統(tǒng)的可靠性，可移植性和可以支持分布式系統(tǒng)，采用面向?qū)ο蠹夹g(shù)等特點。主要思想：在操作系統(tǒng)內(nèi)核中只留下一些最基本的功能，而將其他服務(wù)盡可能地從內(nèi)核中分離出去，用若千個運行在用戶態(tài)下

8、的進程來實現(xiàn)。優(yōu)點：(1)每個服務(wù)進程運行在獨立的用戶進程中，即某個服務(wù)器失敗或產(chǎn)生問題時不會引起系統(tǒng)其他服務(wù)器和其他組成部分的崩潰，可靠性好。(2)系統(tǒng)具有很好的靈活性，只要接口規(guī)范，操作系統(tǒng)可以方便地增刪服務(wù)功能。(3)便于維護，即修改服務(wù)器的代碼不會影響、(4)系統(tǒng)其他部分。缺點：效率不高，因為所有的用戶進程都要通過微內(nèi)核相互通信，所以微內(nèi)核本身就成了系統(tǒng)的瓶頸，尤其是通信頻繁的系統(tǒng)。8 .客戶/服務(wù)器模式即C/S模式，普通用戶進程可以通過內(nèi)核像服務(wù)器進程發(fā)送請求，以取得操作系統(tǒng)的服務(wù)。優(yōu)點：既允許數(shù)據(jù)的分布處理和存儲，又便于集中管理，靈活性和可擴充性強，容易修改。缺點：存在不可靠性和瓶

9、頸問題。(服務(wù)器是瓶頸)9 .操作系統(tǒng)的硬件環(huán)境：(1)特權(quán)指令和非特權(quán)指令特權(quán)指令在指令系統(tǒng)中那些只能由操作系統(tǒng)使用的指令。非特權(quán)指令用戶只能使用的指令。問題：如果用戶想要使用特權(quán)指令，只能通過系統(tǒng)調(diào)用來實現(xiàn)，否則會使系統(tǒng)陷入混亂(2)處理機的狀態(tài):核心態(tài)(管態(tài)，系統(tǒng)態(tài))全部指令可以執(zhí)行，可以使用所有資源并具有改變處理機狀態(tài)的能力。用戶態(tài)(目態(tài))只有非特權(quán)指令能執(zhí)行。注意：在系統(tǒng)調(diào)用時，將由用戶態(tài)轉(zhuǎn)到核心態(tài)(3)存儲器的類型:分類定義作用(舉例)讀/寫存儲器可以把數(shù)據(jù)存入其中任一地址單元，并且可在以后的任何時候把數(shù)據(jù)讀出來或者重新存入別的數(shù)據(jù)。通常被稱為隨機訪問存儲器（RAM）用于存放隨機存

10、取的程序和數(shù)據(jù)。只讀型存儲器只能從其中讀取數(shù)據(jù)。通常被稱為只讀存儲器（ROM）（4）存儲器的層次結(jié)構(gòu):磁帶機寄存器0高速緩存O內(nèi)存儲器O硬盤存儲0光盤存儲器（存儲裝置）達到提高存儲系統(tǒng)效能的關(guān)鍵在于：程序的存儲訪問局部性原理。注意：按層次結(jié)構(gòu)來設(shè)計操作系統(tǒng)，就是將操作系統(tǒng)的所有功能模塊按功能的調(diào)用次序排列成若干層，使得功能模塊之間只存在單向調(diào)用和單向依賴。優(yōu)點：模塊間的組織和依賴關(guān)系清晰明了。缺點：個功能模塊應(yīng)該放在哪一層，如何有效地進行分層式必須考慮的問題。（5）常用存儲保護機制：界地址寄存器比較簡單，易于實現(xiàn)。在處理機中設(shè)置一對界限寄存器用來存放概用戶作業(yè)內(nèi)存中的下限和上限地址。當(dāng)處理機要

11、訪問內(nèi)存時，如果越界就將程序中斷。存儲鍵每個存儲塊都有一個與其相關(guān)的由二進制組成的內(nèi)存保護鍵附加在每個存儲塊上。（6）緩沖技術(shù)：緩沖區(qū)：是硬件設(shè)備之間進行數(shù)據(jù)傳輸時，專門用來暫存這些數(shù)據(jù)的一個存儲區(qū)域。緩沖技術(shù)的用途：處理機與內(nèi)存之間處理機與其他外部設(shè)備之間設(shè)備與設(shè)備之間目的：解決部件之間速度不匹配的問題。（7）中斷：含義：指處理機對系統(tǒng)中或者系統(tǒng)外發(fā)生的異步事件的響應(yīng)。分類：可屏蔽中斷（I/O中斷）不可屏蔽中斷（機器內(nèi)部故障，掉電中斷）程序錯誤中斷（溢出，除法錯等中斷）軟件中斷（Trap指令或者終端指令I(lǐng)NT）中斷與異常的區(qū)別：中斷時系統(tǒng)正常功能的一部分，在系統(tǒng)處理完其他事情之后會繼續(xù)執(zhí)行中

12、斷前的進程。異常是由錯誤引起的。（通常異常會引起中斷，而中斷未必是由異常引起的）（8）系統(tǒng)調(diào)用：系統(tǒng)調(diào)用時操作系統(tǒng)提供的用戶接口之一，是由操作系統(tǒng)實現(xiàn)的所有系統(tǒng)調(diào)用所構(gòu)成的集合，即程序接口或應(yīng)用編程接口，是應(yīng)用程序同系統(tǒng)之間的接口。系統(tǒng)調(diào)用把應(yīng)用程序的請求傳給內(nèi)核，調(diào)用相應(yīng)的內(nèi)核函數(shù)完成所需的處理，將處理結(jié)果返回給應(yīng)用程序。組成：進程控制、文件系統(tǒng)控制、系統(tǒng)控制、內(nèi)存管理、網(wǎng)絡(luò)管理、socket控制、用戶管理、進程間通信(9)作業(yè)狀態(tài):提交狀態(tài)通過各種輸入設(shè)備將作業(yè)從外部送入計算機系統(tǒng)的輔助存儲設(shè)備。等待作業(yè)調(diào)度程序調(diào)度。被分配所需資源，然后調(diào)入內(nèi)存，并為其創(chuàng)建進程。作業(yè)調(diào)度程序收回其占用的所

13、有資源，做必要的善后處理。第三章：進程與進程管理1 .前趨圖(有向無循環(huán)圖)圖中每個節(jié)點可以表示一條語句，一個程序段或者一個進程，節(jié)點間的有向邊表示兩個節(jié)點之間存在的偏序或前趨關(guān)系“一”2 .程序的順序執(zhí)行：一個程序中的程序段必須按照某種先后順序執(zhí)行，僅當(dāng)一個操作執(zhí)行完之后才能執(zhí)行后續(xù)操作。特征：順序性嚴(yán)格按照程序所規(guī)定的順序執(zhí)行封閉性程序一旦開始運行，執(zhí)行結(jié)果不受外界因素影響?？稍佻F(xiàn)性只要程序執(zhí)行的初始狀態(tài)和執(zhí)行環(huán)境相同，當(dāng)程序重復(fù)執(zhí)行時，都將獲得相同的結(jié)果。3.程序的并發(fā)執(zhí)行：注意并發(fā)跟并行的區(qū)別:并行兩個或多個事件在同一時刻發(fā)生。并發(fā)兩個或多個事件在同一時間間隔內(nèi)發(fā)生。特征：(相比順序執(zhí)

14、行)間斷性由共享資源而產(chǎn)生的間接制約關(guān)系，這種制約關(guān)系將導(dǎo)致并發(fā)程序具有“執(zhí)行一暫停執(zhí)行一執(zhí)行”這種間接性的活動規(guī)律。失去封閉性程序并發(fā)執(zhí)行時，多個程序共享系統(tǒng)資源，故這些資源的狀態(tài)將由多個程序來改變，程序的運行失去封閉性。致使不可再現(xiàn)性程序并發(fā)執(zhí)行時，由于失去了封閉性，將導(dǎo)致也失去其運行結(jié)果的可再現(xiàn)性。程序和計算不在并發(fā)執(zhí)行時，一個共享程序可為多個用戶作業(yè)調(diào)用，而使該程序處于多個執(zhí)行中，因而再對應(yīng)形成了多個“計算”。注意：引入并發(fā)的目的是為了提高資源的利用率，從而提高系統(tǒng)的效率。程序并發(fā)執(zhí)行，雖然能有效地提高資源利用率和系統(tǒng)吞吐量，但必須采取某種措施使并發(fā)程序保持“可再現(xiàn)性”。4 .多道程序

15、設(shè)計：注意一點：核心是并發(fā)。5 .進程(1)定義：進程是一個程序?qū)δ硞€數(shù)據(jù)集的一次運行活動。(進程是動態(tài)的概念，程序是靜態(tài)的概念)(2)特征：動態(tài)性進程是程序在處理器上的一次執(zhí)行過程過程。并發(fā)性多個進程同時存在于內(nèi)存中，能在一段時間內(nèi)同時運行。引入進程的目的是使程序能于其他程序并發(fā)執(zhí)行，以提高資源利用率。獨立性進程是一個能獨立運行運行的基本單位，也是系統(tǒng)進行資源分配和調(diào)度的獨立單位。異步性進程以各自獨立的，不可預(yù)知的速度向前推進。結(jié)構(gòu)特征為了描述和記錄進程的運動變化過程，引入了進程控制模塊PCBo從結(jié)構(gòu)上看，進程=程序段蝕據(jù)段+PCB(3)3種基本狀態(tài):就緒狀態(tài)進程已獲得除了處理器以外的其他所

16、有資源。執(zhí)行狀態(tài)獲得必要資源在CPU上面執(zhí)行。阻塞狀態(tài)正在執(zhí)行的進程，由于發(fā)生某事件而暫時無法執(zhí)行下去。(注意：當(dāng)進程處于阻塞狀態(tài)時，即使把處理器分配給該進程，也無法運行)三個狀態(tài)相互轉(zhuǎn)換:：進程分配到處理機。：在分時系統(tǒng)中，正在執(zhí)行的進程由于時間片用完而暫時被暫停執(zhí)行。在搶占調(diào)度方式中，一個優(yōu)先級高的進程可以搶占一個正在進行的優(yōu)先級低的進程的處理機：因為某事件而無法執(zhí)行。例如：臨界資源被其他進程訪問。：進程等待的事件發(fā)生而被喚醒。(4)引入掛起狀態(tài):在上面三個狀態(tài)轉(zhuǎn)換的基礎(chǔ)上加入一個掛起狀態(tài)。(5)為什么說PCB是進程存在的唯一標(biāo)識？首先看PCB的作用：是系統(tǒng)為每個進程定義的一個數(shù)據(jù)結(jié)構(gòu)，是

17、為了使程序能獨立運行。PCB是為了保證程序的并發(fā)執(zhí)行。創(chuàng)建進程實質(zhì)是創(chuàng)建PCB,撤銷進程，實質(zhì)上是撤銷PCB.接下來：PCB保存著處理機的狀態(tài)信息，系統(tǒng)總是通過PCB對進程進行控制。(6)進程的創(chuàng)建：一個進程可以創(chuàng)建若干個新的進程，新的進程又可以創(chuàng)建子進程。(一般用前趨圖表示)過程：申請空白進程控制塊f為新進程分配資源f初始化進程控制塊f將新進程插入就緒隊列（7）進程的終止：引起終止事件：正常結(jié)束越界錯誤：程序所訪問的存儲區(qū)已越出該進程的區(qū)域。保護錯誤：以不適當(dāng)?shù)姆椒ㄟM行訪問。特權(quán)指令錯誤：用戶進程試圖去執(zhí)行一條只允許操作系統(tǒng)執(zhí)行的指令。異常結(jié)束：非法指令錯：試圖去執(zhí)行一條不存在的指令。運行超

18、時：執(zhí)行時間超出指定的最大值。等待超時算數(shù)運算錯：進程試圖去執(zhí)行一個被禁止的計算I/0故障外界干預(yù)過程：從PCB中讀出進程的狀態(tài)t終止進程執(zhí)行并設(shè)置調(diào)度標(biāo)志為真f如進程還有子孫進程，也予以終止T，歸還進程的資源給系統(tǒng)t將被終止的進程的PCB從所在隊列移除（8）進程的阻塞和喚醒：阻塞原語：執(zhí)行狀態(tài)f阻塞狀態(tài)（進程自己調(diào)用）過程：停止當(dāng)前進程的運行f保存該進程的CPU現(xiàn)場f停止運行該進程f轉(zhuǎn)到進程調(diào)度程序喚醒原語：阻塞狀態(tài)f就緒狀態(tài)（另一個發(fā)現(xiàn)者調(diào)用）過程：將被喚醒進程從相應(yīng)的等待隊列中移除f將狀態(tài)改為就緒并插入相應(yīng)的就緒隊列（9）調(diào)度方式：非剝奪方式（非搶占方式）即使有優(yōu)先級高的進程進入就緒隊列

19、，也直到正在進行的進程完成或者因某事件而進入阻塞時，才讓優(yōu)先級高的進程執(zhí)行。剝奪方式（搶占方式）當(dāng)有某個優(yōu)先級更高的進程進入就緒隊列，則立即暫停正在執(zhí)行的進程，將處理器分配給優(yōu)先級高的進程。（10）進程調(diào)度算法:先來先服務(wù)（最簡單）：按照進入就緒隊列的先后次序來分配處理器。短作業(yè)優(yōu)先（SJF）:把處理器分配給最快完成的作業(yè)。優(yōu)先級調(diào)度：把處理器分配給優(yōu)先級最高的進程。按進程累確定（系統(tǒng)進程用戶進程）靜態(tài)優(yōu)先級.按作業(yè)的資源要求（申請資源越多，優(yōu)先級越低）進程優(yōu)先級按用戶類型和要求（收費標(biāo)準(zhǔn)越高，優(yōu)先級越高）占用CPU時間長短（時間越長，優(yōu)先級越低）動態(tài)優(yōu)先級I等待CPU時間長短（時間越長，優(yōu)先

20、級越高）時間片輪轉(zhuǎn)（分時系統(tǒng)）：等將所有就緒進程按時間先后排成隊列，進程調(diào)度選擇第一個進程執(zhí)行，并規(guī)定一個時間（時間片），當(dāng)一進程執(zhí)行完規(guī)定的時間，即使沒有執(zhí)行結(jié)束,也把它送到隊尾，輪流進行，直到所有進程都執(zhí)行結(jié)束。時間片的大?。ㄏ到y(tǒng)響應(yīng)時間（進程數(shù)目一定，時間片大小與系統(tǒng)響應(yīng)時間成正比）決定因素：就緒隊列中的進程數(shù)目（響應(yīng)時間一定，時間片大小與進程數(shù)目成反比）系統(tǒng)的處理能力（速度越快，時間片越短）高響應(yīng)比優(yōu)先調(diào)度：綜合了先來先服務(wù)和短作業(yè)優(yōu)先（每次進行作業(yè)調(diào)度時，先計算就緒隊列中的每個作業(yè)的響應(yīng)比）響應(yīng)比=作業(yè)響應(yīng)時間作業(yè)等待時間+估計運行時間估計運行時間估計運行時間多級隊列調(diào)度：根據(jù)進程的

21、性質(zhì)或類型，將就緒隊列劃分為若干個獨立的隊列，每個進程固定地分屬于一個隊列。每個隊列采用一種調(diào)度算法，不同的隊列可以采用不同的調(diào)度算法。例：為交互型任務(wù)設(shè)置一個就緒隊列，該隊列采用時間片輪轉(zhuǎn)調(diào)度算法；為批處理任務(wù)另外設(shè)置一個就緒隊列，該隊列采用先來先服務(wù)調(diào)度算法。（通過調(diào)整進程優(yōu)先級和時間片的大小，可以兼顧多方面的系統(tǒng)目標(biāo)。）優(yōu)先級逐漸降低時間片逐漸增大多級反饋隊列調(diào)度：綜合了時間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級調(diào)度算法。（11）進程與線程的比較:線程進程調(diào)度獨立調(diào)度的基本單位。同一進程中線程的切換不會引起進程的切換。擁有資源的基本單位。不同的進程中進行線程的切換將會引起進程的切換。擁有資源不擁有系統(tǒng)資

22、源，但是線程可以訪問其隸屬進程的系統(tǒng)資源。擁有資源的基本單位。并發(fā)性同一進程內(nèi)的多個線程之間可以并發(fā)，大大提高了系統(tǒng)的吞吐量。多個進程可以并發(fā)執(zhí)行。系統(tǒng)開銷開銷小開銷大第四章進程同步與通信1.進程間的聯(lián)系：資源共享關(guān)系共享CPU和I/O設(shè)備。進程同步的主要任務(wù)是保證進程能互斥的訪問臨界資源，為此，資源不允許用戶進程直接使用，而由系統(tǒng)一一分配。相互合作關(guān)系進程同步的主要任務(wù)是保證相互合作的諸進程在執(zhí)行次序上的協(xié)調(diào)，不會出現(xiàn)時間與空間有關(guān)的差錯。2.臨界資源定義：臨界資源是指每次僅允許一個進程訪問的資源。屬于臨界資源的硬件有打印機、磁帶機等，軟件有消息緩沖隊列、變量、數(shù)組、緩沖區(qū)等。3.臨界區(qū)定義

23、：不論是硬件臨界資源，還是軟件臨界資源，多個進程必須互斥地對它進行訪問。每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。3.生產(chǎn)者一消費者問題：（1個生產(chǎn)者1個消費者）描述：一組生產(chǎn)者向一組消費者提供產(chǎn)品，他們共享一個有界緩沖區(qū)，生產(chǎn)者向其中投入產(chǎn)品，消費者從中取走廣品。解決方法：設(shè)一個數(shù)組來表示n個緩沖區(qū)的緩沖池。一個輸入指針in表示下一個可投放產(chǎn)品的緩沖區(qū)。一個輸出指針out指示下一個可獲取產(chǎn)品的緩沖區(qū)。一個整型變量counter,初始值為0。生產(chǎn)者和消費者共享下面的變量：Typedef.Item;intn;itembuffern;intin,out,counter;指針in和out初始化為1

24、,在生產(chǎn)者進程使用一個局部變量nextp,用于暫存每次剛生產(chǎn)出來的產(chǎn)品。在消費者進程中使用一個局部變量nextc用于暫存每次要消費的產(chǎn)品。voidproducer()/生產(chǎn)者進程while(1)/(當(dāng)為真時porduceaniteminnextp;while(counter=n)/當(dāng)counter的值為n的時候，執(zhí)行一條空操作，否則把nextpno-op;這個局部變量賦值給指針inbufferin=nextp;/in=(in+1)moden;/counter+;把nextp看成一個籃子,當(dāng)生產(chǎn)者投放一個產(chǎn)品后,/counter的值+1把籃子頭的東西放進去指針in向后移動一位voidconsum

25、er()/(消費者進程while(1)/當(dāng)為真時while(counter=0)/當(dāng)counter的值為0的時候，執(zhí)行一條空操作no-op;nextc=bufferout;/把緩沖池上的東西放到籃子頭去，再拿去消費out=(out+1)moden;/counter-;/ounter消費者取走一個產(chǎn)品后，輸入指針的值-1out向后移動一位consumetheiteminnextc;空閑讓進當(dāng)臨界資源處于空閑狀態(tài)時，可以允許一個要求進入臨界區(qū)的進程進入自己的臨界區(qū)，有效地利用臨界資源。忙則等待當(dāng)已經(jīng)有進程處于自己的臨界區(qū)時，其他所有想要進入臨界區(qū)的進程都必須等待，以保證進程互斥。有限等待對要求訪問

26、臨界資源的進程，應(yīng)保證該進程能在有效地時間內(nèi)進入自己的臨界區(qū)，以免陷入“死等”的狀態(tài)。counter的值不同。問題：關(guān)鍵在于counter的值失去了可再現(xiàn)性，如果兩個進程并發(fā)執(zhí)行時，就會使4.同步機制應(yīng)該遵循的準(zhǔn)則：讓權(quán)等待當(dāng)進程不能進入自己的臨界資源，應(yīng)立即釋放處理機，以免陷入“忙等”狀態(tài)。(處理機本身是臨界資源)5.軟件方法解決互斥問題：算法1:(強行輪流法)設(shè)置一個公用變量turn,用于指被允許進入臨界區(qū)的進程的編號。進程pl和p2,p3訪問臨界資源，turn=1表示pl可以訪問，訪問完之后trun變成2,p2可以訪問。問題：如果p2暫時不想訪問，p3想訪問，就必須等到p2訪問完之后才能

27、訪問。算法2:(查看標(biāo)志法)設(shè)置一個數(shù)組，pl的flag0=1表示pl正在訪問，p2的flag1=1表示p2正在訪問，p3的flag2=1表示p3正在訪問。問題：如果3個進程都要訪問，都發(fā)現(xiàn)對方的flag為0,所以3個進程都進入臨界區(qū)，違背了要互斥訪問臨界資源的原則了。算法3：(先標(biāo)記，再看別人)設(shè)置一個數(shù)組，flag0=1表示p1希望進入臨界區(qū)，然后去查看p2的flag1=1,表示p2也想進入或者p2已經(jīng)進入了臨界區(qū)，那么p1等待。問題：當(dāng)3個進程都要進入臨界區(qū)，當(dāng)檢查到對方的flag為1,每個進程都等待，結(jié)果每個人沒有訪問到臨界資源。算法4：(君子裁判法模式，算法1+算法3)設(shè)置一個數(shù)組和

28、一個turn變量。Flag0=1表示p1要求進入臨界區(qū)或者正在臨界區(qū)中執(zhí)行。While(1)(Flag0=1;turn=2;/p1想進入臨界區(qū)，就先把flag0=1,然后將turn變成2,去While(flag1=1&&turn=2)試探進程p2。flag1=1&&turn=2的反義詞就是flag1=0No-op;orturn=1Criticalsection;Flag0=0;6 .用硬件方法解決進程互斥：P102(1)利用Test-and-set指令實現(xiàn)互斥(2)利用Swap指令實現(xiàn)進程互斥主要思想：用一條指令完成標(biāo)志的檢查和修改兩個操作，因而保證了檢查操作與

29、修改操作不被打斷；或者通過中斷屏蔽的方法來保證檢查和修改作為一個整體執(zhí)行。優(yōu)點：適用范圍廣；簡單；支持多個臨界區(qū)。缺點：不能實現(xiàn)讓權(quán)等待(需要軟件配合進行判斷)。7 .信號量機制：(1)基本思想：在多個相互合作的進程之間使用簡單的信號來同步。(2) PV操作：信號量是一個確定的二元組(s,q),其中s是一個具有非負初值的整型變量，設(shè)s為一個信號量；q是一個初始狀態(tài)為空的隊列。P(s)完成以下動作：先執(zhí)行s=s-1,若執(zhí)行后的s>=0,則進程繼續(xù)執(zhí)行；若執(zhí)行后的s<0,則阻塞該進程，并插入到信號量的等待隊列中。(申請資源wait)V(s)完成以下動作：先執(zhí)行s=s+1,若執(zhí)行后的s&

30、gt;0,則進程繼續(xù)執(zhí)行；若執(zhí)行后的s<=0,則從該信號量等待隊列中移除第一個進程，并插入到信號量的等待隊列中。(釋放資源signal)(3)記錄型信號量機制：有一個用于代表資源數(shù)目的整型變量vlaue和一個進程鏈表L,用于鏈接所有等待該信號量代表資源的進程。描述如下：typedefstruct(intvalue;/代表資源數(shù)目listofprocess*L;/進程鏈表L(記錄所有需要資源的進程)semaphore(4)利用信號量實現(xiàn)進程互斥為臨界資源設(shè)置一個信號量mutex,并且初值為1,然后將個進程的臨界區(qū)放在wait(mutex)和signal(mutex)之間。(5)利用信號量描

31、述程序或者語句的前趨關(guān)系(P105)8.信號量集機制(1) And信號量集機制p105基本思想：將進程在整個運行過程中所需要的所有臨界資源一次性全部分配給進程，使用完之后再一起釋放。對若干個臨界資源的分配采取原子操作，要么全部分配到進程，要么一個也得不到。(2) 一般信號量集機制p106基本思想：當(dāng)一次需要n個某類資源時，便需要進行n次wait操作，顯然是低效的。所以需要進行判斷：當(dāng)資源數(shù)量低于某一下限時便不予分配。幾種特殊情況：Wait(s,d,d)只有一個信號量，但是允許每次申請d個資源，當(dāng)現(xiàn)有資源數(shù)少于d時，不予分配。Wait(s,1,1)一般記錄型信號量。Wait(s,1,0)當(dāng)s&g

32、t;=1時，允許多個進程進入某個特定區(qū)，當(dāng)s變?yōu)?時，阻止任何進程進入特定區(qū)。9.經(jīng)典同步問題：(1)生產(chǎn)者一消費者問題：利用記錄型信號量解決生產(chǎn)者一消費者問題。(P107-P109)描述：在生產(chǎn)者和消費者之間的公用緩沖池中有n個緩沖區(qū)，設(shè)置一個互斥信號量mutexo一個輸入指針in表示下一個可投放產(chǎn)品的緩沖區(qū)。一個輸出指針out指示下一個可獲取產(chǎn)品的緩沖區(qū)。(指針in和out初始化為1)在生產(chǎn)者進程使用一個局部變量nextp,用于暫存每次剛生產(chǎn)出來的產(chǎn)品。在消費者進程中使用一個局部變量nextc用于暫存每次要消費的產(chǎn)品。資源信號量empty和full分別表示空緩沖區(qū)數(shù)量和滿緩沖區(qū)數(shù)量。代碼描

33、述：semaphoremutex=1;/緩沖區(qū)進行操作的互斥信號量semaphoreempty=n;/空緩沖區(qū)的數(shù)量為nsemaphorefull=0;/滿緩沖區(qū)的數(shù)量為0itembuffern;/數(shù)組表示緩沖區(qū)個數(shù)intout=in=0;voidproducer()(while(1)(produdeaniteminnextp;/nextp是一個臨時緩沖區(qū)，比喻成一個籃子。wait(empty);/申請一個空的緩沖區(qū)(保證要有一個空的緩沖區(qū))wait(mutex);/申請使用緩沖池bufferin=nextp;/將產(chǎn)品放入緩沖池。把nextp看成一個籃子，把籃子頭的東西放進去in=(in+1)

34、modn;/當(dāng)生產(chǎn)者投放一個產(chǎn)品后，指針in向后移動一位signal(mutex);/緩沖池使用完畢，釋放互斥信號量signal(full);/增加一個滿緩沖池voidconsumer()while(1)wait(full);/申請一個滿緩沖池(保證要有個一個滿的緩沖區(qū))wait(mutex);/申請使用緩沖池nextc=bufferout;/把緩沖池上的東西放到籃子頭去，再拿去消費out=(out+1)modn;/消費者取走一個產(chǎn)品后，輸入指針out向后移動一位signal(mutex);/緩沖池使用完畢，釋放互斥信號量signal(empty);/增加一個空的緩沖池main()cobegi

35、nproducer();consumer();利用AND言號量集機制解決生產(chǎn)者一消費者問題：P109-110描述：只有緩沖區(qū)全滿或者全空的時候，指針in和out才會指向同一緩沖區(qū)，所以可以設(shè)置兩個互斥信號量mutex1和mutex2。代碼描述：semaphoremutex1=mutex2=1;/緩沖區(qū)進行操作的互斥信號量semaphoreempty=n;/空緩沖區(qū)的數(shù)量為nsemaphorefull=0;/滿緩沖區(qū)的數(shù)量為0itembuffern;/數(shù)組表示緩沖區(qū)個數(shù)intout=in=0;voidproducer()while(1)produdeaniteminnextp;/nextp是一個

36、臨時緩沖區(qū)，比喻成一個籃子。Swait(empty,mutex1)/申請一個空的緩沖區(qū)(保證要有一個空的緩沖區(qū))和申請使用緩沖池bufferin=nextp;/將產(chǎn)品放入緩沖池。把nextp看成一個籃子，把籃子頭的東西放進去in=(in+1)modn;/當(dāng)生產(chǎn)者投放一個產(chǎn)品后，指針in向后移動一位Ssignal(mutex1,full)/緩沖池使用完畢，釋放互斥信號量和增加一個滿緩沖池)voidconsumer()(while(1)(Swait(full,mutex2)/申請一個滿緩沖池(保證要有個一個滿的緩沖區(qū))和申請使用緩沖池nextc=bufferout;/把緩沖池上的東西放到籃子頭去，

37、再拿去消費out=(out+1)modn;/消費者取走一個產(chǎn)品后，輸入指針out向后移動一位Ssignal(mutex2,empty)/緩沖池使用完畢，釋放互斥信號量并且增加一個空的緩沖池)main()(cobegin(producer();consumer();)利用管程解決生產(chǎn)者一消費者問題：P117描述：建立一個管程命名為P-C,其中包含兩個過程：(1) put(item)生產(chǎn)者將自己生產(chǎn)的產(chǎn)品投放到緩沖池，并用count來表示在緩沖池已有的產(chǎn)品數(shù)目(2) get(item)消費者從緩沖池取得一個產(chǎn)品。P-C代碼描述：monitorP-C(intin,out,count;itembuff

38、ern;conditionnotfull,notempty;entryput(item)/生產(chǎn)者生產(chǎn)產(chǎn)品(if(count>=n)notfull.wait;/生產(chǎn)者需要等待一個空的緩沖區(qū)。bufferin=nextp;/否則，將籃子里面的產(chǎn)品放到空的緩沖區(qū)in=(in+1)modn;/指針in向后移動一位count+;/count的值+1notempty.signal;/釋放之后，多了一個滿的緩沖區(qū))entryget(item)/消費者消費產(chǎn)品(if(count<=0)notempty.wait;/消費者需要等待一個滿的緩沖區(qū)。nextc=bufferout;/把緩沖池上的東西放到

39、籃子頭去，再拿去消費out=(out+1)modn;/消費者取走一個產(chǎn)品后，輸入指針out向后移動一位count-;notfull.signal;/釋放之后，多了一個空的緩沖區(qū))int=out=0;/初始化count=0;)(2)讀者一寫者問題：利用記錄型信號量解決讀者一寫者問題：P111(讀者優(yōu)先)問題描述：“讀者優(yōu)先”除了某個寫者正在訪問數(shù)據(jù)之外，任何情況下讀者想要訪問數(shù)據(jù)均可以直接進行訪問，即只要存在讀者正在訪問數(shù)據(jù)，后續(xù)到達的那些欲訪問數(shù)據(jù)的讀者就無須判斷此時是否存在等待訪問數(shù)據(jù)的寫者，均直接訪問。設(shè)置變量描述：設(shè)置互斥信號量mutex,實現(xiàn)讀者與寫者的互斥，讀者與寫者之間有一個數(shù)據(jù)區(qū)

40、。整型變量readcount表示正在讀的進程的數(shù)目。僅當(dāng)readcount=0時，沒有讀者進程在進行，此時需要執(zhí)行wait(mutex),操作成功，讀者進程就可以進入臨界區(qū)。相應(yīng)的，當(dāng)readcount-之后的值為0,執(zhí)行signal(mutex)。為readcount設(shè)置一個互斥信號量rmutex。代碼描述：Semaphorermutex=mutex=1;/intreadcount=0;/用于記錄讀者數(shù)量voidreader(inti)(while(1)(wait(rmutex);/讀者去申請readcount的使用權(quán)if(readcount=0)/如果readcount的值為0,那么就去申

41、請使用數(shù)據(jù)區(qū)。否則直接readcount+1wait(mutex);readcount+;signal(rmutex);/釋放掉rmutex,讓后面進來的讀者可以申請到readcount,performreadoperation;/開始讀的操作wait(rmutex);/再去申請rmutex使得readcount-1。readcount-;if(readcount=0)/判斷readcount的值，判斷是否是最后一個讀者然后好釋放mutexsignal(mutex);signal(rmutex);)Voidwriter(inti)(While(1)(Wait(mutex);Performwri

42、teoperation;Signal(mutex);)Main()Cobegin/并發(fā)執(zhí)行Reader(1);.Reader(n);Writer(1);.Writer(m);)利用信號量集機制解決讀者一寫者問題：P112(讀者優(yōu)先)描述：增加了一條限制，即最多只允許RN個讀者進去同時讀。所以引入了一個信號量L并賦予初值RZ代碼描述：#defineRNsemaphoreL=RNmx=1;設(shè)置一個信號量L和mx(若mx=1讀者可以進去讀，若mx=0寫者可以進去讀)voidreader()while()swait(L,1,1);/進去一個讀者進行判斷(相當(dāng)于限制房間的座位數(shù))swait(mx,1,0

43、);/再進行mx的判斷，mx=1讀者可以進去讀，mx=0寫者可以進去寫performreadoperation;signal(L,1);/釋放掉一個L(相當(dāng)于增加一個座位數(shù))voidwriter()while(1)swait(mx,1,1,L,RN,0);/當(dāng)mx=1時，mx-1=1-1=0<1(開關(guān)關(guān)閉)并且L=RN,L-RN=0(沒有讀者performwriteoperation;在房間里面)，寫者才進去進行寫的操作。signal(mx,1);/寫完之后釋放掉mx使其+1,讓下一個想進入房間的讀者或者寫著能夠打)開門。)利用管程解決讀者一寫者問題：P120(寫著優(yōu)先)問題描述：在寫者

44、訪問數(shù)據(jù)時，若后面的等待隊列里面還有等待的寫者，那么就會優(yōu)先喚醒等待的寫者，直到等待的寫者都訪問完數(shù)據(jù)，最后一個寫者訪問完數(shù)據(jù)時，就喚醒其他等待的所有讀者。變量的描述：設(shè)置兩個計數(shù)器readercount和writercount分別對讀者進程和寫者進程計數(shù)。設(shè)置條件變量R和W分別表示允許讀者讀和允許寫者寫代碼描述：monitorreader-writer(intreadercount,writercount;conditionR,W;entrystart_read/開始讀的方法if(writercount>0)R.wait;/readercount+;先判斷有沒有寫者正在訪問數(shù)據(jù)或者等待

45、訪問數(shù)據(jù)，如果有,么就R.wait并且readercount+1R.signal;entryend_read/結(jié)束讀的方法readercount-;if(readercount=0)W.signal;entrystart_write/開始寫的方法writercount+;/先讓writercount+1增加一個寫者if(readercount>0)|writercount>0)W.wait;/如果readcount>0或者writercount>0那么W.waitentryend_write/結(jié)束寫的方法writercount-;/先讓writercount-1少了一個

46、寫者，再判斷-1之后的writercount的if(writercount>0)W.signal;值，如果0,就允許寫者寫，否則允許讀者讀。elseR.signal;readercount=writercount=0;/初始化;(3)哲學(xué)家進餐問題:利用管程解決哲學(xué)家進餐問題:P118問題描述：哲學(xué)家有三種狀態(tài)：饑餓，思考，進餐。三個過程：pickup(inti):拿起筷子準(zhǔn)備進餐。只要他處于饑餓狀態(tài)并且左右的兩個人都沒有進餐的話，就允許他進餐，否則的話就用self(i).wait推遲自己進餐。putdown(inti):放下筷子準(zhǔn)備思考。他吃完飯就去看左右兩邊的哲學(xué)家，如果都饑餓并且沒

47、有進餐的話，就讓他們進餐。Test(inti):這個是測試過程。測試哲學(xué)家是不是具備進餐的條件：自己饑餓，左右兩邊的人都沒有進餐。代碼描述：Monitordining-philosophers(enumstatus(thinking,hungry,eating)；enumstatus5;conditionself5;/entrypickup(inti)/(statei=hungry;/test(i);/if(statei!=eating)/self(i).wait;)Entryputdown(inti)/(Statei=thinking;Test(i-1mode5);/Test(i+1mode

48、5);/定義的一個數(shù)據(jù)結(jié)構(gòu)條件變量用一個數(shù)組表示拿起筷子準(zhǔn)備進餐首先判斷是不是饑餓。再調(diào)用test函數(shù)去測試具不具備進餐的條件。如果不允許進餐的t那么就用self(i).wait來讓自己推遲進餐。放下筷子開始思考測試左邊的人具不具備進餐的條件。測試左邊的人具不具備進餐的條件。)Test(inti);(If(statei-1mode5!=eating&&statei=hungry&&statei+1mode5!=eating)(Statei=eating;Selfi.signal;)(For(i=0;i<=4;i+)/循環(huán)5個哲學(xué)家執(zhí)行上述過程。Statei

49、=thinking;);(4)嗜睡的理發(fā)師問題：P115問題描述：一個理發(fā)店里面有一個理發(fā)椅和n張沙發(fā)。沒有顧客的話，理發(fā)師就去睡覺。當(dāng)?shù)谝粋€顧客進入理發(fā)店時：如果理發(fā)師在睡覺，則去喚醒理發(fā)師為其理發(fā)。如果理發(fā)師在理發(fā)，則找一個空沙發(fā)坐下等待。如果沒有空沙發(fā)了，則離開。設(shè)置變量描述：設(shè)置信號量customers來實現(xiàn)只有理發(fā)椅空閑時，顧客才能坐到上面等待理發(fā)師理發(fā)，否則等待。設(shè)置信號量barbers來實現(xiàn)只有當(dāng)理發(fā)椅上面有顧客時，理發(fā)師才開始理發(fā)，否則等待。設(shè)置一個整型變量waiting來對沙發(fā)上等待的顧客數(shù)量。由于waiting被對個顧客互斥訪問，故設(shè)置一個信號量mutex來實現(xiàn)。代碼描述：

50、Semaphorecustomers,barbers,mutex;customers=0;barbers=0;waiting=0;mutex=1;barbers()/理發(fā)師進程while(1)wait(customers);/先去申請理發(fā)椅上的顧客wait(mutex);/再去申請一個在外面沙發(fā)等待的的顧客。waiting=waiting-1;/這時，在外面等彳f的顧客數(shù)量-1signal(barbers);/這時理發(fā)椅上面有顧客，便喚醒理發(fā)師。signal(mutex);/釋放掉mutex讓下一個顧客可以申請理發(fā)椅。cuthair;/開始剪發(fā)。customer(inti)wait(mutex

51、);/申請一個空沙發(fā)的位置。(相當(dāng)于mutex是大門)if(waiting<n)waiting=waiting+1;signal(customers);/喚醒一個在理發(fā)椅上面的顧客signal(mutex);/釋放掉mutex以便下一個進來大門的顧客可以申請到。wait(barbers);/申請理發(fā)師來理發(fā)haveahaircut;elsesignal(mutex);leave;10.管程機制管程的概念：Hansan為管程所下的定義：“一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行(在該數(shù)據(jù)結(jié)構(gòu)上)的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)”。管程的組成：一局部于管程的共享變量說明

52、；一對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程；一對局部于管程的數(shù)據(jù)設(shè)置初始值的語句11.進程通信概念：(1)進程通信是指進程之間的信息交換。(2)進程的互斥和同步可歸結(jié)為低級通信。(3)高級進程通信：用戶可直接利用操作系統(tǒng)所提供的一組通信命令高效地傳送大量數(shù)據(jù)的一種通信方式。12.進程通信的類型：(1)共享存儲器系統(tǒng)：1基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式(只適合傳遞少量數(shù)據(jù))2基于共享存儲區(qū)的通信方式(屬于高級通信，為了傳遞大量數(shù)據(jù))(2)消息傳遞系統(tǒng)：進程間的數(shù)據(jù)交換以消息為單位。分為直接和間接通信方式(信箱通信方式)。(3)管道通信：管道是指用于連接一個讀進程和一個寫進程以實現(xiàn)它們之間通信的共享文件，又稱為

53、pipe文件(以字符流的形式將數(shù)據(jù)送入管道)。為了協(xié)調(diào)雙方的通信，管道通信機制必須提供以下三方面的協(xié)調(diào)能力：互斥、同步、雙方是否存在。13 .直接通信和間接通信(1)直接通信：直接通信方式是指發(fā)送進程利用操作系統(tǒng)所提供的發(fā)送命令直接把消息發(fā)送給目標(biāo)進程。系統(tǒng)提供下述兩條通信原語：send(receiver,message)；receive(sender,message)；利用直接進程通信原語來解決生產(chǎn)者-消費者問題P123(2)間接通信：進程之間的通信需要通過作為某種共享數(shù)據(jù)結(jié)構(gòu)的實體，該實體用來暫存發(fā)送進程發(fā)送給目標(biāo)進程的消息；接收進程則從該實體中取出對方發(fā)送給自己的消息。通常把這種中間實體稱為信箱(可由操作系統(tǒng)或用戶進程創(chuàng)建。分為私有信箱、共有信箱、共享信箱)(3)發(fā)送進程和接收進程的關(guān)系：一對一關(guān)系、多對一關(guān)系、一對多關(guān)系、多對多關(guān)系。14 .消息緩沖隊列通信機制發(fā)送原語，接受原語P12515 .死鎖：(1)定義：在多道程序系統(tǒng)中，一組進程中的每一個進程均無限期地等待被該組進程中的另一個進程所占有且永遠不會釋放的資源；這種現(xiàn)象稱