Computer Science Questions: Process Synchronization-Scheduling/Threads

Main Memory: Part 2 Paging

Paging • Problem: Contiguous allocation schemes contribute

to suboptimal memory utilization due fragmentation. Can we do better?

Paging • Solution: Divide physical memory into small

fixed units called frames • Process virtual address space is divided up into

similarly sized chunks called pages • Pages are loaded into memory frames

• This approach used by current operating systems

Paging Advantages • No external fragmentation • Physical address space is noncontiguous – Process pages need not occupy adjacent frames

• Process memory usage is dynamic – Memory footprint can change at execution time

• Enables virtual memory – More on this next time

Paging Disadvantages • Mapping pages to frames creates overhead – Requires memory for storing page tables – Every memory access requires extra work

• Internal fragmentation still possible – Example: a process uses 5 4KB pages, 5th page stores one

byte – Tradeoff of overhead vs. memory efficiency

• Requires additional complexity in hardware and OS implementations

Basic Method • Addresses generated by the CPU have two parts: – Page number(p): an index into a page table which contains the

base addresses of all pages in physical memory. – Page offset (d): the offset within the page.

CPU p d

f

pages

Page table

f d

Virtual address

Physical address

Physical memory

frames

d

MMU/Paging Hardware:

f

Paging Example • Paging model of virtual and physical memory:

1 4 3 7

Page table

Page 0

Page 1

Page 2

Page 3

Virtual memory

Page 0

Page 2

Page 1

Page 3

0

1

2

3

4

5

6

7

0 1 2 3

Physical memory

Process Load Time • When a process arrives, the OS allocates physical frames for

each virtual page and creates a process page table

Before allocation After allocation

Page Size

• Defined by the hardware • Typically a power of 2 • Usually ranges between 512 bytes – 16 MB – 4KB is typical size for Intel based environments

• Given virtual address space size 2m and page size 2n, the virtual address has the following format:

page number (p) offset (d)

m - n n

Page Size Considerations • Small Pages – Advantages: • Less internal fragmentation • Better fit for various data structures, code

sections – Disadvantage: • Program needs more pages ➔ has larger page

table • Large pages: opposite of small pages.

Paging Example • Paging example for a 32-byte physical memory with

4-byte pages and 16-byte virtual address space We need 4 bits to address any byte in a 32-byte sized memory.

We need 2 bits to specify an offset within a 4-byte page.

This leaves 4-2=2 bits to specify the page number.

page # offset

4 bits

2 bits 2 bits

Paging Example Cont. Example: process wishes to access byte f.

1. Virtual address of f is: 5 (0101 in binary). This is the address the process will request.

2. Split the address into page-offset format:

Page number: 001 = 1 Page offset: 01 = 1

According to the page table virtual page 1 is mapped to physical frame 6. Hence, we access offset 1 in physical frame 6.

01 01

4 bits

2 bits 2 bits

About Page Tables • Page tables are usually stored in the main

memory • Page table pointer register (PTBR): stores the

beginning of the process page table. • During context switch PTBR is changed to

point to the page table of the newly scheduled process.

• Memory protection: a process cannot access pages outside of its page table

Paging Performance • Problem: accessing in-memory data/instructions

with in-memory page tables requires two memory accesses – slow! 1. To lookup the physical address 2. Access the data at the address

Paging Performance • Solution: Use caching! • Modern systems contain Translation Look-Aside

Buffers – Specialized, small, fast-lookup hardware caches, called

• Used to cache a subset of page table entries

Translation Look-Aside Buffers (TLBs) • Associative high-speed memory consisting of TLB entries: – Tag: usually the page number – Value: the corresponding frame

• During lookup, a given key is compared against all keys in parallel – if match return the associated value is returned

• If all entries are full, some entries must be evicted before adding new ones (many eviction algorithms exist).

• Some TLBs allow entries to be wired down – i.e. prevent from being evicted.

Translation Look-Aside Buffers (TLBs) • Using TLBs for address translation:

• TLB hit - page number is in the TLB; return the corresponding frame number

