Skip to content

Testing and evaluating the correctness of solutions

Jump to bottom
Hanna edited this page Jan 6, 2019 · 2 revisions

The program can be run by the console in two versions:

  • version allowing one simulation with the selected algorithm,

  • a version allowing comparison of all algorithms for the same input data due to:

    • number of frames,

    • number of references to memory,

    • number of page errors,

    • number of entries in memory,

    • the duration of the algorithm.

For the purpose of comparing the algorithms, a generator will also be created containing memory addresses and read or write operations (R/W, Read/Write). Comparative charts will be generated from the program output data.

Verification of the correctness of algorithms - examples

Unit tests were implemented to verify the correctness of individual methods.

Assumptions

  • The contents of the file with memory addresses and read/write operations:

    number hexadecimal (address) hexadecimal (VPN) decimal (VPN) operation type
    1 12345678 12345 74565 R
    2 01234567 01234 4660 R
    3 90123456 90123 590115 W
    4 a9012345 a9012 692242 R
    5 12345678 12345 74565 W
    6 ba901234 ba901 764161 R
    7 a9012345 a9012 692242 R
    8 cba90123 cba90 834192 W
    9 dcba9012 dcba9 904105 R
    10 01234567 01234 4660 W

    Above are contents of the memory array for the examples discussed.

  • Number of frames in memory: 3.

  • refresh_rate for the aging: 3 algorithm.

  • Initial state:

    Page table: [null, null, null]

    Counters (aging): [0000000000000000, 0000000000000000, 0000000000000000]

Testing algorithms using Python unittest

For each algorithm, a test class inheriting from the unittest.TestCase class was created. Each class has a test called test_algorithm. It checks the total numbers:

  • access to memory,

  • page errors,

  • disk writing.

The next steps of the algorithm being executed are stored in the form of a copy of the PageTable class instance, which also stores the state of the frame table (frame_table).

Each of the array states (successive iterations of addresses) is compared to the expected state, which is saved in files in the JSON format. In this way, you can accurately verify the operation of the algorithm step by step.

The input data is the same for each algorithm; saved in test.trace. They contain the same data as those presented in the table with assumptions. To provide a simple way to substitute test parameters, they are saved in the params.json file.

This data is read via the PublicParams class, in a file with auxiliary methods and test_config classes. An instance of this class is created in each test class and properly configured in the setUp methods.

Clock algorithm

Subsequent operations:

  1. Page error - page 74565 missing in page table.

    Page table: [74565 R, null, null].

  2. Page error - page 4660 is missing from the page table.

    Page table: [74565 R, 4660 R, null].

  3. Page error - page 590115 is missing from page table.

    Table of pages: [74565 R, 4660 R, 590115 W].

  4. Page error - no page 692242 in the page table; removal of page 74565, because this position was determined by the clock pointer and the page has not been used recently.

    Table of pages: [692242 R, 4660 R, 590115 W].

  5. Page error - page 74565 exists in the page table; 4660 is removed.

    Table of pages: [692242 R, 74565 W, 590115 W].

  6. Page error - no page 764161 in the page table; removal of page 590115.

    Table of pages: [692242 R, 74565 W, 764161 R].

  7. Page 692242 exists in the page table, setting the bit that was last used, which gives it a second chance in the next iteration.

    Table of pages: [692242 R, 74565 R, 764161 R].

  8. Page error - page 834192 missing in page table; page 764161 is deleted.

    Table of pages: [692242 R, 74565 R, 834192 W].

  9. Page error - no page 904105 in the page table, page 692242 removed.

    Table of pages: [904105 R, 74565 R, 834192 W].

  10. Page error - page 4660 missing in page table, page 74565 removed.

    Table of pages: [904105 R, 4660 W, 834192 W].

Page errors: 9

Writing to disk: 2

Last Recently Used (LRU)

Subsequent operations:

  1. Page error - page 74565 missing in page table.

    Page table: [74565 R, null, null].

  2. Page error - page 4660 is missing from the page table.

    Page table: [74565 R, 4660 R, null].

  3. Page error - page 590115 is missing from page table.

    Table of pages: [74565 R, 4660 R, 590115 W].

  4. Page error - no page 692242 in the page table; removal of the page 74565, because it is the page that was used most recently.

    Table of pages: [692242 R, 4660 R, 590115 W].

  5. Page error - page 74565 exists in the page table; 4660 stays deleted.

    Table of pages: [692242 R, 74565 W, 590115 W].

  6. Page error - no page 764161 in the page table; removal pages 590115.

    Table of pages: [692242 R, 74565 W, 764161 R].

  7. Page 692242 exists in the page table, it is increased the last reference count.

    Table of pages: [692242 R, 74565 R, 764161 R].

  8. Page error - page 834192 missing in page table; it is removed page 74565.

    Table of pages: [692242 R, 834192 W, 764161 R].

  9. Page error - no page 904105 in the page table, deletion pages 764161.

    Table of pages: [692242 R, 834192 W, 904105 R].

  10. Page error - page 4660 missing in page table, deletion pages 692242.

    Table of pages: [4660 W, 834192 W, 904105 R].

