User Rating:  / 0

PoorBest 

Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems

Summary

• Belady’s Anomaly
• Page Replacement Algorithms
  • Least Frequently Used (LFU)
  • Most Frequently Used (MFU)
  • Page Buffering Algorithm
• Allocation of Frames
• Minimum Number of Frames
• Thrashing

Belady’s Anomaly

Consider the following example of the FIFO algorithm.

• Number of frames allocated = 3
• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• Number of page faults = 9

Now an intuitive idea is that if we increase the number of frames allocated to 4 from 3, the page faults should decrease, but the following example demonstrates otherwise.

• Number of frames allocated = 4
• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• Number of page faults = 10

This is due to the Belady’s Anomaly which states that “For some page replacement algorithms, the page fault rate may increase as the number of allocated frames increases.”

Stack Replacement Algorithms

These are a class of page replacement algorithms with the following property:
Set of pages in the main memory with n frames is a subset of the set of pages in memory with n+1 frames.
These algorithms do not suffer from Belady’s Anomaly. An example is the LRU algorithm.
Consider the following example which shows that LRU does not suffer from Belady’s anomaly for the given reference string.

• Number of frames allocated = 3
• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• Number of page faults = 10

• Number of frames allocated = 4
• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• Number of page faults = 8

LRU Approximation Algorithm

Few computer systems provide sufficient hardware support for true LRU page replacement. Some systems provide no hardware support and other page replacement algorithms must be used. Many systems provide some help however, in the form of a reference bit. The reference bit for a page is set by the hardware whenever that page is
referenced. Reference bits are associated with each entry in the page table.
Initially all bits are cleared by the operating system. As a user process executes the bit associated with each page referenced is set to 1 by the hardware. After some time we can determine which pages have been used and which have not been used by examining the reference bits. We do not know the order of use however, but we know which pages were used and which were not used.

Least frequently used algorithm

This algorithm is based on the locality of reference concept— the least frequently used page is not in the current locality. LFU requires that the page with the smallest count be replaced. The reason for this selection is that an actively used page should have a large reference count. This algorithm suffers from the situation in which a page is used heavily during the initial phase 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 longer needed.
One solution is to shift the counts right by 1 bit at regular intervals, forming an exponentially decaying average user count.

Most Frequently Used

The MFU page replacement algorithm is based on the argument that the page with the smallest count was probably just brought in and has yet to be used; it will be in the locality that has just started.

Page Buffering Algorithm

The OS may keep a pool of free frames. When a page fault occurs a victim page is chosen as before. However the desired page is read into a free frame from the pool before the victim is written out. This allows the process to restart as soon as possible, without waiting for the victim to be written out. When the victim is later written out, its frame is added to the free frame pool. Thus a process in need can be given a frame quickly and while victims are selected, free frames are added to the pool in the background An expansion of this idea is to maintain a list of modified pages. Whenever the paging device is idle, a modified page is selected and is written to disk. Its modify bit is then reset. This scheme increases the probability that a page will be clean when it is selected for replacement and will not need to be written out.

Another modification is to keep a pool of free frames, but to remember which page was in which frame. Since the frame contents are not modified when a frame is written to disk, the old page can be reused directly from the free-frame pool if it is needed before that frame is reused. No I/O is needed in this case. When a page fault occurs we check whether the desired page is in the free-frame pool. If it is not we must select a free frame and read into it. This method is used together with FIFO replacement in the VAX/VMS operating system.

Local vs Global Replacement

If process P generates a page fault, page can be selected in two ways:

• Select for replacement one of its frames.
• Select for replacement a frame from a process with lower priority number.

Global replacement allows a process to select a replacement frame from the set of all frames, even if that frame belongs to some other process; one process can take a frame from another. Local replacement requires that each process select from only its allocated frames.
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 the low priority process.

Allocation of frames

Each process needs a minimum number of frames so that its execution may be guaranteed on a given machine. Let’s consider the MOV X,Y instruction. The instruction is 6 bytes long (16-bit offsets) and might span 2 pages. Also, two pages to handle source and two pages are required to handle destination (assuming 16-bit source and destination).

Minimum frames required to guarantee execution of the MOV X,Y instruction

There are three major allocation schemes:

• Fixed allocation
  In this scheme free frames are equally divided among processes
• Proportional Allocation
  Number of frames allocated to a process is proportional to its size in this scheme.
• Priority allocation
  Priority-based proportional allocation

Here is an example of frame allocation:

Number of free frames = 64
Number of processes = 3
Process sizes: P1 = 10 pages; P2 = 40 pages; P3 = 127 pages

• Fixed allocation
  64/3 = 21 frames per process and one put in the free frames list
• Proportional Allocation
  • si = Size of process Pi
  • S = Σ si
  • m = Number of free frames
  • ai = Allocation for Pi = (si / S) * m
    • a1 = (10 / 177) * 64 = 3 frames
    • a2 = (40 / 177) * 64 = 14 frames
    • a3 = (127 / 177) * 64 = 45 frames
  • Two free frames are put in the list of free frames

Thrashing

If a process does not have “enough” pages, the page-fault rate is very high. This leads to low CPU utilization. The operating system thinks that it needs to increase the degree of multiprogramming, because it monitors CPU utilization and find it to be decreasing due to page faults. Thus another process is added to the system and hence thrashing occurs and causes throughput to plunge.
A process is thrashing if it is spending more time paging (i.e., swapping pages in and out) than executing. Thrashing results in severe performance problems:

• Low CPU utilization
• High disk utilization
• Low utilization of other I/O devices

The figure shows that as the degree of multiprogramming increases CPU utilization also increases, although more slowly, until a maximum is reached. If the degree of multiprogramming is increased further, thrashing sets in and CPU utilization drops sharply. At this point we must decrease the degree of multiprogramming. We can limit the effects of thrashing by using a local replacement scheme. With local replacement if one process starts thrashing it cannot steal frames from another process and cause the latter to thrash also. Pages are replaced with regard to the process of which they are a part. Hence local page replacement prevents thrashing to spread among several processes. However if processes are thrashing, they will be in the queue for the paging device most of the time. The average service time for a page fault will increase and effective access time will increase even for a process that is not thrashing.

• < Prev
• Next >