Paging and Segmentation in Operating System
Paging and Segmentation are important memory management techniques used by an operating system to organize, allocate, protect, and access memory. Both techniques divide a process into smaller logical or physical units, but the way those units are created and managed is different.
Paging divides memory into fixed-size blocks, while segmentation divides a program according to its logical structure into variable-size segments. Understanding both techniques is important for learning Operating System Memory Management, virtual memory, address translation, fragmentation, and memory protection.
Learning Objectives
After studying this chapter, you should be able to:
- Explain the basic concept of paging.
- Differentiate between pages and frames.
- Understand the role of a page table.
- Perform paging address translation.
- Understand the purpose of a Translation Lookaside Buffer (TLB).
- Explain internal fragmentation in paging.
- Explain segmentation and segment tables.
- Perform segmentation address translation.
- Understand segment protection and sharing.
- Compare paging and segmentation.
- Solve numerical problems related to paging and segmentation.
- Prepare important interview and examination questions.
1. What is Paging in Operating System?
Paging is a memory management technique in which the logical address space of a process is divided into fixed-size blocks called pages, while physical memory is divided into blocks of the same size called frames.
Since every page and frame has the same size, any page can be placed into any available frame in physical memory. Therefore, a complete process does not have to occupy one continuous region of physical memory.
Important Terms in Paging
| Term | Meaning |
|---|---|
| Page | A fixed-size block of a process's logical address space. |
| Frame | A fixed-size block of physical memory. |
| Page Table | Data structure used to map page numbers to frame numbers. |
| Page Number | Identifies a particular page in the logical address space. |
| Offset | Identifies the exact byte or word inside a page. |
| Frame Number | Identifies the physical memory frame containing a page. |
Paging Concept
Figure 1: Pages of a process are mapped to available frames in physical memory.
The important point is that the pages of a process do not necessarily have to be placed in consecutive physical frames. The operating system maintains a page table to remember where each page is located.
2. Why is Paging Required?
In a simple contiguous memory allocation system, a process may require one large continuous block of memory. Over time, allocation and deallocation can create small gaps between allocated blocks. Even when the total free memory is sufficient, a process may fail to find one sufficiently large continuous region.
Paging addresses this problem by allowing the pages of a process to be placed in different physical frames.
Example
Suppose a process requires four pages and physical memory currently has four available frames at different locations:
| Process Page | Allocated Frame |
|---|---|
| Page 0 | Frame 5 |
| Page 1 | Frame 2 |
| Page 2 | Frame 8 |
| Page 3 | Frame 1 |
The pages are physically separated, but the page table allows the operating system to locate them correctly.
3. Working of Paging
Figure 2: Logical address translation using a page table in paging.
When a CPU generates a logical address, the operating system and memory-management hardware divide the address into two components:
- Page Number (p)
- Page Offset (d)
The page number is used to search the page table. The corresponding page-table entry gives the frame number. The frame number is then combined with the original offset to construct the physical address.
Steps of Paging Address Translation
-
CPU generates a logical address.
The address contains a page number and an offset.
-
Page number is extracted.
The page number identifies which page contains the required data.
-
Page table is consulted.
The page table provides the frame number associated with that page.
-
Frame number is obtained.
The operating system or memory-management hardware obtains the physical frame containing the required page.
-
Physical address is formed.
The frame number and offset are combined to obtain the physical address.
-
Memory is accessed.
The processor accesses the required location in physical memory.
Figure 3: General paging address-translation process.
4. Page Table in Operating System
A page table is a data structure maintained for a process to map logical page numbers to physical frame numbers.
Consider the following page table:
| Page Number | Frame Number |
|---|---|
| 0 | 4 |
| 1 | 7 |
| 2 | 1 |
| 3 | 6 |
This means:
- Page 0 is stored in Frame 4.
- Page 1 is stored in Frame 7.
- Page 2 is stored in Frame 1.
- Page 3 is stored in Frame 6.
The page table therefore provides the mapping required to translate logical addresses into physical addresses.
5. Translation Lookaside Buffer (TLB)
A page-table lookup introduces additional memory-access overhead. To reduce this overhead, computer systems commonly use a small, fast associative cache called the Translation Lookaside Buffer (TLB).
The TLB stores recently used page-to-frame mappings. When a logical address is generated, the system can first check the TLB.
TLB Hit
If the required page number is found in the TLB, the corresponding frame number can be obtained quickly. This is called a TLB hit.
TLB Miss
If the page number is not present in the TLB, the system must consult the page table. This situation is called a TLB miss.
6. Page Size and Address Bits
Page size determines the number of bits required for the offset portion of a logical address.
For example, if the page size is 1024 bytes:
Therefore, Offset = 10 bits
If the logical address contains 16 bits, then:
Therefore, the logical address can contain:
- 6 bits for page number
- 10 bits for offset
7. Solved Numerical Example of Paging
Consider a system with:
- Page size = 1024 bytes
- Logical address = 2300
- Page 0 → Frame 5
- Page 1 → Frame 1
- Page 2 → Frame 8
- Page 3 → Frame 3
Step 1: Find Page Number
Page Number = 2
Step 2: Find Offset
Offset = 252
Step 3: Find Frame Number
According to the page table:
Step 4: Calculate Physical Address
= 8 × 1024 + 252
= 8192 + 252
= 8444
8. Another Paging Address Translation Example
A system uses a page size of 512 bytes. Suppose logical address 1000 is generated and the page table contains:
| Page | Frame |
|---|---|
| 0 | 3 |
| 1 | 6 |
| 2 | 1 |
Solution
Page Number:
Offset:
Page 1 is stored in Frame 6.
Physical Address:
= 3072 + 488
= 3560
9. Fragmentation in Paging
Paging eliminates external fragmentation because a page can be placed into any available frame. However, paging may produce internal fragmentation.
Internal fragmentation occurs when the final page of a process is not completely filled.
Example
Suppose:
- Page size = 1000 bytes
- Process size = 2500 bytes
The process requires three pages:
- Page 1 = 1000 bytes
- Page 2 = 1000 bytes
- Page 3 = 500 bytes actually used
The remaining 500 bytes in the final page are unused.
10. Advantages and Disadvantages of Paging
Advantages of Paging
- Eliminates external fragmentation.
- Allows non-contiguous allocation of a process.
- Supports virtual memory effectively.
- Allows pages to be loaded independently.
- Memory allocation becomes easier because all frames have equal size.
- Different processes can use available frames without requiring one large continuous region.
Disadvantages of Paging
- Can cause internal fragmentation.
- Page tables require additional memory.
- Address translation introduces overhead.
- Large address spaces may require multi-level page tables.
- TLB and hardware support may be required for efficient translation.
- Very small page sizes can increase page-table size.
11. What is Segmentation in Operating System?
Segmentation is a memory management technique in which a program is divided into logical units called segments.
Unlike pages, segments are not required to have a fixed size. Their sizes depend on the logical requirements of the program.
Common examples of logical segments include:
- Code segment
- Data segment
- Stack segment
- Heap segment
- Shared library or shared-code segment
12. Segment Table
The operating system maintains a segment table to keep information about each segment.
A typical segment table entry contains:
- Base Address: Starting physical address of the segment.
- Limit: Size or boundary information for the segment.
| Segment | Meaning | Base | Limit |
|---|---|---|---|
| 0 | Code | 2000 | 600 |
| 1 | Data | 3000 | 400 |
| 2 | Stack | 1200 | 200 |
13. Working of Segmentation
Figure 4: Segmentation converts a logical segment address into a physical address.
A logical address in segmentation consists of:
The segment number is used to locate the corresponding segment-table entry. The base address and limit are then used to validate and translate the address.
Segmentation Address Translation Steps
- CPU generates a logical address containing a segment number and offset.
- Segment number is used to locate the corresponding segment-table entry.
- The offset is checked against the segment limit.
- If the offset is outside the permitted range, the access is rejected.
- If the offset is valid, the physical address is calculated using:
14. Solved Numerical Example of Segmentation
Consider the following segment table:
| Segment | Base Address | Limit |
|---|---|---|
| 0 | 2000 | 600 |
| 1 | 3000 | 400 |
| 2 | 1200 | 200 |
Logical Address: (1, 150)
Segment number = 1
Offset = 150
Segment 1 has:
- Base = 3000
- Limit = 400
Since the offset is within the segment boundary, the address is valid.
= 3150
Logical Address: (2, 250)
Segment 2 has a limit of 200.
The requested offset is 250, which exceeds the segment's permitted range.
Figure 5: Segmentation address translation with a boundary check.
15. Protection in Segmentation
One important advantage of segmentation is that different logical portions of a program can have different protection requirements.
For example:
| Segment | Possible Protection |
|---|---|
| Code | Read and Execute |
| Data | Read and Write |
| Stack | Read and Write |
This logical separation can make memory protection easier to express because permissions can be associated with meaningful program components.
16. Sharing in Segmentation
Segmentation can also support sharing of logical program components. For example, a read-only code segment may be shared by multiple processes running the same program.
Sharing can reduce the amount of physical memory required because multiple processes may refer to the same physical segment when appropriate protection rules are satisfied.
17. Fragmentation in Segmentation
Since segments can have different sizes, segmentation can suffer from external fragmentation.
When segments are repeatedly allocated and released, free spaces of different sizes can appear between allocated segments.
The total free memory may be large, but it may be divided into several smaller holes that cannot satisfy a large segment request without additional memory management.
Segmentation → mainly associated with external fragmentation.
18. Advantages and Disadvantages of Segmentation
Advantages
- Matches the logical organization of programs.
- Provides meaningful logical units such as code, data and stack.
- Supports protection at segment level.
- Supports sharing of logical program components.
- Segments can have different sizes.
- Logical separation can simplify program organization.
Disadvantages
- Can cause external fragmentation.
- Variable-size allocation is more complicated.
- Memory allocation may require suitable free holes.
- Segment tables require base and limit information.
- Fragmentation can reduce efficient memory utilization.
- Compaction may be required in some allocation strategies.
19. Difference Between Paging and Segmentation
Paging and segmentation solve memory-management problems using different approaches. Paging uses fixed-size units, while segmentation uses variable-size logical units.
| Feature | Paging | Segmentation |
|---|---|---|
| Basic Unit | Page | Segment |
| Size | Fixed size | Variable size |
| Physical Memory Unit | Frame | Segment occupies a contiguous memory region in the basic model |
| Logical Address | Page number + offset | Segment number + offset |
| Main Table | Page table | Segment table |
| Table Mapping | Page → Frame | Segment → Base + Limit |
| Fragmentation | Internal fragmentation | External fragmentation |
| Program View | More focused on fixed-size memory management | Closely represents logical program structure |
| Protection | Can be implemented through page-level mechanisms | Natural logical protection boundaries at segment level |
| Sharing | Possible through suitable page mappings | Can naturally correspond to shared logical segments |
| Allocation | Frames are equal-sized | Variable-sized memory regions |
| Virtual Memory | Widely used as a foundation for virtual memory | Can be combined with paging in systems using segmented address spaces |
Paging vs Segmentation in Simple Words
20. Paging and Segmentation Together
Paging and segmentation are not necessarily mutually exclusive. A system can conceptually combine the two approaches so that a program is first organized into logical segments and those segments are then managed using paging.
In such an arrangement, segmentation provides the logical organization while paging provides fixed-size memory management.
21. Common Mistakes Students Make
- Confusing page with frame: A page belongs to the logical address space, while a frame belongs to physical memory.
- Forgetting the offset: The offset remains unchanged during ordinary paging address translation.
- Using the wrong page size: Always use the page size given in the numerical problem.
- Confusing internal and external fragmentation: Paging is associated with internal fragmentation, while segmentation can produce external fragmentation.
- Ignoring the segment boundary: In segmentation, the offset must satisfy the segment's protection/boundary condition.
- Confusing page table with segment table: Page tables map pages to frames; segment tables provide base and limit information.
- Assuming paging removes all fragmentation: Paging eliminates external fragmentation but may still have internal fragmentation.
22. Practice Problems on Paging and Segmentation
Try to solve the following questions before opening the solutions. These problems are useful for semester examinations, competitive examinations, technical interviews and Operating System revision.
Practice Problem 1: Paging Address Translation
A system has a page size of 512 bytes. The page table is:
| Page | Frame |
|---|---|
| 0 | 3 |
| 1 | 6 |
| 2 | 1 |
Find the physical address for logical address 1000.
Show Solution
1000 ÷ 512 = 1 remainder 488
Page = 1
Offset = 488
Page 1 → Frame 6
Physical Address:
6 × 512 + 488
= 3072 + 488
= 3560
Practice Problem 2: Paging
A page size is 1024 bytes. Find the page number and offset for logical address 2500.
Show Solution
Floor(2500 ÷ 1024) = 2
Offset:
2500 − (2 × 1024)
= 2500 − 2048
= 452
Practice Problem 3: Segmentation
Consider:
| Segment | Base | Limit |
|---|---|---|
| 0 | 500 | 300 |
| 1 | 1200 | 150 |
Determine the result for logical address (0, 250).
Show Solution
Base = 500
Limit = 300
Offset = 250
Since the requested offset is within the segment's permitted range, the address is valid.
Physical Address:
500 + 250 = 750
Practice Problem 4: Invalid Segmentation Address
Segment 1 has base address 1200 and limit 150. Determine whether logical address (1, 180) is valid.
Show Solution
Requested offset = 180
The requested offset is outside the permitted segment range.
Result: Invalid memory access.
Practice Problem 5: Conceptual Question
Which technique uses fixed-size logical and physical blocks: paging or segmentation?
Show Answer
23. Frequently Asked Questions and Interview Questions
1. What is paging in Operating System?
Paging is a memory management technique that divides a process's logical address space into fixed-size pages and physical memory into equal-sized frames. A page table maps pages to frames.
2. What is a page?
A page is a fixed-size block of a process's logical address space.
3. What is a frame?
A frame is a fixed-size block of physical memory. Its size is equal to the page size.
4. What is a page table?
A page table stores the mapping between logical page numbers and physical frame numbers.
5. What is TLB?
Translation Lookaside Buffer is a small, fast cache that stores recently used page-to-frame mappings to reduce address-translation overhead.
6. What type of fragmentation occurs in paging?
Paging can cause internal fragmentation, especially in the final page of a process when that page is not completely filled.
7. Does paging cause external fragmentation?
Standard paging eliminates external fragmentation because any available frame can hold a page of the appropriate size.
8. What is segmentation?
Segmentation divides a program into variable-size logical units such as code, data, stack and heap.
9. What is a segment table?
A segment table stores information such as the base address and limit associated with each logical segment.
10. What is the logical address format in segmentation?
A logical address in segmentation is generally represented as:
11. What is the physical address formula in segmentation?
After validating the offset against the segment boundary, the physical address is calculated as:
12. What type of fragmentation occurs in segmentation?
Segmentation can suffer from external fragmentation because segments have variable sizes and allocation can leave scattered free spaces.
13. What is the main difference between paging and segmentation?
Paging uses fixed-size pages and frames, whereas segmentation uses variable-size logical segments.
14. Which technique provides a logical view of a program?
Segmentation provides a logical organization because segments can correspond to meaningful program components such as code, data and stack.
15. Why is paging useful for virtual memory?
Paging allows individual fixed-size pages to be managed independently, making it suitable for loading and managing portions of a process rather than requiring the entire process to occupy contiguous physical memory.
16. Can paging and segmentation be combined?
Yes. A system can organize a program into logical segments and then use paging to manage the memory associated with those segments.
17. Why is page size important?
Page size determines the size of each page and frame and also determines how many bits of a logical address are used for the offset.
18. What happens during a TLB miss?
During a TLB miss, the required mapping is not found in the TLB, so the system must consult the appropriate page table to obtain the frame mapping.
24. Quick Revision Notes
25. Important Points for Exams
- Pages and frames have equal fixed sizes.
- Page tables map pages to frames.
- Paging eliminates external fragmentation.
- Paging can produce internal fragmentation.
- TLB reduces the time required for repeated address translations.
- Segmentation divides a program according to logical structure.
- Segments are variable in size.
- Segment tables contain base and limit information.
- Segmentation can produce external fragmentation.
- Paging uses page number and offset.
- Segmentation uses segment number and offset.
- Paging is widely used as part of modern virtual-memory systems.
- Segmentation is useful for expressing logical organization, protection and sharing.
26. Conclusion
Paging and segmentation are fundamental concepts in Operating System memory management. Although both divide a process into smaller units, they are based on different ideas.
Paging divides the logical address space into fixed-size pages and physical memory into equal-sized frames. A page table is used to determine where each page is located. Paging makes non-contiguous allocation possible and eliminates external fragmentation, although internal fragmentation can occur.
Segmentation, on the other hand, divides a program according to its logical structure. Code, data, stack and other meaningful components can become separate segments. Each segment is associated with information such as its base address and limit, allowing logical protection and sharing.
The most important distinction to remember is:
Segmentation: Variable-size logical segments → Segment Table → External Fragmentation
A clear understanding of these concepts provides a strong foundation for studying virtual memory, page replacement algorithms, memory protection, address translation and other advanced Operating System topics.