Memory Management and Virtual Memory

Memory Accesses Time

  • Effective Memory Access Time

    • Associative Lookup = T_{tlb} time unit

    • TLB hit ratio = h - percentage of times that a page number is found in the associative registers

      • T{hit} = T{tlb} + T_{mem}

      • T{miss} = T{tlb} + T{mem} + T{tlb_update} + T_{mem}

      • T{miss} = T{tlb} + T_{mem} + \text{Tmem access page table} + \text{access data}

    • Effective Access Time = h * T{hit} + (1-h) * T{miss}

  • Example Calculation

    • Single-level paging scheme.

    • TLB has 32 entries.

    • TLB access time is 10 ns; memory access time is 200ns.

      • Time to access data in memory with a TLB hit: 10 ns + 200 ns = 210 ns

      • Time to access data in memory with a TLB miss: 10 ns + 200 ns + 200 ns = 410 ns

      • Effective memory-access time with a TLB hit ratio of 80%:

        • 0.8 * 210 + 0.2 * 410 = 168 + 82 = 250 \text{ ns}

      • Minimal hit ratio to guarantee an effective access time of at most 220ns:

        • 220 = h * 210 + (1-h) * 410

        • 220 = 210h + 410 - 410h

        • -190 = -200h

        • h = 0.95

Memory Protection

  • Associate a protection bit with each frame to indicate if read-only or read-write access is allowed.

  • Valid-invalid bit attached to each entry in the page table:

    • "valid" indicates that the associated page is in the process’ logical address space, and is thus a legal page.

    • "invalid" indicates that the page is not in the process’ logical address space.

    • Or, use page-table length register (PTLR).

  • Any violations result in a trap to the kernel.

Shared Pages

  • Shared code: one copy of read-only (reentrant) code shared among processes.

  • Private code and data: Each process keeps a separate copy of the code and data.

Hashed Page Table

  • The virtual page number is hashed into a page table.

  • What happens if two page numbers are hashed to the same location?

Clustered Page Tables

  • Similar to hashed page tables.

  • Each entry refers to several pages (such as 16) rather than 1.

    • Especially useful for sparse address spaces (where memory references are non-contiguous and scattered).

Inverted Page Table Architecture

  • Track all physical pages.

  • One entry for each frame in physical memory.

  • Entry: pid + page#.

  • Pros: Decreases memory needed to store each page table.

  • Cons: Increases time needed to search the table.

  • TLB.

  • Use a hash table to improve performance of the inverted page table.

Summary

  • Hierarchical Page Tables

  • Translation Look-aside Buffers (TLBs)

  • Effective Memory Access Time

  • Hashed Page Table

  • Inverted Page Table Architecture

OS Policies for Virtual Memory

Segment Organization

  • Each segment table entry contains the starting address of the corresponding segment in main memory and the length of the segment.

  • A bit is needed to determine if the segment is already in main memory.

  • Another bit is needed to determine if the segment has been modified since it was loaded in main memory.

