操作系統(tǒng)課件：04第四章 互斥同步與通訊2

1、4.3.6 會(huì)合(Rendezvous)背景80年代, Ada, Initiated by DOD;Ada 95, (Object-oriented)會(huì)合：兩個(gè)并發(fā)執(zhí)行流匯集到一處并發(fā)執(zhí)行流調(diào)用接受均發(fā)生，握手，同步。P1:會(huì)合引入背景分布系統(tǒng) 共享變量（被動(dòng)）Semaphore s;P(S)CR2V(S)P2:共享變量與訪問進(jìn)程在同一存儲(chǔ)區(qū)，不適合分布環(huán)境。PV操作問題:P(S)CR1V(S)P1:會(huì)合引入背景分布系統(tǒng) 共享變量（被動(dòng)）Semaphore s;P(S)CR2V(S)P2:共享變量與訪問進(jìn)程在同一存儲(chǔ)區(qū)，不適合分布環(huán)境。PV操作問題:P(S)CR1V(S)站點(diǎn)1站點(diǎn)2會(huì)合引入背

2、景分布系統(tǒng)共享變量CR1CR2管程（被動(dòng)）P1：.P2：.管程與調(diào)用進(jìn)程在同一存儲(chǔ)區(qū)，不適合分布環(huán)境。管程問題:會(huì)合引入背景分布系統(tǒng)共享變量CR1CR2管程（被動(dòng)）P1：.P2：.管程與調(diào)用進(jìn)程在同一存儲(chǔ)區(qū)，不適合分布環(huán)境。管程問題:站點(diǎn)1站點(diǎn)2會(huì)合圖示任務(wù)task任務(wù)task任務(wù)task調(diào)用語句調(diào)用語句接受語句選擇語句被調(diào)用者代調(diào)用者執(zhí)行調(diào)用代碼會(huì)合圖示被調(diào)用任務(wù)入口1：accept入口2：acceptselect.PCBPCB.PCBPCB.調(diào)用語句調(diào)用語句調(diào)用任務(wù)入口FIFO隊(duì)列Ada同步語句1. 調(diào)用語句 . 2. 接受語句 accept doendAccept語句有調(diào)用者等待選取第一

3、個(gè)會(huì)合開始調(diào)用者等待有in參數(shù)取in參數(shù)有語句序列執(zhí)行之有out參數(shù)送out參數(shù)會(huì)合結(jié)束調(diào)用者繼續(xù)會(huì)合期TFTFTFTF例子-單一資源管理task single_resource is entry acquire; entry return;end single_resource;task body single_resource is begin loop accept acquire; accept return; end loop end single_resource;single_resource.acquire; 使用single_resource.return;Ada同步語句（c

4、ont.）3. 選擇語句 select when = or when = else end select4.3.6.1 會(huì)合的描述(Cont.)F任取一開放且被調(diào)用的select 語句流程FT取 in 參數(shù)T執(zhí)行語句序列T送 out 參數(shù)T計(jì)算所有布爾表達(dá)式為真者對應(yīng)標(biāo)記開放有開放的有else部分有被調(diào)用的開放的有else部分等 待F會(huì)合開始，調(diào)用者等待有 in 參數(shù)有語句序列F有 out 參數(shù)F執(zhí)行else部分T建立異常條件F執(zhí)行else部分TF會(huì)合結(jié)束，調(diào)用者繼續(xù)T選擇語句后有執(zhí)行TF4.3.6.2 會(huì)合例子-客棧問題.explorersbakeryhunter活動(dòng)：(1)接受獵物(2)接

5、受面包(3)做三明治(4)給探險(xiǎn)家限制：一份獵物一份面包一份三明治一位客人master客棧客棧問題explorer：loop 探 險(xiǎn) 進(jìn)客棧 取三明治 出客棧 吃三明治end loophunter：loop 狩 獵 進(jìn)客棧 送獵物 出客棧end loopbakery：loop 做面包 進(jìn)客棧 送面包 出客棧end loop入口入口入口客棧問題procedure Adalodge is task type explorer; task hunter; task bakery; task master is entry deliverbread; /面包師送面包 entry delivermeat

