計算機操作系統(tǒng)chb全解PPT課件

1、1Inter-process CommunicationThree issues are involved in inter-process communication (IPC)1.How one process can pass information to another.2.Resource shared (e.g. printer) How to make sure two or more processes do not get into each others way when engaging in critical activities. 3.Process cooperat

2、ion Proper sequencing when dependencies are present.第1頁/共62頁2Process Synchronization 進(jìn)程同步：對多個相關(guān)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，用于保證這種關(guān)系的相應(yīng)機制稱為進(jìn)程同步。（或相互合作的一組并發(fā)進(jìn)程在一些關(guān)鍵點上可能需要互相等待與互通消息，這種相互制約的等待與互通消息稱為進(jìn)程同步。） 例：醫(yī)生為病員診病，認(rèn)為需要化驗，開出化驗單。病員取樣送到化驗室，等化驗完畢交給醫(yī)生化驗結(jié)果，繼續(xù)診病。醫(yī)生診病是一個進(jìn)程，化驗室的化驗工作是另一個進(jìn)程，它們各自獨立的活動，但又共同完成醫(yī)療任務(wù)?；炦M(jìn)程只有在接收到診病進(jìn)程的化驗單

3、后才開始工作；而診病進(jìn)程只有獲得化驗結(jié)果后才能繼續(xù)為該病員診病，并根據(jù)化驗結(jié)果確定醫(yī)療方案。 例：計算進(jìn)程與打印進(jìn)程共享一個單緩沖區(qū)的問題。第2頁/共62頁3Spooling Example: CorrectSpooler DirectoryabcProg.cProg.n4567F2outinProcess 1Process 2next_free = in;next_free = inint next_free;Stores F1 into next_free;Stores F2 into next_free;int next_free;124in=next_free+1F1in=next_f

4、ree+135689第3頁/共62頁4Spooling Example: RacesShared memoryabcProg.cProg.n4567outinProcess 1Process 2next_free = in;/* value: 7 */next_free = in/* value: 7 */int next_free;Stores F1 into next_free;Stores F2 into next_free;int next_free;152in=next_free+1F1in=next_free+1634F2第4頁/共62頁5Mutual exclusionSome

5、way of making sure that if one process is using a shared variable or file, the other processes will be excluded from doing the same thing.Race conditionsRace conditions are situations in which several processes access shared data and the final result depends on the order of operations.The key to avo

6、id race conditions is to prohibit more than one process from reading and writing the shared data at the same time.第5頁/共62頁6 Critical Resource(臨界資源) 一次僅允許一個進(jìn)程訪問的資源稱為臨界資源 臨界資源包括： 硬件資源：輸入機、打印機等 軟件資源：變量、表格、隊列、文件等 Critical Region (Critical Section) The part of the program where the critical resource is a

7、ccessed is called critical region or critical section.If we could arrange matters such that no two processes were ever in their critical regions at the same time, we could avoid races.第6頁/共62頁7程 序 段1程 序 段2程 序 段n共 享 變 量第7頁/共62頁8a := a -1 print (a)a := a +1 print (a)P1P2If a 0then a := a +1else a:= a-

8、1P3Mutual exclusionentry sectionexit section critical section remainder section第8頁/共62頁9Critical Region Requirement Four conditions to provide mutual exclusion1.No two processes simultaneously in critical region2.No assumptions made about speeds or numbers of CPUs3.No process running outside its cri

9、tical region may block another process4.No process must wait forever to enter its critical region第9頁/共62頁10Mutual exclusion using critical regions第10頁/共62頁11Mutual Exclusion Possible Solutions Disabling Interrupts Lock Variables Strict Alternation Petersons solution TSL Sleep and Wakeup第11頁/共62頁12So

