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. */
44 static void kernel_thread (thread_func *, void *aux);
46 static void idle (void *aux UNUSED);
47 static struct thread *running_thread (void);
48 static struct thread *next_thread_to_run (void);
49 static void init_thread (struct thread *, const char *name, int priority);
50 static bool is_thread (struct thread *);
51 static void *alloc_frame (struct thread *, size_t size);
52 static void destroy_thread (struct thread *);
53 static void schedule (void);
54 void schedule_tail (struct thread *prev);
55 static tid_t allocate_tid (void);
57 /* Initializes the threading system by transforming the code
58 that's currently running into a thread. Note that this is
59 possible only because the loader was careful to put the bottom
60 of the stack at a page boundary; it won't work in general.
61 Also initializes the run queue.
63 After calling this function, be sure to initialize the page
64 allocator before trying to create any threads with
69 ASSERT (intr_get_level () == INTR_OFF);
71 lock_init (&tid_lock, "tid");
73 /* Set up a thread structure for the running thread. */
74 initial_thread = running_thread ();
75 init_thread (initial_thread, "main", PRI_DEFAULT);
76 initial_thread->status = THREAD_RUNNING;
77 initial_thread->tid = allocate_tid ();
79 /* Initialize run queue. */
80 list_init (&ready_list);
83 /* Starts preemptive thread scheduling by enabling interrupts.
84 Also creates the idle thread. */
88 thread_create ("idle", PRI_DEFAULT, idle, NULL);
92 /* Creates a new kernel thread named NAME with the given initial
93 PRIORITY, which executes FUNCTION passing AUX as the argument,
94 and adds it to the ready queue. If thread_start() has been
95 called, then the new thread may be scheduled before
96 thread_create() returns. It could even exit before
97 thread_create() returns. Use a semaphore or some other form
98 of synchronization if you need to ensure ordering. Returns
99 the thread identifier for the new thread, or TID_ERROR if
102 The code provided sets the new thread's `priority' member to
103 PRIORITY, but no actual priority scheduling is implemented.
104 Priority scheduling is the goal of Problem 1-3. */
106 thread_create (const char *name, int priority,
107 thread_func *function, void *aux)
110 struct kernel_thread_frame *kf;
111 struct switch_entry_frame *ef;
112 struct switch_threads_frame *sf;
115 ASSERT (function != NULL);
117 /* Allocate thread. */
118 t = palloc_get (PAL_ZERO);
122 /* Initialize thread. */
123 init_thread (t, name, priority);
124 tid = t->tid = allocate_tid ();
126 /* Stack frame for kernel_thread(). */
127 kf = alloc_frame (t, sizeof *kf);
129 kf->function = function;
132 /* Stack frame for switch_entry(). */
133 ef = alloc_frame (t, sizeof *ef);
134 ef->eip = (void (*) (void)) kernel_thread;
136 /* Stack frame for switch_threads(). */
137 sf = alloc_frame (t, sizeof *sf);
138 sf->eip = switch_entry;
140 /* Add to run queue. */
146 /* Transitions a blocked thread T from its current state to the
147 ready-to-run state. This is an error if T is not blocked.
148 (Use thread_yield() to make the running thread ready.) */
150 thread_unblock (struct thread *t)
152 enum intr_level old_level;
154 ASSERT (is_thread (t));
156 old_level = intr_disable ();
157 ASSERT (t->status == THREAD_BLOCKED);
158 list_push_back (&ready_list, &t->elem);
159 t->status = THREAD_READY;
160 intr_set_level (old_level);
163 /* Returns the name of the running thread. */
167 return thread_current ()->name;
170 /* Returns the running thread.
171 This is running_thread() plus a couple of sanity checks.
172 See the big comment at the top of thread.h for details. */
174 thread_current (void)
176 struct thread *t = running_thread ();
178 /* Make sure T is really a thread.
179 If either of these assertions fire, then your thread may
180 have overflowed its stack. Each thread has less than 4 kB
181 of stack, so a few big automatic arrays or moderate
182 recursion can cause stack overflow. */
183 ASSERT (is_thread (t));
184 ASSERT (t->status == THREAD_RUNNING);
189 /* Returns the running thread's tid. */
193 return thread_current ()->tid;
196 /* Deschedules the current thread and destroys it. Never
197 returns to the caller. */
201 ASSERT (!intr_context ());
203 /* Just set our status to dying and schedule another process.
204 We will be destroyed during the call to schedule_tail(). */
206 thread_current ()->status = THREAD_DYING;
211 /* Yields the CPU. The current thread is not put to sleep and
212 may be scheduled again immediately at the scheduler's whim. */
216 struct thread *cur = thread_current ();
217 enum intr_level old_level;
219 ASSERT (!intr_context ());
221 old_level = intr_disable ();
222 list_push_back (&ready_list, &cur->elem);
223 cur->status = THREAD_READY;
225 intr_set_level (old_level);
228 /* Puts the current thread to sleep. It will not be scheduled
229 again until awoken by thread_unblock().
231 This function must be called with interrupts turned off. It
232 is usually a better idea to use one of the synchronization
233 primitives in synch.h. */
237 ASSERT (!intr_context ());
238 ASSERT (intr_get_level () == INTR_OFF);
240 thread_current ()->status = THREAD_BLOCKED;
244 /* Idle thread. Executes when no other thread is ready to run. */
246 idle (void *aux UNUSED)
248 idle_thread = thread_current ();
252 /* Let someone else run. */
257 /* Use CPU `hlt' instruction to wait for interrupt. */
262 /* Function used as the basis for a kernel thread. */
264 kernel_thread (thread_func *function, void *aux)
266 ASSERT (function != NULL);
268 intr_enable (); /* The scheduler runs with interrupts off. */
269 function (aux); /* Execute the thread function. */
270 thread_exit (); /* If function() returns, kill the thread. */
273 /* Returns the running thread. */
275 running_thread (void)
279 /* Copy the CPU's stack pointer into `esp', and then round that
280 down to the start of a page. Because `struct thread' is
281 always at the beginning of a page and the stack pointer is
282 somewhere in the middle, this locates the curent thread. */
283 asm ("movl %%esp, %0\n" : "=g" (esp));
284 return pg_round_down (esp);
287 /* Returns true if T appears to point to a valid thread. */
289 is_thread (struct thread *t)
291 return t != NULL && t->magic == THREAD_MAGIC;
294 /* Does basic initialization of T as a blocked thread named
297 init_thread (struct thread *t, const char *name, int priority)
300 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
301 ASSERT (name != NULL);
303 memset (t, 0, sizeof *t);
304 t->status = THREAD_BLOCKED;
305 strlcpy (t->name, name, sizeof t->name);
306 t->stack = (uint8_t *) t + PGSIZE;
307 t->priority = priority;
308 t->magic = THREAD_MAGIC;
311 /* Allocates a SIZE-byte frame at the top of thread T's stack and
312 returns a pointer to the frame's base. */
314 alloc_frame (struct thread *t, size_t size)
316 /* Stack data is always allocated in word-size units. */
317 ASSERT (is_thread (t));
318 ASSERT (size % sizeof (uint32_t) == 0);
324 /* Chooses and returns the next thread to be scheduled. Should
325 return a thread from the run queue, unless the run queue is
326 empty. (If the running thread can continue running, then it
327 will be in the run queue.) If the run queue is empty, return
329 static struct thread *
330 next_thread_to_run (void)
332 if (list_empty (&ready_list))
335 return list_entry (list_pop_front (&ready_list), struct thread, elem);
338 /* Destroys T, which must not be the running thread. */
340 destroy_thread (struct thread *t)
342 ASSERT (is_thread (t));
343 ASSERT (t != thread_current ());
348 if (t != initial_thread)
352 /* Completes a thread switch by activating the new thread's page
353 tables, and, if the previous thread is dying, destroying it.
355 At this function's invocation, we just switched from thread
356 PREV, the new thread is already running, and interrupts are
357 still disabled. This function is normally invoked by
358 thread_schedule() as its final action before returning, but
359 the first time a thread is scheduled it is called by
360 switch_entry() (see switch.S).
362 After this function and its caller returns, the thread switch
365 schedule_tail (struct thread *prev)
367 struct thread *cur = running_thread ();
369 ASSERT (intr_get_level () == INTR_OFF);
371 /* Mark us as running. */
372 cur->status = THREAD_RUNNING;
375 /* Activate the new address space. */
379 /* If the thread we switched from is dying, destroy it.
380 This must happen late because it's not a good idea to
381 e.g. destroy the page table you're currently using. */
382 if (prev != NULL && prev->status == THREAD_DYING)
383 destroy_thread (prev);
386 /* Schedules a new process. At entry, interrupts must be off and
387 the running process's state must have been changed from
388 running to some other state. This function finds another
389 thread to run and switches to it. */
393 struct thread *cur = running_thread ();
394 struct thread *next = next_thread_to_run ();
395 struct thread *prev = NULL;
397 ASSERT (intr_get_level () == INTR_OFF);
398 ASSERT (cur->status != THREAD_RUNNING);
399 ASSERT (is_thread (next));
402 prev = switch_threads (cur, next);
403 schedule_tail (prev);
406 /* Returns a tid to use for a new thread. */
410 static tid_t next_tid = 1;
413 lock_acquire (&tid_lock);
415 lock_release (&tid_lock);
420 /* Offset of `stack' member within `struct thread'.
421 Used by switch.S, which can't figure it out on its own. */
422 uint32_t thread_stack_ofs = offsetof (struct thread, stack);