This project will require you to implement a simple virtual memory mechanism in your operating system. The processes will now each execute in a separate virtual address space. These address space will be protected from each other, so one process may not access or modify data in another address space. Additionally the kernel will also be protected from the processes in a similar manner. In this project the kernel and the kernel threads run in kernel mode (privilege level 0) and the processes are executed in user mode (privilege level 3).

Your task in this project is to implement a simple, demand-paged virtual memory system with a floppy diskette. In order to accomplish this, you will need to the following :

• Set up a two-level page table per process, the page table will also map (with proper protection) the entire address space of the kernel. Thus, all kernel threads share the same page table.
• A page fault handler for the faulting virtual page to allocate a physical page frame and fetch the virtual page from the floppy diskette.
• A physical page frame allocation scheme to allocate the physical page frame. When it runs out of physical page frames, it will trigger a random page replacement policy to evict a physical page frame to the floppy diskette.

You should use the code available in the class webpage as a starting point for your project. We have provided you with two main components to help you with the virtual memory implementation:

• The user and kernel protection mechanism.
• A floppy diskette driver that allow you to write to and read from a sector synchronously (see floppy.h for more details).

There are now 33 files. Don't be daunted by the large number of files since you are already familiar with many of them, and the only file that needs to be changed is memory.c.

• Makefile : A makefile for you to compile with the right options.
• bootblock.s: Code for the bootblock of a bootable disk.
• cantboot.s: Code for the bootblock of a non-bootable disk.
• common.h: Common constants, macros, and type definitions.
• createimage.c: Tool to create a bootable operating system image on a floppy diskette.
• floppy.c: Code to access the floppy drive.
• floppy.h: Header file for floppy.c.
• interrupt.c: Interrupt handlers.
• interrupt.h: Header file for interrupt.c.
• kernel.c: Kernel code.
• kernel.h: Header file for kernel.c.
• keyboard.c: Keyboard handling code.
• keyboard.h: Header file for keyboard.c.
• mbox.c: The implementation of the mailbox mechanism.
• mbox.h: Header file for mbox.c.
• memory.c: Allocator for physical memory page frame, page-table handling, and virtual memory mapping.
• memory.h: Header file for memory.c.
• process1.c: The first user process.
• process2.c: The second user process.
• process3.c: One of the processes to test the mailboxes.
• process4.c: The other process used to test the mailboxes.
• scheduler.c: Scheduler code.
• scheduler.h: Header file for scheduler.c.
• shell.c: A primitive shell that uses the keyboard input.
• syslib.c: System calls.
• syslib.h: Header file for syslib.c.
• th.h: Header file of th1.c and th2.c.
• th1.c: Code of the loader thread and the clock thread.
• th2.c: Code of two kernel threads to test synchronization primitives.
• thread.c: Synchronization primitives.
• thread.h: Header file for thread.c.
• util.c: Library of useful support routines.
• util.h: Header file for util.c.

Since our entire project will be using the floppy drive, please do not read/modify the hard disk.

Detailed Requirements and Hints

Before starting this project, you should read carefully Chapters 2-4 of the Intel Architecture Software Developer's Manual, Volume 3: System Programming Guide to understand the address translation mechanism so that you can understand how to set up the page tables. As discussed in class, x86 architectures use a two-level table structure with a directory page that has 1024 entries pointing to the actual page tables. You need to understand this structure very well.

In this project, you can make several assumptions and constraints to simplify your design and implementation.

The floppy diskette is much smaller than the physical memory on your PC, you can assume that the physical memory for all user processes is smaller than the size of the reserved virtual memory paging space on a floppy diskette. This assumption will allow you to trigger demand paging.

You can simplify the mapping between a virtual address space and the backing store space on the floppy diskette to avoid implementing a diskette allocator. You can use the area allocated on the diskette for the image file as the backing store for each process. You can assume that processes do not use a heap for dynamic memory allocation.

You need to figure out how to initially map your physical memory page frames to run the kernel threads and how to load the code and data of a process into its address space. When the address space for the process is initialized, all the code and data pages for the process are marked as invalid. This will triggers the page_fault_handler() to run on the first access to any of these pages. At this time you can allocate a physical page frame and read in the page from the diskette.

Finally, you can assume that your virtual memory deals with only the data and code pages. All pages of the stack segments are "pinned," they will never be evicted by your page replacement mechanism. This means that you need to perform pinning when you initialize a process's address space. Also, you can assume that physical pages that are allocated to store the page-tables are pinned in memory and do not get paged.

Extra Credits

There are up to two possible extra credits you can receive in this project by doing one of the following extensions to the project:

Implement the FIFO with second chance replacement policy described in the class.

Implement asynchronous operations. This means that after issuing a floppy diskette read or write operation, the faulting process will be suspended instead of busy waiting and let another process to run to overlap your I/O with computation.

Useful Resources

• Chapter 2 (System Architecture Overview), Chapter 3 (Protected-Mode Memory Management), and Chapter 4 (Protection), Intel Architecture Software Developer's Manual, Volume 3: System Programming Guide
• Guide to programming with Pentium/Pentium-Pro.
• Using the GNU Assembler (especially the section specific to 80386): Describes the format and more
• Brennan's Guide to Inline Assembly
• An Introduction to Programming with Threads, Andrew D. Birrell
• M-x info under Emacs. Then : gcc -> C extensions -> Extended Asm

Submitting Programming Assignments

Submit your final solution electronically using the following command:

/u/cs318/bin/318submit 5 README otherfiles ...

The submit command copies your files to the directory /u/cs318/submit/user/number and lists all the files that you have submitted for assignment number. user is your user account name. If you execute submit after the project deadline, your files are placed in directory number_late. You can run submit more than once, and you can submit partial lists of files.

CS318 Staff