4003-440-02 Operating Systems I Module 5. Concurrent Design Issues -- Lecture Notes Prof. Alan Kaminsky -- Winter Quarter 2012 Rochester Institute of Technology -- Department of Computer Science The Dining Philosophers Problem Invented by Tony Hoare (based on a problem by Edsger Dijkstra) to illustrate certain issues that arise when designing concurrent (multi-threaded) programs   The story line -- forks, or spoons?   Package edu.rit.os1 Class DP1 -- source code   Demonstration   Issues Deadlock Starvation Deadlock Definition: A set of blocked threads, each of which cannot make progress until one of the others makes progress   The wait-for graph   Necessary conditions for deadlock Mutual exclusion No preemption (no backtracking) Cycle in the wait-for graph Implies threads are holding resources while blocking waiting to acquire other resources (hold-and-wait)   Techniques for dealing with deadlock . . .   Deadlock prevention: Design the program so deadlock is impossible in the first place Always acquire resources in the same order in all threads; prevents cycles in the wait-for graph Package edu.rit.os1 Class DP2 -- source code   Deadlock avoidance: Avoid entering an unsafe state Precursor to a deadlock state The system is not yet deadlocked, but all subsequent actions lead inexorably to a deadlock State diagram Package edu.rit.os1 Class DP3 -- source code   Deadlock detection: Let deadlocks happen; an outside deadlock detector breaks the deadlock Deadlock detector must abort one of the deadlocked threads, or preempt the resources a deadlocked thread is holding Package edu.rit.os1 Class DP4 -- source code Starvation Definition: A thread is starved if the thread could make progress but it never does make progress, because of other threads' actions   Starvation for execution on the CPU A thread could run on the CPU but never does because other threads always run on the CPU instead For example, a high-priority thread will starve low-priority threads The operating system's CPU scheduling algorithm must deal with starvation (to be studied later) A thread can explicitly "yield" the CPU to cause a context switch to another thread if possible   Starvation for access to a resource A thread is trying to acquire a semaphore but never does because other threads always acquire the semaphore instead Deal with this by putting threads waiting for access into a queue and granting access in FIFO order   Package edu.rit.os1 Class DP5 -- source code Operating Systems I • 4003-440-02 • Winter Quarter 2012 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2008 Alan Kaminsky. All rights reserved. Last updated 27-Aug-2008. Please send comments to ark­@­cs.rit.edu.