pintos-os.org Git - pintos-anon/blob - src/threads/thread.c

   1 #include "thread.h"
   2 #include <stddef.h>
   3 #include "debug.h"
   4 #include "interrupt.h"
   5 #include "intr-stubs.h"
   6 #include "lib.h"
   7 #include "mmu.h"
   8 #include "palloc.h"
   9 #include "random.h"
  10 #include "switch.h"
  11
  12 #define THREAD_MAGIC 0x1234abcdu
  13
  14 /* List of processes in THREAD_READY state, that is, processes
  15    that are ready to run but not actually running. */
  16 static struct list run_queue;
  17
  18 /* Idle thread. */
  19 static struct thread *idle_thread;      /* Thread. */
  20 static void idle (void *aux UNUSED);    /* Thread function. */
  21
  22 /* Stack frame for kernel_thread(). */
  23 struct kernel_thread_frame
  24   {
  25     void *eip;                  /* Return address. */
  26     void (*function) (void *);  /* Function to call. */
  27     void *aux;                  /* Auxiliary data for function. */
  28   };
  29
  30 static void kernel_thread (void (*function) (void *aux), void *aux);
  31
  32 static struct thread *next_thread_to_run (void);
  33 static struct thread *new_thread (const char *name);
  34 static bool is_thread (struct thread *t);
  35 static void *alloc_frame (struct thread *t, size_t size);
  36 static void destroy_thread (struct thread *t);
  37 static void schedule (void);
  38 void schedule_tail (struct thread *prev);
  39
  40 /* Initializes the threading system.  After calling, create some
  41    threads with thread_create() or thread_execute(), then start
  42    the scheduler with thread_start(). */
  43 void
  44 thread_init (void)
  45 {
  46   ASSERT (intr_get_level () == INTR_OFF);
  47
  48   /* Initialize run queue. */
  49   list_init (&run_queue);
  50
  51   /* Create idle thread. */
  52   idle_thread = thread_create ("idle", idle, NULL);
  53   idle_thread->status = THREAD_BLOCKED;
  54 }
  55
  56 /* Starts the thread scheduler.  The caller should have created
  57    some threads with thread_create() or thread_execute().  Never
  58    returns to the caller. */
  59 void
  60 thread_start (void)
  61 {
  62   struct thread *t = next_thread_to_run ();
  63   if (t->status == THREAD_READY)
  64     list_remove (&t->rq_elem);
  65   t->status = THREAD_RUNNING;
  66   switch_threads (NULL, t);
  67
  68   NOT_REACHED ();
  69 }
  70
  71 /* Creates a new kernel thread named NAME, which executes
  72    FUNCTION passing AUX as the argument, and adds it to the ready
  73    queue.  If thread_start() has been called, then the new thread
  74    may be scheduled before thread_create() returns.  Use a
  75    semaphore or some other form of synchronization if you need to
  76    ensure ordering. */
  77 struct thread *
  78 thread_create (const char *name, void (*function) (void *aux), void *aux)
  79 {
  80   struct thread *t;
  81   struct kernel_thread_frame *kf;
  82   struct switch_entry_frame *ef;
  83   struct switch_threads_frame *sf;
  84
  85   ASSERT (function != NULL);
  86
  87   t = new_thread (name);
  88
  89   /* Stack frame for kernel_thread(). */
  90   kf = alloc_frame (t, sizeof *kf);
  91   kf->eip = NULL;
  92   kf->function = function;
  93   kf->aux = aux;
  94
  95   /* Stack frame for switch_entry(). */
  96   ef = alloc_frame (t, sizeof *ef);
  97   ef->eip = (void (*) (void)) kernel_thread;
  98
  99   /* Stack frame for switch_threads(). */
 100   sf = alloc_frame (t, sizeof *sf);
 101   sf->eip = switch_entry;
 102
 103   /* Add to run queue. */
 104   thread_wake (t);
 105
 106   return t;
 107 }
 108
 109 #ifdef USERPROG
 110 /* Starts a new thread running a user program loaded from
 111    FILENAME, and adds it to the ready queue.  If thread_start()
 112    has been called, then new thread may be scheduled before
 113    thread_execute() returns.*/
 114 bool
 115 thread_execute (const char *filename)
 116 {
 117   struct thread *t;
 118   struct intr_frame *if_;
 119   struct switch_entry_frame *ef;
 120   struct switch_threads_frame *sf;
 121   void (*start) (void);
 122
 123   ASSERT (filename != NULL);
 124
 125   t = new_thread (filename);
 126   if (t == NULL)
 127     return false;
 128
 129   if (!addrspace_load (t, filename, &start))
 130     PANIC ("%s: program load failed", filename);
 131
 132   /* Interrupt frame. */
 133   if_ = alloc_frame (t, sizeof *if_);
 134   if_->es = SEL_UDSEG;
 135   if_->ds = SEL_UDSEG;
 136   if_->eip = start;
 137   if_->cs = SEL_UCSEG;
 138   if_->eflags = FLAG_IF | 2;
 139   if_->esp = PHYS_BASE;
 140   if_->ss = SEL_UDSEG;
 141
 142   /* Stack frame for switch_entry(). */
 143   ef = alloc_frame (t, sizeof *ef);
 144   ef->eip = intr_exit;
 145
 146   /* Stack frame for switch_threads(). */
 147   sf = alloc_frame (t, sizeof *sf);
 148   sf->eip = switch_entry;
 149
 150   /* Add to run queue. */
 151   thread_wake (t);
 152
 153   return true;
 154 }
 155 #endif
 156
 157 /* Transitions T from its current state to THREAD_READY, the
 158    ready-to-run state.  On entry, T must be ready or blocked.
 159    (Use thread_yield() to make the running thread ready.) */
 160 void
 161 thread_wake (struct thread *t)
 162 {
 163   ASSERT (is_thread (t));
 164   ASSERT (t->status == THREAD_READY || t->status == THREAD_BLOCKED);
 165   if (t->status != THREAD_READY)
 166     {
 167       list_push_back (&run_queue, &t->rq_elem);
 168       t->status = THREAD_READY;
 169     }
 170 }
 171
 172 /* Returns the name of thread T. */
 173 const char *
 174 thread_name (struct thread *t)
 175 {
 176   ASSERT (is_thread (t));
 177   return t->name;
 178 }
 179
 180 /* Returns the running thread. */
 181 struct thread *
 182 thread_current (void)
 183 {
 184   uint32_t *esp;
 185   struct thread *t;
 186
 187   /* Copy the CPU's stack pointer into `esp', and then round that
 188      down to the start of a page.  Because `struct thread' is
 189      always at the beginning of a page and the stack pointer is
 190      somewhere in the middle, this locates the curent thread. */
 191   asm ("movl %%esp, %0\n" : "=g" (esp));
 192   t = pg_round_down (esp);
 193
 194   /* Make sure T is really a thread.
 195      If this assertion fires, then your thread may have
 196      overflowed its stack.  Each thread has less than 4 kB of
 197      stack, so a few big automatic arrays or moderate recursion
 198      can cause stack overflow. */
 199   ASSERT (is_thread (t));
 200
 201   return t;
 202 }
 203
 204 /* Deschedules the current thread and destroys it.  Never
 205    returns to the caller. */
 206 void
 207 thread_exit (void)
 208 {
 209   ASSERT (!intr_context ());
 210
 211   intr_disable ();
 212   thread_current ()->status = THREAD_DYING;
 213   schedule ();
 214   NOT_REACHED ();
 215 }
 216
 217 /* Yields the CPU.  The current thread is not put to sleep and
 218    may be scheduled again immediately at the scheduler's whim. */
 219 void
 220 thread_yield (void)
 221 {
 222   struct thread *cur = thread_current ();
 223   enum intr_level old_level;
 224
 225   ASSERT (!intr_context ());
 226
 227   old_level = intr_disable ();
 228   list_push_back (&run_queue, &cur->rq_elem);
 229   cur->status = THREAD_READY;
 230   schedule ();
 231   intr_set_level (old_level);
 232 }
 233
 234 /* Puts the current thread to sleep.  It will not be scheduled
 235    again until awoken by thread_wake(). */
 236 void
 237 thread_sleep (void)
 238 {
 239   ASSERT (!intr_context ());
 240   ASSERT (intr_get_level () == INTR_OFF);
 241
 242   thread_current ()->status = THREAD_BLOCKED;
 243   schedule ();
 244 }
 245 \f
 246 /* Idle thread.  Executes when no other thread is ready to run. */
 247 static void
 248 idle (void *aux UNUSED)
 249 {
 250   for (;;)
 251     {
 252       /* Wait for an interrupt. */
 253       DEBUG (idle, "idle");
 254       asm ("hlt");
 255
 256       /* Let someone else run. */
 257       intr_disable ();
 258       thread_sleep ();
 259       intr_enable ();
 260     }
 261 }
 262
 263 /* Function used as the basis for a kernel thread. */
 264 static void
 265 kernel_thread (void (*function) (void *aux), void *aux)
 266 {
 267   ASSERT (function != NULL);
 268
 269   intr_enable ();       /* The scheduler runs with interrupts off. */
 270   function (aux);       /* Execute the thread function. */
 271   thread_exit ();       /* If function() returns, kill the thread. */
 272 }
 273 \f
 274 /* Returns true if T appears to point to a valid thread. */
 275 static bool
 276 is_thread (struct thread *t)
 277 {
 278   return t != NULL && t->magic == THREAD_MAGIC;
 279 }
 280
 281 /* Creates a new thread named NAME and initializes its fields.
 282    Returns the new thread if successful or a null pointer on
 283    failure. */
 284 static struct thread *
 285 new_thread (const char *name)
 286 {
 287   struct thread *t;
 288
 289   ASSERT (name != NULL);
 290
 291   t = palloc_get (PAL_ZERO);
 292   if (t != NULL)
 293     {
 294       strlcpy (t->name, name, sizeof t->name);
 295       t->stack = (uint8_t *) t + PGSIZE;
 296       t->status = THREAD_BLOCKED;
 297       t->magic = THREAD_MAGIC;
 298     }
 299
 300   return t;
 301 }
 302
 303 /* Allocates a SIZE-byte frame at the top of thread T's stack and
 304    returns a pointer to the frame's base. */
 305 static void *
 306 alloc_frame (struct thread *t, size_t size)
 307 {
 308   /* Stack data is always allocated in word-size units. */
 309   ASSERT (is_thread (t));
 310   ASSERT (size % sizeof (uint32_t) == 0);
 311
 312   t->stack -= size;
 313   return t->stack;
 314 }
 315
 316 /* Chooses and returns the next thread to be scheduled.  Should
 317    return a thread from the run queue, unless the run queue is
 318    empty.  (If the running thread can continue running, then it
 319    will be in the run queue.)  If the run queue is empty, return
 320    idle_thread. */
 321 static struct thread *
 322 next_thread_to_run (void)
 323 {
 324   if (list_empty (&run_queue))
 325     return idle_thread;
 326   else
 327     return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
 328 }
 329
 330 /* Destroys T, which must be in the dying state and must not be
 331    the running thread. */
 332 static void
 333 destroy_thread (struct thread *t)
 334 {
 335   ASSERT (is_thread (t));
 336   ASSERT (t->status == THREAD_DYING);
 337   ASSERT (t != thread_current ());
 338
 339   addrspace_destroy (t);
 340   palloc_free (t);
 341 }
 342
 343 /* Completes a thread switch by activating the new thread's page
 344    tables, and, if the previous thread is dying, destroying it.
 345
 346    At this function's invocation, we just switched from thread
 347    PREV, the new thread is already running, and interrupts are
 348    still disabled.  This function is normally invoked by
 349    thread_schedule() as its final action before returning, but
 350    the first time a thread is scheduled it is called by
 351    switch_entry() (see switch.S).
 352
 353    After this function and its caller returns, the thread switch
 354    is complete. */
 355 void
 356 schedule_tail (struct thread *prev)
 357 {
 358   struct thread *cur = thread_current ();
 359
 360   ASSERT (intr_get_level () == INTR_OFF);
 361
 362   cur->status = THREAD_RUNNING;
 363   if (prev != NULL && prev->status == THREAD_DYING)
 364     destroy_thread (prev);
 365
 366 #ifdef USERPROG
 367   addrspace_activate (cur);
 368 #endif
 369 }
 370
 371 /* Schedules a new process.  At entry, interrupts must be off and
 372    the running process's state must have been changed from
 373    running to some other state.  This function finds another
 374    thread to run and switches to it. */
 375 static void
 376 schedule (void)
 377 {
 378   struct thread *cur = thread_current ();
 379   struct thread *next = next_thread_to_run ();
 380
 381   ASSERT (intr_get_level () == INTR_OFF);
 382   ASSERT (cur->status != THREAD_RUNNING);
 383   ASSERT (is_thread (next));
 384
 385   if (cur != next)
 386     {
 387       struct thread *prev = switch_threads (cur, next);
 388       schedule_tail (prev);
 389     }
 390 }
 391 \f
 392 /* Offset of `stack' member within `struct thread'.
 393    Used by switch.S, which can't figure it out on its own. */
 394 uint32_t thread_stack_ofs = offsetof (struct thread, stack);