程序代写代做代考 algorithm chain COMP8551 Multithreading and multiprocessing II

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