Operating Systems
Lecture #9: Concurrent Processes
Written by David Goodwin
based on the lecture series of Dr. Dayou Li
and the book Understanding Operating Systems 4th ed.
by I.M.Flynn and A.McIver McHoes (2006)
Department of Computer Science and Technology,
University of Bedfordshire.
Operating Systems, 2013
15th April 2013
Outline
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
1 Introduction
Configurations
Programming
Threads
2 Configurations
3 Programming
4 Threads
Operating Systems
24
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction 3
Configurations
Programming
Threads
Introduction
Operating Systems
24
What is parallel processing?
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction 4
Configurations
Parallel processing (also called multiprocessing)
Programming situation in which two or more procesors operate in unison
Threads i.e. two or more CPUs are executing instructions
simultaneously
each CPU can have a RUNNING process at the same time
Process manager must coordinate each processor
Process manager must synchronise the interaction among
CPUs
enhance throughput and increase computing power
Operating Systems
24
What is parallel processing?
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire Example: Information Retrieval System
Processor 1
Introduction 5
accepts a query
Configurations
checks for errors
Programming
passes request to Processor 2
Threads
Processor 2
searches database for required information
Processor 3
retrieves data from database (if kept off-line in secondary
storage)
data placed where Processor 2 can get it
Processor 2
passes information to Processor 4
Processor 4
routes the response back to the originator of the request
Operating Systems
24
Benefits
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire Increased reliability
Introduction 6 more than one CPU
Configurations if one fails, others can absorb the load
Programming failing processor must inform other processors
Threads
OS must re-structure its resource allocation strategies
faster processing
instructions processed two or more at a time
allocate CPU to each job
allocate CPU to each working set
subdivide individual instructions, called concurrent
programming
Challenges:
How to connect the processors in configurations?
How to orchestrate their interaction?
Operating Systems
24
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
Configurations 7
Programming
Threads
Configurations
Operating Systems
24
Master/Slave configuration
Lecture #9
Concurrent Processes
David Goodwin
Master/Slave configuration is asymmetric
University of
Bedfordshire
Introduction Essentially a single processor with additional “slaves”
Configurations 8
Master processor responsible for managing entire system
Programming
maintains status of processes, storage management, schedules
Threads
work for slave processors, executes all control programs.
suited for environments with front-end interactive users, and
back-end batch job mode
Operating Systems
24
Master/Slave configuration
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction Advantage:
Configurations 9
Simplicity
Programming
Threads
Disadvantage:
Reliability no higher than for single processor (if master fails
the whole system fails)
Poor use of resources (if matser is busy, slave must wait until
master becomes free until it can be assigned more work)
Increases the number of interrupts (slaves must interrupt the
master every time they need OS intervention e.g. IO
requests), creating long queues at the master processor
Operating Systems
24
Loosely Coupled configuration
Lecture #9
Concurrent Processes Loosely Coupled system features several complete computing
David Goodwin
University of
systems
Bedfordshire each has its own memory, IO devices, CPU, and OS
Introduction each processor controls its own resources
Configurations 10
each processor can communicate and cooperate with others
Programming
job assigned to one processor, and will remain there until
Threads
finished
job scheduling based on several requiremenyts and policies
(new jobs may be assigned to the processor with lightest
load)
Operating Systems
24
Loosely Coupled configuration
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
Configurations 11
Programming Advantage:
Isn’t prone to catastrophic system failures (when a processor
Threads
fails, others can continue work independently)
Disadvantage:
Difficult to detect when a processor has failed
Operating Systems
24
Symmetric configuration
Lecture #9
Concurrent Processes
David Goodwin Symmetric configuration best implimented if processors are
University of
Bedfordshire
the same type
Processor scheduling is decentralised
Introduction
Single copy of OS and a globqal table listing each process
Configurations 12
Programming
and its status (stored in a common area of memory)
Threads
Each processor uses the same scheduling algorithm
If interrupted, processor updates process list and finds
another to run (processors are kept busy)
Any given job can be executed on several processors
Presents a need for process synchronisation
Operating Systems
24
Symmetric configuration
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
Configurations 13 Advantage:
Programming
Reliable
Threads
Uses resources effectively
Balance loads well
Can degrade gracefully in the event of a failure
Disadvantage:
Processors must be well synchronised to avoid problems of
races and deadlocks
Operating Systems
24
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
Configurations
Programming
Threads
14 Programming
Operating Systems
24
Concurrent Programming Applications
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
Configurations
Programming 15
Multiprocessing can refer to one job using several processors
Threads This requires a programming language and computer system
that can support it, called concurrent processing system
Most programming languages are serial - instructions
executed one at a time
To resolve and arithmetic expression, every operation is done
in sequence
Operating Systems
24
Concurrent Programming Applications
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
Example:
Configurations A = 3 ∗ B ∗ C + 4/(D + E) ∗ ∗(F − G)
Programming 16
Threads
step Operation Result
1 (F − G) Store difference in T1
2 (D + E) Store sum in T2
3 (T1 ) ∗ ∗(T2 ) Store power in T1
4 4/(T1 ) Store quotient in T2
5 3∗B Store product in T1
6 (T1 ) ∗ C Store product in T1
7 (T1 ) + (T2 ) Store sum in A
Operating Systems
24
Concurrent Programming Applications
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Arithmetic expressions can be processed differently if we use a
Introduction
language that allows concurrent processing
Configurations
Define COBEGIN and COEND to indicate to the compiler
Programming 17
Threads
which instructions can be processed concurrently
COBEGIN
T1 = 3 ∗ B step proc. Operation Result
T2 = D + E 1 1 3∗B Store difference in T1
T3 = F − G 2 (D + E) Store sum in T2
COEND 3 (F − G) Store difference in T3
COBEGIN
2 1 (T1 ) ∗ C Store product in T4
2 (T2 ) ∗ ∗(T3 ) Store power in T5
T4 = T1 ∗ C
3 1 4/(T5 ) Store quotient in T1
T 5 = T 2 ∗ ∗T 3
4 1 (T4 ) + (T1 ) Store sum in A
COEND
A = T 4 + 4/T 5
Operating Systems
24
Concurrent Programming Applications
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
Configurations
Increased computational speed
Programming 18
increased complexity of programming language
Threads
increased complexity of hardware (machinary and
communication among machines)
programmer must explicitly state which instructions are to be
executed in parallel, called explicit parallelism
solution: automatic detection by the compiler of instructions
that can be performed in parallel, called implicit parallelism
Operating Systems
24
Case 1: Array Operations
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
To perform an array operation within a loop in three steps,
Configurations
Programming 19
the instruction might say:
Threads for(j=1;j<=3;j++)
a(j)=b(j)+c(j);
If we use three processors, the instruction can be performed
in a single step:
processor#1 performs: a(1)=b(1)+c(1)
processor#2 performs: a(2)=b(2)+c(2)
processor#3 performs: a(3)=b(3)+c(3)
Operating Systems
24
Case 2: Matrix Multiplication
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction To perform C = A ∗ B where A and B represent two
Configurations matricies:
Programming 20 1 2 3 1 2 3
Threads A = 4 5 6 , B = 4 5 6
7 8 9 7 8 9
Several elements of a row of A are multiplied by the
corresponding elements of the column in B.
Serially, the answer can be computed in 45 steps (5 × 9)
With three processors the answer takes only 27 steps,
multiplying in parallel (3 × 9)
Operating Systems
24
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Introduction
Configurations
Programming
Threads 21
Threads
Operating Systems
24
Threads & Concurrent Programming
Lecture #9
Concurrent Processes
David Goodwin
University of We have considered cooperation and synchronisation of
Bedfordshire
traditional processes (known as heavyweight processes):
require space in main memory where they reside during
Introduction
Configurations
execution
may require other resources such as data files or IO devices
Programming
Threads 22
pass through several states: ready, running, waiting, delayed,
blocked
this requires an overhead from swapping between main
memory and secondary storage
To minimise overhead time, impliment the use of threads
defined as a smaller unit within a process, that can be
scheduled and executed (uses CPU)
each has its own processor registers, program counter, stack
and staus, but shares the data area and resources allocated
to its process
Operating Systems
24
Threads States
Lecture #9
Concurrent Processes
David Goodwin
University of
The same operations are performed on both traditional
Bedfordshire processes and threads.
Introduction The OS must be able to support:
Configurations
Creating new threads
Programming
Setting up a thread so it is ready to execute
Threads 23
Delaying, or putting to sleep, threads for a specific amount of
time
Blocking, or suspending, threads that are waiting for IO to
complete
Setting threads to wait state until specific event
Scheduling threads for execution
Synchronising thread execution using semaphores, events, or
conditional variables
Terminating a thread and releasing its resources
This is done by the OS tracking critical information for each
thread
Operating Systems
24
Thread Control Block
Lecture #9
Concurrent Processes
David Goodwin
University of
Bedfordshire
Just as processes are represented by Process Contol Blocks
Introduction
Configurations
(PCBs), threads are represented by Thread Contol Blocks
Programming
(TCBs):
Threads 24 Thread ID: unique identifier assigned by OS
Thread State: changes as the thread progresses though
execution
CPU information: how far the thread has executed, which
instruction is being performed, what data is begin used
Thread Priority: used by Thread Scheduler to determine
which thread should be selected for the ready queue
Pointer: to the process that created the thread
Pointers: to other threads created by this thread
Operating Systems
24
