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_wake (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_wake (t);
 164
 165   return true;
 166 }
 167 #endif
 168
 169 /* Transitions T from its current state to THREAD_READY, the
 170    ready-to-run state.  On entry, T must be ready or blocked.
 171    (Use thread_yield() to make the running thread ready.) */
 172 void
 173 thread_wake (struct thread *t)
 174 {
 175   ASSERT (is_thread (t));
 176   ASSERT (t->status == THREAD_READY || t->status == THREAD_BLOCKED);
 177   if (t->status != THREAD_READY)
 178     {
 179       list_push_back (&run_queue, &t->rq_elem);
 180       t->status = THREAD_READY;
 181     }
 182 }
 183
 184 /* Returns the name of thread T. */
 185 const char *
 186 thread_name (struct thread *t)
 187 {
 188   ASSERT (is_thread (t));
 189   return t->name;
 190 }
 191
 192 /* Returns the running thread.
 193    This is running_thread() plus a couple of sanity checks. */
 194 struct thread *
 195 thread_current (void)
 196 {
 197   struct thread *t = running_thread ();
 198
 199   /* Make sure T is really a thread.
 200      If either of these assertions fire, then your thread may
 201      have overflowed its stack.  Each thread has less than 4 kB
 202      of stack, so a few big automatic arrays or moderate
 203      recursion can cause stack overflow. */
 204   ASSERT (is_thread (t));
 205   ASSERT (t->status == THREAD_RUNNING);
 206
 207   return t;
 208 }
 209
 210 /* Deschedules the current thread and destroys it.  Never
 211    returns to the caller. */
 212 void
 213 thread_exit (void)
 214 {
 215   ASSERT (!intr_context ());
 216
 217   intr_disable ();
 218   thread_current ()->status = THREAD_DYING;
 219   schedule ();
 220   NOT_REACHED ();
 221 }
 222
 223 /* Yields the CPU.  The current thread is not put to sleep and
 224    may be scheduled again immediately at the scheduler's whim. */
 225 void
 226 thread_yield (void)
 227 {
 228   struct thread *cur = thread_current ();
 229   enum intr_level old_level;
 230
 231   ASSERT (!intr_context ());
 232
 233   old_level = intr_disable ();
 234   list_push_back (&run_queue, &cur->rq_elem);
 235   cur->status = THREAD_READY;
 236   schedule ();
 237   intr_set_level (old_level);
 238 }
 239
 240 /* Puts the current thread to sleep.  It will not be scheduled
 241    again until awoken by thread_wake(). */
 242 void
 243 thread_sleep (void)
 244 {
 245   ASSERT (!intr_context ());
 246   ASSERT (intr_get_level () == INTR_OFF);
 247
 248   thread_current ()->status = THREAD_BLOCKED;
 249   schedule ();
 250 }
 251 \f
 252 /* Idle thread.  Executes when no other thread is ready to run. */
 253 static void
 254 idle (void *aux UNUSED)
 255 {
 256   for (;;)
 257     {
 258       /* Wait for an interrupt. */
 259       DEBUG (idle, "idle");
 260       asm ("hlt");
 261
 262       /* Let someone else run. */
 263       intr_disable ();
 264       thread_sleep ();
 265       intr_enable ();
 266     }
 267 }
 268
 269 /* Function used as the basis for a kernel thread. */
 270 static void
 271 kernel_thread (thread_func *function, void *aux)
 272 {
 273   ASSERT (function != NULL);
 274
 275   intr_enable ();       /* The scheduler runs with interrupts off. */
 276   function (aux);       /* Execute the thread function. */
 277   thread_exit ();       /* If function() returns, kill the thread. */
 278 }
 279 \f
 280 /* Returns the running thread. */
 281 struct thread *
 282 running_thread (void)
 283 {
 284   uint32_t *esp;
 285
 286   /* Copy the CPU's stack pointer into `esp', and then round that
 287      down to the start of a page.  Because `struct thread' is
 288      always at the beginning of a page and the stack pointer is
 289      somewhere in the middle, this locates the curent thread. */
 290   asm ("movl %%esp, %0\n" : "=g" (esp));
 291   return pg_round_down (esp);
 292 }
 293
 294 /* Returns true if T appears to point to a valid thread. */
 295 static bool
 296 is_thread (struct thread *t)
 297 {
 298   return t != NULL && t->magic == THREAD_MAGIC;
 299 }
 300
 301 /* Creates a new thread named NAME and initializes its fields.
 302    Returns the new thread if successful or a null pointer on
 303    failure. */
 304 static struct thread *
 305 new_thread (const char *name)
 306 {
 307   struct thread *t;
 308
 309   ASSERT (name != NULL);
 310
 311   t = palloc_get (PAL_ZERO);
 312   if (t != NULL)
 313     init_thread (t, name);
 314
 315   return t;
 316 }
 317
 318 /* Initializes T as a new thread named NAME. */
 319 static void
 320 init_thread (struct thread *t, const char *name)
 321 {
 322   memset (t, 0, sizeof *t);
 323   strlcpy (t->name, name, sizeof t->name);
 324   t->stack = (uint8_t *) t + PGSIZE;
 325   t->status = THREAD_BLOCKED;
 326   t->magic = THREAD_MAGIC;
 327 }
 328
 329 /* Allocates a SIZE-byte frame at the top of thread T's stack and
 330    returns a pointer to the frame's base. */
 331 static void *
 332 alloc_frame (struct thread *t, size_t size)
 333 {
 334   /* Stack data is always allocated in word-size units. */
 335   ASSERT (is_thread (t));
 336   ASSERT (size % sizeof (uint32_t) == 0);
 337
 338   t->stack -= size;
 339   return t->stack;
 340 }
 341
 342 /* Chooses and returns the next thread to be scheduled.  Should
 343    return a thread from the run queue, unless the run queue is
 344    empty.  (If the running thread can continue running, then it
 345    will be in the run queue.)  If the run queue is empty, return
 346    idle_thread. */
 347 static struct thread *
 348 next_thread_to_run (void)
 349 {
 350   if (list_empty (&run_queue))
 351     return idle_thread;
 352   else
 353     return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
 354 }
 355
 356 /* Destroys T, which must be in the dying state and must not be
 357    the running thread. */
 358 static void
 359 destroy_thread (struct thread *t)
 360 {
 361   ASSERT (is_thread (t));
 362   ASSERT (t->status == THREAD_DYING);
 363   ASSERT (t != thread_current ());
 364
 365 #ifdef USERPROG
 366   addrspace_destroy (t);
 367 #endif
 368   palloc_free (t);
 369 }
 370
 371 /* Completes a thread switch by activating the new thread's page
 372    tables, and, if the previous thread is dying, destroying it.
 373
 374    At this function's invocation, we just switched from thread
 375    PREV, the new thread is already running, and interrupts are
 376    still disabled.  This function is normally invoked by
 377    thread_schedule() as its final action before returning, but
 378    the first time a thread is scheduled it is called by
 379    switch_entry() (see switch.S).
 380
 381    After this function and its caller returns, the thread switch
 382    is complete. */
 383 void
 384 schedule_tail (struct thread *prev)
 385 {
 386   struct thread *cur = running_thread ();
 387
 388   ASSERT (intr_get_level () == INTR_OFF);
 389
 390   cur->status = THREAD_RUNNING;
 391   if (prev != NULL && prev->status == THREAD_DYING)
 392     destroy_thread (prev);
 393
 394 #ifdef USERPROG
 395   addrspace_activate (cur);
 396 #endif
 397 }
 398
 399 /* Schedules a new process.  At entry, interrupts must be off and
 400    the running process's state must have been changed from
 401    running to some other state.  This function finds another
 402    thread to run and switches to it. */
 403 static void
 404 schedule (void)
 405 {
 406   struct thread *cur = running_thread ();
 407   struct thread *next = next_thread_to_run ();
 408   struct thread *prev = NULL;
 409
 410   ASSERT (intr_get_level () == INTR_OFF);
 411   ASSERT (cur->status != THREAD_RUNNING);
 412   ASSERT (is_thread (next));
 413
 414   if (cur != next)
 415     prev = switch_threads (cur, next);
 416   schedule_tail (prev);
 417 }
 418 \f
 419 /* Offset of `stack' member within `struct thread'.
 420    Used by switch.S, which can't figure it out on its own. */
 421 uint32_t thread_stack_ofs = offsetof (struct thread, stack);