UNIT-IV Memory Management

! Background
! Swapping
! Contiguous Allocation
! Paging
! Segmentation
! Segmentation with
! Paging

Operating System Concepts 9.1 Silberschatz, Galvin and Gagne Ó2002

 Background

! Program must be brought into memory and placed as a

process for it to be run.

! Input queue – collection of processes on the disk that are

waiting to be brought into memory to run the program.

! User programs go through several steps before being

run.

Operating System Concepts 9.2 Silberschatz, Galvin and Gagne Ó2002

 Performance Measures for Various
Memory Management Schemes

• Wasted Memory ( internal, external and table fragmentation)

• Time Complexity
• Memory Access overhead

Objectives of the Ideal Memory Manager

• To minimize wasted memory

• To have minimal time complexity and memory access overhead
•To provide good protection and flexible sharing

Operating System Concepts 9.3 Silberschatz, Galvin and Gagne Ó2002

 Two Conflicting requirements of a
memory Manager

Operating System Concepts 9.4 Silberschatz, Galvin and Gagne Ó2002

 Address Binding

Operating System Concepts 9.5 Silberschatz, Galvin and Gagne Ó2002

 Contd…

Operating System Concepts 9.6 Silberschatz, Galvin and Gagne Ó2002

 Logical vs. Physical Address Space

! The concept of a logical address space that is bound to a

separate physical address space is central to proper
memory management.
! Logical address – generated by the CPU; also referred to as
virtual address.
! Physical address – address seen by the memory unit.
! Relocation: implies binding of logical addresses to
Physical addresses
! The compile-time and load-time address-binding methods
generate identical logical and physical addresses.

Operating System Concepts 9.7 Silberschatz, Galvin and Gagne Ó2002

 Memory-Management Unit (MMU)

! Hardware device that maps virtual to physical address.

! In MMU scheme, the value in the relocation register is

added to every address generated by a user process at
the time it is sent to memory.

! The user program deals with logical addresses; it never

sees the real physical addresses.

Operating System Concepts 9.8 Silberschatz, Galvin and Gagne Ó2002

 Basic Hardware for Memory
Management

!Relocation-register scheme used to protect user processes from each

other, and from changing operating-system code and data.( accidental
or malicious)
!Relocation register contains value of smallest physical address; limit
register represents range of logical addresses – each logical address
must be less than the limit register.

Operating System Concepts 9.9 Silberschatz, Galvin and Gagne Ó2002

 Static Vs Dynamic Relocation

! Relocatability : It refers to load and execute a given

program into an arbitrary place in memory, as opposed to
a fixed set of locations assigned at program translation
time.
! Static Relocation: Usually implies that the relocation is
performed before loading (linker) or during the
loading(loader) of the program in memory. Process must
always be loaded into same address space in memory, or
relocator must be run again.
! Dynamic Relocation: Implies that mapping from the
logical(virtual) address space to the physical address
space is performed at run time usually with some
hardware assistance. Process can be freely moved
around in memory.

Operating System Concepts 9.10 Silberschatz, Galvin and Gagne Ó2002

 Dynamic relocation using a relocation register

Operating System Concepts 9.11 Silberschatz, Galvin and Gagne Ó2002

 Swapping

" A process can be swapped temporarily out of memory to a

backing store, and then brought back into memory for continued
execution.

" Backing store – fast disk large enough to accommodate copies

of all memory images for all users; must provide direct access to
these memory images.

" Roll out, roll in – swapping variant used for priority-based

scheduling algorithms; lower-priority process is swapped out so
higher-priority process can be loaded and executed.

" Major part of swap time is transfer time; total transfer time is
directly proportional to the amount of memory swapped.

" Modified versions of swapping are found on many systems, i.e.,

UNIX, Linux, and Windows.

Operating System Concepts 9.12 Silberschatz, Galvin and Gagne Ó2002

 Schematic View of Swapping

Operating System Concepts 9.13 Silberschatz, Galvin and Gagne Ó2002

 Memory Management Schemes
! Contiguous Allocation
! Single-partition allocation
! Multi-Partition Allocation
# Static /Fixed Partition Allocation
# Dynamic / Variable Partition Allocation

! Non-Contiguous Allocation
! Paging
! Segmentation
! Combined Systems

! Virtual Memory Management

! Demand Paging
! Demand Segmentation

