Operating Systems ECS 251
Popular in Course
Popular in Engineering Computer Science
This 33 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 251 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 54 views. For similar materials see /class/191716/ecs-251-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Operating Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
January 13 2000 1 N E 4 V ECS 251 7 Winter 2000 Page 1 Process Synchronization and Cooperation Parallelism a concurrent vs sequential b logical vs physical concurrency c process creation static vs dynamic Proper nesting a b de nition of proper nesting c precedence grap Precedence relation lt a predecessor process b proces domain range c equivalent systems of processes d determinate system of processes e Bernstein conditions f mutually noninterfering system g Theorem mutually noninterfering systems are determinate h maximally parallel system Basic concurrency language constructs a cobegincoend b forkj oinquit Critical section problems a producer consumer b readers writers rst gives readers priority second gives writers priority c dining philosophers Software solutionss a Dekker s Peterson s b bakery algorithm Hardware solutionss a disable interrupts b test and set Basic language constructs a sem ap ores b sequencers and eventcounters c simultamepus primitives SP S V P ar d send reveive Higherlevel language constructs abstract data types comparison of constructs constraints expressive power ease of use portability process failure In onitors crowd monitors invariant expressions path expressions predicate path expressions CSP RPC ADATM r39r39 m Wop06x Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 2 Improper Nesting Example Introduction One of the limits on the use of parbeginparend and any related constructs is that the program involved must be prop erly nested Not all programs are For example consider the program represented by the following graphs The Program as Graphs precedence graph process ow graph p1 p2 p7 p3 p8 Using forkjoin Primitives The program equivalent to these precedence and process ow graphs is 2 t8 3 Sl fork p2 fork p5 fork p7 quit p2 82 fork p3 fork p4 quit p5 SS join t6 p6 quit p7 S7 join t8 p8 quit p3 S3 join t8 p8 quit p4 S4 join t6 p6 quit p6 S6 join t8 p8 quit p8 SS quit where Si is the program for pi Using parbeginparend Primitives To see if this is possible we must determine if the above program is properly nested If not we clearly cannot repre sent it using parbegin and parend which require a block structure and hence proper nesting Let Sab represent the serial execution of processes a and b and Pab the parallel execution of processes a and I Then a process ow graph is properly nested if it can be described by P S and functional composition For example the program Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 3 parbegin pl 3 b 1 p2 C d l parend p3 e a 0 would be written as SPp1p2p3 We now prove Claim The example is not properly nested Proof For something to be properly nested it must be of the form Spipj or Ppify39 at the most interior level Clearly the example39s most interior level is not Ppipj as there are no constructs of that form in the graph In the graph all serially connected processes pi and pj have at least 1 more process pk starting or nishing at the node nij between pi and pf but if Spipj is in the innermost level there can be no such pk else a more interior P or S is needed contradiction Hence it39s not Spipj either Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 4 Maximally Parallel Systems Introduction A maximally parallel system is a determinate system for which the removal of any pair from the precedence relation lt makes the two processes in the pair interfering processes Example The system S lt is composed of the set of processes H p1 p9 and the precedence relation lt P1gtP2gt O71gtP3gt P1gtP4gt P2gtP5gt O73gtP5gt P4gtP6gt P4gtP7gt 074178 P5178 176178 O77gtP9gt P8179 The processes have the following domains and ranges Process P1 P2 P3 P4 P5 P6 P7 P8 P9 domain 1 4 3 1 3 6 5 13 146 range 23 4 23 1 3 6 5 4 23 Transitive closure of lt 1n the following a bullet is placed whenever the process in the row precedes the process in the column under lt P1 P2 P3 P4 P5 P6 P7 P8 P9 71 P2 P3 4 P5 P6 P7 P8 Forpl we have p1ltp2 andpz ltp5 sopl ltp5 As 75 ltp8 p1 ltp8 As 78 ltp9 p1 ltp9 The table becomes P1 P2 P3 P4 P5 P6 P7 P8 P9 71 P2 P3 74 P5 P6 P7 P8 Continuing on in this fashion the table nally becomes P1 P2 P3 P4 P5 P6 P7 P8 P9 1 p2 p3 p4 P5 P6 P7 P8 giving the transitive closure of lt to be lt P1gtP2gt P1gtP3gt P1gtP4gt P1gtP5gt P1gtP6gt P1gtP7gt P1gtP8gt P1gtP9gt P2gtP5gt Q72gtP8gt P2gtP9gt P3gtP5gt Q73gtP8gt P3gtP9gt P4gtP6gt P4gtP7gt P4178 P4gtP9gt P5178 P5gtP9gt 176178 P6gtP9gt O77gtP9gt P8179 Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 5 Bernstein Conditions For the system to be determinate the Bernstein conditions must hold This means that two processes which write into the same memory location cannot be executed concurrently Also if a process reads from a location that another pro cess writes to those two processes cannot be concurrent So we rst list those processes which cannot be concurrent by computing the elements of the three sets listed below Note that the range of pl is the set of memory locations that pl writes to and the domain of pl is the set of memory locations that pl reads from rangdpz rangdp 071173 171175 171179 172178 173175 P3179 P5179 domainm 0 range 071174 172178 173175 173179 P5179 P8179 rangdpz n domaanvj 071173 171175 171178 172179 173175 173178 174178 174179 175178 P5179 The EquivalenlMaximalbI Parallel System The only precedences that are actually required by the system are those that enforce the Bernstein conditions The complete set of precedences that ex1st 1n the system is given by the set lt so taking those elements of lt in the three sets above gives us the precedence relation lt l for the maximally parallel system equivalent to the original system lt 171173 071174 171175 171178 071179 172178 172179 073175 173178 173179 174178 174179 175178 175179 P5179 P8179 Now note that several of these elements are implied by others since precedence is transitive39 for example 171174 and 174178 means 071178 holds Eliminating these redundent precedences this set becomes 171173 171174 072178 173175 174178 075178 P5179 P8179 Last modified at 1001 am on Thursday January 13 2000 January 13 2000 Introduction ECS 251 7 Winter 2000 Page 6 Bakery Algorithm This algorithm solves the critical section problem for n processes in software The basic idea is that of a bakery cus tomers take numbers and whoever has the lowest number gets service next Here of course service means entry to the critical section Algorithm 1 var Comments lines l2 lines 46 lines 712 line 14 choosing shared array 0n l of boolean number shared array 0n l of integer repeat choosingi true numberi maxnumber0numberlmnumbern l l choosingi false for j O to n l do begin while choosingj do nothing while numberj ltgt 0 and numberj nothing j lt numberii do end critical section numberi O remainder section until false Here choosing i is true if P is choosing a number The number that P will use to enter the critical section is in number i 39 it is 0 if P is not trying to enter its critical section These three lines rst indicate that the process is choosing a number line 4 then try to assign a unique number to the process P line 5 however that does not always happen Afterwards P indicates it is done line 6 Now we select which process goes into the critical section P waits until it has the lowest number of all the processes waiting to enter the critical section If two processes have the same number the one with the smaller name 7 the value of the subscript 7 goes in39 the notation ab lt cd means true ifa lt c or if both a c and b lt d lines 910 Note that if a process is not trying to enter the critical section its number is 0 Also if a process is choosing a number when P tries to look at it P waits until it has done so before looking line 8 Now P is no longer interested in entering its critical section so it sets number i to 0 Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 7 Bogus Bakery Algorithm Introduction Why does Lamport s Bakery algorithm used a variable called choosing see the algorithm lines 1 4 6 and 8 It is very instructive to see what happens if you leave it out This gives an example of mutual exclusion being violated if you don39t put choosing in But rst the algorithm with the lines involving choosing commented out so you can see what the modi cation was Algorithm 1 var choosing shared array 0n l of boolean 2 number shared array 0n l of integer 3 repeat 4 choosingi true 5 numberi maxnumber0numberl numbern l l 6 choosingi false 7 for j O to n l do begin 8 while choosingj do 9 while numberj ltgt 0 and 10 numberj j lt numberii do 11 nothing 12 end 13 critical section 14 numberi O 15 remainder section 16 until false Proof of Violation of Mutual Exclusion Suppose we have two processes just beginning call them p0 and p1 Both reach line 5 at the same time Now we39ll assume both read number O and number 1 before either addition takes place Let p1 complete the line assigning 1 to number l but p0 block before the assignment Then p1 gets through the whi 1e loop at lines 911 and enters the critical section While in the critical section it blocks p0 unblocks and assigns 1 to number O at line 5 1t proceeds to the while loop at lines 911 When it goes through that loop for j 1 the condition on line 9 is true Further the condition on line 10 is false so p0 enters the critical section Now p0 and p1 are both in the critical section viuolating mutual exclusion The reason for choosing is to prevent the whi 1e loop in lines 911 from being entered when process j is setting its number j Note that if the loop is entered and then process j reaches line 5 one of two situations arises Either number j has the value 0 when the rst test is executed in which case process 1 moves on to the next process or number j has a nonzero value in which case at some point number j will be greater than number i since process 1 nished executing statement 5 before process j began Either way process 1 will enter the critical section before process j and when process j reaches the while loop it will loop at least until process 1 leaves the critical section Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 8 Test and Set Solution Introduction This algorithm solves the critical section problem for n processes using a Test and Set instruction called TaS here This instruction does the following function atomically unction TaSvar Lock boolean boolean begin TaS Lock Lock true end Algorithm 1 var waiting shared array 0n l of boolean 2 Lock shared boolean 3 O 111 4 key boolean 5 repeat process Pi 6 waitingi true 7 key true 8 while waitingi and key do 9 key TaSLock 10 waitingi false 11 critical section goes here 12 jilmodn 13 while j ltgt i and not waitingj do 14 jjlmodn 15 if j i then 16 Lock 2 false 17 else 18 waitingj false 19 until false Comments lines 12 These are global to all processes and are all initialized to false lines 34 These are local to each process P and are uninitialized lines 510 This is the entry section Basically waitingi is true as long as P is trying to get into its critical section if any other process is in that section then Lock will also be true and P will loop in lines 89 Once P can go on it is no longer waiting for permission to enter and sets wait ing i to false line 10 it then proceeds into the critical section Note that Lock is set to true by the TaS instruction in line 9 that returns false lines 1218 This is the exit section When P leaves the critical section it must choose which other waiting pro cess may enter next It starts with the process with the next higher index line 12 1t checks each process to see if that process is waiting for access lines 1314 if noone is it simply releases the lock by setting Lock to false lines 1516 However if some other process Pj is waiting for entry P simply shanges wai ting j to false to allow Pj to enter the critical section lines 17 Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 9 Classical Synchronization Problems Introduction This handout states three classical synchronization problems that are often used to compare language constructs that implement synchronization mechanisms and critical sections The Producer Consumer Problem In this problem two processes one called the producer and the other called the consumer run concurrently and share a common buffer The producer generates items that it must pass to the consumer who is to consume them The pro ducer passes items to the consumer through the buffer However the producer must be certain that it does not deposit an item into the buffer when the buffer is full and the consumer must not extract an item from an empty buffer The two processes also must not access the buffer at the same time for if the consumer tries to extract an item from the slot into which the producer is depositing an item the consumer might get only part of the item Any solution to this problem must ensure none of the above three events occur A practical example of this problem is electronic mail The process you use to send the mail must not insert the letter into a full mailbox otherwise the recipient will never see it similarly the recipient must not read a letter from an empty mailbox or he might obtain something meaningless but that looks like a letter Also the sender producer must not deposit a letter in the mailbox at the same time the recipient extracts a letter from the mailbox otherwise the state of the mailbox will be uncertain Because the buffer has a maximum size this problem is often called the bounded bu er problem A less common variant of it is the unbounded buffer problem which assumes the buffer is in nite This eliminates the problem of the producer having to worry about the buffer lling up but the other two concerns must be dealt with The Readers Writers Problem In this problem a number of concurrent processes require access to some object such as a le Some processes extract information from the object and are called readers others change or insert information in the object and are called writers The Bernstein conditions state that many readers may access the object concurrently but if a writer is accessing the object no other processes readers or writers may access the object There are two possible policies for doing is FiriseadersWn39lers Problem Readers have priority over writers that is unless a writer has permission to access the object any reader requesting access to the object will get it Note this may result in a writer waiting inde nitely to access the object SecondReaders Wrilers Problem Writers have priority over readers that is when a writer wishes to access the object only readers which have already obtained permission to access the object are allowed to complete their access any readers that request access after the writer has done so must wait until the writer is done Note this may result in readers waiting inde nitely to access the object So there are two concerns rst enforce the Bernstein conditions among the processes and secondly enforcing the appropriate policy of whether the readers or the writers have priority A typical example of this occurs with databases when several processes are accessing data some will want only to read the data others to change it The database must implement some mechanism that solves the readerswriters problem The Dining Philosophers Problem In this problem ve philosophers sit around a circular table eating spaghetti and thinking In front of each philoso pher is a plate and to the left of each plate is a fork so there are ve forks one to the right and one to the left of each philosopher39s plate see the gure When a philosopher wishes to eat he picks up the forks to the right and to the left of his plate When done he puts both forks back on the table The problem is to ensure that no philosopher will be allowed to starve because he cannot ever pick up both forks There are two issues here rst deadlock where each philosopher picks up one fork so none can get the second must never occur and second no set of philosophers should be able to act to prevent another philosopher from ever eating Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 10 A solution must prevent both 092 6 t0 Figure The Dining Philosopher39s Table Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 11 ProducerConsumer Problem Introduction This algorithm uses semaphores to solve the producerconsum er or bounded buffer problem Algorithm 1 var buffer array 0n 1 of item 2 full empty mutex semaphore 3 nextp nextc item 4 begin 5 full O 6 empty 7 mutex 1 8 parbegin 9 repeat producer process 10 produce an item in nextp 11 down empty 12 down mutex 13 deposit nextp in buffer 14 up mutex 15 up full 16 until false 17 repeat consumer process 18 down full 19 down mutex 2O extract an item in nextc 2 1 up mu t ex 22 upempty i 23 consume the item in nextc 24 until false 25 parend 26 end Comments lines l3 Here buffer is the shared buffer and contains 11 spaces full is a semaphore the value of which is the number of lled slots in the buffer empty is a semaphore the value of which is the number of emoty slots in the buffer and mutex is a semaphore used to enforce mutual exclusion so only one process can access the buffer at a time nextp and nextc are the items produced by the pro ducer and consumed by the consumer respectively line 57 This just initializes all the semaphores It is the only time anything other than a down or an up operation may be done to them line 10 Since the buffer is not accessed while the item is produced we don39t need to put semaphores around this part lines 1113 Depositing an item into the buffer however does require that the producer process obtain exclusive access to the buffer First the producer checks that there is an empty slot in the buffer for the new item and if not waits until there is down empty When there is it waits until it can obtain exclusive access to the buffer down mutex Once both these conditions are met it can safely deposit the item lines 1415 As the producer is done with the buffer it signals that any other process needing to access the buffer may do so up mutex It then indicates it has put another item into the buffer up full Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 12 lines 1820 Extracting an item from the buffer however does require that the consumer process obtain exclu sive access to the buffer First the consumer checks that there is a slot in the buffer with an item deposited and if not waits until there is down full When there is it waits until it can obtain exclusive access to the buffer down mutex Once both these conditions are met it can safely extract the item lines 2122 As the consumer is done with the buffer it signals that any other process needing to access the buffer may do so upmutex It then indicates it has extracted another item into the buffer up empty line 23 Since the buffer is not accessed while the item is consumed we don39t need to put semaphores around this part Last modified at 1001 am on Thursday January 13 2000 January 13 2000 Introduction ECS 251 7 Winter 2000 Page 13 First Readers Writers Problem This algorithm uses semaphores to solve the rst readerswriters problem Algorithm 1 var wrt mutex semaphore 2 readcount integer 3 begin 4 readcount O 5 wrt l 6 mutex 1 7 parbegin 8 repeat reader process 9 do something 10 down mutex 11 readcount readcount 1 12 i f readcount 1 then 13 down wrt 14 up mutex 15 read the file 16 down mutex 17 readcount readcount 1 18 i f readcount 0 then 19 up wrt 2 0 up mu t ex 21 do something else 22 until false 23 repeat writer process 24 do something 25 down wrt 26 write to the file 27 up wrt i 28 do something else 29 until false 3 O parend 3 1 end Comments lines l2 Here readcount contains the number of processes reading the le and mutex is a semaphore used to provide mutual exclusion when quot is 39 or The sema phore wrt is comm on to both readers and writers and ensures that when one writer is accessing the le no other readers or writers may do so lines 46 This just initializes all the semaphores It is the only time anything other than a down or an up operation may be done to them As no readers are yet reading the le readcount is initialized to 0 line 9 Since the le is not accessed here we don39t need to put semaphores around this part lines 1015 Since the value of the shared variable readcount is going to be changed the process must wait until noone else is accessing it down mutex Since this process will read from the le Last modified at 1001 am on Thursday January 13 2000 January 13 2000 lines 1620 line 24 lines 2526 line 27 ECS 251 7 Winter 2000 Page 14 readcount is incremented by 139 if this is the only reader that will access the le it waits until any writers have nished down wrt It then indicates other processes may access readcount down mutex and proceeds to read from the le Now the reader is done reading the le for now It must update the value of readcount to indi cate this so it waits until noone else is accessing that variable down mutex and then decre ments readcount If no other readers are waiting to read readcount 0 it signals that any reader or writer who wishes to access the le may do so up wrt Finally it indicates it is done with readcoun t up mu t ex Since the le is not accessed here we don39t need to put semaphores around this part The writer process waits down wrt until no other process is accessing the le39 it then proceeds to write to the le When the writer is done writing to the le it signals that anyone who wishes to access the le may do so up wrt Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 15 First ReadersWriters Problem Introduction This algorithm uses SP and S V to solve the rst readerswriters problem Algorithm 1 var mutex semaphore 2 readcount integer 3 begin 4 readcount NREADERS 5 mutex 1 6 parbegin 7 repeat reader process 8 do something 9 SPreadcount 1 1 10 SPmutex 1 O 11 read the file 12 SVreadcount 1 13 do something else 14 until false 15 repeat writer process 16 do something 17 SPmutex 1 1 readcount NREADERS O 18 write to the file 19 SVmutex 1 2O do something else 21 until false 22 parend 23 end Comments lines l2 Here readcounl contains the number of processes not currently reading or trying to read the le and mulex is a semaphore used to provide mutual exclusion when the le is being written lines 35 This just initializes all the semaphores It is the only time anything other than a P or a Voperation may be done to them As no readers are yet trying to read the le readcounl is initialized to the number of reader processes the constant NREADERS lines 78 This rst repeat loop contains the code for a reader process Since the le is not accessed here we don39t need to put semaphores around this part lines 911 First we atomically decrement readcounl by 1 since a process is trying to read the le We then check that no writers are writing to the le by testing mutex Note the value of mutex is not changed line 12 Now the reader is done reading the le for now It signals that one less reader is trying to read the le by incrementing readcount by 1 lines 1516 This second repeat loop contains the code for a writer process Since the le is not accessed here we don39t need to put semaphores around this part lines 1718 The writer process waits until two conditions are met simultaneously no other writers are access ing the le so mulex is 1 or false and no readers are access1ng the le so readcounl is NREAD ERS It then atomically sets mulex to 0 or true indicating a writer process is accessing the le but does not change readcount Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 16 line 19 When the writer is done writing to the le it signals that anyone who Wishes to access the le may do so by making mulex l or false Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 17 General Priority Problem Introduction This uses SP and SVto solve the general priority problem in which many different processes each with a different priority is attempting to gain access to a resource Algorithm 1 var resource Semaphore prisem array 1 NUMPROCS of semaphore 3 begin 4 resource 2 1 5 fori 1 i lt NUMPROCS i 6 prisemi 1 7 repeat the numproc th process 8 do something 9 SPprisemnumproc 1 1 10 SPresource 1 1 11 prisem O 1 0 prisem numproc 1 1 O 12 access the resource 13 SVresource 1 prisem numproc 1 14 do something else 15 until false 16 17 end Comments lines l2 Here resource is 1 when the resource is not being used and prisemi is 1 when process 139 does not want access to the resource We assume that the lower the index into prisem the higher the process priority lines 36 This just initializes all the semaphores It is the only time anything other than an SP or an SV oper ation may be done to them As the resource is not yet assigned resource is set to 1 false as no process wants access to it each semaphores prisem i are also set to 1 false lines 7 on A liberty with notation now this loop is replicated in each process We will assume that the vari able procno contains the number of the current process that is the index into prisem line 8 Since the resource is not accessed here we don39t need to put semaphores around this part lines 912 First we atomically decrement prisem numproc by 1 to indicate that this process wishes to gain access to the resource We then check atomically and simultaneously that no other process has access and that no process with a higher priority is waiting for access If these are both true access to the resource is granted so resource is set to 0 false and the process proceeds line 13 Now the process is done accessing the resource for now It signals that by setting both resource and the appropriate element of the semaphore array to 1 false Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 sendreceive Chart Introduction These charts summarize the actions of the send and receive primitives using both blocking and nonblocking mode and explicit and implicit naming Charts This chart summarizes how naming and blocking affects the send primitive send blocking nanblocking explicit send message to receiver wait until message send message to receiver naming accepted implicit broadcast message wait until all processes broadcast message naming accept message This chart summarizes how naming and blocking affects the receive primitive receive blocking nanblocking explicit wait for message from named sender if there is a message from the named sender naming get it39 otherwise procee implicit wait for message from any sender if there is a message from any sender get it39 naming otherwise proceed Last modified at 1001 am on Thursday January 13 2000 Page 18 January 13 2000 ECS 251 7 Winter 2000 Page 19 Producer Consumer Problem Introduction This algorithm uses blocking send and receive primitives to solve the producerconsumer or boundedbuffer prob lem In this solution the buffer size depends on the capacity of the link Algorithm 1 var nextp nextc item 2 procedure producer 3 begin 4 while true do begin 5 produce item in nextp 6 send Consumerprocess nextp 7 end 8 end 9 procedure consumer 10 begin 11 while true do begin 12 receive Producerprocess nextc 13 consume item in nextc H 14 end 15 end 16 begin 17 parbegin 18 Consumerprocess consumer 19 Producerprocess producer 2O parend 21 end Comments line 1 Here nextp is the item the consumer produces and nextc the item that the consumer con sumes lines 28 This procedure simply generates items and sends them to the consumer process named Consum erprocess Suppose the capacity of the link is n items If n items are waiting to be consumed and the producer tries to send the nlst item the producer will block suspend until the consumer has removed one item from the link ie done a receive on the producer process Note the name of the consumer process is given explicitly so this is an example of explicit naming or direct communication Also since the send is blocking it ias an example of synchronous communica tion lines 915 This code simply receives items from the producer process named Producerprocess and consumes them If when the receive statement is executed there are no items in the link the con sumer will block suspend until the producer has put an item from the link ie done a send to the consumer process Note the name of the producer process is given explicitly again this is an example of explicit naming or direct communication Also since the receive is blocking it is an example of synchronous communication lines 1720 This starts two concurrent processes the I L and the L Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 20 Producer Consumer Problem Introduction This algorithm uses a monitor to solve the producerconsum er or boundedbuffer problem Algorithm 1 buffer monitor 2 var slots array 0 n 1 of item 3 count in out integer 4 notempty notfull condition 5 procedure entry deposit data item 6 begin 7 i 5 count n then 8 notfullwait 9 slotsin data 10 in in1modn 11 count 2 count 1 12 notempty signal 13 end 14 procedure entry extractvar data item 15 begin 16 i 5 count 0 then 17 notempty wait 18 data 2 slots out 19 out 2 out 1 mod n 20 count 2 count 1 21 notfullsigna1 22 end 23 begin 24 count O in 0 out O 25 end Comments lines 24 Here slots is the actual buffer count the number of items in the buffer and in and out the indices of the next element of slots where a deposit is to be made or from which an extraction is to be made There are two conditions we care about if the buffer is not full represented by the condition variable notfull and if the buffer is not empty represented by the condition variable not empty line 5 The keyword entry means that this procedure may be called from outside the monitor It is called by placing the name of the monitor rst then a period then the function name so buffer deposit lines 78 This code checks to see if there is room in the buffer for a new item If not the process blocks on the condition notfull39 when some other process does extract an element from the buffer then there will be room and that process will signal on the condition notfull allowing the blocked one to proceed Note that while blocked on this condition other processes may access procedures within the monitor lines 911 This code actually deposits the item into the buffer Note that the monitor guarantees mutual exclu sion line 12 Just as a producer will block on a full buffer a consumer will block on an empty one This indi cates to any such consumer process that the buffer is no longer empty and unblocks exactly one of Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 21 them If there are no blocked consumers this is effectively a noop line 14 As with the previous procedure this is called from outside the monitor by buffer extract lines 1617 This code checks to see if there is any unconsumed item in the buffer If not the process blocks on the condition notempt y when some other process does deposit an element in the buffer then there Will be something for the consumer to extract and that producer process Will signal on the condition notempt y allowing the blocked one to proceed Note that While blocked on this condi tion other processes may access procedures Within the monitor lines 1820 This code actually extracts the item from the buffer Note that the monitor guarantees mutual exclusion line 21 Just as a consumer will block on an empty buffer a producer Will block on a full one This indi cates to any such producer process that the buffer is no longer full and unblocks exactly one of them If there are no blocked producers this is effectively a noop lines 2325 This is the initialization part Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 22 First Readers Writers Problem Introduction This algorithm uses a monitor to solve the rst readerswriters problem Algorithm 1 readerwriter monitor 2 var readcount integer 3 writing boolean 4 oktoread oktowrite condition 5 procedure entry beginread 6 begin 7 readcount readcount 1 8 if writing then 9 oktoreadwait 10 end 11 procedure entry endread 12 begin 13 readcount readcount 1 14 if readcount 0 then 15 oktowritesignal 16 end 17 procedure entry beginwrite 18 begin 19 if readcount gt O or writing then 20 oktowritewait 21 writing 2 true 22 end 23 procedure entry endwrite 24 var i integer 25 begin 26 writing 2 false 27 if readcount gt 0 then 28 for i 1 to readcount 29 oktoreadsignal 30 else 31 oktowritesignal 32 end 33 begin 34 readcount 0 writing 2 false 35 end Comments lines l4 Here readcount contains the number of processes reading the le and wri ting is true when a writer is writing to the le Oktoread and oktowrite correspond to the logical conditions of being able to access the le for reading and writing respectively lines 79 In this routine the reader announces that it is ready to read by adding 1 to readcoun t If a writer is accessing the le it blocks on the condition variable oktoread39 when done the writer will signal on that condition variable and the reader can proceed lines 1315 In this routine the reader announces that it is done by subtracting 1 from readcoun t If no Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 23 more readers are reading it indicates a writer may go ahead by signalling on the condition variable oktowri ts lines 1921 In this routine the writer rst sees if any readers or writers are accessing the le if so it waits until they are done Then it indicates that it is writing to the le by setting the boolean writing to true lines 2631 Here the writer rst announces it is done by setting writing to false Since readers have pri ority it then checks to see if any readers are waiting if so it signals all of them as many readers can access the le simultaneously If not it signals any writers waiting line 34 This initializes the variables Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 24 Monitors and Semaphores Introduction This handout describes how to express monitors in terms of semaphores If an operating system provided semaphores as primitives this is what a compiler would produce when presented with a monitor Algorithm 1 var mutex urgent xcond semaphore 2 rgentcount xcondcount integer The body of each procedure in the monitor is set up like this down xmutex procedure body 5 i f urgentcount gt 0 then 6 up urgent 7 e lse 8 up mutex Each x wait within the procedure is replaced by 9 xcondcount xcondcount 1 10 i f urgentcount gt 0 then 11 up urgent 12 e lse 13 up mutex 14 down xcond 15 xcondcount xcondcount 1 Each x signal within the procedure is replaced by 16 urgentcount urgentcount 1 17 i f xcondcount gt 0 then begin 18 up xcondsem 19 down urgent 2 0 end 21 urgentcount urgentcount 1 Comments line 1 The semaphore mutex is initialized to 1 and ensures that only one process at a time is executing within the monitor The semaphore urgent is used to enforce the requirement that processes that signal and as a result are suspended are to be restarted before any new process enters the mon itor The semaphore xcond will be used to block processes doing waits on the condition variable x Note that if there is more than one such condition variable a corresponding semaphore for each condition variable must be generated Both urgent and xcond are initialized to 0 line 2 The integer urgentcount indicates how many processes are suspended as a result of a signal operation and are therefore waiting on the semaphore urgent the counter xcondcount is associated with the condition variable x and indicates how many processes are suspended on that condition ie suspended on the semaphore xcond lines 38 Since only one process at a time may be in the monitor the process entering the monitor procedure must wait until no other process is using it down mutex On exit the process signals others that they may attempt entry using the following order if any other process has issues a signal and been suspended ie urgentcount 7 O the exiting process indicates that one of those is to be continued up urgent Otherwise one of the processes trying to enter the monitor may do so up mutex lines 915 First the process indicates it will be executing an x wait by adding 1 to xcondcount It then Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 25 signals some other process that that process may proceed using the same priority as above It sus pends on the semaphore xcond When restarted it indicates it is done with the x wait by sub tracting 1 from xcondcount and proceeds Note that the down xcond will always suspend the process since unlike semaphores if no process is suspended on x wait then x signal is ignored So when this is executed the value of the semaphore xcond is always 0 lines 1621 First the process indicates it will be executing an x signal by adding 1 to urgentcount It then checks if any process is waiting on condition variable x xcondcount gt O and if so signals any such process up xcondsem before suspending itself down urgent When restarted the process indicates it is no longer suspended by subtracting 1 from urgentcoun t Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 26 Monitors and Priority Waits Introduction This is an example of a monitor using priority waits It implements a simple alarm clock39 that is a process calls alarmclock wakeme n and suspends for n seconds Note that we are assuming the hardware invokes the pro cedure tick to update the clock every secon Algorithm 1 alarmclock monitor 2 var now integer 3 wakeup condition 4 procedure entry wakemen integer 5 begin 6 alarmsetting 2 now n 7 while now lt alarmsetting do 8 wakeupwaitalarmsetting 9 wakeupsignal 10 end 11 procedure entry tick 12 begin 13 now 2 now 1 l4 wakeupsignal 15 end Comments lines 23 Here now is the current time in seconds and is updated once a second by the procedure tick When a process suspends it will do a wait on the condition wakeup line 6 This computes the time at which the process is to be awakened lines 78 The process now checks that it is to be awakened later and then suspends itself line 9 Once a process has been woken up it signals the process that is to resume next That process checks to see if it is time to wake up39 if not it suspends again hence the while loop above rather than an i 5 statement If it is to wake up it signals the next process line 14 This is done once a second hence the addition of l to now The processes to be woken up are queued in order of remaining time to wait with the next one to wake up rst So when tick sig nals the next one to wake up determines if it is in fact time to wake up If not it suspends itself if so it proceeds Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 27 First Readers Writers Problem Introduction This uses crowd monitors to solve the rst readerswriters problem Algorithm 1 readerwriter crowd monitor 2 var Readers crowd read 3 Writers crowd read write 4 readcount integer 5 writing boolean 6 oktoread oktowrite condition 7 guard procedure entry beginread 8 begin 9 readcount readcount 1 10 if writing then 11 oktoreadwait 12 enter Readers 13 end 14 guard procedure entry endread 15 begin 16 leave Readers 17 readcount readcount 1 18 if readcount 0 then 19 oktowritesignal 20 end 21 guard procedure entry beginwrite 22 begin 23 if readcount gt O or writing then 24 oktowritewait 25 writing 2 true 26 enter Writers 27 end 28 guard procedure entry endwrite 29 var i integer 3O begin 31 leave Writers 32 writing 2 false 33 if readcount gt 0 then 34 for i 1 to readcount 35 oktoreadsignal 36 else 37 oktowritesignal 38 end 39 procedure entry read 40 read from shared data m 41 end 42 procedure entry write 43 write to shared data m 44 end 45 begin 46 readcount 0 writing 2 false Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 28 4 7 end Comments lines 23 These lines de ne which procedures can be called by members of the crowd here members of the Readers crowd can call read and members of the Writers crowd can call either read or write Only processes in those crowds can call read or write should any other process do so it will cause a run time error line 7 The keyword guard means this procedure is mutually exclusive so only one process at a time may be in the guarded procedures Note this relaxes the de nition of Hoare s monitor in that multiple proceses may now access the monitor simultaneously line 12 This puts the calling process into the Readers crowd39 it may now call the procedure read line 16 This removes the calling process from the Readers crowd so it may not call read until after it calls beginread and executes line 12 again line 26 This puts the calling process into the Writers crowd39 it may now call the procedures read and write line 31 This removes the calling process from the Readers crowd so it may not call read or write until after it calls beginread or beginwrite and executes lines 12 or 26 again line 39 Now any number of processes may access the read procedure simultaneously line 42 Although it may appear that any number of processes may access the write procedure simulta neously note that all ca11ers must rst have invoked beginwrite i and only one such process will be active at a time So at most one process will call write Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 29 Producer Consumer Problem Introduction This uses invariant expressions to solve the producer consumer problem Algorithm 1 buffer invariant module 2 const n 1024 3 var slots array 0n 1 of item 4 in out On 1 5 invariant deposit 6 StartCountdeposit FinishCountextract lt n 7 CurrentCountdeposit O 8 invariant extract 9 StartCountextract FinishCountdeposit lt O 10 CurrentCountextract O 11 procedure entry depositdata item 12 begin 13 slotsin data 14 in in 1 mod n 15 end 16 procedure entry extractvar data item 17 begin 18 data slotsout 19 out 2 out 1 mod n 20 end 21 begin 22 in 0 out O 23 end Comments lines 34 Here slots is the actual buffer and in and out the indices of the next element of slots Where a deposit is to be made or from which an extraction is to be made line 5 The next constraints apply to the procedure deposit line 6 This invariant checks that there is at least one slot in the buffer that is empty If false then deposit must have been started at least n times more than extract nishe line 7 This ensures at most one process can be in deposit at a time mutual exclusion line 8 The next constraints apply to the procedure extract line 6 This invariant checks that there is at least one slot in the buffer that is full If so then deposit n ished more times than extract started line 7 This ensures at most one process can be in extract at a time mutual exclusion line 11 As with the previous procedure this is called from outside the monitor by bu erextract lines 121 5 This code actually extracts the item from the buffer Note that the invariant guarantees mutual exclusion lines 2325 This is the initialization part Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 30 First Readers Writers Problem Introduction This uses invariant expressions to solve the rst readers writers problem Algorithm 1 readerwriter invariant module 2 invariant read 3 CurrentCountwrite O 4 invariant write 5 CurrentCountwrite CurrentCountread O 6 procedure entry read 7 read from shared data m 8 end 9 procedure entry write 10 write to shared data m 11 end 12 begin 13 end Comments lines 23 This states the condition that must hold whenever the procedure read is executed it requires that no processes be executing write Note this means readers will have priority over writers when a reader is presently reading it says nothing about what happens if a reader and a writer call the module at the sam e tim e lines 45 This states the condition that must hold whenever the procedure write is executed it requires that no processes be executing either read or write lines 611 Here the routines simply do the reading and writing lines 1213 The initialization part of the module as there are no variables in it this part is empty Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 31 Producer Consumer Problem Introduction This algorithm uses open path expressions in the form of Path Pascal to solve the producerconsum er problem Algorithm 1 type buffer object 2 path 11 12 deposit 1 extract end 3 var slots array 0 n l of item 4 in out integer 5 procedure entry depositdata item 6 begin 7 slotsin data 8 i112 inlmodn 9 end 10 procedure entry extractvar data item 11 begin 12 data slotsout 13 out 2 out 1 mod n 14 end 15 begin 16 in 0 out 0 17 end Comments lines l2 This construct says that at most one invocation of deposit or one invocation of extract can run con currently 1 that for every call to extract at least one call to deposit must have returned and that the difference between the number of calls to deposit and the number of calls to extract must never be more an n lines 34 Here slots is the actual buffer and in and out the indices of the next element of slots Where a deposit is to be made or from which an extraction is to be made Note that we need not keep track of how many slots of the buffer contain som ething39 the path constraint above ensures that neither an extraction from an empty buffer nor insertion into a full buffer Will ever take place line 5 This function is called by placing the name of the object rst then a period then the function name so bu erdeposit lines 78 This code actually deposits the item into the buffer Note that the path expression guarantees mutual exclusion line 10 Again this is called by bu erextract line 14 This code actually extracts the item from the buffer Againthe path expression guarantees mutual exclusion Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 32 Producer Consumer Process Introduction This uses Hoare s CSP language to solve the producer consumer problem Algorithm This process manages the buffer call it boundec m er l uffer O9 1tem 2 in out integer 3 in O 4 out O 5 in lt out n producer bufferin mod n 6 I in in l 7 gt out lt in consumer more 8 I consumer bufferout mod n 9 out 2 out l 10 Comments lines l2 Here bu er is the buffer in the number of items put into the buffer and out the number of items extracted The producer process outputs an item nexzp to this process by boundedbu er I nexlp and the consumer process outputs an item nexlc to this process by boundedbu er I more boundedbu er 7 nextc more is there because CSP does not allow output commands in guards lines 34 These just initialize in and out lines 56 If there is room for another item in the buffer in lt oul n wait for the producer to produce some thing and deposit it in an empty buffer slot producer 7 bu er n mod n and indicate that slot is now used in in 1 lines 79 If the buffer is full out lt in wait until the consumer asks for something consumer 7 moreO then output the next element of the buffer consumer I bu erout mod n and indicate it has been extracted out out 1 Last modified at 1001 am on Thursday January 13 2000 January 13 2000 ECS 251 7 Winter 2000 Page 33 Producer Consumer Problem Introduction This algorithm uses ADA to solve the producerconsum er or boundedbuffer problem Algorithm This process task to ADA manages the buffer 1 task boundedbuffer is 2 entry depositdata in item 3 entry extractdata out item 4 end 5 task body boundedbuffer is 6 buffer array0n 1 of item 7 count integer range On O 8 in out integer range On 1 O 9 begin 10 loop 11 select 12 when count lt n gt 13 accept depositdata in item do 14 bufferin data 15 end 16 in in 1 mod n 17 count 2 count 1 18 or when count gt 0 gt 19 accept extractdata out item do 20 data bufferout 21 end 22 out 2 out 1 mod n 23 count 2 count 1 24 end select 25 end loop 26 end The producer deposits an item into the buffer with 27 boundedbufferdepositnextp and the consumer extracts an item from the buffer with 28 boundedbufferextractnextc Comments lines l4 This indicates that the procedures deposit and extract may be called outside the task and that extract Will return something in its parameter list the out lines 68 As usual buffer is the buffer and count the number of items currently in the buffer in and out are the indices indicating Where deposits go or Where extractions come rom lines 1317 If there is room in the buffer when count lt n this process Will accept a request to deposit an item in it accept deposi t it then updates its variables lines 1823 If there is an item in the buffer when count gt 0 this process Will accept a request to extract an item from the buffer accept extract the item is returned Via the parameter list This pro cedure then updates its variables line 24 If both of the above two when conditions are true and both a producer and consumer has invoked a procedure named by an accept statement called an open accept statement the system will Last modified at 1001 am on Thursday January 13 2000
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'