Paging is a memory management technique of the OS in which the physical memory is divided into the

fixed size pages, and the main memory is divided into fixed size frames. The fixed-size frames are also
known as page frames. The size of each page will be equal to the size of each page frame.

The basic goal of paging is to remove the requirement for memory to be allocated in a contiguous
manner. By using paging, the OS can break programs into small fixed-size pages that are kept in non-
contiguous locations (like a linked list, tree form, etc.) in physical memory, as opposed to allocating
memory in contiguous chunks.

Paging divides the memory into fixed-size blocks known as pages. For easy mapping between pages
and frames, the physical memory is partitioned into frames that are the same size as pages. Because
each page can have its rights, the operating system can manage which memory regions are accessible
to which users. It finds and stops any unauthorised entry. Every process keeps track of the mapping
between its virtual pages and the actual memory frames in a page table. Paging translates the virtual
address into a physical address. When physical memory is full, the system must replace current pages
with new ones. To identify which pages to replace, a variety of algorithms are utilised, including Least
Recently utilised (LRU), First-In-First-Out (FIFO), and Optimal Page Replacement. Demand paging
loads pages into memory only when they are needed, lowering overall memory utilisation and increasing
efficiency.

Advantages of Paging Paging reduces the chances of external fragmentation. Paging allows the
efficient usage of memory in computer systems. Fixed-size blocks called pages are created to reduce
the wastage of memory and allocation of memory in uniform blocks. Paging provides isolation between
processes by ensuring that each process has its page table. Paging ensures security and stability by
preventing one process from accessing another’s memory. Paging allows for demand paging in memory
management. Easy swapping or replacing of processes between pages and frames.
Disadvantages of Paging Paging can issue internal fragmentation as some memory may remain
unused due to fixed-size block allocation. Overhead issues due to the creation of page tables. Paging
requires a large amount of memory consumption and processing power. It may cause page faults when
the required page is not available in the memory.

Segmentation is a non-contiguous memory management technique in OS, in which main memory is

divided into small logical units known as segments and stores data like function, procedure, or any data
structure. In segmentation, the logical units are created in variable size, unlike paging, where fixed-size
blocks are being created. In terms of a compiler, it automatically divides a program into segments
when it is compiled wherein, the different segments may be produced by a compiler for global variables,
heaps, stacks, etc. Although segmentation gives you more control over memory management, segments
of different sizes may cause fragmentation (internal or external) problems.

Features Segments are created in segmentation as individual logical units. Each segment represents a
logical unit, such as a function, array, or data structure, providing a more straightforward mapping to
the programmer’s perspective on memory. A segment table is used by each process containing the base
address and the limit i.e., the size of the segment. Individual segments can contain the program’s code,
data, stack, etc., reflecting their distinct logical uses. Segmentation allows the sharing of resources
among various processes in the memory. Accessing memory outside the defined limits of a segment
results in a segmentation fault, enhancing the protection and stability of the system. Segmentation
reduces the chances of internal fragmentation.
Advantages of Segmentation There is no internal fragmentation in segmentation. A proper
structure of the logical representation of memory is provided in segmentation. Easy for programmers
to understand the memory view. Protection and isolation of different segments can be achieved. Unau-
thorised access can be prevented in segmentation when there is access to segments outside the defined
limit in the segment table. Efficient and less memory usage due to no internal fragmentation and due
to variable size of segments. Easy sharing of segment’s data and code between multiple processes and
therefore multiple processes can access the same region of the memory.
Disadvantages of Segmentation Swapping is not recommended because of the variable size of
segments. External fragmentation can be achieved in segmentation as free memory is divided into small,
non-contiguous blocks, which makes it difficult to allocate large contiguous memory segments. Difficult
memory management as variable size segments are created. The OS has this overhead to keep track of
the size and the location of each segment. There is an overhead of a segment table that increases the
memory consumption and processing power with time.

Page Replacement Problem

Question: Consider the following page reference string:

