+/* 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"
-/* 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:
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
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);
}
-/* 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
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);
}
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
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_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).
/* 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
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
#include <stdbool.h>
#include "list.h"
+/* A counting 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 *);
const char *sema_name (const struct semaphore *);
void sema_self_test (void);
+/* 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 *);
bool lock_held_by_current_thread (const struct lock *);
const char *lock_name (const struct lock *);
+/* Condition variable. */
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 *);
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);
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);
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
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. */
- list_elem rq_elem; /* Run queue list element. */
+ list_elem elem; /* List element. */
#ifdef USERPROG
/* These members are owned by the addrspace_*() functions. */
projects / pintos-anon / commitdiff