MEMORY MANAGEMENT

Chapter 5
OBJECTIVES
▪ Understand the relationships among the
various types of memory in the memory
hierarchy
▪ Understand the purpose and general idea of
address translation
▪ Understand segmented address translation
▪ Understand paged address translation
▪ Be able to identify the application of each of
the memory services
OBJECTIVES
▪ Have a solid mental image of the various
approaches to memory layout, both globally
and per-process
▪ Be able to compare free space
representations and apply them at
appropriate times
▪ Understand the difference between internal
and external fragmentation
▪ Understand the various memory allocation
techniques
▪ Understand the various page replacement
policies
THE MEMORY HIERARCHY
▪ Engineering tradeoff:
Cost and volume versus Speed and capacity
▪ For a given point in time, increased speed
and capacity require greater cost and volume

4
MEMORY HIERARCHY (CONT.)

5
 • General purpose registers

Understanding Operating Systems, Sixth Edition 6

▪ Registers: Storage locations are part of the CPU
itself. Designed to accessed in less time than it takes
to execute an instruction.
▪ Cache: Cache memory (Reality that CPU is
generally able to request and process data from
memory faster than the memory can supply it.)
▪ Main Memory: Primary Storage( focus on the
memory management component of the OS and
occupies something of a middle ground with respect
to size and speed)
▪ Secondary Storage: Backing Storage(disk drives)
use small amount fraction of SS for swapping data
between memory and disk when demands of
application exceeds the available physical memory
▪ Archival Storage: long permanent storage ( data is
never deleted in this type of storage subsystems)
Understanding Operating Systems, Sixth Edition 7
Additional reasons why we have different
technologies for different level of hierarchy:

▪ Volatile fastest memory technologies

(power is lost, data is lost)

▪ Non-volatile memory

Understanding Operating Systems, Sixth Edition 8

ADDRESS TRANSLATION
physical addresses or real addresses are addresses
that directly determined the memory locations
✓generated by the CPU;

process layout,(virtual addresses) are addresses that

are generated by running program (logical
addresses)
✓address seen by the memory unit

Set of physical addresses- physical address space

Set of possible virtual address- virtual address space
9
The discrepancy between these two address spaces is
reconciled through the various form of
▪ address translation-Relocation

▪ Memory Management Unit Protection

- Convert virtual addresses to physical addresses
- Usually require that processes be prevented from
accessing the memory belonging to other processes
or to the OS

Understanding Operating Systems, Sixth Edition 10

MMU
▪ sometimes called paged memory management
unit (PMMU),
▪ is a computer hardware component responsible for
handling accesses to memory requested by the CPU.
▪ Its functions includes:
- translation of virtual addresses to physical
addresses
- memory protection,
- cache control,
- bus arbitration (Bus arbitration is the process of resolving
conflicts that arise when multiple devices attempt to access the
bus at the same time.)
Understanding Operating Systems, Sixth Edition 11
[Link]/LIMIT REGISTERS
✓The simplest method of providing address
translation is by the use of base registers.
✓(Single base register) the contents of which
is added to each virtual address, giving
physical address.
Base – holds the smallest legal physical
memory address
Limit – specifies the size of the range

Understanding Operating Systems, Sixth Edition 12

 Base:
300040

Limit:
120900

This means
that a
process can
access
memory
300040 up
Understanding Operating Systems, Sixth Edition to 420940 13
BASE-LIMIT REGISTERS

TRAP / ERROR

Understanding Operating Systems, Sixth Edition 14

2. SEGMENTATION
▪ Process the various part of the process
separately

Understanding Operating Systems, Sixth Edition 15

▪ 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
local variables, global variables
common block
stack
symbol table
arrays
USER’S VIEW OF A
PROGRAM
LOGICAL VIEW OF SEGMENTATION
1

1 4

3
2
4

user space physical memory space

EXAMPLE
OF
SEGMENTATION
3. PAGING
▪ Physical address space of a process can be
noncontiguous; process is allocated physical
memory whenever the latter is available
▪ Divide physical memory into fixed-sized blocks
called frames
▪ Divide virtual memory into blocks of same size
called pages
▪ Keep track of all free frames
▪ To run a program of size N pages, need to find N free
frames and load program
▪ Set up a page table to translate virtual to physical
addresses
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) – denotes the page size or the number of bits
required to represent a word on a page.
▪ combined with base address to define the physical memory
address that is sent to the memory unit

page number page offset

p d

