UNIT 4: Memory Management & Virtual memory

• Memory Management:
– contiguous memory allocation,
– paging,
– segmentation,
– structure of page the table,
– swapping.
• Virtual memory:
– Demand paging,
– Copy-on-Write,
– page-replacement,
– allocation of frames,
– thrashing.
UNIT 4A: Memory Management & Virtual memory

• Memory Management:
– contiguous memory allocation,
– paging,
– segmentation,
– structure of page the table,
– swapping.
1. Memory Management: Background

1.1 Basic Hardware

• Program must be brought (from disk) into memory and placed within
a process for it to be run
• Main memory and registers are only storage, CPU can access directly
• Memory unit only sees a stream of:
• addresses + read requests, or
• address + data and write requests
• Register access is done in one CPU clock (or less)
• Main memory access may take many cycles of the CPU clock, needs
to stall
• For the fast memory between the CPU and main memory, Cache sits
between main memory and CPU registers
• Protection of memory required to ensure correct operation, provided
by the hardware.
 Protection
 multiple processes loaded in memory for concurrent execution.
 Need to censure that a process can access only access those addresses in it
address space.
 provide protection by using a pair(Two) of base and limit registers define
the logical address space of a process

• The base register holds the smallest

legal physical memory address;
• The limit register specifies the size of
the range.
• For example:
• The base register holds 300040
• The limit register is 120900
• Then the program can legally access
all addresses from 300040 through
420939 (inclusive).
 Hardware Address Protection
 CPU must check every memory access generated in user mode to be
sure it is between base and limit for that user

 The base and limit registers can be loaded only by the operating
system, which uses a special privileged instruction.
1.2 Address Binding
• Usually, a program resides on a disk as a binary executable file.
• To run, the program must be brought into memory and placed within
the context of a process, where it becomes eligible for execution on
an available CPU.
• Programs on disk, ready to be brought into memory to execute form
an input queue.
• As the process executes, it accesses instructions and data from
memory.
• Eventually, the process terminates, and its memory is reclaimed for
use by other processes.
• Systems allow a user process to reside in physical memory.
• The address space of the computer may start at 00000, the first
address of the user process need not be 00000.
 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
Need hardware support for address maps (e.g., base and limit
registers)
Multistep Processing of a User Program
 Addresses represented in different ways at different stages of a
program’s life
• Source code addresses usually symbolic
• Compiled code addresses bind to relocatable addresses
• i.e. “14 bytes from beginning of this module”
• Linker or loader will bind relocatable addresses to absolute
addresses
• i.e. 74014
• Each binding maps one address space to another
 1.3 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
 Logical and physical addresses are the same in compile-time and load-time
address-binding schemes; logical (virtual) and physical addresses differ in
execution-time address-binding scheme
 Logical address space is the set of all logical addresses generated by a
program
 Physical address space is the set of all physical addresses generated by a
program
 The run-time mapping from virtual to physical addresses is done by a
hardware device called the memory-management unit (MMU)
 Memory-Management Unit (MMU)
 Hardware device that at run time maps virtual to physical address

 which is a generalization of the base-register scheme.

 The base register now called relocation register
 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
 Execution-time binding occurs when reference is made to location in
memory
 Logical address bound to physical addresses
 Memory-Management Unit (Cont.)
 Consider generalization of the base-register scheme.
 The base register now called relocation register
 The value in the relocation register is added to every address generated by a
user process at the time it is sent to memory
 two different types of addresses:
• logical addresses (in the range 0 to max) and
• physical addresses (in the range R + 0 to R + max for a base value R).
 1.4 Dynamic Loading

 The entire program does need to be in memory to excute

 Routine is not loaded until it is called
 Better memory-space utilization; unused routine is never loaded
 All routines kept on disk in relocatable load format
 Useful when large amounts of code are needed to handle
infrequently occurring cases
 No special support from the operating system is required
 Implemented through program design
 OS can help by providing libraries to implement dynamic
loading
 1.5 Dynamic Linking
 Dynamically linked libraries (DLLs) are system libraries that are linked to
user programs when the programs are run
 Static linking – system libraries and program code combined by the loader
into the binary program image
 Dynamic linking –linking postponed until execution time
 Small piece of code, stub, used to locate the appropriate memory-resident