10、lution 1 - Disabling Interrupts How does it work? Disable all interrupts just after entering a critical section and re-enable them just before leaving it. Why does it work? With interrupts disabled, no clock interrupts can occur. (The CPU is only switched from one process to another as a result of c

11、lock or other interrupts, and with interrupts disabled, no switching can occur.) Problems: What if the process forgets to enable the interrupts? Multiprocessor? (disabling interrupts only affects one CPU) Only used inside OS第12頁/共62頁13Solution 2 - Lock Variable shared int lock = 0;/* entry_code: exe

12、cute before entering critical section */while (lock != 0) /* do nothing */ ;lock = 1; - critical section -/* exit_code: execute after leaving critical section */lock = 0;This solution may violate property 1. If a context switch occurs after one process executes the while statement, but before settin

13、g lock = 1, then two (or more) processes may be able to enter their critical sections at the same time.第13頁/共62頁14Solution 3 - Strict AlternationThis solution may violate property 3. Since the processes must strictly alternate entering their critical sections, a process wanting to enter its critical

14、 section twice in a row will be blocked until the other process decides to enter (and leave) its critical section.第14頁/共62頁15Solution 4 - Petersonsenter_region ( i );Critical regionleave_region ( i );Noncritical regionprocess i第15頁/共62頁16Solution 4 - PetersonsPetersons solution for achieving mutual

15、exclusion第16頁/共62頁17Hardware solution 5: Test-and-Set Locks (TSL)The hardware must support a special instruction, tsl, which does 2 things in a single atomic action: tsl register, flag(a) copy a value in memory (flag) to a CPU register (b) set flag to 1.第17頁/共62頁18Test-and-Set Locks (TSL)Entering an

16、d leaving a critical region using the TSL instruction返回第18頁/共62頁19Test-and-Set Locks (TSL)Entering and leaving a critical region using the XCHG instruction.第19頁/共62頁20Mutual Exclusion with Busy Waiting The last two solutions, 4 and 5, require BUSY-WAITING; that is, a process executing the entry code

17、 will sit in a tight loop using up CPU cycles, testing some condition over and over, until it becomes true. Busy-waiting may lead to the PRIORITY-INVERSION PROBLEM if simple priority scheduling is used to schedule the processes.第20頁/共62頁21Mutual Exclusion with Busy Waiting Example: Test-and-set Lock

18、s: P0 (low) - in cs -x | context switch | P1 (high) -tsl-cmp-jnz-tsl. x-tsl-cmp. x-. forever. Note, since priority scheduling is used, P1 will keep getting scheduled and waste time doing busy-waiting. :-( Thus, we have a situation in which a low-priority process is blocking a high-priority process,

19、and this is called PRIORITY-INVERSION.第21頁/共62頁22Sleep and Wakeup Solution of previous problems: sleep and wakeup(busy waiting) Block instead of busy waiting when it is not allowed to enter the Critical Region (sleep) Wakeup when it is OK to retry entering the critical region第22頁/共62頁23Producer-Cons

20、umer Problem (Bounded-buffer problem ) Consider two processes share a circular buffer that can hold N items. Producers add items to the buffer and Consumers remove items from the buffer. The Producer-Consumer Problem is to restrict access to the buffer so correct executions result.第23頁/共62頁24Sleep a

21、nd WakeupProducer-consumer problem with fatal race conditionSwitch to producer第24頁/共62頁25Semaphores (E.W. Dijkstra,1965) A SEMAPHORE, S, is a structure consisting of two parts: (a) an integer counter, COUNT (b) a queue of pids of blocked processes, Q That is, struct sem_struct int count; queue Q; se

22、maphore;semaphore S;第25頁/共62頁26Semaphores A semaphore count represents count number of abstract resources Counting semaphores: 0.N Binary semaphores: 0,1 There are 2 operations on semaphores The Down (P) operation is used to acquire a resource and decrements count. The Up (V) operation is used to re

23、lease a resource and increments count. Any semaphore operation is indivisible, must be executed atomically. (what is primitive?) 第26頁/共62頁27Semaphores Suppose that P is the process making the down and up system calls. The operations are defined as follows:P操作 DOWN(S): S.count = S.count - 1; /apply f

24、or a resource if (S.count 0) /if no resourceblock(P); (a) enqueue the pid of P in S.Q,(b) block process P (remove the pid from the ready queue), and(c) pass control to the scheduler. 執(zhí)行一次P操作后，若S.count0，則|S.count|等于Q隊列中等待S資源的進(jìn)程數(shù)。第27頁/共62頁28SemaphoresV操作 UP(S): S.count = S.count + 1; /release a resour

25、ce if ( S.count0表示有S.count個資源可用 S.count=0表示無資源可用 S.count0則|S.count|表示S等待隊列中的進(jìn)程個數(shù) P(S)：表示申請一個資源 V(S)：表示釋放一個資源。信號量的初值應(yīng)該大于等于02) P,V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作 當(dāng)為互斥操作時，它們同處于同一進(jìn)程；當(dāng)為同步操作時，則不在同一進(jìn)程中出現(xiàn)。 如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要，一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前； 而兩個V操作的順序無關(guān)緊要。討論：討論：第43頁/共62頁443) 信號量同步的缺點

