6.828 Fall 2004 Lab 4: Preemptive Multitasking

Handed out Wednesday, October 13
Part A due Thursday, October 21
Part B due Thursday, October 28
Part C due Thursday, November 4

Introduction

Getting Started

Lab Requirements

As before, you will need to do all of the regular exercises described in the lab and at least one challenge problem. (You do not need to do one challenge problem per part, just one for the whole lab.) Additionally, you will need to write up brief answers to the questions posed in the lab and a short (e.g., one or two paragraph) description of what you did to solve your chosen challenge problem. If you implement more than one challenge problem, you only need to describe one of them in the write-up, though of course you are welcome to do more. Place the write-up in a file called answers.txt (plain text) or answers.html (HTML format) in the top level of your lab2 directory before handing in your work.

Part A: User-level Environment Creation and Cooperative Multitasking

Round-Robin Scheduling

Your first task in this lab is to change the JOS kernel so that it does not always just run the environment in envs[0], but instead can alternate between multiple environments in "round-robin" fashion. Round-robin scheduling in JOS works as follows:

• The first environment, in envs[0], will from now on always be a special idle environment, which always runs the program user/idle.c. The purpose of this program is simply to "waste time" whenever the processor has nothing better to do - it just perpetually attempts to give up the CPU to another environment. Read the code and comments in user/idle.c for other useful details. We have modified kern/init.c for you to create this special idle environment in envs[0] before creating the first "real" environment in envs[1].
• The function sched_yield() in the new kern/sched.c is responsible for selecting a new environment to run. It searches sequentially through the envs[] array in circular fashion, starting just after the previously running environment (or at the beginning of the array if there was no previously running environment), picks the first environment it finds with a status of ENV_RUNNABLE (see inc/env.h), and calls env_run() to jump into that environment. However, sched_yield() is aware that envs[0] is the special idle environment, and never picks it unless there are no other runnable environments.
• We have implemented a new system call for you, sys_yield(), which user environments can call to invoke the kernel's sched_yield() function and thereby voluntarily give up the CPU to a different environment. As you can see in user/idle.c, the idle process does this routinely.
• Whenever the kernel switches from one environment to another via env_run(), it must save the old environment's register state so that it can be restored properly later when the first environment is eventually re-entered. (Why? Where is the user environment's register state stored on entry to a system call or trap handler in the kernel, and where does this state need to be stored in order to keep it safe for next time the environment runs?) We have added a few lines of code and a panic() in env_run() to point out where this needs to happen.

1. In your implementation of env_run() you should have called lcr3(). But before and after the call to lcr3(), your code makes references (at least it should) to the variable e--the argument to env_run. How can this work?

   Upon loading the %cr3 register, the addressing context used by the MMU is instantly changed. The problem is that a virtual address (namely e) has meaning relative to a given address context--the address context specifies the physical address to which the virtual address map. Why can the pointer e be dereferenced both before and after the addressing switch?

System Calls for Environment Creation

Although your kernel is now capable of running and switching between multiple user-level environments, it is still limited to running environments that the kernel initially set up. You will now implement the necessary JOS system calls to allow user environments to create and start other new user environments.

Unix provides the fork() system call as its process creation primitive. Unix fork() copies the entire address space of calling process (the parent) to create a new process (the child). The only differences between the two observable from user space are their process IDs and parent process IDs (as returned by getpid and getppid). In the parent, fork() returns the child's process ID, while in the child, fork() returns 0. The two processes do not share any memory: writes to one process's memory do not appear in the other and vice versa.

In JOS we will provide a different, much more primitive set of system system calls for creating new user-mode environments. With these system calls we will be able to implement Unix-like fork() functionality entirely in user space, in addition to other types of environment creation functionality. The new system calls we will use in JOS are as follows:

sys_env_alloc:

This system call creates a new environment with an almost blank slate: nothing mapped in the user portion of its address space, and not runnable. The new environment will have the same register state as the parent environment at the time of the sys_env_alloc call. The only difference is that in the parent, sys_env_alloc will return the id of the newly created environment, but in the child it will return 0. (Since the child starts out marked as not runnable, sys_env_alloc will not actually return in the child until the parent has explicitly allowed this by marking the child runnable.)

