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=“threads”or“processes”
• 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(cont’d):
• Whensomeonearrives,seatedandutables
updatedaslongasutables >0
• Firstcome,firstserve,butthosewith
reservationsmaybeseatedaheadofothers
(priority)
• Ifutables <1,peoplewaitinaqueuefortheirtable• Whenpeopleleave,utables =utables +1 6© Borna NoureddinCOMP 8551Semaphorevs.Mutex•Mutex =semaphorewithonlytwovalues•Mutex forsinglechair:onlyonepersonatatimecanbesittingatit• Semaphorefortablewithmultiplechairs,ormultipletablesinarestaurant:eachtable/chaircanonlybeoccupiedbyonegroup/person,buttherearemultipletables/chairs•Mutex moreefficientthanbinarysemaphore•Mutex canonlybeunlockedby“owner”7© 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-emptionbyotherprocessesorinterrupts•Windowsobject:• 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 waitsDeadlockprevention•Removemutualexclusioncondition• Non-blockingsynchronizationalgorithms• Noexclusiveaccesstoresource• Impossiblewithoutspooling• Notfoolproofevenwithspooling16©-2012 Borna NoureddinCOMP 8551Deadlockprevention•Remove”holdandwait”conditions• Eachprocess/threadmustrequestallresourcesallatonce(usuallyatstartup)• Verydifficultandinefficient• Alternative:releasebeforerequest(all-or-nonealgorithms– notalwayspractical)17©-2012 Borna NoureddinCOMP 8551Deadlockprevention•Usetimeouts• Onlyallowedtohaveresourceforlimitedtime• Difficulttoreinforce•Avoidcircularwaitcondition• E.g.,disableinterruptsduringcriticalsections• E.g.,useahierarchytodetermineapartialorderingofresources18©-2012 Borna NoureddinCOMP 8551Deadlockdetection• OSorresourceschedulercandetectdeadlocks• Rollbackorrestartoneormorethreads/processes• Notalwayspossible,andneverguaranteed• Generally,impossibletoknowifwaitingfor“unlikely”or“impossible”setofcircumstances 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
Reviews
There are no reviews yet.