How is the page size and entries calculated for a page table?

Question

What does this statement mean with respect to an operating system?

With a 2^32 address space and 4K ( 2^12 ) page sizes, this leave 2^20 entries in the page table. At 4 bytes per entry, this amounts to a 4 MB page table, which is too large to reasonably keep in contiguous memory. ( And to swap in and out of memory with each process switch. ) Note that with 4K pages, this would take 1024 pages just to hold the page table!

Please explain how they are calculating 1024 pages at the end? What is 4 bytes per entry in this regard? What is the meaning of 4K page size? Does 4K mean 4*1024 bytes? Are they considering 4 bytes (per word) OR does 4 bytes means it has 4*1024 words with each word having some size, say 4 bytes?

Solution 1

Please explain to me how they are calculating 1024 pages at the end?

Remember that we're dealing with powers of two, so

4 MB = 4,194,304 Bytes

4 KB = 4096 Bytes

4 MB / 4 KB = 4,194,304 Bytes / 4096 Bytes = 1024 Bytes

What is 4 Bytes per entry in this regard?

You need 32 bits to reference all 2^32 address spaces. With 8 bits per Byte, 32 bits = 4 Bytes.

For example the first address is 0 and the last address is 4294967295 or (2^32 - 1).

Entry |   Page Memory Location
------------------------------------------
    1 |          0
    2 |       4096
    3 |       8192
  ... |        ...
 2^20 | 4294963200 ->  (2^32 - 1) - 4096

Each entry in the table points to 1 page somewhere out in memory. In this example lets say it starts at zero. There will be 2^20 entries and they will cover the entire span of memory addresses (2^32). Since each entry is 4096 Bytes you only need 2^20 entries to cover all of the pages.

4K means 4*1024 bytes?

Yes, it refers to each page being 4096 bytes (4*1024).

Are they considering 4 bytes (per word), OR 4 bytes means it has 4*1024 words which each word having some size say 4 bytes?

It can be smaller on 32 bit processors, but normally a word is 32 bits or 4 Bytes.

Additions Comments

When I say a page size is 4K, then it means it has 1024 entries with 4 bytes each or 1024*4 entries with 1 byte each or what else?

The page can hold anything, it's a container of data that is, in this example, 4096 Bytes. The page table holds entries that point to pages. As David stated, since the page table is stored in memory, it also is stored in pages.

Someone was saying that explanation is wrong. Correct one is: With a 2^32 address space and 4K (2^12) page sizes, this leave 2^20 pages in the table. At 4 bytes per entry, this amounts to a 4 GB page table, which is too large to reasonably keep in contiguous memory. (And to swap in and out of memory with each process switch.) Note that with 4K page sizes, this would take 1024 k pages (=1M pages) just to hold the total table! Is he correct or wrong?

He is incorrect. If the page table actually contained the data from each page then he would be correct. With 4096 byte pages and 2^20 entries, that would equal 4,294,967,296 bytes (4 GB), but the entries are only 4 bytes in size. So you multiple that with 2^20 entries to get 4,194,304 bytes (4 MB).

Solution 2

The documentation assumes these values:

2^32 = number of bytes in address space
2^12 = 4K = 4*1024 = number of bytes in one page
2^20 = 1M = 1024*1024 = number of pages
4 = number of bytes in the page table to describe one page
4M = 4*1024*1024 = total number of bytes in the page table
1024 = (4*1024*1024)/(4*1024) = number of pages in the page table

So 4 bytes is 4 bytes (the size of the entry in the page table for one page, not the size of the page itself!). Yes, 4K means 4*1024 bytes, not 4*1024 words.

All memory in use by the OS and any applications is stored in pages somewhere on the system. Since the page table is something that has to be stored in memory, it also is stored in pages.