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:
- 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.
- What is the paging? Explain the basic idea behind it.
- What are all the possible scenarios with wait() regarding
completion of “parent” and “child” processes?
- How can you avoid using “busy waiting” in wait()?
- 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?
- 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?
- 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)
- 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:
- "Parent" exits without calling wait() while the "child"
is still running
- "Child" exits before the "parent" and:
- "parent" calls wait() afterwards, or
- "parent" will exit without calling wait().
- "Parent" calls wait() before the "child" exits.
- 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
English web site
