From b5f0874cd96ee2a62aabc645b9626c2749cb6a01 Mon Sep 17 00:00:00 2001 From: manuel Date: Mon, 26 Mar 2012 12:54:45 +0200 Subject: initial pintos checkin --- doc/pintos_1.html | 788 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 788 insertions(+) create mode 100644 doc/pintos_1.html (limited to 'doc/pintos_1.html') 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 @@ + + + + + +Pintos Projects: Introduction + + + + + + + + + + + + + + + + + + + +

[ << ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

+ +

1. Introduction

+ +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 1.4 Acknowledgements.) +

+ +So ... Welcome to Pintos. Pintos is a simple operating system framework for +the 80x86 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. +

+ +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 80x86 CPU and its peripheral devices accurately +enough that unmodified operating systems and software can run under it. +In class we will use the +Bochs and +QEMU simulators. Pintos has also been tested with +VMware Player. +

+ +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. +

+ +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. +

+ + +

+ +

1.1 Getting Started

+ +

+ +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 (ssh.tilab.tuwien.ac.at), 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. +

+ +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 PATH environment variable. +

+ +Assuming that you extracted the pintos tarball to $HOME/pintos, +you need to add pintos' utils directory to your PATH +environment variable. +

PATH=$HOME/pintos/src/utils:$PATH +
It is a good idea to add this line to your $HOME/.bash_profile +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. +

+ + +

+ +

1.1.1 Source Tree Overview

+ +

+ +Here's the directory structure that you should see in pintos/src: +

+ +

intro/ +: 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. +
+ +
+
threads/ +: Source code for the base kernel, which is the focus of project 1. +
+ +
+
userprog/ +: 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. +
+ +
+
vm/ +: An almost empty directory. You will implement virtual memory here in +project 2. +
+ +
+
filesys/ +: Source code for a basic file system. You will use this file system, +but do not need to modify it in this course. +
+ +
+
devices/ +: 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. +
+ +
+
lib/ +: 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 +#include <...> notation. You should have little need to +modify this code. +
+ +
+
lib/kernel/ +: 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 #include <...> +notation. +
+ +
+
lib/user/ +: 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 +#include <...> notation. +
+ +
+
tests/ +: 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. +
+ +
+
examples/ +: Example user programs for use in project 0, and also project 2. +
+ +
+
misc/ +
utils/ +: These files may come in handy if you decide to try working with Pintos +on your own machine. Otherwise, you can ignore them. +

+ + +

+ +

1.1.2 Building Pintos

+ +

+ +As the next step, build the source code supplied for +the first project. First, cd into the intro +directory. Then, issue the make command. This will create a +build directory under intro, populate it with a +Makefile and a few subdirectories, and then build the kernel +inside. The entire build should take less than 30 seconds. +

+ +Following the build, the following are the interesting files in the +build directory: +

+ +

Makefile +: A copy of pintos/src/Makefile.build. It describes how to build +the kernel. See Adding Source Files, for more information. +
+ +
+
kernel.o +: 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 D.5 GDB) or backtrace (see section D.4 Backtraces) on it. +
+ +
+
kernel.bin +: Memory image of the kernel, that is, the exact bytes loaded into +memory to run the Pintos kernel. This is just kernel.o 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. +
+ +
+
loader.bin +: 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. +

+ +Subdirectories of build contain object files (.o) and +dependency files (.d), both produced by the compiler. The +dependency files tell make which source files need to be +recompiled when other source or header files are changed. +

+ + +

+ +

1.1.3 Running Pintos

+ +

+ +We've supplied a program for conveniently running Pintos in a simulator, +called pintos. In the simplest case, you can invoke +pintos as pintos argument.... Each +argument is passed to the Pintos kernel for it to act on. +

+ +Try it out. First cd into the newly created build +directory. Then issue the command +pintos -kernel-test run alarm-multiple, +which passes the arguments run alarm-multiple to the Pintos +kernel. In these arguments, run, together with the kernel +option -kernel-test, instructs the kernel to run a test and +alarm-multiple is the test to run. +

+ +This command creates a bochsrc.txt 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 alarm-multiple 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. +

+ +(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 -v option to disable X output: +pintos -v -- -kernel-test run alarm-multiple.) +

+ +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 pintos. 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 +stdin and stdout. You can log serial output to a file by +redirecting at the +command line, e.g. pintos run alarm-multiple > logfile. +

+ +The pintos 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 --, so that the whole command looks like +pintos option... -- argument.... Invoke +pintos without any arguments to see a list of available options. +Options can select a simulator to use: the default is Bochs, but +--qemu selects QEMU. You can run the simulator +with a debugger (see section D.5 GDB). You can set the amount of memory to give +the VM. Finally, you can select how you want VM output to be displayed: +use -v to turn off the VGA display, -t to use your +terminal window as the VGA display instead of opening a new window +(Bochs only), or -s to suppress serial input from stdin +and output to stdout. +

