Operating Systems

ECEG-5202

Memory Management

Surafel Lemma Abebe (Ph. D.)

 Outline
• Introduction
• Memory partitioning
• Paging
• Segmentation

Surafel Lemma Abebe (Ph. D.) 2

 Introduction
• Uniprogramming system
– Main memory is divided into two
• For the OS (resident monitor, kernel)
• For the program currently being executed

• Multiprogramming system
– “User” part of memory must be further subdivided to
accommodate multiple processes
– The sub-division is carried out dynamically by OS
=> Memory management

Surafel Lemma Abebe (Ph. D.) 3

 Introduction…
• Memory management
– Involves swapping blocks of data from secondary
storage

– If only a few processes can be kept in main memory,

then much of the time all processes will be waiting for
I/O and the CPU will be idle

– Memory needs to be allocated efficiently in order to

pack as many processes into memory as possible

Surafel Lemma Abebe (Ph. D.) 4

 Introduction…
• Terminologies

Surafel Lemma Abebe (Ph. D.) 5

 Introduction…
• Requirements
– What memory management intends to satisfy
• Relocation
• Protection
• Sharing
• Logical organization
• Physical organization

Surafel Lemma Abebe (Ph. D.) 6

 Introduction…
• Requirements…
– Relocation
• Memory is generally shared among a number of
processes
• The programmer does not know
– Where the program will be placed in memory when it is
executed
– Which other programs will be resident in main memory at the
time of execution of the programmer’s program
• The program may be swapped to disk and return to
main memory at a different location (relocated)

Surafel Lemma Abebe (Ph. D.) 7

 Introduction…
• Requirements…
– Relocation…
• Memory references
in code (for both
instruction and data)
must be translated
to the actual physical
memory address,
reflecting the current
location of the
program in main
memory

Surafel Lemma Abebe (Ph. D.) 8

 Introduction…
• Requirements…
– Protection
• Processes should not be able to reference memory
locations in another process for reading or writing
purpose without permission
• Impossible to check absolute addresses at compile time
to assure protection
– Programs could be relocated
• Address references must be checked at run time by
hardware

Surafel Lemma Abebe (Ph. D.) 9

 Introduction…
• Requirements…
– Sharing
• Flexibility to allow several processes to access a same
portion of main memory
– Processes executing the same program should be allowed to
access the same copy of the program rather than have their
own separate copy
– Cooperating processes may need to share access to the same
data structure

Surafel Lemma Abebe (Ph. D.) 10

 Introduction…
• Requirements…
– Logical organization
• Users write programs in modules with different characteristics
– Instruction modules are execute-only
– Data modules are either read-only or read/write
– Some modules are private others are public
• To effectively deal with user programs, the OS and hardware
should support a basic form of module to provide the required
protection and sharing
• Advantage
– Modules can be written and compiled independently
– Different degrees of protection can be given to different modules
– Sharing on a module level corresponds to user’s way of viewing the
problem
» Easy for user to specify the sharing that is desired

Surafel Lemma Abebe (Ph. D.) 11

 Introduction…
• Requirements…
– Physical organization
• Hierarchy of memory : secondary memory, primary memory
• Moving information between these two levels of memory is
a major concern of memory management
• Highly undesirable and impractical to leave this
responsibility to the application programmer. Why?
1. The main memory available for a program plus its data may be
insufficient
» Overlay: various modules can be assigned the same region of
memory, with a main program being responsible for
switching the modules in and out as needed
» Even with the aid of compiler tools, overlay programming
wastes programmer time
2. At time of coding, programmer doesn’t know how much space
will be available or where that space will be
Surafel Lemma Abebe (Ph. D.) 12
 Introduction…
• Goals of memory management
– Memory management shouldn’t block any process
• All processes should be able to run
– Space overhead of the memory manager must be
reasonable
• It should be as minimum as possible
– CPU time used by the memory manager should be
reasonable
• It should be as minimum as possible

Surafel Lemma Abebe (Ph. D.) 13

 Memory partitioning
