1、操作系統習題集(南京曉莊學院操作系統習題答案)操作系統基礎習題解析及實驗指導1. .第一篇 操作系統基礎知識點及習題解答該部分羅列操作系統基礎各章節的學習要點，指出學習的重點和難點，在回顧相關知識點的基礎上，對典型習題進行分析和解答。第一章 操作系統引論本章學習要點【1】掌握操作系統的概念與作用【2】掌握操作系統的基本類型與特點【3】掌握操作系統的特征與功能【4】深入領會多道程序設計技術本章學習難點【1】多道程序設計技術【2】操作系統的特征知識點回顧一. 操作系統的概念一個完整的計算機系統由計算機硬件系統和計算機軟件系統兩部分組成。操作系統是配置在計算機硬件上的第一層軟件，是對硬件系統功能的第

2、一次擴充。應用程序實用程序操作系統計算機硬件（裸機）用戶圖1-1 計算機系統的層次圖1. 操作系統（Operating System，簡稱OS）的作用（1） OS作為用戶與計算機硬件系統之間的接口OS處于用戶與計算機硬件系統之間，用戶通過OS來使用計算機系統。或者說，用戶在OS的幫助下能夠方便、快捷、安全、可靠地操縱計算機硬件和運行自己的程序。（2） OS作為計算機系統資源的管理者這是廣為流行的一個關于OS作用的觀點。在一個計算機系統中，通常都包含了各種各樣的硬件和軟件資源。歸納起來可將資源分為四類：處理器、存儲器、IO設備以及信息(數據和程序)。OS的主要功能正是針對這四類資源進行有效的管理

3、。（3） OS用作擴充機器對于一臺完全沒有軟件配置的計算機系統(裸機)，即使功能再強，也必定難于使用。OS在裸機上分別覆蓋IO設備管理軟件、文件管理軟件等，此時用戶所看到的機器，將是一臺比裸機功能更強、使用更方便的機器。通常把覆蓋了軟件的機器稱為擴充機器或虛機器。在計算機系統上覆蓋上一層軟件后，系統功能便增強一級。由于OS自身包含了若干層軟件，因此當在裸機上覆蓋上OS后，便可獲得一臺功能顯著增強，使用極為方便的多層擴充機器或多層虛機器。2. 操作系統的概念操作系統是一組控制和管理計算機硬件和軟件資源、合理組織計算機的工作流程，方便用戶使用的程序的集合。操作系統是裸機上的第一層軟件，是對硬件功能

4、的首次擴充。二. 操作系統的發展過程人工操作方式脫機輸入輸出技術批處理技術分時、實時系統通用操作系統微機操作系統網絡操作系統分布式操作系統1. 脫機輸入輸出技術為解決人工操作階段存在的人機矛盾以及CPU與I/O速度不匹配的矛盾，引入脫機輸入輸出技術。系統中除主機外配置一臺外圍機（又稱衛星機），它只與輸入輸出設備打交道，不與主機相連，即脫機。用戶程序與數據可以在外圍機控制下（脫離主機控制）預先從低速設備輸入到磁帶上，CPU需要時再從磁帶上輸入到主機，即脫機輸入技術，以解決CPU與I/O速度不匹配的矛盾。類似地，脫機輸出技術通過外圍機完成數據從主機到磁帶，再到低速輸出設備上的輸出操作。由于主機CP

5、U只與高速的輸入輸出設備打交道，從而有效地減少了CPU等待低速設備輸入輸出的時間。主機輸入帶輸出帶紙帶機打印機機外圍機輸入帶輸出帶圖1-2 脫機輸入/輸出方式2. 批處理技術批處理技術是指計算機對一批作業自動進行處理的一種技術。早期的計算機系統為了充分利用系統資源，通常把一批作業以脫機輸入方式輸入到磁帶上，并在系統中配置監督程序，依次將作業裝入內存，控制磁帶上的作業自動地、一個接一個地進行處理，這樣就形成了早期的單道批處理系統。3. 多道程序設計技術為進一步改進單道批處理系統中CPU和內存利用率較低的問題，引進多道程序設計技術。多道程序設計技術同時將多個作業放入內存并允許作業交替執行，共享系統

6、中的資源。宏觀上并行，微觀上串行。多道程序設計技術能有效提高系統的吞吐量和改善資源利用率，但是為了協調內存中運行的多道程序，應妥善解決處理機分配、內存分配、設備分配、文件安全、作業組織的問題。為解決上述問題而設置的一組軟件就形成了操作系統。程序A輸入設備輸出設備CPU程序B程序A程序B程序A程序B運行處理輸入數據運行處理輸出數據運行處理輸出數據等待CPU運行處理圖1-3多道程序運行情況三. 操作系統的分類1. 單用戶操作系統2. 批處理操作系統（1） 單道批處理系統把一批作業以脫機方式輸入到磁帶上，在系統中配上監督程序，在它的控制下使這批作業能自動地一個接一個地順序處理。對作業的處理是成批進行

