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