Memory management formulas

n is the logical address width in bits; the page offset has d bits and the page number n-d bits.

Physical address = frame number bits followed by d offset bits.

e is the size of one page-table entry in bytes; the number of entries equals the number of pages in the logical address space.

Extra bits are those the question lists (valid, dirty, protection and so on). Round up to whole bytes; round to a power of two only if the question says so.

k is the minimum number of levels when each table occupies one page; n-d is the number of page-number bits. If n-d is not a multiple of the bits per level, the convention used here gives the leftover bits to the outermost table, which then occupies less than a page.

One entry per frame; e is the entry size in bytes (an entry holds the process id and page number).

t = TLB lookup time, m = main-memory access time (same unit as t), k = number of page-table levels walked on a miss. The TLB is searched first on every reference, and a miss then costs k extra memory accesses. Assumes no page faults and page-table entries not cached elsewhere. If a question says the TLB lookup overlaps or is ignored, set t = 0.

k page-table accesses plus one data access.

Offsets run from 0 to limit - 1; an offset equal to the limit is out of range.