Operating system chapter 6

صفحه 1:
Concurrency: Deadlock and Starvation Chapter 6 

صفحه 2:
Deadlock ° Permanent blocking of a set of processes that either compete for system resources or communicate with each other ° No efficient solution ° Involve conflicting needs for resources by two or more processes 

صفحه 3:
Figure 6.1 Illustration of Deadlock 

صفحه 4:
0 ل ببسيس ۲:۷ او Required Required coun sui Pans wa eae | عو لاس د د ۳ عله ا ا اج | و Figure 6.2 Example of Deadlock 

صفحه 5:
Progress 9و ۸ ‎ie) 3‏ مر ۸ ‎lease 2‏ ‎Required me ea‏ ‎aa‏ ‏8 ‎Required‏ ‎GAB 5‏ 3 ‎Progress‏ ‏رز ای 0 ‎A Require B Required‏ 520203 ‎progress pum ce Pama.‏ سس ‎B‏ هه و ‎Pend‏ ] prio of pat nxces seen and Qs wating ‘ara prton of paces seme ats Q's Wales Figure 6.3 Example of No Deadlock [BACO03] 

صفحه 6:
Reusable Resources * Used by only one process at a time and not depleted by that use * Processes obtain resources that they later release for reuse by other processes * Processors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores * Deadlock occurs if each process holds one resource and requests the other 