▪ Example:
▪ a 4Kb page require 4Kb == (4 * 1024) == 4096 == 212 ==)
12 bits of offset
PAGING MODEL OF LOGICAL AND PHYSICAL MEMORY
PAGING AND MEMORY ADDRESS
TRANSLATION

Understanding Operating Systems, Sixth Edition 23

PAGING AND MEMORY ADDRESS
TRANSLATION

Understanding Operating Systems, Sixth Edition 24

SEGMENTATION AND MEMORY ADDRESS
TRANSLATION

Understanding Operating Systems, Sixth Edition 25

SEGMENTATION AND MEMORY ADDRESS
TRANSLATION

Understanding Operating Systems, Sixth Edition 26

SEGMENTATION AND MEMORY ADDRESS
TRANSLATION

Understanding Operating Systems, Sixth Edition 27

SEGMENTATION AND MEMORY ADDRESS
TRANSLATION

Understanding Operating Systems, Sixth Edition 28

MEMORY PROTECTION
▪ Memory protection is a way to control memory access rights on
a computer, and is a part of most modern processor
architectures and operating systems. The main purpose of
memory protection is to prevent a process from accessing
memory that has not been allocated to it.
▪ 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

▪ Any violations result in a trap to the kernel

VALID (V) OR INVALID (I) BIT IN A PAGE TABLE
TRANSLATION LOOKASIDE BUFFER
▪ Page table lookups are usually memory references
▪ TLB caches most recent Page table entry (PTE)
▪ A translation lookaside buffer (TLB) is a memory
cache that stores recent translations of virtual
memory to physical addresses for faster retrieval.
▪ If the requested translation is available, you have a
TLB hit, and the TLB provides the translation of the
physical address immediately. If the TLB does not
have a valid translation for that address, you have a
TLB miss and an external translation table walk is
required.
31
Understanding Operating Systems, Sixth Edition 32
 When a virtual memory address is
referenced by a program, the search
starts in the CPU.
First, instruction caches are
checked. If the required memory is not
in these very fast caches, the system has
to look up the memory’s physical
address. At this point, TLB is checked for
a quick reference to the location in
physical memory.

Understanding Operating Systems, Sixth Edition 33

▪ When an address is searched in the TLB and
not found, the physical memory must be
searched with a memory page crawl
operation.
▪ As virtual memory addresses are translated,
values referenced are added to TLB. When a
value can be retrieved from TLB, speed is
enhanced because the memory address is
stored in the TLB on processor.
▪ Most processors include TLBs to increase the
speed of virtual memory operations through
the inherent latency-reducing proximity as
well as the high-running frequencies of
current CPU’s.
Understanding Operating Systems, Sixth Edition 34
MEMORY SERVICES
✓ OS must decide what data is to reside in each level of hierarchy.
In some cases the hardware decides.
Primary services for process:
✓ Allocation and De-allocation

Allocation:
▪ Explicit allocation: process specifies virtual address range;
application allocates and frees space.
▪ Implicit allocation: kernel decides virtual range; application
allocates but not free space
▪ Garbage collection: identify and free unused blocks

▪ Memory mapped file: file whose contents are directly

associated with a region in the virtual address space

35
TYPICAL SYSTEM MEMORY LAYOUT
▪ We start by
memory space
define by the
hardware.
▪ each interrupt
vector is a pointer
that tells the
microprocessor the
location where the
code associated
with the interrupt is 36
located).
TYPICAL PROCESS MEMORY LAYOUT
▪ Process are laid out in memory. For
most environment, MS of a process is
divided into numbers of segment
(contains process code and process
data)
▪ Code segment are those executable
instructions of the program
▪ Data segment are those data that are
dynamically allocated by allocation
system calls.
▪ Stack segment used to store
activation records. These records are
called stack frames.
37
MEMORY ALLOCATION TECHNIQUES
The primary role of memory management system is to
satisfy request for memory allocation. Sometimes
▪ implicitly with when new process is created.
▪ Explicitly when process requested memory.
Either way the system must locate enough unallocated
memory and assign it to the process.

Understanding Operating Systems, Sixth Edition 38

FREE SPACE MANAGEMENT
▪ Before we can allocate free memory, we must first
locate the free memory either it is physical or the
virtual memory
▪ Free bitmaps:
▪ Good for fixed-sized blocks, like pages coz it store
one bit/page which is set to 1 if the page frame is
allocated and 0 if unallocated
▪ Free list:
▪ Represent set of free memory in a linked list.
▪ Need to search in the list for suitable block
▪ Sometimes tree or hash table are commonly used
data structures.

