当前位置:网站首页>18. Multi level page table and fast table
18. Multi level page table and fast table
2022-07-06 06:51:00 【PacosonSWJTU】
【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 ;
边栏推荐
- Pymongo gets a list of data
- 基于购买行为数据对超市顾客进行市场细分(RFM模型)
- PCL实现选框裁剪点云
- Market segmentation of supermarket customers based on purchase behavior data (RFM model)
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- Traffic encryption of red blue confrontation (OpenSSL encrypted transmission, MSF traffic encryption, CS modifying profile for traffic encryption)
- [Yu Yue education] Dunhuang Literature and art reference materials of Zhejiang Normal University
- 简单描述 MySQL 中,索引,主键,唯一索引,联合索引 的区别,对数据库的性能有什么影响(从读写两方面)
- 【服务器数据恢复】IBM服务器raid5两块硬盘离线数据恢复案例
- Bitcoinwin (BCW): 借贷平台Celsius隐瞒亏损3.5万枚ETH 或资不抵债
猜你喜欢
Office doc add in - Online CS
What are the commonly used English words and sentences about COVID-19?
My seven years with NLP
Attributeerror: can 't get attribute' sppf 'on < module' models. Common 'from' / home / yolov5 / Models / comm
It is necessary to understand these characteristics in translating subtitles of film and television dramas
(practice C language every day) reverse linked list II
When my colleague went to the bathroom, I helped my product sister easily complete the BI data product and got a milk tea reward
Bitcoinwin (BCW): 借贷平台Celsius隐瞒亏损3.5万枚ETH 或资不抵债
Reflex WMS medium level series 3: display shipped replaceable groups
接口自动化测试实践指导(上):接口自动化需要做哪些准备工作
随机推荐
Wish Dragon Boat Festival is happy
UNIPRO Gantt chart "first experience": multi scene exploration behind attention to details
电子书-CHM-上线CS
Brief introduction to the curriculum differences of colleges and universities at different levels of machine human major -ros1/ros2-
Call, apply, bind rewrite, easy to understand with comments
librosa音频处理教程
Phishing & filename inversion & Office remote template
The registration password of day 239/300 is 8~14 alphanumeric and punctuation, and at least 2 checks are included
一文读懂简单查询代价估算
Automated test environment configuration
万丈高楼平地起,每个API皆根基
Use shortcut LNK online CS
Day 248/300 thoughts on how graduates find jobs
Machine learning plant leaf recognition
19.段页结合的实际内存管理
成功解决TypeError: data type ‘category‘ not understood
自动化测试环境配置
中青看点阅读新闻
Fedora/REHL 安装 semanage
hydra常用命令