No longer valid in 2019

Pintos Laboratory Assignment 3: Execution, Termination and Synchronization of User Programs

Goal

Overview

This assignment covers:

• Execution of multiple user programs in Pintos.
• Synchronization of the user programs.
• Argument passing to the user programs.
• Safe argument passing with system calls.

User Programs

In the previous assignment (Lab 1), you had only one user program running by the operating system. In the Part A of this assignment, you are supposed to implement a fully operational multiprogramming environment, where multiple user programs can be executed at the same time. Programs will be allowed to invoke child user programs and, if needed, may wait for completion of these child programs. In such a multiprogramming environment, synchronization becomes important since programs may access shared data structures concurrently.

Part B of this assignment is to implement argument passing such that programs can read command line arguments. Part B is supposed to teach you how the operating system can pass arguments to user programs, in particular, how it is solved in 80x86 architecture by pushing them into the program's stack.

In Part C you will make the operating sytem more robust by implementing argument validation for system calls. The goal is to make the system safe from misbehaving user programs, i.e. a misbehaving program should not be able to crash the operating system.

Note that in this assignment you are not supposed to implement synchronized access to the file system.

Additional System Calls to Enable Multiprogramming

In this assignment, you will need to implement two new systems calls and extend one system call from the previous lab:

• exec - Loads a program into memory and executes it in its own thread or process.
• wait - Waits for a child process to exit and returns its exit status.
• exit - Terminates a program and deallocates resources occupied by the program, for example, closes all files opened by the program. You inherit this system call from earlier labs and extend it.

Preparation

In addition to the source code which you have already looked at in the second lab, you should read and understand the code in userprog/process.c. This file contains a set of functions that you can use to implement execution of a new user program and argument passing. You have to clearly understand how the user program is loaded into the memory and how it is started.

Preparatory Questions:

Before you begin doing your lab assignment, you have to answer the following set of questions to ensure that you are ready to continue:

1. What is paging?
2. How can you avoid using busy waiting in wait()?
3. Name the data structures in your implementation that will be shared? (At least the ones that you have already implemented.) Which synchronization mechanisms can be applied?
4. What are argc and argv that main in a C program takes as arguments? Where are they stored when the program begins executing?
5. In some system calls the user passes pointers as arguments, which are supposed to point to some data in the user-space (for instance, a pointer to a string with a file name in create()). (a) Specify the situations when accessing the data via that pointer can lead to problems. (b) What can be done about it? (Tip: read "Accessing User Memory" Section).
6. Assume that in the kernel code you have got a pointer to a data in the user space which potentially spans across a few pages. Reconsider the previous question again. Does your solution still work? (Tip: You may present and discuss the solution with your lab assistant before doing the lab if you are unsure about it).

Assignment in detail

Part A

The main part of this assignment is to implement (extend) the following system calls:

pid_t exec (const char *cmd_line)

Runs the executable whose name is given in cmd_line, passing any given arguments, and returns the new process’s program id (pid). Must return pid -1, if the program cannot load or run for any reason.

void exit (int status)

Terminates the current user program, returning the exit code status to the kernel.

int wait (pid_t pid)

Provides synchronization between user programs. Parent process waits until its pid-child process dies (if the child is still running) and receives the child exit code. If the child has finished, wait() should return child's exit value without waiting.

Consider all possible situations with wait() that your program must handle before starting your implementation:

1. Parent exits without calling wait() while the child is still running
2. Child exits before the parent and:
• parent calls wait() afterwards, or
  
• parent will exit without calling wait().
3. Parent calls wait() before the child exits.
4. Re-consider all the situations above under the condition that the child does not exit normally (e.g. it may be killed because of a memory violation).

Each thread can have many children (threads), and the number of threads can vary over time and there is no (fixed) upper limit on the number of threads!

Synchronization is one of the most essential aspects in these assignments. The operating system may work fine in some situations but it can crash or malfunction in the other situations, if synchronization is implemented incorrectly or not sufficiently. Therefore, requirements regarding synchronization are as follows:

