An operating system supports a paged virtual memory, using a central processor…
2016
An operating system supports a paged virtual memory, using a central processor with a cycle time of one microsecond. It costs an additional one microsecond to access a page other than the current one. Pages have 1000 words, and the paging device is a drum that rotates at 3000 revolutions per minute and transfers one million words per second. Further, one percent of all instructions executed accessed a page other than the current page. The instruction that accessed another page, 80% accessed a page already in memory and when a new page was required, the replaced page was modified 50% of the time. What is the effective access time on this system, assuming that the system is running only one process and the processor is idle during drum transfers ?
- A.
30 microseconds
- B.
34 microseconds
- C.
60 microseconds
- D.
68 microseconds
Attempted by 68 students.
Show answer & explanation
Correct answer: B
Key data: base memory access = 1 microsecond; extra for accessing a different page in memory = 1 microsecond; page size = 1000 words; drum rotates at 3000 rpm (50 rev/s) so average rotational latency = half revolution = 1/(2·50) s = 0.01 s = 10,000 microseconds; transfer rate = 1,000,000 words/s so page transfer time = 1000/1,000,000 s = 0.001 s = 1,000 microseconds.
Read a page from drum = average rotation (10,000 µs) + transfer (1,000 µs) = 11,000 µs.
Write a page to drum (when replaced page is modified) = 11,000 µs (same calculation).
Probabilities:
1% (0.01) of instructions access a page other than the current page.
Of those, 80% (0.80) find the page already in memory (just incur the extra 1 µs).
20% (0.20) cause a page fault and require bringing the page from the drum; of these faults, the replaced page is modified 50% (0.50) of the time and must be written back.
Average page-fault service time:
If replaced page modified: write (11,000 µs) + read (11,000 µs) = 22,000 µs.
If not modified: read only = 11,000 µs.
Average = 0.5·22,000 + 0.5·11,000 = 11,000 + 5,500 = 16,500 µs.
Now compute expected extra time per instruction due to non-current page accesses:
Probability of accessing another page and finding it already in memory = 0.01 × 0.80 = 0.008. Extra cost per such instruction = 1 µs, contribution = 0.008 × 1 = 0.008 µs.
Probability of a page fault = 0.01 × 0.20 = 0.002. Average page-fault service = 16,500 µs, contribution = 0.002 × 16,500 = 33 µs.
Total expected extra = 0.008 + 33 = 33.008 µs. Add base access time 1 µs → effective access time ≈ 34.008 µs ≈ 34 microseconds.