7、的、且內存中始終只保持一道作業。（2） 多道批處理系統_ 引入多道批處理的目的a) 提高CPU的利用率b) 提高內存和I/O設備的利用率c) 增加系統吞吐量_ 多道批處理的特征多道性、無序性、調度性_ 多道批處理的優缺點資源利用率高，系統吞吐量大，但平均周轉時間長，無交互能力。3. 分時操作系統在分時操作系統中，一臺計算機和多臺終端相連，每個用戶通過自己的終端向系統發出命令請求，系統分析并完成各用戶的請求。（1） 單道分時系統內存中只駐留一道作業，當其運行一個時間片后，調至外存，再從外存上選一個作業進入內存。作業頻繁調進調出，開銷大，系統性能較差。（2） 具有“前臺”和“后臺”的分時系統內存被

8、固定地劃分為“前臺區”和“后臺區”。前臺區存放按時間片“調進”和“調出”的作業流，后臺區存放批處理作業。僅當前臺無作業運行時，方才運行后臺的作業。（3） 多道分時系統內存中的多道作業輪流獲得一個時間片來運行。分時系統的特征具有多路性、獨立性、及時性和交互性等特征。4. 實時操作系統能使計算機系統接收到外部信號后及時進行處理，并且在嚴格的規定時間內處理結束，再給出反饋信號的操作系統。實時操作系統分為實時控制系統和實時信息處理系統。例如生產過程控制系統、航空訂票系統等。實時系統具有多路性、獨立性、及時性、交互性和可靠性等特征。實時控制系統是以計算機為中心的生產過程控制系統，又稱為計算機控制系統，要

9、求快速的響應時間，可靠性要求高。實時信息處理系統在響應時間上和分時系統處于同一級別，但更強調可靠性和安全性，交互性差。批處理操作系統、分時操作系統、實時操作系統是三種基本的操作系統類型。如果一個操作系統兼有三者或其中二者的功能，則該操作系統稱為通用操作系統。5. 其它操作系統包括網絡操作系統、分布式操作系統等。四. 操作系統特征并發、共享、虛擬、異步性1. 并發并發是指兩個或多個事件在同一時間間隔內發生。宏觀上是同時的，微觀上是交替的。程序的并發執行能有效改善系統資源的利用率，但會使系統復雜化。要注意區別并發和并行兩個概念。2. 共享系統中的資源可供內存中多個并發執行的進程共同使用。根據資源的

10、不同屬性，可分為兩種資源共享方式：互斥共享和同時訪問。并發和共享是操作系統的兩個最基本的特征，兩者之間互為存在的條件。一方面，資源的共享是以程序的并發執行為前提的；另一方面，系統若不能對資源共享實施有效管理，則程序的并發執行則無法實現。3. 虛擬通過某種技術把一個物理實體變成若干個邏輯上的對應物，物理實體是實的，即實際存在，而后者是虛的，是用戶的感覺。例如虛擬內存、虛擬設備等。4. 異步性在多道程序環境下，多個進程并發執行，但由于資源等因素的限制，內存中的每個進程何時執行，何時暫停，以怎樣的速度向前推進，每道程序需多少時間才能完成，都是不可預知的，進程以異步的方式運行。但只要運行環境相同，作業

11、經過多次運行，都會獲得完全相同的結果。五. 操作系統的功能操作系統引入多道程序設計技術，一方面改善了系統資源的利用率，但另一方面也引發了復雜的系統管理問題，諸如內存中的作業如何存儲，系統資源如何共享等，操作系統必須具有控制和管理各種并發活動的能力，合理組織計算機的工作流程，有效地提高各類資源的利用率。1. 處理機管理主要任務是對處理機進行分配，并對其進行有效的控制和管理。在多道程序環境下，處理機的分配和運行是以進程為基本單位，又稱進程管理。（1） 進程控制為作業創建進程，撤消已結束的進程，以及控制進程的狀態轉換。（2） 進程同步對諸進程的運行進行協調（互斥和同步）。（3） 進程通信實現相互合作

