COMP310_MemoryManagement:DemandPaging

Memory Management: Demand Paging

For system using right now, most are based on paging instead of segmentation or base&bounds.

• Base&Bounds => used only for niche
• Segmentation => abandoned
  • high complexity for little gain
  • Effect approximated with paging + valid bits
• Paging => universal

Segmentation can be compacted but hard to manage. Segmentation usually used in embedded development.

Paging

Terminology:
Page: fixed-size portion of virtual memory
Frame: fixed-size portion of physical memory
Page size = Frame size
Typical size: 4k-8k (always power of 2)

• Virtual address space
  Linear from 0 up to a multiple of page size
• Physical address space
  Non-contiguous set of frames, one per page
• Virtual Address
  • Two components in the virtual address :
    VPN:Virtual page number
    Offser:offset within the page (page size = $2^{offset}$ Bytes)
  • VPN –(Address Translation(MMU))–>PFN(Physical Frame Number)
• MMU
  • Page Table
    • Page table is the data structure mapping VPN to PFN.
    • Each process has a page table. -> each time we do a context switch, the page table needs to be switched also
  • MMU need a pointer to page table in memory and the length of the page table

Advantage & Disadvantage

• Advantage: easier to implemented compared to segmentation with compaction
• Disadvantage:
  • P1: may have free(null) page = sparsely used page may appears = internal fragmentation $\Rightarrow$ external fragmentation
    The severity of this problem depends on the page size
  • P2: Low translation performance (virtuial address ->page table(in main emory)->accession(in main memory)) = reducing performance by factor of 2

Solution to P1: valid/invalid bit

We can denote the corresponding pages with a valid bit to indicate whether its used or not. (Used for valid bit, unused for invalid bit)
This actually means the page table itself no longer covers the entire virtual address space(all possible pages in thrtual memory) but the allocated pages by the process.

Solution to P2: TLB(Translation Lookaside Buffer)

TLB(Translation lookaside buffer) is a part of MMU which makes the map(translation from virtual address(page number) to physical address) fast.

Part of the page table is in the MMU(TLB). If the map is in it, we get a “hit”, thus no need to find in memory for the map again. If a miss happened, we need to find it in the memory.

Page Table is stored in main memory and MMU has a pointer to it with the length. TLB is not in main memory but in MMU.

Notice that actually finding in memory is by use TLB again.

The hardware basis of TLB
Use associative memory(special hardware)

• Regular Memory -> lookup by address
• Associative Memory -> lookup by contents & lookup in parallel(lookup all at the same time)

Key = Pageno , Value = Frameno

TLB Size
TLB is expensive and small(64-1024 entries)
Want TLB hit rate close to 100%
If TLB full, need to replace existing entry

TLB Hit Rate and Locality

• Temporal Locality -> An instruction that has been accessed will be re-accessed soon in the future
• Spatial Locality -> An instruction is accessed, then the instructions near to it will likely soon be accessed

  Accession to an array can be both an example to spatial locality and temporal locality

They are used together most of the time but may depend.

Process Switching with TLB

Problem

Inability to distinguish between pageno of different processes in TLB.

Solution

• Invalidation of TLB : invalidate all TLB entries(by valid bits) as switching
  • Pro: Simply requires one Valid Bit
  • Con: process switch expensive
  • Con: new process incurs 100% TLB misses
• Process Identifier : add process identifier to TLB entries
  • Con: complicated
  • Pro: cheaper

---

Computation for the size of TLB

Check the lecture

Explanation:
4kB Pages => The number of entries in a page is 4kB(4028).
Page table entries => number of entries in a page table
Every page table entry => the size of each table entry in the main memory

How to make Page Table Smaller?

• Big Pages
• Segmentation + Paging
• Multi-level page tables

Big Pages

Advantage: Easy to implement
Disadvantage: Larger internal fragmentation
Most systems use 4KB or 8KB pages in common sense

Segmentation + Paging

Divide address space into segments, than devide each segment into fixed-sized pages.
Virtual address divided into three portions:

seg

page number

page offsers

Advantage:

• Supports sparse address spaces
  • decrease size of page tables
  • if segment not used, not need for page table
