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.

### 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

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.

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