Related knowledge of paging

What is pagination ？
Divide the memory space into equal and fixed blocks , As the basic unit of main memory . Because the program data is stored in different pages , And the pages are scattered in memory , So you need a page table to record the mapping relationships , To realize the mapping from page number to physical block number .

Accessing the memory data in the paging system requires two memory accesses ( One is to access the page table from memory , Find the specified physical block number , Add the in page offset to get the actual physical address ; The second time is to access the memory and get the data according to the first physical address ).

What is segmentation ？
Paging is to improve memory utilization , Segmentation is to meet some logic requirements of programmers when they write code ( Like data sharing , Data protection , Dynamic linking and so on ).

Segmented memory management , The address is two-dimensional , One dimension is the segment number , Two dimensional is the in segment address ; The length of each segment is different , And inside each segment is from 0 Started addressing . Due to the segmented Management , Inside each segment is a continuous memory allocation , But segments are distributed discretely , Therefore, there is also a mapping relationship between logical address and physical address , The corresponding is the segment table mechanism .

What's the difference between pagination and segmentation ？
Paging is transparent to programmers , But segmentation requires the programmer to explicitly partition each segment .
The paging address space is a one-dimensional address space , Segments are two-dimensional .
The size of the page is immutable , The size of the segment can be changed dynamically .
Paging is mainly used to realize virtual memory , To get more address space ; Segmentation is mainly to make programs and data can be divided into logically independent address spaces and help to share and protect . What is swap space ？
The operating system takes physical memory (physical RAM) Small memory divided into blocks , Each block of memory is called a page (page). When memory resources are low ,Linux Transfer the contents of some pages to a space on the hard disk , To free up memory space . The space on the hard disk is called swap space (swap space), And this process is called exchange (swapping). The total capacity of physical memory and swap space is the available capacity of virtual memory .

purpose ：

When physical memory is low, some pages that are not commonly used can be swapped out , To the system .
Many memory pages are used to initialize when the program starts , And then you don't need to , It can be exchanged .
What are page replacement algorithms ？
While the program is running , If the page to be accessed is not in memory , A page break occurs to call the page into memory . At this time, if there is no free space in memory , The system must transfer a page from memory to the disk swap area to make room .

Including the following algorithms ：

The best algorithm ： The selected page will not be accessed for the longest time , It is usually guaranteed to get the lowest page missing rate . This is a theoretical algorithm , Because it's impossible to know how long a page will not be visited anymore .

fifo ： Choose to change out the page is the first page to enter . The algorithm will be those often visited pages are also replaced , Thus, the page missing rate will increase .

LRU： I don't know what pages to use in the future , But you can know how pages used to be used in the past .LRU Swap out the most recently unused pages . In order to achieve LRU, Need to maintain a linked list of all pages in memory . When a page is visited , Move this page to the list header . In this way, you can ensure that the page at the end of the linked list has not been visited for the longest time . Because every visit needs to update the linked list , So this way LRU The price is high .

Clock algorithm ： The clock algorithm uses a ring linked list to connect pages , Use a pointer to the oldest page . It makes a mark on each page of the entire circular list , If the sign is 0, So it won't be replaced for the time being , Then the clock algorithm traverses the whole loop , Encountered mark as 1 Replace it , Otherwise it will be marked as 0 The mark of is 1.