Understanding Virtual Memory: Paging and Segmentation

Posted on Dec 16, 2024 in Computers

Paging

The virtual address space is divided into pages of equal size. The main memory is divided into physical pages of the same size. These physical pages are shared among different processes in the system. A process will have a few pages resident in main memory (active) and the rest in secondary memory (inactive). The paging mechanism serves two functions:

  1. To carry out the task of transforming addresses, or set the page that corresponds to a particular address of a page, as well as the physical page, if any, occupying this page.
  2. Transfer pages of secondary memory to main memory when needed, and from the main memory to secondary memory when no longer needed.

Segmentation

Segmentation consists in dividing the address space into segments, each of which corresponds to a routine, a program, or data set. This can be accomplished by adding several pairs of base and limit registers for each processor so that the address space can be divided into several different areas. The set of base and limit registers form a table called the segment table.

Drawback: The number of segments, for economic reasons, is necessarily small. We need an agreement in order to establish which segments will be used for each purpose.

Memory Management Strategies

The policies for memory management can be grouped into three groups:

  • Substitution Policy
  • Charging Policy
  • Location Policy

Substitution Policy

These determine what information should be drawn from the main memory, or are responsible for the establishment of zones of free memory.

Replacement Policies for Paged Systems

The information blocks are replaced pages. Three common replacement algorithms are:

  1. Algorithm of the Least Recently Used (LRU): Replace the page that has not been used for the longest time.
  2. Less Frequently Used Algorithm (LFU): Replace the page that has been used least over a specific time interval immediately preceding it.
  3. First-In, First-Out Algorithm (FIFO): Replace the page that has been resident the longest.

Replacement Policies for Non-Paged Systems

The information blocks are replaced by segments (clearly referring to the address space of a process). There is a caveat that not all segments occupy the same amount of memory, so that consideration of the segment to be relegated to the secondary memory will be influenced by the size of the segment to load.

The simplest algorithm is to replace the segment (if any) together with adjacent open spaces that have freed up enough memory for the new segment. If multiple segments of this kind exist, involve any of the above criteria (such as LRU) to choose one of them. If no segment exists, several will be replaced.

Charging Policy

These determine when to load data in main memory. They are divided into two broad categories:

  • On-Demand: The lack of a block causes a request to charge, so that algorithms of location and/or replacement will place the new block in memory.
  • Proactive: They load the blocks in advance, so it should be based on predictions of the future behavior of the program. These predictions can be done based on two criteria:
    1. The nature of the construction of the program, referring to the principle of locality.
    2. The inference based on past behavior.

Location Policies

These determine where in main memory it is necessary to place the information read, i.e., they must choose a part of the area of free memory.

Location Policy for Paged Systems

To place k pages, just use the replacement algorithm in order to free k physical pages.

Location Policy for Non-Paged Systems

There will be a list of holes (memory spaces). Your task is to decide which hole to use and update the list after each insertion hole. If the block load is smaller than the hole, this will be placed on the left side or bottom of the hole. This technique minimizes the fragmentation of this hole.

If it is larger, the location algorithm will move the blocks that are in memory to create a hole big enough.

Main Algorithms

Let x1, x2, x3, …, xn be the list of holes.

  1. Best-Fit Algorithm: Holes are sorted by increasing size. If s is the block size to place, determine the smallest i such that s ≤ xi.
  2. Worst-Fit Algorithm: Holes are sorted by decreasing size. Place the block on the first hole, and the rest of the hole is incorporated into the corresponding position in the list.
  3. First-Fit Algorithm: Holes are ranked by increasing base address. If s is the block size to place, determine the smallest i such that s ≤ xi.
  4. Recursive Algorithm: The sizes of the blocks should be powers of 2, s = 2i, i ≤ k. Holes are grouped by size: 21, 22, …, 2k. A hole can be drawn that is on the list (i+1) and split in half, creating two holes of size 2i in list i. Conversely, compacting holes.