From da80fdf80c1391c1ac6d878e6a7a13782c6dce35 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sat, 16 Oct 2004 00:06:01 +0000 Subject: [PATCH] Add test scripts. --- grading/threads/join-nested.c | 2 +- grading/threads/join-quick.c | 2 - grading/threads/join-simple.exp | 15 +++ grading/threads/review.txt | 66 ++++++++++ grading/threads/run-tests | 214 ++++++++++++++++++++++++++++++++ grading/threads/tests.txt | 32 +++++ 6 files changed, 328 insertions(+), 3 deletions(-) create mode 100644 grading/threads/join-simple.exp create mode 100644 grading/threads/review.txt create mode 100755 grading/threads/run-tests create mode 100644 grading/threads/tests.txt diff --git a/grading/threads/join-nested.c b/grading/threads/join-nested.c index 18970f0..eb8651f 100644 --- a/grading/threads/join-nested.c +++ b/grading/threads/join-nested.c @@ -29,7 +29,7 @@ nested_test (void) printf ("\n" "Testing nested join.\n" "Threads 0 to 7 should start in numerical order\n" - "and finish in reverse order."); + "and finish in reverse order.\n"); tid0 = thread_create ("0", PRI_DEFAULT, nested_thread_func, &zero); thread_join (tid0); printf ("Simple join test done.\n"); diff --git a/grading/threads/join-quick.c b/grading/threads/join-quick.c index 78f1e3f..7330827 100644 --- a/grading/threads/join-quick.c +++ b/grading/threads/join-quick.c @@ -43,8 +43,6 @@ quick_thread_func (void *name_) const char *name = name_; int i; - intr_disable (); - for (i = 0; i < 5; i++) { printf ("Thread %s iteration %d\n", name, i); diff --git a/grading/threads/join-simple.exp b/grading/threads/join-simple.exp new file mode 100644 index 0000000..844a333 --- /dev/null +++ b/grading/threads/join-simple.exp @@ -0,0 +1,15 @@ +Testing simple join. +Thread 0 should finish before thread 1 starts. +Thread 0 iteration 0 +Thread 0 iteration 1 +Thread 0 iteration 2 +Thread 0 iteration 3 +Thread 0 iteration 4 +Thread 0 done! +Thread 1 iteration 0 +Thread 1 iteration 1 +Thread 1 iteration 2 +Thread 1 iteration 3 +Thread 1 iteration 4 +Thread 1 done! +Simple join test done. diff --git a/grading/threads/review.txt b/grading/threads/review.txt new file mode 100644 index 0000000..3c01e7a --- /dev/null +++ b/grading/threads/review.txt @@ -0,0 +1,66 @@ +DESIGN [[/40] +------------- + + -20 Missing or far too brief DESIGNDOC + -2 Troublesome or unexplained dependencies + -2 Changing interfaces, each (max -6) + +DESIGNDOC (per problem): + -1 Minor details missing + -2 Major details missing + -5 Totally missing + +Problem 1-1: Alarm Clock + -1 Uses lock/interrupt disabling without justifying + -1 Uses a lock inside of CallBack + -3 Busy waiting + -2 Wakes up too often, e.g. by using semaphores with negative values + -1 Traverses entire list of sleeping threads every tick + -1 Put threads to sleep directly + -1 Doesn't protect data structure in CallBack + -1 Doesn't protect data structure in WaitUntil + -3 Bad design + +Problem 1-2: Join + -3 Busy waiting in thread finish when waiting on the parent's join + -3 A static list of all parent-child pairs is extremely wasteful + -3 Obviously wasteful with memory (not deleting threads) + -2 Finished parent deletes children which may still be running + -1 Enable/disable interrupts or put thread to sleep directly + -2 Joinable child lets its Thread object be deleted before parent dies + -1 Race condition between join and thread exit + +Problem 1-3: Priority Scheduler + -3 Doesn't use sorted queue scheduler, and don't justify why they didn't + -1 Semaphores don't wake highest-priority thread first + -1 Condition variables don't wake highest-priority thread first + -1 Should use sorted queue in semaphores, unless explained in DESIGNDOC + -1 Should use sorted queue in conditions, unless explained in DESIGNDOC + -2 Yield should pick the highest-priority thread (including current) + -3 Bad design + +2 Used a heap or other advanced priority queue for ready_list + +Problem 1-4: Advanced Scheduler + -2 Isn't table-driven + -5 Bad design + + +TESTCASES [[/10] +---------------- + -2 Problem 1-1: no test cases/no test output/no description in TESTCASES + -1 Problem 1-1: not enough testing/inconclusive test output + -2 Problem 1-2: no test cases/no test output/no description in TESTCASES + -1 Problem 1-2: not enough testing/inconclusive test output + -2 Problem 1-3: no test cases/no test output/no description in TESTCASES + -1 Problem 1-3: not enough testing/inconclusive test output + -2 Problem 1-4: no test cases/no test output/no description in TESTCASES + -1 Problem 1-4: not enough testing/inconclusive test output + + +STYLE [[/10]] +------------- +Insert any comments here + + +COMMENTS +-------- diff --git a/grading/threads/run-tests b/grading/threads/run-tests new file mode 100755 index 0000000..451b6ca --- /dev/null +++ b/grading/threads/run-tests @@ -0,0 +1,214 @@ +#! /usr/bin/perl -w + +use POSIX; +use Text::Diff; + +$verbose = 0; +($GRADES_DIR = $0) =~ s#/[^/]+$##; +-d $GRADES_DIR or die "$GRADES_DIR: stat: $!\n"; + +-d ("output") || mkdir ("output") or die "output: mkdir: $!\n"; + +if (! -d "pintos") { + my (@tarballs) + = grep (/^[a-z0-9]+\.[A-Za-z]+\.\d+\.\d+\.\d+\.\d+.\d+\.tar\.gz$/, + glob ("*.tar.gz")); + die "no pintos dir and no source tarball\n" if scalar (@tarballs) == 0; + die "no pintos dir and multiple tarballs\n" if scalar (@tarballs) > 1; + mkdir "pintos" or die "pintos: mkdir: $!\n"; + mkdir "pintos/src" or die "pintos: mkdir: $!\n"; + print "Extracting $tarballs[0]...\n"; + xsystem ("", "cd pintos/src && tar xzf ../../$tarballs[0]") + or die "extraction failed\n"; +} +-d "pintos/src/threads" or die "pintos/src/threads: stat: $!\n"; + +print "Compiling initial tree...\n"; +xsystem ("make", "cd pintos/src/threads && make") or die; + +for my $test ("alarm-single", "alarm-multiple", "alarm-zero", "alarm-negative", + "join-simple" + #"join-quick", "join-multiple", "join-nested", + #"join-dummy", "join-invalid", "join-no", + #"priority-preempt", "priority-fifo", "priority-donate-one", + #"priority-donate-multiple", "priority-donate-nest", + #"mlfqs" + ) { + print "Testing $test: "; + my ($result) = run_test ($test); + print "$result\n"; + + if ($result eq 'ok') { + print "Grading $test: "; + $result = grade_test ($test); + print "$result\n"; + } +} + +sub grade_test { + my ($test) = @_; + + my (@output) = snarf ("output/$test.run.out"); + + ($grade_func = $test) =~ s/-/_/g; + eval "grade_$grade_func(\@output)"; + if ($@) { + die $@ if $@ =~ /at \S+ line \d+$/; + return $@; + } + return "ok"; +} + +sub grade_alarm_single { + verify_alarm (1, @_); +} + +sub grade_alarm_multiple { + verify_alarm (7, @_); +} + +sub grade_alarm_zero { + my (@output) = @_; + #verify_common (@output); + die "Crashed in timer_sleep()\n" if !grep (/^Success\.$/, @output); +} + +sub grade_alarm_negative { + my (@output) = @_; + #verify_common (@output); + die "Crashed in timer_sleep()\n" if !grep (/^Success\.$/, @output); +} + +sub grade_join_simple { + my (@output) = @_; + #verify_common (@output); + compare_output ("$GRADES_DIR/join-simple.exp", @output); +} + +sub compare_output { + my ($exp_file, @actual) = @_; + my (@expected) = snarf ($exp_file); + + # Trim header and trailer from @actual. + while (scalar (@actual) && $actual[0] ne $expected[0]) { + shift (@actual); + } + die "First line of expected output was not present.\n" if !@actual; + while (scalar (@actual) && $actual[$#actual] ne $expected[$#expected]) { + pop (@actual); + } + die "Final line of expected output was not present.\n" if !@actual; + + # Check whether they're the same. + if ($#actual == $#expected) { + my ($eq) = 1; + for (my ($i) = 0; $i <= $#expected; $i++) { + $eq = 0 if $actual[$i] ne $expected[$i]; + } + return if $eq; + } + + # They differ. Output a diff. + my (@diff) = split ("\n", diff (\@expected, \@actual, {CONTEXT => 0})); + for (my ($i) = 0; $i < $#diff; ) { + if ($diff[$i] =~ /^@@/) { + if ($i == 0) { + shift (@diff); + } else { + $diff[$i++] = ""; + } + } else { + $i++; + } + } + my ($diff) = join ("\n", @diff); + die "Output differs from expected:\n$diff\n"; +} + +sub verify_alarm { + my ($iterations, @output) = @_; + + #verify_common (@output); + + my (@products); + for (my ($i) = 0; $i < $iterations; $i++) { + for (my ($t) = 0; $t < 5; $t++) { + push (@products, ($i + 1) * ($t + 1) * 10); + } + } + @products = sort {$a <=> $b} @products; + + for $_ (@output) { + die $_ if /Out of order/; + + my ($p) = /product=(\d+)$/; + next if !defined $p; + + my ($q) = shift (@products); + die "Too many wakeups.\n" if !defined $q; + die "Out of order wakeups ($p vs. $q).\n" if $p != $q; # FIXME + } + die scalar (@products) . " fewer wakeups than expected.\n" + if @products != 0; +} + +sub run_test { + my ($test) = @_; + return "ok" if -f "output/$test.run.out"; + + my ($src) = "$GRADES_DIR/$test.c"; + -e $src or die "$src: stat: $!\n"; + xsystem ("", "cp $src pintos/src/threads/test.c") or die; + unlink ("pintos/src/threads/build/threads/test.o"); + unlink ("pintos/src/threads/build/kernel.o"); + unlink ("pintos/src/threads/build/kernel.bin"); + unlink ("pintos/src/threads/build/os.dsk"); + xsystem ("$test.make", "cd pintos/src/threads && make") + or return "compile error"; + xsystem ("$test.run", "cd pintos/src/threads/build && pintos -v run -q") + or return "Bochs error"; + return "ok"; +} + +sub xsystem { + my ($log, $command) = @_; + print "$command\n" if $verbose; + + my ($status); + if ($log ne '') { + $status = systimeout ("($command) >output/$log.out 2>output/$log.err"); + unlink ("output/$log.err") unless $status != 0; + } else { + $status = systimeout ($command); + } + + die "Interrupted\n" + if WIFSIGNALED ($status) && WTERMSIG ($status) == SIGINT; + + return $status == 0; +} + +sub systimeout { + my ($command) = @_; + my ($status); + eval { + local $SIG{ALRM} = sub { die "alarm\n" }; + alarm 10; + $status = system ($command); + alarm 0; + }; + if ($@) { + die unless $@ eq "alarm\n"; # propagate unexpected errors + print "Timed out.\n"; + $status = -1; + } + return $status; +} + +sub snarf { + my ($file) = @_; + open (OUTPUT, $file) or die "$file: open: $!\n"; + my (@lines) = ; + close (OUTPUT); + return @lines; +} diff --git a/grading/threads/tests.txt b/grading/threads/tests.txt new file mode 100644 index 0000000..6a88292 --- /dev/null +++ b/grading/threads/tests.txt @@ -0,0 +1,32 @@ +CORRECTNESS [[/40]] +------------------- + +Points are taken off for tests that failed. Only failing tests are +listed. + +Problem 1-1: Alarm Clock [[/8]] +[[-3]] alarm-single: Multiple threads each sleep once (public) +[[-3]] alarm-multiple: Multiple threads each sleep many times (public) +[[-1]] alarm-zero: Zero wait time must not crash or hang +[[-1]] alarm-negative: Negative wait time must not crash or hang + +Problem 1-2: Join [[/14]] +[[-2]] join-simple: A creates B, A joins B (public) +[[-2]] join-quick: A creates B, A joins B, with different details (public) +[[-2]] join-multiple: A creates B and C, A joins B, A joins C (public) +[[-2]] join-nested: A creates B, B creates C, ..., B joins C, A joins B +[[-2]] join-dummy: A creates B, A joins B, A joins B +[[-2]] join-invalid: Joining an invalid tid must not crash or hang +[[-2]] join-no: Creating a thread and never joining it must not crash or hang + +Problem 1-3: Priority Scheduler [[/10]] +[[-2]] priority-preempt: Higher-priority thread preempts others (public) +[[-2]] priority-fifo: Threads of equal priority run round-robin (public) +[[-2]] priority-donate-one: Priority donation with single lock (public) +[[-2]] priority-donate-multiple: Priority donation with multiple locks +[[-2]] priority-donate-nest: Nested priority donation with single lock + +Problem 1-4: Advanced Scheduler [[/8] +[[-2]] Public testcase doesn't run faster with MLFQS +[[-2]] Group's own testcase doesn't run faster with MLFQS +[[-4]] Priorities don't change properly -- 2.30.2