Introduction
************

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.  During the PintOS tasks, you and your group will strengthen its support in two of these areas. You will also add a virtual memory implementation.

PintOS could, theoretically, run on a regular IBM-compatible PC. Unfortunately, it is impractical to supply every student with a dedicated PC for use with PintOS.  Therefore, we will be running PintOS 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 particular, we will be using the QEMU simulator.  PintOS has also been tested with the VMware Player.

These tasks are hard. The PintOS exercise have a reputation of taking a lot of time, and 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 version of the exercise has been adapted for use at Imperial College London, and is significantly different to the original exercise designed at Stanford University. It's recommended that you only use the Imperial version of the documentation to avoid unnecessary confusion.

This chapter explains how to get started working with PintOS.  You should read the entire chapter before you start work on any of the tasks.

Getting Started
===============

To get started, you'll have to log into a machine that PintOS can be built on. localmachines We will test your code on these machines, and the instructions given here assume this environment. We do not have the manpower to provide support for installing and working on PintOS on your own machine, but we provide instructions for doing so nonetheless (see Installing PintOS).

If you are using bash (the default shell for CSG-run machines), several PintOS utilities will already be in your PATH. If you are not using bash on a CSG-run machine, you will need to add these utilities manually.

localpathsetup

Source Tree Overview
--------------------

For Task 0 each student has been provided with a Git repository on the department's GitLab server that contains the files needed for this exercise. To obtain this initial skeleton repository you will need to clone it into your local workspace. You can do this with the following command:

     git clone localindivgitpath

replacing <login> with your normal college login.

For the remaining tasks, each group will be provided with a Git repository on the department's GitLab server that contains the files needed for the entire PintOS project. To obtain this skeleton repository you will need to clone it into your local workspace. You can do this with the following command:

     git clone localgitpath

replacing <gnum> with your group number, which can be found on the GitLab website.

You should work on the files in your local workspace, making regular commits back to the corresponding Git repository. Your final submissions will be taken from these GitLab repositories, so make sure that you push your work to them correctly.

Let's take a look at what's inside the full PintOS repository. Here's the directory structure that you should see in pintos/src:

devices/

     Source code for I/O device interfacing: keyboard, timer, disk, etc. You will modify the timer implementation in task 0.  Otherwise you should have no need to change this code.

threads/

     Source code for the base kernel, which you will modify in task 1.

userprog/

     Source code for the user program loader, which you will modify in task 2.

vm/

     An almost empty directory.  You will implement virtual memory here in task 3.

filesys/

     Source code for a basic file system.  You will use this file system in tasks 2 and 3.

lib/

     An implementation of a subset of the standard C library.  The code in this directory is compiled into both the PintOS kernel and, starting from task 2, 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 task.  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 tasks 2 and 3.

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.

Building PintOS
---------------

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

localcrossbuild

