I took my end semester exam today on the design of the Unix operating system. Most of it was a breeze. However, before the exam, a little confusion cropped up regarding the “working set” algorithm in “on demand paging“. I had initially thought that it was just a regular LRU implementation, but it apparently isn’t. I’ve looked around the internet and I can not really find any details on the implementation. If you know a resource, please do drop in the link as a comment?

I’ll take a brief example to show the difference between the two implementations, one being a regular LRU, and the other being the variant which is what is apparently actually used.

Consider this stream of requests : 24, 15, 18, 23, 24, 17, 18, 17, 17, 15, 24, 17, 24, 18 and assume a window size of 4.

Page reference Simple LRU Variant
24 24 24
15 24,15 24,15
18 24,15,18 24,15,18
23 24,15,18,23 24,15,18,23
24 15,18,23,24 15,18,23,24
17 18,23,24,17 18,23,24,17
18 23,24,17,18 23,24,17,18
17 23,24,18,17 24,18,17
17 23,24,18,17 18,17
15 24,18,17,15 18,17,15
24 18,17,15,24 17,15,24
17 18,15,24,17 15,24,17
24 18,15,17,24 15,17,24
18 15,17,24,18 17,24,18

I have marked the beginning of variation in red. So, which one is correct?? I used the variant in the test because that’s what our lecturer had said was right.