UNIT – IV

VIRTUAL MEMORY
8
Definition

 Virtual Memory is a concept used in some larger computer systems that permit
the users to construct his programs beyond the primary memory capacity.

Virtual Memory Concepts

 Virtual Memory is a technique that allows the execution of processes that may
not be completely in memory.

 The advantage of this scheme is that user programs can be larger than physical
memory. That is, we can execute a process whose logical address space is larger than
the available physical address space.

 Virtual memory also allows processes to share files easily and to implement shared
memory.

Instances where virtual memory can be applied:

1) The code to handle unusual error conditions are almost never executed, and need not
be in physical memory.

2) The unused portions of arrays, lists, and table need not be in physical memory.

Allowing partial program in the physical memory (Virtual memory) has many advantages.

 Users are allowed to write programs for a very large virtual address space, simplifying
the programming task.

 More users may run their programs at the same time. It leads to increase in CPU
utilization and throughput.
8.2 Virtual Memory

 Each user can run faster since less I/O is needed.

Virtual Memory is the use of space on a hard disk drive (HDD) to simulate additional
main memory.

 Figure 8 .1 shows the virtual memory with relation to physical memory.

Figure 8.1: Diagram showing virtual memory that is larger than physical memory

 Virtual Memory is commonly implemented by Demand Paging. It can also be

implemented in a segmentation system.

 Demand Segmentation can also be used to provide virtual memory. Burroughs‟

computer systems have used demand segmentation. The IBM OS/2 operating system
also uses demand segmentation.

8.1 Demand Paging

 Demand Paging is a type of swapping in which pages of data are not copied from
disk to RAM until they are needed.
 A demand-paging system is similar to a paging system with swapping (Figure 8.2)
where processes reside in secondary memory (usually disk).

 When we want to execute a process, we swap it into memory.

 Lazy Swapper concept is used in demand paging. A Lazy swapper never swaps a
page into memory unless that page will be needed.

 A process can be viewed as a sequence of pages, rather than as one large contiguous
address space.

 A swapper manipulates entire processes, whereas a pager is concerned with the

individual pages of a process.
 Operating System 8.3

Figure 8.2: Transfer of a paged memory to contiguous disk space

1. Basic Concepts
 When a process is to be swapped in, the pager guesses which pages will be used before
the process is swapped out again. Instead of swapping in a whole process, the pager
brings only those necessary pages into memory.
 With this scheme, we need some form of hardware support to distinguish between
those pages that are in memory and those pages that are not on the disk.
 The valid-invalid bit scheme can be used for this purpose.
 When the bit is said to “valid”, this value indicates that the associated page is both
legal and in memory. If the bit is set to “invalid”, this value indicates that the page
either is not valid, or is valid but is currently on the disk.
 The page-table entry for a page that is brought into memory is set as usual, but the
page-table entry for a page that is not currently in memory is simply marked invalid, or
contains the address of the page on disk. This situation is depicted in Figure 8.3.

Figure 8.3: Page table when some pages are not in main memory
8.4 Virtual Memory

 Marking a page invalid will have no effect if the process never attempts to access that
page.

 While the process executes and accesses pages that are memory resident, execution
proceeds normally.

 Access to a page marked invalid causes a page-fault trap.

 The procedure for handling this page is straightforward (Figure 8.4).

1. We check an internal table (usually kept with the process control block) for this
process, to determine whether the reference bit was a valid or invalid memory
access.

2. If the reference was invalid, we terminate the process. If it was valid, but we have
not yet brought in that page, we now page it in.

3. We find a free frame from the free-frame list.

4. We schedule a disk operation to read the desired page into the newly allocated
frame.

5. When the disk read is complete, we modify the internal table kept with the process
and the page table to indicate that the page is now in memory.

6. We restart the instruction that was interrupted by the illegal address trap. The
process can now access the page as though it had always been in memory.

Figure 8.4: Steps in handling a page fault

 Operating System 8.5

Pure Demand Paging

 A scheme that never brings a page into memory until it is required.

2. Hardware Support

 The hardware to support demand paging is the same as the hardware for paging and
swapping:

 Page Table: This table has the ability to mark an entry invalid through a valid –
invalid bit or special value of protection bits.

 Secondary memory: This memory holds those pages that are not present in main
memory. The secondary memory is usually a high-speed disk. It is known as the swap
device, and the section of disk used for this purpose is known as swap space.

3. Performance of Demand Paging

Demand paging can have a significant effect on the performance of a computer

system.

