Segmentation and Paging

Segmentation and Paging in Operating Systems

Segmentation and paging are two memory management schemes used to manage how processes are stored in memory. Both techniques are designed to solve the issues of contiguous memory allocation (which suffers from fragmentation) and to make memory management more efficient and flexible. Let’s dive into each of these concepts in detail.

---

Segmentation

Segmentation is a memory management scheme that divides a program into logically distinct segments. Unlike contiguous memory allocation, where the memory is divided into fixed-size partitions, segmentation divides memory based on the program's logical structure (such as code, data, stack, etc.).

How Segmentation Works

In segmentation, a program is divided into segments, where each segment is a separate entity that holds a particular type of data. For example:

• Code segment: Contains the executable code.
• Data segment: Stores global and static variables.
• Stack segment: Holds the runtime stack, including function call information and local variables.
• Heap segment: Used for dynamically allocated memory.

Each segment has its base address and length, which means that the segment is stored in a logical sequence in memory but not necessarily in a contiguous block. This allows processes to have non-contiguous allocation of memory, which helps to overcome fragmentation problems seen in contiguous allocation.

Advantages of Segmentation

1. Logical Division: Segmentation divides the program into logically meaningful units, making the system easier to understand and manage.
2. No External Fragmentation: Segments are allocated non-contiguously, which can help reduce external fragmentation (though internal fragmentation is still possible within each segment).
3. Easy Sharing: Segments like code or libraries can be shared among different processes, reducing memory overhead.

Disadvantages of Segmentation

1. External Fragmentation: Even though each segment is allocated non-contiguously, free memory can still be scattered around, causing external fragmentation between segments.
2. Complexity: Managing multiple segments per process can be complex, especially with multiple segments needing to be loaded or swapped.
3. Variable Size: Different segments may require different amounts of memory, making it difficult to manage space effectively without careful allocation.

Segment Table

Each process has a segment table to store the base address and length of each segment. The logical address (also called a segment number and offset) generated by the CPU is translated using the segment table:

• The segment number indicates which segment to access.
• The offset specifies the exact location within the segment.

---

Paging

Paging is another memory management technique in which the physical memory is divided into fixed-size blocks called pages and physical memory is divided into page frames of the same size. A program is also divided into pages, but instead of the program’s logical divisions (like code, data, and stack), a program is divided into small, fixed-size pages.

How Paging Works

• Page: A page is a small, fixed-length contiguous block of logical memory.
• Frame: A frame is a block of physical memory, also of the same size as a page.
• When a program is executed, the operating system loads its pages into any available frames in physical memory. The mapping between logical pages and physical frames is maintained by the page table.

A program’s logical address is split into two parts:

• Page number: Indicates the page that the data belongs to.
• Offset: Specifies the location of the data within that page.

The logical address is translated to a physical address using the page table. The page table maps the page number to the frame number in physical memory.

Advantages of Paging

1. Eliminates External Fragmentation: Since pages and frames are of fixed size, there’s no problem of external fragmentation. Even if free memory is fragmented, as long as there are enough free frames, the system can continue allocating memory to processes.
2. Efficient Memory Utilization: Paging allows for efficient use of memory, as processes are loaded into non-contiguous blocks in physical memory.
3. Easy Process Isolation: Paging allows the operating system to isolate processes effectively since each process is given its own virtual address space and cannot directly access the memory of another process.
4. Swapping: Paging works well with swapping, as individual pages can be swapped in and out of memory, rather than entire processes.

Disadvantages of Paging

1. Internal Fragmentation: Though paging eliminates external fragmentation, each page is of a fixed size, which means that if a process doesn’t completely fill the last page, the remaining space is wasted (internal fragmentation).
2. Overhead: Paging requires maintaining a page table for each process, and the translation of logical to physical addresses can involve overhead, especially if the page table is large or the system uses multi-level page tables.
3. Complexity: The translation from logical to physical memory (using the page table) adds complexity, and the page tables themselves require memory management.

Page Table

The page table holds the mapping from a process’s logical pages to physical frames. Each entry in the page table stores the frame number corresponding to the page, along with additional bits such as valid/invalid and access permissions.

---

Comparing Segmentation and Paging

Feature	Segmentation	Paging
Memory Division	Divides memory into logical segments (e.g., code, data).	Divides memory into fixed-size pages.
Size	Segments can be variable in size.	Pages are of fixed size.
Fragmentation	External fragmentation can occur.	Internal fragmentation occurs within pages.
Address Translation	Requires segment table and offset.	Uses page table for address translation.
Ease of Sharing	Segments like code can be easily shared among processes.	Pages may be shared but less naturally than segments.
Efficiency	More complex due to variable segment sizes.	Simpler but has the overhead of page tables.
Use Case	Suitable for programs with distinct logical divisions.	Suitable for programs requiring contiguous memory without fragmentation.

---

Page Table Example

Here’s an example of how paging works:

• Logical Address: A process generates a logical address consisting of a page number and an offset.
• Page Table: A page table stores the mapping between the page number and the corresponding frame in physical memory.

Suppose the process has:

• 4 pages, and the physical memory has 4 frames.

Page Number	Frame Number
0	2
1	3
2	0
3	1

If the logical address has a page number of 2 and an offset of 5, we look up page 2 in the page table and find that it is mapped to frame 0. The final physical address is the frame number + offset.

Conclusion

• Segmentation provides a way of managing memory based on the logical structure of a process. It offers flexibility but can suffer from external fragmentation.
• Paging divides memory into small, fixed-sized pages, and addresses this issue by eliminating external fragmentation, but can suffer from internal fragmentation and requires managing page tables.

Modern operating systems often use a combination of segmentation and paging. For example, x86-64 architecture uses paging for memory management but also incorporates segmentation for certain tasks such as code and data separation, although segmentation is less common in modern systems.