Please disable adblock to view this page.

← Go home

Virtual Memory

virtual-memory

October 29, 2016
Published By : Pratik Kataria
Categorised in:

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

virtual-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

lazy-swapper-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:
invalid-valid-bit

Page table when some pages not in main memory

page-missing

Page Fault

Access to page marked invalid causes Page Fault

  1. Operating system looks at another table to decide:
    • Invalid reference -> abort
    • Just not in memory
  2. Get empty frame
  3. Swap page into frame
  4. Reset tables
  5. Set validation bit = v
  6. Restart the instruction that caused the page fault

Steps in Handling a Page Fault

handling-page-fault

Need for Page Replacement

need-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

graph-page-faults-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
fifo-page-replace
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
belady-anomaly

Optimal Page Replacement

optimal-page-replacement

Optimal Algorithm

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)
lru-page-replacePage 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

thrashing

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 a budding programmer, web designer and developer.