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