Lecture 14 - Midterm Review.keynote

Midterm ExamCSE 421/521 - Operating SystemsFall 2011October 20th, Thursday9:30am-10:50am@215 NSCLecture - XIVMidterm ReviewTevfik KoşarUniversity at BuffaloOctober 18th, 20111Chapters included in the Midterm Exam Ch.Ch.Ch.Ch.Ch.Ch.Ch.1234567(Introduction)(OS Structures)(Processes)(Threads)(CPU Scheduling)(Synchronization)(Deadlocks)1 & 2: Overview Basic OS ComponentsOS Design Goals & ResponsibilitiesOS Design ApproachesKernel Mode vs User ModeSystem Calls43. Processes 4. ThreadsProcess Creation & TerminationContext SwitchingProcess Control Block (PCB)Process StatesProcess Queues & SchedulingInterprocess Communication Concurrent ProgrammingThreads vs ProcessesThreading Implementation & Multi-threading ModelsOther Threading Issues––––5Thread creation & cancellationSignal handlingThread poolsThread specific data6

5. CPU Scheduling6. Synchronization 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 burstsRace ConditionsCritical Section ProblemMutual ExclusionSemaphoresMonitorsClassic Problems of Synchronization––––Bounded BufferReaders-WritersDining PhilosophersSleeping Barber787. Deadlocks Deadlock Characterization Deadlock Detection– Resource Allocation Graphs– Wait-for Graphs– Deadlock detection algorithmExercise Questions Deadlock Avoidance Deadlock Recovery9Question 110Solution 11112

Solution 1 (cont)Question 213Solution 214Question 315Question 3 (cont)16Solution 31718

Question 4Solution 4Which processor scheduling algorithm results in the shortestaverage waiting time. Justify your answer.Which processor scheduling algorithm results in the shortestaverage waiting time. Justify your answer.Answer: Shortest Job First (SJF), since moving a shortprocess before a long one decreases the waiting time of theshort process more than it increases the waiting time of thelong process. Consequently, the average waiting timedecreases.1920Question 5Solution 5Explain why Round-Robin scheduling tends to favor CPUbound processes over I/O bound ones.Explain why Round-Robin scheduling tends to favor CPUbound processes over I/O bound ones.Answer: Each process gets put back at the end of the queueno matter how much or how little of the quantum was used.I/O bound processes tend to run for a short period of timeand then block which means they might have to wait in thequeue a long time.21Question 622Solution 6CPU scheduling quanta have remained about the sameover the past 20 years, but processors are now about1,000 times faster. Why haven’t CPU scheduling quantachanged?CPU scheduling quanta have remained about the sameover the past 20 years, but processors are now about1,000 times faster. Why haven’t CPU scheduling quantachanged?Answer: The length of the scheduling quanta is based on theoverhead of context switching a processor and the need tomove between processes within the time of humanperception. The overhead of context switching due to theneed to invalidate caches has remained relatively constant,and the time of human perception has also not evolved muchin the past 20 years.2324

Question 7Solution 7List 4 events that might occur to cause a user process to becontext switched off the processor.List 4 events that might occur to cause a user process to becontext switched off the processor.Answer:1.Timer Interrupt (time for another process to run)2.Blocking to wait for another event (e.g. waitsystem call)3.Process termination4.I/O Interrupt25Question 826Solution 8Assume S and T are binary semaphores, and X, Y, Z areprocesses. X and Y are identical processes and consist of thefollowing 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 Ztogether? Please justify your answer.Assume S and T are binary semaphores, and X, Y, Z areprocesses. X and Y are identical processes and consist of thefollowing 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 Ztogether? Please justify your answer.Answer: It is safer to run X and Y together since they requestresources in the same order, which eliminates the circular waitcondition needed for deadlock.27Question 928Solution 9Remember that if the semaphore operations Wait and Signal are not executedatomically, then mutual exclusion may be violated. Assume that Wait and Signal areimplemented as below:Remember that if the semaphore operations Wait and Signal are not executedatomically, then mutual exclusion may be violated. Assume that Wait and Signal areimplemented as below:void Wait (Semaphore S) {while (S.count 0) {}S.count S.count - 1;}void Wait (Semaphore S) {while (S.count 0) {}S.count S.count - 1;}void Signal (Semaphore S) {S.count S.count 1;}Describe a scenario of context switches where two threads, T1 and T2, can bothenter a critical section guarded by a single mutex semaphore as a result of a lack ofatomicity.29void Signal (Semaphore S) {S.count S.count 1;}Describe a scenario of context switches where two threads, T1 and T2, can bothenter a critical section guarded by a single mutex semaphore as a result of a lack ofatomicity.Answer: Assume that the semaphore is initialized with count 1. T1 calls Wait,executes the while loop, and breaks out because count is positive. Then a contextswitch occurs to T2 before T1 can decrement count. T2 also calls Wait, executesthe while loop, decrements count, and returns and enters the critical section.Another context switch occurs, T1 decrements count, and also enters the criticalsection. Mutual exclusion is therefore violated as a result of a lack of atomicity.30

Question 10Solution 10 31Question 1132Question 11 (cont)33Solution 1134Question 11-b3536

Solution 11-b37

average waiting time. Justify your answer. 19 Solution 4 Which processor scheduling algorithm results in the shortest average waiting time. Justify your answer. Answer: Shortest Job First (SJF), since moving a short process before a long one decreases the waiting time of the short process mor