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
@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
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.
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.
@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
* 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
@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
@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
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
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.
@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
@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.
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
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.}
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.
@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
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;
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
@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).
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})
@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.}
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
}
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);
}
}
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);
close (fd);
exec_children ("child-syn-read", children, CHILD_CNT);
- join_children (children, CHILD_CNT);
+ wait_children (children, CHILD_CNT);
}
(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
(int) CHUNK_SIZE, ofs, filename);
quiet = false;
- join_children (children, CHILD_CNT);
+ wait_children (children, CHILD_CNT);
}
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);
(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
+++ /dev/null
-/* Problem 1-2: Join tests.
-
- Based on a test originally submitted for Stanford's CS 140 in
- winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. Later modified by shiangc, yph, and
- arens. */
-#include "threads/test.h"
-#include <stdio.h>
-#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);
-}
+++ /dev/null
-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.
+++ /dev/null
-/* Problem 1-2: Join tests.
-
- Based on a test originally submitted for Stanford's CS 140 in
- winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. Later modified by shiangc, yph, and
- arens. */
-#include "threads/test.h"
-#include <stdio.h>
-#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);
-}
+++ /dev/null
-/* Problem 1-2: Join tests.
-
- Based on a test originally submitted for Stanford's CS 140 in
- winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. Later modified by shiangc, yph, and
- arens. */
-#include "threads/test.h"
-#include <stdio.h>
-#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);
-}
+++ /dev/null
-/* Problem 1-2: Join tests.
-
- Based on a test originally submitted for Stanford's CS 140 in
- winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. Later modified by shiangc, yph, and
- arens. */
-#include "threads/test.h"
-#include <stdio.h>
-#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);
-}
+++ /dev/null
-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.
+++ /dev/null
-/* Problem 1-2: Join tests.
-
- Based on a test originally submitted for Stanford's CS 140 in
- winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. Later modified by shiangc, yph, and
- arens. */
-
-#include "threads/test.h"
-#include <stdio.h>
-#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);
-}
+++ /dev/null
-/* Problem 1-2: Join tests.
-
- Based on a test originally submitted for Stanford's CS 140 in
- winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. Later modified by shiangc, yph, and
- arens. */
-#include "threads/test.h"
-#include <stdio.h>
-#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);
-}
+++ /dev/null
-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.
+++ /dev/null
-/* Problem 1-2: Join tests.
-
- Based on a test originally submitted for Stanford's CS 140 in
- winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. Later modified by shiangc, yph, and
- arens. */
-#include "threads/test.h"
-#include <stdio.h>
-#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);
-}
+++ /dev/null
-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.
-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]]
-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
-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
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);
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) = @_;
-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)
-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
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
$(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: %
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
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
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
$(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: %
main (void)
{
printf ("(exec-arg) begin\n");
- join (exec ("child-arg childarg"));
+ wait (exec ("child-arg childarg"));
printf ("(exec-arg) end\n");
return 0;
}
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;
}
main (void)
{
printf ("(exec-once) begin\n");
- join (exec ("child-simple"));
+ wait (exec ("child-simple"));
printf ("(exec-once) end\n");
return 0;
}
+++ /dev/null
-#include <stdio.h>
-#include <syscall.h>
-
-int
-main (void)
-{
- printf ("(join-bad-pid) begin\n");
- join ((pid_t) 0x20101234);
- printf ("(join-bad-pid) end\n");
- return 0;
-}
+++ /dev/null
-(join-bad-pid) begin
-(join-bad-pid) end
-join-bad-pid: exit(0)
---OR--
-(join-bad-pid) begin
-join-bad-pid: exit(-1)
+++ /dev/null
-#include <stdio.h>
-#include <syscall.h>
-
-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;
-}
+++ /dev/null
-(join-killed) begin
-(child-bad) begin
-child-bad: exit(-1)
-(join-killed) join(exec()) = -1
-(join-killed) end
-join-killed: exit(0)
+++ /dev/null
-#include <stdio.h>
-#include <syscall.h>
-
-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;
-}
+++ /dev/null
-(join-simple) begin
-(child-simple) run
-child-simple: exit(81)
-(join-simple) join(exec()) = 81
-(join-simple) end
-join-simple: exit(0)
+++ /dev/null
-#include <stdio.h>
-#include <syscall.h>
-
-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;
-}
+++ /dev/null
-(join-twice) begin
-(child-simple) run
-child-simple: exit(81)
-(join-twice) join(exec()) = 81
-(join-twice) end
-join-twice: exit(0)
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)
(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)
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)
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)
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
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) = @_;
-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
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';
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
--- /dev/null
+#include <stdio.h>
+#include <syscall.h>
+
+int
+main (void)
+{
+ printf ("(wait-bad-pid) begin\n");
+ wait ((pid_t) 0x20101234);
+ printf ("(wait-bad-pid) end\n");
+ return 0;
+}
--- /dev/null
+(wait-bad-pid) begin
+(wait-bad-pid) end
+wait-bad-pid: exit(0)
+--OR--
+(wait-bad-pid) begin
+wait-bad-pid: exit(-1)
--- /dev/null
+#include <stdio.h>
+#include <syscall.h>
+
+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;
+}
--- /dev/null
+(wait-killed) begin
+(child-bad) begin
+child-bad: exit(-1)
+(wait-killed) wait(exec()) = -1
+(wait-killed) end
+wait-killed: exit(0)
--- /dev/null
+#include <stdio.h>
+#include <syscall.h>
+
+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;
+}
--- /dev/null
+(wait-simple) begin
+(child-simple) run
+child-simple: exit(81)
+(wait-simple) wait(exec()) = 81
+(wait-simple) end
+wait-simple: exit(0)
--- /dev/null
+#include <stdio.h>
+#include <syscall.h>
+
+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;
+}
--- /dev/null
+(wait-twice) begin
+(child-simple) run
+child-simple: exit(81)
+(wait-twice) wait(exec()) = 81
+(wait-twice) end
+wait-twice: exit(0)
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");
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);
}
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);
}
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);
}
(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
#undef halt
#undef exit
#undef exec
-#undef join
+#undef wait
#undef create
#undef remove
#undef open
}
int
-pintos_join (pid_t child)
+pintos_wait (pid_t child)
{
int status = 0;
waitpid (child, &status, 0);
#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
#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. */
}
int
-join (pid_t pid)
+wait (pid_t pid)
{
- return syscall1 (SYS_join, pid);
+ return syscall1 (SYS_wait, pid);
}
bool
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);
-/* 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 <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. Later modified by shiangc, yph, and
- arens. */
+ winter 1999 by by Matt Franklin
+ <startled@leland.stanford.edu>, Greg Hutchins
+ <gmh@leland.stanford.edu>, Yu Ping Hu <yph@cs.stanford.edu>.
+ Modified by arens. */
+
+#ifdef MLFQS
+#error This test not applicable with MLFQS enabled.
+#endif
+
#include "threads/test.h"
#include <stdio.h>
-#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 ();
+}
+\f
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 ());
}
-/* 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
<startled@leland.stanford.edu>, Greg Hutchins
<gmh@leland.stanford.edu>, Yu Ping Hu <yph@cs.stanford.edu>.
- 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 <stdio.h>
+#include <inttypes.h>
#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");
}
-\f
-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);
}
+++ /dev/null
-/* 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
- <startled@leland.stanford.edu>, Greg Hutchins
- <gmh@leland.stanford.edu>, Yu Ping Hu <yph@cs.stanford.edu>.
- Modified by arens and yph. */
-
-/* Uncomment to print progress messages. */
-/*#define SHOW_PROGRESS*/
-
-#include "threads/test.h"
-#include <stdio.h>
-#include <inttypes.h>
-#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);
-}
if (argc != 4)
{
- printf ("usage: recursor <string> <depth> <joinp>\n");
+ printf ("usage: recursor <string> <depth> <waitp>\n");
exit (1);
}
"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. */
{
pid_t pid = exec (command);
if (pid != PID_ERROR)
- join (pid);
+ wait (pid);
else
printf ("exec failed\n");
}
/* 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. */
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)
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);
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)
{
/* 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. */
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
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)
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);
}
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.
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);
#include "threads/thread.h"
tid_t process_execute (const char *filename);
+int process_wait (tid_t);
void process_exit (void);
void process_activate (void);
-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)
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)
userprog::
$(prep-grading)
$(mk-sandbox)
- $(apply-patch) ../solutions/p1-2.patch
+ $(apply-patch) ../solutions/p2-null.patch
$(run-tests) null
$(clean)
projects / pintos-anon / commitdiff