• enable sharing
• No external fragmentation

Disadvantage:

• each segment might have large page table
• must allocate each page table contiguously

Multi-level Page Tables

Turns the linear page table into tree structure. The level is not limited.

---

Leaving the assumption

Previous discussion is based on the assumption that the whole program resides in the memory. However, now we are dropping this assumption.

• Impossible to reside a program in a memory if it’s huge
• Only needed pieces need to be resided <= load the needed pieces from the file system => many advantages(multiple programs running in a memory&load useful pieces only)

Swapping

Def:
Store the whole program temporarily on the disk to get rid of one or more processes.
Explanantion:
Processes running on the OS resides on disk; whenever the scheduler(context switching) decides one to run, the whole process switch into the memory from disk.(also the same for switching out)
Disadvantage:

• High latency since need to read from disk(~100million cycles).
• Parallelism disabled if the program switching in is huge.
  Solution:
  Demand Paging

Demand Paging

Difference with swapping:

• Swapping = all of the program is in memory or all of the program is on disk
• Demand paging = part of program is in memory

Reason for use demand paging:

1. We want to create an illusion for the program that it has a huge memory space(virual memory space >> physical memory space)
2. Shorter process startup latency
   • start process with part of them in memory (Even 1 page suffices)
3. Better use of main memory
   • Enable parellelism of running multiple programs

Location of the program:
Part of it is in memory but most of it is on disk(a special partition called backing store(only the OS has the access to the backing store)).

NOTICE: Backing store has all the page information of a program.

NOTICE: CPU only directly access memory. CPU access data on disk through OS(OS connect page to the resding backings store).

High-level Mechanism:

• Page fault:
  Program needs to access part only on disk
• Page fault handling:
  The process for the OS to handle the page fault: program suspended -> OS runs and gets page from disk -> program is restarted

1. Discover Page Fault
   Idea: Using the valid bit in page table

   • With demand paging:
     (Exception from the following situation raise error of the OS)
     Valid bit = 0: page is invalid OR page is on disk
     Valid bit = 1: page is valid AND page is in memory
     (indicates more info needed for the OS (Invalid/on-disk?))

2. Suspendisng thne Faulting Process
   Idea: Trap into the OS

   • invalid bit access generates trap
   • Process info stored into the PCB and suspend the process(to increas the efficiency of the CPU)

     Trapping: Making the switch between the user mode and the kernel mode.

3. Getting the page from the disk
   Idea: OS handles fetchs from disk

   • Allocate the free frame(if exist) in memory to the process

   • Find page on disk and transfer the page from disk to frame

     • Two tables are needed here for transferring: Extra table mapping page to backing store

   • While the disk is Busy

     • invoke scheduler to run another process
     • when disk interrupt arrives, suspend the running process and get back to page default handling

4. Completing page fault handling

   • set the introduced page to valid and assign it a frame number(renew page table)
   • set process state to ready
   • invoke scheduler => next time to run will try toaccess the page again

How to find a free frame in the main memory?
If no free frame available, pick a frame to be replaced -> invalidates its page table entry and TLB entry -> write the frame to disk

NOTICE: No worry of loosing information by replacing since all pages are stored in backing store.

How to pick the page/frame to replace?(raplacing policies)

• Random
• FIFO
• OPT
• LRU

Goal: minimizing the page fault since they slow down the program

Random (Relatively universal)
Random page is replaced.

• PRO: Easy to implement
• CON: Does not take advantage of spatial/temporal locality

FIFO
Oldest page is replaced.(The first one brough into memory)

• PRO: Easy to implement, Fair
• CON: Does not account of “hot” pages

OPT(An optimal algorithm)
Replace the page that will be referenced the furthest in the future.(OPT insetad of approximated OPT)

• PRO: Provably optimal
• CON: Hard to implement(Can’t predict)

  OPT always acts as a basis of comaprison for other algorithms

LRU(Least Recently Used)
Use the past information to predict future usage

• PRO: Approximate OPT
• CON: Hard to implement, does not handle all workloads well
  

是否virtual address包含了在硬盘上的部分而并没有对于物理内存形成一个完全的一一映射？