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"
16 #include "userprog/gdt.h"
19 /* Random value for struct thread's `magic' member.
20 Used to detect stack overflow. See the big comment at the top
21 of thread.h for details. */
22 #define THREAD_MAGIC 0xcd6abf4b
24 /* List of processes in THREAD_READY state, that is, processes
25 that are ready to run but not actually running. */
26 static struct list ready_list;
29 static struct thread *idle_thread;
31 /* Initial thread, the thread running init.c:main(). */
32 static struct thread *initial_thread;
34 /* Lock used by allocate_tid(). */
35 static struct lock tid_lock;
37 /* Stack frame for kernel_thread(). */
38 struct kernel_thread_frame
40 void *eip; /* Return address. */
41 thread_func *function; /* Function to call. */
42 void *aux; /* Auxiliary data for function. */
45 static void kernel_thread (thread_func *, void *aux);
47 static void idle (void *aux UNUSED);
48 static struct thread *running_thread (void);
49 static struct thread *next_thread_to_run (void);
50 static struct thread *new_thread (const char *name, int priority);
51 static void init_thread (struct thread *, const char *name, int priority);
52 static bool is_thread (struct thread *);
53 static void *alloc_frame (struct thread *, size_t size);
54 static void destroy_thread (struct thread *);
55 static void schedule (void);
56 void schedule_tail (struct thread *prev);
57 static tid_t allocate_tid (void);
59 /* Initializes the threading system by transforming the code
60 that's currently running into a thread. Note that this is
61 possible only because the loader was careful to put the bottom
62 of the stack at a page boundary; it won't work in general.
63 Also initializes the run queue.
65 After calling this function, be sure to initialize the page
66 allocator before trying to create any threads with
71 ASSERT (intr_get_level () == INTR_OFF);
73 lock_init (&tid_lock, "tid");
75 /* Set up a thread structure for the running thread. */
76 initial_thread = running_thread ();
77 init_thread (initial_thread, "main", PRI_DEFAULT);
78 initial_thread->status = THREAD_RUNNING;
79 initial_thread->tid = allocate_tid ();
81 /* Initialize run queue. */
82 list_init (&ready_list);
85 /* Starts preemptive thread scheduling by enabling interrupts.
86 Also creates the idle thread. */
90 thread_create ("idle", PRI_DEFAULT, idle, NULL);
94 /* Creates a new kernel thread named NAME with the given initial
95 PRIORITY, which executes FUNCTION passing AUX as the argument,
96 and adds it to the ready queue. If thread_start() has been
97 called, then the new thread may be scheduled before
98 thread_create() returns. It could even exit before
99 thread_create() returns. Use a semaphore or some other form
100 of synchronization if you need to ensure ordering. Returns
101 the thread identifier for the new thread, or TID_ERROR if
104 The code provided sets the new thread's `priority' member to
105 PRIORITY, but no actual priority scheduling is implemented.
106 Priority scheduling is the goal of Problem 1-3. */
108 thread_create (const char *name, int priority,
109 thread_func *function, void *aux)
112 struct kernel_thread_frame *kf;
113 struct switch_entry_frame *ef;
114 struct switch_threads_frame *sf;
117 ASSERT (function != NULL);
119 t = new_thread (name, priority);
124 /* Stack frame for kernel_thread(). */
125 kf = alloc_frame (t, sizeof *kf);
127 kf->function = function;
130 /* Stack frame for switch_entry(). */
131 ef = alloc_frame (t, sizeof *ef);
132 ef->eip = (void (*) (void)) kernel_thread;
134 /* Stack frame for switch_threads(). */
135 sf = alloc_frame (t, sizeof *sf);
136 sf->eip = switch_entry;
138 /* Add to run queue. */
144 /* Transitions a blocked thread T from its current state to the
145 ready-to-run state. This is an error if T is not blocked.
146 (Use thread_yield() to make the running thread ready.) */
148 thread_unblock (struct thread *t)
150 enum intr_level old_level;
152 ASSERT (is_thread (t));
154 old_level = intr_disable ();
155 ASSERT (t->status == THREAD_BLOCKED);
156 list_push_back (&ready_list, &t->elem);
157 t->status = THREAD_READY;
158 intr_set_level (old_level);
161 /* Returns the name of the running thread. */
165 return thread_current ()->name;
168 /* Returns the running thread.
169 This is running_thread() plus a couple of sanity checks.
170 See the big comment at the top of thread.h for details. */
172 thread_current (void)
174 struct thread *t = running_thread ();
176 /* Make sure T is really a thread.
177 If either of these assertions fire, then your thread may
178 have overflowed its stack. Each thread has less than 4 kB
179 of stack, so a few big automatic arrays or moderate
180 recursion can cause stack overflow. */
181 ASSERT (is_thread (t));
182 ASSERT (t->status == THREAD_RUNNING);
187 /* Returns the running thread's tid. */
191 return thread_current ()->tid;
194 /* Deschedules the current thread and destroys it. Never
195 returns to the caller. */
199 ASSERT (!intr_context ());
201 /* Just set our status to dying and schedule another process.
202 We will be destroyed during the call to schedule_tail(). */
204 thread_current ()->status = THREAD_DYING;
209 /* Yields the CPU. The current thread is not put to sleep and
210 may be scheduled again immediately at the scheduler's whim. */
214 struct thread *cur = thread_current ();
215 enum intr_level old_level;
217 ASSERT (!intr_context ());
219 old_level = intr_disable ();
220 list_push_back (&ready_list, &cur->elem);
221 cur->status = THREAD_READY;
223 intr_set_level (old_level);
226 /* Puts the current thread to sleep. It will not be scheduled
227 again until awoken by thread_unblock().
229 This function must be called with interrupts turned off. It
230 is usually a better idea to use one of the synchronization
231 primitives in synch.h. */
235 ASSERT (!intr_context ());
236 ASSERT (intr_get_level () == INTR_OFF);
238 thread_current ()->status = THREAD_BLOCKED;
242 /* Idle thread. Executes when no other thread is ready to run. */
244 idle (void *aux UNUSED)
246 idle_thread = thread_current ();
250 /* Let someone else run. */
255 /* Use CPU `hlt' instruction to wait for interrupt. */
260 /* Function used as the basis for a kernel thread. */
262 kernel_thread (thread_func *function, void *aux)
264 ASSERT (function != NULL);
266 intr_enable (); /* The scheduler runs with interrupts off. */
267 function (aux); /* Execute the thread function. */
268 thread_exit (); /* If function() returns, kill the thread. */
271 /* Returns the running thread. */
273 running_thread (void)
277 /* Copy the CPU's stack pointer into `esp', and then round that
278 down to the start of a page. Because `struct thread' is
279 always at the beginning of a page and the stack pointer is
280 somewhere in the middle, this locates the curent thread. */
281 asm ("movl %%esp, %0\n" : "=g" (esp));
282 return pg_round_down (esp);
285 /* Returns true if T appears to point to a valid thread. */
287 is_thread (struct thread *t)
289 return t != NULL && t->magic == THREAD_MAGIC;
292 /* Creates a new thread named NAME as a child of the running
293 thread. Returns the new thread if successful or a null
294 pointer on failure. */
295 static struct thread *
296 new_thread (const char *name, int priority)
298 struct thread *t = palloc_get (PAL_ZERO);
301 init_thread (t, name, priority);
302 t->tid = allocate_tid ();
308 /* Does basic initialization of T as a blocked thread named
311 init_thread (struct thread *t, const char *name, int priority)
314 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
315 ASSERT (name != NULL);
317 memset (t, 0, sizeof *t);
318 t->status = THREAD_BLOCKED;
319 strlcpy (t->name, name, sizeof t->name);
320 t->stack = (uint8_t *) t + PGSIZE;
321 t->priority = priority;
322 t->magic = THREAD_MAGIC;
325 /* Allocates a SIZE-byte frame at the top of thread T's stack and
326 returns a pointer to the frame's base. */
328 alloc_frame (struct thread *t, size_t size)
330 /* Stack data is always allocated in word-size units. */
331 ASSERT (is_thread (t));
332 ASSERT (size % sizeof (uint32_t) == 0);
338 /* Chooses and returns the next thread to be scheduled. Should
339 return a thread from the run queue, unless the run queue is
340 empty. (If the running thread can continue running, then it
341 will be in the run queue.) If the run queue is empty, return
343 static struct thread *
344 next_thread_to_run (void)
346 if (list_empty (&ready_list))
349 return list_entry (list_pop_front (&ready_list), struct thread, elem);
352 /* Destroys T, which must not be the running thread. */
354 destroy_thread (struct thread *t)
356 ASSERT (is_thread (t));
357 ASSERT (t != thread_current ());
362 if (t != initial_thread)
366 /* Completes a thread switch by activating the new thread's page
367 tables, and, if the previous thread is dying, destroying it.
369 At this function's invocation, we just switched from thread
370 PREV, the new thread is already running, and interrupts are
371 still disabled. This function is normally invoked by
372 thread_schedule() as its final action before returning, but
373 the first time a thread is scheduled it is called by
374 switch_entry() (see switch.S).
376 After this function and its caller returns, the thread switch
379 schedule_tail (struct thread *prev)
381 struct thread *cur = running_thread ();
383 ASSERT (intr_get_level () == INTR_OFF);
385 /* Mark us as running. */
386 cur->status = THREAD_RUNNING;
389 /* Activate the new address space. */
393 /* If the thread we switched from is dying, destroy it.
394 This must happen late because it's not a good idea to
395 e.g. destroy the page table you're currently using. */
396 if (prev != NULL && prev->status == THREAD_DYING)
397 destroy_thread (prev);
400 /* Schedules a new process. At entry, interrupts must be off and
401 the running process's state must have been changed from
402 running to some other state. This function finds another
403 thread to run and switches to it. */
407 struct thread *cur = running_thread ();
408 struct thread *next = next_thread_to_run ();
409 struct thread *prev = NULL;
411 ASSERT (intr_get_level () == INTR_OFF);
412 ASSERT (cur->status != THREAD_RUNNING);
413 ASSERT (is_thread (next));
416 prev = switch_threads (cur, next);
417 schedule_tail (prev);
420 /* Returns a tid to use for a new thread. */
424 static tid_t next_tid = 1;
427 lock_acquire (&tid_lock);
429 lock_release (&tid_lock);
434 /* Offset of `stack' member within `struct thread'.
435 Used by switch.S, which can't figure it out on its own. */
436 uint32_t thread_stack_ofs = offsetof (struct thread, stack);