Hệ điều hành - Chapter 5: Concurrency: mutual exclusion and synchronization

Chapter 5Concurrency: Mutual Exclusion and SynchronizationPrincipals of ConcurrencyMutual Exclusion: Hardware SupportSemaphoresReaders/Writers ProblemMultiple ProcessesCentral to the design of modern Operating Systems is managing multiple processesMultiprogrammingMultiprocessingDistributed ProcessingBig Issue is Concurrency Managing the interaction of all of these processesInterleaving and Overlapping ProcessesEarlier (Ch2) we saw that processes may be interleaved on uniprocessorsInterleaving and Overlapping ProcessesAnd not only interleaved but overlapped on multi-processorsBoth interleaving and overlapping present the same problems in concurrent processingOne Difficulty of ConcurrencySharing of global resources can be problematicA Simple Examplevoid echo(){ // send a keyboard-input character to display chin = getchar(); chout = chin; putchar(chout); }What would happen if P1 is interrupted here by P2?Suppose echo is a shared procedure and P1 echoes ‘x’ and P2 echoes ‘y’What would happen if only one process is permitted at a time to be in the procedure?A Simple Example: On a MultiprocessorProcess P1 Process P2 . . chin = getchar(); . . chin = getchar();chout = chin; chout = chin;putchar(chout); . . putchar(chout); . .Enforce Single AccessIf we enforce a rule that only one process may enter the function at a time then:P1 & P2 run on separate processorsP1 enters echo first, P2 tries to enter but is blockedP1 completes executionP2 resumes and executes echoSolution: Control access to shared resourceCompetition among Processes for ResourcesThree main control problems:Need for Mutual ExclusionOnly one program at a time be allowed in its critical section.Critical resource: nonsharable resource, e.g., printerCritical section: portion of the program that uses a critical resourceDeadlockStarvationRequirements for Mutual ExclusionOnly one process at a time is allowed in the critical section for a resourceA process that halts in its noncritical section must do so without interfering with other processesNo deadlock or starvationRequirements for Mutual ExclusionA process must not be delayed access to a critical section when there is no other process using itNo assumptions are made about relative process speeds or number of processesA process remains inside its critical section for a finite time onlyRoadmapPrincipals of ConcurrencyMutual Exclusion: Hardware SupportSemaphoresReaders/Writers ProblemDisabling InterruptsUniprocessors only allow interleavingInterrupt DisablingA process runs until it invokes an operating system service or until it is interruptedDisabling interrupts guarantees mutual exclusion because the critical section cannot be interruptedPseudo-Codewhile (true) {/* disable interrupts */;/* critical section */;/* enable interrupts */;/* remainder */;} Reduced interleaving  Will not work in multiprocessor architectureSpecial MachineInstructionsUse of atomic action: instruction is treated as a single step that cannot be interruptedCompare&Swap Instructionint compare_and_swap (int *word, int testval, int newval){ /* checks a memory location (*word) against a test value (testval) */int oldval;oldval = *word;if (oldval == testval) *word = newval;return oldval;}Mutual Exclusion (fig 5.2)The only process that may enter its critical section is one that finds bolt equal to 0All other processes go into a busy waiting modeHardware Mutual Exclusion: AdvantagesApplicable to any number of processes on either a single processor or multiple processors sharing main memoryIt is simple and therefore easy to verifyIt can be used to support multiple critical sectionsHardware Mutual Exclusion: DisadvantagesBusy-waiting consumes processor timeStarvation is possible when a process leaves a critical section and more than one process is waitingSome process could indefinitely be denied access because selection of a waiting process is arbitrary Deadlock is possibleExample: P1 enters its critical section and is then preempted by higher priority P2 which will go into a busy waiting loopRoadmapPrincipals of ConcurrencyMutual Exclusion: Hardware SupportSemaphoresReaders/Writers ProblemSemaphoreFundamental principle: Processes can cooperate by means of simple signal such that a process can be forced to stop at a specified place until it has received a specific signal.SemaphoreSemaphore: An integer value used for signalling among processesOnly three operations may be performed on a semaphore, all of which are atomic: initialize (to a nonnegative integer value)decrement (semWait), to receive a signalincrement (semSignal), to transmit a signalSemaphore PrimitivesBinary Semaphore PrimitivesStrong/WeakSemaphoreA queue is used to hold processes waiting on the semaphoreIn what order are processes removed from the queue?Strong Semaphores use FIFOWeak Semaphores don’t specify the order of removal from the queueMutual Exclusion Using SemaphoresThe first process that executes a semWait will be able to enter the critical section immediately, setting the value of s to 0Any other processes attempting to enter the critical section will find it busy and will be blockedProcesses Accessing Shared Data UsingSemaphoreThree processes (A,B,C) access a shared resource protected by the semaphore lock.Mutual Exclusion Using SemaphoresThe semaphore can be initialized to a specified value to allow more than one process in its critical section at a times.count  0: the number of processes that can execute semWait(s) without suspensions.count out) before proceedingSemaphoresPrevent the consumer and any other producer from accessing the buffer during the append operationn is equal to the number of items in the bufferThe consumer must wait on both semaphores before proceedingBounded BufferThe buffer is treated as a circular storage; pointer values are expressed modulo the size of the bufferFunctions in a Bounded BufferProducerConsumerwhile (true) { /* produce item v */ while ((in + 1) % n == out) /* do nothing */; b[in] = v; in = (in + 1) % n}while (true) { while (in == out) /* do nothing */; w = b[out]; out = (out + 1) % n; /* consume item w */}in and out are initialized to 0 and n is the size of the bufferSemaphorese keeps track of the number of empty spacesRoadmapPrincipals of ConcurrencyMutual Exclusion: Hardware SupportSemaphoresReaders/Writers ProblemReaders/Writers ProblemA data area (e.g., a file) is shared among many processesSome processes (readers) only read the data area, some (writers) only write to the areaConditions to satisfy:Multiple readers may simultaneously read the file Only one writer at a time may writeIf a writer is writing to the file, no reader may read itReaders have Prioritywsem is used to enforce mutual exclusion: as long as one writer is accessing the shared data area, no other writers and no readers may access itthe first reader that attempts to read should wait on wsemreadcount keeps track of the number of readersx is used to assure that readcount is updated properlyReaders/Writers ProblemOnce a single reader has begun to access the data area, it is possible for readers to retain control of the data area as long as there is at least one reader reading.Therefore, writers are subject to starvationAn alternative solution: no new readers are allowed access to the data area once at least one writer wants to writeWriters have Priorityrsem inhibits all readers while there is at least one writer desiring access to the data areay controls the updating of writecountwritecount controls the setting of rsemWriters have Priorityonly one reader is allowed to queue on rsem, with any additional readers queuing on zWriters have PriorityKey Terms