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. */
113 struct semaphore idle_started;
114 sema_init (&idle_started, 0);
115 thread_create ("idle", PRI_MIN, idle, &idle_started);
117 /* Start preemptive thread scheduling. */
120 /* Wait for the idle thread to initialize idle_thread. */
121 sema_down (&idle_started);
124 /* Called by the timer interrupt handler at each timer tick.
125 Thus, this function runs in an external interrupt context. */
129 struct thread *t = thread_current ();
131 /* Update statistics. */
132 if (t == idle_thread)
135 else if (t->pagedir != NULL)
141 /* Enforce preemption. */
142 if (++thread_ticks >= TIME_SLICE)
143 intr_yield_on_return ();
146 /* Prints thread statistics. */
148 thread_print_stats (void)
150 printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
151 idle_ticks, kernel_ticks, user_ticks);
154 /* Creates a new kernel thread named NAME with the given initial
155 PRIORITY, which executes FUNCTION passing AUX as the argument,
156 and adds it to the ready queue. Returns the thread identifier
157 for the new thread, or TID_ERROR if creation fails.
159 If thread_start() has been called, then the new thread may be
160 scheduled before thread_create() returns. It could even exit
161 before thread_create() returns. Contrariwise, the original
162 thread may run for any amount of time before the new thread is
163 scheduled. Use a semaphore or some other form of
164 synchronization if you need to ensure ordering.
166 The code provided sets the new thread's `priority' member to
167 PRIORITY, but no actual priority scheduling is implemented.
168 Priority scheduling is the goal of Problem 1-3. */
170 thread_create (const char *name, int priority,
171 thread_func *function, void *aux)
174 struct kernel_thread_frame *kf;
175 struct switch_entry_frame *ef;
176 struct switch_threads_frame *sf;
179 ASSERT (function != NULL);
181 /* Allocate thread. */
182 t = palloc_get_page (PAL_ZERO);
186 /* Initialize thread. */
187 init_thread (t, name, priority);
188 tid = t->tid = allocate_tid ();
190 /* Stack frame for kernel_thread(). */
191 kf = alloc_frame (t, sizeof *kf);
193 kf->function = function;
196 /* Stack frame for switch_entry(). */
197 ef = alloc_frame (t, sizeof *ef);
198 ef->eip = (void (*) (void)) kernel_thread;
200 /* Stack frame for switch_threads(). */
201 sf = alloc_frame (t, sizeof *sf);
202 sf->eip = switch_entry;
204 /* Add to run queue. */
210 /* Puts the current thread to sleep. It will not be scheduled
211 again until awoken by thread_unblock().
213 This function must be called with interrupts turned off. It
214 is usually a better idea to use one of the synchronization
215 primitives in synch.h. */
219 ASSERT (!intr_context ());
220 ASSERT (intr_get_level () == INTR_OFF);
222 thread_current ()->status = THREAD_BLOCKED;
226 /* Transitions a blocked thread T to the ready-to-run state.
227 This is an error if T is not blocked. (Use thread_yield() to
228 make the running thread ready.) */
230 thread_unblock (struct thread *t)
232 enum intr_level old_level;
234 ASSERT (is_thread (t));
236 old_level = intr_disable ();
237 ASSERT (t->status == THREAD_BLOCKED);
238 list_push_back (&ready_list, &t->elem);
239 t->status = THREAD_READY;
240 intr_set_level (old_level);
243 /* Returns the name of the running thread. */
247 return thread_current ()->name;
250 /* Returns the running thread.
251 This is running_thread() plus a couple of sanity checks.
252 See the big comment at the top of thread.h for details. */
254 thread_current (void)
256 struct thread *t = running_thread ();
258 /* Make sure T is really a thread.
259 If either of these assertions fire, then your thread may
260 have overflowed its stack. Each thread has less than 4 kB
261 of stack, so a few big automatic arrays or moderate
262 recursion can cause stack overflow. */
263 ASSERT (is_thread (t));
264 ASSERT (t->status == THREAD_RUNNING);
269 /* Returns the running thread's tid. */
273 return thread_current ()->tid;
276 /* Deschedules the current thread and destroys it. Never
277 returns to the caller. */
281 ASSERT (!intr_context ());
287 /* Just set our status to dying and schedule another process.
288 We will be destroyed during the call to schedule_tail(). */
290 thread_current ()->status = THREAD_DYING;
295 /* Yields the CPU. The current thread is not put to sleep and
296 may be scheduled again immediately at the scheduler's whim. */
300 struct thread *cur = thread_current ();
301 enum intr_level old_level;
303 ASSERT (!intr_context ());
305 old_level = intr_disable ();
306 if (cur != idle_thread)
307 list_push_back (&ready_list, &cur->elem);
308 cur->status = THREAD_READY;
310 intr_set_level (old_level);
313 /* Sets the current thread's priority to NEW_PRIORITY. */
315 thread_set_priority (int new_priority)
317 thread_current ()->priority = new_priority;
320 /* Returns the current thread's priority. */
322 thread_get_priority (void)
324 return thread_current ()->priority;
327 /* Sets the current thread's nice value to NICE. */
329 thread_set_nice (int nice UNUSED)
331 /* Not yet implemented. */
334 /* Returns the current thread's nice value. */
336 thread_get_nice (void)
338 /* Not yet implemented. */
342 /* Returns 100 times the system load average. */
344 thread_get_load_avg (void)
346 /* Not yet implemented. */
350 /* Returns 100 times the current thread's recent_cpu value. */
352 thread_get_recent_cpu (void)
354 /* Not yet implemented. */
358 /* Idle thread. Executes when no other thread is ready to run.
360 The idle thread is initially put on the ready list by
361 thread_start(). It will be scheduled once initially, at which
362 point it initializes idle_thread, "up"s the semaphore passed
363 to it to enable thread_start() to continue, and immediately
364 blocks. After that, the idle thread never appears in the
365 ready list. It is returned by next_thread_to_run() as a
366 special case when the ready list is empty. */
368 idle (void *idle_started_ UNUSED)
370 struct semaphore *idle_started = idle_started_;
371 idle_thread = thread_current ();
372 sema_up (idle_started);
376 /* Let someone else run. */
380 /* Re-enable interrupts and wait for the next one.
382 The `sti' instruction disables interrupts until the
383 completion of the next instruction, so these two
384 instructions are executed atomically. This atomicity is
385 important; otherwise, an interrupt could be handled
386 between re-enabling interrupts and waiting for the next
387 one to occur, wasting as much as one clock tick worth of
390 See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a]
391 7.11.1 "HLT Instruction". */
392 asm volatile ("sti; hlt" : : : "memory");
396 /* Function used as the basis for a kernel thread. */
398 kernel_thread (thread_func *function, void *aux)
400 ASSERT (function != NULL);
402 intr_enable (); /* The scheduler runs with interrupts off. */
403 function (aux); /* Execute the thread function. */
404 thread_exit (); /* If function() returns, kill the thread. */
407 /* Returns the running thread. */
409 running_thread (void)
413 /* Copy the CPU's stack pointer into `esp', and then round that
414 down to the start of a page. Because `struct thread' is
415 always at the beginning of a page and the stack pointer is
416 somewhere in the middle, this locates the curent thread. */
417 asm ("mov %%esp, %0" : "=g" (esp));
418 return pg_round_down (esp);
421 /* Returns true if T appears to point to a valid thread. */
423 is_thread (struct thread *t)
425 return t != NULL && t->magic == THREAD_MAGIC;
428 /* Does basic initialization of T as a blocked thread named
431 init_thread (struct thread *t, const char *name, int priority)
434 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
435 ASSERT (name != NULL);
437 memset (t, 0, sizeof *t);
438 t->status = THREAD_BLOCKED;
439 strlcpy (t->name, name, sizeof t->name);
440 t->stack = (uint8_t *) t + PGSIZE;
441 t->priority = priority;
442 t->magic = THREAD_MAGIC;
445 /* Allocates a SIZE-byte frame at the top of thread T's stack and
446 returns a pointer to the frame's base. */
448 alloc_frame (struct thread *t, size_t size)
450 /* Stack data is always allocated in word-size units. */
451 ASSERT (is_thread (t));
452 ASSERT (size % sizeof (uint32_t) == 0);
458 /* Chooses and returns the next thread to be scheduled. Should
459 return a thread from the run queue, unless the run queue is
460 empty. (If the running thread can continue running, then it
461 will be in the run queue.) If the run queue is empty, return
463 static struct thread *
464 next_thread_to_run (void)
466 if (list_empty (&ready_list))
469 return list_entry (list_pop_front (&ready_list), struct thread, elem);
472 /* Completes a thread switch by activating the new thread's page
473 tables, and, if the previous thread is dying, destroying it.
475 At this function's invocation, we just switched from thread
476 PREV, the new thread is already running, and interrupts are
477 still disabled. This function is normally invoked by
478 thread_schedule() as its final action before returning, but
479 the first time a thread is scheduled it is called by
480 switch_entry() (see switch.S).
482 It's not safe to call printf() until the thread switch is
483 complete. In practice that means that printf()s should be
484 added at the end of the function.
486 After this function and its caller returns, the thread switch
489 schedule_tail (struct thread *prev)
491 struct thread *cur = running_thread ();
493 ASSERT (intr_get_level () == INTR_OFF);
495 /* Mark us as running. */
496 cur->status = THREAD_RUNNING;
498 /* Start new time slice. */
502 /* Activate the new address space. */
506 /* If the thread we switched from is dying, destroy its struct
507 thread. This must happen late so that thread_exit() doesn't
508 pull out the rug under itself. (We don't free
509 initial_thread because its memory was not obtained via
511 if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread)
513 ASSERT (prev != cur);
514 palloc_free_page (prev);
518 /* Schedules a new process. At entry, interrupts must be off and
519 the running process's state must have been changed from
520 running to some other state. This function finds another
521 thread to run and switches to it.
523 It's not safe to call printf() until schedule_tail() has
528 struct thread *cur = running_thread ();
529 struct thread *next = next_thread_to_run ();
530 struct thread *prev = NULL;
532 ASSERT (intr_get_level () == INTR_OFF);
533 ASSERT (cur->status != THREAD_RUNNING);
534 ASSERT (is_thread (next));
537 prev = switch_threads (cur, next);
538 schedule_tail (prev);
541 /* Returns a tid to use for a new thread. */
545 static tid_t next_tid = 1;
548 lock_acquire (&tid_lock);
550 lock_release (&tid_lock);
555 /* Offset of `stack' member within `struct thread'.
556 Used by switch.S, which can't figure it out on its own. */
557 uint32_t thread_stack_ofs = offsetof (struct thread, stack);