• Parts of the functions accessing shared resources must be thread safe (especially in the system calls), e.g. employ synchronization techniques such as locks and semaphores.
• Particularly, access to global objects and data must be synchronized.

Note that in this assignment you are not supposed to implement synchronized access to the file system.

When you do your implementation, don't forget to clean up data structures that you dynamically allocate. Memory leakage is a VERY BAD thing!

Part B

A user program may be called with arguments in the command line. Implement arguments passing, so the arguments of a user program can be accessible within it (details).

At first, you should go into userprog/process.c, find the function setup_stack() and change back the following line:
*esp = PHYS_BASE - 12;
into
*esp = PHYS_BASE;
Now your program will always fail until you implement argument passing. Try to run any user program.

Stop! Before continuing, explain why you have KERNEL PANIC after you have removed "-12". What is wrong and why did the program work before?

The user program with arguments should be called with apostrophes (') from the Pintos command line. For example, pintos --qemu -- run 'insult -s 17', where user program insult is called with arguments -s and 17.

When the user program with arguments is called from exec(), you have to call it like this: exec("insult -s 17").

Although you can parse the string from the command line any way you like, we recommend you to have a look at the function strtok_r(), prototyped in lib/string.h and implemented with thorough comments in lib/string.c. You can find more about it by looking at the man page (run man strtok_r at the prompt). We suggest that you limit the number of arguments to, for example, 32, which will simplify your implementation because you can use a static array of a fixed size to store the parsed arguments.

Necessary details about setting up the stack for this task you can find in Program Startup Details section of the Pintos documentation.

Part C

In this part of the assignment you must make the operating system robust by validating the arguments to the system calls. As long as this validation is not implemented a user program may do for instance create((char*)0,1) causing the kernel to crash when trying to read the name of the file to be created.

Your task is to validate all arguments passed by user programs to the interrupt handler via system calls.

Test programs

Once you have finished both Part A and Part B you can run the tests by issuing make check. Please note that you must do both A and B before you can run the tests; if you have only implemented Part A all tests will fail. For the test script to work you need to add printf("%s: exit(%d)\n", thread-name, thread-exit-value) to the code that is executed when a user process exits or is killed.

When you have finished all parts of this lab all 50 tests should pass. As always when testing: passing all tests is not a guarantee that the code is correct.

Helpful Information

Lab demonstration

In order to reduce time for demos and maximize time for questions, please make sure you can be fluent describing all your code and answer questions on implementation details. Hesitations and discussions are time consuming and this time is not available to other groups for solving problems. Please be ready to describe the creation of a new process, waiting for a process and terminating a process as well as stack building and pointer checking.

In order to help you checking your code, below is a list of issues commonly met when grading this lab. Remember passing all the tests and complying with this check list is not necessarily enough. You need to make sure yourself lab assistants won't point out any other issue.

• SYS_EXEC:
• Parent process waits for new child process to load correctly before returning.
• Structure to synchronize parent and child when starting a new process is freed, if any.
• Catches all errors until the process actually starts and reports a failure if necessary (think about executing a file that is not an binary executable, such as a shopping list).
• SYS_WAIT:
• Catches return value once. Any further attempt returns -1.
• A parent thread/process cannot wait for a process that is not his children.
• Free memory in all parent/child termination cases (parent exits first, children exits first, parent doesn't wait children at all, parent and/or children are killed by kernel).
• SYS_EXIT:
• Close all opened files (task from lab1).
• Compliant with SYS_WAIT, especially regarding freeing memory in all cases.
• Pointer checking:
• All bytes are checked. Think about the case of strings and buffers. Consider they be so big that they start in a page, cover a whole second page and finishes in a third page. Think about the second page belonging to another process and therefore forbidden to read or write by thread_current().
• If a thread must be killed, make sure it closes all its opened files and manages correctly the child status structure and frees it if necessary.
• Calling convention and argument stack:
• Make sure you carefully respect the calling convention such as word alignement or zero values. Note you need to provide the argv[] array in the right order, but the actual strings its elements points to do not need to be ordered in a particular way.

Next Laboratory work

Laboratory Assignments 4