I wrote a kernel for my bachelor project so I've always interacted quite a bit with the x86 MMU, setting up paging, managing the TLB, setting up the segmentation system for boot purposes and then promptly ignoring it once booted and all that :P - Still fun to watch your video on the topic and get a nice refresher on it all
I absolutely love your channel, made me interested in computer architecture so much that I've decided to major in Computer science. I would be really grateful if you could do a series on operating systems and distributed systems. Thanks again for the awesome content!!
I am working on verifying a riscv processor's MMU. Excellent video, brings back the memories of going through the spec and drawing out the multi level paging.
What gets me is when I see some comment in a gaming forum of somebody saying they turned off Virtual Memory. Not really possible in a modern OS, what you really did was to tell the OS you don't want a page file. Things like virtual machines and running 32 bit software on a 64 bit OS need virtual memory to function properly, regardless of whether you have a swap file.
Holy cow! I've been into computers for 40 years, but had NO idea that paging and MMUs were THAT complex. I didn't even know what I didn't know. I remember that the 386 & 030 were the first processors with built-in MMUs. What were the first processors with multi-level paging??
The bulk of MMU is just a RAM. To substitute 10b you need 10 address lines and 10 data lines. The OS writes the re-mapping into the RAM so that the processor's address lines provide the RAM's address and the RAM's data becomes the memory's new address lines. There are also cycle skips to allow for MMU fetches when the output changes, interactions with cache, etc. MUCH of memory space does not need to change: ROM, peripherals, and OS RAM can be mapped permanently. One MCU address bit could be dedicated to this static purpose and the system ROM (or flash) could store this static memory map.
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.
the Intel x86 and ilk hardwire designed the page table mechanism where the lookup pages need to be organized just so so. whereas there are other CPU architectures where are provided a hardware interrrupt for a page access that needs to be resolved and one writes a software interrrupt handler - that leaves the paging data structure(s) wide open so on 64-bit systems can implement a paging system that is better geared to the extremely sparse page utilization of a 64-bit address space and not get ocerwhelmed by page tables overhead. Of course a TLB is still present to make things more efficient. And some CPUs have TLB entries that can be tagged with a process ID which can be used to make process context switching and multi-threading more efficient - vs just blindly purge all TLB and replace on a process context switch. And some systems allow for jumbo page sizes that are megabytes in size as can make mapping code pages more efficient.
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.
Isn't the soft page fault also about dynamic memory allocation? Essentialy a program has mapped only certain amount of physical memory to save resources and when he needs more then another couple of pages are allocated in the physical memory and marked as mapped in the MMU?
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).
4:00 yes yes its just location on physical memory. if this is c64 then you cant have more memory use than 64k so u cant have "virtual" memory. it have to point somewhere there is no virtual memory it saved for somewhere. can be in air LOL. so it is just physical memory OR hard disc, but it have to be written somewhere. not in magically virtual air memory lol yes aplication start it will have address base. that virtual space. no other program can use that. if can you can hack xD
Is there a mmu driver that will allow one to address more "ram" then physically possible in a given machine? For instance, my motherboard has 2mb supports 8gb, app needs 16gb, i want 32gb available... App balks at increased swap file, wants raw ram... Is there a way to override normal mmu function to trick the os and app into treating an ssd or other hardware AS real ram?
As far as I’m aware iOS hasn’t had virtual memory (excluding iPadOS 16 adding it for m1 iPad) but instead uses jetsum which boots inactive apps from memory once it’s full
@@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 :)
6:17 why are you wasting an entire bit per mapping for not allocated memory? In the case where it is zero, all the address bits become "don't cares" Why not just have 0x0 be a special NULL memory that is like /dev/null? Then any address not 0x0 be a valid mapping?
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.
We once had a “Virtual memory full” or something like that in a customer’s Windows XP computer. Checked the performance and needed to uninstall some application (driver) for a wifi dongle. It was drawing all that memory! Guess the windows version was too old for the newer hardware driver….
To speed things up they have a TLB cache, to me it all seems like a paper chase. Why not use the TLB as memory instead of a look up table. For all this work you need a minimum amount of resources just to handle memory. The computer scientists know what they are doing. It would nice if you could switch this off and see how fast it would run if pages in memory were directly mapped to page frames.
@@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...
"We are Meta are now offering you - Virtual Memory! Missing Granny? You can now visit your lost near and dear ones here in the Metaverse as 3D representations of their most Liked posts and images during all their years on facebook!". Coming to a dystopian future near you...
![[#2024MAMA] ROSÉ (로제), Bruno Mars - APT. | Mnet 241122 방송](http://i.ytimg.com/vi/dgGqD28J6aQ/mqdefault.jpg)
I wrote a kernel for my bachelor project so I've always interacted quite a bit with the x86 MMU, setting up paging, managing the TLB, setting up the segmentation system for boot purposes and then promptly ignoring it once booted and all that :P - Still fun to watch your video on the topic and get a nice refresher on it all
Bc
I'm planning to do the same as my graduation project, any advice?
I absolutely love your channel, made me interested in computer architecture so much that I've decided to major in Computer science.
I would be really grateful if you could do a series on operating systems and distributed systems.
Thanks again for the awesome content!!
I am working on verifying a riscv processor's MMU. Excellent video, brings back the memories of going through the spec and drawing out the multi level paging.
Nice! Better explanation than my college professor.
Wow, thanks!
Watching your videos are enough to answer basic questions on Operating System and Computer Networks in interviews.
What gets me is when I see some comment in a gaming forum of somebody saying they turned off Virtual Memory. Not really possible in a modern OS, what you really did was to tell the OS you don't want a page file. Things like virtual machines and running 32 bit software on a 64 bit OS need virtual memory to function properly, regardless of whether you have a swap file.
Probably talking about using hard drive as virtual memory which windows does on low available ram
Holy cow!
I've been into computers for 40 years, but had NO idea that paging and MMUs were THAT complex. I didn't even know what I didn't know.
I remember that the 386 & 030 were the first processors with built-in MMUs.
What were the first processors with multi-level paging??
Perfect timing 🙂 I'm gonna have a test on this topic on Friday 😅
The bulk of MMU is just a RAM. To substitute 10b you need 10 address lines and 10 data lines. The OS writes the re-mapping into the RAM so that the processor's address lines provide the RAM's address and the RAM's data becomes the memory's new address lines. There are also cycle skips to allow for MMU fetches when the output changes, interactions with cache, etc. MUCH of memory space does not need to change: ROM, peripherals, and OS RAM can be mapped permanently. One MCU address bit could be dedicated to this static purpose and the system ROM (or flash) could store this static memory map.
Awesome explanation！
Glad you liked it!
If only my teachers explained me , this good.
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
Woah this was super helpful! Thanks!
Thanks yet again. Looking forward to the next installment (as usual).
the Intel x86 and ilk hardwire designed the page table mechanism where the lookup pages need to be organized just so so. whereas there are other CPU architectures where are provided a hardware interrrupt for a page access that needs to be resolved and one writes a software interrrupt handler - that leaves the paging data structure(s) wide open so on 64-bit systems can implement a paging system that is better geared to the extremely sparse page utilization of a 64-bit address space and not get ocerwhelmed by page tables overhead. Of course a TLB is still present to make things more efficient. And some CPUs have TLB entries that can be tagged with a process ID which can be used to make process context switching and multi-threading more efficient - vs just blindly purge all TLB and replace on a process context switch. And some systems allow for jumbo page sizes that are megabytes in size as can make mapping code pages more efficient.
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.
The legend delivered! :D
Great refresher! Than you sir!
Great information, thank you!!!
Loved this video
Simply explained.Can u also how software management of mmu
Explain Gary, Explain!
Can you please teach my Operating Systems class?? Wow...Thanks Gary!
Great explanation Gary. Thank you!
Glad it was helpful!
Good explanation! Thanks :-)
I'm waiting for Speed test G videos, on the latest chips😟😟😟
Sir when are we going to see speed test g videos for snapdragon gen 1
Thanks for the memories! :)
Gary What happened to your speed test G series ? Haven't seen a speed test for a long time !
Great stuff!
Any plans for videos on Analog computers?
Very interesting stuff
Is virtual memory what Samsung's RAM Plus is?
Is virtual memory is paging file in windows?
Isn't the soft page fault also about dynamic memory allocation? Essentialy a program has mapped only certain amount of physical memory to save resources and when he needs more then another couple of pages are allocated in the physical memory and marked as mapped in the MMU?
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!
What's your thoughts on "Extended RAM" often found in the Settings of every android?
9:45 So I guess this is why 3DXpoint (Optane) is so responsive?
4:00 yes yes its just location on physical memory. if this is c64 then you cant have more memory use than 64k so u cant have "virtual" memory. it have to point somewhere there is no virtual memory it saved for somewhere. can be in air LOL. so it is just physical memory OR hard disc, but it have to be written somewhere. not in magically virtual air memory lol yes aplication start it will have address base. that virtual space. no other program can use that. if can you can hack xD
Is there a mmu driver that will allow one to address more "ram" then physically possible in a given machine?
For instance, my motherboard has 2mb supports 8gb, app needs 16gb, i want 32gb available...
App balks at increased swap file, wants raw ram...
Is there a way to override normal mmu function to trick the os and app into treating an ssd or other hardware AS real ram?
Multi tasking please!
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
As far as I’m aware iOS hasn’t had virtual memory (excluding iPadOS 16 adding it for m1 iPad) but instead uses jetsum which boots inactive apps from memory once it’s full
Don't confuse virtual memory and swapping.
@@GaryExplains ahh thanks for the clarification
ayy! i remember a comment asking about this
So if process A has virtual address 123 and process B has virtual address 123 how does the MMU give the right real address?
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.
Please can you talk about kvm on Android and I have seen someone run full win 11 on the new pixel phone us virtual OS
6:17 why are you wasting an entire bit per mapping for not allocated memory? In the case where it is zero, all the address bits become "don't cares" Why not just have 0x0 be a special NULL memory that is like /dev/null? Then any address not 0x0 be a valid mapping?
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.
👍
👍👍
A clever way to waste ressources that you mitigate 30 years later allowing 1Mb and 4Gb pages..
Indeed It's usefull !
Virtual Memory is very last decade. I'm pretty sure most computers don't bother with it now.
LOL, no. If you think that then it means you didn't understand the video at all.
We once had a “Virtual memory full” or something like that in a customer’s Windows XP computer. Checked the performance and needed to uninstall some application (driver) for a wifi dongle. It was drawing all that memory! Guess the windows version was too old for the newer hardware driver….
To speed things up they have a TLB cache, to me it all seems like a paper chase. Why not use the TLB as memory instead of a look up table. For all this work you need a minimum amount of resources just to handle memory. The computer scientists know what they are doing. It would nice if you could switch this off and see how fast it would run if pages in memory were directly mapped to page frames.
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...
I don’t know why I found this intimidating. There’s clearly nothing to it.
where is virtual memory explanation?
Eh?
"We are Meta are now offering you - Virtual Memory! Missing Granny? You can now visit your lost near and dear ones here in the Metaverse as 3D representations of their most Liked posts and images during all their years on facebook!". Coming to a dystopian future near you...
Virtual memory is memory you don't get, even though you paid for it.