From: Ben Pfaff Date: Thu, 31 Mar 2005 04:58:27 +0000 (+0000) Subject: Move problem 1-2 (join) into project 2 as the "wait" system call. X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=commitdiff_plain;h=2cfc156c39840ce7f1cda6b473de1322691a8a0b Move problem 1-2 (join) into project 2 as the "wait" system call. Update the documentation, solutions, grading scripts, and regression tests. In execute_thread(), rephrase the code slightly. Move process_activate() call from execute_thread() to load() to remove potential race condition that students and TAs found confusing. Add memory barrier in process_exit(). --- diff --git a/doc/doc.texi b/doc/doc.texi index 2fec1b4..44f6e7d 100644 --- a/doc/doc.texi +++ b/doc/doc.texi @@ -84,9 +84,7 @@ required, you should explain why you feel so. For each test that you write, explain how we can use them, and show some sample output from a run. -Specifically, here are some pointers for writing @file{TESTCASE} files -which will make them more succinct and us more likely to understand the -tests you write: +Here are some pointers for writing @file{TESTCASE} files: @itemize @bullet @item @@ -95,15 +93,10 @@ Show us that you tested each part of your assignment. @item Clearly state in your @file{TESTCASE} file what each test is supposed to test. You should be testing not only the common case, but testing -corner cases. Specify what criteria or issue is being tested. For -example, in testing @func{thread_join} you would have specified that -you test @func{thread_join} when it is called multiple times on the -same child thread. +corner cases. Specify what criteria or issue is being tested. @item -Make your tests as succinct as possible. Most students in the past -have done a great job with the testing of @func{thread_join}, -creating very succinct short tests. We like that. +Make your tests as succinct as possible. @item Your test cases should be placed in a subdirectory called @@ -133,7 +126,7 @@ Your @file{TESTCASE} file is also where you can show us the improvements that your code makes to the performance of the system. You should be able to show us ``before'' and ``after'' performance data, and explain how the data shows the improvement. For example, -for Problem 1-4, you should show us in the @file{TESTCASE} printouts +for Problem 1-3, you should show us in the @file{TESTCASE} printouts from a workload for the non-Solaris scheduler and the Solaris scheduler and explain why the Solaris scheduler is better. diff --git a/doc/mlfqs.texi b/doc/mlfqs.texi index b9a3186..2e229dc 100644 --- a/doc/mlfqs.texi +++ b/doc/mlfqs.texi @@ -4,7 +4,7 @@ This section gives a brief overview of the behavior of the Solaris 2.6 Time-Sharing (TS) scheduler, an example of a Multilevel Feedback Queue scheduler. The information in this handout, in conjunction with that -given in lecture, should be used to answer Problem 1-4. The end of +given in lecture, should be used to answer Problem 1-3. The end of this document specifies in more detail which aspects of the Solaris scheduler that you should implement. diff --git a/doc/standards.texi b/doc/standards.texi index ab0f01a..a1c70a4 100644 --- a/doc/standards.texi +++ b/doc/standards.texi @@ -80,9 +80,9 @@ There are a few exceptions: @itemize @bullet @item -Problem 1-4, the advanced scheduler. We must be able to turn this on +Problem 1-3, the advanced scheduler. We must be able to turn this on and off with a compile-time directive. You must use the macro name we -specify for that part. @xref{Problem 1-4 Advanced Scheduler}, for +specify for that part. @xref{Problem 1-3 Advanced Scheduler}, for details. @item diff --git a/doc/threads.texi b/doc/threads.texi index 3360039..061c6ee 100644 --- a/doc/threads.texi +++ b/doc/threads.texi @@ -24,9 +24,8 @@ read @ref{Multilevel Feedback Scheduling}. * Debugging versus Testing:: * Tips:: * Problem 1-1 Alarm Clock:: -* Problem 1-2 Join:: -* Problem 1-3 Priority Scheduling:: -* Problem 1-4 Advanced Scheduler:: +* Problem 1-2 Priority Scheduling:: +* Problem 1-3 Advanced Scheduler:: * Threads FAQ:: @end menu @@ -362,27 +361,15 @@ debugging code before turning in your project. @item All parts of this assignment are required if you intend to earn full -credit on this project. However, some will be more important in -future projects: +credit on this project. Problem 1-1 (Alarm Clock) could be handy for +later projects, but it is not strictly required. Problems 1-2 +(Priority Scheduling) and 1-3 (Advanced Scheduler) won't be needed for +later projects. -@itemize @minus @item -Problem 1-1 (Alarm Clock) could be handy for later projects, but it is -not strictly required. - -@item -Problem 1-2 (Join) will be needed for future projects. We don't give -out solutions, so to avoid extra work later you should make sure that -your implementation of @func{thread_join} works correctly. - -@item -Problems 1-3 and 1-4 won't be needed for later projects. -@end itemize - -@item -Problem 1-4 (MLFQS) builds on the features you implement in Problem -1-3. You should have Problem 1-3 fully working before you begin to -tackle Problem 1-4. +Problem 1-3 (MLFQS) builds on the features you implement in Problem +1-2. You should have Problem 1-2 fully working before you begin to +tackle Problem 1-3. @item In the past, many groups divided the assignment into pieces, then each @@ -447,63 +434,8 @@ If your delays seem too short or too long, reread the explanation of the @option{-r} option to @command{pintos} (@pxref{Debugging versus Testing}). -@node Problem 1-2 Join -@section Problem 1-2: Join - -Implement @code{thread_join(tid_t)} in @file{threads/thread.c}. There -is already a prototype for it in @file{threads/thread.h}, which you -should not change. This function causes the currently running thread -to block until the thread whose thread id is passed as an argument -exits. If @var{A} is the running thread and @var{B} is the argument, -then we say that ``@var{A} joins @var{B}.'' - -Incidentally, we don't use @code{struct thread *} as -@func{thread_join}'s parameter type because a thread pointer is not -unique over time. That is, when a thread dies, its memory may be, -whether immediately or much later, reused for another thread. If -thread @var{A} over time had two children @var{B} and @var{C} that -were stored at the same address, then @code{thread_join(@var{B})} and -@code{thread_join(@var{C})} would be ambiguous. Introducing a thread -id or @dfn{tid}, represented by type @code{tid_t}, that is -intentionally unique over time solves the problem. The provided code -uses an @code{int} for @code{tid_t}, but you may decide you prefer to -use some other type. - -The model for @func{thread_join} is the @command{wait} system call -in Unix-like systems. (Try reading the manpages.) That system call -can only be used by a parent process to wait for a child's death. You -should implement @func{thread_join} to have the same restriction. -That is, a thread may only join its immediate children. - -A thread need not ever be joined. Your solution should properly free -all of a thread's resources, including its @struct{thread}, -whether it is ever joined or not, and regardless of whether the child -exits before or after its parent. That is, a thread should be freed -exactly once in all cases. - -Joining a given thread is idempotent. That is, joining a thread T -multiple times is equivalent to joining it once, because T has already -exited at the time of the later joins. Thus, joins on T after the -first should return immediately. - -Calling @func{thread_join} on an thread that is not the caller's -child should cause the caller to return immediately. For this purpose, -children are not inherited, that is, if @var{A} has child @var{B} and -@var{B} has child @var{C}, then @var{A} always returns immediately -should it try to join @var{C}, even if @var{B} is dead. - -Consider all the ways a join can occur: nested joins (@var{A} joins -@var{B}, then @var{B} joins @var{C}), multiple joins (@var{A} joins -@var{B}, then @var{A} joins @var{C}), and so on. Does your join work -if @func{thread_join} is called on a thread that has not yet been -scheduled for the first time? You should handle all of these cases. -Write test code that demonstrates the cases your join works for. - -Be careful to program this function correctly. You will need its -functionality for project 2. - -@node Problem 1-3 Priority Scheduling -@section Problem 1-3: Priority Scheduling +@node Problem 1-2 Priority Scheduling +@section Problem 1-2: Priority Scheduling Implement priority scheduling in Pintos. Priority scheduling is a key building block for real-time systems. Implement functions @@ -531,8 +463,7 @@ to immediately yield the CPU. One issue with priority scheduling is ``priority inversion'': if a high priority thread needs to wait for a low priority thread (for -instance, for a lock held by a low priority thread, or in -@func{thread_join} for a thread to complete), and a middle priority +instance, for a lock held by a low priority thread), and a middle priority thread is on the ready list, then the high priority thread will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is to have the waiting thread @@ -551,12 +482,12 @@ that @var{L} holds, then both @var{M} and @var{L} should be boosted to You only need to implement priority donation when a thread is waiting for a lock held by a lower-priority thread. You do not need to -implement this fix for semaphores, condition variables, or joins, +implement this fix for semaphores or condition variables although you are welcome to do so. However, you do need to implement priority scheduling in all cases. -@node Problem 1-4 Advanced Scheduler -@section Problem 1-4: Advanced Scheduler +@node Problem 1-3 Advanced Scheduler +@section Problem 1-3: Advanced Scheduler Implement Solaris's multilevel feedback queue scheduler (MLFQS) to reduce the average response time for running jobs on your system. @@ -660,9 +591,8 @@ the function isn't actually used by other @file{.c} files, make it @menu * Problem 1-1 Alarm Clock FAQ:: -* Problem 1-2 Join FAQ:: -* Problem 1-3 Priority Scheduling FAQ:: -* Problem 1-4 Advanced Scheduler FAQ:: +* Problem 1-2 Priority Scheduling FAQ:: +* Problem 1-3 Advanced Scheduler FAQ:: @end menu @node Problem 1-1 Alarm Clock FAQ @@ -729,7 +659,7 @@ Make the timer tick more slowly by decreasing @code{TIMER_FREQ} in @end itemize The former two changes are only desirable for testing problem 1-1 and -possibly 1-3. You should revert them before working on other parts +possibly 1-2. You should revert them before working on other parts of the project or turn in the project. We will test problem 1-1 with @code{TIME_SLICE} set to 100 and @code{TIMER_FREQ} set to 19, but we will leave them at their defaults for all the other problems. @@ -740,21 +670,8 @@ will leave them at their defaults for all the other problems. No. The MLFQS will adjust priorities, changing thread ordering. @end enumerate -@node Problem 1-2 Join FAQ -@subsection Problem 1-2: Join FAQ - -@enumerate 1 -@item -@b{Am I correct to assume that once a thread is deleted, it is no -longer accessible by the parent (i.e.@: the parent can't call -@code{thread_join(child)})?} - -A parent joining a child that has completed should be handled -gracefully and should act as a no-op. -@end enumerate - -@node Problem 1-3 Priority Scheduling FAQ -@subsection Problem 1-3: Priority Scheduling FAQ +@node Problem 1-2 Priority Scheduling FAQ +@subsection Problem 1-2: Priority Scheduling FAQ @enumerate 1 @item @@ -827,7 +744,7 @@ Yes. Same scenario as above except L gets blocked waiting on a new lock when H restores its priority. @item -@b{Why is @file{p1-3.c}'s FIFO test skipping some threads? I know my +@b{Why is @file{p1-2.c}'s FIFO test skipping some threads? I know my scheduler is round-robin'ing them like it's supposed to. Our output starts out okay, but toward the end it starts getting out of order.} @@ -868,7 +785,7 @@ its priority has been increased by a donation?} The higher (donated) priority. @item -@b{Should @file{p1-3.c} be expected to work with the MLFQS turned on?} +@b{Should @file{p1-2.c} be expected to work with the MLFQS turned on?} No. The MLFQS will adjust priorities, changing thread ordering. @@ -882,8 +799,8 @@ just before the first @func{printf} in @func{main}. Then modify @func{printf} itself to return immediately if the flag isn't set. @end enumerate -@node Problem 1-4 Advanced Scheduler FAQ -@subsection Problem 1-4: Advanced Scheduler FAQ +@node Problem 1-3 Advanced Scheduler FAQ +@subsection Problem 1-3: Advanced Scheduler FAQ @enumerate 1 @item diff --git a/doc/tour.texi b/doc/tour.texi index 4d0ce03..81eb5bd 100644 --- a/doc/tour.texi +++ b/doc/tour.texi @@ -261,7 +261,7 @@ other registers that must be saved are saved on the stack. A thread priority, ranging from the lowest possible priority @code{PRI_MIN} (0) to the highest possible priority @code{PRI_MAX} (59). Pintos as provided ignores thread priorities, but you will -implement priority scheduling in problem 1-3 (@pxref{Problem 1-3 +implement priority scheduling in problem 1-2 (@pxref{Problem 1-2 Priority Scheduling}). @item struct list_elem elem; diff --git a/doc/userprog.texi b/doc/userprog.texi index 0324a58..9fe874d 100644 --- a/doc/userprog.texi +++ b/doc/userprog.texi @@ -14,8 +14,8 @@ assignment. However, you will also be interacting with almost every other part of the code for this assignment. We will describe the relevant parts below. If you are confident in your HW1 code, you can build on top of it. However, if you wish you can start with a fresh -copy of the code and re-implement @func{thread_join}, which is the -only part of project #1 required for this assignment. +copy of the code. No code from project 1 is required for this +assignment. Up to now, all of the code you have written for Pintos has been part of the operating system kernel. This means, for example, that all the @@ -405,7 +405,7 @@ etc. @item SYS_exit @itemx void exit (int @var{status}) Terminates the current user program, returning @var{status} to the -kernel. If the process's parent @func{join}s it, this is the status +kernel. If the process's parent @func{wait}s for it, this is the status that will be returned. Conventionally, a @var{status} of 0 indicates a successful exit. Other values may be used to indicate user-defined conditions (usually errors). @@ -417,14 +417,36 @@ given arguments, and returns the new process's program id (pid). Must return pid -1, which otherwise should not be a valid program id, if there is an error loading this program. -@item SYS_join -@itemx int join (pid_t @var{pid}) -Joins the process @var{pid}, using the join rules from the last -assignment, and returns the process's exit status. If the process was -terminated by the kernel (i.e.@: killed due to an exception), the exit -status should be -1. If the process was not a child of the calling -process, the return value is undefined (but kernel operation must not -be disrupted). +@item SYS_wait +@itemx int wait (pid_t @var{pid}) +Waits for process @var{pid} to die and returns its exit status. If it +was terminated by the kernel (i.e.@: killed due to an exception), +returns -1. If @var{pid} is invalid or if it was not a child of the +calling thread, or if @code{wait} has already been successfully +called for the given @var{pid}, returns -1 immediately, without +waiting. + +You must ensure that Pintos does not terminate until the initial +process exits. The supplied Pintos code tries to do this by calling +@func{process_wait} (in @file{userprog/process.c}) from @func{main} +(in @file{threads/init.c}). We suggest that you implement +@func{process_wait} according to the comment at the top of the +function and then implement the @code{wait} system call in terms of +@func{process_wait}. + +All of a process's resources, including its @struct{thread}, must be +freed whether its parent ever waits for it or not, and regardless of +whether the child exits before or after its parent. + +Children are not inherited, that is, if @var{A} has child @var{B} and +@var{B} has child @var{C}, then @var{A} always returns immediately +should it try to wait for @var{C}, even if @var{B} is dead. + +Consider all the ways a wait can occur: nested waits (@var{A} waits +for @var{B}, then @var{B} waits for @var{C}), multiple waits (@var{A} +waits for @var{B}, then @var{A} waits for @var{C}), and so on. Does +your @func{wait} work if it is called on a process that has not yet +been scheduled for the first time? @item SYS_create @itemx bool create (const char *@var{file}, unsigned @var{initial_size}) @@ -549,9 +571,7 @@ value), returning an undefined value, or terminating the process. @item @b{Do we need a working project 1 to implement project 2?} -You may find the code for @func{thread_join} to be useful in -implementing the join syscall, but besides that, you can use -the original code provided for project 1. +No. @item @b{@samp{pintos put} always panics.} @@ -643,7 +663,7 @@ process running in it (if created with @func{process_execute}) or not in the kernel. A @code{pid_t} identifies a user process. It is used by user -processes and the kernel in the @code{exec} and @code{join} system +processes and the kernel in the @code{exec} and @code{wait} system calls. You can choose whatever suitable types you like for @code{tid_t} and diff --git a/grading/filesys/fslib.c b/grading/filesys/fslib.c index be17f29..2087d07 100644 --- a/grading/filesys/fslib.c +++ b/grading/filesys/fslib.c @@ -188,15 +188,15 @@ exec_children (const char *child_name, pid_t pids[], size_t child_cnt) } void -join_children (pid_t pids[], size_t child_cnt) +wait_children (pid_t pids[], size_t child_cnt) { size_t i; for (i = 0; i < child_cnt; i++) { - int status = join (pids[i]); + int status = wait (pids[i]); CHECK (status == (int) i, - "join child %zu of %zu returned %d (expected %zu)", + "wait for child %zu of %zu returned %d (expected %zu)", i + 1, child_cnt, status, i); } } diff --git a/grading/filesys/fslib.h b/grading/filesys/fslib.h index ea38624..0d4f12d 100644 --- a/grading/filesys/fslib.h +++ b/grading/filesys/fslib.h @@ -48,7 +48,7 @@ void compare_bytes (const void *read_data, const void *expected_data, size_t size, size_t ofs, const char *filename); void exec_children (const char *child_name, pid_t pids[], size_t child_cnt); -void join_children (pid_t pids[], size_t child_cnt); +void wait_children (pid_t pids[], size_t child_cnt); void test_main (void); diff --git a/grading/filesys/syn-read.c b/grading/filesys/syn-read.c index 7d2ff3d..57fd4cf 100644 --- a/grading/filesys/syn-read.c +++ b/grading/filesys/syn-read.c @@ -24,5 +24,5 @@ test_main (void) close (fd); exec_children ("child-syn-read", children, CHILD_CNT); - join_children (children, CHILD_CNT); + wait_children (children, CHILD_CNT); } diff --git a/grading/filesys/syn-read.exp b/grading/filesys/syn-read.exp index 93bc2fb..730a97b 100644 --- a/grading/filesys/syn-read.exp +++ b/grading/filesys/syn-read.exp @@ -13,14 +13,14 @@ (syn-read) exec child 8 of 10: "child-syn-read 7" (syn-read) exec child 9 of 10: "child-syn-read 8" (syn-read) exec child 10 of 10: "child-syn-read 9" -(syn-read) join child 1 of 10 returned 0 (expected 0) -(syn-read) join child 2 of 10 returned 1 (expected 1) -(syn-read) join child 3 of 10 returned 2 (expected 2) -(syn-read) join child 4 of 10 returned 3 (expected 3) -(syn-read) join child 5 of 10 returned 4 (expected 4) -(syn-read) join child 6 of 10 returned 5 (expected 5) -(syn-read) join child 7 of 10 returned 6 (expected 6) -(syn-read) join child 8 of 10 returned 7 (expected 7) -(syn-read) join child 9 of 10 returned 8 (expected 8) -(syn-read) join child 10 of 10 returned 9 (expected 9) +(syn-read) wait for child 1 of 10 returned 0 (expected 0) +(syn-read) wait for child 2 of 10 returned 1 (expected 1) +(syn-read) wait for child 3 of 10 returned 2 (expected 2) +(syn-read) wait for child 4 of 10 returned 3 (expected 3) +(syn-read) wait for child 5 of 10 returned 4 (expected 4) +(syn-read) wait for child 6 of 10 returned 5 (expected 5) +(syn-read) wait for child 7 of 10 returned 6 (expected 6) +(syn-read) wait for child 8 of 10 returned 7 (expected 7) +(syn-read) wait for child 9 of 10 returned 8 (expected 8) +(syn-read) wait for child 10 of 10 returned 9 (expected 9) (syn-read) end diff --git a/grading/filesys/syn-rw.c b/grading/filesys/syn-rw.c index b87b063..cacdd59 100644 --- a/grading/filesys/syn-rw.c +++ b/grading/filesys/syn-rw.c @@ -30,5 +30,5 @@ test_main (void) (int) CHUNK_SIZE, ofs, filename); quiet = false; - join_children (children, CHILD_CNT); + wait_children (children, CHILD_CNT); } diff --git a/grading/filesys/syn-write.c b/grading/filesys/syn-write.c index c7eef3a..b21edce 100644 --- a/grading/filesys/syn-write.c +++ b/grading/filesys/syn-write.c @@ -19,7 +19,7 @@ test_main (void) CHECK (create (filename, sizeof buf1), "create \"%s\"", filename); exec_children ("child-syn-wrt", children, CHILD_CNT); - join_children (children, CHILD_CNT); + wait_children (children, CHILD_CNT); CHECK ((fd = open (filename)) > 1, "open \"%s\"", filename); CHECK (read (fd, buf1, sizeof buf1) > 0, "read \"%s\"", filename); diff --git a/grading/filesys/syn-write.exp b/grading/filesys/syn-write.exp index 6ce5a42..e4d9816 100644 --- a/grading/filesys/syn-write.exp +++ b/grading/filesys/syn-write.exp @@ -10,16 +10,16 @@ (syn-write) exec child 8 of 10: "child-syn-wrt 7" (syn-write) exec child 9 of 10: "child-syn-wrt 8" (syn-write) exec child 10 of 10: "child-syn-wrt 9" -(syn-write) join child 1 of 10 returned 0 (expected 0) -(syn-write) join child 2 of 10 returned 1 (expected 1) -(syn-write) join child 3 of 10 returned 2 (expected 2) -(syn-write) join child 4 of 10 returned 3 (expected 3) -(syn-write) join child 5 of 10 returned 4 (expected 4) -(syn-write) join child 6 of 10 returned 5 (expected 5) -(syn-write) join child 7 of 10 returned 6 (expected 6) -(syn-write) join child 8 of 10 returned 7 (expected 7) -(syn-write) join child 9 of 10 returned 8 (expected 8) -(syn-write) join child 10 of 10 returned 9 (expected 9) +(syn-write) wait for child 1 of 10 returned 0 (expected 0) +(syn-write) wait for child 2 of 10 returned 1 (expected 1) +(syn-write) wait for child 3 of 10 returned 2 (expected 2) +(syn-write) wait for child 4 of 10 returned 3 (expected 3) +(syn-write) wait for child 5 of 10 returned 4 (expected 4) +(syn-write) wait for child 6 of 10 returned 5 (expected 5) +(syn-write) wait for child 7 of 10 returned 6 (expected 6) +(syn-write) wait for child 8 of 10 returned 7 (expected 7) +(syn-write) wait for child 9 of 10 returned 8 (expected 8) +(syn-write) wait for child 10 of 10 returned 9 (expected 9) (syn-write) open "stuff" (syn-write) read "stuff" (syn-write) end diff --git a/grading/threads/join-dummy.c b/grading/threads/join-dummy.c deleted file mode 100644 index 01733e2..0000000 --- a/grading/threads/join-dummy.c +++ /dev/null @@ -1,52 +0,0 @@ -/* Problem 1-2: Join tests. - - Based on a test originally submitted for Stanford's CS 140 in - winter 1998 by Rob Baesman , Ben - Taskar , and Toli Kuznets - . Later modified by shiangc, yph, and - arens. */ -#include "threads/test.h" -#include -#include "threads/interrupt.h" -#include "threads/thread.h" - -static void dummy_test (void); - -void -test (void) -{ - dummy_test (); -} - -static thread_func simple_thread_func; - -static void -dummy_test (void) -{ - tid_t tid0; - - printf ("\n" - "Testing dummy join.\n" - "Thread 0 should finish before thread 1 starts.\n"); - tid0 = thread_create ("0", PRI_DEFAULT, simple_thread_func, "0"); - thread_yield (); - thread_join (tid0); - thread_join (tid0); - simple_thread_func ("1"); - thread_join (tid0); - printf ("Dummy join test done.\n"); -} - -void -simple_thread_func (void *name_) -{ - const char *name = name_; - int i; - - for (i = 0; i < 5; i++) - { - printf ("Thread %s iteration %d\n", name, i); - thread_yield (); - } - printf ("Thread %s done!\n", name); -} diff --git a/grading/threads/join-dummy.exp b/grading/threads/join-dummy.exp deleted file mode 100644 index b60afa5..0000000 --- a/grading/threads/join-dummy.exp +++ /dev/null @@ -1,15 +0,0 @@ -Testing dummy 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! -Dummy join test done. diff --git a/grading/threads/join-invalid.c b/grading/threads/join-invalid.c deleted file mode 100644 index 05decb4..0000000 --- a/grading/threads/join-invalid.c +++ /dev/null @@ -1,50 +0,0 @@ -/* Problem 1-2: Join tests. - - Based on a test originally submitted for Stanford's CS 140 in - winter 1998 by Rob Baesman , Ben - Taskar , and Toli Kuznets - . Later modified by shiangc, yph, and - arens. */ -#include "threads/test.h" -#include -#include "threads/interrupt.h" -#include "threads/thread.h" - -static void invalid_test (void); - -void -test (void) -{ - invalid_test (); -} - -static thread_func simple_thread_func; - -static void -invalid_test (void) -{ - tid_t tid0; - - printf ("\n" - "Testing invalid join.\n" - "Should just not crash.\n"); - tid0 = thread_create ("0", PRI_DEFAULT, simple_thread_func, "0"); - thread_yield (); - thread_join (1234); - simple_thread_func ("1"); - printf ("Invalid join test done.\n"); -} - -void -simple_thread_func (void *name_) -{ - const char *name = name_; - int i; - - for (i = 0; i < 5; i++) - { - printf ("Thread %s iteration %d\n", name, i); - thread_yield (); - } - printf ("Thread %s done!\n", name); -} diff --git a/grading/threads/join-multiple.c b/grading/threads/join-multiple.c deleted file mode 100644 index c903a25..0000000 --- a/grading/threads/join-multiple.c +++ /dev/null @@ -1,53 +0,0 @@ -/* Problem 1-2: Join tests. - - Based on a test originally submitted for Stanford's CS 140 in - winter 1998 by Rob Baesman , Ben - Taskar , and Toli Kuznets - . Later modified by shiangc, yph, and - arens. */ -#include "threads/test.h" -#include -#include "threads/interrupt.h" -#include "threads/thread.h" - -static void multiple_test (void); - -void -test (void) -{ - multiple_test (); -} - -static thread_func simple_thread_func; - -static void -multiple_test (void) -{ - tid_t tid4, tid5; - - printf ("\n" - "Testing multiple join.\n" - "Threads 4 and 5 should finish before thread 6 starts.\n"); - - tid4 = thread_create ("4", PRI_DEFAULT, simple_thread_func, "4"); - tid5 = thread_create ("5", PRI_DEFAULT, simple_thread_func, "5"); - thread_yield (); - thread_join (tid4); - thread_join (tid5); - simple_thread_func ("6"); - printf ("Multiple join test done.\n"); -} - -void -simple_thread_func (void *name_) -{ - const char *name = name_; - int i; - - for (i = 0; i < 5; i++) - { - printf ("Thread %s iteration %d\n", name, i); - thread_yield (); - } - printf ("Thread %s done!\n", name); -} diff --git a/grading/threads/join-nested.c b/grading/threads/join-nested.c deleted file mode 100644 index fc94c44..0000000 --- a/grading/threads/join-nested.c +++ /dev/null @@ -1,58 +0,0 @@ -/* Problem 1-2: Join tests. - - Based on a test originally submitted for Stanford's CS 140 in - winter 1998 by Rob Baesman , Ben - Taskar , and Toli Kuznets - . Later modified by shiangc, yph, and - arens. */ -#include "threads/test.h" -#include -#include "threads/interrupt.h" -#include "threads/thread.h" - -static void nested_test (void); - -void -test (void) -{ - nested_test (); -} - -static thread_func nested_thread_func; - -static void -nested_test (void) -{ - tid_t tid0; - int zero = 0; - - printf ("\n" - "Testing nested join.\n" - "Threads 0 to 7 should start in numerical order\n" - "and finish in reverse order.\n"); - tid0 = thread_create ("0", PRI_DEFAULT, nested_thread_func, &zero); - thread_join (tid0); - printf ("Nested join test done.\n"); -} - -void -nested_thread_func (void *valuep_) -{ - int *valuep = valuep_; - int value = *valuep; - - printf ("Thread %d starting.\n", value); - if (value < 7) - { - int next = value + 1; - tid_t tid_next; - char name_next[8]; - snprintf (name_next, sizeof name_next, "%d", next); - - tid_next = thread_create (name_next, PRI_DEFAULT, - nested_thread_func, &next); - - thread_join (tid_next); - } - printf ("Thread %d done.\n", value); -} diff --git a/grading/threads/join-nested.exp b/grading/threads/join-nested.exp deleted file mode 100644 index 17ebd14..0000000 --- a/grading/threads/join-nested.exp +++ /dev/null @@ -1,20 +0,0 @@ -Testing nested join. -Threads 0 to 7 should start in numerical order -and finish in reverse order. -Thread 0 starting. -Thread 1 starting. -Thread 2 starting. -Thread 3 starting. -Thread 4 starting. -Thread 5 starting. -Thread 6 starting. -Thread 7 starting. -Thread 7 done. -Thread 6 done. -Thread 5 done. -Thread 4 done. -Thread 3 done. -Thread 2 done. -Thread 1 done. -Thread 0 done. -Nested join test done. diff --git a/grading/threads/join-no.c b/grading/threads/join-no.c deleted file mode 100644 index 7cecf34..0000000 --- a/grading/threads/join-no.c +++ /dev/null @@ -1,49 +0,0 @@ -/* Problem 1-2: Join tests. - - Based on a test originally submitted for Stanford's CS 140 in - winter 1998 by Rob Baesman , Ben - Taskar , and Toli Kuznets - . Later modified by shiangc, yph, and - arens. */ - -#include "threads/test.h" -#include -#include "threads/interrupt.h" -#include "threads/thread.h" - -static void no_test (void); - -void -test (void) -{ - no_test (); -} - -static thread_func simple_thread_func; - -static void -no_test (void) -{ - tid_t tid0; - - printf ("\n" - "Testing no join.\n" - "Should just not crash.\n"); - tid0 = thread_create ("0", PRI_DEFAULT, simple_thread_func, "0"); - simple_thread_func ("1"); - printf ("No join test done.\n"); -} - -void -simple_thread_func (void *name_) -{ - const char *name = name_; - int i; - - for (i = 0; i < 5; i++) - { - printf ("Thread %s iteration %d\n", name, i); - thread_yield (); - } - printf ("Thread %s done!\n", name); -} diff --git a/grading/threads/join-quick.c b/grading/threads/join-quick.c deleted file mode 100644 index 7330827..0000000 --- a/grading/threads/join-quick.c +++ /dev/null @@ -1,66 +0,0 @@ -/* Problem 1-2: Join tests. - - Based on a test originally submitted for Stanford's CS 140 in - winter 1998 by Rob Baesman , Ben - Taskar , and Toli Kuznets - . Later modified by shiangc, yph, and - arens. */ -#include "threads/test.h" -#include -#include "threads/interrupt.h" -#include "threads/thread.h" - -static void quick_test (void); - -void -test (void) -{ - quick_test (); -} - -static thread_func quick_thread_func; -static thread_func simple_thread_func; - -static void -quick_test (void) -{ - tid_t tid2; - - printf ("\n" - "Testing quick join.\n" - "Thread 2 should finish before thread 3 starts.\n"); - - tid2 = thread_create ("2", PRI_DEFAULT, quick_thread_func, "2"); - thread_yield (); - thread_join (tid2); - simple_thread_func ("3"); - printf ("Quick join test done.\n"); -} - -void -quick_thread_func (void *name_) -{ - const char *name = name_; - int i; - - for (i = 0; i < 5; i++) - { - printf ("Thread %s iteration %d\n", name, i); - thread_yield (); - } - printf ("Thread %s done!\n", name); -} - -void -simple_thread_func (void *name_) -{ - const char *name = name_; - int i; - - for (i = 0; i < 5; i++) - { - printf ("Thread %s iteration %d\n", name, i); - thread_yield (); - } - printf ("Thread %s done!\n", name); -} diff --git a/grading/threads/join-quick.exp b/grading/threads/join-quick.exp deleted file mode 100644 index 80690bb..0000000 --- a/grading/threads/join-quick.exp +++ /dev/null @@ -1,15 +0,0 @@ -Testing quick join. -Thread 2 should finish before thread 3 starts. -Thread 2 iteration 0 -Thread 2 iteration 1 -Thread 2 iteration 2 -Thread 2 iteration 3 -Thread 2 iteration 4 -Thread 2 done! -Thread 3 iteration 0 -Thread 3 iteration 1 -Thread 3 iteration 2 -Thread 3 iteration 3 -Thread 3 iteration 4 -Thread 3 done! -Quick join test done. diff --git a/grading/threads/join-simple.c b/grading/threads/join-simple.c deleted file mode 100644 index 3407f56..0000000 --- a/grading/threads/join-simple.c +++ /dev/null @@ -1,50 +0,0 @@ -/* Problem 1-2: Join tests. - - Based on a test originally submitted for Stanford's CS 140 in - winter 1998 by Rob Baesman , Ben - Taskar , and Toli Kuznets - . Later modified by shiangc, yph, and - arens. */ -#include "threads/test.h" -#include -#include "threads/interrupt.h" -#include "threads/thread.h" - -static void simple_test (void); - -void -test (void) -{ - simple_test (); -} - -static thread_func simple_thread_func; - -static void -simple_test (void) -{ - tid_t tid0; - - printf ("\n" - "Testing simple join.\n" - "Thread 0 should finish before thread 1 starts.\n"); - tid0 = thread_create ("0", PRI_DEFAULT, simple_thread_func, "0"); - thread_yield (); - thread_join (tid0); - simple_thread_func ("1"); - printf ("Simple join test done.\n"); -} - -void -simple_thread_func (void *name_) -{ - const char *name = name_; - int i; - - for (i = 0; i < 5; i++) - { - printf ("Thread %s iteration %d\n", name, i); - thread_yield (); - } - printf ("Thread %s done!\n", name); -} diff --git a/grading/threads/join-simple.exp b/grading/threads/join-simple.exp deleted file mode 100644 index 844a333..0000000 --- a/grading/threads/join-simple.exp +++ /dev/null @@ -1,15 +0,0 @@ -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 index 08585b5..739fbac 100644 --- a/grading/threads/review.txt +++ b/grading/threads/review.txt @@ -6,8 +6,6 @@ TESTCASES [[/10]] -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 DESIGN [[/40]] @@ -35,16 +33,7 @@ Problem 1-1: Alarm Clock -1 Doesn't protect data structure in timer_sleep -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 - -2 Joinable child lets its struct thread be deleted before parent dies - -1 Race condition between join and thread exit - -Problem 1-3: Priority Scheduler +Problem 1-2: Priority Scheduler -3 Doesn't use sorted queue scheduler, and don't justify why they didn't -2 sema_up() doesn't pick highest-priority waiting thread -1 Should use sorted queue in semaphores, unless explained in DESIGNDOC @@ -54,7 +43,7 @@ Problem 1-3: Priority Scheduler -3 Bad design +2 Used a heap or other advanced priority queue for ready_list -Problem 1-4: Advanced Scheduler +Problem 1-3: Advanced Scheduler -2 Isn't table-driven -5 Bad design diff --git a/grading/threads/run-tests b/grading/threads/run-tests index 1e718a9..5346211 100755 --- a/grading/threads/run-tests +++ b/grading/threads/run-tests @@ -22,9 +22,6 @@ our (%result); our ($action); parse_cmd_line qw (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-on mlfqs-off); @@ -160,55 +157,6 @@ sub grade_alarm_negative { die "Crashed in timer_sleep()\n" if !grep (/^Success\.$/, @output); } -sub grade_join_invalid { - my (@output) = @_; - 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) = @_; diff --git a/grading/threads/tests.txt b/grading/threads/tests.txt index f2ad06c..2a27bb2 100644 --- a/grading/threads/tests.txt +++ b/grading/threads/tests.txt @@ -11,17 +11,7 @@ Problem 1-1: Alarm Clock -1 alarm-negative: Negative wait time must not crash or hang Score: /8 -Problem 1-2: Join - -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 -Score: /14 - -Problem 1-3: Priority Scheduler +Problem 1-2: Priority Scheduler -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) @@ -29,7 +19,7 @@ Problem 1-3: Priority Scheduler -2 priority-donate-nest: Nested priority donation with single lock Score: /10 -Problem 1-4: Advanced Scheduler +Problem 1-3: Advanced Scheduler -4 mlfqs-speedup: Public testcase doesn't run faster with MLFQS -4 mlfqs-priority: Priorities don't change properly Score: /8 diff --git a/grading/userprog/.cvsignore b/grading/userprog/.cvsignore index b276a49..72f1786 100644 --- a/grading/userprog/.cvsignore +++ b/grading/userprog/.cvsignore @@ -56,10 +56,10 @@ exec-arg exec-multiple exec-missing exec-bad-ptr -join-simple -join-twice -join-killed -join-bad-pid +wait-simple +wait-twice +wait-killed +wait-bad-pid multi-recurse multi-oom multi-child-fd diff --git a/grading/userprog/Make.base b/grading/userprog/Make.base index e0cad44..1e04ab8 100644 --- a/grading/userprog/Make.base +++ b/grading/userprog/Make.base @@ -15,9 +15,9 @@ null: null.o $(CC) $(LDFLAGS) $^ $(LDLIBS) -o $@ null.dsk: null -exec-once.dsk exec-multiple.dsk join-simple.dsk join-twice.dsk: child-simple +exec-once.dsk exec-multiple.dsk wait-simple.dsk wait-twice.dsk: child-simple exec-arg.dsk: child-arg -join-killed.dsk: child-bad +wait-killed.dsk: child-bad multi-child-fd.dsk: child-close %.dsk: % diff --git a/grading/userprog/Make.tests b/grading/userprog/Make.tests index 8df4071..a1f1ec5 100644 --- a/grading/userprog/Make.tests +++ b/grading/userprog/Make.tests @@ -45,10 +45,10 @@ exec-arg exec-multiple exec-missing exec-bad-ptr -join-simple -join-twice -join-killed -join-bad-pid +wait-simple +wait-twice +wait-killed +wait-bad-pid multi-recurse multi-oom multi-child-fd diff --git a/grading/userprog/Makefile b/grading/userprog/Makefile index 2b96694..225180f 100644 --- a/grading/userprog/Makefile +++ b/grading/userprog/Makefile @@ -11,7 +11,7 @@ TESTS = \ read-bad-ptr read-boundary read-zero read-stdout read-bad-fd \ write-normal write-bad-ptr write-boundary write-zero write-stdin \ write-bad-fd exec-once exec-arg exec-multiple exec-missing \ - exec-bad-ptr join-simple join-twice join-killed join-bad-pid \ + exec-bad-ptr wait-simple wait-twice wait-killed wait-bad-pid \ multi-recurse multi-oom multi-child-fd args_argc_SRC = args-argc.c args_argv0_SRC = args-argv0.c @@ -60,10 +60,10 @@ exec_arg_SRC = exec-arg.c exec_multiple_SRC = exec-multiple.c exec_missing_SRC = exec-missing.c exec_bad_ptr_SRC = exec-bad-ptr.c -join_simple_SRC = join-simple.c -join_twice_SRC = join-twice.c -join_killed_SRC = join-killed.c -join_bad_pid_SRC = join-bad-pid.c +wait_simple_SRC = wait-simple.c +wait_twice_SRC = wait-twice.c +wait_killed_SRC = wait-killed.c +wait_bad_pid_SRC = wait-bad-pid.c multi_recurse_SRC = multi-recurse.c multi_oom_SRC = multi-oom.c multi_child_fd_SRC = multi-child-fd.c @@ -85,9 +85,9 @@ null: null.o $(CC) $(LDFLAGS) $^ $(LDLIBS) -o $@ null.dsk: null -exec-once.dsk exec-multiple.dsk join-simple.dsk join-twice.dsk: child-simple +exec-once.dsk exec-multiple.dsk wait-simple.dsk wait-twice.dsk: child-simple exec-arg.dsk: child-arg -join-killed.dsk: child-bad +wait-killed.dsk: child-bad multi-child-fd.dsk: child-close %.dsk: % diff --git a/grading/userprog/exec-arg.c b/grading/userprog/exec-arg.c index 97f94cf..cef5ece 100644 --- a/grading/userprog/exec-arg.c +++ b/grading/userprog/exec-arg.c @@ -5,7 +5,7 @@ int main (void) { printf ("(exec-arg) begin\n"); - join (exec ("child-arg childarg")); + wait (exec ("child-arg childarg")); printf ("(exec-arg) end\n"); return 0; } diff --git a/grading/userprog/exec-multiple.c b/grading/userprog/exec-multiple.c index e2f8506..a690dad 100644 --- a/grading/userprog/exec-multiple.c +++ b/grading/userprog/exec-multiple.c @@ -5,10 +5,10 @@ int main (void) { printf ("(exec-multiple) begin\n"); - join (exec ("child-simple")); - join (exec ("child-simple")); - join (exec ("child-simple")); - join (exec ("child-simple")); + wait (exec ("child-simple")); + wait (exec ("child-simple")); + wait (exec ("child-simple")); + wait (exec ("child-simple")); printf ("(exec-multiple) end\n"); return 0; } diff --git a/grading/userprog/exec-once.c b/grading/userprog/exec-once.c index ab1de21..87bf2be 100644 --- a/grading/userprog/exec-once.c +++ b/grading/userprog/exec-once.c @@ -5,7 +5,7 @@ int main (void) { printf ("(exec-once) begin\n"); - join (exec ("child-simple")); + wait (exec ("child-simple")); printf ("(exec-once) end\n"); return 0; } diff --git a/grading/userprog/join-bad-pid.c b/grading/userprog/join-bad-pid.c deleted file mode 100644 index d2902bb..0000000 --- a/grading/userprog/join-bad-pid.c +++ /dev/null @@ -1,11 +0,0 @@ -#include -#include - -int -main (void) -{ - printf ("(join-bad-pid) begin\n"); - join ((pid_t) 0x20101234); - printf ("(join-bad-pid) end\n"); - return 0; -} diff --git a/grading/userprog/join-bad-pid.exp b/grading/userprog/join-bad-pid.exp deleted file mode 100644 index 2f7f5ee..0000000 --- a/grading/userprog/join-bad-pid.exp +++ /dev/null @@ -1,6 +0,0 @@ -(join-bad-pid) begin -(join-bad-pid) end -join-bad-pid: exit(0) ---OR-- -(join-bad-pid) begin -join-bad-pid: exit(-1) diff --git a/grading/userprog/join-killed.c b/grading/userprog/join-killed.c deleted file mode 100644 index 6a8e6b4..0000000 --- a/grading/userprog/join-killed.c +++ /dev/null @@ -1,11 +0,0 @@ -#include -#include - -int -main (void) -{ - printf ("(join-killed) begin\n"); - printf ("(join-killed) join(exec()) = %d\n", join (exec ("child-bad"))); - printf ("(join-killed) end\n"); - return 0; -} diff --git a/grading/userprog/join-killed.exp b/grading/userprog/join-killed.exp deleted file mode 100644 index 0e28e2e..0000000 --- a/grading/userprog/join-killed.exp +++ /dev/null @@ -1,6 +0,0 @@ -(join-killed) begin -(child-bad) begin -child-bad: exit(-1) -(join-killed) join(exec()) = -1 -(join-killed) end -join-killed: exit(0) diff --git a/grading/userprog/join-simple.c b/grading/userprog/join-simple.c deleted file mode 100644 index 9d1624a..0000000 --- a/grading/userprog/join-simple.c +++ /dev/null @@ -1,11 +0,0 @@ -#include -#include - -int -main (void) -{ - printf ("(join-simple) begin\n"); - printf ("(join-simple) join(exec()) = %d\n", join (exec ("child-simple"))); - printf ("(join-simple) end\n"); - return 0; -} diff --git a/grading/userprog/join-simple.exp b/grading/userprog/join-simple.exp deleted file mode 100644 index b3b4051..0000000 --- a/grading/userprog/join-simple.exp +++ /dev/null @@ -1,6 +0,0 @@ -(join-simple) begin -(child-simple) run -child-simple: exit(81) -(join-simple) join(exec()) = 81 -(join-simple) end -join-simple: exit(0) diff --git a/grading/userprog/join-twice.c b/grading/userprog/join-twice.c deleted file mode 100644 index 2a80ad7..0000000 --- a/grading/userprog/join-twice.c +++ /dev/null @@ -1,14 +0,0 @@ -#include -#include - -int -main (void) -{ - pid_t child; - printf ("(join-twice) begin\n"); - child = exec ("child-simple"); - printf ("(join-twice) join(exec()) = %d\n", join (child)); - join (child); - printf ("(join-twice) end\n"); - return 0; -} diff --git a/grading/userprog/join-twice.exp b/grading/userprog/join-twice.exp deleted file mode 100644 index ffb57ea..0000000 --- a/grading/userprog/join-twice.exp +++ /dev/null @@ -1,6 +0,0 @@ -(join-twice) begin -(child-simple) run -child-simple: exit(81) -(join-twice) join(exec()) = 81 -(join-twice) end -join-twice: exit(0) diff --git a/grading/userprog/multi-child-fd.c b/grading/userprog/multi-child-fd.c index 50b5a50..7b1bc9a 100644 --- a/grading/userprog/multi-child-fd.c +++ b/grading/userprog/multi-child-fd.c @@ -20,7 +20,7 @@ main (void) snprintf (child_cmd, sizeof child_cmd, "child-close %d", handle); - printf ("(multi-child-fd) join(exec()) = %d\n", join (exec (child_cmd))); + printf ("(multi-child-fd) wait(exec()) = %d\n", wait (exec (child_cmd))); byte_cnt = read (handle, actual, sizeof actual - 1); if (byte_cnt != sizeof actual - 1) diff --git a/grading/userprog/multi-child-fd.exp b/grading/userprog/multi-child-fd.exp index 57b2e12..474ea91 100644 --- a/grading/userprog/multi-child-fd.exp +++ b/grading/userprog/multi-child-fd.exp @@ -1,12 +1,12 @@ (multi-child-fd) begin (child-close) success child-close: exit(0) -(multi-child-fd) join(exec()) = 0 +(multi-child-fd) wait(exec()) = 0 (multi-child-fd) end multi-child-fd: exit(0) --OR-- (multi-child-fd) begin child-close: exit(-1) -(multi-child-fd) join(exec()) = -1 +(multi-child-fd) wait(exec()) = -1 (multi-child-fd) end multi-child-fd: exit(0) diff --git a/grading/userprog/multi-oom.c b/grading/userprog/multi-oom.c index 2ad63e9..cfdda66 100644 --- a/grading/userprog/multi-oom.c +++ b/grading/userprog/multi-oom.c @@ -20,9 +20,9 @@ main (int argc UNUSED, char *argv[]) child_pid = exec (child_cmd); if (child_pid != -1) { - int code = join (child_pid); + int code = wait (child_pid); if (code != n + 1) - printf ("(multi-oom) fail: join(exec(\"%s\")) returned %d\n", + printf ("(multi-oom) fail: wait(exec(\"%s\")) returned %d\n", child_cmd, code); } else if (n < 15) diff --git a/grading/userprog/multi-parent-fd.c b/grading/userprog/multi-parent-fd.c index 4a8c89f..56e10b1 100644 --- a/grading/userprog/multi-parent-fd.c +++ b/grading/userprog/multi-parent-fd.c @@ -20,7 +20,7 @@ main (void) snprintf (child_cmd, sizeof child_cmd, "child-close %d", handle); - printf ("(multi-child-fd) join(exec()) = %d\n", join (exec (child_cmd))); + printf ("(multi-child-fd) wait(exec()) = %d\n", wait (exec (child_cmd))); byte_cnt = read (handle, actual, sizeof actual - 1); if (byte_cnt != sizeof actual - 1) diff --git a/grading/userprog/multi-recurse.c b/grading/userprog/multi-recurse.c index 48692e2..4a69d84 100644 --- a/grading/userprog/multi-recurse.c +++ b/grading/userprog/multi-recurse.c @@ -20,9 +20,9 @@ main (int argc UNUSED, char *argv[]) child_pid = exec (child_cmd); if (child_pid != -1) { - int code = join (child_pid); + int code = wait (child_pid); if (code != n - 1) - printf ("(multi-recurse) fail: join(exec(\"%s\")) returned %d\n", + printf ("(multi-recurse) fail: wait(exec(\"%s\")) returned %d\n", child_cmd, code); } else diff --git a/grading/userprog/prep-disk b/grading/userprog/prep-disk index f525b07..39d078e 100755 --- a/grading/userprog/prep-disk +++ b/grading/userprog/prep-disk @@ -46,10 +46,10 @@ put_file ("sample.txt") put_file ("child-simple") if grep ($_ eq $test, qw (exec-once exec-multiple - join-simple join-twice)); + wait-simple wait-twice)); put_file ("child-arg") if $test eq 'exec-arg'; put_file ("child-close") if $test eq 'multi-child-fd'; -put_file ("child-bad") if $test eq 'join-killed'; +put_file ("child-bad") if $test eq 'wait-killed'; sub put_file { my ($fn) = @_; diff --git a/grading/userprog/review.txt b/grading/userprog/review.txt index 29ed26b..0a40021 100644 --- a/grading/userprog/review.txt +++ b/grading/userprog/review.txt @@ -44,6 +44,15 @@ System call design: -5 System call error exit leaks memory/fails to release global lock -5 Uses a pointer as a file descriptor or pid without justifying +Wait system call: + -3 Busy waiting + -3 A static list of all parent-child pairs is extremely wasteful + -3 Obviously wasteful with memory (not deleting processes) + -2 Finished parent deletes children which may still be running + -1 Enable/disable interrupts + -2 Joinable child lets its struct thread be deleted before parent dies + -1 Race condition between wait and thread exit + Style [[/25]] ------------- -5 Extraneous output caused warnings diff --git a/grading/userprog/run-tests b/grading/userprog/run-tests index b09bc5e..e81b533 100755 --- a/grading/userprog/run-tests +++ b/grading/userprog/run-tests @@ -43,7 +43,7 @@ parse_cmd_line qw (args-argc args-argv0 args-argvn args-single args-multiple write-normal write-bad-ptr write-boundary write-zero write-stdin write-bad-fd exec-once exec-arg exec-multiple exec-missing exec-bad-ptr - join-simple join-twice join-killed join-bad-pid + wait-simple wait-twice wait-killed wait-bad-pid multi-recurse multi-oom multi-child-fd); clean_dir (), exit if $action eq 'clean'; diff --git a/grading/userprog/tests.txt b/grading/userprog/tests.txt index dd3ef0a..e6d6599 100644 --- a/grading/userprog/tests.txt +++ b/grading/userprog/tests.txt @@ -68,18 +68,25 @@ System calls: write Score: /9 System calls: exec - -2 exec-once: call exec/join once + -2 exec-once: call exec/wait once -2 exec-arg: check command-line passing on exec - -2 exec-multiple: call exec/join multiple times + -2 exec-multiple: call exec/wait multiple times -2 exec-missing: exec of nonexistent file must return -1 -1 exec-bad-ptr: pass invalid pointer to exec system call Score: /9 -System calls: join - -2 join-simple: join must return proper value - -2 join-twice: join a subprocess two times - -2 join-killed: join must return -1 if subprocess killed by kernel - -1 join-bad-pid: join must return if passed bad pid +System calls: wait + -2 wait-once: A creates B, A waits for B + -2 wait-twice: A creates B, A waits for B, A waits for B again + -2 wait-quick: A creates B, A waits for B, with different details + -2 wait-multiple: A creates B and C, A waits for B, A waits for C + -2 wait-nested: A creates B, B creates C, ..., B waits for C, A waits for B + -2 wait-dummy: A creates B, A waits for B, A waits for B + -2 wait-invalid: Waiting for an invalid pid must return immediately + -2 wait-other: Waiting for a child of another process must return immediately + -2 wait-no: A creates B and never waits for it (must not crash or hang) +Score: /14 + Score: /7 Multiprogramming diff --git a/grading/userprog/wait-bad-pid.c b/grading/userprog/wait-bad-pid.c new file mode 100644 index 0000000..6b8cf88 --- /dev/null +++ b/grading/userprog/wait-bad-pid.c @@ -0,0 +1,11 @@ +#include +#include + +int +main (void) +{ + printf ("(wait-bad-pid) begin\n"); + wait ((pid_t) 0x20101234); + printf ("(wait-bad-pid) end\n"); + return 0; +} diff --git a/grading/userprog/wait-bad-pid.exp b/grading/userprog/wait-bad-pid.exp new file mode 100644 index 0000000..8795167 --- /dev/null +++ b/grading/userprog/wait-bad-pid.exp @@ -0,0 +1,6 @@ +(wait-bad-pid) begin +(wait-bad-pid) end +wait-bad-pid: exit(0) +--OR-- +(wait-bad-pid) begin +wait-bad-pid: exit(-1) diff --git a/grading/userprog/wait-killed.c b/grading/userprog/wait-killed.c new file mode 100644 index 0000000..f1ee40c --- /dev/null +++ b/grading/userprog/wait-killed.c @@ -0,0 +1,11 @@ +#include +#include + +int +main (void) +{ + printf ("(wait-killed) begin\n"); + printf ("(wait-killed) wait(exec()) = %d\n", wait (exec ("child-bad"))); + printf ("(wait-killed) end\n"); + return 0; +} diff --git a/grading/userprog/wait-killed.exp b/grading/userprog/wait-killed.exp new file mode 100644 index 0000000..3032421 --- /dev/null +++ b/grading/userprog/wait-killed.exp @@ -0,0 +1,6 @@ +(wait-killed) begin +(child-bad) begin +child-bad: exit(-1) +(wait-killed) wait(exec()) = -1 +(wait-killed) end +wait-killed: exit(0) diff --git a/grading/userprog/wait-simple.c b/grading/userprog/wait-simple.c new file mode 100644 index 0000000..f0ab5eb --- /dev/null +++ b/grading/userprog/wait-simple.c @@ -0,0 +1,11 @@ +#include +#include + +int +main (void) +{ + printf ("(wait-simple) begin\n"); + printf ("(wait-simple) wait(exec()) = %d\n", wait (exec ("child-simple"))); + printf ("(wait-simple) end\n"); + return 0; +} diff --git a/grading/userprog/wait-simple.exp b/grading/userprog/wait-simple.exp new file mode 100644 index 0000000..082f1a3 --- /dev/null +++ b/grading/userprog/wait-simple.exp @@ -0,0 +1,6 @@ +(wait-simple) begin +(child-simple) run +child-simple: exit(81) +(wait-simple) wait(exec()) = 81 +(wait-simple) end +wait-simple: exit(0) diff --git a/grading/userprog/wait-twice.c b/grading/userprog/wait-twice.c new file mode 100644 index 0000000..c104b61 --- /dev/null +++ b/grading/userprog/wait-twice.c @@ -0,0 +1,14 @@ +#include +#include + +int +main (void) +{ + pid_t child; + printf ("(wait-twice) begin\n"); + child = exec ("child-simple"); + printf ("(wait-twice) wait(exec()) = %d\n", wait (child)); + wait (child); + printf ("(wait-twice) end\n"); + return 0; +} diff --git a/grading/userprog/wait-twice.exp b/grading/userprog/wait-twice.exp new file mode 100644 index 0000000..fd6bf29 --- /dev/null +++ b/grading/userprog/wait-twice.exp @@ -0,0 +1,6 @@ +(wait-twice) begin +(child-simple) run +child-simple: exit(81) +(wait-twice) wait(exec()) = 81 +(wait-twice) end +wait-twice: exit(0) diff --git a/grading/vm/mmap-exit.c b/grading/vm/mmap-exit.c index f49d78e..3601df8 100644 --- a/grading/vm/mmap-exit.c +++ b/grading/vm/mmap-exit.c @@ -27,10 +27,10 @@ main (void) printf ("(mmap-exit) exec() failed\n"); return 1; } - code = join (child); + code = wait (child); if (code != 234) { - printf ("(mmap-exit) join() returned bad exit code: %d\n", code); + printf ("(mmap-exit) wait() returned bad exit code: %d\n", code); return 1; } printf ("(mmap-exit) child finished\n"); diff --git a/grading/vm/page-merge-par.c b/grading/vm/page-merge-par.c index 8f3be48..36f7840 100644 --- a/grading/vm/page-merge-par.c +++ b/grading/vm/page-merge-par.c @@ -75,9 +75,9 @@ sort_chunks (void) char fn[128]; int fd; - if (join (children[i]) != 123) + if (wait (children[i]) != 123) { - printf ("(page-merge-par) join(exec()) returned bad value\n"); + printf ("(page-merge-par) wait(exec()) returned bad value\n"); exit (1); } diff --git a/grading/vm/page-merge-seq.c b/grading/vm/page-merge-seq.c index 57cd53c..34d14f6 100644 --- a/grading/vm/page-merge-seq.c +++ b/grading/vm/page-merge-seq.c @@ -64,9 +64,9 @@ sort_chunks (void) printf ("(page-merge-seq) exec() failed\n"); exit (1); } - if (join (child) != 123) + if (wait (child) != 123) { - printf ("(page-merge-seq) join(exec()) returned bad value\n"); + printf ("(page-merge-seq) wait(exec()) returned bad value\n"); exit (1); } diff --git a/grading/vm/page-parallel.c b/grading/vm/page-parallel.c index f1c3ce0..034a162 100644 --- a/grading/vm/page-parallel.c +++ b/grading/vm/page-parallel.c @@ -28,8 +28,8 @@ main (void) for (i = 0; i < CHILD_CNT; i++) { int code; - printf ("(page-parallel) join child %d\n", i); - code = join (children[i]); + printf ("(page-parallel) wait for child %d\n", i); + code = wait (children[i]); if (code != 0x42) printf ("(page-parallel) child %d returned bad exit code\n", i); } diff --git a/grading/vm/page-parallel.exp b/grading/vm/page-parallel.exp index a3ac6c3..6a2a0b8 100644 --- a/grading/vm/page-parallel.exp +++ b/grading/vm/page-parallel.exp @@ -2,7 +2,7 @@ (page-parallel) start child 0 (page-parallel) start child 1 (page-parallel) start child 2 -(page-parallel) join child 0 -(page-parallel) join child 1 -(page-parallel) join child 2 +(page-parallel) wait for child 0 +(page-parallel) wait for child 1 +(page-parallel) wait for child 2 (page-parallel) end diff --git a/grading/vm/posix-compat.c b/grading/vm/posix-compat.c index a4aae6b..0625461 100644 --- a/grading/vm/posix-compat.c +++ b/grading/vm/posix-compat.c @@ -11,7 +11,7 @@ #undef halt #undef exit #undef exec -#undef join +#undef wait #undef create #undef remove #undef open @@ -68,7 +68,7 @@ pintos_exec (const char *cmd_line) } int -pintos_join (pid_t child) +pintos_wait (pid_t child) { int status = 0; waitpid (child, &status, 0); diff --git a/grading/vm/posix-compat.h b/grading/vm/posix-compat.h index df77e43..70dee12 100644 --- a/grading/vm/posix-compat.h +++ b/grading/vm/posix-compat.h @@ -20,9 +20,9 @@ void pintos_exit (int status) NO_RETURN; #define exec pintos_exec pid_t pintos_exec (const char *file); -#undef join -#define join pintos_join -int pintos_join (pid_t); +#undef wait +#define wait pintos_wait +int pintos_wait (pid_t); #undef create #define create pintos_create diff --git a/src/lib/syscall-nr.h b/src/lib/syscall-nr.h index 5a243bd..0185109 100644 --- a/src/lib/syscall-nr.h +++ b/src/lib/syscall-nr.h @@ -5,7 +5,7 @@ #define SYS_halt 0 /* Halts the operating system. */ #define SYS_exit 1 /* Terminates this process. */ #define SYS_exec 2 /* Start another process. */ -#define SYS_join 3 /* Waits for a child process to die. */ +#define SYS_wait 3 /* Waits for a child process to die. */ #define SYS_create 4 /* Creates a file. */ #define SYS_remove 5 /* Deletes a file. */ #define SYS_open 6 /* Opens a file. */ diff --git a/src/lib/user/syscall.c b/src/lib/user/syscall.c index b6120fd..078d796 100644 --- a/src/lib/user/syscall.c +++ b/src/lib/user/syscall.c @@ -82,9 +82,9 @@ exec (const char *file) } int -join (pid_t pid) +wait (pid_t pid) { - return syscall1 (SYS_join, pid); + return syscall1 (SYS_wait, pid); } bool diff --git a/src/lib/user/syscall.h b/src/lib/user/syscall.h index 1472525..c294108 100644 --- a/src/lib/user/syscall.h +++ b/src/lib/user/syscall.h @@ -13,7 +13,7 @@ typedef int mapid_t; void halt (void) NO_RETURN; void exit (int status) NO_RETURN; pid_t exec (const char *file); -int join (pid_t); +int wait (pid_t); bool create (const char *file, unsigned initial_size); bool remove (const char *file); int open (const char *file); diff --git a/src/tests/threads/p1-2.c b/src/tests/threads/p1-2.c index fb39bb1..50a4fcf 100644 --- a/src/tests/threads/p1-2.c +++ b/src/tests/threads/p1-2.c @@ -1,105 +1,113 @@ -/* Problem 1-2: Join tests. +/* Problem 1-2: Priority Scheduling tests. Based on a test originally submitted for Stanford's CS 140 in - winter 1998 by Rob Baesman , Ben - Taskar , and Toli Kuznets - . Later modified by shiangc, yph, and - arens. */ + winter 1999 by by Matt Franklin + , Greg Hutchins + , Yu Ping Hu . + Modified by arens. */ + +#ifdef MLFQS +#error This test not applicable with MLFQS enabled. +#endif + #include "threads/test.h" #include -#include "threads/interrupt.h" +#include "threads/synch.h" #include "threads/thread.h" -static void simple_test (void); -static void quick_test (void); -static void multiple_test (void); +static void test_preempt (void); +static void test_fifo (void); +static void test_donate_return (void); void test (void) { - simple_test (); - quick_test (); - multiple_test (); -} + /* Make sure our priority is the default. */ + ASSERT (thread_get_priority () == PRI_DEFAULT); + test_preempt (); + test_fifo (); + test_donate_return (); +} + static thread_func simple_thread_func; -static thread_func quick_thread_func; +static thread_func acquire_thread_func; static void -simple_test (void) +test_preempt (void) { - tid_t tid0; - printf ("\n" - "Testing simple join.\n" - "Thread 0 should finish before thread 1 starts.\n"); - tid0 = thread_create ("0", PRI_DEFAULT, simple_thread_func, "0"); - thread_yield (); - thread_join (tid0); - simple_thread_func ("1"); - printf ("Simple join test done.\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 -quick_test (void) +test_fifo (void) { - tid_t tid2; + int i; printf ("\n" - "Testing quick join.\n" - "Thread 2 should finish before thread 3 starts.\n"); - - tid2 = thread_create ("2", PRI_DEFAULT, quick_thread_func, "2"); - thread_yield (); - thread_join (tid2); - simple_thread_func ("3"); - printf ("Quick join test done.\n"); + "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 < 10; i++) + { + char name[16]; + snprintf (name, sizeof name, "%d", i); + thread_create (name, PRI_DEFAULT + 1, simple_thread_func, NULL); + } + thread_set_priority (PRI_DEFAULT); + + printf ("FIFO preemption test done.\n"); } static void -multiple_test (void) +test_donate_return (void) { - tid_t tid4, tid5; - + struct lock lock; + printf ("\n" - "Testing multiple join.\n" - "Threads 4 and 5 should finish before thread 6 starts.\n"); - - tid4 = thread_create ("4", PRI_DEFAULT, simple_thread_func, "4"); - tid5 = thread_create ("5", PRI_DEFAULT, simple_thread_func, "5"); - thread_yield (); - thread_join (tid4); - thread_join (tid5); - simple_thread_func ("6"); - printf ("Multiple join test done.\n"); + "Testing priority donation.\n" + "If the statements printed below are all true, you pass.\n"); + + 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"); } -void -simple_thread_func (void *name_) +static void +simple_thread_func (void *aux UNUSED) { - const char *name = name_; int i; for (i = 0; i < 5; i++) { - printf ("Thread %s iteration %d\n", name, i); + printf ("Thread %s iteration %d\n", thread_name (), i); thread_yield (); } - printf ("Thread %s done!\n", name); + printf ("Thread %s done!\n", thread_name ()); } -void -quick_thread_func (void *name_) +static void +acquire_thread_func (void *lock_) { - const char *name = name_; - int i; + struct lock *lock = lock_; - intr_disable (); - - for (i = 0; i < 5; i++) - { - printf ("Thread %s iteration %d\n", name, i); - thread_yield (); - } - printf ("Thread %s done!\n", name); + lock_acquire (lock); + printf ("%s: got the lock\n", thread_name ()); + lock_release (lock); + printf ("%s: done\n", thread_name ()); } diff --git a/src/tests/threads/p1-3.c b/src/tests/threads/p1-3.c index 6c16023..1b6dbdc 100644 --- a/src/tests/threads/p1-3.c +++ b/src/tests/threads/p1-3.c @@ -1,113 +1,130 @@ -/* Problem 1-3: Priority Scheduling tests. +/* Problem 1-3: Advanced Scheduler tests. + + This depends on a correctly working Alarm Clock (Problem 1-1). + + Run this test with and without the MLFQS enabled. The + threads' reported test should be better with MLFQS on than + with it off. You may have to tune the loop counts to get + reasonable numbers. 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. */ + Modified by arens and yph. */ -#ifdef MLFQS -#error This test not applicable with MLFQS enabled. -#endif +/* Uncomment to print progress messages. */ +/*#define SHOW_PROGRESS*/ #include "threads/test.h" #include +#include #include "threads/synch.h" #include "threads/thread.h" +#include "devices/timer.h" -static void test_preempt (void); -static void test_fifo (void); -static void test_donate_return (void); +static thread_func io_thread; +static thread_func cpu_thread; +static thread_func io_cpu_thread; void test (void) { - /* Make sure our priority is the default. */ - ASSERT (thread_get_priority () == PRI_DEFAULT); + static thread_func *funcs[] = {io_thread, cpu_thread, io_cpu_thread}; + static const char *names[] = {"IO", "CPU", "IO & CPU"}; + struct semaphore done[3]; + int i; + + printf ("\n" + "Testing multilevel feedback queue scheduler.\n"); + + /* Start threads. */ + for (i = 0; i < 3; i++) + { + sema_init (&done[i], 0, names[i]); + thread_create (names[i], PRI_DEFAULT, funcs[i], &done[i]); + } - test_preempt (); - test_fifo (); - test_donate_return (); + /* Wait for threads to finish. */ + for (i = 0; i < 3; i++) + sema_down (&done[i]); + printf ("Multilevel feedback queue scheduler test done.\n"); } - -static thread_func simple_thread_func; -static thread_func acquire_thread_func; static void -test_preempt (void) +cpu_thread (void *sema_) { - 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"); + struct semaphore *sema = sema_; + int64_t start = timer_ticks (); + struct lock lock; + int i; + + lock_init (&lock, "cpu"); + + for (i = 0; i < 5000; i++) + { + lock_acquire (&lock); +#ifdef SHOW_PROGRESS + printf ("CPU intensive: %d\n", thread_get_priority ()); +#endif + lock_release (&lock); + } + + printf ("CPU bound thread finished in %"PRId64" ticks.\n", + timer_elapsed (start)); + + sema_up (sema); } static void -test_fifo (void) +io_thread (void *sema_) { + struct semaphore *sema = sema_; + int64_t start = timer_ticks (); int i; - - printf ("\n" - "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 < 10; i++) + for (i = 0; i < 1000; i++) { - char name[16]; - snprintf (name, sizeof name, "%d", i); - thread_create (name, PRI_DEFAULT + 1, simple_thread_func, NULL); + timer_sleep (10); +#ifdef SHOW_PROGRESS + printf ("IO intensive: %d\n", thread_get_priority ()); +#endif } - thread_set_priority (PRI_DEFAULT); - printf ("FIFO preemption test done.\n"); + printf ("IO bound thread finished in %"PRId64" ticks.\n", + timer_elapsed (start)); + + sema_up (sema); } static void -test_donate_return (void) +io_cpu_thread (void *sema_) { + struct semaphore *sema = sema_; struct lock lock; + int64_t start = timer_ticks (); + int i; - printf ("\n" - "Testing priority donation.\n" - "If the statements printed below are all true, you pass.\n"); - - 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_init (&lock, "io & cpu"); -static void -simple_thread_func (void *aux UNUSED) -{ - int i; - - for (i = 0; i < 5; i++) + for (i = 0; i < 800; i++) { - printf ("Thread %s iteration %d\n", thread_name (), i); - thread_yield (); + int j; + + timer_sleep (10); + + for (j = 0; j < 15; j++) + { + lock_acquire (&lock); +#ifdef SHOW_PROGRESS + printf ("Alternating IO/CPU: %d\n", thread_get_priority ()); +#endif + lock_release (&lock); + } } - 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 ()); + printf ("Alternating IO/CPU thread finished in %"PRId64" ticks.\n", + timer_elapsed (start)); + + sema_up (sema); } diff --git a/src/tests/threads/p1-4.c b/src/tests/threads/p1-4.c deleted file mode 100644 index 1f97b2e..0000000 --- a/src/tests/threads/p1-4.c +++ /dev/null @@ -1,130 +0,0 @@ -/* Problem 1-4: Advanced Scheduler tests. - - This depends on a correctly working Alarm Clock (Problem 1-1). - - Run this test with and without the MLFQS enabled. The - threads' reported test should be better with MLFQS on than - with it off. You may have to tune the loop counts to get - reasonable numbers. - - 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 and yph. */ - -/* Uncomment to print progress messages. */ -/*#define SHOW_PROGRESS*/ - -#include "threads/test.h" -#include -#include -#include "threads/synch.h" -#include "threads/thread.h" -#include "devices/timer.h" - -static thread_func io_thread; -static thread_func cpu_thread; -static thread_func io_cpu_thread; - -void -test (void) -{ - static thread_func *funcs[] = {io_thread, cpu_thread, io_cpu_thread}; - static const char *names[] = {"IO", "CPU", "IO & CPU"}; - struct semaphore done[3]; - int i; - - printf ("\n" - "Testing multilevel feedback queue scheduler.\n"); - - /* Start threads. */ - for (i = 0; i < 3; i++) - { - sema_init (&done[i], 0, names[i]); - thread_create (names[i], PRI_DEFAULT, funcs[i], &done[i]); - } - - /* Wait for threads to finish. */ - for (i = 0; i < 3; i++) - sema_down (&done[i]); - printf ("Multilevel feedback queue scheduler test done.\n"); -} - -static void -cpu_thread (void *sema_) -{ - struct semaphore *sema = sema_; - int64_t start = timer_ticks (); - struct lock lock; - int i; - - lock_init (&lock, "cpu"); - - for (i = 0; i < 5000; i++) - { - lock_acquire (&lock); -#ifdef SHOW_PROGRESS - printf ("CPU intensive: %d\n", thread_get_priority ()); -#endif - lock_release (&lock); - } - - printf ("CPU bound thread finished in %"PRId64" ticks.\n", - timer_elapsed (start)); - - sema_up (sema); -} - -static void -io_thread (void *sema_) -{ - struct semaphore *sema = sema_; - int64_t start = timer_ticks (); - int i; - - for (i = 0; i < 1000; i++) - { - timer_sleep (10); -#ifdef SHOW_PROGRESS - printf ("IO intensive: %d\n", thread_get_priority ()); -#endif - } - - printf ("IO bound thread finished in %"PRId64" ticks.\n", - timer_elapsed (start)); - - sema_up (sema); -} - -static void -io_cpu_thread (void *sema_) -{ - struct semaphore *sema = sema_; - struct lock lock; - int64_t start = timer_ticks (); - int i; - - lock_init (&lock, "io & cpu"); - - for (i = 0; i < 800; i++) - { - int j; - - timer_sleep (10); - - for (j = 0; j < 15; j++) - { - lock_acquire (&lock); -#ifdef SHOW_PROGRESS - printf ("Alternating IO/CPU: %d\n", thread_get_priority ()); -#endif - lock_release (&lock); - } - } - - printf ("Alternating IO/CPU thread finished in %"PRId64" ticks.\n", - timer_elapsed (start)); - - sema_up (sema); -} diff --git a/src/tests/userprog/recursor.c b/src/tests/userprog/recursor.c index f787a90..79c784a 100644 --- a/src/tests/userprog/recursor.c +++ b/src/tests/userprog/recursor.c @@ -11,7 +11,7 @@ main (int argc, char *argv[]) if (argc != 4) { - printf ("usage: recursor \n"); + printf ("usage: recursor \n"); exit (1); } @@ -25,7 +25,7 @@ main (int argc, char *argv[]) "recursor %s %d %s", argv[1], atoi (argv[2]) - 1, argv[3]); pid = exec (buffer); if (atoi (argv[3])) - retval = join (pid); + retval = wait (pid); } /* Done. */ diff --git a/src/tests/userprog/shell.c b/src/tests/userprog/shell.c index 7b9570a..7cf5c60 100644 --- a/src/tests/userprog/shell.c +++ b/src/tests/userprog/shell.c @@ -26,7 +26,7 @@ main (void) { pid_t pid = exec (command); if (pid != PID_ERROR) - join (pid); + wait (pid); else printf ("exec failed\n"); } diff --git a/src/threads/init.c b/src/threads/init.c index b4b1057..f6a01dc 100644 --- a/src/threads/init.c +++ b/src/threads/init.c @@ -120,11 +120,8 @@ main (void) /* Run a user program. */ if (initial_program != NULL) { - tid_t tid; printf ("\nExecuting '%s':\n", initial_program); - tid = process_execute (initial_program); - if (tid != TID_ERROR) - thread_join (tid); + process_wait (process_execute (initial_program)); } #else /* Run the compiled-in test function. */ diff --git a/src/threads/thread.c b/src/threads/thread.c index ae92e1d..6eda280 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -274,17 +274,6 @@ thread_yield (void) intr_set_level (old_level); } -/* Waits for the thread with the specified TID to terminate. If - TID has already terminated or TID does not refer to an - immediate child of the current thread, returns immediately. - - This function will be implemented in problem 1-2. For now, it - does nothing. */ -void -thread_join (tid_t child_tid UNUSED) -{ -} - /* Sets the current thread's priority to NEW_PRIORITY. */ void thread_set_priority (int new_priority) diff --git a/src/threads/thread.h b/src/threads/thread.h index fe7db89..1f17a9c 100644 --- a/src/threads/thread.h +++ b/src/threads/thread.h @@ -119,8 +119,6 @@ const char *thread_name (void); void thread_exit (void) NO_RETURN; void thread_yield (void); -void thread_join (tid_t); - void thread_set_priority (int); int thread_get_priority (void); diff --git a/src/userprog/process.c b/src/userprog/process.c index 88c9d8d..b1e11d1 100644 --- a/src/userprog/process.c +++ b/src/userprog/process.c @@ -21,8 +21,9 @@ static thread_func execute_thread NO_RETURN; static bool load (const char *cmdline, void (**eip) (void), void **esp); /* Starts a new thread running a user program loaded from - FILENAME. The new thread may be scheduled before - process_execute() returns.*/ + FILENAME. The new thread may be scheduled (and may even exit) + before process_execute() returns. Returns the new process's + thread id, or TID_ERROR if the thread cannot be created. */ tid_t process_execute (const char *filename) { @@ -54,13 +55,9 @@ execute_thread (void *filename_) /* Initialize interrupt frame and load executable. */ memset (&if_, 0, sizeof if_); - if_.gs = SEL_UDSEG; - if_.fs = SEL_UDSEG; - if_.es = SEL_UDSEG; - if_.ds = SEL_UDSEG; + if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG; if_.cs = SEL_UCSEG; if_.eflags = FLAG_IF | FLAG_MBS; - if_.ss = SEL_UDSEG; success = load (filename, &if_.eip, &if_.esp); /* If load failed, quit. */ @@ -68,9 +65,6 @@ execute_thread (void *filename_) if (!success) thread_exit (); - /* Switch page tables. */ - process_activate (); - /* Start the user process by simulating a return from an interrupt, implemented by intr_exit (in threads/intr-stubs.S). Because intr_exit takes all of its @@ -81,6 +75,21 @@ execute_thread (void *filename_) NOT_REACHED (); } +/* Waits for thread TID to die and returns its exit status. If + it was terminated by the kernel (i.e. killed due to an + exception), returns -1. If TID is invalid or if it was not a + child of the calling process, or if process_wait() has already + been successfully called for the given TID, returns -1 + immediately, without waiting. + + This function will be implemented in problem 2-2. For now, it + does nothing. */ +int +process_wait (tid_t child_tid UNUSED) +{ + return -1; +} + /* Free the current process's resources. */ void process_exit (void) @@ -89,14 +98,18 @@ process_exit (void) uint32_t *pd; /* Destroy the current process's page directory and switch back - to the kernel-only page directory. We have to set - cur->pagedir to NULL before switching page directories, or a - timer interrupt might switch back to the process page - directory. */ + to the kernel-only page directory. */ pd = cur->pagedir; if (pd != NULL) { + /* We must set cur->pagedir to NULL before switching page + directories, or a timer interrupt might switch back to + the process page directory. The asm statement prevents + GCC from reordering the assignment and the function + calls. */ cur->pagedir = NULL; + asm volatile (""); + pagedir_activate (NULL); pagedir_destroy (pd); } @@ -184,12 +197,12 @@ static bool load_segment (struct file *, const struct Elf32_Phdr *); static bool setup_stack (void **esp); /* Aborts loading an executable, with an error message. */ -#define LOAD_ERROR(MSG) \ - do { \ - printf ("load: %s: ", filename); \ - printf MSG; \ - printf ("\n"); \ - goto done; \ +#define LOAD_ERROR(MSG) \ + do { \ + printf ("load: %s: ", filename); \ + printf MSG; \ + printf ("\n"); \ + goto done; \ } while (0) /* Loads an ELF executable from FILENAME into the current thread. @@ -206,10 +219,11 @@ load (const char *filename, void (**eip) (void), void **esp) bool success = false; int i; - /* Allocate page directory. */ + /* Allocate and activate page directory. */ t->pagedir = pagedir_create (); if (t->pagedir == NULL) LOAD_ERROR (("page directory allocation failed")); + process_activate (); /* Open executable file. */ file = filesys_open (filename); diff --git a/src/userprog/process.h b/src/userprog/process.h index 2db1021..228c324 100644 --- a/src/userprog/process.h +++ b/src/userprog/process.h @@ -4,6 +4,7 @@ #include "threads/thread.h" tid_t process_execute (const char *filename); +int process_wait (tid_t); void process_exit (void); void process_activate (void); diff --git a/tests/Makefile b/tests/Makefile index efea7a5..2450e56 100644 --- a/tests/Makefile +++ b/tests/Makefile @@ -1,4 +1,4 @@ -TESTS = threads p1-1 p1-2 p1-3 list stdlib userprog p2 vm filesys +TESTS = threads p1-1 p1-2 list stdlib userprog p2 vm filesys PATH := $(shell pwd)/../src/utils:$(PATH) @@ -67,13 +67,6 @@ p1-2: PROJECT = threads p1-2:: $(mk-sandbox) $(apply-patch) ../solutions/p1-2.patch - $(run-tests) -d join.* - $(clean) - -p1-3: PROJECT = threads -p1-3:: - $(mk-sandbox) - $(apply-patch) ../solutions/p1-3.patch $(run-tests) -d priority.* $(clean) @@ -90,7 +83,7 @@ userprog: PROJECT = userprog userprog:: $(prep-grading) $(mk-sandbox) - $(apply-patch) ../solutions/p1-2.patch + $(apply-patch) ../solutions/p2-null.patch $(run-tests) null $(clean)