Concurrency: Mutua AND SYNCHRO Ina single processor multiprogramming system the p job to another job until finishes the execution of all processor time to get the simultaneous executic isnot achieved;there is a certain amount forth between processes. Interleaved executi efficiency and in program struct execution. = ;92 © Operating Systems and Systems Programming Tnterleaving with overlapping can be viewed as examples of concurrent ‘Programming. In concurrent programming two or more process execute parallel, so ‘Concurrent access to shared data may result in data inconsistency. 9.1 Critical - Section Consider a system, assume that it consisting of ‘n’ processes. Each process having a ‘of code, in which the process may be changing common variables, updating Atable, writing a file and so on. This segment of code is said to be ‘critical seetign ‘example consider a railway reservation system(assume that it is the centralized ion system, any person from any place to any place can get the tickets). Two from different station (consecutive stations) want to reserved their tickets. number and destination of the place is common. The two Persons try to get vation at same time unfortunately, but the available berths are only one, both for that berth. Itis also the critical section problem. The solution for critical is when one process is executing in its critical section, no other allowed to execute in its critical section. A solution to ‘the critical | must satisfy the folloConcurrency: Mutual Exclusion and Synchronization © 9.2 Mutual exclusion 9.2.1 Requirements for mutual exclusion 1, Mutual exclusion must be enforced, only one process at a time is into its critical section among all processes that have critical the same resource or shared object. A process that halts in its non critical section must do so without it with other processes. When no process is in a critical section, any process that its critical section must be permitted to enter without del: No assumptions are made about relative pro A process remains inside its critical section for a satisfied. One way is to leave the responsibility with the: concurrently. Thus whether they are “system pro; processes would be required to co- ‘with one exclusion with no support from they programming lang We can refer these as software approach. Mutual exclusion—Software approa Software approach is the best-suited method ror on single processor machine or multipi software approaches, Dekker’s algorithOperating Systems and Systems Programming plwantstoenter = false; while favoredprocess = second do; piwantstoenter=true; end; critical section one; favored process = secorid; _ plwantstoenter=false; otherwise one e processtwoConcurrency: Mutual Exclusion and Synchronization @ sections. Ifprocessone is the favored process, it skips the body of the if and. executes the while test waiting for process two to turn off its flag. If processone determines that processtwo is the favored process. Then p is forced into the body of the if statement where it set its own flag off, inside the following while do as long as process two remains the favored turning off its flag, processone allows processtwo to enter its own cr Eventually, processtwo will leave its critical section and ex exclusion exit code. These statements set the favored process bac and set processtwo’s flag off. Processone may now pass the inner wl own flag on. Processone then executes outer while test. If processtwo’s flag (which was recently set off) enters its critical section. If, however, processtwo has quickly critical section, then processtwo’s flag will be on and pi into the body of the outer while. This time, however, 5 seat” because it is now the favored process. So proces and repeatedly executes the outer while test until pro off, allowing processone to enter its critical secti Peterson’s igre = Program a Var favoredprocess :pHBbSA nde ot ad: nter : = true; = first do;Concurrency: Mutual Exclusion and Synchronization End End; Procedure proesstwo; var two cannotenter : boolean; Begin While true do Begin Twocannotenter : true; While twocannotenter do Testandset (twocannotenter, active); critical sectiontwo; Z Active = false; Otherwise two End End; Begin Active = false Parbegin Processend; Processtwo; Parend. In the above algorithm, the boolean variable, active, i it’s criticalsection, and false otherwi 1e bases it critical section on its local boolean variable one cannot.98 ° Operating Systems and Systems Programming the form of operating system calls. When semaphores are used, modifications of code or restructuring of process and modules do not generally necessitate changes in other processes. Semaphores are very convenient for inter process synchronization Semaphores may be provided in a programming language as a program construct gsystem invoked through system calls when provided by the operating Semaphore must be used carefully. A misplaced wait or signal or reserved signal operations may result in indefinite waiting or deadlocks. Consider the 9.3 it suggest a more formal definition of the primitives for semaphores, The signal primitives are assumed to be atomic, that is, they can be interrupted h ‘ine can be treated as an indivisible step. semaphore = record Count : integer ; : list of processConcurrency: Mutual Exclusion and Synchronization © alue=0 Else begin Place this process in S,queue; Block this process End; SignalB(s) If S.queue is empty Then S.value =1 Else begin remove a process p from S.queue place process P on ready list end; Figure 9.4 A definition of binary semaphor A binary semaphore may take on only the values 0 and 9.4 Inter process communicatio:° Operating Systems and Systems Programming int item; while (TRUE) item=produce-tiem(); if (count==N) wait (); insert_item(item) ; count=count +1; if (count==1) wakeup (consumer) ;Concurrency: Mutual Exclusion and Synchronization — @ int item; while (TRUE) { item-produce-item() down (&empty) down (&mutex) ; insert_item(item) ; up (gmutex) ; up (&full) ; } consumer (void) { int item; while (TRUE) down (&full) ; down (&mutex) item=remove-item() up (émutex) 7 up (&empty) 79.12 © Operating Systems al > rs ORO q) Zz ey » o PHI f PHS Figure 9.5 Lunchtime in the philosophers Department PH1,PH2,PH3,PH4,PHS are the 5 philosophers p1,p2,p3,p4,p5 are the 5 plates of noodles, F1,F2,F3,F4,F5 are the 5 forks. The philosophers work is just eating and thinking, When a philosopher gets hungry, he tries to acquire his left and right fork, one at a time, in either order. It successful in acquiring two forks, he eats for a while, then puts down the forks, and continues fo think. The figure 9.6 shows the solution for the problem. #define N5 #define LEFT (I+N-1)%N define RIGHT ) (I+1)%N #define THINKING 0 f#idefine HUNGRY 1 #define EATING 2 typedef int semaphore; int state (N]; semaphore mutex=1; semaphore s(N); void philosopher(int 1) { while (TRUE) { think (); take_forks (i); /* number of philosophers*/ /* number of I/s left neighbur */ /*number of I’s right neighbur */ /* philosopher is thinking */ | /* philosopher is trying to get forks */ /* philosopher is eating */ /* semaphores are a special kind of int */ /* array to keep track of everyone's state */ /* mutual exclusion for critical | regions */ /*one semaphore per philosopher */ /* I; philosopher number, from © to N-1 */ /* repeat forever */ /* philosopher is thinking */ a /* acquire two forks or blockConcurrency: Mutual Exclusion and Synchronization eat(); put_forks (i); } i void take_forks(int I) { down (&mutex) 7 state [I] = HUNGRY; text (i) ; up (&mutex) 7 down (&s [I] ) + void put_forks (i) down (&mutex) ; state [I] =THINKING; test (LEFT) ; test (RIGHT) ; ‘up (&mutex) void test (i) state(I] » sos i; /*yum-yum, spaghetti */ — /* put both forks back on table, / /* I: philosopher numb to N-1 */ 1s : y* /* record fact that | is hungry */ /* try to acquire /wexit critical /* block if forks were ae to N-1 */9.14 © Operating 9.4.3 The readers and writers problem: 7 Another famous IPC problem is the Readers writers problen . to a database. Imagine, for example, an airline reservation ee competing processes wishing to read and write it. It is acceptab atin processes reading the database at the same time, but one process is U el the database. No other process may have access to the data base , a4 an This is the problem of ‘reader and writers’, Consider the figure 9.7 it s solution to the reader and writers problem. gypedet int semaphore; /+ use your imagination */ % Semaphore mutex-1 /*( controls access” (Ci aa Bena rhaee ass /* controls access to the database 4 Tat reso; /* Hof processes reading or wantin to */ Void reader (void) { while (TRUE) { down (mutex) re=re+1; if ( re==1) up (emutex) ; /*repeat forever*/ /*get exclusive access to ‘re’*/ /*one reader more now */ down (sdb)/* if this is the first reader..+) /*xelease exclusive access to ‘ro! #/ /*access the data*/ /* get exclusive access to ‘re’#/ read_data base(); down ( (&mutex) ; xe=re-1 /tone reader fewer now */ if (zes=0) up(edb); -/* it this ie the lace cescee ‘up (&mutex) ; /*release exclusive access to trot #/ use_data_read() /*noncritical region */ } ) void writer (void) { while (TRUE) { /* repeat forever */ think_up_data(); #non' critical region) #/ down (&db) ; /* get exclusive access */ write data base(); /* update the data */ up(&db) ; /* Felease. exclusive accesa */ } Figure 9.7 A solution to the readers and {n this solution, the first reader to get access to the database does a ‘down’ o! the semaphore db. Subsequent readers merely increment a counter re. As leave, they decrement the counterand thelast one out dacs cy “up” om the semapho"® allowing a blocked writer, if there is one, to get in, j writers problemConcurrency: Mutual Exclusion and Synchronization @ 9.45 that while a reader is using the database another reader comes along. ‘tWo reader at the same time is not a problem, the second reader is third and subsequent readers can also be admitted if they come along. riter allowed to write on the database. ‘sleeping barber problem iting customers, if any to sit on, If there are no customers jown in the barber chair and falls a sleep. As illustrated in When a ciistomen arrives, he has to wakeup the slee customers arrive while the.barber is cutting a customer’s h there are empty ohairs) or leave the shop (it all chairs are program the barber and the customers without getting ini rac Our solution uses three semaphores : ‘custo! vl customers(excluding the customer in the barber chair, wl the number of barbers(0 or 1) who are idle, waiting for « is used for mutual exclusion, We also need a variabl the waiting customers. In this solution, a cust number of waiting customers. Ifit he leaves. Consider the figure 9.9 -46 © Operating Systems and Systems Programming ‘executes the procedure ‘barber’, causing him to block on the semaphore, 0 » because it is initially 0. The barber then goes to sleep, he stays a sleep first customer wakes up. Whena customer ae he executes ‘customer’, starting by acquiring ‘mutex? r then checks to see if the number of waiting customers is less than the st, he releases ‘mutex’ and leaves without a haircut. re is an available chair, the customer increments the integer variable, then he does an ‘up’ on the semaphore ‘customers’, thus waking up the is point th ‘the customers releases ‘mutex’, the barber grabs it, does some nd begin the hair cut when the hair cut is over, the customer exits theConcurrency: Mutual Exclusion and Synchronization up (&mutex) ; /*release access to ‘wait down (&barbers) ; /*gp to sleep if # of free. n get_haircut (); /*be seated and be } else { up (Smutex) ; } } 9.5 Monitors Another synchronization construct is the monitor ty procedures, variables and data structures ee ‘of module or package, M° Operating Systems and Systems Programming 0, the calling process will be suspended until the other process has left the monito, 0 other process is using the monitor, the calling process may enter, ds A monitor supports synchronization by the use of condition variables that are d with in the monitor and accessible only within the monitor. Two functions ate on condition variables, + Suspend execution of the calling process on condition ‘monitor is now available for use by another process. ion. If therefore several such processes, choose. one of ere is no such process, do nothing. a atConcurrency: Mutual Exclusion and Synchronization ProducerConsumer. insert (item) End End; Procedure consumer; Begin While true do wroducerConsumer . remove; Consume_item (item) End End; Figure 9.10 9.6 Message passing : process need to the synchronized to enforce ‘mutual ex may need to exchange information. One appro: is ‘message passing’. This method of interprocess: ‘send’ and ‘receive’ , which like semaphores and unlike library procedures such as send (destination,Operating Systems and Systems Programming received are buffered automatically by the operating system. In this Solution, | messages in used, analogous to the N slots in a shared memory buffer, ts out by sending N empty messages to the producer. Whenever an item to give to the consumer, it takes an empty message and full one. In this way, the total number of messages in the system remains >. So they can be stored in a given amount of memory known in works faster than the consumer, all the messages will end up full, isumer; the producer will be blocked, waiting for an empty to come works faster, then the reverse happens all the Messages will Producer to fill them up; the consumer will be blocked , /* Number of slots in the buffer +/ ae |Concurrency: Mutual Exclusion and Synchronization Exercise 1. What is a monitor ? what is the purpose of the monitor ? 2. Explain the following classical IPC problem? a, producer-consumer problem b. Dinning philosophers problem c. Readers-writers problem 4 d. Sleeping barber problem : ¢yeaieae List the requirement for mutual exclusion ? What is a race condition? J What is the basic requirement for the execution what are the differences between competing process? oa : what is a semaphore? Wha what are the differences bet