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;
28 static struct thread *idle_thread;
30 /* Initial thread, the thread running init.c:main(). */
31 static struct thread *initial_thread;
33 /* Lock used by allocate_tid(). */
34 static struct lock tid_lock;
36 /* Stack frame for kernel_thread(). */
37 struct kernel_thread_frame
39 void *eip; /* Return address. */
40 thread_func *function; /* Function to call. */
41 void *aux; /* Auxiliary data for function. */
45 static long long idle_ticks; /* # of timer ticks spent idle. */
46 static long long kernel_ticks; /* # of timer ticks in kernel threads. */
47 static long long user_ticks; /* # of timer ticks in user programs. */
50 #define TIME_SLICE 4 /* # of timer ticks to give each thread. */
51 static unsigned thread_ticks; /* # of timer ticks since last yield. */
53 /* If false (default), use round-robin scheduler.
54 If true, use multi-level feedback queue scheduler.
55 Controlled by kernel command-line option "-o mlfqs". */
58 static void kernel_thread (thread_func *, void *aux);
60 static void idle (void *aux UNUSED);
61 static struct thread *running_thread (void);
62 static struct thread *next_thread_to_run (void);
63 static void init_thread (struct thread *, const char *name, int priority);
64 static bool is_thread (struct thread *) UNUSED;
65 static void *alloc_frame (struct thread *, size_t size);
66 static void schedule (void);
67 void schedule_tail (struct thread *prev);
68 static tid_t allocate_tid (void);
70 /* Initializes the threading system by transforming the code
71 that's currently running into a thread. This can't work in
72 general and it is possible in this case only because loader.S
73 was careful to put the bottom of the stack at a page boundary.
75 Also initializes the run queue and the tid lock.
77 After calling this function, be sure to initialize the page
78 allocator before trying to create any threads with
81 It is not safe to call thread_current() until this function
86 ASSERT (intr_get_level () == INTR_OFF);
88 lock_init (&tid_lock);
89 list_init (&ready_list);
91 /* Set up a thread structure for the running thread. */
92 initial_thread = running_thread ();
93 init_thread (initial_thread, "main", PRI_DEFAULT);
94 initial_thread->status = THREAD_RUNNING;
95 initial_thread->tid = allocate_tid ();
98 /* Starts preemptive thread scheduling by enabling interrupts.
99 Also creates the idle thread. */
103 /* Create the idle thread. */
104 struct semaphore idle_started;
105 sema_init (&idle_started, 0);
106 thread_create ("idle", PRI_MIN, idle, &idle_started);
108 /* Start preemptive thread scheduling. */
111 /* Wait for the idle thread to initialize idle_thread. */
112 sema_down (&idle_started);
115 /* Called by the timer interrupt handler at each timer tick.
116 Thus, this function runs in an external interrupt context. */
120 struct thread *t = thread_current ();
122 /* Update statistics. */
123 if (t == idle_thread)
126 else if (t->pagedir != NULL)
132 /* Enforce preemption. */
133 if (++thread_ticks >= TIME_SLICE)
134 intr_yield_on_return ();
137 /* Prints thread statistics. */
139 thread_print_stats (void)
141 printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
142 idle_ticks, kernel_ticks, user_ticks);
145 /* Creates a new kernel thread named NAME with the given initial
146 PRIORITY, which executes FUNCTION passing AUX as the argument,
147 and adds it to the ready queue. Returns the thread identifier
148 for the new thread, or TID_ERROR if creation fails.
150 If thread_start() has been called, then the new thread may be
151 scheduled before thread_create() returns. It could even exit
152 before thread_create() returns. Contrariwise, the original
153 thread may run for any amount of time before the new thread is
154 scheduled. Use a semaphore or some other form of
155 synchronization if you need to ensure ordering.
157 The code provided sets the new thread's `priority' member to
158 PRIORITY, but no actual priority scheduling is implemented.
159 Priority scheduling is the goal of Problem 1-3. */
161 thread_create (const char *name, int priority,
162 thread_func *function, void *aux)
165 struct kernel_thread_frame *kf;
166 struct switch_entry_frame *ef;
167 struct switch_threads_frame *sf;
170 ASSERT (function != NULL);
172 /* Allocate thread. */
173 t = palloc_get_page (PAL_ZERO);
177 /* Initialize thread. */
178 init_thread (t, name, priority);
179 tid = t->tid = allocate_tid ();
181 /* Stack frame for kernel_thread(). */
182 kf = alloc_frame (t, sizeof *kf);
184 kf->function = function;
187 /* Stack frame for switch_entry(). */
188 ef = alloc_frame (t, sizeof *ef);
189 ef->eip = (void (*) (void)) kernel_thread;
191 /* Stack frame for switch_threads(). */
192 sf = alloc_frame (t, sizeof *sf);
193 sf->eip = switch_entry;
195 /* Add to run queue. */
201 /* Puts the current thread to sleep. It will not be scheduled
202 again until awoken by thread_unblock().
204 This function must be called with interrupts turned off. It
205 is usually a better idea to use one of the synchronization
206 primitives in synch.h. */
210 ASSERT (!intr_context ());
211 ASSERT (intr_get_level () == INTR_OFF);
213 thread_current ()->status = THREAD_BLOCKED;
217 /* Transitions a blocked thread T to the ready-to-run state.
218 This is an error if T is not blocked. (Use thread_yield() to
219 make the running thread ready.)
221 This function does not preempt the running thread. This can
222 be important: if the caller had disabled interrupts itself,
223 it may expect that it can atomically unblock a thread and
224 update other data. */
226 thread_unblock (struct thread *t)
228 enum intr_level old_level;
230 ASSERT (is_thread (t));
232 old_level = intr_disable ();
233 ASSERT (t->status == THREAD_BLOCKED);
234 list_push_back (&ready_list, &t->elem);
235 t->status = THREAD_READY;
236 intr_set_level (old_level);
239 /* Returns the name of the running thread. */
243 return thread_current ()->name;
246 /* Returns the running thread.
247 This is running_thread() plus a couple of sanity checks.
248 See the big comment at the top of thread.h for details. */
250 thread_current (void)
252 struct thread *t = running_thread ();
254 /* Make sure T is really a thread.
255 If either of these assertions fire, then your thread may
256 have overflowed its stack. Each thread has less than 4 kB
257 of stack, so a few big automatic arrays or moderate
258 recursion can cause stack overflow. */
259 ASSERT (is_thread (t));
260 ASSERT (t->status == THREAD_RUNNING);
265 /* Returns the running thread's tid. */
269 return thread_current ()->tid;
272 /* Deschedules the current thread and destroys it. Never
273 returns to the caller. */
277 ASSERT (!intr_context ());
283 /* Just set our status to dying and schedule another process.
284 We will be destroyed during the call to schedule_tail(). */
286 thread_current ()->status = THREAD_DYING;
291 /* Yields the CPU. The current thread is not put to sleep and
292 may be scheduled again immediately at the scheduler's whim. */
296 struct thread *cur = thread_current ();
297 enum intr_level old_level;
299 ASSERT (!intr_context ());
301 old_level = intr_disable ();
302 if (cur != idle_thread)
303 list_push_back (&ready_list, &cur->elem);
304 cur->status = THREAD_READY;
306 intr_set_level (old_level);
309 /* Sets the current thread's priority to NEW_PRIORITY. */
311 thread_set_priority (int new_priority)
313 thread_current ()->priority = new_priority;
316 /* Returns the current thread's priority. */
318 thread_get_priority (void)
320 return thread_current ()->priority;
323 /* Sets the current thread's nice value to NICE. */
325 thread_set_nice (int nice UNUSED)
327 /* Not yet implemented. */
330 /* Returns the current thread's nice value. */
332 thread_get_nice (void)
334 /* Not yet implemented. */
338 /* Returns 100 times the system load average. */
340 thread_get_load_avg (void)
342 /* Not yet implemented. */
346 /* Returns 100 times the current thread's recent_cpu value. */
348 thread_get_recent_cpu (void)
350 /* Not yet implemented. */
354 /* Idle thread. Executes when no other thread is ready to run.
356 The idle thread is initially put on the ready list by
357 thread_start(). It will be scheduled once initially, at which
358 point it initializes idle_thread, "up"s the semaphore passed
359 to it to enable thread_start() to continue, and immediately
360 blocks. After that, the idle thread never appears in the
361 ready list. It is returned by next_thread_to_run() as a
362 special case when the ready list is empty. */
364 idle (void *idle_started_ UNUSED)
366 struct semaphore *idle_started = idle_started_;
367 idle_thread = thread_current ();
368 sema_up (idle_started);
372 /* Let someone else run. */
376 /* Re-enable interrupts and wait for the next one.
378 The `sti' instruction disables interrupts until the
379 completion of the next instruction, so these two
380 instructions are executed atomically. This atomicity is
381 important; otherwise, an interrupt could be handled
382 between re-enabling interrupts and waiting for the next
383 one to occur, wasting as much as one clock tick worth of
386 See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a]
387 7.11.1 "HLT Instruction". */
388 asm volatile ("sti; hlt" : : : "memory");
392 /* Function used as the basis for a kernel thread. */
394 kernel_thread (thread_func *function, void *aux)
396 ASSERT (function != NULL);
398 intr_enable (); /* The scheduler runs with interrupts off. */
399 function (aux); /* Execute the thread function. */
400 thread_exit (); /* If function() returns, kill the thread. */
403 /* Returns the running thread. */
405 running_thread (void)
409 /* Copy the CPU's stack pointer into `esp', and then round that
410 down to the start of a page. Because `struct thread' is
411 always at the beginning of a page and the stack pointer is
412 somewhere in the middle, this locates the curent thread. */
413 asm ("mov %%esp, %0" : "=g" (esp));
414 return pg_round_down (esp);
417 /* Returns true if T appears to point to a valid thread. */
419 is_thread (struct thread *t)
421 return t != NULL && t->magic == THREAD_MAGIC;
424 /* Does basic initialization of T as a blocked thread named
427 init_thread (struct thread *t, const char *name, int priority)
430 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
431 ASSERT (name != NULL);
433 memset (t, 0, sizeof *t);
434 t->status = THREAD_BLOCKED;
435 strlcpy (t->name, name, sizeof t->name);
436 t->stack = (uint8_t *) t + PGSIZE;
437 t->priority = priority;
438 t->magic = THREAD_MAGIC;
441 /* Allocates a SIZE-byte frame at the top of thread T's stack and
442 returns a pointer to the frame's base. */
444 alloc_frame (struct thread *t, size_t size)
446 /* Stack data is always allocated in word-size units. */
447 ASSERT (is_thread (t));
448 ASSERT (size % sizeof (uint32_t) == 0);
454 /* Chooses and returns the next thread to be scheduled. Should
455 return a thread from the run queue, unless the run queue is
456 empty. (If the running thread can continue running, then it
457 will be in the run queue.) If the run queue is empty, return
459 static struct thread *
460 next_thread_to_run (void)
462 if (list_empty (&ready_list))
465 return list_entry (list_pop_front (&ready_list), struct thread, elem);
468 /* Completes a thread switch by activating the new thread's page
469 tables, and, if the previous thread is dying, destroying it.
471 At this function's invocation, we just switched from thread
472 PREV, the new thread is already running, and interrupts are
473 still disabled. This function is normally invoked by
474 thread_schedule() as its final action before returning, but
475 the first time a thread is scheduled it is called by
476 switch_entry() (see switch.S).
478 It's not safe to call printf() until the thread switch is
479 complete. In practice that means that printf()s should be
480 added at the end of the function.
482 After this function and its caller returns, the thread switch
485 schedule_tail (struct thread *prev)
487 struct thread *cur = running_thread ();
489 ASSERT (intr_get_level () == INTR_OFF);
491 /* Mark us as running. */
492 cur->status = THREAD_RUNNING;
494 /* Start new time slice. */
498 /* Activate the new address space. */
502 /* If the thread we switched from is dying, destroy its struct
503 thread. This must happen late so that thread_exit() doesn't
504 pull out the rug under itself. (We don't free
505 initial_thread because its memory was not obtained via
507 if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread)
509 ASSERT (prev != cur);
510 palloc_free_page (prev);
514 /* Schedules a new process. At entry, interrupts must be off and
515 the running process's state must have been changed from
516 running to some other state. This function finds another
517 thread to run and switches to it.
519 It's not safe to call printf() until schedule_tail() has
524 struct thread *cur = running_thread ();
525 struct thread *next = next_thread_to_run ();
526 struct thread *prev = NULL;
528 ASSERT (intr_get_level () == INTR_OFF);
529 ASSERT (cur->status != THREAD_RUNNING);
530 ASSERT (is_thread (next));
533 prev = switch_threads (cur, next);
534 schedule_tail (prev);
537 /* Returns a tid to use for a new thread. */
541 static tid_t next_tid = 1;
544 lock_acquire (&tid_lock);
546 lock_release (&tid_lock);
551 /* Offset of `stack' member within `struct thread'.
552 Used by switch.S, which can't figure it out on its own. */
553 uint32_t thread_stack_ofs = offsetof (struct thread, stack);