12、進程之間的信息交換。（4） 進程調度從就緒隊列中，按照一定的算法選出一新進程，分配處理機，設置運行現場，使之投入運行。2. 存儲器管理存儲器管理的主要任務是為多道程序的運行提供良好的環境，方便用戶使用存儲器，提高存儲器的利用率，以及從邏輯上來擴充內存。（1） 內存分配為每道程序分配內存空間，提高內存的利用率。（2） 內存保護確保每道用戶作業都在自己的內存空間中運行，互不干擾。（3） 地址映射將地址空間中的邏輯地址轉換為內存空間中與之對應的物理地址。（4） 內存擴充借助虛擬技術，從邏輯上擴充內存容量。3. 設備管理主要任務是完成用戶提出的I/O請求，為用戶分配I/O設備；提高CPU和I/O設備的

13、利用率；提高I/O速度；以及方便用戶使用I/O設備。（1） 緩沖管理管理各種類型的緩沖區。（2） 設備分配根據用戶的I/O請求，分配所需設備。（3） 設備處理實現CPU和設備控制器之間的通信。（4） 設備獨立性和虛擬設備4. 文件管理程序和數據都是以文件的形式存儲在存儲介質上。文件管理的主要任務是對用戶文件和系統文件進行管理，方便用戶使用，保證文件的安全性。（1） 文件存儲空間的管理（2） 目錄管理建立目錄項，實現按名存取、實現文件共享。（3） 文件的讀、寫管理和存取控制（4） 文件保護5. 作業管理（1） 操作系統接口（2） 作業的控制方式六. 操作系統的結構模塊接口法、有序分層法1. 模塊

14、接口法按功能劃分模塊，模塊間可以不加控制的相互調用和轉移。這種結構緊湊、接口簡單直接，系統效率高；但模塊間的調用隨便，獨立性差，系統結構不清晰。2. 有序分層法A0，A1Ai，Ai+1AnA0宿主系統（底），An是目標系統（頂）。既可采用自底向上法，逐步擴充，也可采用自頂向下法，逐層分解。（1） 單向依賴（2） 同一層中各模塊的功能應相近（3） 與硬件緊密相關的模塊安排在A0層，便于移植（4） 運行頻率較高的公用模塊應放置在較低的層次（5） 由于設計目標不同而變化的部分放在外層，增強系統的適應性習題分析一. 判斷改錯題（判斷由下劃線標明的關鍵詞的敘述是否正確，正確的打，錯誤的打并改正。）（1）

15、 實時系統只能應用于生產控制系統，不能應用于信息處理系統。（ ）（2） 并發含有“同時進行”的概念，是指兩個或者是多個事件在同一時刻發生。（ ）（3） 操作系統虛擬機在邏輯功能上與裸機一樣，具有一個物理實體。（ ）（4） 對用戶而言，操作系統是一種人機交互的環境，對設計者而言，它是一種強功能的系統資源管理程序。（ ）（5） 資源的共享是以程序的并行執行為條件的，沒有程序的并行執行，就沒有資源的共享。（ ）（6） 計算機系統的資源包括程序和數據兩大部分。（ ）（7） 若把計算機系統分為若干層次，則按由上而下順序可分為應用系統與應用軟件、操作系統、其它系統軟件和裸機。（ ）（8） 批處理控制程序解

16、決了作業間的自動轉換，減少了時間浪費，尤其是主機CPU時間的浪費，如果一個用戶的計算作業非常龐大,也不會獨自一直占據CPU。（ ）習題解答：（1） 錯；應為：實時系統能應用于生產控制系統，也能應用于信息處理系統。（2） 錯；應為：是指兩個或者是多個事件在一段時間間隔內同時發生。（3） 錯；應為：操作系統虛擬機在邏輯功能上與裸機不同，但只具有一個物理實體。（4） 對；（5） 錯；應為：資源的共享是以程序的并發執行為條件的，沒有程序的并發執行，就沒有資源的共享。（6） 錯；應為：計算機系統的資源包括硬件資源和軟件資源兩大部分。（7） 錯：應為：若把計算機系統分為若干層次，則按由上而下順序可分為應用

17、系統與應用軟件、其它系統軟件、操作系統和裸機。（8） 錯；應為：，尤其是主機CPU時間的浪費，如果一個用戶的計算作業非常龐大,就會獨自一直占據CPU。（9） 對；二. 填空題（1） 實時含有立即、及時之意，因而 是實時系統最關鍵的因素。（2） 操作系統的層次結構中，與 或運行頻率較高的模塊都安排在緊靠硬件的軟件層中，這一部分通常稱為 ，它在執行基本操作時，往往是利用 操作來實現，該操作具有原子性。（3） UNIX是一個真正的 用戶、 任務的 操作系統。（4） 如果一個操作系統兼有 、 和 三者或其中兩者的功能，這樣的操作系統稱為通用操作系統。（5） 實現多道程序設計必須妥善解決三個問題： 、