3, 6, 4, 1, 2, 1, 5, 4, 1, 3, 2, 1, 5
Assume there are 4 frames. How many page faults would occur for the following page replacement
algorithms? Also, find the page fault ratio for each algorithm:

1. FIFO (First-In First-Out)

2. LRU (Least Recently Used)

3. Optimal

(i) FIFO Algorithm

Reference Frame Contents Hit/Fault Evicted

3 3--- Fault –
6 36-- Fault –
4 364- Fault –
1 3641 Fault –
2 2641 Fault 3
1 2641 Hit –
5 2541 Fault 6
4 2541 Hit –
1 2541 Hit –
3 2531 Fault 4
2 2531 Hit –
1 2531 Hit –
5 2531 Hit –

7
Total page faults (FIFO) = 7, Page fault ratio = ≈ 0.538
13
—

(ii) LRU Algorithm

Criteria Paging Segmentation
Allocation type Paging is a type of Segmentation is also a type of
non-contiguous allocation of non-contiguous allocation of
memory. memory.
Memory division In paging, the memory is divided In segmentation, the memory is
into fixed-size pages. divided into variable-size
segments.
Purpose The purpose of paging is to The purpose of segmentation is
manage the physical memory for the logical division of a
efficiently. program.
Done by It is done by the operating It is done by the compiler.
system.
Address For translating the addresses, the For translating the addresses, the
translation page tables are created and used. segment tables are created and
used.
Fragmentation Paging leads to internal Segmentation leads to external
fragmentation within pages. fragmentation between each
segment.
Overhead There is more overhead as a good There is less overhead as a less
amount of memory is used. amount of memory is used by the
segment tables.
Access Speed Due to page faults, the access Due to fewer access faults, the
speed is low. access speed is faster.
Protection The paging isolates processes Segmentation protects the
with the help of individual page processes with the help of
tables. segment limits.
Type of unit A physical unit consisting of A logical unit consisting of
information. information.
Fault handling Page faults can occur on missing Segment faults can occur when
pages. users try to access non-existing or
out-of-bound items.
Tables Page tables are created in Paging. Segment tables are created in
Segmentation.
Logical address Paging has a logical address Segmentation has a logical
consisting of page number and address consisting of segment
page offset. number and segment offset.
Hiding As Paging is done by the OS, it is Segmentation can be seen visibly
completely hidden from the user. by the user.
Sharing of The sharing of resources like The sharing of resources between
resource procedures between different different processes is easier as
processes is difficult as page segments are facilitated to share.
tables are required.
Use case Paging is used in general-purpose Segmentation is used in real-time
operating systems for efficient OS, embedded systems, etc.
memory management.
Examples Paging is being used in Windows Segmentation is used in the early
OS, MacOS, etc. versions of embedded systems,
DOS, etc.

Table 1: Comparison between Paging and Segmentation

Reference Frame Contents Hit/Fault Evicted

 3 3--- Fault –
6 36-- Fault –
4 364- Fault –
1 3641 Fault –
2 2641 Fault 3
1 2641 Hit –
5 2541 Fault 6
4 2541 Hit –
1 2541 Hit –
3 3541 Fault 2
2 3241 Fault 5
1 3241 Hit –
5 3251 Fault 4

9
Total page faults (LRU) = 9, Page fault ratio = ≈ 0.692
13
—

(iii) Optimal Algorithm

Reference Frame Contents Hit/Fault Evicted (Future use)

3 3--- Fault –
6 36-- Fault –
4 364- Fault –
1 3641 Fault –
2 3241 Fault 6 (no future use)
1 3241 Hit –
5 3541 Fault 2 (farthest future use)
4 3541 Hit –
1 3541 Hit –
3 3541 Hit –
2 2541 Fault 3 (farthest)
1 2541 Hit –
5 2541 Hit –

7
Total page faults (Optimal) = 7, Page fault ratio = ≈ 0.538
13
—

Final Summary
Algorithm Page Faults Fault Ratio
F IF O 7 7/13 ≈ 0.538
LRU 9 9/13 ≈ 0.692
Optimal 7 7/13 ≈ 0.538