From 3625c2e6aba3b282f91282492c4b3fba324816c1 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sun, 5 Sep 2004 07:53:53 +0000 Subject: [PATCH] Add copyright notice to synch.h. Reuse list_elem in struct thread for semaphore's wait list. Add comments. --- src/threads/synch.c | 88 ++++++++++++++++++++++++++++---------------- src/threads/synch.h | 19 ++++++---- src/threads/thread.c | 6 +-- src/threads/thread.h | 8 +++- 4 files changed, 77 insertions(+), 44 deletions(-) diff --git a/src/threads/synch.c b/src/threads/synch.c index 08ba8f4..d7601da 100644 --- 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" -/* 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: @@ -30,8 +51,8 @@ sema_init (struct semaphore *sema, unsigned value, const char *name) 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 @@ -48,17 +69,15 @@ sema_down (struct semaphore *sema) 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 @@ -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), - struct thread_elem, elem)->thread); + struct thread, elem)); sema->value++; intr_set_level (old_level); } @@ -83,18 +102,7 @@ sema_name (const struct semaphore *sema) 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 @@ -106,6 +114,7 @@ sema_self_test (void) 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); @@ -114,6 +123,21 @@ sema_self_test (void) 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]); + } } /* 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 { - 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 @@ -232,9 +256,9 @@ cond_init (struct condition *cond, const char *name) 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 diff --git a/src/threads/synch.h b/src/threads/synch.h index e64bc6d..d21ecff 100644 --- a/src/threads/synch.h +++ b/src/threads/synch.h @@ -4,11 +4,12 @@ #include #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 *); @@ -17,11 +18,12 @@ void sema_up (struct semaphore *); 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 *); @@ -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 *); +/* 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 *); diff --git a/src/threads/thread.c b/src/threads/thread.c index 52f0f8d..61351b5 100644 --- 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) { - list_push_back (&run_queue, &t->rq_elem); + list_push_back (&run_queue, &t->elem); t->status = THREAD_READY; } intr_set_level (old_level); @@ -241,7 +241,7 @@ thread_yield (void) 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); @@ -364,7 +364,7 @@ next_thread_to_run (void) 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 diff --git a/src/threads/thread.h b/src/threads/thread.h index a70b48b..421751b 100644 --- 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 `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. */ -- 2.30.2