Virtual-Memory Management

Background, Demand Paging, Page Replacement, allocation offrames, Thrashing

 Background
 A computer can address more memory than the amount of physically
installed on the system. This extra memory is actually called virtual
memory and it is a section of a hard disk that's set up to emulate the
computer's RAM.
 The main visible advantage of this scheme is that programs can be
larger than physical memory. Virtual memory serves two purposes.
First, it allows us to extend the use of physical memory by using disk.
Second, it allows us to have memory protection, because each virtual
address is translated to a physical address.
 Virtual Memory is a storage scheme that provides user an illusion of having a very big
main memory. This is done by treating a part of secondary memory as the main memory.
 In this scheme, User can load the bigger size processes than the available main memory
by having the illusion that the memory is available to load the process.
 Instead of loading one big process in the main memory, the Operating System loads the
different parts of more than one process in the main memory.
 By doing this, the degree of multiprogramming will be increased and therefore, the CPU
utilization will also be increased.
 Virtual memory involves the separation of logical memory as perceivedby users from
physical memory. This separation allows an extremely largevirtual memory to be
provided for programmers when only a smaller physicalmemory is available (Figure 9.1).
 Virtual memory makes the task of programmingmuch easier, because the programmer no
longer needs to worry aboutthe amount of physical memory available; she can
concentrate instead on theproblem to be programmed.
 Demand Paging
 Demand paging is a technique used in virtual memory systems where
the pages are brought in the main memory only when required or
demanded by the CPU. Hence, it is also named as lazy swapper because
the swapping of pages is done only when required by the CPU.
 A demand paging system is quite similar to a paging system with swapping where
processes reside in secondary memory and pages are loaded only on demand, not in
advance. When a context switch occurs, the operating system does not copy any of the
old program’s pages out to the disk or any of the new program’s pages into the main
memory Instead, it just begins executing the new program after loading the first page and
fetches that program’s pages as they are referenced.
 In computer operating systems, demand paging (as opposed to anticipatory paging) is a
method of virtual memory management. ... It follows that a process begins execution with
none of its pages in physical memory, and many page faults will occur until most of a
process's working set of pages are located in physical memory.

 1. Transfer of a paged memory to contiguous disk space:

 A demand-paging system is similar to a paging system with swapping(Figure 9.4) where
processes reside in secondary memory (usually a disk).When we want to execute a
process, we swap it into memory. Rather thanswapping the entire process into memory,
though, we use a lazy swapper.A lazy swapper never swaps a page into memory unless
that page will beneeded.
 2. Page table when some pages are in main memory:
 When a process is to be swapped in, the pager guesses which pages will beused before
the process is swapped out again. Instead of swapping in a wholeprocess, the pager brings
only those pages into memory. Thus, it avoids readinginto memory pages that will not be
used anyway, decreasing the swap timeand the amount of physical memory needed.
 With this scheme, we need some form of hardware support to distinguishbetween the
pages that are in memory and the pages that are on the [Link] valid–invalid bit scheme
described in this Section. This time, however, when this bit is set to “valid,” the
associated pageis both legal and in memory. If the bit is set to “invalid,” the page either is
notvalid (that is, not in the logical address space of the process) or is valid butis currently
on the disk.
 The page-table entry for a page that is brought intomemory is set as usual, but the page-
table entry for a page that is not currentlyin memory is either simply marked invalid or
contains the address of the pageon disk. This situation is depicted in Figure 9.5.
 Notice that marking a page invalid will have no effect if the process neverattempts to
access that page. Hence, if we guess right and page in all pagesthat are actually needed
and only those pages, the process will run exactly asthough we had brought in all pages.
While the process executes and accessespages that are memory resident, execution
proceeds normally.
 Page Faults
 A Page fault occurs when a program attempts to access a block of memory that is
not stored in the physical memory, or RAM. The fault notifies the operating system
that it must locate the data in Virtual memory then transfers it from the storage
device such as an HDD or SSD to the system physical memory or RAM.
 But what happens if the process tries to access a page that was not broughtinto memory?
Access to a page marked invalid causes a page fault. The paginghardware, in translating
the address through the page table, will notice thatthe invalid bit is set, causing a trap to
the operating system. This trap is theresult of the operating system’s failure to bring the
desired page into memory.
 The procedure for handling this page fault is straightforward (Figure 9.6):
