1CMSC 412 – S03 (lect8)Announcementsz Program #1– Due on Th 9:00 AMz Midterm #1– Thursday of next week (March 6th)z Reading– Chapter 7 (this whole week)2CMSC 412 – S03 (lect8)Synchronization Hardwarez If it’s hard to do synchronization in software, why not do it in hardware?z Disable Interrupts– works, but is not a great idea since important events may be lost.– doesn’t generalize to multi-processorsz test-and-set instruction– one atomic operation• executes without being interrupted– operates on one bit of memory– returns the previous value and sets the bit to one z swap instruction– one atomic operation– swap(a,b) puts the old value of b into a and of a into b3CMSC 412 – S03 (lect8)Using Test and Set for Mutual Exclusionrepeatwhile test-and-set(lock);// critical sectionlock = false;// non-critical sectionuntil false;z bounded waiting time versionrepeatwaiting[i] = true;key = true;while waiting[i] and key key = test-and-set(lock);waiting[i] = false;// critical sectionj = (i + 1) % nwhile (j != i) and (!waiting[j])j = (j + 1) % n;if (j == i)lock = false;elsewaiting[j] = false;// non-critical sectionuntil false;Note: no priority based on wait timeno process waitingrelease process jlook for a waiting processwait until released or no one busy4CMSC 412 – S03 (lect8)Semaphoresz getting critical section problem correct is difficult– harder to generalize to other synchronization problems– Alternative is semaphoresz semaphores– integer variable– only access is through atomic operationsz P (or wait)while s <= 0;s = s - 1;z V (or signal)s = s + 1z Two types of Semaphores– Counting (values range from 0 to n)– Binary (values range from 0 to 1)5CMSC 412 – S03 (lect8)Using Semaphoresz critical sectionrepeatP(mutex);// critical sectionV(mutex);// non-critical sectionuntil false;zRequire that Process 2 begin statement S2 after Process 1 has completed statement S1:semaphore synch = 0;Process 1S1V(synch)Process 2P(synch)S26CMSC 412 – S03 (lect8)Implementing semaphoresz Busy waiting implementationsz Instead of busy waiting, process can block itself– place process into queue associated with semaphore– state of process switched to waiting state– transfer control to CPU scheduler– process gets restarted when some other process executes a signal operations7CMSC 412 – S03 (lect8)Implementing Semaphoresz declarationtype semaphore = recordvalue: integer = 1;L: FIFO list of process;end;z P(S): S.value = S.value -1if S.value < 0 then {add this process to S.Lblock;};z V(S): S.value = S.value+1if S.value <= 0 then {remove process P from S.Lwakeup(P);}Can be neg, if so, indicates how many waitingBounded waiting!!Revised from class :-(8CMSC 412 – S03 (lect8)Readers/Writers Problemz Data area shared by processorsz Some processes read data, others write data– Any number of readers my simultaneously read the data– Only one writer at a time may write – If a writer is writing to the file, no reader may read itz Two of the possible approaches– readers have priority or writers have priority9CMSC 412 – S03 (lect8)Readers have PrioritySemaphore wsem = 1, x = 1;reader(){repeatP(x);readcount = readcount + 1;if readcount = 1 then P (wsem);V(x);READUNIT;P(x);readcount = readcount - 1;if readcount = 0 V(wsem);V(x);forever};writer(){repeatP(wsem);WRITEUNIT;V(wsem)forever}10CMSC 412 – S03 (lect8)Comments on Reader Priorityz semaphores x,wsem are initialized to 1z note that readers have priority - a writer can gain access to the data only if there are no readers (i.e. when readcount is zero, signal(wsem) executes)z possibility of starvation - writers may never gain access to data11CMSC 412 – S03 (lect8)Writers Have PriorityreaderrepeatP(z);P(rsem);P(x);readcount++;if (readcount == 1) then P(wsem);V(x);V(rsem);V(z);readunit;P(x);readcount- -;if readcount == 0 then V (wsem)V(x)foreverwriterrepeatP(y);writecount++:if writecount == 1 then P(rsem);V(y);P(wsem);writeunitV(wsem);P(y);writecount--;if (writecount == 0) then V(rsem);V(y);forever;12CMSC 412 – S03 (lect8)Notes on readers/writers with writers getting priorityP(z);P(rsem);P(x);readcount++;if (readcount==1) then P(wsem);V(x);V(rsem);V(z);readers queue up on semaphorez; this way only a single reader queues on rsem. When a writersignals rsem, only a single reader is allowed throughSemaphores x,y,z,wsem,rsem are initialized to
View Full Document
Unlocking...