[SOLVED] algorithm chain COMP8551 Multithreading and multiprocessing II

COMP8551 Multithreading and multiprocessing II

COMP8551
AdvancedGames
Programming
Techniques

Realtime Issues and Multithreading II

Borna Noureddin, Ph.D.
British Columbia Institute of Technology

Review
Overviewofmultithreading

Basicdefinitions

Multithreadingchallenges

Raceconditions

Mutexes

2

B

or
na

N

ou
re

dd
in

C
O

M
P

85
51

Overview

Semaphores

Criticalsections

Deadlocks

3

B

or
na

N
ou

re
dd

in
C

O
M

P
85

51

Semaphore
Protectedvariableorabstractdatatype
Synchronizationmethodofcontrolling
accessbymultipleprocessestoacommon
resource
Binarysemaphore(flag):true/falseor
locked/unlockedvariable
Countingsemaphore:multipleaccessto
sharedresource

4

B

or
na

N
ou

re
dd

in
C

O
M

P
85

51

Semaphore
Restaurantanalogy:
Tables=resources
People=threadsorprocesses
Host=semaphore
Hostkeepstrackofunoccupiedtables(utables)
andwhoistobeseatednext.Veryfocusedand
cannotbeinterruptedwhenperformingduties.
Initially,utables =#oftables

5

B

or
na

N
ou

re
dd

in
C

O
M

P
85

51

Semaphore
Restaurantanalogy(contd):
Whensomeonearrives,seatedandutables
updatedaslongasutables >0
Firstcome,firstserve,butthosewith
reservationsmaybeseatedaheadofothers
(priority)
Ifutables <1,peoplewaitinaqueuefortheirtable Whenpeopleleave,utables =utables +1 6 Borna NoureddinCOMP 8551Semaphorevs.MutexMutex =semaphorewithonlytwovaluesMutex forsinglechair:onlyonepersonatatimecanbesittingatit Semaphorefortablewithmultiplechairs,ormultipletablesinarestaurant:eachtable/chaircanonlybeoccupiedbyonegroup/person,buttherearemultipletables/chairsMutex moreefficientthanbinarysemaphoreMutex canonlybeunlockedbyowner7 Borna NoureddinCOMP 8551CriticalsectionsGeneraluseofterm(Wikipedia):In concurrentprogramming a criticalsection isapieceof code thataccessesasharedresource(datastructureordevice)thatmustnotbeconcurrentlyaccessedbymorethanone threadofexecution.Acriticalsectionwillusuallyterminateinfixedtime,andathread,taskorprocesswillhavetowaitafixedtimetoenterit(akaboundedwaiting).8 Borna NoureddinCOMP 8551Criticalsections Kernel-level(vs.application-level): Processes/threadscannotmigratetootherprocessors Nopre-emptionbyotherprocessesorinterruptsWindowsobject: Morelightweightthanmutex/semaphore/event Canonlybeusedwithinsingleprocess Seehttp://msdn.microsoft.com/en-us/library/ms682530(VS.85).aspx9 Borna NoureddinCOMP 855110-2012 Borna NoureddinCOMP 8551Deadlocks Oneormorethreadswaitforresourcesthatcanneverbecomeavailable Classiccase:twothreadsbothrequiretwosharedresources,anduseblockingmutexestolocktheminoppositeorder11-2012 Borna NoureddinCOMP 8551DeadlocksThreadAlocksresourceXThreadBlocksresourceYThreadAattemptstolockresourceYThreadBattemptstolockresourceXBothresourcesalreadylocked(bytheotherthread):boththreadswaitindefinitely!Deadlocks Necessaryconditions:1. Mutualexclusion:aresourcethatcannotbesharedbymorethanoneprocess2. Holdandwaitcondition:processesalreadyholdingresourcesmayrequestnewresources3. Nopreemptioncondition:onlyaprocessholdingaresourcemayreleaseit4. Circularwaitcondition:twoormoreprocessesformacircularchainwhereeachprocesswaitsforaresourcethatthenextprocessinthechainholds12-2012 Borna NoureddinCOMP 8551DeadlocksKansaslegislature:Whentwotrainsapproacheachotheratacrossing,bothshallcometoafullstopandneithershallstartupagainuntiltheotherhasgone.13-2012 Borna NoureddinCOMP 8551Deadlockavoidance Checkforavailabilitybeforegrantingresource: Willsystementeranunsafestate? Systemmustknowinadvancenumberandtypeofallresources E.g.,Banker’salgorithm Normally,impossibletoknowinadvancewhateveryprocesswillrequest14-2012 Borna NoureddinCOMP 8551Deadlockavoidance Symmetry-breakingtechniques:Wait/DieandWound/Wait Processagedeterminedbytimestamp15-2012 Borna NoureddinCOMP 8551Wait/Die Wound/WaitO needs a resource held by Y O waits Y diesY needs a resource held by O Y dies Y waitsDeadlockpreventionRemovemutualexclusioncondition Non-blockingsynchronizationalgorithms Noexclusiveaccesstoresource Impossiblewithoutspooling Notfoolproofevenwithspooling16-2012 Borna NoureddinCOMP 8551DeadlockpreventionRemove”holdandwait”conditions Eachprocess/threadmustrequestallresourcesallatonce(usuallyatstartup) Verydifficultandinefficient Alternative:releasebeforerequest(all-or-nonealgorithms notalwayspractical)17-2012 Borna NoureddinCOMP 8551DeadlockpreventionUsetimeouts Onlyallowedtohaveresourceforlimitedtime DifficulttoreinforceAvoidcircularwaitcondition E.g.,disableinterruptsduringcriticalsections E.g.,useahierarchytodetermineapartialorderingofresources18-2012 Borna NoureddinCOMP 8551Deadlockdetection OSorresourceschedulercandetectdeadlocks Rollbackorrestartoneormorethreads/processes Notalwayspossible,andneverguaranteed Generally,impossibletoknowifwaitingforunlikelyorimpossiblesetofcircumstances 19-2012 Borna NoureddinCOMP 855120 Borna NoureddinCOMP 8551AdditionalReadinghttp://en.wikipedia.org/wiki/Semaphore_(programming)http://en.wikipedia.org/wiki/Critical_sectionhttp://msdn.microsoft.com/en-us/library/ms682530(VS.85).aspxhttp://www.drdobbs.com/high-performance-computing/225400066Review Semaphores Criticalsections Deadlocks21 Borna NoureddinCOMP 855122 Borna NoureddinCOMP 8551E N D