1. We check an internal table (usually kept with the process control block)for this process
to determine whether the reference was a valid or aninvalid memory access.
2. If the reference was invalid, we terminate the process. If it was valid butwe have not
yet brought in that page, we now page it in.
3. We find a free frame (by taking one fromthe free-frame list, for example).
4. We schedule a disk operation to read the desired page into the newlyallocated frame.
5. When the disk read is complete, we modify the internal table kept withthe process and
the page table to indicate that the page is now in memory.
6. We restart the instruction that was interrupted by the trap. The processcan now access
the page as though it had always been in memory.
 In the extreme case, we can start executing a process with no pages inmemory. When the
operating system sets the instruction pointer to the firstinstruction of the process, which is
on a non-memory-resident page, the processimmediately faults for the page. After this
page is brought into memory, theprocess continues to execute, faulting as necessary until
every page that itneeds is in memory. At that point, it can execute with no more faults.
Thisscheme is pure demand paging: never bring a page into memory until it isrequired.
 Page Replacement
 The page replacement algorithm decides which memory page is to be replaced. The
process of replacement is sometimes called swap out or write to disk. Page
replacement is done when the requested page is not found in the main memory
(page fault).
 Page replacement algorithms are an important part of virtual memory management
and it helps the OS to decide which memory page can be moved out, making space
for the currently needed page. However, the ultimate objective of all page
replacement algorithms is to reduce the number of page faults.
 There are two main aspects of virtual memory, Frame allocation and Page Replacement.
It is very important to have the optimal frame allocation and page replacement algorithm.
Frame allocation is all about how many frames are to be allocated to the process while
the page replacement is all about determining the page number which needs to be
replaced in order to make space for the requested page.
 Page replacement takes the following approach. If no frame is free, we findone that is not
currently being used and free [Link] can free a frame by writingits contents to swap space
and changing the page table (and all other tables) toindicate that the page is no longer in
memory (Figure 9.10). We can now usethe freed frame to hold the page for which the
process [Link] modify thepage-fault service routine to include page replacement:
 1. Find the location of the desired page on the disk.
 2. Find a free frame:
 a. If there is a free frame, use it.
 b. If there is no free frame, use a page-replacement algorithm to select a victim frame.
 c. Write the victim frame to the disk; change the page and frame tablesaccordingly.
 3. Read the desired page into the newly freed frame; change the page andframe tables.
 4. Continue the user process from where the page fault [Link] that, if no frames
are free, two page transfers (one out and one in)are required. This situation effectively
doubles the page-fault service time andincreases the effective access time accordingly.
 Types of Page Replacement Algorithms:
 There are various page replacement algorithms. Each algorithm has a different method by
which the pages can be replaced.
 First In First Out (FIFO) algorithm:
 Oldest page in main memory is the one which will be selected for replacement.
 Easy to implement, keep a list, replace pages from the tail and add new pages at the head.
 Optimal Page algorithm:
 An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms.
An optimal page-replacement algorithm exists, and has been called OPT or MIN.
 Replace the page that will not be used for the longest period of time. Use the time
when a page is to be used.
 Least Recently Used (LRU) algorithm:
 If we use the recent past as an approximation of the near future, then we can replace the
page that has not been used for the longest period of time.
 ThisEasy to implement, keep a list, replace pages by looking back into time.

 First In First Out (FIFO) algorithm:

 Belady's Anomaly:
Bélády's anomaly is the phenomenon in which increasing the number of page frames
results in an increase in the number of page faults for certain memory access patterns.
This phenomenon is commonly experienced when using the first-in first-out (FIFO) page
replacement algorithm.
 Optimal Page algorithm:

 Least Recently Used (LRU) algorithm:

 LRU-Approximation Page Replacement:

 Few computer systems provide sufficient hardware support for true LRU
pagereplacement. In fact, some systems provide no hardware support, and otherpage-
replacement algorithms (such as a FIFO algorithm) must be used.
 Manysystems provide some help, however, in the form of a reference bit. Thereference
bit for a page is set by the hardware whenever that page is referenced(either a read or a
write to any byte in the page). Reference bits are associatedwith each entry in the page
table.
 Initially, all bits are cleared (to 0) by the operating system. As a user processexecutes, the
bit associated with each page referenced is set (to 1) by thehardware.
 After some time, we can determinewhich pages have been used andwhich have not been
used by examining the reference bits, although we do notknow the order of use. This
information is the basis for many page-replacementalgorithms that approximate LRU
replacement.
 (a) Additional-Reference-Bits Algorithm
 We can gain additional ordering information by recording the reference bits at regular
