pintos-os.org Git - pintos-anon/blob - doc/sample.tmpl

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