X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;ds=sidebyside;f=sigcse2009%2Fassignments.tex;h=3d8ff0ff154a5fb0eea3c4b946c08110d78918df;hb=02d9affcb344f1ebc4253c59230fea7119469a89;hp=dd4d48b841242056091e28c7d59ed0caeeab3e77;hpb=4cabd6418ed47409ca394f63853df7ea9bbb6273;p=pintos-anon diff --git a/sigcse2009/assignments.tex b/sigcse2009/assignments.tex index dd4d48b..3d8ff0f 100644 --- a/sigcse2009/assignments.tex +++ b/sigcse2009/assignments.tex @@ -19,7 +19,7 @@ \subsection{Project 1 -- Threads} % intro -Project 1 centers around threads. The baseline Pintos code boots into a kernel that +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. @@ -27,7 +27,7 @@ Students study the existing, barebones threading system (about 600 lines of C co 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. -Student can examine the context switch code, but the projects do not involve any modifications +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 @@ -36,23 +36,20 @@ alarm clock, which requires maintaining a timer queue of sleeping threads and ch 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. In this model, one of the threads with the highest priority -always runs. When a thread's priority changes, or when threads block or unblock, -a scheduling decision must be triggered to ensure this invariant. Students learn about -the different ways in which such situations occur. -Project 1 also introduces synchronization primitives such as semaphores, locks, -and condition variables. The project explores the interaction between such primitives, -thread states, and the scheduler. - -Based on the priority scheduler, students implement two additional tasks: priority -inheritance and a multi-level feedback queue scheduler. Priority inheritance is a way -to avoid priority inversion, a phenonemon that most famously led to an almost-failure -of the Mars Pathfinder Mission. We use this example to motivate -the problem. Implementing priority inheritance correctly requires a deep understanding of the -interaction of threads and locks. +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' priority based on a sampling of how -much CPU time a thread has received recently. +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 @@ -63,10 +60,10 @@ output; the grading script will point out differences between the expected and t 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 in a different way. Since those tests rely on estimating CPU +The MLFQS scheduler tests are graded differently. 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 we accept the output. The envelope is large enough to allow for minor +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. @@ -181,7 +178,7 @@ page replacement schemes. \paragraph{Learning Objectives} In project 3, 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 to +It also provides a deep understanding of how OS use fault resumption 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. @@ -203,17 +200,17 @@ we use an intermediate ``scratch'' disk or partition that is attached 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. Similarly, we encourage students to experiment with different replacement -strategies for their buffercache (though we require that their algorithm +strategies for their buffer cache (though we require that their algorithm behaves at least as good as a least-recently-used (LRU) strategy. As with all projects, this assignment includes additional parallel programming -tasks: in this project, we include a requirement that students a multiple-reader, -single-writer access scheme for individual buffer cache blocks. +tasks: in this project, we suggest that students implement +a multiple-reader, single-writer access scheme for individual buffer cache blocks. \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 can be built -either on project 2 or 3 depending on the instructor's judgment. +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. For each functionality test, we provide a sibling persistence test that verifies that the changes done to the filesystem survive a shutdown and restart.