From 15aa248a41556196803c75cb4f56ddad05f5d64e Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Thu, 31 Mar 2005 04:58:27 +0000 Subject: [PATCH] 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(). --- TODO | 13 +- doc/doc.texi | 15 +- doc/mlfqs.texi | 2 +- doc/standards.texi | 4 +- doc/threads.texi | 131 ++------- doc/tour.texi | 2 +- doc/userprog.texi | 50 +++- grading/filesys/fslib.c | 6 +- grading/filesys/fslib.h | 2 +- grading/filesys/syn-read.c | 2 +- grading/filesys/syn-read.exp | 20 +- grading/filesys/syn-rw.c | 2 +- grading/filesys/syn-write.c | 2 +- grading/filesys/syn-write.exp | 20 +- grading/threads/join-dummy.c | 52 ---- grading/threads/join-dummy.exp | 15 - grading/threads/join-invalid.c | 50 ---- grading/threads/join-multiple.c | 53 ---- grading/threads/join-nested.c | 58 ---- grading/threads/join-nested.exp | 20 -- grading/threads/join-no.c | 49 ---- grading/threads/join-quick.c | 66 ----- grading/threads/join-quick.exp | 15 - grading/threads/join-simple.c | 50 ---- grading/threads/join-simple.exp | 15 - grading/threads/review.txt | 15 +- grading/threads/run-tests | 52 ---- grading/threads/tests.txt | 14 +- grading/userprog/.cvsignore | 8 +- grading/userprog/Make.base | 4 +- grading/userprog/Make.tests | 8 +- grading/userprog/Makefile | 14 +- grading/userprog/exec-arg.c | 2 +- grading/userprog/exec-multiple.c | 8 +- grading/userprog/exec-once.c | 2 +- grading/userprog/join-bad-pid.c | 11 - grading/userprog/join-bad-pid.exp | 6 - grading/userprog/join-killed.c | 11 - grading/userprog/join-killed.exp | 6 - grading/userprog/join-simple.c | 11 - grading/userprog/join-simple.exp | 6 - grading/userprog/join-twice.c | 14 - grading/userprog/join-twice.exp | 6 - grading/userprog/multi-child-fd.c | 2 +- grading/userprog/multi-child-fd.exp | 4 +- grading/userprog/multi-oom.c | 4 +- grading/userprog/multi-parent-fd.c | 2 +- grading/userprog/multi-recurse.c | 4 +- grading/userprog/prep-disk | 4 +- grading/userprog/review.txt | 9 + grading/userprog/run-tests | 2 +- grading/userprog/tests.txt | 21 +- grading/userprog/wait-bad-pid.c | 11 + grading/userprog/wait-bad-pid.exp | 6 + grading/userprog/wait-killed.c | 11 + grading/userprog/wait-killed.exp | 6 + grading/userprog/wait-simple.c | 11 + grading/userprog/wait-simple.exp | 6 + grading/userprog/wait-twice.c | 14 + grading/userprog/wait-twice.exp | 6 + grading/vm/mmap-exit.c | 4 +- grading/vm/page-merge-par.c | 4 +- grading/vm/page-merge-seq.c | 4 +- grading/vm/page-parallel.c | 4 +- grading/vm/page-parallel.exp | 6 +- grading/vm/posix-compat.c | 4 +- grading/vm/posix-compat.h | 6 +- solutions/README | 5 +- solutions/p1-2.patch | 407 +++++++++++++++++--------- solutions/p1-3.patch | 308 -------------------- solutions/p2-null.patch | 183 ++++++++++++ solutions/p2.patch | 427 ++++++++++++---------------- src/lib/syscall-nr.h | 2 +- src/lib/user/syscall.c | 4 +- src/lib/user/syscall.h | 2 +- src/tests/threads/p1-2.c | 136 ++++----- src/tests/threads/p1-3.c | 161 ++++++----- src/tests/threads/p1-4.c | 130 --------- src/tests/userprog/recursor.c | 4 +- src/tests/userprog/shell.c | 2 +- src/threads/init.c | 5 +- src/threads/thread.c | 11 - src/threads/thread.h | 2 - src/userprog/process.c | 56 ++-- src/userprog/process.h | 1 + tests/Makefile | 11 +- 86 files changed, 1101 insertions(+), 1823 deletions(-) delete mode 100644 grading/threads/join-dummy.c delete mode 100644 grading/threads/join-dummy.exp delete mode 100644 grading/threads/join-invalid.c delete mode 100644 grading/threads/join-multiple.c delete mode 100644 grading/threads/join-nested.c delete mode 100644 grading/threads/join-nested.exp delete mode 100644 grading/threads/join-no.c delete mode 100644 grading/threads/join-quick.c delete mode 100644 grading/threads/join-quick.exp delete mode 100644 grading/threads/join-simple.c delete mode 100644 grading/threads/join-simple.exp delete mode 100644 grading/userprog/join-bad-pid.c delete mode 100644 grading/userprog/join-bad-pid.exp delete mode 100644 grading/userprog/join-killed.c delete mode 100644 grading/userprog/join-killed.exp delete mode 100644 grading/userprog/join-simple.c delete mode 100644 grading/userprog/join-simple.exp delete mode 100644 grading/userprog/join-twice.c delete mode 100644 grading/userprog/join-twice.exp create mode 100644 grading/userprog/wait-bad-pid.c create mode 100644 grading/userprog/wait-bad-pid.exp create mode 100644 grading/userprog/wait-killed.c create mode 100644 grading/userprog/wait-killed.exp create mode 100644 grading/userprog/wait-simple.c create mode 100644 grading/userprog/wait-simple.exp create mode 100644 grading/userprog/wait-twice.c create mode 100644 grading/userprog/wait-twice.exp delete mode 100644 solutions/p1-3.patch create mode 100644 solutions/p2-null.patch delete mode 100644 src/tests/threads/p1-4.c diff --git a/TODO b/TODO index 3e9c3e4..494cd72 100644 --- a/TODO +++ b/TODO @@ -11,8 +11,6 @@ * Threads: - - join-invalid doesn't compile if tid_t is not scalar type. - - mlfqs tests suck. They aren't even correct, e.g. the amarv submission from win0405 is graded incorrectly. @@ -24,12 +22,6 @@ project 3 and in real OSes. Also revise the grading criteria to match. - - Move `join' implementation here, from `threads' project, to help - normalize the project difficulties. - - - The semantics of the join system call should change so that it - only returns the exit code once. - - Mark read-only pages as actually read-only in the page table. Or, since this was consistently rated as the easiest project by the students, require them to do it. @@ -124,3 +116,8 @@ - Get rid of all compile-time flags, e.g. MLFQS should be a runtime command-line option. + + - Need an optimization barrier and an explanation of it in the + documentation. + + - Need to check the wait system call more thoroughly. 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/solutions/README b/solutions/README index ab3e9a0..a4dabc0 100644 --- a/solutions/README +++ b/solutions/README @@ -1,8 +1,9 @@ Sample solutions. -* The solutions for p1-1, p1-2, p1-3, and p2 are good enough. They +* The solutions for p1-1, p1-2, and p2 are good enough. They pass all the appropriate tests in the grading directory. * The solution for p3 is terrible. For example, there's no locking at all. I just wrote it to make sure that the project was possible - given the tools that we gave the students. + given the tools that we gave the students. It also suffers from bit + rot and won't actually apply anymore. diff --git a/solutions/p1-2.patch b/solutions/p1-2.patch index 3c0866e..70944ed 100644 --- a/solutions/p1-2.patch +++ b/solutions/p1-2.patch @@ -1,169 +1,308 @@ -diff -X pat -urpN threads/synch.c! src/threads/synch.c ---- src/threads/synch.c~ 2004-09-19 21:29:53.000000000 -0700 -+++ src/threads/synch.c 2004-09-27 16:50:14.000000000 -0700 -@@ -330,3 +330,35 @@ cond_name (const struct condition *cond) - - return cond->name; +Index: src/threads/synch.c +=================================================================== +RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/synch.c,v +retrieving revision 1.15 +diff -u -p -u -r1.15 synch.c +--- src/threads/synch.c 31 Dec 2004 21:13:38 -0000 1.15 ++++ src/threads/synch.c 31 Dec 2004 22:31:03 -0000 +@@ -77,6 +77,18 @@ sema_down (struct semaphore *sema) + intr_set_level (old_level); } -+ -+void -+latch_init (struct latch *latch, const char *name) + ++/* Returns true if thread A has lower priority than thread B. */ ++static bool ++donated_lower_priority (const struct list_elem *a_, ++ const struct list_elem *b_, ++ void *aux UNUSED) +{ -+ latch->released = false; -+ lock_init (&latch->monitor_lock, name); -+ cond_init (&latch->rel_cond, name); -+} ++ const struct thread *a = list_entry (a_, struct thread, donor_elem); ++ const struct thread *b = list_entry (b_, struct thread, donor_elem); + -+void -+latch_acquire (struct latch *latch) -+{ -+ lock_acquire (&latch->monitor_lock); -+ if (!latch->released) -+ { -+ cond_wait (&latch->rel_cond, &latch->monitor_lock); -+ ASSERT (latch->released); -+ } -+ lock_release (&latch->monitor_lock); ++ return a->priority < b->priority; +} + -+void -+latch_release (struct latch *latch) -+{ -+ lock_acquire (&latch->monitor_lock); -+ if (!latch->released) + /* Up or "V" operation on a semaphore. Increments SEMA's value + and wakes up one thread of those waiting for SEMA, if any. + +@@ -89,10 +100,28 @@ sema_up (struct semaphore *sema) + ASSERT (sema != NULL); + + old_level = intr_disable (); +- if (!list_empty (&sema->waiters)) +- thread_unblock (list_entry (list_pop_front (&sema->waiters), +- struct thread, elem)); + sema->value++; ++ if (!list_empty (&sema->waiters)) + { -+ latch->released = true; -+ cond_signal (&latch->rel_cond, &latch->monitor_lock); ++ /* Find highest-priority waiting thread. */ ++ struct thread *max = list_entry (list_max (&sema->waiters, ++ donated_lower_priority, NULL), ++ struct thread, elem); ++ ++ /* Remove `max' from wait list and unblock. */ ++ list_remove (&max->elem); ++ thread_unblock (max); ++ ++ /* Yield to a higher-priority thread, if we're running in a ++ context where it makes sense to do so. ++ ++ Kind of a funny interaction with donation here. ++ We only support donation for locks, and locks turn off ++ interrupts before calling us, so we automatically don't ++ do the yield here, delegating to lock_release(). */ ++ if (!intr_context () && old_level == INTR_ON) ++ thread_yield_to_higher_priority (); + } -+ lock_release (&latch->monitor_lock); -+} -diff -X pat -urpN src/threads/synch.h~ src/threads/synch.h ---- src/threads/synch.h~ 2004-09-19 21:29:53.000000000 -0700 -+++ src/threads/synch.h 2004-09-27 16:50:14.000000000 -0700 -@@ -44,4 +44,16 @@ void cond_signal (struct condition *, st - void cond_broadcast (struct condition *, struct lock *); - const char *cond_name (const struct condition *); - -+/* Latch. */ -+struct latch -+ { -+ bool released; /* Released yet? */ -+ struct lock monitor_lock; /* Monitor lock. */ -+ struct condition rel_cond; /* Signaled when released. */ -+ }; -+ -+void latch_init (struct latch *, const char *); -+void latch_acquire (struct latch *); -+void latch_release (struct latch *); -+ - #endif /* threads/synch.h */ -diff -X pat -urpN src/threads/thread.c~ src/threads/thread.c ---- src/threads/thread.c~ 2004-09-26 14:15:17.000000000 -0700 -+++ src/threads/thread.c 2004-09-27 16:51:03.000000000 -0700 -@@ -80,6 +80,7 @@ thread_init (void) - init_thread (initial_thread, "main", PRI_DEFAULT); - initial_thread->status = THREAD_RUNNING; - initial_thread->tid = allocate_tid (); -+ sema_up (&initial_thread->can_die); + intr_set_level (old_level); } - /* Starts preemptive thread scheduling by enabling interrupts. -@@ -148,6 +149,7 @@ thread_create (const char *name, int pri - /* Initialize thread. */ - init_thread (t, name, priority); - tid = t->tid = allocate_tid (); -+ list_push_back (&thread_current ()->children, &t->children_elem); - - /* Stack frame for kernel_thread(). */ - kf = alloc_frame (t, sizeof *kf); -@@ -224,16 +226,34 @@ thread_tid (void) - void - thread_exit (void) +@@ -184,6 +213,23 @@ lock_acquire (struct lock *lock) + ASSERT (!lock_held_by_current_thread (lock)); + + old_level = intr_disable (); ++ ++ if (lock->holder != NULL) ++ { ++ /* Donate our priority to the thread holding the lock. ++ First, update the data structures. */ ++ struct thread *donor = thread_current (); ++ donor->want_lock = lock; ++ donor->donee = lock->holder; ++ list_push_back (&lock->holder->donors, &donor->donor_elem); ++ ++ /* Now implement the priority donation itself ++ by recomputing the donee's priority ++ and cascading the donation as far as necessary. */ ++ while (donor->donee != NULL && thread_recompute_priority (donor->donee)) ++ donor = donor->donee; ++ } ++ + sema_down (&lock->semaphore); + lock->holder = thread_current (); + intr_set_level (old_level); +@@ -198,13 +244,38 @@ void + lock_release (struct lock *lock) { + enum intr_level old_level; + struct thread *t = thread_current (); -+ struct list_elem *e, *next; -+ - ASSERT (!intr_context ()); ++ struct list_elem *e; - #ifdef USERPROG - process_exit (); - #endif + ASSERT (lock != NULL); + ASSERT (lock_held_by_current_thread (lock)); -+ /* Notify our parent that we're dying. */ -+ latch_release (&t->ready_to_die); + old_level = intr_disable (); + -+ /* Notify our children that they can die. */ -+ for (e = list_begin (&t->children); e != list_end (&t->children); e = next) ++ /* Remove donations from threads that want the lock we're ++ releasing. */ ++ for (e = list_begin (&t->donors); e != list_end (&t->donors); ) + { -+ struct thread *child = list_entry (e, struct thread, children_elem); -+ next = list_next (e); -+ list_remove (e); -+ sema_up (&child->can_die); ++ struct thread *donor = list_entry (e, struct thread, donor_elem); ++ if (donor->want_lock == lock) ++ { ++ donor->donee = NULL; ++ e = list_remove (e); ++ } ++ else ++ e = list_next (e); + } + -+ /* Wait until our parent is ready for us to die. */ -+ sema_down (&t->can_die); ++ /* Release lock. */ + lock->holder = NULL; + sema_up (&lock->semaphore); + - /* Just set our status to dying and schedule another process. - We will be destroyed during the call to schedule_tail(). */ - intr_disable (); -- thread_current ()->status = THREAD_DYING; -+ t->status = THREAD_DYING; ++ /* Recompute our priority based on our remaining donations, ++ then yield to a higher-priority ready thread if one now ++ exists. */ ++ thread_recompute_priority (t); ++ thread_yield_to_higher_priority (); ++ + intr_set_level (old_level); + } + +Index: src/threads/thread.c +=================================================================== +RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.c,v +retrieving revision 1.48 +diff -u -p -u -r1.48 thread.c +--- src/threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48 ++++ src/threads/thread.c 31 Dec 2004 22:31:03 -0000 +@@ -166,6 +166,8 @@ thread_create (const char *name, int pri + + /* Add to run queue. */ + thread_unblock (t); ++ if (priority > thread_get_priority ()) ++ thread_yield (); + + return tid; + } +@@ -186,6 +188,19 @@ thread_block (void) schedule (); - NOT_REACHED (); } -@@ -283,8 +290,18 @@ thread_block (void) - This function will be implemented in problem 1-2. For now, it - does nothing. */ - void --thread_join (tid_t child_tid UNUSED) + ++/* Returns true if A has higher priority than B, ++ within a list of threads. */ ++static bool ++thread_higher_priority (const struct list_elem *a_, ++ const struct list_elem *b_, ++ void *aux UNUSED) ++{ ++ const struct thread *a = list_entry (a_, struct thread, elem); ++ const struct thread *b = list_entry (b_, struct thread, elem); ++ ++ return a->priority > b->priority; ++} ++ + /* Transitions a blocked thread T to the ready-to-run state. + This is an error if T is not blocked. (Use thread_yield() to + make the running thread ready.) */ +@@ -198,7 +212,7 @@ thread_unblock (struct thread *t) + + old_level = intr_disable (); + ASSERT (t->status == THREAD_BLOCKED); +- list_push_back (&ready_list, &t->elem); ++ list_insert_ordered (&ready_list, &t->elem, thread_higher_priority, NULL); + t->status = THREAD_READY; + intr_set_level (old_level); + } +@@ -266,8 +280,8 @@ thread_yield (void) + ASSERT (!intr_context ()); + + old_level = intr_disable (); +- list_push_back (&ready_list, &cur->elem); ++ list_insert_ordered (&ready_list, &cur->elem, thread_higher_priority, NULL); + cur->status = THREAD_READY; + schedule (); + intr_set_level (old_level); + } +@@ -274,19 +288,75 @@ + { + } + +-/* Sets the current thread's priority to NEW_PRIORITY. */ +-void +-thread_set_priority (int new_priority) +-{ +- thread_current ()->priority = new_priority; +-} +- +-/* Returns the current thread's priority. */ +-int +-thread_get_priority (void) -{ -+thread_join (tid_t child_tid) +- return thread_current ()->priority; +-} ++ ++/* Sets the current thread's priority to PRIORITY. */ ++void ++thread_set_priority (int priority) +{ -+ struct thread *cur = thread_current (); -+ struct list_elem *e; ++ struct thread *t = thread_current (); ++ enum intr_level old_level; ++ ++ t->normal_priority = priority; ++ ++ old_level = intr_disable (); ++ while (thread_recompute_priority (t) && t->donee != NULL) ++ t = t->donee; ++ thread_yield_to_higher_priority (); ++ intr_set_level (old_level); ++} ++ ++/* Returns the current thread's priority. */ ++int ++thread_get_priority (void) ++{ ++ return thread_current ()->priority; ++} ++ ++/* Returns true if thread A has lower priority than thread B, ++ within a list of donors. */ ++static bool ++donated_lower_priority (const struct list_elem *a_, ++ const struct list_elem *b_, ++ void *aux UNUSED) ++{ ++ const struct thread *a = list_entry (a_, struct thread, donor_elem); ++ const struct thread *b = list_entry (b_, struct thread, donor_elem); ++ ++ return a->priority < b->priority; ++} ++ ++/* Recomputes T's priority in terms of its normal priority and ++ its donors' priorities, if any. ++ Returns true if T's new priority is higher than its old ++ priority, false otherwise. */ ++bool ++thread_recompute_priority (struct thread *t) ++{ ++ int old = t->priority; ++ int donation = 0; ++ if (!list_empty (&t->donors)) ++ donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL), ++ struct thread, donor_elem)->priority; ++ t->priority = donation > t->normal_priority ? donation : t->normal_priority; ++ return t->priority > old; ++} + -+ for (e = list_begin (&cur->children); e != list_end (&cur->children); ) ++/* If the ready list contains a thread with a higher priority, ++ yields to it. */ ++void ++thread_yield_to_higher_priority (void) ++{ ++ enum intr_level old_level = intr_disable (); ++ if (!list_empty (&ready_list)) + { -+ struct thread *child = list_entry (e, struct thread, children_elem); -+ e = list_next (e); -+ if (child->tid == child_tid) -+ latch_acquire (&child->ready_to_die); ++ struct thread *cur = thread_current (); ++ struct thread *max = list_entry (list_front (&ready_list), ++ struct thread, elem); ++ if (max->priority > cur->priority) ++ thread_yield (); + } - } - - /* Sets the current thread's priority to NEW_PRIORITY. */ -@@ -335,6 +371,9 @@ init_thread (struct thread *t, const cha ++ intr_set_level (old_level); ++} + + /* Idle thread. Executes when no other thread is ready to run. */ + static void +@@ -335,8 +417,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; - t->priority = priority; -+ latch_init (&t->ready_to_die, "ready-to-die"); -+ sema_init (&t->can_die, 0, "can-die"); -+ list_init (&t->children); +- t->priority = priority; ++ t->priority = t->normal_priority = priority; t->magic = THREAD_MAGIC; ++ list_init (&t->donors); } -diff -X pat -urpN src/threads/thread.h~ src/threads/thread.h ---- src/threads/thread.h~ 2004-09-26 14:15:17.000000000 -0700 -+++ src/threads/thread.h 2004-09-27 16:50:14.000000000 -0700 -@@ -4,6 +4,7 @@ - #include - #include - #include -+#include "threads/synch.h" - - /* States in a thread's life cycle. */ - enum thread_status -@@ -89,6 +90,12 @@ struct thread + /* Allocates a SIZE-byte frame at the top of thread T's stack and +Index: src/threads/thread.h +=================================================================== +RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.h,v +retrieving revision 1.28 +diff -u -p -u -r1.28 thread.h +--- src/threads/thread.h 29 Sep 2004 01:04:20 -0000 1.28 ++++ src/threads/thread.h 31 Dec 2004 22:31:03 -0000 +@@ -87,7 +87,14 @@ struct thread + enum thread_status status; /* Thread state. */ + char name[16]; /* Name (for debugging purposes). */ uint8_t *stack; /* Saved stack pointer. */ - int priority; /* Priority. */ - -+ /* Members for implementing thread_join(). */ -+ struct latch ready_to_die; /* Release when thread about to die. */ -+ struct semaphore can_die; /* Up when thread allowed to die. */ -+ struct list children; /* List of child threads. */ -+ struct list_elem children_elem; /* Element of `children' list. */ +- int priority; /* Priority. */ + ++ /* Thread priority. */ ++ int priority; /* Priority, including donations. */ ++ int normal_priority; /* Priority, without donations. */ ++ struct list donors; /* Threads donating priority to us. */ ++ struct list_elem donor_elem; /* Element in donors list. */ ++ struct thread *donee; /* Thread we're donating to. */ ++ struct lock *want_lock; /* Lock we're waiting to acquire. */ + /* Shared between thread.c and synch.c. */ struct list_elem elem; /* List element. */ +@@ -118,6 +125,8 @@ const char *thread_name (void); + + void thread_exit (void) NO_RETURN; + void thread_yield (void); ++void thread_yield_to_higher_priority (void); ++bool thread_recompute_priority (struct thread *); + void thread_set_priority (int); + int thread_get_priority (void); diff --git a/solutions/p1-3.patch b/solutions/p1-3.patch deleted file mode 100644 index 3295f0e..0000000 --- a/solutions/p1-3.patch +++ /dev/null @@ -1,308 +0,0 @@ -Index: src/threads/synch.c -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/synch.c,v -retrieving revision 1.15 -diff -u -p -u -r1.15 synch.c ---- src/threads/synch.c 31 Dec 2004 21:13:38 -0000 1.15 -+++ src/threads/synch.c 31 Dec 2004 22:31:03 -0000 -@@ -77,6 +77,18 @@ sema_down (struct semaphore *sema) - intr_set_level (old_level); - } - -+/* Returns true if thread A has lower priority than thread B. */ -+static bool -+donated_lower_priority (const struct list_elem *a_, -+ const struct list_elem *b_, -+ void *aux UNUSED) -+{ -+ const struct thread *a = list_entry (a_, struct thread, donor_elem); -+ const struct thread *b = list_entry (b_, struct thread, donor_elem); -+ -+ return a->priority < b->priority; -+} -+ - /* Up or "V" operation on a semaphore. Increments SEMA's value - and wakes up one thread of those waiting for SEMA, if any. - -@@ -89,10 +100,28 @@ sema_up (struct semaphore *sema) - ASSERT (sema != NULL); - - old_level = intr_disable (); -- if (!list_empty (&sema->waiters)) -- thread_unblock (list_entry (list_pop_front (&sema->waiters), -- struct thread, elem)); - sema->value++; -+ if (!list_empty (&sema->waiters)) -+ { -+ /* Find highest-priority waiting thread. */ -+ struct thread *max = list_entry (list_max (&sema->waiters, -+ donated_lower_priority, NULL), -+ struct thread, elem); -+ -+ /* Remove `max' from wait list and unblock. */ -+ list_remove (&max->elem); -+ thread_unblock (max); -+ -+ /* Yield to a higher-priority thread, if we're running in a -+ context where it makes sense to do so. -+ -+ Kind of a funny interaction with donation here. -+ We only support donation for locks, and locks turn off -+ interrupts before calling us, so we automatically don't -+ do the yield here, delegating to lock_release(). */ -+ if (!intr_context () && old_level == INTR_ON) -+ thread_yield_to_higher_priority (); -+ } - intr_set_level (old_level); - } - -@@ -184,6 +213,23 @@ lock_acquire (struct lock *lock) - ASSERT (!lock_held_by_current_thread (lock)); - - old_level = intr_disable (); -+ -+ if (lock->holder != NULL) -+ { -+ /* Donate our priority to the thread holding the lock. -+ First, update the data structures. */ -+ struct thread *donor = thread_current (); -+ donor->want_lock = lock; -+ donor->donee = lock->holder; -+ list_push_back (&lock->holder->donors, &donor->donor_elem); -+ -+ /* Now implement the priority donation itself -+ by recomputing the donee's priority -+ and cascading the donation as far as necessary. */ -+ while (donor->donee != NULL && thread_recompute_priority (donor->donee)) -+ donor = donor->donee; -+ } -+ - sema_down (&lock->semaphore); - lock->holder = thread_current (); - intr_set_level (old_level); -@@ -198,13 +244,38 @@ void - lock_release (struct lock *lock) - { - enum intr_level old_level; -+ struct thread *t = thread_current (); -+ struct list_elem *e; - - ASSERT (lock != NULL); - ASSERT (lock_held_by_current_thread (lock)); - - old_level = intr_disable (); -+ -+ /* Remove donations from threads that want the lock we're -+ releasing. */ -+ for (e = list_begin (&t->donors); e != list_end (&t->donors); ) -+ { -+ struct thread *donor = list_entry (e, struct thread, donor_elem); -+ if (donor->want_lock == lock) -+ { -+ donor->donee = NULL; -+ e = list_remove (e); -+ } -+ else -+ e = list_next (e); -+ } -+ -+ /* Release lock. */ - lock->holder = NULL; - sema_up (&lock->semaphore); -+ -+ /* Recompute our priority based on our remaining donations, -+ then yield to a higher-priority ready thread if one now -+ exists. */ -+ thread_recompute_priority (t); -+ thread_yield_to_higher_priority (); -+ - intr_set_level (old_level); - } - -Index: src/threads/thread.c -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.c,v -retrieving revision 1.48 -diff -u -p -u -r1.48 thread.c ---- src/threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48 -+++ src/threads/thread.c 31 Dec 2004 22:31:03 -0000 -@@ -166,6 +166,8 @@ thread_create (const char *name, int pri - - /* Add to run queue. */ - thread_unblock (t); -+ if (priority > thread_get_priority ()) -+ thread_yield (); - - return tid; - } -@@ -186,6 +188,19 @@ thread_block (void) - schedule (); - } - -+/* Returns true if A has higher priority than B, -+ within a list of threads. */ -+static bool -+thread_higher_priority (const struct list_elem *a_, -+ const struct list_elem *b_, -+ void *aux UNUSED) -+{ -+ const struct thread *a = list_entry (a_, struct thread, elem); -+ const struct thread *b = list_entry (b_, struct thread, elem); -+ -+ return a->priority > b->priority; -+} -+ - /* Transitions a blocked thread T to the ready-to-run state. - This is an error if T is not blocked. (Use thread_yield() to - make the running thread ready.) */ -@@ -198,7 +212,7 @@ thread_unblock (struct thread *t) - - old_level = intr_disable (); - ASSERT (t->status == THREAD_BLOCKED); -- list_push_back (&ready_list, &t->elem); -+ list_insert_ordered (&ready_list, &t->elem, thread_higher_priority, NULL); - t->status = THREAD_READY; - intr_set_level (old_level); - } -@@ -266,8 +280,8 @@ thread_yield (void) - ASSERT (!intr_context ()); - - old_level = intr_disable (); -- list_push_back (&ready_list, &cur->elem); -+ list_insert_ordered (&ready_list, &cur->elem, thread_higher_priority, NULL); - cur->status = THREAD_READY; - schedule (); - intr_set_level (old_level); - } -@@ -274,19 +288,75 @@ - { - } - --/* Sets the current thread's priority to NEW_PRIORITY. */ --void --thread_set_priority (int new_priority) --{ -- thread_current ()->priority = new_priority; --} -- --/* Returns the current thread's priority. */ --int --thread_get_priority (void) --{ -- return thread_current ()->priority; --} -+ -+/* Sets the current thread's priority to PRIORITY. */ -+void -+thread_set_priority (int priority) -+{ -+ struct thread *t = thread_current (); -+ enum intr_level old_level; -+ -+ t->normal_priority = priority; -+ -+ old_level = intr_disable (); -+ while (thread_recompute_priority (t) && t->donee != NULL) -+ t = t->donee; -+ thread_yield_to_higher_priority (); -+ intr_set_level (old_level); -+} -+ -+/* Returns the current thread's priority. */ -+int -+thread_get_priority (void) -+{ -+ return thread_current ()->priority; -+} -+ -+/* Returns true if thread A has lower priority than thread B, -+ within a list of donors. */ -+static bool -+donated_lower_priority (const struct list_elem *a_, -+ const struct list_elem *b_, -+ void *aux UNUSED) -+{ -+ const struct thread *a = list_entry (a_, struct thread, donor_elem); -+ const struct thread *b = list_entry (b_, struct thread, donor_elem); -+ -+ return a->priority < b->priority; -+} -+ -+/* Recomputes T's priority in terms of its normal priority and -+ its donors' priorities, if any. -+ Returns true if T's new priority is higher than its old -+ priority, false otherwise. */ -+bool -+thread_recompute_priority (struct thread *t) -+{ -+ int old = t->priority; -+ int donation = 0; -+ if (!list_empty (&t->donors)) -+ donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL), -+ struct thread, donor_elem)->priority; -+ t->priority = donation > t->normal_priority ? donation : t->normal_priority; -+ return t->priority > old; -+} -+ -+/* If the ready list contains a thread with a higher priority, -+ yields to it. */ -+void -+thread_yield_to_higher_priority (void) -+{ -+ enum intr_level old_level = intr_disable (); -+ if (!list_empty (&ready_list)) -+ { -+ struct thread *cur = thread_current (); -+ struct thread *max = list_entry (list_front (&ready_list), -+ struct thread, elem); -+ if (max->priority > cur->priority) -+ thread_yield (); -+ } -+ intr_set_level (old_level); -+} - - /* Idle thread. Executes when no other thread is ready to run. */ - static void -@@ -335,8 +417,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; -- t->priority = priority; -+ t->priority = t->normal_priority = priority; - t->magic = THREAD_MAGIC; -+ list_init (&t->donors); - } - - /* Allocates a SIZE-byte frame at the top of thread T's stack and -Index: src/threads/thread.h -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.h,v -retrieving revision 1.28 -diff -u -p -u -r1.28 thread.h ---- src/threads/thread.h 29 Sep 2004 01:04:20 -0000 1.28 -+++ src/threads/thread.h 31 Dec 2004 22:31:03 -0000 -@@ -87,7 +87,14 @@ struct thread - enum thread_status status; /* Thread state. */ - char name[16]; /* Name (for debugging purposes). */ - uint8_t *stack; /* Saved stack pointer. */ -- int priority; /* Priority. */ -+ -+ /* Thread priority. */ -+ int priority; /* Priority, including donations. */ -+ int normal_priority; /* Priority, without donations. */ -+ struct list donors; /* Threads donating priority to us. */ -+ struct list_elem donor_elem; /* Element in donors list. */ -+ struct thread *donee; /* Thread we're donating to. */ -+ struct lock *want_lock; /* Lock we're waiting to acquire. */ - - /* Shared between thread.c and synch.c. */ - struct list_elem elem; /* List element. */ -@@ -118,6 +125,8 @@ const char *thread_name (void); - - void thread_exit (void) NO_RETURN; - void thread_yield (void); -+void thread_yield_to_higher_priority (void); -+bool thread_recompute_priority (struct thread *); - - /* This function will be implemented in problem 1-2. */ - void thread_join (tid_t); diff --git a/solutions/p2-null.patch b/solutions/p2-null.patch new file mode 100644 index 0000000..6777104 --- /dev/null +++ b/solutions/p2-null.patch @@ -0,0 +1,183 @@ +diff -urp -X pat src/threads/init.c~ src/threads/init.c +--- src/threads/init.c~ 2005-03-30 10:26:02.000000000 -0800 ++++ src/threads/init.c 2005-03-30 20:05:20.000000000 -0800 +@@ -120,8 +120,11 @@ main (void) + /* Run a user program. */ + if (initial_program != NULL) + { ++ struct semaphore done; ++ sema_init (&done, 0, "done"); + printf ("\nExecuting '%s':\n", initial_program); +- process_wait (process_execute (initial_program)); ++ process_execute (initial_program, &done); ++ sema_down (&done); + } + #else + /* Run the compiled-in test function. */ +diff -urp -X pat src/threads/synch.c~ src/threads/synch.c +--- src/threads/synch.c~ 2005-03-29 22:23:20.000000000 -0800 ++++ src/threads/synch.c 2005-03-30 20:01:45.000000000 -0800 +@@ -117,7 +117,7 @@ sema_self_test (void) + printf ("Testing semaphores..."); + sema_init (&sema[0], 0, "ping"); + sema_init (&sema[1], 0, "pong"); +- thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema); ++ thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema, NULL); + for (i = 0; i < 10; i++) + { + sema_up (&sema[0]); +diff -urp -X pat src/threads/test.c~ src/threads/test.c +--- src/threads/test.c~ 2005-01-22 11:14:57.000000000 -0800 ++++ src/threads/test.c 2005-03-30 20:03:11.000000000 -0800 +@@ -93,7 +93,7 @@ test_sleep (int thread_cnt, int iteratio + t->iterations = 0; + + snprintf (name, sizeof name, "thread %d", i); +- thread_create (name, PRI_DEFAULT, sleeper, t); ++ thread_create (name, PRI_DEFAULT, sleeper, t, NULL); + } + + /* Wait long enough for all the threads to finish. */ +diff -urp -X pat src/threads/thread.c~ src/threads/thread.c +--- src/threads/thread.c~ 2005-03-30 10:26:13.000000000 -0800 ++++ src/threads/thread.c 2005-03-30 20:08:17.000000000 -0800 +@@ -51,7 +51,8 @@ static void kernel_thread (thread_func * + static void idle (void *aux UNUSED); + static struct thread *running_thread (void); + static struct thread *next_thread_to_run (void); +-static void init_thread (struct thread *, const char *name, int priority); ++static void init_thread (struct thread *, const char *name, int priority, ++ struct semaphore *); + static bool is_thread (struct thread *); + static void *alloc_frame (struct thread *, size_t size); + static void schedule (void); +@@ -78,7 +79,7 @@ thread_init (void) + + /* Set up a thread structure for the running thread. */ + initial_thread = running_thread (); +- init_thread (initial_thread, "main", PRI_DEFAULT); ++ init_thread (initial_thread, "main", PRI_DEFAULT, NULL); + initial_thread->status = THREAD_RUNNING; + initial_thread->tid = allocate_tid (); + } +@@ -88,7 +89,7 @@ thread_init (void) + void + thread_start (void) + { +- thread_create ("idle", PRI_DEFAULT, idle, NULL); ++ thread_create ("idle", PRI_DEFAULT, idle, NULL, NULL); + intr_enable (); + } + +@@ -133,7 +134,8 @@ thread_print_stats (void) + Priority scheduling is the goal of Problem 1-3. */ + tid_t + thread_create (const char *name, int priority, +- thread_func *function, void *aux) ++ thread_func *function, void *aux, ++ struct semaphore *completion) + { + struct thread *t; + struct kernel_thread_frame *kf; +@@ -149,7 +151,7 @@ thread_create (const char *name, int pri + return TID_ERROR; + + /* Initialize thread. */ +- init_thread (t, name, priority); ++ init_thread (t, name, priority, completion); + tid = t->tid = allocate_tid (); + + /* Stack frame for kernel_thread(). */ +@@ -245,6 +247,9 @@ thread_exit (void) + { + ASSERT (!intr_context ()); + ++ if (thread_current ()->completion) ++ sema_up (thread_current ()->completion); ++ + #ifdef USERPROG + process_exit (); + #endif +@@ -342,7 +347,8 @@ is_thread (struct thread *t) + /* Does basic initialization of T as a blocked thread named + NAME. */ + static void +-init_thread (struct thread *t, const char *name, int priority) ++init_thread (struct thread *t, const char *name, int priority, ++ struct semaphore *completion) + { + ASSERT (t != NULL); + ASSERT (PRI_MIN <= priority && priority <= PRI_MAX); +@@ -353,6 +359,7 @@ init_thread (struct thread *t, const cha + strlcpy (t->name, name, sizeof t->name); + t->stack = (uint8_t *) t + PGSIZE; + t->priority = priority; ++ t->completion = completion; + t->magic = THREAD_MAGIC; + } + +diff -urp -X pat src/threads/thread.h~ src/threads/thread.h +--- src/threads/thread.h~ 2005-03-30 10:26:13.000000000 -0800 ++++ src/threads/thread.h 2005-03-30 20:03:11.000000000 -0800 +@@ -92,6 +92,9 @@ struct thread + /* Shared between thread.c and synch.c. */ + struct list_elem elem; /* List element. */ + ++ /* Completion semaphore. */ ++ struct semaphore *completion; ++ + #ifdef USERPROG + /* Owned by userprog/process.c. */ + uint32_t *pagedir; /* Page directory. */ +@@ -107,7 +110,8 @@ void thread_tick (void); + void thread_print_stats (void); + + typedef void thread_func (void *aux); +-tid_t thread_create (const char *name, int priority, thread_func *, void *); ++tid_t thread_create (const char *name, int priority, thread_func *, void *, ++ struct semaphore *); + + void thread_block (void); + void thread_unblock (struct thread *); +diff -urp -X pat src/userprog/process.c~ src/userprog/process.c +--- src/userprog/process.c~ 2005-03-30 20:06:20.000000000 -0800 ++++ src/userprog/process.c 2005-03-30 20:06:27.000000000 -0800 +@@ -21,11 +21,10 @@ static thread_func execute_thread NO_RET + 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 (and may even exit) +- before process_execute() returns. Returns the new process's +- thread id, or TID_ERROR if the thread cannot be created. */ ++ FILENAME. The new thread may be scheduled before ++ process_execute() returns.*/ + tid_t +-process_execute (const char *filename) ++process_execute (const char *filename, struct semaphore *completion) + { + char *fn_copy; + tid_t tid; +@@ -38,7 +37,8 @@ process_execute (const char *filename) + strlcpy (fn_copy, filename, PGSIZE); + + /* Create a new thread to execute FILENAME. */ +- tid = thread_create (filename, PRI_DEFAULT, execute_thread, fn_copy); ++ tid = thread_create (filename, PRI_DEFAULT, execute_thread, fn_copy, ++ completion); + if (tid == TID_ERROR) + palloc_free_page (fn_copy); + return tid; +diff -urp -X pat src/userprog/process.h~ src/userprog/process.h +--- src/userprog/process.h~ 2005-03-30 15:09:53.000000000 -0800 ++++ src/userprog/process.h 2005-03-30 20:02:51.000000000 -0800 +@@ -2,8 +2,9 @@ + #define USERPROG_PROCESS_H + + #include "threads/thread.h" ++#include "threads/synch.h" + +-tid_t process_execute (const char *filename); ++tid_t process_execute (const char *filename, struct semaphore *); + int process_wait (tid_t); + void process_exit (void); + void process_activate (void); diff --git a/solutions/p2.patch b/solutions/p2.patch index add0f5a..fc53891 100644 --- a/solutions/p2.patch +++ b/solutions/p2.patch @@ -1,87 +1,6 @@ -Index: src/threads/synch.c -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/synch.c,v -retrieving revision 1.15 -diff -u -p -r1.15 synch.c ---- src/threads/synch.c 31 Dec 2004 21:13:38 -0000 1.15 -+++ src/threads/synch.c 1 Jan 2005 02:13:41 -0000 -@@ -330,3 +330,45 @@ cond_name (const struct condition *cond) - - return cond->name; - } -+ -+/* Initializes LATCH and names it NAME (for debugging purposes). -+ A latch is a boolean condition. Until it is released for the -+ first time, all threads block attempting to acquire. After it -+ is released once, all ongoing and subsequent acquisitions -+ "fall through" immediately. Releases after the first have no -+ additional effect. */ -+void -+latch_init (struct latch *latch, const char *name) -+{ -+ latch->released = false; -+ lock_init (&latch->monitor_lock, name); -+ cond_init (&latch->rel_cond, name); -+} -+ -+/* Acquires LATCH, blocking until it is released for the first -+ time. */ -+void -+latch_acquire (struct latch *latch) -+{ -+ lock_acquire (&latch->monitor_lock); -+ if (!latch->released) -+ { -+ cond_wait (&latch->rel_cond, &latch->monitor_lock); -+ ASSERT (latch->released); -+ } -+ lock_release (&latch->monitor_lock); -+} -+ -+/* Releases LATCH, causing all ongoing and subsequent -+ acquisitions to pass through immediately. */ -+void -+latch_release (struct latch *latch) -+{ -+ lock_acquire (&latch->monitor_lock); -+ if (!latch->released) -+ { -+ latch->released = true; -+ cond_signal (&latch->rel_cond, &latch->monitor_lock); -+ } -+ lock_release (&latch->monitor_lock); -+} -Index: src/threads/synch.h -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/synch.h,v -retrieving revision 1.7 -diff -u -p -r1.7 synch.h ---- src/threads/synch.h 29 Sep 2004 01:04:09 -0000 1.7 -+++ src/threads/synch.h 1 Jan 2005 02:13:41 -0000 -@@ -44,4 +44,16 @@ void cond_signal (struct condition *, st - void cond_broadcast (struct condition *, struct lock *); - const char *cond_name (const struct condition *); - -+/* Latch. */ -+struct latch -+ { -+ bool released; /* Released yet? */ -+ struct lock monitor_lock; /* Monitor lock. */ -+ struct condition rel_cond; /* Signaled when released. */ -+ }; -+ -+void latch_init (struct latch *, const char *); -+void latch_acquire (struct latch *); -+void latch_release (struct latch *); -+ - #endif /* threads/synch.h */ -Index: src/threads/thread.c -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.c,v -retrieving revision 1.48 -diff -u -p -r1.48 thread.c ---- src/threads/thread.c 9 Oct 2004 18:01:37 -0000 1.48 -+++ src/threads/thread.c 1 Jan 2005 02:13:42 -0000 +diff -urp -X pat src/threads/thread.c~ src/threads/thread.c +--- src/threads/thread.c~ 2005-03-30 10:26:13.000000000 -0800 ++++ src/threads/thread.c 2005-03-30 16:19:26.000000000 -0800 @@ -13,6 +13,7 @@ #include "threads/synch.h" #ifdef USERPROG @@ -90,52 +9,20 @@ diff -u -p -r1.48 thread.c #endif /* Random value for struct thread's `magic' member. -@@ -81,6 +82,7 @@ thread_init (void) - init_thread (initial_thread, "main", PRI_DEFAULT); - initial_thread->status = THREAD_RUNNING; - initial_thread->tid = allocate_tid (); -+ sema_up (&initial_thread->can_die); - } - - /* Starts preemptive thread scheduling by enabling interrupts. -@@ -149,6 +151,7 @@ thread_create (const char *name, int pri - /* Initialize thread. */ - init_thread (t, name, priority); - tid = t->tid = allocate_tid (); -+ list_push_back (&thread_current ()->children, &t->children_elem); - - /* Stack frame for kernel_thread(). */ - kf = alloc_frame (t, sizeof *kf); -@@ -241,16 +244,36 @@ thread_tid (void) +@@ -243,16 +244,19 @@ thread_tid (void) void thread_exit (void) { + struct thread *t = thread_current (); -+ struct list_elem *e, *next; + ASSERT (!intr_context ()); #ifdef USERPROG process_exit (); #endif +- + syscall_exit (); + -+ /* Notify our parent that we're dying. */ -+ latch_release (&t->ready_to_die); -+ -+ /* Notify our children that they can die. */ -+ for (e = list_begin (&t->children); e != list_end (&t->children); -+ e = next) -+ { -+ struct thread *child = list_entry (e, struct thread, children_elem); -+ next = list_next (e); -+ list_remove (e); -+ sema_up (&child->can_die); -+ } -+ -+ /* Wait until our parent is ready for us to die. */ -+ sema_down (&t->can_die); - /* Just set our status to dying and schedule another process. We will be destroyed during the call to schedule_tail(). */ intr_disable (); @@ -144,52 +31,21 @@ diff -u -p -r1.48 thread.c schedule (); NOT_REACHED (); } -@@ -283,8 +290,22 @@ thread_block (void) - This function will be implemented in problem 1-2. For now, it - does nothing. */ --void --thread_join (tid_t child_tid UNUSED) --{ -+int -+thread_join (tid_t child_tid) -+{ -+ struct thread *cur = thread_current (); -+ struct list_elem *e; -+ -+ for (e = list_begin (&cur->children); e != list_end (&cur->children); ) -+ { -+ struct thread *child = list_entry (e, struct thread, children_elem); -+ e = list_next (e); -+ if (child->tid == child_tid) -+ { -+ latch_acquire (&child->ready_to_die); -+ return child->exit_code; -+ } -+ } -+ return -1; - } - - /* Sets the current thread's priority to NEW_PRIORITY. */ -@@ -336,6 +379,12 @@ init_thread (struct thread *t, const cha +@@ -353,6 +357,11 @@ init_thread (struct thread *t, const cha strlcpy (t->name, name, sizeof t->name); t->stack = (uint8_t *) t + PGSIZE; t->priority = priority; -+ latch_init (&t->ready_to_die, "ready-to-die"); -+ sema_init (&t->can_die, 0, "can-die"); + list_init (&t->children); + t->exit_code = -1; ++ t->wait_status = NULL; + list_init (&t->fds); + t->next_handle = 2; t->magic = THREAD_MAGIC; } -Index: src/threads/thread.h -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/threads/thread.h,v -retrieving revision 1.28 -diff -u -p -r1.28 thread.h ---- src/threads/thread.h 29 Sep 2004 01:04:20 -0000 1.28 -+++ src/threads/thread.h 1 Jan 2005 02:13:42 -0000 +diff -urp -X pat src/threads/thread.h~ src/threads/thread.h +--- src/threads/thread.h~ 2005-03-30 10:26:13.000000000 -0800 ++++ src/threads/thread.h 2005-03-30 16:17:45.000000000 -0800 @@ -4,6 +4,7 @@ #include #include @@ -198,47 +54,52 @@ diff -u -p -r1.28 thread.h /* States in a thread's life cycle. */ enum thread_status -@@ -89,12 +90,23 @@ struct thread +@@ -89,6 +90,11 @@ struct thread uint8_t *stack; /* Saved stack pointer. */ int priority; /* Priority. */ -+ /* Members for implementing thread_join(). */ -+ struct latch ready_to_die; /* Release when thread about to die. */ -+ struct semaphore can_die; /* Up when thread allowed to die. */ -+ struct list children; /* List of child threads. */ -+ struct list_elem children_elem; /* Element of `children' list. */ -+ int exit_code; /* Return status. */ ++ /* Owned by process.c. */ ++ int exit_code; /* Exit code. */ ++ struct wait_status *wait_status; /* This process's completion status. */ ++ struct list children; /* Completion status of children. */ + /* Shared between thread.c and synch.c. */ struct list_elem elem; /* List element. */ - #ifdef USERPROG - /* Owned by userprog/process.c. */ +@@ -97,10 +103,29 @@ struct thread uint32_t *pagedir; /* Page directory. */ -+ + #endif + + /* Owned by syscall.c. */ + struct list fds; /* List of file descriptors. */ + int next_handle; /* Next handle value. */ - #endif - ++ /* Owned by thread.c. */ -@@ -120,7 +132,7 @@ void thread_exit (void) NO_RETURN; - void thread_exit (void) NO_RETURN; - void thread_yield (void); + unsigned magic; /* Detects stack overflow. */ + }; --void thread_join (tid_t); -+int thread_join (tid_t); - - void thread_set_priority (int); - int thread_get_priority (void); -Index: src/userprog/exception.c -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/userprog/exception.c,v -retrieving revision 1.10 -diff -u -p -r1.10 exception.c ---- src/userprog/exception.c 26 Sep 2004 21:15:17 -0000 1.10 -+++ src/userprog/exception.c 1 Jan 2005 02:13:42 -0000 -@@ -147,6 +147,14 @@ page_fault (struct intr_frame *f) ++/* Tracks the completion of a process. ++ Reference held by both the parent, in its `children' list, ++ and by the child, in its `wait_status' pointer. */ ++struct wait_status ++ { ++ struct list_elem elem; /* `children' list element. */ ++ struct lock lock; /* Protects ref_cnt. */ ++ int ref_cnt; /* 2=child and parent both alive, ++ 1=either child or parent alive, ++ 0=child and parent both dead. */ ++ tid_t tid; /* Child thread id. */ ++ int exit_code; /* Child exit code, if dead. */ ++ struct semaphore dead; /* 1=child alive, 0=child dead. */ ++ }; ++ + void thread_init (void); + void thread_start (void); + void thread_tick (void); +diff -urp -X pat src/userprog/exception.c~ src/userprog/exception.c +--- src/userprog/exception.c~ 2005-01-01 18:09:59.000000000 -0800 ++++ src/userprog/exception.c 2005-03-30 13:26:14.000000000 -0800 +@@ -150,6 +150,14 @@ page_fault (struct intr_frame *f) write = (f->error_code & PF_W) != 0; user = (f->error_code & PF_U) != 0; @@ -253,14 +114,15 @@ diff -u -p -r1.10 exception.c /* To implement virtual memory, delete the rest of the function body, and replace it with code that brings in the page to which fault_addr refers. */ -Index: src/userprog/process.c -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/userprog/process.c,v -retrieving revision 1.6 -diff -u -p -r1.6 process.c ---- src/userprog/process.c 15 Dec 2004 02:32:02 -0000 1.6 -+++ src/userprog/process.c 1 Jan 2005 02:13:43 -0000 -@@ -18,7 +18,17 @@ +diff -urp -X pat src/userprog/process.c~ src/userprog/process.c +--- src/userprog/process.c~ 2005-03-30 10:40:10.000000000 -0800 ++++ src/userprog/process.c 2005-03-30 16:19:32.000000000 -0800 +@@ -14,11 +14,23 @@ + #include "threads/init.h" + #include "threads/interrupt.h" + #include "threads/mmu.h" ++#include "threads/malloc.h" + #include "threads/palloc.h" #include "threads/thread.h" static thread_func execute_thread NO_RETURN; @@ -272,14 +134,15 @@ diff -u -p -r1.6 process.c + thread. */ +struct exec_info + { -+ const char *filename; /* Program to load. */ -+ struct semaphore load_done; /* "Up"ed when loading complete. */ -+ bool success; /* True if program successfully loaded. */ ++ const char *filename; /* Program to load. */ ++ struct semaphore load_done; /* "Up"ed when loading complete. */ ++ struct wait_status *wait_status; /* Child process. */ ++ bool success; /* Program successfully loaded? */ + }; /* Starts a new thread running a user program loaded from FILENAME. The new thread may be scheduled before -@@ -26,31 +36,32 @@ static bool load (const char *cmdline, v +@@ -26,29 +38,33 @@ static bool load (const char *cmdline, v tid_t process_execute (const char *filename) { @@ -305,9 +168,12 @@ diff -u -p -r1.6 process.c + if (tid != TID_ERROR) + { + sema_down (&exec.load_done); -+ if (!exec.success) ++ if (exec.success) ++ list_push_back (&thread_current ()->children, &exec.wait_status->elem); ++ else + tid = TID_ERROR; + } ++ return tid; } @@ -322,32 +188,123 @@ diff -u -p -r1.6 process.c struct intr_frame if_; bool success; - /* Initialize interrupt frame and load executable. */ - memset (&if_, 0, sizeof if_); -@@ -59,11 +69,9 @@ execute_thread (void *filename_) +@@ -57,10 +73,28 @@ execute_thread (void *filename_) + 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); -- ++ success = load (exec->filename, &if_.eip, &if_.esp); ++ ++ /* Allocate wait_status. */ ++ if (success) ++ { ++ exec->wait_status = thread_current ()->wait_status ++ = malloc (sizeof *exec->wait_status); ++ success = exec->wait_status != NULL; ++ } + - /* If load failed, quit. */ - palloc_free_page (filename); -+ success = exec->success = load (exec->filename, &if_.eip, &if_.esp); ++ /* Initialize wait_status. */ ++ if (success) ++ { ++ lock_init (&exec->wait_status->lock, "child process"); ++ exec->wait_status->ref_cnt = 2; ++ exec->wait_status->tid = thread_current ()->tid; ++ sema_init (&exec->wait_status->dead, 0, "dead child"); ++ } ++ ++ /* Notify parent thread and clean up. */ ++ exec->success = success; + sema_up (&exec->load_done); if (!success) thread_exit (); - /* Switch page tables. */ -@@ -89,6 +97,8 @@ process_exit (void) +@@ -74,19 +108,48 @@ execute_thread (void *filename_) + NOT_REACHED (); + } + ++/* Releases one reference to CS and, if it is now unreferenced, ++ frees it. */ ++static void ++release_child (struct wait_status *cs) ++{ ++ int new_ref_cnt; ++ ++ lock_acquire (&cs->lock); ++ new_ref_cnt = --cs->ref_cnt; ++ lock_release (&cs->lock); ++ ++ if (new_ref_cnt == 0) ++ free (cs); ++} ++ + /* 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. */ ++ immediately, without waiting. */ + int +-process_wait (tid_t child_tid UNUSED) ++process_wait (tid_t child_tid) + { ++ struct thread *cur = thread_current (); ++ struct list_elem *e; ++ ++ for (e = list_begin (&cur->children); e != list_end (&cur->children); ++ e = list_next (e)) ++ { ++ struct wait_status *cs = list_entry (e, struct wait_status, elem); ++ if (cs->tid == child_tid) ++ { ++ int exit_code; ++ list_remove (e); ++ sema_down (&cs->dead); ++ exit_code = cs->exit_code; ++ release_child (cs); ++ return exit_code; ++ } ++ } + return -1; + } + + /* Free the current process's resources. */ +@@ -93,8 +157,29 @@ void + process_exit (void) + { struct thread *cur = thread_current (); ++ struct list_elem *e, *next; uint32_t *pd; + printf ("%s: exit(%d)\n", cur->name, cur->exit_code); + ++ /* Notify parent that we're dead. */ ++ if (cur->wait_status != NULL) ++ { ++ struct wait_status *cs = cur->wait_status; ++ cs->exit_code = cur->exit_code; ++ sema_up (&cs->dead); ++ release_child (cs); ++ } ++ ++ /* Free entries of children list. */ ++ for (e = list_begin (&cur->children); e != list_end (&cur->children); ++ e = next) ++ { ++ struct wait_status *cs = list_entry (e, struct wait_status, elem); ++ next = list_remove (e); ++ release_child (cs); ++ } ++ /* 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 -@@ -182,7 +192,7 @@ struct Elf32_Phdr + to the kernel-only page directory. */ + pd = cur->pagedir; +@@ -192,7 +277,7 @@ struct Elf32_Phdr #define PF_R 4 /* Readable. */ static bool load_segment (struct file *, const struct Elf32_Phdr *); @@ -355,8 +312,8 @@ diff -u -p -r1.6 process.c +static bool setup_stack (const char *cmd_line, void **esp); /* Aborts loading an executable, with an error message. */ - #define LOAD_ERROR(MSG) \ -@@ -198,13 +208,15 @@ static bool setup_stack (void **esp); + #define LOAD_ERROR(MSG) \ +@@ -208,13 +293,15 @@ static bool setup_stack (void **esp); and its initial stack pointer into *ESP. Returns true if successful, false otherwise. */ bool @@ -372,10 +329,10 @@ diff -u -p -r1.6 process.c + char *cp; int i; - /* Allocate page directory. */ -@@ -212,6 +224,14 @@ load (const char *filename, void (**eip) - if (t->pagedir == NULL) + /* Allocate and activate page directory. */ +@@ -223,6 +310,14 @@ load (const char *filename, void (**eip) LOAD_ERROR (("page directory allocation failed")); + process_activate (); + /* Extract filename from command line. */ + while (*cmd_line == ' ') @@ -388,7 +345,7 @@ diff -u -p -r1.6 process.c /* Open executable file. */ file = filesys_open (filename); if (file == NULL) -@@ -272,7 +292,7 @@ load (const char *filename, void (**eip) +@@ -283,7 +378,7 @@ load (const char *filename, void (**eip) } /* Set up stack. */ @@ -397,7 +354,7 @@ diff -u -p -r1.6 process.c goto done; /* Start address. */ -@@ -381,10 +401,92 @@ load_segment (struct file *file, const s +@@ -392,10 +487,92 @@ load_segment (struct file *file, const s return true; } @@ -493,7 +450,7 @@ diff -u -p -r1.6 process.c { uint8_t *kpage; bool success = false; -@@ -392,9 +494,9 @@ setup_stack (void **esp) +@@ -403,9 +580,9 @@ setup_stack (void **esp) kpage = palloc_get_page (PAL_USER | PAL_ZERO); if (kpage != NULL) { @@ -506,13 +463,9 @@ diff -u -p -r1.6 process.c else palloc_free_page (kpage); } -Index: src/userprog/syscall.c -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/userprog/syscall.c,v -retrieving revision 1.4 -diff -u -p -r1.4 syscall.c ---- src/userprog/syscall.c 26 Sep 2004 21:15:17 -0000 1.4 -+++ src/userprog/syscall.c 1 Jan 2005 02:13:43 -0000 +diff -urp -X pat src/userprog/syscall.c~ src/userprog/syscall.c +--- src/userprog/syscall.c~ 2004-09-26 14:15:17.000000000 -0700 ++++ src/userprog/syscall.c 2005-03-30 15:11:37.000000000 -0800 @@ -1,20 +1,478 @@ #include "userprog/syscall.h" #include @@ -535,7 +488,7 @@ diff -u -p -r1.4 syscall.c +static int sys_halt (void); +static int sys_exit (int status); +static int sys_exec (const char *ufile); -+static int sys_join (tid_t); ++static int sys_wait (tid_t); +static int sys_create (const char *ufile, unsigned initial_size); +static int sys_remove (const char *ufile); +static int sys_open (const char *ufile); @@ -573,12 +526,12 @@ diff -u -p -r1.4 syscall.c + }; + + /* Table of system calls. */ -+ static const struct syscall syscall_table[] = ++ static const struct syscall syscall_table[] = + { + {0, (syscall_function *) sys_halt}, + {1, (syscall_function *) sys_exit}, + {1, (syscall_function *) sys_exec}, -+ {1, (syscall_function *) sys_join}, ++ {1, (syscall_function *) sys_wait}, + {2, (syscall_function *) sys_create}, + {1, (syscall_function *) sys_remove}, + {1, (syscall_function *) sys_open}, @@ -590,13 +543,13 @@ diff -u -p -r1.4 syscall.c + {1, (syscall_function *) sys_close}, + }; + -+ struct syscall *sc; -+ int call_nr; ++ const struct syscall *sc; ++ unsigned call_nr; + int args[3]; + + /* Get the system call. */ + copy_in (&call_nr, f->esp, sizeof call_nr); -+ if (call_nr < 0 || call_nr >= sizeof syscall_table / sizeof *syscall_table) ++ if (call_nr >= sizeof syscall_table / sizeof *syscall_table) + thread_exit (); + sc = syscall_table + call_nr; @@ -716,11 +669,11 @@ diff -u -p -r1.4 syscall.c + return tid; +} + -+/* Join system call. */ ++/* Wait system call. */ +static int -+sys_join (tid_t child) ++sys_wait (tid_t child) +{ -+ return thread_join (child); ++ return process_wait (child); +} + +/* Create system call. */ @@ -811,7 +764,7 @@ diff -u -p -r1.4 syscall.c + } + thread_exit (); -+} + } + +/* Filesize system call. */ +static int @@ -995,14 +948,10 @@ diff -u -p -r1.4 syscall.c + file_close (fd->file); + free (fd); + } - } -Index: src/userprog/syscall.h -=================================================================== -RCS file: /afs/ir.stanford.edu/users/b/l/blp/private/cvs/pintos/src/userprog/syscall.h,v -retrieving revision 1.2 -diff -u -p -r1.2 syscall.h ---- src/userprog/syscall.h 6 Sep 2004 05:38:45 -0000 1.2 -+++ src/userprog/syscall.h 1 Jan 2005 02:13:43 -0000 ++} +diff -urp -X pat src/userprog/syscall.h~ src/userprog/syscall.h +--- src/userprog/syscall.h~ 2004-09-05 22:38:45.000000000 -0700 ++++ src/userprog/syscall.h 2005-03-30 13:26:14.000000000 -0800 @@ -2,5 +2,6 @@ #define USERPROG_SYSCALL_H 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) -- 2.30.2