Memory management summary

The concept of memory management

The division and management of memory by the operating system , Is the concept of memory management .·

Functions of memory management ：

1. address translation
2. Memory protection
3. Expansion of memory space
4. Allocation and recycling of memory space

1. address translation

Programmers only need to focus on Relative address , The conversion from logical address to physical address （ Address relocation ） It's done by the operating system ;

absolute loading ： The logical address and physical address of the program are the same , Only single program environment is supported （ Early single channel program ）
Static repositioning ： Convert logical address to physical address at one time when loading , Complete by the transfer procedure , Used in early multi-channel batch processing system （ Early multichannel batch processing ）
Dynamic relocation ： After the program loads the module into memory , The relative address of the loaded module is not immediately converted to the physical address , But only when the program really needs to be executed ; Allows programs to move in memory , Only change the value in the relocation register （ Modern operating system ）
The relocation register stores the starting position , The starting position + Relative address = Physical address

2. Memory protection

Ensure that all processes are in 【 In their respective storage space 】 function , Mutual interference , For example, ordinary processes cannot access the memory space of the operating system

Method 1 ： Set up Upper and lower limit registers
When the instruction of the process wants to access memory ,cpu It will be compared according to the memory address and the upper and lower limits of memory , Access is allowed only within the upper and lower memory ranges ;
Method 2 ： use Boundary address register
The bound address register contains the maximum value of the relative address , If the relative address of the loaded module does not exceed the value of the bound address register , Just add the relocation register （ Save the starting address ） Convert to physical address

3. Expansion of memory space

Using virtual technology , from 【 logically 】 Expand memory （ Virtuality , That is, expand the physical small memory into the logical large memory ）

1. Coverage technology （ history ）
Divide the user memory space into fixed area and coverage area , Always be active in the fixed area , Other parts are placed on the disk in sections according to the relationship , Call and put into the coverage area when necessary , Replace the original memory in the coverage area .
characteristic ： It breaks the restriction that all inherited information must be loaded into main memory to run
The only place where memory is updated is the coverage area
shortcoming ： Programmers are required to declare the coverage structure , Increase programming burden

2. Switching technology （ Currently in use ）
Move the waiting program from memory to auxiliary memory , Free up memory space （ Pending state ）— Swap out ;
Move the program to be run from auxiliary memory to memory — Exchange in ;
For efficiency , Need to make the execution time of each process > Exchange time
Switching technology is mainly different 【 Between processes 】 Conduct , Coverage is the same 【 In process 】 Conduct

3. Virtual technology
Specific coverage 、 The exchange technology is more advanced , Later, .
Virtual technology is 【 In process 】 Conduct ！

4. Memory allocation and recycling

4.1. Continuous distribution management mode

It refers to a whole continuous memory space occupied by user processes ;

1. Single continuous distribution
Memory is divided into system area and user area , The system area is only used by the operating system , There is only one program in the user area ！ The user program monopolizes the user area , Concurrency is not supported ！ And there are internal fragments （ The space waste caused by the program is smaller than the fixed partition size ）, No external debris ;

2. Fixed partition allocation
The user area is divided into multiple fixed size areas , Only one program is loaded per partition ; Yes Internal fragmentation , No external debris , Low utilization .

3. Dynamic partition allocation
Memory partitions are not pre partitioned , It is 【 When the program loads memory 】, Dynamically create partitions based on the size of the process , Make the partition size just fit the needs of the process ;
The size and number of partitions are variable ;
Adjacent free partitions will be merged ;
Use the free partition table 、 Free partition chain data structure to record memory usage ;
Yes External debris （ Users go out of free memory ）, Use Compact technology Come and solve , That is, the relocation register is used to move and organize the program , Process PCB Modify the starting address in and put it into the relocation register

4.1. Discontinuous distribution management

Distributed memory space is allocated for user processes ;

introduce ：
The disadvantage of continuous distribution ：
Fixed partitions are not flexible , Produce a lot of internal debris
Dynamic partition generates external fragments , Need to use compact technology to organize , But the cost of time is relatively high ;
Then I think of loading processes into non adjacent partitions , You can make full use of memory without using compact technology

1. Basic paging storage
① Divide the memory into equal small partitions, that is Page box ,
② Then divide the process into small parts according to the size of the page box — namely page ;
③ Each page of the process will be put into the page box in memory
Page management corresponds to logical address and physical address through page table , The page table records the page number + Page frame number

advantage ： The granularity of the page is small , Improved memory utilization , Reduced debris ;
shortcoming ： There is no logical relationship between pages , The process is split into fixed size pages , It is not conducive to safety and protection

Multi level page table ：
The page table needs a continuous memory to store , If the page table is too large , This is obviously unrealistic ---- Multi level page table
Split the page table into several small page tables , The size of each page table is the same ,4KB, You can put it in the page box , A top-level page table records the position of the secondary page table , The top-level page table records the page table number and the corresponding page frame number ;
The multi-level page table is a typical time to space scenario .

Watch it
The fast table can be directly understood as the cache of page memory management （Cache）
The function of the fast watch ： Speed up the conversion from virtual address to physical address
The system always compares the page number with all table items in the quick table first . If a matching page is found , Then take the block number directly from the fast table , Instead of going through the page table .

2. Basic segmented storage
Although page management improves memory utilization , But pages stored as pages are meaningless , Each segment defines a set of logical information , Such as main program MAIN, Subroutines X, Data segment D etc. ;
Segment management corresponds to logical address and physical address through segment table

Address space of the process ： According to the logical relationship of the program itself, it is divided into several segments , Each segment has a segment name , Each segment from 0 Start preparation
Memory is in segments , Each segment occupies a contiguous space in memory , But each segment can be directly non adjacent

advantage ： Segmented storage is divided by secret logic function , User programming is more convenient , High readability ;
shortcoming ： It creates external debris

piecewise 、 Comparison of paging management ：
1. Page is the physical unit of information , The purpose of paging is to realize the discrete allocation of memory , Improve memory utilization , Paging is just a system management need , Invisible to users
Segment is the logical unit of information , The purpose is to better meet the needs of users , A segment usually contains a set of information belonging to a logical block ,
Segments are visible to the user , When programming, you need to display the given segment name
2. The size of the page is fixed , The length of the segment is not fixed , Depends on user programming
3. Segmentation is easier to share and protect information than paging , If you want different processes to share a piece of memory , Sharing can be achieved by simply making the segment table entries of the process point to the same segment ; It is easy to realize security protection in sections , Just mark the segment as not allowed to access .

3. Segment page storage
introduce ：

The principle of segmented management to generate external fragments is similar to that of dynamic allocation in continuous allocation , Compact technology is also used to solve , Time is expensive

And paragraph page management first Segment by logical module , Then page each section ;
The logical address structure of the segment page system consists of segment number 、 Page number 、 Page address （ Page offset ） form

Segments are visible to the user , The programmer only needs to give the segment number and the address in the segment ; The process of dividing each segment into pages is invisible to users , The system will automatically divide the address in the segment into page number and page offset ;

The system will create a segment table for each process , Each segment table item consists of segment number 、 Page table length 、 Page frame number
In the paragraph page format , A process corresponds to a segment table , But it may correspond to multiple page tables

Virtual memory management

Characteristics of traditional storage management 、 shortcoming ：
Disposable ： Jobs must be fully loaded into memory at once before they can start running . Can cause ：
① The job is too big to be loaded into memory
② Large job runtime , Because memory cannot hold all jobs , Therefore, only a few jobs can be run , This leads to a decrease in concurrency
Residency ： Once the job is loaded into memory , will Always resides in memory , Until the end . As a matter of fact , In a period of time , You only need to access a small part of the data to operate normally , This leads to a large amount of unused data in the main stream of memory

The above shortcomings can be solved by virtual storage technology ,
The proposal of virtual technology stems from the principle of locality ：
The principle of time locality ： When a program executes an instruction , It may be executed again soon ; Some data may be accessed again soon after being accessed （ Because there are a lot of loops in the program ）
The principle of spatial locality ： The program accesses a storage unit , Soon, the storage units nearby will also be accessed ,B The application of tree in storage （ Because a lot of data is stored continuously in memory ）

Based on the principle of locality , When the program is loaded , You can put the part that the program will soon use into memory , Put the unused ones on the disk ;
When the information accessed is not in memory , The operating system transfers the required information from the disk
Under the management of the operating system , It seems to users that there is much more memory than the actual memory ---------- Virtual technology （ Time for space ）
（ Switching technology is to swap the whole process out of memory ）

Characteristics of virtual memory ：

Multiple rows and convertibility correspond to the one-time and resident nature of traditional memory management ,

The realization of Virtual Technology ：

Allow a job to be called into memory multiple times , If continuous distribution is adopted , It will be inconvenient to realize ; Therefore, the implementation of virtual memory is based on Discontinuous distribution On the basis of ;

The main difference between traditional discontinuous allocation and virtual memory implementation ：
① When the access information is not in memory , The operating system should transfer the required information from external memory to memory , And then go ahead and do it ------ Request page change function （ paragraph ）
② When there is not enough memory , The operating system switches out the unused information in the memory to the external memory ---- Page replacement function （ paragraph ）

Request paging storage management ：

Page table requesting paging storage ：
Whether the status bit mark is called into memory , Whether the modification bit mark has been modified , If it hasn't been modified, you don't need to write it back to external storage , The external storage address marks the storage address of the page in the external village , Call in and call out the pages of the process through key fields .

Page replacement algorithm ：

If there is not enough memory , You need to exchange unused information to external storage ---- Page replacement , The page replacement algorithm determines which page should be replaced
Page change in 、 Replace the disk that needs the system I/O, It's going to cost a lot , Therefore, a good page replacement algorithm should pursue better Page fault rate （ That is, the number of exchanges in and out should be as few as possible ）

Best permutation algorithm OPT：
The selected obsolete page will never be used in the future , Or pages that are no longer visited for the longest time , In this way, we can guarantee the minimum page missing rate . But at present, it is impossible to predict which of the thousands of pages in memory will not be accessed for the longest time in the future , So the algorithm can't be implemented . Generally as a measure of other permutation algorithms .

Fifo algorithm FIFO：
Always weed out the first pages in memory , That is, select the page with the longest stay time in memory to be eliminated . But the first page may also be visited frequently ;
Easy to implement , The performance of the algorithm is poor .

The most recent page replacement algorithm not used LRU：
LRU The algorithm gives each page an access field , Used to record the time of a page since it was last visited T, When a page has to be eliminated , Select one of the existing pages T The most valuable , That is, the most recent unused page to be eliminated .
Hardware is needed to implement , Good performance , Spending big , Difficult to achieve , The closest best permutation algorithm

Clock replacement algorithm CLOCK：
Clock replacement algorithm is a kind of algorithm with balanced performance and cost ,
Realization ： Connect the pages in memory into a circular queue through the connection pointer , The access bit of the page is 1 The representative has visited , The access bit of the page is 0 The representative has not visited ; When you need to weed out pages , Will scan the queue , Find the access bit 0 And change out of the page , And the access bit is 1 All of are set to 0; If it's all 1, Then the second round of scanning will encounter 0 And change out