library routine
 Stub replaces itself with the address of the routine, and executes the
routine
 Operating system checks if routine is in processes’ memory address
 If not in address space, add to address space
 Dynamic linking is particularly useful for libraries
 System also known as shared libraries
 Consider applicability to patching system libraries
 Versioning may be needed
 UNIT 4A:
Memory Management & Virtual memory

 Memory Management:

 contiguous memory allocation,

 paging,
 segmentation,
 structure of page the table,
 swapping.
 2. Contiguous Allocation
 The memory is usually divided into two partitions:
 one for the operating system and
 one for the user processes.
 place the operating system in either low memory addresses or high memory
addresses.
 User processes then held in high memory
 This depends on many factors, such as the location of the interrupt vector.
 Limited resource, must allocate efficiently
 Contiguous allocation is one early method
 Main memory usually into two partitions:
 Resident operating system, usually held in low memory with interrupt
vector
 User processes then held in high memory
 Each process contained in single contiguous section of memory
 1. Memory Protection
 Relocation registers used to protect user processes from each other, and
from changing operating-system code and data
 Base register contains value of smallest physical address
 Limit register contains range of logical addresses – each logical address
must be less than the limit register
 MMU maps logical address dynamically
 Can then allow actions such as kernel code being transient and kernel
changing size
Hardware Support for Relocation and Limit Registers
 2. Memory Allocation/ Variable Partition

 Multiple-partition allocation
 Degree of multiprogramming limited by number of partitions

 For example, a 500Mb memory may be (equally or unequally)

divided to blocks 5 blocks of 100Mb each.

 Variable-partition sizes for efficiency (sized to a given process’

needs)

 Or unequally as in 5 blocks of 125mb, 75mb, 125mb, 75mb,

125mb respectively.
 2. Memory Allocation/ Variable Partition
 Hole – block of available memory; holes of various size are scattered
throughout memory
 When a process arrives, it is allocated memory from a hole large
enough to accommodate it
 Process exiting frees its partition, adjacent free partitions combined
 Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
 Dynamic Storage-Allocation Problem
How to satisfy a request of size n from a list of free holes?

 First fit. Allocate the first hole that is big enough. Searching can start
either at the beginning of the set of holes or at the location where the
previous first-fit search ended. We can stop searching as soon as we find a
free hole that is large enough.
 Best fit . Allocate the smallest hole that is big enough. We must search the
entire list, unless the list is ordered by size. This strategy produces the
smallest leftover hole.
 Worst fit. Allocate the largest hole. Again, we must search the entire list,
unless it is sorted by size. This strategy produces the largest leftover hole,
which may be more useful than the smaller leftover hole from a best-fit
approach.

First-fit and best-fit better than worst-fit in terms of speed and storage
utilization
 Example of Memory Partitioning
The main memory must accommodate – Memory Partitioning Algorithms
1. Operating system 1. First Fit
2. User processes 2. Best Fit
3. Operating System Processes 3. Worst Fit
4. Next Fit
• There are two major divisions one for operating system residing and other for
allocating processes.
• OS memory can’t be altered in a direct by way by user.
• Process memory is managed by OS to perform processes.

One of the simplest methods for memory allocation

1.Divide memory into several fixed-sized partitions.
2.Each partition may contain exactly one process.
3.When a partition is free, a process is selected from the input queue and is loaded into
the free partition.
4.When the process terminates, the partition becomes available for another process.
5.The operating system keeps a table indicating which parts of memory are available
and which are occupied using a table.
6.Finally, when a process arrives and needs memory, a memory section large enough
for this process is provided.
use the following memory block to demonstrate each process –

Memory Block Size