Operating System Concepts 9.14 Silberschatz, Galvin and Gagne Ó2002

 Contiguous Allocation

! Contiguous allocation means that each logical

object is placed in a set of memory locations
with strictly consecutive addresses
! It can be of two types
" Single-partition allocation
" Multi-Partition Allocation
" Static /Fixed Partition Allocation
" Dynamic / Variable Partition Allocation

Operating System Concepts 9.15 Silberschatz, Galvin and Gagne Ó2002

 Single Partition Allocation

! Main memory usually divided into two partitions:

! Resident operating system, usually held in low memory
with interrupt vector.
! User processes then held in high memory.

Operating System Concepts 9.16 Silberschatz, Galvin and Gagne Ó2002

 Contiguous Allocation (Cont.)

! Multiple-partition allocation

! Static(fixed) Partitioning Vs Dynamic(Variable) Partitioning

! Hole – block of available memory; holes of various sizes are

scattered throughout memory.

! When a process arrives, it is allocated memory from a hole

large enough to accommodate it.

! Operating system maintains information about:

a) allocated partitions (PDT-Partition Description Table)

b) free partitions (Free list , only with D.P. Scheme)

Operating System Concepts 9.17 Silberschatz, Galvin and Gagne Ó2002

 Static Vs Dynamic Partitioning

Static/Fixed Dynamic/Variable
Principle Number of Number of partitions and
partitions and size size of each partition is
of each partition is changing as per memory
fixed at system requirements of processes
generation time
Advantage Simple to Internal fragmentation is
implement minimized
Disadvantages • Internal • External Fragmentation
Fragmentation, • Degree of MP limited
• limited degree of only by available
MP memory

Allocation First Fit, Next Fit, First Fit, Next Fit, Best Fit,
algorithms and Best Fit and Worst Fit

Operating System Concepts 9.18 Silberschatz, Galvin and Gagne Ó2002

 Fragmentation

! External Fragmentation – total memory space exists to satisfy a

request, but it is not contiguous.
! Internal Fragmentation – allocated memory may be slightly larger
than requested memory; this size difference is memory internal to a
partition, but not being used.
! Disadvantages of Multi- Partitioned Allocation schemes
! S.P. Suffers from internal Fragmentation
! D. P. Suffers mainly from external fragmentation
! Reduce external fragmentation by compaction
! Shuffle memory partitions to place all free memory together into one
large block – Known as Compaction or Garbage Collection.
! Compaction is possible only if relocation is dynamic, and is done at
execution time.
! Coalescing of adjacent free partitions (holes) is the another remedy

Operating System Concepts 9.19 Silberschatz, Galvin and Gagne Ó2002

 Static Storage-Allocation Problem

How to satisfy a request of size n from a list of free partitions(hole).

! First-fit: Allocate the first hole that is big enough.

! Best-fit: Allocate the smallest hole that is big enough; must
search entire list, unless ordered by size.
! Next-fit: Next fit is a modified version of ‘first fit’. It begins as
the first fit to find a free partition but when called next time it
starts searching from where it left off, not from the beginning.

First-fit and best-fit better than worst-fit in terms of

speed and storage utilization.

Operating System Concepts 9.20 Silberschatz, Galvin and Gagne Ó2002

 Dynamic Storage-Allocation Problem

! How to satisfy a request of size n from a list of free holes ?

! First-fit:
! Next-fit :
! Best Fit:
! Worst-fit:

Unlike static portioning the remaining free space is declared as a

new free partition.
First-fit and best-fit better than worst-fit in terms of speed and
storage utilization.

Operating System Concepts 9.21 Silberschatz, Galvin and Gagne Ó2002

 Examples

1. Given a system with static memory partitioning and free

memory partitions of 100 KB, 500KB, 200KB, 300KB
and 600KB(in order), how would each of the first fit,
and best fit algorithms place processes of 212 KB, 417
KB, 112 KB and 426KB (in order)? Which algorithm
makes the most efficient use of memory in this case?
Justify your answer.

2. Given a system with dynamic memory partitioning and

free memory partitions of 100 KB, 500KB, 200KB,
300KB and 600KB(in order), how would each of the first
fit, best fit and worst fit algorithms place processes of
212 KB, 417 KB, 112 KB and 426KB (in order)? Which
algorithm makes the most efficient use of memory in this
case? Justify your answer.

