summaryrefslogtreecommitdiffstats
path: root/doc/pintos_1.html
diff options
context:
space:
mode:
authormanuel <manuel@mausz.at>2012-03-26 12:54:45 +0200
committermanuel <manuel@mausz.at>2012-03-26 12:54:45 +0200
commitb5f0874cd96ee2a62aabc645b9626c2749cb6a01 (patch)
tree1262e4bbe0634de6650be130c36e0538240f4cbf /doc/pintos_1.html
downloadprogos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.tar.gz
progos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.tar.bz2
progos-b5f0874cd96ee2a62aabc645b9626c2749cb6a01.zip
initial pintos checkin
Diffstat (limited to 'doc/pintos_1.html')
-rw-r--r--doc/pintos_1.html788
1 files changed, 788 insertions, 0 deletions
diff --git a/doc/pintos_1.html b/doc/pintos_1.html
new file mode 100644
index 0000000..e921154
--- /dev/null
+++ b/doc/pintos_1.html
@@ -0,0 +1,788 @@
1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
2 "http://www.w3.org/TR/html40/loose.dtd">
3<HTML>
4<!-- Created on March, 6 2012 by texi2html 1.66 -->
5<!--
6Written by: Lionel Cons <Lionel.Cons@cern.ch> (original author)
7 Karl Berry <karl@freefriends.org>
8 Olaf Bachmann <obachman@mathematik.uni-kl.de>
9 and many others.
10Maintained by: Many creative people <dev@texi2html.cvshome.org>
11Send bugs and suggestions to <users@texi2html.cvshome.org>
12
13-->
14<HEAD>
15<TITLE>Pintos Projects: Introduction</TITLE>
16
17<META NAME="description" CONTENT="Pintos Projects: Introduction">
18<META NAME="keywords" CONTENT="Pintos Projects: Introduction">
19<META NAME="resource-type" CONTENT="document">
20<META NAME="distribution" CONTENT="global">
21<META NAME="Generator" CONTENT="texi2html 1.66">
22<LINK REL="stylesheet" HREF="pintos.css">
23</HEAD>
24
25<BODY >
26
27<A NAME="SEC1"></A>
28<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
29<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top"> &lt;&lt; </A>]</TD>
30<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_2.html#SEC15"> &gt;&gt; </A>]</TD>
31<TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top">Top</A>]</TD>
32<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
33<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
34<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
35</TR></TABLE>
36
37<HR SIZE=2>
38<A NAME="Introduction"></A>
39<H1> 1. Introduction </H1>
40<!--docid::SEC1::-->
41Welcome to the Operating System Development course at Vienna. In this
42course, you will be working with an adapted version of the Pintos
43operating system, which was written by Ben Pfaff (See section <A HREF="pintos_1.html#SEC13">1.4 Acknowledgements</A>.)
44<P>
45
46So ... Welcome to Pintos. Pintos is a simple operating system framework for
47the 80<VAR>x</VAR>86 architecture. It supports kernel threads, loading and
48running user programs, and a file system, but it implements all of
49these in a very simple way. In the Pintos projects, you and your
50project team will strengthen its support in some of these areas.
51</P>
52<P>
53
54Pintos could, theoretically, run on a regular IBM-compatible PC.
55For simplicity, we will run Pintos projects in a system simulator, that is,
56a program that simulates an 80<VAR>x</VAR>86 CPU and its peripheral devices accurately
57enough that unmodified operating systems and software can run under it.
58In class we will use the
59<A HREF="http://bochs.sourceforge.net">Bochs</A> and
60<A HREF="http://fabrice.bellard.free.fr/qemu/">QEMU</A> simulators. Pintos has also been tested with
61<A HREF="http://www.vmware.com/">VMware Player</A>.
62</P>
63<P>
64
65The course at the University of Stanford, where pintos originated, has a
66reputation of taking a lot of time -- we suppose deservedly so.
67We will do what we can to reduce the workload, such as providing a lot
68of support material, but there is plenty of hard work that needs to be done.
69We welcome your feedback. If you have suggestions on how we can reduce the
70unnecessary overhead of assignments, cutting them down to the important
71underlying issues, please let us know.
72</P>
73<P>
74
75This chapter explains how to get started working with Pintos. You
76should read the entire chapter before you start work on any of the
77projects.
78</P>
79<P>
80
81<A NAME="Getting Started"></A>
82<HR SIZE="6">
83<A NAME="SEC2"></A>
84<H2> 1.1 Getting Started </H2>
85<!--docid::SEC2::-->
86<P>
87
88To get started, you'll have to log into a machine that Pintos can be
89built on. There are two possibilities: Either you work on one of the
90machines in the TILAB (<A HREF="ssh.tilab.tuwien.ac.at">ssh.tilab.tuwien.ac.at</A>), or you use
91a virtual machine such as KVM, VMWare Player or VirtualBox. You may
92also setup your own machine to build pintos, but in this case we
93cannot provide support for problems you might encounter.
94We will test your submission in the TILAB environment, and thus you should
95ensure that your code works there.
96</P>
97<P>
98
99Once you've logged into one of these machines, either locally or
100remotely, start out by extracting the pintos tarball, and adding
101our binaries directory to your <CODE>PATH</CODE> environment variable.
102</P>
103<P>
104
105Assuming that you extracted the pintos tarball to <Q><TT>$HOME/pintos</TT></Q>,
106you need to add pintos' <Q><TT>utils</TT></Q> directory to your <CODE>PATH</CODE>
107environment variable.
108<TABLE><tr><td>&nbsp;</td><td class=example><pre>PATH=$HOME/pintos/src/utils:$PATH
109</pre></td></tr></table>It is a good idea to add this line to your <Q><TT>$HOME/.bash_profile</TT></Q>
110startup script (or an equivalent script, if you do not happen to use bash).
111Otherwise, you'll have to type it every time you log in.
112<P>
113
114<A NAME="Source Tree Overview"></A>
115<HR SIZE="6">
116<A NAME="SEC3"></A>
117<H3> 1.1.1 Source Tree Overview </H3>
118<!--docid::SEC3::-->
119<P>
120
121Here's the directory structure that you should see in <Q><TT>pintos/src</TT></Q>:
122</P>
123<P>
124
125</P>
126<DL COMPACT>
127
128<DT><Q><TT>intro/</TT></Q>
129<DD>This directory is used to build the system and run tests for project 0.
130It only contains a Makefile, which describes how to build the system
131and run tests.
132<P>
133
134</P>
135<DT><Q><TT>threads/</TT></Q>
136<DD>Source code for the base kernel, which is the focus of project 1.
137<P>
138
139</P>
140<DT><Q><TT>userprog/</TT></Q>
141<DD>Source code for the user programs. You will complete the user program
142loader in project 0, and rely on the code in this directory in
143project 2.
144<P>
145
146</P>
147<DT><Q><TT>vm/</TT></Q>
148<DD>An almost empty directory. You will implement virtual memory here in
149project 2.
150<P>
151
152</P>
153<DT><Q><TT>filesys/</TT></Q>
154<DD>Source code for a basic file system. You will use this file system,
155but do not need to modify it in this course.
156<P>
157
158</P>
159<DT><Q><TT>devices/</TT></Q>
160<DD>Source code for I/O device interfacing: keyboard, timer, disk, etc.
161You will modify the timer implementation in project 0. Otherwise
162you should have no need to change this code.
163<P>
164
165</P>
166<DT><Q><TT>lib/</TT></Q>
167<DD>An implementation of a subset of the standard C library. The code in
168this directory is compiled into both the Pintos kernel and user
169programs that run under it. In both kernel code
170and user programs, headers in this directory can be included using the
171<CODE>#include &lt;<small>...</small>&gt;</CODE> notation. You should have little need to
172modify this code.
173<P>
174
175</P>
176<DT><Q><TT>lib/kernel/</TT></Q>
177<DD>Parts of the C library that are included only in the Pintos kernel.
178This also includes implementations of some data types that you are
179free to use in your kernel code: bitmaps, doubly linked lists, and
180hash tables. In the kernel, headers in this
181directory can be included using the <CODE>#include &lt;<small>...</small>&gt;</CODE>
182notation.
183<P>
184
185</P>
186<DT><Q><TT>lib/user/</TT></Q>
187<DD>Parts of the C library that are included only in Pintos user programs.
188In user programs, headers in this directory can be included using the
189<CODE>#include &lt;<small>...</small>&gt;</CODE> notation.
190<P>
191
192</P>
193<DT><Q><TT>tests/</TT></Q>
194<DD>Tests for each project. You can modify this code if it helps you test
195your submission, but we will replace it with the originals before we run
196the tests.
197<P>
198
199</P>
200<DT><Q><TT>examples/</TT></Q>
201<DD>Example user programs for use in project 0, and also project 2.
202<P>
203
204</P>
205<DT><Q><TT>misc/</TT></Q>
206<DD><DT><Q><TT>utils/</TT></Q>
207<DD>These files may come in handy if you decide to try working with Pintos
208on your own machine. Otherwise, you can ignore them.
209</DL>
210<P>
211
212<A NAME="Building Pintos"></A>
213<HR SIZE="6">
214<A NAME="SEC4"></A>
215<H3> 1.1.2 Building Pintos </H3>
216<!--docid::SEC4::-->
217<P>
218
219As the next step, build the source code supplied for
220the first project. First, <CODE>cd</CODE> into the <Q><TT>intro</TT></Q>
221directory. Then, issue the <Q><SAMP>make</SAMP></Q> command. This will create a
222<Q><TT>build</TT></Q> directory under <Q><TT>intro</TT></Q>, populate it with a
223<Q><TT>Makefile</TT></Q> and a few subdirectories, and then build the kernel
224inside. The entire build should take less than 30 seconds.
225</P>
226<P>
227
228Following the build, the following are the interesting files in the
229<Q><TT>build</TT></Q> directory:
230</P>
231<P>
232
233</P>
234<DL COMPACT>
235<DT><Q><TT>Makefile</TT></Q>
236<DD>A copy of <Q><TT>pintos/src/Makefile.build</TT></Q>. It describes how to build
237the kernel. See <A HREF="pintos_2.html#Adding Source Files">Adding Source Files</A>, for more information.
238<P>
239
240</P>
241<DT><Q><TT>kernel.o</TT></Q>
242<DD>Object file for the entire kernel. This is the result of linking
243object files compiled from each individual kernel source file into a
244single object file. It contains debug information, so you can run
245GDB (see section <A HREF="pintos_8.html#SEC102">D.5 GDB</A>) or <CODE>backtrace</CODE> (see section <A HREF="pintos_8.html#SEC100">D.4 Backtraces</A>) on it.
246<P>
247
248</P>
249<DT><Q><TT>kernel.bin</TT></Q>
250<DD>Memory image of the kernel, that is, the exact bytes loaded into
251memory to run the Pintos kernel. This is just <Q><TT>kernel.o</TT></Q> with
252debug information stripped out, which saves a lot of space, which in
253turn keeps the kernel from bumping up against a 512 kB size limit
254imposed by the kernel loader's design.
255<P>
256
257</P>
258<DT><Q><TT>loader.bin</TT></Q>
259<DD>Memory image for the kernel loader, a small chunk of code written in
260assembly language that reads the kernel from disk into memory and
261starts it up. It is exactly 512 bytes long, a size fixed by the
262PC BIOS.
263</DL>
264<P>
265
266Subdirectories of <Q><TT>build</TT></Q> contain object files (<Q><TT>.o</TT></Q>) and
267dependency files (<Q><TT>.d</TT></Q>), both produced by the compiler. The
268dependency files tell <CODE>make</CODE> which source files need to be
269recompiled when other source or header files are changed.
270</P>
271<P>
272
273<A NAME="Running Pintos"></A>
274<HR SIZE="6">
275<A NAME="SEC5"></A>
276<H3> 1.1.3 Running Pintos </H3>
277<!--docid::SEC5::-->
278<P>
279
280We've supplied a program for conveniently running Pintos in a simulator,
281called <CODE>pintos</CODE>. In the simplest case, you can invoke
282<CODE>pintos</CODE> as <CODE>pintos <VAR>argument</VAR><small>...</small></CODE>. Each
283<VAR>argument</VAR> is passed to the Pintos kernel for it to act on.
284</P>
285<P>
286
287Try it out. First <CODE>cd</CODE> into the newly created <Q><TT>build</TT></Q>
288directory. Then issue the command
289<CODE>pintos -kernel-test run alarm-multiple</CODE>,
290which passes the arguments <CODE>run alarm-multiple</CODE> to the Pintos
291kernel. In these arguments, <CODE>run</CODE>, together with the kernel
292option <Q><SAMP>-kernel-test</SAMP></Q>, instructs the kernel to run a test and
293<CODE>alarm-multiple</CODE> is the test to run.
294</P>
295<P>
296
297This command creates a <Q><TT>bochsrc.txt</TT></Q> file, which is needed for
298running Bochs, and then invoke Bochs. Bochs opens a new window that
299represents the simulated machine's display, and a BIOS message briefly
300flashes. Then Pintos boots and runs the <CODE>alarm-multiple</CODE> test
301program, which outputs a few screenfuls of text. When it's done, you
302can close Bochs by clicking on the &quot;Power&quot; button in the window's top
303right corner, or rerun the whole process by clicking on the &quot;Reset&quot;
304button just to its left. The other buttons are not very useful for our
305purposes.
306</P>
307<P>
308
309(If no window appeared at all, then you're probably logged in remotely and X
310forwarding is not set up correctly. In this case, you can fix your X
311setup, or you can use the <Q><SAMP>-v</SAMP></Q> option to disable X output:
312<CODE>pintos -v -- -kernel-test run alarm-multiple</CODE>.)
313</P>
314<P>
315
316The text printed by Pintos inside Bochs probably went by too quickly to
317read. However, you've probably noticed by now that the same text was
318displayed in the terminal you used to run <CODE>pintos</CODE>. This is
319because Pintos sends all output both to the VGA display and to the first
320serial port, and by default the serial port is connected to Bochs's
321<CODE>stdin</CODE> and <CODE>stdout</CODE>. You can log serial output to a file by
322redirecting at the
323command line, e.g. <CODE>pintos run alarm-multiple &gt; logfile</CODE>.
324</P>
325<P>
326
327The <CODE>pintos</CODE> program offers several options for configuring the
328simulator or the virtual hardware. If you specify any options, they
329must precede the commands passed to the Pintos kernel and be separated
330from them by <Q><SAMP>--</SAMP></Q>, so that the whole command looks like
331<CODE>pintos <VAR>option</VAR><small>...</small> -- <VAR>argument</VAR><small>...</small></CODE>. Invoke
332<CODE>pintos</CODE> without any arguments to see a list of available options.
333Options can select a simulator to use: the default is Bochs, but
334<Q><SAMP>--qemu</SAMP></Q> selects QEMU. You can run the simulator
335with a debugger (see section <A HREF="pintos_8.html#SEC102">D.5 GDB</A>). You can set the amount of memory to give
336the VM. Finally, you can select how you want VM output to be displayed:
337use <Q><SAMP>-v</SAMP></Q> to turn off the VGA display, <Q><SAMP>-t</SAMP></Q> to use your
338terminal window as the VGA display instead of opening a new window
339(Bochs only), or <Q><SAMP>-s</SAMP></Q> to suppress serial input from <CODE>stdin</CODE>
340and output to <CODE>stdout</CODE>.
341</P>
342<P>
343
344The Pintos kernel has commands and options other than <CODE>run</CODE>.
345These are not very interesting for now, but you can see a list of them
346using <Q><SAMP>-h</SAMP></Q>, e.g. <CODE>pintos -h</CODE>.
347</P>
348<P>
349
350<A NAME="Debugging versus Testing"></A>
351<HR SIZE="6">
352<A NAME="SEC6"></A>
353<H3> 1.1.4 Debugging versus Testing </H3>
354<!--docid::SEC6::-->
355<P>
356
357When you're debugging code, it's useful to be able to run a
358program twice and have it do exactly the same thing. On second and
359later runs, you can make new observations without having to discard or
360verify your old observations. This property is called
361&quot;reproducibility.&quot; One of the simulators that Pintos supports, Bochs,
362can be set up for
363reproducibility, and that's the way that <CODE>pintos</CODE> invokes it
364by default.
365</P>
366<P>
367
368Of course, a simulation can only be reproducible from one run to the
369next if its input is the same each time. For simulating an entire
370computer, as we do, this means that every part of the computer must be
371the same. For example, you must use the same command-line argument, the
372same disks, the same version
373of Bochs, and you must not hit any keys on the keyboard (because you
374could not be sure to hit them at exactly the same point each time)
375during the runs.
376</P>
377<P>
378
379While reproducibility is useful for debugging, it is a problem for
380testing thread synchronization, an important part of most of the projects. In
381particular, when Bochs is set up for reproducibility, timer interrupts
382will come at perfectly reproducible points, and therefore so will
383thread switches. That means that running the same test several times
384doesn't give you any greater confidence in your code's correctness
385than does running it only once.
386</P>
387<P>
388
389So, to make your code easier to test, we've added a feature, called
390&quot;jitter,&quot; to Bochs, that makes timer interrupts come at random
391intervals, but in a perfectly predictable way. In particular, if you
392invoke <CODE>pintos</CODE> with the option <Q><SAMP>-j <VAR>seed</VAR></SAMP></Q>, timer
393interrupts will come at irregularly spaced intervals. Within a single
394<VAR>seed</VAR> value, execution will still be reproducible, but timer
395behavior will change as <VAR>seed</VAR> is varied. Thus, for the highest
396degree of confidence you should test your code with many seed values.
397</P>
398<P>
399
400On the other hand, when Bochs runs in reproducible mode, timings are not
401realistic, meaning that a &quot;one-second&quot; delay may be much shorter or
402even much longer than one second. You can invoke <CODE>pintos</CODE> with
403a different option, <Q><SAMP>-r</SAMP></Q>, to set up Bochs for realistic
404timings, in which a one-second delay should take approximately one
405second of real time. Simulation in real-time mode is not reproducible,
406and options <Q><SAMP>-j</SAMP></Q> and <Q><SAMP>-r</SAMP></Q> are mutually exclusive.
407</P>
408<P>
409
410The QEMU simulator is available as an
411alternative to Bochs (use <Q><SAMP>--qemu</SAMP></Q> when invoking
412<CODE>pintos</CODE>). The QEMU simulator is much faster than Bochs, but it
413only supports real-time simulation and does not have a reproducible
414mode.
415</P>
416<P>
417
418<A NAME="Grading"></A>
419<HR SIZE="6">
420<A NAME="SEC7"></A>
421<H2> 1.2 Grading </H2>
422<!--docid::SEC7::-->
423<P>
424
425We will grade your assignments based on test results and design quality,
426inspecting both your implementation and your design documents.
427</P>
428<P>
429
430<A NAME="Testing"></A>
431<HR SIZE="6">
432<A NAME="SEC8"></A>
433<H3> 1.2.1 Testing </H3>
434<!--docid::SEC8::-->
435<P>
436
437Your test result grade will be based on our tests. Each project has
438several tests, each of which has a name beginning with <Q><TT>tests</TT></Q>.
439To completely test your submission, invoke <CODE>make check</CODE> from the
440project <Q><TT>build</TT></Q> directory. This will build and run each test and
441print a &quot;pass&quot; or &quot;fail&quot; message for each one. When a test fails,
442<CODE>make check</CODE> also prints some details of the reason for failure.
443After running all the tests, <CODE>make check</CODE> also prints a summary
444of the test results.
445</P>
446<P>
447
448For project 1, the tests will probably run faster in Bochs. For the
449other projects, they will run much faster in QEMU.
450<CODE>make check</CODE> will select the faster simulator by default, but
451you can override its choice by specifying <Q><SAMP>SIMULATOR=--bochs</SAMP></Q> or
452<Q><SAMP>SIMULATOR=--qemu</SAMP></Q> on the <CODE>make</CODE> command line.
453</P>
454<P>
455
456You can also run individual tests one at a time. A given test <VAR>t</VAR>
457writes its output to <Q><TT><VAR>t</VAR>.output</TT></Q>, then a script scores the
458output as &quot;pass&quot; or &quot;fail&quot; and writes the verdict to
459<Q><TT><VAR>t</VAR>.result</TT></Q>. To run and grade a single test, <CODE>make</CODE>
460the <Q><TT>.result</TT></Q> file explicitly from the <Q><TT>build</TT></Q> directory, e.g.
461<CODE>make tests/threads/alarm-multiple.result</CODE>. If <CODE>make</CODE> says
462that the test result is up-to-date, but you want to re-run it anyway,
463either run <CODE>make clean</CODE> or delete the <Q><TT>.output</TT></Q> file by hand.
464</P>
465<P>
466
467By default, each test provides feedback only at completion, not during
468its run. If you prefer, you can observe the progress of each test by
469specifying <Q><SAMP>VERBOSE=1</SAMP></Q> on the <CODE>make</CODE> command line, as in
470<CODE>make check VERBOSE=1</CODE>. You can also provide arbitrary options to the
471<CODE>pintos</CODE> run by the tests with <Q><SAMP>PINTOSOPTS='<small>...</small>'</SAMP></Q>,
472e.g. <CODE>make check PINTOSOPTS='-j 1'</CODE> to select a jitter value of 1
473(see section <A HREF="pintos_1.html#SEC6">1.1.4 Debugging versus Testing</A>).
474</P>
475<P>
476
477All of the tests and related files are in <Q><TT>pintos/src/tests</TT></Q>.
478Before we test your submission, we will replace the contents of that
479directory by a pristine, unmodified copy, to ensure that the correct
480tests are used. Thus, you can modify some of the tests if that helps in
481debugging, but we will run the originals.
482</P>
483<P>
484
485All software has bugs, so some of our tests may be flawed. If you think
486a test failure is a bug in the test, not a bug in your code,
487please point it out. We will look at it and fix it if necessary.
488</P>
489<P>
490
491Please don't try to take advantage of our generosity in giving out our
492test suite. Your code has to work properly in the general case, not
493just for the test cases we supply. For example, it would be unacceptable
494to explicitly base the kernel's behavior on the name of the running
495test case. Such attempts to side-step the test cases will receive no
496credit. If you think your solution may be in a gray area here, please
497ask us about it.
498</P>
499<P>
500
501<A NAME="Design"></A>
502<HR SIZE="6">
503<A NAME="SEC9"></A>
504<H3> 1.2.2 Design </H3>
505<!--docid::SEC9::-->
506<P>
507
508We will judge your design based on the design document and the source
509code that you submit. We will read your entire design document and much
510of your source code.
511</P>
512<P>
513
514Don't forget that design quality, including the design document, is 30%
515of your project grade. It
516is better to spend one or two hours writing a good design document than
517it is to spend that time getting the last 5% of the points for tests and
518then trying to rush through writing the design document in the last 15
519minutes.
520</P>
521<P>
522
523<A NAME="Design Document"></A>
524<HR SIZE="6">
525<A NAME="SEC10"></A>
526<H4> 1.2.2.1 Design Document </H4>
527<!--docid::SEC10::-->
528<P>
529
530We provide a design document template for each project. For each
531significant part of a project, the template asks questions in four
532areas:
533</P>
534<P>
535
536</P>
537<DL COMPACT>
538<DT><STRONG>Data Structures</STRONG>
539<DD><P>
540
541The instructions for this section are always the same:
542</P>
543<P>
544
545<BLOCKQUOTE>
546Copy here the declaration of each new or changed <CODE>struct</CODE> or
547<CODE>struct</CODE> member, global or static variable, <CODE>typedef</CODE>, or
548enumeration. Identify the purpose of each in 25 words or less.
549</BLOCKQUOTE>
550<P>
551
552The first part is mechanical. Just copy new or modified declarations
553into the design document, to highlight for us the actual changes to data
554structures. Each declaration should include the comment that should
555accompany it in the source code (see below).
556</P>
557<P>
558
559We also ask for a very brief description of the purpose of each new or
560changed data structure. The limit of 25 words or less is a guideline
561intended to save your time and avoid duplication with later areas.
562</P>
563<P>
564
565</P>
566<DT><STRONG>Algorithms</STRONG>
567<DD><P>
568
569This is where you tell us how your code works, through questions that
570probe your understanding of your code. We might not be able to easily
571figure it out from the code, because many creative solutions exist for
572most OS problems. Help us out a little.
573</P>
574<P>
575
576Your answers should be at a level below the high level description of
577requirements given in the assignment. We have read the assignment too,
578so it is unnecessary to repeat or rephrase what is stated there. On the
579other hand, your answers should be at a level above the low level of the
580code itself. Don't give a line-by-line run-down of what your code does.
581Instead, use your answers to explain how your code works to implement
582the requirements.
583</P>
584<P>
585
586</P>
587<DT><STRONG>Synchronization</STRONG>
588<DD><P>
589
590An operating system kernel is a complex, multithreaded program, in which
591synchronizing multiple threads can be difficult. This section asks
592about how you chose to synchronize this particular type of activity.
593</P>
594<P>
595
596</P>
597<DT><STRONG>Rationale</STRONG>
598<DD><P>
599
600Whereas the other sections primarily ask &quot;what&quot; and &quot;how,&quot; the
601rationale section concentrates on &quot;why.&quot; This is where we ask you to
602justify some design decisions, by explaining why the choices you made
603are better than alternatives. You may be able to state these in terms
604of time and space complexity, which can be made as rough or informal
605arguments (formal language or proofs are unnecessary).
606</DL>
607<P>
608
609An incomplete, evasive, or non-responsive design document or one that
610strays from the template without good reason may be penalized.
611Incorrect capitalization, punctuation, spelling, or grammar can also
612cost points. See section <A HREF="pintos_7.html#SEC93">C. Project Documentation</A>, for a sample design document
613for a fictitious project.
614</P>
615<P>
616
617<A NAME="Source Code"></A>
618<HR SIZE="6">
619<A NAME="SEC11"></A>
620<H4> 1.2.2.2 Source Code </H4>
621<!--docid::SEC11::-->
622<P>
623
624Your design will also be judged by looking at your source code. We will
625typically look at the differences between the original Pintos source
626tree and your submission, based on the output of a command like
627<CODE>diff -urpb pintos.orig pintos.submitted</CODE>. We will try to match up your
628description of the design with the code submitted. Important
629discrepancies between the description and the actual code will be
630penalized, as will be any bugs we find by spot checks.
631</P>
632<P>
633
634The most important aspects of source code design are those that specifically
635relate to the operating system issues at stake in the project. For
636example, the organization of the supplemental page table is an important
637part of virtual memory design, so in the virtual memory project a poorly designed
638pagetable would lose points. Other issues are much less important. For
639example, multiple Pintos design problems call for a &quot;priority
640queue,&quot; that is, a dynamic collection from which the minimum (or
641maximum) item can quickly be extracted. Fast priority queues can be
642implemented many ways, but we do not expect you to build a fancy data
643structure even if it might improve performance. Instead, you are
644welcome to use a linked list (and Pintos even provides one with
645convenient functions for sorting and finding minimums and maximums).
646</P>
647<P>
648
649Pintos is written in a consistent style. Make your additions and
650modifications in existing Pintos source files blend in, not stick out.
651In new source files, adopt the existing Pintos style by preference, but
652make your code self-consistent at the very least. There should not be a
653patchwork of different styles that makes it obvious that three different
654people wrote the code. Use horizontal and vertical white space to make
655code readable. Add a brief comment on every structure, structure
656member, global or static variable, typedef, enumeration, and function
657definition. Update
658existing comments as you modify code. Don't comment out or use the
659preprocessor to ignore blocks of code (instead, remove it entirely).
660Use assertions to document key invariants. Decompose code into
661functions for clarity. Code that is difficult to understand because it
662violates these or other &quot;common sense&quot; software engineering practices
663will be penalized.
664</P>
665<P>
666
667In the end, remember your audience. Code is written primarily to be
668read by humans. It has to be acceptable to the compiler too, but the
669compiler doesn't care about how it looks or how well it is written.
670</P>
671<P>
672
673<A NAME="Legal and Ethical Issues"></A>
674<HR SIZE="6">
675<A NAME="SEC12"></A>
676<H2> 1.3 Legal and Ethical Issues </H2>
677<!--docid::SEC12::-->
678<P>
679
680Pintos is distributed under a liberal license that allows free use,
681modification, and distribution. Students and others who work on Pintos
682own the code that they write and may use it for any purpose.
683Pintos comes with NO WARRANTY, not even for MERCHANTABILITY or FITNESS
684FOR A PARTICULAR PURPOSE.
685See section <A HREF="pintos_11.html#SEC117">License</A>, for details of the license and lack of warranty.
686</P>
687<P>
688
689In the context of the Operating System Development at Vienna University
690of Technology, please respect the spirit and the letter of the honor code
691by refraining from reading any homework solutions available online or
692elsewhere. Reading the source code for other operating system kernels,
693such as Linux or FreeBSD, is allowed, but do not copy code from them literally.
694Please cite the code that inspired your own in your design documentation.
695Additionally, please do not redistribute the modified Pintos environment
696used in this course. It contains partial solutions which might spoil the
697fun for people at other universities.
698</P>
699<P>
700
701<A NAME="Acknowledgements"></A>
702<HR SIZE="6">
703<A NAME="SEC13"></A>
704<H2> 1.4 Acknowledgements </H2>
705<!--docid::SEC13::-->
706The Pintos core and this documentation were originally written by Ben
707Pfaff <A HREF="mailto:blp@cs.stanford.edu">blp@cs.stanford.edu</A>.
708<P>
709
710Additional features were contributed by Anthony Romano
711<A HREF="mailto:chz@vt.edu">chz@vt.edu</A>.
712</P>
713<P>
714
715The GDB macros supplied with Pintos were written by Godmar Back
716<A HREF="mailto:gback@cs.vt.edu">gback@cs.vt.edu</A>, and their documentation is adapted from his
717work.
718</P>
719<P>
720
721The original structure and form of Pintos was inspired by the Nachos
722instructional operating system from the University of California,
723Berkeley ([ <A HREF="pintos_10.html#Christopher">Christopher</A>]).
724</P>
725<P>
726
727The Pintos projects and documentation originated with those designed for
728Nachos by current and former CS 140 teaching assistants at Stanford
729University, including at least Yu Ping, Greg Hutchins, Kelly Shaw, Paul
730Twohey, Sameer Qureshi, and John Rector.
731</P>
732<P>
733
734Example code for monitors (see section <A HREF="pintos_5.html#SEC62">A.3.4 Monitors</A>) is
735from classroom slides originally by Dawson Engler and updated by Mendel
736Rosenblum.
737</P>
738<P>
739
740For the undergraduate OS Development course at Vienna UT, Rene Freingruber
741<A HREF="mailto:renefreing@yahoo.de">renefreing@yahoo.de</A> evaluated Pintos, and provided information on
742expected work hours and typical pitfalls. Benedikt Huber
743<A HREF="mailto:benedikt@vmars.tuwien.ac.at">benedikt@vmars.tuwien.ac.at</A> adapted Pintos and its documentation to
744meet the requirements of the course; Roland Kammerer
745<A HREF="mailto:kammerer@vmars.tuwien.ac.at">kammerer@vmars.tuwien.ac.at</A> created the virtual machine environments
746to simplify working outside the lab.
747</P>
748<P>
749
750<A NAME="Trivia"></A>
751<HR SIZE="6">
752<A NAME="SEC14"></A>
753<H2> 1.5 Trivia </H2>
754<!--docid::SEC14::-->
755<P>
756
757Pintos originated as a replacement for Nachos with a similar design.
758Since then Pintos has greatly diverged from the Nachos design. Pintos
759differs from Nachos in two important ways. First, Pintos runs on real
760or simulated 80<VAR>x</VAR>86 hardware, but Nachos runs as a process on a
761host operating system. Second, Pintos is written in C like most
762real-world operating systems, but Nachos is written in C++.
763</P>
764<P>
765
766Why the name &quot;Pintos&quot;? First, like nachos, pinto beans are a common
767Mexican food. Second, Pintos is small and a &quot;pint&quot; is a small amount.
768Third, like drivers of the eponymous car, students are likely to have
769trouble with blow-ups.
770<A NAME="Project 0--Introducing Pintos"></A>
771<HR SIZE="6">
772<TABLE CELLPADDING=1 CELLSPACING=1 BORDER=0>
773<TR><TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_1.html#SEC1"> &lt;&lt; </A>]</TD>
774<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_2.html#SEC15"> &gt;&gt; </A>]</TD>
775<TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT"> &nbsp; <TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Top">Top</A>]</TD>
776<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos.html#SEC_Contents">Contents</A>]</TD>
777<TD VALIGN="MIDDLE" ALIGN="LEFT">[Index]</TD>
778<TD VALIGN="MIDDLE" ALIGN="LEFT">[<A HREF="pintos_abt.html#SEC_About"> ? </A>]</TD>
779</TR></TABLE>
780<BR>
781<FONT SIZE="-1">
782This document was generated
783by on <I>March, 6 2012</I>
784using <A HREF="http://texi2html.cvshome.org"><I>texi2html</I></A>
785</FONT>
786
787</BODY>
788</HTML>
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-12 02:11:04 +0000