Block 1 50k
Block 2 200k
First Fit: Block 3 70k
• For a process P1, Block 4 115k
• whichever first partition (starting from
Block 5 15k
the top) is large enough to fit the current
process, Jobs –
• gets the process allocated to itself.
Job Number Size
Job 1 100k
Job 2 10k
Job 3 35k
Job 4 15k
Job 5 23k
• Job 1 (size – 100k)
1.Can’t fit in block 1 as 50k(block size) <100k (job size)
2.Goes to block 2 as can fit in block 2 as 200K > 100K Memory Block Size
(Size of block more than size of process)
Block 1 50k
1.100K remains empty in this block now.
Block 2 200k
• Job 2 (size 10K)
Block 3 70k
1.Goes to block 1 as 10K < 50k
•Job 3 (size 35 K) Block 4 115k
1.Can fit Block 1 but block 1 is not empty(used by job2) Block 5 15k
2.Can’t fit and also Block 2 not empty
3.Can fit in block 3 Goes to block 3
•Job 4 3 (size 15 K)
Job Number Size
1.Goes to block 4
•Job 5 3 (size 23 K) Job 1 100k
1.All blocks 1 to 4 are occupied Job 2 10k
2.Can’t fit in block 5 as size is more than block Job 3 35k
• So block 5 remains unused. and Job 4 15k
• Job5 has to wait until other processes finish. Job 5 23k
 Job Number Size
Memory Block Size
Job 1 100k
Block 1 50k
Job 2 10k
Block 2 200k
Job 3 35k
Block 3 70k
Job 4 15k
Block 4 115k
Job 5 23k
Block 5 15k
Size of Memory Size Occupant
Memory Block Occupied by Wasted Space
Block Job
Block 1 Job 2 50k 10k 40k
Block 2 Job 1 200k 100k 100k
Block 3 Job 3 70k 35k 35k
Block 4 Job 4 115k 15k 100k
Block 5 Free 15k not valid 15k

• First-fit memory allocation is faster in making allocation but leads to memory

waste.
• If the chosen block is significantly larger than that requested, then it is usually
split, and the remainder added to the list as another free block.
• The first fit algorithm performs reasonably well, as it ensures that allocations are
quick. When recycling free blocks, there is a choice as to where to add the blocks
to the free list—effectively in what order the free list is kept
Best Fit
• Best-fit memory allocation makes the best use of memory space
• but slower in making the allocation.
Job Number Size
Memory Block Size
Job 1 100k
Block 1 50k
Job 2 10k
Block 2 200k
Job 3 35k
Block 3 70k
Job 4 15k
Block 4 115k
Job 5 23k
Block 5 15k

• Allocate the process to the partition which is first smallest

sufficient partition among the free available partition.
• Job 1 (size – 100k)
1.Block 1 size(50k) – 100k = Negative value
2.Block 2 size(200k) – 100k = 100k
3.Block 3 size(70k) – 100k = Negative value
4.Block 4 size(115k) – 100k = 15k
5.Block 5 size(15k) – 100k = Negative value
6.Goes to block 4 as 15K is best case
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

• Job 2 (size – 10k)

1.Block 1 size(50k) – 10k = 40k
2.Block 2 size(200k) – 10k = 190k
3.Block 3 size(70k) – 10k = 60k
4.Block 4 occupied by job 1
5.Block 5 size(15k) – 10k = 5K
6.Goes to block 5 as 5K is best case
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

• Job 3 (size – 35k)

1.Block 1 size(50k) – 35k = 15k
2.Block 2 size(200k) – 35k = 165k
3.Block 3 size(70k) – 35k = 35k
4.Block 4 occupied by job 1
5.Block 5 occupied by job 2
6.Goes to block 1 as 15K is best case
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

• Job 3 (size – 35k)

1.Block 1 size(50k) – 35k = 15k
2.Block 2 size(200k) – 35k = 165k
3.Block 3 size(70k) – 35k = 35k
4.Block 4 occupied by job 1
5.Block 5 occupied by job 2
6.Goes to block 1 as 15K is best case
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

• Job 4 (size – 15k)

• Block 1 occupied by job 3
• Block 2 size(200k) – 15k = 185k
• Block 3 size(70k) – 15k = 55k
• Block 4 occupied by job 1
• Block 5 occupied by job 2
• Goes to block 3 as 55k is best case
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

• Job 4 (size – 15k)

• Block 1 occupied by job 3
• Block 2 size(200k) – 15k = 185k
• Block 3 size(70k) – 15k = 55k
• Block 4 occupied by job 1
• Block 5 occupied by job 2
• Goes to block 3 as 55k is best case
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

• Job 5 (size – 23k)

• Block 1 occupied by job 3

• Only option. size of block (200k) > size of job(23k)
• Block 3 occupied by job 4
• Block 4 occupied by job 1
• Block 5 occupied by job 2
• Goes to block 2 as 100K is worst case
Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