6、; /狩獵者送獵物 entry lodge; /探險(xiǎn)家取三明治 end master;客棧問題task body explorer is victuals:food; begin loop explore; master.lodge(victuals); /入客棧取三明治 eat(victuals) end loop end explorer;客棧問題task body hunter is walrus:food; begin loop hunt(walrus); master.delivermeat(walrus) end loop end hunter;task body bakery i

7、s rolls:food; begin loop bake(rolls); master.deliverbread(rolls) end loop end bakery;客棧問題客棧問題task body master is bread, meat, sandwich: food; procedure makesandwich is begin cook(meat); sandwich:=bread+meat; bread:=0; meat:=0; end makesandwich;客棧問題 begin bread:=0; meat:=0; sandwich:=0; loop select w

8、hen bread=0 = accept deliverbread(br: in food) do bread:=br; end deliverbread; or when meat=0 = accept delivermeat(mt: in food) do meat:=mt; end delivermeat;客棧問題 or when (sandwich0)or(bread0 and meat0)= accept lodge(snack: out food) do /入店取三明治 if sandwich=0 then makesandwich end if; snack:=sandwich;

9、 end lodge; sandwich:=0 /會(huì)合期之外 else if (bread0)and(meat0)and(sandwich=0) then makesandwich end if /棧主人活動(dòng) end select end loop end master客棧問題 explorers: array(1.numberofexploers)of explorer; begin null; end Adalodge; Bounded buffer problemtask boundedbuffer is entry putin; entry getout;end boundedbuff

10、er;task body boundedbuffer is b: array(0.k-1)of integer; ip, op: 0.k-1; count: integer; begin ip:=0; op:=0; count:=0;Bounded buffer problem loop select when (count accept putin(item:in integer) do b(ip):=item end putin; ip:=(ip+1)mod k; count:=count+1; Bounded buffer problem or when (count0) = accep

11、t getout(item:out integer) do item:=b(op); end getout; op:=(op+1)mod k; count:=count-1; end select end loopend boundedbuffer; 作業(yè) #41. 用Ada語言中的會(huì)合解決讀者/寫者問題，要求寫者優(yōu)先。即編寫一個(gè)任務(wù)，其中有如下四個(gè)入口： start_read; finish_read, start_write, finish_write. 提示：可以使用嵌套的accept語句。讀者-寫者問題Task readers_writers is entry start_read;

12、entry finish_read; entry start_write; entry finish_write;End readers_writes;Task body readers_writers is; Var read_count, write_count: integer; begin read_count:=0; write_count:=0;讀者-寫者問題 Loop select when write_count=0 = accept start_read do read_count := read_count+1; end start_read or when read_co

13、unt0 = accept finish_read do read_count := read_count-1; end finish_read; or 讀者-寫者問題 when write_count=0 = accept start_write do while read_count 0 do accept finish_read do read_count:= read_count -1; end finish_read end while end start_write; write_count:=write_count+1; or when write_count0 = accept

14、 finish_write do write_count:=write_count-1; end finish_write; end select End loop;End readers_writers讀者-寫者問題讀者活動(dòng):Readers_writers.start_read;讀操作Readers_writers.finish_read;寫者活動(dòng):Readers_writers.start_write;寫操作Readers_writers.finish_write;4.4 進(jìn)程高級通訊進(jìn)程通訊：進(jìn)程之間的相互作用。低級通訊（簡單信號）進(jìn)程互斥進(jìn)程同步高級通訊（大宗信息）高級通訊memory

15、 sharing vs. message passingdirect vs. indirectsymmetric vs. non-symmetricbuffering vs. non-buffering4.4.1 進(jìn)程通訊概念4.4.2 進(jìn)程通訊模式1. 共享內(nèi)存模式(shared memory)：2. 消息傳遞模式(message passing)：OS提供：（1）公共內(nèi)存（2）互斥同步機(jī)制P1P2Msendreceive直接：進(jìn)程-進(jìn)程間接：進(jìn)程-信箱-進(jìn)程P1P2公共內(nèi)存4.4.3 直接方式對稱形式(sender and receiver name each other)send(R,m

16、essage)receive(S,message)Send(R,M).Receive(S,N).S:R:4.4.3 直接方式receive(pid,N).send(R,M1).send(R,M2).非對稱形式(only sender names receiver)send(R,message)receive(pid,message)C/S modelR:S1:S2:4.4.3.1 有緩沖途徑(消息傳遞模式,直接方式,非對稱形式)PCBsend(R,M)size text PCBreceive(pid,N) M:N:msgmsgmsg.發(fā)送者S:接收者R:Message passing, dir

17、ect,non-symmetric, bufferingSizetextsenderlink載有消息的緩沖：進(jìn)程消息隊(duì)列管理： Var Sm:semaphore; (0) 收取消息前：P（Sm）; 消息入隊(duì)后：V（Sm);消息隊(duì)列互斥： Var m_mutex:semaphore;(1) P(m_mutex); 入列(出列)動(dòng)作; V(m_mutex);Buffer pool managementbufbufbuf.Var Sb, b_mutex:semaphore; (k,1)申請：P(Sb); P(b_mutex); 頭緩沖出鏈; V(b_mutex);釋放：P(b_mutex); 緩沖入

