• retagged by
161 views
4 4 votes

A demand-paging system has $3$ physical page frames.

Consider the reference string:

$\text{A, B, C, D, B, A, B, A, D, C}$

Starting with empty memory, determine the total number of page faults using:

  1. FIFO
     
  2. Clock
     
  3. LRU

For the Clock algorithm, when a page fault occurs, the clock hand advances before performing checks or actions, as specified in the original exam.

Which tuple is correct?

  1. $(7, 6, 6)$
     
  2. $(6, 7, 6)$
     
  3. $(7, 7, 6)$
     
  4. $(6, 6, 7)$

1 Answer

0 0 votes

For FIFO:

  • $\text{A}$: fault

  • $\text{B}$: fault

  • $\text{C}$: fault

  • $\text{D}$: fault, replaces $\text{A}$

  • $\text{B}$: hit

  • $\text{A}$: fault, replaces $\text{B}$

  • $\text{B}$: fault, replaces $\text{C}$

  • $\text{A}$: hit

  • $\text{D}$: hit

  • $\text{C}$: fault, replaces $\text{D}$

FIFO page faults = $7$.

For Clock, initially $\text{A}$, $\text{B}$ and $\text{C}$ are loaded, giving $3$ faults.

When $\text{D}$ arrives, all three reference bits are $1$. 

Since the clock hand advances before checking, it moves through the pages, clears their reference bits, and eventually replaces $\text{A}$ with $\text{D}$.

Faults so far = $4$.

Next, $\text{B}$ is a hit, so its reference bit becomes $1$.

When $\text{A}$ is referenced, it is not present. 

The clock advances, clears $\text{B}$'s reference bit, and replaces $\text{C}$, whose reference bit is $0$.

Faults so far = $5$.

The next references $\text{B}$, $\text{A}$ and $\text{D}$ are all hits.

Finally, $\text{C}$ is absent, producing one more fault.

Clock page faults = $6$.

For LRU:

  • $\text{A}$: fault

  • $\text{B}$: fault

  • $\text{C}$: fault

  • $\text{D}$: fault, replaces $\text{A}$

  • $\text{B}$: hit

  • $\text{A}$: fault, replaces $\text{C}$

  • $\text{B}$: hit

  • $\text{A}$: hit

  • $\text{D}$: hit

  • $\text{C}$: fault, replaces $\text{B}$

LRU page faults = $6$.

So, the correct tuple is $(7, 6, 6)$.


Answer : A

Answer:
Position:
Show:

Related questions

2 2 votes
1 1 answer
4.6k
4.6k views
jhaanuj2108 asked Aug 14, 2018
4,599 views
Consider a demand paged memory system, page table is held in registers. It takes 800 nsec to service a page fault if empty page is available or replaced page is not modif...
1 1 vote
0 0 answers
556
556 views
Reetu Chaudhary asked May 6, 2024
556 views
For a certain page trace starting with no page in the memory, a demand-paged memory system operated under the LRU replacement policy results in 9 and 11 page faults when ...
4 4 votes
1 1 answer
131
131 views
GO Classes asked Aug 26
131 views
An underwater vehicle takes one photograph every minute during a $\textbf{1}$-hour mission.Each photograph is stored as a separate file of size $5$ kBAfter the mission, a...
2 2 votes
1 1 answer
169
169 views
GO Classes asked Aug 26
169 views
Consider an integer semaphore $\texttt{S}$.Method $\textbf{1}$wait(S): disable interrupts while S <= 0: do nothing S = S - 1 enable interrupts signal(S): disable interrup...