5 #include "intr-stubs.h"
15 #define THREAD_MAGIC 0x1234abcdu
17 /* List of processes in THREAD_READY state, that is, processes
18 that are ready to run but not actually running. */
19 static struct list run_queue;
22 static struct thread *idle_thread; /* Thread. */
23 static void idle (void *aux UNUSED); /* Thread function. */
25 /* Stack frame for kernel_thread(). */
26 struct kernel_thread_frame
28 void *eip; /* Return address. */
29 thread_func *function; /* Function to call. */
30 void *aux; /* Auxiliary data for function. */
33 static void kernel_thread (thread_func *, void *aux);
35 static struct thread *next_thread_to_run (void);
36 static struct thread *new_thread (const char *name);
37 static bool is_thread (struct thread *t);
38 static void *alloc_frame (struct thread *t, size_t size);
39 static void destroy_thread (struct thread *t);
40 static void schedule (void);
41 void schedule_tail (struct thread *prev);
43 /* Initializes the threading system. After calling, create some
44 threads with thread_create() or thread_execute(), then start
45 the scheduler with thread_start(). */
49 ASSERT (intr_get_level () == INTR_OFF);
51 /* Initialize run queue. */
52 list_init (&run_queue);
54 /* Create idle thread. */
55 idle_thread = thread_create ("idle", idle, NULL);
56 idle_thread->status = THREAD_BLOCKED;
59 /* Starts the thread scheduler. The caller should have created
60 some threads with thread_create() or thread_execute(). Never
61 returns to the caller. */
65 struct thread *t = next_thread_to_run ();
66 if (t->status == THREAD_READY)
67 list_remove (&t->rq_elem);
68 t->status = THREAD_RUNNING;
69 switch_threads (NULL, t);
74 /* Creates a new kernel thread named NAME, which executes
75 FUNCTION passing AUX as the argument, and adds it to the ready
76 queue. If thread_start() has been called, then the new thread
77 may be scheduled before thread_create() returns. Use a
78 semaphore or some other form of synchronization if you need to
81 thread_create (const char *name, thread_func *function, void *aux)
84 struct kernel_thread_frame *kf;
85 struct switch_entry_frame *ef;
86 struct switch_threads_frame *sf;
88 ASSERT (function != NULL);
90 t = new_thread (name);
92 /* Stack frame for kernel_thread(). */
93 kf = alloc_frame (t, sizeof *kf);
95 kf->function = function;
98 /* Stack frame for switch_entry(). */
99 ef = alloc_frame (t, sizeof *ef);
100 ef->eip = (void (*) (void)) kernel_thread;
102 /* Stack frame for switch_threads(). */
103 sf = alloc_frame (t, sizeof *sf);
104 sf->eip = switch_entry;
106 /* Add to run queue. */
113 /* Starts a new thread running a user program loaded from
114 FILENAME, and adds it to the ready queue. If thread_start()
115 has been called, then new thread may be scheduled before
116 thread_execute() returns.*/
118 thread_execute (const char *filename)
121 struct intr_frame *if_;
122 struct switch_entry_frame *ef;
123 struct switch_threads_frame *sf;
124 void (*start) (void);
126 ASSERT (filename != NULL);
128 t = new_thread (filename);
132 if (!addrspace_load (t, filename, &start))
133 PANIC ("%s: program load failed", filename);
135 /* Interrupt frame. */
136 if_ = alloc_frame (t, sizeof *if_);
141 if_->eflags = FLAG_IF | FLAG_MBS;
142 if_->esp = PHYS_BASE;
145 /* Stack frame for switch_entry(). */
146 ef = alloc_frame (t, sizeof *ef);
149 /* Stack frame for switch_threads(). */
150 sf = alloc_frame (t, sizeof *sf);
151 sf->eip = switch_entry;
153 /* Add to run queue. */
160 /* Transitions T from its current state to THREAD_READY, the
161 ready-to-run state. On entry, T must be ready or blocked.
162 (Use thread_yield() to make the running thread ready.) */
164 thread_wake (struct thread *t)
166 ASSERT (is_thread (t));
167 ASSERT (t->status == THREAD_READY || t->status == THREAD_BLOCKED);
168 if (t->status != THREAD_READY)
170 list_push_back (&run_queue, &t->rq_elem);
171 t->status = THREAD_READY;
175 /* Returns the name of thread T. */
177 thread_name (struct thread *t)
179 ASSERT (is_thread (t));
183 /* Returns the running thread. */
185 thread_current (void)
190 /* Copy the CPU's stack pointer into `esp', and then round that
191 down to the start of a page. Because `struct thread' is
192 always at the beginning of a page and the stack pointer is
193 somewhere in the middle, this locates the curent thread. */
194 asm ("movl %%esp, %0\n" : "=g" (esp));
195 t = pg_round_down (esp);
197 /* Make sure T is really a thread.
198 If this assertion fires, then your thread may have
199 overflowed its stack. Each thread has less than 4 kB of
200 stack, so a few big automatic arrays or moderate recursion
201 can cause stack overflow. */
202 ASSERT (is_thread (t));
207 /* Deschedules the current thread and destroys it. Never
208 returns to the caller. */
212 ASSERT (!intr_context ());
215 thread_current ()->status = THREAD_DYING;
220 /* Yields the CPU. The current thread is not put to sleep and
221 may be scheduled again immediately at the scheduler's whim. */
225 struct thread *cur = thread_current ();
226 enum intr_level old_level;
228 ASSERT (!intr_context ());
230 old_level = intr_disable ();
231 list_push_back (&run_queue, &cur->rq_elem);
232 cur->status = THREAD_READY;
234 intr_set_level (old_level);
237 /* Puts the current thread to sleep. It will not be scheduled
238 again until awoken by thread_wake(). */
242 ASSERT (!intr_context ());
243 ASSERT (intr_get_level () == INTR_OFF);
245 thread_current ()->status = THREAD_BLOCKED;
249 /* Idle thread. Executes when no other thread is ready to run. */
251 idle (void *aux UNUSED)
255 /* Wait for an interrupt. */
256 DEBUG (idle, "idle");
259 /* Let someone else run. */
266 /* Function used as the basis for a kernel thread. */
268 kernel_thread (thread_func *function, void *aux)
270 ASSERT (function != NULL);
272 intr_enable (); /* The scheduler runs with interrupts off. */
273 function (aux); /* Execute the thread function. */
274 thread_exit (); /* If function() returns, kill the thread. */
277 /* Returns true if T appears to point to a valid thread. */
279 is_thread (struct thread *t)
281 return t != NULL && t->magic == THREAD_MAGIC;
284 /* Creates a new thread named NAME and initializes its fields.
285 Returns the new thread if successful or a null pointer on
287 static struct thread *
288 new_thread (const char *name)
292 ASSERT (name != NULL);
294 t = palloc_get (PAL_ZERO);
297 strlcpy (t->name, name, sizeof t->name);
298 t->stack = (uint8_t *) t + PGSIZE;
299 t->status = THREAD_BLOCKED;
300 t->magic = THREAD_MAGIC;
306 /* Allocates a SIZE-byte frame at the top of thread T's stack and
307 returns a pointer to the frame's base. */
309 alloc_frame (struct thread *t, size_t size)
311 /* Stack data is always allocated in word-size units. */
312 ASSERT (is_thread (t));
313 ASSERT (size % sizeof (uint32_t) == 0);
319 /* Chooses and returns the next thread to be scheduled. Should
320 return a thread from the run queue, unless the run queue is
321 empty. (If the running thread can continue running, then it
322 will be in the run queue.) If the run queue is empty, return
324 static struct thread *
325 next_thread_to_run (void)
327 if (list_empty (&run_queue))
330 return list_entry (list_pop_front (&run_queue), struct thread, rq_elem);
333 /* Destroys T, which must be in the dying state and must not be
334 the running thread. */
336 destroy_thread (struct thread *t)
338 ASSERT (is_thread (t));
339 ASSERT (t->status == THREAD_DYING);
340 ASSERT (t != thread_current ());
343 addrspace_destroy (t);
348 /* Completes a thread switch by activating the new thread's page
349 tables, and, if the previous thread is dying, destroying it.
351 At this function's invocation, we just switched from thread
352 PREV, the new thread is already running, and interrupts are
353 still disabled. This function is normally invoked by
354 thread_schedule() as its final action before returning, but
355 the first time a thread is scheduled it is called by
356 switch_entry() (see switch.S).
358 After this function and its caller returns, the thread switch
361 schedule_tail (struct thread *prev)
363 struct thread *cur = thread_current ();
365 ASSERT (intr_get_level () == INTR_OFF);
367 cur->status = THREAD_RUNNING;
368 if (prev != NULL && prev->status == THREAD_DYING)
369 destroy_thread (prev);
372 addrspace_activate (cur);
376 /* Schedules a new process. At entry, interrupts must be off and
377 the running process's state must have been changed from
378 running to some other state. This function finds another
379 thread to run and switches to it. */
383 struct thread *cur = thread_current ();
384 struct thread *next = next_thread_to_run ();
386 ASSERT (intr_get_level () == INTR_OFF);
387 ASSERT (cur->status != THREAD_RUNNING);
388 ASSERT (is_thread (next));
392 struct thread *prev = switch_threads (cur, next);
393 schedule_tail (prev);
397 /* Offset of `stack' member within `struct thread'.
398 Used by switch.S, which can't figure it out on its own. */
399 uint32_t thread_stack_ofs = offsetof (struct thread, stack);