Unit V

Memory Management
 Contents

◼ Memory Management Requirements

◼ Memory Partitioning: Fixed and Variable Partitioning,

◼ Allocation Strategies (First Fit, Best Fit, and Worst Fit), Fragmentation,
Swapping.

◼ Virtual Memory: Concepts, Segmentation, Paging, Address Translation,

◼ Page Replacement Policies (FIFO, LRU, Optimal, Other Strategies),

◼ Thrashing.
 Introduction

CPU Memory

Computer

• Desirable properties of memory

• Size -more

• Access time -less

• Per unit cost -less

 Introduction

Secondary
Main memory memory
CPU Cache
memory
• This Memory Hierarchy Design is divided into 2 main types:

1. External Memory or Secondary Memory –

Comprising of Magnetic Disk, Optical Disk, Magnetic Tape i.e. peripheral
storage devices which are accessible by the processor via I/O Module.

2. Internal Memory or Primary Memory –

Comprising of Main Memory, Cache Memory & CPU registers. This is
directly accessible by the processor.
• characteristics of Memory Hierarchy Design

• Capacity:
It is the global volume of information the memory can store. As we move
from top to bottom in the Hierarchy, the capacity increases.

• Access Time:
It is the time interval between the read/write request and the availability
of the data. As we move from top to bottom in the Hierarchy, the access
time increases.

•
• Performance:
Earlier when the computer system was designed without Memory Hierarchy
design, the speed gap increases between the CPU registers and Main
Memory due to large difference in access time. This results in lower
performance of the system and thus, enhancement was required. This
enhancement was made in the form of Memory Hierarchy Design because
of which the performance of the system increases. One of the most
significant ways to increase system performance is minimizing how far
down the memory hierarchy one has to go to manipulate data.

• Cost per bit:

As we move from bottom to top in the Hierarchy, the cost per bit increases
i.e. Internal Memory is costlier than External Memory.
 Memory Management

◼ In a uniprogramming system, main memory is divided into two parts:

• one part for the operating system (resident monitor, kernel) and

• one part for the program currently being executed.

◼ In a multiprogramming system, the “user” part of memory must be further

subdivided to accommodate multiple processes.

◼ The task of subdivision is carried out dynamically by OS is known as

Memory Management.

◼ Memory needs to be allocated to ensure a reasonable supply of ready

processes to consume available processor time.

◼ Memory Management, involves swapping blocks of data from secondary

storage
 Execution of a Program
◼ Operating system brings into main memory a few pieces of the program.

◼ Resident set - portion of process that is in main memory.

◼ An interrupt is generated when an address is needed that is not in main

memory.

◼ Operating system places the process in a blocking state.

 Memory Management Requirements

1. Relocation

2. Protection

3. Sharing

4. Logical organisation

5. Physical organisation
 Memory Management Terms

Term Description
Frame Fixed-length block of main
memory.
Page Fixed-length block of data in
secondary memory (e.g. on disk).
Segment Variable-length block of data that
resides in secondary memory.
 Memory Management Requirements
1. 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.
Addressing
The OS needs to know the location
of:
•process control information
• the execution stack,
• the entry point to begin
execution of the program for
this process.

There will be memory references

within the program
Eg. BT, GD, PD
Processor HW and OS should be
able to translate these into actual
physical memory addresses
Changes every time
 Memory Management Requirements
2. 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
 Memory Management Unit

• MMU is the hardware device that maps

logical address to physical address
 Relocation

Limit register
 Registers Used during Execution
◼ Base register: Starting address for the process.

◼ Bounds register: Ending location of the process.

◼ These values are set when the process is loaded or when the
process is swapped in.

◼ The value of the base register is added to a relative address to

produce an absolute address.

◼ The resulting address is compared with the value in the bounds

register.

◼ If the address is not within bounds, an interrupt is generated to the

operating system otherwise instruction gets executed.
 Paging
◼ Fixed & variable size partitions are insufficient as involves internal / external
fragmentation.→ contiguous

◼ What were the two problems with equal sized fixed partitions?
▪ Program too large for a partition
▪ Program too small for a partition
◼ 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

