Simulation of common page replacement algorithms used by operating systems to manage memory usage.
This is built upon a programming assignment given in Operating Systems (CSC 4301) at LSU, instructed by Feng Chen.
Algorithms Implemented
- Optimal
- Random
- FIFO
- LRU
- CLOCK
- NFU
- NFU with aging
Todo
- Improve configuration ability
- Configuration File (json parser? or just VAR=meh. I kinda like jsmn's feature set)
- Read page calls from file or define in config file (hard coded page refs is no beuno)
Optimal algorithmGenerate list of page calls to grab from before running the event loopNeed Look-ahead for page refs- Second-chance algorithm
- Same as CLOCK with no hand?
- Guess we can do some list manipulation here to make it more genuine
- Most recently used (lol, these should be the worst, why even)
- Most frequently used (lol, these should be the worst, why even)
- Stat comparing all other algorithms to Optimal algorithm
- Add better page call models than random
- Exponential (call some pages exponentionally more times)
- ???
- Ability to record/replay a system's page calls for real-world application testing
- Learn proper C modularity
Currently tested on Linux, Mac OS X, and Windows.
Pull requests always welcome. =)
make./pagesim <algorithm: {ALL, LRU, CLOCK}> <# page frames: integer greater than 0> <debug: 0 or 1, default 0>./pagesim ALL 10[selby@dux os-2]$ ./pagesim A 10
RANDOM Algorithm
Frames in Mem: 10, Hits: 0, Misses: 1, Hit Ratio: 0.000000
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 10 _ _ _ _ _ _ _ _ _
Extra : 0 0 0 0 0 0 0 0 0 0
Time : 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061
FIFO Algorithm
Frames in Mem: 10, Hits: 0, Misses: 1, Hit Ratio: 0.000000
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 10 _ _ _ _ _ _ _ _ _
Extra : 0 0 0 0 0 0 0 0 0 0
Time : 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061
LRU Algorithm
Frames in Mem: 10, Hits: 0, Misses: 1, Hit Ratio: 0.000000
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 10 _ _ _ _ _ _ _ _ _
Extra : 0 0 0 0 0 0 0 0 0 0
Time : 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061
CLOCK Algorithm
Frames in Mem: 10, Hits: 0, Misses: 1, Hit Ratio: 0.000000
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 10 _ _ _ _ _ _ _ _ _
Extra : 0 0 0 0 0 0 0 0 0 0
Time : 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061
NFU Algorithm
Frames in Mem: 10, Hits: 0, Misses: 1, Hit Ratio: 0.000000
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 10 _ _ _ _ _ _ _ _ _
Extra : 0 0 0 0 0 0 0 0 0 0
Time : 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061
AGING Algorithm
Frames in Mem: 10, Hits: 0, Misses: 1, Hit Ratio: 0.000000
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 10 _ _ _ _ _ _ _ _ _
Extra : 0 0 0 0 0 0 0 0 0 0
Time : 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061 31806061
...
RANDOM Algorithm
Frames in Mem: 10, Hits: 827, Misses: 173, Hit Ratio: 0.827828
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 5 0 7 6 3 2 4 10 9 11
Extra : 986 995 982 992 985 999 988 991 998 996
Time : 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962
FIFO Algorithm
Frames in Mem: 10, Hits: 829, Misses: 171, Hit Ratio: 0.829830
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 4 9 6 3 2 11 7 0 1 10
Extra : 988 998 992 985 999 996 982 995 997 991
Time : 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962
LRU Algorithm
Frames in Mem: 10, Hits: 815, Misses: 185, Hit Ratio: 0.815816
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 11 9 5 3 6 2 7 4 1 10
Extra : 996 998 986 985 992 999 982 988 997 991
Time : 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962
CLOCK Algorithm
Frames in Mem: 10, Hits: 813, Misses: 187, Hit Ratio: 0.813814
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 9 1 5 11 0 4 2 3 6 10
Extra : 0 0 1 1 1 1 0 1 1 1
Time : 31805961 31805961 31805961 31805961 31805961 31805961 31805961 31805961 31805961 31805961
NFU Algorithm
Frames in Mem: 10, Hits: 809, Misses: 191, Hit Ratio: 0.809810
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 8 9 6 3 2 11 5 0 1 10
Extra : 72 68 75 91 84 81 96 80 92 1
Time : 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962
AGING Algorithm
Frames in Mem: 10, Hits: 811, Misses: 189, Hit Ratio: 0.811812
Frame # : 0 1 2 3 4 5 6 7 8 9
Page Ref : 1 10 0 5 9 4 7 3 2 11
Extra : 2812504 70806 625000 1221 0 0 76 610 10000028 1250009
Time : 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962 31805962
RANDOM Algorithm
Frames in Mem: 10, Hits: 827, Misses: 173, Hit Ratio: 0.827000
FIFO Algorithm
Frames in Mem: 10, Hits: 829, Misses: 171, Hit Ratio: 0.829000
LRU Algorithm
Frames in Mem: 10, Hits: 815, Misses: 185, Hit Ratio: 0.815000
CLOCK Algorithm
Frames in Mem: 10, Hits: 813, Misses: 187, Hit Ratio: 0.813000
NFU Algorithm
Frames in Mem: 10, Hits: 809, Misses: 191, Hit Ratio: 0.809000
AGING Algorithm
Frames in Mem: 10, Hits: 811, Misses: 189, Hit Ratio: 0.811000