1CSC 4103 - Operating SystemsFall 2009Tevfik Ko!arLouisiana State UniversityOctober 13th, 2009Lecture - XIVMidterm ReviewMidterm ExamOctober 15th, Thursday 3:10pm-4:30pm @1112 Patrick Taylor HallChapters included in the Midterm Exam• Ch. 1.1-1.10 (Introduction)• Ch. 2.1-2.8 (OS Structures)• Ch. 3.1-3.4 (Processes)• Ch. 4.1-4.4 (Threads)• Ch. 5.1-5.3 (CPU Scheduling)• Ch. 6.1-6.7 (Synchronization)• Ch. 7-1-7.7 (Deadlocks)1 & 2: Overview• Basic OS Components• OS Design Goals & Responsibilities• OS Design Approaches• Kernel Mode vs User Mode• System Calls• Virtual Machines43. Processes• Process Creation & Termination• Context Switching• Process Control Block (PCB)• Process States• Process Queues & Scheduling• Interprocess Communication54. Threads• Concurrent Programming• Threads vs Processes• Threading Implementation & Multi-threading Models• Other Threading Issues– Thread creation & cancellation– Signal handling– Thread pools– Thread specific data65. CPU Scheduling• Scheduling Criteria & Metrics• Scheduling Algorithms– FCFS, SJF, Priority, Round Robing– Preemptive vs Non-preemptive– Gantt charts & measurement of different metrics• Multilevel Feedback Queues• Estimating CPU bursts76. Synchronization• Race Conditions• Critical Section Problem• Mutual Exclusion• Semaphores• Monitors• Classic Problems of Synchronization– Bounded Buffer– Readers-Writers– Dining Philosophers– Sleeping Barber87. Deadlocks• Deadlock Characterization• Deadlock Detection– Resource Allocation Graphs– Wait-for Graphs– Deadlock detection algorithm• Deadlock Avoidance• Deadlock Recovery9Exercise Questions1011Question 112Question 213Question 314Question 3 (cont)Question 4 Which processor scheduling algorithm results in the shortest average waiting time. Justify your answer.15Question 5Explain why Round-Robin scheduling tends to favor CPU bound processes over I/O bound ones.16Question 6 CPU scheduling quanta have remained about the same over the past 20 years, but processors are now about 1,000 times faster. Why haven’t CPU scheduling quanta changed?17Question 7List 4 events that might occur to cause a user process to be context switched off the processor.18Question 8Assume S and T are binary semaphores, and X, Y, Z are processes. X and Y are identical processes and consist of the following four statements: P(S); P(T); V(T); V(S) And, process Z consists of the following statements: P(T); P(S); V(S); V(T) Would it be safer to run X and Y together or to run X and Z together? Please justify your answer.19Question 9Remember that if the semaphore operations Wait and Signal are not executed atomically, then mutual exclusion may be violated. Assume that Wait and Signal are implemented as below:Describe a scenario of context switches where two threads, T1 and T2, can both enter a critical section guarded by a single mutex semaphore as a result of a lack of atomicity.20void Signal (Semaphore S) {S.count = S.count + 1;}void Wait (Semaphore S) {while (S.count <= 0) {}S.count = S.count - 1;}Question 10•Given a system that provides binary semaphores (semaphores whose values is either 0 or 1). Show the code to implement counting semaphores using binary semaphores.21Question 11Consider the following set of processes:PS: Lower priority numbers mean higher priority. (eg. 1-highest, 5-lowest)(a) Draw Gantt charts illustrating the execution of these processes using the following algorithms: 1. Priority (Non-preemptive)2. Priority (Preemptive):22!Question 11 (cont.)b) What is the waiting time of each process for each of the scheduling algorithms in Part a? c) What is the turnaround time of each process for each of the scheduling algorithms in Part a? 23Question 122425Question 1326Question 13 (cont)27Question
View Full Document