Transcript Critical Section

Concurrent Execution of
Programs
An Overview
Copyright © 1997 – 2014 Curt Hill
MultiTasking
• Multitasking is the apparent
execution of programs in parallel
• This supports parallel execution
usually under one of these names
– Tasks
– Processes
– Threads
• This can be accomplished with a
single processor or with several
processors
Copyright © 1997 – 2014 Curt Hill
• Process
Definitions
– An executable program to the OS
– Sole possession of code and variable
memory
– Must communicate through the OS
• Thread
– Independent execution within a
process
– Share code and variables within a
process
• These work in Win32 and UNIX
• Tasks can be either
Copyright © 1997 – 2014 Curt Hill
UniProcessing
• Single CPU, but apparent multiple
tasks
• Permissive
– Any system call allows the current task
to be suspended and another started
• Preemptive
– A task is suspended when it makes a
system call that could require waiting
– A time slice occurs
Copyright © 1997 – 2014 Curt Hill
Multiple Processors
MultiProcessing
• Real multiprocessing involves
multiple CPUs
• Multiple CPUs can be executing
different jobs
• They may also be in the same job, if
the OS allows
Copyright © 1997 – 2014 Curt Hill
Half Way: HyperThreading
• The Hyper Threading CPUs are a
transitional form
• There is one CPU with two register
sets
• The CPU alternates between
registers in execution thus giving
better concurrency than a
uniprocessor
• Windows XP considers it two CPUs
Copyright © 1997 – 2014 Curt Hill
Why is this important?
• The multi-core CPUs are here
• The heat problem:
– Smaller means Faster means Hotter
– Heat kills semiconductors
• More speed may be obtained with
multiple cores
• Four slower CPUs on a chip will be
faster and cooler than one
– The multiple cores share memory
Copyright © 1997 – 2014 Curt Hill
Manufacturer’s Offerings
• AMD and Intel both offered in 2005
– Initially targeted server and work
stations
– Client machines are now out
– The Pentium Processor Extreme Edition
– AMD Opteron
• Sun, IBM and others expected
momentarily
• Microsoft changed its license to be
per chip, so that a multi-core chip is
considered one processor
Copyright © 1997 – 2014 Curt Hill
Off to the Races
• Most programming languages are
Sequential
• There are a number of kinds of
errors that can occur when there
are two simultaneously executing
tasks that share anything
• When different results may be
obtained by the same code and data
because of time dependencies, this
is called a race
Copyright © 1997 – 2014 Curt Hill
Instruction Granularity
• With UniProcessing (and
HyperThreading) most instructions
are indivisible
– The instruction that is started is
finished before the time slice is allowed
to interrupt the current task
– Certain long instructions such as string
operations may be interrupted and
resumed without problem
Copyright © 1997 – 2014 Curt Hill
Instruction Granularity
• With MultiProcessing even
instructions are not indivisible
– The memory could have been changed
by the other CPU between the time the
instruction started and the instruction
ended
• A statement in a high level language
is usually multiple machine language
instructions
Copyright © 1997 – 2014 Curt Hill
Race Example
• Consider two tasks that share an
integer variable share
• Task A has
– share = share + 2;
• Task B has
– share = share + 5;
Copyright © 1997 – 2014 Curt Hill
Racing Form
•
•
•
•
;share += 2
mov ax,share
add
ax,2
mov share,ax
•
•
•
•
;share += 5
mov ax,share
add
ax,5
mov share,ax
There are three possible outcomes
Copyright © 1997 – 2014 Curt Hill
Race Results
• If one task completes before the
other starts share will have 7 added
to it
• If A starts and is interrupted, then
the add of two is kept and the add of
five is lost
• If B starts first and is interrupted,
then the add of five is kept and the
add of two is lost
Copyright © 1997 – 2014 Curt Hill
Classical Problems
• There are a number of problems that
illustrate race errors
• The first is the producer and
consumer problem
• One task fills a buffer and another
empties it
• This problem is inside every file
copy
• Consider the Producer and
Consumer problem:
Copyright © 1997 – 2014 Curt Hill
Producer and Consumer
Problem
Remove point
Add point
Length
Copyright © 1997 – 2014 Curt Hill
• A buffer exists
char buf[80]; int len,strt,end;
• A process adds a char:
if(len<80){
end=(end+1)%80;
buf[end] = inchar;
len=len+1;
}
• A process empties:
if(len>0) {
strt = (strt+1)%80;
outchar = buf[strt];
len=len-1;
}
Copyright © 1997 – 2014 Curt Hill
Producers and Consumers
• The critical thing here is the len
variable
• What happens if they both try to
store to that variable at the same
time?
• The assignment statement is not a
single machine language statement
in all cases
• Caching only complicates things in a
multi CPU system
Copyright © 1997 – 2014 Curt Hill
The Experiment
• Two threads do this:
– Increment count1
– Two assignments
– Increment count2
• Three threads compare count1 and
count2 and stop if they are not equal
• Each thread sleeps for a short time
• Measurement is how many
comparisons occur before a
difference in the comparison is
found
Copyright © 1997 – 2014 Curt Hill
The participants
• Three machines:
– A single Pentium
– A hyper-threading Pentium
– Dual Pentium
• The three different machines had three
different operating systems and three
different clock speeds
• While the program is running it
appears to fully consume the CPU in all
cases
Copyright © 1997 – 2014 Curt Hill
The results
UniProc Hyper Dual
Thread Chip
Multi
Core
Mean
compares
145.4 45.3
29.8
170.3
Median
compares
72
4
19.5
13
Max
compares
688
1135 329
5800
N
52
52
57
84
Copyright © 1997 – 2014 Curt Hill
Solutions
• In the producer and consumer
problem what is needed is a
serialization
• A Critical Section is a piece of code
that has limitation as to how many
processes can be in it
• A critical section is usually guarded
by a Semaphore
• Consider the increment/decrement
of len a critical section
Copyright © 1997 – 2014 Curt Hill
Semaphore
• Named after communication flag
• It usually is a count of processes in
the critical section
• When a task enters the section it
increments the count and
decrements it upon exit
• A task wanting to enter a critical
section is either given access to the
section or made to wait
Copyright © 1997 – 2014 Curt Hill
Waiting
• If a semaphore prohibits entry the
task must wait
• Two kinds of wait:
– Busy wait - spin in a loop
– Idle wait - suspended until later
• This wait time keeps a multi CPU
system from reaching its true
potential, especially while in the
dispatcher
Copyright © 1997 – 2014 Curt Hill
Wait Problems
• A critical section guarded by a
semaphore is a special case of
resource allocation
• In order for a task to complete it has
to ask for and receive a resource
– If it cannot, it is forced to wait
• This however allows for other
problems
Copyright © 1997 – 2014 Curt Hill
Deadlock
• Situation where tasks cannot get the
resources they need
• Task A has resource 1 and is waiting
for resource 2
• Task B has resource 2 and is waiting
for resource 1
• Both are waiting for a situation that
cannot be resolved
Copyright © 1997 – 2014 Curt Hill
The Dining Philosophers
Problem
h
Copyright © 1997 – 2014 Curt Hill
The Dining Philosophers
Problem
• There is a round table with five
philosophers, five plates of
spaghetti and five forks
• A philosopher must have two forks
to eat
• If at the same time they each reach
out and take the fork nearest their
right hand there is deadlock
Copyright © 1997 – 2014 Curt Hill
Traffic Deadlock
Copyright © 1997 – 2014 Curt Hill
Deadlock
• Is it a programmer problem or a
operating system problem?
• Both.
Copyright © 1997 – 2014 Curt Hill
Operating System
Response
• Operating system should be able to
detect a deadlock
• Usual solution is to cancel jobs until
something can proceed
• Ability to reclaim a resource also
required
Copyright © 1997 – 2014 Curt Hill
Programmer Planning
• Programmer should avoid situations
that might lead to it:
• Do not wait for a resource while
holding a resource
Copyright © 1997 – 2014 Curt Hill