Project 1

CMSC 412

Due: Friday, September 14, 6:00pm see Piazza


In this project we will be augmenting the GeekOS process services to include (1) detached ("background") processes, (2) being able to kill a process asynchronously from another process, and (3) being able to view the currently running processes and their status.

Getting Started


We will first provide some background on process lifetimes in GeekOS, and some more details on how system calls are implemented. The project requirements are presented below. Following the requirements we present further background material on how process address spaces are implemented, many details of which are not important for this project but will be more important for project 4 (so it might be useful to understand at least some of them now).

Process Creation and Termination

As you already know, a user process in GeekOS is a Kernel_Thread with an attached User_Context. Each Kernel_Thread has a field alive that indicates whether it has terminated (i.e., Exit() has been called). A Kernel_Thread also has a refCount field that indicates the number of kernel threads interested in this thread. When a thread is alive, its refCount is always at least 1 because the thread has a reference to itself. If a thread for a process is started via Start_User_Thread with a detached argument of "false", then the refCount will be 2: one self reference plus one reference from the owner. When detached is false, the owner field in the new Kernel_Thread object is initialized to point to the Kernel_Thread spawning it (aka the parent). Typically the parent of a new user process is the shell process that spawned it.

The parent-child relationship is useful when the parent wants to retrieve the returned result of its child using the Wait() system call. (We say "Wait() system call" as short for the C wrapper function to the wait system call.) For example, in the shell (src/user/shell.c), if Spawn_Program is successful, the shell calls Wait() to wait for the newly-launched child process to terminate. Wait() returns the child process's exit code. The Wait system call is implemented by using thread queues, which we explain below.