Segmentation System Exercise

  • Address translation process in a segmentation system.

  • Virtual Address (Seg #, Offset = d)

  • Physical Address = Base + d

  • Segmentation mechanism involves using a segment table with Length and Base, and a Segment Table Ptr.

Combining Paging and Segmentation

  • Each segment contains multiple pages.

  • A user’s address space is broken up into a number of segments.

  • Each segment is broken up into a number of fixed-sized pages.

  • Each page is equal in length to a main memory frame.

  • Segmentation is visible to the programmer.

  • Paging is transparent to the programmer.

Address Translation in a Segmentation/Paging System

  • Virtual Address: Seg #, Page #, Offset

  • Segmentation Mechanism:

    • Segment Table: Seg# -> Frame #

  • Paging Mechanism:

    • Page Table: Page# -> Offset
      Combined Segmentation and Paging: Virtual Address breakdown into Segment Number, Page Number, and Offset. Segment Table Entry includes Control Bits, Length, and Segment Base. Page Table Entry includes control bits and Frame Number.

Protection and Sharing

  • Segmentation lends itself to the implementation of protection and sharing policies.

  • Each entry has a base address and length so inadvertent memory access can be controlled.

  • Sharing can be achieved by segments referencing multiple processes.

Memory Management Design

  • The design of the memory management depends on:

    • whether or not to use virtual memory techniques

    • the use of paging or segmentation or both

    • the algorithms employed for various aspects of memory management

Virtual Memory OS Policies

  • Fetch Policy:

    • Demand paging

    • Prepaging

  • Placement Policy

  • Replacement Policy:

    • Basic Algorithms:

      • Optimal

      • Least recently used (LRU)

      • First-in-first-out (FIFO)
        *Clock

    • Page Buffering

  • Resident Set Management:

    • Resident set size:

      • Fixed

      • Variable

    • Replacement Scope:

      • Global

      • Local

  • Cleaning Policy:

    • Demand

    • Precleaning

  • Load Control:

    • Degree of multiprogramming

Fetch Policy

  • Determines when a page should be brought into memory.

  • Two main types:

    • Demand Paging

    • Prepaging

Demand Paging

  • Brings pages into main memory when a reference is made to a location on the page.

  • Many page faults when process is first started.

  • After more and more pages are brought in, the principle of locality suggests that most future references will be to pages that have recently been brought in, and page faults should drop to a very low level.

Prepaging

  • Pages other than the one demanded by a page fault are brought in.

  • Exploits the characteristics of most secondary memory devices.

  • Downside: Ineffective if extra pages are not referenced.

  • If pages of a process are stored contiguously in secondary memory it is more efficient to bring in a number of pages at one time.

Placement Policy

  • Determines where in real memory a process piece is to reside.

  • Important design issue in a segmentation system.

  • Paging or combined paging with segmentation placing is irrelevant because hardware performs functions with equal efficiency.

  • For NUMA systems an automatic placement strategy is desirable.

Replacement Policy

  • Deals with the selection of a page in main memory to be replaced when a new page must be brought in.

  • Objective: the page that is removed should be the page least likely to be referenced in the near future.

  • The more elaborate the replacement policy the greater the hardware and software overhead to implement it.

Frame Locking

  • When a frame is locked the page currently stored in that frame may not be replaced.

  • Pages that should be locked:

    • Kernel of the OS as well as key control structures are held in locked frames.

    • I/O buffers and time-critical areas may be locked into main memory frames.

  • Locking is achieved by associating a lock bit with each frame.

Basic Algorithms

  • Optimal

  • Least recently used (LRU)

  • First-in-first-out (FIFO)

  • Clock

Least Recently Used (LRU)

  • Replaces the page that has not been referenced for the longest time.

  • By the principle of locality, this should be the page least likely to be referenced in the near future.

Summary - OS Software

  • Hardware and control structures

  • Combined paging and segmentation

  • Protection and sharing

  • OS software

  • Fetch policy

  • Placement policy

  • Replacement policy

  • Resident set management

LRU Cache Implementation

  • Implement an LRU cache.

  • One approach is to tag each page with the time of last reference.

    • This requires a great deal of overhead.

First-In-First-Out (FIFO)

  • Treats page frames allocated to a process as a circular buffer.

  • Pages are removed in round-robin style.

  • Simple replacement policy to implement.

  • Page that has been in memory the longest is replaced.

Clock Policy

  • Requires the association of an additional bit with each frame: referred to as the use bit.

  • When a page is first loaded in memory or referenced, the use bit is set to 1.

  • The set of frames is considered to be a circular buffer.

  • Any frame with a use bit of 1 is passed over by the algorithm.

  • Page frames visualized as laid out in a circle.

Comparisons of Page Replacement Algorithms

  • Page Faults per 1000 References

  • Optimal is the lowest, then LRU, then Clock, then FIFO

Resident Set Management

  • The OS must decide how many pages to bring into main memory.

    • The smaller the amount of memory allocated to each process, the more processes can reside in memory.

    • Small number of pages loaded increases page faults.

    • Beyond a certain size, further allocations of pages will not effect the page fault rate.

Resident Set Size

*Fixed-allocation: gives a process a fixed number of frames in main memory within which to execute. When a page fault occurs, one of the pages of that process must be replaced.
*Variable-allocation: allows the number of page frames allocated to a process to be varied over the lifetime of the process.