18、鏈頭; V(b_mutex); V(Sb);Head：緩沖池發(fā)送-接收原語Send(R,M) 根據(jù)R找接收者； P(Sb); P(b_mutex); 取一空buf; V(b_mutex); size,text,sender = buf P(m_mutex); 消息入鏈尾； V(m_mutex); V(Sm); Receive(pid,N) P(Sm); P(m_mutex); 頭消息出鏈; V(m_mutex); size,text= N sender = pid P(b_mutex); 空buf入鏈； V(b_mutex); V(Sb);Remarks：Send/receive 為高級通訊原

19、語，可用低級原語實(shí)現(xiàn)；Send/receive不是真正意義的原語，可以被中斷。4.4.3.2 無緩沖途徑(消息傳遞模式,直接方式,非對稱形式)發(fā)送-接收都發(fā)生,信息由發(fā)送者復(fù)制到接收者.PCB中兩個(gè)信號燈, S_m, S_w, 初值0.S_m: 接收進(jìn)程等待S_w: 發(fā)送進(jìn)程等待發(fā)送過程:send(R,M)根據(jù)R找到消息接收者發(fā)送消息進(jìn)程增1, 如接收進(jìn)程等待將其喚醒, 即執(zhí)行V(S_m)等待消息傳送完畢, 即執(zhí)行P(S_w)4.4.3.2 無緩沖途徑接收過程:receive(pid,N)等待消息到達(dá), 即執(zhí)行P(S_m)消息由發(fā)送進(jìn)程空間復(fù)制到接收進(jìn)程空間;喚醒發(fā)送消息進(jìn)程, 即執(zhí)行V(S_

20、w)4.4.3.2 無緩沖途徑Send(R,M)Receive(pid, N)M:N:regsendreceiveS_mS_wPCB硬件OS4.4.3.2 無緩沖途徑優(yōu)點(diǎn):節(jié)省空間(不需要buffer)缺點(diǎn):并發(fā)性差: 發(fā)送進(jìn)程需要等待接收進(jìn)程執(zhí)行receive把信息復(fù)制到接收進(jìn)程空間后才能繼續(xù).4.4.4 間接方式MailboxSend_mb(mb,m)Receive_mb(mb,n).multi-sender - multi-receiver;multi-sender - one receiver4.4.4.1 信箱屬于操作系統(tǒng)空間Type mailbox=record in,out:0.

21、k; s1,s2:semaphore; (k,0) mutex:semaphore; (1) letter:array0.k-1of message; end;Var mb:mailbox;create_mb(mb); 系統(tǒng)調(diào)用delete_mb(mb); 系統(tǒng)調(diào)用信箱通訊Procedure send_mb(var mb:mailbox; m:massage); begin with mb do begin P(s1); /申請空位 P(mutex); letterin:=m; in:=(in+1)mod k; V(mutex); V(s2) /消息增加一個(gè) end; end;信箱通訊Proc

