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 schedule (void);
53 void schedule_tail (struct thread *prev);
54 static tid_t allocate_tid (void);
56 /* Initializes the threading system by transforming the code
57 that's currently running into a thread. Note that this is
58 possible only because the loader was careful to put the bottom
59 of the stack at a page boundary; it won't work in general.
60 Also initializes the run queue.
62 After calling this function, be sure to initialize the page
63 allocator before trying to create any threads with
68 ASSERT (intr_get_level () == INTR_OFF);
70 lock_init (&tid_lock, "tid");
71 list_init (&ready_list);
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 ();
80 /* Starts preemptive thread scheduling by enabling interrupts.
81 Also creates the idle thread. */
85 thread_create ("idle", PRI_DEFAULT, idle, NULL);
89 /* Creates a new kernel thread named NAME with the given initial
90 PRIORITY, which executes FUNCTION passing AUX as the argument,
91 and adds it to the ready queue. If thread_start() has been
92 called, then the new thread may be scheduled before
93 thread_create() returns. It could even exit before
94 thread_create() returns. Use a semaphore or some other form
95 of synchronization if you need to ensure ordering. Returns
96 the thread identifier for the new thread, or TID_ERROR if
99 The code provided sets the new thread's `priority' member to
100 PRIORITY, but no actual priority scheduling is implemented.
101 Priority scheduling is the goal of Problem 1-3. */
103 thread_create (const char *name, int priority,
104 thread_func *function, void *aux)
107 struct kernel_thread_frame *kf;
108 struct switch_entry_frame *ef;
109 struct switch_threads_frame *sf;
112 ASSERT (function != NULL);
114 /* Allocate thread. */
115 t = palloc_get (PAL_ZERO);
119 /* Initialize thread. */
120 init_thread (t, name, priority);
121 tid = t->tid = allocate_tid ();
123 /* Stack frame for kernel_thread(). */
124 kf = alloc_frame (t, sizeof *kf);
126 kf->function = function;
129 /* Stack frame for switch_entry(). */
130 ef = alloc_frame (t, sizeof *ef);
131 ef->eip = (void (*) (void)) kernel_thread;
133 /* Stack frame for switch_threads(). */
134 sf = alloc_frame (t, sizeof *sf);
135 sf->eip = switch_entry;
137 /* Add to run queue. */
143 /* Transitions a blocked thread T from its current state to the
144 ready-to-run state. This is an error if T is not blocked.
145 (Use thread_yield() to make the running thread ready.) */
147 thread_unblock (struct thread *t)
149 enum intr_level old_level;
151 ASSERT (is_thread (t));
153 old_level = intr_disable ();
154 ASSERT (t->status == THREAD_BLOCKED);
155 list_push_back (&ready_list, &t->elem);
156 t->status = THREAD_READY;
157 intr_set_level (old_level);
160 /* Returns the name of the running thread. */
164 return thread_current ()->name;
167 /* Returns the running thread.
168 This is running_thread() plus a couple of sanity checks.
169 See the big comment at the top of thread.h for details. */
171 thread_current (void)
173 struct thread *t = running_thread ();
175 /* Make sure T is really a thread.
176 If either of these assertions fire, then your thread may
177 have overflowed its stack. Each thread has less than 4 kB
178 of stack, so a few big automatic arrays or moderate
179 recursion can cause stack overflow. */
180 ASSERT (is_thread (t));
181 ASSERT (t->status == THREAD_RUNNING);
186 /* Returns the running thread's tid. */
190 return thread_current ()->tid;
193 /* Deschedules the current thread and destroys it. Never
194 returns to the caller. */
198 ASSERT (!intr_context ());
204 /* Just set our status to dying and schedule another process.
205 We will be destroyed during the call to schedule_tail(). */
207 thread_current ()->status = THREAD_DYING;
212 /* Yields the CPU. The current thread is not put to sleep and
213 may be scheduled again immediately at the scheduler's whim. */
217 struct thread *cur = thread_current ();
218 enum intr_level old_level;
220 ASSERT (!intr_context ());
222 old_level = intr_disable ();
223 list_push_back (&ready_list, &cur->elem);
224 cur->status = THREAD_READY;
226 intr_set_level (old_level);
229 /* Puts the current thread to sleep. It will not be scheduled
230 again until awoken by thread_unblock().
232 This function must be called with interrupts turned off. It
233 is usually a better idea to use one of the synchronization
234 primitives in synch.h. */
238 ASSERT (!intr_context ());
239 ASSERT (intr_get_level () == INTR_OFF);
241 thread_current ()->status = THREAD_BLOCKED;
245 /* Idle thread. Executes when no other thread is ready to run. */
247 idle (void *aux UNUSED)
249 idle_thread = thread_current ();
253 /* Let someone else run. */
258 /* Use CPU `hlt' instruction to wait for interrupt. */
263 /* Function used as the basis for a kernel thread. */
265 kernel_thread (thread_func *function, void *aux)
267 ASSERT (function != NULL);
269 intr_enable (); /* The scheduler runs with interrupts off. */
270 function (aux); /* Execute the thread function. */
271 thread_exit (); /* If function() returns, kill the thread. */
274 /* Returns the running thread. */
276 running_thread (void)
280 /* Copy the CPU's stack pointer into `esp', and then round that
281 down to the start of a page. Because `struct thread' is
282 always at the beginning of a page and the stack pointer is
283 somewhere in the middle, this locates the curent thread. */
284 asm ("movl %%esp, %0\n" : "=g" (esp));
285 return pg_round_down (esp);
288 /* Returns true if T appears to point to a valid thread. */
290 is_thread (struct thread *t)
292 return t != NULL && t->magic == THREAD_MAGIC;
295 /* Does basic initialization of T as a blocked thread named
298 init_thread (struct thread *t, const char *name, int priority)
301 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
302 ASSERT (name != NULL);
304 memset (t, 0, sizeof *t);
305 t->status = THREAD_BLOCKED;
306 strlcpy (t->name, name, sizeof t->name);
307 t->stack = (uint8_t *) t + PGSIZE;
308 t->priority = priority;
309 t->magic = THREAD_MAGIC;
312 /* Allocates a SIZE-byte frame at the top of thread T's stack and
313 returns a pointer to the frame's base. */
315 alloc_frame (struct thread *t, size_t size)
317 /* Stack data is always allocated in word-size units. */
318 ASSERT (is_thread (t));
319 ASSERT (size % sizeof (uint32_t) == 0);
325 /* Chooses and returns the next thread to be scheduled. Should
326 return a thread from the run queue, unless the run queue is
327 empty. (If the running thread can continue running, then it
328 will be in the run queue.) If the run queue is empty, return
330 static struct thread *
331 next_thread_to_run (void)
333 if (list_empty (&ready_list))
336 return list_entry (list_pop_front (&ready_list), struct thread, elem);
339 /* Completes a thread switch by activating the new thread's page
340 tables, and, if the previous thread is dying, destroying it.
342 At this function's invocation, we just switched from thread
343 PREV, the new thread is already running, and interrupts are
344 still disabled. This function is normally invoked by
345 thread_schedule() as its final action before returning, but
346 the first time a thread is scheduled it is called by
347 switch_entry() (see switch.S).
349 After this function and its caller returns, the thread switch
352 schedule_tail (struct thread *prev)
354 struct thread *cur = running_thread ();
356 ASSERT (intr_get_level () == INTR_OFF);
358 /* Mark us as running. */
359 cur->status = THREAD_RUNNING;
362 /* Activate the new address space. */
366 /* If the thread we switched from is dying, destroy its struct
367 thread. This must happen late so that thread_exit() doesn't
368 pull out the rug under itself. */
369 if (prev != NULL && prev->status == THREAD_DYING)
371 ASSERT (prev != cur);
372 if (prev != initial_thread)
377 /* Schedules a new process. At entry, interrupts must be off and
378 the running process's state must have been changed from
379 running to some other state. This function finds another
380 thread to run and switches to it. */
384 struct thread *cur = running_thread ();
385 struct thread *next = next_thread_to_run ();
386 struct thread *prev = NULL;
388 ASSERT (intr_get_level () == INTR_OFF);
389 ASSERT (cur->status != THREAD_RUNNING);
390 ASSERT (is_thread (next));
393 prev = switch_threads (cur, next);
394 schedule_tail (prev);
397 /* Returns a tid to use for a new thread. */
401 static tid_t next_tid = 1;
404 lock_acquire (&tid_lock);
406 lock_release (&tid_lock);
411 /* Offset of `stack' member within `struct thread'.
412 Used by switch.S, which can't figure it out on its own. */
413 uint32_t thread_stack_ofs = offsetof (struct thread, stack);