1、操作系統教程南郵正式版習題解答第三章 進程管理與調度習題1、什么是多道程序設計？多道程序設計利用了系統與外圍設備的并行工作能力，從而提高工作效率，具體表現在哪些方面？答：讓多個計算問題同時裝入一個計算機系統的主存儲器并行執行，這種設計技術稱“ 多道程序設計 ”，這種計算機系統稱“多道程序設計系統” 或簡稱“多道系統”。在多道程序設計的系統中，主存儲器中同時存放了多個作業的程序。為避免相互干擾，必須提供必要的手段使得在主存儲器中的各道程序只能訪問自己的區域。 提高工作效率，具體表現在：· 提高了處理器的利用率； · 充分利用外圍設備資源：計算機系統配置多種外圍設備，采用多道程

2、序設計并行工作時，可以將使用不同設備的程序搭配在一起同時裝入主存儲器，使得系統中各外圍設備經常處于忙碌狀態，系統資源被充分利用； · 發揮了處理器與外圍設備以及外圍設備之間的并行工作能力； 從總體上說，采用多道程序設計技術后，可以有效地提高系統中資源的利用率，增加單位時間內的算題量，從而提高了吞吐率。 2、請描述進程的定義和屬性。答：進程是具有獨立功能的程序關于某個數據集合上的一次運行活動，是系統進行資源分配、調度和保護的獨立單位。進程的屬性有：結構性共享性動態性獨立性制約性并發性3、請描述進程與程序的區別及關系。答：程序是靜止的，進程是動態的。進程包括程序和程序處理的對象（數據集）

3、，進程能得到程序處理的結果。進程和程序并非一一對應的，一個程序運行在不同的數據集上就構成了不同的進程。通常把進程分為“系統進程”和“用戶進程”兩大類，把完成操作系統功能的進程稱為系統進程，而完成用戶功能的進程則稱為用戶進程。 4、進程有哪三種基本狀態？三種進程狀態如何變化？答：通常，根據進程執行過程中不同時刻的狀態，可歸納為三種基本狀態： · 等待態 ：等待某個事件的完成； · 就緒態 ：等待系統分配處理器以便運行； · 運行態 ：占有處理器正在運行。 進程在執行中狀態會不斷地改變，每個進程在任何時刻總是處于上述三種基本狀態的某一種基本狀態，進程狀態之間轉換關系：

4、運行態等待態 往往是由于等待外設，等待主存等資源分配或等待人工干預而引起的。 等待態就緒態 則是等待的條件已滿足，只需分配到處理器后就能運行。 運行態就緒態 不是由于自身原因，而是由外界原因使運行狀態的進程讓出處理器，這時候就變成就緒態。例如時間片用完，或有更高優先級的進程來搶占處理器等。 就緒態運行態 系統按某種策略選中就緒隊列中的一個進程占用處理器，此時就變成了運行態。 5、進程控制塊是什么，有何作用？通常進程控制塊包含哪些信息？答：進程控制塊(Process Control Block,簡稱PCB)，是操作系統為進程分配的用于標志進程，記錄各進程執行情況的。進程控制塊是進程存在的標志，它

5、記錄了進程從創建到消亡動態變化的狀況，進程隊列實際也是進程控制塊的鏈接。操作系統利用進程控制塊對進程進行控制和管理。 ·標志信息 含唯一的進程名 ·說明信息 有進程狀態、等待原因、進程程序存放位置和進程數據存放位置 ·現場信息 包括通用、控制和程序狀態字寄存器的內容 ·管理信息 存放程序優先數和隊列指針 進程控制塊的作用有： · (1)記錄進程的有關信息，以便操作系統的進程調度程序對進程進行調度。這些信息包括標志信息、說明信息、現場信息和管理信息等； · (2)標志進程的存在，進程控制塊是進程存在的唯一標志 6、什么是可再入程序？答：

