Operating Systems

Chapter 3 Memory Management

Tien Pham Van, Dr. rer. nat.

(Lecture compiled with reference to other presentations)

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 1
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Concept

• Memory management is the act of

managing computer memory.
• It involves providing ways to allocate
portions of memory to programs at
their request, and freeing it for reuse
when no longer needed.
• The management of main memory is
critical to the computer system,
particular embedded systems

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 2
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Memory Management Requirements
• Relocation
– Programmer does not know where the
program will be placed in memory
when it is executed
– While the program is executing, it may
be swapped to disk and returned to
main memory at a different location
(relocated)
– Memory references must be translated
in the code to actual physical memory
address

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 3
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 4
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Memory Management Requirements
• Protection
– Processes should not be able to reference memory
locations in another process without permission
– Impossible to check absolute addresses at compile time
– Must be checked at run time
– Memory protection requirement must be satisfied by
the processor (hardware) rather than the operating
system (software)
• Operating system cannot anticipate all of the memory
references a program will make

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 5
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Memory Management Requirements

• Sharing
– Allow several processes to access the same portion of
memory
– Better to allow each process access to the same copy of
the program rather than have their own separate copy

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 6
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Memory Management Requirements

• Logical Organization
– Programs are written in modules
– Modules can be written and compiled independently
– Different degrees of protection given to modules (read-
only, execute-only)
– Share modules among processes

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 7
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 • Operating Systems 2 - Memory Manager -
YouTube
[Link]
195s

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 8
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Memory Management Requirements

• Physical Organization
– Memory available for a program plus its data may
be insufficient
• Overlaying allows various modules to be assigned the
same region of memory
– Programmer does not know how much space will
be available

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 9
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Overview clip

• Address Binding,Address Translation and

Memory Management Unit Tutorial-2 -
YouTube
[Link]
t=PLskQvPDUk0sJnmLgi4qBRyshlmHydbsAJ&index=3

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 10
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 MMU

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 11
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Fixed Partitioning
• Equal-size partitions
– Because all partitions are of equal size, it does not matter
which partition is used
– Main memory use is inefficient. Any program, no matter
how small, occupies an entire partition. This is called
internal fragmentation.
• Unequal-size partitions
– Can assign each process to the smallest partition within
which it will fit
– Queue for each partition
– Processes are assigned in such a way as to minimize
wasted memory within a partition

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 12
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 13
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Dynamic Partitioning

• Partitions are of variable length and number

• Process is allocated exactly as much memory as
required
• Eventually get holes in the memory. This is called
external fragmentation
• Must use compaction to shift processes so they are
contiguous and all free memory is in one block

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 14
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 15
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Dynamic Partitioning Placement Algorithm

• Operating system must decide which free block to

allocate to a process
• Best-fit algorithm
– Chooses the block that is closest in size to the request
– Worst performer overall
– Since smallest block is found for process, the smallest
amount of fragmentation is left
– Memory compaction must be done more often

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 16
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Dynamic Partitioning Placement Algorithm
• First-fit algorithm
– Scans memory form the beginning and chooses the first
available block that is large enough
– Fastest
– May have many process loaded in the front end of
memory that must be searched over when trying to find a
free block

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 17
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Dynamic Partitioning Placement Algorithm

• Next-fit
– Scans memory from the location of the last placement
– More often allocate a block of memory at the end of
memory where the largest block is found
– The largest block of memory is broken up into smaller
blocks
– Compaction is required to obtain a large block at the end
of memory

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 18
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 19
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Buddy System
• Entire space available is treated as a single block of
2U
• If a request of size s such that 2U-1 < s <= 2U, entire
block is allocated
– Otherwise block is split into two equal buddies
– Process continues until smallest block greater than or
equal to s is generated

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 20
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 21
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 22
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Addresses
• Logical
– Reference to a memory location independent of the
current assignment of data to memory
– Translation must be made to the physical address
• Relative
– Address expressed as a location relative to some known
point
• Physical
– The absolute address or actual location in main memory

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 23
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 24
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Paging

• Partition memory into small equal fixed-size chunks

and divide each process into the same size chunks
• The chunks of a process are called pages and chunks
of memory are called frames
• Operating system maintains a page table for each
process
– Contains the frame location for each page in the process
– Memory address consist of a page number and offset
within the page

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 25
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Page Size (1)

Small page size

• Advantages
– less internal fragmentation
– better fit for various data structures, code sections
– less unused program in memory
• Disadvantages
– programs need many pages, larger page tables

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 26
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Page Size (2)
• Overhead due to page table and internal
fragmentation

page table space

se p
overhead = + internal
p 2 fragmentation

• Where
– s = average process size in bytes
Optimized when
– p = page size in bytes
p = 2se
– e = page entry
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 27
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Page size (3)
Smallest
Architecture page Larger page sizes
size
2 MiB, 1 GiB (only when the CPU
x86-64[18] 4 KiB
has PDPE1GB flag)
Power ISA[21] 4 KiB 64 KiB, 16 MiB, 16 GiB
SPARC v8 with SPARC
4 KiB 256 KiB, 16 MiB
Reference MMU[22]

64 KiB, 512 KiB (optional), 4 MiB, 32 MiB

UltraSPARC
8 KiB (optional), 256 MiB (optional), 2 GiB (optional),
Architecture 2007[23]
16 GiB (optional)

64 KiB, 1 MiB ("section"), 16 MiB

ARMv7[24] 4 KiB ("supersection") (defined by a particular
implementation)

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 28
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Page size (4)
#include <stdio.h>
#include <unistd.h> /* sysconf(3) */

int main(void)
{
printf("The page size for this system is %ld bytes.\n",
sysconf(_SC_PAGESIZE)); /* _SC_PAGE_SIZE is OK too. */

return 0;
}

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 29
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 30
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Virtual Memory

• [Link]
4wGo&ab_channel=Xoviabcs
[Link]

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 31
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Virtual Memory Paging

The position and function of the MMU

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 32
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Paging and translation

The relation between

virtual addresses
and physical
memory addres-
ses given by
page table

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 33
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Internal Operation of MMU with 16 4 KB Pages*

16 bit addresses => address space size: 216

Page size ~4K ~ 212 => 216 / 212 = 24 = 16 pages.
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 34
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Segmentation

• All segments of all programs do not have to be of

the same length
• There is a maximum segment length
• Addressing consist of two parts - a segment number
and an offset
• Since segments are not equal, segmentation is
similar to dynamic partitioning

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 35
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 36
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 37
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 38
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
 Hardware Support

• For each process, a pointer to the page

table is stored with the other register values
(like the instruction counter) in the PCB
• When the dispatcher starts a process, it
must reload all registers and copy the
stored page table values into the hardware
page table in the MMU.

Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 39
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596
Embedded Networking Research Group School of Elec. and Telecom - Hanoi University of Science and Technology 40
Email: tien.phamvan1@[Link] C9-411, Dai Co Viet str. 1, HBT, Hanoi Tel: +84-243-8693596