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.
| Address | Logical/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.
| Address | Page Number | 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
| Address | Level 1 (Outer) | Level 2 (Inner) | Offset |
|---|---|---|---|
| Length (bits) | $n - s - d$ | $d$ | $s$ |
Similarly, a virtual address with three-level paging looks like
| Address | Level 1 | Level 2 | Level 3 | Offset |
|---|---|---|---|---|
| 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
| Address | Page Number | Offset |
|---|---|---|
| Length (bits) | 20 | 10 |
If we use two-level paging, then an address should should look like
| Address | Level 1 (Outer) | Level 2 | Offset |
|---|---|---|---|
| Length (bits) | 12 | 8 | 10 |
Similarly, if we use three-level paging, then an address should look like
| Address | Level 1 | Level 2 | Level 3 | Offset |
|---|---|---|---|---|
| Length (bits) | 4 | 8 | 8 | 10 |
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.
| Address | Segmentation Number | Offset |
|---|---|---|
| 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.