操作系統原理（第2版）習題參考答案

習題1

1.計算機系統主要由哪些部分組成？

答：通常，一個完整的計算機系統是由硬件和軟件兩大部分組成的。

2.解釋以下術語：硬件、軟件、特權指令、核心態、用戶態、多道程序設計、操作系

統、分時、實時、并發、并行、吞吐量、系統調用、純碼

答：硬件一一是指計算機物理裝置本身，它是計算機軟件運行的基礎。

軟件一一是與計算機系統操作有關的計算機程序、過程、規則以及相關的文檔資料的總

稱。

特權指令一一計算機的指令集中一類具有特殊權限的指令，只用于操作系統或其他系統

軟件，一般普通用戶不能直接使用。它主要用于系統資源的分配和管理。

核心態一一是處理機的一種運行模式。當執行操作系統程序時，處理機處于核心態。它

有較高的特權，可以執行所有的指令，包括一般用戶程序中不能使用的特權指令，從而能對

所有寄存器和內存進行訪問、啟動I/O操作等。

用戶態一一是處理機的一種運行模式。用戶程序是在用戶態下執行，它的權限較低，只

能執行指令集中非特權指令。

多道程序設計一一內存中同時存放多道程序，在管理程序的控制下交替地執行。這些作

業共享CPU和系統中的其他資源。

操作系統一一是控制和管理計算機系統內各種硬件和軟件資源、有效地組織多道程序運

行的系統軟件（或程序集合），是用戶與計算機之間的接口。

分時——是對時間的共享。在分時系統中，分時主要是指若干并發程序對CPU時間的共享。

實時一表示"及時”或“即時”。

并發——是指兩個或多個活動在同一?給定的時間間隔中進行。它是宏觀上的概念。

并行一一是指兩個或多個活動在同一時刻進行。

吞吐量——在一段給定的時間內，計算機所能完成的總工作量。

系統調用一是用戶在程序中能以“函數調用”形式調用的、由操作系統提供的子功能

的集合。每一個子功能稱做一條系統調用命令。它是操作系統對外的接口，是用戶級程序取

得操作系統服務的唯一途徑。

純碼一一是指在執行過程中，本身不作任何變化的代碼，通常是由指令和常數組成的。

3.什么是操作系統（OS）?它的主要功能是什么？

答：操作系統是控制和管理計算機系統內各種硬件和軟件資源、有效地組織多道程序運

行的系統軟件（或程序集合），是用戶與計算機之間的接口。

操作系統應具備的五大基本功能，即存儲管理、進程和處理機管理、文件管理、設備管

理、用戶接口。

4.操作系統主要有哪三種基本類型？各有什么特點？

答：傳統上說，最基本的類型有三種，即多道批處理系統、分時系統和實時系統。

批處理系統有兩個特點：一是“多道”，二是“成批”。

分時系統的特點是：同時性：若干用戶可同時上機使用計算機系統；交互性：用戶能方

便地與系統進行人一機對話；獨立性：系統中各用戶可以彼此獨立地操作，互不干擾或破壞;

及時性；用戶能在很短時間內得到系統的響應.

實時系統的特點是：對時間的嚴格限制和對可靠性的嚴格要求。

5.操作系統的基本特征是什么？

答：操作系統的基本特征是：并發、共享、異步性和抽象性。

6.何謂脫機I/O和聯機I/O?

答：脫機I/。是指輸入/輸出工作不受主機直接控制.而由衛星機專門負責完成I/O,主

機專門完成快速計算任務，從而二者可以并行操作。

聯機I/O是指作業的輸入、調入內存及結果的輸出都在CPU直接控制下進行。

7.操作系統一般為用戶提供了哪三種接口？各有什么特點？

答：現代操作系統通常向用戶提供如下三種類型的接口：程序接口=命令行接口和圖

形用戶接口。

程序接口的特點：①它是程序一級的接口，也稱系統調用或者廣義指令，是操作系統內

核與用戶程序、應用程序之間的接II;②它位于操作系統內核的最高層，并且只能在核心態

下執行；③在UNIX/Linux系統中，系統調用以C函數的形式出現。

命令行接口的特點：①它是操作系統與用戶的交互界面：②在提示符之后用戶從鍵盤上

輸入命令，命令解釋程序接收并解釋這些命令，然后把它們傳遞給操作系統內部的程序，執

行相應的功能；③這些命令及其解釋程序都在用戶態下運行，需要操作系統內核提供服務；

④在UNIX/Linux系統中，稱其為shell。

圖形用戶接口通常稱作圖形用戶界面（簡稱圖形界面）。其特點是：①它是用戶上機最宜

觀、方便的工具；②利用鼠標、窗I」、菜單、圖標等圖形界面工具，可以有效地使用系統服

務和各種應用程序及實用工具；③它是核外的用戶接口程序，在用戶態下運行。

8.操作系統主要有哪些類型的體系結構？