sys_set_trapframe:

Sets the user register state to new values specified by the caller in a struct Trapframe. We will not actually use this system call until lab 5, but we introduce it here because of its logical relationship to the task of setting up new user environments.

sys_set_status:

Sets the status of a specified environment to ENV_RUNNABLE or ENV_NOT_RUNNABLE. This system call is typically used to mark a new environment ready to run, once its address space and register state has been fully initialized.

sys_mem_alloc:

Allocates a page of physical memory and maps it at a given virtual address in a given environment's address space.

sys_mem_map:

Copy a page mapping (not the contents of a page!) from one environment's address space to another, leaving a memory sharing arrangement in place so that the new and the old mappings can both be used to access the same page of physical memory.

sys_mem_unmap:

Unmap a page mapped at a given virtual address in a given environment.

For all of the system calls above that accept environment IDs, the JOS kernel supports the special convention that a value of 0 effectively means "the current environment." This convention is implemented by envid2env() in kern/env.cc.

We have provided a very primitive implementation of Unix-like fork() functionality in the test program user/dumbfork.c. This test program uses the above system calls to create and run a child environment with a copy of its own address space. The two environments then switch back and forth using sys_yield as in the previous exercise. The parent exits after 10 iterations, whereas the child exits after 20.

Permission Checking

An environment can only use the above system calls to manipulate environments as long as all of the environments affected are either:

1. The environment making the system call.
2. Immediate children of the environment making the system call.

This completes Part A of the lab; hand it in using make handin as usual.

Part B: Copy-on-Write Fork

V6 Unix implemented fork() by copying the parent's entire data segment into a new memory region allocated for the child. This is essentially the same approach that our dumbfork() function above takes. The copying of the parent's address into the child is generally, by far, the most expensive part of the fork() operation.

However, a call to fork() is frequently followed almost immediately by a call to exec() in the child process, which clears out the child process's address space and loads a new program in its place. (This is what the the shell typically does, for example.) In this case, most of the laborious work done in copying the parent's entire address space into the child is useless, because the child process will probably actually touch very little of its memory before calling exec() to execute a new program.

For this reason, Later versions of Unix took advantage of more advanced virtual memory hardware to allow the parent and child to share the memory mapped into their respective address spaces until one of the processes actually modifies it. This technique is known as copy-on-write. To do this, on fork() the kernel would merely copy the address space mappings from the parent to the child instead of the actual contents of the mapped pages, and at the same time mark the now-shared pages read-only. When one of the two processes tries to write to one of these shared pages, the process takes a page fault. At this point, the Unix kernel realizes that the page was really a "virtual" or "copy-on-write" copy, and so it makes a new, private copy of the page for the faulting process. In this way, the contents of individual pages aren't actually copied until they are actually written to. This optimization makes a fork() followed by an exec() in the child much cheaper: the child will probably only need to copy one page (the current page of its stack) before it calls exec().

In the next piece of this lab, you will implement "proper" Unix-like fork() functionality with copy-on-write, as a user space library routine. Implementing fork() and copy-on-write support in user space has the benefit that the kernel remains much simpler and thus more likely to be correct. It also lets individual user-mode programs define their own semantics for fork(). A program that wants a slightly different implementation (for example, the expensive always-copy version like dumbfork(), or one in which the parent and child actually share memory afterward) can easily provide its own.

User-level page fault handling

Most page faults encountered during normal program execution are usually fixable. For example, most Unix kernels initially map only a single page in a new process's stack region, and allocate and map additional stack pages later "on demand" as the process's stack consumption increases and causes page faults on stack pages that are not yet mapped. A typical Unix kernel must track, for each user-mode process, the various regions of memory that are mapped and what to do when faults happen in them. For example, a fault in the stack region will typically allocate and map in a new page. A fault in the program's BSS region will typically map in a new page and also make sure it is zeroed. In systems with demand-paged executables, a fault in the text region will read the corresponding page of the binary off of disk and then map it in.

