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