COMP 530 Operating Systems Deadlock Don Porter Portions courtesy Emmett Witchel 1 COMP 530 Operating Systems Concurrency Issues Past lectures Problem Safely coordinate access to shared resource Solutions Use locks condition variables Coordinate access within shared objects What about coordinated access across multiple objects If you are not careful it can lead to deadlock Today s lecture What is deadlock How can we address deadlock COMP 530 Operating Systems Deadlock Motivating Examples Two producer processes share a buffer but use a different protocol for accessing the buffers Producer1 Lock emptyBuffer Lock producerMutexLock Producer2 Lock producerMutexLock Lock emptyBuffer A postscript interpreter and a visualization program compete for memory frames PS Interpreter request memory frames 10 process file request frame buffer 1 draw file on screen Visualize request frame buffer 1 display data request memory frames 20 update display COMP 530 Operating Systems Deadlock Definition Head Tail ready queue Waiting Waiting Ready Ready Head Tail Running Running semaphore condition queues A set of threads is deadlocked when every thread in the set is waiting for an event that can only be generated by some thread in the set Starvation vs deadlock Starvation threads wait indefinitely e g because some other thread is using a resource Deadlock circular waiting for resources Deadlock starvation but not the other way COMP 530 Operating Systems Resource Allocation Graph Basic components of any resource allocation problem Processes and resources Model the state of a computer system as a directed graph G V E V the set of vertices P1 Pn R1 Rm Pi Rj E the set of edges edges from a resource to a process edges from a process to a resource request edge Pi allocation edge Pk Rj COMP 530 Operating Systems Resource Allocation Graph Example A PostScript interpreter that is waiting for the frame buffer lock and a visualization process that is waiting for memory V PS interpret visualization memory frames frame buffer lock Visualization Process Memory Frames PostScript Interpreter Frame Buffer COMP 530 Operating Systems Resource Allocation Graph Deadlock Theorem If a resource allocation graph does not contain a cycle then no processes are deadlocked A cycle in a RAG is a necessary condition for deadlock Is the existence of a cycle a sufficient condition Game PostScript Interpreter Visualization Process Memory Frames Frame Buffer COMP 530 Operating Systems Resource Allocation Graph Deadlock Theorem If there is only a single unit of all resources then a set of processes are deadlocked iff there is a cycle in the resource allocation graph Memory Frames Visualization Process PostScript Interpreter Frame Buffer An Operational Definition of Deadlock COMP 530 Operating Systems Visualization Process Memory Frames Frame Buffer PostScript Interpreter A set of processes are deadlocked iff the following conditions hold simultaneously 1 Mutual exclusion is required for resource usage serially useable 2 A process is in a hold and wait state 3 Preemption of resource usage is not allowed 4 Circular waiting exists a cycle exists in the RAG COMP 530 Operating Systems Deadlock Prevention and or Recovery Adopt some resource allocation protocol that ensures deadlock can never occur Deadlock prevention avoidance Guarantee that deadlock will never occur Generally breaks one of the following conditions Mutex Hold and wait No preemption Circular wait This is usually the weak link Deadlock detection and recovery Admit the possibility of deadlock occurring and periodically check for it On detecting deadlock abort Breaks the no preemption condition And non trivial to restore all invariants What does the RAG for a lock look like COMP 530 Operating Systems Deadlock Avoidance Resource Ordering Recall this situation How can we avoid it Producer2 Lock producerMutexLock Lock emptyBuffer Producer1 Lock emptyBuffer Lock producerMutexLock Eliminate circular waiting by ordering all locks or semaphores or resoruces All code grabs locks in a predefined order Problems Maintaining global order is difficult especially in a large Global order can force a client to grab a lock earlier than it Deadlock is a global property but lock manipulation is local project would like tying up a resource for too long COMP 530 Operating Systems Lock Ordering A program code convention Developers get together have lunch plan the order of locks In general nothing at compile time or run time prevents you from violating this convention Research topics on making this better Finding locking bugs Automatically locking things properly Transactional memory 12 COMP 530 Operating Systems How to order What if I lock each entry in a linked list What is a sensible ordering Lock each item in list order What if the list changes order Uh oh This is a hard problem Lock ordering usually reflects static assumptions about the structure of the data When you can t make these assumptions ordering gets hard 13 COMP 530 Operating Systems Linux solution In general locks for dynamic data structures are ordered by kernel virtual address I e grab locks in increasing virtual address order A few places where traversal path is used instead 14 COMP 530 Operating Systems Lock ordering in practice From Linux fs dcache c Care taken to lock inode before each alias void d prune aliases struct inode inode struct dentry dentry struct hlist node p restart spin lock inode i lock hlist for each entry dentry p inode i dentry d alias spin lock dentry d lock if dentry d count dget dlock dentry d drop dentry spin unlock dentry d lock spin unlock inode i lock dput dentry goto restart spin unlock dentry d lock spin unlock inode i lock Inode lock protects list Must restart loop after modification 15 Care taken to lock inode before each aliasInode lock protects list Must restart loop after modification COMP 530 Operating Systems mm filemap c lock ordering Lock ordering i mmap lock vmtruncate private lock free pte set page dirty buffers swap lock exclusive swap page others mapping tree lock i mutex i mmap lock truncate unmap mapping range mmap sem i mmap lock page table lock or pte lock various mainly in memory c mapping tree lock arch dependent flush dcache mmap lock mmap sem lock page access process vm mmap sem i mutex msync i mutex i alloc sem various inode lock sb lock fs fs writeback c mapping tree lock sync single inode i mmap lock anon vma lock vma adjust anon vma lock page table lock or pte lock anon vma prepare