P3L2 Memory Management - Page Table Size

Question 1

In a 32-bit architecture, how many different addresses into physical memory can you have?

Answer 1

Since the address can have 32 bits, you can have up to 2^32 different addresses.

Question 2

In a 32-bit architecture, with page size 4K, calculate the number of VPNs.

i.e how many entries would you need in the page table?

Answer 2

1. 2^32 different addresses.
2. Divide by blocks of 4K, 4k is 2^12
3. So ..2^32/2^12 —-> 2^20 entries

Question 3

In a 64-bit architecture, with page size 4K, where each page table entry is 64 bits (8 bytes), calculate the total size of the page table

Answer 3

1. 2^64 different addresses.
2. Divide by blocks of 4K (2*2*2^10), 4k is 2^12
3. So ..2^64/2^12 —-> 2^52 entries
4. Multiply by size of entry —> 8* 2^52 bytes —> 2^55 or 2^5 PB,
5. That’s 32 PB !!

Question 4

In a 32-bit architecture, with page size 4K, where each page table entry is 32 bits (4 bytes), calculate the total size of the page table

Answer 4

1. 2^32 different addresses.
2. Divide by blocks of 4K, 4k is 2^12
3. So ..2^32/2^12 —-> 2^20 entries
4. Multiply by size of entry —> 4* 2^20 bytes —> 2 ^22 or 4MB

Question 5

Review for quick calculations:

Kb is 2^____

Mb is 2^____

Gb is 2^_____

Tera byte is 2^____

Peta byte is 2^____

Answer 5

KB - 2^10

MB - 2^20

GB - 2^30

TB - 2^40

PB - 2^50

Question 6

Describe Hierarchical page tables. How do they use less memory?

Answer 6

The outer level is referred to as a page table directory. Its elements are not pointers to individual page frames, but rather pointers to page tables themselves.

The inner level has proper page tables that actually to point to page frames in physical memory. Their entries have the page frame number and all the protection bits for the physical addresses that are represented by the corresponding virtual addresses.

The internal page tables exist only for those virtual memory regions that are actually valid. Any holes in the virtual memory space will result in lack of internal page tables.

Question 7

Hierarchical page table

If a process requests more memory to be allocated to it via malloc the OS will check and potentially create another ________________ for the process, adding a new entry in the _______________________.

Answer 7

If a process requests more memory to be allocated to it via malloc the OS will check and potentially create another page table for the process, adding a new entry in the page table directory.

Question 8

Virtual address with 2 layer hierarchical page table

1. The first portion indexes into the __________________ to get the page table
2. The second portion indexes into the _____________ to get the PFN.
3. The last part of the logical address is still the ___________, which is used to actually index into the physical page frame.

Answer 8

Virtual address with 2 layer page table

1. The first portion indexes into the page table directory to get the page table
2. The second portion indexes into the page table to get the PFN.
3. The last part of the logical address is still the offset, which is used to actually index into the physical page frame.

Question 9

What is the advantage of adding more levels to a hierarchical page table?

Answer 9

As we add more levels, the internal page tables/directories end up covering smaller regions of the virtual address space.

As a result, it is more likely that the virtual address space will have gaps that will match that granularity, and we will be able to reduce the size of the page table as a result.

Question 10

What is the disadvantage of adding more levels to the hierarchical page table?

Answer 10

More memory accesses required for translation, since we will have to access more page table components before actually accessing the physical memory. Therefore, the translation latency will be increased.

Question 11

Multi-level page table quiz

A process with 12 bit architecture has an address space where only the first 2Kb and the last 1Kb is used.

1. Given 6 bits for the page number, how many entries are there in the single level page table?
2. Given 2 bits for the directory table and 4 bits for the inner page table, and considering the sparse usage:
   
   • How many inner page tables are needed?
   • How many inner page table entries are needed?

Answer 11

1. 2^6 –> 64 entries
2. Given 2 bits for the directory table and 4 bits for the inner page table, and considering the sparse usage:
   
   • 3 inner tables
   • 3 * 2^4 —> 3*16 = 48 total entries

Question 12

