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