Operating Systems BCS303 PDF

OPERATING SYSTEMS BCS303 COURSE NAME: OPERATING SYSTEMS COURSE CODE: BCS303 SEMESTER: 3RD 2022 SCHEME MODULE: 3 NUMBER OF HOURS: 08 CONTENTS: ❖ Process Synchronization: The Critical Section Problems Peterson's Solution Synchronization Hardware Semaphores...

OPERATING SYSTEMS BCS303 COURSE NAME: OPERATING SYSTEMS COURSE CODE: BCS303 SEMESTER: 3RD 2022 SCHEME MODULE: 3 NUMBER OF HOURS: 08 CONTENTS: ❖ Process Synchronization: The Critical Section Problems Peterson's Solution Synchronization Hardware Semaphores Classical Problems of Synchronization ❖ Deadlocks: System Models Deadlock Characterization Method for Handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection and Recovery from Deadlock ❖ WEB RESOURCES: https://vtucode.in  Operating Systems BCS303 21CS44 MODULE 3 PROCESS SYNCHRONIZATION A cooperating process is one that can affect or be affected by other processes executing in the system. Cooperating processes can either directly share a logical address space (that is, both code and data) or be allowed to share data only through files or messages. Concurrent access to shared data may result in data inconsistency. To maintain data m consistency, various mechanisms is required to ensure the orderly execution of cooperating processes that share a logical address space. o Producer- Consumer Problem c A Producer process produces information that is consumed by consumer process.. To allow producer and consumer process to run concurrently, A Bounded Buffer can be used where the items are filled in a buffer by the producer and emptied by the e consumer. The original solution allowed at most BUFFER_SIZE - 1 item in the buffer at the same time. To overcome this deficiency, an integer variable counter, initialized to 0 d isadded. counter is incremented every time when a new item is added to the buffer and is o decremented every time when one item removed from thebuffer. c The code for the producer process can be modified as follows: u while (true) { t while v (counter == BUFFER_SIZE) ; // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; } The code for the consumer process can be modified as follows: while (true){ while (counter ==0) ; // donothing nextConsumed =buffer[out]; out = (out + 1) % BUFFER_SIZE; counter--; } 1  Operating Systems 21CS44 BCS303 Race Condition When the producer and consumer routines shown above are correct separately, they may not function correctly when executed concurrently. Illustration: Suppose that the value of the variable counter is currently 5 and that the producer and consumer processes execute the statements "counter++" and "counter--" concurrently. The value of the variable counter may be 4, 5, or 6 but the only correct result is m counter == 5, which is generated correctly if the producer and consumer execute separately. c o The value of counter may be incorrect as shown below:. The statement counter++ could be implemented as register1= counter register1 = register1 + 1 e counter =register1 d The statement counter-- could be implemented as register2 =counter o register2 = register2 – 1 count = register2 u c The concurrent execution of "counter++" and "counter--" is equivalent to a sequential execution in which the lower-level statements presented previously are interleaved in some t arbitrary order. One such interleaving is v Consider this execution interleaving with “count = 5” initially: S0: producer execute register1=counter {register1 = 5} S1: producer execute register1 = register1+1 {register1 = 6} S2: consumer execute register2=counter {register2 = 5} S3: consumer execute register2 = register2-1 {register2 = 4} S4: producer execute counter=register1 {count =6} S5: consumer execute counter=register2 {count =4} Note: It is arrived at the incorrect state "counter == 4", indicating that four buffers are full, when, in fact, five buffers are full. If we reversed the order of the statements at T4 and T5, we would arrive at the incorrect state "counter==6". Definition Race Condition: A situation where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place, is called a RaceCondition. To guard against the race condition, ensure that only one process at a time can be manipulating the variable counter. To make such a guarantee, the processes are synchronized in some way. 2  Operating Systems BCS303 21CS44 The Critical Section Problems Consider a system consisting of n processes {Po, P1 ,... ,Pn-1}. Each process has a segment of code, called a critical section in which the process may be changing common variables, updating a table, writing a file, and soon The important feature of the system is that, when one process is executing in its m critical section, no other process is to be allowed to execute in its critical section. That is, no two processes are executing in their critical sections at the sametime. The critical-section problem is to design a protocol that the processes can use to o cooperate.. c The general structure of a typical process Pi is shown in below figure. Each process must request permission to enter its critical section. The section of code e implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the d reminder section. c o t u v Figure: General structure of a typical process Pi A solution to the critical-section problem must satisfy the following three requirements: 1. Mutual exclusion:If process Pi is executing in its critical section, then no other processes can be executing in their criticalsections. 2. Progress:If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponedindefinitely. 3. Bounded waiting:There exists a bound, or limit, on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request isgranted. 3  Operating Systems 21CS44 BCS303 PETERSON'S SOLUTION This is a classic software-based solution to the critical-section problem. There are no guarantees that Peterson's solution will work correctly on modern computer architectures Peterson's solution provides a good algorithmic description of solving the critical- m section problem and illustrates some of the complexities involved in designing software that addresses the requirements of mutual exclusion, progress, and o bounded waiting. c Peterson's solution is restricted to two processes that alternate execution between their. critical sections and remainder sections. The processes are numbered Po and P1 or Pi and Pj where j = 1-i Peterson's solution requires the two processes to share two data items: e int turn; d boolean flag; turn: The variable turn indicates whose turn it is to enter its critical section. Ex: o if turn == i, then process Pi is allowed to execute in its criticalsection flag: The flag array is used to indicate if a process is ready to enter its critical c section. Ex: if flag [i] is true, this value indicates that Pi is ready to enter its critical section. t u do { v flag[i] = TRUE; turn = j; while (flag[j] && turn == j) ; // do nothing critical section flag[i] = FALSE; remainder section } while (TRUE); Figure: The structure of process Pi in Peterson's solution To enter the critical section, process Pi first sets flag [i] to be true and then sets turn to the value j, thereby asserting that if the other process wishes to enter the critical section, it can doso. If both processes try to enter at the same time, turn will be set to both i and j at roughly the same time. Only one of these assignments will last, the other will occur but will be over written immediately. 4  Operating Systems BCS303 21CS44 The eventual value of turn determines which of the two processes is allowed to enter its critical sectionfirst To prove that solution is correct, then we need to show that 1. Mutual exclusion ispreserved 2. Progress requirement is satisfied m 3. Bounded-waiting requirement is met o 1. To prove Mutual exclusion Each pi enters its critical section only if either flag [j] == false or turn ==i. c If both processes can be executing in their critical sections at the same time, then. flag == flag ==true. These two observations imply that Pi and Pj could not have successfully executed e their while statements at about the same time, since the value of turn can be either 0 or 1 but cannot be both. Hence, one of the processes (Pj) must have successfully d executed the while statement, whereas Pi had to execute at least one additional statement ("turn==j"). o However, at that time, flag [j] == true and turn == j, and this condition will persist as long as Pi is in its critical section, as a result, mutual exclusion ispreserved. c 2. To prove Progress and Bounded-waiting u A process Pi can be prevented from entering the critical section only if it is stuck in t the while loop with the condition flag [j] ==true and turn=== j; this loop is the only onepossible. v If Pj is not ready to enter the critical section, then flag [j] ==false, and Pi can enter its criticalsection. If Pj has set flag [j] = true and is also executing in its while statement, then either turn === i or turn ===j. ▪ If turn == i, then Pi will enter the criticalsection. ▪ If turn== j, then Pj will enter the criticalsection. However, once Pj exits its critical section, it will reset flag [j] = false, allowing Pi to enter its criticalsection. If Pj resets flag [j] to true, it must also set turn to i. Thus, since Pi does not change the value of the variable turn while executing the while statement, Pi will enter the critical section (progress) after at most one entry by Pj (boundedwaiting). 5  Operating Systems BCS303 21CS44 SYNCHRONIZATIONHARDWARE The solution to the critical-section problem requires a simple tool-alock. Race conditions are prevented by requiring that critical regions be protected by locks. That is, a process must acquire a lock before entering a critical section and it releases the lock when it exits the critical section m do { o acquire lock critical section c release lock. remainder section } while (TRUE); e Figure: Solution to the critical-section problem using locks. The critical-section problem could be solved simply in a uniprocessor d environment if interrupts are prevented from occurring while a shared variable o was being modified. In this manner, the current sequence of instructions would be allowed to execute in order without preemption. No other instructions would be c run, so no unexpected modifications could be made to the sharedvariable. But this solution is not as feasible in a multiprocessor environment. Disabling u interrupts on a multiprocessor can be time consuming, as the message is passed to t all the processors. This message passing delays entry into each critical section, and system efficiency decreases. v TestAndSet ( ) and Swap( ) instructions Many modern computer systems provide special hardware instructions that allowto test and modify the content of a word or to swap the contents of two words atomically, that is, as one uninterruptibleunit. Special instructions such as TestAndSet () and Swap() instructions are used to solve the critical-sectionproblem The TestAndSet () instruction can be defined as shown in Figure. The important characteristic of this instruction is that it is executedatomically. Definition: booleanTestAndSet (boolean *target) { booleanrv = *target; *target = TRUE; return rv: } Figure: The definition of the TestAndSet () instruction. 6  Operating Systems 21CS44 BCS303 Thus, if two TestAndSet () instructions are executed simultaneously, they will be executed sequentially in some arbitrary order. If the machine supports the TestAndSet () instruction, then implementation of mutual exclusion can be done by declaring a Boolean variable lock, initialized to false. do { m while ( TestAndSet (&lock )) ; // do nothing o // critical section lock =FALSE; c // remaindersection. } while (TRUE); Figure: Mutual-exclusion implementation with TestAndSet () e The Swap() instruction, operates on the contents of two words, it is defined as shown d below o Definition: void Swap (boolean *a, boolean *b) c { boolean temp = *a; u *a = *b; t *b = temp: } v Figure: The definition of the Swap ( ) instruction Swap() it is executed atomically. If the machine supports the Swap() instruction, then mutual exclusion can be provided as follows. A global Boolean variable lock is declared and is initialized to false. In addition, each process has a local Boolean variable key. The structure of process Pi is shown in below do { key = TRUE; while ( key == TRUE) Swap (&lock, &key ); // critical section lock =FALSE; // remaindersection } while (TRUE); Figure: Mutual-exclusion implementation with the Swap() instruction 7  Operating Systems BCS303 21CS44 These algorithms satisfy the mutual-exclusion requirement, they do not satisfy the bounded- waiting requirement. Below algorithm using the TestAndSet () instruction that satisfies all the critical- section requirements. The common data structures are boolean waiting[n]; m boolean lock; o These data structures are initialized to false. c do {. waiting[i] = TRUE; key = TRUE; while (waiting[i] && key) e key = TestAndSet(&lock); waiting[i] = FALSE; d // critical section j o = (i + 1) % n; while ((j != i) && !waiting[j]) c j = (j + 1) % n; if (j == i) lock = FALSE; u else t waiting[j] = FALSE; // remainder section v } while (TRUE); Figure:Bounded-waiting mutual exclusion with TestAndSet () 8 Deepak D, Asst. Prof., Dept. of CS&E, Canara Engineering College, Mangaluru 30  Operating Systems BCS303 21CS44 1. To prove the mutual exclusionrequirement Note that process Pi can enter its critical section only if either waiting [i] == false or key ==false. The value of key can become false only if the TestAndSet( ) isexecuted. The first process to execute the TestAndSet( ) will find key== false; all others must m wait. The variable waiting[i] can become false only if another process leaves its critical section; only one waiting[i] is set to false, maintaining the mutual-exclusion o requirement. c 2. To prove the progressrequirement. Note that, the arguments presented for mutual exclusion also apply here, since a process exiting the critical section either sets lock to false or sets waiting[j] to false. Both allow a e process that is waiting to enter its critical section to proceed. 3. To prove the bounded-waitingrequirement d Note that, when a process leaves its critical section, it scans the array waiting in the cyclic ordering (i + 1, i + 2,... , n 1, 0,... , i 1). It designates the first process in this ordering that is in the entry section (waiting[j] o ==true) as the next one to enter the critical section. Any process waiting to enter its c critical section will thus do so within n - 1 turns. u SEMAPHORE t A semaphore is a synchronization tool is used solve various synchronization v problem and can be implementedefficiently. Semaphore do not require busywaiting. A semaphore S is an integer variable that, is accessed only through two standard atomic operations: wait () and signal (). The wait () operation was originally termed P and signal() was calledV. Definition of wait (): wait (S) { while S