Multiple-level-Paging

 1級分頁

由於我們在每個虛擬地址空間中都有2 ^ 20頁，並且每個頁表條目使用8個字節，因此頁表的大小將為2 ^ 20 * 2 ^ 3 = 2 ^ 23。這是進程自身內存空間的1/512。 （8 MB）

2級分頁

該地址將被劃分為10 | 10 | 12，因為我們希望頁面表頁面適合一頁，並且我們還希望將位大致相等地劃分。

由於該進程的大小為4GB = 2 ^ 32 B，因此我認為這意味著該進程訪問的所有不同頁面的總大小為2 ^ 32B。因此，該進程訪問2 ^ 32/2 ^ 12 = 2 ^ 20頁。然後，頁表的最底層包含2 ^ 20個引用。我們知道頁表的每個底層塊的大小為2 ^ 10個條目。因此，我們需要2 ^ 20/2 ^ 10 = 2 ^ 10的這些底層塊。

頁表的總大小為：（〜8.4M）

//外部頁表的大小//內部頁的總大小

1 * 2 ^ 10 * 3 + 2 ^ 10 * 2 ^ 10 * 3 = 2 ^ 10 *（3+ 3 * 2 ^ 10 ^ 3）

3級分頁

對於三級分頁，我們可以按以下方式劃分地址：

7 | 7 | 6 | 12

再次使用與上述相同的推理，我們需要2 ^ 20/2 ^ 6 = 2 ^ 14 3級頁表塊。每個2級頁面表塊引用2 ^ 7 3級頁面表塊。所以我們需要2 ^ 14/2 ^ 7 = 2 ^ 7 2級表。當然，還有一張1級桌子。

頁表的總大小為：

//外部頁表的大小//級別2表的總大小//最內部表的總大小

1 * 2 ^ 7 * 3 2 ^ 8 * 2 ^ 7 * 3 2 ^ 14 * 2 ^ 6 * 3〜3MB

顯而易見，一級，二級分頁需要大致相等的空間。 3級分頁比其他頁面少得多的空間。由於內存訪問的成本，為此過程選擇3級分頁方案更加合乎邏輯。

 

 

1 Level Paging
Since we have 2^20 pages in each virtual address space, and we use 8 bytes per page table entry, the size of the page table will be 2^20 * 2^3 = 2^23. This is 1/512 of the process' own memory space. (8 MB)

2 Level Paging
The address would be divided up as 10 | 10 | 12 since we want page table pages to fit into one page and we also want to divide the bits roughly equally.

Since the process' size is 4GB = 2^32 B, I assume what this means is that the total size of all the distinct pages that the process accesses is 2^32 B. Hence, this process accesses 2^32 / 2^12 = 2^20 pages. The bottom level of the page table then holds 2^20 references. We know the size of each bottom level chunk of the page table is 2^10 entries. So we need 2^20 / 2^10 = 2^10 of those bottom level chunks.

The total size of the page table is then: (~8.4M)

//size of the outer page table	//total size of the inner pages
1 * 2^10 * 3	+    2^10 * 2^10 * 3	=   2^10 * (3+ 3*2^10^3)

3 Level Paging
For 3 level paging we can divide up the address as follows:
7 | 7 | 6 | 12

Again using the same reasoning as above we need 2^20/2^6 = 2^14 level 3 page table chunks. Each level 2 page table chunk references 2^7 level 3 page table chunks. So we need 2^14/2^7 = 2^7 level-2 tables. And, of course, one level-1 table.

The total size of the page table is then:

//size of the outer page table	//total size of the level 2 tables	//total size of innermost tables
1 * 2^7 *3	2^8 * 2^7 *3	2^14 * 2^ 6* 3	~3MB

As easily seen, 1-level、2-level paging require roughly equal space. 3-level paging is much less space than others. Due to the cost of memory accesses, choosing a 3 level paging scheme for this process is much more logical.