Multilevel Page Table

Q1. Explain Multilevel Page Table.

Ans.The multilevel page table method is to avoid keeping all the pages tables in memory all the time. The top level page table with 1024 entries corresponding to the 10 bits PTL (Page Table Length Filed). When a virtual address is presented to the memory management unit (MMU), it first extracts the PTL (Page Table Length Filed), and uses this value as an index into the top level page table.

Figure: A two-level page table scheme

Program Structure

Q1. Explain Program Structure.

Ans. Demand paging is designed to be transparent to the user program. In many cases, the user is completely unaware of the paged nature of memory. In other cases, however, system performance can be improved if the user (or compiler) has an awareness of the underlying demand paging.


Let’s look at a contrived but informative example. Assume that pages are 128 words in size. Consider a C program whose function is to initialize to 0 each element of a 128-by-128 array. The following code is typical:


inti , j ;

int [128][128] data;

for (j = 0; j < 128; j++)

for (i = 0; i< 128; i++)

data[i] [j] = 0;


Notice that the array is stored row major; that is, the array is stored data[0] [0], data[0] [1], …, data[0] [127], data[l] [0], data[l] [1], …,data [127] [127]. For pages of 128 words, each row takes one page. Thus, the preceding code zeroes one word in each page, then another word in each page, and so on. If the operating system allocates fewer than 128 frames to the entire program, then its execution will result in 128 x 128 = 16,384 page faults.


In. contrast, changing the code to


inti, j ;

int[128][128] data;

for (i = 0; i< 128; i++)

for (j = 0 ; j < 128; j++)

data[i] [j] = 0;


zeroes all the words on one page before starting the next page, reducing the number of page faults to 128.


Careful selection of data structures and programming structures can increase locality and hence lower the page-fault rate and the number of pages in the working set.


For example, a stack has good locality, since access is always made to the top.

Difference between Global and Local Replacement

Q1. What is the difference between Global and Local Replacement.

Ans.With multiple processes competing for frames, we can classify page-replacement algorithms into two broad categories:

Global replacement and

Local replacement.


Global replacement allows a process to select a replacement frame from the set of all frames, even if that frame is currently allocated to some other process; that is, one process can take a frame from another. Local replacement requires that each process select from only its own set of allocated frames.


For example, consider an allocation scheme where we allow high-priority processes to select frames from low-priority processes for replacement. A process can select a replacement from among its own frames or the frames of any lower-priority process. This approach allows a high-priority process to increase its frame allocation at the expense of a low-priority process.


With a local replacement strategy, the number of frames allocated to a process does not change. With global replacement, a process may happen to select only frames allocated to other processes, thus increasing the number of frames allocated to it (assuming that other processes do not choose its frames for replacement).


One problem with a global replacement algorithm is that a process cannot control its own page-fault rate. The set of pages in memory for a process depends not only on the paging behavior of that process but also on the paging behavior of other processes. Therefore, the same process may perform quite differently (for example, taking 0.5 seconds for one execution and 10.3 seconds for the next execution) because of totally external circumstances.


Such is not the case with a local replacement algorithm. Under local replacement, the set of pages in memory for a process is affected by the paging behavior of only that process. Local replacement might hinder a process, however, by not making available to it other, less used pages of memory. Thus, global replacement generally results in greater system throughput and is therefore the more common method.

Least Frequently Used (LFU) Page-Replacement Algorithm

Q3. Explain Least Frequently Used (LFU) Page-Replacement Algorithm.

Ans. The least frequently used (LFU) page-replacement algorithm requiresthat the page with the smallest count be replaced. The reason for thisselection is that an actively used page should have a large reference count.A problem arises, however, when a page is used heavily during the initialphase of a process but then is never used again. Since it was used heavily,it has a large count and remains in memory even though it is no longerneeded. One solution is to shift the counts right by 1 bit at regular intervals,forming an exponentially decaying average usage count.