Lecture 9:Lecture 9:Midterm ReviewMidterm ReviewCSE 120: Principles of Operating SystemsAlex C. SnoerenProject 1 Due at MidnightCSE 120 – Lecture 92MidtermMidterm Everything we’ve covered is fair game◆ Readings, lectures, homework, and Nachos◆ Yes, there may be Nachos code on the exam! Exam will be individual, closed book◆ Leave books, notes, laptops, etc., at home or in your bag◆ We’ll provide scrap paper should you need it◆ Please don’t cheat, none of us will enjoy the results Barath will proctor the exam Tuesday◆ Please sit every other seat when you arriveCSE 120 – Lecture 93TopicsTopics WeWe’’ve Coveredve Covered OS modules, interfaces, and structures Architectural support for OSes Processes Threads Locks & Semaphores Monitors & Condition Variables Scheduling DeadlockCSE 120 – Lecture 94OS Modules and InterfacesOS Modules and Interfaces Modules◆ OS services and abstractions Interfaces◆ Operations supported by componentsCSE 120 – Lecture 95ModulesModules Processes Memory I/O Secondary storage Files Protection Account Command interpreter (shell)CSE 120 – Lecture 96Arch Support for Arch Support for OSesOSes Types of architecture support◆ Manipulating privileged machine state◆ Generating and handling eventsCSE 120 – Lecture 97Privileged InstructionsPrivileged 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 devicesCSE 120 – Lecture 98EventsEvents 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 andinterrupts?CSE 120 – Lecture 99ProcessesProcesses What is a process? What resource does it virtualize? What is the difference between a process and aprogram? What is contained in a process?CSE 120 – Lecture 910Process Data StructuresProcess 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?CSE 120 – Lecture 911Process ManipulationProcess Manipulation What does CreateProcess on NT do? 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? Why separate fork() and exec() ?CSE 120 – Lecture 912ThreadsThreads 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?CSE 120 – Lecture 913Thread ImplementationThread 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-preemptivescheduling and preemptive thread scheduling?◆ Voluntary and involuntary context switchesCSE 120 – Lecture 914SynchronizationSynchronization Why do we need synchronization?◆ Coordinate access to shared data structures◆ Coordinate thread/process execution What can happen to shared data structures ifsynchronization is not used?◆ Race condition◆ Corruption◆ Bank account example When are resources shared?◆ Global variables, static objects◆ Heap objectsCSE 120 – Lecture 915Mutual ExclusionMutual 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» Progress» Bounded waiting (no starvation)» Performance How does mutual exclusion relate to critical sections? What are the mechanisms for building criticalsections?◆ Locks, semaphores, monitors, condition variablesCSE 120 – Lecture 916LocksLocks 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 work?◆ What kind of lock does it implement? What are the limitations of using spinlocks, interrupts?◆ Inefficient, interrupts turned off too longCSE 120 – Lecture 917SemaphoresSemaphores What is a semaphore?◆ What does Wait/P/Decrement do?◆ What does Signal/V/Increment do?◆ How does a semaphore differ from a spin lock?◆ What is the difference between a binary semaphore and acounting semaphore? When do threads block on semaphores? When are they woken up again? Using semaphores to solve synchronization problems◆ Readers/Writers problem◆ Bounded Buffers problemCSE 120 – Lecture 918MonitorsMonitors 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 supportCSE 120 – Lecture 919Condition VariablesCondition 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 fromsemaphores?CSE 120 – Lecture 920Implementing MonitorsImplementing 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 Mesamonitors?◆ Semantics of signal (whether the woken up waiter gets to runimmediately or not)◆
View Full Document