intervals. We can keep an 8-bit byte for each page in a table in memory. At regular
intervals (say, every 100 milliseconds), a timer interrupt transfers control to the operating
system. The operating system shifts the reference bits for each page into the high order
bit of its 8-bit bytes, shifting the other bits right by 1 bit and discarding the low-order bit.
These 8-bit shift registers contain the history of page use for the last eight time periods. If
the shift register contains 00000000, for example, then the page has not been used for
eight time periods; a page that is used at least once in each period has a shift register
value of 11111111. A page with a history register value of 11000100 has been used more
recently than one with a value of 01110111. If we interpret these 8-bit bytes as unsigned
integers, the page with the lowest number is the LRU page, and it can be replaced. Notice
that the numbers are not guaranteed to be unique, however. We can either replace (swap
out) all pages with the smallest value or use the FIFO method to choose among them.

 (b)Second-Chance Algorithm (or) Second ChanceFIFO (clock) replacement

algorithm
 The second chance algorithm is essentially a FIFO, except the reference bit is used to
give pages a second chance at staying in the page table.
 When a page must be replaced, the page table is scanned in a FIFO (circularqueue )
manner.
 If a page is found with its reference bit not set, then that page is selected as the next
victim.
 If, however, the next page in the FIFO does have its reference bit set, then it is given a
second chance:
o The reference bit is cleared, and the FIFO search continues.
o If some other page is found that did not have its reference bit set, then that page
will be selected as the victim, and this page ( the one being given the second
chance ) will be allowed to stay in the page table.
o If , however, there are no other pages that do not have their reference bit set, then
this page will be selected as the victim when the FIFO search circles back around
to this page on the second pass.
 If all reference bits in the table are set, then second chance degrades to FIFO, but also
requires a complete search of the table for every page-replacement.
 As long as there are some pages whose reference bits are not set, then any page
referenced frequently enough gets to stay in the page table indefinitely.
 This algorithm is also known as the clock algorithm, from the hands of the clock moving
around the circular queue.
 Figure 9.17 - Second-chance ( clock ) page-replacement algorithm.

 Example:
 (c)Enhanced Second-Chance Algorithm:
 The enhanced second chance algorithm looks at the reference bit and the modify bit
( dirty bit ) as an ordered page, and classifies pages into one of four classes:
 ( 0, 0 ) - Neither recently used nor modified.
 ( 0, 1 ) - Not recently used, but modified.
 ( 1, 0 ) - Recently used, but clean.
 ( 1, 1 ) - Recently used and modified.
 This algorithm searches the page table in a circular fashion ( in as many as four passes ),
looking for the first page it can find in the lowest numbered category. I.e. it first makes a
pass looking for a ( 0, 0 ), and then if it can't find one, it makes another pass looking for a
( 0, 1 ), etc.
 The main difference between this algorithm and the previous one is the preference for
replacing clean pages if possible.

 Counting-Based Page Replacement:

 There are several algorithms based on counting the number of references that have been
made to a given page, such as:
 (a) Least Frequently Used, LFU: Replace the page with the lowest reference count. A
problem can occur if a page is used frequently initially and then not used any more, as the
reference count remains high. A solution to this problem is to right-shift the counters
periodically, yielding a time-decaying average reference count.
 (b)Most Frequently Used, MFU: Replace the page with the highest reference count. The
logic behind this idea is that pages that have already been referenced a lot have been in
the system a long time, and we are probably done with them, whereas pages referenced
only a few times have only recently been loaded, and we still need them.
 In general counting-based algorithms are not commonly used, as their implementation is
expensive and they do not approximate OPT well.

 Page-Buffering Algorithms:
 There are a number of page-buffering algorithms that can be used in conjunction with the
afore-mentioned algorithms, to improve overall performance and sometimes make up for
inherent weaknesses in the hardware and/or the underlying page-replacement algorithms:
 Maintain a certain minimum number of free frames at all times. When a page-fault
occurs, go ahead and allocate one of the free frames from the free list first, to get the
requesting process up and running again as quickly as possible, and then select a victim
page to write to disk and free up a frame as a second step.
 Keep a list of modified pages, and when the I/O system is otherwise idle, have it write
these pages out to disk, and then clear the modify bits, thereby increasing the chance of
finding a "clean" page for the next potential victim.
 Keep a pool of free frames, but remember what page was in it before it was made free.
Since the data in the page is not actually cleared out when the page is freed, it can be
made an active page again without having to load in any new data from disk. This is
useful when an algorithm mistakenly replaces a page that in fact is needed again soon.
 Allocation of frames
 The main memory of the operating system is divided into various frames.
The process is stored in these frames, and once the process is saved as a
frame, the CPU may run it. As a result, the operating system must set aside
enough frames for each process. As a result, the operating system uses
various algorithms in order to assign the frame.
 Demand paging is used to implement virtual memory, an essential operating