6、（1） 什么是 可再入程序 。 一個能被 多個用戶同時調用 的程序稱做" 可再入 "的程序。 （2） 可再入程序的性質。 · 可再入程序必須是純代碼，在執行時自身不改變； · 一個可再入程序要求調用者提供工作區，以保證程序以同樣方式為各用戶服務。 編譯程序 和 操作系統程序 通常都是"可再入"程序，能同時被不同用戶調用而構成不同的進程。 7、闡述進程調度的常用算法：先來先服務、優先數法、輪轉法。答：· 先來先服務調度算法 該算法按進程進入就緒隊列的先后次序選擇可以占用處理器的進程。 · 優先數調度算法 對每個進程確

7、定一個優先數，該算法總是讓優先數最高的進程先使用處理器。對具有相同優先數的進程，再采用先來先服務的次序分配處理器。系統常以任務的緊迫性和系統效率等因素確定進程的優先數。進程的優先數可以固定的，也可隨進程執行過程動態變化。 一個高優先數的進程占用處理器后，系統處理該進程時有兩種方法，一是"非搶占式"，另一種是"可搶占式"。前者是此進程占用處理器后一直運行到結束，除非本身主動讓出處理器，后者則是嚴格保證任何時刻總是讓優先數最高的進程在處理器上運行。 · 時間片輪轉調度法 把規定進程一次使用處理器的最長時間稱為"時間片"。時間片輪

8、轉調度算法讓就緒進程按就緒的先后次序排成隊列，每次總選擇該隊列中第一個進程占用處理器，但規定只能使用一個時間片，如該進程尚未完成，則排入隊尾，等待下一個供它使用的時間片。各個進程就這樣輪轉運行。時間片輪轉算法經常用于分時操作系統中。 8、程序狀態字包含哪些主要內容?答：(1)程序基本狀態 (2)中斷碼 (3)中斷屏蔽位9、比較進程調度與作業調度的不同點。答：1）作業調度是宏觀調度，它決定了哪一個作業能進入主存。進程調度是微觀調度，它決定各作業中的哪一個進程占有中央處理機。（或）作業調度是高級調度，它位于操作系統的作業管理層次。進程調度是低級調度，它位于操作系統分層結構的最內層。（2）作業調度是

9、選符合條件的收容態作業裝入內存。進程調度是從就緒態進程中選一個占用處理機。10、C程序說明系統調用fork()的應用。請在處填入有關父、子進程的正確語句： * Example to demonstrate the function of System Call fork * main() int i； if(i)0 printf(“”) ； else printf(“”) ； printf(“”) ； 執行本程序時，子進程在標準輸出上打印以下結果： It is child process Exit 父進程在標準輸出上打印以下結果： It is Parent process Exit11、單道批

10、處理環境下有5個作業，各作業進入系統的時間和估計運行時間如下表所示：作業進入系統時間估計運行時間/分鐘18:004028:203038:301249:001859:105 (1) 如果應用先來先服務的作業調度算法，試將下面表格填寫完整。作業進入系統時間估計運行時間/分鐘開始時間結束時間周轉時間/分鐘18:004028:203038:301249:001859:105作業平均周轉時間T= （2）如果應用最短作業優先的作業調度算法，試將下面表格填寫完整。作業進入系統時間估計運行時間/分鐘開始時間結束時間周轉時間/分鐘18:004028:203038:301249:001859:105作業

11、平均周轉時間T= 答：1 (1) 作業進入系統時間估計運行時間/分鐘開始時間結束時間周轉時間/分鐘18:00408：008：404028:20308：409：105038:30129：109：225249:00189：229：404059:1059：409：4535作業平均周轉時間T= 43.4217 （2）作業進入系統時間估計運行時間/分鐘開始時間結束時間周轉時間/分鐘18:00408：008：404028:20308：529：226238:30128：408：522249:00189：279：454559:1059：229：2717作業平均周轉時間T= 37.218612、有一個

12、具有兩道作業的批處理系統，作業調度采用短作業優先的非搶式調度算法，進程調度采用以優先數為基礎的搶占式調度算法，在下表所示的作業序列中，作業優先數即為進程優先數，優先數越小優先級越高。作業名 到達時間 估計運行時間 優先數A 10：00 40分 5B 10：20 30分 3C 10：30 50分 4D 10：50 20分 6（1）列出所有作業進入內存時間及結束時間。（2）計算平均周轉時間。答：每個作業運行將經過兩個階段：作業調度(SJF算法)和進程調度(優先數搶占式)。另外，批處理最多容納2道作業，更多的作業將在后備隊列等待。進程就緒隊列作業后備隊列時間(分鐘) 10:00 10:20 10:3