22、edure receive_mb(var mb:mailbox; var n:massage); begin with mb do begin P(s2); /申請消息 P(mutex); n:=letterout; out:=(out+1)mod k; V(mutex); V(s1) /空位增加一個(gè) end; end;屬于操作系統(tǒng)空間的信箱Var mb: mailboxcreate_MBdelete_MBsend_MBreceive_MBcreate_MB(mb)receive_MB(mb,N)delete_MB(mb)N: send_MB(mb,M)M: UNIX進(jìn)程高級通訊機(jī)制Pipe:

23、 an unnamed file with two fds, one for write, and the other for read. The size of pipe file is limited to 4 blocks(one block is 512 bytes). int fd2; pipe(fd): 功能：創(chuàng)建一個(gè)pipe文件返回：fd0: 讀描述符； fd1: 寫描述符。pipe可以被子進(jìn)程繼承子進(jìn)程1： write(fd1,buf1,count1);子進(jìn)程2：read(fd0,buf2,count2)UNIX進(jìn)程高級通訊機(jī)制速度：pipe作為文件，需要兩次IO，但一般不會(huì)真

24、正執(zhí)行IO操作:緩沖與延遲寫(delayed write), 寫到內(nèi)存緩沖區(qū), 只要內(nèi)存資源不緊張, 緩沖區(qū)不另作它用, 不會(huì)寫到外存, 讀時(shí)可在內(nèi)存緩沖區(qū)中得到.Pipe文件大小的限制 (Eg. 2k), 循環(huán)使用, 避免緩沖資源緊張.特點(diǎn)：基于文件系統(tǒng)實(shí)現(xiàn)，與文件統(tǒng)一的界面。UNIX信號通訊機(jī)制struct proc char p_sig; procNPROCstruct user int u_signalNSIG; 系統(tǒng)調(diào)用signal(sig, func)預(yù)置信號處理程序u_signalsig=func;Func=0時(shí)接收信號進(jìn)程終止自己; Func=奇數(shù)時(shí)忽略;Func=偶數(shù)時(shí)為處理

25、程序入口.進(jìn)程初創(chuàng)時(shí)繼承其父進(jìn)程信號處理程序.信號發(fā)送與接收任何時(shí)候都可接收, 記錄在p_sig中.處理被調(diào)度選中即將由核心態(tài)轉(zhuǎn)到目態(tài).(用戶處理的中斷)Windows2000/xp的管道1. 無名管道：BOOL CreatePipe(PHANDLE hReadPipe, PHANDLE hWritepipe, LPSECURITY_ATTRIBUTES lpPipeAt, DWORD nSize)2. 命名管道：服務(wù)器端：.pipePipeName;客戶端：serverNamepipePipeNameCreateNamedPipe: 在服務(wù)器端建立管道；ConnectNamedPipe: 在

26、服務(wù)器端等待客戶連接請求；CallNamedPipe: 客戶進(jìn)程建立與服務(wù)器管道連接；ReadFile, WriteFile: 管道讀寫。Windows2000/xp的mailslot服務(wù)器端：.mailslotpathname客戶進(jìn)程：rangemailslotpathname range: 本地或服務(wù)器CreatMailslot: 服務(wù)器端創(chuàng)建郵件槽；GetMailslotInfo: 服務(wù)器查詢郵件槽信息；ReadFile: 服務(wù)器讀郵件槽；WriteFile: 客戶端發(fā)送消息。Linux共享內(nèi)存通訊textdata棧共享存儲(chǔ)區(qū)進(jìn)程P的邏輯空間textdata棧進(jìn)程Q的邏輯空間內(nèi)存空間AA

