CS3103-Lecture-7

發表於2023-03-23更新於2023-03-23

Background

  • User programs must be brought into memory and placed within a process for it to run

  • User programs go through several steps before running

Logical vs. Physical Address Space

  • The concept of a logical address space that is bound to a separate physical address space is central to memory management

    • Logical address – generated by the CPU; also called virtual address
    • Physical address – address seen by the momery unit

  • Logical and physical addresses are the same in complie-time and load-time address-binding schemes

  • Logical (virtual) and physical addresses differ in execution-time address-binding scheme

Memory-Management Unit (MMU)

  • Hardware device that maps virtual to physical address
    • The value in the relocation register is added to every address generated by a user process when sent to memory
  • The user program deals with logical addresses; it never sees the real physical addresses

Swapping

  • Process can be swapped temporarily out of memory, and brought back into memory later
    • Major part of swap time is transfer time, directly proportional to the amount of memory swapped
    • COmmonly used in many OS(i.e. UNIX, Linux, and Windows)

Dynamic Storage-Allocation Problem

  • Hole: block of available memory; holes of various size are scattered throughout memory

  • When a process arrives, it is allocated memory from a hole large enough to accommodate it

  • OS maintains: allocated partitions and free partitions(hole)

  • How to satisfy a request of size n from a list of tree holes

    • First-fit: Allocate the first hole that is big enough. Simple
    • Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size. Produces the smallest leftover hole
    • Worst-fit: Allocate the largest hole; must also search entire list. Produces the largest leftover hole

Fragmentation

  • External Fragmentation: total memory space enough to satisfy a request, but not contingous

    • Reduce external fragmentation by compaction
      • Shuffle memory contents to place all free memory together in one block
      • Possible only with dynamic relocation

  • Internal Fragmentation: allocated memory may be larger than requested memory

Memory Management Techniques

  • Two major memory management techniques
    • Paging
    • Segmentation

Paging

  • Divide physical memory into fixed-sized blocks called frames
    • size is power of 2, typically between 512 bytes and 8192 bytes
  • Divide logical memory into blocks of same size called pages
  • Keep track of all free frames
    • To run a program of size n pahes, need to find n free frames
  • Set up a page table to translate logical to physical addresses
  • External fragmentation eliminated
  • Inernal fragmentation still exists

Advantages of Paging

  • Flexibility: Supporting the abstraction of address sapce effectively

    • Don’t need assumption how heap and stack grow and are used

  • Simplicity: ease of free-space management

    • The page in address sapce and the page frame are the same size
    • Easy to allocate and keep a free list

Example: A Simple Paging

  • 128-byte physical memory with 16 bytes page frames
  • 64-byte logical address space with 16 bytes pages

Paging Example

Free Frames

Address Translation

  • Two components in the virtual address

    • Virtual page number(VPN)
    • Offset: offset within the page

  • Example: virtual address 21 in 64-byte address space

What is In the Page Table?

  • The page table is just a data structure that is used to map the virtual address to physical address

    • Simplest form: a linear page table, an array

  • The OS indexes the array by VPN, and looks up the page-table entry

Common Flags Of Page Table Entity

  • Valid Bit: Indicating whether the particular translation is valid
  • Protection Bit: Indicating whether the page could be read from, written to, or executed form
  • Present Bit: Indicating whether this page is in physical memory or on disk (swapped out)
  • Dirty Bit: Indicating whether the page has been modified since it was brought into memory
  • Reference Bit(Accessed Bit): Indicating that a page has been accessed

Page Table

  • Simple linear page table:
    • The high-order(left-most) bit is the VALID bit
    • If the bit is 1, the rest of the entry is the physical frame no. (PFN)
    • IF the nit is 0, the page is not valid

A linear Page Table Example

  • Some basic assumptions:
    • address space size 16k
      • virtual address: 14bits
  • Translate virtual address: 0x3229
    • Binary: 11 0010 0010 1001

Storing Linear Page Tables

  • Page tables for each process are stored in memory
  • Page table are too big and thus consume too much memory
    • 32-bit address space with 4-KB pages, 20 bits for VPN
      • imagine there are 100 processes: the OS would need 400MB of memory just for all those address translations!

Page Size vs Page Table Size

  • we could reduce the size of the page table in one simple way: use bigger pages
    • assume 32-bit address space wtih 16KB pages and 4-bytes page-table entry

