第二部分進(jìn)程管理

1、第二章 進(jìn)程管理 2.1 進(jìn)程的基本概念 2.2 進(jìn)程控制 2.3 進(jìn)程同步 2.4 經(jīng)典進(jìn)程的同步問題 2.5 第二部分進(jìn)程管理上節(jié)回顧四種信號量的比較生產(chǎn)者-消費(fèi)者問題兩私一公的典型，公用信號量與私用信號量公用信號量用于資源（變量）互斥，一般在同個過程中私用信號量用于進(jìn)程控制，多交叉在不同過程中先私后公哲學(xué)家就餐問題：AND信號量第二部分進(jìn)程管理 1. 利用記錄型信號量解決生產(chǎn)者消費(fèi)者問題具有n個緩沖區(qū)公用緩沖池中互斥信號量mutex實(shí)現(xiàn)諸進(jìn)程對緩沖池的互斥使用信號量empty表示緩沖池中空緩沖區(qū)數(shù)量。信號量full表示緩沖池中滿緩沖區(qū)的數(shù)量。mutex為公用信號量，full與empty與

2、私用信號量假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池中取走一個消息。第二部分進(jìn)程管理Var mutex, empty, full:semaphore=1,n,0; buffer:array0, , n-1 of item; in, out: integer=0, 0; begin parbegin proceducer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in)=nextp; in=(in+1) mod n; signal(

3、mutex); signal(full); until false; end 第二部分進(jìn)程管理consumer:begin repeat wait(full); wait(mutex); nextc =buffer(out); out =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end 第二部分進(jìn)程管理2.4.3 讀者-寫者問題 1. 利用記錄型信號量解決讀者-寫者問題互斥信號量Wmutex：實(shí)現(xiàn)Reader與Writer進(jìn)程的互斥整型變量Re

4、adcount表示正在讀的進(jìn)程數(shù)目。僅當(dāng)Readcount=0, 表示尚無Reader進(jìn)程在讀時，Reader進(jìn)程才需要執(zhí)行wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。僅當(dāng)Reader進(jìn)程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進(jìn)程寫。因?yàn)镽eadcount是一個可被多個Reader進(jìn)程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個互斥信號量rmutex。 第二部分進(jìn)程管理讀者-寫者問題可描述如下：Var rmutex, wmutex:semapho

5、re =1,1; Readcount:integer =0; begin parbegin READER:begin repeat wait(rmutex); if readcount=0 then wait(wmutex); Readcount =Readcount+1; signal(rmutex); perform read operation; 第二部分進(jìn)程管理 wait(rmutex); readcount =readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end WRITER

6、:begin repeat wait(wmutex); perform write operation; signal(wmutex); until false; end parend end 第二部分進(jìn)程管理2. 利用信號量集機(jī)制解決讀者-寫者問題 增加限制，最多允許RN個讀者讀信號量L，初值RN，用于控制讀者數(shù)目在第RN+1個讀者要進(jìn)入讀時，會引起阻塞使用Swait(S, 1, 0)的方法實(shí)現(xiàn)開關(guān)作用第二部分進(jìn)程管理Var RN integer; L, mx:semaphore =RN,1; begin parbegin READER:begin repeat Swait(L,1,1);

7、Swait(mx,1,0); perform read operation; Ssignal(L,1); until false; end第二部分進(jìn)程管理WRITER:begin repeat Swait(mx,1,1; L,RN,0); perform write operation; Ssignal(mx,1); until false; end parend end 第二部分進(jìn)程管理2.5 管 程 機(jī) 制 第二部分進(jìn)程管理管程的基本概念 管程由三部分組成： 局部于管程的共享變量說明； 對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程； 對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。此外，還須為管程賦予一個名字。 第

