Operating System

Demand paging and Segmentation

Segmentation supports the user’s point of view. In segmentation, memory is divided into segments of variable size and each segment is allocated to a process.

Demand paging follows a criterion that states that a page is only loaded from secondary memory into main memory when it is needed.

Scope

This article explains segmentation and demand paging in detail.

Definition

Users want to see memory as a collection of variable-sized segments with no necessary ordering of segments. They do not want to view memory as a linear array of bytes.

A logical grouping of instructions such as subroutine, array, or data is called a segment. Every program is a collection of these segments. 

The main program includes various data structures such as objects, arrays, stacks, variables, etc. Each of these segments is of variable length where length is the purpose of the segment in the program. Elements within a segment are identified by their offset from the beginning of the segment.

Segmentation is a memory management scheme that supports the user’s view of memory. A logical address space is a collection of segments. Each segment has a name and length. 

The segment name and the offset within the segment are specified by the addresses. A logical address consists of:

< Segment_number, offset>

A C compiler creates separate segments for the following :

  1. The code
  2. Global variables
  3. The heap from which memory is allocated.
  4. The stacks are used for each thread.
  5. The standard C library

The mapping of logical addresses into physical memory is done with the help of a segment table. Each entry in the segment table has a segment base and segment limit. The segment base contains the starting physical addresses where the segments reside in the memory and the segment limit specifies the length of the segment.

A logical address consists of two parts: a segment number and an offset into that segment (d). The segment number is used as an index to the segment table. The offset d of the logical address must be between 0 and the segment limit. If it is not, we trap the OS. When an offset is legal, it is added to the segment to produce the address in the physical memory of the desired byte. The segment table is an array of base limit register pairs.

Segment 2 is 400 bytes long and begins at 4300. Thus, a reference to byte 53 of segment 2 is mapped to location 4300 + 53 = 4353. A reference to segment 3, byte 852 is mapped to 3200 + 852 = 4052. A reference to byte 1222 of segment 0 would result in the trap as this segment is only 1000 bytes long.

Advantages 

  • It eliminates fragmentation.
  • Segmentation supports virtual memory.
  • It allows dynamically growing segments.
  • It facilitates shared segments 
  • It provides dynamic linking and loading of segments..

The segment table base register (STBR) points to the segment table’s location in memory. The segment table length register (STLR) indicates the number of segments used by a program.

Demand Paging

Sometimes we may not initially need the entire program in memory. To solve this problem we use a technique called demand paging. In demand paging, we initially load pages only as they are needed. It is commonly used in virtual memory systems. 

In-demand paged virtual memory pages are only loaded when they are demanded during program execution. Pages that are never demanded are thus never loaded into physical memory. 

To swap the process into the memory a lazy swapper is used, it never swaps a page into the memory unless that page will be needed. 

A pager is used for demand paging because a pager is concerned with the individual pages of a process, unlike a swapper which manipulates the entire process. When a process is to be swapped in, the pager guesses which pages will be used before the process is swapped out again. The pager only brings the guessed pages into the memory. Thus, it avoids reading into memory pages that are not going to be used. And doing this decreases the swap time and the amount of physical memory needed.

The valid and invalid bit scheme is described. The pages are legal and in memory when the bit is set valid. And if the bit is set to invalid then the page can be either valid or invalid. But it will remain on the disk. The page table entry for a page that is brought into memory is marked as valid but the page entry that is not currently in memory is simply marked as invalid.

A page fault trap is caused when we access a page marked as invalid. It causes a trap in the operating system. This is the result of the failure of the operating system to bring the desired page into the memory. 

The procedure is as follows:

  1. Firstly we determine whether the reference was valid or invalid memory access by checking an internal table for this process.
  2. We terminate the process if the reference was invalid but if it was invalid and not yet brought into that page, we now page it in.
  3. Then we check the free frame list and search for the free frames.
  4. A disk operation is scheduled to read the desired page into the newly allocated frame.
  5. On completion of the disk read, we modify the internal table kept with the process and the page table to indicate that the page is now in memory.
  6. The instruction that was interrupted by the trap is now restarted.

The process starts executing with no pages in memory. When the OS sets the instruction pointer to the first instruction of the process which is on a non-memory resident page, the process immediately faults the page. This page is brought into the memory and then the process continues to execute. It continues faulting as necessary until every page that it needs is in memory. At that point, it can execute with no more faults. This scheme is pure demand paging i.e never bring a page into memory until it is required. 

Summary

Segmentation is a memory management technique that is similar to paging but unlike paging, segments are of variable length. It supports the user’s view of memory. 

Demand paging is the combination of both paging and swapping. In this, a page is only loaded from secondary memory to main memory only when it is needed.

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article