Memory Management

Reading:
Silberschatz
chapter 9
Reading:
Stallings
chapter 7
EEL 602 1
Outline
¾ Background
¾ Issues in Memory Management
¾ Logical Vs Physical address, MMU
¾ Dynamic Loading
¾ Memory Partitioning
„ Placement Algorithms
„ Dynamic Partitioning
¾ Buddy System
¾ Paging
¾ Memory Segmentation
¾ Example – Intel Pentium

EEL 602 2
Background
¾ Main memory → fast, relatively high cost, volatile

¾ Secondary memory → large capacity, slower, cheaper

than main memory and is usually non volatile

¾ The CPU fetches instructions/data of a program from

memory; therefore, the program/data must reside in the
main (RAM and ROM) memory

¾ Multiprogramming systems → main memory must be

subdivided to accommodate several processes

¾ This subdivision is carried out dynamically by OS and

known as memory management

EEL 602 3
Issues in Memory Management
¾ Relocation: Swapping of active process in and out of
main memory to maximize CPU utilization
„ Process may not be placed back in same main memory region!
„ Ability to relocate the process to different area of memory

¾ Protection: Protection against unwanted interference by

another process
Must be ensured by processor (hardware) rather than OS

¾ Sharing: Flexibility to allow several process to access the

same portions of the main memory

¾ Efficiency: Memory must be fairly allocated for high

processor utilization, Systematic flow of information
between main and secondary memory
EEL 602 4
Binding of Instructions and Data to Memory

Compiler → Generates Object Code

Linker → Combines the Object code into

a single self sufficient executable code

Loading → Copies executable

code into memory

Execution → dynamic memory allocation

EEL 602 5
Binding of Instructions and Data to Memory
Address binding of instructions and data to memory addresses can
happen at three different stages

¾ Compile time: If memory location known a priori,

absolute code can be generated; must recompile code if
starting location changes

¾ Load time: Must generate relocatable code if memory

location is not known at compile time

¾ Execution time: Binding delayed until run time if the

process can be moved during its execution from one
memory segment to another → most general purpose OS

EEL 602 6
Logical Vs Physical Address Space
¾ Each logical address is bound to physical
address space;
„ Logical address – generated by the CPU; also
referred to as virtual address
„ Physical address – address seen by the memory unit

¾ Logical and physical addresses ;

„ Identical in compile-time and load-time address-
binding schemes
„ Differ in execution-time address-binding scheme
„ Logical address ↔ Virtual address

EEL 602 7
Memory-Management Unit (MMU)
¾ The runtime mapping from virtual → physical address

¾ Relocation register is added to every address →

generated by user process

¾ The user program → logical addresses, it never sees

the real physical addresses
EEL 602 8
Dynamic Loading
¾ Routine is not loaded until it is called

¾ Better memory-space utilization → unused

routine is never loaded

¾ Useful to handle infrequently occurring cases,

e.g. error handling routines

¾ No special support from the OS required

implemented through user program design

EEL 602 9
Memory Partitioning
Two schemes – used in several variations of now-obsolete OS
¾ Fixed Partitioning: OS occupies fixed portion of main memory, rest available for
multiple processes. Two alternatives;
„ Equal size fixed partitions → any process ≤ partition size can be loaded
„ Unequal size partitions → several unequal size partitions, process of matching sizes

¾ Problems with equal size fixed partitions:

„ If program is bigger than a partition size, use of overlays
„ Main memory utilization is extremely inefficient; Internal Fragmentation – waste of space
internal to partition due to the fact that block of data loaded is smaller than partition

EEL 602 10
Unequal-Size Partitions
Assign each processes the smallest partition to which it will fit
¾ Advantages:
„ Process are always assigned in such a way as to minimize
wasted memory within a partition → internal fragmentation
„ Relatively simple and require minimal OS software and
overhead

¾ Disadvantages:
„ Limitations on the active number of processes, number of
partitions specified at system generation time
„ Small jobs cannot utilize partition space efficiently; In most
cases it is an inefficient technique

EEL 602 11
Placement Algorithm with Partitions
¾ Equal-size partitions
„ Because all partitions are of equal size, it does not
matter which partition is used

¾ Unequal-size partitions
„ Can assign each process to the smallest partition
within which it will fit
„ Queue for each partition size
„ Processes are assigned in such a way as to minimize
wasted memory within a partition

EEL 602 12
Placement Algorithm with Partitions

EEL 602 13
Dynamic Partitioning
Developed to address the drawbacks of fixed partitioning

¾ Partitions of variable length and number; Process in bought into main

memory, it is allocated exactly as much memory as it requires

¾ Leaves Holes
„ First at the end → eventually lot of small holes
„ Memory becomes more fragmented with time, memory utilization ↓

¾ External Fragmentation
„ Memory that is external to all partitions becomes increasingly fragmented

¾ Compaction
„ Used to overcome external fragmentation
„ OS shifts processes so that free memory is together in one block
„ Compaction requires use of dynamic relocation capability
„ Time consuming procedure and wasteful of processor time

EEL 602 14
Dynamic Partitioning

EEL 602 15
Placement Algorithms
Compaction is time consuming → OS must be clever in plugging holes
while assigning processes to memory

¾ Three placement algorithms → Selecting among free

blocks of main memory

¾ Best-Fit: Closest in size to the request

¾ First-Fit: Scans the main memory from the beginning

and first available block that is large enough

¾ Next-Fit: Scans the memory from the location of last

placement and chooses next available block that is large
enough
EEL 602 16
Placement Algorithms - Example
Allocation of 16 MB block using three placement algorithms

EEL 602 17
Placement Algorithms
¾ Which of the above approaches is the best?
Process Size/Sequence, General Comments
„ First-Fit → Simplest, usually the best and fastest

