Homework 4 Solutions

22C:116, Fall 1997

Douglas W. Jones

Background Consider the following MMU interface:

The MMU has Stlb registers, named tlb[0] to tlb[Stlb]. Each register has the following format:
```
         ____________ _____________ ________
        |____________|_____________|________|
        | pagenumber | framenumber | rights |
```
The pagenumber and framenumber fields are fields of the virtual and physical address, respectively. the rights field may have values of either no-access, read-only or read-write.
1. An appropriate data structure for the virtual address map (page table) and frame table:
  The frame table would be indexed by frame number, and it would have an entry for each frame in main memory. Each frame table entry would contain the following:
```
         ____________ ______ _______ __________
        |____________|______|_______|__________|
        | pagenumber | mark | dirty | tlb_slot |
```
  The page table would be indexed by the page number, and it would contain an entry for each page in the virtual address space. Each entry would have the following information:
```
         _____________ ________
        |_____________|________|
        | framenumber | rights |
```
  In addition, clock replacement will require a clock hand, a variable that indexes into the frame table.
2. Given the above, the page fault handler would look something like the following:
```
page_fault_handler:
	va = virtual address that caused fault
	f = page_table[va].frame_number
	if f invalid
		replace_page
	else
		soft_fault

soft_fault
	/* assert page_table[va].rights > no_access */
	t = frame_table[f].tlb_slot
	if t invalid
		/* tlb soft page fault */
		/* here, we assume random tlb entry replacement */
		t = random tlb entry
		f' = tlb[t].frame_number
		frame_table[f'].tlb_slot = invalid
		frame_table[f].tlb_slot = t
		tlb[t].page_number = va
		tlb[t].frame_number = f
		tlb[t].rights = read_only
		set frame_table[f].mark
	elseif not frame_table[f].mark
		set frame_table[f].mark
		tlb[t].rights = read_only
	elseif not frame_table[f].dirty
		/* note:  faults with mark bit set
		   result from writing read_only pages! */
		if page_table[va].rights not read_write
			treat this as a bus trap error
		else
			set frame_table[f].dirty
			tlb[t].rights = read_write
		endif
	endif

replace_page
	while frame_table[clock_hand].marked
		if frame_table[clock_hand].dirty
			write frame f to disk_address(va)
			reset frame_table[clock_hand].dirty
			t = frame_table[f].tlb_slot
			if t valid
				tlb[t].rights = read_only
			endif
		else
			reset frame_table[clock_hand].marked
			t = frame_table[f].tlb_slot
			if t valid
				tlb[t].rights = no_access
			endif
		endif
		clock_hand = (clock_hand + 1) mod frames
	endloop

	/* assert frame_table[clock_hand] is clean! */
			
	f = clock_hand

	read disk_address(va) into frame f

	page_table[va].frame_number = f
	frame_table[f].page_number = va
	reset frame_table[f].dirty
	reset frame_table[f].marked 
	frame_table[f].tlb_slot = invalid
	/* it'll take a soft fault to validate this! */
```
3. If the virtual address map was so large that it was not practical to fit it entirely in main memory, I would:
  - Only store entries with non-invalid access rights, for example, by using something akin to run-length encoding or segmenting, with the length field of each segment giving the number of valid pages in that segment (where pages in each segment must be allocated consecutively from the start).
  - Write the page-fault handler to be recursive -- that is, allow a page fault within the page fault handler, and then store the page table in virtual memory. This requires that certain pages in memory be guaranteed never to be replaced. Those pages would be locked in memory by adding a new bit, the lock bit, to the frame table entries for those pages. The page holding the part of the virtual address map that describes the locations of the pages holding the entire map must be locked in memory!
  - Equivalently to the above, the map could be organized as a paged-segmented map, with the segment table locked in main memory and using segment faults to bring page table segments into memory.
4. If the system has multiple processes, so one process can run while disk I/O for page faults of another process take place, the following changes must be made to the above design:
  The block of code in the above that starts with reading from disk_address(va) into frame f must instead schedule the read request and block the process that had the page fault. The page fault handler would then return from the fault by scheduling a new ready process, and the remaining changes to the map would be done by the disk handler on completion of the read operation for the page. The disk handler would then unblock the process that had caused the page fault, allowing it to be scheduled and run.
  The code to clean pages in the map must be changed so that it schedules the write operations. The state of the frame would be changed from dirty to "being written" when the write is scheduled. The disk handler would change the state to "clean" but only if it was still marked as "being written" when the I/O completes. If another write takes place to the frame while it is marked "being written", the soft page fault routine would change the state back to dirty, preventing the disk handler from marking the frame as clean.