Project 3: Writing a Kernel From Scratch

Table of Contents

• Project Overview
• Goals
• Technical Disclaimer
• Important Dates
• Groups
• Grading
• Handin
• Hardware Primitives
• Segment Selector Registers
• The EFLAGS Register
• Control Registers
• The Kernel Stack Pointer
• Paging
• The Interrupt Descriptor Table
• The Layout of Physical Memory
• Kernel Programming Environment
• Context Switching
• A Loader for a.out
• Getting the Executable's Bytes
• Details on the a.out Format
• Linking User Processes
• Kernel System Calls
• System Call Interface
• Hints on Implementing a Kernel
• Plan of Attack

The kernel project is a four week project, unlike the two projects you have completed. It will be very important to adhere to a reasonable schedule throughout the four weeks to ensure completion of the project. While project four (the file system) is probably more code than the kernel, the kernel is arguably the most complicated project conceptually.

Goals

• Implementing context switching and preemptive multitasking.
• Implementing the system calls used by the second project.
• Understanding and implementing virtual memory.
• Debugging kernel code. Kernels are a little harder to debug than simple user processes. Virtual memory often complicates debugging, as do interrupts.

The goal of this project set is certainly not to teach the idiosyncrasies of the x86 architecture (or Intel's documentation). That said, it will be necessary to become accustomed to the x86 way of doing things, and the Intel nomenclature, for the purposes of completing this project set. Just keep in mind that the x86 way of doing things is not the only way of doing things. It is the price to be paid for learning the principles of operating systems on a real world system instead of a simulated architecture.

Important Dates

Although it is not the first thing we will look at, style is also important. Use an appropriate level of commenting, name variables consistently, and try not to resort to global variables when possible.

It is also our intent that part of the project 3 grade will be based on a face to face interview process. We reserve the right to give partners in a group different project grades if circumstances make that necessary.

Please hand in a design document with your kernel. It should talk about all the important design decisions you made, what works, and what does not. If you tell us about something that doesn't work, it puts you in a better position to be given more partial credit than if you do not tell us and we stumble across it ourselves, because it lets us know that you understand that there is a problem and have spent some nonzero amount of time trying to find it.

Handin

Each segment has a privilege level associated with it, which is the minimum privilege to access that segment. In project 1, all of our segments were privilege level 0, and we never left kernel mode. In this project however, we will have user processes which cannot access segments that require privilege level 0. Fortunately we have already defined segments for user code and data (user data can be used for both the user's stack segment and data segment). They are specified in seg.h.

When you start a user process, you will need to specify a user-level code and stack segment. You will also need to load a user-level data segment into the data segment registers. When a user process takes an interrupt, the code and stack segment registers will get saved automatically (see intel-sys.pdf page 153). The data segment registers will not be saved, though. You will need to save these along with the other general purpose registers, and then restore them before the user process is run again.

The EFLAGS Register

Although the EFLAGS register stores a flag controlling whether interrupts are enabled or disabled, there is a much faster way to disable and enable interrupts. The sti and cli instructions enable and disable interrupts. You can find more information on them in intel-isr.pdf.

Control Registers

Control register 1 (CR1) is reserved and should not be touched.

Control register 2 (CR2) is only used in one instance. When your kernel takes a page fault, CR2 will contain the address that caused the page fault. You will need to get the value of this register inside your page fault handler.

Control register 3 (CR3) is sometimes referred to as the page directory base register, or PDBR. It holds the address of the current page directory in the top 20 bits (these are the top twenty bits of the page directory's address, the bottom 12 must be zero since the page directory must be page-aligned). It also has two flags, present in bits 3 and 4. Bit 3 controls whether the processor's internal caches are write-back or write-through (if the bit is set, write-through caching is enabled, if it is clear, write-back caching is enabled). Bit 4 controls whether the page directory may be cached (if the bit is set, the page directory may not be cached). Both of these flags should be cleared (not set). You will need to update CR3 whenever you wish to switch address spaces. Fortunately the x86 architecture flushes the TLB for you when you update CR3.

Control register 4 (CR4) contains a variety of extension flags, which for the most part we will not be using. The one flag we do care about is the Page Global Enable (PGE) flag, stored in bit 7. We will want to set this flag to enable global pages. The reason for this is made clear below. Do not modify the state of any of the other flags in this register.

We have provided assembly macros to read and write from the control registers. Be very careful about reading and writing to control registers (think about interrupts).

The Kernel Stack Pointer

The initial value of the stack pointer when we enter kernel mode is defined by the currently running task. Tasks are a hardware process mechanism provided by the x86 architecture. We will not be using tasks, however. Not only is it faster to manipulate the process abstraction in software, we can also tailor that abstraction to our particular design needs. However it is necessary on the x86 to define at least one task. The OSKit libraries take care of setting that up for you. We have provided a function to go into the processor data structure for this single task and set the initial kernel stack pointer value. It is called set_esp0(void* addr), defined in seg.h.

For more information on hardware tasks, refer to chapter 6 of intel-sys.pdf.

Paging

Both entry formats use the top 20 bits to specify an address (a page directory entry specifies the address of a page table, a page table entry specifies the address of a frame in memory). Note that both page tables and frames must be page aligned (they are both exactly 4k in size and the bottom 12 bits of their addresses must be zero), which is why we can simply specify the top 20 bits of the address.

The designers of the x86 architecture have kindly left us three bits which we can use as we please. These are the bits in the field marked "Avail" in both types of entries.

Bit 8 is the global flag, which has no meaning in the page directory entry (it can be set to either 0 or 1). In a page table entry however, if the global flag is set the virtual-to-physical mapping for this page will not be flushed from the TLB automatically. This can be useful for pages that are the same for all address spaces. You should use this to prevent the kernel mappings from being flushed on context switches. To use this bit, you also need to set the page global enable flag (PGE) in control register 4.

Bit 7 is the page size flag in the page directory entry, and in the page table entry it is the page attribute table index flag. Since we are only using 4k pages and they are all the same type of page, both of these flags should be set to zero.

Bit 6 is the dirty bit, and is only valid in page table entries. This flag gets set by the hardware when the page pointed to by the page table entry is written to. This can be used in implementing demand paging. It will not be used, however, in this project.

Bit 5 is the accessed bit. It gets set by the hardware when the page pointed to by a page table entry is accessed. The accessed bit gets set in a page directory entry as soon as any of its page tables point to pages have been accessed. You will not need to worry about using this flag.

Bit 4 is the page-level disable caching bit. If the flag is set then caching of the associated page (or page table if the entry is a page directory entry) is disabled. This flag should always be cleared to enable caching.

Bit 3 is the page-level write through bit. If it is set, write-through caching is enabled for that page (or page table if the entry is a page directory entry), otherwise write-back caching is used. This flag should be left clear.

Bits 1 and 2 of the page directory and page table entries interact with each other to provide page-level protection. We will be using page-level protection in the kernel to make sure that user processes cannot clobber the kernel. See the table on page 136 of intel-sys.pdf for the specific behavior of these two flags:
Bit 2 is the user/supervisor flag. If the flag is set, then the page is user accessible. This flag has different meaning depending on whether it is set in the page directory entry or the page table entry. It also interacts with the user/supervisor flag. See the table on page 136 of intel-sys.pdf for specific behavior.

Bit 1 is the read/write flag. If the flag is set, the page may be written to. If it is clear, the page is read-only. This flag has different meaning depending on whether it is set in the page directory entry or the page table entry. It also interacts with the user/supervisor flag. See the table on page 136 of intel-sys.pdf for specific behavior.

Bit 0 is the present flag in both the page directory and page table entries. If the page is marked not present, then an attempt to read, write, or execute data stored at an address within that page will generate a page fault. When you install a page into a page frame, you should set this bit. Likewise, if a page table is marked not present, then an attempt to read, write, or execute data stored anywhere at an address spanned by that page table will generate a page fault. When you install a new page table, make sure to set the present bit in its corresponding page directory entry.

Recall from the section on control registers that the address of the active page directory is kept in CR3, and the top bit of CR0 controls whether paging is active or not. You will need to install a page fault handler (this is similar to your installation of timer and keyboard interrupt handlers). That page fault handler will need to look at CR2 for the address of the fault, and decide whether it is a valid request (in which case you will need to allocate a new page and possibly a new page table), or an invalid request (an attempt to access kernel memory or the void between the heap and the stack). In order to get page faults when a user process attempts to access kernel memory, set the proper permission bits in the corresponding page directory and page table entries.

Of course, some accesses between the heap and the stack are valid; in fact, any time the user process grows its stack, it will access memory between the heap and the current stack pointer. You will need to decide how far is "too far" when judging whether a pointer access is an attempt to grow the stack, or a wild read/write into the middle of nowhere.

The Interrupt Descriptor Table

Installing a handler should be familiar from project one; if you're a little rusty, consult your project one solution or the project one handout.

The Layout of Physical Memory

The rest of physical memory, i.e. from 0x1000000 on up, should be reserved for page frames. The simulated machines have 256MB of memory. Although it is quite possible to determine how much memory there is in the system, for now your kernel should have a #define for the amount of memory.

#define MACHINE_MEMORY_SIZE_MB 256

You should use this memory size in determining the size of your kernel data structures.

Kernel Programming Environment

While we could make you write your own memory management routines for kernel space, we have decided that you should be focusing on process management, virtual memory and system calls instead. To that end, there is a small collection of malloc functions that are available to you. OSKit supports these malloc functions with a list-based memory manager. In particular, here are the malloc functions that you can use.

• void* malloc(int size)
  Standard malloc function. Remember to make sure it returned a non-null pointer!
• void free(void* p)
  Standard free function. Remember to only call it once on an allocated block of memory!
• void* smemalign(int alignment, int size)
  Mallocs a block of memory aligned on the specified alignment boundary (i.e. if alignment is 8, the block of memory will be aligned on an 8 byte boundary). A block of memory malloced with smemalign must be freed with sfree, which takes a size. Therefore, you must keep track of the size of the block of memory you allocated. This is useful for allocating things like page tables, which must be aligned on a page boundary. By volunteering to remember the size, you free the malloc implementation from putting headers or footers which keep it from allocating consecutive pages.
• void sfree(void* p, int size)
  Frees the block of memory pointed to by p. This block must have been malloced by smemalign and it must be the specified size.

To use these functions, #include <oskit/c/malloc.h.> You may also use the str*** and mem*** functions, as well as bzero. To use any of those functions, #include <oskit/c/string.h>. The prototypes of these functions are the same as their Unix counterparts, so you can look up the behavior/prototype using common man pages.

Your console output should be done using your solution to project one. If you did not get project one to work, or were not satisfied with it, you may contact us for some simple console and keyboard routines. We would much rather you use your own code if possible however.

Context Switching

Context switching involves saving the general purpose registers and the segment selector registers of one process, halting its execution somewhere, and then loading the general purpose registers and segment selector registers of another process and resuming its execution where it previously was stopped. You will also need to switch the active page directory to correspond to the new process' address space.

One way to simplify the burden of context switching is to always do it in the same place. If you have a single function which performs the context switch, then the point of execution for every process not currently running is inside that function. You need not explicitly save the instruction pointer.

Writing the routine to context switch processes that have already run is actually not so bad. The messier part is bootstrapping a process to get it to execute for the first time. Before you attempt to run a process for the first time, you will need to set up the top of its kernel stack so that your context switching code loads meaningful context. You might also have a routine which context switches a little differently if the new process has never run before.

A useful tool in bootstrapping processes is the iret instruction. The iret, which you should be familiar with from project one, is used to return from interrupt handler routines. It is capable of changing the code and stack segments, stack pointer, instruction pointer, and EFLAGS register all in one step. It is particularly useful in starting user processes for the first time. A good place to find more information on the behavior of the iret instruction (and what it expects on the stack) is page 153 of intel-sys.pdf. This gives a diagram of what iret expects on the stack.

Do not forget that you will need to register a handler for the timer interrupt, and that it may need to call your scheduler and context switch. Refer to your solution for project one and the project one handout to see how to use the timer. As in project one, your timer should go off every ten milliseconds (i.e. "ticks" are separated by ten milliseconds). As far as your scheduler is concerned, a simple round robin scheme is sufficient for this project.

A Loader for a.out

Getting the Executable's Bytes

exec2obj hello

the result would be a new file in that directory called hello_obj.c. Inside that hello_obj.c file would be a char array called hello, and it would be initialized to the data contained within the hello executable. You can then refer to that array in your loader when you wish to load that particular user application. A table of contents is also created which you can use to locate the array (of which there may be more than one) based on the filename of the executable. The definition for the table of contents is in exec2obj.h.

Eventually, you will be reading your executables from a file system. To facilitate an easy switch from exec2obj to a file system, we would like you to create the following interface to the arrays provided by exec2obj:

int getbytes(char* filename, int offset, int size, char* buf)

The getbytes function should find the file 'filename' in the table of contents in exec2obj.h, seek to the specified offset within the array of bytes for that file, and copy size bytes to buf. The function should return the number of bytes succesfully copied (this could be cut short if you run into the end of the array). If the offset is to the end of the file, getbytes should return zero (regardless of size). If offset goes past the end of the file, -1 should be returned.

Your loader should make calls to your getbytes function in order to acquire the actual bytes of the executable.

Details on the a.out Format

http://www.freebsd.org/cgi/man.cgi

There are some macros that you will find useful in dealing with the a.out format. They are:

#define N_MAGIC(exec) ((exec).a_info & 0xffff)
#define N_BADMAG(x) (N_MAGIC(x) != NMAGIC)
#define N_TXTOFF(x) (sizeof( exec_t ))
#define N_DATOFF(x) (N_TXTOFF + (x)->a_text)

In addition, we will only be using the NMAGIC variant of a.out. You will need this then as well:

#define NMAGIC 0410 /* 0x108 */

The rest of the information should be available in the man page on a.out.

Linking User Processes

• -nostdinc
  Tells the compiler not to include the regular C standard library.
• -g
  Adds debugging information to the object.

• -static
  Tells the linker not to rely on dynamic libraries (this forces all the code that the executable uses to be in the executable).
• --entry=func
  Sets the entrypoint of the executable to be the function func.
• -Ttext addr
  Links the final executable to start at the address addr in memory.

Kernel System Calls

To receive the system call you will need to install a handler for the int instruction you have been using. You should remember how to do this from project one, if not, consult your project one handout or solution. In short you will need to add an entry into the interrupt descriptor table (IDT).

To ensure that we can test for robustness easily, we are requiring you to use int 0x40 as your system call software interrupt. Please do not use a different software interrupt. We also require that you store your system call number in %edi, and a single argument to your system call in %esi. For system calls that take more than one parameter, an argument structure is defined below. The system call should, in this case, take a pointer to this structure in user space.

System Call Interface

• int fork();
  Create a new child process as a copy of the parent (calling) process. On success, in the parent, the new process ID of the child is returned. In the child, the return value should be 0. There may be situations in which the semantics of Fork() may admit several interpretations. You should feel free to implement the semantics you think are best. You may decide to return ERROR if doing the right thing would be grossly inefficient or complex.

• int exec(char* execname, char** argvec)
  Replace the currently running program in the calling process with the program stored in the file named by execname. The argument argvec points to a vector of arguments to pass to the new program as its argument list. The new program receives these arguments as arguments to its main procedure. The argvec is formatted the same as any C program's argv vector. The last entry in the argvec vector must be a NULL pointer to indicate the end of the list. By convention, argvec[0] is the name of the program to be run, but this is controlled entirely by the calling program. The first argument to the new program's main procedure is the number of arguments passed in this vector. On success, there is no return from this call in the calling program, but, rather, the new program begins executing at its entry point, and its conventional main(argc, argv) routine is called. On failure, this call returns an error code.

  Since this system call takes more than one parameter, you should have it take a pointer to a structure with this format:

  struct {
  char* execname;
  char** argvec;
  }

• int exit(int status)
  Terminate execution of the current program and process, and save the integer status for possible later collection by the parent process on a call to wait. All resources used by the calling process are freed, except for the saved status. An exception to this is if some of those resources were being shared with other processes which are still active. In this case, those resources should not and must not be freed.

  On success, there is no return from this call, since the calling process is terminated. On failure, this call returns an ERROR. When a process exits or is aborted, if it has children, they should continue to run normally, but they will no longer have a parent. When the orphans exit, at a later time, you need not save or report their exit status since there is no longer anybody to care.

• int wait(int* status_ptr)
  Collect the process ID and exit status returned by a child process of the calling program. When a child process exits, it is added to a FIFO queue of child processes not yet collected by its specific parent. After the wait call, the child process is removed from this queue. If the calling process has no child processes ( exited or running,) ERROR is returned. Otherwise, if there are no exited child processes waiting for collection by this process, the calling process is blocked until its next child calls exit. The process ID of the child process is returned on success, and its exit status is copied to the integer referenced by the status_ptr argument.

• int yield(int pid)
  The calling process is moved to the end of the runnable queue and a different process is scheduled. If pid is -1, the process that is at the head of the runnable queue is scheduled. If pid refers to a runnable process, that process is scheduled. If pid does not refer to a runnable process, and it is not equal to -1, an ERROR should be returned. Otherwise 0 is returned by yield.

• int deschedule(int* flag)
  This system call must atomically check the integer pointed to by flag, and if that integer is nonzero, this system call returns immediately. Otherwise the kernel must permanently deschedule the calling process until it is made runnable by make_runnable. This function returns 0 if the process was never descheduled, and nonzero if the process was descheduled.

• int make_runnable(int pid)
  Make the process referred to by pid runnable once again. That process must have been previously descheduled by the deschedule system call. If pid does not refer to a process that was previously descheduled, an ERROR should be returned. Otherwise, 0 is returned.

• int getpid()
  Returns the PID of the calling process.

• int brk(void* addr)
  Allocate memory to the calling process' program area, enlarging the program's heap storage so that the value addr is the new break value of the calling process. The break value of a process is the address immediately above the last address used for its program instructions and data. This call has the effect of allocating or deallocating enough memory to cover only up to the specified address, rounded up to an integer multiple of PAGESIZE. If addr is NULL, the current break value should be returned. Note that in this project we do not require you to be able to shrink the heap, therefore if addr is non-NULL and less than the current break value you should return an ERROR. The value 0 is returned on success.

• int sleep(int ticks)
  The calling process is blocked until at least ticks timer interrupts have occurred after the call. Upon completion of the sleep, the value 0 is returned. If ticks is 0, return is immediate. If ticks is less than 0 an ERROR is returned. Remember that "ticks" should be separated by ten milliseconds.

• char getchar()
  Returns a single character from the character input stream. If no characters are currently available, the function blocks until a character is available. It is ok not to return the backspace character; this should simplify integration with the readline system call.

• int readline(int size, char* buf)
  Read the next line from the console and copy it into the buffer pointed to by buf. If there is not currently a line of input available from the console, the process should block until a line is available. The size of the buffer is indicated by the parameter size. If the size of the line exceeds the length of the buffer, only size-1 characters should be returned (you will need to NULL terminate the string also). In this case the remaining characters on the line should be saved for a future call to readline. If the line is smaller than the size of the buffer, then the complete line (including the newline at the end of the line) is copied into the buffer.

  Note that character processing on the backspace character should happen before the string is copied into the buffer and returned to the calling process. The readline system call returns the size of the line (not including the NULL terminating character) as its return value.

  You will need your keyboard interrupt handler from project one to drive this system call. Since it takes more than one argument, you should have readline take a pointer to a structure formatted like this:

  struct {
  int size;
  char* buf;
  }

• int print(int size, char* buf)
  Prints the string pointed to by buf to the console. Only size characters of this string should be printed (imagine what would happen if the user forgot to NULL terminate their string). You should establish a maximum size on the string passed to print and return an ERROR if a process calls print with a larger size than your established maximum. The calling process should block until all characters have been printed to the screen. The print system call returns 0 on success.

  You will need to use your console driver from project one to print characters to the screen. The same scrolling behavior that was present in project one should also be present in project three. You need not maintain a clock, however.

  Also keep in mind that the output of two concurrent print calls should not be intermixed. Since it takes more than one argument, you should have readline take a pointer to a structure formatted like this:

  struct {
  int size;
  char* buf;
  }

• int set_term_color(int color)
  Sets the terminal print color for future calls to print to color. Whether or not this is a global change that affects all processes is a design decision that we leave to you; you must be able to justify your position however. If color does not specify a valid color combination, an ERROR should be returned. Otherwise, 0 is returned by set_term_color.

• int set_cursor_pos(int row, int col)
  Sets the cursor to the location (row,col). Again, whether or not this affects all processes or not is a design decision that you must be able to defend. If the location (row,col) is not valid, an ERROR should be returned. Otherwise, 0 is returned by set_cursor_pos. This system call should take a pointer to a structure that looks like this:

  struct {
  int row;
  int col;
  }

• int minclone()
  The functionality of minclone should be familiar to you from project two. A new process should be created which is an exact copy of the calling process. However, unlike fork, these processes will share their address spaces. The new process also differs in that when it calls exit, it is not eligible to be waited upon by the process that created it with minclone. This is because you have already implemented a thread library which supports this feature.

  You should implement the raw system call (the kernel side of minclone) and then reuse your minclone wrapper from project two.

• int rand()
  Returns a random number between 0 and (2^31 - 1). To get this random number, you may use OSKit's random number generator. To use it, you will need to:
  1. #include <oskit/com/random.h>
  2. Create a random number generator object. This is done by doing something like this:

     oskit_random_t* mr_unpredictable;
     oskit_random_create(&mr_unpredictable);

  3. In the interest of debugging, we will not be seeding our random number generators. If you leave the OSKit random number generator object unseeded it will always be seeded with 0, giving you the same sequence of numbers each time you run your kernel. You would typically do this using things like the time and input from devices which are known to be somewhat random.
  4. To get a random number, use the aptly named oskit_random_random:

     int rand_num;
     oskit_random_random(mr_unpredictable,&rand_num);

• Process IDs
  Using an unsigned integer to represent process IDs will allow billions of unique IDs to be created. For the purposes of this assignment you may forget about the possibility of wrap around. Real operating systems do confront this issue, however it is not a conceptually rich problem so we will not bother with it.

• Fork
  On a Fork, a new process ID is assigned, the user context from the running parent is copied to the child, and new physical memory is allocated into which to copy the parent's memory space contents. Since the CPU can only access memory by virtual addresses (using the page tables) you must map both the source and the destination of this copy into the virtual address space at the same time. You need not map all of both address spaces at the same time, however: the copy may be done piece-meal, since the address spaces are already naturally divided into pages.

• Shared Resources
  If a process exits, you normally need to deallocate all of its resources (including its page tables). However if it is a thread, it may be sharing these resources with another process. Be careful to keep track of whether or not these resources are still being shared and do not free them if they are.

• Requests for Help
  Please do not ask for help from the course staff with a message like this:

  "I'm getting the OSKit default trap handler telling me I have a general protection fault. What's wrong?"

  or

  "I installed my illegal instruction handler and now it's telling me I've executed an illegal instruction. What's wrong?"

  The problem with both of these messages is that they do not show that you have made any effort to debug the problem yourself. We put a lot of effort into giving you powerful debugging tools. Please use them. Questions like these give the appearance that you would rather place your debugging burden on a TA then solve the problem yourself. Debugging is actually one of the best ways to learn operating system concepts.

  Having said that, if you have spent reasonable amount of time trying to solve the problem and are not making any progress, do not hesitate to ask a question. But when you do, provide evidence that you have spent some time trying to solve the problem yourself.

To help you, we have established a recommended plan of attack. Hopefully this will give you an idea of how to start. This also establishes the criteria used for the checkpoints.

1. Read this handout thoroughly.

2. Re-read the complicated parts to make sure you understand what's being said.

3. Think about it all for a while.

4. Write up pseudocode for all the system calls, as well as the timer interrupt handler, scheduler, paging system, and context switcher. You may want to do this in several iterations. Start by just writing down how all these pieces fit together. Then take the level of detail up a notch and start thinking about how they break down into functions. Then write some high-level pseudocode for those functions.

5. Using the previous step as a guide, come up with the data structures you think you will need for your kernel. The most important data structure is probably your process control block, or PCB. What needs to be in the PCB?

6. Write the a.out loader. The a.out loader is very straightforward and you will need it to get your user processes running.

7. Write a user-level idle process (a simple while(1); will do), create a PCB for it, and switch to it in your kernel. At this point you will not be running virtual memory, and you will not have any other processes. Being able to switch to a user-mode process is an important step however.

8. If you can switch to the idle process, you have enough for checkpoint one.

9. Implement paging. Write a page fault handler that allocates frames for legal accesses in unallocated memory, and prints a message when a bad memory reference occurs.

10. Now that you can load a user process and switch to it, do the same thing except this time load a second user process (init) and have the timer interrupt switch between the two of them. This will require you to write your context switching code.

11. If you can load two processes and context switch between them, you have successfully reached checkpoint two.

12. Implement the getpid system call. Once this is working, your system call interface is functioning correctly.

13. Implement the brk system call and test it with user processes that use malloc.

14. Implement sleep. This will test blocking a process from executing.

15. Implement fork.

16. Implement exec. You can now test fork and exec by having your init process spawn off a third user process.

17. Implement wait and exit.

18. If fork, exec, wait, and exit are all working, you have enough to pass checkpoint three.

19. Implement yield,deschedule, and make_runnable.

20. Implement minclone. You should now be able to use your thread library with your kernel.

21. Implement the terminal I/O related system calls.

22. Implement rand.

23. Bang on your kernel to shake all the bugs out until your fists are sore.

24. Hand your kernel project in.

25. Have an excellent Spring Break!