1 #include "threads/thread.h"
6 #include "threads/interrupt.h"
7 #include "threads/intr-stubs.h"
8 #include "threads/mmu.h"
9 #include "threads/palloc.h"
10 #include "threads/switch.h"
12 #include "userprog/gdt.h"
15 /* Value for struct thread's `magic' member.
16 Used to detect stack overflow. See the big comment at the top
17 of thread.h for details. */
18 #define THREAD_MAGIC 0x1234abcdu
20 /* List of processes in THREAD_READY state, that is, processes
21 that are ready to run but not actually running. */
22 static struct list ready_list;
25 static struct thread *idle_thread; /* Thread. */
26 static void idle (void *aux UNUSED); /* Thread function. */
28 /* Stack frame for kernel_thread(). */
29 struct kernel_thread_frame
31 void *eip; /* Return address. */
32 thread_func *function; /* Function to call. */
33 void *aux; /* Auxiliary data for function. */
36 static void kernel_thread (thread_func *, void *aux);
38 static struct thread *running_thread (void);
39 static struct thread *next_thread_to_run (void);
40 static struct thread *new_thread (const char *name);
41 static void init_thread (struct thread *, const char *name);
42 static bool is_thread (struct thread *);
43 static void *alloc_frame (struct thread *, size_t size);
44 static void destroy_thread (struct thread *);
45 static void schedule (void);
46 void schedule_tail (struct thread *prev);
48 /* Initializes the threading system by transforming the code
49 that's currently running into a thread. Note that this is
50 possible only because the loader was careful to put the bottom
51 of the stack at a page boundary; it won't work in general.
52 Also initializes the run queue.
54 After calling this function, be sure to initialize the page
55 allocator before trying to create any threads with
62 ASSERT (intr_get_level () == INTR_OFF);
64 /* Set up a thread structure for the running thread. */
65 t = running_thread ();
66 init_thread (t, "main");
67 t->status = THREAD_RUNNING;
69 /* Initialize run queue. */
70 list_init (&ready_list);
73 /* Starts preemptive thread scheduling by enabling interrupts.
74 Also creates the idle thread. */
78 /* Create idle thread. */
79 idle_thread = thread_create ("idle", idle, NULL);
80 idle_thread->status = THREAD_BLOCKED;
82 /* Enable interrupts. */
86 /* Creates a new kernel thread named NAME, which executes
87 FUNCTION passing AUX as the argument, and adds it to the ready
88 queue. If thread_start() has been called, then the new thread
89 may be scheduled before thread_create() returns. Use a
90 semaphore or some other form of synchronization if you need to
93 thread_create (const char *name, thread_func *function, void *aux)
96 struct kernel_thread_frame *kf;
97 struct switch_entry_frame *ef;
98 struct switch_threads_frame *sf;
100 ASSERT (function != NULL);
102 t = new_thread (name);
104 /* Stack frame for kernel_thread(). */
105 kf = alloc_frame (t, sizeof *kf);
107 kf->function = function;
110 /* Stack frame for switch_entry(). */
111 ef = alloc_frame (t, sizeof *ef);
112 ef->eip = (void (*) (void)) kernel_thread;
114 /* Stack frame for switch_threads(). */
115 sf = alloc_frame (t, sizeof *sf);
116 sf->eip = switch_entry;
118 /* Add to run queue. */
125 /* Starts a new thread running a user program loaded from
126 FILENAME, and adds it to the ready queue. If thread_start()
127 has been called, then new thread may be scheduled before
128 thread_execute() returns.*/
130 thread_execute (const char *filename)
133 struct intr_frame *if_;
134 struct switch_entry_frame *ef;
135 struct switch_threads_frame *sf;
136 void (*start) (void);
138 ASSERT (filename != NULL);
140 t = new_thread (filename);
144 if (!addrspace_load (t, filename, &start))
145 PANIC ("%s: program load failed", filename);
147 /* Interrupt frame. */
148 if_ = alloc_frame (t, sizeof *if_);
153 if_->eflags = FLAG_IF | FLAG_MBS;
154 if_->esp = PHYS_BASE;
157 /* Stack frame for switch_entry(). */
158 ef = alloc_frame (t, sizeof *ef);
161 /* Stack frame for switch_threads(). */
162 sf = alloc_frame (t, sizeof *sf);
163 sf->eip = switch_entry;
165 /* Add to run queue. */
172 /* Transitions a blocked thread T from its current state to the
173 ready-to-run state. If T is not blocked, there is no effect.
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 if (t->status == THREAD_BLOCKED)
185 list_push_back (&ready_list, &t->elem);
186 t->status = THREAD_READY;
188 intr_set_level (old_level);
191 /* Returns the name of thread T. */
193 thread_name (struct thread *t)
195 ASSERT (is_thread (t));
199 /* Returns the running thread.
200 This is running_thread() plus a couple of sanity checks.
201 See the big comment at the top of thread.h for details. */
203 thread_current (void)
205 struct thread *t = running_thread ();
207 /* Make sure T is really a thread.
208 If either of these assertions fire, then your thread may
209 have overflowed its stack. Each thread has less than 4 kB
210 of stack, so a few big automatic arrays or moderate
211 recursion can cause stack overflow. */
212 ASSERT (is_thread (t));
213 ASSERT (t->status == THREAD_RUNNING);
218 /* Deschedules the current thread and destroys it. Never
219 returns to the caller. */
223 ASSERT (!intr_context ());
225 /* Just set our status to dying and schedule another process.
226 We will be destroyed during the call to schedule_tail(). */
228 thread_current ()->status = THREAD_DYING;
233 /* Yields the CPU. The current thread is not put to sleep and
234 may be scheduled again immediately at the scheduler's whim. */
238 struct thread *cur = thread_current ();
239 enum intr_level old_level;
241 ASSERT (!intr_context ());
243 old_level = intr_disable ();
244 list_push_back (&ready_list, &cur->elem);
245 cur->status = THREAD_READY;
247 intr_set_level (old_level);
250 /* Puts the current thread to sleep. It will not be scheduled
251 again until awoken by thread_unblock().
253 This function must be called with interrupts turned off. It
254 is usually a better idea to use one of the synchronization
255 primitives in synch.h. */
259 ASSERT (!intr_context ());
260 ASSERT (intr_get_level () == INTR_OFF);
262 thread_current ()->status = THREAD_BLOCKED;
266 /* Idle thread. Executes when no other thread is ready to run. */
268 idle (void *aux UNUSED)
272 /* Wait for an interrupt. */
273 DEBUG (idle, "idle");
276 /* Let someone else run. */
283 /* Function used as the basis for a kernel thread. */
285 kernel_thread (thread_func *function, void *aux)
287 ASSERT (function != NULL);
289 intr_enable (); /* The scheduler runs with interrupts off. */
290 function (aux); /* Execute the thread function. */
291 thread_exit (); /* If function() returns, kill the thread. */
294 /* Returns the running thread. */
296 running_thread (void)
300 /* Copy the CPU's stack pointer into `esp', and then round that
301 down to the start of a page. Because `struct thread' is
302 always at the beginning of a page and the stack pointer is
303 somewhere in the middle, this locates the curent thread. */
304 asm ("movl %%esp, %0\n" : "=g" (esp));
305 return pg_round_down (esp);
308 /* Returns true if T appears to point to a valid thread. */
310 is_thread (struct thread *t)
312 return t != NULL && t->magic == THREAD_MAGIC;
315 /* Creates a new thread named NAME and initializes its fields.
316 Returns the new thread if successful or a null pointer on
318 static struct thread *
319 new_thread (const char *name)
323 ASSERT (name != NULL);
325 t = palloc_get (PAL_ZERO);
327 init_thread (t, name);
332 /* Initializes T as a new, blocked thread named NAME. */
334 init_thread (struct thread *t, const char *name)
336 memset (t, 0, sizeof *t);
337 strlcpy (t->name, name, sizeof t->name);
338 t->stack = (uint8_t *) t + PGSIZE;
339 t->status = THREAD_BLOCKED;
340 t->magic = THREAD_MAGIC;
343 /* Allocates a SIZE-byte frame at the top of thread T's stack and
344 returns a pointer to the frame's base. */
346 alloc_frame (struct thread *t, size_t size)
348 /* Stack data is always allocated in word-size units. */
349 ASSERT (is_thread (t));
350 ASSERT (size % sizeof (uint32_t) == 0);
356 /* Chooses and returns the next thread to be scheduled. Should
357 return a thread from the run queue, unless the run queue is
358 empty. (If the running thread can continue running, then it
359 will be in the run queue.) If the run queue is empty, return
361 static struct thread *
362 next_thread_to_run (void)
364 if (list_empty (&ready_list))
367 return list_entry (list_pop_front (&ready_list), struct thread, elem);
370 /* Destroys T, which must be in the dying state and must not be
371 the running thread. */
373 destroy_thread (struct thread *t)
375 ASSERT (is_thread (t));
376 ASSERT (t->status == THREAD_DYING);
377 ASSERT (t != thread_current ());
380 addrspace_destroy (t);
385 /* Completes a thread switch by activating the new thread's page
386 tables, and, if the previous thread is dying, destroying it.
388 At this function's invocation, we just switched from thread
389 PREV, the new thread is already running, and interrupts are
390 still disabled. This function is normally invoked by
391 thread_schedule() as its final action before returning, but
392 the first time a thread is scheduled it is called by
393 switch_entry() (see switch.S).
395 After this function and its caller returns, the thread switch
398 schedule_tail (struct thread *prev)
400 struct thread *cur = running_thread ();
402 ASSERT (intr_get_level () == INTR_OFF);
404 /* Mark us as running. */
405 cur->status = THREAD_RUNNING;
408 /* Activate the new address space. */
409 addrspace_activate (cur);
412 /* If the thread we switched from is dying, destroy it.
413 This must happen late because it's not a good idea to
414 e.g. destroy the page table you're currently using. */
415 if (prev != NULL && prev->status == THREAD_DYING)
416 destroy_thread (prev);
419 /* Schedules a new process. At entry, interrupts must be off and
420 the running process's state must have been changed from
421 running to some other state. This function finds another
422 thread to run and switches to it. */
426 struct thread *cur = running_thread ();
427 struct thread *next = next_thread_to_run ();
428 struct thread *prev = NULL;
430 ASSERT (intr_get_level () == INTR_OFF);
431 ASSERT (cur->status != THREAD_RUNNING);
432 ASSERT (is_thread (next));
435 prev = switch_threads (cur, next);
436 schedule_tail (prev);
439 /* Offset of `stack' member within `struct thread'.
440 Used by switch.S, which can't figure it out on its own. */
441 uint32_t thread_stack_ofs = offsetof (struct thread, stack);