程序代写代做代考 concurrency Java go cache C Concurrency

Concurrency
Mitchell Chapter 14

Concurrent Programs Two or more sequences of events occur in parallel
• Multiprogramming
– Asinglecomputerruns several programs at the same time
– Eachprogramproceeds sequentially
– Actionsofoneprogrammay occur between two steps of another
• Multiprocessors
– Twoormoreprocessorsmay
be connected
– Programsononeprocessor communicatewithprograms on another
– Actionsmayhappen simultaneously
process, thread, task:
sequential program running on a processor
2

Concurrency
• Allows different tasks to proceed at different speeds.
• Multiprogramming
– Allows one program to do useful work while another is waiting for input
– More efficient use of a single processor
• Multiprocessing
– More raw processing power available
– Introduces new issues
• Reliability of network
• Some processor(s) proceeding while another crashes
• Interaction between separate sequential programs raises programming challenges (in both multiprogramming and
multiprocessing)
Most of the concepts discussed apply to either kind of concurrency.
3

Concurrent Programming Languages
• Provide abstractions and control structures defined specifically for concurrent programming.
• Can provide “light-weight” processes that are less costly than operating system processes
• Can provide portability across operating systems.
– Historically, concurrent systems written in languages that did not support concurrency. For example, using system calls specific to a particular operating system.
• We study basic concepts using particular example languages. – Concurrent ML (as an extension of Standard ML)
– Java
4

Basic Concepts in Concurrency
• ExecutionOrderandNondeterminism
• Communication,Coordination,andAtomicity • MutualExclusionandLocking
• Semaphores
• Monitors
5

Execution Order and Nondeterminism
• An early limited concurrency primitive in Concurrent Pascal: cobegin…coend statement
• Example x := 0;
cobegin
begin x := 1; x := x+1 end; begin x := 2; x := x+1 end;
coend; print(x);
x := 1
x := 0
x := 2
execute sequential blocks in parallel
x := x+1
print(x) x := x+1
Example showing execution on a single processor
6

Execution Order and Nondeterminism
x := 1
x := 0
x := 2
x := x+1
print(x) x := x+1
• Each assignment statement executes atomically, which means that there may be more than one low-level machine step, but one assignment is fully completed before allowing another process to execute.
• Some possible orderings between statements: x:=0;x:=1;x:=2;x:=x+1;x:=x+1;print(x) Output:4 x:=0;x:=2;x:=1;x:=x+1;x:=x+1;print(x) Output:3 x:=0;x:=1;x:=x+1;x:=2;x:=x+1;print(x) Output:3 x:=0;x:=2;x:=x+1;x:=1;x:=x+1;print(x) Output:2
Illustrates problem of nondeterminism
7

Nondeterminism
• Aprogramisdeterministicif,foreachsequenceof program inputs, there is one sequence of program actions and resulting outputs.
• Aprogramisnondeterministicifthereismorethan one possible sequence of actions corresponding to a given input sequence.
– Several possible execution orders
– Different results for different runs, even on the same
computer
– Difficult to design and debug programs
8

Example Illustrating Problem of Nondeterminism
• Cachecoherenceprotocolsinmultiprocessors
– A set of processors share memory
– Access to memory is slow, can be bottleneck
– Each processor maintains a memory cache
– The job of the cache coherence protocol is to maintain the processor caches, and to guarantee that the values returned by every load/store sequence generated by the multiprocessor are consistent with the memory model.
9

Cache filled by read
• PEA reads location x
– Copy of x put in PEA’s
cache.
• PEB also reads x
– Copy of x put in PEB’s cache too.
10

Cache modified by write
• PEA adds1tox
– x is in PEA’s cache, so
there’s a cache hit
• If PEB reads x from cache, may be wrong
– OK if program semantics allows PEB read before PEA write
• Need protocol to avoid using stale values
11

Communication, Coordination, and Atomicity • Mechanisms in programming languages for explicit
concurrency:
– Mechanism to initiate and terminate individual sequential processes (all concurrent programming languages provide this capability)
– Communication between processes
• Buffered communication channels
• Synchronous communication channels
• Broadcast
• Shared variables or objects (as in Concurrent Pascal example)
– Coordination between processes
• May explicitly or implicitly cause one process to wait for another
before continuing
– Atomicity (mentioned earlier)
• Affects both interaction between processes and handling of errors 12

Interprocess Communication
• Sharedvariablesismostelementaryform
• Canalsohaveshareddatastructuresorfiles
• Anotherformismessagepassingwithavarietyof mechanisms (see next page)
13

Message Passing
– Buffering
• If communication is buffered, then every data item that is sent
remains available until it is received
• In unbuffered communication, a data item sent before the receiver is ready to accept may be lost
– Synchronicity
• In synchronous communication, the sender cannot transmit data
unless the receiver is ready to receive it.
• In asynchronous communication, the sending process may transmit a data item and continue executing even if the receiver is not ready to receive the data.
– Message Order
• A communication mechanism may preserve order of transmission
of messages, or it may not.
• If so, messages will be received in the order they are sent.
14

