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

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:

• 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$.

-
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.

The thorough solution:

-
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.

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

-
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}
$$

-
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\\
$$

• 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}$.

StackExchange Computer Science Q#45620, answer score: 2