18、和系統資源的管理和調度。（6） 批處理系統的主要優點是 ，資源利用率高，系統開銷小，它的缺點在于作業處理的 ，用戶交互能力較弱。（7） 操作系統是對計算機進行 的程序，是計算機和 的接口。（8） 提供網絡通訊和網絡資源共享功能的操作系統稱為 操作系統。（9） 對系統總體設計目標來說，批處理系統注重提高計算機的效率，盡量增加系統的 ，分時系統應保證用戶的 ，而實時系統在及時響應和處理的前提下，再考慮 。（10） 在主機控制下進行的輸入/輸出操作稱為 操作。（11） 在計算機系統中， 是整個系統硬件的核心和基礎，而在計算機軟件系統中， 具有同樣的核心和基礎作用。習題解答：（1） 響應時間；（2）

19、硬件緊密相關，內核，原語；（3） 多，多，網絡；（4） 批處理操作系統、分時操作系統、實時操作系統；（5） 文件，作業；（6） 系統吞吐量大，平均周轉時間較長；（7） 控制和管理，用戶；（8） 網絡；（9） 吞吐量，交互性，與用戶的交互性；（10） 聯機I/O操作；（11） CPU，操作系統； 三. 簡答題1. 簡述操作系統在計算機系統中的位置。答：操作系統OS是運行在計算機硬件系統上的最基本的系統軟件。它在計算機系統中位于計算機裸機和計算機用戶之間，為系統軟件和用戶應用軟件提供了強大的支持。2. 簡述描述操作系統的兩種主要觀點。答：描述操作系統有兩種主要觀點，一種是虛擬機的觀點裝有操作系統的

20、計算機極大地擴展了原計算機的功能，給用戶提供了一個友好的、易于操作的界面，對用戶來說，好像是一個擴展了的機器，即一臺虛擬機器。另一種是資源管理的觀點，操作系統完成對處理機、存儲器、I/O設備等硬件資源和文件等軟件資源的管理。3. 什么是操作系統它有什么基本特征 答：操作系統是一組控制和管理計算機硬件和軟件資源、合理組織計算機的工作流程，以及方便用戶的程序的集合。操作系統的基本特征是：并發是指兩個或多個事件在同一時間間隔內發生。宏觀上是同時的，微觀上是交替的。共享系統中的資源可供內存中多個并發執行的進程共同使用。根據資源的不同屬性，可分為兩種資源共享方式：互斥共享和同時訪問。虛擬通過某種技術把一

21、個物理實體變成若干個邏輯上的對應物，物理實體是實的，即實際存在，而后者是虛的，是用戶的感覺。異步性在多道程序環境下，多個進程并發執行，但由于資源等因素的限制，內存中的每個進程何時執行，何時暫停，以怎樣的速度向前推進，每道程序需多少時間才能完成，都是不可預知的，進程以異步的方式運行。但只要運行環境相同，作業經過多次運行，都會獲得完全相同的結果。4. 多道程序設計時應注意什么問題？答：處理機管理問題多道程序之間如何分配CPU，使CPU既能滿足各程序運行的需要，又能提高處理機的利用率。內存管理問題為每道程序分配必要的內存空間，并防止程序遭破壞。I/O設備管理分配為多道程序共享的I/O設備，方便用戶使

22、用，提高設備利用率。文件管理問題組織大量的程序和數據，便于用戶使用，保證數據的安全和一致。作業管理問題對系統中各種類型的作業進行組織。四. 練習題1. 實時操作系統必須在（ ）內處理來自外部的事件。A.一個機器周期 B. 被控制對象規定的時間C.周轉時間 D.時間片2. 操作系統中最基本的兩個特征是（ ）A.并發和不確定性 B.并發和共享 C.共享和虛擬 D.虛擬和不確定性3. 分時系統追求的目標是（ ）A.充分利用I/O設備 B.快速響應用戶C.提高系統吞吐量D.充分利用內存4. 批處理系統的主要缺點是（ ）A.系統吞吐量小 B.CPU利用率不高 C.資源利用率低 D.無交互能力5. 在主機

23、控制下進行的輸入輸出操作稱為（ ）操作。6. 如果操作系統具有很強的交互性，可同時供多個用戶使用，系統響應比較及時，則屬于（ ）類型；如果系統可靠，響應及時但僅有簡單交互能力則屬于（ ）類型；如果操作系統在用戶提交作業后不提供交互能力，它追求的是計算機資源的高利用率，大吞吐量和作業流程的自動化，則屬于（ ）類型。7. 設內存中有三道程序A、B、C，它們按A、B、C的優先次序執行。它們的計算和I/O操作時間操作程序ABC計算306020I/O403040計算101020如下表所示（單位：ms）。假設三道程序使用相同設備進行I/O操作，即程序以串行方式使用設備。試畫出單道運行和多道運行的時間關系圖

