Göm menyn
IT-Programmet, Tema 1 i termin 4:

TTIT61 Processprogrammering och Operativ System

/Concurrent Programming and Operating Systems/


Lab 3: Execution, Termination and Synchronization of User Programs

Goal

In this assignment you are supposed to learn about multiprogramming environment, synchronization between user programs, and setting up the program stack. The main goal is to understand how important synchronization is in the multiprogramming environment and implement a set of system calls in Pintos that allow to provide synchronization between the user programs.

Overview

This assignment covers:

  • Execution of several user programs in Pintos.
  • Synchronization of the user programs.
  • Argument passing to the user programs.

User Programs

In the last assignment (Lab 2), you had only one user program running by the operating system, which is a very rare and exceptional situation. In the Part A of the assignment, you are supposed to implement a fully operational multiprogramming environment, where a set of user programs can be executed at the same time. Programs will allow to invoke "child" user programs and, if needed, may wait for completion of "child" programs. In the multiprogramming environment, synchronization becomes ultimately 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 OS can pass arguments to user programs, in particular, how it is solved in 80x86 architecture by pushing them into the program's stack.

Note that in this assignment you are not supposed to implement synchronized access to the file system, which is a part of Lab 4 "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 Lab 2 and extend it.

Preparation

In addition to the source code, which you have already gone through in the second lab, you should read and understand the code in userprog/process.c, which 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 on the following set of questions to ensure that you are ready to continue:

  1. When the program starts, what major steps are performed, what is initialized and where? E.g. registers, program counter, stack, … . Look into the current Pintos implementation and identify these steps in the code.
  2. What is the paging? Explain the basic idea behind it.
  3. What are all the possible scenarios with wait() regarding completion of “parent” and “child” processes?
  4. How can you avoid using “busy waiting” in wait()?
  5. What is the default value, which is returned by exit? Do you know any typical error exit codes that are returned by the user programs in Linux/Windows?
  6. Name which data structures in your implementation will be shared? (At least the ones that you have already implemented.) Which synchronization mechanisms from Lab 1 can be applied?
  7. Provide any scenario of a concurrent execution of two or more processes with your implementation such that it ends with problems. (Tip: consider a shared object and find out what bad can happen if you do not synchronize access to it)
  8. What are argc and argv that main in a C program takes as arguments? Where are they stored when the program begins executing

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. Conventionally, a status of 0 indicates success and nonzero values indicate errors. Remember to free all the resources that will be not needed anymore.

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

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.
  • Only one thread can have access to the console at a time. Other threads must wait until completion of reading/writing.

Note that in this assignment you are not supposed to implement synchronized access to the file system, which is a part of Lab 4 "File System".  Therefore, concurrent access to files will not work properly until Lab 4.

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 setup_stack() function and change back the following line:
*esp = PHYS_BASE - 12;
into
*esp = PHYS_BASE;
Now your program will always fail unless 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 '...' from the Pintos command line. For example, pintos --qemu -- run 'nasty_student_program i love pintos', where user program nasty_student_program is called with arguments i, love, and pintos.

When the user program with arguments is called from exec(), you have to call it like this: exec("nasty_student_program i love pintos").

Although you can parse the string from the command line any way you like, we can recommend to take 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 with, for example, 32, which will simplify your implementation because you can use a static array of a fixed size to store the parsed arguments.

For the sake of simplicity and reducing the amount of "unsolvable bugs", we also suggest that you first parse the command line into arguments, store them into a static array, and only then push the arguments into the stack copying them from the array.

Necessary details about setting up the stack for this task you can find in Program Startup Details section of Pintos documentation. The stack should be set in the start_process() function located in userprog/process.c, after all the "original" preparations have been done.

Stop! Find out why, when and from where the start_process() function is called.

We provide you with the "help" function that prints the content of the program stack:



// ORIGINAL DECLARATIONS
  int i;
  void *ptr_save;
// YOUR DECLARATIONS HERE

// ORIGINAL PREPARATIONS TO START THE USER PROGRAM

// YOUR COMMAND LINE PARSING CODE HERE

  ptr_save = if_.esp;