答：一般說來，操作系統主要有以下體系結構，即：單體結構,一層次結構虛擬機結

構、微內核結構和客戶■服務器結構。

9.多道程序設計的主要特點是什么？

答：多道程序設計的主要特點是：

①多道-內存中同時存放兩道或兩道以上的程序，它們共享CPU和系統中的其他資源。

②宏觀上開行一在一個時間段內，多個作業都在同時運行。

③微觀上串行一在某一個時刻，只有一道作業真正在CPU上運行，即：各作業都在管

理程序的控制下在一臺計算機上交替地執行。

10.系統初啟的一般過程是什么？

答：一般初啟過程分為硬件檢測、加載引導程序、列始化內核和實現用戶登錄等階段。

11.在計算機系統中操作系統處于什么地位？

答：操作系統是裸機之上的第一層軟件，它只在核心態模式下運行，受硬件保護，與硬

件關系尤為密切。操作系統是整個計算機系統的控制管理中心，其他所有軟件都建立在操作

系統之上。操作系統對它們既具有支配權力，又為其運行建造必備環境。

12.什么是處理機的核心態和用戶態？為什么要設置這兩種不同的狀態？

答：當執行操作系統程序時，處理機處于核心態。它有較高的特權，可以執行所有的指

令，包括一般用戶程序中不能使用的特權指令，從而能對所有寄存器和內存進行訪問、啟動

I/O操作等。

用戶程序是在用戶態下執行，它的權限較低，只能執行指令集中非特權指令。

設置這兩種不同狀態的目的是為了保護操作系統程序（特別是其內核部分），防止受到

用戶程序的損害。

13.下列哪些指令應該只在核心態下執行？

①屏蔽所有中斷

②讀時鐘日期

③設置時鐘日期

@改變指令地址寄存器的內容

⑤啟動打印

⑥清內存

答：只在核心態下執行的指令有：①屏蔽所有中斷。③設置時鐘日期。⑤啟動打印機。

⑥清內存。

14.設計實時操作系統必須首先考慮的因素是什么？

答：實時系統的一個重要特征就是對時間的嚴格限制和要求。實時系統的首要任務是調

度一切可利用的資源完成實時控制任務，其次才著眼F提高計算機系統的使用效率。所以，

設計實時操作系統必須首先考慮處理各種事件的時間限制。

15.你熟悉哪些操作系統？想一想你在使用計算機過程中，操作系統如何提供服務？

答：（個人發揮）通常，大家會熟悉以下操作系統：Windows,UNIX或Linux

使用計算機過程中，操作系統為用戶提供的服務包括：命令和數據輸入/輸出的管理，

內存的分配，用戶文件的管理，CPU的分配，設備管理等。

16.設計操作系統時采用層次結構有什么好處？

答：①結構關系清晰，提高系統的可靠性和安全性。②各層模塊的功能明確，提高系統

的可擴充性和可移植性。③各層間具有單向依賴性，增強系統的可維爐性。④符合軟件工程

的思想，便于實施研制開發。

17.一個分層結構的計算機系統由裸機，用戶，CPU調度和P、V操作，文件系統，作業

管理，內存管理，設備管理，命令管理等部分組成。試按層次結構的原則從外至內將它們重

新排列。

答：按層次結構的原則從外至內重新排列的順序應是：用戶，命令管理，作業管理，文

件系統，內存管理，設備管理，CPU調度和P、V操作，裸機。

18.UNIX系統屬于哪和類型的操作系統？其核心結構是怎樣的？

答：UNIX是當代最著名的多用戶、多進程、多任務分時操作系統。

UNIX系統可分為三層：靠近硬件的底層是內核，即UNIX操作系統常駐內存部分；核

心外的中間層是shell層；最高層是應用層。

UNIXS_5（BPsystemV）的核心結構如本書圖1-14所示（略）。

19.采用虛擬機結構的操作系統其主要優點和缺點是什么？

答：虛擬機結構的操作系統其主要優點是：①實現對裸機的更用，可以有多個不同的操

作系統運行在同一物理硬件機器之上；②提供一個比裸機有更方便擴展界面的計算機；③支

持多道程序處理能力。④多個不同操作系統的應用程序可以同時運行在同?裸機之上，是研

究操作系統技術的理想平臺。

其主要缺點是：①實現比較困難。要實現對底層硬件所有特性的完全模擬是相當困難的。

②由于應用程序運行在各自的操作系統之上，因此，系統運行性能受到影響。

20.采用微內核模式設計系統的主要優點是什么？

答：①精減核心的功能，提供了一種簡單的高度模塊化的體系結構，提高了系統設計及

使用的靈活性。②可移植性好。所有與具體機器特征相關的代碼，全部隔離在微內核中。③

可伸縮性好。操作系統能方便地進行定制、獷充或縮減，以適應硬件的快速更新和應用需求

