Transcript 14 Concurency

Concurrency
• Architecture Types
• Tasks
• Synchronization
– Semaphores
– Monitors
– Message Passing
• Concurrency in Ada
• Java Threads
1
Motivations for Studying Concurrency
• Many real-world situations involve concurrency
– ~80% of software produced
• Multiple-core processors are now widely used
– Even on PCs
• Very useful, but different way of programming
2
Multiprocessor Architecture Types
• Late 1950s
– 1 general-purpose processor, and
– 1+ special-purpose I/O processors
• Early 1960s
– Multiple complete processors
– Program-level concurrency
• Mid-1960s
– Multiple partial processors
– Instruction-level concurrency
• Architecture Types
– SIMD (Single-Instruction Multiple-Data)
– MIMD (Multiple-Instruction Multiple-Data)
• Synchronized Independent processors
• Unit-level concurrency
3
Categories of Concurrency
• A thread
– Sequence of program points reached as program runs
• Physical concurrency
– Multiple independent processors
• Multiple threads
• Logical concurrency, Quasi-concurrency
– Time-sharing of one processor
• Software designed as if there were multiple threads
– Coroutines
• Single thread
4
Tasks
• A task or process
– A program unit that executes concurrently with other program
units
• Task differs from a subprogram
– May be started implicitly
– The program unit that starts it may not be suspended
– When a task ends, control may not return to the caller
• A heavyweight task
– Runs in its own address space
• A lightweight task
– Runs in the same address space as other tasks
• A disjoint task
– Is completely independent from any other tasks
5
Task Synchronization
• Controls the order in which tasks execute
• Two kinds
– Cooperation synchronization
• A task must wait for another task to complete some activity
• E.g., the producer-consumer problem
– Competition synchronization
• Two or more tasks use shared resource
• Usually provided by mutually exclusive access
• Synchronized task communication is provided by
– Shared nonlocal variables
– Parameters
– Message passing
6
Task Execution
• A scheduler controls task execution
– Maps tasks onto available processors
• Task Execution States
– New – created, but not yet started
– Ready - ready to run, but currently not running
• No available processor
– Running
– Blocked – did run, but can't continue now
• Waiting for an event
– Dead - no longer active
7
Liveness and Deadlock
• Liveness
– A program unit will eventually continue its execution
• No problem in sequential code
• In a concurrent environment, liveness can be easily lost
• Deadlock
– All tasks lose their liveness
8
Concurrency Design and Mechanisms
• Design Issues
–
–
–
–
Competition and cooperation synchronization
Controlling task scheduling
How and when tasks start and end
How and when are tasks created
• Mechanisms
– Semaphores
– Monitors
– Message Passing
9
Semaphores
• Dijkstra - 1965
• A semaphore
– Data structure with a counter and a queue of task descriptors
– Two operations
• wait
• release
– Guards access to shared data
• Incorrect use of semaphores can cause fatal errors
– In cooperation synchronization
• E.g., buffer overflow
– In competition synchronization
• E.g., deadlock
10
Monitors
• Ada, Java, C#
• The idea
– Encapsulate the shared data and its operations to
restrict access
• A monitor
– An abstract data type for shared data
– Shared data is not the client units
– All accesses are managed by the monitor
• Only one task is allowed to access data at a time
• If the monitor is busy all other tasks requesting access are
waiting in a queue
11
Cooperation Synchronization
• Cooperation between processes is still a programming task
– Code must guarantee that a shared buffer does not underflow or overflow
Program
Process
SUB1
Monitor
Process
SUB1
Insert
Process
SUB1
Remove
Process
SUB4
B
U
F
F
E
R
12
Evaluation of Monitors
• A better way to provide competition
synchronization than are semaphores
• Semaphores can be used to implement monitors
• Monitors can be used to implement semaphores
• Cooperation synchronization is similar to
semaphores
– It has the same problems
13
Message Passing
• The idea
–
task communication is like seeing a doctor
• most of the time she waits for you, or
• you wait for her
• only when you are both ready, you rendezvous
• A general concurrency model
– Not just for competition synchronization
– Can implement semaphores
– Can implement monitors
14
Rendezvous
• Message passing must
– Let a task indicate that it is accepting messages
– Remember tasks waiting to have their message
accepted
– Provide a fair way of choosing the next message
• Rendezvous
– Message transmission from the sender task to the
receiver task
15
Message-Passing in Ada 83
• Tasks have specification and body parts
– Like packages
• The specification defines the entry points
task Task_Example is
entry entry_name (Item : in Integer);
end Task_Example;
• The body describes the actions during a rendezvous
– accept clauses correspond to the entry points in the spec
accept entry_name (formal parameters) do
…
end entry_name
16
Message-Passing in Ada 83 (cont.)
• The task executes till the accept clause then
waits for a message
• The sender is suspended during execution of
the accept clause,
• The parameters of accept can transmit
information in either or both directions
• Every accept clause has an associated queue
to store waiting messages
17
Server and Actor Tasks
• A server task
– Has only accept clauses
• An actor task
– Has no accept clause
• An actor task can send messages to other tasks
• A sender must know the entry name of the
receiver, but not vice versa
– Asymmetric
18
Graphical Representation of a Rendezvous
Task A
Accept clauses
JOB1
Body
Accept clauses
JOB2
B. JOBS3 (Value)
Accept clauses
JOB3
Accept clauses
JOB4
Task B
Body
19
Concurrency in Ada 95
• Ada 95 has two additional features
• Protected objects
– A more efficient way of accessing shared data
without rendezvous
• Asynchronous communication
20
Protected Objects
• A protected object is like an abstract data type
• Access to a protected object
– Either through message passing,
– Or through protected subprograms
• A protected procedure
– provides mutually exclusive read-write access
• A protected function
– provides concurrent read-only access
21
Asynchronous Communication
• Asynchronous select structures
• Two triggering alternatives
– The entry clause is triggered when sent a
message
– The delay clause is triggered when its time
limit is reached
22
Evaluation of Ada
• Message passing is powerful and general
• Protected objects are a better way to provide
synchronized shared data
• Message passing is a better concurrency model
for truly distributed systems
23
Java Threads
• The concurrent unit are run() methods in a Thread
– run() can be in concurrent execution with other threads
– run() is called indirectly, through start()
Class MyThread extends Thread
public void run () {…}
}
…
Thread thread = new MyThread ();
thread.start();
24
Thread Control
• Methods in the Thread class control the
execution of the thread
– yield()
• Voluntarily surrenders the processor
– sleep()
• Blocks the thread
– join()
• Waits until another thread's run() is completed
– setPriority()
• Changes the thread's priority
25
Competition Synchronization in Java
• Only one of the synchronized methods can run on the
same object
public synchronized void deposit(int i) {…}
public synchronized int fetch() {…}
• If another synchronized method is called on the same
object it has to wait in a queue
– While obj.deposit() runs, obj.fetch() must wait
• A synchronized method has exclusive access to
instance variables
• A synchronized statement synchronizes only a part
of a method
synchronized (expression) statement
– The expression determines to which object is the statement
synchronized
26
Cooperation Synchronization in Java
• Cooperation synchronization in Java is achieved using
the methods wait(), notify(), and notifyAll()
– Because the methods are defined in the root class Object,
they are available for all objects
• wait() must be called in a loop
• notify() tells one waiting thread that the event it was
waiting for has happened
• The notifyAll() method awakens all of the threads
on the object’s wait list
27
Java’s Thread Evaluation
• Java’s support for concurrency is relatively
simple but effective
• Not as powerful as Ada’s tasks
28