8、二部分進(jìn)程管理2.6 進(jìn) 程 通 信 信號量適合同步控制， 不適宜作為通信工具。因此需要高級進(jìn)程通信方式。第二部分進(jìn)程管理2.6.1 高級進(jìn)程通信的類型 高級通信的定義：P54 第二部分進(jìn)程管理2.6.1 進(jìn)程通信的類型 1. 共享存儲器系統(tǒng)(Shared-Memory System) 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。 例如生產(chǎn)者-消費(fèi)者問題中的緩沖池。該方式增加程序員負(fù)擔(dān)，OS只須提供共享空間，低效，只能傳遞少量數(shù)據(jù)。(2) 基于共享存儲區(qū)的通信方式。 例如Windows的DDE第二部分進(jìn)程管理DDE技術(shù)通信原理動態(tài)數(shù)據(jù)交換(Dynamic Data Exchange,DDE)是一種進(jìn)程間通信形

9、式。兩個同時運(yùn)行的程序間通過DDE方式交換數(shù)據(jù)時是客戶/服務(wù)器關(guān)系，一旦客戶和服務(wù)器建立起來連接關(guān)系，則當(dāng)服務(wù)器中的數(shù)據(jù)發(fā)生變化后就會馬上通知客戶。通過DDE方式建立的數(shù)據(jù)連接通道是雙向的，即客戶不但能夠讀取服務(wù)器中的數(shù)據(jù)，而且可以對其進(jìn)行修改。第二部分進(jìn)程管理第二部分進(jìn)程管理 2. 消息傳遞系統(tǒng)(Message passing system) 不論是單機(jī)系統(tǒng)、多機(jī)系統(tǒng)，還是計算機(jī)網(wǎng)絡(luò)，消息傳遞機(jī)制都是用得最廣泛的一種進(jìn)程間通信的機(jī)制。1、在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換，是以格式化的消息(message)為單位（在計算機(jī)網(wǎng)絡(luò)中，又把message稱為報文）2、程序員直接利用系統(tǒng)提供的一組通

10、信命令(原語)進(jìn)行通信。 操作系統(tǒng)隱藏了通信的實(shí)現(xiàn)細(xì)節(jié)，大大減化了通信程序編制的復(fù)雜性，而獲得廣泛的應(yīng)用。消息傳遞系統(tǒng)的通信方式屬于高級通信方式。又因其實(shí)現(xiàn)方式的不同而進(jìn)一步分成直接通信方式和間接通信方式兩種。 第二部分進(jìn)程管理 3. 管道(Pipe)通信 所謂“管道”，是指用于連接一個讀進(jìn)程和一個寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫進(jìn)程)， 以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)，則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由

11、于它能有效地傳送大量數(shù)據(jù)，因而又被引入到許多其它操作系統(tǒng)中。 第二部分進(jìn)程管理 為了協(xié)調(diào)雙方的通信，管道機(jī)制必須提供以下三方面的協(xié)調(diào)能力： 互斥，即當(dāng)一個進(jìn)程正在對pipe執(zhí)行讀/寫操作時，其它(另一)進(jìn)程必須等待。 同步，指當(dāng)寫(輸入)進(jìn)程把一定數(shù)量(如4 KB)的數(shù)據(jù)寫入pipe，便去睡眠等待， 直到讀(輸出)進(jìn)程取走數(shù)據(jù)后，再把他喚醒。當(dāng)讀進(jìn)程讀一空pipe時，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入管道后，才將之喚醒。 確定對方是否存在，只有確定了對方已存在時，才能進(jìn)行通信。 第二部分進(jìn)程管理2.6.2 消息傳遞通信的實(shí)現(xiàn)方法 1. 直接通信方式 這是指發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接

12、把消息發(fā)送給目標(biāo)進(jìn)程。此時，要求發(fā)送進(jìn)程和接收進(jìn)程都以顯式方式提供對方的標(biāo)識符。第二部分進(jìn)程管理通常，系統(tǒng)提供下述兩條通信命令(原語)： Send(Receiver, message); 發(fā)送一個消息給接收進(jìn)程； Receive(Sender, message); 接收Sender發(fā)來的消息；例如原語Send(P2, m1)：表示將消息m1發(fā)送給接收進(jìn)程P2; 原語Receive(P1，m1)：表示接收由P1發(fā)來的消息m1。 第二部分進(jìn)程管理 在某些情況下，接收進(jìn)程可與多個發(fā)送進(jìn)程通信，因此，它不可能事先指定發(fā)送進(jìn)程。例如，用于提供打印服務(wù)的進(jìn)程，它可以接收來自任何一個進(jìn)程的“打印請求”消息。