• TLB miss - page number is not in the TLB; look up the frame number the page table

Page # Frame #

Paging hardware with TLB

Address Space Identifiers (ASIDs) • Problem: Because each process has its own page

table, during context switch all TLB entries must be invalidated i.e. flushed.

Address Space Identifiers (ASIDs) • Solution: Store address-space identifiers (ASIDs) that

identify the process each TLB entry belongs. • ASIDs uniquely identifies each process to provide

address-space protection • During address translation, the ASID of the process and

the page number must both match those in the TLB entry • No need to flush the TLB on every context switch – Saves overhead of flushing cache – Can take advantage of what is still there the next time the

process runs

Page Sharing • Problem: It is inefficient for every process to have its

own copy of the same code in memory

Page Sharing • Solution: Use concept of protection bits to

allow sharing of pages – Stored within the page table

Protection • Access permission:

– Associate read-write bits with each frame number – If a process attempts to write a read-only page, the attempt is

trapped to the OS

• Valid-invalid bit: – Set: page part of the virtual memory space of the process – Not set: page not part of the virtual memory space – This bit also serves another purpose covered next chapter

• Page-table length Register (PTLR) – hardware that indicates size of a process page table – Checked against every logical address to verify it is in valid range – Conserves memory by limiting page table entries

Protection • Example of valid-invalid bit: system with 14-bit address space

(0-16383) and program that uses addresses 0 to 10468.

Shared Pages • Pages containing re-entrant (i.e. read-only) code may be

shared amongst processes – Example: two notepad processes will have different data but

the same code; hence the pages containing the code may be shared between the processes

• Shared code must appear in the same location in the virtual address space of all processes

• Also applies to run time libraries (DLLs) • Data may also be shared, recall IPC Shared Memory – More on this in virtual memory chapter

Shared Pages • Example: 3 editor processes sharing pages containing

identical code:

Structure of Page Tables

• Problem: page tables can be excessively large! • Example: a hypothetical system: – 32-bit virtual address space. – 4 KB (212) sized pages. – 4 byte per page table entry. – # of page table entries = 232/212 = 1 million. – Page table size = 4 bytes * 1 million = 4 MB. – Every process requires 4 MB of contiguous physical memory to

store the page table!

Structure of Page Table • Solution: Reduce page table size • Options: – Hierarchical page tables – Hashed page tables

Hierarchical Paging • Idea: page the page table! – Break up the virtual address space into multiple page

tables – x86 and x86-64 architectures use this model – Example: for a system with a 32-bit virtual address space

and 4 KB pages, we can use a two-level page table

Hierarchical Paging Example • Address translation in a two-level page table: – Virtual address format:

– p1: index into the outer page table. – p2: displacement within the page of the outer page table. – d: offset within the page.

p1 p2 d

10 bits 10 bits 12 bits

Page number Page offset

Hierarchical Paging Diagram • A two-level page table:

Hierarchical Paging • Two-level page table is inefficient for 64-bit systems. • Example: a system with a 64-bit virtual address space 4 KB

(212) pages, and 4-byte page table entries: – Inner page table: 210 entries; entry size = 4-bytes

• All entries can be stored using a single physical page.

– Outer page table: 242 entries (244 bytes) – too large!

– A slightly better idea (still bad): use a 3-level page table:

p1 p2 d

42 bits 10 bits 12 bits

outer page offsetinner page

p1 p2 d

32 bits 10 bits 12 bits

2nd outer page offsetinner page p2

10 bits

outer page

Hierarchical Paging • For a 64-bit system may need up 7-levels of paging! – Requires 7 memory accesses to translate each virtual address

• x86-64 systems currently limit addressable space to 248 – Uses four levels of paging

Hashed Page Tables • Hash value: virtual page number. • Table entry: a linked list of elements that hash to the same

location • Each element contains 3 fields: – The virtual page # – The value of the mapped page frame – Pointer to the next element

• Address translation algorithm: – 1. Virtual page number is hashed into the page table. – 2. Find the element in the linked list that has a matching virtual

page number. – 3. Return the page frame address within the element.

Hashed Page Tables