Size of Memory Size Occupant

Memory Block Occupied by Wasted Space
Block Job

Block 1 Job 3 50k 35k 15k

Block 2 Job 5 200k 23k 177k
Block 3 Job 4 70k 15k 55k
Block 4 Job 1 115k 100k 15k
Block 5 Job 2 15k 10k 5k
Worst Fit
• Worst-fit memory allocation is opposite to best-fit.
• It allocates free available block to the new job and it is not the best choice
for an actual system It selects the largest available hole in memory that can
fit a needed segment,
• so as to leave a large hole for other segments

Memory Block Size Job Number Size

Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k
Worst Fit
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Worst Fit Job 5 23k
Block 5 15k

• Job 1 (size – 100k)

• Block 1 size(50k) – 100k = negative value => Can’t fit
• Block 2 size(200k) – 100k = 100k
• Block 3 size(70k) – 100k =negative value => Can’t fit
• Block 4 size(115k) – 100k = 15k
• Block 5 size(15k) – 100k = negative value => Can’t fit
• Goes to block 2 as 100K is worst case
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Worst Fit Job 5 23k
Block 5 15k

• Job 2 (size – 10k)

• Block 1 size(50k) – 10k = 40k
• Block 2 already used by job 1. So not possible
• Block 3 size(70k) – 10k = 60k
• Block 4 size(115k) – 10k = 105k
• Block 5 size(15k) – 10k = 5k
• goes to block 4 as 105k is worst case.
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Worst Fit Job 5 23k
Block 5 15k

• Job 3(size – 35k) Block 1 size(50k) – 35k = 15k

• Block 2 already used by job 1. So not possible
• Block 3 size(70k) – 35k = 35k
• Block 4 already used by job 2. So not possible
• Block 5 size(15k) – 35k = negative value => Can’t fit
• goes to block 3 as 35k is worst case.
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Worst Fit Job 5 23k
Block 5 15k

• Job 3(size – 35k) Block 1 size(50k) – 35k = 15k

• Block 2 already used by job 1. So not possible
• Block 3 size(70k) – 35k = 35k
• Block 4 already used by job 2. So not possible
• Block 5 size(15k) – 35k = negative value => Can’t fit
• goes to block 3 as 35k is worst case.
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Worst Fit Job 5 23k
Block 5 15k

• Job 4(size -15k)

• Block 1 size(50k) – 15k = 35k
• Block 2 already used by job 1. So not possible
• Block 3 already used by job 3. So not possible
• Block 4 already used by job 2. So not possible
• Block 5 size(15k) – 15k = 0
• Goes to block 1 as 35k is the worst
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Worst Fit Job 5 23k
Block 5 15k

• Job 5(size – 23k)

• Block 1 already used by job 4. So not possible
• Block 2 already used by job 1. So not possible
• Block 3 already used by job 3. So not possible
• Block 4 already used by job 2. So not possible
• Block 5 size(15k) – 23k = negative value
• Goes no where has to wait indefinitely for other blocks
free up.
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Worst Fit Job 5 23k
Block 5 15k

Memory
Occupied by Size of Memory Block Size Occupant Job Wasted Space
Block

Block 1 Job 4 50k 15k 35k

Block 2 Job 1 200k 100k 100k
Block 3 Job 3 70k 35k 35k
Block 4 Job 2 115k 10k 105k
Block 5 none 15k not valid 15k
Next Fit
• Next fit is a modified version of ‘first fit’.
• It begins as first fit to find a free partition but when called next time it
starts searching from where it left off, not from the beginning next fit
is a very fast searching algorithm and
• is also comparatively faster than First Fit and Best Fit Memory
Management Algorithms

Memory Block Size Job Number Size

Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

• Job 1 (size – 100k)

1. Can’t fit in block 1 as 50k(block size) <100k(job size)
2. Can fit in block 2 as 200K > 100K (Size of block more than size of
process)
3. 100K remains empty in this block now.

•Job 2 (size 10k)

1.Last job entered in block 2 so will start from block 3 now
2.Goes to block 3 as block size(70k) > job size(10k)
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

• Job 3(size 35K)

• Last job entered in block 3 so will start from block 4 now
• Goes to block 4 as block size(115k) > job size(10k)

•Job 4(size 15k)

