Concurrent Programming
CT074-3-2 Version 0120
What is Concurrent and Parallel
Programming?
Expectations
• Commitment from you during sessions
• Engagement in activities and labs
– Record of engagement
– EMR
CT074-3-2 Concurrent Programming
Topic & Structure of The Lesson
• Introduction to Concurrent Programming :
• Concurrency as abstract parallelism
• The challenge of concurrent programming
Introduction to Parallel Programming :
• The challenge of parallel programming
CT074-3-2 Concurrent Programming
Learning Outcomes
• At the end of this topic, You should be able
to
• Describe concurrent programs and its
advantages/disadvantages
• Describe parallel programs and its
advantages/disadvantages
CT074-3-2 Concurrent Programming
Key Terms You Must Be Able To
Use
• If you have mastered this topic, you should be able to use the following
terms correctly in your assignments and exams:
• Concurrency
• Parallelism
• Multitasking
CT074-3-2 Concurrent Programming
What is a Concurrent Program?
A sequential program has a single
thread of control.
A concurrent program has multiple
threads of control allowing it perform
multiple computations in parallel and to
control multiple external activities which
occur at the same time.
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
Concurrent and Distributed
Software?
Interacting,
concurrent software
components of a
C o m m u n ic a tio n system:
N e w
t o kr
single machine ->
shared memory
interactions
multiple machines ->
network interactions
CT074-3-2 Concurrent Programming
Why Concurrent Programming?
Performance gain from multiprocessing hardware
parallelism.
Increased application throughput
an I/O call need only block one thread.
Increased application responsiveness
high priority thread for user requests.
More appropriate structure
for programs which interact with the environment,
control multiple activities and handle multiple
events.
CT074-3-2 Concurrent Programming
The Promise of Concurrency
• Speed
– If a task takes time t on one processor, shouldn’t it
take time t/n on n processors?
• Availability
– If one process is busy, another may be ready to help
• Distribution
– Processors in different locations can collaborate to
solve a problem or work together
• Humans do it so why can’t computers?
– Vision, cognition appear to be highly parallel activities
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
Same meaning?
• Concurrency: At least two tasks are making
progress at the same time frame.
• Not necessarily at the same time
• Include techniques like time-slicing
• Can be implemented on a single processing unit
• Concept more general than parallelism
• Parallelism: At least two tasks execute literally at
the same time.
– Requires hardware with multiple processing units
CT074-3-2 Concurrent Programming
Reading a file from disk takes 5 seconds
and processing it takes 2 seconds
5 seconds reading file A
2 seconds processing file A
5 seconds reading file B
2 seconds processing file B
-----------------------
14 seconds total
CT074-3-2 Concurrent Programming
Reading a file from disk takes 5 seconds
and processing it takes 2 seconds
5 seconds reading file A
5 seconds reading file B + 2 seconds processing file A
2 seconds processing file B
-----------------------
12 seconds total
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
Concurrency vs. Parallelism
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
Do I need to know about
concurrent programming?
Concurrency is widespread but error prone.
¨ Therac - 25 computerised radiation therapy machine
Concurrent programming errors contributed to
accidents causing deaths and serious injuries.
¨ Mars Rover
Problems with interaction between concurrent
tasks caused periodic software resets reducing
availability for exploration.
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
Continue
CT074-3-2 Concurrent Programming
Slido
• If we have as much hardware as we want,
do we get as much parallelism as we wish?
• If we have 2 cores, do we get 2x speedup?
• Slido tab
CT074-3-2 Concurrent Programming
Parallel Overhead
• The amount of time required to
coordinate parallel tasks, as opposed to
do useful work.
• Examples:
– Time to start a task
– Time to terminate a task
– Synchronization time.
CT074-3-2 Concurrent Programming
Multitasking
CT074-3-2 Concurrent Programming
Multitasking
• Multitasking is a concept of performing
multiple tasks (also known as processes)
over a certain period of time by executing
them concurrently
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
Implicit and explicit concurrency
• In principle, most programs may be considered
concurrent in that they are likely to:
– contain independent processing steps (at the block,
statement, or expression level) that may be executed
in parallel; or
– trigger device operations that may proceed in parallel
with the execution of the program. This may be
termed implicit concurrency.
• Explicit concurrency is where concurrent
behavior is specified by the program designer.
CT074-3-2 Concurrent Programming
Multiple computers
• A concurrent program defines actions that
may be performed simultaneously.
• A parallel program is a concurrent program
that is designed for execution on parallel
hardware.
• A distributed program is a parallel program
designed for execution on a network of
autonomous processors that do not share
main memory
CT074-3-2 Concurrent Programming
• Thus, concurrent program is a generic
term used to describe any program
involving actual or potential parallel
behavior; parallel and distributed programs
are sub-classes of concurrent program
that are designed for execution in specific
parallel processing environments.
CT074-3-2 Concurrent Programming
Programming practice in Java
Java is
¨ widely available, generally accepted and portable
¨ provides sound set of concurrency features
Hence Java is used for all the illustrative examples,
the demonstrations and the exercises. Subsequent
lectures will explain how to construct Java programs
such as the Cruise Control System.
“Toy” problems are also used as
they exemplify particular aspects of
concurrent programming problems!
CT074-3-2 Concurrent Programming
The Challenges of Concurrency
• Concurrent programs are harder to get right
– Folklore: need at least an order of magnitude in
speedup for concurrent program to be worth the effort
• Some problems are inherently sequential
– Theory – circuit evaluation is P-complete
– Practice – many problems need coordination and
communication among sub-problems
• Specific issues
– Communication – send or receive information
– Synchronization – wait for another process to act
– Atomicity – do not stop in the middle and leave a mess
CT074-3-2 Concurrent Programming
Language Support for Concurrency
• Threads
– Think of a thread as a system “object” containing the
state of execution of a sequence of function calls
– Each thread needs a separate run-time stack
– Pass threads as arguments, return as function results
• Communication abstractions
– Synchronous communication
– Asynchronous buffers that preserve message order
• Concurrency control
– Locking and mutual exclusion
– Atomicity is more abstract, less commonly provided
slide 36
CT074-3-2 Concurrent Programming
The challenge of concurrent
programming
• Concurrent programming is difficult
– Carefully coordinate access to shared data
– Race conditions may create scheduler-dependent
bugs
– Hard to detect and reproduce
• Programming languages offer features to
support concurrent programming
– Synchronization mechanisms:
• semaphores, locks, monitors
– Still have to deal with deadlocks, granularity issues
CT074-3-2 Concurrent Programming
The challenge of concurrent
programming
• Need to synchronize the execution of
different processes and to enable them to
communicate.
CT074-3-2 Concurrent Programming
Distributed program
CT074-3-2 Concurrent Programming
• Paused
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
Back to Threads!
CT074-3-2 Concurrent Programming
Creating Threads in Java – 1st Way
A Thread class manages a single sequential thread of
control. Threads may be created and deleted
dynamically.
The Thread class executes instructions from its
method run(). The actual code executed depends on
Threads
the implementation provided for run() in a derived
run() class.
class MyThread extends Thread {
public void run() {
//......
}
}
MyThread
run() Creating a thread object:
Thread a = new MyThread();
CT074-3-2 Concurrent Programming
Creating Threads in Java
• Creating a thread in Java is done like this:
Thread thread = new Thread();
• To start the thread you will call its start()
method, like this:
thread.start();
CT074-3-2 Concurrent Programming
Creating Threads in Java – 2nd Way
Since Java does not permit multiple inheritance, we often
implement the run() method in a class not derived from
Thread but from the interface Runnable.
target
Runnable Thread
run()
Creating a thread object:
public interface Runnable
{
Thread b = new
public abstract void run(); Thread(new
} MyRun());
MyRun
run() class MyRun implements Runnable
{
public void run()
{ ........
CT074-3-2 Concurrent Programming
Operations provided by the Thread
class to control a thread :
• Once created, start() causes a thread to call its run()
method and execute it as an independent activity,
concurrent with the thread called start().
• A thread terminates when the run() method returns or
when it is stopped by stop(). This has been deprecated in
the current version of Java.
• A terminated thread may not be restarted. A thread object
is only garbage collected when there is no references to it
and it has been terminated.
• The predicate isAlive() returns true if a thread has been
started but has not yet terminated.
CT074-3-2 Concurrent Programming
Operations provided by the Thread
class to control a thread :
• When started, a thread may be currently running on the
processor, or it may be runnable but waiting to be
scheduled. A running process may explicitly give up the
processor using yield().
• sleep() causes a thread to be suspended (made non-
runnable) for a given time (specified in miliseconds) and
then automatically resume (be made runnable).
CT074-3-2 Concurrent Programming
CT074-3-2 Concurrent Programming
Thread life-cycle in Java
An overview of the life-cycle of a thread as state transitions:
new Thread() start() causes the thread to call
its run() method.
start()
Created Alive
stop(), or
st run() returns
op
()
Terminated
The predicate isAlive() can be
used to test if a thread has been started
but not terminated. Once terminated, it
cannot be restarted.
CT074-3-2 Concurrent Programming
Thread alive states in Java
Once started, an alive thread has a number of substates :
Alive
Running sl
su ee
sp p (
en )
d(
)
yield() dispatch
suspend()
start()
Runnable Non-Runnable
resume()
stop(), or
Also, wait() makes a Thread Non-Runnable, run() returns
and notify() makes it Runnable.
CT074-3-2 Concurrent Programming
Public, Protected and Private
• Access modifiers
– Public - may be accessed by any class
– Protected - by subclass
– Private - by the class itself
– No modifier - "package protected", accessed
by classes from the same package.
CT074-3-2 Concurrent Programming
Java Thread Example
public class ThreadExample {
public static void main(String[ ] args){
System.out.println(Thread.currentThread().getName());
for(int i=0; i<10; i++){
new Thread("" + i){
public void run(){
System.out.println("Thread: " + getName() + " running");
}
}.start();
}
}
}
CT074-3-2 Concurrent Programming
Java Thread Example
• First it prints out the name of the thread
executing the main() method. This thread
is assigned by the JVM. Then it starts up
10 threads and give them all a number as
name ("" + i). Each thread then prints its
name out, and then stops executing.
CT074-3-2 Concurrent Programming
Java Thread Example
• Note that even if the threads are started in
sequence (1, 2, 3 etc.) they may not execute
sequentially, meaning thread 1 may not be the
first thread to write its name to System.out. This
is because the threads are in principle executing
in parallel and not sequentially. The JVM and/or
operating system determines the order in which
the threads are executed. This order does not
have to be the same order in which they were
started.
CT074-3-2 Concurrent Programming
Question and Answer Session
Q&A
CT074-3-2 Concurrent Programming
What we will cover next
• Abstraction and Interleaving
CT074-3-2 Concurrent Programming
