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