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

   1                          +-----------------+
   2                          |      CS 140     |
   3                          |  SAMPLE PROJECT |
   4                          | DESIGN DOCUMENT |
   5                          +-----------------+
   6
   7 ---- GROUP ----
   8
   9 Ben Pfaff <blp@stanford.edu>
  10
  11 ---- PRELIMINARIES ----
  12
  13 >> If you have any preliminary comments on your submission, notes for the
  14 >> TAs, or extra credit, please give them here.
  15
  16 (This is a sample design document.)
  17
  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.
  21
  22 None.
  23
  24                                  JOIN
  25                                  ====
  26
  27 ---- DATA STRUCTURES ----
  28
  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.
  32
  33 A "latch" is a new synchronization primitive.  Acquires block
  34 until the first release.  Afterward, all ongoing and future
  35 acquires pass immediately.
  36
  37     /* Latch. */
  38     struct latch
  39       {
  40         bool released;              /* Released yet? */
  41         struct lock monitor_lock;   /* Monitor lock. */
  42         struct condition rel_cond;  /* Signaled when released. */
  43       };
  44
  45 Added to struct thread:
  46
  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. */
  52
  53 ---- ALGORITHMS ----
  54
  55 >> Briefly describe your implementation of thread_join() and how it
  56 >> interacts with thread termination.
  57
  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.
  62
  63 ---- SYNCHRONIZATION ----
  64
  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?
  70
  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
  75 it frees itself.
  76
  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.)
  80
  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.
  84
  85 ---- RATIONALE ----
  86
  87 >> Critique your design, pointing out advantages and disadvantages in
  88 >> your design choices.
  89
  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.
  96
  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.