❑ Page number is used as an index to page table.

 Paging
◼ Each process has its own page table.

◼ Each page table entry contains the frame number of the corresponding page
in main memory

◼ A bit is needed to indicate whether the page is in main memory or not.

◼ No external fragmentation

◼ all frames (physical memory) can be used by processes

◼ Possibility of Internal fragmentation

◼ The physical memory used by a process is no longer contiguous

◼ The logical memory of a process is still contiguous

◼ The logical and physical addresses are separated

◼ the process does not see the translation or the difference to having physical
memory
 Advantages of Breaking up a Process

◼ More processes may be maintained in main memory

❑ Only load in some of the pieces of each process

❑ With so many processes in main memory, it is very likely a process will

be in the Ready state at any particular time

◼ A process may be larger than all of main memory

7.22
Processes and Frames

A.0
A.1
A.2
A.3
D.0
B.0
D.1
B.1
D.2
B.2
C.0
C.1
C.2
C.3
D.3
D.4
Assignment of Process Pages to Free Frames
Assignment of Process Pages to Free Frames
Page Tables for Example
 Paging

⚫ The page size is defined by the hardware.

⚫ The page size is typically a power of [Link] size can be 512 bytes to 16
MB.

⚫ The selection of power of 2 as a page size makes translation of logical

address into a page number and page offset easy.

⚫ 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) – combined with base address to define the physical
memory address that is sent to the memory unit.

For given logical address space 2m and page size 2n

 Paging

Assume 16 bit address

 Logical Address vs Relative Address
• What does relative address 1502 mean?

– Start from base relative address of the process

• What logical address would this correspond to?

– Let page size be 1000 bytes

– Logical address = page 1, offset 502

• That is, relative address 1502 corresponds to logical

address (1,502)

• Expressed as 16 bit values, relative address is

0000010111011110 and

logical address is (000001, 0111100110)

• They are different

Vishal Kaushal
⚫In this example, 16-bit addresses are used, and the page size is 1K
=1024 bytes=210
⚫The relative address 1502, in binary form, is 0000010111011110.
⚫From page size, we understand how many bits the offset would need
⚫Remaining bits are then available for page number
⚫Logical address simply corresponds to the two portions of relative
address
⚫With a page size of 1K, an offset field of 10 bits is needed,
leaving 6 bits for the page number.
⚫Can you compute maximum number of pages a program can contain?
- 26 =64 pages of 1K bytes each.
⚫As Figure 7.11b shows, relative address 1502 corresponds to
an offset of 478 (0111011110) on page 1 (000001),
which yields the same 16-bit number, 0000010111011110.
Illustration
 Logical to physical address translation
• Consider a logical address of n+m bits

– First n bits = page number

– Last m bits = offset

• Use the page number as an index into process page table to find
frame number, k

• Starting physical address of that frame then would be k X 2^m

• Desired physical address = this + offset, m

– Again, doesn’t need to be calculated

– Just append offset to the frame number k

 Logical to Physical Address Translation in Paging

The logical address is 0000010111011110, which is page number 1,

