Transcript Multiprocessor Memory Allocation

Operating Systems
CMPSCI 377
Lecture 12: Paging
Emery Berger
University of Massachusetts, Amherst
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
Last Time

Memory Management



Uniprogramming vs. Multiprogramming
Segments
Memory allocation



First-fit, best-fit, worst-fit...
Compaction
Relocation
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
2
Today: Paging

Motivation




Fragmentation
Page Tables
Hardware Support
Other Benefits
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
3
Segmentation, Revisited


As processes enter system, grow & terminate, OS must track
available and in-use memory
Can leave holes
 OS must decide where to put new processes
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
4
Motivation:
Problems with Segments


Processes don’t (usually) use entire space in
memory all the time
Fragmentation problematic


Internal & external
Compaction expensive
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
5
Alternative: Paging

Divide memory into fixedsized pages (4K, 8K)


Allocates pages to frames in
memory
OS manages pages


A
Moves, removes, reallocates
Pages copied to and from
disk
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
6
Example: Page Layout

How does this help?
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
7
Paging Advantages

Most programs obey
90/10 “rule”


90% of time spent
accessing 10% of
memory
Exploiting this rule:

A
A
B
B
Only keep “live” parts
of process in memory
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
8
Paging Advantages

“Hole-fitting problem” vanishes!



Eliminates external fragmentation


Logical memory contiguous
Physical memory not required to be
But not internal (why not?)
But: Complicates address lookup...
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
9
Example: Page Layout

So how do we resolve addresses?
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
10
Today: Paging

Motivation




Fragmentation
Page Tables
Hardware Support
Other Benefits
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
11
Paging Hardware

Processes use virtual addresses
 Addresses start at 0 or other known address


OS lays process down on pages
MMU (memory-management unit):



Hardware support for paging
Translates virtual to physical addresses
Uses page table to keep track of frame assigned
to memory page
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
12
Paging Hardware: Diagram
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
13
Paging Hardware: Intuition

Paging: form of dynamic relocation


Page table ¼ set of relocation registers


One per frame
Mapping – invisible to process



Virtual address bound by paging hardware to physical
address
OS maintains mapping
H/W does translation
Protection – provided by same mechanisms as in
dynamic relocation
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
14
Paging Hardware: Nitty-Gritty

Page size (= frame size):




Typically power of 2 between 512 & 8192 bytes
Linux, Windows: 4K; Solaris: 8K
Support for larger page sizes varies (e.g., 128K)
Use of powers of 2 simplifies translation of
virtual to physical addresses
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
15
Address Translation

Powers of 2:




Virtual address space:
size 2m
Page size 2n
High-order m-n bits
of virtual address
select page
Low order n bits select
offset in page
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
16
Address Translation: Example




How big is
page table?
How many bits
per address?
(assume 1 byte
addressing)
What part is p,
d?
Given virtual
address 24, do
virtual to
physical
translation
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
17
Address Translation: Example



How many bits
per address?
(assume 4 byte
addressing)
What part is p,
d?
Given virtual
address 13, do
virtual to
physical
translation
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
18
Making Paging Efficient

Where should the page table go?

Registers:


Pros? Cons?
Memory:

Pros? Cons?
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
19
Translation Lookaside Buffer (TLB)

TLB: fast, fully associative memory


Assumption: locality of reference


Stores page numbers (key) and frame (value) in
which they are stored
Locality in memory accesses )
locality in address translation
TLB sizes: 8 to 2048 entries
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
20
TLB: Diagram

v = valid bit: entry is up-to-date
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
21
Cost of Using TLB

Measure in terms of memory access cost

What is cost if:



Page table is in memory?
Page table managed with TLB?
Large TLB:


Improves hit ratio
Decreases average memory cost
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
22
Managing the TLB:
Process Initialization & Execution



Process arrives, needs k pages
If k page frames free, allocate;
else free frames that are no longer needed
OS:





puts pages in frames
puts frame numbers into page table
marks all TLB entries as invalid (flush)
starts process
loads TLB entries as pages are accessed,
replaces entries when full
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
23
Managing the TLB:
Context Switches

Extend Process Control Block (PCB) with:



Context switch:






Page table
Copy of TLB (optional)
Copy page table base register value to PCB
Copy TLB to PCB (optional)
Flush TLB
Restore page table base register
Restore TLB (optional)
Use multilevel paging if tables too big
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
24
Today: Paging

Motivation




Fragmentation
Page Tables
Hardware Support
Other Benefits
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
25
Sharing

Paging allows sharing of memory across
processes



Compiler marks “text” segment (i.e., code) of
applications (e.g., emacs) - read-only
OS: keeps track of such segments


Shared pages –different virtual addresses,
point to same physical address
Reuses if another instance of app arrives
Can greatly reduce memory requirements
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
26
Summary: Paging Advantages

Paging: big improvement over segmentation


Eliminates external fragmentation (thus
avoiding need for compaction)
Allows sharing of code pages across processes


Reduces memory demands
Enables processes to run when only partially
loaded in main memory
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
27
Summary: Paging Disadvantages

Paging: some costs

Translating from virtual addresses to physical
addresses efficiently requires hardware support



Larger TLB ) more efficient, but more expensive
More complex operating system required to
maintain page table
More expensive context switches

Why?
UNIVERSITY OF MASSACHUSETTS, AMHERST • Department of Computer Science
28