This is a lot of information for the kernel to track and get right. Instead of taking the traditional Unix approach, in JOS we push this fault handling functionality into user space, where bugs are less damaging. This design has the added benefit of allowing programs great flexibility in defining their memory regions. Not only do we get the ability to implement copy-on-write fork(), but we will use user-level page fault handling later for mapping and accessing files on a disk-based file system.

Setting the Page Fault Handler

Normal and Exception Stacks in User Environments

The JOS user exception stack is also one page in size, and its top is defined to be at virtual address UXSTACKTOP, so the valid bytes of the user exception stack are from UXSTACKTOP-BY2PG through UXSTACKTOP-1 inclusive. While running on this exception stack, the user-level page fault handler can use JOS's regular system calls to map new pages or adjust mappings so as to fix whatever problem originally caused the page fault. Then the user-level page fault handler returns, via an assembly language stub, to the faulting code on the original stack.

Each user environment that wants to support user-level page fault handling will need to allocate memory for its own exception stack, using the sys_mem_alloc() system call introduced in part A.

Invoking the User Page Fault Handler

You will now need to change the page fault handling code in kern/trap.c to handle page faults from user mode as follows. We will call the state of the user environment at the time of the fault the trap-time state.

If there is no page fault handler registered, the JOS kernel destroys the user environment with a message as before. Otherwise, the kernel sets up a trap frame on the exception stack that looks like this:

                 	-0  <-- UXSTACKTOP
empty			-4
empty			-8
empty			-12
empty			-16
empty			-20
trap-time eip		-24
trap-time eflags   	-28
trap-time esp		-32
tf_err (error code)	-36
fault_va        	-40 <-- %esp when handler is run

The kernel then arranges for the user environment to resume execution with the page fault handler running on the exception stack with this stack frame. (You must figure out how to make this happen.) Each empty line in the frame above is simply a 32-bit word-size space on the exception stack that the kernel does not initialize, but which the fault handler in the user environment can use. The fault_va is the virtual address at which the page fault occurred.

If the user environment is already running on the user exception stack when an exception occurs, then the page fault handler itself has faulted. In this case, you should start the new stack frame just under the current tf->tf_esp rather than at UXSTACKTOP:

(...existing contents
of exception stack...)
                 	-0  <-- tf->tf_esp
empty			-4
empty			-8
empty			-12
empty			-16
empty			-20
trap-time eip		-24
trap-time eflags   	-28
trap-time esp		-32
tf_err (error code)	-36
fault_va        	-40 <-- %esp when handler is run

To test whether tf->tf_esp is already on the user exception stack, check whether it is in the range between UXSTACKTOP-BY2PG and UXSTACKTOP-1, inclusive.

User-mode Page Fault Entrypoint

Next, you need to implement the assembly routine that will take care of calling the C page fault handler and resume execution at the original faulting instruction. This assembly routine is the handler that will be registered with the kernel using sys_set_pgfault_entry().

Finally, you need to implement the C user library side of the user-level page fault handling mechanism.

Testing

[00000000] new env 00000800
[00000000] new env 00001001
[00001001] user fault va 00000000 ip 0080003a
TRAP frame ...
[00001001] free env 00001001

Change kern/init.c to run user/faultdie. Build your kernel and run it. You should see:

[00000000] new env 00000800
[00000000] new env 00001001
i faulted at va deadbeef, err 6
[00001001] exiting gracefully
[00001001] free env 00001001

Change kern/init.c to run user/faultalloc. Build your kernel and run it. You should see:

[00000000] new env 00000800
[00000000] new env 00001001
fault deadbeef
this string was faulted in at deadbeef
fault cafebffe
fault cafec000
this string was faulted in at cafebffe
[00001001] exiting gracefully
[00001001] free env 00001001

If you see only the first "this string" line, it means you are not handling recursive page faults properly.

Change kern/init.c to run user/faultallocbad. Build your kernel and run it. You should see:

[00000000] new env 00000800
[00000000] new env 00001001
[00001001] PFM_KILL va deadbeef ip f010263d
TRAP frame ...
[00001001] free env 00001001

Make sure you understand why user/faultalloc and user/faultallocbad behave differently.

Implementing Copy-on-Write Fork