// YOUR STACK INITIALIZATION CODE HERE

  i = -15; //we start printing with 16 bytes above the user space

  while(ptr_save - i >= if_.esp) {
    char *whats_there = (char *)(ptr_save - i);

    // show the address ...
    printf("%x\t", (uint32_t)whats_there);

    // ... printable byte content ...
    if(*whats_there >= 32 && *whats_there < 127)
      printf("%c\t", *whats_there);
    else
      printf(" \t");

    // ... 16-bit content ...
    printf("%d\t", (uint16_t)*whats_there);

    // ... and 32-bit aligned content
    if(i % 4 == 0) {
      uint32_t *wt_uint32 = (uint32_t *)(ptr_save - i);

      printf("%d\t%x\t", *wt_uint32, *wt_uint32);

      printf("\n-------");
      if(i != 0)
        printf("------------------------------------------------");
      else
        printf(" the border between KERNEL SPACE and USER SPACE ");
      printf("-------");
    }
    printf("\n");
    i++;
  }

Copy-paste this function into start_process() to see how the stack is set up. All the changes that you make to the stack will be printed (until the stack pointer esp). If nothing is printed, it means that you have set up the stack pointer incorrectly.

Test programs

Add printf("%s: exit(%d)\n", thread-name, thread-exit-value) to the code before a user process exits or is killed (e.g. because of a memory violation). Otherwise, the tests will not work.

The following tests should pass when you run gmake check if your implementation is correct:

1) Argument passing when executing:
tests/userprog/args-none
tests/userprog/args-single
tests/userprog/args-multiple
tests/userprog/args-many
tests/userprog/args-dbl-space

2) Different exec-tests:
tests/userprog/exec-once
tests/userprog/exec-arg
tests/userprog/exec-multiple
tests/userprog/exec-missing
tests/userprog/exec-bad-ptr

3) Wait-tests:
tests/userprog/wait-simple
tests/userprog/wait-twice
tests/userprog/wait-killed
tests/userprog/wait-bad-pid

gmake check does more checks that the ones listed below. Many of the other checks belong to the second lab. If any of them fails, then it means that something is wrong with your implementation of Lab 2:

tests/userprog/sc-bad-sp
tests/userprog/sc-bad-arg
tests/userprog/sc-boundary
tests/userprog/sc-boundary-2
tests/userprog/halt
tests/userprog/exit
tests/userprog/create-normal
tests/userprog/create-empty
tests/userprog/create-null
tests/userprog/create-bad-ptr
tests/userprog/create-long
tests/userprog/create-exists
tests/userprog/create-bound
tests/userprog/open-normal
tests/userprog/open-missing
tests/userprog/open-boundary
tests/userprog/open-empty
tests/userprog/open-null
tests/userprog/open-bad-ptr
tests/userprog/open-twice
tests/userprog/close-normal
tests/userprog/close-stdin
tests/userprog/close-stdout
tests/userprog/close-bad-fd
tests/userprog/read-bad-ptr
tests/userprog/read-boundary
tests/userprog/read-zero
tests/userprog/read-stdout
tests/userprog/read-bad-fd
tests/userprog/write-normal
tests/userprog/write-bad-ptr
tests/userprog/write-boundary
tests/userprog/write-zero
tests/userprog/write-stdin
tests/userprog/write-bad-fd

Helpful Information

Code directory: src/userprog, src/threads, src/lib, src/lib/kernel
Textbook chapters: Chapter 2.3: System Calls
Chapter 2.4: Types of System Calls
Chapter 4.4: Threading Issues
Chapter 6.2: The Critical-Section Problem
Chapter 8.4: Paging
Documentation: Pintos documentation related to Project 2
(Always remember that the TDDB68 lab instructions always have higher precedence)

ddd man page (call man ddd)

Next Laboratory work

Laboratory Assignments 4

TTIT61
Temamål
Temaplan
Schema
Examination
Referenslitteratur
Personal
Register for labs

Föreläsningarna
Programexempel
Forum
Labresultat

Schemaläggning
Kritiska sektioner
Processorstöd för operativsystem
Sekundärminne
UNIX, WinNT
Säkerhet

Intro: C/make
Intro: installation
Threads and synchronisation
System calls
Execution of user programs
File system

Lesson 1
Lesson 2
Lesson 3

C/C++ OH
C/C++ tutorial
C pointers tutorial
Pintos documentation
Memory Issues in Pintos
Pintos on-line documentation
The gnu DDD documentation
DDD tutorial
Debugging topics
Programing with threads

Guidelines for writine and changing source code
Pintos source code

Sidansvarig: Sergiu Rafiliu
Senast uppdaterad: 2011-09-12