5 sub mlfqs_expected_load {
6 my ($ready, $recent_delta) = @_;
7 my (@load_avg, @recent_cpu);
10 for my $i (0...$#$ready) {
11 $load_avg = (59/60) * $load_avg + (1/60) * $ready->[$i];
12 push (@load_avg, $load_avg);
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);
21 return (\@load_avg, \@recent_cpu);
24 sub mlfqs_expected_ticks {
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;
34 # Update load average.
35 $load_avg = (59/60) * $load_avg + (1/60) * $thread_cnt;
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);
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);
53 # Choose thread to run.
55 for my $j (1...$#priority) {
56 if ($priority[$j] < $priority[$max]
57 || ($priority[$j] == $priority[$max]
58 && $fifo[$j] < $fifo[$max])) {
62 $fifo[$max] = $next_fifo++;
65 $recent_cpu[$max] += 4;
71 sub check_mlfqs_fair {
72 my ($nice, $maxdiff) = @_;
74 my (@output) = read_text_file ("$test.output");
75 common_checks (@output);
76 @output = get_core_output (@output);
81 my ($id, $count) = /Thread (\d+) received (\d+) ticks\./ or next;
82 $actual[$id] = $count;
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.");
94 my ($indep_var, $format,
95 $actual_ref, $expected_ref, $maxdiff, $t_range, $message) = @_;
96 my ($t_min, $t_max, $t_step) = @$t_range;
99 for (my ($t) = $t_min; $t <= $t_max; $t += $t_step) {
100 my ($actual) = $actual_ref->[$t];
101 my ($expected) = $expected_ref->[$t];
103 if !defined ($actual) || abs ($actual - $expected) > $maxdiff + .01;
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) {
117 $rationale = 'Missing value.';
119 my ($delta) = abs ($actual - $expected);
120 if ($delta > $maxdiff + .01) {
121 my ($excess) = $delta - $maxdiff;
122 if ($actual > $expected) {
124 $rationale = sprintf "Too big, by $format.", $excess;
127 $rationale = sprintf "Too small, by $format.", $excess;
133 $actual = sprintf ($format, $actual);
135 $expected = sprintf ($format, $expected);
136 mlfqs_row ($t, $actual, $diff, $expected, $rationale);
142 printf "%6s %8s %3s %-8s %s\n", @_;