的不斷變化。④實時性好。微內核可以方便地支持實時處理。⑤提供多線程機制，支持多處

理器的體系結構和分布式系統及計算機網絡。⑥系統安全性好。傳統的操作系統將安全性功

能建立在內核之外，因而它并不是很安全的。而微內核則將安全性作為系統內特性來進行設

計。

進程程序

進程是動態概念程序是爵態概念

進程具仃并發性.宏觀上同時運行程序本身具有順序性,程序的并發執行是通過進程實現的

進程具有獨立性，是一個能獨立運行的單位，是系統資源分

程序本身沒有此特性

配的基本單位,是運行調度的基本單位

程序和進程無一一對應關系，一個進程可順序執行多個程序一個程序可由多個進程共用

進程異步前進，公相互制約程序不具備此特性

然而，進程與程序之間存在密切關系，進程的功能是通過程序的運行得以實現的，進程

活動的主體是程序。進程不能脫離開具體程序而獨自存在。

進程的基本特征是：①動態性②并發性③調度性④異步性⑤結構性。

3.PCB的作用是什么？它是怎樣描述進程的動態性質的？

答：PCB是進程組成中最關鍵的部分。每個進程有唯一的進程控制塊；操作系統根據PCB

對進程實施控制和管理，進程的動態、并發等特征是利用PCB表現出來的；PCB是進程存在

的唯一標志。

PCB中有表明進程狀態的信息，該進程的狀態包括運行態、就緒態和阻塞態,它利用狀

態信息來描述進程的動態性質。

4.進程的基本狀態有哪幾種？試描繪進程狀態轉換圖。

答：(見本書P39)

5.進程進入臨界區的調度原則是什么？

答：(見本書P65-66)

6.用如圖2-38所示的進程狀態轉換圖能夠說明

有關處理機管理的大量內容。試回答：

①什么事件引起每次顯著的狀態變遷？

②下述狀態變迂因果關系能否發生？為什

么？

(A)2一1(B)3.2(C)4Tl

答：①就緒一運行：CPU空閑，就緒態進程被

調度程序選中。

運行一阻塞運行態進程因某種條件未滿足而放棄對CPU的占用，如等待讀文件。

阻塞一就緒阻塞態進程所等待的事件發生了，例如讀數據的操作完成。

運行f就緒正在運行的進程用完了本次分配給它的CPU時間片。

②下述狀態變遷：

(A)2-1,可以。運行進程用完了本次分配給它的時間片，讓出CPU,從就緒隊列中

選一個進程投入運行。

(B)3~2,不行。任何時候一個進程只能處于一種狀態，它既然由運行態變為阻定態，

就不能再變為就緒態。

(C)4-l,可以。某一阻塞態進程等待的事件出現了，而且此時就緒隊列為空，該進

程進入就緒隊列后馬上又被調度運行。

7.PCB表的組織方式主要有哪幾種？分別簡要說明。

答：(見本書P43-44)

8.簡述信號量的定義和作用。P、V操作原語是如何定義的？

答：信號量是協調相關進程活動的一種設施。一般信號量是由兩個成員組成的數據結構:

一個成員是整型變量，表示該信號量的值；另一個是指向PCB的指針。當多個進程都等待

同一信號量時，它們就排成一個隊列，山信號量的指針項指出該隊列的頭。

利用信號量和相應操作可以解決多個進程的互斥和同步問題。

（有關P、v操作原語的定義，參見本書P69-70。）

9.N個進程共享某一臨界資源，則互斥信號量的取值范圍為o

a.0~1b.-l-0c.1--（N-I）d.0--（N-l）

答：co由于互斥信號量的初值是1,而另一極端情況是某一個進程在訪問臨界資源，

其余NT個進程處于阻塞狀態，此時信號量的值為-（NT）。

10.簡述線程與進程的關系。

答：（參見本書P61；

11.實現線程主要由哪兩種方式？各有何優缺點？

答：（參見本書P61-62）

12.管程由哪些部分組成？有什么基本特性？

答：（參見本書P86）

13.計算機系統中產生死鎖的根本原因是什么？

答：產生死鎖的根本原因是資源有限且操作不當。

14.產生死鎖的四個必要條件是什么？一般對待死鉞的方法有哪三種？

答：發生死鎖的四個必要條件是：互斥條件、不可搶占條件、占有且申請條件和環路等

待條件。

解決死鎖的一般方法有：死鎖的預防、死鎖的避免、死鎖的檢測與恢復等二種。

15.死鎖預防的基本思想是什么？

答：死鎖預防的基本思想是：要求進程申請資源時遵循某種協議，從而打破產生死鎖的

4個必要條件中的一個或幾個（互斥條件不能被破壞），保證系統不會進入死鎖狀態。

16.死鎖避免的基本思想是什么？

答：死鎖避免的基本思想是：對進程所發出的每一個申請資源命令加以動態地檢查，并