Coordination
• Coordinationmechanismsallowoneprocesstowait for another or notify a waiting process that it may proceed.
– Concurrent Pascal cobegin…coend: all processes started at the same cobegin must finish before the statement following coend may proceed
– Locking
– Semaphores
15

Mutual Exclusion and Locking
• Issue: maintaining consistency of shared data
• Sample action
procedure sign_up(person) begin
number := number + 1;
list[number] := person; end;
• Problem with parallel execution cobegin
sign_up(fred);
sign_up(julie); end;
bob
16

Mutual Exclusion and Locking
• Issue: maintaining consistency of shared data
• Sample action
procedure sign_up(person) begin
number := number + 1;
list[number] := person; end;
• Problem with parallel execution cobegin
sign_up(fred);
sign_up(julie); end;
bob
17

Mutual Exclusion and Locking
• Issue: maintaining consistency of shared data
• Sample action
procedure sign_up(person) begin
number := number + 1;
list[number] := person; end;
• Problem with parallel execution cobegin
sign_up(fred);
sign_up(julie); end;
bob
18

Mutual Exclusion and Locking
• Issue: maintaining consistency of shared data
• Sample action
procedure sign_up(person) begin
number := number + 1;
list[number] := person; end;
• Problem with parallel execution cobegin
sign_up(fred);
sign_up(julie); end;
bob
fred
19

Mutual Exclusion and Locking
• Issue: maintaining consistency of shared data
• Sample action
procedure sign_up(person) begin
number := number + 1;
list[number] := person; end;
• Problem with parallel execution cobegin
sign_up(fred);
sign_up(julie); end;
julie fred
bob
20

Incorrect Ordering
cobegin
n := n+1 n := n+1
list[n]:=fred list[n]:=julie
coend
n := n+1; n := n+1; list[n] := fred; list[n] := julie;
Results in an inconsistent state because it is not consistent with intended behaviour.
21

Mutual Exclusion
• Critical Section—a section of a program that accesses shared resources
– Two processes may access shared resource
– Inconsistent behavior if two actions are interleaved
• Mutual Exclusion
– One process at a time may be in its critical section
– Progress: If no processes are in their critical section and some process wants to enter a critical section, it becomes possible for one waiting process to enter its critical section.
– Bounded waiting: If one process is waiting, there must be a bound on the number of times that other processes are allowed to enter their critical sections before this one.
22

Locks and Busy Waiting • Example using wait and signal actions

cobegin begin

sign_up(fred); // critical section

end; begin

sign_up(julie);
// critical section
Need atomic operations to implement wait

end; end;
23

Lock and Signal Implemented as Integers
lock := 0;
cobegin begin
while lock=1 do end; // wait until lock is 0 lock := 1; // set lock to enter critical section sign_up(fred); // critical section
lock := 0; // release lock
end; begin
while lock=1 do end; // wait until lock is 0 lock := 1; // set lock to enter critical section sign_up(julie); // critical section
lock := 0; // release lock end;
end;
24

Lock and Signal Implemented as Integers
while lock=1 do end; // wait until lock is 0 lock := 1; // set lock to enter critical section sign_up(…); // critical section
• Using a loop to wait is called busy waiting.
• Problem with using a shared variable for mutual exclusion: operation that reads the value of the variable is different from the operation that sets it.
• It is possible for one process to test the variable and see that the lock is open (lock=0), but before the process can lock other processes out by setting it. (lock := 1), another process can also see the lock is open and set the variable first.
• Two processes can then call signup at once.
25

Atomic Test-and-Set Lock (TSL)
• Instructionatomicallyreadsandwritessomelocation
• Commonhardwareinstruction
• Combinewithbusy-waitinglooptoimplement mutual exclusion.
26

Deadlock
• Process may hold some locks while awaiting others
• Deadlock occurs when no process can proceed
• Example:
– Process 1 sets Lock 1 and waits for Lock 2 – Process 2 sets Lock 2 and waits for Lock 1
• Possible solution: 2-phase locking
– A process is viewed as a sequence of independent tasks.
– Locking phase: For each task, the process must acquire all the locks that could be needed.
– Release phase: A process must release all locks before proceeding to the next task.
– There must be an ordering on locks.
27

Semaphore
– Avoid busy-waiting loop
– Keep queue of waiting processes
– A standard semaphore is represented by an integer value: the maximum number of processes that may enter a critical section at the same time
– Scheduler has access to semaphore; process sleeps
– Disable interrupts during semaphore operations
• OK since operations are short
– Processescallwait,andthenmustcallsignalwhen
finished, otherwise deadlock could occur.
28

Semaphore Wait
// This procedure must be executed atomically.
procedure wait (s:Semaphore) begin
if s.value > 0 then
s.value := s.value – 1; // Enter section and
// decrement counter
else
suspend_on (s.queue); // Wait for other
end;
// processes to finish
29

