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