60

I'm reading through an example of page tables and just found this:

Consider a system with a 32-bit logical address space. If the page size in such a system is 4 KB (2^12), then a page table may consist of up to 1 million entries (2^32/2^12). Assuming that each entry consists of 4 bytes, each process may need up to 4 MB of physical address space for the page table alone.

I don't really understand what this 4MB result represents. Does it represent the space the actual page table takes up?

1
  • 3
    Just for information, this line is from Operating System Concepts, Avi Silberschatz, Peter Baer Galvin, Greg Gagne - Section 8.5.1 in the 8th edition. Dec 22, 2014 at 17:43

6 Answers 6

84

Since we have a virtual address space of 2^32 and each page size is 2^12, we can store (2^32/2^12) = 2^20 pages. Since each entry into this page table has an address of size 4 bytes, then we have 2^20*4 = 4MB. So the page table takes up 4MB in memory.

3
  • 1
    Hi, thanks for explanation, i could not understand: if page size is 2^12 bytes why we are not converting it to bits like (2^12 bytes = 2 ^ 15 bits) and then calculate division 2^32 (bits) / 2^15 (bits) = 2^17 (max possible number of pages)? Why use bytes? Jun 8, 2019 at 5:13
  • 3
    @MukhtarBimurat Each address is pointing at one whole byte in memory. Individual bits are not addressable. So you are able to address 2^32 bytes. The page table is a mapping from virtual address space to physical address space. But it does not map individual bytes, but maps in chunks called pages. Pages in this example are 2^12 bytes large. Therefore your page table needs 2^32/2^12=2^20 entries to map all possible pages.
    – beesteak
    Jun 13, 2019 at 21:51
  • 1
    Also note that MB technically should be MiB, which is 2^20 bytes as opposed to 10^6 bytes. Jul 25, 2021 at 23:35
25

My explanation uses elementary building blocks that helped me to understand. Note I am leveraging @Deepak Goyal's answer above since he provided clarity:

We were given a logical 32-bit address space (i.e. We have a 32 bit computer)

Consider a system with a 32-bit logical address space

We were also told that

each page size is 4 KB

  • 1 KB (kilobyte) = 1 x 1024 bytes = 2^10 bytes
  • 4 x 1024 bytes = 2^2 x 2^10 bytes => 4 KB (i.e. 2^12 bytes)
  • The size of each page is thus 4 KB (Kilobytes NOT kilobits).

As Depaak said, we calculate the number of pages in the page table with this formula:

Num_Pages_in_PgTable = Total_Possible_Logical_Address_Entries / page size 
Num_Pages_in_PgTable =         2^32                           /    2^12
Num_Pages_in_PgTable = 2^20 (i.e. 1 million) 

The authors go on to give the case where each entry in the page table takes 4 bytes. That means that the total size of the page table in physical memory will be 4MB:

Memory_Required_Per_Page = Size_of_Page_Entry_in_bytes x Num_Pages_in_PgTable
Memory_Required_Per_Page =           4                 x     2^20
Memory_Required_Per_Page =     4 MB (Megabytes)

So yes, each process would require at least 4MB of memory to run, in increments of 4MB.

Example

Now if a professor wanted to make the question a bit more challenging than the explanation from the book, they might ask about a 64-bit computer. Let's say they want memory in bits. To solve the question, we'd follow the same process, only being sure to convert MB to Mbits.

Let's step through this example.

Givens:

  • Logical address space: 64-bit
  • Page Size: 4KB
  • Entry_Size_Per_Page: 4 bytes

Recall: A 64-bit entry can point to one of 2^64 physical page frames - Since Page size is 4 KB, then we still have 2^12 byte page sizes

  • 1 KB (kilobyte) = 1 x 1024 bytes = 2^10 bytes
  • Size of each page = 4 x 1024 bytes = 2^2 x 2^10 bytes = 2^12 bytes

How Many pages In Page Table?

`Num_Pages_in_PgTable = Total_Possible_Logical_Address_Entries / page size 
Num_Pages_in_PgTable =         2^64                            /    2^12
Num_Pages_in_PgTable =         2^52 
Num_Pages_in_PgTable =      2^2 x 2^50 
Num_Pages_in_PgTable =       4  x 2^50 `  

How Much Memory in BITS Per Page?

Memory_Required_Per_Page = Size_of_Page_Entry_in_bytes x Num_Pages_in_PgTable 
Memory_Required_Per_Page =   4 bytes x 8 bits/byte    x     2^52
Memory_Required_Per_Page =     32 bits                x   2^2 x 2^50
Memory_Required_Per_Page =     32 bits                x    4  x 2^50
Memory_Required_Per_Page =     128 Petabits

[2]: Operating System Concepts (9th Ed) - Gagne, Silberschatz, and Galvin

0
5

In 32 bit virtual address system we can have 2^32 unique address, since the page size given is 4KB = 2^12, we will need (2^32/2^12 = 2^20) entries in the page table, if each entry is 4Bytes then total size of the page table = 4 * 2^20 Bytes = 4MB

5

Suppose logical address space is 32 bit so total possible logical entries will be 2^32 and other hand suppose each page size is 4 kilobyte then size of one page is 2^22^10=2^12... now we know that no. of pages in page table is pages=total possible logical address entries/page size so pages=2^32/2^12 =2^20 Now suppose that each entry in page table takes 4 bytes then total size of page table in physical memory will be=2^22^20=2^22=4mb**

4

Since the Logical Address space is 32-bit long that means program size is 2^32 bytes i.e. 4GB. Now we have the page size of 4KB i.e.2^12 bytes.Thus the number of pages in program are 2^20.(no. of pages in program = program size/page size).Now the size of page table entry is 4 byte hence the size of page table is 2^20*4 = 4MB(size of page table = no. of pages in program * page table entry size). Hence 4MB space is required in Memory to store the page table.

2
  • 2
    "Since the Logical Address space is 32-bit long that means program size is 2^32 bytes???" Didn't you just confused bits with bytes?
    – harogaston
    Jul 8, 2015 at 0:35
  • 1
    If I am not wrong,'Logical Address space is 32-bit long' means we can store up to 2^32 numbers i.e 2^32 memory addresses and each memory address/location can store 1 byte data so in total you can store 2^32 bytes of data Sep 18, 2016 at 10:25
1

yes it represents the space the actual page table takes for one process.

if each page is 4KB -> 12 bits for offset (how?)

1 kb is 2^10 bytes => 4 kb is 4*2^10 bytes which is 2^12 => hence 12 bits for offset and the remaining 20 bits for VPN => 2^20 translations which means 2^20 pages are there which means 2^20 entries in the page table.

Hence, size of page table = number of entries in the page table * size of one entry

=> size of page table = 2^20 * 4 KB = 2^22 kB and 1 MB is 2^20 KB => 4 MB

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.