Memory

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 ...

References 5.6 Problem Generally when traversing the index made up of btree we have to take latch on it. In MySQL 5.6 the approach of taking latch depends on the possible operation we are doing: If the operation is a read operation then taking a read lock is sufficient to prevent any writes to happen to the pages we are accessing in Btree while reading If the operation is a write operation then there are again two possibilities: Optimistic Locking If the write is limited to modifying the leaf page only without modifying the structure of the tree (Merging OR Splitting) then it’s an optimistic locking approach where we take read latch on root of the tree and write latch only on the leaf node to modify ^ab3c53 Pessimistic Locking But if the operation result is in any type of restructuring of the tree itself then that will be known to us only after reaching the target leaf node and knowing its neighbours and parents. So the approach is first to try with optimistic locking defined above and then go for pessimistic locking Pessimistic locking involves taking a write latch on the root resulting in full ownership of the tree by the current operation (until the operation is complete no other operation can take a read or write latch, so all the other operations has to wait even if they are read operations and involve only optimistic locking). When the leaf node is found we take write latch on the leaf’s neighbours as well as its parent and do the restructuring and if the same restructuring needs to happen at parent level then we will take similar write locks recursively up the tree. ^17a3ff ...