137 lines
5.5 KiB
Markdown
137 lines
5.5 KiB
Markdown
06/11/20
|
|
|
|
## Paging implementation
|
|
|
|
Benefits of paging
|
|
|
|
* **Reduced internal fragmentation**
|
|
* No **external fragmentation**
|
|
* Code execution and data manipulation are usually **restricted to a small subset** (i.e limited number of pages) at any point in time.
|
|
* **Not all pages** have to be **loaded in memory** at the **same time** => **virtual memory**
|
|
* Loading an entire set of pages for an entire program/data set into memory is **wasteful**
|
|
* Desired blocks could be **loaded on demand**.
|
|
* This is called the **principle of locality**.
|
|
|
|
#### Memory as a linear array
|
|
|
|
> * Memory can be seen as one **linear array** of **bytes** (words)
|
|
> * Address ranges from $0 - (N-1)$
|
|
> * N address lines can be used to specify $2^N$ distinct addresses.
|
|
|
|
### Address Translation
|
|
|
|
* A **logical address** is relative to the start of the **program (memory)** and consists of two parts:
|
|
* The **right most** $m$ **bits** that represent the **offset within the page** (and frame) .
|
|
* $m$ often is 12 bits
|
|
* The **left most** $n$ **bits** that represent the **page number** (and frame number they're the same thing)
|
|
* $n$ is often 4 bits
|
|
|
|
|
|
|
|
#### Steps in Address Translation
|
|
|
|
> 1. **Extract the page number** from logical address
|
|
> 2. Use page number as an **index** to **retrieve the frame number** in the **page table**
|
|
> 3. **Add the logical offset within the page** to the start of the physical frame
|
|
>
|
|
> **Hardware Implementation**
|
|
>
|
|
> 1. The CPU's **memory management uni** (MMU) intercepts logical addresses
|
|
> 2. MMU uses a page table as above
|
|
> 3. The resulting **physical address** is put on the **memory bus**.
|
|
>
|
|
> Without this specialised hardware, paging wouldn't be quick enough to be viable.
|
|
|
|
### Principle of Locality
|
|
|
|
|
|
|
|
We have more pages here, than we can physically store as frames.
|
|
|
|
**Resident set**: The set of pages that are loaded in main memory. (In the above image, the resident set consists of the pages not marked with an 'X')
|
|
|
|
#### Page Faults
|
|
|
|
> A **page fault** is generated if the processor accesses a page that is **not in memory**
|
|
>
|
|
> * A page fault results in an interrupt (process enters **blocked state**)
|
|
> * An **I/O operation** is started to bring the missing page into main memory
|
|
> * A **context switch** (may) take place.
|
|
> * An **interrupt signal** shows that the I/O operation is complete and the process **enters the ready state**.
|
|
|
|
```
|
|
1. Trap operating system
|
|
- Save registers / process state
|
|
- Analyse interrupt (i.e. identify the interrupt is a page fault)
|
|
- Validate page reference, determine page location
|
|
- Issue disk I/O: queueing, seek, latency, transfer
|
|
2. Context switch (optional)
|
|
3. Interrupt for I/O completion
|
|
- Store process state / registers
|
|
- Analyse interrupt from disk
|
|
- Update page table (page in memory) **
|
|
- Wait for original process to be sceduled
|
|
4. Context switch to original process
|
|
```
|
|
|
|
### Virtual Memory
|
|
|
|
#### Benefits
|
|
|
|
> * Being able to maintain **more processes** in main memory through the use of virtual memory **improves CPU utilisation**
|
|
> * Individual processes take up less memory since they are only partially loaded
|
|
> * Virtual memory allows the **logical address space** (processes) to be larger than **physical address space** (main memory)
|
|
> * 64 bit machine => 2^64^ logical addresses (theoretically)
|
|
|
|
#### Contents of a page entry
|
|
|
|
> * A **present/absent bit** that is set if the frame is in main memory or not.
|
|
> * A **modified bit** that is set if the page/frame has been modified (only modified pages have to be written back to the disk when evicted. This makes sure the pages and frames are kept in sync).
|
|
> * A **referenced bit** that is set if the page is in use (If you needed to free up space in main memory, move a page, however it is important that a page not in use is moved).
|
|
> * **Protection and sharing bits**: read, write, execute or various different combos of those.
|
|
|
|
|
|
|
|
##### Page Table Size
|
|
|
|
> * On a **16 bit machine**, the total address space is 2^16^
|
|
> * Assuming that 10 bits are used for the offset (2^10^)
|
|
> * 6 bits can be used to number the pages
|
|
> * This means 2^6^ or 64 pages can be maintained
|
|
> * On a **32 bit machine**, 2^20^ or ~10^6^ pages can be maintained
|
|
> * On a **64 bit machine**, this number increases a lot. This means the page table becomes stupidly large.
|
|
|
|
Where do we **store page tables with increasing size**?
|
|
|
|
* Perfect world would be registers - however this isn't possible due to size
|
|
* They will have to be stored in (virtual) **main memory**
|
|
* **Multi-level** page tables
|
|
* **Inverted page tables** (for large virtual address spaces)
|
|
|
|
However if the page table is to be stored in main memory, we must maintain acceptable speeds. The solution is to page the page table.
|
|
|
|
### Multi-level Page Tables
|
|
|
|
We use a tree-like structure to hold the page tables
|
|
|
|
* Divide the page number into
|
|
* An index to a page table of second level
|
|
* A page within a second level page table
|
|
|
|
This means there's no need to keep all the page tables in memory all the time!
|
|
|
|
|
|
|
|
The above image has 2 levels of page tables.
|
|
|
|
> * The **root page table** is always maintained in memory.
|
|
> * Page tables themselves are **maintained in virtual memory** due to their size.
|
|
>
|
|
> Assume that a **fetch** from main memory takes *T* nano-seconds
|
|
>
|
|
> * With a **single page table level**, access is $2 \cdot T$
|
|
> * With **two page table levels**, access is $3 \cdot T$
|
|
> * and so on...
|
|
>
|
|
> We can have many levels as the address space in 64 bit computers is so massive.
|