根據檢查結果決定是否進行資源分配。就是說，在資源分配過程中若預測有發生死鎖的可能

性，則加以避免。這種方法的關鍵是確定資源分配的安全性。

17.什么是進程的安全序列？何謂系統是安全的？

答：（參見本書P93）

18.死鎖預防的有效方法是什么？死鎖避免的著名算法是什么？

答：死鎖預防的有效方法是：資源有序分配策略一分類編號，按序分配。

死鎖避免的著名算法是銀行家算法。

19.死鎖、"饑餓’’和活鎖之間的主要差別是什么？

答：①死鎖是一種僵局，在無外力干預下，處于死鎖狀態的全部進程都不能前進，即它

們都處于阻塞態，可能造成整個系統癱瘓；而現饑餓時系統照常運行，只是某個或某幾個

進程永遠也不能得到所需的全部服務；處于活鎖的進程是在不斷的改變狀態，并未被封鎖，

是可以“活動”的，活鎖有可能自行解開，死鎖則不能。

②造成死鎖的根本原因是資源有限且使用不當；造成饑餓的原因是資源分配策略或調度

策略不合適，如果采用先來先服務的資源分配策略就可以避免饑餓；造成活鎖的原因是進程

在輪詢地等待某個不可能為真的條件為真。

③發生死鎖時，一定至少有一個資源被無限期地占用而得不到釋放；而饑餓出現時，系

統中的每個資源占有者都在有限的時間內釋放它所占用的資源。活鎖是忙式等待，占用CPU

且不會主動讓出CPU。

20.在生產者-消費者問題中，如果對調生產者（或消費者）進程中的兩個P操作和兩

個V操作的次序，會發生什么情況？試說明之。

答：在生產者-消費者問題中，如果對調生產者進程中的兩個P操作，形如：

生產者進程Producer：

while(TRUE){

P(mutcx);

P(empty);

V(mutex);

V(full);

)

當緩沖區全滿時，只要有一個生產者進程試圖進入臨界區，并在empty信號量上阻塞，

所有消費者進程都無法進入自己的臨界區(在信號量mutex上阻塞)，從而無法使該生產者

進程醒來。于是，所有生產者進程和消費者進程都無限期地處于阻塞狀態，從而出現死鎖。

然而，如果對調生產者進程中的兩個V操作，并不出現任何故障，只是從進程退出臨

界區的角度考慮，應越快越好。

如果對調消費者進程中的兩個P操作，也會產生同群的死鎖問題。

21.高級進程通信有哪幾類？各自如何實現進程間通信？

答：(參見本書P78-79)

22.是否所有的共享資源都是臨界資源？為什么？

答：不足所有的共享資源都是臨界資源。因為臨界資源是一次僅允許一個進程使用的資

源，而系統中有很多資源可以讓多個進程同時使用，例如硬盤、正文段等。

23.系統中只有一臺打印機，有三個用戶的程序在執行過程中都要使用打印機輸出計算

結果。設每個用戶程序對應一個進程。問：這三個進程間有什么樣的制約關系？試用P、V

操作寫出這些進程使用打印機的算法。

答：因為打印機是一種臨界資源，所以這三個進程只能互斥使用這臺打印機，即一個川

戶的計算結果打印完之后，另一個用戶再打印。

設三個進程分別為A,B和C,如圖1所示。設一個互斥信號量為mutex,其初值為1。

A進程B進程C進程

P(mutex)P(mutex)P(mutex)

使用打印機使用打印機使用打印機

V(mutex)V(mutcx)V(mutcx)

圖I

24.判斷下列同步問勉的算法是否正確？若有錯，請指出錯誤原因并予以改正。

①設A,B兩個進程共用一個緩沖區Q,A向Q寫入信息，B從Q讀出信息，算法框

圖如圖2-39所示。

②設A,B為兩個并發進程，它們共享一個臨界資源。其運行臨界區的算法框圖如圖

2-40所示。

進程A進程B進程A進程B

信號費SLS2的初值均為0

信號量$的初值為0

圖2-39進程A,B的算法框圖圖2-40兩個并發進程臨界區的算法框圖

答：①這個算法不對，因為A,B兩進程共用一個緩沖區Q,如果A先運行，且信息數

量足夠多，那么緩沖區Q中的信息就會發生后面的沖掉前面的，造成信息丟失，B就不能

從Q中讀出完整的信息。

改正：A,B兩進程要同步使用緩沖區Q。為此，設立兩個信號量。empty—緩沖區Q

為空，初值為1。full——緩沖區Q為滿，初值為0。

算法框圖如圖2所示。

②這個算法不對。因為A,B兩個進程是并發的，它們共享一個臨界資源，所以二者應

互斥地使用該臨界資源，在進入臨界區時不存在A先B后的時序關系，而是哪個進程先到

?步就先進入自口的臨界區。