24、（調度程序的時間忽略不計）。在兩種情況下，完成三道程序各要花多少時間？8. 試比較分時系統和實時系統。9. 簡述DOS、Windows和UNIX操作系統的特點。. .第二章 進程管理本章學習要點【1】掌握進程的定義和特征【2】深入領會進程狀態及其狀態轉換的原因【3】熟練運用信號量解決進程同步問題【4】掌握調度的類型與方式【5】掌握常用的進程調度算法【6】掌握死鎖的相關知識【7】深入領會銀行家算法本章學習重點和難點【1】運用信號量解決進程同步問題【2】進程調度算法【2】銀行家算法知識點回顧多道程序設計技術的引入，實現了資源的共享和程序的并發執行。為了描述并發執行的動態特點，引入進程的概念。進程是

25、可并發執行的程序在一個數據集合上的運行過程，具有動態性、并發性、獨立性、異步性和結構特征。進程管理包括進程控制、進程同步、進程通信和進程調度四個主要方面。一. 前趨圖和程序執行1. 前趨圖是一個有向無循環圖，以描述結點（語句、程序段或進程）之間的前趨關系，前趨關系描述了結點執行的先后次序。2. 程序順序執行和并發執行的特征 程序的順序執行14653112數據1：1輸入 2計算 3打印 數據2：4輸入 5計算 6打印對較大程序的若干個程序段，或者某個程序段的多條語句，執行時必須按照某種先后次序逐個執行。具備順序性、封閉性和可再現性。C1I1P2P3I3C3C2I2P1 程序的并發執行I 輸入C

26、計算P 輸出同一數據的不同操作之間、不同數據的同一操作之間存在著前趨關系。但不同數據的不同操作之間可考慮并發執行。例：I3、C2、P1，可并發執行。并發執行出現了新特征： 間斷性、失去封閉性和不可再現性。3. 程序并發執行的條件。（Bernstein條件）R（pi）:讀集，表示程序pi在執行期間所需參考的所有變量的集合。W（pi）:寫集，表示程序pi在執行期間要改變的所有變量的集合。若兩個進程p1和p2能滿足下述Bernstein條件，它們便能并發執行，且具有可再現性。R(p1) W(p2)R(p2)W(p1)W(p1)W(p2)= 二. 進程的描述1. 進程的定義和特征進程是可并發執行的程序

27、在一個數據集合上的運行過程。具有以下特征： 動態性是進程最基本的特性。進程有一定的生命期，由創建而產生，由調度而執行，因得不到資源而暫停執行，由撤消而消亡。而程序是一組有序指令的集合，是靜態實體。 并發性多個進程在一段時間間隔內同時運行。 獨立性進程實體是一個能獨立運行的基本單位，也是系統中獨立獲得資源和獨立調度的基本單位。 異步性進程按各自獨立的、不可預知的速度向前推進。 結構特征進程實體由程序段、數據段和進程控制塊PCB組成。2. 進程的基本狀態及其轉換就緒執行阻塞ABCD A:進程調度 B:發生某事件無法執行 C:時間片到或優先級高的進程到達 D:阻塞的事件消失3. 進程控制塊 進程控制

28、塊是進程實體的一部分，它記錄了操作系統所需的、用于描述進程情況及控制進程運行所需的全部信息。 進程控制塊的作用是使一個在多道程序環境下不能獨立運行的程序（含數據），成為一個能獨立運行的基本單位，一個能和其它進程并發執行的進程。 PCB是進程存在的唯一標志。創建新進程時建立一個PCB，進程結束時回收PCB。 PCB經常被系統訪問，應常駐內存。 PCB的內容 進程標識符信息外部標識符、內部標識符（唯一整數）。 處理機狀態信息 進程調度信息進程狀態、優先級等。 進程控制信息程序和數據地址、同步機制、資源清單等。 PCB的組織方式 鏈接方式相同狀態的PCB，鏈接成一個隊列。 索引方式建立索引表。三.

29、進程控制1. 操作系統的內核內核是計算機硬件的第一層擴充軟件，由與硬件緊密相關的模塊以及運行頻率較高的模塊組成，常駐內存，以提高OS的運行效率。 支撐功能 中斷處理是內核最基本的功能，它是整個操作系統賴以活動的基礎。內核只對中斷進行“有限的處理”，然后轉由有關進程繼續處理。 時鐘管理 原語操作原語本身是由若干條指令構成，用于完成一定功能的一個過程。原語是一個不可分割的原子操作。 資源管理功能進程管理、存儲器管理和設備管理。2. 進程的創建、終止、阻塞與喚醒（1） 進程的創建 進程圖是描述進程家族關系的有向樹。有向邊表示了進程的創建關系，即父子關系 ，（注：并不能說明前趨關系），子進程可以繼承父

