Assignment 7, due Mar 28

a) Assume that there is only a frame table. At what point (or points) is it necessary to search the frame table, and what system component (hardware or software) is obligated to perform this search. (0.5 points)

Distinguish between indexed access to the table and searching! Virtual addressing can be done by indexing into a page table, but it requires a search of the frame table. With only a frame table, therefore, there must be a search of the table each time an address is translated. This must be done by the memory management unit hardware.

b) Assume that there is only a page table. At what point (or points) is it necessary to search the page table, and what system component (hardware or software) is obligated to perform this search. (0.5 points)

The page fault service routine must search the page table to find the candidate page for replacement whenever there is a page fault.

• frame number - big enough to address all frames of physical memory
• access rights - 3 bits, corresponding to read-write-execute
• spare - 3 bits, available for arbitrary use by software

The frame number and access rights fields are used by the MMU. The MMU has no knowledge of any segment table, although you can assume that the software maintains a frame table.

a) We would like to use this system with the clock page-replacement algorithm. The problem is, the MMU does not have a mechanism to set the mark bit on each page frame (or rather, on the frame-table entry for each page frame) each time it is referenced by a running program. Therefore, we have to use software, specifically the page-fault service routine, to set the mark bit.

Outline the structure of a page-fault service routine that will do this. You may abbreviate the part of the new service routine that does conventional page-fault handling by calling it the conventional page-fault service part of the new routine.

Hint: You don't need to set the mark bit each time a page is referenced, only on the first reference after the mark has been reset. You can use access rights to force a trap even if the page is actually in memory. You can use the spare field in the page-table entry to hold the real access rights for the page, so only if the spare field equals the access-rights field is this page fault a real page fault. (0.5 points)

In general, we use the spare bits to record the real access rights the user has to the page, while we use the access rights to force a trap at the right time. So, "mark bit set" is indicated by having the hardware access rights field equal to the real access rights. "Mark bit not set" is indicated by having the hardware access rights set to "no access".

On page fault, if the hardware access rights of the page in question are no access but the real access rights permit some access, mark the page by making these equal. If, on the other hand, the real and hardware access rights are identical, treat the fault as a real page fault.

b) When the decision is made to replace the page in some frame, we would like to avoid copying that frame back to disk, but the MMU does not have a mechanism to set the dirty bit on each page frame whenever a write to that frame is allowed.

Suggest how your solution to part a) can be modified to also set the dirty bit on a page frame when that frame is first modified. (0.5 points)

The above scheme can be extended to include a dirty bit as follows: Dirty pages are ones where the real and hardware access rights are identical and the page is read-write. Marked pages have hardware access rights that are read or execute only.

On page fault, if the hardware and real access rights to the page are identical, treat it as a real page fault, otherwise if the hardware access rights permit read or execute but not write, but the real access rights include write, mark the page as dirty by setting the hardware access rights equal to the real rights. Finally, if the hardware access rights to the page are no-access, mark the page by giving it the read and execute rights from the real access rights.

Obviously, this virtual address space is larger than either the main memory (probably under a few gigabytes) and far larger than the backing storage (probably disk, and probably under a few terabytes). It is extremely unlikely that the backing storage will be 16 exabytes (giga-gigabytes, the size of the virtual address space).

a) Given that programs use position independent or self-relocating jumps for all internal control transfers, how do you load and run a program on this system? (0.2 points)

Just jump to the starting address, where that address is composed from the 32-bit i-node number of the object file plus the 32-bit address of the starting address local to that file. If we adopt the convention that all object files have their starting address at byte zero, so we just jump to the address given by the i-node number padded on the right with zeros.

b) In theory, a program could manipulate a file by simply referencing memory at an address in the range for that file. Why would users still want to have an open command. (0.2 points)

We need some command that understands the directory structure well enough to compute the i-node number of a file -- which gives its virtual address -- from the name of the file.

c) Suppose a program tries to read from address X in memory. Enumerate and briefly explain the different reasons that this read operation might fail, that is, reasons the page-fault-trap interrupt service routine might have to raise an exception in the application program (one can imagine that each of these reasons might lead to a different exception).

File does not exist -- that is, there is no file associated with the i-node.

Address out of bounds -- the file exists, but the address used was beyond the end of file or corresponds to a location in the file which has not been written.

Insufficient access rights -- file exists, but the current user does not have sufficient access rights to the file.

d) For a 32-bit machine, there is something "magic" about dividing virtual addresses into 12 bits of byte-in-page, 10 bits of page-in-segment, and 10 bits for the segment number. This is because 1024 32-bit page-table or segment-table entries fit perfectly in one 4096-bit page of memory. Give a reasonably natural division for 64-bit virtual addresses, making reasonable assumptions about the page-table-entry size. (Hint, it is not as "magic" as the division of a 32-bit address space.) (0.2 points)

Each page-table or segment-table entry would be 64 bits or 8 bytes. So, if a page contains 2^x page-table entries, then the page size is 2^x+3 bytes.

If we have a 3-level address space (segment, page, byte in page), that means 3x+3 = 64 or 3x = 61 or x = 20.3. It does not come out even, so we have to round up to x = 21 and a page size of 2²⁴. It is a bit on the large size!

If we have a 4-level address space (supersegment, segment, page, byte-in-page) then this means 4x+3 = 64, or 4x = 61, or x = 15.3. Rounding up, this gives us a page size of 2¹⁹ bits, only a bit on the large size, and it still does not come out even.

If we introduce super-super-segments, then we need to solve 5x+3 = 64, or 5x = 61, or x = 12.3. Again, we have to round up, with a page-size of 2¹⁵ bytes. Still not even.

e) What about the user's stack and heap? Suggest how these might look if we unified the concepts of file system and virtual memory. (0.2 points)

The stack could easily be a file. The heap could easily be a file. The state of a process could be stored as a directory containing the stack and heap files of that process.