Assignment 9, due Nov. 1Solutions
Part of
the homework for 22C:112, Fall 2013
|
On all assignments, your name must be legible as it appears on your University ID card! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what lawyers call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the teaching assistant's mailbox. Never push late work under someone's door!
|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| | segment | page in segment | byte in page |
In this case, the MMU has no support for a mark bit or a dirty bit, and in fact, not even a valid bit. Page-table entries have the following format (in binary):
|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| | frame number | unused |R W X| R - read permission bit W - write permission bit X - execute permission bit
The unused bits in each page-table entry are ignored by the MMU but may be used by software for any purpose.
a) Give the physical address format. (0.4 points)
._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _| |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| | frame number | byte in page |
Some students had difficulty wrapping their minds around the idea that the physical address could be bigger than the word size of the machine. This is actually quite common. The Intel 8088, the processor used for the original IBM PC, had a 20 bit virtual address with a 16-bit word. Any modern 32-bit PC with more than 4 gigabytes of memory is in the same category. The first MMU offered for the classic DEC PDP-11 allowed an 18-bit virtual address, yet the -11 had only a 16-bit word.
b) How many gigabytes of RAM can be attached to this computer? (0.4 points)
64 gigabytes.
void MMUtraphandler() {
/* assume entire CPU state has been saved */
intptr_t va = get_virtual_address_from_mmu();
intptr_t op = get_memory_operation_from_mmu();
/* va is the address that caused the trap */
/* op is the memory operation (rwx) that caused the trap */
uint32_t page = va >> 12;
uint32_t frame = pagetable[ page ] >> 8;
uint32_t rights = pagetable[ page ] & 0xFF;
uint32_t hardr = rights & 7;
uint32_t realr = (rights >> 3) & 7;
uint32_t ondisk = rights >> 6;
if ((op & realr) == 0) {
throw_user_exception_in_saved_state( op );
} else if (ondisk) {
frame = handle_page_fault( page );
ondisk = 0;
hardr = realr & op;
} else {
hardr = hardr | (realr & op);
}
pagetable[ page ] == (frame << 8)
| (ondisk << 6)
| (realr << 3)
| (hardr );
/* assume entire CPU state will be restored */
}
a) Give the layout of the rights field of a page table entry, showing the interpretation, if any, of each of the 8 bits. Keep it brief -- for example, use the access rights r, w and x, with the qualifiers real and hardware, and do not use English sentences. (0.4 points)
|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|_ _ _ _._ _ _ _|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
| frame number | |O|R W X|R W X|
|D|realr|hardr|
R - read permission bit
W - write permission bit
X - execute permission bit
OD - on-disk, a boolean
This follows from what was given in the hardware description, plus what we can learn from the packing and unpacking of the rights field in the given code. The fact that the OD or ondisk field is just one bit can be inferred from its use as a Boolean value to control an if statement.
b) Which combinations of access rights correspond to unmarked pages, that is which combinations indicate that the page is in RAM but has not been recently used. (0.4 points)
(realr != 0) && (!ondisk) && (hardr == 0)
The cascade of else clauses in the if statement helps here; realr gives the real access rights -- since if the user's operation is not included in the real rights, the trap handler throws an exception to the user.
If the page is marked as on disk, it is a real page fault, so marking is not relevant.
If it is not on disk and the operation is really permitted, we mark the page by moving the access right that was used from the real access rights to the hardware access rights field.
c) Give the appropriate code to apply to the rights field of a page table entry to clear the marked-state of that page when the clock hand sweeps by the frame holding that page. (Don't bother packing or unpacking the fields of the page-table entry, since the code for that can be swiped from the code given above and is therefore trivial. The correct answer is just one line of code!) (0.4 points)
hardr = 0;
d) Which combinations of access rights correspond to clean pages, that is, pages that, if replaced, need not be copied back to disk. (0.4 points)
(realr != 0) && (!ondisk) && ((hardr & w) != 0)
The logic for this closely parallels tht for part b). The first two terms of this should never need to be checked since we only care about marking and dirty bits for pages that are not on disk.
Look up the mmap() system call on Linux.
A problem: The easiest way to support MMAP would be to enlarge each page table entry to contain more data. Following this lead, what are the obvious fields to add to each page table entry to make MMAP work. (0.6 points)
Add a field to each page-table entry giving the sector number of that page on disk. When mmap() is called, it finds the disk addresses of all sectors in the mapped part of the file and fills those addresses into the mapped part of the address space, marking those page pages as being currently on disk.