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