Systems Programming and Machine Organization
This is the 2012 version of the course. Main site
- 1 Assignment 3: WeensyOS
- 1.1 Get the code
- 1.2 Initial state
- 1.3 Goal
- 1.4 Notes
- 1.5 Step 1: Kernel isolation
- 1.6 Step 2: Virtual page allocation
- 1.7 Step 3: Isolated address spaces
- 1.8 Step 4: Overlapping address spaces
- 1.9 Step 5: Fork
- 1.10 Step 6: Shared read-only memory
- 1.11 Step 7 (Optional/Extra Credit): Freeing memory
- 1.12 More extra credit ideas
- 1.13 Turnin
Assignment 3: WeensyOS
In this assignment, you implement process memory isolation, virtual memory, and some system calls in a tiny operating system. This will introduce you to virtual memory and operating system design.
- Assigned Tue 10/16
- Due Tue 10/30 Wed 10/31 11:59:59pm (extension 1 day later)
- This assignment may be completed in pairs.
- You must run this assignment on a CS50 Appliance. Running on Linux will probably work too, but running on Mac without a VM will not likely work.
We will update this problem set description. You may also want to ponder Chapter 9 of CS:APP2e. The 32-bit x86 virtual memory architecture is described in Section 9.6.3. The
PTE_U bits are mentioned in Section 9.7.1.
Get the code
First, ensure that your repository has a
handout remote. Type
git remote show handout
If this reports an error, run
git remote add handout git://code.seas.harvard.edu/cs61/cs61-psets.git
git pull handout master. This will merge our Assignment 3 code with your previous work. If you have any “conflicts” from Assignment 1, resolve them before continuing further. Run
git push to save your work back to code.seas.
You may also create a new
cs61-psets repository for this assignment. You’ll need to tell us if you do.
make run in your
pset3 directory. You should see something like this, which shows four versions of the
p-allocator process running in parallel:
This image loops forever; in an actual run, the bars will move to the right and stay there. Don't worry if your image has different numbers of K's or otherwise has different details.
If your bars run painfully slowly, edit the
p-allocator.c file and reduce the
Stop now to read and understand
p-allocator.c. Here’s what’s going on in the physical memory display.
- WeensyOS displays the current state of physical and virtual memory. Each character represents 4 KB of memory: a single page. There is 2 MB of physical memory in total.
- WeensyOS runs four processes, 1 through 4. Each process is compiled from the same source code (
p-allocator.c), but linked at a different address.
- Each process must use a separate region of memory in this initial WeensyOS version. We preallocate 1/4 MB for each process.
- Each process asks the kernel for more heap space, one page at a time, until it runs out of room. As usual, each process's heap begins just above its code and global data, and ends just below its stack. The processes allocate space at different rates: compared to Process 1, Process 2 allocates space twice as fast, Process 3 goes three times as fast, and Process 4 goes four times as fast. (A random number generator is used, so the exact rates may vary.) The marching rows of numbers show how fast the heap spaces for processes 1, 2, 3, and 4 are allocated.
Here are two labeled memory diagrams, showing what the characters mean and how memory is arranged.
The virtual memory display is similar.
- The virtual memory display cycles between the four processes' address spaces. However, all the address spaces are the same for now.
- Blank spaces in the virtual memory display correspond to unmapped addresses. If a process (or the kernel) tries to access such an address, the processor will page fault.
- The character shown at address X in the virtual memory display identifies the owner of the corresponding physical page.
- In the virtual memory display, a character is reverse video if an application process is allowed to access the corresponding address. Initially, any process can modify all of physical memory, including the kernel. Memory is not properly isolated.
You will implement complete and correct memory isolation for WeensyOS processes. Then you'll implement full virtual memory, which will improve utilization. You'll implement fork: creating new processes at runtime. Finally, for extra credit, you'll implement exit.
We need to provide a lot of support code for this assignment, but the code you write will be limited. Our solutions contain less than 200 lines. All your code goes in
kernel.c (except for part of step 6).
README-OS.md file for information on how to run WeensyOS. If QEMU’s default display causes accessibility problems, you will want to run
make run-console. To make
run-console the default, run
export QEMUCONSOLE=1 in your shell. We recommend
make run-gdb for debugging, as well as adding
log_printf statements to your code (the output of
log_printf is written to the file
Memory system layout
WeensyOS memory system layout is described by several constants.
||Start of kernel code.|
||Top of kernel stack. The kernel stack is one page long.|
||CGA console memory.|
||Start of application code. Applications should not be able to access memory below |
||Size of physical memory in bytes. WeensyOS does not support physical addresses ≥ |
||Number of physical pages. Equals |
||Size of virtual memory. WeensyOS does not support virtual addresses ≥ |
Kernel and process address spaces
WeensyOS begins with the kernel and all processes sharing a single address space. This is defined by the
kernel_pagedir page directory.
kernel_pagedir is initialized to the identity mapping: virtual address X maps to physical address X.
As you work through the pset, you will shift processes to using their own independent address spaces. Only a subset of physical memory is accessible through any individual process’s address space.
The kernel, though, still needs the ability to access any location in physical memory. Therefore, all kernel functions use the
kernel_pagedir page directory, and in kernel functions, each accessible virtual address has the same numeric value as the corresponding physical address. Code in
interrupt explicitly installs
kernel_pagedir on entry.
There is one exception—after Step 2 and before Step 3, the kernel can’t necessarily access all of physical memory. Why?
WeensyOS system calls are more expensive than they need to be, since every system call switches address spaces twice (once to
kernel_pagedir and once back to the process’s page directory). Real operating systems avoid this overhead. In real OSes kernels access memory using process page directories, rather than a kernel-specific
kernel_pagedir. This makes the kernel code more complicated, since kernels can’t always access all of physical memory directly.
Step 1: Kernel isolation
WeensyOS processes could stamp all over the kernel’s memory if they wanted. Better stop that. Change
start, the kernel initialization function, so that kernel memory is inaccessible to applications—except for the memory holding the CGA console (the single page at
(uintptr_t) console == 0xB8000).
When you are done, WeensyOS should look like this. In the virtual map, kernel memory is no longer reverse-video, since the user can’t access it. Note the lonely CGA console memory block.
virtual_memory_map. A description of this function is in
kernel.h. You will benefit from reading all the function descriptions in
- If you really want to look at the code for
virtual_memory_map, it is in
k-hardware.c, along with many other grody hardware functions.
virtual_memory_mapis a bitwise-or of zero or more
PTE_Pmarks Present pages (pages that are mapped).
PTE_Wmarks Writable pages.
PTE_Umarks User-accessible pages—pages accessible to applications. You want kernel memory to be mapped with permissions
PTE_P|PTE_W, which will prevent applications from reading or writing the memory, while allowing the kernel to both read and write.
- Make sure that your
sys_page_allocsystem call is safe. Applications shouldn’t be able to use
sys_page_allocto screw up the kernel.
Step 2: Virtual page allocation
You could also do step 3 first.
So far, WeensyOS processes use physical page allocation: the page with physical address X is used to satisfy the
sys_page_alloc(X) allocation request for virtual address X. This is inflexible and limits utilization. Change the implementation of the
INT_SYS_PAGE_ALLOC system call so that it can use any free physical page to satisfy a
INT_SYS_PAGE_ALLOC code must perform the following tasks.
- Find a free physical page using the
-1to the application if you can’t find one. Use any algorithm you like to find a free physical page; we just return the first one we find.
- Record the physical page’s allocation in
- Map that physical page at the requested address (
Don’t modify the
page_alloc helper function, which is also used by the program loader. You can write a new function if you want.
Here’s how our OS looks after this step.
- Look at the other code in
kernel.cfor some hints on how to examine the
- A physical page is free if
pageinfo[PAGENUMBER].refcount == 0.
Step 3: Isolated address spaces
Implement process isolation by giving each process its own independent page directory. Your OS should look like this:
What goes in per-process page directories:
- Each process’s initial page directory should be based on
- A WeensyOS page directory consists of two physical pages: the page directory page (PDP) and a single page table page (PTP). You must allocate both these pages. (In a larger operating system, a PDP would reference multiple PTPs.) These pages should be owned by the process (should have
pageinfo[PN].owner == processid).
- The PDP’s contents are all 0, except for
pagedir, which should equal
(pageentry_t) address_of_new_PTP | PTE_P | PTE_W | PTE_U.
- The initial mappings for addresses less than
PROC_START_ADDRshould be copied from those in
kernel_pagedir. You can use a loop with
virtual_memory_mapto copy them. Alternately, you can copy the mappings from the kernel’s page directory into the new page directory using
memcpy. This is faster, but make sure you copy the right data! (Hint: not
- The initial mappings for addresses greater than or equal to
PROC_STARTshould be all zero.
- It is also acceptable to copy all the mappings from
kernel_pagedirinto the new page directory. But in this case, your
kernel_pagedirshould map all memory as inaccessible to processes. This strategy leads to an OS that looks like this:
The reverse video shows that this OS also implements process isolation correctly.
How to implement per-process page directories:
process_setupto create per-process page directories.
- We suggest you write a
copy_pagedir(pageentry_t *pagedir, int8_t owner)function that allocates and returns a new page directory, initialized as a copy of
pagedir. This function will be useful in Step 5. In
process_setupyou can modify the page directory returned by
copy_pagediraccording to the requirements above.
- If you create an incorrect page directory, it’s likely that WeensyOS will crazily reboot.
page_allocfunction must include a call to
virtual_memory_map(pagedir, addr, addr, PAGESIZE, PTE_P|PTE_W|PTE_U). Our initial handout code lacked this call. Try
git pull handout masterto update your code.
Step 4: Overlapping address spaces
Now the processes are isolated, which is awesome. But they’re still not taking full advantage of virtual memory. Isolated address spaces can use the same virtual addresses for different physical memory. There’s no need to keep the four process address spaces disjoint.
In this step, change each process’s stack to start from address
0x300000 == MEMSIZE_VIRTUAL. Now the processes have enough heap room to use up all of physical memory!
(Our solution prints “
Out of physical memory!” to the console when a
sys_page_alloc fails for that reason. You don’t need to implement this.)
Step 5: Fork
fork system call is one of Unix’s great ideas. It starts a new process as a copy of an existing process. The
fork system call appears to return twice, once to each process. To the child process, it returns 0. To the parent process, it returns the child’s process ID.
Run WeensyOS with
make run or
make run-console. At any time, press the ‘
f’ key. This will soft-reboot WeensyOS and ask it to run a single
p-fork process, rather than the gang of
allocators. You should see something like this:
This is because you haven’t implemented
- When a process calls
fork, look for a free process slot in the
processesarray. Don’t use slot 0. If no slot exists, return
-1to the caller.
- If a free slot is found, make a copy of
current->p_pagedir, the forking process’s page directory, using your function from earlier.
- But you must also copy the process data in every application page shared by the two processes. The processes should not share any writable memory except the console (otherwise they wouldn’t be isolated). So
forkmust examine every virtual address in the old page directory. Whenever the parent process has an application-writable page at virtual address
forkmust allocate a new physical page
P; copy the data from
memcpy; and finally map page
Vin the child process’s page directory.
- The child process’s registers are initialized as a copy of the parent process’s registers, except for
virtual_memory_lookupto query the mapping between virtual and physical addresses in a page directory.
When you’re done, you should see something like this after pressing ‘
An image like this means you forgot to copy the data for some pages, so the processes are actually sharing stack and/or data pages:
You must complete at least one of Step 6 and Step 7. Step 6 is easier.
It’s wasteful for
fork() to copy all of a process’s memory. For example, most processes, including
p-fork, never change their code. So what if we shared the memory containing the code? That’d be fine for process isolation, as long as neither process could write the code.
Change the process loader in
k-loader.c to detect read-only program segments and map them as read-only for applications (
PTE_P|PTE_U). A program segment
ph is read-only iff
(ph->p_flags & ELF_PFLAG_WRITE) == 0.
fork() code shouldn’t copy shareable pages, but it should keep track of the number of active references to each user page. Specifically, if
pageinfo[pn].refcount > 0 and
pageinfo[pn].owner > 0, then
pageinfo[pn].refcount should equal the number of times
pn is mapped in process page directories.
When you’re done, running
p-fork should look like this:
Each process’s virtual address space begins with a darker-colored “1”. The dark color indicates that the corresponding physical page has reference count (
refcount) greater than 1. (The color difference is only visible on graphical QEMU; the console version doesn’t distinguish between light reverse-video and dark reverse-video.)
- Mark a program segment read-only after the
memsetoperations that add data to the segment. Otherwise you’ll get a fault.
Step 7 (Optional/Extra Credit): Freeing memory
So far none of your test programs have ever freed memory or exited. Memory allocation’s pretty easy until you add free! So let’s do that, by allowing applications to exit. In this exercise you’ll implement the
sys_exit system call, which exits the current process.
We hope everyone tries this exercise, but it is optional, and definitely harder than the others. Freeing memory will tend to expose weaknesses and problems in your other code.
To test your work, use
make run and then type ‘
e’. This reboots WeensyOS to run the
p-forkexit program. (Initially it’ll crash because
sys_exit() isn’t implemented yet.)
p-forkexit combines two types of behavior:
- Process 1 simply forks children indefinitely.
- The child processes, #2 and up, are memory allocators, as in the previous parts of the pset. But with small probability at each step, each child process either exits or attempts to fork a new child.
The result is that once your code is correct,
p-forkexit makes crazy patterns forever. An example:
Here’s your task.
sys_exitshould mark a process as free and free all of its memory. This includes the process’s code, data, heap, and stack pages, as well as the pages used for its page directory and page table pages.
p-forkexit, unlike in previous parts of the pset,
sys_forkcan run when there isn’t quite enough memory to create a new process. Your code should handle this case. If there isn’t enough free memory to allocate a process,
fork()should clean up after itself (i.e., free any memory that was allocated for the new process before memory ran out), and then return
-1to the caller.
- If you implemented Step 6, make sure your reference counts are correct.
virtual_memory_check function, which runs periodically, should help catch some errors. Feel free to add checks of your own.
More extra credit ideas
- Copy-on-write page allocation!
- Faster system calls!
You will turn in your code by pushing your git repository to code.seas.harvard.edu.
This pset was created for CS61, Fall 2012, completely revised from “minilabs” written for classes at UCLA.