13、對于這樣的應(yīng)用，在接收進(jìn)程接收消息的原語中的源進(jìn)程參數(shù)，是完成通信后的返回值，接收原語可表示為： Receive (id, message); 第二部分進(jìn)程管理利用直接通信原語解決生產(chǎn)者-消費(fèi)者問題。當(dāng)生產(chǎn)者生產(chǎn)出一個產(chǎn)品(消息)后，便用Send原語將消息發(fā)送給消費(fèi)者進(jìn)程；而消費(fèi)者進(jìn)程則利用Receive原語來得到一個消息。如果消息尚未生產(chǎn)出來，消費(fèi)者必須等待，直至生產(chǎn)者進(jìn)程將消息發(fā)送過來。生產(chǎn)者-消費(fèi)者的通信過程可分別描述如下： repeat produce an item in nextp; send(consumer, nextp); until false; repeat receiv

14、e(producer, nextc); consume the item in nextc; until false; 第二部分進(jìn)程管理2. 間接通信方式 第二部分進(jìn)程管理 間接通信的原語 (1) 信箱的創(chuàng)建和撤消。進(jìn)程可利用信箱創(chuàng)建原語來建立一個新信箱：Create (mailbox)創(chuàng)建者進(jìn)程應(yīng)給出信箱名字、信箱屬性(公用、私用或共享)；對于共享信箱， 還應(yīng)給出共享者的名字。當(dāng)進(jìn)程不再需要讀信箱時，可用信箱撤消原語將之撤消。Delete (mailbox) 第二部分進(jìn)程管理2. 間接通信方式 (2) 消息的發(fā)送和接收。當(dāng)進(jìn)程之間要利用信箱進(jìn)行通信時，必須使用共享信箱，并利用系統(tǒng)提供的下述通

15、信原語進(jìn)行通信。 Send(mailbox, message); 將一個消息發(fā)送到指定信箱； Receive(mailbox, message); 從指定信箱中接收一個消息； 第二部分進(jìn)程管理 信箱可由操作系統(tǒng)創(chuàng)建，也可由用戶進(jìn)程創(chuàng)建，創(chuàng)建者是信箱的擁有者。據(jù)此，可把信箱分為以下三類。 1) 私用信箱 用戶進(jìn)程可為自己建立一個新信箱，并作為該進(jìn)程的一部分。信箱的擁有者有權(quán)從信箱中讀取消息，其他用戶則只能將自己構(gòu)成的消息發(fā)送到該信箱中。這種私用信箱可采用單向通信鏈路的信箱來實(shí)現(xiàn)。 當(dāng)擁有該信箱的進(jìn)程結(jié)束時，信箱也隨之消失。 第二部分進(jìn)程管理 2) 公用信箱 它由操作系統(tǒng)創(chuàng)建，并提供給系統(tǒng)中的所有

16、核準(zhǔn)進(jìn)程使用。核準(zhǔn)進(jìn)程既可把消息發(fā)送到該信箱中，也可從信箱中讀取發(fā)送給自己的消息。顯然，公用信箱應(yīng)采用雙向通信鏈路的信箱來實(shí)現(xiàn)。通常，公用信箱在系統(tǒng)運(yùn)行期間始終存在。 3) 共享信箱 它由某進(jìn)程創(chuàng)建，在創(chuàng)建時或創(chuàng)建后，指明它是可共享的，同時須指出共享進(jìn)程(用戶)的名字。信箱的擁有者和共享者，都有權(quán)從信箱中取走發(fā)送給自己的消息。 第二部分進(jìn)程管理 在利用信箱通信時，在發(fā)送進(jìn)程和接收進(jìn)程之間，存在以下四種關(guān)系： (1) 一對一關(guān)系。這時可為發(fā)送進(jìn)程和接收進(jìn)程建立一條兩者專用的通信鏈路，使兩者之間的交互不受其他進(jìn)程的干擾。 (2) 多對一關(guān)系。允許提供服務(wù)的進(jìn)程與多個用戶進(jìn)程之間進(jìn)行交互，也稱為客戶