Let p be the probability of a page fault (o < p < 1). We would expect p to be close to
zero; this is, there will be only a few page faults. The effective access time is then

Effective access time = (1 – p) x ma + p x page fault time.

To compute the effective access time, we must know how much time is needed to
service a page fault. A page fault causes the following sequence to occur:

1. Trap to the operating system.

2. Save the user registers and process state.

3. Determine that the interrupt was a page fault.

4. Check that the page reference was legal and determine the location of the page on
the disk.

5. Issue a read from the disk to a free frame:

a. Wait in a queue for this device until the read request is serviced.

b. Wait for the device seek and / or latency time.

c. Begin the transfer of the page to a free frame.

8.6 Virtual Memory

6. While waiting, allocate the CPU to some other user (CPU scheduling optional).

7. Interrupt from the disk (I/O completed).

8. Save the registers and process state for the other user (if step 6 is executed).

9. Determine that the interrupt was from the disk.

10. Correct the page table and other tables to show that the desired page is now in
memory.

11. Wait for the CPU to be allocated to this process again.

12. Restore the user register, process state, and new page table, then resume the
interrupted instruction.

In any case, we are faced with three major components of the page-fault service time:

 Service the Page-Fault interrupt

 Read in the page

 Restart the process

Advantages of Demand Paging

 Large virtual memory.

 More efficient use of memory.

 Unconstrained multiprogramming. There is no limit on the degree of

multiprogramming.

Disadvantages of Demand Paging

 Number of tables and amount of processor over head for handling page interrupts are
greater than in the case of the simple paged management techniques.

 Due to the lack of an explicit constraint on a job‟s address space size.

 Operating System 8.7

Comparison of Demand Paging with Segmentation

Sl. No. Segmentation Demand Paging

1. Segments may be of different size. Pages are of same size.

2. Segment can be shared Pages cannot be shared.

It allows dynamic growth of

3. Page size is fixed.
segments.

Segment map table indicates the Page map table keeps track of pages in
4.
address of each segment in memory. memory.

Segments are allocated to the program Pages are loaded in memory on

5.
while compilation. demand.

6. Provides Virtual Memory Also provides Virtual Memory.

8.2 Page Replacement

 Page replacement policy deals with the selection of a page in memory to be

replaced when a new page must be brought in.

 A page replacement algorithm looks at the limited information about accesses to the
pages provided by hardware, and tries to guess which pages should be replaced to
minimize the total number of page misses, while balancing this with the costs (primary
storage and processor time) of the algorithm itself.

Basic Scheme

 Page replacement takes the following approach. If no frame is free, we fine one that is
not currently being used and free it.

 We can free a frame by writing its contents to swap space, and changing the page table
(and all other tables) to indicate that the page is no longer in memory (Figure 8.5).

 The page-fault service routine can be modified 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.
8.8 Virtual Memory

b) If there is no free frame, use a page-replacement algorithm to select a victim

frame.

c) Write the victim page to the disk; change the page and frame tables
accordingly.

3. Read the desired page into the (newly) free frame; change the page and frame
tables.

4. Restart the user process.

Figure 8.5: Page Replacement

 Page replacement is basic to demand paging. It completes the separation between

logical and physical memory.

 With this mechanism, an enormous virtual memory can be provided for programmers
on a smaller physical memory.

8.3 Page Replacement Algorithms

 A page-replacement algorithm is an algorithm that decides which pages should be

written to disk or file, when a new page needs to be allocated.

 There are many different page-replacement algorithms. Every operating system

probably has its own replacement scheme.

 The algorithm is evaluated by running it on a particular string of memory references

and computing the number of page faults. The string of memory references is called
a reference string.

 The various page-replacement algorithms are as follows:

 Operating System 8.9

1. FIFO Page Replacement

 The simplest page-replacement algorithm is a FIFO algorithm.

 A FIFO replacement algorithm associates with each page the time when that page was
brought into memory.

 When a page must be replaced, the oldest page is chosen.

 The operating system keeps track of all the pages in memory in a queue, with the most
recent arrival at the back, and the earliest arrival in front.

 The page is replaced at the head of the queue.

 When a page is brought into memory, it is inserted at the tail of the queue.

 If an active page is replaced to bring the new page, a fault occurs immediately to
retrieve the active page.

 The FIFO page-replacement algorithm is easy to understand and program. However,

its performance is not always good.

 This algorithm experiences

Belady's anomaly:

 For some page replacement algorithms, the page-fault rate may increase as the