13、0 10:50 11:10 12:00 12:20A B A C DA D D C CPU(1) 10:00，作業A到達并投入運行。(2) 10:20，作業B到達且優先權高于作業A，故作業B投入運行而作業A在就緒隊列等待。(3) 10:30，作業C到達，因內存中已有兩道作業，故作業C進入作業后備隊列等待。(4) 10:50，作業B運行結束，作業D到達，按SJF短作業優先算法，作業D被裝入內存進入就緒隊列。而由于作業A的優先級高于作業D，故作業A投入運行。(5) 11:10，作業A運行結束，作業C被調入內存，且作業C的優先級高于作業D，故作業C投入運行。(6) 12:00，作業C運行結束，作業D

14、投入運行。(7) 12:20，作業D運行結束。作業 進入內存時間 運行結束時間 A 10:00 11:10 B 10:20 10;50 C 11:10 12:00 D 10:50 12:20各作業周轉時間為：作業A 70，作業B 30，作業C 90，作業D 90。平均作業周轉時間為70分鐘。第四章 并發進程的同步與互斥1、進程間同步和互斥的含義是什么?答：同步：并發進程之間存在的相互制約和相互依賴的關系。互斥：若干進程共享一資源時，任何時刻只允許一個進程使用。2、用文字描述銀行家算法的基本思想？ 答：銀行家算法的基本思想是：將系統中的所有資源比做銀行家的資金，每進行一次資源的分配，銀行家都要從

15、當前的資源分配情況出發，計算這種分配方案的安全性，如果是安全的，則進行分配，否則選擇其它可能的分配方案。這樣，每次分配都計算安全性，從而可以避免死鎖的發生。3、簡述死鎖的防止與死鎖的避免的區別。答：死鎖的防止是系統預先確定一些資源分配策略，進程按規定申請資源，系統按預先規定的策略進行分配，從而防止死鎖的發生。而死鎖的避免是當進程提出資源申請時系統測試資源分配，僅當能確保系統安全時才把資源分配給進程，使系統一直處于安全狀態之中，從而避免死鎖。4、試說明資源的靜態分配策略能防止死鎖的原因。答：資源靜態分配策略要求每個進程在開始執行前申請所需的全部資源，僅在系統為之分配了所需的全部資源后，該進程才開

16、始執行。這樣，進程在執行過程中不再申請資源，從而破壞了死鎖的四個必要條件之一“占有并等待條件”，從而防止死鎖的發生。5、有三個進程P1，P2和P3并發工作。進程P1需用資源S3和S1；進程P2需用資源S1和S2；進程P3需用資源S2和S3。回答：(1)若對資源分配不加限制，會發生什么情況?為什么?(2)為保證進程正確工作，應采用怎樣的資源分配策略?為什么?答：.(1)可能會發生死鎖例如：進程P1，P2和P3分別獲得資源S3，S1和S2后再繼續申請資源時都要等待(2分)，這是循環等待。(或進程在等待新源時均不釋放已占資源)(2)可有幾種答案：A.采用靜態分配由于執行前已獲得所需的全部資源，故不會

17、出現占有資源又等待別的資源的現象(或不會出現循環等待資源現象)。或B.采用按序分配不會出現循環等待資源現象。或C.采用銀行家算法因為在分配時，保證了系統處于安全狀態。、某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下列問題：(1)用PV操作管理這些并發進程時，應怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。(2)根據所定義的信號量，把應執行的PV操作填入適當，以保證進程能夠正確地并發執行。COBEGINPROCESSPI(I=1，2，) begin；進入售票廳；購票；退出

18、； end；COEND(3)若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)。答：.(1)定義一信號量S，初始值為20。意義：S>0S的值表示可繼續進入售 票廳的人數S=0表示售票廳中已有20名顧 客(購票者)S<0|S|的值為等待進入售票 廳的人數(2)P(S)進入售票廳；購票；退出；V(S)(3)S的最大值為20 S的最小值為20n注：信號量的符號可不同(如寫成t)，但使用時應一致(即上述的s全應改成t)。、假定系統有三個并發進程read, move和print共享緩沖器B1和B2。進程read負責從輸入設備上讀信息，每讀出一個記錄后把它存放到緩沖器B1中。進

