The aim of this lab is to implement a basic paging scheme using a page table, and to see mapping of virtual addresses to physical addresses taking place. Since only the superuser in UNIX has access to the physical address space, a file will be used to simulate physical memory. Portions of this file will be mapped into a process's address space and UNIX's support of this mapping will simulate the mapping normally done by MMU hardware for an operating system.
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 lab is divided into sections, and these sections do not always build on each other. You are required to keep your solution from every section so your demonstrator can mark it.
You must complete this lab to pass it.
You cannot use any memory allocating functions in this lab. The lab might not work if you do so. Functions that do memory allocation include malloc(), strdup(), calloc(), realloc(). There is one exception, alloca(), that is acceptable to use since it allocates memory on the stack.
Every process in UNIX has a virtual address space. In this lab we will make use of the same virtual address space that UNIX does so that any normal programs can operate with the addresses we set up. This is also close to the real situation because the hardware does the mapping from the virtual address space to physical memory anyway, not UNIX.
Much of the virtual address space is private for a process. To see this, write a simple program that declares a global char and prints out its address in hexadecimal. The char must be global so it is not allocated on the stack (this is explained further below). After printing out the address make the program wait for some input so it does not terminate immediately.
Run the program once and, without terminating this first run, run it again. You should see the same address given for the variable, but you know this variable is not shared between the two processes running the program.
Change your program so that it reads a character from input and assigns it to the variable before waiting for input again (you will need to clear the newline from the first input from the buffer). After this pause for input, output the value of the variable.
Run the program in two different windows and give two different characters. After entering both characters, allow both runs of the program to continue so that you see them output the correct characters.
Since both processes have the same address for the variable, the only way this can be working is if the address is not real (it is virtual) and if the address is being translated to a different part of physical memory for each process.
Despite the fact that all the addresses available to the process are virtual, we cannot choose just any range of addresses to use for our own memory management. Firstly, not all addresses are private. Secondly, some addresses are already in use.
The addresses that a process makes use of are mapped to real storage and accessing these locations accesses this storage. These mapped regions are the segments of a process as viewed by UNIX. Accessing an address which is outside any of these regions is a segmentation fault (or segmentation violation) because that address would not map to any real storage. As such, we will know we have found an unused address when it causes a segmentation fault.
Simple processes in UNIX have three segments: the stack segment, text segment (for the program instructions), and data segment. Addresses next to the data segment are most appropriate for what we want. The old way in UNIX of allocating more memory for a process used to be to shift the `break' of the data segment, i.e. the end of it, with the function sbrk(). The same function, with an argument of 0, can be used to discover where that end is. Do this, and print out the address in hexadecimal.
Try to read from a location which is one address beyond the end of the data segment. If you like, you can print out the data from that location. You must use a char pointer to be able to move one address at a time. Adding 1 to any other kind of pointer will change the address by the size of the type being pointed to (e.g. it will probably add 4 for an int pointer). You should continue to use a char pointer for all pointer arithmetic in this lab.
It is extremely likely this access will not cause a segfault, even though it should have. Since our aim is to get such a segfault, write a loop which each time increments the address being accessed and accesses it again. The loop can be infinite since the program will eventually terminate with a segfault.
Compile your program with debugging information. Load your program into gdb, and run it from inside gdb. After it crashes, print out the value of the address that caused the segmentation fault. Note that it is some distance beyond the data segment break.
The reason why no segfault happened initially is that UNIX uses paging. This means that when it allocates memory, it allocates it in pages, and nothing less. Even though sbrk() is the traditional way of allocating more memory, the way it is done in modern, paged, UNIX is that the segment break is recorded, but no more memory is allocated unless it is pushed beyond the end of the last page. When it does go off the end, a new page is allocated, so no matter how small the increase in the segment break, a whole page's worth of virtual addresses will now map to some memory.
The overall result of this is that the `true' end of the data segment will be the value returned by sbrk(), rounded up to the nearest multiple of the page size.
Write a new program which calculates this address. The page size for the system can be found using the function getpagesize(). To test that your programs arrives at the correct address, try accessing a location one below it. This should work, as it is the last address of the last page. Then try accessing the calculated address, which should not work since it is the first unmapped address after the data segment.
Memory mapping is done with the function mmap() which, amongst other things, allows a portion of a file to be accessed as if it were a piece of memory. Using this, we can have a file pretend to be physical memory and allocate memory to a process by mapping portions of that file. Since mmap() is also used for real memory allocation this is a very good representation of the way UNIX does memory management.
For this to work we must create our physical memory at least
once. The file will be reused and so needing to recreate it is not
likely. In a paged system, which is what we will be writing, physical
memory is divided up into frames that are the same size as pages. As
mmap() is for use with real memory, it works with UNIX pages, and so
the filesize needs to be a multiple of UNIX's page size. To create a
file with n blocks of size f do
dd
if=/dev/zero of=yourfile bs=f count=n
where f should
be the framesize (UNIX's pagesize). The file will initially be filled
with zeroes (the byte value, not the character).
Using mmap(), map some of the file to the unmapped virtual address calculated earlier. You will need a flag to force mmap() to use the address you specify. Since physical memory is, in reality, shared by everything in the computer, you will need another flag to indicate that these mappings are shared (the way memory is kept from some processes is by not mapping it). The protection should be read and write since this memory will be used for data, and the size should be one page since in a paged system memory is always allocated one page at time. The offset into the file doesn't matter for the moment, but zero is the easiest.
When calling mmap(), check to make sure that it succeeded. You may like to double check that the address of the mapping matches what you asked for, although if you gave the right flags mmap() should fail if it can't use the address you specified. Since you needed to open() the file to do the mapping you should close() it immediately after the mapping is done. Mapped files do not need to be kept open.
To test the mapping, write some data into addresses that were previously causing segfaults, i.e. the first unused address and above, which is our first page. If the mapping is working and the flags are correct, not only should the accesses no longer segfault, but the written data should appear in the file in the corresponding locations, which is the frame in physical memory. Since the file could easily end up with binary data in it, you may like to view it using the hexdump command, particularly with the option for canonical display.
The main advantage of a paged system is that it can allocate frames from anywhere in memory but that this variety of locations will look like one contiguous block to the process. Using mmap(), we already have the ability to do something like this, but since we will be doing it a lot it is worth writing a special function for the mapping.
The function should take two arguments, one of them being a page number and the other a frame number. When it is called it will attempt to map the requested frame from `physical' memory (which will be some offset into the file) into the requested page, where page 0 is considered the first page after the calculated segment break. It is easiest to treat a failure of mmap() as fatal, so if it fails simply output the error and exit. If it succeeds, return the address of the newly mapped page.
The main() of your program should now be empty, with the mapping being done in this function. To test your function, call it twice, mapping two frames which are not next to each other into two pages which are. Then, starting from the first address of the first page, write some data into all the locations up to the last address of the second page. This should be done in one loop, and that loop should not care where the break between the two pages is.
Have a look in the memory file (using hexdump) to see that the data you wrote went into two separate regions. If it's not clear, you may like to run your program again after having regenerated the memory file to fill it with zeroes, as hexdump skips zeroes. You should see that the break between the two regions was invisible to your program as a result of the mappings you set up.
The usual way programs allocate memory is to ask for a certain amount of it. To keep things simple, we will write an allocator that allocates a number of pages.
Declare a global array which will keep track of the frames that have been been mapped to each page. The array is a pagetable, and the index to the array is a page number. In your mapping function, after the mmap() has been successfully performed, record the mapping by assigning the frame number that was requested to the pagetable, indexed with the page number that was requested.
You should test this addition to your program by adding a printout of the page table in main().
Since the allocator is only going to be told the number of pages to be allocated, it must decide which pages to map to itself. To do this, declare a global variable to keep track of the number of pages already mapped, and inititalise the variable to zero. (The initialisation is not strictly necessary, since global variables are static and will initialise to zero anyway, but it's good practice and the initialisation will be changed later.)
Write a new function which takes as its only argument the number of pages. In it put a loop which calls your mapping function, choosing the current value of the page counter as the page to mapped, and then incrementing the page counter. For the moment, allocate frames starting from zero and using as many as necessary.
Your function should return the starting address of the first page that was allocated.
Test this by removing the calls to your mapping function from main() and replacing it with a call to this new allocator, requesting two pages. Have your program again write data from the starting address and onwards for two pages worth, but also print out the page table and this new counter. You should be able to tell from the pagetable whether the new function has worked.
Keeping a page count and pagetable is easy because they are both unique to each process. Choosing frames, on the other hand, depends on identifying which frames are free, and this is information which must be shared among all the processes.
To do this, we will reserve frame 0 in physical memory to keep track of free frames, and reserve page 0 in every process to have frame 0 mapped onto it.
Change the initialisation of the page counter to 1, to reflect the fact that one page, page 0, is always in use. At the start of your allocator function, map frame 0 to page 0 using your mapping function. You do not need to worry about calling your allocator twice and remapping this because mmap() does not complain about remapping.
The start of frame 0 will be used to keep a count of free frames, so assign the address returned by the mapping to an int pointer.
Memory is basically and array, and so the easiest way to keep track of the free frames will be with an array. The array will be changing in size, however, and since moving the end of an array is much easier than moving the start, we will use a stack to store the free frames. Use another int pointer to point to this array, and assign to it 1 plus the address of the frame counter, so that this array is located just after the counter.
In your page allocator, check at the start to see whether there are enough frames to satisfy the number of pages that were asked for. If not, print out an error and exit.
If there are enough frames, change the loop which calls your mapper to pop a frame off the free frame stack and use that as the next frame to map. To get this value, use the free frame counter as an index to the stack-array, and then decrement the free frame counter (which effectively pops the value).
Unfortunately this cannot be tested immediately since it depends on a free frame counter and stack being present in memory. To set this up, write a separate program to initialise the memory and have it write the number of free frames in the first location of the file and a list of free frames in the locations after, which is the stack. The easiest way to achieve this is to use the mapper function you've already written, and assign to int pointers as you are doing in the allocator. Don't forget that since frame 0 is now reserved, the number of free frames will be one less than the number of frames in the file, and the list of free frames will start at 1.
Test all of this by calling your allocator with a request for two pages, and writing two pages worth of data. You should examine the memory file with hexdump to see that the writes were successful and that the data structure maintaining the free frames was correctly updated. If you run your program a few times, you should see that it will consume frames and then terminate without releasing them. Running it enough times would use up all of memory.
Write a small clean up function which returns the frames in the pagetable to the free frame stack. Remember to only return the frames mapped to pages 1 and up since frame 0 has been mapped to page 0 and that must remain reserved.
Test this by calling it just before your program finishes. If you now reinitialise memory and run your program you should end up with just as many free frames as you started with (look in the file itself). It is possible that cleanup will return frames to the stack in a different order than they were taken off, but that does not matter at all since a paged system deals perfectly with jumbled blocks of physical memory. All that matters is that the right frames are in the stack.
Add a little bit of debugging information to your mapping function that outputs, if the frame is not frame 0, the number of the frame that was just mapped.
Write a new main() that prompts the user for the number of pages to allocate, allocates them, and then waits for the user to press return before cleaning up and exiting. When you run this you should be able to see which frames were allocated in response to your request.
In one window, run the program and allocate less than half of your available memory. In another window, do the same. Return to the first window, and press return to allow the first process to cleanup and exit. The situation now is that the second process is holding some frames in the middle of physical memory, and this has broken up the free memory into two blocks. This is external fragmentation.
Leaving this second process holding the memory, run your program again in the first window and request more memory than you did the very first time. The frames allocated in response to your request should `jump around' the block being held by the second process.
Even though the frames allocated might be from different places in memory, the mapping into the virtual address space means that anything using the address returned by your page allocator does not need to worry about that. In this way a paged system copes very easily with external fragmentation.