1. 線程和進程，怎麼實現線程的同步
線程同步機制：
臨界區(Critical Section)、互斥量(Mutex)、事件(Event)、信號量(Semaphore)四種方式
1、臨界區：又稱阻塞,通過對多線程的串列化來訪問公共資源或一段代碼，速度快，適合控制數據訪問。在任意時刻只允許一個線程對共享資源進行訪問，如果有多個線程試圖訪問公共資源，那麼在有一個線程進入後，其他試圖訪問公共資源的線程將被掛起，並一直等到進入臨界區的線程離開，臨界區在被釋放後，其他線程才可以搶占。
使用臨界區域的第一個忠告就是不要長時間鎖住一份資源。這里的長時間是相對的，視不同程序而定。對一些控制軟體來說，可能是數毫秒，但是對另外一些程序來說，可以長達數分鍾。但進入臨界區後必須盡快地離開，釋放資源。如果不釋放的話，會如何？答案是不會怎樣。如果是主線程（GUI線程）要進入一個沒有被釋放的臨界區，呵呵，程序就會掛了！臨界區域的一個缺點就是：Critical Section不是一個核心對象，無法獲知進入臨界區的線程是生是死，如果進入臨界區的線程掛了，沒有釋放臨界資源，系統無法獲知，而且沒有辦法釋放該臨界資源。
2、互斥量：採用互斥對象機制。只有擁有互斥對象的線程才有訪問公共資源的許可權，因為互斥對象只有一個，所以能保證公共資源不會同時被多個線程訪問。互斥不僅能實現同一應用程序的公共資源安全共享，還能實現不同應用程序的公共資源安全共享
互斥比較類似阻塞，關鍵在於互斥可以跨進程的線程同步，而且等待一個被鎖住的Mutex可以設定TIMEOUT，不會像Critical Section那樣無法得知臨界區域的情況，而一直死等。很多隻允許應用程序運行一次的實例就是用互斥方法來實現的。當一個互斥對象不再被一個線程所擁有，它就處於發信號狀態。此時首先調用waitForsingleobject()的線程就成為該互斥對象的擁有者，此互斥對象設為不發信號狀態。當線程調用releaseMutex()並傳遞一個互斥對象的句柄作為參數時，這種擁有關系就被解除，互斥對象重新進入發信號狀態。
3、信號量：它允許多個線程在同一時刻訪問同一資源，但是需要限制在同一時刻訪問此資源的最大線程數目, 信號量增加了資源計數的功能，預定數目的線程允許同時進入要同步的代碼。
4、事件：通過通知操作的方式來保持線程的同步，還可以方便實現對多個線程的優先順序比較的操作
進程通訊機制：
1． 內存映射文件(Memory-MappedFiles)
能使進程把文件內容當作進程地址區間一塊內存那樣來對待, 進程不必使用文件I/O操作，只需簡單的指針操作就可讀取和修改文件的內容。
2． 共享內存(Shared Memory)
實際就是文件映射的一種特殊情況。進程在創建文件映射對象時用0xFFFFFFFF來代替文件句柄(HANDLE)，就表示了對應的文件映射對象是從操作系統頁面文件訪問內存，其它進程打開該文件映射對象就可以訪問該內存塊。由於共享內存是用文件映射實現的，所以它也有較好的安全性，也只能運行於同一計算機上的進程之間。
3． 管道(Pipe)
是一種具有兩個端點的通信通道：有一端句柄的進程可以和有另一端句柄的進程通信。管道可以是單向－一端是只讀的，另一端點是只寫的；也可以是雙向的一管道的兩端點既可讀也可寫。
匿名管道(Anonymous Pipe)是在父進程和子進程之間，或同一父進程的兩個子進程之間傳輸數據的無名字的單向管道。命名管道(Named Pipe)是伺服器進程和一個或多個客戶進程之間通信的單向或雙向管道。
4． Sockets
5．WM_COPYDATA消息
2. 如何利用信號量機制實現多進程訪問臨界資源
進程互斥 定義:兩個或兩個以上的進程,不能同時進入關於同一組共享變數的臨界區域,否則可能發生與時間有關的錯誤,這種現象被稱作進程互斥.
在多道程序環境下，存在著臨界資源，它是指多進程存在時必須互斥訪問的資源。也就是某一時刻不允許多個進程同時訪問，只能單個進程的訪問。我們把這些程序的片段稱作臨界區或臨界段，它存在的目的是有效的防止競爭條件又能保證最大化使用共享數據。而這些並發進程必須有好的解決方案，才能防止出現以下情況：多個進程同時處於臨界區，臨界區外的進程阻塞其他的進程，有些進程在臨界區外無休止的等待。除此以外，這些方案還不能對CPU的速度和數目做出任何的假設。只有滿足了這些條件，才是一個好的解決方案。
訪問臨界資源的循環進程可以這樣來描述：
Repeat
entry section
Critical sections;
exit section
Remainder sectioni;
Until false
為實現進程互斥，可以利用軟體的方法，也可以在系統中設置專門的同步機制來協調多個進程，但是所有的同步機制應該遵循四大准則：
1.空閑讓進 當臨界資源處於空閑狀態，允許一個請求進入臨界區的進程立即進入臨界區，從 而有效的利用資源。
2.忙則等待 已經有進程進入臨界區時，意味著相應的臨界資源正在被訪問，所以其他准備進 入臨界區的進程必須等待，來保證多進程互斥。
3.有限等待 對要求訪問臨界資源的進程，應該保證該進程能在有效的時間內進入臨界區，防 止死等狀態。
4.讓權等待 當進程不能進入臨界區，應該立即釋放處理機，防止進程忙等待。
早期解決進程互斥問題有軟體的方法和硬體的方法，如：嚴格輪換法，Peterson的解決方案，TSL指令，Swap指令都可以實現進程的互斥，不過它們都有一定的缺陷，這里就不一一詳細說明，而後來Kijkstra提出的信號量機制則更好的解決了互斥問題。
3. 關於3個進程共享一個臨界資源
在操作系統理論中有一個非常重要的概念叫做P,V原語。在我們研究進程間的互斥的時候經常會引入這個概念，將P,V操作方法與加鎖的方法相比較，來解決進程間的互斥問題。實際上，他的應用范圍很廣，他不但可以解決進程管理當中的互斥問題，而且我們還可以利用此方法解決進程同步與進程通信的問題。
[一]P,V原語理論
闡述P,V原語的理論不得不提到的一個人便是赫赫有名的荷蘭科學家E.W.Dijkstra。如果你對這位科學家沒有什麼印象的話，提起解決圖論中最短路徑問題的Dijkstra演算法應當是我們再熟悉不過的了。P,V原語的概念以及P,V操作當中需要使用到的信號量的概念都是由他在1965年提出的。
信號量是最早出現的用來解決進程同步與互斥問題的機制，包括一個稱為信號量的變數及對它進行的兩個原語操作。信號量為一個整數，我們設這個信號量為：sem。很顯然，我們規定在sem大於等於零的時候代表可供並發進程使用的資源實體數，sem小於零的時候，表示正在等待使用臨界區的進程的個數。根據這個原則，在給信號量附初值的時候，我們顯然就要設初值大於零。
p操作和v操作是不可中斷的程序段，稱為原語。P,V原語中P是荷蘭語的Passeren，相當於英文的pass, V是荷蘭語的Verhoog,相當於英文中的incremnet。
P原語操作的動作是：
（1） sem減1；
（2） 若sem減1後仍大於或等於零，則進程繼續執行；
（3） 若sem減1後小於零，則該進程被阻塞後進入與該信號相對應的隊列中，然後轉進程調度。
V原語操作的動作是：
（1） sem加1；
（2） 若相加結果大於零，則進程繼續執行；
（3） 若相加結果小於或等於零，則從該信號的等待隊列中喚醒一等待進程，然後再返回原進程繼續執行或轉進程調度。
需要提醒大家一點就是P,V操作對於每一個進程來說，都只能進行一次。而且必須成對使用。且在P,V願語執行期間不允許有中斷的發生。
對於具體的實現，方法非常多，可以用硬體實現，也可以用軟體實現。我們採用如下的定義：
procere p(var s:samephore);
{
s.value=s.value-1;
if (s.value<0) asleep(s.queue);
}
procere v(var s:samephore);
{
s.value=s.value+1;
if (s.value<=0) wakeup(s.queue);
}
其中用到兩個標准過程：
asleep(s.queue);執行此操作的進程式控制制塊進入s.queue尾部，進程變成等待狀態
wakeup(s.queue);將s.queue頭進程喚醒插入就緒隊列
對於這個過程，s.value初值為1時，用來實現進程的互斥。
雖軟說信號量機制畢加鎖方法要好得多，但是也不是說它沒有任何的缺陷。由此我們也可以清晰地看到，這種信號量機制必須有公共內存，不能用於分布式操作系統，這是它最大的弱點。
[二]P,V原語的應用
正如我們在文中最開始的時候提到的，P,V原語不但可以解決進程管理當中的互斥問題，而且我們還可以利用此方法解決進程同步與進程通信的問題。
（1）用P V原語實現進程互斥
把臨界區置於P(sem) 和V(sem)之間。當一個進程想要進入臨界區時，它必須先執行P原語操作以將信號量sem減1，在進程完成對臨界區的操作後，它必須執行V原語操作以釋放它所佔用的臨界區。從而就實現了進程的互斥：
具體的過程我們可以簡單的描述如下：
PA:
P(sem)
<S>;
V(sem)
PB:
P(sem)
<S>;
V(sem)
(2) 用P V原語實現進程同步
進程同步問題的解決同樣可以採用這種操作來解決，我們假設兩個進程需要同步進行，一個進程是計算進程，另一個進程是列印進程，那麼這個時候兩個進程的定義可以表示為：
PC（表示計算進程）
A: local buf
repeat
buf=buf
until buf=空
計算
得到計算結果
buf=計算結果
goto A
PP:（表示列印進程）
B: local pri
repeat
pri=buf
until pri!=空
列印buf中的數據
清除buf中的數據
goto B
相應用P,V原語的實現過程為：
PA: deposit(data)
Begin local x
P(bufempty)
按FIFO方式選擇一個空緩沖區buf(x)
buf(x)=data
buf(x)置滿標記
V(buffull)
end
PB:remove(data)
Begin local x
P(buffull)
按FIFO方式選擇一個裝滿
數據的緩沖區buf(x)
data=buf(x)
buf(x)置空標記
V(bufempty)
end
（3）用P V原語實現進程通信
我們以郵箱通信為例說明問題：
郵箱通信滿足的條件是：
<1>;發送進程發送消息的時候，郵箱中至少要有一個空格能存放該消息。
<2>;接收進程接收消息時，郵箱中至少要有一個消息存在。
發送進程和接收進程我們可以進行如下的描述：
Deposit(m)為發送進程，接收進程是remove(m). Fromnum為發送進程的私用信號量，信箱空格數n。mesnum為接收進程的私用信號量，初值為0.
Deposit(m):
Begin local x
P(fromnum)
選擇空格x
將消息m放入空格x中
置格x的標志為滿
V(mesnum)
end
Remove(m)
Begin local x
P(mesnum)
選擇滿格x
把滿格x中的消息取出放m中
置格x標志為空
V(fromnum)
end
筆者僅從最基本的進程問題上論述P,V原語的應用。當然關於這一部分的應用是十分廣泛的。比如操作系統文化史上非常經典的哲學家就餐問題，生產-消費問題，讀者-寫者問題，理發師問題等等。大家不妨嘗試一下用信號量的方法進行實現。
4. 東秦的操作系統答案第二章
第二章
1. 什麼是前趨圖？為什麼要引入前趨圖？
答：前趨圖(Precedence Graph)是一個有向無循環圖，記為DAG(Directed Acyclic
Graph)，用於描述進程之間執行的前後關系。
2. 畫出下面四條語句的前趨圖:
S1=a：=x+y; S2=b：=z+1; S3=c：=a – b； S4=w：=c+1;
答：其前趨圖為：
3. 什麼程序並發執行會產生間斷性特徵？
答：程序在並發執行時，由於它們共享系統資源，為完成同一項任務需要相互合作，致使這
些並發執行的進程之間，形成了相互制約關系，從而使得進程在執行期間出現間斷性。
4．程序並發執行時為什麼會失去封閉性和可再現性？
答：程序並發執行時，多個程序共享系統中的各種資源，因而這些資源的狀態由多個程序改變，致使程序運行失去了封閉性，也會導致其失去可再現性。
5．在操作系統中為什麼要引入進程概念？它會產生什麼樣的影響?
答：為了使程序在多道程序環境下能並發執行，並對並發執行的程序加以控制和描述，在操作系統中引入了進程概念。
影響: 使程序的並發執行得以實行。
6．試從動態性，並發性和獨立性上比較進程和程序?
答：(1)動態性是進程最基本的特性，表現為由創建而產生，由調度而執行，因得不到資源
而暫停執行，由撤銷而消亡。進程有一定的生命期，而程序只是一組有序的指令集合，是靜
態實體。
(2)並發性是進程的重要特徵，同時也是OS 的重要特徵。引入進程的目的正是為了使
其程序能和其它進程的程序並發執行，而程序是不能並發執行的。
(3)獨立性是指進程實體是一個能獨立運行的基本單位，也是系統中獨立獲得資源和獨
立調度的基本單位。對於未建立任何進程的程序，不能作為獨立單位參加運行。
7．試說明PCB 的作用，為什麼說PCB 是進程存在的惟一標志？
答：PCB 是進程實體的一部分，是操作系統中最重要的記錄型數據結構。作用是使一個在
多道程序環境下不能獨立運行的程序，成為一個能獨立運行的基本單位，成為能與其它進程
並發執行的進程。OS是根據PCB對並發執行的進程進行控制和管理的。
8．試說明進程在三個基本狀態之間轉換的典型原因。
答： （1）就緒狀態→執行狀態：進程分配到CPU資源
（2）執行狀態→就緒狀態：時間片用完
（3）執行狀態→阻塞狀態：I/O請求
（4）阻塞狀態→就緒狀態：I/O完成
9．為什麼要引入掛起狀態？該狀態有哪些性質？
答：引入掛起狀態處於五種不同的需要: 終端用戶需要，父進程需要，操作系統需要，對換
北京石油化工學院信息工程學院計算機系5/48
《計算機操作系統》習題參考答案余有明與計07和計G09的同學們編著 5/48
需要和負荷調節需要。處於掛起狀態的進程不能接收處理機調度。
10．在進行進程切換時，所要保存的處理機狀態信息有哪些？
答：進行進程切換時，所要保存的處理機狀態信息有：
（1）進程當前暫存信息
（2）下一指令地址信息
（3）進程狀態信息
（4）過程和系統調用參數及調用地址信息。
11．試說明引起進程創建的主要事件。
答：引起進程創建的主要事件有：用戶登錄、作業調度、提供服務、應用請求。
12．試說明引起進程被撤銷的主要事件。
答：引起進程被撤銷的主要事件有：正常結束、異常結束（越界錯誤、保護錯、非法指令、
特權指令錯、運行超時、等待超時、算術運算錯、I/O 故障）、外界干預（操作員或操作系
統干預、父進程請求、父進程終止）。
13．在創建一個進程時所要完成的主要工作是什麼？
答：
（1）OS 發現請求創建新進程事件後，調用進程創建原語Creat()；
（2）申請空白PCB；
（3）為新進程分配資源；
（4）初始化進程式控制制塊；
（5）將新進程插入就緒隊列.
14．在撤銷一個進程時所要完成的主要工作是什麼？
答：
（1）根據被終止進程標識符，從PCB 集中檢索出進程PCB，讀出該進程狀態。
（2）若被終止進程處於執行狀態，立即終止該進程的執行，置調度標志真，指示該進程被
終止後重新調度。
（3）若該進程還有子進程，應將所有子孫進程終止，以防它們成為不可控進程。
（4）將被終止進程擁有的全部資源，歸還給父進程，或歸還給系統。
（5）將被終止進程PCB 從所在隊列或列表中移出，等待其它程序搜集信息。
15．試說明引起進程阻塞或被喚醒的主要事件是什麼？
答：a. 請求系統服務；b. 啟動某種操作；c. 新數據尚未到達；d. 無新工作可做.
16．進程在運行時存在哪兩種形式的制約？並舉例說明之。
答：
（1）間接相互制約關系。舉例：有兩進程A 和B，如果A 提出列印請求，系統已把唯一的
一台列印機分配給了進程B，則進程A 只能阻塞；一旦B 釋放列印機，A 才由阻塞改為就
緒。
（2）直接相互制約關系。舉例：有輸入進程A 通過單緩沖向進程B 提供數據。當緩沖空時，
計算進程因不能獲得所需數據而阻塞，當進程A 把數據輸入緩沖區後，便喚醒進程B；反
之，當緩沖區已滿時，進程A 因沒有緩沖區放數據而阻塞，進程B 將緩沖區數據取走後便
喚醒A。
17．為什麼進程在進入臨界區之前應先執行「進入區」代碼？而在退出前又要執行「退出
區」代碼？
答：為了實現多個進程對臨界資源的互斥訪問，必須在臨界區前面增加一段用於檢查欲訪問
的臨界資源是否正被訪問的代碼，如果未被訪問，該進程便可進入臨界區對資源進行訪問，
並設置正被訪問標志，如果正被訪問，則本進程不能進入臨界區，實現這一功能的代碼為"
北京石油化工學院信息工程學院計算機系6/48
《計算機操作系統》習題參考答案余有明與計07和計G09的同學們編著 6/48
進入區"代碼；
在退出臨界區後，必須執行"退出區"代碼，用於恢復未被訪問標志，使其它進程能再訪問此
臨界資源。
18. 同步機構應遵循哪些基本准則？為什麼？
答：同步機構應遵循的基本准則是：空閑讓進、忙則等待、有限等待、讓權等待
原因：為實現進程互斥進入自己的臨界區。
19. 試從物理概念上說明記錄型信號量wait 和signal。
答：wait(S)：當S.value>0 時，表示目前系統中這類資源還有可用的。執行一次wait 操
作，意味著進程請求一個單位的該類資源，使系統中可供分配的該類資源減少一個，因此描
述為S.value:=S.value-1；當S.value<0時，表示該類資源已分配完畢，進程應調用block
原語自我阻塞，放棄處理機，並插入到信號量鏈表S.L中。
signal(S)：執行一次signal操作，意味著釋放一個單位的可用資源，使系統中可供分配
的該類資源數增加一個，故執行S.value:=S.value+1 操作。若加1 後S.value≤0，則表
示在該信號量鏈表中，仍有等待該資源的進程被阻塞，因此應調用wakeup 原語，將S.L
鏈表中的第一個等待進程喚醒。
20．你認為整型信號量機制是否完全遵循了同步機構的四條准則？
答：整型信號量機制不完全遵循同步機制的四條准則，它不滿足「讓權等待」准則。
21．如何利用信號量機制來實現多個進程對臨界資源的互斥訪問？並舉例說明之。
答：為使多個進程互斥訪問某臨界資源，只需為該資源設置一互斥信號量mutex，並設其
初值為1，然後將各進程訪問該資源的臨界區CS置於wait(mutex)和signal(mutex)操作
之間即可。這樣，每個欲訪問該臨界資源的進程在進入臨界區之前，都要先對mutex 執行
wait 操作，若該資源此刻未被訪問，本次wait 操作必然成功，進程便可進入自己的臨界區，
這時若再有其他進程也欲進入自己的臨界區，此時由於對mutex 執行wait操作定會失敗，
因而該進程阻塞，從而保證了該臨界資源能被互斥訪問。當訪問臨界資源的進程退出臨界區
後，應對mutex執行signal 操作，釋放該臨界資源。利用信號量實現進程互斥的進程描述
如下：
Var mutex: semaphore:=1；
begin
parbegin
process 1: begin
repeat
wait(mutex)；
critical section
signal(mutex)；
remainder seetion
until false；
end
process 2: begin
repeat
wait(mutex)；
critical section
signal(mutex)；
remainder section
until false；
end
parend
22．試寫出相應的程序來描述圖2-17所示的前驅圖。
答：（a）Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0, 0;
begin
parbegin
begin S1; signal(a); signal(b); end;
begin wait(a); S2; signal(c); signal(d); end;
begin wait(b); S3; signal(e); end;
begin wait(c); S4; signal(f); end;
begin wait(d); S5; signal(g); end;
begin wait(e); S6; signal(h); end;
begin wait(f); wait(g); wait(h); S7; end;
parend
end
（b）Var a, b, c, d, e, f, g, h,i,j; semaphore:= 0, 0, 0, 0, 0, 0, 0,0,0, 0;
begin
parbegin
begin S1; signal(a); signal(b); end;
begin wait(a); S2; signal(c); signal(d); end;
begin wait(b); S3; signal(e); signal(f); end;
begin wait(c); S4; signal(g); end;
begin wait(d); S5; signal(h); end;
begin wait(e); S6; signal(i); end;
begin wait(f); S7; signal(j); end;
begin wait(g);wait(h); wait(i); wait(j); S8; end;
parend
end
23．在生產者消費者問題中，如果缺少了signal(full)或signal(empty),對執行結果有何影響？
答：
如果缺少signal(full)，那麼表明從第一個生產者進程開始就沒有改變信號量full 值，
即使緩沖池產品已滿，但full 值還是0，這樣消費者進程執行wait(full)時認為緩沖池是空
而取不到產品，消費者進程一直處於等待狀態。
如果缺少signal(empty)，在生產者進程向n個緩沖區投滿產品後消費者進程才開始從
中取產品，這時empty=0，full=n，那麼每當消費者進程取走一個產品empty 值並不改變，
直到緩沖池取空了，empty 值也是0，即使目前緩沖池有n 個空緩沖區，生產者進程要想
再往緩沖池中投放產品也會因為申請不到空緩沖區被阻塞。
24．在生產消費者問題中，如果將兩個wait 操作即wait(full)和wait(mutex)互換位置，
或者將signal(mutex)與signal（full）互換位置，結果如何？
答：將wait(full)和wait(mutex)互換位置後，可能引起死鎖。考慮系統中緩沖區全滿時，
若一生產者進程先執行了wait(mutex)操作並獲得成功，則當再執行wait(empty)操作時，
它將因失敗而進入阻塞狀態，它期待消費者進程執行signal(empty)來喚醒自己，在此之前，
它不可能執行signal(mutex)操作，從而使試圖通過執行wait(mutex)操作而進入自己的臨
界區的其他生產者和所有消費者進程全部進入阻塞狀態，這樣容易引起系統死鎖。
若signal(mutex)和signal(full)互換位置後只是影響進程對臨界資源的釋放次序，而
不會引起系統死鎖，因此可以互換位置。
25．我們在為某一臨界資源設置一把鎖W，當W=1時表示關鎖，當W=0時表示鎖已打開。
試寫出開鎖和關鎖的原語，並利用他們實現互斥。
答：整型信號量：lock(W): while W=1 do no-op
W:=1;
unlock(W): W:=0;
記錄型信號量：lock(W): W:=W+1;
if(W>1) then block(W, L)
unlock(W): W:=W-1;
if(W>0) then wakeup(W, L)
例子：
Var W:semaphore:=0；
begin
repeat
lock(W);
critical section
unlock(W);
remainder section
until false;
end
26．試修改下面生產者－消費者問題解法中的錯誤:
答： procer:
begin
repeat
…
procer an item in nextp;
wait(mutex);
wait(full); /* 應為wait(empty),而且還應該在wait(mutex)的前面 */
buffer(in):=nextp;
/* 緩沖池數組游標應前移: in:=(in+1) mod n; */
signal(mutex);
/* signal(full); */
until false;
end
consumer:
begin
repeat
wait(mutex);
wait(empty); /* 應為wait(full),而且還應該在wait(mutex)的前面 */
nextc:=buffer(out);
out:=out+1; /* 考慮循環，應改為: out:=(out+1) mod n; */
signal(mutex);/* signal(empty); */
consumer item in nextc;
until false;
end
27．試利用記錄型信號量寫出一個不會出現死鎖的哲學家進餐問題的演算法.
答：Var chopstick:array[0,…,4] of semaphore;
所有信號量均被初始化為1，第i 位哲學家的活動可描述為：
Repeat
Wait(chopstick[i]);
Wait(. chopstick[(i+1) mod 5]);
…
Ea.t ;
…
Signal(chopstick[i]);
Signal(chopstick[(i+1) mod 5])
Ea.t ;
…
Think;
Until false;
28．在測量控制系統中的數據採集任務，把所採集的數據送一單緩沖區；計算任務從該單
緩沖中取出數據進行計算.試寫出利用信號量機制實現兩者共享單緩沖的同步演算法。
答：
a. Var mutex, empty, full: semaphore:=1, 1, 0;
gather:
begin
repeat
……
gather data in nextp;
wait(empty);
wait(mutex);
buffer:=nextp;
signal(mutex);
signal(full);
until false;
end
compute:
begin
repeat
……
wait(full);
wait(mutex);
nextc:=buffer;
signal(mutex);
signal(empty);
compute data in nextc;
until false;
end
b. Var empty, full: semaphore:=1, 0;
gather:
begin
repeat
……
gather data in nextp;
wait(empty);
buffer:=nextp;
signal(full);
until false;
end
compute:
begin
repeat
……
wait(full);
nextc:=buffer;
signal(empty);
compute data in nextc;
until false;
end
29．畫圖說明管程由哪幾部分組成，為什麼要引入條件變數？
答：管程由四部分組成：①管程的名稱；②局部於管程內部的共享數據結構說明；③對該數
據結構進行操作的一組過程；④對局部於管程內部的共享數據設置初始值的語句；
當一個進程調用了管程，在管程中時被阻塞或掛起，直到阻塞或掛起的原因解除，而在此期
間，如果該進程不釋放管程，則其它進程無法進入管程，被迫長時間地等待。為了解決這個
問題，引入了條件變數condition。
30．如何利用管程來解決生產者與消費者問題？
答：首先建立一個管程，命名為ProclucerConsumer，包括兩個過程：
（1）Put（item）過程。生產者利用該過程將自己生產的產品放到緩沖池，用整型變
量count 表示在緩沖池中已有的產品數目，當count≥n 時，表示緩沖池已滿，生產者須
等待。
（2）get（item）過程。消費者利用該過程從緩沖池中取出一個產品，當count≤0
時，表示緩沖池中已無可取的產品，消費者應等待。
PC 管程可描述如下：
type procer-consumer =monitor
Var in,out,count:integer;
buffer:array[0,…,n-1]of item;
notfull，notempty:condition;
procere entry dot(item)
begin
if count>=n then not full.wait;
buffer(in):=nextp;
in:=(in+1)mod n;
count:=count+1;
if notempty.queue then notempty.signal;
end
procere entry get(item)
begin
if count<=0 then not full.wait;
nextc:=buffer(out);
out:=(out+1)mod n;
count:=count-1;
if notfull.quene then notfull.signal;
end
begin in:=out:=0;
count:=0
end
在利用管程解決生產者一消費者問題時，其中的生產者和消費者可描述為：
procer: begin
pepeat
proce an inem in nestp
PC.put(item);
until false;
end
consumer: begin
repeat
PC.get(item);
consume the item in enxtc;
until false;
end
31．什麼是AND信號量？試利用AND信號量寫出生產者一消費者問題的解法。
答：為解決並行帶來的死鎖問題，在wait 操作中引入AND 條件，其基本思想是將進
程在整個運行過程中所需要的所有臨界資源，一次性地全部分配給進程，用完後一次性釋放。
解決生產者－消費者問題可描述如下:
var mutex,empty,full: semaphore:=1,n,0;
buffer: array[0,...,n-1] of item;
in,out: integer:=0,0;
begin
parbegin
procer: begin
repeat
…
proce an item in nextp;
…
wait(empty);
wait(s1,s2,s3,...,sn); //s1,s2,...,sn為執行生產者進程除empty 外其餘的條件
wait(mutex);
buffer(in):=nextp;
in:=(in+1) mod n;
signal(mutex);
signal(full);
signal(s1,s2,s3,...,sn);
until false;
end
consumer: begin
repeat
wait(full);
wait(k1,k2,k3,...,kn); //k1,k2,...,kn 為執行消費者進程除full 外其餘的條件
wait(mutex);
nextc:=buffer(out);
out:=(out+1) mod n;
signal(mutex);
signal(empty);
signal(k1,k2,k3,...,kn);
consume the item in nextc;
until false;
end
parend
end
32．什麼是信號量集？試利用信號量集寫出讀者一寫者問題的解法。
答：對AND信號量加以擴充，形成的信號量集合的讀寫機制。
解法：Var RN integer;
L,mx: semaphore:=RN,1;
begin
parbegin
reader:begin
repeat
Swait(L,1,1);
Swait(mx,1,1);
…
perform read operation;
…
Ssignal(L,1);
until false
end
writer:begin
repeat
Swait(mx,1,1;L,RN,0);
perform write operation;
Ssignal(mx,1);
until false
end
parend
end
33．試比較進程間的低級與高級通信工具。
答：用戶用低級通信工具實現進程通信很不方便，效率低，通信對用戶不透明，所有操作都
必須由程序員來實現，而高級通信工具彌補了這些缺陷，用戶直接利用操作系統提供的一組
通信命令，高效地傳送大量的數據。
34．當前有哪幾種高級通信機制？
答：共享存儲器系統、消息傳遞系統以及管道通信系統。
35．消息隊列通信機制有哪幾方面的功能？
答：（1）構成消息（2）發送消息（3）接收梢息（4）互斥與同步。
36．為什麼要在OS 中引入線程？
答：在操作系統中引入線程，則是為了減少程序在並發執行時所付出的時空開銷，使OS具
有更好的並發性，提高CPU的利用率。進程是分配資源的基本單位,而線程則是系統調度的
基本單位。
37．試說明線程具有哪些屬性？
答：（1)輕型實體（2）獨立調度和分派的基本單位（3）可並發執行（4）共享進程資源。
38. 試從調度性，並發性，擁有資源及系統開銷方面對進程和線程進行比較。
答：
（1）調度性。線程在OS 中作為調度和分派的基本單位，進程只作為資源擁有的基本單位。
（2）並發性。進程可以並發執行，一個進程的多個線程也可並發執行。
（3）擁有資源。進程始終是擁有資源的基本單位，線程只擁有運行時必不可少的資源，本
身基本不擁有系統資源，但可以訪問隸屬進程的資源。
（4）系統開銷。操作系統在創建、撤消和切換進程時付出的開銷顯著大於線程。
39. 為了在多線程OS 中實現進程之間的同步與通信，通常提供了哪幾種同步機制？
答：同步功能可以控製程序流並訪問共享數據，從而並發執行多個線程。共有四種同步模型：
互斥鎖、讀寫鎖、條件變數和信號。
40．用於實現線程同步的私用信號量和公用信號量之間有何差別？
答：
（1）私用信號量。當某線程需利用信號量實現同一進程中各線程之間的同步時，可調用創
建信號量的命令來創建一個私用信號量，其數據結構存放在應用程序的地址空間中。
（2）公用信號量。公用信號量是為實現不同進程間或不同進程中各線程之間的同步而設置
的。其數據結構是存放在受保護的系統存儲區中，由OS為它分配空間並進行管理。
41．何謂用戶級線程和內核支持線程？
答：
（1）用戶級線程：僅存在於用戶空間中的線程，無須內核支持。這種線程的創建、撤銷、
線程間的同步與通信等功能，都無需利用系統調用實現。用戶級線程的切換通常發生在一個
應用進程的諸多線程之間，同樣無需內核支持。
（2）內核支持線程：在內核支持下運行的線程。無論是用戶進程中的線程，還是系統線程
中的線 程，其創建、撤銷和切換等都是依靠內核，在內核空間中實現的。在內核空間里還
為每個內核支持線程設置了線程式控制制塊，內核根據該控制塊感知某線程的存在並實施控制。
42．試說明用戶級線程的實現方法。
答：用戶級線程是在用戶空間中的實現的，運行在「運行時系統」與「內核控制線程」的中
間系統上。運行時系統用於管理和控制線程的函數的集合。內核控制線程或輕型進程LWP
可通過系統調用獲得內核提供服務，利用LWP進程作為中間系統。
43．試說明內核支持線程的實現方法。
答：系統在創建新進程時，分配一個任務數據區PTDA，其中包括若干個線程式控制制塊TCB
空間。創建一個線程分配一個TCB，有關信息寫入TCB，為之分配必要的資源。當PTDA
中的TCB 用完，而進程又有新線程時，只要所創建的線程數目未超過系統允許值，系統可
在為之分配新的TCB；在撤銷一個線程時，也應回收線程的所有資源和TCB。