17、/服務(wù)器交互(client/server interaction)。 (3) 一對多關(guān)系。允許一個發(fā)送進(jìn)程與多個接收進(jìn)程進(jìn)行交互，使發(fā)送進(jìn)程可用廣播方式，向接收者(多個)發(fā)送消息。 (4) 多對多關(guān)系。允許建立一個公用信箱，讓多個進(jìn)程都能向信箱中投遞消息；也可從信箱中取走屬于自己的消息。 第二部分進(jìn)程管理2.6.3 消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題 1. 通信鏈路(communication link) 為使在發(fā)送進(jìn)程和接收進(jìn)程之間能進(jìn)行通信，必須在兩者之間建立一條通信鏈路。有兩種方式建立通信鏈路。第一種方式是：由發(fā)送進(jìn)程在通信之前，用顯式的“建立連接”命令(原語)請求系統(tǒng)為之建立一條通信鏈路；在

18、鏈路使用完后，也用顯式方式拆除鏈路。 這種方式主要用于計算機(jī)網(wǎng)絡(luò)中。第二種方式是發(fā)送進(jìn)程無須明確提出建立鏈路的請求，只須利用系統(tǒng)提供的發(fā)送命令(原語)，系統(tǒng)會自動地為之建立一條鏈路。這種方式主要用于單機(jī)系統(tǒng)中。 第二部分進(jìn)程管理根據(jù)通信鏈路的連接方法，又可把通信鏈路分為兩類： 點(diǎn)點(diǎn)連接通信鏈路，這時的一條鏈路只連接兩個結(jié)點(diǎn)(進(jìn)程)； 多點(diǎn)連接鏈路，指用一條鏈路連接多個(n2)結(jié)點(diǎn)(進(jìn)程)。根據(jù)通信方式的不同，則又可把鏈路分成兩種： 單向通信鏈路，只允許發(fā)送進(jìn)程向接收進(jìn)程發(fā)送消息； 雙向鏈路，既允許由進(jìn)程A向進(jìn)程B發(fā)送消息，也允許進(jìn)程B同時向進(jìn)程A發(fā)送消息。 第二部分進(jìn)程管理2. 消息的格式 在

19、某些OS中，消息是采用比較短的定長消息格式，這減少了對消息的處理和存儲開銷。這種方式可用于辦公自動化系統(tǒng)中，為用戶提供快速的便箋式通信；但這對要發(fā)送較長消息的用戶是不方便的。 在有的OS中，采用另一種變長的消息格式，即進(jìn)程所發(fā)送消息的長度是可變的。系統(tǒng)在處理和存儲變長消息時，須付出更多的開銷，但方便了用戶。 這兩種消息格式各有其優(yōu)缺點(diǎn)，故在很多系統(tǒng)(包括計算機(jī)網(wǎng)絡(luò))中，是同時都用的。 第二部分進(jìn)程管理3. 進(jìn)程同步方式 發(fā)送進(jìn)程阻塞、 接收進(jìn)程阻塞。(2) 發(fā)送進(jìn)程不阻塞、 接收進(jìn)程阻塞。 (3) 發(fā)送進(jìn)程和接收進(jìn)程均不阻塞。 第二部分進(jìn)程管理2.6.4 消息緩沖隊(duì)列通信機(jī)制 1. 消息緩沖隊(duì)列通信機(jī)制中的數(shù)據(jù)結(jié)構(gòu) (1) 消息緩沖區(qū)。在消息緩沖隊(duì)列通信方式中，主要利用的數(shù)據(jù)結(jié)構(gòu)是消息緩沖區(qū)。它可描述如下：type message buffer=record sender; 發(fā)送者進(jìn)程標(biāo)識符 size; 消息長度 text; 消息正文 next; 指向下一個消息緩沖區(qū)的指針 end 第二部分進(jìn)程管理 (2) PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)。在利用消息緩沖隊(duì)列通信機(jī)制時，在設(shè)置消息緩沖隊(duì)列的同時，還應(yīng)增加用于對消息隊(duì)列