COMS W4118 Operating Systems I

Introduction to Paging

Motivating memory management

Virtual Address Space

Recall 32-bit virtual address space diagram from L09-syscall:

While each process has its own virtual address space, multiple virtual address spaces coexist in physical memory at any given time.

Virtual pages (usually 4KB) of the virtual address space are mapped to physical frames of physical memory.

Clearly, virt-addr != phys-addr. How does the OS manage memory mappings so that virtual memory accesses are transparently converted to physical memory access?

Memory management goals

Sharing: multiple processes should coexist in physical memory.

Transparency: a given process shouldn’t be aware about sharing physical memory. shouldn’t be responsible for performing translations or protection checks.

Protection: processes shouldn’t be able to access memory belonging to other processes or kernel (unless you specifically request sharing, e.g. MAP_SHARED via mmap())

Efficiency:

• we expect reasonable performance. surely every pointer dereference doesn’t trap into the kernel
• OS and hardware must be cooperating to implement virtual address translation
• memory allocation shouldn’t be wasteful. aim to prevent fragmentation

Fragmentation

Refers to the inefficient use of storage space. Consider a memory allocator whose job it is to allocate chunks of memory from a region of free space:

Internal fragmentation: the memory allocator shouldn’t allocate needlessly large chunks. If space inside of allocated chunks goes unused, then it could’ve been used for another allocation.

External fragmentation: as chunks are allocated and freed, the allocator must carefully choose where to allocate chunks from. Small gaps between allocated chunks add up over time. While there may be X bytes of free space, those X bytes may not be contiguous, meaning that the allocator can’t create a chunk of X bytes.

Implementing memory management

Memory mangement unit (MMU)

CPU works with MMU to translate virtual addresses to physical addresses at every reference during runtime. The translation is performed by the hardware, but it depends on mappings set up by the OS. The MMU will also check the validity of the access (e.g. permissions).

Segmentation

Naive solution to memory management:

Let’s just place the entire virtual address space contiguously in physical memory!

Problem: huge unused region between heap and stack (internal fragmentation).

Let’s try mapping each region of virtual memory independently:

Each region is referred to as a segment, which has an associated base address and size. Translate virtual address to physical address by interpreting virtual address as two parts:

• segment selector bits
• offset bits

Sample 14-bit virtual address: 11000010010010
Assuming max segment size is 4KB (need 12 bits for offset).

        1    1        000010010010
|--segment selector--|---offset---|

        +----------+-------+-------+
        | segment  | base  | size  |
        +----------+-------+-------+
        |    00    |  6KB  |  2KB  |
        +----------+-------+-------+
        |    01    |  8KB  |  2KB  |
        +----------+-------+-------+
        |    10    |  12KB |  2KB  |
        +----------+-------+-------+
        |    11    |  16KB |  2KB  |
        +----------+-------+-------+

physical address: segment base + offset

Use segment selector bits to index into segment table to retrieve segment base. Derive physical address by adding offset bits to segment base. Check for valid access by comparing with size – an invalid access is referred to a segmentation fault (this is where the term comes from!).

Problems with segmentation:

• What if a segment (e.g. stack/heap) grows large and collides with another segment?
• External fragmentation: free space trapped between allocated segments

Segmentation is not widely used today.

Towards paging

Goals

• eliminate fragmentation
• don’t allocate memory that won’t be used
• enable fine-grained sharing

Paging

Goals

1. Eliminate fragmentation
2. Don’t allocate memory that won’t be used
3. Enable fine-grained sharing

Let’s divide virtual and physical memory into fixed-sized pages.

Translation

Similar concept to to segmentation using selector bits.

Interpret virtual address as two parts:

• virtual page number (VPN)
• page offset

Translate VPN into physical frame number PFN using page table.

phys_addr = page_table[virt_addr / page_size] + virt_addr % page_size

VPN is the index into the page table to retrieve page table entry (PTE). PFN (physical frame number), contained within PTE is the index into physical memory to retrieve physical frame.

