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. If thread_start() has been
122 called, then the new thread may be scheduled before
123 thread_create() returns. It could even exit before
124 thread_create() returns. Use a semaphore or some other form
125 of synchronization if you need to ensure ordering. Returns
126 the thread identifier for the new thread, or TID_ERROR if
129 The code provided sets the new thread's `priority' member to
130 PRIORITY, but no actual priority scheduling is implemented.
131 Priority scheduling is the goal of Problem 1-3. */
133 thread_create (const char *name, int priority,
134 thread_func *function, void *aux)
137 struct kernel_thread_frame *kf;
138 struct switch_entry_frame *ef;
139 struct switch_threads_frame *sf;
142 ASSERT (function != NULL);
144 /* Allocate thread. */
145 t = palloc_get_page (PAL_ZERO);
149 /* Initialize thread. */
150 init_thread (t, name, priority);
151 tid = t->tid = allocate_tid ();
153 /* Stack frame for kernel_thread(). */
154 kf = alloc_frame (t, sizeof *kf);
156 kf->function = function;
159 /* Stack frame for switch_entry(). */
160 ef = alloc_frame (t, sizeof *ef);
161 ef->eip = (void (*) (void)) kernel_thread;
163 /* Stack frame for switch_threads(). */
164 sf = alloc_frame (t, sizeof *sf);
165 sf->eip = switch_entry;
167 /* Add to run queue. */
173 /* Puts the current thread to sleep. It will not be scheduled
174 again until awoken by thread_unblock().
176 This function must be called with interrupts turned off. It
177 is usually a better idea to use one of the synchronization
178 primitives in synch.h. */
182 ASSERT (!intr_context ());
183 ASSERT (intr_get_level () == INTR_OFF);
185 thread_current ()->status = THREAD_BLOCKED;
189 /* Transitions a blocked thread T to the ready-to-run state.
190 This is an error if T is not blocked. (Use thread_yield() to
191 make the running thread ready.) */
193 thread_unblock (struct thread *t)
195 enum intr_level old_level;
197 ASSERT (is_thread (t));
199 old_level = intr_disable ();
200 ASSERT (t->status == THREAD_BLOCKED);
201 list_push_back (&ready_list, &t->elem);
202 t->status = THREAD_READY;
203 intr_set_level (old_level);
206 /* Returns the name of the running thread. */
210 return thread_current ()->name;
213 /* Returns the running thread.
214 This is running_thread() plus a couple of sanity checks.
215 See the big comment at the top of thread.h for details. */
217 thread_current (void)
219 struct thread *t = running_thread ();
221 /* Make sure T is really a thread.
222 If either of these assertions fire, then your thread may
223 have overflowed its stack. Each thread has less than 4 kB
224 of stack, so a few big automatic arrays or moderate
225 recursion can cause stack overflow. */
226 ASSERT (is_thread (t));
227 ASSERT (t->status == THREAD_RUNNING);
232 /* Returns the running thread's tid. */
236 return thread_current ()->tid;
239 /* Deschedules the current thread and destroys it. Never
240 returns to the caller. */
244 ASSERT (!intr_context ());
250 /* Just set our status to dying and schedule another process.
251 We will be destroyed during the call to schedule_tail(). */
253 thread_current ()->status = THREAD_DYING;
258 /* Yields the CPU. The current thread is not put to sleep and
259 may be scheduled again immediately at the scheduler's whim. */
263 struct thread *cur = thread_current ();
264 enum intr_level old_level;
266 ASSERT (!intr_context ());
268 old_level = intr_disable ();
269 list_push_back (&ready_list, &cur->elem);
270 cur->status = THREAD_READY;
272 intr_set_level (old_level);
275 /* Idle thread. Executes when no other thread is ready to run. */
277 idle (void *aux UNUSED)
279 idle_thread = thread_current ();
283 /* Let someone else run. */
288 /* Use CPU `hlt' instruction to wait for interrupt. */
293 /* Function used as the basis for a kernel thread. */
295 kernel_thread (thread_func *function, void *aux)
297 ASSERT (function != NULL);
299 intr_enable (); /* The scheduler runs with interrupts off. */
300 function (aux); /* Execute the thread function. */
301 thread_exit (); /* If function() returns, kill the thread. */
304 /* Returns the running thread. */
306 running_thread (void)
310 /* Copy the CPU's stack pointer into `esp', and then round that
311 down to the start of a page. Because `struct thread' is
312 always at the beginning of a page and the stack pointer is
313 somewhere in the middle, this locates the curent thread. */
314 asm ("movl %%esp, %0\n" : "=g" (esp));
315 return pg_round_down (esp);
318 /* Returns true if T appears to point to a valid thread. */
320 is_thread (struct thread *t)
322 return t != NULL && t->magic == THREAD_MAGIC;
325 /* Does basic initialization of T as a blocked thread named
328 init_thread (struct thread *t, const char *name, int priority)
331 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
332 ASSERT (name != NULL);
334 memset (t, 0, sizeof *t);
335 t->status = THREAD_BLOCKED;
336 strlcpy (t->name, name, sizeof t->name);
337 t->stack = (uint8_t *) t + PGSIZE;
338 t->priority = priority;
339 t->magic = THREAD_MAGIC;
342 /* Allocates a SIZE-byte frame at the top of thread T's stack and
343 returns a pointer to the frame's base. */
345 alloc_frame (struct thread *t, size_t size)
347 /* Stack data is always allocated in word-size units. */
348 ASSERT (is_thread (t));
349 ASSERT (size % sizeof (uint32_t) == 0);
355 /* Chooses and returns the next thread to be scheduled. Should
356 return a thread from the run queue, unless the run queue is
357 empty. (If the running thread can continue running, then it
358 will be in the run queue.) If the run queue is empty, return
360 static struct thread *
361 next_thread_to_run (void)
363 if (list_empty (&ready_list))
366 return list_entry (list_pop_front (&ready_list), struct thread, elem);
369 /* Completes a thread switch by activating the new thread's page
370 tables, and, if the previous thread is dying, destroying it.
372 At this function's invocation, we just switched from thread
373 PREV, the new thread is already running, and interrupts are
374 still disabled. This function is normally invoked by
375 thread_schedule() as its final action before returning, but
376 the first time a thread is scheduled it is called by
377 switch_entry() (see switch.S).
379 It's not safe to call printf() until the thread switch is
380 complete. In practice that means that printf()s should be
381 added at the end of the function.
383 After this function and its caller returns, the thread switch
386 schedule_tail (struct thread *prev)
388 struct thread *cur = running_thread ();
390 ASSERT (intr_get_level () == INTR_OFF);
392 /* Mark us as running. */
393 cur->status = THREAD_RUNNING;
396 /* Activate the new address space. */
400 /* If the thread we switched from is dying, destroy its struct
401 thread. This must happen late so that thread_exit() doesn't
402 pull out the rug under itself. */
403 if (prev != NULL && prev->status == THREAD_DYING)
405 ASSERT (prev != cur);
406 if (prev != initial_thread)
407 palloc_free_page (prev);
411 /* Schedules a new process. At entry, interrupts must be off and
412 the running process's state must have been changed from
413 running to some other state. This function finds another
414 thread to run and switches to it.
416 It's not safe to call printf() until schedule_tail() has
421 struct thread *cur = running_thread ();
422 struct thread *next = next_thread_to_run ();
423 struct thread *prev = NULL;
425 ASSERT (intr_get_level () == INTR_OFF);
426 ASSERT (cur->status != THREAD_RUNNING);
427 ASSERT (is_thread (next));
430 prev = switch_threads (cur, next);
431 schedule_tail (prev);
434 /* Returns a tid to use for a new thread. */
438 static tid_t next_tid = 1;
441 lock_acquire (&tid_lock);
443 lock_release (&tid_lock);
448 /* Offset of `stack' member within `struct thread'.
449 Used by switch.S, which can't figure it out on its own. */
450 uint32_t thread_stack_ofs = offsetof (struct thread, stack);