This blog talks about Virtual Memory. For each process (the running program), we need to allocate memory to it. We have two goals
(1) User use “memory” like a large and uniform (continuous) array.
(2) And each process has private memory space for safety.
So, we need virtual memory, which is a simple abstraction provided to users. CPU and OS can help us to translate efficient address (virtual address) into physical address.
Basically, we can use the strategy like “Cache”, Then we have some terms
- A virtual memory “Block” is called a “Page”.
- A virtual memory address translation “Miss” is called a “Page fault”.
Base and Bound
The first and easy idea it we pick up a continuous region in physical space and provide it to users. We set “Base” as start and “Bound” as end of the region. So, the translation is quite easy \(\text{Physical address } = \text{ Virtual address } + \text{ base}\) If $\text{ Virtual address } + \text{ base} > \text{bound}$, it’s a violation. For process, it can use a private and uniform address space from $0$ to $\text{bound}-\text{base}+1$.
Segmented Address Space
But if we only select one base and bound, it’s not very large. So, we hope to pick up several pairs of base and bound (a pair is called a segment). Hence, we have the following address
| SEG # | Efficient Address |
We can refer segment table to get the base and bound for some segment and then translate it into physical address.
Paged Address Space
Segment address also has problems, if the remaining space do not form a sufficient large contiguous region for each segment. We will waste a lot of space. Then we introduce Paged Address System
First, we divide physical address into fixed size segments (e.g. 4k byte), which is called “Page frames”. And Efficient Address is interpreted as page number and page offset.
| Page No. | Page Offset |
Similarly, we can refer page table to get the base and bound for each page frame and then add base to Page offset to get physical address.
Mechanisms of translation
For a virtual address, it has two part “virtual page number” and page offset. Then, we search virtual page number in Page Table, to get the Physical page base address (also physical page number). Then we combine “physical page number” and page offset to get physical address.
Translation Look-aside Buffer (TLB)
Now, we want to speed up the translation. The searching in Page table is time-consuming, so we can use the idea of cache. Then we build Translation Look-aside Buffer (TLB). And the structure of TLB as below
- Index: it’s also the lower bits of VPN (Virtual Page number)
- Tag: it’s also the upper bits of VPN
- Data: a page-table entry i.e. PPN (Physical Page number) and access permission
- Status: valid, dirty
Other cache design choices can also apply here, like associative.