• Understand the lecture slides and discussions thoroughly.
• Revisit the MPs and make sure you understand why you lost any points and how to correct your mistakes. Seek help from the TA of the instructor if you are unclear about any aspects of these problems.
• Take the sample exam as a dry-run for the actual exam.
.

Syllabus

[top]

The exam will cover the lectures from Thread Implementaion through Virtual Machine Monitor I/O architecture. The following give examples of the topic (Not complete yet):

• Thread Implementation
• What are the main states of a thread?
• Know what is the main information stored in the thread control block used for switching contexts.
• Know the main steps to switching threads.
• Know the ways in which a thread can return control to the OS
• Know the main steps of context switching and in what order they have to be done
• Lock Implementation
• Know what the basic correctness criteria for an implementation of locks are
• Know what the main mechanism for implementing locks on a uniprocessor is, and why.
• Be able to analyze an implementation of locks on a uniprocessor for its correctness, and be able to comment on its efficiency.
• Know why the mechanism for implementing locks on a uniprocessor is insuficient for a multiprocessor.
• Know what the main mechanism for implementing locks on a multiprocessor is, and why.
• Be able to analyze an implementation of locks on a multiprocessor for its correctness, and be able to comment on its efficiency.
• Scheduling
• Know the definition of deadlocl
• Know the conditions necessary for deadlock to arise
• Know the algorithms for First-Come-First-Served and Round Robin scheduling
• Be able to compute the average response time for an example under each scheduling algorithm
• Know the Earliest Deadline First algorithm
• Be able to compute the execution schedule for a system given the set of tasks for the system including their arrival times, whether they a periodic or aperiodic, periodicity as appropriate, their execution times, and their deadlines.
• Virtual Memory
• Know what abstraction is provided by virtual memory
• Understand the relationship between virtual memory and context switching
• Know the what the Base and Limit method is for implementing virtual memory
• Understand and be able to work an example for each of the following memory allocation & deallocation algorithms:
• First Fit
• Nearest Fit
• Best Fit
• Worst Fit
• The Buddy System
• Paging
• Be able to explain the relationship between pages and page frames
• Know what it means for a page to be resident, and to be valid.
• Know what features hardware typically supplies to support paging and how the OS uses it to implement virtual memory
• Know what a page table is, with what it is associated, how it is used in implementing virtual memory and when it needs replacing
• Know what the general structure of a page table entry is and how it is used to find a physical address
• Be able to explain why multi-level page tables are used in implementing virtual memory
• Know how multi-level page tables are used to translate a virtual address into a physcial address
• Know what the function of a Translation Lookaside Buffer is, and what its relationship to the current page table is
• Page Deallocation
• Know what the Page replacement/deallocation problem is
• Know what a working set is
• Know the algorithm for, and be able to work an example for each of:
  • Second Chance Algorithm
  • Clock Replacement Algorithm
  • Working Set Algorithm
  • Working Set Clock Algorithm
• Virtual Machine Monitors
• Know the difinitions of and differences between a Virtual Machine and a Virtual Machine Monitor
• Be able to list at least three benefits for using VMMs
• Know the difference is between an Application Binary Interface (ABI) VMM and an Instruction Set Architecture (ISA) VMM
• Know what are the three main objectives of an (ISA) VMM
• Virtual Machine Monitors as Simulators
• Know what is the basic methodology in creating a VMM via simulation
• Know what are the main components and phases in a simulator VMM
• Know how to decode an instruction from binary, given an instruction format
• Know how to use the basic structures in the VMM to simulate basic classes of instructions, such a ALU instructions and memory instructions
• Be able to describe how and in which phases having variable length instructions complicates their simulation
• Dynamic Binary Translation for Virtual Machine Monitors
• Know what the main problem is that Dynamic Binary Translation is designed to address
• Know what is the main idea behind behind the implementation of dynamic binary translation, and what limitations on the relationship between the VM exported by the VMM and the underlying architecure on which the VMM runs
• Know what basic blocks are, and what role they play when translating instructions
• Know how to use the basic structures in the VMM and support from the underlying architecture to translate basic classes of instructions, such a ALU instructions and memory instructions
• I/O
• Describe the main components of the hardward interface to the CPU
• Describe the thee main ways software can interact with hardware, and for each one state what harware support is required, if any
• For a given application, be able to analyze the relative merits of each of those three main ways
• Know what abstractions a devive driver (or family of device drivers) should provide
• What are the four main principles I/O software should strive to support?
• Virtual Machine Monitor I/O arichitecure
• What must a WMM export to support Guest Software's access to I/O devices?
• How does a Type I VMM support virtual devices?
• How does a Type II VMM support virtual devices?
• What are the tradeoffs between the two approaches?