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