offset 478.
Suppose that this page is residing in main memory frame 6 = binary
000110. Then the physical address is frame number 6, offset 478 =
0001100111011110
( 6*2^10=6144+478=6622 (0001100111011110 )
Let us consider an example:
•Physical Address = 12 bits, then Physical Address
Space = 4 K words
•Logical Address = 13 bits, then Logical Address Space
= 8 K words
•Page size = frame size = 1 K words (assumption)
 Segmentation
◼ User program and associated data now divided not into pages, but
segments which could be of unequal size

◼ All segments of all programs do not have to be of the same length, May be
unequal, dynamic size

◼ There is a maximum segment length, Simplifies handling of growing data

structures

◼ Logical Address consist of two parts - a segment number and an offset

◼ Similar to dynamic partitioning

A program however can now occupy more than one partitions
Partitions need not be contiguous
◼ No internal fragmentation?

◼ No external fragmentation?
 Segmentation
• Paging is invisible to the programmer, segmentation is usually visible and is
provided as a convenience for organizing programs and data
– Compiler or programmer assigns programs and data to different
segments
– One program may be further broken down into multiple segments for
purposes of modular programming
• Allows programs to be altered and recompiled independently
• Lends itself well to sharing data among processes
• Lends itself well to protection
• Simplifies handling of growing data structures
• Logical address to physical address translation is now little complicated but
similar
– Segment table
• Length of segment and starting physical address
 Segment Organization

◼ Starting address corresponding segment in main memory

◼ Each entry contains the length of the segment

◼ A bit is needed to determine if segment is already in main memory

◼ Another bit is needed to determine if the segment has been modified

since it was loaded in main memory
 Logical to Physical Address Translation in Segmentation

⚫In this example, 16-bit addresses are

used,
⚫The relative address 1502, in binary
form, is 0000010111011110.
⚫Consider an address of n + m bits,
where the leftmost n bits are the segment
number and the rightmost m bits are the
offset.
⚫In the example on the slide n = 4
And m =12.
 Address translation
• Extract segment number from logical address (left most
n bits)

• Find base address of this segment from segment table

• Compare offset (rightmost m bits) with segment length

• If ok, desired physical address = base address + offset

Logical to Physical Address Translation in Segmentation

The logical address is 0001001011110000, which is segment

number 1, offset 752.
Suppose that this segment is residing in main memory starting at
physical address 0010000000100000.
Then the physical address(base addess+offset):
0010000000100000 +
001011110000 =0010001100010000
 Example
• Consider a logical address space of 64 pages of 1024 words each,
mapped onto a physical memory of 32 frames.

a) How many bits are there in the logical address?

Sol:64 pages=64*1024=2^6*2^10=2^16=16 bits

a) How many bits are there in the physical address?

Sol: 32 frames= 32 *1024=2^5*2^10=2^15=15 bits

 Example
• Consider a logical address space of 32 pages of 1024 words per
page, mapped onto a physical memory of 16 frames.

a) How many bits are there in the logical address?

Sol:32 pages=32*1024=2^5*2^10=2^15=15 bits

b) How many bits are there in the physical address?

Sol:16 pages=16*1024=2^4*2^10=2^14=14 bits

 Example
• Consider a computer system with a 32 bit logical address
and 4KB page size. The system supports up to 512 MB of
physical memory. How many entries are there in a
conventional page table?
 Translation Lookaside Buffer
◼ Each virtual memory reference can cause two physical memory
accesses

❑ One to fetch appropriate page table

❑ One to fetch appropriate data

◼ Effect of doubling the memory access time!

◼ To overcome this problem a high-speed cache is set up for page

table entries

❑ Called a Translation Lookaside Buffer (TLB)

❑ Contains page table entries that have been most recently used
 TLB Operation
◼ Given a virtual address, processor examines the TLB

◼ If page table entry is present (TLB hit), the frame number is retrieved
and the real address is formed

◼ If page table entry is not found in the TLB (TLB miss), the page
number is used to index the process page table

▪ First checks if page is already in main memory

• If yes, go ahead, update TLB to include this new entry

• If no, a page fault is issued to get the page (OS takes

over), page table is updated, instruction is re-executed

◼ It have entries between 64 to 1024

Translation Lookaside Buffer
TLB Operation
Translation Lookaside Buffer
Translation Lookaside Buffer
 Contents

◼ Memory Management requirements

◼ Memory Partitioning: Fixed and Variable Partitioning,

◼ Allocation Strategies (First Fit, Best Fit, and Worst Fit), Fragmentation,
Swapping.

◼ Virtual Memory: Concepts, Segmentation, Paging, Address Translation,

◼ Page Replacement Policies (FIFO, LRU, Optimal, Other Strategies),

◼ Thrashing.

◼ OS Services layer in the Mobile OS: Multimedia and Graphics Services,

Connectivity Services.
 What
happens
when there
is no free
frame?
 What happens if there is no free frame?

◼ Page replacement – find some page in memory, but not really in use,
swap it out
• Different algorithms, different performance
• Want an algorithm which will result in minimum number of page faults
◼ Same page may be brought into memory several times
 Page Replacement
