The primary object of memory management is memory. This article summarizes two ways of memory allocation, which focuses on mastering the basic concepts of discontinuous allocation: paging, segmented and segment-page allocation and address translation.

Continuous memory allocation

To run programs in the system, it is necessary to allocate a certain size of memory space. There are two main memory allocation modes: continuous allocation and discontinuous allocation.

Dynamic partition allocation is a continuous allocation method, which dynamically establishes a variable partition for the program when it is loaded according to the actual needs of the process, and the address of the partition is continuous.

Memory Management mode

In order to achieve dynamic partition allocation, the system must manage the free memory, there are two main methods: bitmap method and free area linked list.

Bitmap method

With the bitmap approach, memory may be divided into allocation units as small as a few words or as large as several thousand bytes. Each allocation unit corresponds to a bit in the bitmap, with 0 indicating idle and 1 indicating occupied.

The disadvantage of bitmaps is that if you want to call in a process with k allocation units, you must search the bitmap for strings with k consecutive zeros. Finding consecutive zeros of specified length in a bitmap is time-consuming.

Free area linked list method

The linked list method maintains a linked list of allocated and free memory segments. A node in a linked list consists of a process, or a free area between two processes.

Memory allocation algorithm

When the program is loaded into memory, it is necessary to select partitions from the bitmap or free linked list and allocate them to the process according to certain algorithms.

First Fit

The first – time adaptation algorithm requires the free – area list to be sorted in ascending order of address. When allocating memory, search along the linked list until you find a partition large enough to split it into two parts, one for the process to use, and one to form a new free area.

Its implementation is relatively simple, but the low-address portion is constantly partitioned, leaving many small free partitions.

Next fit

The next adaptation algorithm is similar to the first adaptation algorithm, except that the search starts from the next free partition of the last found free partition instead of starting from the beginning like the first adaptation algorithm.

Best fit

The best fit algorithm requires that the free partitions be sorted according to their capacity. When allocating memory, find the smallest free partition that meets the requirements and allocate it to the process.

The disadvantage of this algorithm is that the remaining portion of the partition after each allocation is always minimal, leaving many fragments that are difficult to use.

Worst fit

When allocating memory, the worst-adaptive algorithm always selects the largest free partition and divides it into two parts. One part is used by the process, and the other part forms a new free partition.

The worst-fit algorithm prevents the remaining free partitions from generating too small fragments. However, it is easy to destroy large free partitions, and it is difficult to find large partitions later.

Quick fit

The fast adaptation algorithm classifies free partitions according to their capacity and maintains a linked list for each type of free partitions with the same capacity. At the same time, set up a management index table, each item in the table corresponds to a free partition type.

The disadvantage of the fast fit algorithm is that it is time-consuming to effectively merge partitions when the process is terminated or swapped out to free them.

Discontinuous memory allocation

In the case of discontinuous allocation, according to the basic unit of the allocated address space, it can be divided into three storage management modes: paging storage management, segmented storage management, and segmented page storage management.

Paging storage management

In paged storage management, the address space of a user program is divided into several pages of fixed size. A typical page size is 1KB. Accordingly, free memory is also divided into several physical blocks of the same page and block size, so that any page of the user program can be placed in any physical fast to achieve discontinuous allocation.

The address structure in a paging address is:

The address length is 32 bits, in which 0 to 11 bits are intra-page addresses. That is, each page is 4KB. The page number contains 12 to 31 characters and can contain a maximum of 1 MB pages.

The system establishes a page table for each process, which is responsible for the address translation between logical page numbers and physical block numbers. Each page corresponds to a page entry, which records the physical block number of the corresponding page in memory.

Set up a page table base register in the CPU, which stores the start address of the page table and the length of the page table.

During address translation, the page number is compared with the page table length. If the page number is greater than or equal to the page table length, it indicates that the accessed address has exceeded the address space of the process, resulting in an out-of-bounds interrupt. If no out-of-bounds interrupt occurs, the position of the page entry in the page table is obtained by adding the product of the page number and the page entry length, from which the physical block number of the page is obtained, and finally the physical address is obtained from the physical block number and the in-page address.

Paged storage management has two major disadvantages:

  • Performance issues: Accessing a memory unit requires two memory accesses, the first to fetch page table entries and the second to access data. (fast)
  • If each page is too small, the page table can be very large, making it harder to find large contiguous memory space. (Multi-level page table)

A page table to improve

Fast table

In order to improve the speed of address translation, a parallel query buffer register can be added to the address translation mechanism, which is called fast table.

During address translation, the page number is first compared with all page numbers in the fast table. If there is a matching page number, the physical block number corresponding to the page can be read directly from the fast table. If there is no corresponding page table entry in the fast table, you need to access the page table in memory. After finding the physical block number, you can obtain the physical address to access. Also, store this page entry into the fast table. If the fast table is full, you need to find a suitable page table entry and swap it out.

Two-level page table or multilevel page table

A two-level or multilevel page table method in which the page table is paginated so that each page is the same size as the physical block of memory, they are numbered, and then the pages are placed separately in different physical blocks discretely. Similarly, an outer page table is created, with each page entry recording the physical block number on the surface of the page.

During address transformation, an outer page table register needs to be added to store the start address of the outer page table. Use the outer page table start address and the outer page number in the logical address to find the specified page table start address, then use the outer page address to find the specified page table entry, from which the page in memory physical block number, finally get the physical address. A total of three memory accesses are required to access a memory unit.

Segmented storage management

In segmented storage management, the address space of a process is divided into several segments, such as main code segment, sub-module code segment, stack segment, initialization data segment, symbol table, and so on. Each segment is addressed from 0, uses a contiguous address space, and is not of equal length.

The address structure of the segment address is as follows:

In this address structure, a process is allowed to have a maximum of 64K segments, and the maximum length of each segment is 64KB.

The system establishes a segment table for each process, which is used to map logical segments to physical memory areas. Each segment has an entry in the table that records its base address in memory and the length of the segment.

A segment table register is set up in the system, which is used to store the segment table beginning address and segment table length. During address translation, the segment number is compared with the segment table length. If the segment number is greater than the segment table length, the access is out of bounds.

If no, it obtains the position of the corresponding segment entry based on the start address of the segment table and the segment number, and reads the start address of the segment in memory. Then check whether the IP address in the segment exceeds the length of the segment. If it exceeds, it also generates an out-of-bounds interrupt; Otherwise, the segment base address and the segment address are added to obtain the memory address to be accessed.

Paged and segmented comparison

  • Paging storage is used to improve memory utilization. Segmentation is used to better meet the needs of users.
  • In paging storage, the page size is determined by the system and fixed. In segmented storage, the length of a segment is determined by the user program.
  • In paging storage, physical block numbers are mainly stored in page tables. In segmented storage, the segment table mainly stores the segment base address and segment length.

Segment-page storage management

Segment-page storage is a combination of segmenting and paging, in which a user program is first divided into segments and then each segment into pages. The address structure of a segment page consists of the segment number, the page number within the segment, and the address within the page.

To implement address translation, the system needs to set up both the segment table and the page table. Here, however, the segment table stores the start address and segment length of the page table.

In address translation, the first will be compared with long period, if segment number is less than the long said without crossing the line, then using the segment table segment start address and number of which corresponds to the position of segment table entries in the segment table, get this page table start address, and pages related to the logical address of the segment number is used to obtain the corresponding page page table entries, to read the page’s physical block number, Use the block number and page address to get the physical address.