Bc

I'm planning to do the same as my graduation project, any advice?

Wow, thanks!

Probably talking about using hard drive as virtual memory which windows does on low available ram

Glad it was helpful!

Glad you liked it!

I have implemented a processor for such an architecture (with a Software Managed TLB). And yes, much above 2 or 3 levels, a traditional nested page tables start to have serious issues in terms of memory overhead (particularly with sparse address spaces; in my case, the processor supports a virtual address space up to 96 bits, but the overheads when doing ASLR with an 8-level page-table is absurd). Had tested various options, and curiously one of the better-performing options here seems to be AVL Trees (I had compared these both with Hash Tables and B-Trees), along with a few "hybrid" options (such as combining the lower level of a page table with the upper levels as an AVL tree). A hash table has simpler up-front logic, and is faster for a small space, but doesn't scale up particularly well. Chain-hashes are bottlenecked by the size of the front-end hash, whereas direct hashes don't resize cleanly (expanding the hash typically requires re-hashing its contents). Even with a 2048-entry hash on the front-end, the "break even point" (past which point the AVL tree became faster) wasn't all that large. B-Trees seem better in-theory (and in many other contexts), but in testing were slower and had higher memory overhead than the AVL Tree nodes in this case. This is likely due the particular consequences of the (fairly large) 96-bit virtual address space (B-Trees would have more of a space advantage with 48 or 64 bit addresses than with 96 bit addresses). B-Trees could still potentially have an advantage though in that nodes can be paged-out to swap in a "sane" way (unlike either AVL Trees or Hash Tables), assuming the use of page-sized B-Tree nodes. One could potentially also stick all the processes in the OS into a single large B-Tree (by treating the PID/ASID as part of the B-Tree's lookup key). ...

@@BGBTech paging seemed so cool and straight forward back when the 32-bit 80386 came out where the MMU and CPU got hitched, but then in the 64-bit world, it's technique doesn't really translate forward very well maybe one thing to do is just throw more TLB caching at the problem - to mitigate those deeper multilevel lookups? but you're probably tracking in the right direction - exploring alternative data structures

@@TheSulross The problem isn't really speed, but rather "sparseness". With a much bigger address space, and more page-table levels, most of the pages in the upper levels of the page table end up with maybe only a few entries "actually holding anything", and "a whole lot of zeroes", wasting considerable amounts of RAM in the process (at 2 or 3 levels, it isn't too bad, but at 8 levels, it gets "real bad"; and "level skipping" tricks don't really work with ASLR). With both B-Tree or AVL-Tree designs, one can simply skip storing these vast expanses of zeroes (albeit the computational cost of the page lookup is a little higher). The per-page overhead is also a bit higher (say, 28 or 32 bytes rather than 8 bytes), but the space needed for the page-table as a whole is reduced considerably (due mostly to avoiding the "vast expanses of zeroes"). This is why I had also experimented with hybrid trees, which keep the bottom level as a traditional page-table. These can be a little faster, but only "win" in terms of storage space if (on average) the bottom level page tables are more than around 25-33% full. Otherwise, B-Tree or AVL-Tree is smaller. B-Tree has a lower per-page cost than AVL, but tends to end up losing "on average" in terms of storage overhead due to node related overheads (B-Tree nodes are much bigger and tend to end up only around half-full due to "splitting"). In my implementation, the per-page cost was close enough (28B per B-Tree entry, 32B per AVL node), that this caused the balance to lean in favor of the AVL Trees. But, ability to page-out B-Tree nodes could still give them the win. Both tree types have a roughly O(log2 n) lookup cost, where 'n' in this case is the total number of pages allocated into the address space. Chain hashing is faster for "small n", but the break-even point was low enough, and the speed difference small enough, that I felt it "wasn't really worth the bother" in this case.

In all of my recent classes I've learned more about real life applications of tech and how it works from watching this guy, level1techs/Linux and others of the same sort. I've been able to apply then to where I work now even.

@@LeonisYT Thats great .

95% of teachers dont like their work and just appear to class to earn paycheck, but still there is the 5% and youtube ppl who like their job :D

@@ognjenjakovljevic494 true

I have covered multitasking in several videos, try my videos on "Multitasking vs Multithreading vs Multiprocessing" and my two videos on Piccolo OS.

@@GaryExplains I dont miss any of your videos! I will look it again. Thank you

Don't confuse virtual memory and swapping.

@@GaryExplains ahh thanks for the clarification

Yes, that is true. Depending on OS, the C runtime and the size of the malloc. Such requests can be satisfied by asking the OS for new pages which are allocated lazily, no actual page is allocated until the first access (which then causes the soft fault and forces the OS to allocate the actual pages and update the MMU).

@@GaryExplains thanks for clarification!

The kernel manages the page tables.

@@GaryExplains So all the logic is done by the kernel and MMU is just for lookup? Does each page table have some sort of id of the process to which it belongs? Thnx for the answer and keep uploading such enjoyable content :)

Yes, yes, and my pleasure.

LOL, no. If you think that then it means you didn't understand the video at all.

I guess you need to go back and check out the section on how large the tables are.

@@GaryExplains FWIW: In my case, I had designed a custom CPU (on an FPGA), and had used a Software Managed TLB. In such a design, the OS is responsible for loading pages into the TLB on behalf of the program (using TLB Miss interrupts instead of Page Fault interrupts). I had also ended up going with 16K pages, partly as these worked out as a "local optimum" in terms of overhead (vs either 4K or 64K pages). Main reason for doing it this way was mostly cost reasons (raising an interrupt on TLB Miss being cheaper than having a hardware page walker). Because the page-table walking is done in software, one isn't necessarily limited to conventional nested page tables. Had done experiments also with Hash Tables, B-Trees, and AVL Trees for page management. Curiously, the AVL Trees do surprisingly well here (for sparse address spaces and ASLR, they can use significantly less memory than traditional page-tables). B-Trees and Hash Tables came close, but had other drawbacks. Debugging all this stuff has thus far been kind of a massive pain though...

With the dedicated bit, you can use the remaining bits (for non-valid pages) to encode the location of pages which have been paged out to the swapfile or similar (and use the other bits to remember the page access mode once it is pulled back in from the swap file, ...). This is rather useful, and couldn't be done with a scheme like that described.

Eh?