Another example, with PFNs and PFNs filled in:

Another one, focusing on page table arithmetic:

Assume 8-bit virtual address space, 10-bit physical address space (physical address space is larger than virtual address space, more RAM than virtual memory), and each page is 64 bytes.

• How many virtual pages per process?
  • Can address 2^8 = 256 of virtual bytes
  • 256B / 64B = 4 virtual pages
• How many physical frames in RAM?
  • Can address 2^10 = 1024 of physical bytes
  • 1024B / 64B = 16 physical frames
• How many entries in per-process page table?
  • Since each process has 4 virtual pages, need 4 entries to translate each one to a frame

• Given the following page table, translate the virtual address 241 to a physical address.

  VPN  PFN
      +---+
  0   | 2 |
      +---+
  1   | 5 |
      +---+
  2   | 1 |
      +---+
  3   | 8 |
      +---+
  

  Represent 241 in binary: 0b11110001. Each process has 4 entries in its page table, so use upper 2 bits 11 to index into page table. VPN 3 translates to PFN 8 (0b1000). Use remaining 6 bits to address into frame (need 6 bits to address into 64B frame.)

  Alternatively, divide virtual address by page size to get VPN: 241 / 64 == 3
  VPN 3 translates to PFN 8.
  Modulo virtual address by page size to get offset: 241 % 64 == 49

  PFN 8: 0b1000 == 8
  Offset: 0b110001 == 49
  Physical address: 0b1000110001 == (8 * 64) + 49 == 561

  Generally speaking for 1-level page table, m-bit virtual address, n-bit physical address, k-bit page size:

  • num virtual pages: 2 ^ (m - k)
  • num physical pages: 2 ^ (n - k)
  • num entries in page table: 2 ^ (m - k)
  • VPN: va / 2^k
  • offset: va % 2^k
  • PFN: page_table[VPN]
  • pa: PFN * 2^k + offset

Page protection

Each page table entry also carries some metadata bits.

Different architectures have different bits, but for example we could have:

• present (p): whether or not this mapping is active. this virtual page is not mapped to physical memory
• writable (w): whether or not this page can be written to. some architectures have readable/executable bits too
• user (u): can this page be accessed by userspace, i.e. to protect kernel pages from user programs

We’ll see more protection bits later on..

High-level hardware implementation

• Hardware has a dedicated Page Table Base Register (PTBR) that points to the base of the page table
  • e.g. cr3 register in x86
• OS also needs to manage the page table – stores the base address in the process control block (PCB)
  • e.g. task_struct in Linux
• PTBR is updated with new page table base address on context switch

Page sharing

We previously learned about shared mappings when we talked about mmap() – different processes can share the same memory regions. How does this work with page tables?

The processes sharing some memory probably will have different virtual addresses for those regions, but their page tables will translate those virtual addresses to the same physical addresses to ensure the two processes actually refer to the same physical memory.

Copy-on-write (COW)

Page sharing allows us to implement fork() a little more efficiently. Our previous understanding of fork() was that the parent and child process receive independent copies of the virtual address space. Copying the entire address space is incredibly expensive and there’s a good chance that the child may not even modify all the pages from the parent’s address space.

Optimization: exploit VA to PA indirection!
Mark forked pages as COW. Parent and children will share them, but as soon as one of them tries to write to a shared page, make an independent copy and update page tables.

Right after fork():

P2 writes to its VP3 causing an independent copy of PF7 to be made, notice P1 and P2 now refer to different frames for their VP3:

Issues with single level page table

Efficiency: Data access now seems to require two memory accesses… extra access for page table.

Memory Usage: Page table consumes unreasonable amount of space!
Consider 32-bit virtual address space (4GB), 4KB page size, page table entry size of 4B.

• num virtual pages: 2 ^ 32 / 2 ^ 12 == 2 ^ 20 == 1M
• Need page table entry per virtual page: 1M pages * 4B entry == 4MB per process?!

We’ll see how to solve these issues in the next couple of lectures…

---

Last updated: 2023-03-22