操作系统课件ch7

1、Chapter 7: Process SynchronizationnBackground 背景nThe Critical-Section Problem 临界区的问题nSynchronization Hardware 同步硬件nSemaphores 信号量nClassical Problems of Synchronization 同步的经典问题nCritical Regions 临界区nMonitors 管程Backgroundn不是一个人在战斗，关键区域只能一个人战斗不是一个人在战斗，关键区域只能一个人战斗nConcurrent access to shared data may res

2、ult in data inconsistency. 对共享数据区的并发访问导致数据的不一致性对共享数据区的并发访问导致数据的不一致性nMaintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes. 维持数据的一致性要求保证合作进程按一定的顺序执行的机制。维持数据的一致性要求保证合作进程按一定的顺序执行的机制。nShared-memory solution to bounded-buffer problem (Chapter 4) allows

3、at most n 1 items in buffer at the same time. A solution, where all N buffers are used is not simple. nSuppose that we modify the producer-consumer code by adding a variable counter, initialized to 0 and incremented each time a new item is added to the bufferBackgroundn进程的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞

4、争进程的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞争（互斥）与协作（同步）（互斥）与协作（同步）n互斥：互斥：两个并行的进程两个并行的进程A、B，如果当如果当A进行某个操作时，进行某个操作时，B不能做这一操作，不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。 n同步：同步：我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。n进程之间的进程之间的互斥互斥是由于共享系统资源而引起的一种间接制约关系是由于共享系统资源而引起的一种

5、间接制约关系n进程之间的进程之间的同步同步是并发进程由于要协作完成同一个任务而引起的一种直是并发进程由于要协作完成同一个任务而引起的一种直接制约关系接制约关系n如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源（即使某个进程刚用过也允许再次使用），这是通过（即使某个进程刚用过也允许再次使用），这是通过进程互斥进程互斥的方式来的方式来管理共享资源管理共享资源n如果某个进程如果某个进程通过共享资源得到指定消息通过共享资源得到指定消息时，在指定消息未到达之前，时，在指定消息未到达之前，即使无进程在共享资源仍不允许该进程去使用共享资

6、源，这是通过采用即使无进程在共享资源仍不允许该进程去使用共享资源，这是通过采用进程同步进程同步的方式来管理共享资源。的方式来管理共享资源。Bounded-Buffer nShared data#define BUFFER_SIZE 10typedef struct . . . item;item bufferBUFFER_SIZE;int in = 0;int out = 0;int counter = 0;Bounded-Buffer nProducer process item nextProduced;while (1) while (counter = BUFFER_SIZE); /*

7、 do nothing */bufferin = nextProduced;in = (in + 1) % BUFFER_SIZE;counter+;Bounded-Buffer nConsumer process item nextConsumed;while (1) while (counter = 0); /* do nothing */nextConsumed = bufferout;out = (out + 1) % BUFFER_SIZE;counter-;Bounded BuffernThe statementscounter+;counter-;must be performe

8、d atomically. nAtomic operation（原子操作） means an operation that completes in its entirety without interruption.Bounded BuffernThe statement “count+” may be implemented in machine language as:register1 = counterregister1 = register1 + 1counter = register1nThe statement “count-” may be implemented as:re

9、gister2 = counterregister2 = register2 1counter = register2Bounded BuffernIf both the producer and consumer attempt to update the buffer concurrently, the assembly language statements may get interleaved.nInterleaving depends upon how the producer and consumer processes are scheduled.Bounded Buffern

10、Assume counter is initially 5. One interleaving of statements is:producer: register1 = counter (register1 = 5)producer: register1 = register1 + 1 (register1 = 6)consumer: register2 = counter (register2 = 5)consumer: register2 = register2 1 (register2 = 4)producer: counter = register1 (counter = 6)co

11、nsumer: counter = register2 (counter = 4)nThe value of count may be either 4 or 6, where the correct result should be 5.Race Condition竞争条件nRace condition: The situation where several processes access and manipulate shared data concurrently. The final value of the shared data depends upon which proce

