Assignment 8, due Mar. 23

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!

1. Background: If you solve MP4, mush still lacks some useful features. Among them, it has no support for while loops. Consider this syntax for while loops in mush:

   while command
      echo this is in the loop body
   endloop
   

   This requires two new built-in commands, while and endloop. The while command interprets its arguments as a shell command and launches that command. If the launched command exits with EXIT_SUCCESS the shell continues executing successive commands of the loop body. If the launched command exits with EXIT_FAILURE, the shell skips over the loop body and the endloop before resuming normal execution. If the shell encounters endloop during normal execution, it skips back to the previous while command.

   In many cases, the launched command would be the test command. If you're curious, you can look at its man page.

   Note: This assignment does not ask you to actually implement anything, it only asks you to think about how to implement it.

   a) Explain how ftell() and fseek() could play a role in the implementation of while and endloop. Ignore the possibility of nested loops in this part of the problem. (0.5 points)

   b) How would your answer to part a change if you allowed nested loops. a user can observe. (0.5 points)

2. Background: Assume your computer offers the standard Unix gettimeofday() kernel call.

   a) How could you use this system call to instrument part of your program, for example, the assignment statement i=j+1 to see whether it causes a page fault? (0.4 points)

   b) Can the instrumentation you proposed in part a) distinguish between page faults caused by instruction fetches and page faults caused by data references? Explain. (0.3 points)

   c) To what extent does the instrumentation you introduced to solve part a create the possibility of additional page faults? (0.3 points)

3. Background: Performance of demand-paged virtual memory can be improved by having the MMU note whenever the CPU writes to a frame by setting the dirty bit on that frame. If a frame is "clean", that is, never written since the last time a page was copied into that frame from disk, there is no need to write that page back to disk when the time comes to replace that page. Only "dirty" pages need to be written back to disk.

   The normal clock replacement algorithm has a mark bit used to record whether a frame has been touched by the CPU since the last time the clock-hand swept by. The easiest variant on the clock algorithm that uses the dirty bit operates just like the original clock algorithm to find a frame to replace, and then it inspects the dirty bit on the frame to see if it is necessary to copy that page back to disk before replacing it. Frames holding pages freshly brought in from disk are always marked as clean.

   An alternative (and much more interesting) scheme is to have the following rule: When the clock hand passes a dirty frame, it schedules it for cleaning. That is, it schedules a write request for that frame in the disk queue. Only when the write is completed does the page in that frame become a candidate for replacement. The search for a frame to replace only terminates when a clean unmarked page is found. Here are the states of a page frame in this scheme:

   • clean-unmarked
   • clean-marked
   • dirty-marked
   • write-scheduled
   • write-in-progress

   A Question: Identify all of the state transitions that can occur in this system, and for each state transition, indicate what causes it, that is, what activity of the CPU, the page-fault service routine, or the disk-interrupt service routine causes the markings on the frame to change. Do not forget the possibility that the CPU might touch a frame while that frame is in the disk queue or while the disk hardware is in mid write. (1.0 points)