number of allocated frame increases.

 Giving more memory to a process improves the performance.

 FIFO page replacement algorithm is used by the VAX/VMS operating system, with
some modifications.

Figure 8.6: FIFO page-replacement algorithm

8.10 Virtual Memory

2. Optimal Page Replacement

 An optimal page-replacement algorithm has the lowest page-fault rate of all
algorithms.
 This algorithm replaces the page that will not be used for the longest period of
time.

 This algorithm has been called OPT or MIN.

 This page-replacement algorithm guarantees the lowest possible page-fault rate for a
fixed number of frames.

 For example, in our sample reference string, the optimal page-replacement algorithm
would yield nine page faults as shown in Figure 8.7.

Figure 8.7: Optimal page-replacement algorithm

 The optimal page-replacement algorithm is difficult to implement, because it requires

the future knowledge of the reference string.

 The optimal algorithm is mainly used for comparison studies.

3. LRU Page Replacement

 The LRU page-replacement algorithm will replace the page that has not been used for
the longest period of time. This approach is the least-recently-used (LRU) algorithm.

 LRU replacement associates with each page the time of that page‟s last use.

 When a page must be replaced, LRU chooses that page that has not been used for the
longest period of time.

 This strategy is the optimal page-replacement algorithm looking backward in time,

rather than forward.

 The result of applying LRU replacement to our example reference string is shown in
Figure 8.8. The LRU algorithm produces 12 faults.
 Operating System 8.11

F
i
g
u
r
e

8.8: LRU page-replacement algorithm

 The LRU policy is often used as a page-replacement algorithm and is considered to be

good. The major problem is how to implement LRU replacement.

 An LRU page-replacement algorithm may require substantial hardware assistance.

Two implementations are feasible:

(a) Counters

 Each page-table entry is associated with time-of-use field.

 Logical clock or counter is added to the CPU and is implemented for every
memory reference.

 When a reference to a page is made, the contents of the clock register are copied
to the time-of-use field.

(b) Stack

 LRU replacement approach here is to keep a stack of page numbers.

 Whenever a page is referenced, it is removed from the stack and put on the top.

 The top of the stack is always the most recently used page and the bottom is the
LRU page (Figure 8.9)

Figure 8.9: Use of a stack to record the most recent references

8.12 Virtual Memory

 A stack algorithm is an algorithm for which it can be shown that the set of pages
in memory for n frames is always a subset of the set of pages that would be in
memory with n+1 frames.

4. LRU Approximation Page Replacement Algorithm

 An LRU page replacement algorithm should update the page removal status
information after every page reference.

 Reference bits are associated with each entry in the page table.

 Initially all the reference bits=0.

 When page is referenced, bit is set to 1.

 Replace the one which is 0 (If one exists).

 Determine which page has been used and which has not.

 Do not know the order of pages however.

(i) Additional – Reference – Bits Algorithm

 Additional reference bits algorithm gain additional information by: Recording the
reference bits at regular intervals.

 For example, keep 8 bits for each page in a table in memory

 Timer interrupts transfers control to the operating system at regular intervals.

 The OS shifts the reference bit for each page into the high-order bit of its 8-bit
byte.

 The 8-bit shift registers contain the history of page use for the last eight time
periods.

(ii) Second-Chance Algorithm

 Second-Chance algorithm is actually a FIFO replacement algorithm with a small

modification that causes it to approximate LRU.

 When a page is selected according to a FIFO order, we check its reference bit. If it
is set (the page was referenced), we clear it and look for another page.

 Also called the clock algorithm.

 Operating System 8.13

 In the worst case, when all bits are set, the pointer cycles through all of the pages,
giving each page a second chance and clearing its bit.

 Requires hardware support for reference bit.

Figure 8.10: Second-chance (clock) page-replacement algorithm

(iii) Enhanced Second – Chance Algorithm

 Enhanced second-chance algorithm is an algorithm that needs a reference bit

and a modify bit as an ordered pair.

 The following four situations are possible:

 (0, 0) - neither recently used nor modified - best page to replace.

 (0, 1) - not recently used but modified - not as good because we need to swap out
a page, but still better than used pages.

 (1, 0) - recently used but unmodified.

 (1, 1) - recently used and modified - the worst page to replace.

 Requires hardware support for reference and modify bits.

 May require two cycles.

8.14 Virtual Memory

5. Counting – Based Page Replacement

 The counting-based page replacement algorithm keeps a counter of the number of