Page errors: 9

Writing to disk: 2

Optimum algorithm (OPT)

Subsequent operations:

  1. Page error (missing page 74565 in the page table).

    Page table: [74565 R, null, null].

  2. Page error (page 4660 missing in page table).

    Page table: [74565 R, 4660 R, null].

  3. Page error (no page 590115 in the page table).

    Table of pages: [74565 R, 4660 R, 590115 W].

  4. Page error (no page 692242 in the page table, page 590115 removed, because it is the latest used, writing frame content to disk).

    Table of pages: [74565 R, 4660 R, 692242 R].

  5. Page 74565 exists in the pages table.

    Table of pages: [74565 W, 4660 R, 692242 R].

  6. Page error (missing page 764161 in the page table, page 74565 removal, because it is the latest used, writing frame content to disk).

    Table of pages: [764161 R, 4660 R, 692242 R].

  7. Page 692242 exists in the pages table.

    Table of pages: [764161 R, 4660 R, 692242 R].

  8. Page error (page 834192 is missing in the page table, page 764161 is deleted, because it is used the latest, there is no need to write the frame content to disk).

    Table of pages: [834192 W, 4660 R, 692242 R].

  9. Page error (no page 904105 in the page table, page 834192 removed, because it is used at the latest, writing frame content to disk).

    Table of pages: [904105 R, 4660 R, 692242 R].

  10. Page 4660 exists in the pages table.

    Table of pages: [904105 R, 4660 W, 904105 R].

Website errors: 7

Writing to disk: 3

Aging

Subsequent operations:

  1. Page error (missing page 74565 in the page table).

    Page table: [74565 R, null, null].

    Last counter refresh: 1

    Counters: [1000000000000000, 0000000000000000, 0000000000000000].

  2. Page error (page 4660 missing in page table).

    Page table: [74565 R, 4660 R, null].

    Last counter refresh: 2

    Counters: [1,000,000,000,000,000, 1,000,000,000,000,000, 0000000000000000].

  3. Page error (no page 590115 in the page table).

    Table of pages: [74565 R, 4660 R, 590115 R].

    Last meter refresh: 3, counter refresh (offset right).

    Counters: [0100000000000000, 0100000000000000, 0100000000000000].

  4. Page error (no page 692242 in the page table, page 74565 removal, because it is the first page found with the smallest counter, you do not need to write the frame content to disk).

    Table of pages: [692242 R, 4660 R, 590115 W].

    Last counter refresh: 1, counter refresh (move to the right).

    Counters: [1,000,000,000,000,000, 1,000,000,000,000,000, 1,000,000,000,000,000].

  5. Page error (missing page 74565 in the page table, page 4660 removal, because it is the first page found with the smallest counter, no need to write the contents of the frame to disk).

    Table of pages: [692242 R, 74565 W, 590115 W].

    Last counter refresh: 2.

    Counters: [1 billion, 1,000,000,000,000, 1 billion).

  6. Page error (missing page 764161 in the page table, page 590115 removal, because it is the first page found with the smallest counter, writing content to disk).

    Table of pages: [692242 R, 74565 W, 764161 R].

    Last meter refresh: 3, counter refresh (right shift).

    Counters: [01000000000000000, 01000000000000000, 0100000000000000].

  7. Page 692242 exists in the pages table.

    Table of pages: [692242 R, 74565 W, 764161 R].

    Last counter refresh: 1.

    Counters: [1100000000000000, 0100000000000000, 0100000000000000].

  8. Page error (page 834192 is missing in the page table, page 74565 is removed, because it is the first page found with the smallest counter, writing frame content to disk).

    Table of pages: [692242 R, 834192 W, 764161 R].

    Last counter refresh: 2.

    Counters: [1100000000000000, 1,000,000,000,000,000, 0100000000000000].

  9. Page error (no page 904105 in the page table, page 764161 removed, because it is the first page found with the smallest counter, you do not need to write the frame content to disk).

    Table of pages: [692242 R, 834192 W, 904105 R].

    Last meter refresh: 3, counter refresh (right shift).

    Counters: [0110000000000000, 0100000000000000, 0100000000000000].

  10. Page error (page 4660 is missing in the page table, page 834192 is deleted, because it is the first page found with the smallest counter, writing frame content to disk).

    Table of pages: [692242 R, 4660 W, 904105 R].

    Last counter refresh: 1.

    Counters: [0110000000000000, 1,000,000,000,000,000, 0100000000000000].

Page errors: 9

Writing to disk: 3

Analysis of algorithms execution

The outcome is the ability to examine the effect of the parameters of the problem at the time of calculation, the number of errors and the number of pages written on the disk.

