Operating Systems - Logical Address Formats

Nathaniel May 11, 2015

Paging

Single Level

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

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.

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

Length (bits)2010

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

Length (bits)12810

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

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.

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