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 /* Sets the current thread's priority to NEW_PRIORITY. */
 278 void
 279 thread_set_priority (int new_priority)
 280 {
 281   thread_current ()->priority = new_priority;
 282 }
 283
 284 /* Returns the current thread's priority. */
 285 int
 286 thread_get_priority (void)
 287 {
 288   return thread_current ()->priority;
 289 }
 290 \f
 291 /* Idle thread.  Executes when no other thread is ready to run. */
 292 static void
 293 idle (void *aux UNUSED)
 294 {
 295   idle_thread = thread_current ();
 296
 297   for (;;)
 298     {
 299       /* Let someone else run. */
 300       intr_disable ();
 301       thread_block ();
 302
 303       /* Re-enable interrupts and wait for the next one.
 304
 305          The `sti' instruction disables interrupts until the
 306          completion of the next instruction, so these two
 307          instructions are executed atomically.  This atomicity is
 308          important; otherwise, an interrupt could be handled
 309          between re-enabling interrupts and waiting for the next
 310          one to occur, wasting as much as one clock tick worth of
 311          time.
 312
 313          See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3] 7.7. */
 314       asm ("sti; hlt");
 315     }
 316 }
 317
 318 /* Function used as the basis for a kernel thread. */
 319 static void
 320 kernel_thread (thread_func *function, void *aux)
 321 {
 322   ASSERT (function != NULL);
 323
 324   intr_enable ();       /* The scheduler runs with interrupts off. */
 325   function (aux);       /* Execute the thread function. */
 326   thread_exit ();       /* If function() returns, kill the thread. */
 327 }
 328 \f
 329 /* Returns the running thread. */
 330 struct thread *
 331 running_thread (void)
 332 {
 333   uint32_t *esp;
 334
 335   /* Copy the CPU's stack pointer into `esp', and then round that
 336      down to the start of a page.  Because `struct thread' is
 337      always at the beginning of a page and the stack pointer is
 338      somewhere in the middle, this locates the curent thread. */
 339   asm ("mov %0, %%esp" : "=g" (esp));
 340   return pg_round_down (esp);
 341 }
 342
 343 /* Returns true if T appears to point to a valid thread. */
 344 static bool
 345 is_thread (struct thread *t)
 346 {
 347   return t != NULL && t->magic == THREAD_MAGIC;
 348 }
 349
 350 /* Does basic initialization of T as a blocked thread named
 351    NAME. */
 352 static void
 353 init_thread (struct thread *t, const char *name, int priority)
 354 {
 355   ASSERT (t != NULL);
 356   ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
 357   ASSERT (name != NULL);
 358
 359   memset (t, 0, sizeof *t);
 360   t->status = THREAD_BLOCKED;
 361   strlcpy (t->name, name, sizeof t->name);
 362   t->stack = (uint8_t *) t + PGSIZE;
 363   t->priority = priority;
 364   t->magic = THREAD_MAGIC;
 365 }
 366
 367 /* Allocates a SIZE-byte frame at the top of thread T's stack and
 368    returns a pointer to the frame's base. */
 369 static void *
 370 alloc_frame (struct thread *t, size_t size)
 371 {
 372   /* Stack data is always allocated in word-size units. */
 373   ASSERT (is_thread (t));
 374   ASSERT (size % sizeof (uint32_t) == 0);
 375
 376   t->stack -= size;
 377   return t->stack;
 378 }
 379
 380 /* Chooses and returns the next thread to be scheduled.  Should
 381    return a thread from the run queue, unless the run queue is
 382    empty.  (If the running thread can continue running, then it
 383    will be in the run queue.)  If the run queue is empty, return
 384    idle_thread. */
 385 static struct thread *
 386 next_thread_to_run (void)
 387 {
 388   if (list_empty (&ready_list))
 389     return idle_thread;
 390   else
 391     return list_entry (list_pop_front (&ready_list), struct thread, elem);
 392 }
 393
 394 /* Completes a thread switch by activating the new thread's page
 395    tables, and, if the previous thread is dying, destroying it.
 396
 397    At this function's invocation, we just switched from thread
 398    PREV, the new thread is already running, and interrupts are
 399    still disabled.  This function is normally invoked by
 400    thread_schedule() as its final action before returning, but
 401    the first time a thread is scheduled it is called by
 402    switch_entry() (see switch.S).
 403
 404    It's not safe to call printf() until the thread switch is
 405    complete.  In practice that means that printf()s should be
 406    added at the end of the function.
 407
 408    After this function and its caller returns, the thread switch
 409    is complete. */
 410 void
 411 schedule_tail (struct thread *prev)
 412 {
 413   struct thread *cur = running_thread ();
 414
 415   ASSERT (intr_get_level () == INTR_OFF);
 416
 417   /* Mark us as running. */
 418   cur->status = THREAD_RUNNING;
 419
 420 #ifdef USERPROG
 421   /* Activate the new address space. */
 422   process_activate ();
 423 #endif
 424
 425   /* If the thread we switched from is dying, destroy its struct
 426      thread.  This must happen late so that thread_exit() doesn't
 427      pull out the rug under itself. */
 428   if (prev != NULL && prev->status == THREAD_DYING)
 429     {
 430       ASSERT (prev != cur);
 431       if (prev != initial_thread)
 432         palloc_free_page (prev);
 433     }
 434 }
 435
 436 /* Schedules a new process.  At entry, interrupts must be off and
 437    the running process's state must have been changed from
 438    running to some other state.  This function finds another
 439    thread to run and switches to it.
 440
 441    It's not safe to call printf() until schedule_tail() has
 442    completed. */
 443 static void
 444 schedule (void)
 445 {
 446   struct thread *cur = running_thread ();
 447   struct thread *next = next_thread_to_run ();
 448   struct thread *prev = NULL;
 449
 450   ASSERT (intr_get_level () == INTR_OFF);
 451   ASSERT (cur->status != THREAD_RUNNING);
 452   ASSERT (is_thread (next));
 453
 454   if (cur != next)
 455     prev = switch_threads (cur, next);
 456   schedule_tail (prev);
 457 }
 458
 459 /* Returns a tid to use for a new thread. */
 460 static tid_t
 461 allocate_tid (void)
 462 {
 463   static tid_t next_tid = 1;
 464   tid_t tid;
 465
 466   lock_acquire (&tid_lock);
 467   tid = next_tid++;
 468   lock_release (&tid_lock);
 469
 470   return tid;
 471 }
 472 \f
 473 /* Offset of `stack' member within `struct thread'.
 474    Used by switch.S, which can't figure it out on its own. */
 475 uint32_t thread_stack_ofs = offsetof (struct thread, stack);