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: $$ 2times 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.
Asked By : Mateusz Piotrowski
Answered By : Mateusz Piotrowski
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}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/45620