1 #include "threads/thread.h"
6 #include "threads/flags.h"
7 #include "threads/interrupt.h"
8 #include "threads/intr-stubs.h"
9 #include "threads/mmu.h"
10 #include "threads/palloc.h"
11 #include "threads/switch.h"
12 #include "threads/synch.h"
14 #include "userprog/gdt.h"
17 /* Random value for struct thread's `magic' member.
18 Used to detect stack overflow. See the big comment at the top
19 of thread.h for details. */
20 #define THREAD_MAGIC 0xcd6abf4b
22 /* List of processes in THREAD_READY state, that is, processes
23 that are ready to run but not actually running. */
24 static struct list ready_list;
27 static struct thread *idle_thread;
29 /* Initial thread, the thread running init.c:main(). */
30 static struct thread *initial_thread;
32 /* Lock used by allocate_tid(). */
33 static struct lock tid_lock;
35 /* Stack frame for kernel_thread(). */
36 struct kernel_thread_frame
38 void *eip; /* Return address. */
39 thread_func *function; /* Function to call. */
40 void *aux; /* Auxiliary data for function. */
43 static void kernel_thread (thread_func *, void *aux);
45 static void idle (void *aux UNUSED);
46 static struct thread *running_thread (void);
47 static struct thread *next_thread_to_run (void);
48 static struct thread *new_thread (const char *name);
49 static void init_thread (struct thread *, const char *name);
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");
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", idle, NULL);
92 /* Creates a new kernel thread named NAME, which executes
93 FUNCTION passing AUX as the argument, and adds it to the ready
94 queue. If thread_start() has been called, then the new thread
95 may be scheduled before thread_create() returns. It could
96 even exit before thread_create() returns. Use a semaphore or
97 some other form of synchronization if you need to ensure
98 ordering. Returns the thread identifier for the new thread,
99 or TID_ERROR if creation fails. */
101 thread_create (const char *name, thread_func *function, void *aux)
104 struct kernel_thread_frame *kf;
105 struct switch_entry_frame *ef;
106 struct switch_threads_frame *sf;
109 ASSERT (function != NULL);
111 t = new_thread (name);
114 tid = t->tid = allocate_tid ();
116 /* Stack frame for kernel_thread(). */
117 kf = alloc_frame (t, sizeof *kf);
119 kf->function = function;
122 /* Stack frame for switch_entry(). */
123 ef = alloc_frame (t, sizeof *ef);
124 ef->eip = (void (*) (void)) kernel_thread;
126 /* Stack frame for switch_threads(). */
127 sf = alloc_frame (t, sizeof *sf);
128 sf->eip = switch_entry;
130 /* Add to run queue. */
137 /* Starts a new thread running a user program loaded from
138 FILENAME, and adds it to the ready queue. If thread_start()
139 has been called, then new thread may be scheduled before
140 thread_execute() returns.*/
142 thread_execute (const char *filename)
145 struct intr_frame *if_;
146 struct switch_entry_frame *ef;
147 struct switch_threads_frame *sf;
148 void (*start) (void);
151 ASSERT (filename != NULL);
153 t = new_thread (filename);
156 tid = t->tid = allocate_tid ();
158 if (!addrspace_load (t, filename, &start))
159 PANIC ("%s: program load failed", filename);
161 /* Interrupt frame. */
162 if_ = alloc_frame (t, sizeof *if_);
167 if_->eflags = FLAG_IF | FLAG_MBS;
168 if_->esp = PHYS_BASE;
171 /* Stack frame for switch_entry(). */
172 ef = alloc_frame (t, sizeof *ef);
175 /* Stack frame for switch_threads(). */
176 sf = alloc_frame (t, sizeof *sf);
177 sf->eip = switch_entry;
179 /* Add to run queue. */
186 /* Transitions a blocked thread T from its current state to the
187 ready-to-run state. This is an error if T is not blocked.
188 (Use thread_yield() to make the running thread ready.) */
190 thread_unblock (struct thread *t)
192 enum intr_level old_level;
194 ASSERT (is_thread (t));
196 old_level = intr_disable ();
197 ASSERT (t->status == THREAD_BLOCKED);
198 list_push_back (&ready_list, &t->elem);
199 t->status = THREAD_READY;
200 intr_set_level (old_level);
203 /* Returns the name of the running thread. */
207 return thread_current ()->name;
210 /* Returns the running thread.
211 This is running_thread() plus a couple of sanity checks.
212 See the big comment at the top of thread.h for details. */
214 thread_current (void)
216 struct thread *t = running_thread ();
218 /* Make sure T is really a thread.
219 If either of these assertions fire, then your thread may
220 have overflowed its stack. Each thread has less than 4 kB
221 of stack, so a few big automatic arrays or moderate
222 recursion can cause stack overflow. */
223 ASSERT (is_thread (t));
224 ASSERT (t->status == THREAD_RUNNING);
229 /* Returns the running thread's tid. */
233 return thread_current ()->tid;
236 /* Deschedules the current thread and destroys it. Never
237 returns to the caller. */
241 ASSERT (!intr_context ());
243 /* Just set our status to dying and schedule another process.
244 We will be destroyed during the call to schedule_tail(). */
246 thread_current ()->status = THREAD_DYING;
251 /* Yields the CPU. The current thread is not put to sleep and
252 may be scheduled again immediately at the scheduler's whim. */
256 struct thread *cur = thread_current ();
257 enum intr_level old_level;
259 ASSERT (!intr_context ());
261 old_level = intr_disable ();
262 list_push_back (&ready_list, &cur->elem);
263 cur->status = THREAD_READY;
265 intr_set_level (old_level);
268 /* Puts the current thread to sleep. It will not be scheduled
269 again until awoken by thread_unblock().
271 This function must be called with interrupts turned off. It
272 is usually a better idea to use one of the synchronization
273 primitives in synch.h. */
277 ASSERT (!intr_context ());
278 ASSERT (intr_get_level () == INTR_OFF);
280 thread_current ()->status = THREAD_BLOCKED;
284 /* Idle thread. Executes when no other thread is ready to run. */
286 idle (void *aux UNUSED)
288 idle_thread = thread_current ();
292 /* Let someone else run. */
297 /* Use CPU `hlt' instruction to wait for interrupt. */
302 /* Function used as the basis for a kernel thread. */
304 kernel_thread (thread_func *function, void *aux)
306 ASSERT (function != NULL);
308 intr_enable (); /* The scheduler runs with interrupts off. */
309 function (aux); /* Execute the thread function. */
310 thread_exit (); /* If function() returns, kill the thread. */
313 /* Returns the running thread. */
315 running_thread (void)
319 /* Copy the CPU's stack pointer into `esp', and then round that
320 down to the start of a page. Because `struct thread' is
321 always at the beginning of a page and the stack pointer is
322 somewhere in the middle, this locates the curent thread. */
323 asm ("movl %%esp, %0\n" : "=g" (esp));
324 return pg_round_down (esp);
327 /* Returns true if T appears to point to a valid thread. */
329 is_thread (struct thread *t)
331 return t != NULL && t->magic == THREAD_MAGIC;
334 /* Creates a new thread named NAME and initializes its fields.
335 Returns the new thread if successful or a null pointer on
337 static struct thread *
338 new_thread (const char *name)
342 ASSERT (name != NULL);
344 t = palloc_get (PAL_ZERO);
346 init_thread (t, name);
351 /* Initializes T as a new, blocked thread named NAME. */
353 init_thread (struct thread *t, const char *name)
355 memset (t, 0, sizeof *t);
356 t->status = THREAD_BLOCKED;
357 strlcpy (t->name, name, sizeof t->name);
358 t->stack = (uint8_t *) t + PGSIZE;
359 t->magic = THREAD_MAGIC;
362 /* Allocates a SIZE-byte frame at the top of thread T's stack and
363 returns a pointer to the frame's base. */
365 alloc_frame (struct thread *t, size_t size)
367 /* Stack data is always allocated in word-size units. */
368 ASSERT (is_thread (t));
369 ASSERT (size % sizeof (uint32_t) == 0);
375 /* Chooses and returns the next thread to be scheduled. Should
376 return a thread from the run queue, unless the run queue is
377 empty. (If the running thread can continue running, then it
378 will be in the run queue.) If the run queue is empty, return
380 static struct thread *
381 next_thread_to_run (void)
383 if (list_empty (&ready_list))
386 return list_entry (list_pop_front (&ready_list), struct thread, elem);
389 /* Destroys T, which must be in the dying state and must not be
390 the running thread. */
392 destroy_thread (struct thread *t)
394 ASSERT (is_thread (t));
395 ASSERT (t->status == THREAD_DYING);
396 ASSERT (t != thread_current ());
399 addrspace_destroy (t);
401 if (t != initial_thread)
405 /* Completes a thread switch by activating the new thread's page
406 tables, and, if the previous thread is dying, destroying it.
408 At this function's invocation, we just switched from thread
409 PREV, the new thread is already running, and interrupts are
410 still disabled. This function is normally invoked by
411 thread_schedule() as its final action before returning, but
412 the first time a thread is scheduled it is called by
413 switch_entry() (see switch.S).
415 After this function and its caller returns, the thread switch
418 schedule_tail (struct thread *prev)
420 struct thread *cur = running_thread ();
422 ASSERT (intr_get_level () == INTR_OFF);
424 /* Mark us as running. */
425 cur->status = THREAD_RUNNING;
428 /* Activate the new address space. */
429 addrspace_activate (cur);
432 /* If the thread we switched from is dying, destroy it.
433 This must happen late because it's not a good idea to
434 e.g. destroy the page table you're currently using. */
435 if (prev != NULL && prev->status == THREAD_DYING)
436 destroy_thread (prev);
439 /* Schedules a new process. At entry, interrupts must be off and
440 the running process's state must have been changed from
441 running to some other state. This function finds another
442 thread to run and switches to it. */
446 struct thread *cur = running_thread ();
447 struct thread *next = next_thread_to_run ();
448 struct thread *prev = NULL;
450 ASSERT (intr_get_level () == INTR_OFF);
451 ASSERT (cur->status != THREAD_RUNNING);
452 ASSERT (is_thread (next));
455 prev = switch_threads (cur, next);
456 schedule_tail (prev);
459 /* Returns a tid to use for a new thread. */
463 static tid_t next_tid = 1;
466 lock_acquire (&tid_lock);
468 lock_release (&tid_lock);
473 /* Offset of `stack' member within `struct thread'.
474 Used by switch.S, which can't figure it out on its own. */
475 uint32_t thread_stack_ofs = offsetof (struct thread, stack);