.HTML "Process Sleep and Wakeup on a Shared-memory Multiprocessor.TLProcess Sleep and Wakeup on a Shared-memory Multiprocessor.AURob PikeDave PresottoKen ThompsonGerard Holzmann.sprob,presotto,ken,gerard@plan9.bell-labs.com.AB.FSAppeared in a slightly different form in.IProceedings of the Spring 1991 EurOpen Conference,.RTromsø, Norway, 1991, pp. 161-166..FEThe problem of enabling a `sleeping' process on a shared-memory multiprocessoris a difficult one, especially if the process is to be awakened by an interrupt-timeevent.  We present here the codefor sleep and wakeup primitives that we use in our multiprocessor system.The code has been exercised by years of active use and by a verificationsystem..AE.LPOur problem is to synchronise processes on a symmetric shared-memory multiprocessor.Processes suspend execution, or.I sleep,while awaiting an enabling event such as an I/O interrupt.When the event occurs, the process is issued a.I wakeupto resume its execution.During these events, other processes may be running and other interruptsoccurring on other processors..LPMore specifically, we wish to implement subroutines called.CW sleep ,callable by a process to relinquish control of its current processor,and.CW wakeup ,callable by another process or an interrupt to resume the executionof a suspended process.The calling conventions of these subroutines will remain unspecifiedfor the moment..LPWe assume the processors have an atomic test-and-set or equivalentoperation but no other synchronisation method.  Also, we assume interruptscan occur on any processor at any time, except on a processor that haslocally inhibited them..LPThe problem is the generalisation to a multiprocessor of a familiarand well-understood uniprocessor problem.  It may be reduced to auniprocessor problem by using a global test-and-set to serialise thesleeps and wakeups,which is equivalent to synchronising through a monitor.For performance and cleanliness, however,we prefer to allow the interrupt handling and process control to be multiprocessed..LPOur attempts to solve the sleep/wakeup problem in Plan 9[Pik90]prompted this paper.We implemented solutions several times over several months and eachtime convinced ourselves \(em wrongly \(em they were correct.Multiprocessor algorithms can bedifficult to prove correct by inspection and formal reasoning about themis impractical.  We finally developed an algorithm we trust byverifying our code using anempirical testing tool.We present that code here, along with some comments about the process bywhich it was designed..SHHistory.LPSince processes in Plan 9 and the UNIXsystem have similar structure and properties, one might ask ifUNIX.CW sleepand.CW wakeup[Bac86]could not easily be adapted from their standard uniprocessor implementationto our multiprocessor needs.The short answer is, no..LPTheUNIXroutinestake as argument a single global addressthat serves as a uniqueidentifier to connect the wakeup with the appropriate process or processes.This has several inherent disadvantages.From the point of view of.CW sleepand.CW wakeup ,it is difficult to associate a data structure with an arbitrary address;the routines are unable to maintain a state variable recording thestatus of the event and processes.(The reverse is of course easy \(em we couldrequire the address to point to a special data structure \(embut we are investigatingUNIX.CW sleepand.CW wakeup ,not the code that calls them.)Also, multiple processes sleep `on' a given address, so.CW wakeupmust enable them all, and let process scheduling determine which processactually benefits from the event.This is inefficient;a queueing mechanism would be preferablebut, again, it is difficult to associate a queue with a general address.Moreover, the lack of state means that.CW sleepand.CW wakeupcannot know what the corresponding process (or interrupt) is doing;.CW sleepand.CW wakeupmust be executed atomically.On a uniprocessor it suffices to disable interrupts during theirexecution.On a multiprocessor, however,most processorscan inhibit interrupts only on the current processor,so while a process is executing.CW sleepthe desired interrupt can come and go on another processor.If the wakeup is to be issued by another process, the problem is even harder.Some inter-process mutual exclusion mechanism must be used,which, yet again, is difficult to do without a way to communicate state..LPIn summary, to be useful on a multiprocessor,UNIX.CW sleepand.CW wakeupmust either be made to run atomically on a singleprocessor (such as by using a monitor)or they need a richer model for their communication..SHThe design.LPConsider the case of an interrupt waking up a sleeping process.(The other case, a process awakening a second process, is easier becauseatomicity can be achieved using an interlock.)The sleeping process is waiting for some event to occur, which may bemodeled by a condition coming true.The condition could be just that the event has happened, or somethingmore subtle such as a queue draining below some low-water mark.We represent the condition by a function of oneargument of type.CW void* ;the code supporting the device generating the interruptsprovides such a function to be used by.CW sleepand.CW wakeupto synchronise.  The function returns.CW falseif the event has not occurred, and.CW truesome time after the event has occurred.The.CW sleepand.CW wakeuproutines must, of course, work correctly if theevent occurs while the process is executing.CW sleep ..LPWe assume that a particular call to.CW sleepcorresponds to a particular call to.CW wakeup ,that is,at most one process is asleep waiting for a particular event.This can be guaranteed in the code that calls.CW sleepand.CW wakeupby appropriate interlocks.We also assume for the moment that there will be only one interruptand that it may occur at any time, even before.CW sleephas been called..LPFor performance,we desire that multiple instances of.CW sleepand.CW wakeupmay be running simultaneously on our multiprocessor.For example, a process calling.CW sleepto await a character from an input channel need notwait for another process to finish executing.CW sleepto await a disk block.At a finer level, we would like a process reading from one input channelto be able to execute.CW sleepin parallel with a process reading from another input channel.A standard approach to synchronisation is to interlock the channel `driver'so that only one process may be executing in the channel code at once.This method is clearly inadequate for our purposes; we needfine-grained synchronisation, and in particular to applyinterlocks at the level of individual channels rather than at the levelof the channel driver..LPOur approach is to use an object called a.I rendezvous ,which is a data structure through which.CW sleepand.CW wakeupsynchronise.(The similarly named construct in Ada is a control structure;ours is an unrelated data structure.)A rendezvousis allocated for each active source of events:one for each I/O channel,one for each end of a pipe, and so on.The rendezvous serves as an interlockable structure in which to recordthe state of the sleeping process, so that.CW sleepand.CW wakeupcan communicate if the event happens before or while.CW sleepis executing..LPOur design for.CW sleepis therefore a function.P1void sleep(Rendezvous *r, int (*condition)(void*), void *arg).P2called by the sleeping process.The argument.CW rconnects the call to.CW sleepwith the call to.CW wakeup ,and is part of the data structure for the (say) device.The function.CW conditionis described above;called with argument.CW arg ,it is used by.CW sleepto decide whether the event has occurred..CW Wakeuphas a simpler specification:.P1void wakeup(Rendezvous *r)..P2.CW Wakeupmust be called after the condition has become true..SHAn implementation.LPThe.CW Rendezvousdata type is defined as.P1typedef struct{	Lock	l;	Proc	*p;}Rendezvous;.P2Our.CW Locksare test-and-set spin locks.The routine.CW lock(Lock\ *l)returns when the current process holds that lock;.CW unlock(Lock\ *l)releases the lock..LPHere is our implementation of.CW sleep .Its details are discussed below..CW Thispis a pointer to the current process on the current processor.(Its value differs on each processor.).P1voidsleep(Rendezvous *r, int (*condition)(void*), void *arg){	int s; 	s = inhibit();		/* interrupts */	lock(&r->l); 	/*	 * if condition happened, never mind	 */	if((*condition)(arg)){			unlock(&r->l);		allow();	/* interrupts */		return;	} 	/*	 * now we are committed to	 * change state and call scheduler	 */	if(r->p)		error("double sleep %d %d", r->p->pid, thisp->pid);	thisp->state = Wakeme;	r->p = thisp;	unlock(&r->l);	allow(s);	/* interrupts */	sched();	/* relinquish CPU */}.P2.ne 3iHere is.CW wakeup..P1voidwakeup(Rendezvous *r){	Proc *p;	int s; 	s = inhibit();	/* interrupts; return old state */	lock(&r->l);	p = r->p;	if(p){		r->p = 0;		if(p->state != Wakeme)			panic("wakeup: not Wakeme");		ready(p);	}	unlock(&r->l);	if(s)		allow();}.P2.CW Sleepand.CW wakeupboth begin by disabling interruptsand then locking the rendezvous structure.Because.CW wakeupmay be called in an interrupt routine, the lock must be set onlywith interrupts disabled on the current processor,so that if the interrupt comes during.CW sleepit will occur only on a different processor;if it occurred on the processor executing.CW sleep ,the spin lock in.CW wakeupwould hang forever.At the end of each routine, the lock is released and processor priorityreturned to its previous value..CW Wakeup "" (needs to inhibit interrupts in caseit is being called by a process;this is a no-op if called by an interrupt.).LP.CW Sleepchecks to see if the condition has become true, and returns if so.Otherwise the process posts its name in the rendezvous structure where.CW wakeupmay find it, marks its state as waiting to be awakened(this is for error checking only) and goes to sleep by calling.CW sched() .The manipulation of the rendezvous structure is all done under the lock,and.CW wakeuponly examines it under lock, so atomicity and mutual exclusionare guaranteed..LP.CW Wakeuphas a simpler job.  When it is called, the condition has implicitly become true,so it locks the rendezvous, sees if a process is waiting, and readies it to run..SHDiscussion.LPThe synchronisation technique used hereis similar to known methods, even as far back as Saltzer's thesis[Sal66].The code looks trivially correct in retrospect: all access to data structures is doneunder lock, and there is no place that things may get out of order.Nonetheless, it took us several iterations to arrive at the aboveimplementation, because the things that.I cango wrong are often hard to see.  We had four earlier implementationsthat were examined at great length and only found faulty when a new,different style of device or activity was added to the system..LP.ne 3iHere, for example, is an incorrect implementation of wakeup,closely related to one of our versions..P1voidwakeup(Rendezvous *r){	Proc *p;	int s; 	p = r->p;	if(p){		s = inhibit();		lock(&r->l);		r->p = 0;		if(p->state != Wakeme)			panic("wakeup: not Wakeme");		ready(p);		unlock(&r->l);		if(s)			allow();	}}.P2The mistake is that the reading of.CW r->pmay occur just as the other process calls.CW sleep ,so when the interrupt examines the structure it sees no one to wake up,and the sleeping process misses its wakeup.We wrote the code this way because we reasoned that the fetch.CW p.CW =.CW r->pwas inherently atomic and need not be interlocked.The bug was found by examination when a new, very fast devicewas added to the system and sleeps and interrupts were closely overlapped.However, it was in the system for a couple of months without causing an error..LPHow many errors lurk in our supposedly correct implementation above?We would like a way to guarantee correctness; formal proofs are beyondour abilities when the subtleties of interrupts and multiprocessors areinvolved.With that in mind, the first three authors approached the last to seeif his automated tool for checking protocols[Hol91]could beused to verify our new.CW sleepand.CW wakeupfor correctness.The code was translated into the language for that system(with, unfortunately, no way of proving that the translation is itself correct)and validated by exhaustive simulation..LPThe validator found a bug.Under our assumption that there is only one interrupt, the bug cannotoccur, but in the more general case of multiple interrupts synchronisingthrough the same condition function and rendezvous,the process and interrupt can enter a peculiar state.A process may return from.CW sleepwith the condition function falseif there is a delay betweenthe condition coming true and.CW wakeupbeing called,with the delay occurringjust as the receiving process calls.CW sleep .The condition is now true, so that process returns immediately,does whatever is appropriate, and then (say) decides to call.CW sleepagain.  This time the condition is false, so it goes to sleep.The wakeup process then finds a sleeping process,and wakes it up, but the condition is now false..LPThere is an easy (and verified) solution: at the end of.CW sleepor after.CW sleepreturns,if the condition is false, execute.CW sleepagain.  This re-execution cannot repeat; the second synchronisation is guaranteedto function under the external conditions we are supposing..LPEven though the original code is completelyprotected by interlocks and had been examined carefully by all of usand believed correct, it still had problems.It seems to us that some exhaustive automated analysis isrequired of multiprocessor algorithms to guarantee their safety.Our experience has confirmed that it is almost impossible toguarantee by inspection or simple testing the correctnessof a multiprocessor algorithm.  Testing can demonstrate the presenceof bugs but not their absence[Dij72]..LP

Lines 1–500 of 541. Load more