1.Last job entered in block 4 so will start from block 5 now
2.Goes to block 5 as block size(15k) = job size(15k)
 Memory Block Size Job Number Size
Block 1 50k Job 1 100k
Block 2 200k Job 2 10k
Block 3 70k Job 3 35k
Block 4 115k Job 4 15k
Block 5 15k Job 5 23k

1. Job 5 (23k)
1.Last job entered in block 5 and there no further blocks, so goes back
to block 1
2.Goes to block 1 as block size(50k) > job size(23k)
Memory Block Occupied by Size of Memory Block Size Occupant Job Wasted Space

Block 1 Job 5 50k 23k 27k

Block 2 Job 1 200k 100k 100k
Block 3 Job 2 70k 10k 60k
Block 4 Job 3 115k 35k 80k
Block 5 Job 4 15k 15k 0
 3. Fragmentation
• Memory space in the system constantly goes through loading and releasing
processes and their resources because of which the total memory spaces
gets broken into a lot of small pieces,
• this causes creation small non utilised fragmented memory spaces, which
are so small that normal processes can not fit into those small fragments,
• causing those memory spaces not getting utilised at all, this is called
memory Fragmentation in operating system.
• Fragmentation is of the following two types –
• Internal Fragmentation
• External Fragmentation
External Fragmentation
• External Fragmentation – total memory space exists to satisfy a request,
but it is not contiguous
• Both the first-fit and best-fit strategies for memory allocation suffer from
external fragmentation.
• storage is fragmented into a large number of small holes. This
fragmentation problem can be severe.
• In worst case, have a block of free (or wasted) memory between every two
processes.
• If all these small pieces of memory were in one big free block instead, we
might be able to run several more processes.
• One solution to the problem of external fragmentation is compaction.
• The goal is to shuffle the memory contents so as to place all free memory
together in one large block.
• Compaction is not always possible.
• If relocation is static and is done at assembly or load time, compaction
cannot be done.
• It is possible only if relocation is dynamic and is done at execution
time.
• If addresses are relocated dynamically, relocation requires only moving
the program and data and then changing the base register to reflect the
new base address. When compaction is possible, we must determine its
cost.
• The simplest compaction algorithm is to move all processes toward one
end of memory;
• all holes move in the other direction,
• producing one large hole of available memory.
• This scheme can be expensive.
• Another possible solution to the external-fragmentation problem is paging
Internal Fragmentation
• Internal Fragmentation – allocated memory may be slightly larger than
requested memory; this size difference is memory internal to a partition, but
not being used
• Consider multiple-partition allocation scheme with a hole of 18,464 bytes.
• Suppose that the next process requests 18,462 bytes.
• left with a hole of 2 bytes.

• The general approach to avoiding this problem is to break the physical

memory into fixed-sized blocks and allocate memory in units based on
block size.
• Depending on the total amount of memory storage and the average
process size, external fragmentation may be a minor or a major problem.
• Statistical analysis of first fit, for instance, reveals that, even with some
optimization, given N allocated blocks, another 0.5 N blocks will be lost
to fragmentation.
• That is, one-third of memory may be unusable! This property is known as
the 50-percent rule.
 UNIT 4A:
Memory Management & Virtual memory

• Memory Management:
– contiguous memory allocation,
– paging,
– segmentation,
– structure of page the table,
– swapping.
 Paging
 Physical address space of a process can be noncontiguous; process is
allocated physical memory whenever the latter is available
 Avoids external fragmentation
 Avoids problem of varying sized memory chunks
 Divide physical memory into fixed-sized blocks called frames
 Size is power of 2, between 512 bytes and 16 Mbytes
 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 to physical addresses
 Backing store likewise split into pages
 Still have Internal fragmentation
 Address Translation Scheme
 breaking physical memory into fixed-sized blocks called frames and
 breaking logical memory into blocks of the same size called pages.
 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
Paging Hardware
• The page number is used as an index into a per-process page table.
• The page table contains the base address of each frame in physical
memory, and the offset is the location in the frame being referenced.
• The base address of the frame is combined with the page offset to
define the physical memory address.
• offset d does not change,
• it is not replaced, and
• the frame number and offset now comprise the physical address.

• The steps taken by the MMU to translate a logical address generated