We have provided a skeleton for your fork() function in lib/fork.c. Like dumbfork(), fork() creates a new environment, then scans through the parent environment's entire address space and sets up corresponding page mappings in the child. The key difference is that, while dumbfork() copied entire pages, fork() will initially only copy page mappings. Notice that the duppage() helper function in dumbfork calls sys_mem_alloc() to allocate a new page of physical memory for each page in the parent, and then calls memcpy() to copy the contents of the parent's page into the child's new page. These calls to memcpy() represent the bulk of the time dumbfork() takes to run, and so fork() attempts to "optimize away" most of this page copying by copying pages lazily only when they are actually modified.

The basic control flow for fork() is as follows:

1. The parent installs pgfault() as the C-level page fault handler, using the set_pgfault_handler() function you implemented above.
2. The parent calls sys_env_alloc() to allocate a child environment.
3. For each writable or copy-on-write page in its address space below UTOP, the parent maps the page copy-on-write into the address space of the child and then remaps the page copy-on-write in its own address space.

   The exception stack is not remapped this way, however. Instead you need to allocate a fresh page in the child for the exception stack. Since the page fault handler will be doing the actual copying and the page fault handler runs on the exception stack, the exception stack cannot be made copy-on-write: who would copy it?

4. The parent sets the user page fault entrypoint for the child to look like its own.
5. The child is now ready to run, so the parent marks it runnable.

After the fork, both processes will take page faults when the code they run attempts to write to a page that hasn't been copied yet. Here's the control flow for the user page fault handler:

1. Kernel propagates page fault to _pgfault_entry, which calls fork()'s pgfault() handler.
2. pgfault() checks that the fault is a write (check FEC_WR) and that the PTE for the page is marked PTE_COW (copy-on-write). If not, panic.
3. pgfault() allocates a new page mapped at a temporary location and copies the contents of the faulting page contents into it. Then the fault handler maps the new page at the appropriate address with read/write permissions, in place of the old read-only mapping.

	1001: I am ''
	1802: I am '0'
	2801: I am '00'
	3802: I am '000'
	2003: I am '1'
	5001: I am '11'
	4802: I am '10'
	6801: I am '100'
	5803: I am '110'
	3004: I am '01'
	8001: I am '011'
	7803: I am '010'
	4005: I am '001'
	6006: I am '111'
	7007: I am '101'
	

This ends part B. As usual, you can grade your submission with gmake grade and hand it in with gmake handin.

Part C: Preemptive Multitasking and Inter-Process communication (IPC)

Clock Interrupts and Preemption

Modify kern/init.c to run the user/spin test program. This test program forks off a child process, which simply spins forever in a tight loop once it receives control of the CPU. Neither the parent process nor the kernel ever regains the CPU. This is obviously not an ideal situation in terms of protecting the system from bugs or malicious code in user-mode environments, because any user-mode environment can bring the whole system to a halt simply by getting into an infinite loop and never giving back the CPU. In order to allow the kernel to preempt a running environment, forcefully retake control of the CPU from it, we must extend the JOS kernel to support external hardware interrupts.

Interrupt discipline

External interrupts (i.e., device interrupts) are refered as IRQs. There are 16 possible IRQs, numbered 0 through 15. The mapping from IRQ number to IDT entry is not fixed. Pic_init in picirq.c maps IRQs 0-15 to interrupts IRQ_OFFSET through IRQ_OFFSET+15.

In kern/picirq.h, IRQ_OFFSET is defined to be decimal 32. Thus the IDT entries 32-44 correspond to the IRQs 0-15. For example, the clock interrupt is IRQ 0. Thus, IDT[32] contains the address of the clock's interrupt handler routine in the kernel. This IRQ_OFFSET is chosen so that the device interrupts do not overlap with the processor exceptions, which could obviously cause confusion. (In fact, in the early days of PCs running MS-DOS, the IRQ_OFFSET effectively was zero, which indeed caused massive confusion between handling hardware interrupts and handling processor exceptions!)

In JOS, we make a key simplification compared to V6 Unix. External device interrupts are always disabled when in the kernel and always enabled when in user space. External interrupts are controlled by the FL_IF flag bit of the %eflags register (see inc/mmu.h). When this bit is set, external interrupts are enabled. While the bit can be modified in several ways, because of our simplification, we will handle it solely through the process of saving and restoring %eflags register as we enter and leave user mode.

