CPSC 431, Fall 2016
Lab 4: Introduction to Pintos OS /
Assignment: Implementing Sleep

In this lab, you will start working with the Pintos operating system. Pintos is an educational operating system from Stanford university, where it is used for four long projects. In the assignment for this lab, you will do the first part of their Project 1. We will continue Project 1 in the next assignment, and we then decide how much more we want to do with Pintos. The in-class part of the lab introduces Pintos and shows how to compile, run, and debug it. Project 1 uses a kernel-only version of Pintos, and we will stick to that for now.

Pintos is meant to be run as a virtual machine in an x86 emulator. For Project 1, it is run using an emulator named Bochs by default. A slightly customized version of Bochs, modified to work better with Pintos, is installed on the lab computers in Lansing and Rosenberg. You will not run Bochs directly; instead, you will run a script that starts Bochs and tells it to load Pintos.

The source code for Pintos is in the directory /classes/cs431/pintos-src. This is the original source from the full Pintos distribution, with just a few changes. (I deleted a couple of directories that contain auxiliary materials and added some lines to a Makefile to make it possible to check parts of Project 1 instead of checking the entire project.) The full original distribution, including the .git metadata, is in /classes/cs431/pintos-original.

For this assignment and later Pintos assignments, you have the option of working with a partner. The assignment includes a written report, as discussed below. If you work with a partner, you should turn in only one copy of your work, and you should make sure that both names are on the written report.

The programming for this lab is not very long. We can discuss the due date in class on Wednesday.

Running Pintos OS

Before you can begin, you need to modify your PATH environment variable to include the Pintos scripts. It's a good idea to put the command for doing that into your .bashrc file so that you will never have to enter the command again. Open your .bashrc file in a text editor and add the following command to the end of the file:

export PATH="$PATH:/usr/local/pintos/bin"

(In case you don't know what that means, make sure that you are in your home directory, and give the command xed .bashrc to edit the file, add the above line, and save the file. The change won't take effect until you open a new Terminal window, so do that now. Give the command pintos in the new terminal. If things are set up correctly, it will print out some usage info.)


To start working with Pintos, copy /classes/cs431/pintos-src into your own account. Change into that directory, then into the subdirectory named threads. Run make. That is, simply give the command

make

This will build the operating system. The output will be in a subdirectory named build. You can run Pintos from either the original threads directory or from inside build (but later, when running the debugger, you should be inside build).

Note that when you make a change to the source code, you can run make again to rebuild the kernel. The make command will only re-compile files that you have modified.

The version of the kernel that is built by running make in the kernel directory is kernel-only. That is, there are no user mode processes. This severely limits what it can do. In particular, there is no way for you to provide input at run time, and there is no way to specify an external program to run. To make it possible for the kernel to do anything at all, several small test programs are actually compiled into the kernel, and you can tell the OS to run one of those programs when it boots. As an example, give the command

pintos run alarm-single

This starts the Bochs emulator, loads the Pintos kernel and starts it running, and tells the kernel to call the test program named "alarm-single". The actual test program sources are in .c files the directory pintos-src/tests/threads; the source for the alarm-single test is in the file named alarm-wait.c. If you want to modify a test to do something different, for your own testing purposes, you can modify the file where the test is defined. To see that this works, try adding the line printf("Hello World!!\n"); to the function test_alarm_single in the file alarm-wait.c; run make and give the command pintos run alarm-single again. However, you should not make a permanent change to test_alarm_wait or the other existing tests, since those tests will be used to check your work for the assignment.

It is also possible to add a completely new "test" to Pintos, containing arbitrary code. To do that, you can add a function such as

void test_mycode() {
    printf("\nHello World!\n\n");
    while (1) {
       timer_msleep(3000);
       printf("Hello Again three seconds later.\n");
    }
}

Add this to, say, the file alarm-wait.c. You also need to add a declaration of the function ("extern test_func test_mycode;") to pintos-src/tests/threads/tests.h, and add a new element ('{"mycode", test_mycode},') to the list of tests in pintos-src/tests/threads/tests.c. You can then make the kernel again, and run the test with the command pintos run mycode.

When you run Pintos in this way, the command will open a separate window for the Bochs emulator's GUI. You will need to shut down the emulator by clicking the power icon in the top right corner of the emulator window. Pintos has been set up to send its output both to the terminal window and to the emulator window, so the emulator window is sort of useless for now (especially if you are working on Pintos remotely, through ssh to one of the lab computers). To run the test without a separate Bochs emulator window, add the -v option to the pintos command:

pintos  -v  --  run alarm-single

The extra "--" is there to separate the -v option from the command that will be sent to the kernel. You will need to use Control-C in the terminal window to kill the emulator! Otherwise, the emulator will just sit there forever with the kernel continuously running its idle thread.

