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

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