1 #include "threads/thread.h"
7 #include "threads/flags.h"
8 #include "threads/interrupt.h"
9 #include "threads/intr-stubs.h"
10 #include "threads/mmu.h"
11 #include "threads/palloc.h"
12 #include "threads/switch.h"
13 #include "threads/synch.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. */
49 static void kernel_thread (thread_func *, void *aux);
51 static void idle (void *aux UNUSED);
52 static struct thread *running_thread (void);
53 static struct thread *next_thread_to_run (void);
54 static void init_thread (struct thread *, const char *name, int priority);
55 static bool is_thread (struct thread *);
56 static void *alloc_frame (struct thread *, size_t size);
57 static void schedule (void);
58 void schedule_tail (struct thread *prev);
59 static tid_t allocate_tid (void);
61 /* Initializes the threading system by transforming the code
62 that's currently running into a thread. This can't work in
63 general and it is possible in this case only because loader.S
64 was careful to put the bottom of the stack at a page boundary.
66 Also initializes the run queue and the tid lock.
68 After calling this function, be sure to initialize the page
69 allocator before trying to create any threads with
74 ASSERT (intr_get_level () == INTR_OFF);
76 lock_init (&tid_lock, "tid");
77 list_init (&ready_list);
79 /* Set up a thread structure for the running thread. */
80 initial_thread = running_thread ();
81 init_thread (initial_thread, "main", PRI_DEFAULT);
82 initial_thread->status = THREAD_RUNNING;
83 initial_thread->tid = allocate_tid ();
86 /* Starts preemptive thread scheduling by enabling interrupts.
87 Also creates the idle thread. */
91 thread_create ("idle", PRI_DEFAULT, idle, NULL);
95 /* Called by the timer interrupt handler at each timer tick to
100 struct thread *t = thread_current ();
101 if (t == idle_thread)
104 else if (t->pagedir != NULL)
111 /* Prints thread statistics. */
113 thread_print_stats (void)
115 printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
116 idle_ticks, kernel_ticks, user_ticks);
119 /* Creates a new kernel thread named NAME with the given initial
120 PRIORITY, which executes FUNCTION passing AUX as the argument,
121 and adds it to the ready queue. Returns the thread identifier
122 for the new thread, or TID_ERROR if creation fails.
124 If thread_start() has been called, then the new thread may be
125 scheduled before thread_create() returns. It could even exit
126 before thread_create() returns. Contrariwise, the original
127 thread may run for any amount of time before the new thread is
128 scheduled. Use a semaphore or some other form of
129 synchronization if you need to ensure ordering.
131 The code provided sets the new thread's `priority' member to
132 PRIORITY, but no actual priority scheduling is implemented.
133 Priority scheduling is the goal of Problem 1-3. */
135 thread_create (const char *name, int priority,
136 thread_func *function, void *aux)
139 struct kernel_thread_frame *kf;
140 struct switch_entry_frame *ef;
141 struct switch_threads_frame *sf;
144 ASSERT (function != NULL);
146 /* Allocate thread. */
147 t = palloc_get_page (PAL_ZERO);
151 /* Initialize thread. */
152 init_thread (t, name, priority);
153 tid = t->tid = allocate_tid ();
155 /* Stack frame for kernel_thread(). */
156 kf = alloc_frame (t, sizeof *kf);
158 kf->function = function;
161 /* Stack frame for switch_entry(). */
162 ef = alloc_frame (t, sizeof *ef);
163 ef->eip = (void (*) (void)) kernel_thread;
165 /* Stack frame for switch_threads(). */
166 sf = alloc_frame (t, sizeof *sf);
167 sf->eip = switch_entry;
169 /* Add to run queue. */
175 /* Puts the current thread to sleep. It will not be scheduled
176 again until awoken by thread_unblock().
178 This function must be called with interrupts turned off. It
179 is usually a better idea to use one of the synchronization
180 primitives in synch.h. */
184 ASSERT (!intr_context ());
185 ASSERT (intr_get_level () == INTR_OFF);
187 thread_current ()->status = THREAD_BLOCKED;
191 /* Transitions a blocked thread T to the ready-to-run state.
192 This is an error if T is not blocked. (Use thread_yield() to
193 make the running thread ready.) */
195 thread_unblock (struct thread *t)
197 enum intr_level old_level;
199 ASSERT (is_thread (t));
201 old_level = intr_disable ();
202 ASSERT (t->status == THREAD_BLOCKED);
203 list_push_back (&ready_list, &t->elem);
204 t->status = THREAD_READY;
205 intr_set_level (old_level);
208 /* Returns the name of the running thread. */
212 return thread_current ()->name;
215 /* Returns the running thread.
216 This is running_thread() plus a couple of sanity checks.
217 See the big comment at the top of thread.h for details. */
219 thread_current (void)
221 struct thread *t = running_thread ();
223 /* Make sure T is really a thread.
224 If either of these assertions fire, then your thread may
225 have overflowed its stack. Each thread has less than 4 kB
226 of stack, so a few big automatic arrays or moderate
227 recursion can cause stack overflow. */
228 ASSERT (is_thread (t));
229 ASSERT (t->status == THREAD_RUNNING);
234 /* Returns the running thread's tid. */
238 return thread_current ()->tid;
241 /* Deschedules the current thread and destroys it. Never
242 returns to the caller. */
246 ASSERT (!intr_context ());
252 /* Just set our status to dying and schedule another process.
253 We will be destroyed during the call to schedule_tail(). */
255 thread_current ()->status = THREAD_DYING;
260 /* Yields the CPU. The current thread is not put to sleep and
261 may be scheduled again immediately at the scheduler's whim. */
265 struct thread *cur = thread_current ();
266 enum intr_level old_level;
268 ASSERT (!intr_context ());
270 old_level = intr_disable ();
271 list_push_back (&ready_list, &cur->elem);
272 cur->status = THREAD_READY;
274 intr_set_level (old_level);
277 /* Sets the current thread's priority to NEW_PRIORITY. */
279 thread_set_priority (int new_priority)
281 thread_current ()->priority = new_priority;
284 /* Returns the current thread's priority. */
286 thread_get_priority (void)
288 return thread_current ()->priority;
291 /* Idle thread. Executes when no other thread is ready to run. */
293 idle (void *aux UNUSED)
295 idle_thread = thread_current ();
299 /* Let someone else run. */
303 /* Re-enable interrupts and wait for the next one.
305 The `sti' instruction disables interrupts until the
306 completion of the next instruction, so these two
307 instructions are executed atomically. This atomicity is
308 important; otherwise, an interrupt could be handled
309 between re-enabling interrupts and waiting for the next
310 one to occur, wasting as much as one clock tick worth of
313 See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3] 7.7. */
318 /* Function used as the basis for a kernel thread. */
320 kernel_thread (thread_func *function, void *aux)
322 ASSERT (function != NULL);
324 intr_enable (); /* The scheduler runs with interrupts off. */
325 function (aux); /* Execute the thread function. */
326 thread_exit (); /* If function() returns, kill the thread. */
329 /* Returns the running thread. */
331 running_thread (void)
335 /* Copy the CPU's stack pointer into `esp', and then round that
336 down to the start of a page. Because `struct thread' is
337 always at the beginning of a page and the stack pointer is
338 somewhere in the middle, this locates the curent thread. */
339 asm ("mov %0, %%esp" : "=g" (esp));
340 return pg_round_down (esp);
343 /* Returns true if T appears to point to a valid thread. */
345 is_thread (struct thread *t)
347 return t != NULL && t->magic == THREAD_MAGIC;
350 /* Does basic initialization of T as a blocked thread named
353 init_thread (struct thread *t, const char *name, int priority)
356 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
357 ASSERT (name != NULL);
359 memset (t, 0, sizeof *t);
360 t->status = THREAD_BLOCKED;
361 strlcpy (t->name, name, sizeof t->name);
362 t->stack = (uint8_t *) t + PGSIZE;
363 t->priority = priority;
364 t->magic = THREAD_MAGIC;
367 /* Allocates a SIZE-byte frame at the top of thread T's stack and
368 returns a pointer to the frame's base. */
370 alloc_frame (struct thread *t, size_t size)
372 /* Stack data is always allocated in word-size units. */
373 ASSERT (is_thread (t));
374 ASSERT (size % sizeof (uint32_t) == 0);
380 /* Chooses and returns the next thread to be scheduled. Should
381 return a thread from the run queue, unless the run queue is
382 empty. (If the running thread can continue running, then it
383 will be in the run queue.) If the run queue is empty, return
385 static struct thread *
386 next_thread_to_run (void)
388 if (list_empty (&ready_list))
391 return list_entry (list_pop_front (&ready_list), struct thread, elem);
394 /* Completes a thread switch by activating the new thread's page
395 tables, and, if the previous thread is dying, destroying it.
397 At this function's invocation, we just switched from thread
398 PREV, the new thread is already running, and interrupts are
399 still disabled. This function is normally invoked by
400 thread_schedule() as its final action before returning, but
401 the first time a thread is scheduled it is called by
402 switch_entry() (see switch.S).
404 It's not safe to call printf() until the thread switch is
405 complete. In practice that means that printf()s should be
406 added at the end of the function.
408 After this function and its caller returns, the thread switch
411 schedule_tail (struct thread *prev)
413 struct thread *cur = running_thread ();
415 ASSERT (intr_get_level () == INTR_OFF);
417 /* Mark us as running. */
418 cur->status = THREAD_RUNNING;
421 /* Activate the new address space. */
425 /* If the thread we switched from is dying, destroy its struct
426 thread. This must happen late so that thread_exit() doesn't
427 pull out the rug under itself. */
428 if (prev != NULL && prev->status == THREAD_DYING)
430 ASSERT (prev != cur);
431 if (prev != initial_thread)
432 palloc_free_page (prev);
436 /* Schedules a new process. At entry, interrupts must be off and
437 the running process's state must have been changed from
438 running to some other state. This function finds another
439 thread to run and switches to it.
441 It's not safe to call printf() until schedule_tail() has
446 struct thread *cur = running_thread ();
447 struct thread *next = next_thread_to_run ();
448 struct thread *prev = NULL;
450 ASSERT (intr_get_level () == INTR_OFF);
451 ASSERT (cur->status != THREAD_RUNNING);
452 ASSERT (is_thread (next));
455 prev = switch_threads (cur, next);
456 schedule_tail (prev);
459 /* Returns a tid to use for a new thread. */
463 static tid_t next_tid = 1;
466 lock_acquire (&tid_lock);
468 lock_release (&tid_lock);
473 /* Offset of `stack' member within `struct thread'.
474 Used by switch.S, which can't figure it out on its own. */
475 uint32_t thread_stack_ofs = offsetof (struct thread, stack);