From bf1a64b2f21bd6035d955951dd97239953cf4538 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Thu, 21 Oct 2004 00:45:06 +0000 Subject: [PATCH] Final updates for grading project 1. --- grading/threads/alarm-multiple.c | 58 ++++++++++++------- grading/threads/alarm-single.c | 19 ++----- grading/threads/priority-donate-multiple.c | 20 +++---- grading/threads/priority-donate-multiple.exp | 20 +++---- grading/threads/priority-donate-nest.c | 20 +++---- grading/threads/priority-donate-nest.exp | 20 +++---- grading/threads/priority-donate-one.c | 16 +++--- grading/threads/priority-donate-one.exp | 16 +++--- grading/threads/priority-fifo.c | 60 +++++++++++++------- grading/threads/run-tests | 55 +++++++++--------- 10 files changed, 163 insertions(+), 141 deletions(-) diff --git a/grading/threads/alarm-multiple.c b/grading/threads/alarm-multiple.c index ac42fb3..3d30af2 100644 --- a/grading/threads/alarm-multiple.c +++ b/grading/threads/alarm-multiple.c @@ -31,10 +31,10 @@ struct sleep_thread_data int iterations; /* Number of iterations to run. */ struct semaphore done; /* Completion semaphore. */ tid_t tid; /* Thread ID. */ + int id; /* Sleeper ID. */ - struct lock *lock; /* Lock on access to remaining members. */ - int *product; /* Largest product so far. */ - char **out; /* Output pointer. */ + struct lock *lock; /* Lock on access to `op'. */ + int **op; /* Output buffer position. */ }; static void sleeper (void *); @@ -44,7 +44,7 @@ test_sleep (int iterations) { struct sleep_thread_data threads[5]; const int thread_cnt = sizeof threads / sizeof *threads; - char *output, *cp; + int *output, *op; struct lock lock; int64_t start; int product; @@ -59,7 +59,7 @@ test_sleep (int iterations) /* Start all the threads. */ product = 0; lock_init (&lock, "product"); - cp = output = malloc (128 * iterations * thread_cnt); + op = output = malloc (sizeof *output * iterations * thread_cnt * 2); ASSERT (output != NULL); start = timer_ticks (); for (i = 0; i < thread_cnt; i++) @@ -74,17 +74,42 @@ test_sleep (int iterations) t->iterations = iterations; sema_init (&t->done, 0, name); t->tid = thread_create (name, PRI_DEFAULT, sleeper, t); + t->id = i; t->lock = &lock; - t->product = &product; - t->out = &cp; + t->op = &op; } /* Wait for all the threads to finish. */ for (i = 0; i < thread_cnt; i++) - sema_down (&threads[i].done); + { + sema_down (&threads[i].done); + threads[i].iterations = 1; + } + + /* Print output buffer. */ + product = 0; + for (; output < op; output++) + { + struct sleep_thread_data *t; + int new_prod; + + ASSERT (*output >= 0 && *output < thread_cnt); + t = threads + *output; + + new_prod = t->iterations++ * t->duration; + + printf ("thread %d: duration=%d, iteration=%d, product=%d\n", + t->id, t->duration, t->iterations, new_prod); + + if (new_prod >= product) + product = new_prod; + else + printf ("thread %d: Out of order sleep completion (%d > %d)!\n", + t->id, product, new_prod); + } - printf ("%s...done\n", output); + printf ("...done\n"); } static void @@ -95,21 +120,10 @@ sleeper (void *t_) for (i = 1; i <= t->iterations; i++) { - int old_product; - int new_product = i * t->duration; - - timer_sleep ((t->start + new_product) - timer_ticks ()); + timer_sleep ((t->start + i * t->duration) - timer_ticks ()); lock_acquire (t->lock); - old_product = *t->product; - *t->product = new_product; - *t->out += snprintf (*t->out, 128, - "%s: duration=%d, iteration=%d, product=%d\n", - thread_name (), t->duration, i, new_product); - if (old_product > new_product) - *t->out += snprintf (*t->out, 128, - "%s: Out of order sleep completion (%d > %d)!\n", - thread_name (), old_product, new_product); + *(*t->op)++ = t->id; lock_release (t->lock); } diff --git a/grading/threads/alarm-single.c b/grading/threads/alarm-single.c index fabf420..8acef92 100644 --- a/grading/threads/alarm-single.c +++ b/grading/threads/alarm-single.c @@ -33,8 +33,8 @@ struct sleep_thread_data tid_t tid; /* Thread ID. */ int id; /* Sleeper ID. */ - struct lock *lock; /* Lock on access to `out'. */ - int **out; /* Output buffer. */ + struct lock *lock; /* Lock on access to `op'. */ + int **op; /* Output buffer position. */ }; static void sleeper (void *); @@ -77,7 +77,7 @@ test_sleep (int iterations) t->id = i; t->lock = &lock; - t->out = &op; + t->op = &op; } /* Wait for all the threads to finish. */ @@ -109,7 +109,7 @@ test_sleep (int iterations) t->id, product, new_prod); } - printf ("...done\n", output); + printf ("...done\n"); } static void @@ -120,20 +120,13 @@ sleeper (void *t_) for (i = 1; i <= t->iterations; i++) { - int old_product; - int new_product = i * t->duration; - - timer_sleep ((t->start + new_product) - timer_ticks ()); + timer_sleep ((t->start + i * t->duration) - timer_ticks ()); lock_acquire (t->lock); - *t->op++ = t->id; + *(*t->op)++ = t->id; lock_release (t->lock); } - lock_acquire (t->lock); - *t->op++ = t->id; - lock_release (t->lock); - /* Signal completion. */ sema_up (&t->done); } diff --git a/grading/threads/priority-donate-multiple.c b/grading/threads/priority-donate-multiple.c index 07d9684..a00447e 100644 --- a/grading/threads/priority-donate-multiple.c +++ b/grading/threads/priority-donate-multiple.c @@ -45,21 +45,21 @@ test_donate_multiple (void) lock_acquire (&b); thread_create ("a", PRI_DEFAULT + 1, a_thread_func, &a); - printf (" 1. Main thread should have priority %d. Actual priority: %d.\n", + printf ("Main thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT + 1, thread_get_priority ()); thread_create ("b", PRI_DEFAULT + 2, b_thread_func, &b); - printf (" 2. Main thread should have priority %d. Actual priority: %d.\n", + printf ("Main thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT + 2, thread_get_priority ()); lock_release (&b); - printf (" 5. Thread b should have just finished.\n"); - printf (" 6. Main thread should have priority %d. Actual priority: %d.\n", + printf ("Thread b should have just finished.\n"); + printf ("Main thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT + 1, thread_get_priority ()); lock_release (&a); - printf (" 9. Thread a should have just finished.\n"); - printf ("10. Main thread should have priority %d. Actual priority: %d.\n", + printf ("Thread a should have just finished.\n"); + printf ("Main thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT, thread_get_priority ()); printf ("Multiple priority priority donation test finished.\n"); } @@ -70,9 +70,9 @@ a_thread_func (void *lock_) struct lock *lock = lock_; lock_acquire (lock); - printf (" 7. Thread a acquired lock a.\n"); + printf ("Thread a acquired lock a.\n"); lock_release (lock); - printf (" 8. Thread a finished.\n"); + printf ("Thread a finished.\n"); } static void @@ -81,7 +81,7 @@ b_thread_func (void *lock_) struct lock *lock = lock_; lock_acquire (lock); - printf (" 3. Thread b acquired lock b.\n"); + printf ("Thread b acquired lock b.\n"); lock_release (lock); - printf (" 4. Thread b finished.\n"); + printf ("Thread b finished.\n"); } diff --git a/grading/threads/priority-donate-multiple.exp b/grading/threads/priority-donate-multiple.exp index b92bdee..aaff85e 100644 --- a/grading/threads/priority-donate-multiple.exp +++ b/grading/threads/priority-donate-multiple.exp @@ -1,13 +1,13 @@ Testing multiple priority donation. If the statements printed below are all true, you pass. - 1. Main thread should have priority 30. Actual priority: 30. - 2. Main thread should have priority 31. Actual priority: 31. - 3. Thread b acquired lock b. - 4. Thread b finished. - 5. Thread b should have just finished. - 6. Main thread should have priority 30. Actual priority: 30. - 7. Thread a acquired lock a. - 8. Thread a finished. - 9. Thread a should have just finished. -10. Main thread should have priority 29. Actual priority: 29. +Main thread should have priority 30. Actual priority: 30. +Main thread should have priority 31. Actual priority: 31. +Thread b acquired lock b. +Thread b finished. +Thread b should have just finished. +Main thread should have priority 30. Actual priority: 30. +Thread a acquired lock a. +Thread a finished. +Thread a should have just finished. +Main thread should have priority 29. Actual priority: 29. Multiple priority priority donation test finished. diff --git a/grading/threads/priority-donate-nest.c b/grading/threads/priority-donate-nest.c index 1d145f3..73c7866 100644 --- a/grading/threads/priority-donate-nest.c +++ b/grading/threads/priority-donate-nest.c @@ -54,18 +54,18 @@ test_donate_nest (void) locks.b = &b; thread_create ("medium", PRI_DEFAULT + 1, medium_thread_func, &locks); thread_yield (); - printf (" 1. Low thread should have priority %d. Actual priority: %d.\n", + printf ("Low thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT + 1, thread_get_priority ()); thread_create ("high", PRI_DEFAULT + 2, high_thread_func, &b); thread_yield (); - printf (" 2. Low thread should have priority %d. Actual priority: %d.\n", + printf ("Low thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT + 2, thread_get_priority ()); lock_release (&a); thread_yield (); - printf (" 9. Medium thread should just have finished.\n"); - printf ("10. Low thread should have priority %d. Actual priority: %d.\n", + printf ("Medium thread should just have finished.\n"); + printf ("Low thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT, thread_get_priority ()); printf ("Nested priority priority donation test finished.\n"); } @@ -78,9 +78,9 @@ medium_thread_func (void *locks_) lock_acquire (locks->b); lock_acquire (locks->a); - printf (" 3. Medium thread should have priority %d. Actual priority: %d.\n", + printf ("Medium thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT + 2, thread_get_priority ()); - printf (" 4. Medium thread got the lock.\n"); + printf ("Medium thread got the lock.\n"); lock_release (locks->a); thread_yield (); @@ -88,8 +88,8 @@ medium_thread_func (void *locks_) lock_release (locks->b); thread_yield (); - printf (" 7. High thread should have just finished.\n"); - printf (" 8. Middle thread finished.\n"); + printf ("High thread should have just finished.\n"); + printf ("Middle thread finished.\n"); } static void @@ -98,7 +98,7 @@ high_thread_func (void *lock_) struct lock *lock = lock_; lock_acquire (lock); - printf (" 5. High thread got the lock.\n"); + printf ("High thread got the lock.\n"); lock_release (lock); - printf (" 6. High thread finished.\n"); + printf ("High thread finished.\n"); } diff --git a/grading/threads/priority-donate-nest.exp b/grading/threads/priority-donate-nest.exp index 66de83f..d6e496c 100644 --- a/grading/threads/priority-donate-nest.exp +++ b/grading/threads/priority-donate-nest.exp @@ -1,13 +1,13 @@ Testing nested priority donation. If the statements printed below are all true, you pass. - 1. Low thread should have priority 30. Actual priority: 30. - 2. Low thread should have priority 31. Actual priority: 31. - 3. Medium thread should have priority 31. Actual priority: 31. - 4. Medium thread got the lock. - 5. High thread got the lock. - 6. High thread finished. - 7. High thread should have just finished. - 8. Middle thread finished. - 9. Medium thread should just have finished. -10. Low thread should have priority 29. Actual priority: 29. +Low thread should have priority 30. Actual priority: 30. +Low thread should have priority 31. Actual priority: 31. +Medium thread should have priority 31. Actual priority: 31. +Medium thread got the lock. +High thread got the lock. +High thread finished. +High thread should have just finished. +Middle thread finished. +Medium thread should just have finished. +Low thread should have priority 29. Actual priority: 29. Nested priority priority donation test finished. diff --git a/grading/threads/priority-donate-one.c b/grading/threads/priority-donate-one.c index 0f84e09..35f135c 100644 --- a/grading/threads/priority-donate-one.c +++ b/grading/threads/priority-donate-one.c @@ -41,14 +41,14 @@ test_donate_return (void) lock_init (&lock, "donor"); lock_acquire (&lock); thread_create ("acquire1", PRI_DEFAULT + 1, acquire1_thread_func, &lock); - printf ("1. This thread should have priority %d. Actual priority: %d.\n", + printf ("This thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT + 1, thread_get_priority ()); thread_create ("acquire2", PRI_DEFAULT + 2, acquire2_thread_func, &lock); - printf ("2. This thread should have priority %d. Actual priority: %d.\n", + printf ("This thread should have priority %d. Actual priority: %d.\n", PRI_DEFAULT + 2, thread_get_priority ()); lock_release (&lock); - printf ("7. acquire2, acquire1 must already have finished, in that order.\n" - "8. This should be the last line before finishing this test.\n" + printf ("acquire2, acquire1 must already have finished, in that order.\n" + "This should be the last line before finishing this test.\n" "Priority donation test done.\n"); } @@ -58,9 +58,9 @@ acquire1_thread_func (void *lock_) struct lock *lock = lock_; lock_acquire (lock); - printf ("5. acquire1: got the lock\n"); + printf ("acquire1: got the lock\n"); lock_release (lock); - printf ("6. acquire1: done\n"); + printf ("acquire1: done\n"); } static void @@ -69,7 +69,7 @@ acquire2_thread_func (void *lock_) struct lock *lock = lock_; lock_acquire (lock); - printf ("3. acquire2: got the lock\n"); + printf ("acquire2: got the lock\n"); lock_release (lock); - printf ("4. acquire2: done\n"); + printf ("acquire2: done\n"); } diff --git a/grading/threads/priority-donate-one.exp b/grading/threads/priority-donate-one.exp index 01f86d5..a178523 100644 --- a/grading/threads/priority-donate-one.exp +++ b/grading/threads/priority-donate-one.exp @@ -1,11 +1,11 @@ Testing priority donation. If the statements printed below are all true, you pass. -1. This thread should have priority 30. Actual priority: 30. -2. This thread should have priority 31. Actual priority: 31. -3. acquire2: got the lock -4. acquire2: done -5. acquire1: got the lock -6. acquire1: done -7. acquire2, acquire1 must already have finished, in that order. -8. This should be the last line before finishing this test. +This thread should have priority 30. Actual priority: 30. +This thread should have priority 31. Actual priority: 31. +acquire2: got the lock +acquire2: done +acquire1: got the lock +acquire1: done +acquire2, acquire1 must already have finished, in that order. +This should be the last line before finishing this test. Priority donation test done. diff --git a/grading/threads/priority-fifo.c b/grading/threads/priority-fifo.c index b49ff5d..6f8fa9b 100644 --- a/grading/threads/priority-fifo.c +++ b/grading/threads/priority-fifo.c @@ -12,6 +12,7 @@ #include "threads/test.h" #include +#include "devices/timer.h" #include "threads/malloc.h" #include "threads/synch.h" #include "threads/thread.h" @@ -31,42 +32,65 @@ static thread_func simple_thread_func; struct simple_thread_data { + int id; /* Sleeper ID. */ + int iterations; /* Iterations so far. */ struct lock *lock; /* Lock on output. */ - char **out; /* Output pointer. */ + int **op; /* Output buffer position. */ }; +#define THREAD_CNT 10 +#define ITER_CNT 5 + static void test_fifo (void) { - struct simple_thread_data data; + struct simple_thread_data data[THREAD_CNT]; struct lock lock; - char *output, *cp; + int *output, *op; int i; printf ("\n" "Testing FIFO preemption.\n" - "10 threads will iterate 5 times in the same order each time.\n" - "If the order varies then there is a bug.\n"); + "%d threads will iterate %d times in the same order each time.\n" + "If the order varies then there is a bug.\n", + THREAD_CNT, ITER_CNT); - output = cp = malloc (5 * 10 * 128); + output = op = malloc (sizeof *output * THREAD_CNT * ITER_CNT * 2); ASSERT (output != NULL); lock_init (&lock, "output"); - data.lock = &lock; - data.out = &cp; - thread_set_priority (PRI_DEFAULT + 2); - for (i = 0; i < 10; i++) + for (i = 0; i < THREAD_CNT; i++) { char name[16]; + struct simple_thread_data *d = data + i; snprintf (name, sizeof name, "%d", i); - thread_create (name, PRI_DEFAULT + 1, simple_thread_func, &data); + d->id = i; + d->iterations = 0; + d->lock = &lock; + d->op = &op; + thread_create (name, PRI_DEFAULT + 1, simple_thread_func, d); } + + /* This should ensure that the iterations start at the + beginning of a timer tick. */ + timer_sleep (10); thread_set_priority (PRI_DEFAULT); lock_acquire (&lock); - *cp = '\0'; - printf ("%sFIFO preemption test done.\n", output); + for (; output < op; output++) + { + struct simple_thread_data *d; + + ASSERT (*output >= 0 && *output < THREAD_CNT); + d = data + *output; + if (d->iterations != ITER_CNT) + printf ("Thread %d iteration %d\n", d->id, d->iterations); + else + printf ("Thread %d done!\n", d->id); + d->iterations++; + } + printf ("FIFO preemption test done.\n"); lock_release (&lock); } @@ -76,17 +100,11 @@ simple_thread_func (void *data_) struct simple_thread_data *data = data_; int i; - for (i = 0; i < 5; i++) + for (i = 0; i <= ITER_CNT; i++) { lock_acquire (data->lock); - *data->out += snprintf (*data->out, 128, "Thread %s iteration %d\n", - thread_name (), i); + *(*data->op)++ = data->id; lock_release (data->lock); thread_yield (); } - - lock_acquire (data->lock); - *data->out += snprintf (*data->out, 128, - "Thread %s done!\n", thread_name ()); - lock_release (data->lock); } diff --git a/grading/threads/run-tests b/grading/threads/run-tests index 462a1ba..94fd802 100755 --- a/grading/threads/run-tests +++ b/grading/threads/run-tests @@ -89,7 +89,11 @@ if ($grade) { print OUT "$p_got points out of $p_pos total\n\n"; print OUT map ("$_\n", @tests), "\n"; - print OUT map ("$_\n", @review); + print OUT map ("$_\n", @review), "\n"; + + print OUT "DETAILS\n"; + print OUT "-------\n\n"; + print OUT map ("$_\n", snarf ("details.out")); exit 0; } @@ -238,6 +242,17 @@ sub really_run_test { close (CONSTANTS); } + # Changes devices/timer.c if necessary. + my ($new_time_slice) = $test eq 'priority-fifo' ? 100 : 1; + my (@timer) = snarf ("pintos/src/devices/timer.c"); + if (!grep (/^\#define TIME_SLICE $new_time_slice$/, @timer)) { + @timer = grep (!/^\#define TIME_SLICE/, @timer); + unshift (@timer, "#define TIME_SLICE $new_time_slice"); + open (TIMER, ">pintos/src/devices/timer.c"); + print TIMER map ("$_\n", @timer); + close (TIMER); + } + # Copy in the new test.c and delete enough files to ensure a full rebuild. my ($src) = test_source ($test); xsystem ("cp $src pintos/src/threads/test.c", DIE => "cp failed\n"); @@ -592,43 +607,25 @@ sub compare_output { } # They differ. Output a diff. - my ($diff) = ""; + my (@diff) = ""; my ($d) = Algorithm::Diff->new (\@expected, \@actual); - $d->Base (1); while ($d->Next ()) { my ($ef, $el, $af, $al) = $d->Get (qw (min1 max1 min2 max2)); if ($d->Same ()) { - if ($af != $al) { - $diff .= "Actual lines $af...$al match expected lines " - . "$ef...$el.\n"; - } else { - $diff .= "Actual line $af matches expected line $ef.\n"; - } + push (@diff, map (" $_", $d->Items (1))); } else { - my (@i1) = $d->Items (1); - my (@i2) = $d->Items (2); - if (!@i1) { - $diff .= "Extra or misplaced line(s) $af...$al " - . "in actual output:\n"; - $diff .= number_lines ($af, \@i2); - } elsif (!$d->Items (2)) { - $diff .= "Expected line(s) $ef...$el missing or misplaced:\n"; - $diff .= number_lines ($ef, \@i1); - } else { - $diff .= "The following expected line(s) $ef...$el:\n"; - $diff .= number_lines ($ef, \@i1); - $diff .= "became actual line(s) $af...$al:\n"; - $diff .= number_lines ($af, \@i2); - } + push (@diff, map ("- $_", $d->Items (1))) if $d->Items (1); + push (@diff, map ("+ $_", $d->Items (2))) if $d->Items (2); } } my ($details) = ""; - $details .= "$test actual output (line numbers added):\n"; - $details .= number_lines (1, \@actual); - $details .= "\n$test expected output (line numbers added):\n"; - $details .= number_lines (1, \@expected); - $details .= "\n$diff\n"; + $details .= "$test actual output:\n"; + $details .= join ('', map (" $_", @actual)); + $details .= "\n$test expected output:\n"; + $details .= join ('', map (" $_", @expected)); + $details .= "\nOutput differences in `diff -u' format:\n"; + $details .= join ('', @diff) . "\n"; $details{$test} = $details; die "Output differs from expected. Details at end of file.\n"; } -- 2.30.2