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