Operating System Concepts 9.22 Silberschatz, Galvin and Gagne Ó2002

 Handling external fragmentation
# Compaction or garbage collection:
! Shuffle memory partitions to place all free memory together in one large
block.
! Compaction is possible only if relocation is dynamic, and is done at
execution time.
! Compaction is a costly operation as it requires to copy memory blocks
allocated to processes
! When: process departs or upon failure to allocate a suitable partition
! How: Selective move (relocate some partitions) or global (relocate all
partitions)
# Coalescing:
! Combine small contagious free memory blocks to create a
larger hole suitable for allocation.
! Coalescing doesn’t require relocation whereas compaction
requires relocation of partitions being moved

Operating System Concepts 9.23 Silberschatz, Galvin and Gagne Ó2002

 Non Contiguous Allocation
1. Paging

" Divide physical memory into fixed-sized blocks called frames (size is
power of 2, typically between 512 bytes and 8192 bytes).
" Divide logical 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 logical addresses to physical
addresses.
" In this scheme physical address space of a process can be non-
contiguous; i.e. process is allocated physical memory whenever it is
available.
" External fragmentation is eliminated, a small internal fragmentation is
still there.

Operating System Concepts 9.24 Silberschatz, Galvin and Gagne Ó2002

 Address Translation Scheme

! Address generated by CPU is divided into:

! Page number (p) – used as an index into a page table which
contains frame number of each page in physical memory.

! Page offset (d) – combined with page number to define the

physical memory address that is sent to the memory unit.

Operating System Concepts 9.25 Silberschatz, Galvin and Gagne Ó2002

 Paging Example

Operating System Concepts 9.26 Silberschatz, Galvin and Gagne Ó2002

 Address Translation Architecture

Operating System Concepts 9.27 Silberschatz, Galvin and Gagne Ó2002

 Paging Example

Address translation for item g

Page size =4 bytes, Physical memory 32 bytes

Logical address (1,2)-> Physical address (6,2)

Physical Address Length =

(Page number 3 bits + offset 2 bits)

Address Translation(LA->PA)

PA=(Frame Number x Page Size) + Offset

= (6x4)+2=26

OR

PA=Strcat (Frame no., offset)

Operating System Concepts 9.28 Silberschatz, Galvin and Gagne Ó2002

 Example

Consider a logical address space of 8 pages of 1024 words mapped into physical

memory of 32 frames.

i. How many bits are there in the logical address?

ii. How many bits are there in physical address?

iii. What is the linear address (in decimal) of physical memory for the item stored at

logical address given by (3,100) if page 3 is stored in frame 17?

Operating System Concepts 9.29 Silberschatz, Galvin and Gagne Ó2002

 Free Frames

Before allocation After allocation

Operating System Concepts 9.30 Silberschatz, Galvin and Gagne Ó2002

 Implementation of Page Table

! Page table is kept in main memory.

! Page-table base register (PTBR) points to the page table.
! Page-table length register (PRLR) indicates size of the
page table.
! In this scheme every data/instruction access requires two
memory accesses. One for the page table and one for
the data/instruction.
! The two memory access problem can be solved by the
use of a special fast-lookup hardware cache called
associative memory or translation look-aside buffers
(TLBs)

Operating System Concepts 9.31 Silberschatz, Galvin and Gagne Ó2002

 Associative Memory or TLB

! Associative memory – parallel search

! It is a fast-lookup hardware cache

Page # (key) Frame # (value)

Px Fx
Py Fy
Page #
Pz Fz
Pw Fw

! Address translation
! If the key P# is in associative register, get frame F# out.
! Otherwise get frame # from page table in memory

Operating System Concepts 9.32 Silberschatz, Galvin and Gagne Ó2002

 Paging Hardware With TLB
• TLB: Translation Lookaside Buffer, is. A small (64-1024 entries)
fast lookup hardware cache
• It is an associative high-speed memory

Operating System Concepts 9.33 Silberschatz, Galvin and Gagne Ó2002

 Effective Access Time

! Hit ratio – percentage of times that a page number is found in the

associative registers; ratio is related to the number of associative
registers.
! Hit ratio = a
! EAT = a (Hit_Time) + (1- a) (Miss_Time)

! Example:
Consider a paging system with TLB to store frequently used entries in
the page table. The system has 98% hit ratio, 20 nano-seconds time
to search the associative registers, 100 nano-seconds time to access
memory. Find the effective memory access time for this paging
system

