INTRO TO OPERATING SYSTEMS
INTRO TO OPERATING SYSTEMS CS 333
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 101 page Class Notes was uploaded by Orrin Rutherford on Tuesday September 1, 2015. The Class Notes belongs to CS 333 at Portland State University taught by Jonathan Walpole in Fall. Since its upload, it has received 18 views. For similar materials see /class/168271/cs-333-portland-state-university in ComputerScienence at Portland State University.
Reviews for INTRO TO OPERATING SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/01/15
CS 333 Introduction to Operating Systems Class 7 Deadlock Jonathan Walpole Computer Science Portland State University Resources and Deadlocks a Processes need access To resources in order To make progress a Examples of compuTer resources prinTers Tape drives kernel daTa sTrucTures process amp file Table enTries lockssemaphores To proTecT criTicaI secTions a Suppose a process holds resource A and requesTs resource B aT The same Time anoTher process holds B and requesTs A boTh are blocked and remain so This is deadlock Resource Usage Model u Sequence of evenTs required To use a resource requesT The resource like acquiring a muTex lock use The resource release The resource like releasing a muTex lock u MusT waiT if requesT is denied block busy waiT fail wiTh error code Preempfable vs Nonpreempfable Resources u Preemp rable resources z can be Taken away from a process wi rh no ill effects a Nonpreemp rable resources z will cause The process To fail if Taken away a Deadlocks occur when processes are granted exclusive access ro nonpreemp rable resources and wait when The resource is not available Definition of Deadlock A sef of processes Is deadlocked if each process in fhe sef is waifing for an evenquot fhaf only anofher process in fhe sef can cause a Usually The event is The release of a currently held resource a None of The processes can be awakened run 4 release resources Deadlock conditions a A deadlock situation can occur if and only if The following conditions hold simultaneously MuTual exclusion condiTion resource assigned To one process Hold and waiT condiTion processes can geT more Than one resource No preempTion condiTion Circular waiT condiTion chain of Two or more processes musT be waiTing for resource from nexT one in chain Resource acquisition scenarios Thread A acquire resource1 use resource1 release re eurce1 Exalee var r1mutex Mutex rlmutexLock Use resource1 rlmutexUnlock Resource acquisition scenarios Thread A acquire resource1 use resource1 release resource Another Exalee var r1sem Semaphore r1sem Up r1sem Down Use resource1 r 1s em Up Resource acquisition scenarios Thread A Thread B acquire resource1 acquire resource2 use resourcel use resource2 release resource1 release resource2 Resource acquisition scenarios Thread A Thread B acquire resource1 use resourcel release resource1 acquire resource2 use resource2 release resource2 N0 deadlock can occur here Resource acquisition scenarios 2 resources Thread A Thread B acquire resource1 acquire resource1 acquire resource2 acquire resource2 use resources 1 amp 2 use resources 1 amp 2 release resource2 release resource2 release resource1 release resource1 Resource acquisition scenarios 2 resources Thread A Thread B acquire resource1 acquire resource1 acquire resource2 acquire resource2 use resources 1 amp 2 use resources 1 amp 2 release resource2 release resource2 release resource1 release resource1 N0 deadlock can occur here Resource acquisition scenarios 2 resources Thread A Thread B acquire resource1 acquire resource2 use resources 1 use resources 2 release resource1 release resource2 acquire resource2 acquire resource1 use resources 2 use resources 1 release resource2 release resource1 Resource acquisition scenarios 2 resources Thread A Thread B acquire resource1 acquire resource2 use resources 1 use resources 2 release resource1 release resource2 acquire resource2 acquire resource1 use resources 2 use resources 1 release resource2 release resource1 N0 deadlock can occur here Resource acquisition scenarios 2 resources Thread A Thread B acquire resource1 acquire resource2 acquire resource2 acquire resource1 use resources 1 amp 2 use resources 1 amp 2 release resource2 release resource1 release resource1 release resource2 Resource acquisition scenarios 2 resources Thread A Thread B acquire resource1 acquire resource2 acquire resource2 acquire resource1 use resources 1 amp 2 use resources 1 amp 2 release resource2 release resource1 release resource1 release resource2 Deadlock is possible Examples of deadlock u Deadlock occurs in a single program z Programmer creaTes a siTuaTion ThaT deadlocks Kill The program and move on z NoT a big deal a Deadlock occurs in The OperaTing SysTem z Spin locks and locking mechanisms are mismanaged wiThin The OS z Threads become frozen z SysTem hangs or crashes z MusT resTarT The sysTem and kill and applicaTions Other examples of deadlock Resource Allocation Graphs ProcessThread El Resource Allocation Graphs ProcessThread is held by 20 Resource Allocation Graphs Resource ProcessThread is requesting 21 Resource Allocation Graphs 22 Resource Allocation Graphs Deadlock 23 Resource Allocation Graphs Deadlock a cycle in The graph 24 MuliTple uniTs of a resource u Some resources have only one uniT z Only one Thread aT a Time may hold The resource PrinTer Lock on ProcessTable u Some resources have several uniTs z All uniTs are considered equal any one will do Page Frames Dice z A Thread requesTs quotkquot uniTs of The resource z Several requesTs may be saTisfied simulTaneously 25 Dealing with deadlock a Four general strategies z Ignore the problem Hmm advantages disadvantages 4 Detection and recovery 4 Dynamic avoidance through resource allocation z Prevention by structurally negating one of the four conditions 26 Deadlock detection 1 resource of each a Let The problem happen then recover a How do you know it happened a Do a depthfirs rsearch on The resource allocation graph in W 5 143 ampL3 L In HLN A nu a u Inna I 3quot l g39 139 a Hquot l quot 391quot 1ij 1 l 23 2ng A A y 5 l j J a v m A 5 J a v l g 3 quotlt quot 393 3973 Tb 1 7 quot 39 a 39 r 553 m E 1quot t quot5 IV 3 1 lo 27 Deadlock detection 1 resource of each a Let The problem happen then recover a How do you know it happened a Do a depthfirs rsearch on The resource allocation graph l l 3f 45 L E39 W 1 1 a e M r L quota T r mt a J 239 v o V as Isl l l All g at MI E 1 5 we us Ear is 28 Deadlock detection 1 resource of each a Let The problem happen then recover a How do you know it happened a Do a depthfirs rsearch on The resource allocation graph 395 r E g L L a u n 39 V a f a 27quot 1 mm a i 39 g 1 L r I quot 391quot 2 quotlg J iii 39 3 H 3 amp I T j a g a il V i a 1 in e5 w 39L J la 29 Deadlock detection 1 resource of each a Let The problem happen then recover a How do you know it happened a Do a depthfirs rsearch on The resource allocation graph 39a M 5 39l or 174quot 1 l 1 if R M I FL El f V l 5m 1 quotif 2 Jquot 39 fl 325 is 30 Deadlock detection 1 resource of each a Let The problem happen then recover a How do you know it happened a Do a depthfirs rsearch on The resource allocation graph 31 Deadlock modeling with multiple resources u Theorem If a graph does nof confain a cycle fhen no processes are deadlocked z A cycle in a RAG is a necessary condi rion for deadlock z Is if a sufficient condi rion 32 Deadlock modeling with multiple resources u Theorem If a graph does nof confain a cycle fhen no processes are deadlocked z A cycle in a RAG is a necessary condi rion for deadlock z Is if a sufficient condi rion 33 Deadlock defection multiple resources Ev zir 39 1 um quotmam z39w 39JL m quot f 15 4 mj e gagzmic mam a c a tuz We 39 39 39 1 5739 39 2r quot5 quotgri 393 53 z 1 gquot 2 u v w i quotJig 711 a 6 g 3 39 y 4 N I wu quotu rd ilwz39e fIdg39 39Ev39 39r LH39lt 3 I 441 i w v qu 31 i 34 Deadlock defection multiple resources To139al resource vec139or r N h i l 64 2 39 lt mals f SFZ zillih39 mm 1313 f u 5 r a f 39 new Maw u r u x 4 n dquot N gt5W 963 w 1 quotqurri 9 y r 39 4 a 39 I 39 E39w w mmquot W 52 l fzamhtluu Ts rum 5 WEE3 x Available resource vec139or i 39 xll ti K VlEll G 1 s v S 39hu Mg 4 a swj Flextaxi mai w n flaw 2 132 n rS39 Hour 1 I n y 333335 2 m a 35 Deadlock defection multiple resources Total resource vector Available resource VCC I39OP v NE 39 yn d h i 64 s k 39 lt 2413 513 139 MinivhquotE U 1513 l quot quot19 V15 39u39 z inn3 t5 v39 1 r 39 F 15 9quot 4423 a Apy i u r If If i 39 W ya 1 5W 3 5 a 7 J i m d A M an 5 R P Yquot 5 w I h 3 In hum x5quot v 1 x 5 3 1 J W f39ni aquot I 18 J Sii s quot dw39e atlu rww g 4 3 fx 5 133315435 In g f x 39 4 What I have now What I am requesting now 36 Example a Is There a sequence of running process such That all The resources will be returned quotQ 59 fa 65 lt15 Q o bl 3959 5 9 0 59 l as as Q as g Q E I 4 2 3 1 l A 2 1 D O 0 Current allocation matrix 0 Cl 1 C 2 0 Cl C 1 2 Request matrix 201 R10 D 210 0 80 3 40 37 Detection algorithm 1 Look for an unmarked process Pi for which the 1th row of R is less than or equal to A 2 If such a process is found add the ith row of C to A mark the process and go back to step 1 3 If no such process exists the algorithm terminates If all marked no deadlock 38 Detection algorithm Current allocatian matrix D t 001 C2200 0120 Request matrix I II N XM 0 O I Dag 1 D O 39 Detection algorithm 6 a a 1 a 36 0 55 063 3 ekcvquot 55 0amp9 QQ Q xo c399 09 59 2 9 Cb OQ E 4 2 3 1 u A t 2 1 O O Current allocation matrix Request matrix 0 O 1 D C 2 O D 1 D 1 2 O 4O Detection algorithm 5 5 4 59 1 4339 52 2 63 965 0 Q e9 QK J r2 5 c2lt9 E 1 4 2 3 1 A t 2 1 0 0 Current allocation matrix Re uest matrix D t 001 C2200 D120 41 Detection algorithm 51 5 4 459 63 he 4 G3 atg a QB OQQ ES 616 Q E 4 2 3 1 A t 2 1 0 0 j 2 2 2 0 Current allocation matrix O 0010 322001 012 42 Detection algorithm Currentallocatian matrix 1 D D t 39B l E S 00 C220 Request matrix 2 U 1 quotI 1 D 392 1 5 639 0 R D 43 Detection algorithm Current allocation matrix A2 1 2 2 2 0 4 2 2 1 Request matrix 2 0 D 1 Rzv o 1 u 2 1 a e 44 Detection algorithm Current allocation matrix 0010 CZ39Q H t i E a Request matrix 2001 Rzv D 1 u No deadlock 45 Deadlock de139ec139ion issues a How often should The algorithm run 4 Af rer every resource reques r z Periodically When CPU u riliza rion is low z When we suspec r deadlock because some rhread has been asleep for a long period of Time 46 Recovery from deadlock a What should be done To recover z Abor r deadlocked processes and reclaim resources 4 Temporarily reclaim resource if possible z Abor r one process a r a Time un ril deadlock cycle is elimina red u Where To start z Low priori ry process z How long process has been execu ring 4 How many resources a process holds 4 Ba rch or in rerac rive 4 Number of processes Tha r mus r be Termina red 47 Other deadlock recovery Techniques a Recovery through rollback 4 Save state periodically take a checkpoint start computation again from checkpoint z Done for large computation systems 48 Deadlock avoidance u De rec rion vs avoidance z De rec rion op rimis ric approach Alloca39l39e resources quotBreakquot system To fix i1 4 Avoidance pessimistic approach Don39139 alloca39l39e resource if it may lead to deadlock If a process requests a resource make if wait until you are sure it39s OK 4 Which one To use depends upon The applica rion 49 Processresource Trajectories t1 t2 t3 t4 ProcessA time 50 Processresource Trajectories Requests Printer Requests CDR W Releases Printer Releases CDR W t1 t2 t3 i4 7 me Process A 51 Processresource Trajectories time Process B we hgr Ne 21 52 Processresource Trajectories OE Releases CDR W Requests Printer m tz Requests CDRW 8 t Y 3 X tW 53 Processresource Trajectories time NH Process B hgr NH 2H t1 t2 t3 t4 ProcessA time 54 Processresource Trajectories m t 8 Z Both processes t Process A 55 Processresource Trajectories time Both processes hold Printer 7 7 t1 t2 t3 Process A t4 time 56 Processresource Trajectories time Forbidden Zone Process A 57 Processresource Trajectories time 7 t4 tlme Trajectory showing system progress 58 Processresource Trajectories a tZ 7 V B makes progroess t A ls not runnmg tw 7 t1 t2 t3 t4 39 me Process A 59 Processresource Trajectories m sf a A a time 1 Pro 3 4 Brequests the CDR W 60 Processresource Trajectories m t I t 5 t Re t 39 t B m X WW ques ls gran e tw t1 t2 t3 t4 39 me ProcessA 61 Processresource Trajectories A runs amp makes no t I V a request for printer g tZ r m t f 9 t1 t2 t3 t4 7 me Process A 62 Processresource Trajectories m a www m t f u t1 t2 t3 39 time Process A Request is granted A proceeds 63 Processresource Trajectories time B runs amp requests the printer MUST WAIT e t1 t2 t3 t4 39 tlme Process A 64 Processresource Trajectories A runs amp requests 39 the CDRW m t f u Process A 65 Processresource Trajectories A holds printer m requests CDRW Rammew E tY requests printer t f u t1 t2 t3 t4 39 me ProcessA 66 Processresource Trajectories A holds printer requests CDRW If Rammew a tY requests printer tX f quot4 W DEADLOCK t1 t2 t3 t4 39 me ProcessA 67 Processresource Trajectories E A danger occurred here on g iiviakei i Ziii tw fun quot5 t1 t2 t3 t4 time Process A 68 Processresource Trajectories m w m t t2 t3 rocess A t4 This area is unsafe 39 time 69 Processresource Trajectories g KWithin the unsafe area deadlock is inevitable m t We don t want to V V e s 0a ma e E t A wait at this point t2 t3 39 tlme Process A t4 7O Processresource Trajectories m t a W B requests the printer t t t t B releases CDRW 1 2 3 4 B releases rlnter Process A L p then A runs to completion 71 Safe states u The current state which processes hold which resourcesquot a A safe state 4 No deadlock and z There is some scheduling order in which every process can run to completion even if all of them request their maximum number of units immediately a The Banker39s Alqorithm z 600 Avoid unsafe states When a process requests more units should the system grant the request or make it wait 72 The Banker39s Algorithm u Assumptions z Only one Type of resource wi rh mul riple uni rs z Processes declare Their maximum po ren rial resource needs ahead of Time a When a process requesfs more unifs should fhe sysfem make if waif f0 ensure safe fy Example One resource type with 10 units it if 32 I 7533 39233 r j 1 g fg y I i 5 F 6 e 2 4 5 53 r3 2 2 3 2 j z i i 39 2 A a Jr J g r a l i 1 39 I39mquot 3 l I t KM 23 quot quotuu J 73 Safe states a Safe state when system is not deadlocked and there is some scheduling order in which every process can run to completion even if all of them suddenly request their maximum number of resource immediately 10 total 39 r quot n W F v a n l N an V I Mimi 15 3473 3 H55 xgt s 23 5 Mth I its wlrf 39 7 39 39 U 7 A 14 n 5 c 2 k 3 z I 5 2 l 5quot a s v 6 EA 39 l r v n v 393 quot l2 4 b l p L1 quot39 l 393 3 p is 2 quot quot a r 439 39rn hr 9quot 39 IS 9 ft quot l i d J in r l M 9 m a it A Jin39n 74 Unsafe states 10 Total My mum39s Wax Ham h six s 34 Li I E 393 a 2 j 4 quot M w 5 a M 39W Al a rquot 5quot 5 k f J 3 mins 2 171m Unsafe f c 39 ni39 Avoidance with multiple resource Types c 39 quot ww 3 i uu f3die 9quot M i i E d e m39mil u J n 39 v 1 a a 1 we 1 I n L h i 39I 39 39 l a quot 39 r u39 J m I kg p I1l 39 qiu 3913 q I A A eJLETEETJ ail lLafEigtil 15111 39 EBALEML f39TWiL A a W M 9 3 1 395 91 an 3114233 quotkid w 1 f Hung I39m395 H 39 a J r le r 1quot 1 39 1 5M 1 I u n 39H39 J 15 39 Mr E g I H vi Ii E39 W 33 if 43 11 t tquot I39 I I U39 y l 1 I a J a n 3 I u y I I 8 s i l l Ii 3 J I 39 M M 3 7quotquot w I u u quot u quot1 quot1 39f quot quot 39 M f i a 7n n 1 25 m f a w quotpm 2 quot 3 v C r A 439 mm L e 39 htlv HEM at 131am gwi s l x i Note These are the max gossible requests which we assume are known ahead of time 76 Banker39s algorithm for multiple resources El Look for a row R whose unmet resource needs are all smaller than or equal to A If no such row exists the system will eventually deadlock since no process can run to completion El Assume the process of the row chosen requests all the resources that it needs which is guaranteed to be possible and finishes Mark that process as terminated and add all its resources to A vector El Repeat steps 1 and 2 until either all process are marked terminated in which case the initial state was safe or until deadlock occurs in which case it was not 77 Avoidance modeling Total resource vector Available resource vector quotm amid am quotr m g HEP rm d h i a k 39 lt LJLL 33 all ICim a piequot3 o 13113 Maximum Request Vector 34 531 3 2 9 fig 3 3 H30 1 V39n I I u A 51quot Xquot 3 quotquot39a 5 far 3 quot rie 39 91 quotquot3quot u r If g quotr quoti S 9 55 5 n1 Jvmi he i 39 3 71 FEET n I n f 4 73 min 39r tjw Iquot 13239Iihi i39lstw Row 2 is what process 2 might need 4 r RUNALGORITHM ONEVERY RESOURCE REQUEST 78 Avoidance algorithm Current allocatian matrix 0 001 C2200 0120 Max request matrix 200 RZTD1D 2100 79 Avoidance algorithm 6 e NAP 4f 63 quot2quot 459 r5 6 o 0 9 b 5 0 0 E4 2 3 1 A 2 1 0 0 Currentallocatian matrix Max requesi matrix 0 0 1 D C 2 2 D D T D 1 2 O 80 Avoidance algorithm 393 5 ca 857quot c a 6663 65 0 9 3 g39x c r2 5 O 9 E 4 2 3 1 A t 2 1 0 0 Current allocatian matrix Ma requesi matrix O 0010 322001 012 81 Avoidance algorithm 6 ca 57quot 539 363 Q 0 55 0 9 3 5 0 59 0 K E4 2 3 1 A 2 1 0 0 2 2 2 0 Currentallocatian matrix Ma requesi matrix 0 0 1 D C 2 2 O D T D 1 2 O 82 Avoidance algorithm Current allocation matrix 1 D 0 396 1 2 6 00 320 5 392 G S3 69 0 6 Q 0 13925 4quot lt2 63quot 0 Max request matrix 2 D 1 quotI 1 D 392 1 6 639 0 R D 83 Avoidance algorithm Current allocation matrix 010 CZqLLQ D l Max request matrix 200 REA QA Q 392 1 6 639 84 Deadlock avoidance u Deadlock avoidance is usually impossible z because you don39T know in advance wha r resources a process will need a Alternative approach deadlock preventionquot 4 Preven r The si rua rion in which deadlock mlth occur for all Time z A r rack one of The four condi rions rha r are necessary for deadlock To be possible 85 Deadlock avoidance u Conditions necessary for deadlock Mu ruol exclusion condi rion Hold and wai r condi rion No preemption condi rion Circular wai r condi rion 86 Attacking the conditions u Attacking mutual exclusion z a bad idea for some resource types z may work for others a Attacking no preemption z a bad idea for some resource types z may work for others 87 Attacking the conditions u Attacking hold and wait z Require processes to request all resources before they begin 4 Process must know ahead of time 4 Process must tell system its max potential needsquot 88 Attacking the conditions u If a process decides it wants more than its initial declared needs it must z Release all resources 4 Give the system a new max potential needsquot 4 Resume execution u Issues z Underallocation of resources z Resource needs not known in advance 89 Attacking the conditions a Attacking circular wait 4 Number each of the resources z Require each process to acquire lower numbered resources before higher numbered resources 4 More precisely A process is not allowed to request a resource whose number is lower than the highest numbered resource it currently holds 90 Recall This example of deadlock Thread A Thread 3 acquire resource1 acquire resource2 use resources 1 amp 2 release resource2 release resource1 acquire resource2 acquire resource1 use resources 1 amp 2 release resource1 release resource2 Assume that resources are ordered 1 2 3 Resource1 Resource2 e rc 91 Recall This example of deadlock Thread A Thread 3 acquire resource1 acquire resource2 acquire resource2 acquire resource1 use resources 1 amp 2 use resources 1 amp 2 release resource2 release resource1 release resource1 release resource2 u Assume that resources are ordered a 1 Resource1 u 2 Resource2 a 3 e rc a Thread B violates The ordering 92 Why Does Resource Ordering Work u Assume deadlock has occurred a Process A holds X z reques rs Y a Process B holds Y z reques rs Z a Process C holds Z z reques rs X 93 Why Does Resource Ordering Work u Assume deadlock has occurred a Process A z holds X z reques rs Y a Process B z holds Y z reques rs Z a Process C holds Z z reques rs X 94 Why Does Resource Ordering Work u Assume deadlock has occurred a Process A holdsx 4 reques rsY a Process B z holds Y z reques rs Z a Process C z holds Z z req ues rs X 95 Why Does Resource Ordering Work u Assume deadlock has occurred a Process A z holds X z reques rs Y a Process B z holds Y z reques rs Z a Process C z holds Z z req ues rs X 96 Why Does Resource Ordering Work u Assume deadlock has occurred a Process A z holds X This is impossibe z reques rs Y a Process B holds Y z reques rs Z a Process C z holds Z z req ues rs X 97 Why Does Resource Ordering Work a Assume deadlock has occurred a Process A z holds X This is impossibe z reques rs Y Therefore 12 assump an musf be fase a Process B holds Y z reques rs Z a Process C z holds Z z req ues rs X 98 Resource Ordering u The chief problem z If is hard 7 0 come up wit7 an ordering of the resources that everyone finds acceptable u Still I believe this is particularly useful within an OS 1 ProcessControlBlock 2 FileControl Block 3 Page Frames u Also the problem of resources with multiple units is not addressed 99 A word on starvation a Starvation and deadlock are two different thi ngs With deadlock no work is being accomplished for the processes that are deadlocked because processes are waiting for each other Once present it will not go away z With starvation work progress is getting done however a particular set of processes may not be getting any work done because they cannot obtain the resource they need 100 Quiz a What is deadlock a What conditions must hold for deadlock to be possible a What are the main approaches for dealing with deadlock u Why does resource ordering help 101
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'