22 Virtual Memory
Mary Anitha Rajam
25.1 Introduction
Instructions of any process that are currently being executed must be placed in physical memory. If the entire process has to be placed in the physical memory, the size of the process becomes limited. That is, the size of the process cannot be larger than the size of the physical memory. The concept of virtual memory helps in having processes larger than the size of the physical memory. This module explains the concepts of virtual memory and demand paging, explains why page faults occur and how page faults are handled.
25.2 Virtual Memory
Even when an entire process is loaded into the main memory, the entire process may not be used. The code for handling certain error conditions may not be executed if such kind of errors do not occur. There can be unused space occupied by arrays, tables etc. Code for rarely used features may not be used. Even when entire program is used, all portions of the program may not be used at the same time. Hence it is not required for the entire process to be in the main memory. Rather, a part of the process can be in the main memory and the remaining process can be kept in the secondary storage device.
Fig.25.1 Logical address space larger than physical memory (Source: [1])
Thus, programs are not constrained by the physical memory available. More physical memory space is now available for more programs. Thus, virtual memory provides the separation of user logical memory from physical memory. Only part of a program needs to be in physical memory for execution. Logical address space can therefore be much larger than physical address space (Figure 25.1). This allows a large virtual memory to be available for programmers when only small physical memory is available. This also allows address spaces to be shared by several processes. Virtual memory can be implemented via demand paging or demand segmentation. In this module, we will discuss the issues related to demand paging.
25.3 Demand Paging
Demand paging is a paging system with swapping. Processes reside in secondary memory. When needed to be executed, processes are brought into main memory. Instead of bringing in the whole process, only the pages which are currently needed are brought in. Figure 25.2 shows program A being swapped out to the secondary storage device and program B being swapped into the main memory.
Fig. 25.2 Swap-in and swap-out of processes (Source: [1])
Since only pages which are needed are brought in, bringing in pages which will not be used at all is avoided. Because of this, less I/O is needed, less physical memory is needed, faster response is provided to users and more number of users can use the system at a particular time.
To differentiate between the pages in main memory and those on disk, the valid / invalid bit is used. If the bit is set as valid, then it means that the page is valid and is present in main memory. If the bit is set as invalid, then either the page is not valid or the page is valid but not present in the main memory. Figure 25.3 shows the use of the valid/invalid bit. The process has six valid pages A – F. All the pages are kept in the secondary storage device (disk). Of these only A, C and F are present in the main memory. The valid bit in the page table is set only for these three pages. For all the remaining pages, the valid bit is not set.
Fig. 25.3 Valid/invalid bit (Source: [1])
25.4 Page Faults
When the CPU generates a logical address, the OS checks the page table. If the valid bit is set, it means that the page is in memory and the process proceeds as normal. When the process accesses a page that is not in memory, a trap is given to the OS. This is called a page fault.
Fig. 25.4 Page fault (Source:[1])
This page fault is not due to an invalid address error. It is a result of the OS’s failure to bring the desired page into memory. When a page fault occurs, the OS looks at another internal table (usually kept in the process control block) to decide whether the reference is actually valid or invalid. If it is an invalid reference, the process is terminated. If it is a valid reference, but just not in memory, the OS proceeds as follows: The OS gets an empty frame from free-frame list, swaps the required page from the disk into the free frame, resets the internal table and the page table. In the page table, the valid bit is set to 1 and the instruction is restarted (Figure 25.4) When a page fault occurs, the process is interrupted and the state of the process is saved. After handling page fault, process is restarted in exactly the same place and state.
When a process starts executing, it is possible to start executing the process even with no page in memory. Then, in this case, even for the first instruction, there is a page fault. When all the needed pages are brought into memory, there are no more page faults. This is called pure demand paging. That is, a page of a process is never brought into memory until it is required.
Programs tend to have locality of reference. That is, when a particular region of a process is being executed, pages corresponding to that region alone will be used. For example, if a particular subroutine is being executed, the pages corresponding to that subroutine alone will be executed. Thus, it is enough to have only these pages in the physical memory during that time. This is the reason for the success of demand paging.
25.4.1 What happens if there is no free frame?
We saw in the earlier section that a page is brought into a free frame in the physical memory from the secondary storage device. But, if a free frame is not available, a frame has to be freed in the physical memory. This is called page replacement. That is, it is needed to find some page in memory, but not really in use and swap out. The needed page is then brought into this free frame. There are a number of ways in which the victim frame can be chosen, called, page replacement algorithms, which will be discussed in the next module.
25.5 Performance of Demand Paging
The performance of demand paging can be analyzed by calculating the effective memory access time. When there is no page fault, the effective access time is same as the memory access time. If page fault occurs, it is necessary to read the relevant page from disk and then access the physical memory to access the desired word.
Let p (0 £ p £ 1.0) be the probability that a page fault will occur. If p = 0, there are no page faults. If p = 1, every reference is a page fault. The effective Access Time (EAT) is calculated as
EAT = (1 – p) x memory access
+ p x (page fault overhead [swap page out + swap page in+ restart overhead])
Thus, it is seen that the effective access time depends on the page fault rate and the time required to service the page fault. A lot of overhead is involved in servicing a page fault. The following sequence of steps show the overhead involved in servicing a page fault.
25.5.1 Servicing a page fault
The steps involved in the servicing of a page fault are given below:
1. Trap to the OS
2. Save user registers and process state of the current process
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 disk
5. Issue a read from the disk to a free frame
6. Wait in a queue for the disk until read request is serviced
7. Wait for device seek and/or latency time
8. Begin the transfer of page to a free frame
9. While waiting, allocate the CPU to some other user
10. Interrupt from the disk (I/O completed)
11. Save registers and process state for currently executing process (some other process is being executed now)
12. Determine that the interrupt was from the disk
13. Correct the page table and other tables to show that the desired page is now in memory
14. Wait for the CPU to be allocated to this process again
15. Restore the user registers, process state, new page table
16. Restart the interrupted instruction
Suppose that the page fault service time in a system is 25 ms and the memory access time is 100 ns, the effective memory access time
= (1-p) x 100 + 25,000,000 x p
= 100 + 24,999,900 x p
Even if p = 1/1000, effective memory access time = 25,099.9 ns. When compared to the memory access time of 100ns, this is very large. Thus it is seen that effective memory access time is directly proportional to page fault rate. It is required that the page fault rate must be as small as possible.
25.5.2 Problem:
Consider a demand paging system with a paging disk that has an average access and transfer time of 20 milliseconds. Addresses are translated through a page table in main memory, with an access time of 1 microsecond per memory access. Thus, each memory reference through the page table takes two memory accesses. To improve this time, an associative memory is added that reduces access time to one memory reference, if the page-table entry is in associative memory.
Assume that 80 percent of the accesses are in the associative memory, and that of the remaining, 10 percent (or 2 percent of the total) cause page faults. What is the effective memory access time?
80% of the accesses are in associative memory. Therefore it is enough to have one memory access and hence the access time = 1 microseconds Of the remaining 20% of the accesses, 2% result in page faults. For this 2%, 1 microsecond is needed to access the page table in memory, 20 milliseconds to service the page fault, 1 microsecond to access the memory location. Therefore 20,002 microseconds are needed.
For the remaining 18% 2 microseconds are needed, 1 microsecond to access the page table and 1 microsecond to access the memory location.
Therefore, effective memory access time = 0.8 x 1 + 0.18 x 2 + 0.02 x 20,002
= 401.2 microsecs
25.6 Summary
In this module, we learnt the concepts of virtual memory and demand paging. Virtual memory allows the size of the process to be larger than the size of the physical memory. The entire process need not be present in the physical memory during the execution of the process. Virtual memory can be implemented using demand paging. In demand paging, a page is brought into the memory only when a reference is made to that particular page. Whenever a reference is generated, the page table is checked if the page is valid and in memory. If yes, the page is accessed as usual. Else, a page fault is generated. The OS now checks if the page is valid and not in memory. If the page is valid and not in memory, the page is brought into the memory and the instruction is restarted.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Sixth Edition, John Wiley & Sons Inc., 2003.
- Andrew S. Tanenbaum, Herbert Bos, “Modern Operating Systems”, Fourth Edition, Pearson Education, 2014.
- Gary Nutt, “Operating Systems”, Third Edition, Pearson Education, 2009.