CS414 Homework 4.  Due in class on Thursday November 15.

 

1.      Consider the page reference string shown below.  Assuming that Δ=3 (for the demand paging algorithms, Δ is the memory size; for working set algorithms Δ is the working set window size), fill in the table for the (a) LRU and the (b) WS algorithms.   Time starts at 0 and we’ve filled in the first three entries to “warm start” the algorithms.

 

(a) LRU

R(t)

1

2

5

3

2

6

3

1

5

3

2

5

3

1

4

1

5

4

5

4

5

4

3

S(t)

1

1
2

1
2
5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

In(t)

1

2

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Out(t)

Ø

Ø

Ø

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(b) WS

R(t)

1

2

5

3

2

6

3

1

5

3

2

5

3

1

4

1

5

4

5

4

5

4

3

S(t)

1

1
2

1
2
5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

In(t)

1

2

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Out(t)

Ø

Ø

Ø

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. For each of the two algorithms, compute the hit ratio starting from time t = 3 (i.e. skipping the part that we filled in for you).

 

 

 

 


 

2.      Suppose LRU was used to page a mapped file k pages long, which your program scans twice, from start to end sequentially.  Thus the application visits pages 0, 1, … k-1 of the file, then revisits pages 0, 1, … k-1.  For simplicity assume that this is the only paged segment and that the paging algorithm is configured to use Δ frames of memory.

a.       If Δ ≥ k, what hit rate will we obtain using LRU?

 

 

 

 

b.      If Δ < k, what hit rate will we obtain using LRU?

 

 

 

 

c.       Would Denning’s WS algorithm give a different result for 2.a and 2.b using the same values of Δ, but where Δ is now the working set window size?  Explain briefly.

 

 

 

 

 

 

 

 

 

 

3.      Modern computers tend to have a lot of memory – for example, a gigabyte of main memory will probably be common within a few years, and this is enough to hold a million 1-kbyte pages.  Very few programs are this large.  You’re being interviewed by Microsoft’s operating systems group and they want to know your opinions on virtual memory in this new world.

a.       Give a simple argument for eliminating virtual memory – a few lines long[1].

 

 

 

 

 

 

 

 

 

 

 

b.      Give a simple argument for keeping virtual memory – again a few lines long.

 

 



[1] Hint: your answer should focus on the main issues – the strongest pro and con you can come up with.