Recently I read “Modern Operating system”, “In-depth Understanding of computer System” and “Introduction to Operating system”. Because the books are very thick, I focused on learning virtual memory and related knowledge of paging mechanism first. This blog is used as a study note to facilitate review with others in the future
Virtual memory
Some knowledge points
Three important capabilities of virtual memory
- Think of main memory as a cache of address space stored on disk, holding only active areas in main memory and passing data back and forth between disk and main memory as needed. In this way, it uses main memory efficiently
- It simplifies memory management by providing a consistent address space for each process
- It protects the address space of each process from being corrupted by other processes
Virtual addressing
Virtual addressing: The CPU accesses main Memory by generating a Virtual Address (VA), which is translated into a physical Address by the Memory Manage Unit (MMU) through a query table placed in main Memory
Each byte in main memory has a virtual address selected from the virtual address space and a physical address selected from the physical address space
The virtual memory address space is divided into several cells of fixed size, called pages. The physical address space is divided into units called page frames. They are usually the same size
A page table
Page tables map virtual pages to physical pages. Exists in physical memory
A Page Table is an array of Page Table entries (PTE), equivalent to one PTE per grid in the Page Table
The 16-bit virtual address of the MMU = 4-bit page number + 12-bit offset
The PTE contains the page frame id, cache deny bit, access bit, modify bit, protect bit, and present/ Absent bit
Missing pages interruption
MMU found that the page was not mapped. The operating system then needs to find a rarely used page box and write its contents to disk (if it is not on disk), then read the page that needs to be accessed into the reclaimed page box, modify the mapping, and re-execute the instructions that caused the missing page interrupt
Locality principle
The principle of locality guarantees that at any given moment, programs will tend to work on a smaller set of active pages, called the working set, or resident set. After the initial overhead, that is, scheduling the working set pages into memory, subsequent drinking of the working set results in a hit with no additional disk traffic.
jitter
If the size of the working set exceeds the size of the physical memory, the program will jitter and pages will move in and out.
TLB
If you need to access the page table each time to access the target memory, then you need to access the memory twice to achieve sequential memory accesses, which can reduce performance in half
It has been observed that most programs make multiple visits to a small number of pages, so the solution is to set up a small hardware device that maps virtual addresses directly to physical addresses without going through the page table (equivalent to another layer of caching). This device is called Translation Lookaside Buffer. TLB), which also contains the modified bit, protected bit, and virtual page number
TLB soft failure
Soft failure occurs when a page access is in memory but not in TLB. In this case, you only need to update the TLB and no disk I/O is generated
TLB hard failure
Hard failure occurs when a page does not exist in memory or TLB. The sequential disk access is required to load the page
Multilevel and inverted page tables
If memory needs to be particularly large, the page table becomes large, and can be multilevel. Inverted page table pages can save a lot of space, but converting from virtual addresses to physical addresses becomes difficult and the entire inverted page table must be searched.
TLB acceleration can be used to solve the defect of inverted page table. When TLB fails, a hash table is established and virtual addresses are used to hash to speed up the process of storing new addresses in TLB
Multistage page table inverted page table here has not fully understood, learn to understand I will write in detail
Page replacement algorithm
How to determine which page to eliminate when a page – missing interruption occurs?
Optimal page replacement algorithm
It’s an ideal, impossible algorithm
The idea is that we can know how many more instructions each page needs to go through before it gets accessed (which it can’t), by the order in which pages are accessed, and then swap out pages that have to wait the longest to be accessed
Page replacement algorithms have not been used recently
By adding flag bits to pages, they are divided into four categories: 0. Not accessed, not modified
- Not accessed, modified
- Has been accessed, not modified
- It has been accessed. It has been modified
Select a random substitution from a class with a small number. The central idea is “try to delete the ones that are not accessed. If they are accessed but not modified, they may be used frequently (locality principle), so keep them.”
Fifo page replacement algorithm
FIFO first in first out is easy to understand, but not so good because it may change the page that is often used
Second chance page replacement algorithm
Because THE FIFO may be used to change out, check the R position before changing out, if 1 is used, then put it at the end of the queue to give it another chance, if 0 is never used, then directly change out
Clock page replacement algorithm
The second chance algorithm above is more reasonable, but because it maintains a linked list, it is very inefficient to move pages frequently in the linked list, so it can be improved, change the linked list to a circular list, use a pointer to point to the oldest page, and then look at the R position.
In fact, in addition to the linked list loop nothing changes, moving the pointer is not the page, high efficiency
The least recently used page replacement algorithm LRU
LRU, while theoretically possible, is expensive in practice because the entire linked list must be updated every time memory is accessed. Finding a page and moving to the top of the table also takes time
It can be implemented in hardware, with a counter C, every time after the execution of an instruction, automatically add 1, and then the value is stored in the corresponding page, when the page is interrupted to find the smallest value but which page, this is the least recently used page
The least frequently used page replacement algorithm NFU/ aging algorithm
LRU is a rough implementation of LRU, which is actually very difficult to implement
Working set page replacement algorithm
It’s related to the principle of locality. The basic idea is “find a page that’s not in your work set and swap it out.”
Suggest to see “modern operating system” P121-122
Working set clock page replacement algorithm
To improve on the previous one, change the data structure into a circular linked list
Modern Operating Systems P123
Page replacement algorithm comparison summary
Modern Operating Systems P124 is very detailed
Page missing interrupt processing
What does the system do when a page-missing interrupt occurs
Modern operating systems, P131, section 3.6.2
conclusion
This book is very detailed, and some parts of the book are easy to understand. I do not need to repeat the summary of the book. Next week I hope to summarize process communication, threads, deadlocks, fragmentation mechanisms, file system I/O
Come on, don’t chase the horse, use the time to chase the horse to plant grass.