صفحه 7:
Example of Deadlock Process P Process Q Step Action Step __Action Po [Request Dy 7 مت رو عم رها Py Request (T) ‏بو‎ |Request D) ‎[Lock )‏ بو ‎[Lock (ry‏ وه ‎Perform function | Pesform function‏ | ير سا بو مس وه ‎Pe [Unlock (r) [Unlock (>) ‎ ‎ ‎ ‎ ‎ ‎ ‎Figure 6.4 Example of Two Processes Competing for Reusable Resources ‎ ‎ 

صفحه 8:
Another Example of Deadlock ° Space is available for allocation of 200Kbytes, and the following sequence of events occur Request 80 Kbytes; Request 70 Kbytes; Request 60 Kbytes; Request 80 Kbytes; ۰ Deadlock occurs if both processes progress to their second request 8 

صفحه 9:
Consumable Resources ° Created (produced) and destroyed (consumed) ° Interrupts, signals, messages, and information in I/O buffers ° Deadlock may occur if a Receive message is blocking ° May take a rare combination of events to cause deadlock 

صفحه 10:
Example of Deadlock ° Deadlock occurs if receive is 2 Receive(P1); Send(P1, M2); blocking Send(P2, M1); 

صفحه 11:
Resource Allocation Graphs * Directed graph that depicts a state of the system of resources and processes or 

صفحه 12:
Resource Allocation Graphs Figure ‏كن‎ Examples of Resource Allocation Graphs 

صفحه 13:
Conditions for Deadlock ° Mutual exclusion ~ Only one process may use a resource at a time ° Hold-and-wait - A process may hold allocated resources while awaiting assignment of others * No preemption ~ No resource can be forcibly removed form a process holding it 13 

صفحه 14:
Conditions for Deadlock * Circular wait - A closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chai Ra 14 

صفحه 15:
15 Ra Figure 6.6 Resource Allocation Graph for Figure 6.16 Re 

صفحه 16:
Possibility of Deadlock ° Mutual Exclusion ° No preemption ° Hold and wait 

صفحه 17:
Existence of Deadlock ° Mutual Exclusion ° No preemption ° Hold and wait ¢ Circular wait 

صفحه 18:
Deadlock Prevention ° Mutual Exclusion ~ Must be supported by the operating system ° Hold and Wait ~ Require a process request all of its required resources at one time 

صفحه 19:
Deadlock Prevention ° No Preemption ~ Process must release resource and request again ~- Operating system may preempt a process to require it releases its resources ° Circular Wait ~ Define a linear ordering of resource types 

صفحه 20:
Deadlock Avoidance ° A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead toa deadlock ° Requires knowledge of future process request 

صفحه 21:
Two Approaches to Deadlock Avoidance ° Do not start a process if its demands might lead to deadlock » Do not grant an incremental resource request to a process if this allocation might lead to deadlock 

صفحه 22:
Resource Allocation Denial ° Referred to as the banker’s algorithm ° State of the system is the current allocation of resources to process ° Safe state is where there is at least one sequence that does not result in deadlock ° Unsafe state is a state that is not safe 

صفحه 23:
Vetermination OF a 6 State Initial State ROR ORB 09 1 2 1 1 0 6 ‘Allocation marx A (@) Initial state 

صفحه 24:
Vetermination Of a sale State P2 Runs to Completion RR ORD RoR RS 2 PL PL 2 2 0 P2 P2 0|] 6 4 3 BB "3 2 Pa Pa 2 0 21 RY oR RR RY 93 5 ۳ 2 Resource vector R ‘Available vector V () P2 runs to completion 

صفحه 25:
Vetermination Of a sale State P1 Runs to Completion RI RR ‏با‎ RD RS RIOR RB 61 5 |] 6 ‏ثم ]م‎ 6|] 5 2 ] 1 6| 0 9 © | 5 ‏هم | م ]مهم‎ | o ‏هم | شم ]مهم‎ | o 3 1 4 ‏و« 1 1 2 و«‎ ] 1 0 3 4 2 ‏ب‎ 10 = (lee 1 Claim mais € ‘Allocation mavix A C-A 2 ‏ند تع بو‎ RB 3 3 8 7۳۳2 3 Resource vector R Avalable vector V (©) PL runs to completion 0 Pt 

صفحه 26:
Vetermination Of a sale State P3 Runs to Completion 2 RD Ri 1 1 0 1 #أه أه أه أن | BB 2 1 a 2 2 8 8 a o تع ‎ROR‏ ‏3 ‏7 6 هه ل (@) PS runs to completion 

صفحه 27:
27 Determination of an Unsafe State ‎R2‏ 2۲ ته جم انع 7 :۶ 9[ ه 1 ‎pe {i‏ 2 1 ]| ند 0 | 1 ا 1 1 |2 ]قم ‎rm fo | ۵ | 2 2۸ | ۸ | 2‏ ‎‘Allocation matrix A CoA‏ 22 8۱ تع ۳ 2 1 1 6 | 3 | 9 ‎Resource vector R Available vector V‏ ‎(@) Initial state ‎RIOR? ‏قتع‎ ‎3 ‎6 ‎3 ‎4 ‎ ‎ ‎w]e] wis ‎‘Claim matrix © ‎ ‎ ‎21 ‏و2 ‎Pa‏ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 28:
28 a Determination of an Unsafe State اف | ننه سم | عو PL P2 P3 P4 1 0 2 1ظ 1 1 3 قظ ‎p3 | 2 1 1‏ 2 0 م | ‎pa‏ ‎Allocation matrix A‏ قع ‎RB Rl R2‏ 6 0 1 1 Available vector V (b) P1 requests one unit each of RI and R3 R2 3 RL 9 Resource vector R 8 8 8 vfalwfel ae Claim matrix € PL P2 ‏و‎ ‎4 

صفحه 29:
29 Deadlock Avoidance Logic (a) global data structures 7 + wequest (-] > claim 12,1) sLaim+/ /+ coral veque: /* simalaze alloc */ < restore original state > © suspend process >: () resource alloc algorizhn 

