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 options "-o mlfqs".
56 Note that the command line is not parsed until well after
57 thread_init() is called. */
60 static void kernel_thread (thread_func *, void *aux);
62 static void idle (void *aux UNUSED);
63 static struct thread *running_thread (void);
64 static struct thread *next_thread_to_run (void);
65 static void init_thread (struct thread *, const char *name, int priority);
66 static bool is_thread (struct thread *) UNUSED;
67 static void *alloc_frame (struct thread *, size_t size);
68 static void schedule (void);
69 void schedule_tail (struct thread *prev);
70 static tid_t allocate_tid (void);
72 /* Initializes the threading system by transforming the code
73 that's currently running into a thread. This can't work in
74 general and it is possible in this case only because loader.S
75 was careful to put the bottom of the stack at a page boundary.
77 Also initializes the run queue and the tid lock.
79 After calling this function, be sure to initialize the page
80 allocator before trying to create any threads with
83 The kernel command line is not parsed until *after* this
84 function returns, so that when this function runs,
85 thread_mlfqs is always false.
87 It is not safe to call thread_current() until this function
92 ASSERT (intr_get_level () == INTR_OFF);
94 lock_init (&tid_lock);
95 list_init (&ready_list);
97 /* Set up a thread structure for the running thread. */
98 initial_thread = running_thread ();
99 init_thread (initial_thread, "main", PRI_DEFAULT);
100 initial_thread->status = THREAD_RUNNING;
101 initial_thread->tid = allocate_tid ();
104 /* Starts preemptive thread scheduling by enabling interrupts.
105 Also creates the idle thread.
107 By the time this function runs, thread_mlfqs has been properly
108 initialized to its final value. */
112 /* Create the idle thread with maximum priority. This ensures
113 that it will be scheduled soon after interrupts are enabled.
114 The idle thread will block almost immediately upon
115 scheduling, and subsequently it will never appear on the
116 ready list, so the priority here is otherwise
118 struct semaphore idle_started;
119 sema_init (&idle_started, 0);
120 thread_create ("idle", PRI_MAX, idle, &idle_started);
122 /* Start preemptive thread scheduling. */
125 /* Wait for the idle thread to initialize idle_thread. */
126 sema_down (&idle_started);
129 /* Called by the timer interrupt handler at each timer tick.
130 Thus, this function runs in an external interrupt context. */
134 struct thread *t = thread_current ();
136 /* Update statistics. */
137 if (t == idle_thread)
140 else if (t->pagedir != NULL)
146 /* Enforce preemption. */
147 if (++thread_ticks >= TIME_SLICE)
148 intr_yield_on_return ();
151 /* Prints thread statistics. */
153 thread_print_stats (void)
155 printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
156 idle_ticks, kernel_ticks, user_ticks);
159 /* Creates a new kernel thread named NAME with the given initial
160 PRIORITY, which executes FUNCTION passing AUX as the argument,
161 and adds it to the ready queue. Returns the thread identifier
162 for the new thread, or TID_ERROR if creation fails.
164 If thread_start() has been called, then the new thread may be
165 scheduled before thread_create() returns. It could even exit
166 before thread_create() returns. Contrariwise, the original
167 thread may run for any amount of time before the new thread is
168 scheduled. Use a semaphore or some other form of
169 synchronization if you need to ensure ordering.
171 The code provided sets the new thread's `priority' member to
172 PRIORITY, but no actual priority scheduling is implemented.
173 Priority scheduling is the goal of Problem 1-3. */
175 thread_create (const char *name, int priority,
176 thread_func *function, void *aux)
179 struct kernel_thread_frame *kf;
180 struct switch_entry_frame *ef;
181 struct switch_threads_frame *sf;
184 ASSERT (function != NULL);
186 /* Allocate thread. */
187 t = palloc_get_page (PAL_ZERO);
191 /* Initialize thread. */
192 init_thread (t, name, priority);
193 tid = t->tid = allocate_tid ();
195 /* Stack frame for kernel_thread(). */
196 kf = alloc_frame (t, sizeof *kf);
198 kf->function = function;
201 /* Stack frame for switch_entry(). */
202 ef = alloc_frame (t, sizeof *ef);
203 ef->eip = (void (*) (void)) kernel_thread;
205 /* Stack frame for switch_threads(). */
206 sf = alloc_frame (t, sizeof *sf);
207 sf->eip = switch_entry;
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 thread_unblock (struct thread *t)
237 enum intr_level old_level;
239 ASSERT (is_thread (t));
241 old_level = intr_disable ();
242 ASSERT (t->status == THREAD_BLOCKED);
243 list_push_back (&ready_list, &t->elem);
244 t->status = THREAD_READY;
245 intr_set_level (old_level);
248 /* Returns the name of the running thread. */
252 return thread_current ()->name;
255 /* Returns the running thread.
256 This is running_thread() plus a couple of sanity checks.
257 See the big comment at the top of thread.h for details. */
259 thread_current (void)
261 struct thread *t = running_thread ();
263 /* Make sure T is really a thread.
264 If either of these assertions fire, then your thread may
265 have overflowed its stack. Each thread has less than 4 kB
266 of stack, so a few big automatic arrays or moderate
267 recursion can cause stack overflow. */
268 ASSERT (is_thread (t));
269 ASSERT (t->status == THREAD_RUNNING);
274 /* Returns the running thread's tid. */
278 return thread_current ()->tid;
281 /* Deschedules the current thread and destroys it. Never
282 returns to the caller. */
286 ASSERT (!intr_context ());
292 /* Just set our status to dying and schedule another process.
293 We will be destroyed during the call to schedule_tail(). */
295 thread_current ()->status = THREAD_DYING;
300 /* Yields the CPU. The current thread is not put to sleep and
301 may be scheduled again immediately at the scheduler's whim. */
305 struct thread *cur = thread_current ();
306 enum intr_level old_level;
308 ASSERT (!intr_context ());
310 old_level = intr_disable ();
311 if (cur != idle_thread)
312 list_push_back (&ready_list, &cur->elem);
313 cur->status = THREAD_READY;
315 intr_set_level (old_level);
318 /* Sets the current thread's priority to NEW_PRIORITY. */
320 thread_set_priority (int new_priority)
322 thread_current ()->priority = new_priority;
325 /* Returns the current thread's priority. */
327 thread_get_priority (void)
329 return thread_current ()->priority;
332 /* Sets the current thread's nice value to NICE. */
334 thread_set_nice (int nice UNUSED)
336 /* Not yet implemented. */
339 /* Returns the current thread's nice value. */
341 thread_get_nice (void)
343 /* Not yet implemented. */
347 /* Returns 100 times the system load average. */
349 thread_get_load_avg (void)
351 /* Not yet implemented. */
355 /* Returns 100 times the current thread's recent_cpu value. */
357 thread_get_recent_cpu (void)
359 /* Not yet implemented. */
363 /* Idle thread. Executes when no other thread is ready to run.
365 The idle thread is initially put on the ready list by
366 thread_start(). It will be scheduled once initially, at which
367 point it initializes idle_thread, "up"s the semaphore passed
368 to it to enable thread_start() to continue, and immediately
369 blocks. After that, the idle thread never appears in the
370 ready list. It is returned by next_thread_to_run() as a
371 special case when the ready list is empty. */
373 idle (void *idle_started_ UNUSED)
375 struct semaphore *idle_started = idle_started_;
376 idle_thread = thread_current ();
377 sema_up (idle_started);
381 /* Let someone else run. */
385 /* Re-enable interrupts and wait for the next one.
387 The `sti' instruction disables interrupts until the
388 completion of the next instruction, so these two
389 instructions are executed atomically. This atomicity is
390 important; otherwise, an interrupt could be handled
391 between re-enabling interrupts and waiting for the next
392 one to occur, wasting as much as one clock tick worth of
395 See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a]
396 7.11.1 "HLT Instruction". */
401 /* Function used as the basis for a kernel thread. */
403 kernel_thread (thread_func *function, void *aux)
405 ASSERT (function != NULL);
407 intr_enable (); /* The scheduler runs with interrupts off. */
408 function (aux); /* Execute the thread function. */
409 thread_exit (); /* If function() returns, kill the thread. */
412 /* Returns the running thread. */
414 running_thread (void)
418 /* Copy the CPU's stack pointer into `esp', and then round that
419 down to the start of a page. Because `struct thread' is
420 always at the beginning of a page and the stack pointer is
421 somewhere in the middle, this locates the curent thread. */
422 asm ("mov %%esp, %0" : "=g" (esp));
423 return pg_round_down (esp);
426 /* Returns true if T appears to point to a valid thread. */
428 is_thread (struct thread *t)
430 return t != NULL && t->magic == THREAD_MAGIC;
433 /* Does basic initialization of T as a blocked thread named
436 init_thread (struct thread *t, const char *name, int priority)
439 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
440 ASSERT (name != NULL);
442 memset (t, 0, sizeof *t);
443 t->status = THREAD_BLOCKED;
444 strlcpy (t->name, name, sizeof t->name);
445 t->stack = (uint8_t *) t + PGSIZE;
446 t->priority = priority;
447 t->magic = THREAD_MAGIC;
450 /* Allocates a SIZE-byte frame at the top of thread T's stack and
451 returns a pointer to the frame's base. */
453 alloc_frame (struct thread *t, size_t size)
455 /* Stack data is always allocated in word-size units. */
456 ASSERT (is_thread (t));
457 ASSERT (size % sizeof (uint32_t) == 0);
463 /* Chooses and returns the next thread to be scheduled. Should
464 return a thread from the run queue, unless the run queue is
465 empty. (If the running thread can continue running, then it
466 will be in the run queue.) If the run queue is empty, return
468 static struct thread *
469 next_thread_to_run (void)
471 if (list_empty (&ready_list))
474 return list_entry (list_pop_front (&ready_list), struct thread, elem);
477 /* Completes a thread switch by activating the new thread's page
478 tables, and, if the previous thread is dying, destroying it.
480 At this function's invocation, we just switched from thread
481 PREV, the new thread is already running, and interrupts are
482 still disabled. This function is normally invoked by
483 thread_schedule() as its final action before returning, but
484 the first time a thread is scheduled it is called by
485 switch_entry() (see switch.S).
487 It's not safe to call printf() until the thread switch is
488 complete. In practice that means that printf()s should be
489 added at the end of the function.
491 After this function and its caller returns, the thread switch
494 schedule_tail (struct thread *prev)
496 struct thread *cur = running_thread ();
498 ASSERT (intr_get_level () == INTR_OFF);
500 /* Mark us as running. */
501 cur->status = THREAD_RUNNING;
503 /* Start new time slice. */
507 /* Activate the new address space. */
511 /* If the thread we switched from is dying, destroy its struct
512 thread. This must happen late so that thread_exit() doesn't
513 pull out the rug under itself. (We don't free
514 initial_thread because its memory was not obtained via
516 if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread)
518 ASSERT (prev != cur);
519 palloc_free_page (prev);
523 /* Schedules a new process. At entry, interrupts must be off and
524 the running process's state must have been changed from
525 running to some other state. This function finds another
526 thread to run and switches to it.
528 It's not safe to call printf() until schedule_tail() has
533 struct thread *cur = running_thread ();
534 struct thread *next = next_thread_to_run ();
535 struct thread *prev = NULL;
537 ASSERT (intr_get_level () == INTR_OFF);
538 ASSERT (cur->status != THREAD_RUNNING);
539 ASSERT (is_thread (next));
542 prev = switch_threads (cur, next);
543 schedule_tail (prev);
546 /* Returns a tid to use for a new thread. */
550 static tid_t next_tid = 1;
553 lock_acquire (&tid_lock);
555 lock_release (&tid_lock);
560 /* Offset of `stack' member within `struct thread'.
561 Used by switch.S, which can't figure it out on its own. */
562 uint32_t thread_stack_ofs = offsetof (struct thread, stack);