-\section{Assignments}
+\section{Pintos Projects}
\label{sec:assignments}
+The Pintos instructional operating system is split into four projects.
\pintostestcounttable{}
%
\paragraph{Testing and Grading}
Project 1 is accompanied by 27 tests as shown in Table~\ref{table:tests}, which are
-run using the Bochs simulator by a grading script.
-Most tests are designed to test a single aspect, but some tests
-test more involved scenarios. Most of the tests are designed to produce a deterministic
-output; the grading script will point out differences between the expected and the actual output.
+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 are graded differently. Since those tests rely on estimating CPU
+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 a kernel,
-because wasting CPU cycles in the kernel reduces the amount available to applications.
+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
-a simple underlying mechanism - such as priority-based scheduling - can lead to more
-sophisticated scheduling policies. 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.
+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 OS implements protection and isolation between user processes,
-how user processes gain access to kernel services, and how user processes lay out the virtual
+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.
-The project adds support to Pintos to load and execute user programs that make use
-of kernel services. We kept the provided code purposefully minimal, consisting of
-only a library that reads the program and data segments of ELF binaries. These binaries
+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 processes do not separate process creation (i.e., fork()) from program loading
+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, deepening their understanding of how
+per-process resources such as file descriptors, which deepens their understanding of how
an operating system provides the abstraction of a process.
-Like most current OS, Pintos exploits dual-mode operation in which user processes run
-in a nonprivileged mode that prevents access to kernel resources and to resources allocated
-to other processes. Processes attempting to bypass these restrictions are terminated.
+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 parallel programming techniques, notably fork/join
-parallelism, which students implement when providing support for the exec()/wait()/exit()
-system calls. The rendezvous-style synchronization necessary to support this model
-can be implemented using semaphores, providing a practical example of this style
-synchronization presented in accompanying lectures.
-
-% How threads extend into 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}
-The tests for project 2 exclusively consist of user programs written in C.
+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 expected set of services when it is used as
-expected. A set of robustness tests checks that the OS rejects all attempts at passing
+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}
-In project 2, students learn how the thread abstraction introduced in project 1 is
+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
\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 implemented in a page fault service handler and during the
-program loading process.
+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.
+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 how to accomplish set goals. We added an intermediate
+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 provide a suggested order of implementation.
+outline their planned design. We also provided a suggested order of implementation.
-Like project 2, project 3 requires the use of parallel programming techniques.
+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 reduces unnecessary serialization.
+and unnecessary serialization.
\paragraph{Testing and Grading}
-Project 3 relies on project 2, therefore, we include all tests provided with project 2
+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 functionality tests for 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, which are graded by inspection. We test the students
+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. Timeouts are used to detect grossly inefficient
-page replacement schemes.
+accessed by our test programs.
+Grossly inefficient page replacement schemes result test failures due to time-outs.
\paragraph{Learning Objectives}
-In project 3, students learn how an OS creates the environment in which a user
+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 also provides a deep understanding of how OS use fault resumption
+It provides a thorough understanding of how OS use resumption after page faults
to virtualize a process's use of physical memory.
-In addition, students gain hands-on experience with page replacement algorithms
-and have the opportunity to observe their performance impact.
+Students gain hands-on experience with page replacement algorithms
+and have the opportunity to directly observe their performance impact.
%
%
%
-\subsection{Project 4 -- File Systems}
-Project 4 asks the students to design and implement a hierarchical, multi-threaded
-filesystem and buffer cache. In projects 2 and 3, students use a basic filesystem
-to access the disk, which supports only fixed-size files, no subdirectories,
+\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.
-Though we suggest a traditional, Unix-like filesystem design, which stores file
-metadata in inodes and in which directories are treated 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.
+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 use an intermediate ``scratch'' disk or partition that is attached to the
+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 in and out of their filesystems.
+to copy files into and out of their filesystems.
Similarly, we encourage students to experiment with different replacement
-strategies for their buffer cache (though we require that their algorithm
-behaves at least as good as a least-recently-used (LRU) strategy.
+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 parallel programming
+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.
+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 that test the extended functionality.
-Project 4 does not require the virtual memory functionality, so it can be built
-on either project 2 or 3, depending on the instructor's judgment.
+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 deeper understanding of how OS's manage secondary storage
+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.
+disk access patterns.
Students learn how the use of a buffer cache helps absorb disk requests and
-improve performance.
-They also gain insight into filesystem semantics in the presence of simultaneously
-occurring requests.
+improves performance.
+They also gain insight into filesystem semantics in the presence of
+simultaneously occurring requests.
projects / pintos-anon / blobdiff