by the CPU to a physical address:
1. Extract page number p and use it as an index into the page table.
2. Extract the corresponding frame number f from the page table.
3. Replace the page number p in the logical address with the
frame number f.
Paging Model of Logical and Physical Memory
• The page size (like the frame size) is defined by the hardware.
• The size of a page is a power of 2,
• typically varying between 4 KB and 1 GB per page, depending
on the computer architecture.
• The selection of a power of 2 as a page size makes the translation of
a logical address into a page number and page offset particularly
easy.
• If the size of the logical address space is 2m, and a page size is 2n
bytes, then the high-order m−n bits of a logical address designate the
page number, and
• the n low-order bits designate the page offset.
• Thus, the logical address is as follows:

• where page number page offset

• p is an index into the page
table and p d
• d is the displacement within
the page. m -n n
 Paging Example
• Logical address: n = 2 and m = 4.
• Using a page size of 4 bytes and a physical memory of 32 bytes (8 pages)
• How the memory can be mapped into physical memory.
• Logical address 0 is page 0, offset 0.
• Indexing into the page table,
• find that page 0 is in frame 5.
• logical address 0 maps to physical address 20 [= (5 × 4) + 0].
• Logical address 3 (page 0, offset 3) maps to physical address 23
[= (5 × 4) + 3].
• Logical address 4 is page 1, offset 0;
• according to the page table, page 1 is mapped to frame 6.
• Thus, logical address 4 maps to physical address 24 [= (6 × 4) + 0].
• Logical address 13 maps to physical address 9.

• Paging itself is a form of dynamic relocation.

• Every logical address is bound by the paging hardware to some
physical address
• Paging scheme:
• no external fragmentation:
 Paging -- Calculating internal fragmentation
 Page size = 2,048 bytes
 Process size = 72,766 bytes
 35 pages + 1,086 bytes
 Internal fragmentation of 2,048 - 1,086 = 962 bytes
 Worst case fragmentation = 1 frame – 1 byte
 On average fragmentation = 1 / 2 frame size
 So small frame sizes desirable?
 But each page table entry takes memory to track
 Page sizes growing over time
 Solaris supports two page sizes – 8 KB and 4 MB
 Linux also supports two page sizes: a default page size (typically 4
KB) and an architecture dependent larger page size called huge
pages.
 Free Frames
• the operating system is managing physical memory,
• it must be aware of the allocation details of physical memory—
• which frames are allocated, which frames are available,
• how many total frames there are, and so on.
• This information is generally kept in a single, system-wide data
structure called a frame table.

• The frame table has one entry for each physical page frame,
indicating whether the latter is free or allocated and,
• if it is allocated, to which page of which process (or processes).
 Free Frames

Before allocation After allocation

2. Hardware Support- Implementation of Page Table
• The page table is implemented as a set of dedicated high-speed
hardware registers, which makes the page-address translation very
efficient.
• This approach increases context-switch time, as each one of these
registers must be exchanged during a context switch.

 Page table is kept in main memory

 Page-table base register (PTBR) points to the page table
 Page-table length register (PTLR) 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 translation look-aside buffers
(TLBs) (also called associative memory).
 Translation Look-Aside Buffer
 Some TLBs store address-space identifiers (ASIDs) in each TLB
entry – uniquely identifies each process to provide address-space
protection for that process
 Otherwise need to flush at every context switch
 TLBs typically small (64 to 1,024 entries)
 On a TLB miss, value is loaded into the TLB for faster access next
time
 Replacement policies must be considered
 Some entries can be wired down for permanent fast access
 Hardware

 Associative memory – parallel search

P a ge # F ra m e #

 Address translation (p, d)

 If p is in associative register, get frame # out
 Otherwise get frame # from page table in memory
Paging Hardware With TLB
 Hardware

 Associative memory – parallel search

P a ge # F ra m e #

 Address translation (p, d)

 If p is in associative register, get frame # out
 Otherwise get frame # from page table in
memory
Paging Hardware With TLB
 Effective Access Time
 Hit ratio – percentage of times that a page number is found in the
TLB
 An 80% hit ratio means that we find the desired page number in the
TLB 80% of the time.
 Suppose that 10 nanoseconds to access memory.
 If we find the desired page in TLB then a mapped-memory access
take 10 ns
 Otherwise we need two memory access so it is 20 ns
 Effective Access Time (EAT)