(Pintos has the function timer_msleep for sleeping for a specified number of milliseconds. However, the system will not actually measure time properly unless you add the option "-r" to the pintos command. For example,

pintos -r -- run mycode

The "r" stands for "real time." If you don't add the "-r" option, it is likely that sleep times will be much less than expected. Also, the time between ticks, which should be 1/100 second, will be much shorter than that. But unless you are trying for correct real time measurements, this is not important.)


As you start working on Pintos, you might find that you need to do some debugging. You might want to read Appendix E, Debugging, in the Pintos documentation. In many cases, the simplest way to debug is to add appropriate printf statements to the code. The documentation talks about some other possibilities that are specific to Pintos. Here, I will just note how to use the gdb debugger, which can be particularly useful if you run into a segfault.

To use gdb with Pintos, you will need two Terminal windows. You will run Pintos in one of the windows and the debugger in the other. Both Pintos and gdb need to be run with special commands.

In one window, run Pintos with the --gdb option. This can be done either in the threads directory or in the build subdirectory. For example,

pintos --gdb -v -- run alarm_multiple

In the second window, you should be in the build directory. Use the following command to run gdb for debugging the Pintos kernel:

pintos-gdb kernel.o

In the same window, at the (gdb) prompt, give the command:

debugpintos

This will connect gdb to the Bochs emulator where the kernel is running. You can then use all the usual gdb commands. For example, if you want to see the sequence of steps that Pintos goes through as it boots and initializes the system, you can set a breakpoint at the main function with the command

break main

and then use the "continue" command to run the kernel, stopping at the beginning of main. Use the "n" or "next" command to step through main.


You should try running Pintos. Spend some time exploring the source code. Try making some of the modifications described above. Try running Pintos with the debugger. If you have time left during class, you can start thinking about the following assignment.

Assignment: Implement timer_sleep in Pintos OS

For this assignment, you will do part of Project 1 from the Pintos OS manual. The first assignment is the "alarm clock" part of the project. It is not a large assignment. For this assignment, you must modify the definition of the function timer_sleep(), which is specified in the header file devices/timer.h and defined in the cooresponding C file devices/timer.c. You might also need to work on threads in the files thread.h and/or thread.c. Of course, you will also need to know about other parts of the system, including perhaps the synchronization primitives, defined in synch.h and synch.c, and the Pintos version of linked lists, defined in lib/kernel/list.h and lib/kernel/list.c. (We used Pintos lists in Lab 2.) All of the files are in the pintos_src directory, which you have already copied into your account and have used in the first part of the lab.

The function timer_sleep(int64_t ticks) puts the current thread (the one in which the function is executed) to sleep for ticks ticks of the timer device. That is, the function will not return until at least that number of ticks have occurred. The function already has a working implementation, but it uses "busy waiting," where the function runs in a while loop until the specified number of ticks have occurred. This is, of course, an awful way to do it! The assignment is to change the implementation so that the current thread is blocked. In the blocked state, the thread will not consume any processing time. Of course, a different thread will have to wake it up when the time comes to do that.

You can do this assignment in less than fifty lines of code, but that doesn't mean that it's easy. You will have to spend some time understanding the system before you can modify it. You might start by figuring out exactly what happens when a timer tick interrupt occurs.

You should read the background material, Section 2.1, for Project 1 in the Pintos documentation. It would also be useful to look at the parts of the reference guide on threads (Section A.2) and synchronization (Section A.3). (The links in this paragraph will only work on campus. For off-campus use, you could try the documentation at Stanford.)

Recall that the kernel-only version of Pintos that is used in Project 1 has several tests compiled into the kernel. The tests for timer_sleep are named alarm-single, alarm-multiple, alarm-negative, alarm-zero, and alarm-simultaneous. You can run them from the build directory with commands such as

pintos run alarm-single

or, if you want to avoid opening the extra Bochs GUI window,

pintos -v -- run alarm-single

You can also ask the system to check whether your code runs the tests correctly. Make sure that you are in the build directory, and enter the command

make check-alarm

The five tests will be run in the background, and you will be told whether you pass or fail each test. Unless you make a change to the code, running this command a second time will only tell you that there is "Nothing to be done for 'check-alarm'". (If you really want to run the tests again without making any changes in the code, give the command rm tests/threads/*.result to remove the results from the previous run.)

Requirements: Your code should pass the five tests, but that is not sufficient to get full credit. I will look at and evaluate your code. In particular, I will look carefully at how you do synchronization. In addition to the program, you should write a short report in which you explain the modifications that you made to the code and how they are supposed to work to implement timer_sleep without busy waiting. You should try to justify your design decisions. The written report should be in a file in the top level of your pintos-src. You should copy that directory into your homework folder in /classes/cs431/homework. Please rename the copy pintos-alarm to distinguish it from later Pintos assignments.

As noted above, you can work with a partner on this assignment. You, or you and your partner, should develop your own ideas for the assigment. Note that there are many ways to approach the problem, and it is not likely that any two versions will have exactly the same approach. (I did the assignment twice, once using semaphores and once by enabling/disabling interrupts.)