• Principal operation of memory management
– To bring processes into main memory for execution by
the processor
• Memory partitioning is simple but old approach
used to manage memory
• Memory partitioning is not used in modern OSs
• Two types of memory partitioning
– Fixed partitioning
– Dynamic partitioning
Surafel Lemma Abebe (Ph. D.) 14
 Memory partitioning…
• Fixed partitioning
– “User” memory is divided into N non-
overlapping regions called partitions
– Two alternatives
• Equal-size partition
• Unequal-size partition
– Difficulties with equal-size partition
• Program could be too big to fit into the partition
– Programmer must design the program with the use of
overlays
• Main memory utilization is extremely in efficient
– Internal fragmentation

Surafel Lemma Abebe (Ph. D.) 15

 Memory partitioning…
• Fixed partitioning …
– Placement algorithm
• Equal-size partitioning
– If there is an available partition, a process can be loaded into
that partition
» Because all partitions are of equal size, it does not matter
which partition is used
– If all partitions are occupied by blocked processes, choose one
process to swap out to make room for the new process
» Which one to swap out is scheduling decision

Surafel Lemma Abebe (Ph. D.) 16

 Memory partitioning…
• Fixed partitioning…
– Placement algorithm…
• Unequal-size partitioning
– Two approaches
– Use of multiple queue
» Assign each process to the smallest
partition within which it will fit
» Requires a scheduling queue for each
partition
» Has minimal overhead
» Advantage
• Processes are assigned in such a
way as to minimize wasted
memory within a partition
» Problem
• Some queues will be empty if no
process within a size range is
present

Surafel Lemma Abebe (Ph. D.) 17

 Memory partitioning…
• Fixed partitioning…
– Placement algorithm…
• Unequal-size partitioning…
– Use of a single queue
» The smallest available partition that will hold
the process is selected
» If there is no free slot, swap out of the smallest
partition that will hold the incoming process
» Advantage (general)
• Simple and require minimal OS software
and processing overhead
» Disadvantages
• Number of partitions dictate number of
active processes
• Small jobs will not utilize partition space
efficiently (internal fragmentation)
– Used in IBM mainframe OS, OS/MT
(Multiprogramming with a Fixed Number of Tasks)

Surafel Lemma Abebe (Ph. D.) 18

 Memory partitioning…
• Dynamic partitioning
– Overcomes some of the difficulties with fixed partitioning
– Partitions are of variable length and number
– Each process is allocated exactly as much memory as it requires
• Used in IBM mainframe OS, OS/MVT (Multiprogramming with a Variable Number of Tasks)
– Leads to a situation in which there are a lot of holes in memory
– Example
• A hole of 4M is left after loading 3 processes
• Several holes are created as more processes are swapped

Surafel Lemma Abebe (Ph. D.) 19

 Memory partitioning…
• Dynamic partitioning…

– The holes , which are formed in main memory are called

external fragmentation
– Solution
• Compaction
– Shifts processes so they are contiguous and all free memory is in one
block
Surafel Lemma Abebe (Ph. D.) 20
 Memory partitioning…
• Dynamic partitioning…
– Disadvantage of compaction
• It is time consuming procedure
• Wastes processor time

– Note
• Compaction implies the need for a dynamic relocation
capability
– Must be possible to move a program from one region to
another in main memory without invalidating the memory
references in the program

Surafel Lemma Abebe (Ph. D.) 21

 Memory partitioning…
• Dynamic partitioning…
– Placement algorithm
• Used to decide which free block that is equal to or larger
than the process size to allocate
• Goal
– To reduce usage of compaction which is time and CPU consuming
• Possible algorithms
– Best-fit
» Choose smallest block that is closest in size to the request
» Scans all available blocks
– First-fit
» Scans and choose first block from beginning of memory
– Next-fit
» Scans and choose the next available block from last
placement
Surafel Lemma Abebe (Ph. D.) 22
 Memory partitioning…
• Dynamic partitioning…
– Placement algorithm…
– Example
• Memory configuration
before and after
allocation of 16KB block
using best-fit, first-fit and
next-fit

Surafel Lemma Abebe (Ph. D.) 23

 Memory partitioning…
