18. Multi level page table and fast table

【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. Operating system memory management ： Paging mechanism + Multi level page table + Fast watch to achieve ;

---

【0】 Paging problem

1） Paging problem （ Large page table ）： To improve memory utilization , The page should be small , The page is smaller , There are more page entries , The page table is big ;（ Page is 4K, Each segment wastes at most 4K）

• problem ： A large page table is not conducive to searching , And the large page table takes up too much memory ;

【 example 】 Page table structure and large page table

Page number	Page frame number	Protect
0	5	R
1	1	R/W
2	3	R/W
3	6	R

•   Such as total memory size 2^32=4G, The size of each page 4K, Then the number of page table items =4G/4K=1M namely 100 Ten thousand page table items ;
• And each page table item occupies 4 Bytes , So it contains 100 The total memory occupied by the page table with 10000 page table entries is 4M;
• And if the system executes concurrently 10 A process , Each process page entry 4M, So we need to 40M; If the system is concurrent 100 A process , You need to 400M Storage page table , This leads to low memory utilization ;

---

【1】 The solution of large page table 1（ Just trying ）： Store only the pages you need

1） The page table only stores the pages used （ Page table numbers are discontinuous ）

actually , Most logical addresses don't use ;
Delete the unused logical page number from the page table , This reduces the page table size of the current process ; namely , Only the logical pages used have page table entries ;

 2） Only the logical pages used have page table entries
Because the unused logical page number is deleted , So page numbers are discontinuous （ Page number 0 1 3 ）. as follows .

Page number	Page frame number	Protect
0	5	R
1	1	R/W
3	3	R

When calculating the page base address , You need to find the page frame number from the page table according to the page number , Then calculate the physical memory base address of the page .
3） How to find the page frame number according to the page number ？

• In order to find , Half the search is slow ;
• For example, the total memory size is 4M, The number of page table items is 4M/4K=1K; Finding in order requires 1K Time , It takes log(2^10)=10 Time ; That is to say, every instruction needs 10 Second visit and deposit ,1 Secondary main memory access costs about 200ns, be 10 Second need 2us; This will seriously affect the speed of instruction execution ;

【 Summary 】

• Page numbers must be continuous , In this way, you can immediately locate the page table item . Such as page table item base address +3 You can get the page number 3 Page table entry for （ Instead of sequential or half search ）;
• This goes back to the initial problem , namely 32 Bit address space + 4K page + Page numbers must be continuous => Led to 2^20 Page table items => As a result, large page tables occupy too much memory , wasteful ;

therefore resolvent 1 The attempt in is a failure .

  further , We conclude that the problem to be solved is ：

• Page numbers are continuous , And the page table takes up less memory ;
• Think by analogy with the chapter catalogue and section catalogue of the book ;

---

【2】 The solution of large page table 2（ Try ）： Multi level page table

【2.1】 Multi level page table

From single level page table to multi-level page table ;
That is, multi-level page table , Page table of contents （ Chapter ）+ A page table （ section ）;

1） Specific allocation of multi-level page tables
The logical address structure in the instruction is as follows ：

10 bits	10 bits	12 bits
Page catalog number	Page number	Offset Offset

• step 1： Query the base address of the page table from the page directory table according to the page directory number ;
• step 2： From page table according to page number （ Determine through the base address of the page table ） The page frame number is found in （ Physical memory page number ）;
• step 3： The physical memory page base address can be calculated according to the page frame number （ Specifically, the page frame number times 4K）, Use the page base address plus the logical address offset to get the physical memory address ;

because Page catalog number , Page numbers are continuous , Therefore, the query time complexity of page directory number and page number is O(1);

2） Address translation steps using multi-level paging  

【 explain 】 Illustration ：

• explain 1）1 Page catalog entries （ Chapter ） Point to 1k Memory pages , Per memory page 4K, therefore 1 Page directory entries point to 4M Memory ; therefore 1K Page directory entries can be mapped with a capacity of 4G Of memory space ;
• explain 2） Page table of contents , The process uses 3 Page catalog entries , That is to use 4G In memory 12M Memory ; The total memory size occupied by page directory table and page table =1K*4 + 3 * 1K*4 = 16K;（ Each page directory entry and each page table entry occupy 4 Bytes , because 32 Bit address space ）
• explain 3） It should be noted that , If memory uses single level paging , need 4G/4K=1M Page table items , Each page table item occupies 4 Bytes , Then the memory occupied by the page table under single level paging is 4M;

