# Calculate Paging System

I have this problem to solve and I have the answers, but I'm trying to understand the concepts behind it.

A paging system has the following parameters: 2^32 bytes of physical memory; page size of 2^10 bytes; 2^16 pages of logical address space.

  1. How many bits are in a logical address? 26 bits
2. How many bytes are in a frame? (?)
3. How many bits are in the physical address specifying the frame? 22 bits
4. How many entries in the page table? 2^16
5. How many bits in each page table entry? Assume each page table entry contains a valid/invalid bit. 23 bits

• As an aside for anyone looking at this (clearly academic) question and wondering how it relates to the real world: logical address spaces are usually larger rather than smaller than physical addresses in real processors. 2^10 is a very small page size; 2^12 is the smallest in common use, but it's generally considered that larger sizes than that are better in most cases. The question assumes a single level page table, but most current systems are either hierarchical or use some form of content addressable memory or programmable lookup to avoid needing page tables that cover the entire space. Jul 17 '18 at 7:42

Ok, let's break it down:

• Physical: 232
• Page Size: 210
• Number of Pages: 216

1. How many bits in a logical address? That's the page address bits plus the number of pages bits. The upper portion of an address is the page number (16 bits), and the lower portion is the offset within that address (10 bits), so the whole address size is 26 bits (1026 bytes).
2. How many bytes are in a frame? A frame is where a page can be mapped into memory, so a frame has to be the same size as a page - 210 bytes.
3. How many bits are in the physical address specifying the frame? Well, you have 32 bits of physical address, and a frame is 210 big, so that leaves 22 of the bits (32 - 10) for the frame's base address.
4. How many entries in the page table? The page table is the full list of pages, whether mapped or unmapped - so there are 216 entries in the page table, since there are 216 pages.
5. How many bits in each page table entry? Assume each page table entry contains a valid/invalid bit. If each page maps to an entry in the page table, and that table is a list of the addresses at which the pages are mapped in physical memory, then each address in the table must be the size of answer 3 (22 bits) plus one bit for the valid/invalid bit, so 23 bits.

Is that clearer?