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. Note that this is
63 possible only because the loader was careful to put the bottom
64 of the stack at a page boundary; it won't work in general.
65 Also initializes the run queue.
67 After calling this function, be sure to initialize the page
68 allocator before trying to create any threads with
73 ASSERT (intr_get_level () == INTR_OFF);
75 lock_init (&tid_lock, "tid");
76 list_init (&ready_list);
78 /* Set up a thread structure for the running thread. */
79 initial_thread = running_thread ();
80 init_thread (initial_thread, "main", PRI_DEFAULT);
81 initial_thread->status = THREAD_RUNNING;
82 initial_thread->tid = allocate_tid ();
85 /* Starts preemptive thread scheduling by enabling interrupts.
86 Also creates the idle thread. */
90 thread_create ("idle", PRI_DEFAULT, idle, NULL);
94 /* Called by the timer interrupt handler at each timer tick to
99 struct thread *t = thread_current ();
100 if (t == idle_thread)
103 else if (t->pagedir != NULL)
110 /* Prints thread statistics. */
112 thread_print_stats (void)
114 printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n",
115 idle_ticks, kernel_ticks, user_ticks);
118 /* Creates a new kernel thread named NAME with the given initial
119 PRIORITY, which executes FUNCTION passing AUX as the argument,
120 and adds it to the ready queue. If thread_start() has been
121 called, then the new thread may be scheduled before
122 thread_create() returns. It could even exit before
123 thread_create() returns. Use a semaphore or some other form
124 of synchronization if you need to ensure ordering. Returns
125 the thread identifier for the new thread, or TID_ERROR if
128 The code provided sets the new thread's `priority' member to
129 PRIORITY, but no actual priority scheduling is implemented.
130 Priority scheduling is the goal of Problem 1-3. */
132 thread_create (const char *name, int priority,
133 thread_func *function, void *aux)
136 struct kernel_thread_frame *kf;
137 struct switch_entry_frame *ef;
138 struct switch_threads_frame *sf;
141 ASSERT (function != NULL);
143 /* Allocate thread. */
144 t = palloc_get_page (PAL_ZERO);
148 /* Initialize thread. */
149 init_thread (t, name, priority);
150 tid = t->tid = allocate_tid ();
152 /* Stack frame for kernel_thread(). */
153 kf = alloc_frame (t, sizeof *kf);
155 kf->function = function;
158 /* Stack frame for switch_entry(). */
159 ef = alloc_frame (t, sizeof *ef);
160 ef->eip = (void (*) (void)) kernel_thread;
162 /* Stack frame for switch_threads(). */
163 sf = alloc_frame (t, sizeof *sf);
164 sf->eip = switch_entry;
166 /* Add to run queue. */
172 /* Transitions a blocked thread T from its current state to the
173 ready-to-run state. This is an error if T is not blocked.
174 (Use thread_yield() to make the running thread ready.) */
176 thread_unblock (struct thread *t)
178 enum intr_level old_level;
180 ASSERT (is_thread (t));
182 old_level = intr_disable ();
183 ASSERT (t->status == THREAD_BLOCKED);
184 list_push_back (&ready_list, &t->elem);
185 t->status = THREAD_READY;
186 intr_set_level (old_level);
189 /* Returns the name of the running thread. */
193 return thread_current ()->name;
196 /* Returns the running thread.
197 This is running_thread() plus a couple of sanity checks.
198 See the big comment at the top of thread.h for details. */
200 thread_current (void)
202 struct thread *t = running_thread ();
204 /* Make sure T is really a thread.
205 If either of these assertions fire, then your thread may
206 have overflowed its stack. Each thread has less than 4 kB
207 of stack, so a few big automatic arrays or moderate
208 recursion can cause stack overflow. */
209 ASSERT (is_thread (t));
210 ASSERT (t->status == THREAD_RUNNING);
215 /* Returns the running thread's tid. */
219 return thread_current ()->tid;
222 /* Deschedules the current thread and destroys it. Never
223 returns to the caller. */
227 ASSERT (!intr_context ());
233 /* Just set our status to dying and schedule another process.
234 We will be destroyed during the call to schedule_tail(). */
236 thread_current ()->status = THREAD_DYING;
241 /* Yields the CPU. The current thread is not put to sleep and
242 may be scheduled again immediately at the scheduler's whim. */
246 struct thread *cur = thread_current ();
247 enum intr_level old_level;
249 ASSERT (!intr_context ());
251 old_level = intr_disable ();
252 list_push_back (&ready_list, &cur->elem);
253 cur->status = THREAD_READY;
255 intr_set_level (old_level);
258 /* Puts the current thread to sleep. It will not be scheduled
259 again until awoken by thread_unblock().
261 This function must be called with interrupts turned off. It
262 is usually a better idea to use one of the synchronization
263 primitives in synch.h. */
267 ASSERT (!intr_context ());
268 ASSERT (intr_get_level () == INTR_OFF);
270 thread_current ()->status = THREAD_BLOCKED;
274 /* Idle thread. Executes when no other thread is ready to run. */
276 idle (void *aux UNUSED)
278 idle_thread = thread_current ();
282 /* Let someone else run. */
287 /* Use CPU `hlt' instruction to wait for interrupt. */
292 /* Function used as the basis for a kernel thread. */
294 kernel_thread (thread_func *function, void *aux)
296 ASSERT (function != NULL);
298 intr_enable (); /* The scheduler runs with interrupts off. */
299 function (aux); /* Execute the thread function. */
300 thread_exit (); /* If function() returns, kill the thread. */
303 /* Returns the running thread. */
305 running_thread (void)
309 /* Copy the CPU's stack pointer into `esp', and then round that
310 down to the start of a page. Because `struct thread' is
311 always at the beginning of a page and the stack pointer is
312 somewhere in the middle, this locates the curent thread. */
313 asm ("movl %%esp, %0\n" : "=g" (esp));
314 return pg_round_down (esp);
317 /* Returns true if T appears to point to a valid thread. */
319 is_thread (struct thread *t)
321 return t != NULL && t->magic == THREAD_MAGIC;
324 /* Does basic initialization of T as a blocked thread named
327 init_thread (struct thread *t, const char *name, int priority)
330 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
331 ASSERT (name != NULL);
333 memset (t, 0, sizeof *t);
334 t->status = THREAD_BLOCKED;
335 strlcpy (t->name, name, sizeof t->name);
336 t->stack = (uint8_t *) t + PGSIZE;
337 t->priority = priority;
338 t->magic = THREAD_MAGIC;
341 /* Allocates a SIZE-byte frame at the top of thread T's stack and
342 returns a pointer to the frame's base. */
344 alloc_frame (struct thread *t, size_t size)
346 /* Stack data is always allocated in word-size units. */
347 ASSERT (is_thread (t));
348 ASSERT (size % sizeof (uint32_t) == 0);
354 /* Chooses and returns the next thread to be scheduled. Should
355 return a thread from the run queue, unless the run queue is
356 empty. (If the running thread can continue running, then it
357 will be in the run queue.) If the run queue is empty, return
359 static struct thread *
360 next_thread_to_run (void)
362 if (list_empty (&ready_list))
365 return list_entry (list_pop_front (&ready_list), struct thread, elem);
368 /* Completes a thread switch by activating the new thread's page
369 tables, and, if the previous thread is dying, destroying it.
371 At this function's invocation, we just switched from thread
372 PREV, the new thread is already running, and interrupts are
373 still disabled. This function is normally invoked by
374 thread_schedule() as its final action before returning, but
375 the first time a thread is scheduled it is called by
376 switch_entry() (see switch.S).
378 After this function and its caller returns, the thread switch
381 schedule_tail (struct thread *prev)
383 struct thread *cur = running_thread ();
385 ASSERT (intr_get_level () == INTR_OFF);
387 /* Mark us as running. */
388 cur->status = THREAD_RUNNING;
391 /* Activate the new address space. */
395 /* If the thread we switched from is dying, destroy its struct
396 thread. This must happen late so that thread_exit() doesn't
397 pull out the rug under itself. */
398 if (prev != NULL && prev->status == THREAD_DYING)
400 ASSERT (prev != cur);
401 if (prev != initial_thread)
402 palloc_free_page (prev);
406 /* Schedules a new process. At entry, interrupts must be off and
407 the running process's state must have been changed from
408 running to some other state. This function finds another
409 thread to run and switches to it. */
413 struct thread *cur = running_thread ();
414 struct thread *next = next_thread_to_run ();
415 struct thread *prev = NULL;
417 ASSERT (intr_get_level () == INTR_OFF);
418 ASSERT (cur->status != THREAD_RUNNING);
419 ASSERT (is_thread (next));
422 prev = switch_threads (cur, next);
423 schedule_tail (prev);
426 /* Returns a tid to use for a new thread. */
430 static tid_t next_tid = 1;
433 lock_acquire (&tid_lock);
435 lock_release (&tid_lock);
440 /* Offset of `stack' member within `struct thread'.
441 Used by switch.S, which can't figure it out on its own. */
442 uint32_t thread_stack_ofs = offsetof (struct thread, stack);