【 Summary 】

• In total memory size 4G On the basis of , Occupy 12M Memory program , When using multi-level paging, the page table occupies 16K Far less than Single level paging 4M;

 

 

---

【2.2】 Advantages and disadvantages of multi-level page table

1） Advantages of multi-level page table ：

• Multi level page table not only ensures the continuity of page table items , It makes the search very fast （ Time complexity O(1)）;
• also Ensure that there are fewer page tables stored in memory , Reduced memory waste , Improved memory utilization ;

2） Disadvantages of multi-level page table

• Multi level page tables increase the speed of memory access , special 64 Bit system （ because 64 The multi-level page table of bit system has 5,6 level ）;  
• Multi level page table , Every level of increase , The number of deposit visits will increase 1; therefore 64 The number of multi-level page table accesses of the bit system is about 5,6 Time ;
• The more levels of the multi-level page table , The more you visit , The less efficient （ More series , Multi level catalogue of analogy books ）, This will result in inefficient instruction execution ;

For the shortcomings of multi-level page tables , The introduction of the fast watch ;

---

【3】 Watch it （ refer to TLB register ）

1） Watch it ：

• Also called TLB,TLB Is a set of associative fast storage , It's a register ;
• TLB, namely Translation lookaside buffer, Also known as translation fallback buffer register ;
• adopt TLB You can quickly find the physical page number of the recently used logical page mapping ;  

2）TLB Stored content （ It records the physical page number of the most recently used logical page mapping ） as follows ：

It works	Page number （ disorder ）	modify	Protect	Page frame number （ Physical page number ）
1	140	0	R	56
1	20	1	R/W	23
0	19	0	R/W	29
1	21	0	R	43

Because register access speed is fast , Can design TLB Hardware logic of registers , bring It can be accessed at one time You can query the page frame number according to the page number （ Physical page number ）, Finally get the physical address ;

 

---

【3.1】 Address translation based on fast table

1） Address translation steps based on fast table

• step 1： According to the page number of the logical address , Check once TLB Register can get the page frame number （ Physical page number ）;
• step 2： Ruo Kuai meter TLB There is no page frame number （ Not hit ）, Then query the multi-level page table , And send the query results to TLB Store as a buffer for subsequent address translation ;

Summary ： Watch it + The structure formed by the combination of multi-level page tables , Ensure the query （ Translate physical address ） Fast time , Page entries are continuous , Reduce the waste of memory resources ;

2） It also fully embodies Operating system compromise ; By putting some technologies together , Make the visit time good , Space utilization is also good ; The concrete is ：

• Multilevel page tables reduce space waste , Reduced space complexity , The visit time is ok , But I also want to improve the query speed of page table ;
• TLB It improves the query speed of page table , Reduced time complexity ;
• TLB It can make up for multi-level page tables （ special 64 Bit system ） Storage access takes time , The disadvantage of being slow ;

---

【3.2】TLB How to ensure high hit rate

1）TLB The reason why it works ： Ensure high hit rate ;

 【 explain 】 Formula description ：

• The effective access time is equal to the access time at the time of hit + The access time when it misses ;
• The symbol explanation in the effective access time formula in the above figure ：
• HitR Express shooting ;
• （1-HitR） Express Miss rate ;
• TLB Indicates the time when the register was accessed ; Usually it is 10ns （ Of course, the figure shows 20ns, Of the same order of magnitude ）
• MA Represents the actual access to memory ; Usually it is 200ns  （ The picture shows 100ns, Of the same order of magnitude ）
• You can see ： Higher hit rate , Then the access time is close to 1 Time of the first deposit ;

2） How to improve TLB shooting  

• TLB The bigger the better , but TLB Very expensive , The compromise is TLB The range of page table items that can be stored is [64,1024];

3） Why? TLB The number of stored page table items can be in 64~1024 Between ？
reason ：

• The address access of the program is local ;
• Because of the locality of access , So the program uses the fixed logical page numbers ;
• The mapping relationship between the recently accessed logical page and the physical page will be sent into TLB Storage , therefore TLB Your hit rate will be high ;
• Add ： Programs are mostly embodied in cycles , Sequential structure ;