hvvka/page-replacement

Simulation and data analysis for 4 different page replacement algorithms

page-replacement

Original project – VMsim by Tony Poerio.

Simulation and data analysis for 4 different page replacement algorithms.

Algorithms

• Clock. More efficient version of the second chance algorithm (FINUFO, First In Not Used First Out), because the pages do not have to be constantly moved to the end of the list, while they fulfill the same general function as the second chance.

• LRU – Least Recently Used. This algorithm assumes that pages that were most often used in the past will also be the most commonly used in the future. While LRU provides in theory almost optimal performance, it is expensive to implement.

• OPT – optimal. Used as a baseline in the analysis, because it requires perfect future knowledge and is therefore not possible to implement in a real system. Also known as the Bélády algorithm.

• Aging – approximate LRU. The aging algorithm derives from the NFU (Not Frequently Used) algorithm. Each page in the page table has its own counter.

Usage notes

Requires Python 3.

vmsim

Main program. 3 arguments can be passed:

• --numframes – number of frames in RAM. Required

• --refresh – refresh time [ms] for aging algorithm. Optional

• --tracefile – path to the source file (should contain 32b addresses with memory access type). Required

E.g. run:

$ python vmsim.py --numframes 8 --refresh 6 --tracefile data/100000.trace

generator

Generates trace file. Parametrized with file size. E.g.:

$ python generator.py --pages 500000

Output directory is data/.

run

Bash script used for measurement.

The script is parameterized with two data arrays (traces & frames). It runs two scripts in Python – generator and vmsim.

Firstly, 3 files with input data (trace files) are generated. Then for each of the files all algorithms are executed for each frame length.

9 CSV files in results/ are produced as a result.

Simply run:

$ ./run.sh

Analysis

Tables and charts can be found here.

There's also a wiki page.

page-replacement's Issues

Aging & OPT tests

• Implement helper methods to map page_table.
• Aging test.
• OPT test.

ZWS-6 Serialize tuples into CSV

When we got algorithms results in vmsim.py, then

• serialize them into separate CSV files.

ZWS-4 opt refactor

• PEP-8 variable/function/class compliance
• Adding function/class documentation
• Python 3 compliance checking
• Algorithm verification (if implemented properly)
• OPT algorithm project documentation (latex)

ZWS-9 Clock algorithm

• PEP-8 variable/function/class compliance.
• Add function/class documentation.
• Python 3 compliance checking.
• Clock algorithm Latex documentation.

ZWS-7 Generator instead of trace files

• Generate trace data.
• First 20 bits should be limited from 0 to X. Note: chose X=2
• Last 12 bits can be random <0, F>.
• Parametrize number of lines. Note: --pages=< file size in lines >
• Investigate upper bound (X): parse swim.trace and gcc.trace to see how many pages are repeated.
• Remove old trace files from project.

ZWS-1 Fix getUserInput() method from vmsim.py

Generally, taking input from user doesn't work correctly (at least for MacOS). Input args are read in wrong order and sometimes evaluated to None (even though they were provided).

The method should be either fixed, or simply changed to some nice wrapper.

Docs

https://www.overleaf.com/project/5bc346d271944f6a1987f69c

TODO
\section:

• 3. Projekt aplikacji (wstęp) @zxxa
• 3.3 Koncepcja działania algorytmów (wstęp) @hvvka
• 3.5 Struktura danych wejściowych @zxxa
• 4.1.3 CircularQueue
• 4.3 Metoda odczytu danych wejściowych @zxxa
• 5.2 Analiza wykonania algorytmów @hvvka
• 5.3 Wnioski z testów i badań @hvvka
• 6. Podsumowanie @zxxa
• 5.1.2 Opis testów unittests (jeden przykładowy) @hvvka

ogólne:

• nie wklejać kodu do punktów – czytać z pliku @zxxa

nowe:

• dodać nowe template @zxxa
• podpisać listingi kodu @hvvka
• poprawić podpisy tabel/obrazków @hvvka

ZWS-2 Change python version from python2 to python3

python 3.6.x

Clock & LRU tests

• Implement helper methods to map page_table.
• LRU test.
• Clock test.

Update README

At the very end:

• Copy and translate most important parts from latex documentation (would be nice to have charts) to README.
• Translate report from latex to markdown.
• Add report to wiki page.

ZWS-3 Add logger

Don't use print anymore.

All the messages should be logged.
Printing during algorithm execution should have level debug.

ZWS-12 Excel

• Bash script for running trace generation and invoking algorithms.
• Prepare XLSX file with serialized results for traces: 100000, 250000 and 500000 and (for each) frames: 16, 32, 64.
• Create charts out of it.

ZWS-14 OPT algorithm

• PEP-8 variable/function/class compliance.
• Add function/class documentation.
• Python 3 compliance checking.
• Algorithm verification. Is it implemented properly? Write unit tests.
• OPT algorithm Latex documentation.

ZWS-13 input_parser

• useless comments deleting
• exception handling while file opening

ZWS-5 Intermediate results method

• Boolean parameter in algorithms' constructor
• Method for getting page_table state (with info about hits, evict etc.)

ZWS-8 LRU algorithm

• PEP-8 variable/function/class compliance.
• Add function/class documentation.
• Python 3 compliance checking.
• Algorithm verification. Is it implemented properly? Write unit tests.
• LRU algorithm Latex documentation.

ZWS-10 Aging algorithm

• PEP-8 variable/function/class compliance.
• Add function/class documentation.
• Python 3 compliance checking.
• Algorithm verification. Is it implemented properly? Write unit tests.
• Aging algorithm Latex documentation.

ZWS-11 Code refactor (clock, lru)

• Add type suggestions.
• Reorder methods to be top-down.
• Manage useless comments and docstrings.
• Verify implementation with literature.