A execution walk-through.


R. Clayton (rclayton@monmouth.edu)
Mon, 13 Nov 2000 20:16:10 -0500 (EST)


To illustrate the kinds of execution behavior you can expect when running under
virtual memory, this message walks through a run of my implementation of the
third assignment as it executes the pa1-nosleep batch disk under virtual
memory.

The pa1-nosleep batch disk contains four programs of size 4, 3, 2, and 1 blocks
(or pages). The processes don't do anything but no-op and exit.

The f28 debug-print flag prints information about process execution; the f30
debug-print flag prints information about paging activity. Both of these are
implemented in my os, not in the simulator.

  cl pa3os -Df28,f30,disk-io -d /export/opt/cs-438-505/devices/pa1-nosleep.dsk

The idle process, process 0, runs until the program-index block lands in user
space. Then all the process on disk are hung on the ready queue. After all
programs are loaded, the scheduler switches the idle process for the first
process.

  At time 0, process 0 runs.
  At time 10, the disk read from block 0 to location 1024 ends.
  At time 10, process 1 runs.

Process 1 throws an immediate page fault because none of its pages are in user
space. Address 3072, contained on page 0, is the first address in virtual
process address space. Page 0 lands in the first page frame in user space,
although it may appear in any page frame in user space. Process 1 gets swapped
out while its page is in transit and process 4 is brought in for execution.

  At time 11, page in 0 to 1024 for address 3072 in process 1.
  At time 11, process 4 runs.

Process 4 also throws an immediate page fault because none of its pages are in
user space either. A page in for process 4 is scheduled, and process 4 gets
bounced in favor of process 3, which throws... Eventually all the user
processes are waiting for their first page and the idle process steps back in
for execution.

  At time 12, page in 0 to 1056 for address 3072 in process 4.
  At time 12, process 3 runs.
  At time 13, page in 0 to 1088 for address 3072 in process 3.
  At time 13, process 2 runs.
  At time 14, page in 0 to 1120 for address 3072 in process 2.
  At time 14, process 0 runs.

Finally, process 1's page lands in user space and it can start execution.
However, it soon runs off the end of its page, causing another page fault, this
time for the second page. While process 1 is executing, the first pages for
processes 3 and 4 land in user space.

  At time 22, the disk read from block 1 to location 1024 ends.
  At time 22, process 1 runs.
  At time 41, the disk read from block 10 to location 1056 ends.
  At time 53, the disk read from block 8 to location 1088 ends.
  At time 57, page in 1 to 1152 for address 3104 in process 1.

Process 1 abandons the cpu to wait for its second page, and process 4 resumes
execution. Process 4 is only one block long, so it exits during its execution.
Process 3 is brought in to execute and throws a page fault when it runs past
the end of its first block. The page for process 3 will eventually end up in
the same page frame that held process 4's page; this is a decision made by the
software managing the page table. While process 3 was executing, the pages for
processes 2 and 1 land in user space.

  At time 57, process 4 runs.
  At time 59, process 4 exits.
  At time 59, process 3 runs.
  At time 66, the disk read from block 5 to location 1120 ends.
  At time 79, the disk read from block 2 to location 1152 ends.
  At time 94, page in 1 to 1056 for address 3104 in process 3.

Process 2 executes and also throws a page fault for its second block. Process
3 replaces process 2, and, being only two blocks long, exits. During all this,
the pages for processes 3 and 2 show up.

  At time 94, process 2 runs.
  At time 111, the disk read from block 9 to location 1056 ends.
  At time 128, page in 1 to 1184 for address 3104 in process 2.
  At time 128, process 3 runs.
  At time 141, the disk read from block 6 to location 1184 ends.
  At time 155, process 3 exits.

Its page availabe, process 2 resumes execution, until it runs off the end of
the second page and throws a page fault for its third page. Process 1
continues execution in process 2's place.

  At time 155, process 2 runs.
  At time 188, page in 2 to 1056 for address 3136 in process 2.
  At time 188, process 1 runs.
  At time 199, the disk read from block 7 to location 1056 ends.

Process 1 runs off the end of its second page, throwing a page fault for its
third page. Process 2's third page is, by now, in user space, and process 2
continues execution.

  At time 222, page in 2 to 1088 for address 3136 in process 1.
  At time 222, process 2 runs.

Process 2 has three pages, so it exits during its execution. Process 1's page
hasn't shown up yet, so the idle process takes over. Eventually the page
arrives and process 1 resumes execution, only to run off the end of the page
and set off a page fault for its fourth and final page. The idle process takes
over again.

  At time 228, process 2 exits.
  At time 228, process 0 runs.
  At time 236, the disk read from block 3 to location 1088 ends.
  At time 236, process 1 runs.
  At time 269, page in 3 to 1056 for address 3168 in process 1.
  At time 269, process 0 runs.

The fourth page shows up, process 1 resumes, and exits. The idle process runs,
and, with no user processes to execute, the system halts.

  At time 280, the disk read from block 4 to location 1056 ends.
  At time 280, process 1 runs.
  At time 296, process 1 exits.
  At time 296, process 0 runs.

  The system is halted.
  Total execution time: 296 ticks, idle time: 33 ticks (11%).

Keep in mind that this is an example; I neither expect nor want your assignment
to exactly mimic the sequence of events shown here.



This archive was generated by hypermail 2.0b3 on Mon Dec 18 2000 - 13:30:06 EST