https://homeostasis.scs.carleton.ca/wiki/index.php?action=history&feed=atom&title=Operating_Systems_2015F_Lecture_18 2026-04-22T13:25:15Z Revision history for this page on the wiki MediaWiki 1.42.1 https://homeostasis.scs.carleton.ca/wiki/index.php?title=Operating_Systems_2015F_Lecture_18&diff=20388&oldid=prev 2015-11-13T22:32:48Z

<p>Created page with &quot;==Video== The video from the lecture given on November 13, 2015 [http://homeostasis.scs.carleton.ca/~soma/os-2015f/lectures/comp3000-2015f-lec18-13Nov2015.mp4 is now availabl...&quot;</p> <p><b>New page</b></p><div>==Video==<br /> <br /> The video from the lecture given on November 13, 2015 [http://homeostasis.scs.carleton.ca/~soma/os-2015f/lectures/comp3000-2015f-lec18-13Nov2015.mp4 is now available].<br /> <br /> ==Notes==<br /> <br /> &lt;pre&gt;<br /> Lecture 18<br /> ----------<br /> <br /> Virtual Memory<br /> <br /> swapping, er...paging<br /> <br /> Swapping technically means writing currently running program to disk and loading another one to run<br /> <br /> Paging means moving pages out of RAM and onto disk<br /> <br /> Question: why does linux use much more than the bare minimum of RAM? What is it doing with all of that extra memory?<br /> <br /> Answer: very aggressive caching of disk contents<br /> <br /> Problem: But what if I need more RAM for programs?<br /> <br /> Need algorithms for moving pages between RAM and disk<br /> <br /> Types of page contents:<br /> * Program data<br /> * Program code<br /> * File contents<br /> <br /> Note that program code is also (read only) file contents<br /> <br /> Really, you have:<br /> 1. File contents, read only<br /> 2. File contents, read write<br /> 3. Program data<br /> <br /> You need more RAM. What do you kick out first?<br /> - not such an easy question!<br /> <br /> Kick out (evict) read only file contents first<br /> Pro: we don&#039;t have to write anything to disk!<br /> Con: Hey, I was running that code!<br /> <br /> Evict read write file contents<br /> Pro: hey they are supposed to go to disk anyway, go ahead and write it<br /> Con: but we have to wait for it to be written first<br /> <br /> Evict program data...to swap<br /> Pro: Hey, we didn&#039;t need that data anyway<br /> Con: Hey, we *did* need that data!<br /> <br /> <br /> Hardware helps with the decision on what pages can be kicked out<br /> * accessed bit<br /> * dirty bit<br /> <br /> Ideal eviction targets are pages with accessed bit clear and dirty bit clear (a clean, non-accessed page)<br /> <br /> Next eviction target is non-accessed dirty pages. Save them to disk then evict<br /> <br /> After evict accessed but clean pages...but this is bad if done frequently (system is &quot;thrashing&quot;)<br /> <br /> Dirty pages are easy - just have a process constantly writing dirty pages to disk, thus &quot;cleaning&quot; them<br /> - sweeps through memory periodically looking for dirty pages<br /> <br /> Ideally what you&#039;d want is a timestamp of last access for every page<br /> <br /> For accessed bits, periodically sweep through memory setting accessed bits to 0. If it is 1, then you know the page has been accessed since the last sweep.<br /> <br /> These &quot;sweep&quot; type algorithms are called clock algorithms because you can think of the pages as positions on a very very big clock, with a hand moving from one to the next.<br /> <br /> Page replacement algorithms can get very complex because, in their ideal form, they predict the future. Best approximation is a bunch of heuristics and adaptive mechanisms based on past behavior.<br /> <br /> But page replacement needs to be reasonable, especially on systems with no swap<br /> <br /> <br /> When a program asks for memory, how do you know if you have enough? When do you say no?<br /> <br /> Conservative way: find pages for every byte requested, return yes only once you&#039;ve allocated it all<br /> <br /> Linux kernel is not conservative at all<br /> <br /> Example: fork<br /> - logically, doubles RAM usage<br /> - at least, doubles program data RAM usage<br /> - but in practice it generally only causes a modest increase in RAM usage<br /> <br /> Example: malloc<br /> - are you really going to use all that memory at once?<br /> <br /> Linux kernel memory allocation is like banking<br /> - gives out loans at a drop of the hat, takes deposits...<br /> - assumes everyone won&#039;t want their money at once<br /> &lt;/pre&gt;</div>

Soma