COMP30023 – Computer Systems University of Melbourne Operating systems: Process communication Olya Ohrimenko Inter process communication Process scheduling Today University of Melbourne 2 Processes Threads: share and execute in the address space of the same process Interrupts University of Melbourne Recap 3 Why concurrency: increase efficiency (parallelism) through cooperation Exchange information between processes/threads Concerns: – How – Processes can interfere with each other – Proper sequencing and order Ensure system integrity and predictable behavior University of Melbourne Interprocess communication 4 Setting: multiple processes have access to shared object (e.g., memory or file) All can read and write it Race condition arises when output depends on the order of operations Very hard to debug University of Melbourne Race condition Process 1 Process 2 Process N Shared memory ….. 5 University of Melbourne Race condition example Pseudo code for popping from a stack. stack // global shared variable void my_stack_function() { if (isEmpty(stack)) return; int s = pop(stack); //do something with s… } 6 University of Melbourne Race condition example Pseudo code for popping from a stack. stack // global shared variable void my_stack_function() { if (isEmpty(stack)) return; int s = pop(stack); //do something with s… } 7 A B Processes A and B University of Melbourne Race condition example Pseudo code for popping from a stack. stack // global shared variable void my_stack_function() { if (isEmpty(stack)) return; int s = pop(stack); //do something with s… } 1. process A tests stack.isEmpty() false 2. process A pops stack is now empty 3. process B tests stack.isEmpty() true 4. process B just returns – nothing to do 8 Potential execution transcript University of Melbourne Race condition example Pseudo code for popping from a stack. stack // global shared variable void my_stack_function() { if (isEmpty(stack)) return; int s = pop(stack); //do something with s… } 1. process A tests stack.isEmpty() false 2. process B tests stack.isEmpty() false 3. process A pops stack is now empty 4. process B pops – Exception 9 Another potential execution transcript How to prevent race conditions – finding them later is hard Idea: prohibit access to shared object at the same time Mutual exclusion: many design choices Identify critical region/section of the program University of Melbourne Critical regions (1) 10 Requirements to avoid race conditions: 1. No two processes may be simultaneously inside their critical regions. 2. No assumptions may be made about speeds or the number of CPUs. 3. No process running outside its critical region may block other processes. 4. No process should have to wait forever to enter its critical region. University of Melbourne Critical regions (2) 11 University of Melbourne Critical regions (3) Figure 2-22. Mutual exclusion using critical regions. 12 University of Melbourne Critical region example Pseudo code for popping from a stack. stack // global shared variable void my_stack_function() { if (isEmpty(stack)) return; int s = pop(stack); //do something with s… } Put this code in critical region 13 Shared variable: lock while (lock != 0) {# wait}lock = 1critical_region()lock = 0 University of Melbourne Lock variable problem 14 Shared variable: lock while (lock != 0) {# wait}lock = 1critical_region()lock = 0 University of Melbourne Lock variable problem Interrupt occurs 15 Methods: Disabling Interrupts Strict Alternation Test and Set Lock Sleep and Wakeup Other: Semaphores, Monitors, Message passing University of Melbourne Techniques for Avoiding Race Conditions Implementation: Busy Waiting Blocking 16 University of Melbourne Strict Alternation with Busy Waiting 17 Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting turn=0 18 Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 19 turn=0Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 20 turn=0Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 21 turn=1Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 22 turn=1Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 23 turn=1Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 24 turn=1Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 25 turn=0Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 26 turn=0Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 27 turn=0Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 28 turn=1Thread A Thread B University of Melbourne Strict Alternation with Busy Waiting 29 turn=1Thread A Thread B Most CPUs come with a test and set lock instructionTSL RX, LOCK Set RX to LOCK Test LOCK, if it is 0, set LOCK to 1 RX can be used to decide whether to enter critical region or not: Compare RX and LOCK University of Melbourne Test and Set Lock (TSL) Atomic operation 43 When a process wants to enter a critical section it checks if the entry is allowed If not, the process executes a loop, checking if it is allowed to enter a critical section Cons: Waste of CPU Priority Inversion Problem – Low and high priority processes – Low priority process may starve -> High priority process is blocked by a lower lower priority process University of Melbourne Busy Waiting 44 Approach – Attempt to enter a critical section – If critical section available, enter it – If not, register interest in the critical section and block – When the critical section becomes available, the OS will unblock a process waiting for the critical section, if one exists Example: Sleep() and Wakeup() Using blocking constructs improves the CPU utilization University of Melbourne Blocking 45 Deadlock: A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause May exist in many shared resource settings; not just memory University of Melbourne Deadlocks Lock(M1) DoWork(…) Lock(M2) DoWork(…) Release_lock(M1) Release_lock(M2) Lock(M2) DoWork(…) Lock(M1) DoWork(…) Release_lock(M2) Release_lock(M1) Process A Process B 46 Deadlock: A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause May exist in many shared resource settings; not just memory University of Melbourne Deadlocks Process A Process B Lock(M1) DoWork(…) Lock(M2) DoWork(…) Release_lock(M1) Release_lock(M2) Lock(M2) DoWork(…) Lock(M1) DoWork(…) Release_lock(M2) Release_lock(M1) 47 1. Ignore the problem 2. Detection (e.g., graph algorithms) and recovery 3. Avoid by careful resource allocation 4. Prevention University of Melbourne Dealing with deadlocks M1 M2 Process A Process B 48 Resource allocation graph: Race conditions Critical region Techniques to ensure mutual exclusion Deadlock University of Melbourne Summary: Process Communication 49 The slides were prepared by Olya Ohrimenko. Some of the images included in the notes were supplied as part of the teaching resources accompanying the text books listed in lecture 1. Reference: TB 2.3, 6.2.2 Acknowledgement University of Melbourne 50
