selmanozleyen / os-virtual-mem-emulator

A simulation of the virtual memory. The purpose here is to compare the page replacement and allocation policies.

os-virtual-mem-emulator

A simulation of the virtual memory. Page replacement and allocation algorithms are compared by the number of:

• Reads
• Writes
• Page replacements
• Disk page writes
• Disk page reads

sortArrays frameSize numPhysical numVirtual pageReplacement allocPolicy pageTablePrintInt diskFileName.dat

frameSize is the size of the page frames, numPhysical is the total number of page frames in the physical memory, numVirtual is the total number of frames in the virtual address space, pageReplacement is the page replacement algorithm (NRU, FIFO, SC, LRU, WSClock), allocPolicy is the allocation policy (global or local), pageTablePrintInt is the interval of memory accesses after which the page table is printed on screen, diskFileName.dat is the name of the file that keeps the out of memory frames. For example,

sortArrays 12 5 10 LRU local 10000 diskFileName.dat

defines a frame size of 2 12 (4096) integers, 2 5 (32) physical frames, 2 10 (1024) virtual frames, uses LRU as page replacement algorithm, local allocation policy, and diskFileName.dat as the disk file name. In other words, this system has a physical memory that can hold 4096*32=131.072 integers and has a virtual memory that can hold 4096*1024= 4.194.304 integers. This command prints the page table on the screen at every 10000 memory accesses.

Benchmark parameters are like this:

./benchmark phyIntCount

phyIntCount is the number of integers in the physical memory in terms of 2's power. For example: if phyIntCount = 14 then for framSize = 1, numPhysical will be 13. (also numVirtual is always set to numPhysical + 4) phyIntCount = 14 is the parameter required for sorting 16K integers in physical memory and 128K integers in virtual memory.

Building

make

Results and Evaluation

Some stats to compare the algorithms.
Here index sort causes many misses because index sort changes the target array elements only when the sorted position of each index is known thus the number of writes required would be minimal. re very high because locality principles do not apply strongly in the first phase of the algorithm. In the second phase even though the number of writes is minimum, very high are done to unrelated places because the initial array given is unsorted. Even though bubble sort has 100 times more number of writes the close to each other with index sort. Index sort is maybe more useful when the target array elements are big data structures.

Let w(k,t) the working set be the set of pages used by an application in the most recent k references at time t. We can plot the appoximate working set graph with our utilities when t is fixed to the finishing moment of the application.
Here is an example for Merge Sort thread.

The sudden increase in the number of pages is probably because quicksort thread finished early and the remaining pages was given to merge sort thread.

Benchmark results from various experiments.

Bubble Sort

Optimal Frame Size is 4

Read Count	Write Count	Page Misses	Page Replacement	Disk Reads	Disk Writes
65251	36982	5693	5693	5693	1671

Optimal Replacement Algorithm is LRU

Read Count	Write Count	Page Misses	Page Replacement	Disk Reads	Disk Writes
65251	36982	9029	9024	9029	2197

Quick Sort

Optimal Frame Size is 4

Read Count	Write Count	Page Misses	Page Replacement	Disk Reads	Disk Writes
4678	2230	638	636	638	311

Optimal Replacement Algorithm is LRU

Read Count	Write Count	Page Misses	Page Replacement	Disk Reads	Disk Writes
4678	2230	577	574	577	244

Merge Sort

Optimal Frame Size is 4

Read Count	Write Count	Page Misses	Page Replacement	Disk Reads	Disk Writes
21337	17585	2394	2394	2394	1113

Optimal Replacement Algorithm is LRU

Read Count	Write Count	Page Misses	Page Replacement	Disk Reads	Disk Writes
21337	17585	3879	3877	3879	1385

Index Sort

Optimal Frame Size is 3

Read Count	Write Count	Page Misses	Page Replacement	Disk Reads	Disk Writes
132020	948	54445	54442	54445	4565

Optimal Replacement Algorithm is LRU

Read Count	Write Count	Page Misses	Page Replacement	Disk Reads	Disk Writes
132020	948	44718	44714	44718	8597