Transcript Virtual memory

Virtual memory
n
All the memory management policies we have discussed so far try
to keep a number of processes in memory simultaneously to allow
multiprogramming, but they require the entire process to be
loaded in memory before it can execute.
With the virtual memory technique, we can execute a process which is
only partially loaded in memory. Thus, the logical address space
may be larger than physical memory, and we can have more
processes executing in memory at a time, hence a greater degree
of multiprogramming.
n
In Virtual Memory Paging and Virtual Memory Segmentation, all
pages of a process need NOT be in the main memory. Pages are
read from disk as needed.
Fetch Policy
The fetch policy determines when a page should be brought into
main memory.
n In demand paging approach, programs reside on a swapping
device (i.e. a disk). When the OS decides to start a new process, it
swaps only a small part of this new process (a few pages) into
memory. The PT of this new process is prepared and loaded into
memory.
n If the process currently executing tries to access a page which is
not in memory, a page fault occurs, and the OS must bring that
page into memory.
n In prepaging approach, the operating system tries to predict the
pages a process will need and preload them when memory space
is available.
n
Page Replacement
When a page fault occurs, the OS finds the desired page on the
disk, but if there are no free frames, OS must choose a page in
memory (which is not the one being used) as a victim, and must
swap it out to the disk.
n It then swaps the desired page into the newly freed frame. The PT
is modified accordingly. Therefore, in servicing a page fault, the OS
performs two page transfers:
n
F Swap the victim page out,
F Swap the desired page in.
n
The answers to the following two crucial questions for demand
paging systems are important:
F How shall we select the victim page when page replacement is
required?
F How many frames should we allocate to each process?
Page Replacement Algorithms
n
A page replacement algorithm determines how the victim page(s)
is selected when a page fault occurs.
n
The aim is to minimize the page fault rate.
n
The efficiency of a page replacement algorithm is evaluated by
running it on a particular string of memory references and
computing the number of page faults.
Page Replacement Algorithms
n
Consecutive references to the same page may be reduced to a
single reference, because they won’t cause any page fault except
possibly the first one.
F Ex: (1,4,1,6,1,1,1,3) → (1,4,1,6,1,3).
n
We have to know the number of frames available in order to be
able to decide on the page replacement scheme of a particular
reference string.
n
Normally, one would expect that as number of frames increases,
the number of page faults decreases.
Example
n
With the above reference string (1,4,1,6,1,3) , if we had 4 frames,
it would cause only 4 page faults: one fault for the first reference
to each page.
√
n
√
If we had only a single frame, then the above string would cause 6
page faults, one for every new page reference.
Optimal Page Replacement Algorithm
•
With this algorithm, we replace the page that will not be used fort the
longest period of time.
•
OPT has the lowest page fault rate for a fixed number of frames
among all the page replacement algorithms.
•
OPT is not implementable in practice, because it requires future
knowledge. It is mainly used for performance comparison.
Example: Consider the following reference string:
5,7,6,0,7,1,7,2,0,1,7,1,0.
Assume there are 3 page frames:
√
√
This string causes 7 page faults by OPT
√
√
√
√
First-in First-out algorithm
• This is a simple algorithm, and easy to implement:
choose the oldest page as the victim. .
Example: Consider the following reference string:
5,7,6,0,7,1,7,2,0,1,7,1,0.
Assume there are 3 page frames:
√
√
This string causes 10 page faults by FIFO
√
√
Belady’s Anomaly
•
Normally as the number of page frames increase, the number of page
faults should decrease. However, for FIFO there are cases where this
generalization will fail! This is called Belady’s Anomaly. Notice that
OPT never suffers from Belady’s anomaly
Example: Consider the reference string: 1,2,3,4,1,2,5,1,2,3,4,5.
√
√
√
4
This string causes 9 page faults by FIFO with 3 frames
√
√
This string causes 10 page faults by FIFO with 4 frames
Least Recently Used (LRU)
•
The idea in LRU is to use recent past as an approximation of the near
future. LRU replaces that page which has not been used for the
longest period of time. So, the operating system has to associate with
each page the time it was last used.
Example: Assume that there are 3 page frames, and consider
5,7,6,0,7,1,7,2,0,1,7,1,0. .
√
√
This string causes 9 page faults by LRU
√
√