You will have to ensure that the FL_IF flag is set in user processes when they run so that when an interrupt arrives, it gets passed through to the processor and handled by your interrupt code. Otherwise, interrupts are masked, or ignored until interrupts are re-enabled. Interrupts are masked by default after processor reset, and so far we have simply never gotten around to enabling them.

Handling Clock Interrupts

In the user/spin program, after the child environment was first run, it just spun in a loop, and the kernel never got control back. We need to program the hardware to generate clock interrupts periodically, which will force control back to the kernel where we can switch control to a different user environment.

The calls to pic_init and kclock_init (from i386_init in init.c), which we have written for you, set up the clock and the interrupt controller to generate interrupts. You now need to write the code to handle these interrupts.

Make sure you can answer the following questions:

1. How many instruction of user code are executed between each interrupt?
2. How many instructions of kernel code are executed to handle the interrupt?
   Hint: use the vb command mentioned earlier.

Inter-Process communication (IPC)

We've been focusing on the isolation aspects of the operating system, the ways it provides the illusion that each program has a machine all to itself. Another important service of an operating system is to allow programs to communicate with each other when they want to. It can be quite powerful to let programs interact with other programs. The Unix pipe model is the canonical example.

There are many models for interprocess communication. Even today there are still debates about which models are better for various reasons. We won't get into that debate. Instead, we'll implement a simple IPC mechanism and then try it out.

IPC in JOS

The "messages" that user environments can send to each other using JOS's IPC mechanism consist of two components: a single 32-bit value, and optionally a single page mapping. Allowing environments to pass page mappings in messages provides an efficient way to transfer more data than will fit into a single 32-bit integer, and also allows environments to set up shared memory arrangements easily.

Sending and Receiving Messages

To receive a message, an environment calls sys_ipc_recv. This system call deschedules the current environment and does not run it again until a message has been received. When an environment is waiting to receive a message, any other environment can send it a message - not just a particular environment, and not just environments that have a parent/child arrangement with the receiving environment. In other words, the permission checking that you implemented in Part A will not apply to IPC, because the IPC system calls are carefully designed so as to be "safe": an environment cannot cause another environment to malfunction simply by sending it messages (unless the target environment is also buggy).

To try to send a value, an environment calls sys_ipc_can_send with both the receiver's environment id and the value to be sent. If the named environment is actually receiving (it has called sys_ipc_recv and not gotten a value yet), then the send delivers the message and returns 0. Otherwise the send returns -E_IPC_NOT_RECV to indicate that the target environment is not currently expecting to receive a value.

A library function ipc_recv in user space will take care of calling sys_ipc_recv and then looking up the information about the received values in the current environment's struct Env.

Similarly, a library function ipc_send will take care of repeatedly calling sys_ipc_can_send until the send succeeds.

Transferring Pages

When an environment calls sys_ipc_recv with a nonzero dstva parameter, the environment is stating that it is willing to receive a page mapping. If the sender sends a page, then that page should be mapped at dstva in the receiver's address space. If the receiver already had a page mapped at dstva, then that previous page is unmapped.

When an environment calls sys_ipc_can_send with a nonzero srcva, it means the sender wants to send the page currently mapped at srcva to the receiver, with permissions perm. After a successful IPC, the sender keeps its original mapping for the page at srcva in its address space, but the receiver also obtains a mapping for this same physical page at the dstva originally specified by the receiver, in the receiver's address space. As a result this page becomes shared between the sender and receiver.

If either the sender or the receiver does not indicate that a page should be transferred, then no page is transferred. After any IPC the kernel sets the new field env_ipc_perm in the receiver's Env structure to the permissions of the page received, or zero if no page was received.

Implementing IPC

This ends part C. As usual, you can grade your submission with gmake grade and hand it in with gmake handin. If you are trying to figure out why a particular test case is failing, run sh grade.sh -v, which will show you the output of the kernel builds and Bochs runs for each test, until a test fails. When a test fails, the script will stop, and then you can inspect bochs.out to see what the kernel actually printed.