30、進程所擁有的資源，父進程撤消時必須同時撤消其所有子進程。 引起創建進程的事件 用戶登錄（分時系統） 作業調度（批處理系統） 由系統內核創建進程 提供服務 應用請求應用進程創建 進程的創建創建原語申請空白PCB 為進程分配資源 初始化PCB 插入就緒隊列（2） 進程的終止正常結束、異常結束、外界干預（3） 進程的阻塞與喚醒 原因請求系統服務、啟動某種操作、新數據未到達、無新工作 阻塞當出現上述事件，進程無法繼續執行，進程通過調用阻塞原語block把自己阻塞，是進程自身的一種主動行為。 喚醒當阻塞事件結束，由發現者進程調用喚醒原語將阻塞進程喚醒，是一種被動行為。四. 進程同步1. 進程同步的基本概

31、念多道程序環境下，系統中的進程間可能存在兩種關系：間接制約關系資源共享，進程同步保證諸進程互斥訪問臨界資源。直接制約關系相互合作，進程同步保證諸進程在執行次序上的協調。 臨界資源一段時間內只允許一個進程訪問的資源。例如：打印機。 臨界區進程中訪問臨界資源的那段代碼稱為臨界區。要保證對臨界資源的互斥訪問，只需保證進程互斥地進入自己的臨界區。 Repeat進入區（entry section） 檢查臨界資源的使用，設置訪問標志 臨界區(critical section)退出區(exit section) 恢復未訪問標志 剩余區(remainder section) until false 同步機制應

32、遵循的準則 空閑讓進有效利用 忙則等待互斥 有限等待避免“死等” 讓權等待避免“忙等” 利用硬件方法解決進程互斥特殊的硬件指令2. 信號量機制 整型信號量機制 將整型信號量定義為一個整型量，僅能通過兩個標準的原子(不可中斷)操作（P、V）來訪問。P(S)： while s0 do no op“忙等” s:=s-1;V(S)：s:=s+1; 利用信號量實現互斥為使多個進程能互斥地訪問某臨界資源，應為該臨界資源設置一互斥信號量mutex，并設初始值為1，然后將各進程的臨界區置于P（mutex）和V（mutex）操作之間。注意實現進程互斥時P、V操作必須成對出現。 Repeat進入區P（mutex）

33、 臨界區(critical section)退出區V（mutex） 剩余區(remainder section) until false 由于mutex的初值為1任何時刻只能有一個進程進入臨界區，此時互斥信號量=0，其它欲進入臨界區的進程忙等。 利用信號量描述前趨關系設置公用信號量S。 記錄型信號量機制采用記錄型的數據結構 type semaphore=recordvalue:integer; 表示資源數目L:list of process;等待該資源的進程鏈表 end p(s)s.value:=s.value-1;if s.value0 then block(s,l)s.value的初值表示

34、系統中某類資源的數目。s.value0（不含=0）表示資源已分配完畢，自我阻塞。s.value1)一般的記錄型信號量 (s=1) 互斥信號量J p(s,1,0)可控開關3. 經典進程的同步問題 生產者消費者問題：相互合作進程關系的抽象 公用緩沖池0 1 2 n-1empty=n 空緩沖的數量 mutex=1 互斥信號量full=0 滿緩沖的數量生產者 消費者 生產一產品 p(full) 是否有產品可消費 p(empty) 是否有空緩沖存放產品 p(mutex) p(mutex) 對緩沖區 從緩沖中取產品 的互斥訪問產品放人緩沖區 v(mutex)v(mutex) v(empty)v(full)

35、 消費產品 每個程序中實現互斥的p(mutex)和v(mutex)必須成對出現。 對生產者和消費者的pv操作同樣需要成對出現，但它們是分別處于不同的程序中。 在每個程序中多個p操作順序不能顛倒。 讀者寫者問題一個數據對象(數據文件或記錄)，可被多個進程共享。允許多個reader進程同時讀一個共享對象，但絕不允許一個writer進程和其它reader進程或writer進程同時訪問共享對象。 利用記錄型信號量解決讀者寫者問題readcount=0：讀者數目，臨界資源rmutex=1：對readcount互斥訪問的互斥信號量wmutex=1： 寫互斥信號量流程見下圖。 利用信號量集機制解決讀者寫者問