12、ss finishes last. 竞争条件：几个进程并行地访问和操作共享数据的情形。最后的结果取决于最后那一个进程最后完成。nTo prevent race conditions, concurrent processes must be synchronized. 为了阻止出现竞争的条件，并行进程必须同步。The Critical-Section Problem临界区问题临界区问题nn processes all competing to use some shared data n个进程都需要竞争使用某些共享的数据区。个进程都需要竞争使用某些共享的数据区。nEach process ha

13、s a code segment, called critical section, in which the shared data is accessed. 每个进程有一个代码段，称为每个进程有一个代码段，称为临界区临界区，访问共享数据的代码都在，访问共享数据的代码都在临界区中。临界区中。nProblem ensure that when one process is executing in its critical section, no other process is allowed to execute in its critical section. 问题问题-确保当一个进程在

14、临界区中时，没有其它进程在临界区中。确保当一个进程在临界区中时，没有其它进程在临界区中。你方唱罢我登场你方唱罢我登场临界区问题进程结构n进程的一般结构do entry sectioncritical sectionexit sectionreminder section while (1);Solution to Critical-Section Problem临界区问题的解决方案-满足三个条件Mutual Exclusion(互斥条件互斥条件)： If process Pi is executing in its CS, then no other processes can be exec

15、uting in their CSs. Progress(进入条件进入条件)：If no process is executing in its CS and some processes wish to enter their CSs, then only those processes that are not executing in their RSs can participate in the decision on which will enter its CS next, and this selection cannot be postponed indefinitely.

16、Bounded Waiting(有限等待的条件有限等待的条件)：There exists a bound, or limit, on the number of times that other processes are allowed to enter their CSa after a process has made a request to enter its CS and before that request is granted. Assume that each process executes at a nonzero speed. No assumption concer

17、ning relative speed of the n processes.Initial Attempts to Solve Problem解决临界区问题的初步方案-考虑两个进程nOnly 2 processes, P0 and P1仅考虑两个进程的情形nGeneral structure of process Pi (other process Pj, j=1-i) 进程中的一般结构do entry sectioncritical sectionexit sectionreminder section while (1);nProcesses may share some common

18、variables to synchronize their actions. 进程通过共享一些变量来同步它们的行为。 Algorithm 1nShared variables: nint turn;initially turn = 0nturn = i Pi can enter its critical sectionnProcess Pido while (turn != i) ;critical sectionturn = j;reminder section while (1);nSatisfies mutual exclusion, but not progress两进程需严格两进程

19、需严格按顺序交替执行按顺序交替执行，一个进程在，一个进程在RS就可能使另一个进程不能进其就可能使另一个进程不能进其CSAlgorithm 2nShared variablesnboolean flag2;initially flag 0 = flag 1 = false.nflag i = true Pi ready to enter its critical sectionnProcess Pido flagi = true;while (flagj) ;critical sectionflag i = false;remainder section while (1);nSatisfies

20、 mutual exclusion, but not progress requirement.两进程需严格按一定两进程需严格按一定时序时序运行，否则可能在运行，否则可能在ES无限等待而没有进程能进入其无限等待而没有进程能进入其CSAlgorithm 3nCombined shared variables of algorithms 1 and 2.nProcess Pido flag i = true;turn = j;while (flag j & turn = j) ;critical sectionflag i = false;remainder section while (1);n

21、Meets all three requirements; solves the critical-section problem for two processes.Bakery Algorithm面包师算法面包师算法nBefore entering its critical section, process receives a number. Holder of the smallest number enters the critical section. 进入临界区前，进程得到一个数字，持有最进入临界区前，进程得到一个数字，持有最小数字的进程获准进入临界区。小数字的进程获准进入临界区

22、。nIf processes Pi and Pj receive the same number, if i j, then Pi is served first; else Pj is served first. 如果两个如果两个进程得到相同的数字，进程号较小者获准进入临界区进程得到相同的数字，进程号较小者获准进入临界区nThe numbering scheme always generates numbers in increasing order of enumeration; i.e., 1,2,3,3,3,3,4,5. 永远以增序的形式产生数字。永远以增序的形式产生数字。Critic

