Virtualisation

From Power-On to C: How xv6 Boots on RISC-V (Part 1) After finishing Operating Systems: Three Easy Pieces (OSTEP) and experimenting with various Linux interfaces and system calls, I wanted to get my hands dirty with an actual operating system kernel codebase. OSTEP frequently points to xv6 for this, and to connect the theoretical concepts: virtual memory, page tables, traps, and scheduling, with real hardware and code, I have been diving into the xv6 kernel alongside MIT’s 6.S081 / 6.828 Operating System Engineering course. This is the start of a multi-part series where I document my notes, walk through the source code, and explain how things actually work under the hood. ...

Segmented Page Table Page table can grow large for a 32-bit address space and 4 KB page size we will be using 20 bits for virtual page number resulting in 2^20 bytes (i.e. 4MB of page table) for a single page table and each process will have its own page table so it is possible that we will be storing ~100sMB for page table alone which is not good. For above page table with 4 bits for VPN (Virtual page number) we can see that only VPN 0,4,14 and 15 are valid i.e. pointing to a PFN (Physical Frame Number) other PTEs (Page table entry) are just taking up space which is not used. We can use segmentation here with base and bound registers for each page table to only store valid PTE in the table. This will again split the virtual address to also contain the segment bits to identify which segment the address belongs to (code, heap or stack). Instead of using Base Page Table Register to query page table we will now be using Base Page Table Register [Segment] to get page table physical address for a given segment. ...

TLB Translation look-aside buffer is a CPU cache which is generally small but since it is closer to CPU a TLB hit results in address translation to happen in 1-5 CPU cycles. CPU Cycle Time taken by CPU to fully execute an instruction, while CPU frequency refers to the number of these cycles that occur per second A TLB hit means for given virtual address the physical frame number was found in the TLB cache. A TLB hit will benefit all the address that lie on the same page. In the above given image page size is 16 bytes, so 4 INT variables can be saved in a single page, so a TLB hit of VPN 07 will serve address translation for VPN = 07 + page of offset of 0, 4,8 and 12 byte. This type of caching is benefitted from spatial locality of data where a cache hit results in cache hits for surrounding data as well. If we cache data and other data points which are more probable to get accessed in the same time frame (like loop variables etc) then such caching is benefitted from Temporal locality. ...

Page Tables Page table contains the translation information of virtual page number to physical frame number. For an address space of 32 bits and page size of 4 KB (i.e. memory of 2^32 is divided into segments of 4 KB where each segment is called a memory page) , The virtual address will be of size 32 bits of which 12 bits (2^12 = 4 KB) will be used as offset inside a single page whereas remaining 20 bits will be used as virtual page number ...