36、題讀者：寫者：repeatrepeatsp(L,1,1)L 為讀者數(RN) sp(mx,1,1;L,RN,0) sp(mx,1,0) mx為控制開關寫操作讀操作sv(mx,1)sv(L,1)until falseuntil false讀者：寫者：p(rmutex) p(wmutex)readcount=0 Y 第一個讀者 np(wmutex) 寫操作readcount:=readcount+1v(rmutex)v(wmutex)讀操作p(rmutex)readcount:=readcount-1readcount=0 Y 最后一個讀者讀完 n v(wmutex) v(rmutex) 哲學家進

37、餐問題五. 進程通信進程通信是指進程間的信息交換。進程的同步是低級通信，效率低，對用戶不透明。高級通信是指用戶直接利用操作系統所提供的一組通信命令(隱藏了進程通信的實現細節)，高效地傳送大量數據的一種通信方式。1. 共享存儲器系統相互通信的進程共享某些數據結構或共享存儲區。 基于共享數據結構的通信方式（低級） 基于共享存儲區的通信方式2. 消息傳遞系統進程間的數據交換以消息為單位。程序員直接利用系統提供的一組通信命令（原語）來實現通信。 直接通信方式發送進程利用OS所提供的發送命令，直接把消息發送給目標進程。要求發送進程和接收進程都以顯式的方式提供對方的標識符。Send(receiver ,

38、message)Receive(sender , message) 間接通信方式通過中間實體（信箱）進行通信，廣泛用于計算機網絡中。消息在信箱中可以安全保存，只允許核準的用戶隨時讀取。系統為信箱提供了創建、撤消、消息發送、接收等原語。信箱的種類：私用信箱用戶進程自己創建，作為該進程的一部分，采用單向鏈路，其他用戶發送消息，主人讀取消息。公用信箱操作系統創建，在系統運行期始終存在，采用雙向通信鏈路，核準用戶可發送和取出消息。共享信箱某進程創建，指明共享進程的名字。主人和共享者都有權取走自己的消息。信箱通信，發送和接收進程之間存在1:1、n:1、1:n（廣播）、m:n（公用信箱）的關系。3. 管道

39、通信共享文件的通信方式管道是指用于連接一個讀進程和一個寫進程，以實現它們之間通信的共享文件，又稱pipe文件。UNIX系統采用。寫進程以字符流的形式將大量數據送入管道，讀進程接收數據。 讀進程 寫進程 管道通信機制必須提供互斥、同步和確定對方的三種協調能力。六. 進程調度1. 調度隊列模型 作業調度 時間片完CPU 后備隊列 就緒隊列 進程調度 進程完成批量 作業 中級調度 就緒掛起隊列 交互型作業 事件出現 阻塞掛起隊列 事件 出現 掛起 阻塞隊列 等待事件2. 調度類型 高級調度作業調度批處理系統中使用，周期較長。 低級調度進程調度是最基本的一種調度，在三種類型的OS中都必須配置。進程調度

40、可采用非搶占或搶占兩種方式。其中搶占方式允許調度程序根據某種原則，例時間片原則、優先權原則、短進程優先原則等去停止某個正在執行的進程，將已分配給該進程的處理機，重新分配給另一進程。進程調度的運行頻率最高，故算法不能太復雜。 中級調度引入中級調度的目的是為了提高內存的利用率和系統吞吐量。中級調度實際上是存儲器管理中的對換功能。3. 選擇調度方式和算法的準則周轉時間（批處理）面向用戶 響應時間（分時）的準則 截止時間的保證（實時） 優先權準則面向系統 系統吞吐量高（批處理）的準則 處理機利用率好 各類資源的平衡利用 周轉時間指作業提交系統開始，到作業完成為止的時間間隔。 帶權周轉時間作業的周轉時間

41、與系統為它提供的實際服務時間之比。W=T/TS 響應時間從用戶通過鍵盤提交一個請求開始，直至系統首次產生響應為止的時間。 截止時間某任務必須開始執行的最遲時間，或必須完成的最遲時間。 吞吐量單位時間內所完成的作業數。4. 調度算法（作業調度、進程調度） 先來先服務調度算法（FCFS） 按進入后備（或就緒）隊列的先后選擇目標作業（或進程）。 有利于長作業（進程），不利于短作業（進程）。 最短作業優先調度算法SJ（P）F 從后備（或就緒）隊列中選擇估計運行時間最短的作業（或進程） tn+1=a tn+(1-a) tn tn為實際值， tn為預測值 SJF有效地降低作業的平均等待時間，提高了系統的吞

