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