23、al section for n processesn个进程的临界区算法个进程的临界区算法Bakery Algorithm 面包师算法nNotation lexicographical order (ticket #, process id #)n(a,b) (c,d) if a c or if a = c and b dnmax (a0, an-1) is a number, k, such that k ai for i ： 0, , n 1nShared databoolean choosingn;int numbern; Data structures are initialized

24、to false and 0 respectivelyBakery Algorithm do choosingi = true;numberi = max(number0, number1, , number n 1)+1;choosingi = false;for (j = 0; j n; j+) while (choosingj) ; while ( (numberj != 0) & (numberj,j) (numberi,i) ) ;critical sectionnumberi = 0;remainder section while (1);Synchronization Hardw

25、arenTest and modify the content of a word atomically.boolean TestAndSet(boolean &target) boolean rv = target;tqrget = true;return rv;Mutual Exclusion with Test-and-SetnShared data: boolean lock = false;nProcess Pido while (TestAndSet(lock) ;critical sectionlock = false;remainder sectionSynchronizati

26、on Hardware nAtomically swap two variables.void Swap(boolean &a, boolean &b) boolean temp = a;a = b;b = temp;Mutual Exclusion with SwapnShared data (initialized to false): boolean lock;boolean waitingn;nProcess Pido key = true;while (key = true) Swap(lock,key);critical sectionlock = false;remainder

27、sectionSemaphoresnSynchronization tool that does not require busy waiting.nSemaphore S integer variablencan only be accessed via two indivisible (atomic) operationswait (S): while S 0 do no-op;S-;signal (S): S+;Critical Section of n ProcessesnShared data: semaphore mutex; /initially mutex = 1nProces

28、s Pi: do wait(mutex); critical section signal(mutex); remainder section while (1); Semaphore Implementationn能不能聪明一点？能不能聪明一点？nDefine a semaphore as a recordtypedef struct int value; struct process *L; semaphore;nAssume two simple operations:nblock suspends the process that invokes it.nwakeup(P) resum

29、es the execution of a blocked process P.ImplementationnSemaphore operations now defined as wait(S):S.value-;if (S.value 0) add this process to S.L;block;signal(S): S.value+;if (S.value = 0) remove a process P from S.L;wakeup(P);Semaphore as a General Synchronization ToolnExecute B in Pj only after A

30、 executed in PinUse semaphore flag initialized to 0nCode:PiPj Await(flag)signal(flag)BDeadlock and StarvationnDeadlock（死锁）（死锁） two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.nLet S and Q be two semaphores initialized to 1P0P1wait(S

31、);wait(Q);wait(Q);wait(S); signal(S);signal(Q);signal(Q)signal(S);nStarvation（饿死）（饿死） indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.Two Types of SemaphoresnCounting semaphore（计数信号量）（计数信号量） integer value can range over an unrestricted domain.nBi

32、nary semaphore（二元信号量）（二元信号量） integer value can range only between 0 and 1; can be simpler to implement.nCan implement a counting semaphore S as a binary semaphore.Implementing S as a Binary SemaphorenData structures:binary-semaphore S1, S2;int C: nInitialization:S1 = 1S2 = 0C = initial value of sema

33、phore SImplementing Snwait operationwait(S1);C-;if (C 0) signal(S1);wait(S2);signal(S1);nsignal operationwait(S1);C +;if (C = 0)signal(S2);elsesignal(S1);Classical Problems of SynchronizationnBounded-Buffer Problem（有界缓存）nReaders and Writers Problem（读者-写者）nDining-Philosophers Problem（哲学家就餐）Bounded-Bu

34、ffer ProblemnShared datasemaphore full, empty, mutex;Initially:full = 0, empty = n, mutex = 1Bounded-Buffer Problem Producer Processdo produce an item in nextp wait(empty);wait(mutex); add nextp to buffer signal(mutex);signal(full); while (1);Bounded-Buffer Problem Consumer Processdo wait(full)wait(

35、mutex); remove an item from buffer to nextc signal(mutex);signal(empty); consume the item in nextc while (1);Readers-Writers ProblemnShared datasemaphore mutex, wrt;Initiallymutex = 1, wrt = 1, readcount = 0Readers-Writers Problem Writer Processwait(wrt); writing is performed signal(wrt);Readers-Wri

36、ters Problem Reader Processwait(mutex);readcount+;if (readcount = 1)wait(wrt);signal(mutex); reading is performed wait(mutex);readcount-;if (readcount = 0)signal(wrt);signal(mutex):Readers-Writers ProblemnWriter正在写时，第一个reader等待writer，其他readers等待第一个readern只要有readers，writer必须等nWriters必须等writer（有writer

37、正在writing）和readers（有readers正在reading）n思考：能让写者优先吗？能让两者公平吗？Dining-Philosophers ProblemnShared data semaphore chopstick5;Initially all values are 1Dining-Philosophers Problem （1）nPhilosopher i:do wait(chopsticki)wait(chopstick(i+1) % 5) eat signal(chopsticki);signal(chopstick(i+1) % 5); think while (1)

38、;Dining-Philosophers Problem（2）nStarvation？nHow to deal with？About synchronizationnRace conditionnMust keep correct timing sequencesnUsernUsually timing errorsnNeed play tricknbadnOsnSemaphorenBetternBut，wrong use of semaphores resulting in timing errorsAbout synchronization(1)nHow to deal with erro

39、rs listed above？nHigh level synchronization constructnmonitorSignal(mutex) CSWait(mutex)No mutual exclusionwait(mutex) Wait(mutex)Deadlock MonitorsnA monitor is characterized by a set of programmer-defined operators.nMonitor确保一次只有一个进程在monitor内活跃。monitor monitor-name/shared variable declarationsproce

40、dure body P1 () . . .procedure body P2 () . . . procedure body Pn () . . . initialization code() Monitorsn如何保证？条件变量nTo allow a process to wait within the monitor, a condition variable must be declared, ascondition x, y;nCondition variable can only be used with the operations wait and signal.nThe ope

41、rationx.wait();means that the process invoking this operation is suspended until another process invokesx.signal();nThe x.signal operation resumes exactly one suspended process. If no process is suspended, then the signal operation has no effect.Schematic View of a MonitorMonitor With Condition Vari

42、ablesDining Philosophers Example只有同时拿到左右两根筷子才能吃monitor dp enum thinking, hungry, eating state5;condition self5;void pickup(int i) / following slidesvoid putdown(int i) / following slidesvoid test(int i) / following slidesvoid init() for (int i = 0; i 5; i+)statei = thinking;Dining Philosophersvoid p

43、ickup(int i) statei = hungry;test(i);if (statei != eating)selfi.wait();void putdown(int i) statei = thinking;/ test left and right neighborstest(i+4) % 5);test(i+1) % 5);Dining Philosophersvoid test(int i) if ( (state(i + 4) % 5 != eating) & (statei = hungry) & (state(i + 1) % 5 != eating) statei =

44、eating;selfi.signal();Dining Philosophersnphilosopher indp.pickup(i);nn eatndp.putdown(i);Synchronization examplesnSolaris 2: adaptive mutex, condition variable, semaphore, reader-writer lock, turnstile(十字转门)nWindows XP: nIn kernel - mask interrupt (uniprocessor), spinlock(multiprocessor)nOutside ke

45、rnel- dispatcher objectsnMutex, semaphore, event, timernLinux 2.6: enable/disable preemption(uniprocessor), spinlock(multiprocessor) nPthreads API: mutex lock, condition variable, read-write lockAtomic Transactions原子交易nCS-你方唱罢我登场nMutual exclusion of critical sectionsnAT-油盐坛子，公不离婆秤不离砣 nHow to make su

46、re a critical section forms a single logic unit of worknEither performed in its entiretynOr not performed at allnTransaction交易nA collection of instructions(or operations)that performs a single logical functionnA major issue in processing transactions is the preservation of atomicity despite the poss

47、ibility of failures within the computer systemnA sequence of read and write operations, terminated by a commit or abort operationAtomic Transactions(1)nCommit提交nThe effect of a committed transaction can not be undone by abortion of the transactionnAbort终止nAn aborted transaction must have no effect o

48、n the state of the data it has already modifiednThe state of the data accessed by an aborted transaction must be restored to what it was just before the transaction started executing.n如何恢复？存储信息。怎么存储？nTo record on stable storage, information describing all the modifications made by the transaction to

49、 the various data it accessedHow to recordnLog-based recoverynTransaction namenData item namenOld valuenNew valuenCheckpointsnTo reduce the searching overheadnConcurrent atomic transactionsnSerializabilitynLocking protocolnTimestamp-based protocolsSummaryn进程的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞争（互斥）与协作（同步）进程

50、的同步隐含了系统中并发进程之间存在的两种相互制约关系：竞争（互斥）与协作（同步）n互斥：互斥：两个并行的进程两个并行的进程A、B，如果当如果当A进行某个操作时，进行某个操作时，B不能做这一操作，进程间的这种不能做这一操作，进程间的这种限制条件称为进程互斥，这是引起资源不可共享的原因。限制条件称为进程互斥，这是引起资源不可共享的原因。 n同步：同步：我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。n进程之间的互斥是由于共享系统资源而引起的一种间接制约关系进程之间的互斥是由于共享系统资源而引起的一种间接制约关系n进程之间的同步

51、是并发进程由于要协作完成同一个任务而引起的一种直接制约关系进程之间的同步是并发进程由于要协作完成同一个任务而引起的一种直接制约关系n如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源（即使某个进程刚用过也允如果无进程在使用共享资源时，可允许任何一个进程去使用共享资源（即使某个进程刚用过也允许再次使用），这是通过许再次使用），这是通过进程互斥进程互斥的方式来管理共享资源的方式来管理共享资源n如果某个进程如果某个进程通过共享资源得到指定消息通过共享资源得到指定消息时，在指定消息未到达之前，即使无进程在共享资源仍时，在指定消息未到达之前，即使无进程在共享资源仍不允许该进程去使用共享资源，这

52、是通过采用不允许该进程去使用共享资源，这是通过采用进程同步进程同步的方式来管理共享资源。的方式来管理共享资源。n临界资源：一些被临界资源：一些被共享的资源共享的资源，具有，具有一次仅允许一个进程使用一次仅允许一个进程使用的特点的特点n临界区：临界区：并发进程访问临界资源并发进程访问临界资源的那段的那段必须互斥执行的程序必须互斥执行的程序n实现临界区互斥一个遵循的准则实现临界区互斥一个遵循的准则n有空让进，临界区空闲时，允许一个进程进入执行有空让进，临界区空闲时，允许一个进程进入执行n无空等待，有进程在临界区执行时，要进入的进程必须等待无空等待，有进程在临界区执行时，要进入的进程必须等待n让权等

53、待，有进程在临界区执行时，要求进入的进程必须立即释放让权等待，有进程在临界区执行时，要求进入的进程必须立即释放CPU而等待而等待n有限等待，不应该使进入临界区的进程无限期地等待在临界区之外有限等待，不应该使进入临界区的进程无限期地等待在临界区之外n信号量及信号量及p、v操作操作n经典同步问题经典同步问题n原子交易原子交易作业n1. The first known correct software solution to the critical-section problem for two threads was developed by Dekker. The two threads, T

54、0 and T1, share the following variables: Boolean flag2; /* initially false */ int turn;The structure of thread Ti (i=0 or 1), with Tj (j=1 or 0) being the other thread, is shown as: do flag i = true;while ( flag j ) if (turn = j) flag i = false; while (turn = = j); flag i = true; critical section turn = j;flag i = false; remainder section while (1);Prove that the algorithm satisfies all three requirements for the critical-section problem.7-cont.n2. The first known correct software solution to the critical-section problem for n processe