How to calculate the size of a page in a two level paging CPU?

Question

I am having difficulties with understanding the concept of paging.

As a result I've got no idea how I can solve the following exercise - I'm lacking one more equation to solve it.

I've read a lot about paging and watched a few tutorials, but I still cannot solve paging problems easily. I'll provide some of the resources I learnt from at the bottom of this question.

---

Background:

The CPU has two level paging and the logical and physical addresses are of $34$ bits size each.

The sizes of the page table directory, the table directory and the page are equal.

The logical address $(12345678)_{16}$ has been translated to the $(ba9678)_{16}$ physical address.

What's the size of a single page?

---

My attempt:

1. The logical address can be decoded to:
   $$(00\ 0001\ 0010\ 0011\ 0100\ 0101\ 0110\ 0111\ 1000)_2$$ The physical address can be decoded to: $$(00\ 0000\ 0000\ 1011\ 1010\ 1001\ 0110\ 0111\ 1000)_2$$ So, as you can see, they share the last $14$ bits.
   Hence, the number of bits representing offset is $\leq 14$.

2. The physical address looks like this:

   +-----------+-----------+--------+
   +-page-size-+-page-size-+-offset-+
   +-----------+-----------+--------+
   

   because page size = page table size = table directory size.
   Therefore, we get the following equation: $$ 2\times \text{page size} + \text{offset} = 34 $$
   However it is not sufficient to tell what is the page size. I'm stuck.

---

Resources:

• Segmentation and paging
• Wikipedia (discouraged)
• Video tutorial by Anshul Agarwal: part 1, 2, 3, 4 and 5.

Answer 1

The thorough solution:

1. The virtual address looks like this:

   +-------------+------------+--------+
   + table index + page index + offset +
   +-------------+------------+--------+
   

   where:

   • table index is the index length of an entry in the page table directory. I'll call it $i_t$.
   • page index is the index length of an entry in the page table. I'll call it $i_p$.
     
     So we have such an equation now: $$ i_t+i_p+o=32 $$ where $o$ represents bits that we need for offset.

2. From the decoded addresses we know that offset cannot be greater than $14$, so: $$ o \leq 14 $$

3. We know that an entry in both page tables and page tables directories needs $i_t + b_d$ of bits where $b_d$ is the number of bits for accounting information (such as dirty bits, protection bits and so on). So, $b_d$ are accounting bits in the page table directory and $b_t$ are are accounting bits in page table.

   So, if $\text{page size} = 2^\text{offset}$ then $\text{page table size} = 2^\text{offset}$ and $\text{page table directory size} = 2^\text{offset}$: $$ \begin{cases} i_t+b_d = o\\ i_s+b_t = o\\ \end{cases} $$

4. We can say thatSince $\text{page table size} = \text{page table directory size}$ then $i:= i_t = i_s$ and $b :=b_d=b_t$, so we end up with a system of equations like this: $$ \begin{cases} i_t+b_d = o\\ i_s+b_t = o\\ i_t+i_p+o=32 \end{cases} $$ $$ o-b_d+o-b_t+o=32\\ $$ and finally because of $b :=b_d=b_t$: $$ 3o-2b=32\\ $$

5. Now we will test different values of $o$ (I'll not test odd $o$'s because $o$ must be dividable by $2$):
   • when $o=14$: $$ 42-32=2b=10\\ \implies b=5\\ \implies i = 14-5=11\\ \implies i_t+i_s+o=11+11+14=36 \neq 32 $$
   • when $o=12$: $$ 36-32=2b=4\\ \implies b=2\\ \implies i = 12-2=10\\ \implies i_t+i_s+o=10+10+12=32 = 32 $$ which seems to be the answer. Let's just make sure there are no other possibilities.
   • when $o=10$: $$ 30-32=2b=-2\\ \implies b=-1\\ $$ which cannot be true - you obviously cannot have a negative number of bits.

Therefore, the size of a page is equal $2^o=2^{12}$.

Answer 2

Your inference about the format of the physical address is not correct. A physical address looks like

+------------------+--------+
| page frame index | offset |
+------------------+--------+

I think you are getting virtual pages and physical pages confused. Refresh your understanding of how virtual memory and page tables works. I suggest you consult an operating systems textbook: Wikipedia is less than ideal and doesn't have thorough coverage.

Once you fix that confusion: You haven't fully used the information in "The sizes of a page table directory, a table directory and a page are equal."

Suppose the offset was 5 bits (say). This would let you figure out how many bits are needed for each entry in the page table, and thus let you figure out the size of the page tables. You should then be able to use this to determine whether it's possible that a 5-bit offset is feasible. You can then try each possible offset size from 1 to 14 to work out which ones are possible, given the statements in the exercise.

In the future, rather than asking how to solve your particular exercise, I suggest you try to use the exercise to diagnose what your conceptual confusion is (this might require additional self-study) and then ask a conceptual question.