Operating Systems - Logical Address Formats

Paging

Single Level

First of all, to distinguish each byte in an address space of $2^n$ bytes, we need an $n$ bits.

AddressLogical/Physical
Length (bits)$n$

By applying the idea above, we’ll know that, given the page/frame size is $2^s$ bytes, we need $s$ bits to distinguish each byte in the page/frame.

Hence, we can conceptually divide the original $n$-bit address into two parts: page number and offset.

AddressPage NumberOffset
Length (bits)$n-s$$s$

The “page number“ tells us which page this address belongs to, and the “offset“ gives the address’s location inside that page.

Also, from here we can know that such a address space contains $(n-s)$ pages.

Multi Level

If each page entry takes $2^e$ bytes storage space, then a page can hold exactly $2^d$ entries, where $d = s - e$.

Again, to distinguish each of the $2^d$ entries, we need $d$ bits.

Hence, the “page number“ part of a virtual address with two-level paging can be divided further as

AddressLevel 1 (Outer)Level 2 (Inner)Offset
Length (bits)$n - s - d$$d$$s$

Similarly, a virtual address with three-level paging looks like

AddressLevel 1Level 2Level 3Offset
Length (bits)$n - s - 2d$$d$$d$$s$

Example

Given that

  • Page/frame size ($2^s$) = 2^10 bytes
  • Page table entry size ($2^e$) = 2^2 bytes
  • Logical address space ($2^n$) = 2^30 bytes

Then, it’s easy to compute $d = s - e = 10 - 2 = 8$, which means that each page can hold exactly 2^8 page entries.

If we use single-level paging, then an address should look like

AddressPage NumberOffset
Length (bits)2010

If we use two-level paging, then an address should should look like

AddressLevel 1 (Outer)Level 2Offset
Length (bits)12810

Similarly, if we use three-level paging, then an address should look like

AddressLevel 1Level 2Level 3Offset
Length (bits)48810

Segmentation

Given that

  • Max segment size: $2^s$ bytes
  • Virtual address space: $2^n$ bytes

A logical address can be devided into two parts: segmentation number and offset.

AddressSegmentation NumberOffset
Length (bits)$n-s$$s$

The segmentation number tells us which entry in the segmentation table this address belongs to, and then we can get the physical address by adding the offset to the base of that table entry.