1CMSC 412 – S02 (lect 9)Announcementsz Office hours– W office hour will be 10-11 not 11-12 starting this weekz Midterm is next Tuesday– Covers through lecture on Thursdayz Project #2 is available on the web2CMSC 412 – S02 (lect 9)Using Test and Test 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 busy3CMSC 412 – S02 (lect 9)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)4CMSC 412 – S02 (lect 9)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:Process 2S1V(synch)Process 1P(synch)S25CMSC 412 – S02 (lect 9)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 operations6CMSC 412 – S02 (lect 9)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 :-(7CMSC 412 – S02 (lect 9)Readers/Writers Problemz Data area shared by processorsz Some processors read data, other processors can read or 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 priority8CMSC 412 – S02 (lect 9)Readers have Priorityreader(){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}9CMSC 412 – S02 (lect 9)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 data10CMSC 412 – S02 (lect 9)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;11CMSC 412 – S02 (lect 9)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 112CMSC 412 – S02 (lect 9)Deadlocksz System contains finite set of resources– memory space–printer–tape–file– access to non-reentrant codez Process requests resource before using it, must release resource after usez Process is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set13CMSC 412 – S02 (lect 9)Formal Deadlocksz 4 necessary deadlock conditions:– Mutual exclusion - at least one resource must be held in a non-sharable mode, that is, only a single process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource is released– Hold and wait - There must exist a process that is holding at least one resource and is waiting to acquire additional resources that are currently held by other processors14CMSC 412 – S02 (lect 9)Formal Deadlocks– No preemption: Resources cannot be preempted; a resource can be released only voluntarily by the process holding it, after that process has completed its task– Circular wait: There must exist a set {P0,...,Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource held by P2 etc.z Note that these are not sufficient conditions15CMSC 412 – S02 (lect 9)Deadlock Preventionz Ensure that one (or more) of the necessary conditions for deadlock do not holdz Hold and wait– guarantee that when a process requests a resource, it does not hold any other resources– Each process could be allocated all needed resources before beginning execution– Alternately, process might only be allowed to wait for a new resource when it is not currently holding any resource16CMSC 412 – S02 (lect 9)Deadlock Preventionz Mutual exclusion– Sharable resources do not require mutually exclusive access and cannot be involved in a deadlock. z Circular wait– Impose a total ordering on all resource types and make sure that each process claims all resources in increasing order of resource type enumerationz No Premption– virutalize resources and permit them to be prempted. For example, CPU can be
View Full Document
Unlocking...