改正:A,B兩個進程應互斥地進入臨界區。為此，設立一個信號量：互斥信號量為mutex,

其初值為算法框圖如圖3所示。

A進程B進程A進程B進程

P(empty)P(full)P(mutex)P(mutex)

向Q寫入植息

從Q中讀出信息臨界區代碼CSa臨界區代碼CSb

V(fiill)V；empty)V(mutex)V(mutex)

圖2圖3

25.設有一臺計算機，有兩條I/O通道，分別接一臺卡片輸入機和一臺打印機。卡片機

把一疊卡片逐一揄入到緩沖區B1中，加工處理后再搬到緩沖區B2中，并在打印機上打印

結果。問：

①系統要設幾個進程來完成這個任務？各自的工作是什么？

②這些進程間有什么樣的相互制約關系？

③用P、V操作寫出這些進程的同步算法。

答：①如圖4所示，系統可設三個進程來完成這個任務：R進程負責從卡片輸入機上讀

入卡片信息，輸入到緩沖區B1中；C進程負責從緩沖區B1中取出信息，進行加工處理，

之后將結果送到緩沖區B2中；P進程負責從緩沖區B2中取出信息，并在打印機上印出。

R進程C進程P進程

P(Blempty)P(Blfull)P(B2full)

輸入信息寫入緩沖區Bl從Bl中取出信息從B2中取出信息進行打印

V(Blfull)V(Blempty)V(B2cmpty)

P(B2empty)

加工信息

結果送入B2

V(B2ftill)

圖4

②R進程受C進程影響，B1放滿信息后R進程要等待，等到C進程將其中信息全部取

走，才能繼續讀入信息；C進程受R進程和P進程的約束，BI中信息放滿后C進程才可從

中取出它們，且B2被取空后C進程才可將加工結果送入其中：P進程受C進程的約束，B2

中信息放滿后P進程才可從中取出它們，進行打印。

③信號量含義及初值：Blfull——緩沖區BI滿，初值為0。Blempty——緩沖區B1空，

初值為1。B2full——線沖區B2滿，初值為0。B2empty——緩沖區B2空，初值為1。

同步算法如圖4所示。

26.設有無窮多個信息，輸入進程把信息逐個寫入緩沖區，輸出進程逐個從緩沖區中取

出信息。針對下述兩種情況：

①緩沖區是環形的，最多可容納〃個信息；

②緩沖區是無窮大的。

試分別回答下列問題：

①輸入、輸出兩組進程讀/寫緩沖區需要什么條件？

②用P、V操作寫出榆入、輸出兩組進程的同步算去，并給出信號量含義及初值。

答；(1)①輸入、輸出兩組進程讀/寫緩沖區需要的條件是；

-所有進程都要互斥使用緩沖區。

?所有輸入進程連續寫入緩沖區的個數不能超過緩沖區的總容量(n)o

?輸出進程不能超前輸入進程。

②設置三個信號量：

full—放有信息的緩沖區數，其初值為0。

empty——可供使用的緩沖區數，其初值為n。

mutex—互斥信號量，初值為1,表示各進程互斥進入臨界區，即保證任何時候只有一

個進程使用緩沖區。

兩個計數變量：in和。ut分別是輸入進程和輸出進程使用的計數量，衣示下面使用的緩

沖區編號，初值都是0。

輸入進程：輸出進程：

while(TRUE)(while(TRLE)(

P(empty);P(full);

P(mutex);P(mutex);

信息送往buffer(in):從bufiier(out)中取出信息

in=(in+1)modn;/*以n為模*/out=(out+1)?nodn;/*以n為模*/

V(mutex);V(mu.ex);

V(full);V(cmpty);

)

（2）①輸入、輸出兩組進程讀/寫緩沖區需要的條件是所有進程都要互斥使用緩沖區;

輸出進程不能超前輸入進程。

②信號量：full——緩沖區滿的情況，初值為0。mutex-----互斥信號量，初值為1。

計數器：i=0,j=0（i,j分別為輸入進程和輸出進程使用的緩沖區號碼）。

輸入進程：輸出進程：

while(TRUE){while(TRUE){

P(mutex);P(full);

信息送往buffer(i);P(mutex);

i=i+l;從hif￥er（j）中取出信息；

V(mutex);j=j+l；

V(full);V(mutex);

})

27.假定一個閱覽室最多可容納100人，讀者進入和離開閱覽室時都必須在閱覽室門口

的一張登記表上做標識（進入時登記，離開時去掉登記項），而且每次只允許一人登記或去

掉登記。問:

①應編寫幾個程序完成此項工作？程序的主要動作是什么？應設置幾個進程？進程與

程序間的對應關系如何？

②用P、V操作寫出這些進程的同步通信關系。

答：①完成此項工作可編寫一個或兩個程序（函數），要求：

每個讀者對應一個進程。

每個讀省的動作包括：

,入室前查表、登記---register（）o

-進入室內，閱讀書籍。

,出室時刪除登記項----delete（）。

進程是程序的一次執行過程，程序和進程無一一對應關系。

②信號量：

S——座位情況，初值為100o

mutex----互斥使用登記表，初值為1。

下面給出兩種解決方案：

第一種方案（僅一個程序）第二種方案（3個困數）

每位讀者進程typedefintsemaphore;

Isemaphores=IOO:

P(S)semaphoremutex=I;

P(mutex)voidmain()

查表，登記

V(mutex)regisler():

入室，閱讀rcading();

P(mutcx)dclete();

出室查表，刪除登記項

V(mutex)voidregister)

