9 Ben Pfaff <blp@stanford.edu>
11 ---- PRELIMINARIES ----
13 >> If you have any preliminary comments on your submission, notes for the
14 >> TAs, or extra credit, please give them here.
16 (This is a sample design document.)
18 >> Please cite any offline or online sources you consulted while
19 >> preparing your submission, other than the Pintos documentation, course
20 >> text, and lecture notes.
27 ---- DATA STRUCTURES ----
29 >> Copy here the declaration of each new or changed `struct' or `struct'
30 >> member, global or static variable, `typedef', or enumeration.
31 >> Identify the purpose of each in 25 words or less.
33 A "latch" is a new synchronization primitive. Acquires block
34 until the first release. Afterward, all ongoing and future
35 acquires pass immediately.
40 bool released; /* Released yet? */
41 struct lock monitor_lock; /* Monitor lock. */
42 struct condition rel_cond; /* Signaled when released. */
45 Added to struct thread:
47 /* Members for implementing thread_join(). */
48 struct latch ready_to_die; /* Release when thread about to die. */
49 struct semaphore can_die; /* Up when thread allowed to die. */
50 struct list children; /* List of child threads. */
51 list_elem children_elem; /* Element of `children' list. */
55 >> Briefly describe your implementation of thread_join() and how it
56 >> interacts with thread termination.
58 thread_join() finds the joined child on the thread's list of
59 children and waits for the child to exit by acquiring the child's
60 ready_to_die latch. When thread_exit() is called, the thread
61 releases its ready_to_die latch, allowing the parent to continue.
63 ---- SYNCHRONIZATION ----
65 >> Consider parent thread P with child thread C. How do you ensure
66 >> proper synchronization and avoid race conditions when P calls wait(C)
67 >> before C exits? After C exits? How do you ensure that all resources
68 >> are freed in each case? How about when P terminates without waiting,
69 >> before C exits? After C exits? Are there any special cases?
71 C waits in thread_exit() for P to die before it finishes its own
72 exit, using the can_die semaphore "down"ed by C and "up"ed by P as
73 it exits. Regardless of whether whether C has terminated, there
74 is no race on wait(C), because C waits for P's permission before
77 Regardless of whether P waits for C, P still "up"s C's can_die
78 semaphore when P dies, so C will always be freed. (However,
79 freeing C's resources is delayed until P's death.)
81 The initial thread is a special case because it has no parent to
82 wait for it or to "up" its can_die semaphore. Therefore, its
83 can_die semaphore is initialized to 1.
87 >> Critique your design, pointing out advantages and disadvantages in
88 >> your design choices.
90 This design has the advantage of simplicity. Encapsulating most
91 of the synchronization logic into a new "latch" structure
92 abstracts what little complexity there is into a separate layer,
93 making the design easier to reason about. Also, all the new data
94 members are in `struct thread', with no need for any extra dynamic
95 allocation, etc., that would require extra management code.
97 On the other hand, this design is wasteful in that a child thread
98 cannot free itself before its parent has terminated. A parent
99 thread that creates a large number of short-lived child threads
100 could unnecessarily exhaust kernel memory. This is probably
101 acceptable for implementing kernel threads, but it may be a bad
102 idea for use with user processes because of the larger number of
103 resources that user processes tend to own.