Memory management

Virtual memory

The purpose of virtual memory is to expand physical memory into larger logical memory, thus allowing programs to have more available memory.

To better manage memory, the operating system abstracts memory into address space. Each program has its own address space, which is divided into multiple sections, each called a page. These pages are mapped to physical memory, but they do not need to be mapped to contiguous physical memory, nor do they need to have all pages in physical memory. When a program references a page that is not in physical memory, the hardware performs the necessary mapping, loads the missing part into physical memory and re-executes the failed instruction.

As you can see from the above description, virtual memory allows a program to run without having to map every page of the address space to physical memory.

Paging system address mapping

The memory management unit manages the conversion of address space to physical memory, where the page table stores the mapping table of pages (program address space) and page frames (physical memory space).

A virtual address is divided into two parts, one stores the page number and one stores the offset.

Page replacement algorithm

During a program run, if the page to be accessed is not in memory, a page miss interrupt occurs and the page is called into memory. If there is no free space in memory, the system must transfer a page from memory to the swap area of disk to make room.

The main goal of the page replacement algorithm is to minimize the frequency of page replacement (or the rate of missing pages).

1. Optimal displacement algorithm

The page selected to be swapped out will be the longest that is not accessed, usually guaranteeing the lowest page miss rate.

2. Most recently unused algorithm (LRU algorithm)

There is no way to know what pages will be used in the future, but you can know how pages have been used in the past. LRU swaps out the most recent and longest unused page.

To implement LRU, you need to maintain a linked list of all pages in memory. When a page is visited, move the page to the linked list header. This ensures that the pages at the end of the list are the most recent and unvisited.

Because the linked list needs to be updated with each access, the LRU implemented this way is expensive.

3. Not recently used (NRU algorithm)

Each page has two status bits: R and M, setting R=1 when the page is visited and M=1 when the page is modified. The R bit is periodically cleared. Pages can be divided into the following four categories:

  • R = 0, M = 0
  • R = 0, M = 1
  • R = 1, M = 0
  • R = 1, M = 1

When a page-missing interrupt occurs, the NRU algorithm randomly selects a page from the nonempty class with the smallest class number to swap them out.

NRU prioritizes dirty pages that have been modified (R=0,M=1) over frequently used clean pages (R=1,M=0)

4. First in, first out (FIFO)

Select the page to pout to be the first page to enter.

However, the first page is also likely to be visited more often, which can lead to higher page miss rates.

5. Second chance algorithm

FIFO algorithm may replace frequently used pages. To avoid this problem, make a simple change to the algorithm:

Set the R bit of the page to 1 when it is accessed (read or written). When replacement is needed, check the R bit of the oldest page. If the R bit is 0, the page is old and unused and can be replaced immediately. If it is 1, clear R bit to 0, place the page at the end of the list, modify its load time to look like it was just loaded, and continue searching from the head of the list.

6. Clock algorithm

Second chance algorithms require moving pages through linked lists, reducing efficiency. The clock algorithm uses a circular linked list to connect pages and a pointer to the oldest page.

piecewise

Users divide their jobs into logical segments, each of which is addressed from 0 and has its own name and length (such as data segment, code segment, stack segment in assembly language).

Therefore, the logical addresses that programmers desperately need to access are determined by segment names (segment numbers) and in-segment offsets (in-segment addresses), which not only makes programming easier for programmers, but also makes programs intuitive and more readable.

A page in a paging system is just a physical unit (block) of information and has no complete logical meaning

Section of the page type

The address space of a program is divided into segments with independent address Spaces, and the address space on each segment is divided into pages of the same size. This has both the sharing and protection of a segmented system and the virtual memory function of a paging system.

Comparison of paging and segmentation

  • Transparency to the programmer: Paging transparency, but segmentation requires the programmer to explicitly partition each segment.
  • Dimensions of address space: paging is a one-dimensional address space and segmentation is a two-dimensional address space.
  • Whether the size can change: The page size is immutable, and the segment size can change dynamically.
  • Why this happens: Paging is mainly used to implement virtual memory, thus obtaining larger address space; The purpose of segmentation is to enable programs and data to be divided into logically separate address Spaces and to facilitate sharing and protection.