Concurrency

Concurrency

program level
subprogram level
statement level
instruction level

first computers: general, i, o
early 60's: multiple processors - program level
Now: multi-processor: single instruction multiple data - eg. on vectors
mult instruc mult data: each general processor has own data. can be a distributed system

physical vs. logical concurrency
thread of control
coroutines - quasi-concurrent, because single thread of control

physical, logical concurrency - have, or can imagine have, different threads of control

task: a unit that can be in concurrent execution with other such units
vs. subprogram:
can be implicitly started rather than explicitly called
when task invoked, need not wait for return from that task (asynchronous)
on return, may not necessarily return control to the caller

Communication w other tasks
shared nonlocal variables
message passing
parameters
if no such communication, called disjoint
often used for simulations, so to coordinate need communication

Synchronization:
mechanism controlling order of task execution
coop vs competition.
cooperative when A must wait for B, in order for task A to continue sensibly
Competitive: both require same resource which cannot be used simultaneously
if A needs to access shared location x, which B is using, B must wait.

famous cooperation: producer/consumer problem. from OS
one unit produces, the other consumes.place in, take from a buffer.
cannot take from buffer if empty.

competitive:
int total = 3;
A: add 1 to total.
B: mult total by 2

each must fetch, modify
what can happen without syncronization?
3 values can result. 8 (correct),
if A, B fetch before other writes back, --- if A writes first, Total = 6. If B first, total = 4

mutual exclusion. each must request and then release the resource.

Also, if more tasks than processors, need a scheduler, which delays execution.
Can time slice. let process execute for X amount of time. OK if all processes have same priority. complications,
as e.g. they wait for i/o, delays for syncronization.

tasks can be in several states.
1. New - task created, not begun
2. runnable, ready - ready to run but not currently running. given processor time, or was running and was blocked
3. running - currently executing
4. blocked - was running, but interrupted by an event. i/o most common, since most slow.
5. dead - no longer actuve. execution finished or was killed.

different algorithms for choosing which ready task to make runnable when currently running one is blocked. e.g. priority queue.

characteristic: liveness - program continues ti execute, leading to its completion.
deadlike can break liveness. how so?
A and B need X and Y to continue, but A has X, B has Y. deadlock avoidance - in lang and program design.

Language support for concurrency: PL/I, Ada 95, Java.



to be continued