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