Concurrency Important and difficult Ada slides copied from Ed Schonberg Asynchronous concurrency Two threads of computation proceed simultaneously Don t know the relative timing in advance Threads must communicate and they must sometimes synchronize Difficulties Non deterministic What happens may depend on the relative timing A program is correct only if it is correct for all possible interleavings of steps For 2 thread each with N steps there are C 2N N 2N interleavings Interaction with multi process OS or not Scott has a detailed account Architectures Low level architecture and peripherals Universal but below the PL level Multiple CPUs Not uncommon but rarely enough for all the threads you want Pseudo parallelism Time sharing CPU executes some of one thread then changes to another Computers on a network Languages for distributed system are different reflecting the high cost of communication Common forms of synchronization Mutual exclusion Condition synchronization Barriers Mutual exclusion Only one thread at a time can enter its critical section Shared resources e g printer terminal speaker Shared memory Race condition Thread A X X 10 Thread B X X 20 Assembly A1 LOAD R1 X B1 LOAD R2 X A2 ADD R1 10 B2 ADD R2 20 A3 STORE R1 X B3 STORE R2 X Race condition cntd X 10 A1 LOAD R1 X B1 LOAD R2 X A2 ADD R1 10 B2 ADD R2 20 B3 STORE R2 X A3 STORE R1 X R1 10 R2 10 20 30 30 20 Condition synchronization Suspend the thread until some condition is met In a complex calculation thread A may have to wait for the result of B in order to continue In a web search engine a thread requests a web page from a server then waits until the page arrives Barriers Make sure that all the threads have reached a barrier point before any proceed past it E g in simulation of a physical system have a thread for each physical part compute behavior over a time step Make sure that all parts finish one time step before any proceed to the next Tasks in Ada Individual tasks and task types Task declaration task boss task body boss is begin end Task type declaration type task worker type Worker id is access worker task body worker is begin end Task Declarations Individual tasks and task types A task can be a component of a composite The number of tasks in a program is not fixed at compile time W1 W2 worker type Crew is array integer range of worker First Shift Crew 1 10 Task Activation When does a task start running Individual task at start of program If statically allocated at next begin If dynamically allocated at the point of allocation declare W1 W2 Worker Joe Worker ID new Worker starts working at once Third Shift Crew 1 N of Worker begin start W1 W2 Third Shift end wait for W1 W2 Third Shift to complete not Joe Task Services A task can perform some actions entries on request from another task The declaration of the task specifies the available entries A task can also execute actions on its own behalf task type Device is entry Read X out Integer entry Write X Integer end Device Synchronization Rendezvous Caller makes explicit request entry call Callee server states its availability accept statement If server is not available caller blocks and queues up on the entry for later service If both present and ready parameters are transmitted to server Server performs body of entry Out parameters are transmitted to caller Both caller and server continue execution Example 1 item shared buffer task Buffer is entry Put X in Item entry Get X out Item end task body Buffer is V Item begin loop accept Put X in Item do V X end Put accept Get X in Item do X V end Get end loop end Buffer To call Buffer Put Buffer Get Example Mutual Exclusion task type Mutex is entry Lock entry Unlock end task body Mutex is begin loop accept Lock do end Lock accept Unlock do end Unlock end loop end Mutex task XMutex Mutex Thread A XMutex Lock X X 10 XMutex Unlock Thread B XMutex Lock X X 20 XMutex Unlock Delays and Time A delay statement can be executed anywhere at any time to make current task quiescent for a stated duration or until a specified time delay 0 2 unit is seconds type is Duration delay until Noon Conditional communication Need to protect against excessive delays deadlock starvation caused by missing or malfunctioning task Timed entry Caller waits for rendezvous a stated amount of time select D Write 997 D is a task or delay 0 2 end select Conditional communication ii Conditional entry call Caller ready for rendezvous only if no one else is queued and rendezvous can begin at once select D Write 997 else Put Line Device busy end select Print message if call cannot be accepted immediately Conditional communication iii The server may accept a call only if the internal state of the task is appropriate select when not full accept Write V integer or when not empty accept Read V integer or delay 0 2 end select If several guards are satisfied and callers are present then any one of the calls may be accepted Non determinism Readers Writers problem Problem Various tasks want to read and write to the same data a chunk of data of some size Writers must be mutually exclusive with one another and with readers but readers need not be accept with and without body accept Write do V X end caller must wait until end accept Start caller must synchronize but need not wait after acceptance Common barrier Problem N threads must move through iterations of a loop in lock step Controller loop for I in 1 NThreads loop accept finish end loop for I in 1 NThreads loop accept continue end loop end loop Common barrier cntd Each of the computational threads has the following form for I in 1 NumIterations loop body of iteration Controller finish Controller continue end loop Protected variables Built in mechanism for mutual exclusion and readers writers on data Concurrency in Java A thread is an object Two ways to define a class of threads extend class Thread and override run implement interface runnable and define run interface runnable public void run Creating a thread by extending Thread class plum extends Thread public void run plum P new plum creates thread P P start starts P running The start method is inherited from Thread and calls the run method Alternatively you can write new Plum start Creating a thread by implementing Runnable class Pear implements Runnable public void run Thread t1 new Thread new Pear t1 start or new Thread new Pear start Pros and Cons of implementing Runnable Advantage You can derive the new Thread class from a non Thread class Disadvantage