39
FRAGMENTATION
▪ In allocating memory, we ended up wasted space:
▪ External fragmentation: wasted space outside
allocation units
total memory space exists to satisfy a request, but it
is not contiguous
▪ Internal fragmentation: wasted space within
allocation units
allocated memory may be slightly larger than
requested memory; this size difference is memory
internal to a partition, but not being used
40
▪ Reduce external fragmentation by
compaction
▪ Shuffle memory contents to place all free
memory together in one large block
▪ To optimize files for fast access, a volume can
be defragmented.
▪ Defragmentation is the process of moving
portions of files around on a disk to
defragment files, that is, the process of moving
file clusters on a disk to make them
contiguous.

Understanding Operating Systems, Sixth Edition 41

PARTITIONS
▪ Simplest way of allocating memory are
based on dividing memory into areas with
fixed partitions.
▪ we administratively define fixed partitions
between blocks of varying size.
▪ These partitions are in effect from the time
the system starts to the time it is shut down.
▪ Memory requests are all satisfied from the
fixed set of defined partitions.

42
SELECTION POLICIES
▪ Among free blocks at least as large as the request:
▪ First fit: pick the first
▪ Next fit: pick the next
▪ Best fit: pick the smallest
▪ Worst fit: pick the biggest

43
 FIRST FIT EXAMPLE
▪ begin searching the list and take the first block whose
size is greater than or equal to the request size

44
NEXT FIT EXAMPLE
▪ similar to the first fit approach, except for the place
where the search starts.
▪ we begin the search with the free block that was next
on the list after the last allocation.

45
BEST FIT EXAMPLE
▪ allocate the free block that is closest in size to the
request.
▪ we search the list for the block that is smallest but
greater than or equal to the request size.

46
WORST FIT EXAMPLE
▪ Allocates the largest block for every request.
▪ one advantage: If most of the requests are of similar
size, a worst fit policy tends to minimize external
fragmentation.

47
FIRST FIT
Original: 100KB 500KB 200KB 300KB 600KB

▪ 212KB: 100KB 288KB 200KB 300KB 600KB

▪ 417KB: 100KB 288KB 200KB 300KB 183KB
▪ 112KB: 100KB 176KB 200KB 300KB 183KB
▪ 426KB: FAILS: Cannot be allocated
▪ 100KB: 0KB 176KB 200KB 300KB 183KB

Understanding Operating Systems, Sixth Edition 48

NEXT FIT
Original: 100KB 500KB 200KB 300KB 600KB

▪ 212KB: 100KB 288KB 200KB 300KB 600KB

▪ 417KB: 100KB 288KB 200KB 300KB 183KB
▪ 112KB: 100KB 176KB 200KB 300KB 183KB
▪ 426KB: FAILS: Cannot be allocated
▪ 100KB: 100KB 176KB 100KB 300KB 183KB

Understanding Operating Systems, Sixth Edition 49

BEST FIT
▪ Original: 100KB 500KB 200KB 300KB 600KB

▪ 212KB: 100KB 500KB 200KB 88KB 600KB

▪ 417KB: 100KB 83KB 200KB 88KB 600KB
▪ 112KB: 100KB 83KB 88KB 88KB 600KB
▪ 426KB: 100KB 83KB 88KB 88KB 174KB
▪ 100KB: 0KB 83KB 88KB 88KB 174KB

Understanding Operating Systems, Sixth Edition 50

WORST FIT
▪ Original: 100KB 500KB 200KB 300KB 600KB

▪ 212KB: 100KB 500KB 200KB 300KB 388KB

▪ 417KB: 100KB 83KB 200KB 300KB 388KB
▪ 112KB: 100KB 83KB 200KB 300KB 276KB
▪ 426KB: FAILS: Cannot be allocated
▪ 100KB: 100KB 83KB 200KB 200KB 276KB

Understanding Operating Systems, Sixth Edition 51

52
PART 2

Understanding Operating Systems, Sixth Edition

OVERALLOCATION TECHNIQUES
▪ Swapping: copying full processes between
main memory and backing store
▪ Segment swapping: copying individual
segments between main memory and
backing store
▪ Paging (page swapping): copying
individual pages between main memory and
backing store