After the build has completed, you will find the following 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 GDB) or backtrace (see 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.

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 run alarm-multiple, which passes the arguments run alarm-multiple to the PintOS kernel.  In these arguments, run instructs the kernel to run a test and alarm-multiple is the test to run.

PintOS boots and runs the alarm-multiple test program, which outputs a few screenfulls of text. 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. You can run the simulator with a debugger (see GDB). You can also set the amount of memory to give the VM.

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.

Testing
=======

To help you ensure that your code will compile and run as expected in our testing environment we have provided you with a Lab Testing Service: LabTS.  LabTS will clone your git repository and run several automated test process over your work. This will happen automatically when you submit your work, but can also be requested during the course of each task.

You can access the LabTS webspages at https://teaching.doc.ic.ac.uk/labts. Note that you will be required to log-in with your normal college username and password.

If you click through to the pintos exercise you will see a list of the different versions of your work that you have pushed. Next to each commit you will see a button that will allow you to request that this version of your work is run through the automated test process for the currently viewed milestone. If you click on this button your work will be tested (this may take a few minutes) and the results will appear om the relevant column.

Important: submitted code that fails to compile and run on LabTS will be awarded 0 marks for the automated tests grade! You should be periodically (but not continuously) testing your code on LabTS. If you are experiencing problems with the compilation or execution of your code then please seek help/advice as soon as possible.

Your automated test result grade will be based on our test suite. Each task has several tests, each of which has a name beginning with tests. To completely test your submission, invoke make check from the task 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. You can run make grade to see the automated test results output in the same format as will be presented to the markers.

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/devices/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='...'.

All of the tests and related files can be found in pintos/src/tests. Before we test your submission, we will replace the contents of this directory by a pristine, unmodified copy, to ensure that the correct tests are used. Thus, you can freely modify any of the tests if that helps in your debugging, but we will run our automated tests on the originals.

All software has bugs, so it is possible that 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 the full test suite. Your code has to work properly in the general case and not just for the test cases we supply. We will be asking questions about the general case during the code review sessions, so you won't be able to get away with it. For example, it would be unacceptable to explicitly base the kernel's behaviour on the name of the running test case. Such attempts to side-step the test cases will be spotted during the code review process and will receive no credit. If you think your solution may be in a gray area here, please ask us about it.

Debugging versus Testing
------------------------

The QEMU simulator you will be using to run PintOS only supports real-time simulations. This has ramifications with regards to both testing and debugging.

Whilst reproducibility is in general extremely useful for debugging, running PintOS in QEMU is not necessarily deterministic. You should keep this in mind when testing for bugs in your code. In each run, timer interrupts will come at irregularly spaced intervals, meaning that bugs may appear and disappear with repeated tests. Therefore, it's very important that you run your tests at a least few times. No number of runs can guarantee that your synchronisation is perfect, but the more you do, the more confident you can be that your code doesn't have major flaws.

Important: the PintOS kernel is written for a single-cored CPU, which helps to limit the possible interleavings of concurrently executing threads. However, as you have no control over the occurence of timer interrupts, you will still need to consider the implications of your code being interrupted at almost any arbitrary point. Much of our assessment will be conducted as a ``demonic'' scheduler that chooses the ``worst-case'' possibilities.

Submission
==========

As you work, you should add, commit and push your changes to your git repository. Your GitLab repository should contain the source code, header files and make files for your OS.

Prior to submission, you should check the state of your GitLab repository using the LabTS webpages at https://teaching.doc.ic.ac.uk/labts. If you click through to the pintos exercise you will see a list of the different versions of your work that you have pushed to the master branch of your repository. Next to each commit you will see a link to that commit on GitLab as well as a button to submit that version of your code for assessment.

You should submit the version of your code that you consider to be "final" for each task. You can change this later, as usual, by submitting a different version of your code. The submission button on LabTS will be replaced with a green confirmation message if the submission has been sucessful.

For each pintos task you will also need to submit a design document (designT#.pdf) directly to Scientia. Your submission must be signed off as a group on Scientia in the usual way.

Grading
=======

We will grade each pintos task over 3 catagories:

  * automated tests: your score from the automated test results.

  * code review: an assessment of your design quality and efficiency.

  * design document: your answers to the task's design document questions.

The marks for each pintos task will contribute to both your coursenumber Operating Systems coursework mark and your labnumber Computing Practical 2 exercises mark.

For pintos task 0, part A will make up all of the task's Operating Systems coursework grade, while part B will make up all of the task's Computing Practical 2 grade.

For all other pintos tasks, the automated tests will count for 40% of each task's Computing Practical 2 grade with the code review making up the other 60%. The design document will count for 100% of the Operating Systems coursework grade for each of these tasks.

Note that some of the automated tests may be zero-weighted. These tests help us to identify likely design issues in your code and will probably affect your code review mark.

The weighting of the pintos tasks is 10%, 20%, 30% and 40% for each of task 0, task 1, task 2 and task 3 respectively. JMC students are not assessed on task 3, but have the same relative weighting for task 0, task 1 and task 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.

Important: Don't forget that design quality and efficiency will account for 60% of each task's labnumber Computing Practical 2 grade and that the design documents will make up your entire coursenumber Operating Systems coursework mark. It is, therefore, better to spend a day or two writing a good design document and thinking about the efficiency and edge-cases of your code, than it is to spend that time trying to get the last 5% of the points for the automated tests and then having to rush through writing the design document in the last 15 minutes.

Design Document
...............

We will provide you with a design document template for each task. For each significant part of a task, 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 roughly 25 words.

     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 suggestion of 25 words is a guideline intended to save your time and avoid duplication with later areas of the design document.

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 alone, 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 of your design decisions, by explaining why the choices you made are better than alternatives you considered. You may be able to state these justifications in terms of time and space complexity, which can be made as rough or informal arguments (formal language or proofs are unnecessary).

Any incomplete, evasive, or non-responsive answers to design document questions or those that stray from the provided template without good reason may be penalised. Additionally, any design docuement that does not match the reality of your implementation may be penalised unless any descrepencies are clearly stated and explained. Incorrect capitalization, punctuation, spelling, or grammar may also cost points if this impedes our reading of your design document. See Task Documentation, for an example design document for a fictitious task.

Important: You should carefully read the design document for a task before you begin writing any code. The questions we ask should help you identify some of the tricky corner cases that your implementation will be expected to handle.

Source Code
...........

Your design will also be judged by reviewing your source code with you during interactive code review sessions. 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 or reviewing the Git commits directly on GitLab. 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 penalised, as will be any bugs we find by spot checks during the code review sessions.

The most important aspects of source code design are those that specifically relate to the operating system issues at stake in the task. It is important that you consider the efficiency of your operating system design choices, but other issues are much more 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. Your additions and modifications do not have to be in the same style as the existing PintOS source files, but you should ensure that your code style is self-consistent. There should not be a patchwork of different styles that makes it obvious that three or four 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. Use phase-level comments within fuctions to help explain longer, or more complicated, behaviour. Update existing comments as you modify code. Don't comment out or use the preprocessor to ignore blocks of code (instead, remove it entirely - remember you have Git if you need to get it back). 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 penalised during the code review sessions.

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. See Coding Standards for additional guidance.

Legal and Ethical Issues
========================

PintOS is distributed under a liberal license that allows free use, modification, and distribution of this material. 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 License, for details of the license and lack of warranty.

localhonorcodepolicy

Acknowledgements
================

The PintOS core kernel 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 tasks 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 Monitors) is from classroom slides originally by Dawson Engler and updated by Mendel Rosenblum.

localcredits

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

So, 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.