◼ Prevent over-allocation of memory by modifying page-fault service routine to
include page replacement

◼ Use modify (dirty) bit to reduce overhead of page transfers – only modified
pages are written to disk

◼ Page replacement completes separation between logical memory and

physical memory – large virtual memory can be provided on a smaller
physical memory
 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

3) Bring the desired page into the (newly) free frame; update
the page and frame tables

4) Restart the process

Page Replacement
 Page-Replacement Algorithms
• Want lowest page-fault rate.

• Evaluate algorithm by running it on a particular string of memory references

(reference string) and computing the number of page faults on that string.

• In all our examples, the reference string is

ABCABDADBCB
 Basic Replacement Algorithms

◼ First-in, first-out (FIFO)

❑ Treats page frames allocated to a process as a circular buffer

❑ Pages are removed in round-robin style

❑ Simplest replacement policy to implement

❑ Page that has been in memory the longest is replaced

❑ These pages may be needed again very soon

❑ How would you implement FIFO strategy?

• Keep a queue and do round robin
 Example: FIFO
• Suppose we have 3 page frames, 4 virtual pages, and
following reference stream:
– ABCABDADBCB
• Consider FIFO Page replacement:

Ref: A B C A B D A D B C B
Page:
1 A D C
2 B A
3 C B

– FIFO: 7 faults.
– When referencing D, replacing A is bad choice, since
need A again right away
 Basic Replacement Algorithms

◼ Optimal policy

❑ Selects for replacement that page for which the time to the next
reference is the longest

❑ Impossible to have perfect knowledge of future events

 Example: Optimal(MIN)
• Suppose we have the same reference stream:
– ABCABDADBCB
• Consider Optimal Page replacement:

Ref: A B C A B D A D B C B
Page:
1 A C
2 B
3 C D

– MIN: 5 faults
– Where will D be brought in? Look for page not
referenced farthest in future.
 Basic Replacement Algorithms

◼ Least Recently Used (LRU)

❑ Replaces the page that has not been referenced for the longest time

❑ By the principle of locality, this should be the page least likely to be

referenced in the near future

❑ Each page could be tagged with the time of last reference. This would
require a great deal of overhead.
 Example: LRU
• Suppose we have the same reference stream:
– ABCABDADBCB
• Consider LRU Page replacement:

Ref: A B C A B D A D B C B
Page:
1 A C
2 B
3 C D

– LRU: 5 faults
• What will LRU do?
– Same decisions as MIN here, but won’t always be true!
 LRU Algorithm (Cont.)
◼ How would you implement LRU strategy?

◼ Stack implementation – keep a stack of page numbers in a double link form:

❑ Any time Page is referenced move it to the top

❑ Replace page from the bottom of the stack

❑ No search for replacement

 Global vs. Local Allocation
• Global replacement – process selects a replacement frame from the set of
all frames; one process can take a frame from another.

• Local replacement – each process selects from only its own set of allocated
frames.
 Graph of Page Faults Versus The Number of Frames

• One desirable property: When you add memory the miss rate goes
down
– Does this always happen?
– Seems like it should, right?
• No: BeLady’s anomaly
– Certain replacement algorithms (FIFO) don’t have this obvious
property!
 Adding Memory Doesn’t Always Help Fault Rate
• Does adding memory reduce number of page
faults?
– Yes for LRU and MIN
– Not necessarily for FIFO! (Called Belady’s
anomaly)
Ref: A B C D A B E A B C D E
Page:
1 A D E
2 B A C
3 C B D
Ref: A B C D A B E A B C D E
Page:
1 A E D
2 B A E
3 C B
4 D C
 Comparison of Algorithms
FIFO OPT/MIN LRU
Data structure for Queue NA DLL using counter
implementation or stack method
Traversal of Forward Forward Backward
reference string
Implementation Easy to Diff. to impl. Approximation of
understand n OPT ,impl is
imple. possible
Performance Not good Mainly used for Good
comparison study
Time to be Uses the time Uses the time Approximation of
considered when page was when a page is to OPT , Uses the
brought into be used time when a page
memory is used