ConcurrencyConcurrency• Interleaved or overlapped execution • Examples from general purpose digital computing:– Threads– Multiprogramming– Multiprocessing• Examples from computing in nature:– Team projects– Transportation– Food chain• Allows more efficient execution, design flexibilityChallenges of concurrency• Cannot predict relative execution speedCannot know which process* will run next• Effective allocation of shared resources– Memory (e.g. shared variables)– I/O devices (or associated data structures) • Testing and debugging– Program behaviour cannot be reliably replicated* In this discussion “process” is used to mean an entity of dispatchRace conditions• Final result depends on order of execution• Can happen when two or more processes modify a shared resource• For example …… a threaded mail server• Suppose – Mail server counts the emails received each day– Emails received by any of several worker threads • The assembly language description of the worker threads might include the following:LOAD MailCountADD 1STORE MailCountA Possible Execution Trace Thread 1Load MailCountAdd 1Store MailCountThread 2Load MailCountAdd 1Store MailCountPreventing Race Conditions– Restrict access to shared resources– Requires restricting access to code (at some level) that accesses shared resources (“critical section”)– Only when one process has completed execution of the critical section can another process be allowed to begin executing it (“mutual exclusion”)Requirements for a mutual exclusion solutionOnly one process at a time is allowed into its critical section (CS)To prevent race conditionsA process that halts in its non-CS must do so without interfering with other processes.Definition of critical sectionProcess waiting for CS must not be delayed indefinitelyTo prevent deadlock and starvationWhenever there is no process in the CSand at least one process waiting to enter the CS, one must be permitted accessTo prevent starvationNo assumptions are made about the relative speeds or number of processesTo prevent starvationThe time that any one process remains inside its critical section is finiteAssumptionFour different approaches• Hardware– Turn off interrupts– Special instruction(s)• Software– Application layer– System layer (OS/compiler)1. Disable interruptsvoid func(){<non CS>/* disable interrupts */<CS>/* enable interrupts */<non CS>}• Satisfies requirements– No interrupts means no mode switches– No mode switches means no process switches– No process switches means no race condition• Simple and efficient– Appropriate for some embedded systems• Insecure – Trusts application to announce exit from critical section• Only applicable on single processor systems2. Special Instruction(s)TESTSET X1, X2:• Test X1, and set X2 accordingly• Executes atomically – nothing else executes between test operation and set operation!• For example (assuming X1 and X2 are stored in registers R1 and R2):– If register R1 contains the value 0, store the value 1 in both register R1 and R2– Otherwise, leave R1 unchanged and store the value 0 in register R2.• Pros? Cons?Example application (busy wait):int bolt = false;void main() {parbegin( P( 0 ),P( 1 )…P( n ) )}void P( int j ) {while( ! TestSet( bolt ) ) {/* do nothing */}<CS>bolt = false;<non-CS>}3. Application layer • Relies on hardware support• Typical assumption: machine language instructions cannot concurrently modify a memory locationDekker’s Algorithm (1)• Discussed in Appendix A (Figure A.2, p. 375) for the case of two processes• Global variable indicates next process to receive access to critical section• Processes busy wait (a.k.a. spin wait) while checking the global variable• When a process detects that no other process is in the critical section, it asserts its entry (i.e. updates the global variable)• Issues: – Processes are strictly ordered (coroutines)– Process failure (in or out of critical section)Dekker’s Algorithm (2)• Global variable for each process indicating its presence in critical section• Processes busy wait while checking other processes’ presence• When a process detects that no other process is in the critical section, it asserts its entry (i.e. updates its global variable)• Issues: – Process failure in critical section (this does not violate requirements)– No mutual exclusion (two processes check global variables, then enter critical section)Dekker’s Algorithm (3)• Global variable for each process indicating its presence in critical section• Processes first assert their entry, then busy wait while checking other processes’ presence• Issues: – Process failure in critical section– Deadlock (two processes assert their entry, then busy wait)Dekker’s Algorithm (4)• Global variable for each process indicating its need to enter critical section• Processes first assert their need to enter, then busy wait checking other processes’ need to enter– Unassert their own need– Wait– Assert it again• Issues: – Process failure in critical section– “Livelock” starvation (two processes assert their needs, then unassert them, then sequence repeats indefinitely)Dekker’s Algorithm (Final)• Global variables indicating – Each process’ need to enter critical section– Which process is first in line for the critical section• Processes first assert their need to enter, then busy wait – Check other processes’ need to enter– If they are not first in line• Unassert their own need• Wait• Assert it again• Upon entering critical section, processes update the global variable indicating which process is next• Issue:– Fairness (how to decide which process is next)Peterson’s Algorithm• Discussed in Appendix A (Figure A.3, p. 736) for the case of two processes• More elegant than Dekker’s algorithm• Generalization to n processes left as an exercise for the