************************ Concurrent Programming ************************ .. index:: single: sequential single: concurrent single: parallel single: preenptive ========================= Concurrent and parallel ========================= Sequential Execution progresses in a predefined order, one step at a time. Concurrent The execution order of more than one component is not defined. Also called *logically concurrent*. Parallel More than one step is executed at the same time by more than one hardware. Also called *physically concurrent*. Concurrent does not necessarily mean parallel. Single CPU can execute concurrent tasks by switching them. Preemptive A task has a chance to be switched at any time. Switching usually occurs on timer interrupts or I/O events. Non-preemptive A task will not be switched against its will. .. index:: single: thread single: synchronization pair: cooperation; synchronization pair: competition; synchronization single: critical section single: mutual exclusion ================= Synchronization ================= Thread A flow of control, or a unit of execution that holds its context such as CPU registers and contents of stack. One thread executes a program sequentially, while more than one threads execute a program concurrently. Synchronization To put a constraint on execution of threads at a certain point of a program. Cooperation synchronization When we simply say synchronization, it usually means cooperation synchronization. It includes several cases: for example, a fast thread waits for another slow thread, a thread sends data to another thread, etc. Competition synchronization It is also called *mutual exclusion*. When a certain resource cannot be accessed by more than one thread at the same time, a constraint should be put so that only one thread access it at a time. Critical section A part of program that needs mutual exclusion. .. admonition:: Competition Suppose the initial value of a variable ``x`` is 1. Both threads *A* and *B* will increment ``x`` by 1. 1. *A* reads 1 (the value of ``x``). 2. *B* reads 1 (the value of ``x``). 3. *A* computes 1+1 (result of increment) 4. *B* computes 1+1 (result of increment) 5. *A* writes 2 to ``x`` 6. *B* writes 2 to ``x`` .. index:: single: lock single: unlock single: deadlock single: starvation ======================= Deadlock and starvation ======================= If a thread *locks* a shared resource, other threads cannot access it until the thread *unlocks* it. Deadlock All threads are waiting for some shared resources to be unlocked. No threads can proceed. Starvation A certain thread cannot access a shared resource forever while others can do. .. admonition:: Dining philosophers problem `See Wikipedia `_ There is a chance that deadlock occurs. :: loop Pick up the left folk. Pick up the right folk. Eat for a while. Put the both folks down. Think for a while. end .. admonition:: Now, philosphers get smarter Still, there is a chance that starvation occurs. :: loop Pick up the left folk. if (the right folk is not available) then Put the left folk down. else Pick up the right folk. Eat for a while. Put the both folks down. Think for a while. end end .. admonition:: Exercise 19 :class: exercise If philosophers sit in a row, instead of a circle, deadlock will not occur. Explain why. :ref:`[Answer] ` .. index:: single: semaphore =========== Semaphore =========== A *semaphore* is an abstract data type used for managing synchronization. It consists of a counter and a thread queue. P operation If the counter is greater than 0, decrement it by 1. Otherwise, suspend the current thread, and put it into the queue. V operation If the thread queue is empty, increment the counter by 1. Otherwise, pick a thread from the queue, and let it continue. * Usually provided as a library. * Error-prone. Mistakes easily cause deadlock. .. admonition:: Producers-consumers problem (without mutual exclusion) `See Wikipedia `_ In Ada, ``wait`` and ``release`` conrrespond to P operation and V operation respectively. .. code-block:: ada semaphore fullspots, -- Number of filled spots in the buffer emptyspots; -- Number of empty spots in the buffer fullspots.count := 0; -- Initially no spots are filled emptyspots.count := BUFLEN; -- Initially all spots are empty task producer; loop -- Produce a data wait(emptyspots); -- Wait if no spot is empty -- Put the data into the buffer release(fullspots); -- Increment the number of filled spots end loop end producer; task consumer; loop wait(fullspots); -- Wait if no spot if filled -- Get a data from the buffer release(emptyspots); -- Increment the number of empty spots -- Consume the data end loop end consumer; .. admonition:: Producer-consumer problem (with mutual exclusion) Accessing the shared buffer should be a critical section. A semaphore ``exclusion`` is used to lock the buffer. .. code-block:: ada semaphore exclusion, fullspots, emptyspots; exclusion.count := 1; fullspots.count := 0; emptyspots.count := BUFLEN; task producer; loop -- Produce a data wait(emptyspots); wait(exclusion); -- Lock the buffer -- Put the data into the buffer release(exclusion); -- Unlock the buffer release(fullspots); end loop end producer; task consumer; loop wait(fullspots); wait(exclusion); -- Lock the buffer -- Get a data from the buffer release(exclusion); -- Unlock the buffer release(emptyspots); -- Consume the data end loop end consumer; ========= Monitor ========= A *monitor* is a syntactical structure of mutual exclusion. * Inside a monitor, only one thread can be executed at a time. This enforces mutual exclusion. * A thread can *sleep* in a monitor, which enables another thread to enter the monitor. * A thread can *wake up* another thread sleeping in a monitor. It is less likely to make a mistake about mutual exclusion, compared to semaphore. Still, it is difficult to write cooperation synchronizations. .. admonition:: Producer-comsumer problem in Concurrent Pascal .. code-block:: modula2 type databuf = monitor const bufsize = 100; var buf : array [1..bufsize] of integer; next_in, next_out : 1..bufsize; filled : 0..bufsize; sender_q, receiver_q : queue; procedure entry deposit(item : integer); begin if filled = bufsize then delay(sender_q); buf[next_in] := item; next_in := (next_in mod bufsize) + 1; filled := filled + 1; continue(receiver_q) end ; procedure entry fetch(var item : integer) ; begin if filled = 0 then delay(receiver_q); item := buf[next_out]; next_out := (next_out mod bufsize) + 1; filled := filled - 1; continue(sender_q) end; begin filled := 0; next_in := 1; next_out := 1 end; type producer = process(buffer: databuf); var new_value : integer; begin cycle (* generate a data *) buffer.deposit(new_value); end end; type consumer = process(buffer: databuf); var stored_value : integer; begin cycle buffer.fetch(stored_value); (* consume a data *) end end; .. admonition:: Exercise 20 :class: exercise Which features in Java correspond to the following concepts? * monitor * sleeping in a monitor * waking up another thread :ref:`[Answer] ` .. index:: single: channel ========= Channel ========= Since it is error-prone to use shared memory with mutual exclusion, there is an idea that communication should be used for synchronization. It is theoretically based on *process algebras*. Occam ----- Occam was developed for Transputer, a microprocessor architecture for parallel computing of the 1980s. Concepts of Occam are taken from the *communicating sequential processes* (CSP) which is one of process algebras. Its program is a collection of processes communicating with each other through *channels*. A channel is a one-to-one, uni-directional, and synchronous (i.e. sending and receiving must take place simultaneously) communication devise. * See `An Introduction to the occam Language `_ Go -- Go was first announced by Google in 2009, and Version 1 was released in March 2012. A *goroutine* is a function executing concurrently with others. Two goroutines can communicate via a channel. A channel may be buffered (asynchronous) or unbuffered (synchronous). * See `The Go Programming Language `_