Concurrency Control

Question 1

3 Concurrency contexts

Answer 1

1. Multiple applications, process time shared 2. Structured applications 3. OS structures

Question 2

Critical resources(CR)

Answer 2

Memory, shared I/O (printer), shared devices

Question 3

Critical section (CS)

Answer 3

portion of program that uses critical resources

Question 4

Concurrency Cases (3 broad activities)

Answer 4

1. communication among processes 2. sharing and competing for resources 3. synchronization of activities of multiple processes

Question 5

OS design and management issues of concurrency

Answer 5

1. OS must be able to track active processes using PCB 2. OS allocate and deallocate resources for each process 3. OS must protect data and physical resources of each process against unintended interface by other processes 4, Results of process must be independent of speed of execution

Question 6

how do processes interact

Answer 6

1. unaware of each other 2. indirectly aware (share access to some I/O 3. directly aware of each other

Question 7

principle strategies of concurrency

Answer 7

single processor - processes interleaved multiple processor, multiprogramming - processes overlapped

Question 8

data coherence, consistency

Answer 8

maintenance of global variables and relationships between them

Question 9

how do we maintain data coherence

Answer 9

sequential program execution

Question 10

3 control problems of concurrency

Answer 10

1. mutual exclusion - only one program at a time allowed 2. deadlocks - p1 has r1 needs r2; p2 has r2 needs r1 3, starvation - p1 has r1; p3 may get but p2 starved

Question 11

requirements for ME (mutual exclusion)

Answer 11

1. ME must be enforced 2. Process that halts in non CS must do so without interfering with other processes 3. Process requiring CS can’t be delayed indefinitely 4. When no process in CS, process that requests entry must be allowed to enter 5. No assumptions about relative process speeds or number of processes 6. Process remains inside CS for finite time delay

Question 12

implementation of ME 3 approaches

Answer 12

software approach special purpose machine instructions (turn, test and set) semaphores

Question 13

1st software approach to ME implementation (turn)

Answer 13

address reserved for turn shared variable Process 0 Process 1 while (turn != 0) ….. /*do nothing*/; while (turn != 1) /*CS*/ /* do nothing*/; turn = 1; /*CS*/ turn = 0;

Question 14

analysis of turn approach

Answer 14

ME guaranteed with problems toggle issue - processes strictly alternate, pace dictated by slower if one process fails, other stalls

Question 15

2nd software approach to ME (Boolean flags)

Answer 15

flag[0] for P0; if TRUE, it’s in CS flag[1] for P1 if FALSE not in CS reset own flag after leaving CS each process may examine other’s flag (not change it)

Question 16

analysis of Boolean flag approach

Answer 16

ME not guaranteed P0 executes the while flag[1] false P1 executes the while flag[0] false BOTH can enter the CS at the same time…..!!!!!!! If flag[1] = TRUE and P1 fails; then system hangs If flag[1]=FALSE and P1 fails; then it is ok . NOT independent of relative process execution speeds…. A process can change its state after the other process has checked it, but before the other process can enter into critical section…

Question 17

correct software solutions to ME

Answer 17

Decker’s algorithm Peterson’s algorithm Combine flag and turn approaches Need to observe state of both processes, which process has right to insist on entering CS

Question 18

Decker’s algorithm

Answer 18

void P0() //need same method for 1() { while(TRUE) //main while loop { flag[0] = TRUE; //turn on your own flag while(flag[1]) //test for P1’s flag { If (turn == 1) //if P1 is active then { flag[0] = FALSE; //turn off your own flag while (turn == 1) //wait for P1 to release /*do nothing, stay here*/; flag[0] = TRUE; //you got the turn now } /* CS */; turn = 1; //give turn to other guy flag[0] = FALSE; //turn off your flag /* remainder */ } //end of test for P1 } //end of main while } //

Question 19

Peterson’s algorithm

Answer 19

boolean flag[2]; int turn; //MAIN PROGRAM void main() { flag[0] = FALSE; flag[1] = FALSE; turn = 0; parabegin (P0, P1); } void P0() //duplicate method for p1() { while(TRUE) //main while loop { flag[0] = TRUE; //turn on your own flag // so that P1 can’t get in turn = 1; //Give a chance to P1 while(flag[1] && turn == 1) //test for P1’s flag and his turn { /*do nothing, stay here*/; } /* CS */; flag[0] = FALSE; //turn off your flag /* remainder */ } //end of main while } //end of P0

Question 20

major issue with all software support for ME

Answer 20

not scalable, multiplies turns and flags

Question 21

hardware support for ME - single processor

Answer 21

with single processor, disable interrupts; guarantees ME while(TRUE) { /* disable interrupts */ * CS */ /*enable interrupts */ /*remainder*/ }

Question 22

analysis of hardware approach to ME

Answer 22

ok for single CPU; not good solution, need to have control breaks and so on

Question 23

Hardware approach - ASM Test and Set Special machine instructions Be able to write for final

Answer 23

Test and Set Instruction Reading and writing with one instruction in an atomic fashion (not subject to interrupts) boolean testset (int i) { If (i==0) { i = 1; return TRUE; } else { return FALSE; } }; /*program ME */ const int n = /*number of processes */ int bolt; void P(int i) { while (TRUE) { while (!testset(bolt)) /* do nothing, testset was not successful*/; /* CS testset was successful */ bolt = 0; /* release the bolt*/ /*remainder*/; } //end of main while }//end of P void main() { Bolt = 0; parabegin ((P(1), P(2), …, P(n)); }

Question 24

Summary of Test and Set (ASM)

Answer 24

Reads and writes at the same time Go and test lock on CS If available, lock it N processes have their own test and set on one CS (say the printer ) Atomic (no interrupts); must be done at assembly level Wastes CPU

Question 25

Semaphores (Dijkstra) CSP

Answer 25

CSP communicating sequential processes parallel - sequential - parallel

Question 26

Advantages/Disadvantages of Machine Instr (test/set)

Answer 26

Advantages: - It is applicable to any number of processes on either a single or multiple processors sharing main memory - It is simple and therefore easy to implement - It can be used to support multiple CSs; each can be defined by its own variable Disadvantages: - Busy waiting is employed; while waiting for a CS, it consumes CPU time - Starvation is possible, selection of a waiting process is arbitrary - Deadlock—P1 in CS needs CR r1; P2 higher priority, needs r1 also; can't compete

Question 27

Semaphores for signaling

Answer 27

Each semaphore has one queue. init semaphore to non-neg 1. Semaphores have two functions: wait() and signal() 2. The wait() operation decrements count, the semaphore value. If someone in CS, go into queue 3. The signal() operation increments the semaphore value. If the value is not positive, then a process is unblocked.

Question 28

Semaphore image

Answer 28

S = 1, s \<\>0 so go to Q; Q is FIFO Wait () ---------------- decrements S was 1 is now 0 p1 can enter CS CS S = 0 Signal() ---------------- increments S=1

Question 29

Producer Consumer problem using semaphores

Answer 29

One or more processes generating data and placing in a buffer. Single consumer taking data out of the buffer one at a time. Prevent overlap of buffer operations. Assume infinite buffer. Producer must read Queue pointers to determine where to write the next item and also determine if the buffer is full. Consumer is not just a reader, it must adjust a Queue pointer to show that it has removed a unit from the buffer…

Question 30

Readers Writers problem using Semaphores (Reader's Priority)

Answer 30

1. Any number of readers may simultaneously read a file. 2. Only one writer at a time may write to the file. 3. If a writer is writing to a file, no reader may read it. 4. Once a single reader access a file, then all other readers can retain control to access the file. (Readers have priority; wait for a writer but multiple readers can read) void Writer() { while(TRUE) {wait(wsem); WRITEUNIT(); //critical section resources signal(wsem); //end writer } wait(x) //reader readcount++; signal (x); wait (x); etc.