Add copyright notice to synch.h.

Reuse list_elem in struct thread for semaphore's wait list.
Add comments.

diff --git a/src/threads/synch.c b/src/threads/synch.c
index 08ba8f4b90cff42b698ab89a99f7c19d65ba45f6..d7601dacddc89f7c772d3340cf0e856b81c82f09 100644 (file)
--- a/src/threads/synch.c
+++ b/src/threads/synch.c
@@ -1,15 +1,36 @@
+/* This file is derived from source code for the Nachos
+   instructional operating system.  The Nachos copyright notice
+   is reproduced in full below. */
+
+/* Copyright (c) 1992-1996 The Regents of the University of California.
+   All rights reserved.
+
+   Permission to use, copy, modify, and distribute this software
+   and its documentation for any purpose, without fee, and
+   without written agreement is hereby granted, provided that the
+   above copyright notice and the following two paragraphs appear
+   in all copies of this software.
+
+   IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO
+   ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR
+   CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE
+   AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA
+   HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+   THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY
+   WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+   PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS"
+   BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
+   PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
+   MODIFICATIONS.
+*/
+

 #include "synch.h"
 #include "interrupt.h"
 #include "lib.h"
 #include "thread.h"
 
 #include "synch.h"
 #include "interrupt.h"
 #include "lib.h"
 #include "thread.h"
 

-/* One thread in a list. */
-struct thread_elem
-  {
-    list_elem elem;
-    struct thread *thread;      
-  };
-

 /* Initializes semaphore SEMA to VALUE and names it NAME (for
    debugging purposes only).  A semaphore is a nonnegative
    integer along with two atomic operators for manipulating it:
 /* Initializes semaphore SEMA to VALUE and names it NAME (for
    debugging purposes only).  A semaphore is a nonnegative
    integer along with two atomic operators for manipulating it:


@@ -30,8 +51,8 @@ sema_init (struct semaphore *sema, unsigned value, const char *name)
   list_init (&sema->waiters);
 }
 
   list_init (&sema->waiters);
 }
 

-/* Waits for SEMA's value to become positive and then
-   atomically decrements it.
+/* Down or "P" operation on a semaphore.  Waits for SEMA's value
+   to become positive and then atomically decrements it.

 
    This function may sleep, so it must not be called within an
    interrupt handler.  This function may be called with
 
    This function may sleep, so it must not be called within an
    interrupt handler.  This function may be called with


@@ -48,17 +69,15 @@ sema_down (struct semaphore *sema)
   old_level = intr_disable ();
   while (sema->value == 0) 
     {
   old_level = intr_disable ();
   while (sema->value == 0) 
     {

-      struct thread_elem te;
-      te.thread = thread_current ();
-      list_push_back (&sema->waiters, &te.elem);
+      list_push_back (&sema->waiters, &thread_current ()->elem);

       thread_block ();
     }
   sema->value--;
   intr_set_level (old_level);
 }
 
       thread_block ();
     }
   sema->value--;
   intr_set_level (old_level);
 }
 

-/* Increments SEMA's value.  Wakes up one thread of those waiting
-   for SEMA, if any. 
+/* Up or "V" operation on a semaphore.  Increments SEMA's value
+   and wakes up one thread of those waiting for SEMA, if any.

 
    This function may be called from an interrupt handler. */
 void
 
    This function may be called from an interrupt handler. */
 void


@@ -71,7 +90,7 @@ sema_up (struct semaphore *sema)
   old_level = intr_disable ();
   if (!list_empty (&sema->waiters)) 
     thread_unblock (list_entry (list_pop_front (&sema->waiters),
   old_level = intr_disable ();
   if (!list_empty (&sema->waiters)) 
     thread_unblock (list_entry (list_pop_front (&sema->waiters),

-                                struct thread_elem, elem)->thread);
+                                struct thread, elem));

   sema->value++;
   intr_set_level (old_level);
 }
   sema->value++;
   intr_set_level (old_level);
 }


@@ -83,18 +102,7 @@ sema_name (const struct semaphore *sema)
   return sema->name;
 }
 
   return sema->name;
 }
 

