ConcurrencyAsynchronous concurrencyDifficultiesArchitecturesCommon forms of synchronizationMutual exclusionRace conditionRace condition (cntd)Condition synchronizationBarriersTasks in AdaTask DeclarationsTask Activation: When does a task start running?Task ServicesSynchronization: RendezvousExample: 1 item shared bufferExample: Mutual ExclusionSlide 18Delays and TimeConditional communicationConditional communication (ii)Conditional communication (iii)Readers/Writers problemaccept with and without bodyCommon barrierCommon barrier (cntd)Protected variablesConcurrency in JavaCreating a thread by extending Thread.Creating a thread by implementing RunnablePros and Cons of implementing RunnableExample of non-interacting threadsMutual exclusion in JavaMutual exclusion over a methodMutual exclusion over a method (example)Wait/notify in JavaConcurrencyImportant and difficult(Ada slides copied from Ed Schonberg)Asynchronous concurrencyTwo 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.•BarriersMutual exclusionOnly one thread at a time can enter its critical section.•Shared resources: e.g. printer, terminal, speaker.•Shared memory.Race conditionThread A: Thread B:X = X+10; X = X+20; AssemblyA1: LOAD R1, X B1: LOAD R2,XA2: ADD R1, 10 B2: ADD R2, 20A3: STORE R1, X B3: STORE R2,XRace condition (cntd) X = 10 R1 R2A1: LOAD R1,X 10B1: LOAD R2,X 10A2: ADD R1, 10 20B2: ADD R2, 20 30B3: STORE R2, X 30A3: STORE R1,X 20Condition synchronizationSuspend 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 arrivesBarriersMake 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 AdaIndividual 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 … endTask 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 buffertask 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 Exclusiontask type Mutex is entry Lock(); entry Unlock();end;task body Mutex isbegin loop accept Lock() do ; end Lock; accept Unlock() do ; end Unlock; end loop; end Mutex;task XMutex: Mutex;…Thread A Thread BXMutex.Lock(); XMutex.Lock();X := X+10; X := X+20;XMutex.Unlock(); 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 selectConditional 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 selectIf several guards are satisfied and callers are present, then any one of the calls may be accepted: