Statement ： Most of the screenshots come from the Wangdao postgraduate entrance examination operating system , Some drawings have been marked with the source , Invasion and deletion

1 Memory allocation and recycling

process 3 Where should it be assigned ? How to allocate ?
The following figure is from the Wangdao postgraduate entrance examination operating system

1.1 Continuous distribution

Continuous distribution ： The user process must be allocated a contiguous memory space

1.1.1 Single continuous distribution

The user area stores user process related data
There can only be one user program in memory , This program monopolizes the entire user area

The following figure is from the Wangdao postgraduate entrance examination operating system

1.1.2 Fixed partition allocation

In early multiprogramming systems , The whole user space is divided into several fixed size partitions , Load only one job per partition
The following figure is from the Wangdao postgraduate entrance examination operating system

1.1.3 Dynamic partition allocation

Memory partitions are not pre partitioned , When the process loads memory , Dynamically establish partitions according to the process size , Make the size of the partition equal to the size of the process

1. What kind of data structure should the system use to record memory usage
Record which addresses are occupied ？ Which are not occupied ？

The following figure is from the Wangdao postgraduate entrance examination operating system

（1） Free partition table

（2） Free partition chain

2. When many free partitions can meet the requirements , Which partition should be selected for allocation ？
Using dynamic partition allocation algorithm

Common dynamic partition allocation algorithms :

1. First adaptation algorithm ( Find the most suitable free partition from beginning to end )
The basic idea : Find the free partition table / chain , Start at the low address every time , Find the first free partition that meets the size , That is, the partition size required by the process to enter memory ≤ The size of a free partition
2. Neighborhood adaptation algorithm ( Each time you start searching from where the last search ended )
The first adaptation algorithm starts from the low address every time ( Free partition table / The head of the chain / Chain head ) Start looking for , Too expensive
The basic idea : Each time the memory is allocated, the free partition table is searched from the end of the last search / chain , Find the first free partition that meets the size
3. Best fit algorithm ( Give priority to smaller free partitions , Keep more large partitions )
The basic idea : First find and use the smallest free partition that can satisfy the process
4. Worst fit algorithm ( Give priority to larger free partitions , Prevent too small unusable fragments )
Solve the problem that too many external fragments will be generated in the best adaptation algorithm , Because the small partition used first , But this small partition may not be used up
The basic idea : First find and use the largest free partition that can satisfy the process

3. How to perform partition recycling ？

Directly modify the partition size and starting address in the free partition table
The location of the process is different , The situation after recycling is also different
It may also cause multiple partitions to merge , The number of partitions decreases , You need to delete the merged original partition
It may also cause partitions to increase

External debris : Some free areas in memory are too small to be used
The problem of external fragmentation can be solved through compact technology , That is to move the processes together

Internal fragmentation : Some parts of the memory area allocated to a process are not used

1.2 Discontinuous distribution

Discontinuous distribution ： Distributed memory space can be allocated for user processes

1.2.1 Segment storage management

In segmented storage management , The address space of the job is divided into several segments （ The size is not necessarily equal ）, Each segment defines a set of logical information – Excerpt from ： Basic segmented storage management

Segment is the logical unit of information . The main purpose of segmentation is to better meet the needs of users . Segments are visible to the user , When programming, the user needs to explicitly give the segment name
The length of the segment is not fixed, which is determined by the program written by the user

1.2.1.1 Address change mechanism

Be careful ： The address in the segment should be judged whether it is out of bounds , Because the sizes of segments are different , It is impossible to know whether it is beyond the boundary without judgment . The size of pages in paging is fixed , There is no need to judge whether the address on the page is out of bounds

1.2.1.2 Segment sharing

Code that cannot be modified is called Pure code or Reentrant code （ Not a critical resource ） Such code can be shared , Data that cannot be modified can also be shared . Code and data that can be modified cannot be shared

Why paging cannot be shared ？
Because if a part of the page is allowed to be shared , And the other part is not allowed to be shared , There will be contradictions , Whether this page can be shared
And the data in the shared segment can all be shared

