os161-1.99
 All Data Structures
synch.c
00001 /*
00002  * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009
00003  *      The President and Fellows of Harvard College.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 3. Neither the name of the University nor the names of its contributors
00014  *    may be used to endorse or promote products derived from this software
00015  *    without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
00018  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED.  IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
00021  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027  * SUCH DAMAGE.
00028  */
00029 
00030 /*
00031  * Synchronization primitives.
00032  * The specifications of the functions are in synch.h.
00033  */
00034 
00035 #include <types.h>
00036 #include <lib.h>
00037 #include <spinlock.h>
00038 #include <wchan.h>
00039 #include <thread.h>
00040 #include <current.h>
00041 #include <synch.h>
00042 
00043 ////////////////////////////////////////////////////////////
00044 //
00045 // Semaphore.
00046 
00047 struct semaphore *
00048 sem_create(const char *name, int initial_count)
00049 {
00050         struct semaphore *sem;
00051 
00052         KASSERT(initial_count >= 0);
00053 
00054         sem = kmalloc(sizeof(struct semaphore));
00055         if (sem == NULL) {
00056                 return NULL;
00057         }
00058 
00059         sem->sem_name = kstrdup(name);
00060         if (sem->sem_name == NULL) {
00061                 kfree(sem);
00062                 return NULL;
00063         }
00064 
00065         sem->sem_wchan = wchan_create(sem->sem_name);
00066         if (sem->sem_wchan == NULL) {
00067                 kfree(sem->sem_name);
00068                 kfree(sem);
00069                 return NULL;
00070         }
00071 
00072         spinlock_init(&sem->sem_lock);
00073         sem->sem_count = initial_count;
00074 
00075         return sem;
00076 }
00077 
00078 void
00079 sem_destroy(struct semaphore *sem)
00080 {
00081         KASSERT(sem != NULL);
00082 
00083         /* wchan_cleanup will assert if anyone's waiting on it */
00084         spinlock_cleanup(&sem->sem_lock);
00085         wchan_destroy(sem->sem_wchan);
00086         kfree(sem->sem_name);
00087         kfree(sem);
00088 }
00089 
00090 void 
00091 P(struct semaphore *sem)
00092 {
00093         KASSERT(sem != NULL);
00094 
00095         /*
00096          * May not block in an interrupt handler.
00097          *
00098          * For robustness, always check, even if we can actually
00099          * complete the P without blocking.
00100          */
00101         KASSERT(curthread->t_in_interrupt == false);
00102 
00103         spinlock_acquire(&sem->sem_lock);
00104         while (sem->sem_count == 0) {
00105                 /*
00106                  * Bridge to the wchan lock, so if someone else comes
00107                  * along in V right this instant the wakeup can't go
00108                  * through on the wchan until we've finished going to
00109                  * sleep. Note that wchan_sleep unlocks the wchan.
00110                  *
00111                  * Note that we don't maintain strict FIFO ordering of
00112                  * threads going through the semaphore; that is, we
00113                  * might "get" it on the first try even if other
00114                  * threads are waiting. Apparently according to some
00115                  * textbooks semaphores must for some reason have
00116                  * strict ordering. Too bad. :-)
00117                  *
00118                  * Exercise: how would you implement strict FIFO
00119                  * ordering?
00120                  */
00121                 wchan_lock(sem->sem_wchan);
00122                 spinlock_release(&sem->sem_lock);
00123                 wchan_sleep(sem->sem_wchan);
00124 
00125                 spinlock_acquire(&sem->sem_lock);
00126         }
00127         KASSERT(sem->sem_count > 0);
00128         sem->sem_count--;
00129         spinlock_release(&sem->sem_lock);
00130 }
00131 
00132 void
00133 V(struct semaphore *sem)
00134 {
00135         KASSERT(sem != NULL);
00136 
00137         spinlock_acquire(&sem->sem_lock);
00138 
00139         sem->sem_count++;
00140         KASSERT(sem->sem_count > 0);
00141         wchan_wakeone(sem->sem_wchan);
00142 
00143         spinlock_release(&sem->sem_lock);
00144 }
00145 
00146 ////////////////////////////////////////////////////////////
00147 //
00148 // Lock.
00149 
00150 struct lock *
00151 lock_create(const char *name)
00152 {
00153         struct lock *lock;
00154 
00155         lock = kmalloc(sizeof(struct lock));
00156         if (lock == NULL) {
00157                 return NULL;
00158         }
00159 
00160         lock->lk_name = kstrdup(name);
00161         if (lock->lk_name == NULL) {
00162                 kfree(lock);
00163                 return NULL;
00164         }
00165         
00166         // add stuff here as needed
00167         
00168         return lock;
00169 }
00170 
00171 void
00172 lock_destroy(struct lock *lock)
00173 {
00174         KASSERT(lock != NULL);
00175 
00176         // add stuff here as needed
00177         
00178         kfree(lock->lk_name);
00179         kfree(lock);
00180 }
00181 
00182 void
00183 lock_acquire(struct lock *lock)
00184 {
00185         // Write this
00186 
00187         (void)lock;  // suppress warning until code gets written
00188 }
00189 
00190 void
00191 lock_release(struct lock *lock)
00192 {
00193         // Write this
00194 
00195         (void)lock;  // suppress warning until code gets written
00196 }
00197 
00198 bool
00199 lock_do_i_hold(struct lock *lock)
00200 {
00201         // Write this
00202 
00203         (void)lock;  // suppress warning until code gets written
00204 
00205         return true; // dummy until code gets written
00206 }
00207 
00208 ////////////////////////////////////////////////////////////
00209 //
00210 // CV
00211 
00212 
00213 struct cv *
00214 cv_create(const char *name)
00215 {
00216         struct cv *cv;
00217 
00218         cv = kmalloc(sizeof(struct cv));
00219         if (cv == NULL) {
00220                 return NULL;
00221         }
00222 
00223         cv->cv_name = kstrdup(name);
00224         if (cv->cv_name==NULL) {
00225                 kfree(cv);
00226                 return NULL;
00227         }
00228         
00229         // add stuff here as needed
00230         
00231         return cv;
00232 }
00233 
00234 void
00235 cv_destroy(struct cv *cv)
00236 {
00237         KASSERT(cv != NULL);
00238 
00239         // add stuff here as needed
00240         
00241         kfree(cv->cv_name);
00242         kfree(cv);
00243 }
00244 
00245 void
00246 cv_wait(struct cv *cv, struct lock *lock)
00247 {
00248         // Write this
00249         (void)cv;    // suppress warning until code gets written
00250         (void)lock;  // suppress warning until code gets written
00251 }
00252 
00253 void
00254 cv_signal(struct cv *cv, struct lock *lock)
00255 {
00256         // Write this
00257         (void)cv;    // suppress warning until code gets written
00258         (void)lock;  // suppress warning until code gets written
00259 }
00260 
00261 void
00262 cv_broadcast(struct cv *cv, struct lock *lock)
00263 {
00264         // Write this
00265         (void)cv;    // suppress warning until code gets written
00266         (void)lock;  // suppress warning until code gets written
00267 }
 All Data Structures