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 uint32_t thread_stack_ofs = offsetof (struct thread, stack);
  13
  14 static struct list run_queue;
  15 static struct thread *idle_thread;
  16
  17 static void
  18 idle (void *aux UNUSED)
  19 {
  20   for (;;)
  21     {
  22       /* Wait for an interrupt. */
  23       asm ("hlt");
  24
  25       /* Let someone else run. */
  26       intr_disable ();
  27       thread_sleep ();
  28       intr_enable ();
  29     }
  30 }
  31
  32 void
  33 thread_init (void)
  34 {
  35   list_init (&run_queue);
  36   idle_thread = thread_create ("idle", idle, NULL);
  37 }
  38
  39 struct thread_root_frame
  40   {
  41     void *eip;                  /* Return address. */
  42     void (*function) (void *);  /* Function to call. */
  43     void *aux;                  /* Auxiliary data for function. */
  44   };
  45
  46 static void
  47 thread_root (void (*function) (void *aux), void *aux)
  48 {
  49   ASSERT (function != NULL);
  50
  51   intr_enable ();
  52   function (aux);
  53   thread_exit ();
  54 }
  55
  56 static struct thread *
  57 new_thread (const char *name)
  58 {
  59   struct thread *t;
  60
  61   ASSERT (name != NULL);
  62
  63   t = palloc_get (PAL_ZERO);
  64   if (t != NULL)
  65     {
  66       strlcpy (t->name, name, sizeof t->name);
  67       t->stack = (uint8_t *) t + PGSIZE;
  68       t->status = THREAD_BLOCKED;
  69     }
  70
  71   return t;
  72 }
  73
  74 static void *
  75 alloc_frame (struct thread *t, size_t size)
  76 {
  77   ASSERT (size % sizeof (uint32_t) == 0);
  78
  79   t->stack -= size;
  80   return t->stack;
  81 }
  82
  83 struct thread *
  84 thread_create (const char *name, void (*function) (void *aux), void *aux)
  85 {
  86   struct thread *t;
  87   struct thread_root_frame *rf;
  88   struct switch_entry_frame *ef;
  89   struct switch_threads_frame *sf;
  90
  91   ASSERT (function != NULL);
  92
  93   t = new_thread (name);
  94
  95   /* Stack frame for thread_root(). */
  96   rf = alloc_frame (t, sizeof *rf);
  97   rf->eip = NULL;
  98   rf->function = function;
  99   rf->aux = aux;
 100
 101   /* Stack frame for switch_entry(). */
 102   ef = alloc_frame (t, sizeof *ef);
 103   ef->eip = (void (*) (void)) thread_root;
 104
 105   /* Stack frame for thread_switch(). */
 106   sf = alloc_frame (t, sizeof *sf);
 107   sf->eip = switch_entry;
 108
 109   /* Add to run queue. */
 110   thread_ready (t);
 111
 112   return t;
 113 }
 114
 115 struct thread *
 116 thread_current (void)
 117 {
 118   uint32_t *esp;
 119   asm ("movl %%esp, %0\n" : "=g" (esp));
 120   return pg_round_down (esp);
 121 }
 122
 123 #ifdef USERPROG
 124 bool
 125 thread_execute (const char *filename)
 126 {
 127   struct thread *t;
 128   struct intr_frame *if_;
 129   struct switch_entry_frame *ef;
 130   struct switch_threads_frame *sf;
 131   void (*start) (void);
 132
 133   ASSERT (filename != NULL);
 134
 135   t = new_thread (filename);
 136   if (t == NULL)
 137     return false;
 138
 139   if (!addrspace_load (&t->addrspace, filename, &start))
 140     panic ("%s: program load failed", filename);
 141
 142   /* Interrupt frame. */
 143   if_ = alloc_frame (t, sizeof *if_);
 144   if_->es = SEL_UDSEG;
 145   if_->ds = SEL_UDSEG;
 146   if_->eip = start;
 147   if_->cs = SEL_UCSEG;
 148   if_->eflags = FLAG_IF | 2;
 149   if_->esp = PHYS_BASE;
 150   if_->ss = SEL_UDSEG;
 151
 152   /* Stack frame for switch_entry(). */
 153   ef = alloc_frame (t, sizeof *ef);
 154   ef->eip = intr_exit;
 155
 156   /* Stack frame for thread_switch(). */
 157   sf = alloc_frame (t, sizeof *sf);
 158   sf->eip = switch_entry;
 159
 160   /* Add to run queue. */
 161   thread_ready (t);
 162
 163   return true;
 164 }
 165 #endif
 166
 167 void
 168 thread_ready (struct thread *t)
 169 {
 170   if (t->status != THREAD_READY)
 171     {
 172       list_push_back (&run_queue, &t->rq_elem);
 173       t->status = THREAD_READY;
 174     }
 175 }
 176
 177 static struct thread *
 178 find_next_to_run (void)
 179 {
 180   if (list_empty (&run_queue))
 181     return NULL;
 182   else
 183     return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
 184 }
 185
 186 void
 187 thread_destroy (struct thread *t)
 188 {
 189   ASSERT (t->status == THREAD_DYING);
 190   ASSERT (t != thread_current ());
 191
 192   palloc_free (t);
 193 }
 194
 195 void schedule_tail (struct thread *prev);
 196
 197 void
 198 schedule_tail (struct thread *prev)
 199 {
 200   struct thread *cur = thread_current ();
 201
 202   ASSERT (intr_get_level () == IF_OFF);
 203
 204 #ifdef USERPROG
 205   addrspace_activate (&cur->addrspace);
 206 #endif
 207
 208   if (prev != NULL && prev->status == THREAD_DYING)
 209     thread_destroy (prev);
 210 }
 211
 212 static void
 213 thread_schedule (void)
 214 {
 215   struct thread *cur, *next, *prev;
 216
 217   ASSERT (intr_get_level () == IF_OFF);
 218
 219   cur = thread_current ();
 220   ASSERT (cur->status != THREAD_RUNNING);
 221
 222   next = find_next_to_run ();
 223   if (next == NULL)
 224     next = idle_thread;
 225
 226   next->status = THREAD_RUNNING;
 227   if (cur != next)
 228     {
 229       prev = switch_threads (cur, next);
 230
 231       /* Prevent GCC from reordering anything around the thread
 232          switch. */
 233       asm volatile ("" : : : "memory");
 234
 235       schedule_tail (prev);
 236     }
 237 }
 238
 239 void
 240 thread_yield (void)
 241 {
 242   enum if_level old_level;
 243
 244   ASSERT (!intr_context ());
 245
 246   old_level = intr_disable ();
 247   thread_ready (thread_current ());
 248   thread_schedule ();
 249   intr_set_level (old_level);
 250 }
 251
 252 void
 253 thread_start (struct thread *t)
 254 {
 255   ASSERT (intr_get_level () == IF_OFF);
 256
 257   if (t->status == THREAD_READY)
 258     list_remove (&t->rq_elem);
 259   t->status = THREAD_RUNNING;
 260   switch_threads (NULL, t);
 261   NOT_REACHED ();
 262 }
 263
 264 void
 265 thread_exit (void)
 266 {
 267   ASSERT (!intr_context ());
 268
 269   intr_disable ();
 270   thread_current ()->status = THREAD_DYING;
 271   thread_schedule ();
 272   NOT_REACHED ();
 273 }
 274
 275 void
 276 thread_sleep (void)
 277 {
 278   ASSERT (!intr_context ());
 279   ASSERT (intr_get_level () == IF_OFF);
 280
 281   thread_current ()->status = THREAD_BLOCKED;
 282   thread_schedule ();
 283 }
 284
 285 static void
 286 tfunc (void *aux UNUSED)
 287 {
 288   for (;;)
 289     {
 290       size_t count, i;
 291       if (random_ulong () % 5 == 0)
 292         {
 293           printk ("%s exiting\n", thread_current ()->name);
 294           break;
 295         }
 296       count = random_ulong () % 25 * 10000;
 297       printk ("%s waiting %zu: ", thread_current ()->name, count);
 298       for (i = 0; i < count; i++);
 299       printk ("%s\n", thread_current ()->name);
 300     }
 301 }
 302
 303 void
 304 thread_self_test (void)
 305 {
 306   struct thread *t;
 307   int i;
 308
 309   for (i = 0; i < 4; i++)
 310     {
 311       char name[2];
 312       name[0] = 'a' + i;
 313       name[1] = 0;
 314       t = thread_create (name, tfunc, NULL);
 315     }
 316   thread_start (t);
 317 }