OPERATING SYSTEMS
7
Virtual Memory
• Hardware and Control Structures
-Locality and Virtual Memory
- Paging
-Segmentation
-Combined Paging & Segmentation
- protection and Sharing
• Operating System Software
-Fetch Policy
-Placement Policy
-Replacement policy
-Resident set Management
Hardware and Control Structures
Characteristics of Paging and Segmentation
• Paging and Segmentation leads to measure breakthrough in
memory management.
• The two important characteristics of Paging and
Segmentation are:
1. Use of logical addressing which can be dynamically
translated to physical address. It enable process to
occupy different locations in the memory during run-
time.
2. Process can be broken down into many pages or
segments and does not have to be contiguous within
the memory space.
Hardware and Control Structures
Characteristics of Paging and Segmentation
Hardware and Control Structures
Thrashing
• Consider a situation where there many processes pieces in
the memory with less space left.
• OS can bring a piece of a process which is currently needed
and can throw another piece out to virtual memory.
• If it throws out a piece just before it is used, then it will just
have to get that piece again almost immediately from the
virtual memory.
• The situation whereby system spends most of its time
swapping pieces rather than executing instructions is known
as Thrashing
Hardware and Control Structures
Principal of locality
Principle of locality makes it possible for virtual memory
addressing to be possible and efficient. It states that
1. Program and data references within a process tend to
cluster.
2. Only a few pieces of a process will be needed over a short
period of time.
3. It is possible to make intelligent guesses about which pieces
will be needed in the future.
This suggests that virtual memory may work efficiently
Hardware and Control Structures
Virtual memory paging
• The term virtual memory is usually associated with systems
that employ paging, although virtual memory based on
segmentation exists.
• With virtual memory paging, we again have equal-size
pages of the same length as frames; however, not all pages
need to be loaded into main memory frames for execution.
• Some pages of the process reside in the virtual memory
Memory Management Requirements
Virtual memory paging
• The OS must create, and load page table of each process
into the memory
• For virtual memory paging extra bits are needed apart from
page number to indicate if the page is in main memory or
virtual memory.
• The page table entry includes a Modify (M) bit, indicating
whether the contents of the corresponding page have been
altered since the page was last loaded into main memory.
Memory Management Requirements
Page Table Structure
• The basic mechanism for reading a word from memory
involves the translation of a virtual, or logical, address to a
physical address
• Physical address, consist of frame number and offset.
• The page number, frame number and offset are saved in
the page table as Page Table Entry (PTE).
• In most systems, there is one page table per process.
• The amount of memory devoted to page tables alone could
be unacceptably high.
• Most virtual memory schemes store page tables in virtual
memory rather than real memory.
Memory Management Requirements
Page Table Structure
Memory Management Requirements
Page Table Structure
• For example, in the VAX (Virtual Address Extension)
architecture, each process can have up to 𝟐𝟑𝟏 = 𝟐 𝑮𝑩 of
virtual memory.
• If the page size is 𝟐𝟗 = 𝟓𝟏𝟐 𝑩 and the system uses 16-bit
addressing space.
• What will be the maximum size of the Page Table ?
• Maximum number of pages required is 𝟐𝟑𝟏 /𝟐𝟗 = 𝟐𝟐𝟐 .
• Therefore 𝟐𝟐𝟐 PTE are requires each taking 16-bits of
memory space.
• Hence, Page Table size= 𝟐𝟐𝟐 × 𝟏𝟔 = 𝟐𝟐𝟔 𝒃𝒊𝒕𝒔 or 8 MB
Memory Management Requirements
multı-level hierarchical page table
• If we assume byte-level addressing and 4-kB pages, 4-GB
virtual space for a process and a 32-bit addressing space.
𝟐𝟑𝟐
1 Page Table size= × 𝟑𝟐𝒃𝒊𝒕𝒔 = 𝟒𝑴𝑩
𝟐𝟏𝟐
𝟒𝑴𝑩 𝟐𝟐𝟐
2 Page Table size= 𝟐𝟏𝟐 = 𝟐𝟏𝟐
= 𝟐𝟏𝟎 × 𝟑𝟐𝒃𝒊𝒕𝒔
Memory Management Requirements
multı-level hierarchical page table
• If the size of page table is less than the size of one Frame,
then the whole page is loaded into the main memory.
• If the size of page table is greater than the size of one Frame,
then the page table is to be divided into multiple page Tables.
𝟐𝟑𝟐
1. Page Table size= × 𝟑𝟐𝒃𝒊𝒕𝒔 = 𝟒𝑴𝑩
𝟐𝟏𝟐
• This Outer Page Table would contain the address of the
Frames which contain the pages of Inner Page Table.
𝟒𝑴𝑩 𝟐𝟐𝟐
2. Page Table Entry (PTE) = 𝟏𝟐 = 𝟏𝟐 = 𝟐𝟏𝟎
𝟐 𝟐
• Therefore size of the 2. Page Table size= 𝟐𝟏𝟎 × 𝟑𝟐𝒃𝒊𝒕 = 𝟒𝒌𝑩
• So its not greater than the frame size and we can stop here.
Memory Management Requirements
multi-level hierarchical page table
• Page Table size 𝟒𝑴𝑩 is greater than the frame size 𝟒𝒌𝑩.
• The Page Table is broken down into Page Table 1 and Page
Table 2.
• Page Table 2 size is 𝟒𝒌𝑩 which is equals to the frame size
𝟒𝒌𝑩, hence wont be broken further.
• Page Table 2 is place in the main memory while Page Table 1
is placed in the virtual memory.
• Page Table 2 contains the addresses of the Page Table 1
entries which point to the physical memory addresses of the
process
Memory Management Requirements
Two-level hierarchical page table
Memory Management Requirements
inverted page table
• A drawback of the multi-level page table is that their size is
proportional to that of the virtual address space.
• Here, the page number portion of a virtual address is mapped
into a hash value using a simple hashing function.
Memory Management Requirements
inverted page table
• It consists of one-page table entry for every frame of the main
memory.
• The number of page table entries reduces to the number of
frames in physical memory
• single page table is used to represent the paging information
of all the processes.
• Each entry in the page table contains the following fields.
1. Page number
2. Process Id
3. Control bits
4. Chained pointer
Memory Management Requirements
inverted page table
Memory Management Requirements
Translation Lookaside Buffer
• Each virtual memory reference can cause two physical
memory accesses
• One to fetch the page table
• One to fetch the data
• To overcome this problem a high-speed cache is set up for
page table entries called a Translation Lookaside Buffer
(TLB).
• TLB Contains page table entries that have been most
recently used
Memory Management Requirements
Translation Lookaside Buffer
Memory Management Requirements
Translation Lookaside Buffer
Memory Management Requirements
Translation Lookaside Buffer
• Given a virtual address, processor examines the TLB
• If page table entry is present (TLB hit), the frame number is
retrieved, and the real address is formed
• If page table entry is not found in the TLB (TLB miss), the
page number is used to index the process page table.
• First checks if page is already in main memory
• If not in main memory a page fault is issued
• The TLB is updated to include the new page entry
