Unix : the "working set" algorithm
I took my end semester exam today on the design of theUnix 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.
Comments