{"id":6893,"date":"2012-08-10T07:00:00","date_gmt":"2012-08-10T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2012\/08\/10\/how-did-real-mode-windows-implement-its-lru-algorithm-without-hardware-assistance\/"},"modified":"2012-08-10T07:00:00","modified_gmt":"2012-08-10T07:00:00","slug":"how-did-real-mode-windows-implement-its-lru-algorithm-without-hardware-assistance","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20120810-00\/?p=6893","title":{"rendered":"How did real-mode Windows implement its LRU algorithm without hardware assistance?"},"content":{"rendered":"

\nI noted some time ago that real-mode Windows had to do all\nits memory management without any hardware assistance.\nAnd yet, along the way, they managed to implement an LRU-based\ndiscard algorithm.\n\nGabe is really interested in how that was done<\/a>.\n<\/p>\n

\n\nAs we saw a few months ago<\/a>,\ninter-segment calls were redirected through a little stub which\neither jumped directly to the target (if it was in memory)\nor loaded the target\n(possibly discarding other memory to make room)\nbefore jumping to it.\nAnd we saw that the executable format had\nINT 3Fh<\/code> instructions baked into it\nso that the Entry Table could be loaded directly into memory\nfor execution.\n<\/p>\n

\nAs it happens, Windows didn’t take advantage of that feature,\nbecause it wanted to do more.\n<\/p>\n

\nWhen it came time to load the Entry Table,\nthe loader did a little rewriting, converting each\n<\/p>\n

\n    db  flags\n    INT 3Fh\n    db  entry_segment\n    dw  entry_offset\n<\/pre>\n
\nsequence into\n<\/p>\n
\n    db  flags\n    sar byte ptr cs:[xxx], 1\n    INT 3Fh\n    db  entry_segment\n    dw  entry_offset\n<\/pre>\n
\nwhere the xxx<\/code> refers to a table of bytes\nin the Entry Table preallocated for this purpose,\ninitialized to 1’s.\n<\/p>\n
\nWhat is “this purpose”?\n<\/p>\n
\nWhenever anybody needed the address of an inter-segment\nfunction, instead of return the address of the int 3Fh<\/code>,\nthe kernel returned the address of the sar<\/code> instruction.\nThe sar<\/code> instruction stands for shift arithmetic right<\/i>,\nFor a byte value, this means to shift the bits right one place,\nbut keep the high-order bit the same.\n<\/p>\n\n\n\n\n
a<\/code><\/td>\nb<\/code><\/td>\nc<\/code><\/td>\nd<\/code><\/td>\ne<\/code><\/td>\nf<\/code><\/td>\ng<\/code><\/td>\nh<\/code><\/td>\n<\/tr>\n
↓<\/code><\/td>\n↘<\/code><\/td>\n↘<\/code><\/td>\n↘<\/code><\/td>\n↘<\/code><\/td>\n↘<\/code><\/td>\n↘<\/code><\/td>\n↘<\/code><\/td>\n<\/tr>\n
a<\/code><\/td>\na<\/code><\/td>\nb<\/code><\/td>\nc<\/code><\/td>\nd<\/code><\/td>\ne<\/code><\/td>\nf<\/code><\/td>\ng<\/code><\/td>\n<\/tr>\n<\/table>\n
\nOkay, so what was the effect of sticking this little\nsar<\/code> instruction at the start of every inter-segment\ncall?\nSince the values in the table were initialized to 1,\na right arithmetic shift changed the 1 to 0.\nTherefore, each time an inter-segment call was performed,\nthe corresponding byte in the table was set to zero.\n<\/p>\n
\nHooray, a software-implemented Accessed bit!\n<\/p>\n
\nEvery 250 milliseconds, Windows scanned and reset the Access bits,\nusing the data to maintain an LRU-list of all the segments in the\nsystem.\nThat way, when it was time to discard some memory,\nit could discard the least recently used ones first.\n<\/p>\n
\nToday, a timer that runs continuously at 250ms would\nincur the wrath of the power management team.\nBut back in the days of real-mode Windows,\nthere was no power management.\nLike Chuck Norris, PCs ran at only one power level: Awesome.\n<\/p>\n
\nI continue to be amazed at how much Windows 1.0 accomplished\nwith so little.\n<\/p>\n
\n[Raymond is currently away; this message was pre-recorded.]<\/p>\n","protected":false},"excerpt":{"rendered":"
I noted some time ago that real-mode Windows had to do all its memory management without any hardware assistance. And yet, along the way, they managed to implement an LRU-based discard algorithm. Gabe is really interested in how that was done. As we saw a few months ago, inter-segment calls were redirected through a little […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[2],"class_list":["post-6893","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-history"],"acf":[],"blog_post_summary":"
I noted some time ago that real-mode Windows had to do all its memory management without any hardware assistance. And yet, along the way, they managed to implement an LRU-based discard algorithm. Gabe is really interested in how that was done. As we saw a few months ago, inter-segment calls were redirected through a little […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/6893","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=6893"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/6893\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=6893"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=6893"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=6893"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}