• Dynamic partitioning…
– Placement algorithm…
• Which of these approaches is best, depends on
– Exact sequence of process swapping that occurs
– The size of those processes
• General comment
– Next-fit
» Often leads to allocation of the largest block at the end of
memory
» Compaction may be required more often (as it breaks the
largest block into smaller pieces quickly)

Surafel Lemma Abebe (Ph. D.) 24

 Memory partitioning…
• Dynamic partitioning…
– Placement algorithm…
• General comment…
– First-fit
» Simplest and fastest
» Favors allocation near the beginning
» Tends to create less fragmentation than Next-fit
» May litter the front end with small free partitions that need to be
searched over on each subsequent first-fit pass
– Best-fit
» Usually the worst
» Searches for smallest block that satisfies the requirement
» Main memory quickly forms holes too small to hold any process
» Compaction generally needs to be done more often

Surafel Lemma Abebe (Ph. D.) 25

 Memory partitioning…
• Buddy system
– Drawbacks of fixed and dynamic partitioning schemes
• Fixed partitioning system
– Limits the number of active processes
– Uses space inefficiently if there is poor match between available
partition size and process size
• Dynamic partitioning system
– Complex to maintain
– Has the overhead of compaction
– Compromise between the two
• Buddy system

Surafel Lemma Abebe (Ph. D.) 27

 Memory partitioning…
• Buddy system…
– Memory blocks are available in size of 2k
where L <= K <= U
2L= smallest size of block allocatable
2U= largest size of block allocatable
(generally, the entire memory available)

Surafel Lemma Abebe (Ph. D.) 28

 Memory partitioning…
• Buddy system…
– We start with the entire block of size 2U
– When a request of size S is made
If 2U-1 < S <= 2U then
allocate the entire block of size 2U
Else
split this block into two buddies, each of size 2U-1

If 2U-2 < S <= 2U-1

then allocate one of the 2 buddies
Else
one of the 2 buddies is split again

– This process is repeated until the smallest block greater or equal to S is

generated
– Two buddies are joined whenever both of them become unallocated

Surafel Lemma Abebe (Ph. D.) 29

 Memory partitioning…
• Buddy system…
– Example

Surafel Lemma Abebe (Ph. D.) 30

 Memory partitioning…
• Relocation
– A process may occupy different main memory
locations during its lifetime
• Reasons
– Swapping and compaction
– Problem
• Physical memory references by a process cannot be
fixed

Surafel Lemma Abebe (Ph. D.) 31

 Memory partitioning…
• Relocation….
– Solution
• Distinguishing between
– Logical address and physical address
• Logical address
– Reference to a memory location independent of the current assignment of
data to memory
– A translation must be made to a physical address before the memory access
can be achieved
– Compilers produce code in which all memory references are logical addresses
– Example
» Relative address
• The address is expressed as a location relative to some known
point, usually a value in a processor register
• Physical address (absolute address)
– Is an actual location in main memory

Surafel Lemma Abebe (Ph. D.) 32

 Memory partitioning…
• Relocation….
– Address translation
• Relative address is the most frequent type of logical
address used
• Modules are loaded in main memory with all memory
references in relative form
• Physical addresses are calculated “on the fly” as the
instructions are executed
• For adequate performance, the translation from
relative to physical address must be done by hardware

Surafel Lemma Abebe (Ph. D.) 33

 Memory partitioning…
• Relocation….
– Address translation…
• When a process is assigned to the running state
– A base register gets loaded with the starting physical address of
the process
– A bound register gets loaded with the process’s ending physical
address
• When a relative addresses is encountered,
– Relative address is added with the content of the base register to
obtain the physical address
– Physical address is compared with the content of the bound
register
» If address is within bounds, the instruction execution may
proceed
» Otherwise an interrupt is generated

Surafel Lemma Abebe (Ph. D.) 34

 Memory partitioning…
• Relocation….
– Address translation…

Surafel Lemma Abebe (Ph. D.) 35

 Paging
• Main memory is partitioned into equal fixed-sized
chunks (of relatively small size) called frames
• Each process is also divided into chunks of the
same size called pages
• The process pages can thus be assigned to the
available chunks in main memory called frames
(or page frames)
• Advantage
– A process does not need to occupy a contiguous
portion of memory