+ +The Pintos kernel has commands and options other than run. +These are not very interesting for now, but you can see a list of them +using -h, e.g. pintos -h. +

+ + +

+ +

1.1.4 Debugging versus Testing

+ +

+ +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 pintos invokes it +by default. +

+ +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. +

+ +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. +

+ +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 pintos with the option -j seed, timer +interrupts will come at irregularly spaced intervals. Within a single +seed value, execution will still be reproducible, but timer +behavior will change as seed is varied. Thus, for the highest +degree of confidence you should test your code with many seed values. +

+ +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 pintos with +a different option, -r, 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 -j and -r are mutually exclusive. +

+ +The QEMU simulator is available as an +alternative to Bochs (use --qemu when invoking +pintos). The QEMU simulator is much faster than Bochs, but it +only supports real-time simulation and does not have a reproducible +mode. +

+ + +

+ +

1.2 Grading

+ +

+ +We will grade your assignments based on test results and design quality, +inspecting both your implementation and your design documents. +

+ + +

+ +

1.2.1 Testing

+ +

+ +Your test result grade will be based on our tests. Each project has +several tests, each of which has a name beginning with tests. +To completely test your submission, invoke make check from the +project build directory. This will build and run each test and +print a "pass" or "fail" message for each one. When a test fails, +make check also prints some details of the reason for failure. +After running all the tests, make check also prints a summary +of the test results. +

+ +For project 1, the tests will probably run faster in Bochs. For the +other projects, they will run much faster in QEMU. +make check will select the faster simulator by default, but +you can override its choice by specifying SIMULATOR=--bochs or +SIMULATOR=--qemu on the make command line. +

+ +You can also run individual tests one at a time. A given test t +writes its output to t.output, then a script scores the +output as "pass" or "fail" and writes the verdict to +t.result. To run and grade a single test, make +the .result file explicitly from the build directory, e.g. +make tests/threads/alarm-multiple.result. If make says +that the test result is up-to-date, but you want to re-run it anyway, +either run make clean or delete the .output file by hand. +

+ +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 VERBOSE=1 on the make command line, as in +make check VERBOSE=1. You can also provide arbitrary options to the +pintos run by the tests with PINTOSOPTS='...', +e.g. make check PINTOSOPTS='-j 1' to select a jitter value of 1 +(see section 1.1.4 Debugging versus Testing). +

+ +All of the tests and related files are in pintos/src/tests. +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. +

+ +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. +

+ +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. +

+ + +

+ +

1.2.2 Design

+ +

+ +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. +

+ +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. +

+ + +

+ +

1.2.2.1 Design Document

+ +

+ +We provide a design document template for each project. For each +significant part of a project, the template asks questions in four +areas: +

+ +

Data Structures +

+ +The instructions for this section are always the same: +

+ +

+Copy here the declaration of each new or changed struct or +struct member, global or static variable, typedef, or +enumeration. Identify the purpose of each in 25 words or less. +

+ +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). +

+ +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. +

+ +

Algorithms +

+ +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. +

+ +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. +

+ +

Synchronization +

+ +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. +

+ +

Rationale +

+ +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). +

+ +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 C. Project Documentation, for a sample design document +for a fictitious project. +

+ + +

+ +

1.2.2.2 Source Code

+ +

+ +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 +diff -urpb pintos.orig pintos.submitted. 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. +

+ +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). +

+ +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. +

+ +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. +

+ + +

+ +

1.3 Legal and Ethical Issues

+ +

+ +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 License, for details of the license and lack of warranty. +

+ +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. +

+ + +

+ +

1.4 Acknowledgements

+ +The Pintos core and this documentation were originally written by Ben +Pfaff blp@cs.stanford.edu. +

+ +Additional features were contributed by Anthony Romano +chz@vt.edu. +

+ +The GDB macros supplied with Pintos were written by Godmar Back +gback@cs.vt.edu, and their documentation is adapted from his +work. +

+ +The original structure and form of Pintos was inspired by the Nachos +instructional operating system from the University of California, +Berkeley ([ Christopher]). +

+ +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. +

+ +Example code for monitors (see section A.3.4 Monitors) is +from classroom slides originally by Dawson Engler and updated by Mendel +Rosenblum. +

+ +For the undergraduate OS Development course at Vienna UT, Rene Freingruber +renefreing@yahoo.de evaluated Pintos, and provided information on +expected work hours and typical pitfalls. Benedikt Huber +benedikt@vmars.tuwien.ac.at adapted Pintos and its documentation to +meet the requirements of the course; Roland Kammerer +kammerer@vmars.tuwien.ac.at created the virtual machine environments +to simplify working outside the lab. +

+ + +

+ +

1.5 Trivia

+ +

+ +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 80x86 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++. +

+ +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. + +

+ + + + + + + +

[ << ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

+
+ +This document was generated +by on March, 6 2012 +using texi2html + + + + -- cgit v1.2.3