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. */
50 #define TIME_SLICE 4 /* # of timer ticks to give each thread. */
51 static unsigned thread_ticks; /* # of timer ticks since last yield. */
53 static void kernel_thread (thread_func *, void *aux);
55 static void idle (void *aux UNUSED);
56 static struct thread *running_thread (void);
57 static struct thread *next_thread_to_run (void);
58 static void init_thread (struct thread *, const char *name, int priority);
59 static bool is_thread (struct thread *) UNUSED;
60 static void *alloc_frame (struct thread *, size_t size);
61 static void schedule (void);
62 void schedule_tail (struct thread *prev);
63 static tid_t allocate_tid (void);
65 /* Initializes the threading system by transforming the code
66 that's currently running into a thread. This can't work in
67 general and it is possible in this case only because loader.S
68 was careful to put the bottom of the stack at a page boundary.
70 Also initializes the run queue and the tid lock.
72 After calling this function, be sure to initialize the page
73 allocator before trying to create any threads with
78 ASSERT (intr_get_level () == INTR_OFF);
80 lock_init (&tid_lock);
81 list_init (&ready_list);
83 /* Set up a thread structure for the running thread. */
84 initial_thread = running_thread ();
85 init_thread (initial_thread, "main", PRI_DEFAULT);
86 initial_thread->status = THREAD_RUNNING;
87 initial_thread->tid = allocate_tid ();
90 /* Starts preemptive thread scheduling by enabling interrupts.
91 Also creates the idle thread. */
95 thread_create ("idle", PRI_MAX, idle, NULL);
99 /* Called by the timer interrupt handler at each timer tick.
100 Thus, this function runs in an external interrupt context. */
104 struct thread *t = thread_current ();
106 /* Update statistics. */
107 if (t == idle_thread)
110 else if (t->pagedir != NULL)
116 /* Enforce preemption. */
117 if (++thread_ticks >= TIME_SLICE)
118 intr_yield_on_return ();
121 /* Prints thread statistics. */
123 thread_print_stats (void)
125 printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
126 idle_ticks, kernel_ticks, user_ticks);
129 /* Creates a new kernel thread named NAME with the given initial
130 PRIORITY, which executes FUNCTION passing AUX as the argument,
131 and adds it to the ready queue. Returns the thread identifier
132 for the new thread, or TID_ERROR if creation fails.
134 If thread_start() has been called, then the new thread may be
135 scheduled before thread_create() returns. It could even exit
136 before thread_create() returns. Contrariwise, the original
137 thread may run for any amount of time before the new thread is
138 scheduled. Use a semaphore or some other form of
139 synchronization if you need to ensure ordering.
141 The code provided sets the new thread's `priority' member to
142 PRIORITY, but no actual priority scheduling is implemented.
143 Priority scheduling is the goal of Problem 1-3. */
145 thread_create (const char *name, int priority,
146 thread_func *function, void *aux)
149 struct kernel_thread_frame *kf;
150 struct switch_entry_frame *ef;
151 struct switch_threads_frame *sf;
154 ASSERT (function != NULL);
156 /* Allocate thread. */
157 t = palloc_get_page (PAL_ZERO);
161 /* Initialize thread. */
162 init_thread (t, name, priority);
163 tid = t->tid = allocate_tid ();
165 /* Stack frame for kernel_thread(). */
166 kf = alloc_frame (t, sizeof *kf);
168 kf->function = function;
171 /* Stack frame for switch_entry(). */
172 ef = alloc_frame (t, sizeof *ef);
173 ef->eip = (void (*) (void)) kernel_thread;
175 /* Stack frame for switch_threads(). */
176 sf = alloc_frame (t, sizeof *sf);
177 sf->eip = switch_entry;
179 /* Add to run queue. */
185 /* Puts the current thread to sleep. It will not be scheduled
186 again until awoken by thread_unblock().
188 This function must be called with interrupts turned off. It
189 is usually a better idea to use one of the synchronization
190 primitives in synch.h. */
194 ASSERT (!intr_context ());
195 ASSERT (intr_get_level () == INTR_OFF);
197 thread_current ()->status = THREAD_BLOCKED;
201 /* Transitions a blocked thread T to the ready-to-run state.
202 This is an error if T is not blocked. (Use thread_yield() to
203 make the running thread ready.) */
205 thread_unblock (struct thread *t)
207 enum intr_level old_level;
209 ASSERT (is_thread (t));
211 old_level = intr_disable ();
212 ASSERT (t->status == THREAD_BLOCKED);
213 list_push_back (&ready_list, &t->elem);
214 t->status = THREAD_READY;
215 intr_set_level (old_level);
218 /* Returns the name of the running thread. */
222 return thread_current ()->name;
225 /* Returns the running thread.
226 This is running_thread() plus a couple of sanity checks.
227 See the big comment at the top of thread.h for details. */
229 thread_current (void)
231 struct thread *t = running_thread ();
233 /* Make sure T is really a thread.
234 If either of these assertions fire, then your thread may
235 have overflowed its stack. Each thread has less than 4 kB
236 of stack, so a few big automatic arrays or moderate
237 recursion can cause stack overflow. */
238 ASSERT (is_thread (t));
239 ASSERT (t->status == THREAD_RUNNING);
244 /* Returns the running thread's tid. */
248 return thread_current ()->tid;
251 /* Deschedules the current thread and destroys it. Never
252 returns to the caller. */
256 ASSERT (!intr_context ());
262 /* Just set our status to dying and schedule another process.
263 We will be destroyed during the call to schedule_tail(). */
265 thread_current ()->status = THREAD_DYING;
270 /* Yields the CPU. The current thread is not put to sleep and
271 may be scheduled again immediately at the scheduler's whim. */
275 struct thread *cur = thread_current ();
276 enum intr_level old_level;
278 ASSERT (!intr_context ());
280 old_level = intr_disable ();
281 list_push_back (&ready_list, &cur->elem);
282 cur->status = THREAD_READY;
284 intr_set_level (old_level);
287 /* Sets the current thread's priority to NEW_PRIORITY. */
289 thread_set_priority (int new_priority)
291 thread_current ()->priority = new_priority;
294 /* Returns the current thread's priority. */
296 thread_get_priority (void)
298 return thread_current ()->priority;
301 /* Sets the current thread's nice value to NICE. */
303 thread_set_nice (int nice UNUSED)
305 /* Not yet implemented. */
308 /* Returns the current thread's nice value. */
310 thread_get_nice (void)
312 /* Not yet implemented. */
316 /* Returns 100 times the system load average. */
318 thread_get_load_avg (void)
320 /* Not yet implemented. */
324 /* Returns 100 times the current thread's recent_cpu value. */
326 thread_get_recent_cpu (void)
328 /* Not yet implemented. */
332 /* Idle thread. Executes when no other thread is ready to run.
334 The idle thread is initially put on the ready list by
335 thread_start(). It will be scheduled once initially, at which
336 point it initializes idle_thread and immediately blocks.
337 After that, the idle thread never appears in the ready list.
338 It is returned by next_thread_to_run() as a special case when
339 the ready list is empty. */
341 idle (void *aux UNUSED)
343 /* Initialize idle_thread.
345 Until we run for the first time, idle_thread remains a null
346 pointer. That's okay because we know that, at that point,
347 the ready list has at least one element (the idle thread),
348 so next_thread_to_run() will not attempt to return the idle
350 idle_thread = thread_current ();
354 /* Let someone else run. */
358 /* Re-enable interrupts and wait for the next one.
360 The `sti' instruction disables interrupts until the
361 completion of the next instruction, so these two
362 instructions are executed atomically. This atomicity is
363 important; otherwise, an interrupt could be handled
364 between re-enabling interrupts and waiting for the next
365 one to occur, wasting as much as one clock tick worth of
368 See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a]
369 7.11.1 "HLT Instruction". */
374 /* Function used as the basis for a kernel thread. */
376 kernel_thread (thread_func *function, void *aux)
378 ASSERT (function != NULL);
380 intr_enable (); /* The scheduler runs with interrupts off. */
381 function (aux); /* Execute the thread function. */
382 thread_exit (); /* If function() returns, kill the thread. */
385 /* Returns the running thread. */
387 running_thread (void)
391 /* Copy the CPU's stack pointer into `esp', and then round that
392 down to the start of a page. Because `struct thread' is
393 always at the beginning of a page and the stack pointer is
394 somewhere in the middle, this locates the curent thread. */
395 asm ("mov %%esp, %0" : "=g" (esp));
396 return pg_round_down (esp);
399 /* Returns true if T appears to point to a valid thread. */
401 is_thread (struct thread *t)
403 return t != NULL && t->magic == THREAD_MAGIC;
406 /* Does basic initialization of T as a blocked thread named
409 init_thread (struct thread *t, const char *name, int priority)
412 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
413 ASSERT (name != NULL);
415 memset (t, 0, sizeof *t);
416 t->status = THREAD_BLOCKED;
417 strlcpy (t->name, name, sizeof t->name);
418 t->stack = (uint8_t *) t + PGSIZE;
419 t->priority = priority;
420 t->magic = THREAD_MAGIC;
423 /* Allocates a SIZE-byte frame at the top of thread T's stack and
424 returns a pointer to the frame's base. */
426 alloc_frame (struct thread *t, size_t size)
428 /* Stack data is always allocated in word-size units. */
429 ASSERT (is_thread (t));
430 ASSERT (size % sizeof (uint32_t) == 0);
436 /* Chooses and returns the next thread to be scheduled. Should
437 return a thread from the run queue, unless the run queue is
438 empty. (If the running thread can continue running, then it
439 will be in the run queue.) If the run queue is empty, return
441 static struct thread *
442 next_thread_to_run (void)
444 if (list_empty (&ready_list))
447 return list_entry (list_pop_front (&ready_list), struct thread, elem);
450 /* Completes a thread switch by activating the new thread's page
451 tables, and, if the previous thread is dying, destroying it.
453 At this function's invocation, we just switched from thread
454 PREV, the new thread is already running, and interrupts are
455 still disabled. This function is normally invoked by
456 thread_schedule() as its final action before returning, but
457 the first time a thread is scheduled it is called by
458 switch_entry() (see switch.S).
460 It's not safe to call printf() until the thread switch is
461 complete. In practice that means that printf()s should be
462 added at the end of the function.
464 After this function and its caller returns, the thread switch
467 schedule_tail (struct thread *prev)
469 struct thread *cur = running_thread ();
471 ASSERT (intr_get_level () == INTR_OFF);
473 /* Mark us as running. */
474 cur->status = THREAD_RUNNING;
476 /* Start new time slice. */
480 /* Activate the new address space. */
484 /* If the thread we switched from is dying, destroy its struct
485 thread. This must happen late so that thread_exit() doesn't
486 pull out the rug under itself. (We don't free
487 initial_thread because its memory was not obtained via
489 if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread)
491 ASSERT (prev != cur);
492 palloc_free_page (prev);
496 /* Schedules a new process. At entry, interrupts must be off and
497 the running process's state must have been changed from
498 running to some other state. This function finds another
499 thread to run and switches to it.
501 It's not safe to call printf() until schedule_tail() has
506 struct thread *cur = running_thread ();
507 struct thread *next = next_thread_to_run ();
508 struct thread *prev = NULL;
510 ASSERT (intr_get_level () == INTR_OFF);
511 ASSERT (cur->status != THREAD_RUNNING);
512 ASSERT (is_thread (next));
515 prev = switch_threads (cur, next);
516 schedule_tail (prev);
519 /* Returns a tid to use for a new thread. */
523 static tid_t next_tid = 1;
526 lock_acquire (&tid_lock);
528 lock_release (&tid_lock);
533 /* Offset of `stack' member within `struct thread'.
534 Used by switch.S, which can't figure it out on its own. */
535 uint32_t thread_stack_ofs = offsetof (struct thread, stack);