V(S)(

P(S);

P(mutex);

Check_regisier();

V(mutex);

}

voiddelctc()

{

P(mutcx);

Check_delete();

V(mutex);

V(S);

)

28.在一個飛機訂票系統中，多個用戶共享一個數據庫。各用戶可以同時查詢信息，若

有一個用戶要訂票，需更新數據庫時，其余所有用戶都不可以訪問數據庫。請用P、V操作

設計一個同步算法，實現用戶查詢與訂票功能。要求：當一個用戶訂票而需要更新數據庫時,

不能因不斷有查詢者到來而使其長時間等待。利用信號量機制保證其正常執行。

答：本題是典型的讀者-寫者問題。查詢信息的用戶是讀者，訂票用戶是寫者，并且要

求寫者優先。

【解法1】讀者-寫者按先后順序交叉訪問數據庫，如圖5所示。

讀者進程寫者進程

P⑸P(S)

P(Src)P(Sw)

rc=rc+1更新數據庫內容

iRrc==l)P(Sw)V(Sw)

V(Src)V(S)

V(S)

查詢庫中信息

P(Src)

iv-ic-l

if(rc==O)V(Sw)

V(Src)

圖5

計數變量：rc——正在運行的查詢者進程數目，初值為0。

信號量：Sw——控制訂票者進程的活動，初值為1。

Src—互斥使用rc變量，初值為L

S——當訂票者到達時封鎖后續的讀進程，初值為1。

【解法2】保證寫者優先于讀者，即一旦有寫者到達時，則新讀者要等待。

信號量：

rmutex一一當至少有一個寫者到達時，阻止所有讀者訪問的互斥操作信號量，初值為1。

wmutex——寫者間以及讀者與寫者間互斥操作信號量，初值為1。

x------控制rcadcount變量修改的互斥信號量，初值為1。

y------控制writecount變量修改的互斥信號量，初值為1。

z——有寫者時，只允許一個讀者在rmutex上排隊，其他讀者在信號量z上排隊，初值

為1。

計數變量：

readcount-----讀者計數器，初值為0。它控制對wmutex的設置。

writecount------寫者數目，初值為0。它控制對rmutex的設置。

讀者進程寫者進程

while(TRUE){while(TRUE){

P(z)；P(y);

P(rmutex);writecount++;

P(x);if(writecount==1)

iciukuun.++,P(llllUlVA),

if(readcount==1)V(y);

P(wmulex);P(wmulcx);

V(x);執行寫操作

V(nnutex);V(wmutex);

Mz);p(y);

執行讀操作wntccount

P(x):if(writecount==0)

readcoun:—;V(rmutex);

if(readcount==0)V(y);

V(umutex);)

V(x);

)

29.某高校計算機系開設網絡課，安排了上機實習。假設機房共有2m臺機器，有2n

名學生選該課，規定：

①每兩個學生為一組，各占一臺機器，協同完成上機實習。

②只有一組兩個學生都到齊，并且此時機房有空用機器時，該組學生才能進入機房。

③上機實習由一名教師檢查，檢查完畢，一組學生同時離開機房。試用P、V操作模擬

上機實習過程。

答：除學生進程、教師進程外，為保證系統控制流程，需另設一個監控進程，用于控制

學生的進入和計算機的分配，如圖6所示。

信號量：

student------學生到達情況，初值為0。

computer-----計算機分配情況，初值為2m。

entei-能否進入機房情況，初值為0。

finish—學生完成情況，初值為0。

check——檢查工作完成情況，初值為0。

學生進程教師進程監控進程

V(student)

P(compnter)P(finish)P(student)

P(enter)P(finish)P(student)

與伙伴一起實習檢查學生實習筲況V(entcr)

V(flnish)V(check)V(cntcr)

P(chcck)V(check)

V(computcr)

圖6

30.用P、V操作實現本書2.6節介紹的哲學家進卷問題的第2種解法，即：僅當某哲

學家面前的左、右兩支筷子均可用時，才允許他拿起筷子。

答：用P、V操作實現本書2.6節介紹的哲學家進餐問題的第2種解法，即：僅當某哲

學家面前的左、右兩支筷子均可用時，才允許他拿起筷子。

設立一個整型數組state,用來保存各位哲學家的狀況：進餐（EATING）、思考