53
PAGING CONCEPTS
▪ Demand paging: reading pages into memory in
response to page faults
▪ Page fault: an interrupt that occurs when a translation
is not valid, often because the page is not resident in
memory; called trap
▪ Prepaging: loading pages in anticipation of later
needing them
▪ Page reference string: list of page numbers in the
order in which they are referenced
▪ Global page replacement policy: page replacement
policy that selects pages without regard to the
processes that own them
▪ Local page replacement policy: page replacement
policy that selects pages only from a given process 54
PAGE REPLACEMENT
▪ Techniques using which OS decides which
memory pages to swap out, write to disk
when a page of memory needs to be
allocated.
▪ Paging happens whenever a page fault
occurs and a free page cannot be used for
allocation purpose accounting to reason that
pages are not available or the number of free
pages is lower than required pages.

Understanding Operating Systems, Sixth Edition 55

BASIC PAGE REPLACEMENT
1. Find the location of the desired page on disk

2. Find a free frame:

- If there is a free frame, use it
- If there is no free frame, use a page
replacement algorithm to select a victim frame
- Write victim frame to disk if dirty

3. Bring the desired page into the (newly) free

frame; update the page and frame tables

4. Continue the process by restarting the instruction

that caused the trap
Understanding Operating Systems, Sixth Edition 56
FIFO PAGE REPLACEMENT

Understanding Operating Systems, Sixth Edition 57

OPTIMAL PAGE REPLACEMENT

Understanding Operating Systems, Sixth Edition 58

OPTIMAL PAGE REPLACEMENT

Understanding Operating Systems, Sixth Edition 59

LEAST RECENTLY USED (LRU) ALGORITHM
▪ Use past knowledge rather than future
▪ Replace page that has not been used in the most amount of
time
▪ Associate time of last use with each page

60
Understanding Operating Systems, Sixth Edition 61
PERFORMANCE ISSUES
If not careful of choosing allocation and replacement policies,
system performance can suffer.
Access time
Thrashing
thrashing is a condition in which excessive
paging operations are taking place. A system that
is thrashing can be perceived as either a very slow system or
one that has come to a halt
Belady’s Anomaly
Bélády's anomaly is the phenomenon in which
increasing the number of page frames results in an increase in
the number of page faults for certain memory access patterns

62
AVERAGE ACCESS TIME
▪ Average Memory Access Time (AMAT) is a
common metric to analyze memory system
performance
▪ Average access time is given by:

Average Memory Access time = Hit time + Miss Rate x Miss penalty

Hit latency (H) is the time to hit in the cache.

Miss rate (MR) is the frequency of cache misses
average miss penalty (AMP) is the cost of a cache miss
in terms of time.
THRASHING
▪ Effect of active working sets being
larger than the physical memory
▪ The system spends more time
swapping than computing
▪ System performance intolerably slow
▪ Can be partially ameliorated with two-
level scheduling
BELADY'S ANOMALY
▪ Phenomenon where adding more page
frames leads to more page faults
▪ Some policies, such as FIFO, are
susceptible
▪ Some policies, such as LRU, are immune

65
BELADY'S ANOMALY

66
 SUMMARY
▪ Memory hierarchy gives perspective on
trade-offs of speed and size
▪ Address translation is needed for relocation
and protection
▪ Translation can be in terms of segments,
using base and limit registers
▪ Translation can be in term of pages using
page tables containing page table entries

Principles of Operating Systems: Design & Applications 67

 SUMMARY (CONT.)
▪ TLB caches recently used PTEs
▪ Both system and per-process memory layouts start at
address 0
▪ Typically process data segments grow up toward
stack and stack down toward data
▪ Free memory can be represented by bitmaps and by
lists
▪ Free lists typically keep pointers and sizes inside the
free blocks

Principles of Operating Systems: Design & Applications 68

 SUMMARY (CONT.)
▪ Fragmentation reduces usable memory
▪ Partitioning is a simple and old technique
being used again with virtualization
▪ Variable-sized blocks can be allocated by
first fit, next fit, best fit, worst fit, or buddy
system
▪ Memory can be overallocated by using
swapping, segment swapping, or page
swapping
Principles of Operating Systems: Design & Applications 69
 SUMMARY (CONT.)
▪ Page replacement policies attempt to get
close to performance of optimal Belady's min
▪ Common policies include FIFO, second
chance (in one and two hand clock
implementations), NRU, LRU, and NFU
▪ Try to keep process's working set in memory
▪ Adjust working set size with page fault
frequency
▪ Performance can be tricky

Principles of Operating Systems: Design & Applications 70