Operating System Concepts 9.34 Silberschatz, Galvin and Gagne Ó2002

 Effect of Page Size on performance of Memory
Manager

System parameters of memory manager

Internal Degree of Page Table Frag.
Page Size Frag. MP Transport
Efficiency
SMALL Reduced High Low Increased
LARGE Increased Low High Reduced

Operating System Concepts 9.35 Silberschatz, Galvin and Gagne Ó2002

 Memory Protection

! Memory protection implemented by associating protection

bit with each frame.

! 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.

Operating System Concepts 9.36 Silberschatz, Galvin and Gagne Ó2002

 Valid (v) or Invalid (i) Bit In A Page Table

Operating System Concepts 9.37 Silberschatz, Galvin and Gagne Ó2002

 Shared Pages

! Shared code
! One copy of read-only (reentrant) code shared among
processes (i.e., text editors, compilers, window systems).
! 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.

Operating System Concepts 9.38 Silberschatz, Galvin and Gagne Ó2002

 Shared Pages Example

Operating System Concepts 9.39 Silberschatz, Galvin and Gagne Ó2002

 Segmentation

" 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,
stack,
symbol table, arrays

Operating System Concepts 9.40 Silberschatz, Galvin and Gagne Ó2002

 User’s View of a Program

Operating System Concepts 9.41 Silberschatz, Galvin and Gagne Ó2002

 Logical View of Segmentation

4
1

3 2
4

user space physical memory space

Operating System Concepts 9.42 Silberschatz, Galvin and Gagne Ó2002

 Segmentation Architecture

! Logical address consists of a two tuple:

<segment-number, offset>,
! Segment table – maps two-dimensional physical
addresses; each table entry has:
! base – contains the starting physical address where the
segments reside in memory.
! limit – specifies the length of the segment.
! Segment-table base register (STBR) points to the
segment table’s location in memory.
! Segment-table length register (STLR) indicates number of
segments used by a program;
segment number s is legal if s < STLR.

Operating System Concepts 9.43 Silberschatz, Galvin and Gagne Ó2002

 Segmentation Architecture (Cont.)

! Protection. With each entry in segment table associate:

! validation bit = 0 Þ illegal segment
! read/write/execute privileges
! Protection bits associated with segments; code sharing
occurs at segment level.
! Since segments vary in length, memory allocation is a
dynamic storage-allocation problem, and hence suffers
from external fragmentation.
! A segmentation example is shown in the following
diagram

Operating System Concepts 9.44 Silberschatz, Galvin and Gagne Ó2002

 Segmentation Hardware

Operating System Concepts 9.45 Silberschatz, Galvin and Gagne Ó2002

 Example of Segmentation

Operating System Concepts 9.46 Silberschatz, Galvin and Gagne Ó2002

 Sharing of Segments

Operating System Concepts 9.47 Silberschatz, Galvin and Gagne Ó2002

 Summary

Paging Segmentation
All Partitions are of the same size Partitions are of varying sizes
Similar to static partitioning Similar to dynamic partitioning
Does not support user view of memory Supports user view of memory
Logical address (page number, offset) Logical address (segment number, offset)
Address mapping done using Page Table Address mapping done using Segment
Table
Suffers from internal fragmentation Suffers from external fragmentation

Qu. What is the similarity?

Operating System Concepts 9.48 Silberschatz, Galvin and Gagne Ó2002

 Quiz

Physical address is a address

A. loaded into the memory address register

B. generated by MMU

C. generated by CPU

D. None

Operating System Concepts 9.49 Silberschatz, Galvin and Gagne Ó2002

 Quiz

In dynamic partitioning, coalescing of holes

A. minimize the effect due to internal fragmentation

B. maintain fragmentation within usable limits

C. minimize the effect due to external fragmentation

D. none of the above

Operating System Concepts 9.50 Silberschatz, Galvin and Gagne Ó2002

 Quiz

The following policies of dynamic storage allocation

will allocate the smallest hole that is big enough to
satisfy a request for a block

A. first fit
B. best fit
C. worst fit
D. none of the above

Operating System Concepts 9.51 Silberschatz, Galvin and Gagne Ó2002

 Quiz

Paging systems reduces effective memory

bandwidth by a factor of

A. 1/3

B. 2/3

C. 1/2

