Memory Management: Paging and Segmentation Explained

Posted on Dec 21, 2024 in Other subjects

Memory Management: Paging and Segmentation

Wasted space at the end of the last page is a physical issue and is grave if the size of the page is large. Table fragmentation (memory wasted to store the page tables) is a serious matter if the size of the page is small. The page size in practice is located between 128 and 1024 words (between 512 and 8192 bytes) fully associative to be the location.

Load Algorithm

When to transfer a page from virtual memory (secondary) to primary memory?

Solutions:

  1. Load on demand: The page is loaded into virtual memory when referenced, and into the principal memory when a page fault occurs. This is simple and does not overload the pagination channel. It is usual for 16 and 32-bit microprocessors.
  2. Preload: Following a page fault, the blocked main page is loaded into memory along with additional ones. It is a predictive method that preloads those pages that would produce a failure in the future. The number of pages filled depends on the organization’s information in secondary memory, the type of interface between the primary and secondary memory, the size of the primary memory, and if the size is constant. Usually, one page is loaded.

Replacement algorithm: Controlled by the OS (theoretical approaches: FIFO, LRU; practical approaches: LFU, NUR).

Disadvantages of Pages

Pages are of fixed and arbitrary size. They bear no relationship to the logical structure of the program. There may be data in an unrelated page with others. Inefficiency by the locality principle.

Segmented Systems

A memory system that considers virtual blocks of unequal size, defined on the logical structure of the program code and data (procedures, functions, arrays). Each block is called a segment. Most of the features (concepts) of segmented systems are similar to paged systems.

Address Translation

  • Virtual address (si, dj): si is the segment number, dj is the displacement.
  • Segment Table: Contains information to translate the segment to a physical address at the beginning of the segment. Its entries contain information similar to that contained in the page table entries, along with the length of the segment.
  • Segment Fault: A segment reference that is not resident in the main memory.
  • Types of translation: The same as in paged systems (direct association or hybrid) with the difference that the displacement is added (not concatenated).

Segmentation Fault

It is necessary to determine if there is space in the primary memory to locate the virtual segment (this problem does not exist in paged systems).

Solution: Structuring the memory by defining two main businesses like linked lists (list of reserved segments, list of free segments (LAVS), usually in ascending order of their position).

Virtual Space

A two-dimensional space is segmented: segments are blocks of contiguous virtual addresses, but the segments are not contiguous with one another. There is an exception when trying to access a position outside the segment.

Segment Sharing

Possibility of sharing segments:

  1. A shared segment is referenced by two processes with the same number.
  2. A shared segment is referenced by two different processes with different numbers. This is a more versatile scheme, implemented with a segment table private to each process that may be needed to generate the shared segment’s number in a context-dependent manner.

Load and Location Algorithms

The load process is similar to paged systems, with the location process being the most complex.

The algorithms are all based on the list of available segments (LAVS):

  1. First-Fit: Uses the LAVS list. The non-resident requested segment is placed in the first free segment of the main memory where it fits (in ascending order of physical addresses). If the processor requests a non-resident segment of size S, the following is performed:
    1. Let Q <- FIRST (initial pointer of LAVS).
    2. If SIZE(Q) > L, S is placed from the physical address Q + SIZE(Q) – L. Updates SIZE(Q) to SIZE(Q) – L.
    3. If SIZE(Q) = L, S is placed from the physical address Q. The free segment is deleted from LAVS.
    4. If SIZE(Q) < L, assign Q <- NEXT(Q) and go to step 2.

    To prevent the formation of free segments that are too small, change steps 2 and 3 to:

    1. If SIZE(Q) > L + C…
    2. If L <= SIZE(Q) <= L + C…
  2. Best-Fit: Uses the LAVS list. The non-resident requested segment is placed in the smallest free segment of the main memory where it fits. The location procedure is the same as the first-fit algorithm, but previously, the LAVS list is sorted in increasing order according to the sizes of the free segments.
  3. Worst-Fit: Uses the LAVS list. The non-resident segment is placed in the largest free segment of the main memory. The location procedure is similar to the Best-Fit algorithm, except that the LAVS list is sorted in descending order according to the sizes of the free segments.
  4. Binary Buddy: Segment size and LAVS are whole powers of 2. It makes use of the LAVS list. The location procedure divides the LAVS list into n lists (2n is the maximum segment size), where the i-th list links free segments of size 2i (buddies). The n lists may restructure in two forms:
    1. A free segment list of (i+1)-th is divided into two equal segments, and are linked to the i-th list.
    2. A reverse process.

    Develop the location algorithm based on the n lists and their two previous restructuring mechanisms.

Comparison of Location Algorithms

  • Best-Fit: Minimizes the size of the free segment remaining after the location. It is the worst of the elections, as it generates many small free spaces that will not be used.
  • Worst-Fit: Based on the idea that after location, the excess free segment is large enough to be useful.
  • Most Efficient: First-Fit and Binary Buddy.
  • Disadvantages associated with the location: External fragmentation – lost physical memory space due to the excess production of free segments of very small (useless) size.

Compaction or Replacement

When applying for a non-resident segment, there may be two situations: that there is a free segment large enough (location) or that there is no such free segment (compaction or replacement).

  • Compaction (garbage collection): Free segments are rearranged to form a single large free segment in an adjoining area of the physical memory. The problems are that it has a large consumption of time and requires updating the segment tables.
  • Replacement: Similar to paged systems. The only difference is that the segment size requested should be noted. Problems include inefficient use of physical memory and the replaced segment may be needed in the future.

The relationship between compaction and replacement is not simple: it depends on each particular situation.

Segment Size: Segments can be inordinately large.

Solution: Limit the size of segments/paged segments (segmentation with paging).

Paged Segmentation System

Today, few pure segmentation systems are used because of the trouble making replacements. A hybrid approach is paged segments. This simplifies the replacement (it is not required that a segment’s memory is contiguous, and it is not necessary to load the whole segment into memory). Segments are divided into an integer number of pages. This leads to either numbered segmentation (segmentation dominates) or nominal segmentation (paging dominates).

Virtual Address

(si, pj, dk) – 3-dimensional space, where si is the virtual segment number, pj is the virtual page number, and dk is the displacement within the page.

The Page Table Segment (PTS) points to the segment table of the ongoing process. The limit field indicates the size of each segment. The bits are the protection level of the pages (not necessary in nominal segmentation). A flag indicates the residence in the primary memory of each page.

DOS translations have a high temporary cost.

Solution: Using or using fast TLB entries.

The page fault is resolved in the same way as purely paged systems.

Problem: Failure to access the page table slows down the process, leading to two failures.

Page Segmentation vs. Words by Address

  • Words by Address:
    • Page: 1
    • Segment: 2 (segment and offset)
  • Visible to Programmer:
    • Page: Invisible to the application programmer.
    • Segment: May be visible to the application programmer.
  • Replacement of a Block:
    • Page: Trivial (all blocks are the same size).
    • Segment: Hard (must find an unused part of the main memory of variable size and contiguous).
  • Inefficient use of Memory:
    • Page: Internal fragmentation (unused portion of the list).
    • Segment: External fragmentation (unused parts of the main memory).
  • Efficient Disk Traffic:
    • Page: Yes, if the page size is adjusted to balance access time and transfer time.
    • Segment: Not provided (small pieces can transfer only a few bytes).

**In the location algorithm examples, the data in parentheses is the first address where the free segment begins and the second is its size.**