1 #include "threads/thread.h"
7 #include "threads/flags.h"
8 #include "threads/interrupt.h"
9 #include "threads/intr-stubs.h"
10 #include "threads/palloc.h"
11 #include "threads/switch.h"
12 #include "threads/synch.h"
13 #include "threads/vaddr.h"
15 #include "userprog/process.h"
18 /* Random value for struct thread's `magic' member.
19 Used to detect stack overflow. See the big comment at the top
20 of thread.h for details. */
21 #define THREAD_MAGIC 0xcd6abf4b
23 /* List of processes in THREAD_READY state, that is, processes
24 that are ready to run but not actually running. */
25 static struct list ready_list;
27 /* List of all processes. Processes are added to this list
28 when they are first scheduled and removed when they exit. */
29 static struct list all_list;
32 static struct thread *idle_thread;
34 /* Initial thread, the thread running init.c:main(). */
35 static struct thread *initial_thread;
37 /* Lock used by allocate_tid(). */
38 static struct lock tid_lock;
40 /* Stack frame for kernel_thread(). */
41 struct kernel_thread_frame
43 void *eip; /* Return address. */
44 thread_func *function; /* Function to call. */
45 void *aux; /* Auxiliary data for function. */
49 static long long idle_ticks; /* # of timer ticks spent idle. */
50 static long long kernel_ticks; /* # of timer ticks in kernel threads. */
51 static long long user_ticks; /* # of timer ticks in user programs. */
54 #define TIME_SLICE 4 /* # of timer ticks to give each thread. */
55 static unsigned thread_ticks; /* # of timer ticks since last yield. */
57 /* If false (default), use round-robin scheduler.
58 If true, use multi-level feedback queue scheduler.
59 Controlled by kernel command-line option "-o mlfqs". */
62 static void kernel_thread (thread_func *, void *aux);
64 static void idle (void *aux UNUSED);
65 static struct thread *running_thread (void);
66 static struct thread *next_thread_to_run (void);
67 static void init_thread (struct thread *, const char *name, int priority);
68 static bool is_thread (struct thread *) UNUSED;
69 static void *alloc_frame (struct thread *, size_t size);
70 static void schedule (void);
71 void schedule_tail (struct thread *prev);
72 static tid_t allocate_tid (void);
74 /* Initializes the threading system by transforming the code
75 that's currently running into a thread. This can't work in
76 general and it is possible in this case only because loader.S
77 was careful to put the bottom of the stack at a page boundary.
79 Also initializes the run queue and the tid lock.
81 After calling this function, be sure to initialize the page
82 allocator before trying to create any threads with
85 It is not safe to call thread_current() until this function
90 ASSERT (intr_get_level () == INTR_OFF);
92 lock_init (&tid_lock);
93 list_init (&ready_list);
94 list_init (&all_list);
96 /* Set up a thread structure for the running thread. */
97 initial_thread = running_thread ();
98 init_thread (initial_thread, "main", PRI_DEFAULT);
99 initial_thread->status = THREAD_RUNNING;
100 initial_thread->tid = allocate_tid ();
103 /* Starts preemptive thread scheduling by enabling interrupts.
104 Also creates the idle thread. */
108 /* Create the idle thread. */
109 struct semaphore idle_started;
110 sema_init (&idle_started, 0);
111 thread_create ("idle", PRI_MIN, idle, &idle_started);
113 /* Start preemptive thread scheduling. */
116 /* Wait for the idle thread to initialize idle_thread. */
117 sema_down (&idle_started);
120 /* Called by the timer interrupt handler at each timer tick.
121 Thus, this function runs in an external interrupt context. */
125 struct thread *t = thread_current ();
127 /* Update statistics. */
128 if (t == idle_thread)
131 else if (t->pagedir != NULL)
137 /* Enforce preemption. */
138 if (++thread_ticks >= TIME_SLICE)
139 intr_yield_on_return ();
142 /* Prints thread statistics. */
144 thread_print_stats (void)
146 printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
147 idle_ticks, kernel_ticks, user_ticks);
150 /* Creates a new kernel thread named NAME with the given initial
151 PRIORITY, which executes FUNCTION passing AUX as the argument,
152 and adds it to the ready queue. Returns the thread identifier
153 for the new thread, or TID_ERROR if creation fails.
155 If thread_start() has been called, then the new thread may be
156 scheduled before thread_create() returns. It could even exit
157 before thread_create() returns. Contrariwise, the original
158 thread may run for any amount of time before the new thread is
159 scheduled. Use a semaphore or some other form of
160 synchronization if you need to ensure ordering.
162 The code provided sets the new thread's `priority' member to
163 PRIORITY, but no actual priority scheduling is implemented.
164 Priority scheduling is the goal of Problem 1-3. */
166 thread_create (const char *name, int priority,
167 thread_func *function, void *aux)
170 struct kernel_thread_frame *kf;
171 struct switch_entry_frame *ef;
172 struct switch_threads_frame *sf;
174 enum intr_level old_level;
176 ASSERT (function != NULL);
178 /* Allocate thread. */
179 t = palloc_get_page (PAL_ZERO);
183 /* Initialize thread. */
184 init_thread (t, name, priority);
185 tid = t->tid = allocate_tid ();
187 /* Prepare thread for first run by initializing its stack.
188 Do this atomically so intermediate values for the 'stack'
189 member cannot be observed. */
190 old_level = intr_disable ();
192 /* Stack frame for kernel_thread(). */
193 kf = alloc_frame (t, sizeof *kf);
195 kf->function = function;
198 /* Stack frame for switch_entry(). */
199 ef = alloc_frame (t, sizeof *ef);
200 ef->eip = (void (*) (void)) kernel_thread;
202 /* Stack frame for switch_threads(). */
203 sf = alloc_frame (t, sizeof *sf);
204 sf->eip = switch_entry;
207 intr_set_level (old_level);
209 /* Add to run queue. */
215 /* Puts the current thread to sleep. It will not be scheduled
216 again until awoken by thread_unblock().
218 This function must be called with interrupts turned off. It
219 is usually a better idea to use one of the synchronization
220 primitives in synch.h. */
224 ASSERT (!intr_context ());
225 ASSERT (intr_get_level () == INTR_OFF);
227 thread_current ()->status = THREAD_BLOCKED;
231 /* Transitions a blocked thread T to the ready-to-run state.
232 This is an error if T is not blocked. (Use thread_yield() to
233 make the running thread ready.)
235 This function does not preempt the running thread. This can
236 be important: if the caller had disabled interrupts itself,
237 it may expect that it can atomically unblock a thread and
238 update other data. */
240 thread_unblock (struct thread *t)
242 enum intr_level old_level;
244 ASSERT (is_thread (t));
246 old_level = intr_disable ();
247 ASSERT (t->status == THREAD_BLOCKED);
248 list_push_back (&ready_list, &t->elem);
249 t->status = THREAD_READY;
250 intr_set_level (old_level);
253 /* Returns the name of the running thread. */
257 return thread_current ()->name;
260 /* Returns the running thread.
261 This is running_thread() plus a couple of sanity checks.
262 See the big comment at the top of thread.h for details. */
264 thread_current (void)
266 struct thread *t = running_thread ();
268 /* Make sure T is really a thread.
269 If either of these assertions fire, then your thread may
270 have overflowed its stack. Each thread has less than 4 kB
271 of stack, so a few big automatic arrays or moderate
272 recursion can cause stack overflow. */
273 ASSERT (is_thread (t));
274 ASSERT (t->status == THREAD_RUNNING);
279 /* Returns the running thread's tid. */
283 return thread_current ()->tid;
286 /* Deschedules the current thread and destroys it. Never
287 returns to the caller. */
291 ASSERT (!intr_context ());
297 /* Remove thread from all threads list, set our status to dying,
298 and schedule another process. That process will destroy us
299 when it call schedule_tail(). */
301 list_remove (&thread_current()->allelem);
302 thread_current ()->status = THREAD_DYING;
307 /* Yields the CPU. The current thread is not put to sleep and
308 may be scheduled again immediately at the scheduler's whim. */
312 struct thread *cur = thread_current ();
313 enum intr_level old_level;
315 ASSERT (!intr_context ());
317 old_level = intr_disable ();
318 if (cur != idle_thread)
319 list_push_back (&ready_list, &cur->elem);
320 cur->status = THREAD_READY;
322 intr_set_level (old_level);
325 /* Invoke function 'func' on all threads, passing along 'aux'.
326 This function must be called with interrupts off. */
328 thread_foreach (thread_action_func *func, void *aux)
332 ASSERT (intr_get_level () == INTR_OFF);
334 for (e = list_begin (&all_list); e != list_end (&all_list);
337 struct thread *t = list_entry (e, struct thread, allelem);
342 /* Sets the current thread's priority to NEW_PRIORITY. */
344 thread_set_priority (int new_priority)
346 thread_current ()->priority = new_priority;
349 /* Returns the current thread's priority. */
351 thread_get_priority (void)
353 return thread_current ()->priority;
356 /* Sets the current thread's nice value to NICE. */
358 thread_set_nice (int nice UNUSED)
360 /* Not yet implemented. */
363 /* Returns the current thread's nice value. */
365 thread_get_nice (void)
367 /* Not yet implemented. */
371 /* Returns 100 times the system load average. */
373 thread_get_load_avg (void)
375 /* Not yet implemented. */
379 /* Returns 100 times the current thread's recent_cpu value. */
381 thread_get_recent_cpu (void)
383 /* Not yet implemented. */
387 /* Idle thread. Executes when no other thread is ready to run.
389 The idle thread is initially put on the ready list by
390 thread_start(). It will be scheduled once initially, at which
391 point it initializes idle_thread, "up"s the semaphore passed
392 to it to enable thread_start() to continue, and immediately
393 blocks. After that, the idle thread never appears in the
394 ready list. It is returned by next_thread_to_run() as a
395 special case when the ready list is empty. */
397 idle (void *idle_started_ UNUSED)
399 struct semaphore *idle_started = idle_started_;
400 idle_thread = thread_current ();
401 sema_up (idle_started);
405 /* Let someone else run. */
409 /* Re-enable interrupts and wait for the next one.
411 The `sti' instruction disables interrupts until the
412 completion of the next instruction, so these two
413 instructions are executed atomically. This atomicity is
414 important; otherwise, an interrupt could be handled
415 between re-enabling interrupts and waiting for the next
416 one to occur, wasting as much as one clock tick worth of
419 See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a]
420 7.11.1 "HLT Instruction". */
421 asm volatile ("sti; hlt" : : : "memory");
425 /* Function used as the basis for a kernel thread. */
427 kernel_thread (thread_func *function, void *aux)
429 ASSERT (function != NULL);
431 intr_enable (); /* The scheduler runs with interrupts off. */
432 function (aux); /* Execute the thread function. */
433 thread_exit (); /* If function() returns, kill the thread. */
436 /* Returns the running thread. */
438 running_thread (void)
442 /* Copy the CPU's stack pointer into `esp', and then round that
443 down to the start of a page. Because `struct thread' is
444 always at the beginning of a page and the stack pointer is
445 somewhere in the middle, this locates the curent thread. */
446 asm ("mov %%esp, %0" : "=g" (esp));
447 return pg_round_down (esp);
450 /* Returns true if T appears to point to a valid thread. */
452 is_thread (struct thread *t)
454 return t != NULL && t->magic == THREAD_MAGIC;
457 /* Does basic initialization of T as a blocked thread named
460 init_thread (struct thread *t, const char *name, int priority)
463 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
464 ASSERT (name != NULL);
466 memset (t, 0, sizeof *t);
467 t->status = THREAD_BLOCKED;
468 strlcpy (t->name, name, sizeof t->name);
469 t->stack = (uint8_t *) t + PGSIZE;
470 t->priority = priority;
471 t->magic = THREAD_MAGIC;
472 list_push_back (&all_list, &t->allelem);
475 /* Allocates a SIZE-byte frame at the top of thread T's stack and
476 returns a pointer to the frame's base. */
478 alloc_frame (struct thread *t, size_t size)
480 /* Stack data is always allocated in word-size units. */
481 ASSERT (is_thread (t));
482 ASSERT (size % sizeof (uint32_t) == 0);
488 /* Chooses and returns the next thread to be scheduled. Should
489 return a thread from the run queue, unless the run queue is
490 empty. (If the running thread can continue running, then it
491 will be in the run queue.) If the run queue is empty, return
493 static struct thread *
494 next_thread_to_run (void)
496 if (list_empty (&ready_list))
499 return list_entry (list_pop_front (&ready_list), struct thread, elem);
502 /* Completes a thread switch by activating the new thread's page
503 tables, and, if the previous thread is dying, destroying it.
505 At this function's invocation, we just switched from thread
506 PREV, the new thread is already running, and interrupts are
507 still disabled. This function is normally invoked by
508 thread_schedule() as its final action before returning, but
509 the first time a thread is scheduled it is called by
510 switch_entry() (see switch.S).
512 It's not safe to call printf() until the thread switch is
513 complete. In practice that means that printf()s should be
514 added at the end of the function.
516 After this function and its caller returns, the thread switch
519 schedule_tail (struct thread *prev)
521 struct thread *cur = running_thread ();
523 ASSERT (intr_get_level () == INTR_OFF);
525 /* Mark us as running. */
526 cur->status = THREAD_RUNNING;
528 /* Start new time slice. */
532 /* Activate the new address space. */
536 /* If the thread we switched from is dying, destroy its struct
537 thread. This must happen late so that thread_exit() doesn't
538 pull out the rug under itself. (We don't free
539 initial_thread because its memory was not obtained via
541 if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread)
543 ASSERT (prev != cur);
544 palloc_free_page (prev);
548 /* Schedules a new process. At entry, interrupts must be off and
549 the running process's state must have been changed from
550 running to some other state. This function finds another
551 thread to run and switches to it.
553 It's not safe to call printf() until schedule_tail() has
558 struct thread *cur = running_thread ();
559 struct thread *next = next_thread_to_run ();
560 struct thread *prev = NULL;
562 ASSERT (intr_get_level () == INTR_OFF);
563 ASSERT (cur->status != THREAD_RUNNING);
564 ASSERT (is_thread (next));
567 prev = switch_threads (cur, next);
568 schedule_tail (prev);
571 /* Returns a tid to use for a new thread. */
575 static tid_t next_tid = 1;
578 lock_acquire (&tid_lock);
580 lock_release (&tid_lock);
585 /* Offset of `stack' member within `struct thread'.
586 Used by switch.S, which can't figure it out on its own. */
587 uint32_t thread_stack_ofs = offsetof (struct thread, stack);