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 /* Offset of `stack' member within `struct thread'.
  13    Used by switch.S, which can't figure it out on its own. */
  14 uint32_t thread_stack_ofs = offsetof (struct thread, stack);
  15
  16 /* List of processes in THREAD_READY state, that is, processes
  17    that are ready to run but not actually running. */
  18 static struct list run_queue;
  19
  20 /* Thread to run when nothing else is ready. */
  21 static struct thread *idle_thread;
  22
  23 static struct thread *find_next_to_run (void);
  24
  25 /* Idle thread.  Executes when no other thread is ready to run. */
  26 static void
  27 idle (void *aux UNUSED)
  28 {
  29   for (;;)
  30     {
  31       /* Wait for an interrupt. */
  32       DEBUG (idle, "idle");
  33       asm ("hlt");
  34
  35       /* Let someone else run. */
  36       intr_disable ();
  37       thread_sleep ();
  38       intr_enable ();
  39     }
  40 }
  41
  42 /* Initializes the threading system and starts an initial thread
  43    which is immediately scheduled.  Never returns to the caller.
  44    The initial thread is named NAME and executes FUNCTION passing
  45    AUX as the argument. */
  46 void
  47 thread_init (void)
  48 {
  49   ASSERT (intr_get_level () == IF_OFF);
  50
  51   /* Initialize run queue. */
  52   list_init (&run_queue);
  53
  54   /* Create idle thread. */
  55   idle_thread = thread_create ("idle", idle, NULL);
  56   idle_thread->status = THREAD_BLOCKED;
  57 }
  58
  59 void
  60 thread_start (void)
  61 {
  62   struct thread *t = find_next_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 \f
  71 /* Stack frame for kernel_thread(). */
  72 struct kernel_thread_frame
  73   {
  74     void *eip;                  /* Return address. */
  75     void (*function) (void *);  /* Function to call. */
  76     void *aux;                  /* Auxiliary data for function. */
  77   };
  78
  79 /* Function used as the basis for a kernel thread. */
  80 static void
  81 kernel_thread (void (*function) (void *aux), void *aux)
  82 {
  83   ASSERT (function != NULL);
  84
  85   intr_enable ();       /* The scheduler runs with interrupts off. */
  86   function (aux);       /* Execute the thread function. */
  87   thread_exit ();       /* If function() returns, kill the thread. */
  88 }
  89
  90 /* Creates a new thread named NAME and initializes its fields.
  91    Returns the new thread if successful or a null pointer on
  92    failure. */
  93 static struct thread *
  94 new_thread (const char *name)
  95 {
  96   struct thread *t;
  97
  98   ASSERT (name != NULL);
  99
 100   t = palloc_get (PAL_ZERO);
 101   if (t != NULL)
 102     {
 103       strlcpy (t->name, name, sizeof t->name);
 104       t->stack = (uint8_t *) t + PGSIZE;
 105       t->status = THREAD_INITIALIZING;
 106     }
 107
 108   return t;
 109 }
 110
 111 /* Allocates a SIZE-byte frame within thread T's stack and
 112    returns a pointer to the frame's base. */
 113 static void *
 114 alloc_frame (struct thread *t, size_t size)
 115 {
 116   /* Stack data is always allocated in word-size units. */
 117   ASSERT (size % sizeof (uint32_t) == 0);
 118
 119   t->stack -= size;
 120   return t->stack;
 121 }
 122
 123 /* Creates a new kernel thread named NAME, which executes
 124    FUNCTION passing AUX as the argument.  The thread is added to
 125    the ready queue.  Thus, it may be scheduled even before
 126    thread_create() returns.  If you need to ensure ordering, then
 127    use synchronization, such as a semaphore. */
 128 struct thread *
 129 thread_create (const char *name, void (*function) (void *aux), void *aux)
 130 {
 131   struct thread *t;
 132   struct kernel_thread_frame *kf;
 133   struct switch_entry_frame *ef;
 134   struct switch_threads_frame *sf;
 135
 136   ASSERT (function != NULL);
 137
 138   t = new_thread (name);
 139
 140   /* Stack frame for kernel_thread(). */
 141   kf = alloc_frame (t, sizeof *kf);
 142   kf->eip = NULL;
 143   kf->function = function;
 144   kf->aux = aux;
 145
 146   /* Stack frame for switch_entry(). */
 147   ef = alloc_frame (t, sizeof *ef);
 148   ef->eip = (void (*) (void)) kernel_thread;
 149
 150   /* Stack frame for switch_threads(). */
 151   sf = alloc_frame (t, sizeof *sf);
 152   sf->eip = switch_entry;
 153
 154   /* Add to run queue. */
 155   thread_ready (t);
 156
 157   return t;
 158 }
 159
 160 struct thread *
 161 thread_current (void)
 162 {
 163   uint32_t *esp;
 164   asm ("movl %%esp, %0\n" : "=g" (esp));
 165   return pg_round_down (esp);
 166 }
 167
 168 #ifdef USERPROG
 169 bool
 170 thread_execute (const char *filename)
 171 {
 172   struct thread *t;
 173   struct intr_frame *if_;
 174   struct switch_entry_frame *ef;
 175   struct switch_threads_frame *sf;
 176   void (*start) (void);
 177
 178   ASSERT (filename != NULL);
 179
 180   t = new_thread (filename);
 181   if (t == NULL)
 182     return false;
 183
 184   if (!addrspace_load (&t->addrspace, filename, &start))
 185     PANIC ("%s: program load failed", filename);
 186
 187   /* Interrupt frame. */
 188   if_ = alloc_frame (t, sizeof *if_);
 189   if_->es = SEL_UDSEG;
 190   if_->ds = SEL_UDSEG;
 191   if_->eip = start;
 192   if_->cs = SEL_UCSEG;
 193   if_->eflags = FLAG_IF | 2;
 194   if_->esp = PHYS_BASE;
 195   if_->ss = SEL_UDSEG;
 196
 197   /* Stack frame for switch_entry(). */
 198   ef = alloc_frame (t, sizeof *ef);
 199   ef->eip = intr_exit;
 200
 201   /* Stack frame for switch_threads(). */
 202   sf = alloc_frame (t, sizeof *sf);
 203   sf->eip = switch_entry;
 204
 205   /* Add to run queue. */
 206   thread_ready (t);
 207
 208   return true;
 209 }
 210 #endif
 211
 212 void
 213 thread_ready (struct thread *t)
 214 {
 215   if (t->status != THREAD_READY)
 216     {
 217       list_push_back (&run_queue, &t->rq_elem);
 218       t->status = THREAD_READY;
 219     }
 220 }
 221
 222 static struct thread *
 223 find_next_to_run (void)
 224 {
 225   if (list_empty (&run_queue))
 226     return idle_thread;
 227   else
 228     return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
 229 }
 230
 231 void
 232 thread_destroy (struct thread *t)
 233 {
 234   ASSERT (t->status == THREAD_DYING);
 235   ASSERT (t != thread_current ());
 236
 237   palloc_free (t);
 238 }
 239
 240 void schedule_tail (struct thread *prev);
 241
 242 void
 243 schedule_tail (struct thread *prev)
 244 {
 245   ASSERT (intr_get_level () == IF_OFF);
 246
 247 #ifdef USERPROG
 248   addrspace_activate (&thread_current ()->addrspace);
 249 #endif
 250
 251   if (prev != NULL && prev->status == THREAD_DYING)
 252     thread_destroy (prev);
 253 }
 254
 255 static void
 256 thread_schedule (void)
 257 {
 258   struct thread *cur, *next, *prev;
 259
 260   ASSERT (intr_get_level () == IF_OFF);
 261
 262   cur = thread_current ();
 263   ASSERT (cur->status != THREAD_RUNNING);
 264
 265   next = find_next_to_run ();
 266
 267   next->status = THREAD_RUNNING;
 268   if (cur != next)
 269     {
 270       prev = switch_threads (cur, next);
 271
 272       /* Prevent GCC from reordering anything around the thread
 273          switch. */
 274       asm volatile ("" : : : "memory");
 275
 276       schedule_tail (prev);
 277     }
 278 }
 279
 280 void
 281 thread_yield (void)
 282 {
 283   enum if_level old_level;
 284
 285   ASSERT (!intr_context ());
 286
 287   old_level = intr_disable ();
 288   thread_ready (thread_current ());
 289   thread_schedule ();
 290   intr_set_level (old_level);
 291 }
 292
 293 void
 294 thread_exit (void)
 295 {
 296   ASSERT (!intr_context ());
 297
 298   intr_disable ();
 299   thread_current ()->status = THREAD_DYING;
 300   thread_schedule ();
 301   NOT_REACHED ();
 302 }
 303
 304 void
 305 thread_sleep (void)
 306 {
 307   ASSERT (!intr_context ());
 308   ASSERT (intr_get_level () == IF_OFF);
 309
 310   thread_current ()->status = THREAD_BLOCKED;
 311   thread_schedule ();
 312 }