-static void
-sema_test_helper (void *sema_) 
-{
-  struct semaphore *sema = sema_;
-  int i;
-
-  for (i = 0; i < 10; i++) 
-    {
-      sema_down (&sema[0]);
-      sema_up (&sema[1]);
-    }
-}
+static void sema_test_helper (void *sema_);

 
 /* Self-test for semaphores that makes control "ping-pong"
    between a pair of threads.  Insert calls to printk() to see
 
 /* Self-test for semaphores that makes control "ping-pong"
    between a pair of threads.  Insert calls to printk() to see


@@ -106,6 +114,7 @@ sema_self_test (void)
   struct semaphore sema[2];
   int i;
 
   struct semaphore sema[2];
   int i;
 

+  printk ("Testing semaphores...");

   sema_init (&sema[0], 0, "ping");
   sema_init (&sema[1], 0, "pong");
   thread = thread_create ("sema-test", sema_test_helper, &sema);
   sema_init (&sema[0], 0, "ping");
   sema_init (&sema[1], 0, "pong");
   thread = thread_create ("sema-test", sema_test_helper, &sema);


@@ -114,6 +123,21 @@ sema_self_test (void)
       sema_up (&sema[0]);
       sema_down (&sema[1]);
     }
       sema_up (&sema[0]);
       sema_down (&sema[1]);
     }

+  printk ("done.\n");
+}
+
+/* Thread function used by sema_self_test(). */
+static void
+sema_test_helper (void *sema_) 
+{
+  struct semaphore *sema = sema_;
+  int i;
+
+  for (i = 0; i < 10; i++) 
+    {
+      sema_down (&sema[0]);
+      sema_up (&sema[1]);
+    }

 }
 \f
 /* Initializes LOCK and names it NAME (for debugging purposes).
 }
 \f
 /* Initializes LOCK and names it NAME (for debugging purposes).


@@ -208,8 +232,8 @@ lock_name (const struct lock *lock)
 /* One semaphore in a list. */
 struct semaphore_elem 
   {
 /* One semaphore in a list. */
 struct semaphore_elem 
   {

-    list_elem elem;
-    struct semaphore semaphore;
+    list_elem elem;                     /* List element. */
+    struct semaphore semaphore;         /* This semaphore. */

   };
 
 /* Initializes condition variable COND and names it NAME.  A
   };
 
 /* Initializes condition variable COND and names it NAME.  A


@@ -232,9 +256,9 @@ cond_init (struct condition *cond, const char *name)
    this function.
 
    The monitor implemented by this function is "Mesa" style, not
    this function.
 
    The monitor implemented by this function is "Mesa" style, not

-   "Hoare" style.  That is, sending a signal is not atomic with
-   delivering it.  Thus, typically the caller must recheck the
-   condition after the wait completes and, if necessary, wait
+   "Hoare" style, that is, sending and receiving a signal are not
+   an atomic operation.  Thus, typically the caller must recheck
+   the condition after the wait completes and, if necessary, wait

    again.
 
    A given condition variable is associated with only a single
    again.
 
    A given condition variable is associated with only a single

diff --git a/src/threads/synch.h b/src/threads/synch.h
index e64bc6da2abf4c7591d940f19be4fab14ab591df..d21ecff08ca546473cbfc7d84229fa5d54310fab 100644 (file)
--- a/src/threads/synch.h
+++ b/src/threads/synch.h
@@ -4,11 +4,12 @@
 #include <stdbool.h>
 #include "list.h"
 
 #include <stdbool.h>
 #include "list.h"
 

+/* A counting semaphore. */

 struct semaphore 
   {
 struct semaphore 
   {

-    char name[16];
-    unsigned value;
-    struct list waiters;
+    char name[16];              /* Name (for debugging purposes only). */
+    unsigned value;             /* Current value. */
+    struct list waiters;        /* List of waiting threads. */

   };
 
 void sema_init (struct semaphore *, unsigned value, const char *);
   };
 
 void sema_init (struct semaphore *, unsigned value, const char *);


@@ -17,11 +18,12 @@ void sema_up (struct semaphore *);
 const char *sema_name (const struct semaphore *);
 void sema_self_test (void);
 
 const char *sema_name (const struct semaphore *);
 void sema_self_test (void);
 

+/* Lock. */

 struct lock 
   {
 struct lock 
   {

-    char name[16];
-    struct thread *holder;
-    struct semaphore semaphore;
+    char name[16];              /* Name (for debugging purposes only). */
+    struct thread *holder;      /* Thread holding lock (for debugging). */
+    struct semaphore semaphore; /* Binary semaphore controlling access. */

   };
 
 void lock_init (struct lock *, const char *);
   };
 
 void lock_init (struct lock *, const char *);


@@ -30,10 +32,11 @@ void lock_release (struct lock *);
 bool lock_held_by_current_thread (const struct lock *);
 const char *lock_name (const struct lock *);
 
 bool lock_held_by_current_thread (const struct lock *);
 const char *lock_name (const struct lock *);
 

+/* Condition variable. */

 struct condition 
   {
 struct condition 
   {

-    char name[16];
-    struct list waiters;
+    char name[16];              /* Name (for debugging purposes only). */
+    struct list waiters;        /* List of waiting threads. */

   };
 
 void cond_init (struct condition *, const char *);
   };
 
 void cond_init (struct condition *, const char *);

diff --git a/src/threads/thread.c b/src/threads/thread.c
index 52f0f8d4fc73d8f65818163aaca9c7229cf8e97e..61351b569add5a112f66f2210f9bb70989ced7c6 100644 (file)
--- a/src/threads/thread.c
+++ b/src/threads/thread.c
@@ -182,7 +182,7 @@ thread_unblock (struct thread *t)
   old_level = intr_disable ();
   if (t->status == THREAD_BLOCKED) 
     {
   old_level = intr_disable ();
   if (t->status == THREAD_BLOCKED) 
     {

-      list_push_back (&run_queue, &t->rq_elem);
+      list_push_back (&run_queue, &t->elem);

       t->status = THREAD_READY;
     }
   intr_set_level (old_level);
       t->status = THREAD_READY;
     }
   intr_set_level (old_level);


@@ -241,7 +241,7 @@ thread_yield (void)
   ASSERT (!intr_context ());
 
   old_level = intr_disable ();
   ASSERT (!intr_context ());
 
   old_level = intr_disable ();

-  list_push_back (&run_queue, &cur->rq_elem);
+  list_push_back (&run_queue, &cur->elem);

   cur->status = THREAD_READY;
   schedule ();
   intr_set_level (old_level);
   cur->status = THREAD_READY;
   schedule ();
   intr_set_level (old_level);


@@ -364,7 +364,7 @@ next_thread_to_run (void)
   if (list_empty (&run_queue))
     return idle_thread;
   else
   if (list_empty (&run_queue))
     return idle_thread;
   else

-    return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
+    return list_entry (list_pop_front (&run_queue), struct thread, elem);

 }
 
 /* Destroys T, which must be in the dying state and must not be
 }
 
 /* Destroys T, which must be in the dying state and must not be

diff --git a/src/threads/thread.h b/src/threads/thread.h
index a70b48b50cb0305f2147089a0b4db17948e8de46..421751be943f90bd7ad080b3dae9aecdb593d095 100644 (file)
--- a/src/threads/thread.h
+++ b/src/threads/thread.h
@@ -68,13 +68,19 @@ enum thread_status
    the `magic' member of the running thread's `struct thread' is
    set to THREAD_MAGIC.  Stack overflow will normally change this
    value, triggering the assertion. */
    the `magic' member of the running thread's `struct thread' is
    set to THREAD_MAGIC.  Stack overflow will normally change this
    value, triggering the assertion. */

+/* The `elem' member has a dual purpose.  It can be an element in
+   the run queue (thread.c), or it can be an element in a
+   semaphore wait list (synch.c).  It can be used these two ways
+   only because they are mutually exclusive: only a thread in the
+   ready state is on the run queue, whereas only a thread in the
+   blocked state is on a semaphore wait list. */

 struct thread
   {
     /* These members are owned by the thread_*() functions. */
     enum thread_status status;          /* Thread state. */
     char name[16];                      /* Name (for debugging purposes). */
     uint8_t *stack;                     /* Saved stack pointer. */
 struct thread
   {
     /* These members are owned by the thread_*() functions. */
     enum thread_status status;          /* Thread state. */
     char name[16];                      /* Name (for debugging purposes). */
     uint8_t *stack;                     /* Saved stack pointer. */

-    list_elem rq_elem;                  /* Run queue list element. */
+    list_elem elem;                     /* List element. */

 
 #ifdef USERPROG
     /* These members are owned by the addrspace_*() functions. */
 
 #ifdef USERPROG
     /* These members are owned by the addrspace_*() functions. */