صفحه 30:
Deadlock Avoidance Logic (o) seat for safety algorithm (banker's algorithm) 

صفحه 31:
Deadlock Avoidance ۰ Maximum resource requirement must be stated in advance ° Processes under consideration must be independent; no synchronization requirements e There must be a fixed number of resources to allocate ° No process may exit while holding resources 

صفحه 32:
Deadlock Detection RR RRS 2 RA RS 9 1 RS 1 1 Resource vector RD 0 Available vector 32 [2 a 8 a #| هه اه 0 Allocation matrix A PL P2 PB Pa a RO RL 196 20۳۳۰ ofolfo mE ۵ Request matrix Q Figure 6.10 Example for Deadlock Detection PL ‏و‎ ‎Pa 

صفحه 33:
Strategies once Deadlock Detected ° Abort all deadlocked processes * Back up each deadlocked process to some previously defined checkpoint, and restart all process ~ Original deadlock may occur ° Successively abort deadlocked processes until deadlock no longer exists ° Successively preempt resources until deadlock no longer exists 

صفحه 34:
Selection Criteria Deadlocked Processes ° Least amount of processor time consumed so far ° Least number of lines of output produced so far ° Most estimated time remaining ° Least total resources allocated so far ° Lowest priority 

صفحه 35:
Strengths and Weaknesses of the 6 ‏مت گنت جاگ اجیه تا‎ Table 6.1 Summary of Deadlock Detection, Prevention, and Avoidance Approaches for Operating Systems [ISLO80] Major Disadeancages موز | Fura resource ‏موه‎ ‎‘mut be knows by proceses “Preenpes:nore oftes than ‎eee‏ و سوم ‎Pune resource sequcemeats ‘ust be known by OS /Proceeres oa be locked for Tong peneds ‏موه مدوم هو مهوت ‎ ‎Major Advantages ‎Work well for processes hat perform a single bors of action Ne preemption nesesseey ‎a ‎‘whose sae con be saved andreswred easly ‎Feasible to enforce via compile sine checks ‎‘cad: no un ine computation since ‘problem is solvedin system design ‎Xo presmprion necessary ‎Never delays ‏مس‎ ‎sFaclitaes on hae hands ‎ ‎ ‎Dittrene Schemes ‏سس بر ‎Preemption ‎‘Resource ordeong ‎Manipaat to nd at feastone ste path ‎Invote pesiodcaly to ‏سيم‎ ‎ ‎‘Resource Allocation Policy ‏سای وی ‏عم موه ود ‎(eteetion ad prevention‏ ‎‘ery bert requested sources sae wanted wher porebe, ‎ ‎ ‏منود ‎۳ ‎Detection ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 36:
Dining Philosophers Nwnhlnaw. 

صفحه 37:
37 Dining Philosophers Problem 7 program senaphore f int void philosopher (int i) while (true) 0 Figure 6.12 A First Solution to the Dining Philosophers Problem 

صفحه 38:
38 Dining Philosophers Problem = (int 1) while (true) chink () (zoom) hilosopher (2), seopher (4) + Losopher (0), epher (3), ph Figure 6.13 A Second Solution to the Dining Philosophers Problem 

صفحه 39:
Dining Philosophers nD 11 0 ‘Figure 6.14 A Solution to the Dining Philosophers Problem Using a Monitor 

صفحه 40:
40 Dining Philosophers Drahlam ‘monitor dining controllers oun stazes (shinbing, ‏رون‎ eating} state[S]: اعطاق سكس كز ی هو عفر یج موم تیه ماد 1 2* ا ب مات کاب مد ‎me‏ اي لت ا ‎TH‏ ‏یتیب سوه سین مت رید 1 ماه سم مهو سي 2 ۰ شنت > دق سم مان ‎Fa ee ita pelt eee cree‏ ‎fe Gtmoltpiati's 5) 2 Eiagd‏ الت لد زتره شش ام ‎Tf‏ ‏تسس نم ی اع سيم م ست ‎Foe‏ ‏ا اق الما ‎GET‏ ‎t= eating)‏ ال 1231 1۱ ‎Leu!‏ ا 1 ‎aaa aaa REEL‏ 0 ام ‎sia‏ ‏3 ‏)د عي مه سس سب سويت عمد عر دش عم إل ساس مد عا معدم ‎Sn Siete‏ 1 ‘Figare 6.17 Ancthor Solution to the Dising Philosophers Problew Using a Mositer 

صفحه 41:
UNIX Concurrency Mechanisms ° Pipes ° Messages ° Shared memory ° Semaphores ° Signals 

صفحه 42:
Table 6.2 UNIX Signals Value Name Description 010 SIGHUP ‘Hang wp, sentto process when kernel assumes thatthe user ofthat process is doing 20 useful work o2 SIGINT Interrupt 03 ١ 51601015. ‏بانع‎ sent by user to induce halting of process and production of core dump ‏موه ...بو‎ egal instruction ‏و‎ SIGTRAP Trace tap; triggers the execution of code for process tracing ‏وه‎ SIGIOT 10T instruction ‏بو‎ SIGEMT. EMT instruction ‏وه‎ SIGFPE Floating-point exception ‏و‎ SIGKILL ‏ات‎ terminate process 10 SIGBUS Bus ertor 11 SIGSEGV _ Segmentation violation, process attempts to access location outside its virtoal address space 22 sIGsys Bad argument to system call ‏در‎ SIGPIPE Write on a pipe that has no readers attached to it 14 SIGALRM_—_ Alarm clock, issued when a process wishes to receive a Signal ater a period of time ‏كز‎ SIGTERM Software termination 16 SIGUSR1. User-defined signal 1 ‏ا‎ SIGUSR2 User-defined signal 2 18 SIGCHLD Death of achild 42 ‎SIGPWR Power failure‏ ور 

صفحه 43:
Linux Kernel Concurrency Mechanisms ° Includes all the mechanisms found in UNIX ° Atomic operations execute without interruption and without interference 

صفحه 44:
44 Linux Atomic Operations Atomic Tnteger Operations ‘At declasation: initialize an tomie_tt0 i Read integer value of ¥ Setthe valve of vt integer i Additov Subiract i ‏سوق‎ ۷ ‘Add tov Subtract 1 from» ‘Subtract fom v; return 1 i the results ere, ‏موم‎ 0 otherwise ‘Add ito v, return 1 ifthe result is negative, return 0 otherwise (used for implementing semaphores) Subtract 1 from v; cetarn 1 ifthe results zea: eran 0 othersiise ‘Add Ito v; return |i the revue ls zero: remarn 0 otherwise ‎avoale_tng_and veer (eteaiae 80‏ مد ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 45:
Linux Atomic Operations “Atomic Bitmap Operations ‘Se bit rin the bitmap pointed to by ada (Clear bit ur inthe bitmap pointed to by addr Inver bit nr inthe bitmap pointed to by addr ‘Set bit ria the bitmap pointed ro by ade: return the old bit value (Clase bit we inthe Bitmap pointed to by add return the old bit value Tver bit ar inthe Bitmap pointed te by addr: retorn the old bit value ‘Retura the value of bit ar in the bitmap pointed toby ade ‘oid ae5 IG (Int mF, veld vaadr) ‘youd clear bislant ae, void veda) youd change BLe[int #5, void vase) Tet test ond oet bie(ine ae, void Male) sod clesr Sie (ine ar, woud *=3i5) Tee reas and ange BLC(iaE ar, wold ‏وضع‎ ‎void aad)‏ عه مهل علط همع عمد ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 46:
Linux Kernel Concurrency Mechanisms * Spinlocks ~ Used for protecting a critical section ‘Table 64 Linux Spinlocks ‘Acquires the specified lock, spinning if weeded ual itis available Like spin lock, butalso daablesintemupts onthe local processor Like spin_lock_ng, bat also saves the curent intecupt sate in flags Like spin lock, but also disables the execution of all bottom halves Releases given lock Releases given lock and enables local iatemupes Releases given lock and restores local interapis fo given previows state ‘Releases given lock and enables bottom balves Initializes given spinlock “Tries to acquire specified lock: reruns nonzero if lock i currently held and zero otherwise Returns noazeo if lock is curently held and zero otherwise ‘eld abla lect lopintook_= "102k مده ع )ادنوه که [0 2007" عمتمادة) ره دوه کم 7 

صفحه 47:
‎Linux Semaphores‏ گ6 لاو ‎Traditional Semaphores Initializes the dynamically crested semaphere to the given count ‎Initializes the dynamically created semaphore with a count of I (initially locked) ‎Initializes the dymamically created semaphore with a count of 0 (initially focked) ‎Attempts to acquire the given semaphore, entering uninterruptible sleep if semaphore is unavailable ‎“Attempts to acquire the given semaphore, entering interraptible leep iF semaphore is unavailable, xetuas -ELNTR value if a signal other than the result of an ip operation is received ‎“Attempts to acquire the given semaphore, and returns a nonzero value if semaphore is unavailable ‎Releases the given semaphore ‘Reader Writer Semaphores ‎Tritalizes the dynamically crested semaphore with a count of 1 Down operation for readers ‎‘Up operation for readers ‎Down operation for writers ‎Up operation for writers ‎ ‎47 ‎saphore Yaen, int count) ‎ ‎void sena_indt tote! ‏اه موه موه دنه ‎vold‏ ‏مه" ههد و ‎ ‎۳ ‎ ‎{ne dove _tavertuptibie acruce senamhore 4 ‎Tat Gova_cxyiock[erruce wanaghore "aen) ‎void wp lacruct senanhers ‏لمعه"‎ ‎ ‏ده مومس عم موی تلو ‎veld‏ ‎ad(atracs r_semaphore, “rveen) ‎ ‎a ‎ ‎‘yeid wp_read acruct =#_senapt ‎ ‎old dows Weite(eurace wy_Semaphors, “Bex ‎2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 48:
Linux Kernel Concurrency Mechanisms Table 6.6 Linux Memory Barrier Operations ab Brevents loads from boing reordered acvous the barrier 0 Brevents stores from being reordered across the barrier 50) Prevents loads and stores from being reordered across the barrier bareier() events the compiler from reordering loads or tore: arose the herier ‏وود‎ (Oa SMP. provides ‏ط و‎ () and on UP provides abarrier () amp 0 (Qa SMP, provides «wi () and on UP provides abarrier ‎(Oa SMP. provides amb () and on UP provides abbazsiex ()‏ اطع وود ‎ ‎ ‎ ‎SMP = ymmetric multiprocessor UP = uniprocessor ‎48 ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 49:
010118 0 Synchronization ° Mutual Erimitives. locks ° Semaphores ° Multiple readers, single writer (readers/writer) locks ۰ Condition variables 

صفحه 50:
عن ان Walters (2 octets) commer (octets) Tok (rete union (4 octets) (sae pter or {ype pein 4 ott) smite et) ‘ees ture te ta =o : Ahead owner acts) (@ MUTEX leek (e) Readerfweiter lock raters (2 octets) 1 0 11 كسام walters (2 tts) count (4 octets) {Semaphore Figure 6.15. Solaris Synchronization Data Structures 

صفحه 51:
Effect on Waiting Threads Allreleased. One thread released All released Allreleased One thread released One thread released Allreleased Allreleased Allreleased All released ation Objects Set to Signaled State When ‘Thread sets the event Owning thtead or other thread releases the mmtex Semaphore count drops to zero Set time arrives or time interval expires Change oceurs in file system that ‘matches filter criteria of this object Input is available for processing LO operation completes Specified type of change ocews within physical memory Last thread terminates ‘Thread terminates Table 6.7 Windows Synchroni Definition ‘An announcement that a system event has occurred ‘A mechanism that provides mutual exclusion capabilities: equivalent toabinary semaphore A counter that regulates the ‘sumer of threads that can use a ‘A counter that records the passage of time AX notification of any file system changes A text window screea buffer (¢ &. used to handle screen IO for an, MS-DOS application) An instance of an opened file or VO device ‘A notification of changeto a memory resource ‘A program invocation, including the address space and resources required to run the program An execuable entity within a process Object Type Event Mates Semaphore ‘Waizable timer File change notification Console input Job [Memory resource notification Process Thread ها وی 6 ‎for tee tcl peace‏ ریا )ی ری یمرو بونج او ‎‘Nate Cokioad‏