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 #ifdef USERPROG
  12 #include "gdt.h"
  13 #endif
  14
  15 #define THREAD_MAGIC 0x1234abcdu
  16
  17 /* List of processes in THREAD_READY state, that is, processes
  18    that are ready to run but not actually running. */
  19 static struct list run_queue;
  20
  21 /* Idle thread. */
  22 static struct thread *idle_thread;      /* Thread. */
  23 static void idle (void *aux UNUSED);    /* Thread function. */
  24
  25 /* Stack frame for kernel_thread(). */
  26 struct kernel_thread_frame
  27   {
  28     void *eip;                  /* Return address. */
  29     thread_func *function;      /* Function to call. */
  30     void *aux;                  /* Auxiliary data for function. */
  31   };
  32
  33 static void kernel_thread (thread_func *, void *aux);
  34
  35 static struct thread *next_thread_to_run (void);
  36 static struct thread *new_thread (const char *name);
  37 static bool is_thread (struct thread *t);
  38 static void *alloc_frame (struct thread *t, size_t size);
  39 static void destroy_thread (struct thread *t);
  40 static void schedule (void);
  41 void schedule_tail (struct thread *prev);
  42
  43 /* Initializes the threading system.  After calling, create some
  44    threads with thread_create() or thread_execute(), then start
  45    the scheduler with thread_start(). */
  46 void
  47 thread_init (void)
  48 {
  49   ASSERT (intr_get_level () == INTR_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
  59 /* Starts the thread scheduler.  The caller should have created
  60    some threads with thread_create() or thread_execute().  Never
  61    returns to the caller. */
  62 void
  63 thread_start (void)
  64 {
  65   struct thread *t = next_thread_to_run ();
  66   if (t->status == THREAD_READY)
  67     list_remove (&t->rq_elem);
  68   t->status = THREAD_RUNNING;
  69   switch_threads (NULL, t);
  70
  71   NOT_REACHED ();
  72 }
  73
  74 /* Creates a new kernel thread named NAME, which executes
  75    FUNCTION passing AUX as the argument, and adds it to the ready
  76    queue.  If thread_start() has been called, then the new thread
  77    may be scheduled before thread_create() returns.  Use a
  78    semaphore or some other form of synchronization if you need to
  79    ensure ordering. */
  80 struct thread *
  81 thread_create (const char *name, thread_func *function, void *aux)
  82 {
  83   struct thread *t;
  84   struct kernel_thread_frame *kf;
  85   struct switch_entry_frame *ef;
  86   struct switch_threads_frame *sf;
  87
  88   ASSERT (function != NULL);
  89
  90   t = new_thread (name);
  91
  92   /* Stack frame for kernel_thread(). */
  93   kf = alloc_frame (t, sizeof *kf);
  94   kf->eip = NULL;
  95   kf->function = function;
  96   kf->aux = aux;
  97
  98   /* Stack frame for switch_entry(). */
  99   ef = alloc_frame (t, sizeof *ef);
 100   ef->eip = (void (*) (void)) kernel_thread;
 101
 102   /* Stack frame for switch_threads(). */
 103   sf = alloc_frame (t, sizeof *sf);
 104   sf->eip = switch_entry;
 105
 106   /* Add to run queue. */
 107   thread_wake (t);
 108
 109   return t;
 110 }
 111
 112 #ifdef USERPROG
 113 /* Starts a new thread running a user program loaded from
 114    FILENAME, and adds it to the ready queue.  If thread_start()
 115    has been called, then new thread may be scheduled before
 116    thread_execute() returns.*/
 117 bool
 118 thread_execute (const char *filename)
 119 {
 120   struct thread *t;
 121   struct intr_frame *if_;
 122   struct switch_entry_frame *ef;
 123   struct switch_threads_frame *sf;
 124   void (*start) (void);
 125
 126   ASSERT (filename != NULL);
 127
 128   t = new_thread (filename);
 129   if (t == NULL)
 130     return false;
 131
 132   if (!addrspace_load (t, filename, &start))
 133     PANIC ("%s: program load failed", filename);
 134
 135   /* Interrupt frame. */
 136   if_ = alloc_frame (t, sizeof *if_);
 137   if_->es = SEL_UDSEG;
 138   if_->ds = SEL_UDSEG;
 139   if_->eip = start;
 140   if_->cs = SEL_UCSEG;
 141   if_->eflags = FLAG_IF | FLAG_MBS;
 142   if_->esp = PHYS_BASE;
 143   if_->ss = SEL_UDSEG;
 144
 145   /* Stack frame for switch_entry(). */
 146   ef = alloc_frame (t, sizeof *ef);
 147   ef->eip = intr_exit;
 148
 149   /* Stack frame for switch_threads(). */
 150   sf = alloc_frame (t, sizeof *sf);
 151   sf->eip = switch_entry;
 152
 153   /* Add to run queue. */
 154   thread_wake (t);
 155
 156   return true;
 157 }
 158 #endif
 159
 160 /* Transitions T from its current state to THREAD_READY, the
 161    ready-to-run state.  On entry, T must be ready or blocked.
 162    (Use thread_yield() to make the running thread ready.) */
 163 void
 164 thread_wake (struct thread *t)
 165 {
 166   ASSERT (is_thread (t));
 167   ASSERT (t->status == THREAD_READY || t->status == THREAD_BLOCKED);
 168   if (t->status != THREAD_READY)
 169     {
 170       list_push_back (&run_queue, &t->rq_elem);
 171       t->status = THREAD_READY;
 172     }
 173 }
 174
 175 /* Returns the name of thread T. */
 176 const char *
 177 thread_name (struct thread *t)
 178 {
 179   ASSERT (is_thread (t));
 180   return t->name;
 181 }
 182
 183 /* Returns the running thread. */
 184 struct thread *
 185 thread_current (void)
 186 {
 187   uint32_t *esp;
 188   struct thread *t;
 189
 190   /* Copy the CPU's stack pointer into `esp', and then round that
 191      down to the start of a page.  Because `struct thread' is
 192      always at the beginning of a page and the stack pointer is
 193      somewhere in the middle, this locates the curent thread. */
 194   asm ("movl %%esp, %0\n" : "=g" (esp));
 195   t = pg_round_down (esp);
 196
 197   /* Make sure T is really a thread.
 198      If this assertion fires, then your thread may have
 199      overflowed its stack.  Each thread has less than 4 kB of
 200      stack, so a few big automatic arrays or moderate recursion
 201      can cause stack overflow. */
 202   ASSERT (is_thread (t));
 203
 204   return t;
 205 }
 206
 207 /* Deschedules the current thread and destroys it.  Never
 208    returns to the caller. */
 209 void
 210 thread_exit (void)
 211 {
 212   ASSERT (!intr_context ());
 213
 214   intr_disable ();
 215   thread_current ()->status = THREAD_DYING;
 216   schedule ();
 217   NOT_REACHED ();
 218 }
 219
 220 /* Yields the CPU.  The current thread is not put to sleep and
 221    may be scheduled again immediately at the scheduler's whim. */
 222 void
 223 thread_yield (void)
 224 {
 225   struct thread *cur = thread_current ();
 226   enum intr_level old_level;
 227
 228   ASSERT (!intr_context ());
 229
 230   old_level = intr_disable ();
 231   list_push_back (&run_queue, &cur->rq_elem);
 232   cur->status = THREAD_READY;
 233   schedule ();
 234   intr_set_level (old_level);
 235 }
 236
 237 /* Puts the current thread to sleep.  It will not be scheduled
 238    again until awoken by thread_wake(). */
 239 void
 240 thread_sleep (void)
 241 {
 242   ASSERT (!intr_context ());
 243   ASSERT (intr_get_level () == INTR_OFF);
 244
 245   thread_current ()->status = THREAD_BLOCKED;
 246   schedule ();
 247 }
 248 \f
 249 /* Idle thread.  Executes when no other thread is ready to run. */
 250 static void
 251 idle (void *aux UNUSED)
 252 {
 253   for (;;)
 254     {
 255       /* Wait for an interrupt. */
 256       DEBUG (idle, "idle");
 257       asm ("hlt");
 258
 259       /* Let someone else run. */
 260       intr_disable ();
 261       thread_sleep ();
 262       intr_enable ();
 263     }
 264 }
 265
 266 /* Function used as the basis for a kernel thread. */
 267 static void
 268 kernel_thread (thread_func *function, void *aux)
 269 {
 270   ASSERT (function != NULL);
 271
 272   intr_enable ();       /* The scheduler runs with interrupts off. */
 273   function (aux);       /* Execute the thread function. */
 274   thread_exit ();       /* If function() returns, kill the thread. */
 275 }
 276 \f
 277 /* Returns true if T appears to point to a valid thread. */
 278 static bool
 279 is_thread (struct thread *t)
 280 {
 281   return t != NULL && t->magic == THREAD_MAGIC;
 282 }
 283
 284 /* Creates a new thread named NAME and initializes its fields.
 285    Returns the new thread if successful or a null pointer on
 286    failure. */
 287 static struct thread *
 288 new_thread (const char *name)
 289 {
 290   struct thread *t;
 291
 292   ASSERT (name != NULL);
 293
 294   t = palloc_get (PAL_ZERO);
 295   if (t != NULL)
 296     {
 297       strlcpy (t->name, name, sizeof t->name);
 298       t->stack = (uint8_t *) t + PGSIZE;
 299       t->status = THREAD_BLOCKED;
 300       t->magic = THREAD_MAGIC;
 301     }
 302
 303   return t;
 304 }
 305
 306 /* Allocates a SIZE-byte frame at the top of thread T's stack and
 307    returns a pointer to the frame's base. */
 308 static void *
 309 alloc_frame (struct thread *t, size_t size)
 310 {
 311   /* Stack data is always allocated in word-size units. */
 312   ASSERT (is_thread (t));
 313   ASSERT (size % sizeof (uint32_t) == 0);
 314
 315   t->stack -= size;
 316   return t->stack;
 317 }
 318
 319 /* Chooses and returns the next thread to be scheduled.  Should
 320    return a thread from the run queue, unless the run queue is
 321    empty.  (If the running thread can continue running, then it
 322    will be in the run queue.)  If the run queue is empty, return
 323    idle_thread. */
 324 static struct thread *
 325 next_thread_to_run (void)
 326 {
 327   if (list_empty (&run_queue))
 328     return idle_thread;
 329   else
 330     return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
 331 }
 332
 333 /* Destroys T, which must be in the dying state and must not be
 334    the running thread. */
 335 static void
 336 destroy_thread (struct thread *t)
 337 {
 338   ASSERT (is_thread (t));
 339   ASSERT (t->status == THREAD_DYING);
 340   ASSERT (t != thread_current ());
 341
 342 #ifdef USERPROG
 343   addrspace_destroy (t);
 344 #endif
 345   palloc_free (t);
 346 }
 347
 348 /* Completes a thread switch by activating the new thread's page
 349    tables, and, if the previous thread is dying, destroying it.
 350
 351    At this function's invocation, we just switched from thread
 352    PREV, the new thread is already running, and interrupts are
 353    still disabled.  This function is normally invoked by
 354    thread_schedule() as its final action before returning, but
 355    the first time a thread is scheduled it is called by
 356    switch_entry() (see switch.S).
 357
 358    After this function and its caller returns, the thread switch
 359    is complete. */
 360 void
 361 schedule_tail (struct thread *prev)
 362 {
 363   struct thread *cur = thread_current ();
 364
 365   ASSERT (intr_get_level () == INTR_OFF);
 366
 367   cur->status = THREAD_RUNNING;
 368   if (prev != NULL && prev->status == THREAD_DYING)
 369     destroy_thread (prev);
 370
 371 #ifdef USERPROG
 372   addrspace_activate (cur);
 373 #endif
 374 }
 375
 376 /* Schedules a new process.  At entry, interrupts must be off and
 377    the running process's state must have been changed from
 378    running to some other state.  This function finds another
 379    thread to run and switches to it. */
 380 static void
 381 schedule (void)
 382 {
 383   struct thread *cur = thread_current ();
 384   struct thread *next = next_thread_to_run ();
 385
 386   ASSERT (intr_get_level () == INTR_OFF);
 387   ASSERT (cur->status != THREAD_RUNNING);
 388   ASSERT (is_thread (next));
 389
 390   if (cur != next)
 391     {
 392       struct thread *prev = switch_threads (cur, next);
 393       schedule_tail (prev);
 394     }
 395 }
 396 \f
 397 /* Offset of `stack' member within `struct thread'.
 398    Used by switch.S, which can't figure it out on its own. */
 399 uint32_t thread_stack_ofs = offsetof (struct thread, stack);