We can use some simple notations to address the 16 virtual pages on the left each of 4K (from 0 until 64K) as V0, V1, V2, .., till V15 and the 8 physical pages on the right each of 4K also (from 0 to 32K) as P0, P1, till P7.

So what happens in the figure here is: V3 from 12K to 16K is referenced first, so it is loaded into physical memory 0-4K or P0, then V1 from 4K-8K is referenced and put into P1, then V0 referenced and put into P2.

In summary, we have a sequence of 8 page references in the virtual memory (hard drive) in this sequence: V3, V1, V0, V5, V4, V9, V2, and V11, mapped to P0, p1, P2, .., P6, and P7 respectively. Now if we reference virtual pages in the first 8 virtual pages later on, these 8 pages will stay instact as physical pages there. However, if we reference some virtual pages not in the original sequence, then some page has to be swapped out called page out.

Suppose we use the simple mind page replacement algorithm listed in slide 20 of chapter 3 of Tanebuam, the FIFO or first in, first out algorithm.

Now consider the next 4 virtual page references: V5, V3, V7, V6. V5 corresponds to P3 and V3 corresponds to P0. These virtual pages are already in physcial memory, so nothing happens.

V7 in the sequence means we refer to virtual memory 28K to 32K, which is not in physical memory. So some virtual page must be swapped out. Since V3 mapped to P0 is the first physical page in, it must be out as the first page. So now we have V7 mapped to P0 (and V3 shows as X now).5, V1

Next, we have V6 which is not in physical memory either. So V1 corresponding to P1 must be paged out and now V6 maps to P1 (and V1 is marked X).

In the sequence, same page can happen repetitively, so sequence like V5, V5, V7, V6, or V5, V10, V10 etc. is possible.

(a)(8%) Assume the first 12 page references are as above V3, V1, V0, V5, V4, V9, V2, V11, V5, V3, V7, V6.

Now with the next 4 (13^th till 16^th references) references as V15, V0, V1, and V0. Explain how the paging in and paging out would happen.

(b)(12%) Now assume we have 128K virtual pages (V0 till V31 each of 4K) and still 32K physcial memory or 8 physical pages.

Assume the first 16 page references are as in (a) V3, V1, V0, V5, V4, V9, V2, V11, V5, V3, V7, V6, V15, V0, V1, and V0.

Assume the next 4 (from 17^th to 20^th) page references are: V31, V0, V1, and V0. Explain how the paging in and paging out would happen. Draw a picture of the extended virtual memory (from 64K to 128K) if possible.

Paging (2) Virtual address space 60K-64K X 56K-60K X 52K-56K X 48K-52K X 44K-48K 7 40K-44K X 36K-40K 5 32K-36K X 28K-32K X 24K-28K X 20K-24K 3 16K-20K 12K-16K 0 8K-12K OK-4K 2 Virtual page Physical memory address 28K-32K 24K-28K 20K-24K 16K-20K 12K-16K 4K-8K Page frame