pintos-os.org Git - pintos-anon/blob - src/tests/threads/mlfqs.pm

   1 # -*- perl -*-
   2 use strict;
   3 use warnings;
   4
   5 sub mlfqs_expected_load {
   6     my ($ready, $recent_delta) = @_;
   7     my (@load_avg, @recent_cpu);
   8     my ($load_avg) = 0;
   9     my ($recent_cpu) = 0;
  10     for my $i (0...$#$ready) {
  11         $load_avg = (59/60) * $load_avg + (1/60) * $ready->[$i];
  12         push (@load_avg, $load_avg);
  13
  14         if (defined $recent_delta->[$i]) {
  15             my ($twice_load) = $load_avg * 2;
  16             my ($load_factor) = $twice_load / ($twice_load + 1);
  17             $recent_cpu = ($recent_cpu + $recent_delta->[$i]) * $load_factor;
  18             push (@recent_cpu, $recent_cpu);
  19         }
  20     }
  21     return (\@load_avg, \@recent_cpu);
  22 }
  23
  24 sub mlfqs_expected_ticks {
  25     my (@nice) = @_;
  26     my ($thread_cnt) = scalar (@nice);
  27     my (@recent_cpu) = (0) x $thread_cnt;
  28     my (@slices) = (0) x $thread_cnt;
  29     my (@fifo) = (0) x $thread_cnt;
  30     my ($next_fifo) = 1;
  31     my ($load_avg) = 0;
  32     for my $i (1...750) {
  33         if ($i % 25 == 0) {
  34             # Update load average.
  35             $load_avg = (59/60) * $load_avg + (1/60) * $thread_cnt;
  36
  37             # Update recent_cpu.
  38             my ($twice_load) = $load_avg * 2;
  39             my ($load_factor) = $twice_load / ($twice_load + 1);
  40             $recent_cpu[$_] = $recent_cpu[$_] * $load_factor + $nice[$_]
  41               foreach 0...($thread_cnt - 1);
  42         }
  43
  44         # Update priorities.
  45         my (@priority);
  46         foreach my $j (0...($thread_cnt - 1)) {
  47             my ($priority) = int ($recent_cpu[$j] / 4 + $nice[$j] * 2);
  48             $priority = 0 if $priority < 0;
  49             $priority = 63 if $priority > 63;
  50             push (@priority, $priority);
  51         }
  52
  53         # Choose thread to run.
  54         my $max = 0;
  55         for my $j (1...$#priority) {
  56             if ($priority[$j] < $priority[$max]
  57                 || ($priority[$j] == $priority[$max]
  58                     && $fifo[$j] < $fifo[$max])) {
  59                 $max = $j;
  60             }
  61         }
  62         $fifo[$max] = $next_fifo++;
  63
  64         # Run thread.
  65         $recent_cpu[$max] += 4;
  66         $slices[$max] += 4;
  67     }
  68     return @slices;
  69 }
  70
  71 sub check_mlfqs_fair {
  72     my ($nice, $maxdiff) = @_;
  73     our ($test);
  74     my (@output) = read_text_file ("$test.output");
  75     common_checks (@output);
  76     @output = get_core_output (@output);
  77
  78     my (@actual);
  79     local ($_);
  80     foreach (@output) {
  81         my ($id, $count) = /Thread (\d+) received (\d+) ticks\./ or next;
  82         $actual[$id] = $count;
  83     }
  84
  85     my (@expected) = mlfqs_expected_ticks (@$nice);
  86     mlfqs_compare ("thread", "%d",
  87                    \@actual, \@expected, $maxdiff, [0, $#$nice, 1],
  88                    "Some tick counts were missing or differed from those "
  89                    . "expected by more than $maxdiff.");
  90     pass;
  91 }
  92
  93 sub mlfqs_compare {
  94     my ($indep_var, $format,
  95         $actual_ref, $expected_ref, $maxdiff, $t_range, $message) = @_;
  96     my ($t_min, $t_max, $t_step) = @$t_range;
  97
  98     my ($ok) = 1;
  99     for (my ($t) = $t_min; $t <= $t_max; $t += $t_step) {
 100         my ($actual) = $actual_ref->[$t];
 101         my ($expected) = $expected_ref->[$t];
 102         $ok = 0, last
 103           if !defined ($actual) || abs ($actual - $expected) > $maxdiff + .01;
 104     }
 105     return if $ok;
 106
 107     print "$message\n";
 108     mlfqs_row ($indep_var, "actual", "<->", "expected", "explanation");
 109     mlfqs_row ("------", "--------", "---", "--------", '-' x 40);
 110     for (my ($t) = $t_min; $t <= $t_max; $t += $t_step) {
 111         my ($actual) = $actual_ref->[$t];
 112         my ($expected) = $expected_ref->[$t];
 113         my ($diff, $rationale);
 114         if (!defined $actual) {
 115             $actual = 'undef' ;
 116             $diff = '';
 117             $rationale = 'Missing value.';
 118         } else {
 119             my ($delta) = abs ($actual - $expected);
 120             if ($delta > $maxdiff + .01) {
 121                 my ($excess) = $delta - $maxdiff;
 122                 if ($actual > $expected) {
 123                     $diff = '>>>';
 124                     $rationale = sprintf "Too big, by $format.", $excess;
 125                 } else {
 126                     $diff = '<<<';
 127                     $rationale = sprintf "Too small, by $format.", $excess;
 128                 }
 129             } else {
 130                 $diff = ' = ';
 131                 $rationale = '';
 132             }
 133             $actual = sprintf ($format, $actual);
 134         }
 135         $expected = sprintf ($format, $expected);
 136         mlfqs_row ($t, $actual, $diff, $expected, $rationale);
 137     }
 138     fail;
 139 }
 140
 141 sub mlfqs_row {
 142     printf "%6s %8s %3s %-8s %s\n", @_;
 143 }
 144
 145 1;