42、吐量。 對長作業（或進程）不利，可能死等，且未考慮作業的緊迫程度。 時間片輪轉調度算法（進程調度） 系統將所有的就緒進程按先來先服務原則，排成一個隊列，每次調度時把CPU分配給隊首進程，令其執行一個時間片。 就緒隊列中所有進程，在一個給定的時間內，均能獲得一個時間片的處理機執行時間。T=nq 優先權調度算法 適用于作業調度和進程調度。 非搶占式、搶占式優先權調度算法 優先權類型：靜態優先權、動態優先權 高響應比優先調度算法（作業調度） 響應比RP= 響應時間/要求服務時間=（等待時間+要求服務時間）/要求服務時間 = 1+等待時間/要求服務時間 同時到達的作業（等待時間相同），要求服務時間越短

43、（短作業），響應比越高，有利于短作業。 要求服務時間相同的作業，等待時間越長，響應比越高，相當于先來先服務。 長作業在等待足夠長時間后，響應比上升，也可被調度，避免長作業的死等。 每次調度需計算響應比，增加系統的開銷。 多級隊列調度 根據作業的性質或類型的不同，將就緒進程隊列分成若干個子隊列，各個作業固定分屬于一個隊列。每個隊列采用各自的調度算法。 多級反饋隊列調度算法 UNIX系統中的進程調度算法。 處理方法：J 設置多個就緒隊列，每個隊列賦予不同的優先權(S1S2Sn )，且各隊列中進程執行的時間片的大小各不相同(q，2qnq)。J 新進程進入內存，首先放在S1的末尾，按FCFS排隊調度，

44、執行q時間片，若未完成，該進程轉入S2，依次類推。J 僅當Si空閑，才會調度Si+1中進程。 能較好地滿足各種類型用戶的需要。七. 死鎖1. 死鎖的概念死鎖是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能向前推進。2. 死鎖產生的原因（1） 競爭資源競爭非剝奪資源、競爭臨時性資源（2） 進程推進順序不當3. 產生死鎖的必要條件（同時具備）（1） 互斥條件進程對所分配到的資源進行排它性使用。（2） 請求和保持條件請求新資源阻塞，保持其它已獲得資源不放。（3） 不剝奪條件進程獲得的資源在使用完之前不能被剝奪。（4） 環路等待條件存在進程資源環形鏈。4. 處理死鎖的基本方法

45、（1） 預防死鎖設置某些限制條件，破壞必要條件中的一個或幾個。（2） 避免死鎖在資源的動態分配過程中，防止系統進入不安全狀態。（3） 檢測死鎖通過系統設置的檢測機構，及時檢測出死鎖的發生，并精確確定與死鎖有關的進程和資源。 保存有關資源的請求和分配信息資源分配圖資源分配圖由一組結點N和一組邊E組成。N被分成兩個互斥的子集，一組進程結點P=p1，p2,，pn，一組資源結點R=r1，r2,，rmE中的邊e連接著P中的一個結點和R中的一個結點。e=pi，ri 表示進程pi請求一個單位的ri資源e=rj，pj 表示把一個單位的rj資源分配給進程pj 提供算法檢測系統是否死鎖死鎖定理在資源分配圖上，找出

46、一個既不阻塞又非獨立的進程結點，簡化后使其成為孤立的結點。在進行一系列的簡化后，若能消去圖中所有的邊，使所有結點都成為孤立的結點，則該圖是可完全簡化的。所有的簡化順序將得到相同的不可簡化圖。s為死鎖狀態的充分條件是，當且僅當S狀態的資源分配圖是不可完全簡化的。（4） 解除死鎖將進程從死鎖狀態下解脫出來。J 剝奪資源J 撤消進程5. 銀行家算法 系統的安全狀態所謂安全狀態，是指系統能按某種順序，如P1,P2Pn，來為每個進程分配其所需資源，直至最大需求，使每個進程都可順利完成。若系統不存在這樣一個安全序列，則稱系統處于不安全狀態。如果不按照安全序列分配資源，則系統可能由安全狀態進入不安全狀態。例，系統共有12臺磁帶機，T0時刻的情況如下表，已分配出9臺，可用磁帶機為3臺。經分析發現，T0時刻存在安全序列P2，P1，P3，故系統是安全的。 進程 最大需求 已分配 尚需要 可用 P110 553（2）P24 22P39 2（3） 7（6）若此時P3請求1臺磁帶機，則分配情況如上表（括號內的數據），此時系統不存在安全序列，進入不安全狀態，將導致死鎖。 利用銀行家算法避免死鎖 數據結構（n個進程，m類資源）可利用資源available1.m最大需求矩陣(n*m) max分配矩陣(n*m) allocation需求矩陣(n*m) needi,j=