1CSC 4103 - Operating SystemsFall 2009Tevfik Ko!arLouisiana State UniversitySeptember 22nd, 2009Lecture - IXProcess Synchronization - II2Roadmap• Solutions for Critical-Section Problem• Semaphores• Classic Problems of Synchronization– Bounded Buffer– Readers-Writers– Dining Philosophers– Sleeping BarberMutual Exclusion3critical region1. thread A reaches the gate to the critical region (CR) before B2. thread A enters CR first, preventing B from entering (B is waiting or is blocked)3. thread A exits CR; thread B can now enter4. thread B enters CR!Desired effect: mutual exclusion from the critical regionBABABABAHOW is thisachieved??Mutual Exclusion4!Implementation 1 — disabling hardware interruptscritical regionB1. thread A reaches the gate to the critical region (CR) before B2. as soon as A enters CR, it disables all interrupts, thus B cannot be scheduled 3. as soon as A exits CR, it enables interrupts; B can be scheduled again4. thread B enters CRBABAABAMutual Exclusion5!Implementation 1 — disabling hardware interrupts "#it works, but not reasonable!#what guarantees that the user process is going to ever exit the critical region?#meanwhile, the CPU cannot interleave any other task, even unrelated to this race condition#the critical region becomes one physically indivisible block, not logically#also, this is not working in multi-processors disable hardware interrupts enable hardware interruptsvoid echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}Mutual Exclusion6!Implementation 2 — simple lock variablecritical region1. thread A reaches CR and finds a lock at 0, which means that A can enter2. thread A sets the lock to 1 and enters CR, which prevents B from entering3. thread A exits CR and resets lock to 0; thread B can now enter4. thread B sets the lock to 1 and enters CRBABABABAMutual Exclusion7 test lock, then set lock reset lock!Implementation 2 — simple lock variable#the “lock” is a shared variable#entering the critical region means testing and then setting the lock#exiting means resetting the lockbool lock = FALSE;void echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}while (lock); /* do nothing: loop */lock = TRUE;lock = FALSE;Mutual Exclusion8!Implementation 2 — simple lock variable "1. thread A reaches CR and finds a lock at 0, which means that A can enter1.1 but before A can set the lock to 1, B reaches CR and finds the lock is 0, too1.2 A sets the lock to 1 and enters CR but cannot prevent the fact that . . .1.3 . . . B is going to set the lock to 1 and enter CR, toocritical regionBABABABAMutual Exclusion9 test lock, then set lock reset lock!Implementation 2 — simple lock variable "#suffers from the very flaw we want to avoid: a race condition#the problem comes from the small gap between testing that the lock is off and setting the lock while (lock); lock = TRUE;#it may happen that the other thread gets scheduled exactly in between these two actions (falls in the gap)#so they both find the lock off and then they both set it and enterbool lock = FALSE;void echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}Mutual Exclusion10!Implementation 3 — “indivisible” lock variable $1. thread A reaches CR and finds the lock at 0 and sets it in one shot, then enters1.1’ even if B comes right behind A, it will find that the lock is already at 12. thread A exits CR, then resets lock to 03. thread B finds the lock at 0 and sets it to 1 in one shot, just before entering CRcritical regionBABABABAMutual Exclusion11 test-and-set-lock set lock off!Implementation 3 — “indivisible” lock variable $#the indivisibility of the “test-lock-and-set-lock” operation can be implemented with the hardware instruction TSLvoid echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}TSLTanenbaum, A. S. (2001)Modern Operating Systems (2nd Edition). Mutual Exclusion12!Implementation 3 — “indivisible” lock ! one key $1. thread A reaches CR and finds a key and takes it1.1’ even if B comes right behind A, it will not find a key2. thread A exits CR and puts the key back in place3. thread B finds the key and takes it, just before entering CRcritical regionBABABABAMutual Exclusion13 take key and run return key!Implementation 3 — “indivisible” lock ! one key $#“holding” a unique object, like a key, is an equivalent metaphor for “test-and-set”#this is similar to the “speaker’s baton” in some assemblies: only one person can hold it at a time#holding is an indivisible action: you see it and grab it in one shot#after you are done, you release the object, so another process can hold on to itvoid echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}Mutual Exclusion14!Implementation 4 — no-TSL toggle for two threads1. thread A reaches CR, finds a lock at 0, and enters without changing the lock2. however, the lock has an opposite meaning for B: “off” means do not enter3. only when A exits CR does it change the lock to 1; thread B can now enter4. thread B sets the lock to 1 and enters CR: it will reset it to 0 for A after exitingcritical regionBABABABAMutual Exclusion15 test toggle switch toggle!Implementation 4 — no-TSL toggle for two threads#the “toggle lock” is a shared variable used for strict alternation#here, entering the critical region means only testing the toggle: it must be at 0 for A, and 1 for B#exiting means switching the toggle: A sets it to 1, and B to 0bool toggle = FALSE;void echo(){ char chin, chout; do { chin = getchar(); chout = chin; putchar(chout); } while (...);}toggle = TRUE; toggle = FALSE;while (toggle); /* loop */while (!toggle); /* loop */A’s code B’s codeMutual Exclusion16!Implementation 4 — no-TSL toggle for two threads "5. thread B exits CR and switches the lock back to 0 to allow A to enter next5.1 but scheduling happens to make B faster than A and come back to the gate first5.2 as long as A is still busy or interrupted in its noncritical region, B is barred access to its CR" this violates item 2. of the chart of mutual exclusionBABABA"this implementation