行程同步.ppt
《行程同步.ppt》由会员分享,可在线阅读,更多相关《行程同步.ppt(30页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、行程同步李紹群learrymdu.edu.tw背景/Producer While(true)while(counter=SUBBER_SIZE);bufferin=nexProduced;in=(in+1)%BUFFER_SIZE;counter+;/ConsumerWhile(true)while(counter=0);nextConsumed=bufferout;out=(out+1)%BUFFER_SIZE;counter-;n同時存取共享資料時可能造成結果不正確n生產者與消費者問題2競爭情況(Race Condition)ncount+could be implemented as r
2、egister1=count register1=register1+1 count =register1ncount-could be implemented as register2=count register2=register2-1 count =register2nConsider this execution interleaving with“count=5”initially:S0:producer execute register1=count register1=5S1:producer execute register1=register1+1 register1=6
3、S2:consumer execute register2=count register2=5 S3:consumer execute register2=register2-1 register2=4 S4:producer execute count=register1 count=6 S5:consumer execute count=register2 count=43臨界區間(Critical-Section)n互斥(mutual exclusion)n如果行程pi正在臨界區間內執行,則其他行程不能在其臨界區間內執行n進行(progress)n如果沒有行程在臨界區間內執行,同時某一行
4、程想要進入其臨界區間,那麼只有那些不在剩餘區間執行的行程才能加入決定誰將在下一次進入臨界區間,並且這個選擇不得無限期地延遲下去n限制等待(bound waiting)n在一個行程已經要求進入其臨界區間,而此要求尚未被答應之前,允許其它的行程進入其臨界區間的次數有一個限制4Petersons 解決方案n須符合n互斥性存在n進行的要求須滿足n限制性的等待須符合n兩個行程共享以下資料nint turn;nboolean flag2;5同步之硬體n硬體同步可方便程式寫作及增加系統效率n單一處理器(Uniprocessors)n禁止中斷產生n在多處理器系統上會降低系統效能n現今多數電腦提供一個特殊硬體指
5、令允許在同一個記憶體週期(automically)內n修改一個字組內容n交換兩個字組內容n不同硬體間實作有困難6號誌(Semaphore)n號誌S 為一個整數n只能透過不可分割運算 wait()及 signal()存取n舊稱 P()and V()wait(S)while(S=0);S-;signal(S)S+;7一般號誌型同步工具n計數號誌(counting semaphore)n值不受限制n二元號誌(binary semaphore)n值可以是0 或 1n又稱為互斥鎖(mutex locks)Semaphore S;/初始值為 1wait(S);臨界區間(Critical Section)s
6、ignal(S);8實作號誌n號誌的缺點-忙碌等待(busy waiting)n當有行程進入臨界區間時,其他行程會在入口處等待浪費CPU資源n盤旋鎖(spinlock)nblock 將行程放置等待佇列中nwakeup 將行程從佇列中提出並放入就緒佇列wait(semaphore*S)Svalue-;if(Svalue 0)add this process to Slist;block();signal(semaphore*S)Svalue+;if(Svalue=0)remove a process P from Slist wakeup(P);9死結(deadlock)與飢餓(Stravati
7、on)n死結(Deadlock)n兩個行程等待一項僅能由等待行程所引發的事件n飢餓(Starvation)n無限期阻滯(indefinite blocking)n行程無限期等待號誌,採用後進先出(LIFO)結構時10典型同步問題n有限緩衝區問題(Bounded-Buffer Problem)n讀取者-寫入者問題(Readers and Writers Problem)n哲學家進餐問題(Dining Philosophers Problem)11有限緩衝區問題(Bounded-Bufferd Problem)nN buffers,each can hold one itemn號誌 mutex 初
8、始值設定為 1n號誌 full 初始值設定為 0n號誌 empty 初始值設定為 N12有限緩衝區問題(Bounded-Bufferd Problem)/producer processdo /produce an item wait(empty);wait(mutex);/add the item to the buffer signal(mutex);signal(full);while(true);/consumerdo wait(full);wait(mutex);/remove an item from buffer signal(mutex);signal(empty);/cons
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 行程 同步
限制150内