1. 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 blocks, each called a page. These pages are mapped to physical memory, but do not need to be mapped to contiguous physical memory, and perhaps all pages do not need to be in physical memory. When a program references a page that is not in physical memory, the hardware performs the necessary mapping, loading the missing part into physical memory and re-executing the failed instruction.

  • As you can see from the above description, virtual memory allows a program to run without mapping every page in the address space to physical memory, meaning that a program does not need to be fully loaded into memory to run large programs, making it possible to run large programs with limited memory.

  • For example, if a computer can generate 16-bit addresses, the address space of a program ranges from 0 to 64K. The computer has only 32KB of physical memory, and virtual memory technology allows the computer to run a 64K program.

2. Paging system address mapping

  • Memory Management Unit (MMU)Manages the conversion of address space to physical memoryThe 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 the other stores the offset.
  • For example, for the virtual address (0010000000000100), the first four bits are used to store page 2, and the entry content is (1101). The last bit of the page entry indicates whether it exists in memory, and 1 indicates in. Last 12 bits storage offset. This page corresponds to the frame address bit (1100000000000100)

3. 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 call a page from memory into disk swap to free up space.
  • Page replacement algorithms are similar to cache elimination strategies in that memory can be thought of as a cache for disk. In a cache system, the size of the cache is limited. When a new cache arrives, part of the existing cache needs to be eliminated so that there is space for storing the new cache data.
  • The main goal of the page replacement algorithm is to minimize the frequency of page replacement (or the rate of missing pages).

3.1, the best

OPT Optimal replacement algorithm

  • The page selected to be swapped out will be the longest not accessed, usually guaranteeing the lowest page miss rate
  • Is a theoretical algorithm, because there is no way to know how long a page is no longer accessed.
  • For example, a system allocates three physical blocks to a process and has the following sequence of page references:

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

To start running, load the 7, 0, and 1 pages into memory. When the process attempts to access page 2, a page-missing interrupt occurs and page 7 is swapped out because page 7 has been accessed the longest.

3.2. Recently and longest unused

LRU, Least Recently Used

  • 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 to be accessed.
  • Because the linked list is updated with each access, the LRU implemented this way is expensive.

4，7，0，7，1，0，1，2，1，2，6

3.3. Not used recently

NRU, Not Recently Used

  • Each page has two status bits: R and M, which are set to R=1 when the page is visited and M=1 when the page is modified. The R bit will be periodically cleared 0, the page can be divided into the following four categories
    • R=0 , M=0
    • R=0 , M=1
    • R=1 , M=0
    • R=1 , M=0
  • When a page-missing interrupt occurs, the NRU algorithm randomly selects a page from the non-empty class with the smallest class number to swap it out
  • NRU is limited to swapping out dirty pages that have been modified (R=0, M=1) instead of frequently used clean pages (R=1, M=0).

3.4 first in, first out

FIFO first in first out

  • Select the first page to enter when swapping out the page.
  • The algorithm will swap out frequently visited pages, resulting in a higher page miss rate

3.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 useless and can be replaced immediately.
  • If it’s a 1, bit R to zero and place the page at the end of the list, modify its load time to make it look like it just loaded, and then continue searching from the head of the list.

3.6, clock

Clock

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

4,

  • Virtual memory uses paging, which divides the address space into fixed-size pages, each of which is mapped to memory.
  • In the following figure, a compiler creates multiple tables during compilation. Four of the tables grow dynamically. If you use a paging system bit address space, dynamic growth can cause overwriting problems

  • Segmentation is the practice of dividing each table into segments, and each segment constitutes a separate address space. The length of each segment can be different and can grow dynamically

5, section 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.

6. Comparison of pagination and segmentation

  • Transparency to the programmer: Paging transparency, but segmentation requires the programmer to display each segment
  • Dimensions of address space: paging is a one-dimensional spatial address and segmentation is a two-dimensional one.
  • 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 main purpose of segmentation is to allow programs and data to be divided into logically separate address Spaces and to facilitate sharing and protection.