Question

Suppose an application is assigned 4 pages of physical memory and the memory is
initially empty. It then references pages in the following sequence:
ACBDBAEFBFAGEFA

a. Show how the system would fault pages into the four frames of physical
memory, using the LRU replacement policy.

b. Show how the system would fault pages into the four frames of physical
memory, using the MIN replacement policy.

c. Show how the system would fault pages into the four frames of physical
memory, using the clock replacement policy.

Answer 1

a)

LRU replacement policy with 4 frames of physical memory.

A

C

B

D

B

A

E

F

B

F

A

G

E

F

A

1

A

hit

hit

hit

2

C

E

G

3

B

hit

hit

E

4

D

F

hit

hit

b)

MIN replacement policy with 4 frames of physical memory.

A

C

B

D

B

A

E

F

B

F

A

G

E

F

A

1

A

hit

hit

hit

2

C

E

hit

3

B

hit

hit

G

4

D

F

hit

hit

c)

CLK replacement policy with 4 frames of physical memory.

	A	C	B	D	B	A	E	F	B	F	A	G	E	F	A
1	A 1	1	1	1	1	hit 1	E 1	1	1	1	1	0	hit 1	1	1
2		C 1	1	1	1	1	0	F 1	1	hit 1	1	0	0	hit 1	1
3			B 1	1	hit 1	1	0	0	hit 1	1	0	G 1	1	1	1
4				D 1	1	1	0	0	0	0	A 1	1	1	1	hit 1

hit= cache hit

1/0 means the state of the "used " bit at the end of specified step

bold italics is the position of the clock hand at the end of the specified step(this is what it will be looked at first the next time the clock hand moves)