„ Next-Fit → Slightly worst results with next fit

Compaction may be more frequently required

„ Best-Fit→ Usually the worst performer; main memory

is quickly littered by blocks too small to satisfy
memory allocation requests
Compaction - more frequently than other algorithms

EEL 602 18
Buddy System
¾ Drawbacks
„ Fixed partitioning: Limits number of active process, inefficient
if poor match between partition and process sizes
„ Dynamic Partitioning: Complex to maintain, includes the
overhead of compaction
¾ Compromise may be the 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

EEL 602 19
Buddy System - Example
Initial block size 1 MB; First request A is for 100 KB

EEL 602 20
Buddy System - Example
Binary tree representation immediately after Release B request.

EEL 602 21
Relocation
¾ A process may occupy different partitions which means different
absolute memory locations during execution (from swapping)

¾ Compaction will also cause a program to occupy a different partition

which means different absolute memory locations

EEL 602 22
Paging
¾ Partitioning main memory → small equal fixed-size chunks
„ Each process is divided into the same size chunks → pages
„ Chunks of memory → frames or page frames

¾ Advantages
„ No external fragmentation
„ Internal fragmentation → only a fraction of last page of a process

¾ OS maintains a page table for each process

„ Contains frame location for each page in the process
„ Memory address → a page number, a offset within the page
„ Processor hardware → logical-to-physical address translation

EEL 602 23
Paging - Example
Assignment of process pages to free frames

EEL 602 24
Paging - Example
Assignment of process pages to free frames.

EEL 602 25
Paging - Example
Data structures for page tables at time epoch (f)

EEL 602 26
Paging - Example
¾ Convenience in Paging scheme
„ Frame size → power of 2
„ Relative address (wrt origin of program) and the logical address
(page # and offset) are same
„ Example - 16 bit address, page size → 1K or 1024 bytes
Š Maximum 64 (26) pages of 1K bytes each

¾ Advantages
„ Logical addressing → transparent to programmer, assembler, linker
„ Relatively easy to implement a function to perform dynamic
address translation at run time

EEL 602 27
Paging - Example

EEL 602 28
Paging - Example
Logical-to-physical address translation in Paging

EEL 602 29
Paging - Example
Logical-to-physical address translation in Paging

EEL 602 30
Implementation of Page Table
¾ Different methods of storing page tables, OS dependent
¾ Pointer to page table → PCB
¾ Hardware implementation of page tables
„ Page table → Set of dedicated high speed registers, Simplest
„ Suitable for small page table sizes, Usually very large
requirements
¾ Page table is kept in main memory
„ Page-table base register (PTBR) points to the page table
„ Two memory access, page table and other for data/instruction
„ Memory access slowed by a factor of two
¾ Solution to the two memory access problem
„ Usage of a special fast-lookup hardware cache called
associative memory or translation look-aside buffers (TLBs)
„ TLB contains Page # → Frame #, Small # of TLB entries (64-
1024)

EEL 602 31
Paging Hardware With TLB

EEL 602 32
Shared Pages
¾ Shared code
„ One copy of read-only (reentrant) code shared
among processes, e.g. text editors, compilers
„ Shared code must appear in same location in the
logical address space of all processes

¾ Private code and data

„ Each process keeps a separate copy of the code and
data
„ The pages for the private code and data can appear
anywhere in the logical address space

EEL 602 33
Shared Pages Example

Sharing of code in paging environment

EEL 602 34
Segmentation
¾ Memory-management scheme that supports user view of
memory
¾ Program → Collection of segments (name and length)
¾ Complier automatically constructs segments reflecting
input program
¾ Example – A C complier might create separate
segments for the following
main program,
procedure,
function,
object,
local variables, global variables,
common block,
stack,
symbol table, arrays

EEL 602 35
Segmentation
¾ The program/process and its associated data is divided
into a number of segments

¾ 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
EEL 602 36
Address Translation Architecture

EEL 602 37
User’s View of a Program

EEL 602 38
Logical View of Segmentation
1

4
1

3 2
4

user space physical memory space

EEL 602 39
Example of Segmentation

EEL 602 40
Sharing of Segments

EEL 602 41
Segmentation
¾ Compared to dynamic partition, segmentation program may occupy
more than one partition and these partitions need not be contiguous

¾ Segmentation eliminates the need for internal fragmentation but like

dynamic partitioning it suffers from external fragmentation

¾ Process is broken in small pieces, the external fragmentation is less

with segmentation than dynamic partition

¾ Paging is invisible to the programmer, segmentation is usually visible

EEL 602 42
Segmentation
EXAMPLE: Logical Addresses.

EEL 602 43
Segmentation
EXAMPLE:
Logical-to-physical address translation in Segmentation

EEL 602 44
Hierarchical Page Tables
¾ Most systems support a large logical address space
„ 232 – 264 , page table itself becomes excessively large
¾ Break up the logical address space into multiple page
tables

¾ A simple technique is a two-level page table

EEL 602 45
Two-Level Paging Example
¾ A logical address (32-bit machine with 4K page size) is divided into:
„ a page number consisting of 20 bits
„ a page offset consisting of 12 bits
¾ Since the page table is paged, page number is further divided into:
„ a 10-bit page number
„ a 10-bit page offset
¾ Thus, a logical address is as follows:

page number page offset

pi p2 d

10 10 12

where pi is an index into the outer page table, and p2 is the

displacement within the page of the outer page table

EEL 602 46
Two-Level Page-Table Scheme

EEL 602 47
Address-Translation Scheme
¾ Address-translation scheme for a two-level 32-bit
paging architecture

EEL 602 48