Memory Management Principles in Operating Systems
C
S
E
1
2
0
P
r
i
n
c
i
p
l
e
s
o
f
O
p
e
r
a
t
i
n
g
S
y
s
t
e
m
s
S
p
r
i
n
g
2
0
1
7
Lecture 11: Memory
Management
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
2
Next few lectures are going
to
cover memory
management
Goals
of
memory management
To provide a convenient abstraction for
programming
To allocate scarce memory resources among competing
processes to maximize performance with minimal
overhead
Mechanisms
Physical and virtual addressing
(1)
Techniques: partitioning, paging, segmentation
(1)
Page table management, TLBs, VM tricks
(2)
Policies
Page replacement algorithms
(3)
L
e
c
t
u
r
e
O
v
e
r
v
i
e
w
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
3
Virtual memory
warm-and-fuzzy
Survey
techniques
for
implementing virtual
memory
Fixed and variable
partitioning
Paging
Segmentation
Focus on hardware support and lookup
procedure
Next
lecture
we’ll go into sharing, protection,
efficient
implementations, and other VM tricks and
features
V
i
r
t
u
a
l
M
e
m
o
r
y
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
4
The
abstraction
that the OS
provides
for
managing
memory is
virtual
memory
(VM)
Virtual memory enables a program to execute with less than its
complete data in physical memory
»
A
program
can
run on
a
machine with less memory
than
it
“needs”
»
Can also run on
a
machine with “too much” physical
memory
Many programs do not need all of their code and data at once
(or ever) – no need to allocate memory for
it
OS will adjust amount of memory allocated to a process based
upon its
behavior
VM requires hardware support and OS management algorithms
to pull it
off
Let’s go back
to
the
beginning…
I
n
t
h
e
b
e
g
i
n
n
i
n
g
…
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
5
Rewind
to
the days of “second-generation”
computers
Programs use
physical addresses
directly
OS loads job, runs it, unloads it
Multiprogramming changes all
of
this
Want multiple processes in memory
at
once
»
Overlap I/O and CPU
of
multiple
jobs
Can do it a number of
ways
»
Fixed and variable partitioning, paging,
segmentation
Requirements
»
Need protection
– restrict
which addresses jobs can
use
»
Fast
translation
–
lookups need to be
fast
»
Fast
change
–
updating
memory
hardware on
context
switch
V
i
r
t
u
a
l
A
d
d
r
e
s
s
e
s
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
6
To
make
it
easier
to
manage
the
memory
of
processes
running in
the system,
we’re going
to
make
them
use
virtual addresses
(logical
addresses)
Virtual addresses are independent of the actual
physical
location
of the
data
referenced
OS determines location of data in physical
memory
Instructions executed by the CPU issue virtual
addresses
Virtual addresses are translated by hardware into physical
addresses (with help from
OS)
The set of
virtual addresses
that
can be used by a
process comprises
its
virtual address space
(VAS)
VAS often larger than physical memory (64-bit
addresses)
But can also be smaller (32-bit VAS with 8 GB of
memory)
V
i
r
t
u
a
l
A
d
d
r
e
s
s
e
s
Many ways
to
do
this
translation…
Start with old, simple ways, progress to current
techniques
m
m
u
p
r
o
c
e
s
s
o
r
p
h
y
s
i
c
a
l
m
e
m
o
r
y
v
i
r
t
u
a
l
a
d
d
r
e
s
s
e
s
p
h
y
s
i
c
a
l
a
d
d
r
e
s
s
e
s
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
7
F
i
x
e
d
P
a
r
t
i
t
i
o
n
s
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
8
Physical memory is broken up into fixed
partitions
Hardware requirements:
base
register
Physical address = virtual address + base
register
Base register loaded by OS when it switches to a
process
Size of each partition is the same and
fixed
How do we provide
protection?
Advantages
Easy to implement, fast context
switch
Problems
Internal fragmentation
: memory in a partition not used by a
process is not available to other
processes
Partition size
: one size does
not fit
all
(very
large
processes)
F
i
x
e
d
P
a
r
t
i
t
i
o
n
s
+
V
i
r
t
u
a
l
A
d
d
r
e
s
s
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
9
P
h
y
s
i
c
a
l
M
e
m
o
r
y
B
a
s
e
R
e
g
i
s
t
e
r
P
4
’
s
B
a
s
e
O
f
f
s
e
t
V
a
r
i
a
b
l
e
P
a
r
t
i
t
i
o
n
s
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
10
10
Natural extension
–
physical memory is broken up into
variable sized
partitions
Hardware requirements:
base register
and
limit
register
Physical address = virtual address + base
register
Why do we need the
limit
register?
Protection
»
If
(physical address
>
base
+
limit) then exception
fault
Advantages
No internal fragmentation
: allocate just enough for
process
Problems
External fragmentation
: process creation and termination
produces empty holes scattered throughout
memory
V
a
r
i
a
b
l
e
P
a
r
t
i
t
i
o
n
s
+
V
i
r
t
u
a
l
A
d
d
r
e
s
s
B
a
s
e
R
e
g
i
s
t
e
r
<
P
r
o
t
e
c
t
i
o
n
F
a
u
l
t
Y
e
s
?
N
o
?
L
i
m
i
t
R
e
g
i
s
t
e
r
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
11
11
P
3
’
s
B
a
s
e
P
3
’
s
L
i
m
i
t
O
f
f
s
e
t
P
a
g
i
n
g
P
a
g
e
N
-
1
Paging solves
the
external fragmentation problem by
using fixed sized units in both physical and virtual
memory
P
h
y
s
i
c
a
l
M
e
m
o
r
y
V
i
r
t
u
a
l
M
e
m
o
r
y
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
12
12
P
r
o
g
r
a
m
m
e
r
/
P
r
o
c
e
s
s
V
i
e
w
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
13
13
Programmers (and processes) view
memory
as one
contiguous address space from 0 through
N
Virtual address space (VAS)
In
reality, pages are
scattered
throughout physical
storage
The
mapping is invisible
to
the
program
Protection is provided because a program cannot
reference memory outside
of its
VAS
The
address “0x1000”
maps to
different
physical
addresses in
different
processes
P
a
g
i
n
g
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
14
14
Translating
addresses
Virtual address has two parts:
virtual page number
and
offset
Virtual page number (VPN) is an index into a page
table
Page table determines page frame number
(PFN)
Physical
address
is PFN::offset (“::”
means
concatenate)
Page
tables
Map
virtual page number
(VPN) to
page frame number
(PFN)
»
VPN
is
the
index into
the
table
that
determines
PFN
One page table entry (PTE) per page in virtual address
space
»
Or,
one
PTE
per
VPN
P
h
y
s
i
c
a
l
M
e
m
o
r
y
P
h
y
s
i
c
a
l
A
d
d
r
e
s
s
P
a
g
e
T
a
b
l
e
P
a
g
e
L
o
o
k
u
p
s
V
i
r
t
u
a
l
A
d
d
r
e
s
s
P
a
g
e
f
r
a
m
e
O
f
f
s
e
t
(
A
l
s
o
u
s
e
d
b
y
N
a
c
h
o
s
)
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
15
15
P
a
g
e
n
u
m
b
e
r
O
f
f
s
e
t
P
a
g
i
n
g
E
x
a
m
p
l
e
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
16
16
Pages are
4K
VPN is 20 bits
(2
20
VPNs), offset is 12
bits
Virtual address is
0x7468
Virtual page is 0x7, offset is
0x468
Page table entry 0x7 contains
0x2
Page frame number is
0x2
Seventh virtual page is at address 0x2000 (2nd physical
page)
Physical address
=
0x2000
+
0x468
=
0x2468
P
a
g
e
T
a
b
l
e
s
November
3,
2015
1
7
P
a
g
e
N
-
1
Page tables completely define
the
mapping between
virtual pages and physical pages
for
an
address
space
Each process has an address
space,
so each process
has a page
table
Page tables are data structures maintained in
the
OS
P
h
y
s
i
c
a
l
M
e
m
o
r
y
P
a
g
e
T
a
b
l
e
V
i
r
t
u
a
l
M
e
m
o
r
y
3
0
2
P
a
g
e
N
-
1
P
a
g
e
T
a
b
l
e
E
n
t
r
y
(
P
T
E
)
0
3
2
N
-
1
Valid/referenced bit
to
distinguish mapped/unmapped
regions
Picture of
address space with example mappings
using
the
various
bits
May 7,
2009
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
1
8
P
a
g
e
T
a
b
l
e
E
n
t
r
i
e
s
(
P
T
E
s
)
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
19
19
1
1
1
2
20
Page table entries control
mapping
The
Modify
bit says whether or not the page has been
written
»
It
is
set
when a write
to the
page
occurs
The
Reference
bit says whether the page has been
accessed
»
It
is
set
when a read or write to
the
page
occurs
The
Valid
bit says whether or not the PTE can be
used
»
It
is checked each
time the
virtual address is
used
The
Protection
bits say what operations are allowed on
page
»
Read, write,
execute
The
page frame number
(PFN) determines physical
page
P
a
g
i
n
g
A
d
v
a
n
t
a
g
e
s
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
20
20
Easy to
allocate
memory
Memory comes from a free list of fixed size
chunks
Allocating a page is just removing it from the
list
External fragmentation not a problem
Easy to
swap
out
chunks
of
a
program
All chunks are the same
size
Use valid bit to detect references to swapped
pages
Pages are a convenient multiple of the disk block
size
P
a
g
i
n
g
L
i
m
i
t
a
t
i
o
n
s
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
21
21
Can still have internal
fragmentation
Process may not use memory in multiples of a
page
Memory reference
overhead
2 references per address lookup (page table, then
memory)
Solution – use a hardware cache of lookups (more
later)
Memory required
to
hold page table can be
significant
Need one PTE per
page
32 bit address space w/ 4KB pages =
2
20
PTEs
4 bytes/PTE = 4MB/page
table
25 processes = 100MB just for page
tables!
Solution – page the page tables (more
later)
S
e
g
m
e
n
t
a
t
i
o
n
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
22
22
Segmentation is a technique
that
partitions memory
into logically related data
units
Module, procedure, stack, data, file,
etc.
Virtual addresses become <segment #,
offset>
»
x86 stores segment
#s in
registers
(CS, DS, SS,
ES,
FS,
GS)
Units of
memory
from
programmer’s
perspective
Natural extension
of
variable-sized
partitions
Variable-sized partitions = 1
segment/process
Segmentation = many
segments/process
Hardware
support
Multiple base/limit pairs, one per segment (segment
table)
Segments named by #, used
to
index into
table
L
i
n
e
a
r
A
d
d
r
e
s
s
S
p
a
c
e
0
x
0
0
0
0
0
0
0
0
0
x
F
F
F
F
F
F
F
F
A
d
d
r
e
s
s
S
p
a
c
e
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
3
–
P
r
o
c
e
s
s
e
s
23
23
S
e
g
m
e
n
t
e
d
A
d
d
r
e
s
s
S
p
a
c
e
S
t
a
c
k
0
x
0
0
0
0
0
0
0
0
C
o
d
e
(
T
e
x
t
S
e
g
m
e
n
t
)
S
t
a
t
i
c
D
a
t
a
(
D
a
t
a
S
e
g
m
e
n
t
)
H
e
a
p
S
e
g
m
e
n
t
D
e
s
c
r
i
p
t
o
r
T
a
b
l
e
0
x
0
0
0
0
0
0
0
0
0
x
0
0
0
0
0
0
0
0
0
x
0
0
0
0
0
0
0
0
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
3
–
P
r
o
c
e
s
s
e
s
24
24
Y
e
s
?
S
e
g
m
e
n
t
L
o
o
k
u
p
s
+
<
P
r
o
t
e
c
t
i
o
n
F
a
u
l
t
S
e
g
m
e
n
t
#
O
f
f
s
e
t
V
i
r
t
u
a
l
A
d
d
r
e
s
s
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
25
25
S
e
g
m
e
n
t
T
a
b
l
e
N
o
?
P
h
y
s
i
c
a
l
M
e
m
o
r
y
S
e
g
m
e
n
t
T
a
b
l
e
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
26
26
Extensions
Can have one segment table per
process
»
Segment #s are then process-relative (why do
this?)
Can easily share
memory
»
Put
same translation into base/limit
pair
»
Can share with
different
protections (same base/limit,
diff
prot)
Problems
Cross-segment
addresses
»
Segments
need to have same #s
for
pointers
to
them
to
be
shared among
processes
Large segment
tables
»
Keep in main
memory,
use hardware cache
for
speed
Large
segments
»
Internal
fragmentation,
paging to/from disk is
expensive
S
e
g
m
e
n
t
a
t
i
o
n
a
n
d
P
a
g
i
n
g
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
27
27
Can combine segmentation and
paging
The x86 supports segments and
paging
Use segments
to
manage logically related
units
Module, procedure, stack, file, data,
etc.
Segments vary in size, but usually large (multiple
pages)
Use pages
to
partition segments into fixed size
chunks
Makes segments easier to manage within physical
memory
»
Segments
become “pageable”
–
rather than moving segments
into and
out of memory, just
move page portions
of
segment
Need to allocate page table entries only for those pieces of
the segments that have themselves been
allocated
Tends
to
be
complex…
S
u
m
m
a
r
y
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
28
28
Virtual
memory
Processes use virtual
addresses
OS + hardware translates virtual address into physical
addresses
Various
techniques
Fixed partitions – easy to use, but internal
fragmentation
Variable partitions – more efficient, but external
fragmentation
Paging – use small, fixed size chunks, efficient for
OS
Segmentation –
manage
in chunks from
user’s
perspective
Combine paging and segmentation to get benefits of
both
N
e
x
t
t
i
m
e
…
November
3,
2015
C
S
E
1
2
0
–
L
e
c
t
u
r
e
9
–
M
e
m
o
r
y
M
a
n
a
g
e
m
e
n
t
29
29
Chapters 19,
20
Memory management in operating systems involves the allocation of memory resources among competing processes to optimize performance with minimal overhead. Techniques such as partitioning, paging, and segmentation are utilized, along with page table management and virtual memory tricks. The concept of virtual memory enables programs to execute with less physical memory, adjusting memory allocation based on process behavior. Hardware support and OS management algorithms are crucial for successful virtual memory implementation.
Uploaded on Oct 05, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CSE CSE 120 of Operating Operating Systems Systems 120 Principles Principles of Spring Spring 201 2017 7 Lecture 11: Memory Management
Memory Memory Management Management Next few lectures are going to cover memory management Goals of memory management To provide a convenient abstraction for programming To allocate scarce memory resources among competing processes to maximize performance with minimal overhead Mechanisms Physical and virtual addressing (1) Techniques: partitioning, paging, segmentation (1) Page table management, TLBs, VM tricks (2) Policies Page replacement algorithms (3) CSE 120 Lecture 9 MemoryManagement November 3,2015 2
Lecture Lecture Overview Overview Virtual memory warm-and-fuzzy Survey techniques for implementing virtual memory Fixed and variable partitioning Paging Segmentation Focus on hardware support and lookup procedure Next lecture we ll go into sharing, protection, efficient implementations, and other VM tricks and features CSE 120 Lecture 9 MemoryManagement November 3,2015 3
Virtual Virtual Memory Memory The abstraction that the OS provides for managing memory is virtual memory (VM) Virtual memory enables a program to execute with less than its complete data in physical memory A program can run on a machine with less memory than it needs Can also run on a machine with too much physicalmemory Many programs do not need all of their code and data at once (or ever) no need to allocate memory for it OS will adjust amount of memory allocated to a process based upon its behavior VM requires hardware support and OS management algorithms to pull it off Let s go back to the beginning CSE 120 Lecture 9 MemoryManagement November 3,2015 4
In In the the beginning beginning Rewind to the days of second-generation computers Programs use physical addresses directly OS loads job, runs it, unloads it Multiprogramming changes all of this Want multiple processes in memory at once Overlap I/O and CPU of multiplejobs Can do it a number of ways Fixed and variable partitioning, paging, segmentation Requirements Need protection restrict which addresses jobs can use Fast translation lookups need to befast Fast change updating memory hardware on contextswitch CSE 120 Lecture 9 MemoryManagement November 3,2015 5
Virtual Virtual Addre Addres ss se es s To make it easier to manage the memory of processes running in the system, we re going to make them use virtual addresses (logical addresses) Virtual addresses are independent of the actual physical location of the data referenced OS determines location of data in physical memory Instructions executed by the CPU issue virtual addresses Virtual addresses are translated by hardware into physical addresses (with help from OS) The set of virtual addresses that can be used by a process comprises its virtual address space (VAS) VAS often larger than physical memory (64-bit addresses) But can also be smaller (32-bit VAS with 8 GB of memory) CSE 120 Lecture 9 MemoryManagement November 3,2015 6
Virtual Virtual Addre Addres ss se es s physical addresses virtual addresses physical memory mmu processor Many ways to do this translation Start with old, simple ways, progress to current techniques CSE 120 Lecture 9 MemoryManagement November 3,2015 7
Fixed Fixed Partitions Partitions Physical memory is broken up into fixed partitions Hardware requirements: base register Physical address = virtual address + base register Base register loaded by OS when it switches to a process Size of each partition is the same and fixed How do we provide protection? Advantages Easy to implement, fast context switch Problems Internal fragmentation: memory in a partition not used by a process is not available to other processes Partition size: one size does not fit all (very large processes) CSE 120 Lecture 9 MemoryManagement November 3,2015 8
Fixed Fixed Partitions Partitions Physical Memory P1 Base Register P4 sBase P2 P3 VirtualAddress Offset + P4 P5 CSE 120 Lecture 9 MemoryManagement November 3,2015 9
Variable Variable Partitions Partitions Natural extension physical memory is broken up into variable sized partitions Hardware requirements: base register and limit register Physical address = virtual address + base register Why do we need the limit register? Protection If (physical address > base + limit) then exception fault Advantages No internal fragmentation: allocate just enough for process Problems External fragmentation: process creation and termination produces empty holes scattered throughout memory CSE 120 Lecture 9 MemoryManagement November 3,2015 10
Variable Variable Partitions Partitions Base Register P3 sBase P1 P2 Limit Register P3 sLimit VirtualAddress Yes? P3 Offset < + No? Protection Fault CSE 120 Lecture 9 MemoryManagement November 3,2015 11
Paging Paging Paging solves the external fragmentation problem by using fixed sized units in both physical and virtual memory Physical Memory Virtual Memory Page 0 Page 1 Page 2 Page N-1 CSE 120 Lecture 9 MemoryManagement November 3,2015 12
Programmer/Process Programmer/Process View View Programmers (and processes) view memory as one contiguous address space from 0 through N Virtual address space (VAS) In reality, pages are scattered throughout physical storage The mapping is invisible to the program Protection is provided because a program cannot reference memory outside of its VAS The address 0x1000 maps to different physical addresses in different processes CSE 120 Lecture 9 MemoryManagement November 3,2015 13
Paging Paging Translating addresses Virtual address has two parts: virtual page number and offset Virtual page number (VPN) is an index into a page table Page table determines page frame number (PFN) Physical address is PFN::offset ( :: means concatenate) Page tables Map virtual page number (VPN) to page frame number (PFN) VPN is the index into the table that determinesPFN One page table entry (PTE) per page in virtual address space Or, one PTE perVPN CSE 120 Lecture 9 MemoryManagement November 3,2015 14
Page Page Lookups Lookups Physical Memory VirtualAddress Pagenumber Offset PhysicalAddress Pageframe PageTable Offset Pageframe (Also used by Nachos) CSE 120 Lecture 9 MemoryManagement November 3,2015 15
Paging Paging Example Example Pages are 4K VPN is 20 bits (220 VPNs), offset is 12bits Virtual address is 0x7468 Virtual page is 0x7, offset is 0x468 Page table entry 0x7 contains 0x2 Page frame number is 0x2 Seventh virtual page is at address 0x2000 (2nd physical page) Physical address = 0x2000 + 0x468 = 0x2468 CSE 120 Lecture 9 MemoryManagement November 3,2015 16
Page Page Tables Tables Page tables completely define the mapping between virtual pages and physical pages for an address space Each process has an address space, so each process has a page table Page tables are data structures maintained in the OS Physical Memory Page Table Virtual Memory 0 Page 0 3 Page TableEntry (PTE) 3 Page 1 0 Page 2 2 2 Page N-1 Page N-1 N-1 November 3,2015 17
Valid/referenced bit to distinguish mapped/unmapped regions Picture of address space with example mappings using the various bits CSE 120 Lecture 9 MemoryManagement May 7,2009 18
Page Table Entries Page Table Entries (PTEs) (PTEs) 1 1 1 2 20 M R V Prot Page Frame Number Page table entries control mapping The Modify bit says whether or not the page has been written It is set when a write to the pageoccurs The Reference bit says whether the page has been accessed It is set when a read or write to the pageoccurs The Valid bit says whether or not the PTE can be used It is checked each time the virtual address is used The Protection bits say what operations are allowed on page Read, write,execute The page frame number (PFN) determines physical page CSE 120 Lecture 9 MemoryManagement November 3,2015 19
Paging Paging Advantages Advantages Easy to allocate memory Memory comes from a free list of fixed size chunks Allocating a page is just removing it from the list External fragmentation not a problem Easy to swap out chunks of a program All chunks are the same size Use valid bit to detect references to swapped pages Pages are a convenient multiple of the disk block size CSE 120 Lecture 9 MemoryManagement November 3,2015 20
Paging Paging Limitations Limitations Can still have internal fragmentation Process may not use memory in multiples of a page Memory reference overhead 2 references per address lookup (page table, then memory) Solution use a hardware cache of lookups (more later) Memory required to hold page table can be significant Need one PTE per page 32 bit address space w/ 4KB pages = 220PTEs 4 bytes/PTE = 4MB/page table 25 processes = 100MB just for page tables! Solution page the page tables (more later) CSE 120 Lecture 9 MemoryManagement November 3,2015 21
Segmentation Segmentation Segmentation is a technique that partitions memory into logically related data units Module, procedure, stack, data, file, etc. Virtual addresses become <segment #, offset> x86 stores segment #s in registers (CS, DS, SS, ES, FS,GS) Units of memory from programmer s perspective Natural extension of variable-sized partitions Variable-sized partitions = 1 segment/process Segmentation = many segments/process Hardware support Multiple base/limit pairs, one per segment (segment table) Segments named by #, used to index into table CSE 120 Lecture 9 MemoryManagement November 3,2015 22
Linear Linear Addre Addres ss s S Sp pa ac ce e 0xFFFFFFFF Stack Address Space Heap Static Data (Data Segment) Code (Text Segment) 0x00000000 CSE 120 Lecture 3 Processes November 3,2015 23
Segmented Address Segmented Address Space Space Segment Descriptor Table Stack 0x00000000 Base & Limit Base & Limit Base & Limit Base & Limit Heap 0x00000000 Static Data (Data Segment) 0x00000000 Code (Text Segment) 0x00000000 CSE 120 Lecture 3 Processes November 3,2015 24
Segment Segment Lookups Lookups SegmentTable Physical Memory limit base Segment# Offset VirtualAddress Yes? < + No? Protection Fault CSE 120 Lecture 9 MemoryManagement November 3,2015 25
Segment Segment Table Table Extensions Can have one segment table per process Segment #s are then process-relative (why do this?) Can easily share memory Put same translation into base/limitpair Can share with different protections (same base/limit, diff prot) Problems Cross-segment addresses Segments need to have same #s for pointers to them to be shared among processes Large segment tables Keep in main memory, use hardware cache forspeed Large segments Internal fragmentation, paging to/from disk is expensive CSE 120 Lecture 9 MemoryManagement November 3,2015 26
Segmentation Segmentation and and Paging Paging Can combine segmentation and paging The x86 supports segments and paging Use segments to manage logically related units Module, procedure, stack, file, data, etc. Segments vary in size, but usually large (multiple pages) Use pages to partition segments into fixed size chunks Makes segments easier to manage within physical memory Segments become pageable rather than moving segments into and out of memory, just move page portions of segment Need to allocate page table entries only for those pieces of the segments that have themselves been allocated Tends to be complex CSE 120 Lecture 9 MemoryManagement November 3,2015 27
Summary Summary Virtual memory Processes use virtual addresses OS + hardware translates virtual address into physical addresses Various techniques Fixed partitions easy to use, but internal fragmentation Variable partitions more efficient, but external fragmentation Paging use small, fixed size chunks, efficient for OS Segmentation manage in chunks from user s perspective Combine paging and segmentation to get benefits of both CSE 120 Lecture 9 MemoryManagement November 3,2015 28
Next Next time time Chapters 19, 20 CSE 120 Lecture 9 MemoryManagement November 3,2015 29
