17. Memory partition and paging

【README】

1. The content of this paper is summarized from B standing 《 operating system - Li Zhijun, teacher of Harbin Institute of technology 》, The content is great , Wall crack recommendation ;

2. The program uses memory 3 A step ：

• step 1： Divide the program into segments , Including code snippets , Data segment ; This is what compilation should do ;
• step 2： Find a free memory in memory （ Or free partition ）;
• step 3： Once the free partition is found , Just read the segment contents of the program on the disk into the free partition ; In the process of reading , Need to put LDT Initialize well ,LDT The mapping relationship between segment sequence number and segment base address is stored ;

---

【1】 Memory partition

1） Memory partition ： How to divide memory , In order to load each segment of the program into the corresponding memory partition ;
simply , Memory partition refers to a segment divided to store program segments （ Or code snippets cs, Or data segment ds） Of memory space ;

【1.1】 Fixed partition and variable partition

1） Fixed partition
Equal division , During the initialization of the operating system, the memory is divided into k Zones ;
But the length of the segment varies , The fixed partition cannot meet the variable segment length Business scenario of ;

 

---

【1.2】 Variable partition management

1） Core data structure

• Free partition table ： Store free memory partition data （ Or the memory space list after segment release ）;
• Partition table assigned ： Record information of used memory partition ;
• Be careful ： Zone information Just record Partition base address and length These two kinds of information ;

2） Request to allocate memory

【 The illustration 】

• Currently, the free memory address space is 250K~500K;
• And paragraph 3 Memory request allocation 100K, Then put 250K~350K Assign to this paragraph 3（seg3）; And add a new allocated partition table record ;

3） Free memory
【 example 】 paragraph 2 No longer need , Release segment 2 Of memory
At the same time, update the released memory to the space partition table , Remove segments from the allocated partition table 2 The record of ;

4） Apply again
At this time, the free partition table is as follows ：

Memory partition number	Base address	length
1	350K	150K
2	200K	50K

---

【1.3】 Memory partition allocation algorithm

Memory request allocation 40K, And partition 1 Yes 150K, Partition 2 Yes 50K, That should allocate partitions 1 Or partition 2 Give this request ？

• First, adapt ：(350, 150), Select the first partition in the free partition table with enough partition space to allocate ; Free partition table query is fast enough ;
• Best fit ：(200, 50), Less memory waste , But the free partition size will be smaller and smaller , There are many memory fragments after segmentation ;
• Worst fit ：(350, 150), Choose the largest partition to allocate , A lot of memory space is wasted , But the free partition size is relatively uniform , Less memory fragmentation ;

 

 
【 example 】 Which memory partition allocation algorithm is the best

---

【2】 paging

【2.1】 Memory fragmentation problem

0） problem ： Caused by memory partition Memory fragmentation problem

• resolvent ： Introduce paging Solve the problem of memory fragmentation caused by memory partitioning ;
• The actual physical memory allocation is Use paging instead of partitioning ; （ Add ： Virtual memory is partitioned or allocated ）

 【 The illustration 】 Memory fragmentation problem ：

• As shown in the figure above , The application size is 160K Of memory space , In the free partition table 2 All partitions are smaller than 160K And they are not contiguous memory address spaces , Therefore, it is impossible to allocate directly 160K Of memory space （ You need to merge free partitions first , Gather the pieces together ）, Even if the total memory size is 200K（ Greater than 160K）;

1） Memory fragments ：

• The total available memory size is larger than the requested memory size , But memory partitions are not continuous , And each partition is smaller than the application size , The memory request failed ;

2） resolvent ：

• Memory crunch ; In short , Merge the white partitions , Color partitions are merged at once , This requires copying the content ;

3） Problems caused by memory compression （ Memory compression takes time and effort ）：

• Need to modify the segment base address LDT, Very trouble ;
• In the process of memory compression , The upper user application cannot execute , Because multiple segments of the program are copying content to the new memory space , The segment base address needs cascade modification ;
• Memory compression takes a long time , It is easy to cause the machine to fake death ;

Summary ： Memory compression is not feasible to solve memory fragmentation ; This leads to memory paging to solve the problem of memory fragmentation ;

---

【2.2】 paging

1） Definition ： When the operating system is initialized , The physical memory space is divided into multiple pages , Each page takes 4K Memory size ;
When processing segment memory requests , Allocate memory to segments on a page by page basis , The following table ：

                                                                 surface 2 Memory paging table

Physical memory page number （ Page frame number ）	paragraph	page
7	paragraph 0	page 3
6	paragraph 0	page 0
5（ Free page ）
4（ Free page ）
3	paragraph 0	page 2
2（ Free page ）
1	paragraph 0	page 1
0（ Free page ）

 

 2） Advantages of memory paging ：

• advantage 1： There is no memory fragmentation , Because the free pages in the middle can be allocated to other processes ;
• advantage 2： Less memory waste ： One segment is wasted at most 1 page , That is, one segment is wasted at most 4K（ A segment consists of multiple pages ）;

【 Summary 】

• Physical memory is divided and allocated by paging , Reduced memory waste , Avoid memory fragmentation ;
• Users want to divide the program into multiple segments ;
• Sum up , The operating system needs to support both segmentation and paging to partition and allocate memory ;

---

【 example 】 Memory allocation in pages

 【 problem 】jmp 40 To which page ?

• Allocation of memory pages , Record through page table , And each process has a page table ; Page table register CR3; The page table base address is stored in the process PCB;  

【 example 】mov [0x2240], %eax  

• step 1：0x2240 Divide 4K, That is, move right 12 position , Get page number as 0x02, offset 0x240;
• step 2： By page number 2 Find the leaf frame number 3;
• step 3： Get the physical address 0x3240 ;（3 multiply 4K,3 Move left 12 Bit gets the base address 0x3000）;
• step 4： Page box 3 The base address of is 0x3000, offset 0x240, So the physical address is 0x3000 + 0x240 obtain 0x3240 ;
• Add ： Put the logical address 0x2240 according to CR3 Stored page table base address , It can be translated into physical address 0x3240, This memory address translation process is performed by MMU Accomplished ;

【 Summary 】

• A program consists of multiple segments ;
• The contents of each segment are scattered and stored in multiple pages in memory ; Each segment is not stored directly in memory （ That will cause memory fragmentation and waste ）;
• In order to realize relocation during program execution （ Find the segment base address plus the offset address to get the physical memory address ）, You need to establish a page table to store the mapping relationship between page number and page frame number , And finding the page frame number can calculate the memory page base address ;
• Because the size of each page 4K, Multiply the page frame number by 4K Get the page base address ;