Semaphore Signal
// This procedure must be executed atomically.
procedure signal (s:Semaphore) begin
if length(s.queue) = 0 then
s.value := s.value + 1; // Increase count
// allowing other
// processes to enter
else
allow_one_process (s.queue);
end;
// Wake up one
// suspended process
30

Monitor
• Synchronized access to private data
• Responsibility for synchronization placed on operations that access data
• Combines:
– private data
– set of procedures (methods) – synchronization policy
• At most one process may execute a monitor procedure at a time; this process is said to be in the monitor.
• If one process is in the monitor, any other process that calls a monitor procedure will be delayed.
• Terminology: synchronized object
31

Concurrent Language Examples
• Language Examples
– Cobegin/coend
– Actors (not covered in this class) – Concurrent ML
– Java
• Main Features to Compare – Threads
– Communication – Synchronization – Atomicity
32

Properties of cobegin/coend
Concurrent Pascal
• Advantages
– Create concurrent processes
– Communication: shared variables
• Limitations
– Mutual exclusion: none
– Atomicity: not much (an assignment statement is atomic)
– Number of processes is fixed by program structure
– Cannot abort processes
• All must complete before parent process can go on
33

Concurrent ML
An Extension to Standard ML
• Threads
– New type of entity
• Communication
– Synchronous channels
– Communication and coordination combined
• Synchronization
– Channels
– Events (allows users to define their own communication and synchronization abstractions)
• Atomicity
– No specific language support
34

Threads
• Thread creation
– spawn : (unit ® unit) ® thread_id
• Example code
CIO.print “begin parent\n”;
spawn (fn () => (CIO.print “child 1\n”;));
spawn (fn () => (CIO.print “child 2\n”;)); CIO.print “end parent\n”
• Result
begin parent
child 1 child 2
end parent
35

Threads
• Thread creation
– spawn : (unit ® unit) ® thread_id
• Example code
CIO.print “begin parent\n”;
spawn (fn () => (CIO.print “child 1\n”;));
spawn (fn () => (CIO.print “child 2\n”;));
CIO.print “end parent\n”
• Result
begin parent
t
N
N
t
o
t
E
.
a
e
E
b
e
b
a
P
.
P
f
”
f
o
e
i
o
i
f
i
o
e
i
f
r
r
o
r
r
t
e
r
t
e
f
r
r
t
t
f
i
h
h
f
f
e
i
s
e
n
s
h
n
h
t
r
m
m
o
t
e
e
o
c
e
e
c
t
t
,
e
,
a
e
i
r
i
t
r
t
s
s
“
s
r
r
s
n
n
r
c
e
e
t
i
a
r
3
i
t
t
n
n
“
n
n
3
i
r
a
c
r
a
i
t
a
t
g
i
t
a
h
g
t
b
b
d
d
t
i
c
c
e
e
p
n
h
n
t
e
e
n
n
a
t
e
t
t
e
o
t
i
h
i
h
g
g
h
o
p
t
i
h
a
o
a
e
e
o
e
i
e
o
n
n
a
n
p
e
e
n
n
n
o
r
r
t
r
r
t
n
e
m
o
n
p
y
y
o
p
o
e
m
h
h
e
e
t
t
n
n
i
n
w
n
i
h
a
p
o
h
a
t
r
t
o
n
r
n
r
w
r
r
r
r
r
e
e
e
e
i
i
d
w
o
a
a
w
r
n
d
t
r
n
t
.
n
n
e
i
t
e
h
r
t
h
r
c
e
i
t
t
t
t
s
r
s
t
r
.
e
”
.
e
c
h
h
t
n
n
t
h
h
o
o
h
h
i
i
l
l
u
u
e
t
o
d
d
t
.
child 1
child 2
end parent
36

Infinite Threads
forever: ‘a ® (‘a ® ‘a) ® unit • (forever x0 f) computes:
x1 =(fx0) x2 =(fx1) x3 =(fx2) …
• The values x1, x2, x3,… are discarded
• f may communicate with other threads
• This thread can be terminated by other CML primitives, otherwise it loops forever.
37

Channels
• Channel creation (for communicating values of type ‘a) – channel : unit ® ‘a chan
• Communication
–recv:‘achan ® ‘a –send:(‘achan*‘a) ® unit
• Message passing in synchronous
– Both sender and receiver must be ready to communicate.
– If one thread executes a send and no thread is ready to execute recv on the same channel, the sending thread blocks (stops and waits) for a thread to execute recv.
– Similarly, if recv is executed, it can block if there is no send. • Example
– Ifcisanintchan,thensend(c,3)sendstheinteger3on channel c. Result type is unit like an assignment.
38

• Example
ch = channel();
Channels
• Result

send/recv


spawn (fn()=> … … send(ch,0); … …);
The synchronous communication causes A and C to execute before B and D.
spawn (fn()=> … … recv ch; …
…);
39