4 Welcome to Pintos. Pintos is a simple operating system framework for
5 the 80@var{x}86 architecture. It supports kernel threads, loading and
6 running user programs, and a file system, but it implements all of
7 these in a very simple way. In the Pintos projects, you and your
8 project team will strengthen its support in all three of these areas.
9 You will also add a virtual memory implementation.
11 Pintos could, theoretically, run on a regular IBM-compatible PC.
12 Unfortunately, it is impractical to supply every student
13 a dedicated PC for use with Pintos. Therefore, we will run Pintos projects
14 in a system simulator, that is, a program that simulates an 80@var{x}86
15 CPU and its peripheral devices accurately enough that unmodified operating
16 systems and software can run under it. In class we will use the
17 @uref{http://bochs.sourceforge.net, , Bochs} and
18 @uref{http://fabrice.bellard.free.fr/qemu/, ,
19 QEMU} simulators. Pintos has also been tested with
20 @uref{http://www.vmware.com/, , VMware Player}.
22 These projects are hard. They have a reputation of taking a lot of
23 time, and deservedly so. We will do what we can to reduce the workload, such
24 as providing a lot of support material, but there is plenty of
25 hard work that needs to be done. We welcome your
26 feedback. If you have suggestions on how we can reduce the unnecessary
27 overhead of assignments, cutting them down to the important underlying
28 issues, please let us know.
30 This chapter explains how to get started working with Pintos. You
31 should read the entire chapter before you start work on any of the
37 * Legal and Ethical Issues::
43 @section Getting Started
45 To get started, you'll have to log into a machine that Pintos can be
48 We will test your code on these machines, and the instructions given
49 here assume this environment. We cannot provide support for installing
50 and working on Pintos on your own machine, but we provide instructions
51 for doing so nonetheless (@pxref{Installing Pintos}).
53 Once you've logged into one of these machines, either locally or
54 remotely, start out by adding our binaries directory to your @env{PATH}
59 * Source Tree Overview::
62 * Debugging versus Testing::
65 @node Source Tree Overview
66 @subsection Source Tree Overview
68 Now you can extract the source for Pintos into a directory named
69 @file{pintos/src}, by executing
71 git clone @value{gitrepo}
74 Let's take a look at what's inside. Here's the directory structure
75 that you should see in @file{pintos/src}:
79 Source code for the base kernel, which you will modify starting in
83 Source code for the user program loader, which you will modify
84 starting with project 2.
87 An almost empty directory. You will implement virtual memory here in
91 Source code for a basic file system. You will use this file system
92 starting with project 2, but you will not modify it until project 4.
95 Source code for I/O device interfacing: keyboard, timer, disk, etc.
96 You will modify the timer implementation in project 1. Otherwise
97 you should have no need to change this code.
100 An implementation of a subset of the standard C library. The code in
101 this directory is compiled into both the Pintos kernel and, starting
102 from project 2, user programs that run under it. In both kernel code
103 and user programs, headers in this directory can be included using the
104 @code{#include <@dots{}>} notation. You should have little need to
108 Parts of the C library that are included only in the Pintos kernel.
109 This also includes implementations of some data types that you are
110 free to use in your kernel code: bitmaps, doubly linked lists, and
111 hash tables. In the kernel, headers in this
112 directory can be included using the @code{#include <@dots{}>}
116 Parts of the C library that are included only in Pintos user programs.
117 In user programs, headers in this directory can be included using the
118 @code{#include <@dots{}>} notation.
121 Tests for each project. You can modify this code if it helps you test
122 your submission, but we will replace it with the originals before we run
126 Example user programs for use starting with project 2.
130 These files may come in handy if you decide to try working with Pintos
131 on your own machine. Otherwise, you can ignore them.
134 @node Building Pintos
135 @subsection Building Pintos
137 As the next step, build the source code supplied for
138 the first project. First, @command{cd} into the @file{threads}
139 directory. Then, issue the @samp{make} command. This will create a
140 @file{build} directory under @file{threads}, populate it with a
141 @file{Makefile} and a few subdirectories, and then build the kernel
142 inside. The entire build should take less than 30 seconds.
146 Following the build, the following are the interesting files in the
147 @file{build} directory:
151 A copy of @file{pintos/src/Makefile.build}. It describes how to build
152 the kernel. @xref{Adding Source Files}, for more information.
155 Object file for the entire kernel. This is the result of linking
156 object files compiled from each individual kernel source file into a
157 single object file. It contains debug information, so you can run
158 GDB (@pxref{GDB}) or @command{backtrace} (@pxref{Backtraces}) on it.
161 Memory image of the kernel, that is, the exact bytes loaded into
162 memory to run the Pintos kernel. This is just @file{kernel.o} with
163 debug information stripped out, which saves a lot of space, which in
164 turn keeps the kernel from bumping up against a @w{512 kB} size limit
165 imposed by the kernel loader's design.
168 Memory image for the kernel loader, a small chunk of code written in
169 assembly language that reads the kernel from disk into memory and
170 starts it up. It is exactly 512 bytes long, a size fixed by the
174 Subdirectories of @file{build} contain object files (@file{.o}) and
175 dependency files (@file{.d}), both produced by the compiler. The
176 dependency files tell @command{make} which source files need to be
177 recompiled when other source or header files are changed.
180 @subsection Running Pintos
182 We've supplied a program for conveniently running Pintos in a simulator,
183 called @command{pintos}. In the simplest case, you can invoke
184 @command{pintos} as @code{pintos @var{argument}@dots{}}. Each
185 @var{argument} is passed to the Pintos kernel for it to act on.
187 Try it out. First @command{cd} into the newly created @file{build}
188 directory. Then issue the command @code{pintos run alarm-multiple},
189 which passes the arguments @code{run alarm-multiple} to the Pintos
190 kernel. In these arguments, @command{run} instructs the kernel to run a
191 test and @code{alarm-multiple} is the test to run.
193 This command creates a @file{bochsrc.txt} file, which is needed for
194 running Bochs, and then invoke Bochs. Bochs opens a new window that
195 represents the simulated machine's display, and a BIOS message briefly
196 flashes. Then Pintos boots and runs the @code{alarm-multiple} test
197 program, which outputs a few screenfuls of text. When it's done, you
198 can close Bochs by clicking on the ``Power'' button in the window's top
199 right corner, or rerun the whole process by clicking on the ``Reset''
200 button just to its left. The other buttons are not very useful for our
203 (If no window appeared at all, then you're probably logged in remotely and X
204 forwarding is not set up correctly. In this case, you can fix your X
205 setup, or you can use the @option{-v} option to disable X output:
206 @code{pintos -v -- run alarm-multiple}.)
208 The text printed by Pintos inside Bochs probably went by too quickly to
209 read. However, you've probably noticed by now that the same text was
210 displayed in the terminal you used to run @command{pintos}. This is
211 because Pintos sends all output both to the VGA display and to the first
212 serial port, and by default the serial port is connected to Bochs's
213 @code{stdin} and @code{stdout}. You can log serial output to a file by
215 command line, e.g.@: @code{pintos run alarm-multiple > logfile}.
217 The @command{pintos} program offers several options for configuring the
218 simulator or the virtual hardware. If you specify any options, they
219 must precede the commands passed to the Pintos kernel and be separated
220 from them by @option{--}, so that the whole command looks like
221 @code{pintos @var{option}@dots{} -- @var{argument}@dots{}}. Invoke
222 @code{pintos} without any arguments to see a list of available options.
223 Options can select a simulator to use: the default is Bochs, but
224 @option{--qemu} selects QEMU. You can run the simulator
225 with a debugger (@pxref{GDB}). You can set the amount of memory to give
226 the VM. Finally, you can select how you want VM output to be displayed:
227 use @option{-v} to turn off the VGA display, @option{-t} to use your
228 terminal window as the VGA display instead of opening a new window
229 (Bochs only), or @option{-s} to suppress serial input from @code{stdin}
230 and output to @code{stdout}.
232 The Pintos kernel has commands and options other than @command{run}.
233 These are not very interesting for now, but you can see a list of them
234 using @option{-h}, e.g.@: @code{pintos -h}.
236 @node Debugging versus Testing
237 @subsection Debugging versus Testing
239 When you're debugging code, it's useful to be able to run a
240 program twice and have it do exactly the same thing. On second and
241 later runs, you can make new observations without having to discard or
242 verify your old observations. This property is called
243 ``reproducibility.'' One of the simulators that Pintos supports, Bochs,
245 reproducibility, and that's the way that @command{pintos} invokes it
248 Of course, a simulation can only be reproducible from one run to the
249 next if its input is the same each time. For simulating an entire
250 computer, as we do, this means that every part of the computer must be
251 the same. For example, you must use the same command-line argument, the
252 same disks, the same version
253 of Bochs, and you must not hit any keys on the keyboard (because you
254 could not be sure to hit them at exactly the same point each time)
257 While reproducibility is useful for debugging, it is a problem for
258 testing thread synchronization, an important part of most of the projects. In
259 particular, when Bochs is set up for reproducibility, timer interrupts
260 will come at perfectly reproducible points, and therefore so will
261 thread switches. That means that running the same test several times
262 doesn't give you any greater confidence in your code's correctness
263 than does running it only once.
265 So, to make your code easier to test, we've added a feature, called
266 ``jitter,'' to Bochs, that makes timer interrupts come at random
267 intervals, but in a perfectly predictable way. In particular, if you
268 invoke @command{pintos} with the option @option{-j @var{seed}}, timer
269 interrupts will come at irregularly spaced intervals. Within a single
270 @var{seed} value, execution will still be reproducible, but timer
271 behavior will change as @var{seed} is varied. Thus, for the highest
272 degree of confidence you should test your code with many seed values.
274 On the other hand, when Bochs runs in reproducible mode, timings are not
275 realistic, meaning that a ``one-second'' delay may be much shorter or
276 even much longer than one second. You can invoke @command{pintos} with
277 a different option, @option{-r}, to set up Bochs for realistic
278 timings, in which a one-second delay should take approximately one
279 second of real time. Simulation in real-time mode is not reproducible,
280 and options @option{-j} and @option{-r} are mutually exclusive.
282 The QEMU simulator is available as an
283 alternative to Bochs (use @option{--qemu} when invoking
284 @command{pintos}). The QEMU simulator is much faster than Bochs, but it
285 only supports real-time simulation and does not have a reproducible
291 We will grade your assignments based on test results and design quality,
292 each of which comprises 50% of your grade.
302 Your test result grade will be based on our tests. Each project has
303 several tests, each of which has a name beginning with @file{tests}.
304 To completely test your submission, invoke @code{make check} from the
305 project @file{build} directory. This will build and run each test and
306 print a ``pass'' or ``fail'' message for each one. When a test fails,
307 @command{make check} also prints some details of the reason for failure.
308 After running all the tests, @command{make check} also prints a summary
311 For project 1, the tests will probably run faster in Bochs. For the
312 rest of the projects, they will run much faster in QEMU.
313 @command{make check} will select the faster simulator by default, but
314 you can override its choice by specifying @option{SIMULATOR=--bochs} or
315 @option{SIMULATOR=--qemu} on the @command{make} command line.
317 You can also run individual tests one at a time. A given test @var{t}
318 writes its output to @file{@var{t}.output}, then a script scores the
319 output as ``pass'' or ``fail'' and writes the verdict to
320 @file{@var{t}.result}. To run and grade a single test, @command{make}
321 the @file{.result} file explicitly from the @file{build} directory, e.g.@:
322 @code{make tests/threads/alarm-multiple.result}. If @command{make} says
323 that the test result is up-to-date, but you want to re-run it anyway,
324 either run @code{make clean} or delete the @file{.output} file by hand.
326 By default, each test provides feedback only at completion, not during
327 its run. If you prefer, you can observe the progress of each test by
328 specifying @option{VERBOSE=1} on the @command{make} command line, as in
329 @code{make check VERBOSE=1}. You can also provide arbitrary options to the
330 @command{pintos} run by the tests with @option{PINTOSOPTS='@dots{}'},
331 e.g.@: @code{make check PINTOSOPTS='-j 1'} to select a jitter value of 1
332 (@pxref{Debugging versus Testing}).
334 All of the tests and related files are in @file{pintos/src/tests}.
335 Before we test your submission, we will replace the contents of that
336 directory by a pristine, unmodified copy, to ensure that the correct
337 tests are used. Thus, you can modify some of the tests if that helps in
338 debugging, but we will run the originals.
340 All software has bugs, so some of our tests may be flawed. If you think
341 a test failure is a bug in the test, not a bug in your code,
342 please point it out. We will look at it and fix it if necessary.
344 Please don't try to take advantage of our generosity in giving out our
345 test suite. Your code has to work properly in the general case, not
346 just for the test cases we supply. For example, it would be unacceptable
347 to explicitly base the kernel's behavior on the name of the running
348 test case. Such attempts to side-step the test cases will receive no
349 credit. If you think your solution may be in a gray area here, please
355 We will judge your design based on the design document and the source
356 code that you submit. We will read your entire design document and much
359 Don't forget that design quality, including the design document, is 50%
360 of your project grade. It
361 is better to spend one or two hours writing a good design document than
362 it is to spend that time getting the last 5% of the points for tests and
363 then trying to rush through writing the design document in the last 15
371 @node Design Document
372 @subsubsection Design Document
374 We provide a design document template for each project. For each
375 significant part of a project, the template asks questions in four
379 @item Data Structures
381 The instructions for this section are always the same:
384 Copy here the declaration of each new or changed @code{struct} or
385 @code{struct} member, global or static variable, @code{typedef}, or
386 enumeration. Identify the purpose of each in 25 words or less.
389 The first part is mechanical. Just copy new or modified declarations
390 into the design document, to highlight for us the actual changes to data
391 structures. Each declaration should include the comment that should
392 accompany it in the source code (see below).
394 We also ask for a very brief description of the purpose of each new or
395 changed data structure. The limit of 25 words or less is a guideline
396 intended to save your time and avoid duplication with later areas.
400 This is where you tell us how your code works, through questions that
401 probe your understanding of your code. We might not be able to easily
402 figure it out from the code, because many creative solutions exist for
403 most OS problems. Help us out a little.
405 Your answers should be at a level below the high level description of
406 requirements given in the assignment. We have read the assignment too,
407 so it is unnecessary to repeat or rephrase what is stated there. On the
408 other hand, your answers should be at a level above the low level of the
409 code itself. Don't give a line-by-line run-down of what your code does.
410 Instead, use your answers to explain how your code works to implement
413 @item Synchronization
415 An operating system kernel is a complex, multithreaded program, in which
416 synchronizing multiple threads can be difficult. This section asks
417 about how you chose to synchronize this particular type of activity.
421 Whereas the other sections primarily ask ``what'' and ``how,'' the
422 rationale section concentrates on ``why.'' This is where we ask you to
423 justify some design decisions, by explaining why the choices you made
424 are better than alternatives. You may be able to state these in terms
425 of time and space complexity, which can be made as rough or informal
426 arguments (formal language or proofs are unnecessary).
429 An incomplete, evasive, or non-responsive design document or one that
430 strays from the template without good reason may be penalized.
431 Incorrect capitalization, punctuation, spelling, or grammar can also
432 cost points. @xref{Project Documentation}, for a sample design document
433 for a fictitious project.
436 @subsubsection Source Code
438 Your design will also be judged by looking at your source code. We will
439 typically look at the differences between the original Pintos source
440 tree and your submission, based on the output of a command like
441 @code{diff -urpb pintos.orig pintos.submitted}. We will try to match up your
442 description of the design with the code submitted. Important
443 discrepancies between the description and the actual code will be
444 penalized, as will be any bugs we find by spot checks.
446 The most important aspects of source code design are those that specifically
447 relate to the operating system issues at stake in the project. For
448 example, the organization of an inode is an important part of file
449 system design, so in the file system project a poorly designed inode
450 would lose points. Other issues are much less important. For
451 example, multiple Pintos design problems call for a ``priority
452 queue,'' that is, a dynamic collection from which the minimum (or
453 maximum) item can quickly be extracted. Fast priority queues can be
454 implemented many ways, but we do not expect you to build a fancy data
455 structure even if it might improve performance. Instead, you are
456 welcome to use a linked list (and Pintos even provides one with
457 convenient functions for sorting and finding minimums and maximums).
459 Pintos is written in a consistent style. Make your additions and
460 modifications in existing Pintos source files blend in, not stick out.
461 In new source files, adopt the existing Pintos style by preference, but
462 make your code self-consistent at the very least. There should not be a
463 patchwork of different styles that makes it obvious that three different
464 people wrote the code. Use horizontal and vertical white space to make
465 code readable. Add a brief comment on every structure, structure
466 member, global or static variable, typedef, enumeration, and function
468 existing comments as you modify code. Don't comment out or use the
469 preprocessor to ignore blocks of code (instead, remove it entirely).
470 Use assertions to document key invariants. Decompose code into
471 functions for clarity. Code that is difficult to understand because it
472 violates these or other ``common sense'' software engineering practices
475 In the end, remember your audience. Code is written primarily to be
476 read by humans. It has to be acceptable to the compiler too, but the
477 compiler doesn't care about how it looks or how well it is written.
479 @node Legal and Ethical Issues
480 @section Legal and Ethical Issues
482 Pintos is distributed under a liberal license that allows free use,
483 modification, and distribution. Students and others who work on Pintos
484 own the code that they write and may use it for any purpose.
485 Pintos comes with NO WARRANTY, not even for MERCHANTABILITY or FITNESS
486 FOR A PARTICULAR PURPOSE.
487 @xref{License}, for details of the license and lack of warranty.
489 @localhonorcodepolicy{}
491 @node Acknowledgements
492 @section Acknowledgements
494 The Pintos core and this documentation were originally written by Ben
495 Pfaff @email{blp@@cs.stanford.edu}.
497 Additional features were contributed by Anthony Romano
500 The GDB macros supplied with Pintos were written by Godmar Back
501 @email{gback@@cs.vt.edu}, and their documentation is adapted from his
504 The original structure and form of Pintos was inspired by the Nachos
505 instructional operating system from the University of California,
506 Berkeley (@bibref{Christopher}).
508 The Pintos projects and documentation originated with those designed for
509 Nachos by current and former CS 140 teaching assistants at Stanford
510 University, including at least Yu Ping, Greg Hutchins, Kelly Shaw, Paul
511 Twohey, Sameer Qureshi, and John Rector.
513 Example code for monitors (@pxref{Monitors}) is
514 from classroom slides originally by Dawson Engler and updated by Mendel
522 Pintos originated as a replacement for Nachos with a similar design.
523 Since then Pintos has greatly diverged from the Nachos design. Pintos
524 differs from Nachos in two important ways. First, Pintos runs on real
525 or simulated 80@var{x}86 hardware, but Nachos runs as a process on a
526 host operating system. Second, Pintos is written in C like most
527 real-world operating systems, but Nachos is written in C++.
529 Why the name ``Pintos''? First, like nachos, pinto beans are a common
530 Mexican food. Second, Pintos is small and a ``pint'' is a small amount.
531 Third, like drivers of the eponymous car, students are likely to have
532 trouble with blow-ups.