+ verify_common (@output);
+ grep (/Testing invalid join/, @output) or die "Test didn't start\n";
+ grep (/Invalid join test done/, @output) or die "Test didn't complete\n";
+}
+
+sub grade_join_no {
+ my (@output) = @_;
+ verify_common (@output);
+ grep (/Testing no join/, @output) or die "Test didn't start\n";
+ grep (/No join test done/, @output) or die "Test didn't complete\n";
+}
+
+sub grade_join_multiple {
+ my (@output) = @_;
+
+ verify_common (@output);
+ my (@t);
+ $t[4] = $t[5] = $t[6] = -1;
+ local ($_);
+ foreach (@output) {
+ my ($idx) = /^Thread (\d+)/ or next;
+ my ($iter) = /iteration (\d+)$/;
+ $iter = 5 if /done!$/;
+ die "Malformed output\n" if !defined $iter;
+ if ($idx == 6) {
+ die "Thread 6 started before either other thread finished\n"
+ if $t[4] < 5 && $t[5] < 5;
+ die "Thread 6 started before thread 4 finished\n"
+ if $t[4] < 5;
+ die "Thread 6 started before thread 5 finished\n"
+ if $t[5] < 5;
+ }
+ die "Thread $idx out of order output\n" if $t[$idx] != $iter - 1;
+ $t[$idx] = $iter;
+ }
+
+ my ($err) = "";
+ for my $idx (4, 5, 6) {
+ if ($t[$idx] == -1) {
+ $err .= "Thread $idx did not run at all\n";
+ } elsif ($t[$idx] != 5) {
+ $err .= "Thread $idx only completed $t[$idx] iterations\n";
+ }
+ }
+ die $err if $err ne '';
+}
+
+sub grade_priority_fifo {
+ my (@output) = @_;
+
+ verify_common (@output);
+ my ($thread_cnt) = 10;
+ my ($iter_cnt) = 5;
+ my (@order);
+ my (@t) = (-1) x $thread_cnt;
+ local ($_);
+ foreach (@output) {
+ my ($idx) = /^Thread (\d+)/ or next;
+ my ($iter) = /iteration (\d+)$/;
+ $iter = $iter_cnt if /done!$/;
+ die "Malformed output\n" if !defined $iter;
+ if (@order < $thread_cnt) {
+ push (@order, $idx);
+ die "Thread $idx repeated within first $thread_cnt iterations: "
+ . join (' ', @order) . ".\n"
+ if grep ($_ == $idx, @order) != 1;
+ } else {
+ die "Thread $idx ran when $order[0] should have.\n"
+ if $idx != $order[0];
+ push (@order, shift @order);
+ }
+ die "Thread $idx out of order output.\n" if $t[$idx] != $iter - 1;
+ $t[$idx] = $iter;
+ }
+
+ my ($err) = "";
+ for my $idx (0..$#t) {
+ if ($t[$idx] == -1) {
+ $err .= "Thread $idx did not run at all.\n";
+ } elsif ($t[$idx] != $iter_cnt) {
+ $err .= "Thread $idx only completed $t[$idx] iterations.\n";
+ }
+ }
+ die $err if $err ne '';
+}
+
+sub grade_mlfqs_on {
+ my (@output) = @_;
+ verify_common (@output);
+ our (@mlfqs_on_stats) = mlfqs_stats (@output);
+}
+
+sub grade_mlfqs_off {
+ my (@output) = @_;
+ verify_common (@output);
+ our (@mlfqs_off_stats) = mlfqs_stats (@output);
+}
+
+sub grade_mlfqs_speedup {
+ our (@mlfqs_off_stats);
+ our (@mlfqs_on_stats);
+ eval {
+ check_mlfqs ();
+ my ($off_ticks) = $mlfqs_off_stats[1];
+ my ($on_ticks) = $mlfqs_on_stats[1];
+ die "$off_ticks ticks without MLFQS, $on_ticks with MLFQS\n"
+ if $on_ticks >= $off_ticks;
+ die "ok\n";
+ };
+ chomp $@;
+ $result{'mlfqs-speedup'} = $@;
+}
+
+sub grade_mlfqs_priority {
+ our (@mlfqs_off_stats);
+ our (@mlfqs_on_stats);
+ eval {
+ check_mlfqs () if !defined (@mlfqs_on_stats);
+ for my $cat qw (CPU IO MIX) {
+ die "Priority changed away from PRI_DEFAULT (29) without MLFQS\n"
+ if $mlfqs_off_stats[0]{$cat}{MIN} != 29
+ || $mlfqs_off_stats[0]{$cat}{MAX} != 29;
+ die "Minimum priority never changed from PRI_DEFAULT (29) "
+ . "with MLFQS\n"
+ if $mlfqs_on_stats[0]{$cat}{MIN} == 29;
+ die "Maximum priority never changed from PRI_DEFAULT (29) "
+ . "with MLFQS\n"
+ if $mlfqs_on_stats[0]{$cat}{MAX} == 29;
+ }
+ die "ok\n";
+ };
+ chomp $@;
+ $result{'mlfqs-priority'} = $@;
+}
+
+sub check_mlfqs {
+ our (@mlfqs_off_stats);
+ our (@mlfqs_on_stats);
+ die "p1-4 didn't finish with MLFQS on or off\n"
+ if !defined (@mlfqs_off_stats) && !defined (@mlfqs_on_stats);
+ die "p1-4 didn't finish with MLFQS on\n"
+ if !defined (@mlfqs_on_stats);
+ die "p1-4 didn't finish with MLFQS off\n"
+ if !defined (@mlfqs_off_stats);
+}
+
+sub mlfqs_stats {
+ my (@output) = @_;
+ my (%stats) = (CPU => {}, IO => {}, MIX => {});
+ my (%map) = ("CPU intensive" => 'CPU',
+ "IO intensive" => 'IO',
+ "Alternating IO/CPU" => 'MIX');
+ my (%rmap) = reverse %map;
+ my ($ticks);
+ local ($_);
+ foreach (@output) {
+ $ticks = $1 if /Timer: (\d+) ticks/;
+ my ($thread, $pri) = /^([A-Za-z\/ ]+): (\d+)$/ or next;
+ my ($t) = $map{$thread} or next;
+
+ my ($s) = $stats{$t};
+ $$s{N}++;
+ $$s{SUM} += $pri;
+ $$s{SUM2} += $pri * $pri;
+ $$s{MIN} = $pri if !defined ($$s{MIN}) || $pri < $$s{MIN};
+ $$s{MAX} = $pri if !defined ($$s{MAX}) || $pri > $$s{MAX};
+ }
+
+ my (%expect_n) = (CPU => 5000, IO => 1000, MIX => 12000);
+ for my $cat (values (%map)) {
+ my ($s) = $stats{$cat};
+ die "$rmap{$cat} printed $$s{N} times, not $expect_n{$cat}\n"
+ if $$s{N} != $expect_n{$cat};
+ die "$rmap{$cat} priority dropped to $$s{MIN}, below PRI_MIN (0)\n"
+ if $$s{MIN} < 0;
+ die "$rmap{$cat} priority rose to $$s{MAX}, above PRI_MAX (59)\n"
+ if $$s{MAX} > 59;
+ $$s{MEAN} = $$s{SUM} / $$s{N};
+ }
+
+ return (\%stats, $ticks);
+}
+\f
+sub verify_common {
+ my (@output) = @_;
+
+ my (@assertion) = grep (/PANIC/, @output);
+ if (@assertion != 0) {
+ my ($details) = "Kernel panic:\n $assertion[0]\n";
+
+ my (@stack_line) = grep (/Call stack:/, @output);
+ if (@stack_line != 0) {
+ $details .= " $stack_line[0]\n\n";
+ $details .= "Translation of backtrace:\n";
+ my (@addrs) = $stack_line[0] =~ /Call stack:((?: 0x[0-9a-f]+)+)/;
+
+ my ($A2L);
+ if (`uname -m`
+ =~ /i.86|pentium.*|[pk][56]|nexgen|viac3|6x86|athlon.*/) {
+ $A2L = "addr2line";
+ } else {
+ $A2L = "i386-elf-addr2line";
+ }
+ open (A2L, "$A2L -fe output/$test/kernel.o @addrs|");
+ for (;;) {
+ my ($function, $line);
+ last unless defined ($function = <A2L>);
+ $line = <A2L>;
+ chomp $function;
+ chomp $line;
+ $details .= " $function ($line)\n";
+ }
+ }
+ $extra{$test} = $details;
+ die "Kernel panic. Details at end of file.\n"
+ }
+
+ die "No output at all\n" if @output == 0;
+ die "Didn't start up properly: no \"Pintos booting\" startup message\n"
+ if !grep (/Pintos booting with.*kB RAM\.\.\./, @output);
+ die "Didn't start up properly: no \"Boot complete\" startup message\n"
+ if !grep (/Boot complete/, @output);
+ die "Didn't shut down properly: no \"Timer: # ticks\" shutdown message\n"
+ if !grep (/Timer: \d+ ticks/, @output);
+ die "Didn't shut down properly: no \"Powering off\" shutdown message\n"
+ if !grep (/Powering off/, @output);