19、程move從緩沖器B1中取出一記錄，加工后存入緩沖器B2。進程print將B2中的記錄取出打印輸出。緩沖器B1和B2每次只能存放一個記錄。要求三個進程協調完成任務，使打印出來的與讀入的記錄的個數，次序完全一樣。請用PV操作，寫出它們的并發程序。答：begin SR,SM1,SM2,SP:semaphore;B1,B2:record;SR:=1;SM1:=0;SM2:=1;SP:=0cobeginprocess readX:record;begin R: (接收來自輸入設備上一個記錄)X:=接收的一個記錄；P(SR)；B1:=X;V(SM1);goto R;end;Process moveY:r

20、ecord;beginM:P(SM1);Y:=B1;V(SR)加工 YP(SM2)；B2:=Y;V(SP);goto M;end;Process printZ:record;beginP:P(SP);Z:=B2;V(SM2)打印Zgoto P;end;coend;end;、某系統中有10臺打印機，有三個進程P1，P2，P3分別需要8臺，7臺和4臺。若P1，P2，P3已申請到4臺，2臺和2臺。試問：按銀行家算法能安全分配嗎？請說明分配過程。答：系統能為進程P3分配二臺打印機。因為盡管此時10臺打印機已分配給進程P1 4臺，P22臺和P34臺，全部分配完，但P3已分配到所需要的全部4臺打印機，它不

21、會對打印機再提出申請，所以它能順利運行下去，能釋放占用的4臺打印機，使進程P1，P2均可能獲得乘余的要求4臺和5臺，按銀行家算法是安全的。、有兩個用戶進程A和B，在運行過程中都要使用系統中的一臺打印機輸出計算結果。(1)   試說明A、B兩進程之間存在什么樣的制約關系？(2)   為保證這兩個進程能正確地打印出各自的結果，請用信號量和P、V操作寫出各自的有關申請、使用打印機的代碼。要求給出信號量的含義和初值。答：(1) A、B兩進程之間存在互斥的制約關系。因為打印機屬于臨界資源，必須一個進程使用完之后另一個進程才能使用。（2）mutex：用于互

22、斥的信號量，初值為1。 進程A 進程B . . . . P(mutex) P(mutex) 申請打印機 申請打印機 使用打印機 使用打印機 V(mutex) V(mutex)試以生產者消費者問題說明進程同步問題的實質。答：一個生產者，一個消費者和一個產品之間關系是典型的進程同步問題。設信號量S為倉庫內產品，P- V操作配對進行缺一不可。生產者進程將產品放人倉庫后通知消費者可用；消費者進程在得知倉庫有產品時取走，然后告訴生產者可繼續生產。、請描述產生死鎖的四個必要條件。答：互斥使用（資源獨占）一個資源每次只能給一個進程使用不可強占（不可剝奪）資源申請者不能強行的從資源占有者手中奪取資源，資源只能

23、由占有者自愿釋放請求和保持（部分分配，占有申請）一個進程在申請新的資源的同時保持對原有資源的占有（只有這樣才是動態申請，動態分配）循環等待存在一個進程等待隊列 P1 , P2 , , Pn, 其中P1等待P2占有的資源，P2等待P3占有的資源，Pn等待P1占有的資源，形成一個進程等待環路、兩個并發執行的進程A和B的程序如下： 進程ARepeatN=N+5;Until false; 進程BRepeat打印N的值；N=0；Until false;其中N為整數，初值為4。若進程A先執行了三個循環后，進程A和進程B又并發執行了一個循環，寫出可能出現的打印值。正確的打印值應該是多少？