EAT = 0.80 x 10 + 0.20 x 20 = 12 nanoseconds
implying 20% slowdown in access time
 Consider amore realistic hit ratio of 99%,
EAT = 0.99 x 10 + 0.01 x 20 = 10.1ns
implying only 1% slowdown in access time.
• CPUs may provide multiple levels of TLBs.

• the Intel Core i7 CPU has a 128-entry L1 instruction TLB and a 64-
entry L1 data TLB.

• In the case of a miss at L1,

• it takes the CPU six cycles to check for the entry in the L2 512-
entry TLB.
• A miss in L2 means that the CPU must either walk through the page-
table entries in memory to find the associated frame address, which
can take hundreds of cycles, or interrupt to the operating system to
have it do the work.
 Memory Protection

 Memory protection implemented by associating protection bit with

each frame to indicate if read-only or read-write access is allowed
 Can also add more bits to indicate page execute-only, and so on
 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
 Or use page-table length register (PTLR)
 Any violations result in a trap to the kernel
Valid (v) or Invalid (i) Bit In A Page Table
 Shared Pages
 Shared code
 One copy of read-only (reentrant) code shared among processes
(i.e., text editors, compilers, window systems)
 Similar to multiple threads sharing the same process space
 Also useful for inter-process communication if sharing of read-
write pages is allowed
 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
Shared Pages Example
 UNIT 4A:
Memory Management & Virtual memory

 Memory Management:

 contiguous memory allocation,

 paging,

 segmentation,

 structure of page the table,

 swapping.
 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
common block
stack
symbol table
arrays
User’s View of a Program
Logical View of Segmentation

4
1

3 2
4

user space physical memory space

 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
 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
 A segmentation example is shown in the following diagram
Segmentation Hardware
 UNIT 4A:
Memory Management & Virtual memory

 Memory Management:

 contiguous memory allocation,

 paging,

 segmentation,

 structure of page the table,

 swapping.
 Structure of the Page Table
 Memory structures for paging can get huge using straight-forward
methods
 Consider a 32-bit logical address space as on modern computers
 Page size of 4 KB (212)
 Page table would have 1 million entries (220 = 232 / 212)
 If each entry is 4 bytes  each process 4 MB of physical address
space for the page table alone
Don’t want to allocate that contiguously in main memory
 One simple solution is to divide the page table into smaller units
Hierarchical Paging
Hashed Page Tables
Inverted Page Tables
 Hierarchical Page Tables
 Break up the logical address space into multiple page tables
 A simple technique is a two-level page table
 We then page the page table
 Two-Level Paging Example
 A logical address (on 32-bit machine with 1K page size) is divided into:
 a page number consisting of 22 bits
 a page offset consisting of 10 bits

 Since the page table is paged, the page number is further divided into :
 a 10-bit page number
 a 12-bit page offset

 Thus, a logical address is as follows:

 where p is an index into the outer page table, and p is the

1 2
displacement within the page of the inner page table
 Known as forward-mapped page table
Address-Translation Scheme
 64-bit Logical Address Space
 Even two-level paging scheme not sufficient
 If page size is 4 KB (212)
 Then page table has 252 entries
 If two level scheme, inner page tables could be 2 10 4-byte entries
 Address would look like

 Outer page table has 242 entries or 244 bytes

 One solution is to add a 2nd outer page table
 But in the following example the 2 nd outer page table is still 2 34 bytes in
size
 And possibly 4 memory access to get to one physical memory location
Three-level Paging Scheme
 Hashed Page Tables
 Common in address spaces > 32 bits
 The virtual page number is hashed into a page table
 This page table contains a chain of elements hashing to the same
location
 Each element contains (1) the virtual page number (2) the value of the
mapped page frame (3) a pointer to the next element
 Virtual page numbers are compared in this chain searching for a match
 If a match is found, the corresponding physical frame is extracted
 Variation for 64-bit addresses is clustered page tables
 Similar to hashed but each entry refers to several pages (such as 16)
rather than 1
 Especially useful for sparse address spaces (where memory
references are non-contiguous and scattered)
Hashed Page Table
 Inverted Page Table
 Rather than each process having a page table and keeping track of all
possible logical pages, track all physical pages
 One entry for each real page of memory
 Entry consists of the virtual address of the page stored in that real
