This lab is the complete exercise, but since the concepts involved are the most sophisticated so far it is likely to need clarification and will be updated. Some links to test data and the expected results will also be added.
This lab expands on the work done in the previous lab by introducing a simplified demand paging scheme for virtual memory. Implementing the virtual memory will allow for the allocation of more pages than can fit in `physical memory'. A floppy disk will serve as the swap device, and a segmentation fault handler will be implemented to simulate page fault handling. Unlike the previous lab, the memory management in this lab will only be done for one process because a proper demand paging scheme would require substantial interprocess communication.
You should consult the textbook if you need to. The concepts and terminology in this lab are too many and too involved to explain. You may also like to compile a glossary of terms for yourself until you are comfortable with them.
The sections of this lab take you through the design of one system, so it will be sufficient to demonstrate only what you have at the end.
Accessing the floppy drive is only possible when logged into a local machine. Anybody working on this lab using a remote login should create a file the same size as a floppy disk and access that file in the parts of their program that would otherwise be accessing the disk device. Nevertheless, you will be expected to use the disk device in the lab.
Since the advantage of virtual memory comes as we increase the demands a program makes on memory, the first thing we will do is write a program that will make such a demand, so that the virtual memory implementation may be tested as it is developed. The simplest data source of varying size are files.
Using your code from the previous lab, write a program that takes the name of a file as its argument and finds the size of the file using either stat() or fstat(). With this size, calculate and allocate the number of pages required to read in and store the entire file. To read in the file you must use the file descriptor system calls open() and read(), since fopen() and other file stream calls allocate memory. You should also read() in the file one character at a time, into a temporary char variable, and then copy the character into the allocated page. Attempting to read() directly into the allocated page will cause problems later on since read() checks the destination address for validity.
Test your program by giving it a file and, after it finishes, hexdumping the memory file to see that the data file was correctly read in. Don't forget to specify a file that is smaller than the size of memory.
One of the challenges with virtual memory is to make it work with an unpredictable pattern of memory accesses. To test this, call the library function qsort() on the data that has been read from the file. qsort() can be applied directly to your allocated pages, and you should sort one character at a time. You will need to write a comparison function to compare characters and pass this function to qsort(), which is good practice for implementing the signal handler later since they both use function pointers.
Test your program by reading in the same file and then hexdumping memory again. You should see memory was sorted before the program exited. What's more, the sort will be easy to read in hexadecimal since the data will be in order of increasing byte value.
To finish the test code, write a loop which prints out the sorted data, one character at a time, to standard out. From now on, when using a large amount of data for testing, you should redirect the output of your program to a file and examine the file after your program finishes.
In the previous lab, the maximum number of pages that could be allocated was equal to the number of frames in physical memory. In a sense, the virtual address space was equal in size to the physical address space. With virtual memory, however, we allocate more pages than can be fit into physical memory at one time, and so the size of the pagetable needs to be increased. A floppy disk is going to be our swap device, and the common 3.5 inch floppy has 18 sectors per track, 2 heads, 80 cylinders, and 512 bytes per sector. Using these parameters, calculate how many pages will fit onto the swap device and make the pagetable this size.
In a purely demand paged system, frames are never allocated as a result of a program request. Instead, the system reserves some space on the swap device and calculates the virtual addresses corresponding to the allocated pages. Normally this involves introducing more tables and lists to keep track of free space on the swap device and where each page is, but since we're only demand paging one process we will greatly simplify this by saying the page number is the location on the swap device. For a real multiprocessing implementation this couldn't work, of course, because processes using the same virtual addresses (pages) would need different locations on the swap device.
Since this is a substantial change from the previous lab, comment out (but do not delete) your page allocator. Write a new one which takes the same argument, i.e. the number of pages to allocated, and returns the virtual address of the first page. The only data the function should update is the counter of pages allocated.
Your new allocator should basically do everything the old one did except for choosing free frames and mapping them to pages. In a virtual memory system this mapping happens when a page is swapped in, and so the code that you've commented out which used to do this will be used in that part of the program.
You should also disable your page cleaner until later in the lab, since the number of allocated pages will no longer be equal to the number of allocated frames. Until the page cleaner is reprogrammed, reinitialise your free frame list between tests of the current program.
Run your program now with a test file you were using earlier. Since no frame was allocated and no memory mapping was done, when your program attempts to access the memory address returned by the allocator, it should cause a segmentation fault. You might like to do this in gdb so you can check that the address, which should be page-aligned and after the segment break, is what you expect.
What has happened so far is that your program has attempted to access a page that has been allocated to it. This is something that should work, of course. The problem is that the page, at the moment, only exists on the swap device and has not been brought into memory. On a real system attempting to access such a page causes a page fault. The operating system then sees if the memory access refers to a page that has been allocated, and brings it into memory from the swap device. If, however, the memory access was completely invalid, i.e. there was no such page even on the swap device, then an error condition is asserted for the process doing the access. In UNIX, this error condition is a segmentation violation, or fault, since the address being accessed was outside any segment the system knew about.
We are doing our own virtual memory system, however, and we want to give that memory address a further chance since it might refer to a page that's been allocated by our program. To do that we will write a segmentation fault handler, and it will be our version of a page fault handler. Nevertheless, it is worth noting that a segmentation fault is really a particular kind of page fault, and so it is not entirely inaccurate to say what we will program is a page fault handler.
In UNIX, When a segmentation fault happens, the process that caused the fault is sent a signal. As a result of receiving the signal, a special function called the handler for that signal is called, and given certain arguments by the system for it to use when handling the signal. UNIX provides default functions for most signals, and the default for the segmentation fault will cause a core dump and exit immediately. If we define our own function, however, and install it as the handler for segmentation faults, we have the option of recovering from the segmentation fault since returning from the handler will continue the program.
Signal handlers are installed with the function sigaction(). By calling sigaction() we tell the system which function we want called when a particular signal happens. As its first argument sigaction() takes the number of the signal which the handler is for, and this number should be given using a standard #define. For a segmentation fault, it is SIGSEGV. The second argument is a special struct which contains the settings for the new handler, and the third argument can be used to save the settings for the old handler, but there's no need to do this.
The struct provides two ways of giving the handler function. One of these ways only uses one argument to the signal handler, and that argument is the signal number. To handle page faults, however, we need more; specifically, we need the address that was being accessed when the page fault occured. As a result, the other version of the handler function must be used. This version has three arguments, and the second argument is an interface called siginfo which will allow us to get that address. Additionally, a flag must be given in the struct to say this version of the handler is being used.
The only other struct member that needs attention is the mask. This is a set of signals that are ignored when the signal we are setting up (SIGSEGV) happens and is handled. Since many things might go wrong while we are handling a page fault, it is better not to block any, and this member can be made an empty set with sigemptyset().
Having done all that, the actual signal handler still needs to be written. To keep things simple at first, this function should just output a message saying that a segmentation fault happened, and the memory address which caused the fault. This address will be in the second argument of the handler, which is a struct described in the sigaction() man page. After outputting the message your program should exit to prevent an infinite loop of segmentation faults, since returning without having changed anything would just cause the fault to happen again.
If you run your program now you should find your own signal handler being called. Make sure it is printing out a sensible value for the address which caused the page fault - the address should be somewhere amongst the pages allocated by your program. With page faults being detected and diagnosed correctly, we are able to move on to the job of moving pages in and out of memory.
Just trapping the segmentation fault is not much use, of course. What needs to be done in response to the fault is that, if the page is one we have allocated, we need to read it in from the swap device and write it to physical memory. To do that, however, a frame in physical memory needs to be allocated for the page first.
Write a new function to swap in a page. This function will not return anything, and will take a page number as its only argument. Copy the code from your old page allocator that chooses a free frame to use for allocation and maps a page in to that frame into this function so that swapping in the page now does this job.
To actually get the page from the swap device, use open() with the file "/dev/fd0", which will access the floppy disk. Then use lseek() to move along the disk by the correct number of bytes to reach where the page is. Remember that the floppy, as swap device, is divided up into pages, and that for convenience the page number is being used as the index to the swap device. Finally, use read() to copy that page from the floppy directly into the memory address corresponding to the page. Since the memory address has been mapped and is valid, you can read() directly into it. You should also output the page number being swapped with an appropriate message, so you can see what's going on when you run your program.
With this function written, change your signal handler to calculate the page number from the address which caused the fault. Check to see that the page is within the range of page numbers that you have allocated, exiting with a `real' segmentation fault if it is not, otherwise swap in this page. Since there should be a mapping at the address which previously caused the page fault, your handler doesn't need to exit anymore and can just return, which will bring the process back to what it was doing when the signal happened.
Test this by running your program. What should now happen is that, if given a file smaller than physical memory, the initial page faults will trigger memory mappings when the pages are swapped in, and then the program should run normally from then on. This does not test if the correct copying from the floppy is being done yet, however. To begin that test, try using a file which is larger than physical memory. If you copied the code from your allocator correctly, your program should exit when it runs out of frames. The solution to this offered by virtual memory is to do some page replacement, and when this is working you will be able to see if your programs swaps to and from the floppy correctly.
Write a function, which, like swapping in a page, doesn't return anything and takes a page number as its only argument. Using lseek() and write(), move to the part of the swap device where this page is stored and copy from memory onto the swap device the current data for the page. This function should also print out an appropriate message with the page number.
Swapping out is normally done because another page needs to use the frame that has just been freed, so attempts to write to the page that has just been swapped out need to be prevented. In short, the page just swapped out needs to be made invalid. Normally there would be a valid/invalid bit in the pagetable, but UNIX is already keeping track of this for us with mapped/unmapped address, so all we need to do is unmap the page which has been swapped out. The function for this is munmap().
Incidentally, it is this part which makes a complete demand paging scheme very difficult, because the page being swapped out to free a frame might belong to another process. It is not possible for processes to munmap() each other's pages in UNIX. In a real system the swapping out is not done by a process anyway, but by the operating system, and the operating system has an overview of all process memory management and can deal with this easily.
Finally, swapping out a page has freed a frame, so look in the pagetable to see which frame the page was using, and put the frame back onto the free frame stack, incrementing the free frame counter appropriately.
At this point you might like to directly test your swapper functions by writing an alternative main() to swap a page in, write some data to it, swap it out, try to access the page (it should fault), swap it in again and see if the data came back. You can also hexdump the floppy device directly to see if the page was written out correctly.
Only two things remain to be done. Firstly, when the swapping in function discovers there are no free frames, it must choose a page to swap out so that a frame is freed. Secondly, it must call the swapping out function with that page.
The simplest way to choose the page is the FIFO page replacement scheme. In this algorithm the page which was the first to be swapped in, of all the pages currently in memory, is the next one to be swapped out when a frame needs to be made available. To know which page this is, we need to keep track of which pages are currently swapped in.
The easiest place to do this is in your mapper function, where you already update the page table. Declare a global array, like the pagetable, which will be used as a queue of pages. The size of this queue should be one less than the number of frames in physical memory, since we keep frame 0 reserved and it should never be used for swapping. Also declare a global index for this array. In your mapper, but only if the page is not 0, write the page just mapped to the current position in the queue, and then increment the index. Don't forget to move the index back to 0 if it runs off the end.
Now when the swapping in function discovers that there are no frames available, swap out the page in the current position in the queue. If physical memory is full, the queue will be too and the index will give the page that was first swapped in. Nothing else should need changing since the swapping out function will put the newly freed frame into the free frame list, so after the swapping out has been done, the swapping in function can continue as if the frame had been free all along. Finally, because the mapper is taking care of updating the queue, the old page which was swapped out will be automatically replaced in the queue by the new page which is swapped in.
This queue, in combination with the pagetable, can be used to discover which frames are currently in use. Now that you have access to this information, rewrite your pagecleaner to go backwards through the queue, freeing up the frames corresponding to those pages, until the free frame counter returns to its maximum.
If everything is working correctly, you should now be able to run your program on a file bigger than physical memory. While running, and especially while sorting, your program will probably swap pages in and out quite often. Floppy disks make very slow swap devices so be patient, but also don't use a file that is too much larger than physical memory or you will be waiting a while. A file which is about 3 pages larger is good.
Test your program with and without the sorting. It is easier to debug the program if it reads in a file and just writes it out again since the output and input can just be compared using cmp, or hexdumped for further detail. To verify that your program with sorting is working, compare its output with the output of this program which will do the same thing without using virtual memory.
To finish off, it is worth seeing for yourself that FIFO is not a good page replacement algorithm. With the current test program its weaknesses are unlikely to be exposed, since reading and writing the data sequentially only accesses each page once, and qsort() has a very friendly pattern of access.
To make life more interesting, replace the call to qsort() with a call to heapsort(), provided here. The arguments are the same, and this sorting algorithm has the same order of time complexity as qsort (n log n). Its pattern of memory access, however, is very different since it is a type of selection sort, and you should start to see pages being swapped out only to be swapped back in again very soon. This is obviously a waste, and would not happen if a different page replacement scheme such as LRU was used.