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$
2
  • $\begingroup$ I'm typing this on a computer with six million pages. So the page table is not small. If the page size was doubled I would only have three million pages. $\endgroup$
    – gnasher729
    Nov 2, 2022 at 19:08
  • $\begingroup$ Bigger pages are less numerous ! $\endgroup$
    – user16034
    Feb 7, 2023 at 21:52

3 Answers 3

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, 2021 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, 2021 at 21:05
  • $\begingroup$ @brucebanner that is how it is... :) $\endgroup$ Jul 6, 2021 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$
3
  • $\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, 2021 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, 2021 at 13:48
  • $\begingroup$ The page size is just a tiny bit in the configuration of the processor. A processor could use 4KB pages, or 64KB pages, or 1MB pages, it makes little difference. But if you change the page size and want the same number of pages, you have to pay real money for more RAM. $\endgroup$
    – gnasher729
    Feb 7, 2023 at 23:31
0
$\begingroup$

As the page size increases, the number of pages in memory decreases. Now, each entry in a page table is an address translation of a page. So, the page table will have fewer entries when the number of pages decreases. Hence, page table size decreases with an increase in page size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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