PAGING

SHILPI MISHRA
 Memory-management technique that permits the
physical address space of a process to be non-
contiguous

Physical memory is divided into fixed size-

blocks called FRAMES
Logical memory is divided into blocks of the
same size called PAGES
A frame
has the same size as a page
is a place where a (logical) page can be
(physically) placed
Address Mapping
Every address generated by the CPU is divided
into two parts: Page number (p) and Page
offset (d)
 Paging Hardware
The page number is used as an index into a
Page Table
The page size is defined by the hardware
The size of a page is typically a power of 2,
varying between 512 bytes and 16MB per
page
Reason: If the size of logical address is 2 ^m
and page size is 2^n, then the high-order
m - n bits of a logical address designate the
page number
Paging Hardware
 Paging Example
When we use a paging scheme, we have no
external fragmentation: ANY free frame can be
allocated to a process that needs it.
However, we may have internal fragmentation

If the process requires n pages, at least n

frames are required
The first page of the process is loaded into the
first frame listed on free-frame list, and the
frame number is put into page table
Paging Example
Paging Example
To implement paging, the simplest method
is to implement the page table as a set of
registers
However, the size of register is limited and
the size of page table is usually large
Therefore, the page table is kept in main
memory
MMU Address Transaction
If we want to access any location, we
must first index into the page table
This requires atleast one memory access
The standard solution is to use a special,
small, fast cache, called Translation
look-aside buffer (TLB) or associative
memory
TLB-Assisted Transaction
If the page number is not in the TLB (TLB
miss) a memory reference to the page
table must be made.
In addition, we add the page number and
frame number into TLB
If the TLB already full, the OS have to
must select one for replacement
Some TLBs allow entries to be wire down,
meaning that they cannot be removed
from the TLB, for example kernel codes
The percentage of times that a particular
page number is found in the TLN is
called hit ratio
If it takes 20 nanosecond to search the
TLB and 100 nanosecond to access
memory
 ADVANTAGES
No external Fragmentation
Simple memory management algorithm
Swapping is easy (Equal sized Pages and Page
Frames)
Share common code especially in a time-sharing
environment
DISADVANTAGES
Internal fragmentation
Page tables may consume more memory.
Multi level paging leads to memory
reference overhead.
There is another way in which addressable memory
can be subdivided, known as
segmentation
An important part of the memory management is
that become unavoidable with paging is the
separation of the user’s view of the memory and
the actual physical memory
The users view is mapped to the physical memory
Thus the differentiation comes between the logical
and physical memory.
Do users view memory as
linear array of bytes some
containing instruction and
other containing data???

No…Rather they would see it

as collection of
segments…….
User View of logical memory

◦ Linear array of bytes

Reflected by the ‘Paging’ memory
scheme

◦ A collection of variable-sized
entities
User thinks in terms of “subroutines”,
“stack”, “symbol table”, “main program”
which are somehow located somewhere
in memory.]

Segmentation supports this user

view. The logical address space
is a collection of segments.
Although the user can refer to objects in the
program by a two-dimensional address, the actual
physical address is still a one-dimensional
sequence

Thus, we need to map the segment number

This mapping is effected by a segment table

In order to protect the memory space, each entry in

segment table has a segment base and a segment
limit
 Segment number
Logical Address space
Offset

The mapping of the logical address to the physical address is done

with the help of the segment table.
the length of the
segment SEGMENT TABLE

Segment Limit Segment Base Other bits

starting address of the

corresponding segment A bit is needed to determine if the segment
in main memory is already in main memory (P)
Another bit is needed to determine if the
segment has been modified since it was
loaded in main memory (M)
Segments are variable-sized
◦ Dynamic memory allocation required (first fit, best fit, worst fit).
External fragmentation
◦ In the worst case the largest hole may not be large enough to fit
in a new segment. Note that paging has no external fragmentation
problem.
Each process has its own segment table
◦ like with paging where each process has its own page table. The
size of the segment table is determined by the number of
segments, whereas the size of the page table depends on the total
amount of memory occupied.
Segment table located in main memory
◦ as is the page table with paging
Segment table base register (STBR)
◦ points to current segment table in memory
Segment table length register (STLR)
◦ indicates number of segments
Segmentation lends itself to the
implementation of protection and sharing
policies

Each entry has a base address and length so

inadvertent memory access can be controlled

Sharing can be achieved by segments

referencing multiple processes

Two processes that need to share access to a

single segment would have the same segment
name and address in their segment tables.
No internal fragmentation
Segment tables consume less memory than
page tables ( only one entry per actual segment
as opposed to one entry per page in Paging
method)
Because of the small segment table, memory
reference is easy
Lends itself to sharing data among processes.
Lends itself to protection.
As the individual lines of a page do not form
one logical unit, it is not possible to set a
particular access right to a page.
Note that each segment could be set up an
access right
External fragmentation.
Costly memory management algorithm
Unequal size of segments is not good in the
case of swapping.
With paging physical memory is divided into f ixed-
size frames. When memory space is needed, as many
free frames are occupied as necessary. These frames
can be located anywhere in memory, the user process
always sees a logical contiguous address space

With segmentation the memory is not systematically

divided. When a program needs k segments (usually
these have different sizes), the OS tries to place these
segments in the available memory holes. The
segments can be scattered around memory. The user
process does not see a contiguous address space, but
sees a collection of segments (of course each
individual segment is contiguous as is each page or
frame).
Paging Segmentation

Each process is assigned Each process is assigned

its page table. a segment table
Page table size Segment table size
proportional to allocated proportional to number
memory of segments
Often large page tables Usually small segment
and/or multi-level tables
paging External fragmentation.
Internal fragmentation Lengthy search times
Free memory is quickly when allocating memory
allocated to a process to a process.
Thank You