[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=“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