1.2.2 Paging storage management

Paging storage management is a process Logical address space Divided into several equal Pieces of , Called a page or page
hold Memory space Divided into several storage blocks of the same size as the page , be called ( Physics ) Block or page box (frame)
When allocating memory for a process , Several pages in the process are loaded into multiple physical blocks that can not be adjacent to each other in a block unit – Excerpt from ： Basic paging storage management

Page is the physical unit of information . The main purpose of paging is to achieve discrete allocation , Improve memory utilization . Paging is just a system management need , It's all system behavior , Invisible to users
The size of the page is fixed and determined by the system

Logical address A Conversion to physical address

1. determine A Corresponding page number P
   ( Page number = Logical address / Page length ) The result takes the integral part , The page length in the above figure is 4KB
2. find P The starting address of page number in memory
   ( The first P The starting address of memory block No = P × Memory block size )
3. Logical address A Corresponding physical address = The starting address of the memory block + Page offset W
   ( Page offset = Logical address % Page length ) The remainder of the result

1.2.2.1 Basic address transformation mechanism

The hardware mechanism that realizes the conversion from logical address to physical address through page table
Two visits are required

1.2.2.2 Address transformation mechanism with fast table

Watch it (TLB) It's a kind of cache ( Hardware ), Used to store recently accessed page table entries ( Page number + Memory block number ) Copy of , Speed up address translation .( Page table is slow table , In memory , Therefore, accessing the page table requires accessing memory )

The fast table only stores a partial copy of the page table entry

The following picture is from Kobayashi coding

Situation 1 ：TLB Not hit , Need to access page table
If the page number to be queried is TLB Miss in , Then the next step is to query the page table , Get the corresponding memory block number after hitting in the page table , Then the starting address of the corresponding memory block + The physical address is obtained by the in page offset , Finally, the corresponding memory unit is accessed by the physical address （TLB Not hit , You need to visit twice ）

Situation two ：TLB hit , No need to access the page table
If the page number to be queried is TLB Hit in the middle , Get the corresponding memory block number , Then the starting address of the corresponding memory block + The physical address is obtained by the in page offset , Finally, the corresponding memory unit is accessed by the physical address （TLB hit , Only one access is needed ）

1.2.2.3 Two level page table

Problems with single level page tables
Question 1 ： Page tables must be stored continuously , When the page table is large , Need to occupy a lot of continuous page boxes
（K No. page corresponds to the storage location of page table items = Page table start address +K*4KB,K You must fetch consecutively to find any memory block , Therefore, the page table must be stored continuously ）

Question two ： There is no need to keep the entire page table in memory , Because you may only need to visit a few pages for a period of time （ Locality principle ）
You can call pages into memory only when you need them （ Virtual storage technology ）, You can add a flag bit to the page table item , Represents whether a page has been transferred into memory . If the page you want to access is not in memory , Then Missing pages interruption （ It belongs to internal interruption ）, Then transfer the target page from external memory to memory

Two level page table
The following picture is from Kobayashi coding

31~22 All in all 10bit, Every bit There are two states , therefore 10 A total of $2^{10}$ States

Briefly describe the process
for example ： Through the memory block number in the first level page table 3, Found the entire secondary page table 0#（ The second... In memory 3 Memory blocks ）, Pass the first 3 The starting address of memory blocks + An offset gets a memory block number , Find the memory block to access finally , Then get the starting address of the memory block + Page offset , Finally, get the physical address of the memory unit to be accessed

Multi level page table

1.2.3 Segment page storage management

1. First, divide the program into logical segments , Is the former ⾯ The segmentation mechanism mentioned ;
2. Then divide each segment into multiple ⻚, That is to say, the continuous space divided by sections , Then divide into fixed ⼤⼩ Of ⻚;– Excerpt from ： Kobayashi coding

The following picture is from Kobayashi coding

1.2.4 Comparison of segmentation and paging