24、請用P、V操作進行管理，使進程A和B并發執行時不會出現與時間有關的錯誤。  答：因為N初值為4，若進程A先執行了三個循環，此時N的值為19。當進程A和進程B并發執行時可能會有如下兩種執行次序，即進程A先執行一次循環，然后再進程B執行一次循環，此時打印的是正確值24，執行后N中的值為0。但若進程B先執行一次循環，然后再進程A執行一次循環，則打印的值是19，執行后N中的值是5。這是錯誤的，即發生了與時間有關的錯誤。用P、V操作進行管理，使進程A和B并發時不會出現與時間有關的錯誤的程序如下：（S為互斥信號量，初值為1），進程ARepeatP(S);N=N+5;V(S);Until fals

25、e; 進程BRepeatP(S);打印N的值；N=0；V(S);Until false;、四個進程P0，P1,P2,P3和四個信箱M0,M1,M2,M3進程間借助相鄰的信箱傳遞消息：   每次從 中取出一條消息，經加工送入 中。其中M0,M1,M2,M3分別設有3,3,2,2個格子，每個格子放一條消息，初始時，M0裝滿了三條消息，其余為空。寫出使用信號量實現進程 （i=0,1,2,3）同步及互斥的流程。答：mutex0 mutex3 : 分別用于控制互斥訪問M0 M 3，初值為1。full0 full3 : 分別用于控制同步訪問M0 M3 ,其中full0 初值為

26、3，full1 full3 初值為0，表示信箱中消息條數。empty0 empty3 : 分別用于同步控制對M0 M3的訪問。Empty0初值為0，empty2 empty3初值為2，empty1初值為3，分別用于表示信箱中空格子個數。另用send ( Mi , message )表示將消息送到（Mi mod 4）號信箱中；而用receive ( Mi，message )表示接收已存在于( Mi mod 4 )中的消息。則使用信號量實現進程Pi (i = 0 , 1 ,2 ,3 )同步及互斥的流程如下：mutex0 , m utex 1, m utex2 , m utex3 : semapho

27、re ;full0 , ful l1 , ful l2 , ful l3 : semaphore ;empty0 , em pty1 , em pty2 , em pty3 : semaphore ;begin    mutex0 : = 1 ;  mutex1 : = 1 ;  mutex2 : = 1 ;  mutex : = 1 ;   full0 : = 3 ;  full1 : = 0 ;  full2 : = 0 ;  fu

28、ll3 :  = 0 ;   empty0 : = 0 ;  empty1 : = 3 ;  empty2 : = 2 ;  empty3 : = 2 ;   Parbegin          P0：beginrepeat P ( mutex0 ) ;P ( full0 ) ;Receive ( M0,message);V (empty0 ) ;Processing the message until finish

29、ed;P ( mutex1 ) ;P ( empty1 ) ;Send ( M1,message ) ;V ( full1 ) ;V ( mutex1 ) ;                 Until false ;                               

30、      end ;         P1：可類似于P0實現之;         P2：可類似于P0實現之;         P3：可類似于P0實現之;       Parend ;     End;、設系統中僅有一類數量為M的獨占型資源，系統中N個進程競爭該類資源，其中各進程對該類資源的最大需求

31、量為W。當M、N、W分別取下列值時，試判斷哪些情況會發生死鎖？為什么？ M=2，N=2，W=1  M=3，N=2，W=2  M=3，N=2，W=3 M=5，N=3，W=2 M=6，N=3，W=3答：可能會發生死鎖。只要一個進程占用了少于3個獨占型資源而另一個進程占用了其余的獨占型資源，兩個進程都會相互處于等待對方進程釋放資源的狀態。也可能會發生死鎖。當每個進程都分配了兩個資源時，3個進程都會彼此等待。、假定具有5個進程的進程集合PP0,P1,P2,P3,P4,系統中有三類資源A，B和C。其中A類資源有10個，B類資源有5個，C類資源有7個。假定

32、在某時刻有如下狀態：Allocation               Max               Available                A   B   C          A&#

33、160;   B   C          A    B    C             P0  0   1    0         7    5    3      

34、0;   3    3     2            P1  2   0    0         3    2    2                  

35、0;               P2  3   0    2         9    0    2            P3  2   1    1      &#

36、160;  2    2    2            P4  0   0    2         4    3    3         試給出Need，并說明當前系統是否處于安全狀態，如果是，給出安全序列。如果不是，說明理由。答：當前系統處于

