Memory management
Tran, Van Hoai
Faculty of Computer Science & Engineering
HCMC University of Technology
E-mail: hoai@hcmut.edu.vn
(partly based on slides of Le Thanh Van)
1 / 58
Outline
1 Background
2 Swapping
3 Contiguous memory allocation
4 Segmentation
5 Paging
Structure of page table
2 / 58
Outline
1 Background
2 Swapping
3 Contiguous memory allocation
4 Segmentation
5 Paging
Structure of page table
3 / 58
Role of memory
4 / 58
Role of memory
Memory storing instructions
Memory storing data
5 / 58
Role of memory
Memory storing instructions
Memory storing data
Instructions of programs are only executed when they are
in memory
Memory management requires some hardware support
6 / 58
Hardware support
Each user process has a separate memory space
Base and limit registers give a range of the memory space
7 / 58
Hardware support
Each user process has a separate memory space
Base and limit registers give a range of the memory space
Memory protection mechanism is not applied for operating
system executing in kernel mode
8 / 58
Address binding
User program to execution
Address binding
A process to convert one kind of high
abstract memory address to low abstract
memory address
a symbolic address to a relocatable
address
a relocatable address to a absolute
address
Example:
a variable “count” → a relocatable address “14
bytes from the beginning of this module”
“14 bytes from the beginning of this module” →
an absolute address “74014”
9 / 58
Address binding
When it happens?
Binding is performed in any of following 3 steps
Compile time: if starting location changes, absolute
address must be regenerated (by compile)
Load time: with relocatable code, only reloading is
needed when starting address changes
Execution time: if a process moved in memory, binding is
delayed until its run time. Most general-purpose OSs use
this method
10 / 58
Logical address vs. physical address
Logical address Physical address
Address generated by CPU Address seen by memory
management unit
(MMU)
11 / 58
Logical address vs. physical address
Logical address Physical address
Address generated by CPU Address seen by memory
management unit
(MMU)
Compile/load-time binding: logical address = physical address
Execution-time binding: logical address 6= physical address
User program thinks logical (virtual) address range is [0, max], but
physical address range is [R + 0, R + max].
12 / 58
Dynamic loading
Dynamic loading
A routine is not loaded until it is called
Routine must be in relocatable load format
Relocatable linking loader is responsible to load dynamic
loading routing when a caller has not loaded yet
Better memory=space utilization, useful to handle
infrequently occuring cases
Dynamic loading does not require support from OS
13 / 58
Dynamic linking and shared library
If multiple programs use a same routine, dynamic loading
requires duplication of the routine in memory
14 / 58
Dynamic linking and shared library
If multiple programs use a same routine, dynamic loading
requires duplication of the routine in memory
Dynamic linking
A routine is linked to user programs when the programs are run
(source:ibm)
15 / 58
Dynamic linking and shared library
If multiple programs use a same routine, dynamic loading
requires duplication of the routine in memory
Dynamic linking
A routine is linked to user programs when the programs are run
A stub is put in the image
of each reference
The stub is replaced with
the address of the needed
routine, and then can be
referred to by other
references without loading (source:ibm)
16 / 58
Dynamic linking and shared library
If multiple programs use a same routine, dynamic loading
requires duplication of the routine in memory
Dynamic linking
A routine is linked to user programs when the programs are run
A stub is put in the image
of each reference
The stub is replaced with
the address of the needed
routine, and then can be
referred to by other
Dynamic linking
references requires
without support (source:ibm)
loading from OS
17 / 58
Outline
1 Background
2 Swapping
3 Contiguous memory allocation
4 Segmentation
5 Paging
Structure of page table
18 / 58
Standard swapping
Backing store must be
large enough to
accommodate copies of all
memory images of all
users
Images of processes in
ready queue are in backing
store
19 / 58
Standard swapping
Backing store must be
large enough to
accommodate copies of all
memory images of all
users
Images of processes in
ready queue are in backing
store
Swapping is influenced by factors
Transfer time between fast disk and memory
Informing mechanism to activate swapping
I/O waiting processes should be swapped out carefully
20 / 58
Standard swapping
Backing store must be
large enough to
accommodate copies of all
memory images of all
users
Images of processes in
ready queue are in backing
store
Swapping is influenced by factors
Transfer time between fast disk and memory
Informing mechanism to activate swapping
I/O waiting processes should be swapped out carefully
Standard swapping is not used in modern OSs
21 / 58
Swapping on mobile systems
Flash drives have finite number of write/erase cycles
Mobile OSs do not support swapping
OSs may terminate processes if memory is not sufficient
Developers for mobile systems must carefully allocate and
release memory
22 / 58
Outline
1 Background
2 Swapping
3 Contiguous memory allocation
4 Segmentation
5 Paging
Structure of page table
23 / 58
Contiguous memory allocation
Memory divided into 2 partitions: resident OS & user
processes
Interrupt vector is often in low memory ⇒ resident OS is
low memory partition
24 / 58
Contiguous memory allocation
Memory divided into 2 partitions: resident OS & user
processes
Interrupt vector is often in low memory ⇒ resident OS is
low memory partition
Contiguous memory allocation
Each process is contained in a single section of memory that is
contiguous to the section of the next process
25 / 58
Contiguous memory allocation
Memory divided into 2 partitions: resident OS & user
processes
Interrupt vector is often in low memory ⇒ resident OS is
low memory partition
Contiguous memory allocation
Each process is contained in a single section of memory that is
contiguous to the section of the next process
OSs use relocation register for memory protection
26 / 58
Memory allocation
There are 2 ways
Fixed-partition: memory is divided into several fixed-size
partitions. A process is in a single partition
Variable-partition: only assign enough memory for
processes and OS keeps a table storing status of memory
27 / 58
Memory allocation
There are 2 ways
Fixed-partition: memory is divided into several fixed-size
partitions. A process is in a single partition
Variable-partition: only assign enough memory for
processes and OS keeps a table storing status of memory
Job list:
J1 (30K)
J2 (50K)
J3 (30K) Original state
J4 (25K)
partition 1 100K
partition 2 25K
partition 3 25K
partition 4 50K
28 / 58
Memory allocation
There are 2 ways
Fixed-partition: memory is divided into several fixed-size
partitions. A process is in a single partition
Variable-partition: only assign enough memory for
processes and OS keeps a table storing status of memory
Job list:
J1 (30K)
J2 (50K)
J3 (30K) Original state
J4 (25K)
partition 1 100K
partition 2 25K
partition 3 25K
partition 4 50K
29 / 58
Memory allocation
There are 2 ways
Fixed-partition: memory is divided into several fixed-size
partitions. A process is in a single partition
Variable-partition: only assign enough memory for
processes and OS keeps a table storing status of memory
Job list:
J1 (30K)
J2 (50K)
J3 (30K) Original state
J4 (25K)
partition 1 100K
partition 2 25K
partition 3 25K
partition 4 50K
30 / 58
Memory allocation
There are 2 ways
Fixed-partition: memory is divided into several fixed-size
partitions. A process is in a single partition
Variable-partition: only assign enough memory for
processes and OS keeps a table storing status of memory
Job list:
J1 (30K)
J2 (50K)
J3 (30K) Original state
J4 (25K)
partition 1 100K
partition 2 25K
partition 3 25K
partition 4 50K
31 / 58
Memory allocation
There are 2 ways
Fixed-partition: memory is divided into several fixed-size
partitions. A process is in a single partition
Variable-partition: only assign enough memory for
processes and OS keeps a table storing status of memory
Job list:
J1 (30K)
J2 (50K)
J3 (30K) Original state After job allocation
J4 (25K)
J1 (30K)
partition 1 100K
partition 2 25K J4 (25K)
partition 3 25K
partition 4 50K J2 (50K)
32 / 58
Variable partition
Fixed-partition scheme limits the level of
multiprogramming
Variable-partition scheme needs a mechanism to deal
efficiently with set of holes
33 / 58
Variable partition
Fixed-partition scheme limits the level of
multiprogramming
Variable-partition scheme needs a mechanism to deal
efficiently with set of holes
State: list of available (free) block sizes, input queue
Dynamic storage-allocation problem: how to satisfy a request
of size n from a list of free holes
Strategies: first-fit, best-fit, worst-fit
34 / 58
Fragmentation
Internal vs. external
OS
Internal fragmentation
job A
job B
External fragmentation
job C
External fragmentation: small holes which cannot satisfy
large request
Internal fragmentation: unused memory which has been
allocated for process
35 / 58
Outline
1 Background
2 Swapping
3 Contiguous memory allocation
4 Segmentation
5 Paging
Structure of page table
36 / 58
What is segmentation ?
Memory management should be convenient to both OS and
programmers
Programmers think of programs as
set of data structures and methods.
With memory, they need
Collection of variable-sized
memory blocks (segments)
No neccessary ordering among
segments
37 / 58
What is segmentation ?
Memory management should be convenient to both OS and
programmers
Programmers think of programs as
set of data structures and methods.
With memory, they need
Collection of variable-sized
memory blocks (segments)
No neccessary ordering among
segments
Segment = <segment-number, offset>
38 / 58
Segmentation hardware
Segment address is 2-dimensional, but physical memory
address is 1-dimensional
Segment table is an array of base–limit register pairs
39 / 58
Outline
1 Background
2 Swapping
3 Contiguous memory allocation
4 Segmentation
5 Paging
Structure of page table
40 / 58
What is paging ?
Segmentation still has external fragmentation, requiring
compaction
Physical memory is divided into fixed-sized blocks (frame)
Logical memory is divided into same-sized blocks (page)
Page address = <page number, page offset>
41 / 58
Paging in practice
Logical address space = 2m
Page size = 2n
42 / 58
Paging in practice
Logical address space = 2m
Page size = 2n
n = 2, m = 4
43 / 58
Paging in practice
Logical address space = 2m
Page size = 2n
6 = 01102
page=012
offset=102
n = 2, m = 4
44 / 58
Paging in practice
Logical address space = 2m
Page size = 2n
6 = 01102
page=012
offset=102
n = 2, m = 4
45 / 58
Paging in practice
Logical address space = 2m
Page size = 2n
phy.mem=26[=(6x4)+2]
6 = 01102
page=012
offset=102
n = 2, m = 4
46 / 58
Paging in practice
Logical address space = 2m
Page size = 2n
phy.mem=26[=(6x4)+2]
6 = 01102
page=012
offset=102
Paging has no external fragmentation, but has internal
fragmentation.
n = 2, m = 4
47 / 58
Frame allocation
A process can be given
a non-contiguous set
of frames
48 / 58
Frame allocation
A process can be given
a non-contiguous set
A data ofstructure
frames (frame-table) is needed to manage frames.
49 / 58
Hardware support
Page table stored in main memory,
A page table for each process, pointer to it in PCB
Few page tables for all processes
50 / 58
Hardware support
Page table stored in main memory,
A page table for each process, pointer to it in PCB
Few page tables for all processes
Page-address translation overhead ⇒ hardware support
Page-table base register (PTBR): point to page table
Translation look-aside buffer (TLB): associative, high-speed
memory (<key,value>)
51 / 58
Hardware support
Page table stored in main memory,
A page table for each process, pointer to it in PCB
Few page tables for all processes
Page-address translation overhead ⇒ hardware support
Page-table base register (PTBR): point to page table
Translation look-aside buffer (TLB): associative, high-speed
memory (<key,value>)
hit ratio
80%
effective access time =
80% × 100(ns) + 20% × 200(ns) = 120(ns)
99%
effective access time =
99% × 100(ns) + 1% × 200(ns) = 101(ns)
52 / 58
Protection
From access permission: read-write/read-only bit
From out-of-range access: valid-invalid bit
Just keep a small range of pages ⇒ page-table length register
(PTLR)
53 / 58
Shared pages
An advantage of paging is possibility of sharing common code
54 / 58
Hierarchical paging
2-level paging scheme
It is often applied for 32(or less)-bit address space
55 / 58
Hashed paging
It is often applied for 32(or more)-bit address space
56 / 58
Hashed paging
It is often applied for 32(or more)-bit address space
57 / 58
Inverted paging
Just keep a page table for all processes. PID is needed to
search for an address-space identifier
58 / 58
