第7章 習題解答
1.什么叫并發(fā)進程？
答：在多道程序設計系統(tǒng)中，作為單個作業(yè)可以同時執(zhí)行，而每一個作業(yè)又需要有多個進程的協(xié)作來完成。因此，系統(tǒng)會同時存在著許多進程，在單處理器的情況下，這些進程輪流的占用處理器，即一個進程的工作沒有全部完成之前，另一個進程就開始工作，我們說這些可同時執(zhí)行的進程具有并發(fā)性，并且把可同時執(zhí)行的進程稱為“并發(fā)進程”。
2.臨界區(qū)是怎樣定義？對臨界區(qū)的管理應符合哪些要求？
答：并發(fā)進程中與共享變量有關的程序段稱為“臨界區(qū)”。對若干個并發(fā)進程共享某一變量的相關臨界區(qū)得管理有三點要求：
①一次至多一個進程能夠進入臨界區(qū)，當有進程在臨界區(qū)執(zhí)行時，其他想進入臨界區(qū)執(zhí)行的進程必須等待。
②不能讓一個進程無限制的在臨界區(qū)執(zhí)行，即任何一個進入臨界區(qū)的進程必須有限的時間內退出臨界區(qū)。
③不能強迫一個進程無限期等待鍵入它的臨界區(qū)，即有進程退出臨界區(qū)時應讓一個等待進入臨界區(qū)的進程進入它的臨界區(qū)執(zhí)行。
3.采用PV操作作為同步機構時，假定與某共享變量相關的信號量S的值可在[-1，l］之間，問S的初值是哪個值？當S=－1，S=0，S=l時它們各自的物理含義是什么？
答：S的初值是 1.
S＝－l，表示有一個進程在等待進入臨界區(qū)執(zhí)行。
S＝0，表示已有一個進程在臨界區(qū)執(zhí)行，這時若有進程想進入臨界區(qū)則必須等待。
S＝l，表示無進程在臨界區(qū)執(zhí)行，若有進程想進入臨界區(qū)則可以立即進入。
4.A、B兩個火車站之間是單軌連接的，現(xiàn)有許多列車同時到A站，須經A再到達B站，列車出B站后又可分路行駛（如圖7－2）為保證行車安全，請你當調度時，你將如何調度列車？請你用PV操作為工具設計一個能實現(xiàn)你的調度方案的自動調度系統(tǒng)。
答：當A、B兩站之間無列車停駛時，可讓到達A站的一列車進人A、B站之間行駛。
當A石站之間有列車在行駛時，則到達A站者必須在站外等待。
當有列車到達B站后，讓等在A站外的一列車進入。
用一個信號量S來控制到達A站的列車能否進入單軌道行駛，S的初始值為l.列車到達A站后，先執(zhí)行P（S），若無列車在A、B站之間行駛，則執(zhí)行P（S）后立即進人單軌道行駛，到達B站后，執(zhí)行V（S），可釋放一個等待進入的列車進入行駛。若A、B站之間已有列車在行駛，則執(zhí)行P（S）后就等待，直到行駛者到了B站執(zhí)行V（S）后釋放一個欲進入者。
5.今有三個進程R、M、P，它們共享一個緩沖區(qū)。R負責從輸入設備讀信息，每次讀出一個記錄并把它存放在緩沖區(qū)中：M在緩沖區(qū)加工讀入的記錄；P把加工后的記錄打印輸出。輸入的記錄經加工輸出后，緩沖區(qū)中又可存放下一個記錄。請用P、V操作為同步機構寫出他們并發(fā)執(zhí)行時能正確工作的程序。
答：三個進程共用一個緩沖區(qū)，他們必須同步工作，可定義三個信號量：
S1：表示是否可把讀人的記錄放到緩沖區(qū)，初始值為1.
S2：表示是否可對緩沖區(qū)中的記錄加工，初始值為0.
S3：表示記錄是否加工好，可以輸出，初始值也為0.
三個進程可如下設計：
begin
S1，S2，S3：semaphore；
S1：＝l；S2：＝S3：＝0；
cobegin
process R
begin
L1：讀記錄；
P（S1）；
記錄存入緩沖區(qū)；
V（S2）；
goto L1；
end；
process M
begin
L2：P（S2）；
加工記錄；
V（S3）；
goto L2；
end；
process P
begin
L3：P（S3）；
輸出加工后的記錄；
V（S1）；
goto L3；
end；
coend；
end.
6.現(xiàn)有4個進程R1，R2，W1，W2，它們共享可以存放一個數(shù)的緩沖器B.進程R1每次把從鍵盤上投入的一個數(shù)存放到緩沖器B中，供進程W1打印輸出；進程R2每次從磁盤上讀一個數(shù)放到緩沖器B中，供進程W2打印輸出。當一個進程把數(shù)據(jù)存放到緩沖器后，在該數(shù)還沒有被打印輸出之前不準任何進程再向緩沖器中存數(shù)。在緩沖器中還沒有存入一個新的數(shù)之前不允許任何進程加快從緩沖區(qū)中取出打印是怎樣才能使這四個進程在并發(fā)執(zhí)行是協(xié)調的工作？
答：這四個進程實際上是兩個生產者 R1，R2和兩個消費者 W1，W2.各自生成不同的產品中各自的消費對象去消費，他們共享一個的緩沖器。由于緩沖器只能存放一個數(shù)，所以，R1和R2在存放數(shù)時必須互斥。而R1和W1、R2和W2之間存在同步。為了協(xié)調它們的工作可定義三個信號量：
S：表示能否把數(shù)存人緩沖器B，初始值為1.
S1：表示R1是否已向緩沖器存入從鍵盤上讀入的一個數(shù)，初始值為0.
S2：表示R2是否已向緩沖器存入從磁盤上讀入的一個數(shù)，初始值為0.
begin
S，S1，S2：semaphore；
S：＝1；S1：＝S2：＝0；
cobegin
process R1
xl ：integer
begin
L1：從鍵盤讀一個數(shù)；
x1：=讀入的數(shù)；
P（S）；
B：＝xl；
V（S1）；
goto L1；
end；
process R2
x2：integer；
begin
L2：從磁盤讀一數(shù)；
x2：=讀入的數(shù)；
P（S）；
B：＝x2；
V（S2）；
goto L2；
end；
process W1
y：integer；
begin
L3：P（S1）；
y：=B；
V（S）；
打印y中的數(shù)；
goto L3；
end；
process W2
z：integer
begin
L4：P（S2）；
z：=B；
V（S）；
打印z中的數(shù)；
goto L4；
end；
coend；
end.
7.兩個并發(fā)進程的程序如下：
begin
N：integer；
N：=3；
cobegin
process A
begin
L1：N：＝N＋5；
goto L1；
end；
process B
begin
L2：print（N）；
N：＝0；
goto L2；
end；
coend；
end.
若process A先執(zhí)行了三個循環(huán)后，process A和 process B又并發(fā)執(zhí)行了一個循環(huán)，寫出可能出現(xiàn)的打印值。請用PV操作實現(xiàn)同步，使兩并發(fā)進程能正確執(zhí)行。
答：可能的值是 18或 23.這是因為 process A執(zhí)行三個循環(huán)后，N＝18，之后 A和 B并發(fā)執(zhí)行，可能先執(zhí)行A中的N：=N＋5，再執(zhí)行B中的print（N）；這樣就會得到23，也可能先執(zhí)行B中的pint（N）；這就會得到18.
可以利用P、V操作實現(xiàn)同步：
begin
N：integer；
S：semphore；
S：＝l；
N：＝3；
cobegin
process A
begin
L1：P（S）；
N：＝N＋5；
V（S）；
gotO L1；
end；
process B
begin
L2：P（S）；
print（N）；
N：＝0；
V（S）；
goto L2；
end；
coend；
end.
8.通信機制中設置哪些基本通信原語？它們的功能是什么？
答：系統(tǒng)提供兩個與信箱通信有關的通信原語：send原語（發(fā)送）和 receive原語（接收）。send（B，M）原語把信件M送人到信箱B中，receive（B，X）原語從信箱B中取出一封信存放到指定的地址X中。
9.什么叫死鎖？什么原因會引起死鎖？
答：若系統(tǒng)中存在一組進程（二個或多個進程），他們中的每一個進程都占用某種資源而又都在等待其中另一個進程所占用的資源，這種等待永遠不能結束，就說系統(tǒng)出現(xiàn)“死鎖”。
進程死鎖的起因是系統(tǒng)提供的資源數(shù)比要求使用資源的進程數(shù)少，或者是若干個個進程要求資源的總數(shù)大于系統(tǒng)能提供的資源數(shù)。這時，進程間就會出現(xiàn)競爭資源的現(xiàn)象，如果對進程競爭的資源管理和分配不當就會引起死鎖。死鎖的出現(xiàn)是與資源分配策略和并發(fā)進程的執(zhí)行速度有關。
10.有哪些策略可防止和避兔死鎖？
答：防止死鎖的策略有：靜態(tài)分配、按序分配、剝奪式分配。銀行家算法可以避免死鎖。
11.某系統(tǒng)有輸入機和打印機各一臺，今有兩個進程都要同時使用他們，采用PV操作實現(xiàn)請求使用和歸還釋放后，還會產生死鎖嗎？若否，說明理由；若會產生死鎖則給出一種防止死鎖的方法。
答：如果 PV操作設計不當，仍會產生死鎖。假如用 S1 S2分別代表輸入機和打印機能否被使用的信號量，由于資源是共享的，所以必須互斥使用，因而它們的初始值都為l.
如果用如下方式實現(xiàn)請求使用和歸還釋放：
process QI
begin
P（S1）；
使用輸入機；
P（S2）；
使用打印機；
V（S2）；
V（S1）；
end；
process Q2
begin
P（S2）；
使用打印機；
P（S1）；
使用輸入機；
V（S2）；
V（S1）；
end；
那么就會出現(xiàn)Q1得到輸入機而 Q2得到打印機，雙方在不釋放已經有的資源的情況下又去申請新的資源，就會造成死鎖。
可以采用為資源編序號的方法，要求按序申請，如下：
process Q1
begin
P（S1）；
使用輸入機；
P（S2）；
使用打印機；
V（S2）；
V（S1）；
end；
process Q2
begin
P（S1）；
使用輸入機；
P（S2）；
使用打印機；
V（S2）；
V（S1）；
end.
12.某一系統(tǒng)分配資源的策略是：當進程提出申請資源時，只要系統(tǒng)有資源中是分配給它，系統(tǒng)無資源時讓它登臺。任一進程總是先釋放以占有的資源后在申請新的資源，且每次申請一個資源，系統(tǒng)中的進程得到資源后總能在有間內歸還。證明該系統(tǒng)不會發(fā)生死鎖。
答：任一進程P申請資源時出現(xiàn)兩種情況：
情況一，立即得到滿足，此時不會成為等待狀態(tài)，也就不存在引起死鎖的條件。
情況二，得不到滿足，處于等待資源狀態(tài)。此時，資源一定被另一進程 Q占有。進程 Q執(zhí)行時若不在申請資源，則必在有間里歸還資源，于是 P不會永遠等待。如果進程 Q執(zhí)行時還要申請資源，按題意，它一定先釋放占有的資源，于是 P也不會永遠等待。所以，任一進程申請資源總能在有間得到資源，因而不會產生死鎖。
1.什么叫并發(fā)進程？
答：在多道程序設計系統(tǒng)中，作為單個作業(yè)可以同時執(zhí)行，而每一個作業(yè)又需要有多個進程的協(xié)作來完成。因此，系統(tǒng)會同時存在著許多進程，在單處理器的情況下，這些進程輪流的占用處理器，即一個進程的工作沒有全部完成之前，另一個進程就開始工作，我們說這些可同時執(zhí)行的進程具有并發(fā)性，并且把可同時執(zhí)行的進程稱為“并發(fā)進程”。
2.臨界區(qū)是怎樣定義？對臨界區(qū)的管理應符合哪些要求？
答：并發(fā)進程中與共享變量有關的程序段稱為“臨界區(qū)”。對若干個并發(fā)進程共享某一變量的相關臨界區(qū)得管理有三點要求：
①一次至多一個進程能夠進入臨界區(qū)，當有進程在臨界區(qū)執(zhí)行時，其他想進入臨界區(qū)執(zhí)行的進程必須等待。
②不能讓一個進程無限制的在臨界區(qū)執(zhí)行，即任何一個進入臨界區(qū)的進程必須有限的時間內退出臨界區(qū)。
③不能強迫一個進程無限期等待鍵入它的臨界區(qū)，即有進程退出臨界區(qū)時應讓一個等待進入臨界區(qū)的進程進入它的臨界區(qū)執(zhí)行。
3.采用PV操作作為同步機構時，假定與某共享變量相關的信號量S的值可在[-1，l］之間，問S的初值是哪個值？當S=－1，S=0，S=l時它們各自的物理含義是什么？
答：S的初值是 1.
S＝－l，表示有一個進程在等待進入臨界區(qū)執(zhí)行。
S＝0，表示已有一個進程在臨界區(qū)執(zhí)行，這時若有進程想進入臨界區(qū)則必須等待。
S＝l，表示無進程在臨界區(qū)執(zhí)行，若有進程想進入臨界區(qū)則可以立即進入。
4.A、B兩個火車站之間是單軌連接的，現(xiàn)有許多列車同時到A站，須經A再到達B站，列車出B站后又可分路行駛（如圖7－2）為保證行車安全，請你當調度時，你將如何調度列車？請你用PV操作為工具設計一個能實現(xiàn)你的調度方案的自動調度系統(tǒng)。
答：當A、B兩站之間無列車停駛時，可讓到達A站的一列車進人A、B站之間行駛。
當A石站之間有列車在行駛時，則到達A站者必須在站外等待。
當有列車到達B站后，讓等在A站外的一列車進入。
用一個信號量S來控制到達A站的列車能否進入單軌道行駛，S的初始值為l.列車到達A站后，先執(zhí)行P（S），若無列車在A、B站之間行駛，則執(zhí)行P（S）后立即進人單軌道行駛，到達B站后，執(zhí)行V（S），可釋放一個等待進入的列車進入行駛。若A、B站之間已有列車在行駛，則執(zhí)行P（S）后就等待，直到行駛者到了B站執(zhí)行V（S）后釋放一個欲進入者。
5.今有三個進程R、M、P，它們共享一個緩沖區(qū)。R負責從輸入設備讀信息，每次讀出一個記錄并把它存放在緩沖區(qū)中：M在緩沖區(qū)加工讀入的記錄；P把加工后的記錄打印輸出。輸入的記錄經加工輸出后，緩沖區(qū)中又可存放下一個記錄。請用P、V操作為同步機構寫出他們并發(fā)執(zhí)行時能正確工作的程序。
答：三個進程共用一個緩沖區(qū)，他們必須同步工作，可定義三個信號量：
S1：表示是否可把讀人的記錄放到緩沖區(qū)，初始值為1.
S2：表示是否可對緩沖區(qū)中的記錄加工，初始值為0.
S3：表示記錄是否加工好，可以輸出，初始值也為0.
三個進程可如下設計：
begin
S1，S2，S3：semaphore；
S1：＝l；S2：＝S3：＝0；
cobegin
process R
begin
L1：讀記錄；
P（S1）；
記錄存入緩沖區(qū)；
V（S2）；
goto L1；
end；
process M
begin
L2：P（S2）；
加工記錄；
V（S3）；
goto L2；
end；
process P
begin
L3：P（S3）；
輸出加工后的記錄；
V（S1）；
goto L3；
end；
coend；
end.
6.現(xiàn)有4個進程R1，R2，W1，W2，它們共享可以存放一個數(shù)的緩沖器B.進程R1每次把從鍵盤上投入的一個數(shù)存放到緩沖器B中，供進程W1打印輸出；進程R2每次從磁盤上讀一個數(shù)放到緩沖器B中，供進程W2打印輸出。當一個進程把數(shù)據(jù)存放到緩沖器后，在該數(shù)還沒有被打印輸出之前不準任何進程再向緩沖器中存數(shù)。在緩沖器中還沒有存入一個新的數(shù)之前不允許任何進程加快從緩沖區(qū)中取出打印是怎樣才能使這四個進程在并發(fā)執(zhí)行是協(xié)調的工作？
答：這四個進程實際上是兩個生產者 R1，R2和兩個消費者 W1，W2.各自生成不同的產品中各自的消費對象去消費，他們共享一個的緩沖器。由于緩沖器只能存放一個數(shù)，所以，R1和R2在存放數(shù)時必須互斥。而R1和W1、R2和W2之間存在同步。為了協(xié)調它們的工作可定義三個信號量：
S：表示能否把數(shù)存人緩沖器B，初始值為1.
S1：表示R1是否已向緩沖器存入從鍵盤上讀入的一個數(shù)，初始值為0.
S2：表示R2是否已向緩沖器存入從磁盤上讀入的一個數(shù)，初始值為0.
begin
S，S1，S2：semaphore；
S：＝1；S1：＝S2：＝0；
cobegin
process R1
xl ：integer
begin
L1：從鍵盤讀一個數(shù)；
x1：=讀入的數(shù)；
P（S）；
B：＝xl；
V（S1）；
goto L1；
end；
process R2
x2：integer；
begin
L2：從磁盤讀一數(shù)；
x2：=讀入的數(shù)；
P（S）；
B：＝x2；
V（S2）；
goto L2；
end；
process W1
y：integer；
begin
L3：P（S1）；
y：=B；
V（S）；
打印y中的數(shù)；
goto L3；
end；
process W2
z：integer
begin
L4：P（S2）；
z：=B；
V（S）；
打印z中的數(shù)；
goto L4；
end；
coend；
end.
7.兩個并發(fā)進程的程序如下：
begin
N：integer；
N：=3；
cobegin
process A
begin
L1：N：＝N＋5；
goto L1；
end；
process B
begin
L2：print（N）；
N：＝0；
goto L2；
end；
coend；
end.
若process A先執(zhí)行了三個循環(huán)后，process A和 process B又并發(fā)執(zhí)行了一個循環(huán)，寫出可能出現(xiàn)的打印值。請用PV操作實現(xiàn)同步，使兩并發(fā)進程能正確執(zhí)行。
答：可能的值是 18或 23.這是因為 process A執(zhí)行三個循環(huán)后，N＝18，之后 A和 B并發(fā)執(zhí)行，可能先執(zhí)行A中的N：=N＋5，再執(zhí)行B中的print（N）；這樣就會得到23，也可能先執(zhí)行B中的pint（N）；這就會得到18.
可以利用P、V操作實現(xiàn)同步：
begin
N：integer；
S：semphore；
S：＝l；
N：＝3；
cobegin
process A
begin
L1：P（S）；
N：＝N＋5；
V（S）；
gotO L1；
end；
process B
begin
L2：P（S）；
print（N）；
N：＝0；
V（S）；
goto L2；
end；
coend；
end.
8.通信機制中設置哪些基本通信原語？它們的功能是什么？
答：系統(tǒng)提供兩個與信箱通信有關的通信原語：send原語（發(fā)送）和 receive原語（接收）。send（B，M）原語把信件M送人到信箱B中，receive（B，X）原語從信箱B中取出一封信存放到指定的地址X中。
9.什么叫死鎖？什么原因會引起死鎖？
答：若系統(tǒng)中存在一組進程（二個或多個進程），他們中的每一個進程都占用某種資源而又都在等待其中另一個進程所占用的資源，這種等待永遠不能結束，就說系統(tǒng)出現(xiàn)“死鎖”。
進程死鎖的起因是系統(tǒng)提供的資源數(shù)比要求使用資源的進程數(shù)少，或者是若干個個進程要求資源的總數(shù)大于系統(tǒng)能提供的資源數(shù)。這時，進程間就會出現(xiàn)競爭資源的現(xiàn)象，如果對進程競爭的資源管理和分配不當就會引起死鎖。死鎖的出現(xiàn)是與資源分配策略和并發(fā)進程的執(zhí)行速度有關。
10.有哪些策略可防止和避兔死鎖？
答：防止死鎖的策略有：靜態(tài)分配、按序分配、剝奪式分配。銀行家算法可以避免死鎖。
11.某系統(tǒng)有輸入機和打印機各一臺，今有兩個進程都要同時使用他們，采用PV操作實現(xiàn)請求使用和歸還釋放后，還會產生死鎖嗎？若否，說明理由；若會產生死鎖則給出一種防止死鎖的方法。
答：如果 PV操作設計不當，仍會產生死鎖。假如用 S1 S2分別代表輸入機和打印機能否被使用的信號量，由于資源是共享的，所以必須互斥使用，因而它們的初始值都為l.
如果用如下方式實現(xiàn)請求使用和歸還釋放：
process QI
begin
P（S1）；
使用輸入機；
P（S2）；
使用打印機；
V（S2）；
V（S1）；
end；
process Q2
begin
P（S2）；
使用打印機；
P（S1）；
使用輸入機；
V（S2）；
V（S1）；
end；
那么就會出現(xiàn)Q1得到輸入機而 Q2得到打印機，雙方在不釋放已經有的資源的情況下又去申請新的資源，就會造成死鎖。
可以采用為資源編序號的方法，要求按序申請，如下：
process Q1
begin
P（S1）；
使用輸入機；
P（S2）；
使用打印機；
V（S2）；
V（S1）；
end；
process Q2
begin
P（S1）；
使用輸入機；
P（S2）；
使用打印機；
V（S2）；
V（S1）；
end.
12.某一系統(tǒng)分配資源的策略是：當進程提出申請資源時，只要系統(tǒng)有資源中是分配給它，系統(tǒng)無資源時讓它登臺。任一進程總是先釋放以占有的資源后在申請新的資源，且每次申請一個資源，系統(tǒng)中的進程得到資源后總能在有間內歸還。證明該系統(tǒng)不會發(fā)生死鎖。
答：任一進程P申請資源時出現(xiàn)兩種情況：
情況一，立即得到滿足，此時不會成為等待狀態(tài)，也就不存在引起死鎖的條件。
情況二，得不到滿足，處于等待資源狀態(tài)。此時，資源一定被另一進程 Q占有。進程 Q執(zhí)行時若不在申請資源，則必在有間里歸還資源，于是 P不會永遠等待。如果進程 Q執(zhí)行時還要申請資源，按題意，它一定先釋放占有的資源，于是 P也不會永遠等待。所以，任一進程申請資源總能在有間得到資源，因而不會產生死鎖。