pintos-os.org Git - pintos-anon/blob - src/threads/thread.c

   1 #include "thread.h"
   2 #include <stddef.h>
   3 #include "debug.h"
   4 #include "interrupt.h"
   5 #include "intr-stubs.h"
   6 #include "lib.h"
   7 #include "mmu.h"
   8 #include "palloc.h"
   9 #include "random.h"
  10 #include "switch.h"
  11
  12 /* Offset of `stack' member within `struct thread'.
  13    Used by switch.S, which can't figure it out on its own. */
  14 uint32_t thread_stack_ofs = offsetof (struct thread, stack);
  15
  16 /* List of processes in THREAD_READY state,
  17    that is, processes that are ready to run but not actually
  18    running. */
  19 static struct list run_queue;
  20
  21 /* Thread to run when nothing else is ready. */
  22 static struct thread *idle_thread;
  23
  24 /* Idle thread.  Executes when no other thread is ready to run. */
  25 static void
  26 idle (void *aux UNUSED)
  27 {
  28   for (;;)
  29     {
  30       /* Wait for an interrupt. */
  31       asm ("hlt");
  32
  33       /* Let someone else run. */
  34       intr_disable ();
  35       thread_sleep ();
  36       intr_enable ();
  37     }
  38 }
  39
  40 /* Initializes the threading system and starts an initial thread
  41    which is immediately scheduled.  Never returns to the caller.
  42    The initial thread is named NAME and executes FUNCTION passing
  43    AUX as the argument. */
  44 void
  45 thread_init (const char *name, void (*function) (void *aux), void *aux)
  46 {
  47   struct thread *initial_thread;
  48
  49   ASSERT (intr_get_level () == IF_OFF);
  50
  51   /* Initialize run queue. */
  52   list_init (&run_queue);
  53
  54   /* Create idle thread. */
  55   idle_thread = thread_create ("idle", idle, NULL);
  56   idle_thread->status = THREAD_BLOCKED;
  57
  58   /* Create initial thread and switch to it. */
  59   initial_thread = thread_create (name, function, aux);
  60   list_remove (&initial_thread->rq_elem);
  61   initial_thread->status = THREAD_RUNNING;
  62   switch_threads (NULL, initial_thread);
  63
  64   NOT_REACHED ();
  65 }
  66 \f
  67 /* Stack frame for kernel_thread(). */
  68 struct kernel_thread_frame
  69   {
  70     void *eip;                  /* Return address. */
  71     void (*function) (void *);  /* Function to call. */
  72     void *aux;                  /* Auxiliary data for function. */
  73   };
  74
  75 /* Function used as the basis for a kernel thread. */
  76 static void
  77 kernel_thread (void (*function) (void *aux), void *aux)
  78 {
  79   ASSERT (function != NULL);
  80
  81   intr_enable ();       /* The scheduler runs with interrupts off. */
  82   function (aux);       /* Execute the thread function. */
  83   thread_exit ();       /* If function() returns, kill the thread. */
  84 }
  85
  86 /* Creates a new thread named NAME and initializes its fields.
  87    Returns the new thread if successful or a null pointer on
  88    failure. */
  89 static struct thread *
  90 new_thread (const char *name)
  91 {
  92   struct thread *t;
  93
  94   ASSERT (name != NULL);
  95
  96   t = palloc_get (PAL_ZERO);
  97   if (t != NULL)
  98     {
  99       strlcpy (t->name, name, sizeof t->name);
 100       t->stack = (uint8_t *) t + PGSIZE;
 101       t->status = THREAD_INITIALIZING;
 102     }
 103
 104   return t;
 105 }
 106
 107 /* Allocates a SIZE-byte frame within thread T's stack and
 108    returns a pointer to the frame's base. */
 109 static void *
 110 alloc_frame (struct thread *t, size_t size)
 111 {
 112   /* Stack data is always allocated in word-size units. */
 113   ASSERT (size % sizeof (uint32_t) == 0);
 114
 115   t->stack -= size;
 116   return t->stack;
 117 }
 118
 119 /* Creates a new kernel thread named NAME, which executes
 120    FUNCTION passing AUX as the argument.  The thread is added to
 121    the ready queue.  Thus, it may be scheduled even before
 122    thread_create() returns.  If you need to ensure ordering, then
 123    use synchronization, such as a semaphore. */
 124 struct thread *
 125 thread_create (const char *name, void (*function) (void *aux), void *aux)
 126 {
 127   struct thread *t;
 128   struct kernel_thread_frame *kf;
 129   struct switch_entry_frame *ef;
 130   struct switch_threads_frame *sf;
 131
 132   ASSERT (function != NULL);
 133
 134   t = new_thread (name);
 135
 136   /* Stack frame for kernel_thread(). */
 137   kf = alloc_frame (t, sizeof *kf);
 138   kf->eip = NULL;
 139   kf->function = function;
 140   kf->aux = aux;
 141
 142   /* Stack frame for switch_entry(). */
 143   ef = alloc_frame (t, sizeof *ef);
 144   ef->eip = (void (*) (void)) kernel_thread;
 145
 146   /* Stack frame for switch_threads(). */
 147   sf = alloc_frame (t, sizeof *sf);
 148   sf->eip = switch_entry;
 149
 150   /* Add to run queue. */
 151   thread_ready (t);
 152
 153   return t;
 154 }
 155
 156 struct thread *
 157 thread_current (void)
 158 {
 159   uint32_t *esp;
 160   asm ("movl %%esp, %0\n" : "=g" (esp));
 161   return pg_round_down (esp);
 162 }
 163
 164 #ifdef USERPROG
 165 bool
 166 thread_execute (const char *filename)
 167 {
 168   struct thread *t;
 169   struct intr_frame *if_;
 170   struct switch_entry_frame *ef;
 171   struct switch_threads_frame *sf;
 172   void (*start) (void);
 173
 174   ASSERT (filename != NULL);
 175
 176   t = new_thread (filename);
 177   if (t == NULL)
 178     return false;
 179
 180   if (!addrspace_load (&t->addrspace, filename, &start))
 181     panic ("%s: program load failed", filename);
 182
 183   /* Interrupt frame. */
 184   if_ = alloc_frame (t, sizeof *if_);
 185   if_->es = SEL_UDSEG;
 186   if_->ds = SEL_UDSEG;
 187   if_->eip = start;
 188   if_->cs = SEL_UCSEG;
 189   if_->eflags = FLAG_IF | 2;
 190   if_->esp = PHYS_BASE;
 191   if_->ss = SEL_UDSEG;
 192
 193   /* Stack frame for switch_entry(). */
 194   ef = alloc_frame (t, sizeof *ef);
 195   ef->eip = intr_exit;
 196
 197   /* Stack frame for switch_threads(). */
 198   sf = alloc_frame (t, sizeof *sf);
 199   sf->eip = switch_entry;
 200
 201   /* Add to run queue. */
 202   thread_ready (t);
 203
 204   return true;
 205 }
 206 #endif
 207
 208 void
 209 thread_ready (struct thread *t)
 210 {
 211   if (t->status != THREAD_READY)
 212     {
 213       list_push_back (&run_queue, &t->rq_elem);
 214       t->status = THREAD_READY;
 215     }
 216 }
 217
 218 static struct thread *
 219 find_next_to_run (void)
 220 {
 221   if (list_empty (&run_queue))
 222     return NULL;
 223   else
 224     return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
 225 }
 226
 227 void
 228 thread_destroy (struct thread *t)
 229 {
 230   ASSERT (t->status == THREAD_DYING);
 231   ASSERT (t != thread_current ());
 232
 233   palloc_free (t);
 234 }
 235
 236 void schedule_tail (struct thread *prev);
 237
 238 void
 239 schedule_tail (struct thread *prev)
 240 {
 241   ASSERT (intr_get_level () == IF_OFF);
 242
 243 #ifdef USERPROG
 244   addrspace_activate (&thread_current ()->addrspace);
 245 #endif
 246
 247   if (prev != NULL && prev->status == THREAD_DYING)
 248     thread_destroy (prev);
 249 }
 250
 251 static void
 252 thread_schedule (void)
 253 {
 254   struct thread *cur, *next, *prev;
 255
 256   ASSERT (intr_get_level () == IF_OFF);
 257
 258   cur = thread_current ();
 259   ASSERT (cur->status != THREAD_RUNNING);
 260
 261   next = find_next_to_run ();
 262   if (next == NULL)
 263     next = idle_thread;
 264
 265   next->status = THREAD_RUNNING;
 266   if (cur != next)
 267     {
 268       prev = switch_threads (cur, next);
 269
 270       /* Prevent GCC from reordering anything around the thread
 271          switch. */
 272       asm volatile ("" : : : "memory");
 273
 274       schedule_tail (prev);
 275     }
 276 }
 277
 278 void
 279 thread_yield (void)
 280 {
 281   enum if_level old_level;
 282
 283   ASSERT (!intr_context ());
 284
 285   old_level = intr_disable ();
 286   thread_ready (thread_current ());
 287   thread_schedule ();
 288   intr_set_level (old_level);
 289 }
 290
 291 void
 292 thread_exit (void)
 293 {
 294   ASSERT (!intr_context ());
 295
 296   intr_disable ();
 297   thread_current ()->status = THREAD_DYING;
 298   thread_schedule ();
 299   NOT_REACHED ();
 300 }
 301
 302 void
 303 thread_sleep (void)
 304 {
 305   ASSERT (!intr_context ());
 306   ASSERT (intr_get_level () == IF_OFF);
 307
 308   thread_current ()->status = THREAD_BLOCKED;
 309   thread_schedule ();
 310 }