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/process.h"
  16 #include "userprog/gdt.h"
  17 #endif
  18
  19 /* Random value for struct thread's `magic' member.
  20    Used to detect stack overflow.  See the big comment at the top
  21    of thread.h for details. */
  22 #define THREAD_MAGIC 0xcd6abf4b
  23
  24 /* List of processes in THREAD_READY state, that is, processes
  25    that are ready to run but not actually running. */
  26 static struct list ready_list;
  27
  28 /* Idle thread. */
  29 static struct thread *idle_thread;
  30
  31 /* Initial thread, the thread running init.c:main(). */
  32 static struct thread *initial_thread;
  33
  34 /* Lock used by allocate_tid(). */
  35 static struct lock tid_lock;
  36
  37 /* Stack frame for kernel_thread(). */
  38 struct kernel_thread_frame
  39   {
  40     void *eip;                  /* Return address. */
  41     thread_func *function;      /* Function to call. */
  42     void *aux;                  /* Auxiliary data for function. */
  43   };
  44
  45 static void kernel_thread (thread_func *, void *aux);
  46
  47 static void idle (void *aux UNUSED);
  48 static struct thread *running_thread (void);
  49 static struct thread *next_thread_to_run (void);
  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   /* Allocate thread. */
 119   t = palloc_get (PAL_ZERO);
 120   if (t == NULL)
 121     return TID_ERROR;
 122
 123   /* Initialize thread. */
 124   init_thread (t, name, priority);
 125   tid = t->tid = allocate_tid ();
 126
 127   /* Stack frame for kernel_thread(). */
 128   kf = alloc_frame (t, sizeof *kf);
 129   kf->eip = NULL;
 130   kf->function = function;
 131   kf->aux = aux;
 132
 133   /* Stack frame for switch_entry(). */
 134   ef = alloc_frame (t, sizeof *ef);
 135   ef->eip = (void (*) (void)) kernel_thread;
 136
 137   /* Stack frame for switch_threads(). */
 138   sf = alloc_frame (t, sizeof *sf);
 139   sf->eip = switch_entry;
 140
 141   /* Add to run queue. */
 142   thread_unblock (t);
 143
 144   return tid;
 145 }
 146
 147 /* Transitions a blocked thread T from its current state to the
 148    ready-to-run state.  This is an error if T is not blocked.
 149    (Use thread_yield() to make the running thread ready.) */
 150 void
 151 thread_unblock (struct thread *t)
 152 {
 153   enum intr_level old_level;
 154
 155   ASSERT (is_thread (t));
 156
 157   old_level = intr_disable ();
 158   ASSERT (t->status == THREAD_BLOCKED);
 159   list_push_back (&ready_list, &t->elem);
 160   t->status = THREAD_READY;
 161   intr_set_level (old_level);
 162 }
 163
 164 /* Returns the name of the running thread. */
 165 const char *
 166 thread_name (void)
 167 {
 168   return thread_current ()->name;
 169 }
 170
 171 /* Returns the running thread.
 172    This is running_thread() plus a couple of sanity checks.
 173    See the big comment at the top of thread.h for details. */
 174 struct thread *
 175 thread_current (void)
 176 {
 177   struct thread *t = running_thread ();
 178
 179   /* Make sure T is really a thread.
 180      If either of these assertions fire, then your thread may
 181      have overflowed its stack.  Each thread has less than 4 kB
 182      of stack, so a few big automatic arrays or moderate
 183      recursion can cause stack overflow. */
 184   ASSERT (is_thread (t));
 185   ASSERT (t->status == THREAD_RUNNING);
 186
 187   return t;
 188 }
 189
 190 /* Returns the running thread's tid. */
 191 tid_t
 192 thread_tid (void)
 193 {
 194   return thread_current ()->tid;
 195 }
 196
 197 /* Deschedules the current thread and destroys it.  Never
 198    returns to the caller. */
 199 void
 200 thread_exit (void)
 201 {
 202   ASSERT (!intr_context ());
 203
 204   /* Just set our status to dying and schedule another process.
 205      We will be destroyed during the call to schedule_tail(). */
 206   intr_disable ();
 207   thread_current ()->status = THREAD_DYING;
 208   schedule ();
 209   NOT_REACHED ();
 210 }
 211
 212 /* Yields the CPU.  The current thread is not put to sleep and
 213    may be scheduled again immediately at the scheduler's whim. */
 214 void
 215 thread_yield (void)
 216 {
 217   struct thread *cur = thread_current ();
 218   enum intr_level old_level;
 219
 220   ASSERT (!intr_context ());
 221
 222   old_level = intr_disable ();
 223   list_push_back (&ready_list, &cur->elem);
 224   cur->status = THREAD_READY;
 225   schedule ();
 226   intr_set_level (old_level);
 227 }
 228
 229 /* Puts the current thread to sleep.  It will not be scheduled
 230    again until awoken by thread_unblock().
 231
 232    This function must be called with interrupts turned off.  It
 233    is usually a better idea to use one of the synchronization
 234    primitives in synch.h. */
 235 void
 236 thread_block (void)
 237 {
 238   ASSERT (!intr_context ());
 239   ASSERT (intr_get_level () == INTR_OFF);
 240
 241   thread_current ()->status = THREAD_BLOCKED;
 242   schedule ();
 243 }
 244 \f
 245 /* Idle thread.  Executes when no other thread is ready to run. */
 246 static void
 247 idle (void *aux UNUSED)
 248 {
 249   idle_thread = thread_current ();
 250
 251   for (;;)
 252     {
 253       /* Let someone else run. */
 254       intr_disable ();
 255       thread_block ();
 256       intr_enable ();
 257
 258       /* Use CPU `hlt' instruction to wait for interrupt. */
 259       asm ("hlt");
 260     }
 261 }
 262
 263 /* Function used as the basis for a kernel thread. */
 264 static void
 265 kernel_thread (thread_func *function, void *aux)
 266 {
 267   ASSERT (function != NULL);
 268
 269   intr_enable ();       /* The scheduler runs with interrupts off. */
 270   function (aux);       /* Execute the thread function. */
 271   thread_exit ();       /* If function() returns, kill the thread. */
 272 }
 273 \f
 274 /* Returns the running thread. */
 275 struct thread *
 276 running_thread (void)
 277 {
 278   uint32_t *esp;
 279
 280   /* Copy the CPU's stack pointer into `esp', and then round that
 281      down to the start of a page.  Because `struct thread' is
 282      always at the beginning of a page and the stack pointer is
 283      somewhere in the middle, this locates the curent thread. */
 284   asm ("movl %%esp, %0\n" : "=g" (esp));
 285   return pg_round_down (esp);
 286 }
 287
 288 /* Returns true if T appears to point to a valid thread. */
 289 static bool
 290 is_thread (struct thread *t)
 291 {
 292   return t != NULL && t->magic == THREAD_MAGIC;
 293 }
 294
 295 /* Does basic initialization of T as a blocked thread named
 296    NAME. */
 297 static void
 298 init_thread (struct thread *t, const char *name, int priority)
 299 {
 300   ASSERT (t != NULL);
 301   ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
 302   ASSERT (name != NULL);
 303
 304   memset (t, 0, sizeof *t);
 305   t->status = THREAD_BLOCKED;
 306   strlcpy (t->name, name, sizeof t->name);
 307   t->stack = (uint8_t *) t + PGSIZE;
 308   t->priority = priority;
 309   t->magic = THREAD_MAGIC;
 310 }
 311
 312 /* Allocates a SIZE-byte frame at the top of thread T's stack and
 313    returns a pointer to the frame's base. */
 314 static void *
 315 alloc_frame (struct thread *t, size_t size)
 316 {
 317   /* Stack data is always allocated in word-size units. */
 318   ASSERT (is_thread (t));
 319   ASSERT (size % sizeof (uint32_t) == 0);
 320
 321   t->stack -= size;
 322   return t->stack;
 323 }
 324
 325 /* Chooses and returns the next thread to be scheduled.  Should
 326    return a thread from the run queue, unless the run queue is
 327    empty.  (If the running thread can continue running, then it
 328    will be in the run queue.)  If the run queue is empty, return
 329    idle_thread. */
 330 static struct thread *
 331 next_thread_to_run (void)
 332 {
 333   if (list_empty (&ready_list))
 334     return idle_thread;
 335   else
 336     return list_entry (list_pop_front (&ready_list), struct thread, elem);
 337 }
 338
 339 /* Destroys T, which must not be the running thread. */
 340 static void
 341 destroy_thread (struct thread *t)
 342 {
 343   ASSERT (is_thread (t));
 344   ASSERT (t != thread_current ());
 345
 346 #ifdef USERPROG
 347   process_destroy (t);
 348 #endif
 349   if (t != initial_thread)
 350     palloc_free (t);
 351 }
 352
 353 /* Completes a thread switch by activating the new thread's page
 354    tables, and, if the previous thread is dying, destroying it.
 355
 356    At this function's invocation, we just switched from thread
 357    PREV, the new thread is already running, and interrupts are
 358    still disabled.  This function is normally invoked by
 359    thread_schedule() as its final action before returning, but
 360    the first time a thread is scheduled it is called by
 361    switch_entry() (see switch.S).
 362
 363    After this function and its caller returns, the thread switch
 364    is complete. */
 365 void
 366 schedule_tail (struct thread *prev)
 367 {
 368   struct thread *cur = running_thread ();
 369
 370   ASSERT (intr_get_level () == INTR_OFF);
 371
 372   /* Mark us as running. */
 373   cur->status = THREAD_RUNNING;
 374
 375 #ifdef USERPROG
 376   /* Activate the new address space. */
 377   process_activate ();
 378 #endif
 379
 380   /* If the thread we switched from is dying, destroy it.
 381      This must happen late because it's not a good idea to
 382      e.g. destroy the page table you're currently using. */
 383   if (prev != NULL && prev->status == THREAD_DYING)
 384     destroy_thread (prev);
 385 }
 386
 387 /* Schedules a new process.  At entry, interrupts must be off and
 388    the running process's state must have been changed from
 389    running to some other state.  This function finds another
 390    thread to run and switches to it. */
 391 static void
 392 schedule (void)
 393 {
 394   struct thread *cur = running_thread ();
 395   struct thread *next = next_thread_to_run ();
 396   struct thread *prev = NULL;
 397
 398   ASSERT (intr_get_level () == INTR_OFF);
 399   ASSERT (cur->status != THREAD_RUNNING);
 400   ASSERT (is_thread (next));
 401
 402   if (cur != next)
 403     prev = switch_threads (cur, next);
 404   schedule_tail (prev);
 405 }
 406
 407 /* Returns a tid to use for a new thread. */
 408 static tid_t
 409 allocate_tid (void)
 410 {
 411   static tid_t next_tid = 1;
 412   tid_t tid;
 413
 414   lock_acquire (&tid_lock);
 415   tid = next_tid++;
 416   lock_release (&tid_lock);
 417
 418   return tid;
 419 }
 420 \f
 421 /* Offset of `stack' member within `struct thread'.
 422    Used by switch.S, which can't figure it out on its own. */
 423 uint32_t thread_stack_ofs = offsetof (struct thread, stack);