|
- 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.
.
The exam will cover the first 16 lectures (not counting the snow day), up to and including the
lectures on lock implementation. The following give examples of
the topic:
- Main role of Operating System
- Know and give examples of the two main roles played by an
OS, namely
- Know the differences, advantages and disadvantages of Micro-Kernel vs Monolithic Architecture
- Processes and threads
- Processes
- Know what abstraction processes provided and what advantages
this abstraction provides
- Know what are the five main states of a process and what the
significance of each state is
- Know what are the main components of a process
- Threads
- What is the difference between a thread and a process?
- What are the five (three plus two) main states of a
thread?
- What are the main components of a thread?
- Synchronization
- Know what it means for a set of threads to be correctly synchronized
- Know what the term Critical Section means
- Know what the term Mutual Exclusion means
- Given pseudo-code for multiple threads (on the scale of
examples done in class), and correctness criteria, tell whether
the criteria are met. If they are, tell why, informally but
rigorously. If they are not, demonstrate a failure of the
criteria (usually by giving a specific interleaving of steps of
the threads involved.
- Given pseudo-code for multiple threads (on the scale of
examples done in class), and correctness criteria, be able to
identify critical sections, and either give a reason why the
threads are correctly have mutual exclusion, or demonstrate an
interleaving that violates mutual exclusion.
- Lock Usage
- Know how you can have multiple locks.
- Know what it means (and what it doesn't mean) to lock a lock
variable.
- Know what the idea of a lock invariant is and when it
needs to hold
- Be able reason about and demonstrate errors in lock usage.
- Be able to describe efficiency concerns with various lock
placements.
- Be able to describe circumstances when locks are inadequate to
guarantee the needed synchronization
- Be able to write a small correct pseudo-code and reasonably
efficient implementation using locks to implement a given
structure.
- Mesa Monitors
- Know the two main types of synchronization, what they mean and
how they differ.
- Know what ordering constraints are.
- Know how condition variables are used, and how they fit
with locks.
- Know the difference between signal and
broadcast, and how you can generally replace signal
by broadcast, and why you might want to use signal over
broadcast and why you might not.
- Know what the basic difference between Mesa Monitors and Hoare
Monitors is,
- Producer-Consumers
- Know what a producer-consumer problem is, including what the
correctness criteria are
- Be able to give an interleaving of a faulty implementation of
a producer-consumer problem.
- Be able to construct a correct and efficient implementation
of a producer-consumer problem.
- Reader-Writer Locks
- Be able to compare Reader-Writer locks to simple locks
- Know how to use reader-writer locks in a simple example
- Understand how to implement reader-writer locks using Mesa Monitors
- 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.
|