I am trying to find videos/resources that can give me a simple, clear, concise description of the VSWS algorithm but I cannot seem to find any. Any help would be appreciated!
Can Someone Give me a high-level overview of the VSWS Algorithm...
The basic idea of the Variable-Interval Sampled Working Set algorithm is:
each virtual page has a "was used" flag
while the program is running, if/when the program uses a virtual page (including when the page's data had to be fetched from elsewhere/disk before it could be used) the CPU or OS sets the page's "was used" flag.
after a variable amount of time, the OS checks all the "was used" flags and decides that if a page wasn't used then its not part of the working set (and may evict them to free up physical memory); then clears all the "was used" flags (ready for the next variable amount of time).
... used in Operating Systems?
I wouldn't assume it's actually used in modern operating systems.
Most operating systems use something loosely based on "least recently used"; where a similar "variable sampling" approach is used to build up an estimate of "time when page was used last" (and not merely a single "was used" flag), which is then used to estimate "probability of future use"; which might then be combined with "cost of eviction" and "priority of program" to come up with a combined score; where the pages with the worst score are deemed "best to evict to free up physical memory".
Note 1: If a page was modified and needs to be written to swap space (and then possibly loaded back from swap space later) then it has a higher "cost of eviction"; and if a page hasn't been modified since it was fetched from a file or swap space last then it has a lower "cost of eviction". To improve performance (reduce the cost of eviction, not forgetting that estimates are crude and often poorly predict future use) it'd make sense to prefer the eviction of "cheaper to evict" pages.
Note 2: When there's multiple tasks running; it's good to give some tasks preferential treatment. For an extreme example, imagine if the OS is under "low memory" conditions and constantly thrashing (transferring data to/from) disks; and an admin/user is trying to terminate a buggy program that is causing all the disk trashing but can't because the tool/s they need to use to fix the problem are unresponsive (because those tools were not given preferential treatment and have to be fetched from the "already being thrashed" disk).
Note 3: In some cases (e.g. a task called sleep() and it's trivial to determine that it will wake up soon) it's possible to use other information to get a better estimate of "probability of future use" than a simple "least recently used" algorithm could provide.
Note 4: Typically when an OS needs to free up some physical memory there's other things (e.g. file data caches) that could also be considered (and could also participate in that "calculate a score and evict whatever has the worst score" system).
Note 5: Modern systems also pre-fetch data (e.g. from files, etc) before the data is actually requested. It's entirely possibly for pre-fetched "not requested by any program, not used at all yet" data to be more important than "explicitly requested and previously used" data.