3 # Find the directory that contains the grading files.
6 # Add our Perl library directory to the include path.
8 ($GRADES_DIR = $0) =~ s#/[^/]+$##;
9 -d $GRADES_DIR or die "$GRADES_DIR: stat: $!\n";
10 unshift @INC, "$GRADES_DIR/../lib";
17 our ($hw) = "threads";
18 our (@TESTS); # Tests to run.
24 parse_cmd_line qw (alarm-single alarm-multiple alarm-zero alarm-negative
25 priority-preempt priority-fifo priority-donate-one
26 priority-donate-multiple priority-donate-nest
29 clean_dir (), exit if $action eq 'clean';
32 exit if $action eq 'extract';
35 exit if $action eq 'build';
37 run_and_grade_tests ();
38 if (defined ($result{'mlfqs-on'}) && defined ($result{'mlfqs-off'})) {
39 grade_mlfqs_speedup ();
40 grade_mlfqs_priority ();
44 exit success () if $action eq 'test';
46 assemble_final_grade ();
47 exit success () if $action eq 'assemble';
49 die "Don't know how to '$action'";
51 # Runs $test in directory output/$test.
52 # Returns 'ok' if it went ok, otherwise an explanation.
54 # Changes devices/timer.c if necessary.
55 my ($new_time_slice) = $test eq 'priority-fifo' ? 100 : 1;
56 my (@timer_c) = snarf ("pintos/src/devices/timer.c");
57 if (!grep (/^\#define TIME_SLICE $new_time_slice$/, @timer_c)) {
58 @timer_c = grep (!/^\#define TIME_SLICE/, @timer_c);
59 unshift (@timer_c, "#define TIME_SLICE $new_time_slice");
60 open (TIMER_C, ">pintos/src/devices/timer.c");
61 print TIMER_C map ("$_\n", @timer_c);
65 # Changes devices/timer.h if necessary.
66 my ($new_timer_freq) = $test eq 'priority-fifo' ? 19 : 100;
67 my (@timer_h) = snarf ("pintos/src/devices/timer.h");
68 if (!grep (/^\#define TIMER_FREQ $new_time_slice$/, @timer_h)) {
69 @timer_h = grep (!/^\#define TIMER_FREQ/, @timer_h);
70 unshift (@timer_h, "#define TIMER_FREQ $new_timer_freq");
71 open (TIMER_H, ">pintos/src/devices/timer.h");
72 print TIMER_H map ("$_\n", @timer_h);
76 # Copy in the new test.c and delete enough files to ensure a full rebuild.
77 my ($src) = "$GRADES_DIR/" . ($test !~ /^mlfqs/ ? "$test.c" : "mlfqs.c");
78 -e $src or die "$src: stat: $!\n";
79 xsystem ("cp $src pintos/src/threads/test.c", DIE => "cp failed\n");
80 unlink ("pintos/src/threads/build/threads/test.o");
81 unlink ("pintos/src/threads/build/kernel.o");
82 unlink ("pintos/src/threads/build/kernel.bin");
83 unlink ("pintos/src/threads/build/os.dsk");
86 if (xsystem ("cd pintos/src/threads && make",
87 LOG => "$test/make") ne 'ok') {
88 $details{$test} = snarf ("output/$test/make.err");
89 return "Compile error";
92 # Copy out files for backtraces later.
93 xsystem ("cp pintos/src/threads/build/kernel.o output/$test");
94 xsystem ("cp pintos/src/threads/build/os.dsk output/$test");
97 my ($timeout) = $test !~ /^mlfqs/ ? 15 : 600;
98 my (@command) = ("-v", "run", "-q");
99 push (@command, "-o mlfqs") if $test eq 'mlfqs-on';
100 return run_pintos (\@command,
101 CHDIR => "pintos/src/threads/build",
103 TIMEOUT => $timeout);
106 sub grade_alarm_single {
107 verify_alarm (1, @_);
110 sub grade_alarm_multiple {
111 verify_alarm (7, @_);
115 my ($iterations, @output) = @_;
117 verify_common (@output);
120 for (my ($i) = 0; $i < $iterations; $i++) {
121 for (my ($t) = 0; $t < 5; $t++) {
122 push (@products, ($i + 1) * ($t + 1) * 10);
125 @products = sort {$a <=> $b} @products;
129 die $_ if /out of order/i;
131 my ($p) = /product=(\d+)$/;
134 my ($q) = shift (@products);
135 die "Too many wakeups.\n" if !defined $q;
136 die "Out of order wakeups ($p vs. $q).\n" if $p != $q; # FIXME
138 die scalar (@products) . " fewer wakeups than expected.\n"
142 sub grade_alarm_zero {
144 verify_common (@output);
145 die "Crashed in timer_sleep()\n" if !grep (/^Success\.$/, @output);
148 sub grade_alarm_negative {
150 verify_common (@output);
151 die "Crashed in timer_sleep()\n" if !grep (/^Success\.$/, @output);
154 sub grade_priority_fifo {
157 verify_common (@output);
158 my ($thread_cnt) = 10;
161 my (@t) = (-1) x $thread_cnt;
164 my ($idx) = /^Thread (\d+)/ or next;
165 my ($iter) = /iteration (\d+)$/;
166 $iter = $iter_cnt if /done!$/;
167 die "Malformed output\n" if !defined $iter;
168 if (@order < $thread_cnt) {
170 die "Thread $idx repeated within first $thread_cnt iterations: "
171 . join (' ', @order) . ".\n"
172 if grep ($_ == $idx, @order) != 1;
174 die "Thread $idx ran when $order[0] should have.\n"
175 if $idx != $order[0];
176 push (@order, shift @order);
178 die "Thread $idx out of order output.\n" if $t[$idx] != $iter - 1;
183 for my $idx (0..$#t) {
184 if ($t[$idx] == -1) {
185 $err .= "Thread $idx did not run at all.\n";
186 } elsif ($t[$idx] != $iter_cnt) {
187 $err .= "Thread $idx only completed $t[$idx] iterations.\n";
190 die $err if $err ne '';
195 verify_common (@output);
196 our (@mlfqs_on_stats) = mlfqs_stats (@output);
199 sub grade_mlfqs_off {
201 verify_common (@output);
202 our (@mlfqs_off_stats) = mlfqs_stats (@output);
205 sub grade_mlfqs_speedup {
206 our (@mlfqs_off_stats);
207 our (@mlfqs_on_stats);
210 my ($off_ticks) = $mlfqs_off_stats[1];
211 my ($on_ticks) = $mlfqs_on_stats[1];
212 die "$off_ticks ticks without MLFQS, $on_ticks with MLFQS\n"
213 if $on_ticks >= $off_ticks;
217 $result{'mlfqs-speedup'} = $@;
220 sub grade_mlfqs_priority {
221 our (@mlfqs_off_stats);
222 our (@mlfqs_on_stats);
224 check_mlfqs () if !defined (@mlfqs_on_stats);
225 for my $cat qw (CPU IO MIX) {
226 die "Priority changed away from PRI_DEFAULT (29) without MLFQS\n"
227 if $mlfqs_off_stats[0]{$cat}{MIN} != 29
228 || $mlfqs_off_stats[0]{$cat}{MAX} != 29;
229 die "Minimum priority never changed from PRI_DEFAULT (29) "
231 if $mlfqs_on_stats[0]{$cat}{MIN} == 29;
232 die "Maximum priority never changed from PRI_DEFAULT (29) "
234 if $mlfqs_on_stats[0]{$cat}{MAX} == 29;
239 $result{'mlfqs-priority'} = $@;
243 our (@mlfqs_off_stats);
244 our (@mlfqs_on_stats);
245 die "p1-4 didn't finish with MLFQS on or off\n"
246 if !defined (@mlfqs_off_stats) && !defined (@mlfqs_on_stats);
247 die "p1-4 didn't finish with MLFQS on\n"
248 if !defined (@mlfqs_on_stats);
249 die "p1-4 didn't finish with MLFQS off\n"
250 if !defined (@mlfqs_off_stats);
255 my (%stats) = (CPU => {}, IO => {}, MIX => {});
256 my (%map) = ("CPU intensive" => 'CPU',
257 "IO intensive" => 'IO',
258 "Alternating IO/CPU" => 'MIX');
259 my (%rmap) = reverse %map;
263 $ticks = $1 if /Timer: (\d+) ticks/;
264 my ($thread, $pri) = /^([A-Za-z\/ ]+): (\d+)$/ or next;
265 my ($t) = $map{$thread} or next;
267 my ($s) = $stats{$t};
270 $$s{SUM2} += $pri * $pri;
271 $$s{MIN} = $pri if !defined ($$s{MIN}) || $pri < $$s{MIN};
272 $$s{MAX} = $pri if !defined ($$s{MAX}) || $pri > $$s{MAX};
275 my (%expect_n) = (CPU => 5000, IO => 1000, MIX => 12000);
276 for my $cat (values (%map)) {
277 my ($s) = $stats{$cat};
278 die "$rmap{$cat} printed $$s{N} times, not $expect_n{$cat}\n"
279 if $$s{N} != $expect_n{$cat};
280 die "$rmap{$cat} priority dropped to $$s{MIN}, below PRI_MIN (0)\n"
282 die "$rmap{$cat} priority rose to $$s{MAX}, above PRI_MAX (59)\n"
284 $$s{MEAN} = $$s{SUM} / $$s{N};
287 return (\%stats, $ticks);