5 #include "intr-stubs.h"
12 #define THREAD_MAGIC 0x1234abcdu
14 /* List of processes in THREAD_READY state, that is, processes
15 that are ready to run but not actually running. */
16 static struct list run_queue;
19 static struct thread *idle_thread; /* Thread. */
20 static void idle (void *aux UNUSED); /* Thread function. */
22 /* Stack frame for kernel_thread(). */
23 struct kernel_thread_frame
25 void *eip; /* Return address. */
26 void (*function) (void *); /* Function to call. */
27 void *aux; /* Auxiliary data for function. */
30 static void kernel_thread (void (*function) (void *aux), void *aux);
32 static struct thread *next_thread_to_run (void);
33 static struct thread *new_thread (const char *name);
34 static bool is_thread (struct thread *t);
35 static void *alloc_frame (struct thread *t, size_t size);
36 static void destroy_thread (struct thread *t);
37 static void schedule (void);
38 void schedule_tail (struct thread *prev);
40 /* Initializes the threading system. After calling, create some
41 threads with thread_create() or thread_execute(), then start
42 the scheduler with thread_start(). */
46 ASSERT (intr_get_level () == INTR_OFF);
48 /* Initialize run queue. */
49 list_init (&run_queue);
51 /* Create idle thread. */
52 idle_thread = thread_create ("idle", idle, NULL);
53 idle_thread->status = THREAD_BLOCKED;
56 /* Starts the thread scheduler. The caller should have created
57 some threads with thread_create() or thread_execute(). Never
58 returns to the caller. */
62 struct thread *t = next_thread_to_run ();
63 if (t->status == THREAD_READY)
64 list_remove (&t->rq_elem);
65 t->status = THREAD_RUNNING;
66 switch_threads (NULL, t);
71 /* Creates a new kernel thread named NAME, which executes
72 FUNCTION passing AUX as the argument, and adds it to the ready
73 queue. If thread_start() has been called, then the new thread
74 may be scheduled before thread_create() returns. Use a
75 semaphore or some other form of synchronization if you need to
78 thread_create (const char *name, void (*function) (void *aux), void *aux)
81 struct kernel_thread_frame *kf;
82 struct switch_entry_frame *ef;
83 struct switch_threads_frame *sf;
85 ASSERT (function != NULL);
87 t = new_thread (name);
89 /* Stack frame for kernel_thread(). */
90 kf = alloc_frame (t, sizeof *kf);
92 kf->function = function;
95 /* Stack frame for switch_entry(). */
96 ef = alloc_frame (t, sizeof *ef);
97 ef->eip = (void (*) (void)) kernel_thread;
99 /* Stack frame for switch_threads(). */
100 sf = alloc_frame (t, sizeof *sf);
101 sf->eip = switch_entry;
103 /* Add to run queue. */
110 /* Starts a new thread running a user program loaded from
111 FILENAME, and adds it to the ready queue. If thread_start()
112 has been called, then new thread may be scheduled before
113 thread_execute() returns.*/
115 thread_execute (const char *filename)
118 struct intr_frame *if_;
119 struct switch_entry_frame *ef;
120 struct switch_threads_frame *sf;
121 void (*start) (void);
123 ASSERT (filename != NULL);
125 t = new_thread (filename);
129 if (!addrspace_load (t, filename, &start))
130 PANIC ("%s: program load failed", filename);
132 /* Interrupt frame. */
133 if_ = alloc_frame (t, sizeof *if_);
138 if_->eflags = FLAG_IF | FLAG_MBS;
139 if_->esp = PHYS_BASE;
142 /* Stack frame for switch_entry(). */
143 ef = alloc_frame (t, sizeof *ef);
146 /* Stack frame for switch_threads(). */
147 sf = alloc_frame (t, sizeof *sf);
148 sf->eip = switch_entry;
150 /* Add to run queue. */
157 /* Transitions T from its current state to THREAD_READY, the
158 ready-to-run state. On entry, T must be ready or blocked.
159 (Use thread_yield() to make the running thread ready.) */
161 thread_wake (struct thread *t)
163 ASSERT (is_thread (t));
164 ASSERT (t->status == THREAD_READY || t->status == THREAD_BLOCKED);
165 if (t->status != THREAD_READY)
167 list_push_back (&run_queue, &t->rq_elem);
168 t->status = THREAD_READY;
172 /* Returns the name of thread T. */
174 thread_name (struct thread *t)
176 ASSERT (is_thread (t));
180 /* Returns the running thread. */
182 thread_current (void)
187 /* Copy the CPU's stack pointer into `esp', and then round that
188 down to the start of a page. Because `struct thread' is
189 always at the beginning of a page and the stack pointer is
190 somewhere in the middle, this locates the curent thread. */
191 asm ("movl %%esp, %0\n" : "=g" (esp));
192 t = pg_round_down (esp);
194 /* Make sure T is really a thread.
195 If this assertion fires, then your thread may have
196 overflowed its stack. Each thread has less than 4 kB of
197 stack, so a few big automatic arrays or moderate recursion
198 can cause stack overflow. */
199 ASSERT (is_thread (t));
204 /* Deschedules the current thread and destroys it. Never
205 returns to the caller. */
209 ASSERT (!intr_context ());
212 thread_current ()->status = THREAD_DYING;
217 /* Yields the CPU. The current thread is not put to sleep and
218 may be scheduled again immediately at the scheduler's whim. */
222 struct thread *cur = thread_current ();
223 enum intr_level old_level;
225 ASSERT (!intr_context ());
227 old_level = intr_disable ();
228 list_push_back (&run_queue, &cur->rq_elem);
229 cur->status = THREAD_READY;
231 intr_set_level (old_level);
234 /* Puts the current thread to sleep. It will not be scheduled
235 again until awoken by thread_wake(). */
239 ASSERT (!intr_context ());
240 ASSERT (intr_get_level () == INTR_OFF);
242 thread_current ()->status = THREAD_BLOCKED;
246 /* Idle thread. Executes when no other thread is ready to run. */
248 idle (void *aux UNUSED)
252 /* Wait for an interrupt. */
253 DEBUG (idle, "idle");
256 /* Let someone else run. */
263 /* Function used as the basis for a kernel thread. */
265 kernel_thread (void (*function) (void *aux), 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 true if T appears to point to a valid thread. */
276 is_thread (struct thread *t)
278 return t != NULL && t->magic == THREAD_MAGIC;
281 /* Creates a new thread named NAME and initializes its fields.
282 Returns the new thread if successful or a null pointer on
284 static struct thread *
285 new_thread (const char *name)
289 ASSERT (name != NULL);
291 t = palloc_get (PAL_ZERO);
294 strlcpy (t->name, name, sizeof t->name);
295 t->stack = (uint8_t *) t + PGSIZE;
296 t->status = THREAD_BLOCKED;
297 t->magic = THREAD_MAGIC;
303 /* Allocates a SIZE-byte frame at the top of thread T's stack and
304 returns a pointer to the frame's base. */
306 alloc_frame (struct thread *t, size_t size)
308 /* Stack data is always allocated in word-size units. */
309 ASSERT (is_thread (t));
310 ASSERT (size % sizeof (uint32_t) == 0);
316 /* Chooses and returns the next thread to be scheduled. Should
317 return a thread from the run queue, unless the run queue is
318 empty. (If the running thread can continue running, then it
319 will be in the run queue.) If the run queue is empty, return
321 static struct thread *
322 next_thread_to_run (void)
324 if (list_empty (&run_queue))
327 return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
330 /* Destroys T, which must be in the dying state and must not be
331 the running thread. */
333 destroy_thread (struct thread *t)
335 ASSERT (is_thread (t));
336 ASSERT (t->status == THREAD_DYING);
337 ASSERT (t != thread_current ());
339 addrspace_destroy (t);
343 /* Completes a thread switch by activating the new thread's page
344 tables, and, if the previous thread is dying, destroying it.
346 At this function's invocation, we just switched from thread
347 PREV, the new thread is already running, and interrupts are
348 still disabled. This function is normally invoked by
349 thread_schedule() as its final action before returning, but
350 the first time a thread is scheduled it is called by
351 switch_entry() (see switch.S).
353 After this function and its caller returns, the thread switch
356 schedule_tail (struct thread *prev)
358 struct thread *cur = thread_current ();
360 ASSERT (intr_get_level () == INTR_OFF);
362 cur->status = THREAD_RUNNING;
363 if (prev != NULL && prev->status == THREAD_DYING)
364 destroy_thread (prev);
367 addrspace_activate (cur);
371 /* Schedules a new process. At entry, interrupts must be off and
372 the running process's state must have been changed from
373 running to some other state. This function finds another
374 thread to run and switches to it. */
378 struct thread *cur = thread_current ();
379 struct thread *next = next_thread_to_run ();
381 ASSERT (intr_get_level () == INTR_OFF);
382 ASSERT (cur->status != THREAD_RUNNING);
383 ASSERT (is_thread (next));
387 struct thread *prev = switch_threads (cur, next);
388 schedule_tail (prev);
392 /* Offset of `stack' member within `struct thread'.
393 Used by switch.S, which can't figure it out on its own. */
394 uint32_t thread_stack_ofs = offsetof (struct thread, stack);