memory location, with information about the process that owns that
page
 Decreases memory needed to store each page table, but increases time
needed to search the table when a page reference occurs
 Use hash table to limit the search to one — or at most a few — page-
table entries
 TLB can accelerate access
 But how to implement shared memory?
 One mapping of a virtual address to the shared physical address
Inverted Page Table Architecture
 Oracle SPARC Solaris
 Consider modern, 64-bit operating system example with tightly integrated
HW
 Goals are efficiency, low overhead
 Based on hashing, but more complex
 Two hash tables
 One kernel and one for all user processes
 Each maps memory addresses from virtual to physical memory
 Each entry represents a contiguous area of mapped virtual memory,
 More efficient than having a separate hash-table entry for each
page
 Each entry has base address and span (indicating the number of
pages the entry represents)
 Oracle SPARC Solaris (Cont.)
 TLB holds translation table entries (TTEs) for fast hardware lookups
 A cache of TTEs reside in a translation storage buffer (TSB)
 Includes an entry per recently accessed page
 Virtual address reference causes TLB search
 If miss, hardware walks the in-memory TSB looking for the TTE
corresponding to the address
 If match found, the CPU copies the TSB entry into the TLB and
translation completes
 If no match found, kernel interrupted to search the hash table
– The kernel then creates a TTE from the appropriate hash table
and stores it in the TSB, Interrupt handler returns control to the
MMU, which completes the address translation.
UNIT 4A: Memory Management & Virtual memory

 Memory Management:

 contiguous memory allocation,

 paging,

 segmentation,

 structure of page the table,

 swapping.
 Swapping
 A process can be swapped temporarily out of memory to a backing
store, and then brought back into memory for continued execution
 Total physical memory space of processes can exceed physical
memory
 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
 System maintains a ready queue of ready-to-run processes which
have memory images on disk
Schematic View of Swapping
 Swapping
 Does the swapped out process need to swap back in to same physical
addresses?
 Depends on address binding method
 Plus consider pending I/O to / from process memory space
 Modified versions of swapping are found on many systems (i.e.,
UNIX, Linux, and Windows)
 Swapping normally disabled
 Started if more than threshold amount of memory allocated
 Disabled again once memory demand reduced below threshold

• generally no longer used in contemporary operating systems, because

the amount of time required to move entire processes between
memory and the backing store is prohibitive.
• (An exception to this is Solaris, which still uses standard swapping,
however only under dire circumstances when available memory is
 Swapping with Paging
 Most systems, including Linux and Windows, now use a variation of
swapping in which pages of a process—rather than an entire process
—can be swapped.
 This strategy still allows only a small number of pages will be
involved in swapping.
 the term swapping now generally refers to standard swapping, and
 paging refers to swapping with paging.
 A page out operation moves a page from memory to the backing
store;
 the reverse process is known as a page in.
 Swapping with Paging
• A subset of pages for processes A and B are being paged-out and
paged-in respectively.
• swapping with paging works well in conjunction with virtual
memory.
 Context Switch Time including Swapping
 If next processes to be put on CPU is not in memory, need to swap out a process
and swap in target process
 Context switch time can then be very high
 100MB process swapping to hard disk with transfer rate of 50MB/sec
 Swap out time of 2000 ms
 Plus swap in of same sized process
 Total context switch swapping component time of 4000ms (4 seconds)
 Can reduce if reduce size of memory swapped – by knowing how much memory
really being used
 System calls to inform OS of memory use via request_memory() and
release_memory()
• Other constraints as well on swapping
• Pending I/O – can’t swap out as I/O would occur to wrong
process
• Or always transfer I/O to kernel space, then to I/O device
Known as double buffering, adds overhead
• Standard swapping not used in modern operating systems
• But modified version common
• Swap only when free memory extremely low
 Swapping on Mobile Systems
 Not typically supported
 Flash memory based
Small amount of space
Limited number of write cycles
Poor throughput between flash memory and CPU on mobile
platform
 Instead use other methods to free memory if low
 iOS asks apps to voluntarily relinquish allocated memory
Read-only data thrown out and reloaded from flash if needed
Failure to free can result in termination
 Android terminates apps if low free memory, but first writes
application state to flash for fast restart
 Both OSes support paging as discussed below