Operating System Concepts
Chapter 8 { Main Memory
Based on the 9th Edition of:
Abraham Silberschatz, Peter B. Galvin and Jreg Gagne:. Operating System
Concepts
Department of Information Technology, College of Business, Law & Governance
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Learning Objectives
To provide a detailed description of various ways of organizing
memory hardware
To discuss various memory-management techniques, including
paging and segmentation
To provide a detailed description of the Intel Pentium, which
supports both pure segmentation and segmentation with
paging
Chapter 8 { Main Memory Operating System Concepts 2
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Outline
1 Background
2 Swapping
3 Contiguous Memory Allocation
4 Segmentation
5 Paging
6 Structure of the Page Table
Chapter 8 { Main Memory Operating System Concepts 3
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background
Program must be brought (from disk) into memory and
placed within a process for it to be run
Main memory and registers are only storage CPU can access
directly
Memory unit only sees a stream of addresses + read requests,
or address + data and write requests Register access in one
CPU clock (or less)
Main memory can take many cycles, causing a stall
Cache sits between main memory and CPU registers
Protection of memory required to ensure correct operation
Chapter 8 { Main Memory Operating System Concepts 4
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background
Base and Limit Registers
A pair of base and
limit registers define
the logical address
space
CPU must check
every memory access
generated in user
mode to be sure it is
between base and
limit for that user
operating
system
0
256000
300040 300040
base
120900
limit
420940
880000
1024000
process
process
process
Chapter 8 { Main Memory Operating System Concepts 5
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background
Hardware Address Protection
base
memory
trap to operating system
monitor—addressing error
address yes yes
no no
CPU
base limit
≥ <
Chapter 8 { Main Memory Operating System Concepts 6
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background | Address Binding
Programs on disk, ready to be brought into memory to
execute form an input queue |without support, must be
loaded into address 0000
Inconvenient to have first user process physical address always
at 0000
Further, addresses represented in different ways at different
stages of a program’s life
Source code addresses usually symbolic
Compiled code addresses bind to relocatable addresses |i.e.
“14 bytes from beginning of this module”
Linker or loader will bind relocatable addresses to absolute
addresses |i.e. 74014
Chapter 8 { Main Memory Operating System Concepts 7
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background
Binding of Instructions and Data to Memory
Address binding of instructions and data to memory addresses
can happen at three different stages
Compile time: If memory location known a priori, absolute
code can be generated; must recompile code if starting
location changes
Load time: Must generate relocatable code if memory location
is not known at compile time
Execution time: Binding delayed until run time if the process
can be moved during its execution from one memory segment
to another
Need hardware support for address maps (e.g., base and limit
registers)
Chapter 8 { Main Memory Operating System Concepts 8
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background | Multistep processing of user programs
dynamic
linking
source
program
object
module
linkage
editor
load
module
loader
in-memory
binary
memory
image
other
object
modules
compile
time
load
time
execution
time (run
time)
compiler or
assembler
system
library
dynamically
loaded
system
library
Chapter 8 { Main Memory Operating System Concepts 9
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background | Logical vs. Physical Address Space
The concept of a logical address space that is bound to a
separate physical address space is central to proper memory
management
Logical address { generated by the CPU
Physical address { address seen by the memory unit
Logical and physical addresses are the same in compile-time
and load-time address-binding schemes; logical and physical
addresses differ in execution-time address-binding scheme
Logical address space is the set of all logical addresses
generated by a program
Physical address space is the set of all physical addresses
generated by a program
Chapter 8 { Main Memory Operating System Concepts 10
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background | Memory Management Unit (MMU)
Hardware device that at run time maps logical (also called
virtual) to physical address
Many methods possible. Consider simple scheme where the
value in the relocation register is added to every address
generated by a user process at the time it is sent to memory
Base register now called relocation register
MS-DOS on Intel 80×86 used 4 relocation registers
The user program deals with logical addresses; it never sees
the real physical addresses
Execution-time binding occurs when reference is made to
location in memory
Logical address bound to physical addresses
Chapter 8 { Main Memory Operating System Concepts 11
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background | Dynamic Relocation
Routine is not loaded until it is called |better memory-space
utilization; unused routine is never loaded
All routines kept on disk
in relocatable load
format
Useful when large
amounts of code are
needed to handle
infrequently occurring
cases
No special support from
the operating system is
required.

MMU
CPU memory
14346
14000
relocation
register
346
logical
address
physical
address
Chapter 8 { Main Memory Operating System Concepts 12
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Background | Dynamic Linking
Static linking { system libraries and program code combined
by the loader into the binary program image
Dynamic linking { linking postponed until execution time
Small piece of code, stub, used to locate the appropriate
memory-resident library routine
Stub replaces itself with the address of the routine, and
executes the routine
Operating system checks if routine is in processes’ memory
address |if not in address space, add to address space
Dynamic linking is particularly useful for libraries |System
also known as shared libraries
Chapter 8 { Main Memory Operating System Concepts 13
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Absolute code can be generated for .
A. compile-time binding
B. load-time binding
C. execution-time binding
D. interrupt binding
answer:
Chapter 8 { Main Memory Operating System Concepts 14
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Absolute code can be generated for .
A. compile-time binding
B. load-time binding
C. execution-time binding
D. interrupt binding
answer: A
Chapter 8 { Main Memory Operating System Concepts 14
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Absolute code can be generated for .
A. compile-time binding
B. load-time binding
C. execution-time binding
D. interrupt binding
answer: A
2 is the method of binding instructions and data to
memory performed by most general-purpose operating
systems.
A. Interrupt binding
B. Compile time binding
C. Execution time binding
D. Load-time binding
Answer:
Chapter 8 { Main Memory Operating System Concepts 14
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Absolute code can be generated for .
A. compile-time binding
B. load-time binding
C. execution-time binding
D. interrupt binding
answer: A
2 is the method of binding instructions and data to
memory performed by most general-purpose operating
systems.
A. Interrupt binding
B. Compile time binding
C. Execution time binding
D. Load-time binding
Answer: C
Chapter 8 { Main Memory Operating System Concepts 14
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Swapping
A process can be swapped temporarily out of memory to a
backing store, and then brought back into memory for
continued execution
Backing store { fast disk large enough to accommodate copies
of all memory images for all users; must provide direct access
to these memory images
Roll out, roll in { swapping variant used for priority-based
scheduling algorithms; lower-priority process is swapped out so
higher-priority process can be loaded and executed
Major part of swap time is transfer time; total transfer time is
directly proportional to the amount of memory swapped
System maintains a ready queue of ready-to-run processes
which have memory images on disk
Chapter 8 { Main Memory Operating System Concepts 15
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Swapping
Semantic View of Swapping
operating
system
swap out
swap in
user
space
main memory
backing store
process P2
process P1
1 2
Chapter 8 { Main Memory Operating System Concepts 16
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Swapping
Context Switch Time Including Swapping
If next processes to be put on CPU is not in memory, need to
swap out a process and swap in target process
Context switch time can then be very high
100MB process swapping to hard disk with transfer rate of
50MB/sec
Swap out time of 2000 ms
Plus swap in of same sized process
Total context switch swapping component time of 4000ms (4
seconds)
Chapter 8 { Main Memory Operating System Concepts 17
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Swapping
Context Switch Time Including Swapping (Cont.)
Other constraints as well on swapping
Pending I/O { can’t swap out as I/O would occur to wrong
process
Or always transfer I/O to kernel space, then to I/O device
|known as double buffering, adds overhead
Standard swapping not used in modern operating systems
But modified version common |swap only when free memory
extremely low
Chapter 8 { Main Memory Operating System Concepts 18
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Swapping on Mobile Systems
Not typically supported
Flash memory based
Small amount of space
Poor throughput between flash memory and CPU on mobile
platform
Instead use other methods to free memory if low
iOS asks apps to voluntarily relinquish allocated memory;
Read-only data thrown out and reloaded from flash if needed
Android terminates apps if low free memory, but first writes
application state to flash for fast restart
Both OSs support paging as discussed below
Chapter 8 { Main Memory Operating System Concepts 19
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Contiguous Memory Allocation
Main memory must support both OS and user processes
Limited resource, must allocate efficiently
Contiguous allocation is one early method
Main memory usually into two partitions:
1 Resident operating system, usually held in low memory with
interrupt vector
2 User processes then held in high memory |each process
contained in single contiguous section of memory
Chapter 8 { Main Memory Operating System Concepts 20
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Contiguous Memory Allocation
Relocation registers used to protect user processes from each
other, and from changing operating-system code and data
Base register contains value of smallest physical address
Limit register contains range of logical addresses each logical
address must be less than the limit register
MMU (Memory Management Unit) maps logical address
dynamically
Can then allow actions such as kernel code being transient and
kernel changing size
Chapter 8 { Main Memory Operating System Concepts 21
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Contiguous Memory Allocation
Hardware Support for Relocation and Limit Registers
CPU memory
logical
address
trap: addressing error
no
yes
physical
address
relocation
register

limit
register
Chapter 8 { Main Memory Operating System Concepts 22
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Contiguous Memory Allocation
Multiple-Partition Allocation
Degree of multiprogramming limited by number of partitions
Variable-partition sizes for efficiency (sized to a given process
needs)
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
Process exiting frees its partition, adjacent free partitions
combined
Operating system maintains information about: (i) allocated
partitions, (ii) free partitions (hole)
Chapter 8 { Main Memory Operating System Concepts 23
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Contiguous Memory Allocation
Multiple-Partition Allocation
Chapter 8 { Main Memory Operating System Concepts 24
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Contiguous Memory Allocation
Dynamic Storage-Allocation Problem
How to satisfy a request of size n from a list of free holes?
First-fit: Allocate the first hole that is big enough
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
Remark: First-fit and best-fit better than worst-fit in terms of
speed and storage utilization
Chapter 8 { Main Memory Operating System Concepts 25
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Contiguous Memory Allocation
Fragmentation
External Fragmentation { total memory space exists to satisfy
a request, but it is not contiguous
Internal Fragmentation { allocated memory may be slightly
larger than requested memory; this size difference is memory
internal to a partition, but not being used
First fit analysis reveals that given N blocks allocated, 0.5 N
blocks lost to fragmentation
1/3 may be unusable ) 50% rule
Chapter 8 { Main Memory Operating System Concepts 26
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Contiguous Memory Allocation
Fragmentation (Cont.)
Reduce external fragmentation by compaction
Shuffle memory contents to place all free memory together in
one large block
Compaction is possible only if relocation is dynamic, and is
done at execution time
I/O problem
Latch job in memory while it is involved in I/O
Do I/O only into OS buffers
Now consider that backing store has same fragmentation
problems
Chapter 8 { Main Memory Operating System Concepts 27
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 The binding scheme facilitates swapping.
A. interrupt time
B. load time
C. assembly time
D. execution time
Answer:
Chapter 8 { Main Memory Operating System Concepts 28
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 The binding scheme facilitates swapping.
A. interrupt time
B. load time
C. assembly time
D. execution time
Answer: D
Chapter 8 { Main Memory Operating System Concepts 28
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 The binding scheme facilitates swapping.
A. interrupt time
B. load time
C. assembly time
D. execution time
Answer: D
2 The roll out, roll in variant of swapping is used .
A. when a backing store is not necessary
B. for the round-robin scheduling algorithm
C. for priority-based scheduling algorithms
D. when the load on the system has temporarily been reduced
Answer:
Chapter 8 { Main Memory Operating System Concepts 28
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 The binding scheme facilitates swapping.
A. interrupt time
B. load time
C. assembly time
D. execution time
Answer: D
2 The roll out, roll in variant of swapping is used .
A. when a backing store is not necessary
B. for the round-robin scheduling algorithm
C. for priority-based scheduling algorithms
D. when the load on the system has temporarily been reduced
Answer: C
Chapter 8 { Main Memory Operating System Concepts 28
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Segmentation
Memory-management scheme that supports user view of
memory
A program is a collection of segments
A segment is a logical unit such as:
main program
procedure
function
method
object
arrays
local variables
global variables
common block
stack
symbol table
Chapter 8 { Main Memory Operating System Concepts 29
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Segmentation
User’s View of a Program
logical address
subroutine stack
symbol
table
main
program
Sqrt
Chapter 8 { Main Memory Operating System Concepts 30
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Segmentation Architecture
Logical address consists of a two tuple:
<segment-number, offset>
Segment table { maps two-dimensional physical addresses;
each table entry has:
base { contains the starting physical address where the
segments reside in memory
limit { specifies the length of the segment
Segment-table base register (STBR) points to the segment
table’s location in memory
Segment-table length register (STLR) indicates number of
segments used by a program;
segment number s is legal if s < STLR.
Chapter 8 { Main Memory Operating System Concepts 31
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Segmentation Architecture
Protection
With each entry in segment table associate:
validation bit is 0 ) illegal segment
read/write/execute privileges
Protection bits associated with segments; code sharing occurs
at segment level
Since segments vary in length, memory allocation is a
dynamic storage-allocation problem
A segmentation example is shown in the following diagram
Chapter 8 { Main Memory Operating System Concepts 32
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Segmentation Architecture
Segmentation Hardware
CPU
physical memory
s d
< +
trap: addressing error
no
yes
segment
table
limit base
s
Chapter 8 { Main Memory Operating System Concepts 33
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 is the dynamic storage-allocation algorithm which
results in the smallest leftover hole in memory.
A. First fit
B. Best fit
C. Worst fit
D. None of the above
Answer:
Chapter 8 { Main Memory Operating System Concepts 34
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 is the dynamic storage-allocation algorithm which
results in the smallest leftover hole in memory.
A. First fit
B. Best fit
C. Worst fit
D. None of the above
Answer: B
Chapter 8 { Main Memory Operating System Concepts 34
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 is the dynamic storage-allocation algorithm which
results in the smallest leftover hole in memory.
A. First fit
B. Best fit
C. Worst fit
D. None of the above
Answer: B
2 Which of the following is true of compaction?
A. It can be done at assembly, load, or execution time.
B. It is used to solve the problem of internal fragmentation.
C. It cannot shuffle memory contents.
D. It is possible only if relocation is dynamic and done at
execution time.
Answer:
Chapter 8 { Main Memory Operating System Concepts 34
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 is the dynamic storage-allocation algorithm which
results in the smallest leftover hole in memory.
A. First fit
B. Best fit
C. Worst fit
D. None of the above
Answer: B
2 Which of the following is true of compaction?
A. It can be done at assembly, load, or execution time.
B. It is used to solve the problem of internal fragmentation.
C. It cannot shuffle memory contents.
D. It is possible only if relocation is dynamic and done at
execution time.
Answer: D
Chapter 8 { Main Memory Operating System Concepts 34
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
Physical address space of a process can be noncontiguous;
process is allocated physical memory whenever the latter is
available
Avoids external fragmentation
Avoids problem of varying sized memory chunks
Divide physical memory into fixed-sized blocks called frames
|Size is power of 2, between 512 bytes and 16 MB
Divide logical memory into blocks of same size called pages
Keep track of all free frames
Chapter 8 { Main Memory Operating System Concepts 35
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
To run a program of size N pages, need to find N free frames
and load program
Set up a page table to translate logical to physical addresses
Backing store likewise split into pages
Still have Internal fragmentation
Chapter 8 { Main Memory Operating System Concepts 36
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
Address Translation Scheme
Address generated by CPU is divided into:
Page number (p) { used as an index into a page table which
contains base address of each page in physical memory
Page offset (d) { combined with base address to define the
physical memory address that is sent to the memory unit
p d
page number page offset
m – n n
For given logical address space 2m and page size 2n
Chapter 8 { Main Memory Operating System Concepts 37
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
Paging Hardware
physical
memory
f
logical
address
page table
physical
address
CPU p
p
f
d f d
f0000 … 0000
f1111 … 1111
Chapter 8 { Main Memory Operating System Concepts 38
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
Paging Model of Logical and Physical Memory
page 0
page 1
page 2
page 3
logical
memory
page 1
page 3
page 0
page 2
physical
memory
page table
frame
number
1 4 3 7
0 1 2 3
0 1 2 3 4 5 6 7
Chapter 8 { Main Memory Operating System Concepts 39
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
Paging Example |n = 2 and m = 4, i.e., 32-byte memory and
4-byte pages
logical memory
physical memory
page table
ijklmnop abcdefgh
abcdefghijklmnop
0123456789
10
11
12
13
14
15
0
0 4 8
12
16
20
24
28
1 2 3
5 6 1 2
Chapter 8 { Main Memory Operating System Concepts 40
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
Calculating internal fragmentation
Page size = 2; 048 bytes
Process size = 72; 766 bytes
35 pages +1; 086 bytes
Internal fragmentation of 2,048 – 1,086 = 962 bytes
Worst case fragmentation = 1 frame – 1 byte
On average fragmentation = 1 / 2 frame size
So small frame sizes desirable?
But each page table entry takes memory to track
Chapter 8 { Main Memory Operating System Concepts 41
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
Page sizes growing over time
Solaris supports two page sizes: 8 KB and 4 MB
Process view and physical memory now very different
By implementation process can only access its own memory
Chapter 8 { Main Memory Operating System Concepts 42
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Paging
Free Frames
(a)
free-frame list
14
13
18
20
15
13
14
15
16
17
18
19
20
21
page 0
page 1
page 2
page 3
new process
(b)
free-frame list
15
13 page 1
page 0
page 2
page 3
14
15
16
17
18
19
20
21
page 0
page 1
page 2
page 3
new process
new-process page table
0 14
123
13
18
20
Before allocation After Allocation
Chapter 8 { Main Memory Operating System Concepts 43
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 With segmentation, a logical address consists of .
A. segment number and offset
B. segment name and offset
C. segment number and page number
D. segment table and segment number
Answer:
Chapter 8 { Main Memory Operating System Concepts 44
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 With segmentation, a logical address consists of .
A. segment number and offset
B. segment name and offset
C. segment number and page number
D. segment table and segment number
Answer: A
Chapter 8 { Main Memory Operating System Concepts 44
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 With segmentation, a logical address consists of .
A. segment number and offset
B. segment name and offset
C. segment number and page number
D. segment table and segment number
Answer: A
2 Assume the value of the base and limit registers are 1200 and
350 respectively. Which of the following addresses is legal?
A. 355
B. 1200
C. 1551
D. all of the above
Answer:
Chapter 8 { Main Memory Operating System Concepts 44
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 With segmentation, a logical address consists of .
A. segment number and offset
B. segment name and offset
C. segment number and page number
D. segment table and segment number
Answer: A
2 Assume the value of the base and limit registers are 1200 and
350 respectively. Which of the following addresses is legal?
A. 355
B. 1200
C. 1551
D. all of the above
Answer: B
Chapter 8 { Main Memory Operating System Concepts 44
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table
Implementation of Page Table
Page table is kept in main memory
Page-table base register (PTBR) points to the page table
Page-table length register (PTLR) indicates size of the page
table
In this scheme every data/instruction access requires two
memory accesses. One for the page table and one for the
data/instruction
The two memory access problem can be solved by the use of a
special fast-lookup hardware cache called associative memory
or translation look-aside buffers (TLBs)
Chapter 8 { Main Memory Operating System Concepts 45
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table
Associative Memory
Associative memory parallel search
Address translation (p, d)
If p is in associative register, get frame # out
Otherwise get frame # from page table in memory
Chapter 8 { Main Memory Operating System Concepts 46
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table
Paging Hardware With TLB (Translation Look-aside Buffer)
page table
f
CPU
logical
address
p d
f d
physical
address
physical
memory
p
TLB miss
page
number
frame
number
TLB hit
TLB
Chapter 8 { Main Memory Operating System Concepts 47
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Memory Protection
Memory protection implemented by associating protection bit
with each frame to indicate if read-only or read-write access is
allowed |can also add more bits to indicate page
execute-only, and so on
Valid-invalid bit attached to each entry in the page table:
valid indicates that the associated page is in the process’
logical address space, and is thus a legal page
invalid indicates that the page is not in the process’ logical
address space
Or use page-table length register (PTLR)
Any violations result in a trap to the kernel
Chapter 8 { Main Memory Operating System Concepts 48
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Memory Protection
Valid (v) or Invalid (i) Bit in a Page Table
page 0
page 0
page 1
page 2
page 3
page 4
page 5
page n
•••
00000
0 1 2 3 4 5 6 7 8 9
frame number
0 1 2 3 4 5 6 7
2 3 4 7 8 9 0 0
v v v v v v i i
page table
valid–invalid bit
10,468
12,287
page 1
page 2
page 3
page 4
page 5
Chapter 8 { Main Memory Operating System Concepts 49
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Shared Pages
Shared code
One copy of read-only (reentrant) code shared among
processes (i.e., text editors, compilers, window systems)
Similar to multiple threads sharing the same process space
Also useful for interprocess communication if sharing of
read-write pages is allowed
Private code and data
Each process keeps a separate copy of the code and data
The pages for the private code and data can appear anywhere
in the logical address space
Chapter 8 { Main Memory Operating System Concepts 50
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Shared Pages Example
5 6 7
4 ed 2
3 ed 1
2
1 data 1
0
3 4 6 1
page table
for P
1
process P1
data 1
ed 2
ed 3
ed 1
3 4 6 2
page table
for P
3
process P3
data 3
ed 2
ed 3
ed 1
3 4 6 7
page table
for P
2
process P2
data 2
ed 2
ed 3
ed 1
8 9
10
11
data 3
data 2
ed 3
Chapter 8 { Main Memory Operating System Concepts 51
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Structure of the Page Table
Memory structures for paging can get huge using
straight-forward methods
Consider a 32-bit logical address space as on modern
computers
Page size of 4 KB (i.e., 212 bytes)
Page table would have 1 million entries (232=212)
If each entry is 4 bytes ) 4 MB of physical address space /
memory for page table alone
That amount of memory used to cost a lot
Don’t want to allocate that contiguously in main memory
Chapter 8 { Main Memory Operating System Concepts 52
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table
Hierarchical Page Tables
Break up the logical address space into multiple page tables
A simple technique is a two-level page table
We then page the page table
Chapter 8 { Main Memory Operating System Concepts 53
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table
Two-Level Page-Table Scheme
•••
•••
outer page
table
page of
page table
page table
memory
929
900
929
900
708
500
100
0 1
•••
100
708
•••
••• ••• ••• ••• ••• •••
1 ••• •••
500
Chapter 8 { Main Memory Operating System Concepts 54
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Two-Level Paging Example
A logical address (on 32-bit machine with 1K page size) is
divided into:
a page number consisting of 22 bits
a page offset consisting of 10 bits
Since the page table is paged, the page number is further
divided into:
a 12-bit page number
a 10-bit page offset
Thus, a logical address is as follows:
Chapter 8 { Main Memory Operating System Concepts 55
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Two Level Paging
Address-Translating Scheme
logical address
outer page
table
p1 p2
p1
page of
page table
p2
d
d
Chapter 8 { Main Memory Operating System Concepts 56
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | 64-bit Logical Address Space
Even two-level paging scheme not sufficient
If page size is 4 KB (i.e., 212 bytes), then
page table has 252 entries
If two level scheme, inner page tables could be 210 4-byte
entries
Address would look like
p1 p2 d
outer page inner page offset
42 10 12
Outer page table has 242 entries or 244 bytes
One solution is to add a 2nd outer page table
Chapter 8 { Main Memory Operating System Concepts 57
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | 64-bit Logical Address Space
Three-Level Paging Scheme
p1 p2 d
outer page inner page offset
42 10 12
p1 p2 p3
2nd outer page outer page inner page
32 10 10
d
offset
12
Note: The 2nd outer page table is still 234 bytes in size, and
possibly 4 memory access to get to one physical memory location
Chapter 8 { Main Memory Operating System Concepts 58
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Hashed Page Tables
Common in address spaces > 32 bits
The virtual page number is hashed into a page table. This
page table contains a chain of elements hashing to the same
location
Each element contains (i) the virtual page number (ii) the
value of the mapped page frame (iii) a pointer to the next
element
Virtual page numbers are compared in this chain searching for
a match. if a match is found, the corresponding physical
frame is extracted
Chapter 8 { Main Memory Operating System Concepts 59
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Hashed Page Tables
hash table
q s
logical address
physical
address
physical
memory
p d r d
hash p r
function • • •
Chapter 8 { Main Memory Operating System Concepts 60
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Inverted Page Table
Rather than each process having a page table and keeping
track of all possible logical pages, track all physical pages
One entry for each real page of memory
Entry consists of the virtual address of the page stored in that
real memory location, with information about the process that
owns that page
Decreases memory needed to store each page table, but
increases time needed to search the table when a page
reference occurs
Use hash table to limit the search to one or at most a few
page-table entries
Chapter 8 { Main Memory Operating System Concepts 61
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Page Table | Inverted Page Table
Inverted Page Table Architecture
page table
CPU
logical
address physical
address
physical
memory
i
pid p
pid
search
p
d i d
Chapter 8 { Main Memory Operating System Concepts 62
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Consider a 32-bit address for a two-level paging system with
an 8 KB page size. The outer page table has 1024 entries.
How many bits are used to represent the second-level page
table?
A. 10
B. 8
C. 12
D. 9
Answer:
Chapter 8 { Main Memory Operating System Concepts 63
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Consider a 32-bit address for a two-level paging system with
an 8 KB page size. The outer page table has 1024 entries.
How many bits are used to represent the second-level page
table?
A. 10
B. 8
C. 12
D. 9
Answer: D
Chapter 8 { Main Memory Operating System Concepts 63
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Consider a 32-bit address for a two-level paging system with
an 8 KB page size. The outer page table has 1024 entries.
How many bits are used to represent the second-level page
table?
A. 10
B. 8
C. 12
D. 9
Answer: D
2 True or False { Reentrant code cannot be shared.
Answer:
Chapter 8 { Main Memory Operating System Concepts 63
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Consider a 32-bit address for a two-level paging system with
an 8 KB page size. The outer page table has 1024 entries.
How many bits are used to represent the second-level page
table?
A. 10
B. 8
C. 12
D. 9
Answer: D
2 True or False { Reentrant code cannot be shared.
Answer: False
Chapter 8 { Main Memory Operating System Concepts 63
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Consider a 32-bit address for a two-level paging system with
an 8 KB page size. The outer page table has 1024 entries.
How many bits are used to represent the second-level page
table?
A. 10
B. 8
C. 12
D. 9
Answer: D
2 True or False { Reentrant code cannot be shared.
Answer: False
3 True or False { Hierarchical page tables are appropriate for
64-bit architectures.
Answer:
Chapter 8 { Main Memory Operating System Concepts 63
Background Swapping Contiguous Segmentation Paging Structure of Page Table
Quick Quiz
1 Consider a 32-bit address for a two-level paging system with
an 8 KB page size. The outer page table has 1024 entries.
How many bits are used to represent the second-level page
table?
A. 10
B. 8
C. 12
D. 9
Answer: D
2 True or False { Reentrant code cannot be shared.
Answer: False
3 True or False { Hierarchical page tables are appropriate for
64-bit architectures.
Answer: False
Chapter 8 { Main Memory Operating System Concepts 63
Background Swapping Contiguous Segmentation Paging Structure of Page Table
End of Chapter 8
Chapter 8 { Main Memory Operating System Concepts 64