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