1. Virtual Memory

Virtual Memory

By using cache, we can provide the illusion that we have fast main memory.

Virtual Memory

Virtual memory is used to increase the available address space that processes can use by providing them with the illusion of a large, private main memory that is actually implemented on slower memory hardware that is shared by multiple proceses.

• Provides the ability to run programs larger than main memory.
• Hides differences in machine configuration from processes.

Link to original

The cost is that we have to do a translation on each memory reference.

Link to original

2. Segmentation

Segmentation

With segmentation, each process’ data is allocated a contiguous segment of physical memory.

A segment is located through its base, which contains the segments’ physical memory location, and bound that indicates the segment’s size.

• $[\text{bound}-\text{base}=\text{size of virtual address space}]$
• typically, systems do not allow processes to access addresses outside its bound

Base and Bound values are stored in dedicated registers.

Link to original

3. External fragmentation

External fragmentation

As processes start and end, their code and data is swapped in and out of main memory. Thiss wapping can lead to external fragmentation: small portions of memory are free, but not contiguous. This is an issue as segmentation requires processes to be stored in contiguous segments.

Fragmentation can lead to situations in which there is enough free memory for a process to be swapped in but it can’t as the free memory is not contiguous.

title: Example of external fragmentation
![](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201/4CCS1CS1%20Computer%20Systems%201/Week%2010.%20Memory%20Hierarchy%2C%20virtual%20memory/Diagrams/Pasted%20image%2020211206134532.png)

Defragmentation

As fragmentation increases, it may become necessary to for the memory to be defragmented. Defragmenting is a process that moves memory around so that free memory is in a continous block, but it may be computationally expensive.

Link to original

4. Paging

Paging

In paging, main memory and virtual memory are divided into equal-sized pages, commonly not the same size as cache blocks. Pages in main memory are sometimes referred to as frames.

• Pages are allocated to a particular process.
• Pages can be non-contiguous in memory.
• Interpret virutal addresses as a pair: $(\text{virtual page number},\text{offset})$
• Each process has its own page table that maps virtual pages to physical pages.

Virtual addresses are divided into two fields:

• Page field: indicates the virtual page location of the address
• Offset: indicates the location of the address within the page

Physical addresses are divided into two fields:

• Page field: indicate the physical page location of the address
• Offset: indicates the location of the address within the page

The page table uses the virtual page index as an index to find the corresponding physical page field.

The valid bit tells us whether the virtual page currently has a corresponding page in main memory. If a process requests a virtual page with a valid bit $=0$ then there is a page fault: the page is fetched from disk.

title: Example 1
Suppose a system has:
- A physical address space of $2^{12}$ addresses.
- A process running on the system that has a virtual address space of $2^{13}$.
- The system uses byte addressing.
- Each physical page contains $2^{10}$ addresses.
 
**How many virtual pages are there?**
- Virtual page size and physical page size are the same so: $\frac{2^{13}}{2^{10}} = 2^{3}$
- Half as many physical pages, $2^2$ physical pages.
 
**How many bits in a virtual address?**
- **Page field**: needs $2^3$ values $\rightarrow 3$ bits
- **Offset**: needs $2^{10}$ values $\rightarrow 10$ bits
- **Total**: $3 + 10 = 13$ bits
 
**How many bits in a physical address?**
- **Page field**: needs $2^2$ values $\rightarrow 2$ bits
- **Offset**: needs $2^{10}$ values $\rightarrow 10$ bits
- **Total**: $2 + 10 = 12$ bits
 
Suppose the page table belonging to the process is as follows:
 
##### What happens when the process requests virtual address $1553_{16}$?
- $1553_{16} = {\color{red}101}{\color{aqua}0101010011}_2$
- Virtual page: ${\color{red}101}_2 = {\color{green}5}_{10}$
- Offset: ${\color{aqua}0101010011}_2$
 
| Index | Valid bit | Physical Page # |
| -----:|:---------:|:---------------:|
|     0 |     0     |        -        |
|     1 |     1     |        3        |
|     2 |     1     |        0        |
|     3 |     0     |        -        |
|     4 |     0     |        -        |
|     5 |     1     |        1        |
|     6 |     1     |        2        |
|     7 |     0     |        -        | 
 
$\color{green}5$ is used to index into the page table.
Valid bit is $1$, so physical page number is extracted and concatenated with offset.
Physical address is $01 \, {\color{aqua}0101010011}_2 = \underline{553_{16}}$.

What happens when the process requests virtual address $1000000000100_2$?

• Virtual page: ${100}_2=4_{10}$
• Offset: ${0000000100}_2$

$4$ is used to index into the page table. Valid bit is $0$, so there is a page fault. The page is retrieved from slower storage. Store newly retrieved page in main memory and update page table:

1. Remove victim page.
2. Set valid bit to $1$.
3. Store physical page #.

Link to original

5. Internal fragmentation

Internal fragmentation

In paging, we have to allocate exactly a page each time, so we can’t give a program a fractional page to provide just enough but instead we have to give it an entire page.

This causes internal fragmentation.

Paging cannot suffer from external fragmentation: processes do not have to be stored contiguously. Segmentation cannot suffer from internal fragmentation: processes can be allocated the exact amount of memory that they require.

Systems can use a mix of paging and segmentation in an attempt to get the best of both worlds.

• Virtual addresses are divided into segments of variable length.
• Segments and main memory are divided into fixed-size pages.
• Each segment as its own page table, so every process has multiple page tables.

Link to original

6. EAT and TLB

Virtual memory EAT

If we store page tables in memory, every time we want to access a main memory address we would have to access main memory twice:

1. Access the page table to convert the virtual address to a physical one.
2. Access the physical address.

There is a penalty when using virtual paging: there must be two main memory accesses, one for the page table, one for the actual data.

$$\begin{array}{rl}EAT& =\text{memory access}+\text{hit rate}\times (\text{MA})+\text{miss rate}\times (\text{out of memory access})\\ & =MA+HR\times (MA)+MR\times (OMR)\end{array}$$

title: Example
Suppose we have a main memory access which requires $200 \text{ ns}$ and the page fault rate is $1\%$.
- Assume it costs us $10 \text{ ms}$ to access a page not in main memory (fetching the page from slower storage, updating page table, accessing data)
- The effective access time would be:
  $$
  	EAT = 0.99 \times (200 \text{ ns} + 200 \text{ ns}) + 0.01 \times (10 \text{ ms}) = 100,396 \text{ ns}
  $$

Translation Lookaside Buffer

We can use a Translation Lookaside Buffer (TLB) to store the most recent page table lookups (virtual and physical address pairs) in a special cache.

Use of a TLB reduces access to main memory and speeds up address translation.

Virtual Page #	Physical Page #
-	-
5	1
2	0
-	-
-	-
1	3
6	2

The steps for using a TLB:

1. Extract the virtual page number from the virtual address.
2. Extract the offset from the virtual address.
3. Look up the virtual page number in the TLB.
4. If there is a TLB hit, use the corresponding physical page number. Add the offset to the physical page number to get memory location.
5. If there is a TLB miss, go to the page table to get the necessary frame number. If the page is in memory, use the corresponding frame number and add the offset to yield the physical address.
6. If the page is not in main memory, generate a page fault and restart the access when the page fault is complete.

Link to original