Transcript Processes
OPERATING SYSTEMS DESIGN AND IMPLEMENTATION Third Edition ANDREW S. TANENBAUM ALBERT S. WOODHULL Chap. 2.3. Classical IPC Problems Chap. 2.4. Scheduling Annotated by B. Hirsbrunner, University of Fribourg, 2012 Lecture 6, 23October 2012 The Dining Philosophers Problem (1) • • • Philosophers eat/think Eating needs 2 forks Pick one fork at a time • • • How to prevent deadlock ? How to prevent livelock ? How to prevent starvation ? Fig. 2-18. Lunch time in the Philosophy Department Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 2 The Dining Philosophers Problem (2) Figure 2-19. A nonsolution to the dining philosophers problem. Fig. 2-19. A nonsolution to the dining philosophers problem Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 3 The Dining Philosophers Problem (3) ... Fig. 2-20. A solution to the dining philosophers problem Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 4 The Dining Philosophers Problem (4) ... ... Fig. 2-20. A solution to the dining philosophers problem (part 2) Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 5 The Dining Philosophers Problem (5) ... Fig. 2-20. A solution to the dining philosophers problem (part 3) Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 6 The Readers and Writers Problem (1) ... Fig. 2-21. A solution to the readers and writers problem : a writer has to wait until no more reader is active Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 7 The Readers and Writers Problem (2) ... Fig. 2-21. A solution to the readers and writers problem (part 2) Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 8 The Sleeping Barber Problem (1) 9 10 Solution to sleeping barber problem 2.4 Scheduling Process Behavior Fig. 2-22. Bursts of CPU usage alternate with periods of waiting for I/O. (a) A CPU-bound process. (b) An I/O-bound process. Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 11 When to Schedule When scheduling is absolutely required: 1. When a process exits. 2. When a process blocks on I/O, or a semaphore. When scheduling usually done (though not absolutely required) 1. When a new process is created. 2. When an I/O interrupt occurs. 3. When a clock interrupt occurs. Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 12 Scheduling Algorithms : goals Fig. 2-23. Some goals of the scheduling algorithm under different circumstances Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 13 Scheduling Algorithms: batch systems • First-Come First Served • Shortest Job First • Shortest Remaining Time Next • Three-level Scheduling : Admission, CPU, Memory Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 14 Scheduling Algorithms: interactive systems • Round-Robin • Priority Scheduling: • with priority classes • Shortest Process Next: • with aging techniques • Guaranteed Scheduling: • each of the n processes obtains 1/n CPU cycles • Lottery Scheduling • each process p obtains np tickets • … Tanenbaum & Woodhull, Operating Systems: Design and Implementation, (c) 2006 Prentice-Hall 15