Search code examples
memory-managementpagingcpu-architecturepage-tables

Pagination, size of page, table of pages - conclusion about size of operational memory

Lets consider that size of page is equal to 1 KB. One entry in table takes 2B. Table of pages takes not more than one page (so <= 1KB).

Can we conclude that size of operational memory is <= 512 KB ?

A correct answer is No, however I can't understand it. For me, answer is yes - look at my reasoning at show me where I am wrong, please.

Table contains <=1024B/2B=512=2^9 entries in table of pages. Size of page is 1024B=2^10B, so offset takes not more than <=10 bits. Number of page takes <=9 bits - because we have 512=2^9 entries. Hence, 9+10=19. Therefore <=2^19 bits make it possible to address <= 2^19 B=2^9KB=512KB.

Where am I wrong?

Solution

  • A page table entry is 2B, so a table entry can point to one of 2^16 physical pages. That's 2*16 kiB (because pages are 1kB). So a kernel can make use of up to 65536 kiB (64MiB) of physical memory.

    This assumes that the entire page table entry (PTE) is a physical page number. That can work if the position of a PTE within the page table associates it with a virtual address. i.e. 9 bits of a virtual address are used as an index into the PT, to select a PTE.

    We can't assume that the machine does work this way, but similarly we can't assume that it doesn't, until we have more information.

    Given just the info in the question, we can conclude:

    • Usable physical memory can be anything up to 65536kiB.
    • Up to 512 virtual pages can be mapped at once (512kiB).
    • Not much else! Many possibilities are open.

    A more likely design would have a valid/invalid bit in each PTE.

    If a PTE's contents (rather than its location) indicate which virtual page it maps, it would be possible to map a large virtual address space onto very few physical pages. This address space would necessarily be sparsely mapped, but the kernel could give a process the illusion of having a lot of active mappings by keeping a separate table of what the mappings should be.

    So on a page fault, the kernel checks to see if the page should have been mapped. If so, it puts the mapping in the PTE and resumes the process. (This kind of thing happens in real OSes, and it's called a minor page fault.)

    In this design, the kernel's use of the page table to hold a subset of the real mappings would be analogous to a software-managed TLB. (Of course, this architecture could have a non-coherent TLB that requires invalidation after every PTE modification, so this would probably perform horribly).