COMP8551 Multithreading and multiprocessing II
COMP 8551
Advanced Games
Programming
Techniques
Realtime Issues and Multithreading II
Borna Noureddin, Ph.D.
British Columbia Institute of Technology
Review
•Overview of multithreading
•Basic definitions
•Multithreading challenges
•Race conditions
•Mutexes
2
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Overview
• Semaphores
• Critical sections
• Deadlocks
3
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Semaphore
• Protected variable or abstract data type
• Synchronization method of controlling
access by multiple processes to a common
resource
• Binary semaphore (flag): true/false or
locked/unlocked variable
• Counting semaphore: multiple access to
shared resource
4
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Semaphore
• Restaurant analogy:
• Tables = “resources”
• People = “threads” or “processes”
• Host = “semaphore”
• Host keeps track of unoccupied tables (utables)
and who is to be seated next. Very focused and
cannot be interrupted when performing duties.
• Initially, utables = # of tables
5
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Semaphore
• Restaurant analogy (cont’d):
• When someone arrives, seated and utables
updated as long as utables > 0
• First come, first serve, but those with
reservations may be seated ahead of others
(priority)
• If utables < 1, people wait in a queue for their
table
• When people leave, utables = utables + 1 6
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Semaphore vs. Mutex
•Mutex = semaphore with only two values
•Mutex for single chair: only one person at a
time can be sitting at it
• Semaphore for table with multiple chairs, or
multiple tables in a restaurant: each
table/chair can only be occupied by one
group/person, but there are multiple
tables/chairs
•Mutex more efficient than binary
semaphore
•Mutex can only be unlocked by “owner”
7
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Critical sections
General use of term (Wikipedia):
In concurrent programming a critical
section is a piece of code that accesses a
shared resource (data structure or device)
that must not be concurrently accessed by
more than one thread of execution. A critical
section will usually terminate in fixed time,
and a thread, task or process will have to
wait a fixed time to enter it (aka bounded
waiting).
8
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Critical sections
• Kernel-level (vs. application-level):
• Processes/threads cannot migrate to other
processors
• No pre-emption by other processes or interrupts
•Windows object:
• More lightweight than mutex/semaphore/event
• Can only be used within single process
• See http://msdn.microsoft.com/en-us/library/ms682530(VS.85).aspx
9
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
1
0
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Deadlocks
• One or more threads wait for resources
that can never become available
• Classic case: two threads both require two
shared resources, and use blocking
mutexes to lock them in opposite order
1
1
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Deadlocks
Thread A locks resource X
Thread B locks resource Y
Thread A attempts to lock resource Y
Thread B attempts to lock resource X
Both resources already locked (by the other thread): both
threads wait indefinitely!
Deadlocks
• Necessary conditions:
1. Mutual exclusion: a resource that cannot
be shared by more than one process
2. Hold and wait condition: processes
already holding resources may request
new resources
3. No preemption condition: only a process
holding a resource may release it
4. Circular wait condition: two or more
processes form a circular chain where
each process waits for a resource that the
next process in the chain holds
1
2
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Deadlocks
Kansas legislature:
When two trains approach each other
at a crossing, both shall come to a full
stop and neither shall start up again
until the other has gone.
1
3
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Deadlock avoidance
• Check for availability before granting
resource:
• Will system enter an unsafe state?
• System must know in advance number and
type of all resources
• E.g., Banker's algorithm
• Normally, impossible to know in advance what
every process will request
1
4
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Deadlock avoidance
• Symmetry-breaking techniques:
•Wait/Die and Wound/Wait
• Process age determined by time stamp
1
5
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Wait/Die Wound/Wait
O needs a resource held by Y O waits Y dies
Y needs a resource held by O Y dies Y waits
Deadlock prevention
•Remove mutual exclusion condition
• Non-blocking synchronization algorithms
• No exclusive access to resource
• Impossible without spooling
• Not foolproof even with spooling
1
6
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Deadlock prevention
•Remove "hold and wait" conditions
• Each process/thread must request all
resources all at once (usually at startup)
• Very difficult and inefficient
• Alternative: release before request (all-
or-none algorithms – not always
practical)
1
7
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Deadlock prevention
•Use timeouts
• Only allowed to have resource for
limited time
• Difficult to reinforce
•Avoid circular wait condition
• E.g., disable interrupts during critical
sections
• E.g., use a hierarchy to determine a
partial ordering of resources
1
8
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Deadlock detection
• OS or resource scheduler can detect
deadlocks
• Roll back or restart one or more
threads/processes
• Not always possible, and never guaranteed
• Generally, impossible to know if waiting for
“unlikely” or “impossible” set of
circumstances 1
9
©
-2
01
2
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
2
0
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
Additional Reading
http://en.wikipedia.org/wiki/Semaphore_(programming)
http://en.wikipedia.org/wiki/Critical_section
http://msdn.microsoft.com/en-us/library/ms682530(VS.85).aspx
http://www.drdobbs.com/high-performance-computing/225400066
Review
• Semaphores
• Critical sections
• Deadlocks
2
1
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
2
2
©
B
or
na
N
ou
re
dd
in
C
O
M
P
85
51
E N D