references that have been made to each page, and develop the following two schemes.

 Least Frequently used (LFU) page-replacement algorithm

 Most frequently used (MFU) page-replacement algorithm

 Least Frequently Used (LFU) Algorithm: This technique involves selecting a page
with the smallest count for replacement. When a page fault occurs, a page that has not
been used for long time is selected for replacement.

 Most Frequently Used (MFU) Algorithm: This technique involves using a page that
has been used very recently. The assumption used here is that the page that has been
used very recently may not be used in the near future.

6. Page – Buffering Algorithm

 The operating system maintains a pool of free frames. 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 technique is used in the VAX/VMS system, with a FIFO replacement algorithm.

8.4 Thrashing
Definition
 High paging activity is called „Thrashing’.
 A process is thrashing if it is spending more time in paging than executing.
Causes of Thrashing
 Thrashing is caused by under allocation of the minimum number of pages required by
a process, forcing it to continuously page fault.
 Operating System 8.15

 It can be eliminated by reducing the level of multiprogramming.

 The operating system always monitors CPU utilization. If CPU utilization is less OS
increases the degree of multi programming by adding more processes to the system.

 It arises when a page fault occurs. A Page fault occurs when a program attempts to
access a block of memory that is not stored in physical memory or RAM.

 The effect of thrashing can be limited by using a local replacement algorithm, since it
does not permit stealing of frames from another process.

 There are three approaches to prevent thrashing, namely locality model of program
execution, working set model of program execution, and page fault frequency strategy.

Figure 8.11: Thrashing

1. Locality model of program execution

 The locality model states that as a program executes, it moves them from locality
to locality.

 A locality is a set of pages which are actively used together (Figure 8.12)

 A program is generally composed by several different localities, which may overlap.

Example: When a subroutine is called, it defines new locality. In this locality, memory
references are made to the instructions of the subroutine, its local variables, and a
subset of the global variables. When the subroutine is exited, the process leaves this
locality, sine the local variables and instructions of the subroutines are no longer in
active use.
8.16 Virtual Memory

Figure 8.12: Locality in a memory-reference pattern

2. Working-Set Model

 The working-set model is based on the concept of locality, and defines a working- set
window, of length delta.

 The idea is to examine the most recent delta page references.

 The set of pages in the most recent delta page references is the working set (Figure
8.13).

 If a page is in active use, it will be in the working set, else, it will be dropped from the
same

Figure 8.13: Working-set Model

 Operating System 8.17

 The accuracy of the working set depends on the selection of delta. If delta is too small,
it will not accommodate the entire locality; if delta is too large, it may overlap several
localities.

 The most important property of the working-set is its size.

 This working-set strategy prevents thrashing while keeping the degree of

multiprogramming as high as possible. Thus, it optimizes CPU utilization.

3. Page-Fault Frequency (PFF)

 Page Fault Frequency (PFF) is an approximation to the working set policy that is
useful for determining how many frames a process needs (but not which pages). For
each process, keep track of the page fault frequency, which is the number
of faults divided by the number of references.

 The page fault frequency strategy takes a more direct approach to prevent thrashing.
Our aim here is to control the page fault rate.

 When it is too high, we know that the process needs more frames. Similarly, if the rate
is too low, the process may have too many frames.

 We can establish upper and lower bounds on the desired page-fault rate (Figure 8.14).

 If the actual page-fault exceeds the upper limit, we allocate that process another frame.
If the page-fault rate falls below the lower limit, we remove a frame from the process.
Thus, we can directly measure and control the page-fault rate to prevent thrashing.

Figure 8.14: Page-Fault Frequency

8.18 Virtual Memory

Exercises:

1. Define Virtual Memory.

2. Write short notes on Virtual Memory Concepts.

3. What is meant by Demand Paging?

4. Explain briefly about Demand Paging with a neat diagram.

5. Distinguish between Demand Paging and Segmentation.

6. Write short notes on Page Replacement in OS.

7. What is meant by Page Replacement Algorithm?

8. Discuss briefly about FIFO Page Replacement Algorithm.

9. Discuss about Optimal Page Replacement Algorithm.

10. Write short notes on LRU Page Replacement Algorithm.

11. Discuss briefly about LRU Approximation Page Replacement Algorithm.

12. Discuss briefly about Counting-Based Page Replacement Algorithm.

13. Write short notes on Page-Buffering Algorithm.

14. Explain briefly the various Page Replacement Algorithms in OS.

15. Define Thrashing.

16. Explain briefly about Thrashing.

****************************