Requirements

Five possible features for your paging simulation are specified below. Everyone should do the first (access permissions) and at least one other feature. People working in a team should do access permissions and at least two other features. Everyone who wants more than an A- should include one of the two features that require files: memory-mapped files or swapping. (Swapping is the most complicated feature; I will be very surprised if someone actually does it. I certainly haven't.)

In addition to the paging system, you should write test programs for the features that you implement.

You are responsible for designing both the API for your system and the implementation. But note that you mght need a more complicated core map of physical memory. For Lab 6, the core map needed only a flag for each physical page saying whether the page is allocated or free. You will also need to add things to the page tables.

You should document your work with an essay that specifies your API and discusses the implementation. You should also say something about each test program and how to use it.

Access Permissions: Read or Read/Write

One of the most basic features of paging is the ability to make pages read-only. Every version of Assignment 7 must implement this feature. The information that you store in your virtual page table should include the access permission for that page. The access permission can be read-only or read/write. An attempt to write to a read-only virtual page will trigger some sort of action. It is possible that the attempted write is simply an error, but your code will have to consult the core map before deciding on the appropriate response. For example, a page might be marked read-only because it is being used as copy-on-write memory.

You should have a way for a "user process" to mark a region of virtual memory as read-only. It is possible that a user process might have its own reasons for doing that. However, it is also possible that read-only memory is only used as part of the implementation of other features.

Shared Memory

Shared memory refers to physical pages that can be mapped into two or more virtual address spaces. That is, there can be entries in two or more page tables that refer to the same page of physical memory. To implement shared memory, you need a way to create shared regions of physical memory and a way to map them into the address space represented by a page table.

Shared memory will need some sort of API. For example, there could be a function to create a shared memory area with a given number of pages and a function to map a shared memory region into a page table. (You might or might not require that the shared memory come from some existing page table; it's easier if you don't do that, but it's easier to make read-only shared memory regions if you do.) Ideally, there would be some way of discarding a shared memory region, but that's not a requirement for this project.

Also ideally, it would be possible to specify that a shared memory region is read-only. But note that even for read/write shared memory, you are not responsible for synchronizing access. That is the responsibility of the processes that share the memory.

You can assume that a shared memory segment is always made up of complete pages. That is, it does not start or end in the middle of a page. (The API might specify the size of the shared region in pages, at the time it is created.)

You can put a limit on the number of shared memory region that your system will allow. (This allows you to store information about shared memory regions in an array of structs, and to identify a shared region by an integer id number giving the index in the array.)

Copy on Write

You can include copy-on-write in your paging implementation by providing an API for copying a segment of (read/write) memory from one virtual address space to another virtual address space. Without copy-on-write, this would be done by making copies of the physical pages that are used by the memory segment in the first address space, and mapping the new pages into the page table for the second virtual address space. However, the goal of copy-on-write is to avoid copying a page until there is a write to the page.

Copy-on-write can be implemented by mapping the original physical pages into the second virtual address space, and marking the corresponding virtual pages as read-only in both page tables. The core map will have to record that each page is copy-on-write. When there is an attempted write to the page using either page table, a copy of the page should be made, the appropriate page table entry should be adjusted accordingly, and the write should then be allowed to proceed.

Note that there is a synchronization issue here. Two threads might both try to write to the same page at about the same time. The page has to be "locked" while a copy is being made. You are responsible for handling this issue. Keeping a reference count for the page might help.

Memory-mapped Files

Memory-mapped files make it possible to make file I/O look like ordinary memory reads and writes. A region in a file is mapped into a region in a virtual address space, so that accesses to virtual memory in that region actually access the file.

You will need to provide an API for mapping a region in a file into a virtual address space. You can assume that the size of the region is a multiple of the page size, and that the mapped region in virtual memory consists of complete pages. It should be possible to have both read-only and read-write mappings. A page table entry that corresponds to part of a file does not need an associated physical page (although in a real operating system, it would have one for efficiency to mirror the contents of the file). You can add data to your page tables to record file mappings, or you can simply mark the virtual page as invalid and let another part of your system recognize the file mapping when there is an access to that invalid page. (The second option is closer to what a real OS does, but you are not required to follow that model.)

My implementation associates a memory-mapped file with a specific page table. As with shared memory, you can put a limit on the total number of memory-mapped files.

You will need to use random access files. We have already used them in C. If you are writing in Java, you will need the RandomAccessFile class. Some methods in that class:

• constructor: new RandomAccessFile(file, mode), where mode can be "r" or "rw" to indicate access permissions.
• long length() — returns the number of bytes in the file.
• void seek(long pos) — moves the file pointer to pos bytes from the beginning.
• int read() — returns -1 if at end-of-file, or reads one byte, which is returned in the lower 8 bits of the int. (That is, you can type-cast the return value to byte, if it is not -1)
• int read(byte[] buffer, int startindex, int count) — reads up to count bytes from the file and stores them in buffer starting at index startindex. The return value is -1 if no bytes are read because the file position is at end of file. Otherwise, it is the actual number of bytes read.
• void write(int b) — write one byte at the current position in the file. The byte is given by the lower 8 bits of b.
• void write(byte[] buffer, int startindex, int count) — writes count bytes from buffer to the file. The bytes are taken from the buffer starting at index startindex.

Swapping to Disk

This is certainly the most complicated feature, and you shouldn't attempt it without thinking carefully about the design of the implementation.

Swapping is what people often think of when they hear the term "virtual memory," since it lets programs use more physical memory than will fit into the computer's RAM. Pages that don't fit into physical memory can be "swapped out to disk" and swapped back into RAM when they are needed. The extra memory is "virtual."

To implement swapping, you need a "swap file" on disk to hold the swapped out pages. The swap file is divided into pages, and each page in the swap file can hold one swapped out page of physical memory. You will need to keep track of which pages in the swap file are free.

You will also need to keep track of which virtual pages have been swapped out and where in the file they are located. It is probably easiest to put this information in the page tables.

It is typical to allow physical pages to be marked as unswappable, to prevent important pages from being swapped out to disk. (You might want to mark shared and copy-on-write pages as unswappable, so you don't have to take swapping into account in their implementation.)

Swapping is only used when physical memory is full and you want to allocate a new physical page. In that case, you can select a page to be swapped out to disk. It will probably be easiest to choose that page at random.

When a reference is made to a swapped out page, it has to be loaded back into physical memory. This might mean evicting another page from memory to make room for it.

Note that swapping requires a "reverse page table" that maps physical pages to the page table entries that refer to them. This is because the page table entry has to be modified when the physical page that it refers to is swapped to or from disk.