timer: Fix timer calibration logic.

[pintos-anon] / sigcse2009 / assignments.tex

\section{Pintos Projects}
\label{sec:assignments}

The Pintos instructional operating system is split into four projects.
\pintostestcounttable{}

%
% Not sure if we need that.
%
% \subsection{Project 0}
% If Pintos is used in a semester-long course, project 0 serves as a ``warm-up'' project.
% In this project, students will gain familiarity with the Pintos source tree and some
% supporting classes, in particular its implementation of doubly-linked lists.
% In OS, doubly-linked lists are frequently used because they allow $O(1)$ insertion and
% removal operations.  Moreover, they are often used in a style in which the list cell
% containing the next and prev pointers is embedded in some larger structure, such as
% a thread control block, rather than having separately allocated list cells.
% In project 0, students use Pintos's list implementation to implement a simple, first-fit 
% memory allocator.  

\subsection{Project 1 -- Threads}
% intro
Project 1 revolves around threads.  The baseline Pintos code boots into a kernel that
supports multiple in-kernel threads.  It provides code for initialization, thread creation and
destruction, context switches, thread blocking and unblocking as well as a simple but
preemptive round-robin scheduler.
Students study the existing, barebones threading system (about 600 lines of C code) to 
understand how threads are created and destroyed, and to understand the transitioning of 
threads between the READY, RUNNING, and BLOCKED states.  They also study how a thread's
internal memory is managed, which is used to store its runtime stack and thread control block.
Students can examine the context switch code, but the projects do not involve any modifications
to it.

After reading the baseline code, the project asks students to implement several features
that exercise thread state transitions.  The first part of this project includes a simple
alarm clock, which requires maintaining a timer queue of sleeping threads and changing 
the timer interrupt handler to unblock those threads whose wakeup time has arrived.
Students learn how to protect data structures that are shared between a thread and an
interrupt handler.  The second part of the project constitutes a strict priority-based
uniprocessor scheduler; students learn about the different ways in which 
such a scheduler must react to thread state changes.
% cut for length
%Project 1 also introduces synchronization primitives such as semaphores, locks,
%and condition variables and explores the interaction between such primitives,
%thread states, and the scheduler.

Based on the priority scheduler, students implement priority inheritance, 
which deepens their understanding of the interaction of threads and locks.
We use the example of the near-failure of the Mars PathFinder mission to motivate
the need for priority inheritance.  
Separately, students build a multi-level feedback queue scheduler on top of the strict
priority scheduler.  This scheduler adjusts threads' priorities based on a sampling  
of how much CPU time a thread has received recently.

\paragraph{Testing and Grading}
Project 1 is accompanied by 27 tests as shown in Table~\ref{table:tests}, which are 
run by a grading script using the Bochs simulator.
Most of the tests are designed to produce deterministic output; 
the grading script will point out differences between expected and actual output. 
Usually, a test failure leads students to study the documented source code of the test
and understand how the expected output derives from it.

The MLFQS scheduler tests require a different approach.  Since those tests rely on estimating CPU
usage, they depend on how much CPU time a specific implementation uses, which in turn depends on how
efficient it is.  We compute the expected CPU consumption values by simulation and provide an
envelope within which the output is accepted.  The envelope is large enough to allow for minor
inefficiencies, but major inefficiencies will usually lead to test failures.  Such failures
convey the importance of using efficient algorithms and data structures within an OS kernel.
% cfl: because wasting CPU cycles in the kernel reduces the amount available to applications.

% intro
\paragraph{Learning Objectives}
Project 1 has three learning objectives.  First, students will understand how
the illusion that ``computers can do multiple things at once'' is created by a sequence
of thread state transitions and context switches.  Second, they will understand how
sophisticated scheduling policies can be built on top of a simple priority-based scheduler.
Third, having seen the mechanisms a preemptive scheduler uses to create apparent 
concurrency, students gain a better intuition of the non-determinism inherent 
in concurrent systems. 

%
%
%
\subsection{Project 2 -- User Programs}
The second project illustrates how an OS implements protection and isolation between user processes,
how user processes access kernel services, and how user processes lay out the virtual
address space in which their program and data is contained.
Students first add support to Pintos to load and execute user programs.
We kept the provided code purposefully minimal to
only a library that reads the text and data segments of ELF binaries.   These binaries
are loaded into a new address space; the baseline code includes functionality to allocate
physical memory and set up a page directory to establish the process's virtual address
mappings.

Students implement support for a small set of system calls that allow processes to perform
I/O, start new processes, wait for their termination, and exit.  Both the Pintos user 
process model and system call API are modeled after traditional Unix, with the exception 
that Pintos does not separate process creation (i.e., fork()) from program loading
(i.e., exec) - instead, Pintos's exec() system call combines these two pieces of functionality 
into one.  The implementation of these calls requires the students to keep track of
per-process resources such as file descriptors, which deepens their understanding of how
an operating system provides the abstraction of a process.

Like most OS, Pintos exploits dual-mode operation in which user processes run
in a nonprivileged mode.
% cfl: that prevents access to kernel resources and to resources allocated to other processes.  
Processes attempting to bypass these restrictions are terminated.
Students implement the system call handling code, a key aspect of which includes the
careful examination of arguments passed by user processes.