37、安全狀態，安全序列如下求解：work = Available = (3 , 3 , 2 )        尋找Needj <=  work  =  ( 3 , 3 , 2 ) (  j  = 0 , 1 , 2 , 3 , 4)        j = 1  Need1 = (1 ,2 ,3 ) < =  (3 , 3 , 2

38、)        work : =  (3 , 3 , 2 ) + (2 ,0 ,0 ) =  (5 , 3 , 2 )        尋找Needj <=  work  =  ( 5 , 3 , 2 ) (  j  = 0 , 2 , 3 , 4)        j =

39、3  Need3 = (0 ,1 ,1 ) < =  (5 , 3 , 2 )        work : =  (5 , 3 , 2 ) + (2 ,1 ,1 ) = (7 , 4 , 3 )        尋找Needj <=  work  =  (7 , 4 , 3 ) ( j = 0 , 2  , 4)  &

40、#160;     j = 4  Need4 = (4 ,3 ,1 ) < =  (7 , 4 , 3 )        work : =   (7 , 4 , 3 ) + (0 ,0 ,2 ) = (7 , 4 , 5)        尋找Needj <=  work  =  (7 , 4 , 5) (j

41、 = 0 , 2 )        j = 2  Need2 =  (6 ,0 ,0 ) < =  (7 , 4 , 5 )        work : =   (7 , 4 , 5 ) + (3 ,0 ,2 ) =  (10 , 4 , 7)         尋找Needj <=  w

42、ork  =  (10 , 4 , 7) ( j = 0 )        j = 0  work : =   (10 , 4 , 7 ) + (0 ,1 ,0 ) = (10 , 5 , 7)       所以安全序列為P1，P3，P4，P2，P0。、有一閱覽室，讀者進入時必須先在一張登記表上登記。該表中每個表項代表閱覽室中的一個座位。讀者離開時要消掉其登記信息。閱覽室共有50個座位。登記表每次僅允許一位讀者進行登

43、記或注銷。讀者登記時，發現登記表滿，他在閱覽室外等待，直至有空位再登記進入。試用類Pascal語言和P、V操作，描述讀者行為。答：Begin initial value of S is 50Parbegin   Begin register      P (S) ;     Register and enter into the reading room ;  End;    Begin leave off    R

44、egister off and leave ;    V (S) ;End ;         End ; 、考慮一個共有150個存儲單元的系統，如下分配給三個進程，P1最大需求70,己占有25；P2最大需求60,己占有40；P3最大需求60,己占有45。使用銀行家算法，以確定下面的任何一個請求是否安全。(1)P4進程到達，P4最大需求60,最初請求25個。(2)P4進程到達，P4最大需求60,最初請求35。如果安全，找出所有的安全序列；如果不安全，給出結果分配情況。答：(1)由于系統目前還有150-25-40-4

45、5=40個單元，P4進程到達，把25個單元分給它。這時系統還余15個單元，可把15個單元分給P3，它執行完后會釋放60個單元。于是可供P1(還要45個單元)，P2(還要20個單元)，P4(還要35個單元)任何一個執行。安全序列為： P1，P2，P3，P4，P3，P1，P2，P4 P1，P2，P3，P4，P3，P1，P4，P2 P1，P2，P3，P4，P3，P2，P1，P4 P1，P2，P3，P4，P3，P2，P4，P1 P1，P2，P3，P4，P3，P4，P1，P2 P1，P2，P3，P4，P3，P4，P2，P1(2)P4進程到達，P4最大需求60,最初請求35。如果把35個單元分給P4，系統還余5個單元，不再能滿足任何一個進程的需求，系統進入不安全狀態。、在一個盒子里，混裝了數量相等的黑白圍棋子。現在用自動分揀系統把黑子、白子分開，設分揀系統有二個進程P1和P2，其中P1揀白子；P2揀黑子。規定每個進程每次揀一子；當一個進程在揀時，不允許另一個進程去揀；當一個進程揀了一子時，必須讓另一個進程去揀。試寫出兩進程P1和P2能并發正確執行的程序。答：實質上是兩個進程的同步問題，設信號量S1和S2分別表示可揀白子和黑子，不失一般性，若令先揀白