TLB

  • Page table is stored in main memory

  • The access to the page table can speedup by using a special fast-lookup hardwawre translation look-aside buffers(TLBs)

    • TLB is small, typically between 64 and 1024 entries
    • A cache for the page table

  • TLB hardware supports parallel search

  • Address translation (A', A'')

    • If A' is found, get frame # out
    • Otherwise get frame # from page table in memory

Paging Hardware With TLB

Multi-level(Hierarchical) Page Tables

  • In order to reduce the memory overhead of page tables
  • Turns the linear page table into something like a tree.
    • Chop up the page table into page-size units
    • If an entire page of page-table entries is invalid, dont allocate that page of the page table at all
    • Use a new structure, called a page directory (outer page table)

Page Directory(Outer Page Table)

  • Advantage

    • Only allocates page-table space in proportion to the amount of address space you are using
    • The OS can grab the next free page whne it needs to allocate or grow a page table

  • Disavantage

    • Multi-level table is a small example of a time-space trade-off
    • Complexity

A Multi-level Page Table Example

  • To understand the idea behind multi-level page tables better, let’s do an example

  • Some basic assumptions:

Page Directory Index

  • The page directory needs one entry per page of the page table

    • it has 32 page-directory entries (PDEs)

  • The page-directory entry is invalid -> Raise an exception (The access is invalid)

  • The format of a page-directory entry is (8-bits)

    • VALID | PT6 … PT0

  • If the page diretory entry(PDE) is valid

    • To fetch the page table entry(PTE) from the page of the page table pointed to by this page-directory entry

  • This page-table index can then be used to index into the page of page table

Addeess Translation

  • Page directory base register (PDBR): the page number used by the page directory, e.g. 108(decimal)

  • A memory page dump:

    • shows the 32 bytes found on pages 0,1,2, and so forth. The first byte (0th byte) on page 0 has the value 0x1b, the second is 0x1d, the third 0x05, and so forth

  • Steps:

    • Use the PDBR to find the relevant page table entries for this virtual page
    • Then find if it is valid. If so, use the translation to form a final physical address. Using this address, you can find the VALUE that the memory reference is looking for. Note that the virtual addres may not be valid and thus generate a fault

  • Let’s try to translate virtual address 0x611c to physical address and fetch its value if it is a valid address

  • Step 1: Use the PDBR to find the page directory on page 108

  • Step 2: Convert virtual address 0x611c to binary (15 bits): 110000100011100

  • Step 3:page directory entry PDE
    – PDE index: 0b11000 = 0x18 = 24
    – PDE content: a1, 24th byte on page 108

    • 0xa1= 0b10100001
    • Valid bit: 1, PT (PFN): 0b0100001=0x21=33

  • Step 4: Locate memory page 33

  • Step 5: PTE
    – PTE index: 0b01000 = 0x8 = 8
    – PTE content: b5, 8th byte on page 33

    • 0xb5 = 0b10110101
    • Valid bit: 1, PFN: 0b0110101 = 0x35

  • Step 6: Physical Address
    – PFN: 0b0110101 = 53, Offset 0b11100 = 28
    – Physical Address: 0b011010111100 = 0x6bc

  • Step 7: Locate memory page 53

  • Step 8: Load Data
    – Page offset: 0b11100 = 0x1c = 28
    – Value: 08, 28th byte on page 53

    • 0x08 = 0b00001000 = 8

  • Summary:

  • Virtual Address 0x611c:
    – PDE index:0x18 (24)10 PED contents:0xa1 (valid 1, pfn 0x21 (33)10)
    – PTE index:0x8 (8)10 PET contents:0xb5 (valid 1, pfn 0x35 (53)10 )
    – Translates to Physical Address 0x6bc –> Value: 08

  • the virtual address may not be valid and thus generate a fault.
    – For example: when translating virtual address 0x3da8, PTE is not valid.

Hashed Page Tables

  • Common when address space > 32 bits
  • The virtual page number is hashed into a (small) page table
    – Contains a chain of elements hashing to same location in hash table
    – Virtual page numbers compared in this chain searching for a match. If a
    match is found, the corresponding physical frame is extracted
    • Maps a large number of keys to much fewer
      items in the hash table
      • Potential collision
      • Efficient if very few collisions
    • Each process typically only uses a small part of the entire address space

Segmentation

  • Memory-management scheme supports user view of memory
  • A program is a collection of segments
  • Each segment is a logical unit such as
    main program,
    procedure,
    function,
    method,
    object,
    local variables, global variables,
    common block,
    stack,
    symbol table, arrays
    …


Sharing of Segment

  • Different processes may share some segments
    • Similar to shared pages