When a process terminates by calling Exit, it decrements its refCount (removing its self-reference). Moreover, when its parent calls Wait on the process, it decrements the refCount (removing the parent's reference), bringing the process's refCount to 0. When this is the case, the Reaper process is able to destroy the process, discarding its Kernel_Thread object and its associated memory.

A process that has terminated but whose refCount is non-zero is called a zombie. This means that its parent has not yet decremented refCount (bug or otherwise).

More about process lifetimes: Zombies

A process can be in one of four states on its way from being alive to being dead:
  1. refCount=0, alive=false
    The process is dead: it has called Exit; its parent, if it had one, has released its reference; the process will soon be reaped.
  2. refCount=1, alive=false
    The process is a zombie: it has called Exit(); its parent has not released its reference, and until then the process will stay a zombie.
  3. refCount=1, alive=true
    The process is alive and detached (or "background").
  4. refCount=2, alive=true
    The process is alive and non-detached (or "foreground").

Thread Queues

As processes enter the system, they are put into a job queue (aka thread queue or process queue). In particular, the processes that are residing in the main memory and are ready and waiting to execute are kept on a list called the run queue. It stays there, not executing, until it is selected for execution. Once the process is allocated the CPU and is executing, one of several events can occur:

In the first two cases, the process eventually switches from the waiting state to the ready state (assuming the IO device or subprocess does not become stuck). It is removed from the queue in which it was waiting and put back in the run queue. The process continues this cycle until it terminates, at which time it is not present on any queue.

Project Requirements

There are three primary goals of this project:

Add detached processes

Currently, in order for a process to be reaped, a parent must Wait() on the child process's pid. However, we may want the child process to just complete on its own and die a graceful death, without having to make the parent Wait() on it. To do this, a process needs a way to spawn a child so that it can continue on with its work, oblivious of what the newly-spawned child is doing. To implement such detached processes, do the following:

Killing processes

It could be that once a process starts to run, it may behave badly, or the work it is performing may become irrelevant. Therefore, we would like to have some way for one process to kill another process. To do this, do the following:

Printing the process table

Now that we can run many processes from the shell at once, we might like to get a snapshot of the system, to see what's going on. Therefore, you will implement a program and a system call that prints the status of the threads and processes in the system:

Further Reading: Implementing Process Address Spaces

Address Space Protection

To prevent one process from accessing another process's memory, or from accessing memory belonging to the kernel, most operating systems, including GeekOS, implement processes as having their own address space. In particular, instructions issued within a process may not refer to physical memory addresses, but rather only to logical addresses, which are essentially one or two levels of indirection removed from the underlying memory address. The kernel is responsible for setting up a process's logical address space when it creates the process---that is, what logical addresses map to what physical addresses---and thus it can control what memory a process can access. If the process attempts to access memory outside of its logical address space, the hardware will generate an interrupt, and the OS can then kill the process. GeekOS currently uses segmented memory to implement user process address spaces. This is a facility provided by the Intel hardware, and we will explain it in more detail below.

User vs. Kernel Memory

The user process and the kernel both access main memory, but addresses in user space and addresses in kernel space to the same memory will be different, because each has its own distinct logical address space. This means that any user address passed to the kernel via a system call will need to be mapped to a kernel address before the kernel can properly access the memory. The kernel therefore uses the routines Copy_From_User and Copy_To_User to copy data to and from user memory, and these routines properly map user addresses to kernel ones.

While it is easy to use these routines (you can look at existing system calls for examples), it is harder to understand how they work, because it requires understanding how GeekOS uses the x86 memory segmentation system to implement kernel and user process address spaces. This is a good time for you to start figuring this out; you will have to understand it in intimate detail to successfully complete project 4.


Memory Segments. The facility that the processor provides for dividing up memory is its handling of memory segments. A memory segment specifies a region of memory and the "privilege level" that is required to access that memory. Each user program has its own memory segments - one for code, one for data, one for its stack, plus a couple extra for various purposes. If the operating system sets up the segments properly, a program will be limited to accessing only its own memory.

Privilege levels range from 0 to 3. Level 0 processes have the most privileges, level 3 processes have the least. Protection levels are also called rings in 386 documentation. Kernel processes in GeekOS run in ring 0, user processes run in ring 3. Besides limiting access to different memory segments, the privilege level also determines the set of processor operations available to a process. A program's privilege level is determined by the privilege level of its code segment.

If a process attempts to access memory outside of its legal segments, the result should be the all-too-familiar segmentation fault, and the process will be halted.

Another important function of memory segments is that they allow programs to use relative memory references. All memory references are interpreted by the processor to be relative to the base of the current memory segment. Instruction addresses are relative to the base of the code segment, data addresses are relative to the base of the data segment. This means that when the linker creates an executable, it doesn't need to specify where a program will sit in memory, only where the parts of the program will be, relative to the start of the executable image in memory.

Descriptor Tables. The information describing a segment---which is logically a base address, a limit address, and a privilege level---is stored in a data structure called a segment descriptor. The descriptors are stored in descriptor tables. The descriptor tables are located in regular memory, but the format for them is exactly specified by the processor design. The functions in the processor that manipulate memory segments assume that the appropriate data structures have been created and populated by the operating system. You will see a similar approach used when you work with multi-level page tables in project 4.

There are two types of descriptor tables. The Local Descriptor Table (LDT) stores the segment descriptors for each user process. There is one LDT per process. The Global Descriptor Table (GDT) contains information for all of the processes, and there is only one GDT in the system. There is one entry in the GDT for each user process which contains a descriptor for the memory containing the LDT for that process. This descriptor is essentially a pointer to the beginning of the user's LDT and its size.

Since all kernel processes are allowed to access all of memory, they can all share a single set of descriptors, which are stored in the GDT.

The relationship between GDT, LDT and User_Context entries is explained in the picture below:

Segment Descriptor Selectors. The GDTR and LDTR registers contain the addresses of the GDT and the current LDT, respectively. (The LDT actually holds a segment descriptor selector.) In addition, for fast access, there are six registers that keep track of a process's active segments:

These registers do not contain the actual segment descriptors. Instead, they contain Segment Descriptor Selectors, which are essentially the indices of descriptors within the GDT and the current LDT.

The memory segments for a process are activated by loading the address of the LDT into the LDTR and the segment selectors into the various segment registers. This happens when the OS switches between processes. If you like, you can follow the Schedule() call in src/geekos/kthread.c to see how this is done (this will require looking at some assembly code---beware!).

Further Reading: For more information on this topic, please refer to the Intel Developer's Manual, Sections 3.1 to 3.5. The book covers segmentation in Chapter 9.