system feature. It requires the development of a page replacement
mechanism and a frame allocation system. If you have multiple processes,
the frame allocation techniques are utilized to define how many frames to
allot to each one. A number of factors constrain the strategies for allocating
frames:
o You cannot assign more frames than the total number of frames available.
o A specific number of frames should be assigned to each process. This
limitation is due to two factors. The first is that when the number of frames
assigned drops, the page fault ratio grows, decreasing the process's execution
performance. Second, there should be sufficient frames to hold all the
multiple pages that any instruction may reference.
 There are mainly five ways of frame allocation algorithms in the OS.
These are as follows:

1. Equal Frame Allocation

2. Proportional Frame Allocation
3. Priority Frame Allocation
4. Global Replacement Allocation
5. Local Replacement Allocation
 Equal frame Allocation - In equal frame allocation, the processes are
assigned equally among the processes in the OS. For example, if the system
has 30 frames and 7 processes, each process will get 4 frames. The 2 frames
that are not assigned to any system process may be used as a free-frame
buffer pool in the system.
 Disadvantage
 In a system with processes of varying sizes, assigning equal frames to each
process makes little sense. Many allotted empty frames will be wasted if
many frames are assigned to a small task.

 Proportional frame Allocation - Frames are allocated to each process

according to the process size.
 For a process pi of size si, the number of allocated frames is ai = (si/S)*m,
where S is the sum of the sizes of all the processes and m is the number of
frames in the system.
 For instance, in a system with 62 frames, if there is a process of 10KB and
another process of 127KB, then the first process will be allocated
(10/137)*62 = 4 frames and the other process will get (127/137)*62 = 57
frames.
 Advantage: All the processes share the available frames according to their
needs, rather than equally.
 Priority Frame Allocation - Priority frame allocation assigns frames based
on the number of frame allocations and the processes. Suppose a process
has a high priority and requires more frames that many frames will be
allocated to it. Following that, lesser priority processes are allocated.
 Global Replacement Allocation - When a process requires a page that isn't
currently in memory, it may put it in and select a frame from the all frames
sets, even if another process is already utilizing that frame. In other words,
one process may take a frame from another.
 Advantages
 Process performance is not hampered, resulting in higher system
throughput.
 Disadvantages
 The process itself may not solely control the page fault ratio of a process.
The paging behavior of other processes also influences the number of
pages in memory for a process.

 Local Replacement Allocation

 When a process requires a page that isn't already in memory, it can bring it
in and assign it a frame from its set of allocated frames.
 Advantages
 The paging behavior of a specific process has an effect on the pages in
memory and the page fault ratio.
 Disadvantages
 A low priority process may obstruct a high priority process by refusing to
share its frames.
 Thrashing

 Thrashing is when the page fault and swapping happens very frequently at a
higher rate, and then the operating system has to spend more time swapping
these pages. This state in the operating system is known as thrashing.
Because of thrashing, the CPU utilization is going to be reduced or
negligible.

 A process that is spending more time paging than executing is said to

be thrashing.
 Thrashing affects the performance of execution in the Operating system.
 Techniques used to handle the thrashing

 As we have already told you the Local Page replacement is better than the
Global Page replacement but local page replacement has many
disadvantages too, so it is not suggestible. Thus, given below are some
other techniques that are used:
 Working-Set Model
 This model is based on the assumption of the locality. It makes the use of
the parameter? in order to define the working-set window. The main idea is
to examine the most recent? page reference. What locality is saying, the
recently used page can be used again, and also the pages that are nearby
this page will also be used?
 1. Working Set
 The set of the pages in the most recent? page reference is known as the
working set. If a page is in active use, then it will be in the working set. In
case if the page is no longer being used then it will drop from the working
set? times after its last reference.
 The accuracy of the working set mainly depends on? what is chosen?
 This working set model avoids thrashing while keeping the degree of
multiprogramming as high as possible.
 2. Page Fault Frequency
 Figure: Page fault frequency
 The working-set model is successful and its knowledge can be useful in
preparing but it is a very clumpy approach in order to avoid thrashing.
There is another technique that is used to avoid thrashing and it is Page
Fault Frequency (PFF) and it is a more direct approach.
 The main problem is how to prevent thrashing. As thrashing has a high page
fault rate and also, we want to control the page fault rate.
 When the Page fault is too high, then we know that the process needs
more frames. Conversely, if the page fault-rate is too low then the process
may have too many frames.
 We can establish upper and lower bounds on the desired page faults. If the
actual page-fault rate exceeds the upper limit then we will allocate the
process to another frame. And if the page fault rate falls below the lower
limit, then we can remove the frame from the process.
 Thus, with this, we can directly measure and control the page fault rate in
order to prevent thrashing.