（THINKING）或者饑餓（HUNGRY,想拿筷子）。一位哲學家僅當其左右鄰座都不進餐

時，他才能進餐。第i位哲學家的兩位鄰座由宏LEFT和RIGHT定義：如果i是2,則LEFT

是1,RIGHT是3。

程序中使用一個信號量數組S,每位哲學家對應其口一個元素（初值為0）。如果感到

饑餓的哲學家所用的筷子正被別人占用著，他就等待（阻塞）。注意，每個進程都從主代碼

philosopher開始執行。

#defineN5

#defineLEFT(i+N-l)%N

#defineRIGHT(i+l)%N

#dcfincTHINKING0

#defineHUNGRYI

#defineEATING2

typedefstruct{/*定義結構型信號量*/

intvalue;

structPCB*list;

}semaphore;

intstate[N];

semaphoremu(ex=I;/*互斥進入臨界區*/

semaphores[N];/*每位哲學家一個信號量*/

voidphilosopher(inti)

while(TRl'E){

think();/*哲學家在思考問題*/

take_chopstick(i);/*拿到兩根筷子或者等待*/

eat();/*進餐*/

put_chcpstick(i);/*把筷子放回原處*/

}

}

voidlake_chopsuck(inti)

[

P(mutex);

state[i]=HLNGRY;

test(i);/*試圖拿兩根筷子*/

V(mutex);

P(s[iJ)；

voidput_chopstick(inti)

{

P(mutex);

state[i]=THINKING;

tcsKLEFT):/*查看左鄰，現在能否進餐*/

tcst(RIGHT);/*查看右鄰，現在能否進餐*/

V(mu(ex);

I

voidtest(inti)

{

if(state[i]==HUNGRY&&state[LEFT]!=EATING&&sta(e[RIGHT]!=EATING){

state(il=EATING;

V(s[i]):

)

31.某個計算機系統有10臺可用磁帶機。在這個系統上運行的所有作業最多要求4臺

磁帶機。此外，這些作業在開始運行的很長一段時間內只要求3臺磁帶機；它們只在自己工

作接近結束時才短時間地要求另一臺磁帶機。這些作業是連續不斷地到來的。

①若作業調度策略是靜態分配資源，滿足后方可運行。那么，能同時運行的最大作業

數是多少？作為這種策略的后果，實際上空閑的磁帶機最少是幾臺？最多是幾臺？

②若采用銀行家算法將怎樣進行調度？能夠同時運行的最大作業數足多少？作為其

后果，實際上空閑的磁帶機最少和最多各是多少臺？

答：①能同時運行的最大作業數是2,實際上空閑的磁帶機最少是2臺，最多是4臺。

②作業對磁帶機資源提出請求時，系統判斷：若分配的話，系統是否仍處于安全狀態。

在3個作業各分到3臺磁帶機的情況下，系統仍然是安全的。所以，能同時運行的最大作業

數是3,實際上空閑的磁帶機最少和最多臺數各是0和I。

32.設有三個進程P1,P1,P3,各按如下所示順序執行程序代碼：

進程P1進程P2進程P3

P(s1)P(s3)P(s2)

P(s2)P(s1)P(s3)

V(s1)V(s3)V(s2)

V(s2)V(s1)V(s3)

其中s1,s2,s3是信號量，且初值均為1.

在執行時能否產生死鎖？如果可能產生死鎖，請說明在什么情況下產生死鎖？并紿出一

個防止死鎖產生的修改辦法。

答：可能產生死鎖。因為當進程P1執行P(sl),進程P2執行P(s3),進程P3執行P(s2)

后，三個資源(即信號量sl,s2,s3)被三個進程分別占用，接下來任何一個進程都無法得到

所申請的資源，于是都無限地循環等待，造成死鎖。

一個防止死鎖產生的辦法是：進程申請信號量時，按序申請。如圖7所示

進程Pl進程P2進程P3

II1

P(sl)P(sl)P(s2)

P(s2)P(s3)P(s3)

V(sl)V(sl)V(s2)

V(s2)V(s3)V(s3)

圖7

33.考慮由〃個進程共享的具有m個同類資源的系統，如果對/=1,2,…，n,有Need,，

>0,并且所有最大需求量之和小于府〃，試證明：該系統不會產生死鎖。

答：設每個進程對共享資源的最大需求量為max(0VmaxW〃?)，由于每個進程最多申請

使用max個資源，在最壞的情況下，每個進程都得到(max-1)個資源，并且都需要申請最后

一個資源v此時，系統剩余的資源為只要系統還有一個資源可用，就可以使

其中的?個進程獲得所需的全部資源。進而該進程運行結束后，釋放出它占用的資源，供其

他進程使用，從而所有的進程都可以運行完成。就是說，當〃L〃(max-l)2l時，系統不會

發生死鎖。整理該不等式,得到如下關系：〃XmaxW(m+1),所以，〃XmaxWm+〃。從而

證明〃個進程所有最大需求量之和小于時，該系統不會產生死鎖。

34.設系統中有三種類型的資源(4B,。和五個進程(月，月，月，PA,只)，4資源的

數量為17,8資源的數量為5,C資源的數量為20。在心時刻系統狀態如表270所示。系

統采用銀行家算法來避免死鎖。

①7；時刻是否為安全狀態？若是，請給出安全序列。

②在石時刻，若進程月請求資源(0,3,4),能否實現資源分配？為什么？

③在②的基礎上，若進程月請求資源(2,0,1),能否實現資源分配？為什么？

④在③的基礎上，若進程月請求資源(0,2,0),能否實現資源分配？為什么？

表2-10萬時刻系統狀態

最大瓷箱需求量已分配波源數量系統利余資源數量

進程

ABCABcABC

p、559212233

536402

p4011405

A425204

P424314

答：①71）時刻是安全狀態，因為存在一個安全序列｛〃4，P5，P1，P2，P3｝。

②不能實現資源分配，因為所剩余的資源數量不夠。

③可以分配。當分配完成后，系統剩余的資源向量為（0,3,2）,這時，仍可找到一個

安全序列（PA,P5,pi,P2,P3｝o

④不能分配。如果分配的話，則系統剩余的資源向最為（0,I,2）,這時無法找到一個

安全序列c

習題3

1.解釋以下術語：作業調度、進程調度、周轉時間、平均周轉時間、響應時間、中斷、

中斷源、中斷請求、中斷向量

答：作業調度一是根據一定的算法，從輸入的一批伶業中選出若干個作業，分配必要的

資源，如內存、外設等，為它建立相應的用戶作業進程和為其服務的系統進程（如輸入、輸

出進程），最后把它們的程序和數據調入內存，等待進程調度程序對其執行調度，并在作業

完成后作善后處理工作。

進程調度一是根據一定的算法將CPU分派給就緒隊列中的一個進程。

周轉時間一從作業提交到作業完成的時間間隔。

平均周轉時間一系統中n個作業周轉時間的算術平均值。

響應時間一從提交第一個請求到產生第一個響應所用的時間。

中斷--是指CPU對系統發生的某個事件作出的一種反應，CPU暫停正在執行的程序，保

留現場后自動地執行相應的處理程序，處理完該事件后，如被中斷進程的優先級最高，則返

回斷點繼續執行被“打斷”的程序。

中斷源一引起中斷的事件或發出中斷請求的來源稱為中斷源。

中斷請求一中斷源向CPU提出進行處理的請求。

中斷向量一中斷向量表的表項,通常包括相應中斷處理程序入口地址和中斷處理時處理

機狀態字PSW。

2.處理機調度的主要目的是什么？

答：處理機調度的主要目的就是為了分配處理機，處理機分配由調度和分派兩個功能組

成。

3.高級調度與低級調度的主要功能是什么？為什么要引入中級調度？

答：高級調度的主要力能是根據一定的算法，從輸入的一批作業中選出若干作業，分配

必要的資源，如內存、外設等，為它建立相應的用戶作業進程和為其服務的系統進程（如輸

入/輸出進程），最后把它們的程序和數據調入內存，等待進程調度程序對其執行調度，并在

作業完成后做善后處理工作。

低級調度的主要功能是根據一定的算法將CPU分派給就緒隊列中的一個進程。

為了使內存中同時存放的進程數目不至于太多，有時需要把某些進程從內存移到外存

上，以減少多道程序的數目，為此設立了中級調度。引入中級調度的主要目的是為了提高內

存的利用率和系統吞吐量，它實際上就是存儲管理中的對換功能。

4.處理機調度一般分為哪三級？其中哪一級調度必不可少？為什么？

答：處理機調度般分為三級調度：高級調度（又稱作業調度）、中級調度和低級調度

（又稱進程調度）。

其中，進程調度必不可少。

CPU是計算機最主要的資源。進程只有在得到CPU之后才能真正活動起來，所有就緒進

程經由進程調度才能獲得CPU的控制權。實際上，進程調度完成一臺物理的CPU轉變成多臺

虛擬（或邏輯）的CPU的工作；進程調度的實現策略往往決定了操作系統的類型，其算法優

劣直接影響整個系統的性能。

5.作業在其存在過程中分為哪四種狀態？

作業在其存在過程中分為提交、后備、執行和完成4種狀態。

6.在OS中，引起進程調度的主要因素有哪些？

答：一般說來，當發生以下事件后要執行進程調度：正在運行的進程任務完成，或等待

資源，或運行到時，或核心發現系統中“重新調度”標志被置上。

7.作業調度與進程調度二者間如何協調工作？

答：作業調度從外存的后備隊列中選擇一批作業調入內存，為它們創建進程，這些進程

被送入就緒隊列。進程調