2
$\begingroup$

I am revising operating systems theory (I'm Italian, forgive me for bad English) and there is a slide that states:

If page size is small then we avoid internal fragmentation (I get that) but we have larger size of page table and therefore larger cost of managing this page table".
If page size is large then we have a larger amount of internal fragmentation but we do have a decreased page table size that's easier to manage.

I don't understand how page size could affect size of page table. Page table (expect from TLB) is saved in memory. I assume that, the amount of free memory we have for a page table is fixed (am I right?) (because we also need memory for OS, processes, and a bunch of other things).

Size of adress in system is also fixed , isn't it? So if we use for instance 32 bits for addresses then we need $2^{32}$ entries in the page table no matter what. (Expect of course, if we use COW: "Copy on write" then we probably need less.)

Anyway, if page size is smaller, the size of page table should be: $$\#\text{entries}*page_{size}$$ where #entries stands for number of entries in the page table. So to me it seems like page size and page table size are analogous.

I am totally missing something here. Could you help?

$\endgroup$
6
$\begingroup$

Suppose you have a virtual address space of say $32$ bits. Then the virtual address space for each and every process is fixed and it ranges from the byte $0$ to $2^{32}-1$.

Now the for the ease of memory management the main memory is divided into frames of certain size say $2^k$ bytes. Also, our virtual address space of the process is divided into chunks or pages each of size $2^k$ bytes. Each page of the process maps to a particular frame of the main memory as a part of memory management/memory mapping of the virtual address space of the process to the physical memory.

Now for a $32$ bit virtual address system, if the page size is $2^k$ the $k$ least significant bits of the virtual address are offsets of the bytes belonging to a particular page and the remaining $32-k$ bits indicate the page number.

The page table has as many entries as there are pages in the virtual address space of the process. So in our generalized running example, the page table has $2^{32-k}$ entries. Suppose that each page table entry is of $4B$, then size of the page table is :

$$\text{No. of page table entries $\times$ size of each page table entry} = 2^{32-k}\times 4 \text{ Bytes} = 2^{34-k} \text{ Bytes}$$

So higher the value of $k$, higher is our page size and smaller is our page table size.

As a specific example:

If page size is $4\text{ KB} = 2^{12}\ B$ we have $k=12$ and hence page table size is $2^{34-12}\ B=2^{22}\ B=4\text{ MB}$

If page size is $4\text{ MB} = 2^{22}\ B$ we have $k=22$ and hence page table size is $2^{34-22}\ B=2^{12}\ B=4\text{ KB}$

$\endgroup$
3
  • $\begingroup$ that actually resolved my confusion thank you . I actually made the false assumption that size of adress space 2^32 , equals the number of pages. But as you said: each virtual adress is made of: d bits for offset and p = 32-d bits for page number (my book says that) so we have $$2^p = 2^{32-d}$$ bits dedicated to the number of pages in total $\endgroup$ Jul 5 at 21:01
  • 1
    $\begingroup$ but just to be sure: the number of bits for offset in virtual adress (you named it k , I named it d there is no difference) is analogous to the page size because? Because bigger offset means longer entries inside the page, so longer = larger (in termsof size ) page? $\endgroup$ Jul 5 at 21:05
  • $\begingroup$ @brucebanner that is how it is... :) $\endgroup$ Jul 6 at 13:07
2
$\begingroup$

The page table isn't a fixed size. Assuming all memory of the system is in use, and no clever tricks to group pages are used, the page table has a size equal to the amount of memory divided by the page size.

$\endgroup$
2
  • $\begingroup$ I do not get the last statement you made page_table_size = total_mem/ page_size. Because that means total memory = page_table_size * page_size? If you wish you could elaborate a little bit more on that $\endgroup$ Jul 5 at 13:18
  • 1
    $\begingroup$ @brucebanner Don't forget the critical assumption: if all memory is in use, or in other words, all physical pages of memory are mapped. $\endgroup$
    – orlp
    Jul 5 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.