1CSE120Principles of Operating SystemsProf Yuanyuan (YY) ZhouMidterm ReviewOct 19th , 201010/19/2010 CSE 120 – Midterm Review2Overview The midterm Architectural support for OSes OS modules, interfaces, and structures Processes Threads Synchronization Scheduling Deadlock10/19/2010 CSE 120 – Midterm Review3Midterm Covers material through scheduling Based upon lecture material, optional homeworks, and projects No cheat sheets Please, do not cheat– Do not copy from your neighbor You will be noticed– No one involved will be happy, particularly the teaching staff10/19/2010 CSE 120 – Midterm Review4Arch Support for OSes Types of architecture support– Manipulating privileged machine state– Generating and handling events– Events: Interrupts, exceptions, system calls, etc210/19/2010 CSE 120 – Midterm Review5Privileged Instructions What are privileged instructions?– Who gets to execute them?– How does the CPU know whether they can be executed?– Difference between user and kernel mode Why do they need to be privileged? What do they manipulate?– Protected control registers– Memory management– I/O devices10/19/2010 CSE 120 – Midterm Review6Events Events– Synchronous: fault (exceptions), system calls– Asynchronous: interrupts, software interrupt What are faults, and how are they handled? What are system calls, and how are they handled? What are interrupts, and how are they handled?– How do I/O devices use interrupts? What is the difference between exceptions and interrupts?10/19/2010 CSE 120 – Midterm Review7OS Modules and Interfaces Modules– OS services and abstractions Interfaces– Operations supported by components10/19/2010 CSE 120 – Midterm Review8Modules Processors Memory I/O Secondary storage Files Protection Account Command interpreter (shell)310/19/2010 CSE 120 – Midterm Review9Processes What is a process? What is the difference between a process and a program? What is contained in a process?10/19/2010 CSE 120 – Midterm Review10Process Data Structures Process Control Blocks (PCBs)– What information does it contain?– How is it used in a context switch? State queues– What are process states?– What is the process state graph?– When does a process change state?– How does the OS use queues to keep track of processes?10/19/2010 CSE 120 – Midterm Review11Process Manipulation What does fork() on Unix do?– What does it mean for it to “return twice”? What does exec() on Unix do?– How is it different from fork? How are fork and exec used to implement shells?10/19/2010 CSE 120 – Midterm Review12Threads What is a thread?– What is the difference between a thread and a process?– How are they related? Why are threads useful? What is the difference between user-level and kernel-level threads?– What are the advantages/disadvantages of one over another?410/19/2010 CSE 120 – Midterm Review13Thread Implementation How are threads managed by the run-time system?– Thread control blocks, thread queues– How is this different from process management? What operations do threads support?– Fork, yield, sleep, etc.– What does thread yield do? What is a context switch? What is the difference between non-preemptive scheduling and preemptive thread scheduling?– Voluntary and involuntary context switches10/19/2010 CSE 120 – Midterm Review14Synchronization Why do we need synchronization?– Coordinate access to shared data structures– Coordinate thread/process execution What can happen to shared data structures if synchronization is not used?– Race condition– Corruption– Bank account example When are resources shared?– Global variables, static objects– Heap objects10/19/2010 CSE 120 – Midterm Review15Mutual Exclusion What is mutual exclusion? What is a critical section?– What guarantees do critical sections provide?– What are the requirements of critical sections? Mutual exclusion (safety) Progress (liveness) Bounded waiting (no starvation: liveness) Performance How does mutual exclusion relate to critical sections? What are the mechanisms for building critical sections?– Locks, semaphores, monitors, condition variables10/19/2010 CSE 120 – Midterm Review16Locks What does Acquire do? What does Release do? What does it mean for Acquire/Release to be atomic? How can locks be implemented?– Spinlocks– Disable/enable interrupts– Blocking (Nachos) How does test-and-set/swap work?– What kind of lock does it implement? What are the limitations of using spinlocks, interrupts?– Inefficient, interrupts turned off too long510/19/2010 CSE 120 – Midterm Review17Semaphores What is a semaphore?– What does P/Decrement do?– What does V/Increment do?– How does a semaphore differ from a lock?– What is the difference between a binary semaphore and a counting semaphore? When do threads block on semaphores? When are they woken up again? Using semaphores to solve synchronization problems– Readers/Writers problem– Bounded Buffers problem10/19/2010 CSE 120 – Midterm Review18Monitors What is a monitor?– Shared data– Procedures– Synchronization In what way does a monitor provide mutual exclusion?– To what extent is it provided? How does a monitor differ from a semaphore? How does a monitor differ from a lock? What kind of support do monitors require?– Language, run-time support10/19/2010 CSE 120 – Midterm Review19Condition Variables What is a condition variable used for?– Coordinating the execution of threads– Not mutual exclusion Operations– What are the semantics of Wait?– What are the semantics of Signal?– What are the semantics of Broadcast? How are condition variables different from semaphores?10/19/2010 CSE 120 – Midterm Review20Implementing Monitors What does the implementation of a monitor look like?– Shared data– Procedures– A lock for mutual exclusion to procedures (w/ a queue)– Queues for the condition variables What is the difference between Hoare and Mesa monitors?– Semantics of signal (whether the woken up waiter gets to run immediately or not)– What are their tradeoffs?– What does Java provide?610/19/2010 CSE 120 – Midterm Review21Locks and Condition Vars In Nachos, we don’t have monitors But we want to be able to use
View Full Document