In a four-level page table, we will need to perform _____ memory accesses:

• Need to perform ______ accesses to navigate through the page table entries, and ____ access to reach the physical memory.

Answer 12

In a four-level page table, we will need to perform __5___ memory accesses.

• Need to perform ___4___ accesses to navigate through the page table entries, and __1__ access to reach the physical memory.

Question 13

In most architectures, the MMU integrates a hardware _______ to store address translations.

This cache is called the_________________________________

If we have a TLB miss, we still need to perform the multi-level page ____________.

Even a small number of addresses cached in TLB can result in a ______ TLB hit rate because we usually have ___________ and ________ locality in memory references.

Answer 13

In most architectures, the MMU integrates a hardware cache to store address translations and by-pass multi-level page table navigation.

This cache is called the translation lookaside buffer (TLB).

If we have a TLB miss, we still need to perform the multi-level page navigation /lookups

Even a small number of addresses cached in TLB can result in a high TLB hit rate because we usually have a high temporal and spatial locality in memory references.

Question 14

True or False?

• On modern x86 platforms, a 64-entry data TLB and 128-entry instruction TLB per core is enough to reduce multi-level page lookup latency.
• A 2nd level TLB shared accross cores can be even smaller.

Answer 14

• TRUE: On modern x86 platforms, there is a 64-entry data TLB and 128-entry instruction TLB per core,
• FALSE: as well as a shared 512-entry shared second-level TLB.

Question 15

True or False?

The type of address translation that is possible on a particular platform is determined by the operaing system’s segmentation algorithm.

Answer 15

FALSE: The type of address translation that is possible on a particular platform is determined by the hardware.

• Intel x86_32 platforms support segmentation and paging.
• Linux supports up to 8K segments per process and another 8K global segments.
• Intel x86_64 platforms support segmentation for backward compatibility, but the default mode is to use just paging.

Question 16

Inverted page tables are managed on a _____________ basis.

(As opposed to regular page tables which are managed on a __________ basis)

Each entry in the inverted page table points to ___________________

Answer 16

Inverted page tables are managed on a system-wide basis.

(as opposed to regular page tables which are managed on a per-process basis.

Each entry in the inverted page table points to a frame in main memory

Question 17

Each process has its own page table, so the total amount of virtual memory “available” in the system is proportional to the amount of _________________ times _______________ currently in the system.

This is the basis of the reason for ____________________.

Answer 17

Each process has its own page table, so the total amount of virtual memory “available” in the system is proportional to the amount of physical memory times the number of processes currently in the system.

This is the basis of the reason for inverted page tables

Question 18

The memory address in an inverted page table contains the __________ of the process attempting the memory address, as well as the __________ and the ________.

A _________ search of the inverted page table is performed. The index found is the _________________________________

That index combined with the offset serves to reference the exact physical address.

Answer 18

The memory address in an inverted page table contains the process id (PID) of the process attempting the memory address, as well as the virtual address and the offset.

A linear search of the inverted page table is performed. The index found is the frame number in physical memory.

That index combined with the offset serves to reference the exact physical address.

Question 19

The size of the memory page, or frame, is determined by ___________________________________

Answer 19

The size of the memory page, or frame, is determined by the number of bits in the offset.

For example, if we have a 10-bit offset, our page size is 2^10 bytes, or 1KB. A 12-bit offset means we have a page size of 4KB.

Question 20

1. What’s one benefit of larger page sizes?
2. What’s the downside of larger page sizes?

Answer 20

1. Larger pages means fewer page table entries, smaller page tables, and more TLB hits.
2. The downside of the larger pages: If a large memory page is not densely populated, there will be larger unused gaps within the page itself, which will leads to wasted memory in pages, also known as internal fragmentation.

Question 21

For a single-level page table, 12-bit architecture, what is the number of entries in the page table if ….

1. page size is 32 bytes?
2. page size is 512 bytes?

Answer 21

12-bit architecture …

1. page size is 32 bytes? 2^12 / 2^5 —> 2^7 = 128 entries
2. page size is 512 bytes? 2^12 / 2^9 —> 2^3 = 8 entries