------------------------------------------------------ Lecture 14 - March 05, 2003 ------------------------------------------------------ AGENDA: 0 Admin 1 P4 discussion (problem 2.38 in text) 2 Ch 3.3: deadlock ------------------------------------------------------ 0 - ADMIN ------------------------------------------------------ Startout Q: What is grep and how can you use it for P4? Today: * RI #4 (there was no official RI last week) Friday: * HM #4: questions 3.7, 3.8, 3.10, 3.13, 3.16 Monday * P4 due ------------------------------------------------------ 1 - P4 DISCUSSION (PROBLEM 2.38 IN TEXT) ------------------------------------------------------ How to create a boot diskette image a) use raread from MS-XXXX (available on the MINIX CD) b) use dd from UNIX $ dd if=/dev/floppy of=imageName bs=1k count=1440 // if means Input File, of means Output File // bs means Block Size, count is number of records Get the F4 part working first. * Notice that F1 and F2 do interesting things? Where are they defined in the kernel? Where do the messages get actually passed in the kernel? * That would be a good place to count them Have separate row/col for each task, MM, and FS. Put all others into an aggregate row/col. ----------------------------------------------------- 2 - CH 3.3 DEADLOCK ------------------------------------------------------ The cause of "bad hair day syndrome" in the O/S world (groans strictly optional) Some people approach O/S as though it were all just about things like scheduling, page replacement algorithms, and deadlock avoidance/recovery. Why study this stuff? These are important topics, but I personally don't find them to be particularly exciting. On the other hand, they are important topics. Messing up can cause you much more trouble than just a bad hair day. To quote Tanenbaum on the topic, "At this point both processes are blocked and will remain so forever. This situation is called a deadlock. Deadlocks are not a good thing to have in your system." What if you're never going to write O/S software? You may never write O/S software, but the whole deadlock thing is a big deal in database work, and I'll bet that any of you who are Systems expect to occasionally run into a database. :-) So learn how to work with them so that you are aware of the issues and can deal with them as necessary, then move on. RESOURCES What is a resource? * We refer to anything that must have been granted for exclusive use as a resource. Are resources sharable? * Some resources - such as a hard disk - are easily shared simultaneously between processes. Others, such as printers, are not easily shared simult. Can I take candy (resources) away from a process? * Preemptable resources: can be taken away from the owner with no ill effects. E.g., memory. * Nonpremptable resources: CANNOT be taken away from owner with no ill effects. E.g., printer. Will the baby (process) cry loudly if I do? * it is relatively easy to recover when there is a fight to access preemptable resources. * deadlocks generally involve nonpreemptable rsrc. Say you want to use a resource. How do you go about it? Usage sequence is (quick rocket science alert!) 1) request resource 2) use resource 3) release resource What if someone else has the candy right now? If the request cannot be currently met, have a couple options: 1) block until available 2) request fails and return to caller DEADLOCK What is a deadlock? * A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. So what's the problem? * The event that will move forward a process can only be caused by one of the blocked (typically, sleeping) processes. Conditions for deadlock 1) Mutual exclusion condition * Each resource is either currently assigned to exactly one process or is available. 2) Hold and wait condition * Processes currently holding resources granted earlier can request new resources. 3) No preemption condition * Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them. 4) Circular wait condition * There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain. All 4 conditions must be present. Note: just because we manage to avoid deadlock, it doesn't mean that all processes ended up happy. It only guarantees that we didn't have a deadlock. You could end up with downright unhappy processes (e.g., a killed process) or grumpy ones (you ran them sequentially, which can greatly reduce turnaround time, depending on I/O-instruction mix). DEADLOCK MODELING Model using directed graphs * fig. 3-7, p. 169 How can we use this to detect deadlock? * look for a cycle. Cycle => deadlock. !Cycle => !deadlock Look at fig 3-8 p. 171 Strategies for dealing with deadlock. 1) Ignore the problem 2) Detection and recovery 3) Dynamic avoidance by careful resource allocation 4) Prevention, by structurally negating one of the four required conditions * What do you think of them? Are any never workable? What are the pros & cons? THE OSTRICH ALGORITHM What's this? * Mathematicians have a "hissy-fit" * Engineers do the stats and weight the odds * People who avoided learning about deadlocks say "Problem? What problem?" * UNIX & MINIX - process slot example. - Ignore problems on assumption that users prefer an occasional deadlock to rules severely restricting what they can do. - High price to pay if want to be deadlock-free. DEADLOCK DETECTION AND RECOVERY How would you implement this? * System monitors requests and releases of resources. * Updates resource graph and check for cycles. * If cycle occurs, play "whack-a-process" until the problem goes away. * Alternatively, check every so often and kill any processes that have been blocked for more than a chosen time limit (e.g., 1 hour). What are the implications of just whacking a process? Besides possibly frustrated users, are there bigger problems? * Discuss checkpointing. DEADLOCK PREVENTION Make deadlocks structurally impossible by imposing restrictions on processes. What sorts of restrictions might work? * Anything that guarantees that at least one of the four deadlock conditions cannot be satisfied. Attacking mutual exclusion * Does this work? * Can avoid some problems by spooling (printer, email) - only have one device then that requests resource - not all resources can be managed via spooling (e.g., what would it mean to spool process table?) - also, spooling can cause problems because the spooling itself requires resources (disk space) Attacking the "hold resources while asking for more" * Could require that all processes request all resources at startup and never make another request. * Any problems with this? - many processes don't know what they will need ahead of time - suboptimal resource usage * Could require process to give up all resources when asking for new resources. Only gets original back if succeeds in getting new resources. Attacking the "no preemption" condition Workable? * Taking printer away from a job in the middle of a job is not a really good solution. * Same for a number of other resources. Attacking the "circular wait" condition Several possibilities * No process can hold more than one resource at any given moment. - Must release current resource to get another. * Global numbering of resources - fig 3-9 p. 174 - all requests must be made in ascending numerical order. - How does this help? - One process always holds the highest numbered resource. It cannot issue any requests that block. It will at some point finish and free up its resources. * Will everybody be happy? - Nope. It avoids deadlock, but some processes will be really disappointed, frustrated, etc. Summary: fig 3-10 p. 175 COS 421 - Lecture Notes #14 SPRING 2003 COS421-lect-2003-03-05.doc Page 7 Printed 05.03.03