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