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 thread_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;
175 ASSERT (function != NULL);
177 /* Allocate thread. */
178 t = palloc_get_page (PAL_ZERO);
182 /* Initialize thread. */
183 init_thread (t, name, priority);
184 tid = t->tid = allocate_tid ();
186 /* Stack frame for kernel_thread(). */
187 kf = alloc_frame (t, sizeof *kf);
189 kf->function = function;
192 /* Stack frame for switch_entry(). */
193 ef = alloc_frame (t, sizeof *ef);
194 ef->eip = (void (*) (void)) kernel_thread;
196 /* Stack frame for switch_threads(). */
197 sf = alloc_frame (t, sizeof *sf);
198 sf->eip = switch_entry;
201 /* Add to run queue. */
207 /* Puts the current thread to sleep. It will not be scheduled
208 again until awoken by thread_unblock().
210 This function must be called with interrupts turned off. It
211 is usually a better idea to use one of the synchronization
212 primitives in synch.h. */
216 ASSERT (!intr_context ());
217 ASSERT (intr_get_level () == INTR_OFF);
219 thread_current ()->status = THREAD_BLOCKED;
223 /* Transitions a blocked thread T to the ready-to-run state.
224 This is an error if T is not blocked. (Use thread_yield() to
225 make the running thread ready.)
227 This function does not preempt the running thread. This can
228 be important: if the caller had disabled interrupts itself,
229 it may expect that it can atomically unblock a thread and
230 update other data. */
232 thread_unblock (struct thread *t)
234 enum intr_level old_level;
236 ASSERT (is_thread (t));
238 old_level = intr_disable ();
239 ASSERT (t->status == THREAD_BLOCKED);
240 list_push_back (&ready_list, &t->elem);
241 t->status = THREAD_READY;
242 intr_set_level (old_level);
245 /* Returns the name of the running thread. */
249 return thread_current ()->name;
252 /* Returns the running thread.
253 This is running_thread() plus a couple of sanity checks.
254 See the big comment at the top of thread.h for details. */
256 thread_current (void)
258 struct thread *t = running_thread ();
260 /* Make sure T is really a thread.
261 If either of these assertions fire, then your thread may
262 have overflowed its stack. Each thread has less than 4 kB
263 of stack, so a few big automatic arrays or moderate
264 recursion can cause stack overflow. */
265 ASSERT (is_thread (t));
266 ASSERT (t->status == THREAD_RUNNING);
271 /* Returns the running thread's tid. */
275 return thread_current ()->tid;
278 /* Deschedules the current thread and destroys it. Never
279 returns to the caller. */
283 ASSERT (!intr_context ());
289 /* Remove thread from all threads list, set our status to dying,
290 and schedule another process. That process will destroy us
291 when it calls thread_schedule_tail(). */
293 list_remove (&thread_current()->allelem);
294 thread_current ()->status = THREAD_DYING;
299 /* Yields the CPU. The current thread is not put to sleep and
300 may be scheduled again immediately at the scheduler's whim. */
304 struct thread *cur = thread_current ();
305 enum intr_level old_level;
307 ASSERT (!intr_context ());
309 old_level = intr_disable ();
310 if (cur != idle_thread)
311 list_push_back (&ready_list, &cur->elem);
312 cur->status = THREAD_READY;
314 intr_set_level (old_level);
317 /* Invoke function 'func' on all threads, passing along 'aux'.
318 This function must be called with interrupts off. */
320 thread_foreach (thread_action_func *func, void *aux)
324 ASSERT (intr_get_level () == INTR_OFF);
326 for (e = list_begin (&all_list); e != list_end (&all_list);
329 struct thread *t = list_entry (e, struct thread, allelem);
334 /* Sets the current thread's priority to NEW_PRIORITY. */
336 thread_set_priority (int new_priority)
338 thread_current ()->priority = new_priority;
341 /* Returns the current thread's priority. */
343 thread_get_priority (void)
345 return thread_current ()->priority;
348 /* Sets the current thread's nice value to NICE. */
350 thread_set_nice (int nice UNUSED)
352 /* Not yet implemented. */
355 /* Returns the current thread's nice value. */
357 thread_get_nice (void)
359 /* Not yet implemented. */
363 /* Returns 100 times the system load average. */
365 thread_get_load_avg (void)
367 /* Not yet implemented. */
371 /* Returns 100 times the current thread's recent_cpu value. */
373 thread_get_recent_cpu (void)
375 /* Not yet implemented. */
379 /* Idle thread. Executes when no other thread is ready to run.
381 The idle thread is initially put on the ready list by
382 thread_start(). It will be scheduled once initially, at which
383 point it initializes idle_thread, "up"s the semaphore passed
384 to it to enable thread_start() to continue, and immediately
385 blocks. After that, the idle thread never appears in the
386 ready list. It is returned by next_thread_to_run() as a
387 special case when the ready list is empty. */
389 idle (void *idle_started_ UNUSED)
391 struct semaphore *idle_started = idle_started_;
392 idle_thread = thread_current ();
393 sema_up (idle_started);
397 /* Let someone else run. */
401 /* Re-enable interrupts and wait for the next one.
403 The `sti' instruction disables interrupts until the
404 completion of the next instruction, so these two
405 instructions are executed atomically. This atomicity is
406 important; otherwise, an interrupt could be handled
407 between re-enabling interrupts and waiting for the next
408 one to occur, wasting as much as one clock tick worth of
411 See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a]
412 7.11.1 "HLT Instruction". */
413 asm volatile ("sti; hlt" : : : "memory");
417 /* Function used as the basis for a kernel thread. */
419 kernel_thread (thread_func *function, void *aux)
421 ASSERT (function != NULL);
423 intr_enable (); /* The scheduler runs with interrupts off. */
424 function (aux); /* Execute the thread function. */
425 thread_exit (); /* If function() returns, kill the thread. */
428 /* Returns the running thread. */
430 running_thread (void)
434 /* Copy the CPU's stack pointer into `esp', and then round that
435 down to the start of a page. Because `struct thread' is
436 always at the beginning of a page and the stack pointer is
437 somewhere in the middle, this locates the curent thread. */
438 asm ("mov %%esp, %0" : "=g" (esp));
439 return pg_round_down (esp);
442 /* Returns true if T appears to point to a valid thread. */
444 is_thread (struct thread *t)
446 return t != NULL && t->magic == THREAD_MAGIC;
449 /* Does basic initialization of T as a blocked thread named
452 init_thread (struct thread *t, const char *name, int priority)
454 enum intr_level old_level;
457 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
458 ASSERT (name != NULL);
460 memset (t, 0, sizeof *t);
461 t->status = THREAD_BLOCKED;
462 strlcpy (t->name, name, sizeof t->name);
463 t->stack = (uint8_t *) t + PGSIZE;
464 t->priority = priority;
465 t->magic = THREAD_MAGIC;
467 old_level = intr_disable ();
468 list_push_back (&all_list, &t->allelem);
469 intr_set_level (old_level);
472 /* Allocates a SIZE-byte frame at the top of thread T's stack and
473 returns a pointer to the frame's base. */
475 alloc_frame (struct thread *t, size_t size)
477 /* Stack data is always allocated in word-size units. */
478 ASSERT (is_thread (t));
479 ASSERT (size % sizeof (uint32_t) == 0);
485 /* Chooses and returns the next thread to be scheduled. Should
486 return a thread from the run queue, unless the run queue is
487 empty. (If the running thread can continue running, then it
488 will be in the run queue.) If the run queue is empty, return
490 static struct thread *
491 next_thread_to_run (void)
493 if (list_empty (&ready_list))
496 return list_entry (list_pop_front (&ready_list), struct thread, elem);
499 /* Completes a thread switch by activating the new thread's page
500 tables, and, if the previous thread is dying, destroying it.
502 At this function's invocation, we just switched from thread
503 PREV, the new thread is already running, and interrupts are
504 still disabled. This function is normally invoked by
505 thread_schedule() as its final action before returning, but
506 the first time a thread is scheduled it is called by
507 switch_entry() (see switch.S).
509 It's not safe to call printf() until the thread switch is
510 complete. In practice that means that printf()s should be
511 added at the end of the function.
513 After this function and its caller returns, the thread switch
516 thread_schedule_tail (struct thread *prev)
518 struct thread *cur = running_thread ();
520 ASSERT (intr_get_level () == INTR_OFF);
522 /* Mark us as running. */
523 cur->status = THREAD_RUNNING;
525 /* Start new time slice. */
529 /* Activate the new address space. */
533 /* If the thread we switched from is dying, destroy its struct
534 thread. This must happen late so that thread_exit() doesn't
535 pull out the rug under itself. (We don't free
536 initial_thread because its memory was not obtained via
538 if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread)
540 ASSERT (prev != cur);
541 palloc_free_page (prev);
545 /* Schedules a new process. At entry, interrupts must be off and
546 the running process's state must have been changed from
547 running to some other state. This function finds another
548 thread to run and switches to it.
550 It's not safe to call printf() until thread_schedule_tail()
555 struct thread *cur = running_thread ();
556 struct thread *next = next_thread_to_run ();
557 struct thread *prev = NULL;
559 ASSERT (intr_get_level () == INTR_OFF);
560 ASSERT (cur->status != THREAD_RUNNING);
561 ASSERT (is_thread (next));
564 prev = switch_threads (cur, next);
565 thread_schedule_tail (prev);
568 /* Returns a tid to use for a new thread. */
572 static tid_t next_tid = 1;
575 lock_acquire (&tid_lock);
577 lock_release (&tid_lock);
582 /* Offset of `stack' member within `struct thread'.
583 Used by switch.S, which can't figure it out on its own. */
584 uint32_t thread_stack_ofs = offsetof (struct thread, stack);