27、BB限制：只能用于同一站點(diǎn)通訊；注意：互斥問題需要用戶自己控制。Linux共享內(nèi)存通訊描述共享存儲(chǔ)區(qū)的數(shù)據(jù)結(jié)構(gòu)struct shmid_ds struct ipc_perm shm_perm; /operation perms int shm_segsz; / size of segment (bytes) _kernel_time_t shm_atime; / last attach time _kernel_time_t shm_dtime; / last detach time _kernel_time_t shm_ctime; / last change time _kernel_ip

28、c_pid_t shm_cpid; / pid of creator _kernel_ipc_pid_t shm_lpid; / pid of last operator unsigned short shm_nattch; / no. of current attaches unsigned short shm_unused; / compatibility void *shm_unused2; / ditto - used by DIPC void *shm_unused3; / unusedLinux共享內(nèi)存通訊相關(guān)系統(tǒng)調(diào)用shmget(key, size, permflg) /共享存儲(chǔ)

29、區(qū)的獲取或創(chuàng)建；shmat(shmid, shmaddr, shmflg) /共享存儲(chǔ)區(qū)的附接；shmdt(virtaddr) /共享存儲(chǔ)區(qū)的剝離；shmctrl(shmid, cmd, buf) /共享存儲(chǔ)區(qū)的控制。Linux共享內(nèi)存通訊共享存儲(chǔ)區(qū)的獲取或創(chuàng)建調(diào)用原型：int shmid=int shmget (key_t key, int size, int shmflag)；參數(shù)：Key: 標(biāo)識共享內(nèi)存的鍵值：(1)任意進(jìn)程通訊，取一名字，注意沖突，可用ftok()產(chǎn)生；(2)父子進(jìn)程通訊，IPC_PRIVATE: 子進(jìn)程繼承。size: 共享存儲(chǔ)區(qū)的大小(以字節(jié)為單位，頁面大小的整數(shù)倍

30、)shmflg: (1)權(quán)限，一般取0666; (2)標(biāo)志(a)IPC_CREATE不存在創(chuàng)建，存在返回標(biāo)識, (b)IPC_CREATE|IPC_EXCL不存在創(chuàng)建，存在報(bào)錯(cuò)。返回值：shmid: 共享內(nèi)存內(nèi)部標(biāo)識, 錯(cuò)誤返回-1。Linux共享內(nèi)存通訊共享內(nèi)存的附接調(diào)用原型*virtaddr=shmat(int shmid, char *shmaddr, int shmflag) 參數(shù)：shmid：共享內(nèi)存的ID；shmaddr：共享內(nèi)存的起始地址；0由系統(tǒng)分配；int shmflag：操作模式，SHM_RDONLY只讀模式，其它(0)讀寫模式；返回值：成功時(shí)，虛擬空間起始地址，失敗時(shí)返回

31、-1。Linux共享內(nèi)存通訊脫離附接調(diào)用原型int shmdt(char *virtaddr)參數(shù)：virtaddr：共享內(nèi)存的虛擬地址。返回值：成功時(shí)返回0。失敗時(shí)返回-1。Linux共享內(nèi)存通訊共享內(nèi)存控制調(diào)用原型int shmctl(int shmid , int cmd , struct shmid_ds *buf );參數(shù)shmid：共享內(nèi)存的ID。cmd：是控制命令(IPC_STAT 取狀態(tài)；IPC_SET 設(shè)狀態(tài)；IPC_RMID 刪除)buf: shmid_ds結(jié)構(gòu)體指針。返回值：成功：0, 失敗：-1Linux共享內(nèi)存通訊(例子)發(fā)送進(jìn)程 sndshm.c#include#i

32、nclude#include#include #include#includemain()int shmid; char *viraddr;char bufferBUFSIZ; shmid=shmget(1234,BUFSIZ,0666|IPC_CREAT); viraddr=(char*)shmat(shmid, 0, 0); Linux共享內(nèi)存通訊(例子) while(1) puts(Enter some text:);fgets(buffer,BUFSIZ,stdin); strcat(viraddr,buffer); if(strncmp(buffer,end,3)=0) break;shmdt(viraddr); exit(0);Linux共享內(nèi)存通訊(例子)接收進(jìn)程 rcvsh