26、用信號量可實現(xiàn)進(jìn)程間的同步，但由于信號量的控制分布在整個程序中，其正確性分析很困難。4) 引入管程 1973年，Hoare和Hanson提出一種高級同步原語管程； 其基本思想是把信號量及其操作原語封裝在一個對象內(nèi)部。 管程是管理進(jìn)程間同步的機制，它保證進(jìn)程互斥地訪問共享變量，并方便地阻塞和喚醒進(jìn)程。 管程可以函數(shù)庫的形式實現(xiàn)。相比之下，管程比信號量好控制。第44頁/共62頁45Monitors A monitor is a collection of procedures, variables, and data structures that can only be accessed by

27、one process at a time (for the purpose of mutual exclusion). To allow a process to wait within the monitor, a condition variable must be declared, as condition x, y; Condition variable can only be used with the operations wait and signal (for the purpose of synchronization). The operationwait(x);mea

28、ns that the process invoking this operation is suspended until another process invokessignal(x); The signal(x) operation resumes exactly one suspended process. If no process is suspended, then the signal operation has no effect.第45頁/共62頁46MonitorsExample of a monitor第46頁/共62頁47MonitorsOutline of pro

29、ducer-consumer problem with monitors only one monitor procedure active at one time buffer has N slots第47頁/共62頁48Message passingPossible Approaches of IPC:1) Shared memory2) Shared file mode;pipe: is a shared fileOne end is for reading and one end is for writing.3) Message passing: primitive: send an

30、d receiveAssign each process a unique address such as addr. Then, send messages directly to the process: send(addr, msg); recv(addr, msg);Use mailboxes: send(mailbox, msg); recv(mailbox, msg);第48頁/共62頁49Message PassingThe producer-consumer problem with N messages第49頁/共62頁50BarriersUse of a barriera)

31、processes approaching a barrierb) all processes but one blocked at barrierc)last process arrives, all are let throughExample: Parallel matrix multiplication第50頁/共62頁51Classical IPC Problems These problems are used for testing every newly proposed synchronization scheme: Bounded-Buffer (Producer-Cons

32、umer) Problem Dining-Philosophers Problem Readers and Writers Problem第51頁/共62頁52Dining Philosophers Dining Philosophers Problem Dijkstra, 1965: Problem: Five philosophers are seated around a table. There is one fork between each pair of philosophers. Each philosopher needs to grab the two adjacent f

33、orks in order to eat. Philosophers alternate between eating and thinking. They only eat for finite periods of time.第52頁/共62頁53 Philosophers eat/think Eating needs 2 forks Pick one fork at a time How to prevent deadlock Dining Philosophers第53頁/共62頁54Dining PhilosophersA nonsolution to the dining phil

34、osophers problem第54頁/共62頁55Dining Philosophers Problem: Suppose all philosophers execute the first DOWN operation, before any have a chance to execute the second DOWN operation; that is, they all grab one fork. Then, deadlock will occur and no philosophers will be able to proceed. This is called a C

35、IRCULAR WAIT. Other Solutions: Only allow up to four philosophers to try grabbing their forks. Asymmetric solution: Odd numbered philosophers grab their left fork first, whereas even numbered philosophers grab their right fork first. Protect the five statements following think() by mutex Pick-up the forks only if both are available. See Fig. 2-46. 第55頁/共62頁56Dining PhilosophersSolution to di