Surafel Lemma Abebe (Ph. D.) 36

 Paging…
• Example
– Process B is swapped out (e)
– Load a new process D with 5 pages. Can D be loaded in memory?
• Yes, see (f)
– Observation
• Process D doesn’t hold contiguous frames
• No external fragmentation

Surafel Lemma Abebe (Ph. D.) 37

 Paging…
• How can we reference data?
– Logical address
• Is a single base address register enough?
– No
– OS maintains a page table for each process
– Page table
• Shows the frame location for each page of the process
• Used to translate logical addresses to physical addresses
– Example: page table during (f) of previous example
• OS also maintains a single free frame list

Surafel Lemma Abebe (Ph. D.) 38

 Paging…
• Logical addressing
– Within the program logical address consists
• Page number
– Used as an index into a page table which contains
base address of each page in physical memory
• Offset within the page
– Combined with base address to define the physical
memory address
– For convenience
• Page size and frame size are a power of 2
– Example
• If 16 bits addresses are used and page size = 1K,
we need 10 bits for offset and have 6 bits
available for page number
• Then the 16 bit address obtained with the 10
least significant bit as offset and 6 most
significant bit as page number is a location
relative to the beginning of the process

Surafel Lemma Abebe (Ph. D.) 39

 Paging…
• Address translation
p = page number
d= page offset

Surafel Lemma Abebe (Ph. D.) 40

 Paging…
• Address translation…
– Example

Surafel Lemma Abebe (Ph. D.) 41

 Paging…
• Advantage of using a page size that is a power of 2
– Logical address scheme is transparent to
• The programmer
• The assembler
• The linker
– Logical address (page number, offset) of a program is
identical to its relative address
– Simplifies implementation of a function in hardware to
perform a dynamic address translation at run time

Surafel Lemma Abebe (Ph. D.) 42

 Segmentation
• Used to subdivide user program into a number
of segments
• Unlike frames and pages, segments could be of
different sizes
– There is no simple relationship between logical
addresses and physical addresses

• Segmentation is visible to the programmer

– Provided as a convenience to organize programs
logically (e.g., data in one segment, code in
another segment)
– Programmers must be aware of segment size limit

Surafel Lemma Abebe (Ph. D.) 43

 Segmentation…
• OS maintains a segment table for each process
• Segment table entry contains
– Starting physical addresses of each segment in main memory
– Length of that segment (for protection)

• When a process enters the running state, the address of its

segment table is loaded into a special register used by the
memory management hardware

Surafel Lemma Abebe (Ph. D.) 44

 Segmentation…
• Address translation
– Consider a logical address of s + d bits
s bits are the segment number
d bits are the offset
– Steps
1. Extract the segment number as the leftmost s bits of the logical
address
2. Use the segment number as an index into the process segment
table to find the starting physical address of the segment
3. Compare the offset, expressed in the rightmost d bits, to the
length of the segment
– If the offset is greater than or equal to the length, the address is invalid
4. Sum the starting physical address of the segment with the offset
to get the desired physical address

Surafel Lemma Abebe (Ph. D.) 45

 Segmentation…
• Address translation…
– Segmentation hardware

Surafel Lemma Abebe (Ph. D.) 46

 Segmentation…
• Example
– Segment 1, offset 752

Surafel Lemma Abebe (Ph. D.) 47

 Virtual memory-overview
• Limitation of previous approaches
– Require that an entire process be in memory before it can execute
• Virtual memory
– Involves separation of logical memory as perceived by users from
physical memory

• Benefits of virtual memory

– Allows programs to be larger than the physical memory
– Less I/O would be needed to load or swap user programs into memory
– Abstracts memory into large, uniform array of storage
– Allows processes to share files
– Allows execution of processes that are not completely in memory
• More programs could be run at the same time

Surafel Lemma Abebe (Ph. D.) 48

 Virtual memory-overview…
• Why is it not necessary to have all code in
memory?
– Part of a program that handle unusual error
condition may never be executed
– Arrays, lists, and tables are often allocated more
memory than they actually need
– Some features of a program may be used rarely

Surafel Lemma Abebe (Ph. D.) 49