Operating System Concepts 9.52 Silberschatz, Galvin and Gagne Ó2002

 Quiz

The following fragmentation (s) does not occur in paging

A. external fragmentation

B. internal fragmentation

C. table fragmentation

D. none of the above

Operating System Concepts 9.53 Silberschatz, Galvin and Gagne Ó2002

 Quiz

The disadvantages of large page size are

A. Low page transport efficiency

B. Increased table fragmentation

C. Increased internal fragmentation

D. Low degree of Multiprogramming

E. None of the above

Operating System Concepts 9.54 Silberschatz, Galvin and Gagne Ó2002

 Quiz

Which of the following is true about Translation

lookaside Buffer(TLB)

A. it is an associate memory
B. it is maintained on Secondary Storage
C. it reduces effective memory access time
D. none

Operating System Concepts 9.55 Silberschatz, Galvin and Gagne Ó2002

 Quiz

Combined paged segmentation system reduces effective

memory bandwidth , by a factor of

A. 1/2

B. 1/3

C. 2/3

Operating System Concepts 9.56 Silberschatz, Galvin and Gagne Ó2002

 Quiz

This page replacement algorithm choses the oldest page

for replacement

A. FIFO
B. Optimal
C. LRU
D. MFU

Operating System Concepts 9.57 Silberschatz, Galvin and Gagne Ó2002

 Quiz

The following page replacement algorithm does not

suffer from Belady's anomaly

A. LRU
B. FIFO
C. Optimal
D. None of the above

Operating System Concepts 9.58 Silberschatz, Galvin and Gagne Ó2002

 Quiz

Optimal page replacement algorithm

A. Is a yardstick for measuring performance of other

algorithms

B. Can never be implemented in practice

C. require the knowledge of future memory references

D. none of above

Operating System Concepts 9.59 Silberschatz, Galvin and Gagne Ó2002

 Quiz

This page replacement algorithm requires to note for each

page, the time when that page was brought into memory

A. None of the above

B. Optimal
C. FIFO
D. LRU

Operating System Concepts 9.60 Silberschatz, Galvin and Gagne Ó2002

 Quiz

This page replacement algorithm requires to record the

time of that page's last use, for each page

A. Clock
B. FIFO
C. LRU
D. LFU
E. None of the above

Operating System Concepts 9.61 Silberschatz, Galvin and Gagne Ó2002

 Quiz

This page replacement algorithm then will replace a page that has not been
used for the longest period of time

A. FIFO
B. LRU
C. Optimal
D. LFU
E. None of the above

Operating System Concepts 9.62 Silberschatz, Galvin and Gagne Ó2002

 Quiz

This page replacement algorithm will replace the page

that will not be used for the longest period of time

A. LRU
B. FIFO
C. Optimal
D. LFU
E. None of the above

Operating System Concepts 9.63 Silberschatz, Galvin and Gagne Ó2002

 Quiz

The page class algorithm for page replacement is based

on the status of following bits

A. presence bit
B. modified bit
C. reference bit
D. none of the above
E. All of the above

Operating System Concepts 9.64 Silberschatz, Galvin and Gagne Ó2002

 Quiz

This algorithm requires to maintain the count of page

references for each page

A. Clock
B. Optimal
C. LFU
D. LRU
E. FIFO
F. None of the above

Operating System Concepts 9.65 Silberschatz, Galvin and Gagne Ó2002

 Quiz

Thrashing

A. is a high paging activity

B. is caused by global replacement policy
C. is caused by excessive degree of Multiprogramming
D. is caused by local replacement algorithm
E. None of the above

Operating System Concepts 9.66 Silberschatz, Galvin and Gagne Ó2002

 Quiz

To enable a process to be larger than the amount of

memory allocated to it , we can use

A. overlays
B. virtual memory
C. none

Operating System Concepts 9.67 Silberschatz, Galvin and Gagne Ó2002

 Quiz

Virtual memory is a technique that

A. allows the execution of process that may not be completely in

memory
B. facilitates the OS to increase the degree of Multiprogramming
C. allows each process to be larger than the available physical
memory
D. none of above

Operating System Concepts 9.68 Silberschatz, Galvin and Gagne Ó2002

 Quiz

We can limit the effects of thrashing by using

A. global replacement algorithm

B. working set theory
C. local replacement algorithm
D. None

Operating System Concepts 9.69 Silberschatz, Galvin and Gagne Ó2002