X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=solutions%2Fp1-3.patch;h=7e111db878dae8057e8d8616707582d5d5d7f8b3;hb=cfbade23277061d4ab0d26a2fb350b98657e7302;hp=db95713f1b58e22c35afc8435e9a75da0d767903;hpb=f80f136740163b8d910db6e804ce60f8e6313cf8;p=pintos-anon diff --git a/solutions/p1-3.patch b/solutions/p1-3.patch index db95713..7e111db 100644 --- a/solutions/p1-3.patch +++ b/solutions/p1-3.patch @@ -1,36 +1,3 @@ -? threads.1 -Index: Make.config -=================================================================== -RCS file: /u/blp/cvs/pintos/src/Make.config,v -retrieving revision 1.2 -diff -u -p -u -r1.2 Make.config ---- Make.config 20 Sep 2004 04:27:28 -0000 1.2 -+++ Make.config 11 Oct 2004 07:29:34 -0000 -@@ -23,7 +23,7 @@ CAT = cat - - # Compiler and assembler invocation. - WARNINGS = -Wall -W -Wstrict-prototypes -Wmissing-prototypes -Wsystem-headers --CFLAGS = -g -O3 -MMD -msoft-float -+CFLAGS = -g -MMD -msoft-float - ASFLAGS = -Wa,--gstabs -MMD - - %.o: %.c -Index: devices/timer.c -=================================================================== -RCS file: /u/blp/cvs/pintos/src/devices/timer.c,v -retrieving revision 1.15 -diff -u -p -u -r1.15 timer.c ---- devices/timer.c 6 Oct 2004 18:27:00 -0000 1.15 -+++ devices/timer.c 11 Oct 2004 07:29:34 -0000 -@@ -109,6 +109,8 @@ timer_interrupt (struct intr_frame *args - { - ticks++; - thread_tick (); -+#if 0 - if (ticks % TIME_SLICE == 0) - intr_yield_on_return (); -+#endif - } Index: threads/synch.c =================================================================== RCS file: /u/blp/cvs/pintos/src/threads/synch.c,v @@ -147,210 +114,9 @@ diff -u -p -u -r1.14 synch.c intr_set_level (old_level); } -Index: threads/test.c -=================================================================== -RCS file: /u/blp/cvs/pintos/src/threads/test.c,v -retrieving revision 1.4 -diff -u -p -u -r1.4 test.c ---- threads/test.c 17 Sep 2004 06:52:27 -0000 1.4 -+++ threads/test.c 11 Oct 2004 07:29:34 -0000 -@@ -1,110 +1,109 @@ -+/* Problem 1-3: Priority Scheduling tests. -+ -+ Based on a test originally submitted for Stanford's CS 140 in -+ winter 1999 by by Matt Franklin -+ , Greg Hutchins -+ , Yu Ping Hu . -+ Modified by arens. */ -+ - #include "threads/test.h" - #include - #include "threads/synch.h" - #include "threads/thread.h" --#include "devices/timer.h" - --static void test_sleep (int iterations); -+static void test_preempt (void); -+static void test_fifo (void); -+static void test_donate_return (void); - - void - test (void) - { -- test_sleep (1); -- test_sleep (7); -+ /* Make sure our prority is the default. */ -+ ASSERT (thread_get_priority () == PRI_DEFAULT); -+ -+ //test_preempt (); -+ //test_fifo (); -+ test_donate_return (); - } - --/* Based on a test originally submitted for Stanford's CS 140 in -- winter 1998 by Rob Baesman , Ben -- Taskar , and Toli Kuznets -- . */ --struct sleep_thread_data -- { -- int64_t start; /* Start time. */ -- int duration; /* Number of ticks to sleep. */ -- int iterations; /* Number of iterations to run. */ -- int *product; /* Largest product so far. */ -- struct lock *lock; /* Lock on access to `product'. */ -- struct semaphore done; /* Completion semaphore. */ -- tid_t tid; /* Thread ID. */ -- }; -+static thread_func simple_thread_func; -+static thread_func acquire_thread_func; - --static void sleeper (void *); -+static void -+test_preempt (void) -+{ -+ printf ("\n" -+ "Testing priority preemption.\n"); -+ thread_create ("high-priority", PRI_DEFAULT + 1, simple_thread_func, NULL); -+ printf ("The high-priority thread should have already completed.\n" -+ "Priority preemption test done.\n"); -+} - - static void --test_sleep (int iterations) -+test_fifo (void) - { -- struct sleep_thread_data threads[5]; -- const int thread_cnt = sizeof threads / sizeof *threads; -- struct lock lock; -- int64_t start; -- int product; - int i; -- -+ - printf ("\n" -- "Testing %d sleeps per thread.\n" -- "If successful, product of iteration count and\n" -- "sleep duration will appear in nondescending order.\n", -- iterations); -- -- /* Start all the threads. */ -- product = 0; -- lock_init (&lock, "product"); -- start = timer_ticks (); -- for (i = 0; i < thread_cnt; i++) -+ "Testing FIFO preemption.\n" -+ "5 threads will iterate 10 times in the same order each time.\n" -+ "If the order varies then there is a bug.\n"); -+ -+ thread_set_priority (PRI_DEFAULT + 2); -+ for (i = 0; i < 5; i++) - { -- struct sleep_thread_data *t; - char name[16]; -- -- snprintf (name, sizeof name, "thread %d", i); -- t = threads + i; -- t->start = start; -- t->duration = (i + 1) * 10; -- t->iterations = iterations; -- t->product = &product; -- t->lock = &lock; -- sema_init (&t->done, 0, name); -- t->tid = thread_create (name, PRI_DEFAULT, sleeper, t); -- } -- -- /* Wait for all the threads to finish. */ -- for (i = 0; i < thread_cnt; i++) -- { --#ifdef THREAD_JOIN_IMPLEMENTED -- thread_join (threads[i].tid); --#else -- sema_down (&threads[i].done); --#endif -+ snprintf (name, sizeof name, "%d", i); -+ thread_create (name, PRI_DEFAULT + 1, simple_thread_func, NULL); - } -+ thread_set_priority (PRI_DEFAULT); - -- printf ("...done\n"); -+ printf ("FIFO preemption test done.\n"); - } - - static void --sleeper (void *t_) -+test_donate_return (void) - { -- struct sleep_thread_data *t = t_; -- int i; -+ struct lock lock; - -- for (i = 1; i <= t->iterations; i++) -- { -- int old_product; -- int new_product = i * t->duration; -+ printf ("\n" -+ "Testing priority donation.\n" -+ "If the statements printed below are all true, you pass.\n"); - -- timer_sleep ((t->start + new_product) - timer_ticks ()); -+ lock_init (&lock, "donor"); -+ lock_acquire (&lock); -+ thread_create ("acquire1", PRI_DEFAULT + 1, acquire_thread_func, &lock); -+ printf ("This thread should have priority %d. Actual priority: %d.\n", -+ PRI_DEFAULT + 1, thread_get_priority ()); -+ thread_create ("acquire2", PRI_DEFAULT + 2, acquire_thread_func, &lock); -+ printf ("This thread should have priority %d. Actual priority: %d.\n", -+ PRI_DEFAULT + 2, thread_get_priority ()); -+ lock_release (&lock); -+ printf ("acquire2 and 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"); -+} - -- lock_acquire (t->lock); -- old_product = *t->product; -- *t->product = new_product; -- lock_release (t->lock); -- -- printf ("%s: duration=%d, iteration=%d, product=%d\n", -- thread_name (), t->duration, i, new_product); -- -- if (old_product > new_product) -- printf ("%s: Out of order sleep completion (%d > %d)!\n", -- thread_name (), old_product, new_product); -- } -+static void -+simple_thread_func (void *aux UNUSED) -+{ -+ int i; - -- /* Signal completion. */ -- sema_up (&t->done); -+ for (i = 0; i < 5; i++) -+ { -+ printf ("Thread %s iteration %d\n", thread_name (), i); -+ thread_yield (); -+ } -+ printf ("Thread %s done!\n", thread_name ()); -+} -+ -+static void -+acquire_thread_func (void *lock_) -+{ -+ struct lock *lock = lock_; -+ -+ lock_acquire (lock); -+ printf ("%s: got the lock\n", thread_name ()); -+ lock_release (lock); -+ printf ("%s: done\n", thread_name ()); - } -Index: threads/thread.c -=================================================================== -RCS file: /u/blp/cvs/pintos/src/threads/thread.c,v -retrieving revision 1.48 -diff -u -p -u -r1.48 thread.c +diff -u -p -u -p -r1.48 thread.c --- threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48 -+++ threads/thread.c 11 Oct 2004 07:29:35 -0000 ++++ threads/thread.c 14 Oct 2004 05:21:08 -0000 @@ -166,6 +166,8 @@ thread_create (const char *name, int pri /* Add to run queue. */ @@ -386,7 +152,7 @@ diff -u -p -u -r1.48 thread.c t->status = THREAD_READY; intr_set_level (old_level); } -@@ -266,11 +278,33 @@ thread_yield (void) +@@ -266,11 +278,44 @@ thread_yield (void) ASSERT (!intr_context ()); old_level = intr_disable (); @@ -401,11 +167,22 @@ diff -u -p -u -r1.48 thread.c +thread_set_priority (int priority) +{ + struct thread *t = thread_current (); -+ int old_priority = t->priority; -+ t->normal_priority = priority; -+ if (t->normal_priority > t->priority) -+ t->priority = t->normal_priority; -+ if (priority < old_priority) ++ int old_priority, new_priority; ++ list_elem *e; ++ ++ old_priority = t->priority; ++ new_priority = t->normal_priority = priority; ++ for (e = list_begin (&t->donors); e != list_end (&t->donors); ++ e = list_next (e)) ++ { ++ struct thread *donor = list_entry (e, struct thread, donor_elem); ++ if (donor->priority > t->priority) ++ new_priority = donor->priority; ++ } ++ ++ t->priority = new_priority; ++ ++ if (new_priority < old_priority) + { + /* FIXME: if this is still (one of) the highest priority + threads then don't yield. */ @@ -421,7 +198,7 @@ diff -u -p -u -r1.48 thread.c /* Idle thread. Executes when no other thread is ready to run. */ static void -@@ -335,8 +369,9 @@ init_thread (struct thread *t, const cha +@@ -335,8 +380,9 @@ init_thread (struct thread *t, const cha t->status = THREAD_BLOCKED; strlcpy (t->name, name, sizeof t->name); t->stack = (uint8_t *) t + PGSIZE;