Assignment 8, due Mar. 30
Part of
the homework for 22C:112, Spring 2012
|
On every assignment, write your name legibly as it appears on your University ID and on the class list! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what insurance companies call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the instructor's mailbox. Never push late work under someone's door!
| segment 10 bits | page in seg 10 bits | byte in page 12 bits |
The physical address is organized as follows:
|
frame
20 bits | byte in page 12 bits |
The segment table is exactly 4K 32-bit words, and the page table for each segment is also exactly 4K 32-bit words. These are stored in RAM. The entries in these tables have the following format, with the access rights being vrwx (valid, read, write, execute):
|
frame
20 bits | unused 8 bits | rights 4 |
The operating system keeps a pointer to the segment table in a global varialbe called segtab. The access rights permitted for a page are the logical and of the rights in the segment table entry and the rights in the page table entry. If a segment is marked as invalid, there is no corresponding page table. If a page table entry is marked as invalid, there is no corresponding page.
The MMU has no knowledge of the existence of the segment table, frame table or the structure of the table entries. Instead, the MMU operates in terms of a translation lookaside buffer. Each TLB entry has the following format, with the access rights vrwx as in the page table:
| page 20 bits | unused 8 bits | rights 4 |
|
frame
20 bits | unused 12 bits | |
When there is a page-fault, which is to say, when the MMU finds that there is no entry in the TLB with the requested page field, or when there is such an entry but the rights do not permit the requested operaiton, the hardware forces a page fault trap. Entry to the trap service routine saves the entire state of the user program and turns off the MMU so the system is running with direct addressing of physical memory. On entry to the trap service routine, the following information is available in global varialbes: trapaddress the virtual address that caused the trap, and trapcause an indication of the cause of the trap. The least significant 4 bits of the cause are vrwx, as in the page table, indicating an attempt to use an invalid TLB entry, to read a non-readable page, to write a non-writable page, or to execute from a non-executable page. Exactly one of these bits will be set when there is a TLB entry for the indicated page. None of these bits will be set if no TLB entry is defined for the page.
The trap service routine may update the TLB by calling tlbupdate(e) where e is the 64-bit TLB entry. The TLB will replace some TLB entry, probably one of the less recently used entries, using a policy known only to the hardware designers. On return from the trap service routine, the state of the user program will be restored and the MMU will be turned on.
a) Write a trap service routine that only handles updating the TLB from the segment and page tables. In the event that the page fault results from an attempt to perform an operation that is illegal according to the page table in RAM, your code should call the real_page_fault() service routine. (1.5 points)
b) Suppose the hardware designers decided they wanted to support physical memory with more than 32-bit addresses. Given the details presented above, are there spare bits in the TLB, segment table and page table entries that would allow support for a physical address space larger than 32-bits? What is the upper bound on the number of bits in the physical address, using these bits. (0.5 points)
c) Suppose the hardware designers wanted to leave the MMU turned on at all times during the processing of page faults. To do this, they add one extra bit to the access rights field of the TLB entry, the lock bit L. The TLB will not replace entries marked as locked.
What is the minimum set of TLB entries that must be locked to make this system work. Your answer should be state in terms of the TLB entries for the pages containing X, where X is some set of operating system components, either specific routines or specific data. (0.5 points)
In short, write a heap manager. You should support the following primitives:
void * mymalloc( size_t size ); void myfree( void * ptr );
The semantics of mymalloc() and myfree() are the same as malloc() and free() except that they manage a heap you define yourself. In the event that a request cannot be satisfied by mymalloc() it should return NULL, but it need not set errno, nor should it attempt alternative allocation strategies not involving your heap. (The real malloc() has a value MMAP_THRESHOLD that can drive allocation to use a different mechanism, ignore this!)
The file heaptest.c is a test program designed to exercise your heap implementation. You must limit your changes to the part of heaptest.c that actually allocates the heap and implements the basic heap functions. As provided, the test program merely uses the malloc() to implement mymalloc() and free() to implement myfree(). A skeletal heapinit() routine is provided, but aside from allocating an appropriately aligned block of memory for the heap, it does nothing.
As usual, half of the total grade will be based on cosmetics, while half is based on the correctness and sufficiency of your code. Note that the test load provided by the heap test program deliberately includes demands that exceed the capacity of your heap, so you must handle the "heap full" condition correctly by returning NULL. Also, note that the test program deliberately scribbles on the allocated blocks, and when it deallocates a block, it checks to see if the scribbles are still intact. This makes it highly likely that any errors in the heap implementation will be detected.