1 Consider a paging system with the page table stored in mem

1. Consider a paging system with the page table stored in memory.
a. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?
b. If we add associative registers, and 75 percent of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)

2. What is the effect of allowing two entries in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What effect would updating some byte on the one page have on the other page?

3. Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.
How many page faults would occur for the following replacement algorithms, assuming one, two, three, four, five, six, or seven frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each.

LRU replacement

FIFO replacement

Optimal replacement

4. A system has a 32-bit architecture so each process has 32-bit virtual address space. Each page is 4KB. If a program\'s total data/code can be fit into two pages, then what are the minimal/maximum page table overhead (in terms of the number of page table entries) for (a) a one-level page table; and (b) a two-level page table, assuming level-1 and level-2 tables are of the same size.

Solution

1. (a) - Page is kept in Main Memory.
Actually when a request comes to access its data in memory, operating system maps the virtual address provided by the process to the physical adress where the actual data is stored.
Here, \" page table \" is, it stores these mappings of virtual address to physical address.
**SO, Actual process( mapping data ) takes 200ns + To access the page table( page lookup ) it takes 200ns for mapping. So, total 400ns it takes.** (Page lookup: It looks up a for a mapping in the page table whether it exists or not.)

(b) - TLB (Translation Lookaside Buffer ) which is a associative memory. i.e, when a virtual address tries to map physiacl address, TLB process begins, It looks for a match, if it finds it will be a hit, if it doesn\'t find, it will be a miss. So, as mentioned 75% page table referrences are found, and 0 to find a page table entry, we can knew that 25% is a miss.

75%(HIT)+25%(MISS) is 75%(200ns)+25%(400ns)= 250ns

2.

Actaually in paging concept, page number and page offset to be known for this question.

Page number- Is like an index value which contains base address of each page in physical memory.
Page offset - combined to the base address to define physical address which is sent to the memory unit.

So, in a page table allowing two entries to the same page frame- effect is, if you change a byte at one address, a byte at offset in the other page also changes. to see advantage is,
we can do multiple copies quickly by mapping a page read-only at two addresses, we can share the data between users, and also is the code is reentrant, more memory space can be saved using programs like editors, databases, compilers as larege amount of code consumes more memory by having different page tables pointing to the same location.

3.

FIFO(Fist-In-First-Out) - Operating System maintains a list of all pages in the table currently in memory ,
with oldest at the head and most arrival at the tail.

So on a page fault, the page at the head is removed and recent one is added to the tail in a list.

reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.

First it takes - 1 2 3 4

As 2, 1 is there already in the list, next 5 will come for replacement.

5 2 3 4

Next 6, now it will be 5 6 3 4

Next 2, now it will be 5 6 2 4

Next 1, now it will be 5 6 2 1

As 2 is already there, next 3 now it will be 5 6 3 1

next 7, now it will be 5 6 3 7

as 6 and 3 is there, next 2 will come 2 6 3 7

next 1, now - 2 1 3 7

as 2 and 3 is there, next 6 , now- 2 6 3 7

LRU(Least Recently Used): Page which has not been used for the longer time will be selected for the replacement.

Optimal replacement algorithm: it selects a page which is no longer used, but uses the page when needed. i.e, why this algorithm has a lowest fault-rate compared to ther algorithms.