ankursinha.in/blog

neuroscience/fedora/musings

Sat 04 December 2010

Unix : the "working set" algorithm

Posted by ankur in Tech (218 words, approximately a 1 minute read)

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