Project 2 also illustrates concurrent programming techniques, notably fork/join
parallelism, which students implement using rendezvous-style synchronization 
% based on semaphores 
when providing support for the exec()/wait()/exit() system calls.  

\paragraph{Testing and Grading}
All tests for Project 2 are user programs written in C.
They are divided into functionality and robustness tests.  Functionality tests check that
the operating system provides the specified set of services when it is used as
expected.  Robustness tests check that the OS rejects all attempts at passing
invalid input to system calls.  To pass those tests, the student's kernel must be 
``bullet-proof.'' We include a stress test in which we artificially induce low memory
conditions by creating a large number of processes and pseudo-randomly introducing
failures in some of them.  We expect the kernel to fully recover from such situations.

\paragraph{Learning Objectives}
Students learn how the thread abstraction introduced in Project 1 is 
extended into the process abstraction, which combines a thread, a virtual address space, 
and its associated resources.
Project 2 enables students to understand how operating systems employ dual-mode
operation to implement isolation between processes and to protect system resources
even in the presence of failing or misbehaving processes.  
Students understand how processes transition into the kernel to access its services,
and how kernels implement such services in a robust way.
The principles learned in this exercise carry over to all scenarios
in which applications must be robust in the face of input coming from untrusted 
sources and uncertain resource availability, as is the case in many server systems.

\subsection{Project 3 -- Virtual Memory}
Project 3 asks students to implement several virtual memory techniques, including
on-demand paging of programs, stack growth, page replacement, and memory-mapped files.
This functionality is primarily implemented in a page fault handler routine.
% and during the program loading process.
We provide supporting code to create and maintain page directories, which hide
the x86-specifics of how to program the memory management unit (MMU) and how
to ensure consistency with the CPU's translation look-aside buffer (TLB).  
As a result, students can treat the MMU as an abstract device in which to 
install, update, or remove virtual-to-physical address mappings.
Consequently, they are free to choose any design for the data structures needed to
keep track of the state of each page or region in a process's virtual address 
space.

In early offerings, this significant creative freedom came at the cost that 
some students were lost as to how to accomplish set goals.  We added an intermediate
design review stage to this project using a structured questionnaire in which students 
outline their planned design.  We also provided a suggested order of implementation.

Like Project 2, Project 3 requires the use of concurrent programming techniques.  
Since the Pintos kernel is fully preemptive, students must consider which data structures
require locking, and they must design a locking strategy that both avoids deadlock
and unnecessary serialization.

\paragraph{Testing and Grading}
Project 3 relies on Project 2, therefore, we include all tests provided with Project 2
as regression tests to ensure that system call functionality does not break in the
presence of virtual memory.  Furthermore, we provide tests for the
added functionality that lends itself to such testing, namely, memory-mapped files
and stack growth.  Some of the project tasks, such as on-demand paging, are 
performance-enhancing techniques that do not directly add functionality that is
apparent to user programs; these tasks are graded by inspection.  We test the students
page replacement code by varying the amount of physical memory available to
the kernel when run under emulation, relative to the amount of memory that is 
accessed by our test programs.  
Grossly inefficient page replacement schemes result test failures due to time-outs.

\paragraph{Learning Objectives}
Students learn how an OS creates the environment in which a user
program executes as it relates to the program's code and variables.
It provides a thorough understanding of how OS use resumption after page faults
to virtualize a process's use of physical memory.
Students gain hands-on experience with page replacement algorithms
and have the opportunity to directly observe their performance impact. 

%
%
%
\subsection{Project 4 -- Filesystems}
Project 4 asks students to design and implement a hierarchical, multi-threaded
filesystem and buffer cache.  In Projects 2 and 3, students use a basic filesystem
we provide to access the disk, which supports only fixed-size files, no subdirectories,
and which lacks a buffer cache.  
Although we suggest a traditional, Unix-like filesystem design, which stores file
metadata in inodes and treats directories as files, students have
complete freedom in designing the layout of their filesystem's metadata.
% as long as their design does not suffer from external fragmentation.
Since our host tools will not know how to interpret the student's filesystems,
we attach an intermediate ``scratch'' disk or partition to the 
physical or virtual computer on which Pintos runs, and use the student's kernel
to copy files into and out of their filesystems.
Similarly, we encourage students to experiment with different replacement
strategies for their buffer cache, although we require that their algorithm
behaves at least as well as a least-recently-used (LRU) strategy.

As with all projects, this assignment includes additional concurrent programming 
tasks: in this project, we suggest that students implement 
a multiple-reader, single-writer access scheme for individual buffer cache blocks
to allow shared access when reading file data and metadata.

\paragraph{Testing and Grading}
Project 4 adds a new set of test cases for the extended functionality, including
stress tests that check correct behavior for deeply nested directories and 
for nearly full disks.
For each functionality test, we provide a sibling persistence test that verifies 
that the changes done to the filesystem survive a shutdown and restart.
Since the project does not require the virtual memory functionality, it can be built
on either Project 2 or 3, depending on the instructor's judgment.

\paragraph{Learning Objectives}
This project provides a deep understanding of how OS's manage secondary storage
while avoiding fragmentation and providing efficiency for commonly occurring 
disk access patterns.
Students learn how the use of a buffer cache helps absorb disk requests and
improves performance.
They also gain insight into filesystem semantics in the presence of 
simultaneously occurring requests.