Virtual Memory
October 29, 2016
Categorised in: Operating System Design
VIRTUAL MEMORY
Virtual Memory is a technique that allows the execution of processes that may not be completely in memory
Virtual memory – separation of user logical memory from physical memory.
- Only part of the program needs to be in memory for execution
- Logical address space can therefore be much larger than physical address space
- Allows address spaces to be shared by several processes
Virtual memory can be implemented via:
- Demand paging
- Demand Segmentation
Virtual Memory that is larger than Physical Memory
Advantages of execution of program loaded partially in Memory
A program is no longer be constrained by amount of physical memory available
As each program takes less physical memory to execute, more program can be executed simultaneously
Less I/O needed to load or swap each user program, so user program run faster
Demand Paging
Bring a page into memory only when it is needed
- Less I/O needed
- Less memory needed
- Faster response
- More users
Lazy swapper – never swaps a page into memory unless page will be needed
– Swapper that deals with pages is a pager
Lazy Swapper or Pager
Basic Concept
The basic idea behind paging is that when a process is swapped in, the pager only loads into memory those pages that it expects the process to need
Pages that are not loaded into memory are marked as invalid in the page table, using the invalid bit.
If the process only ever accesses pages that are loaded in memory ( memory resident pages ), then the process runs exactly as if all the pages were loaded in to memory.
Valid/Invalid Bit
With each page table entry a valid–invalid bit is associated (v in-memory, i not-in-memory)
Initially valid–invalid bit is set to i on all entries
Example of a page table snapshot:
Page table when some pages not in main memory
Page Fault
Access to page marked invalid causes Page Fault
- Operating system looks at another table to decide:
- Invalid reference -> abort
- Just not in memory
- Get empty frame
- Swap page into frame
- Reset tables
- Set validation bit = v
- Restart the instruction that caused the page fault
Steps in Handling a Page Fault
Need for Page Replacement
Performance of Demand Paging
Page Fault Rate 0 <= p <= 1.0
– if p = 0 no page faults
– if p = 1, every reference is a fault
Effective access time=(1-p) x ma+ p x page fault time
PAGE REPLACEMENT
Page replacement – find some page in memory, but not really in use, swap it out
-algorithm
-performance – want an algorithm which will result in minimum number of page faults
Basic Page Replacement Algorithm
Find the location of the desired page on the disk, either in swap space or in the file system.
Find a free frame:
- If there is a free frame, use it.
- If there is no free frame, use a page-replacement algorithm to select an existing frame to be replaced, known as the victim frame.
- Write the victim frame to disk. Change all related page tables to indicate that this page is no longer in memory.
Read in the desired page and store it in the frame. Adjust all related page and frame tables to indicate the change.
Restart the process that was waiting for this page.
Graph of Page Faults versus the number of Frames
FIFO Page Replacement
Page which comes first should be replaced first
Consider reference string
7,0,1,2,0,3,0,4,2,3,0,3,1,2,0,1,7,0,1
Page Faults = 15
Belady’s Anomaly
FIFO Illustrating Belady’s Anomaly with string
1,2,3,4,1,2,5,1,2,3,4,5
Optimal Page Replacement
Optimal Algorithm
LRU Page Replacement
Replace the page that has not been used for longest period of time
This strategy is approximation to optimal algorithm (looking backward in time)
Page Faults = 12
Global vs Local Allocation (for Replacement of pages)
Global replacement – process selects a replacement frame from the set of all frames; one process can take a frame from another
Local replacement – each process selects from only its own set of allocated frames
THRASHING
If a process does not have “enough” pages, the page-fault rate is very high. This leads to:
- low CPU utilization
- operating system thinks that it needs to increase the degree of multiprogramming
- another process added to the system
Thrashing – a process is busy swapping pages in and out
Principle of Locality
Program and data references within a process tend to cluster
Only a few pieces of a process will be needed over a short period of time
Possible to make intelligent guesses about which pieces will be needed in the future
This suggests that virtual memory may work efficiently
Pratik Kataria is currently learning Springboot and Hibernate.
Technologies known and worked on: C/C++, Java, Python, JavaScript, HTML, CSS, WordPress, Angular, Ionic, MongoDB, SQL and Android.
Softwares known and worked on: Adobe Photoshop, Adobe Illustrator and Adobe After Effects.