alg trace_file frames total_mem_access page_faults writes refresh total_time
Clock 100000.trace 16 100000 80384 13579 N/A 5590.407
LRU 100000.trace 16 100000 80235 14344 N/A 5029.594
Aging 100000.trace 16 100000 80200 14329 5 5989.652
Opt 100000.trace 16 100000 62319 13813 N/A 5543.49
Clock 100000.trace 32 100000 60645 11912 N/A 6081.44
LRU 100000.trace 32 100000 60441 13578 N/A 5812.051
Aging 100000.trace 32 100000 60461 13575 5 6558.307
Opt 100000.trace 32 100000 45665 12797 N/A 6421.168
Clock 100000.trace 64 100000 21033 7818 N/A 8073.662
LRU 100000.trace 64 100000 21115 9604 N/A 7359.174
Aging 100000.trace 64 100000 20938 7955 5 8155.441
Opt 100000.trace 64 100000 16783 8346 N/A 9272.511
Clock 250000.trace 16 250000 200612 33955 N/A 21989.618
LRU 250000.trace 16 250000 200535 36107 N/A 21408.97
Aging 250000.trace 16 250000 200558 36080 5 22749.251
Opt 250000.trace 16 250000 155855 34617 N/A 23120.566
Clock 250000.trace 32 250000 151390 29856 N/A 23730.62
LRU 250000.trace 32 250000 151402 34044 N/A 21721.229
Aging 250000.trace 32 250000 151217 34008 5 23169.275
Opt 250000.trace 32 250000 114232 31943 N/A 35070.119
Clock 250000.trace 64 250000 52811 19494 N/A 33288.017
LRU 250000.trace 64 250000 52478 23864 N/A 37851.0
Aging 250000.trace 64 250000 52660 19951 5 33672.981
Opt 250000.trace 64 250000 42043 21003 N/A 34910.078
Clock 500000.trace 16 500000 401401 67677 N/A 119028.641
LRU 500000.trace 16 500000 401518 71868 N/A 103620.654
Aging 500000.trace 16 500000 401501 71846 5 106452.489
Opt 500000.trace 16 500000 311629 68961 N/A 111649.847
Clock 500000.trace 32 500000 303013 59420 N/A 112543.798
LRU 500000.trace 32 500000 302279 67917 N/A 110485.522
Aging 500000.trace 32 500000 302313 67861 5 117974.187
Opt 500000.trace 32 500000 228492 63784 N/A 117076.983
Clock 500000.trace 64 500000 104802 39003 N/A 134732.495
LRU 500000.trace 64 500000 104884 47741 N/A 113685.669
Aging 500000.trace 64 500000 104654 39597 5 125405.137
Opt 500000.trace 64 500000 83595 41757 N/A 155711.03

The table is based on data from 9 CSV files obtained from the execution of the run.sh script. Based on the data from the table above, the charts discussed below were created.

Page errors

The graphs below show the dependence of the number of page errors since the number of frames for each algorithm.

Graph of page errors for 100000 addresses Graph of page errors for 250000 addresses Graph of page errors for 500000 addresses

Each of the charts is devoted to a different size of input data (addresses in memory). Despite generating different sets, the charts look very similar and allow you to clearly determine which algorithm causes the least page errors.

In this respect, the algorithms can be sorted:

  1. optimal,
  2. aging,
  3. LRU,
  4. clock.

Disk writes

The graphs below show the dependencies between the number of writings per disk and the number of frames for each algorithm.

Graph for the number of disk writings for 100000 addresses Graph for the number of disk writings for 250000 addresses Graph for the number of disk writings for 500000 addresses

A larger number of frames reduces the need to save pages to disk, which is in line with predictions.

The size of the input data is directly proportional to the number of errors received.

In this case, the order of the algorithms (from the best to the worst) looks like:

  1. clock.
  2. optimal,
  3. aging,
  4. LRU.

Execution time

Below are presented graphs of the total time dependence on the algorithm performance on a given set of data from the number of frames for each algorithm.

Time chart for 100000 addresses Time chart for 250000 addresses Time chart for 500000 addresses

The execution time of the algorithms is proportional to the size of the input data. In one case, in the graph 1.1{reference-type="ref" reference="fig:250000time"} one can notice a fat error, i.e. an overstated execution time for an optimal algorithm with 32 frames. It may be the result of computer power failure during measurements or lower priority of the measurement process.

For each frame length the ratio of algorithm execution times behaves similarly and can be sorted as follows (for the shortest to the longest time):

  1. LRU,
  2. clock,
  3. aging,
  4. optimal.

The conclusions

Based on the charts, a ranking was made, in which the best algorithms were selected from each category. 1 means that the algorithm is the best in a given comparison, while 4 - the worst.

Finally, the results were summed up. Algorithms that have the lowest sum are the best, assuming that each of the three categories has the same weight.

As predicted, the optimal algorithm works best with respondents. The rest of the results are not a surprise either. The aging algorithm took second place in terms of page errors, however, it is very expensive in terms of time.

In terms of time complexity, the LRU worked best.

Table of contents

  1. Admission

  2. The problem

  3. Application design

  4. System implementation

  5. Testing and evaluating the correctness of solutions

  6. Summary

Clone this wiki locally