Talk about virtual memory

(We usually say how much computer memory, refers to the physical memory)

Process in the process of running need access to physical memory, but the physical memory is limited, in order to put the limited physical memory allocated to the different processes used, Linux for each process provides an independent continuous virtual address space, the virtual address space and physical memory has a mapping relationship, the mapping relationship is stored in the kernel space, A process accessing virtual memory is accessing physical memory. In kernel space, the virtual address of all processes corresponds to the physical address, that is, the kernel process does not have its own address space. In user space, processes have a separate address space to prevent data interference between different processes.)

Each process has a contiguous virtual address space mapped to that physical memory, so the virtual address space is naturally larger than the actual physical memory. So Linux maintains a memory map in the CPU’s memory management unit, the MMU, that maps virtual addresses to physical addresses of processes. Linux also maintains a TLB in the CPU cache to cache the address map (page table) that has been found, speeding up access to the search memory map.

Part of the page is in physical memory and part is on disk. A page-missing interrupt occurs when an application accesses a page whose virtual address is not mapped to physical memory: Linux causes processes to get stuck in kernel space, which uses a page replacement algorithm to get a chunk of free physical memory. Kernel space then reads pages from disk that need to be accessed into the physical memory, changes the mapping between virtual addresses and physical memory, and returns to user space to execute instructions again.

The MMU specifies that the minimum unit of the virtual address space is called a page, so the mapping table is called a page table, and the mapping is called a page table entry. When there are more and more page table entries, it takes up a lot of space. So Linux provides multilevel page tables and large pages.

Multi-level page tables manage memory partitions by changing the original mapping to area indexes and offset (virtual page numbers in the page table match the index, and then the offset is used to obtain the physical memory address). Because the virtual memory space is usually used for only a small portion, only this small portion of the block is held in a multistage page table.

However, in many cases, it is better to have multiple independent address Spaces than just one dimensional page after another. And one-dimensional sequential storage pages are not easily logical. So we divide the user space in the virtual address space into several meaningful segments, and then treat each segment as a virtual memory, and then divide each segment into several pages for storage. And the segment size can be changed with the size of the program’s data structure, which is more conducive to our virtual memory management. (Read-only segment {code and constants}, data segment {all variables}, heap, file mapping segment {shared memory, etc.}, stack)

Page replacement algorithm

Why page replacement: above…. . When a page replacement occurs, detect whether the page has been modified. If it is not modified, it is eliminated directly. If it is modified, it needs to write back to the disk to update the copy on the disk.

(1) Optimal page replacement algorithm: the occurrence of missing page interruption, the replacement of the longest will not be visited the page, impossible to achieve.

② Recently unused: update its R bit when a page is accessed, update its M bit when it is modified. Then according to unvisited unmodified, visited unmodified, etc., it is divided into four categories numbered from small to large. When a page – missing interrupt occurs, a page is randomly selected from the smallest non-empty class to be eliminated.

③ First-in, first-out: the operating system maintains a linked list, and the earliest pages are placed at the head of the list. When a missing page interrupt occurs, the header page is eliminated. But only the use of pure first-in first-out page replacement algorithm easy to commonly used pages out, so there is a second chance page replacement algorithm.

④ Second chance: in the elimination of table header page, will first detect page R bit, if it has been recently visited, then put it R position 0 and move to table bit. It essentially looks for pages that have not been visited in the most recent time interval.

⑤ Least recently used: when sending the missing page interrupt, replace the page that has not been used for the longest time. It is implemented by accessing a counter, and the page with the smallest counter is eliminated in the event of a page-missing interrupt.

On 32-bit systems, user space: kernel space = 3:1