Calculating page table entry size

How many page table entries are required given a virtual address size and page size?

I was confronted with this question when reading Computer Systems from a programmer’s perspective on virtual memory management (VMM) which forced me to reread the chapter, over and over. It wasn’t until I forced myself to close the book, step away from the problem for a day, was I able to fully grasp what was being asked:

Page table entries problem
Page table entries problem

Let’s narrow the scope and focus on a single instance, where n is 16 and P is 4K;  the question can be easily rephrased into something that makes more sense (to me): “How many 4k pages can fit into 16 bit memory address”?

First, how any bits are required, for a 4K block size, to represent a single page? Well, 212 is 4096 so … that’s sufficient. Therefore, we can rephrase the abstract question that we can solve mathematically: “How many 12 bit pages can fit into a 16 bit virtual address size?”

So, the problem now boils down simple division— 216 / 212,which can be expressed as 216-12: 24, which is sixteen (16). That’s 16 page table entries that required for a virtual address of size of 16 combined with a page size of 4k.

The same approach can be taken for all the remaining practice problems. Convert the page (e.g. 4k, 8k) size into bits and divide that into the virtual address size (e.g. 16, 32)