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, int priority);
49 static void init_thread (struct thread *, const char *name, int priority);
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", PRI_DEFAULT);
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", PRI_DEFAULT, idle, NULL);
92 /* Creates a new kernel thread named NAME with the given initial
93 PRIORITY, which executes FUNCTION passing AUX as the argument,
94 and adds it to the ready queue. If thread_start() has been
95 called, then the new thread may be scheduled before
96 thread_create() returns. It could even exit before
97 thread_create() returns. Use a semaphore or some other form
98 of synchronization if you need to ensure ordering. Returns
99 the thread identifier for the new thread, or TID_ERROR if
102 The code provided sets the new thread's `priority' member to
103 PRIORITY, but no actual priority scheduling is implemented.
104 Priority scheduling is the goal of Problem 1-3. */
106 thread_create (const char *name, int priority,
107 thread_func *function, void *aux)
110 struct kernel_thread_frame *kf;
111 struct switch_entry_frame *ef;
112 struct switch_threads_frame *sf;
115 ASSERT (function != NULL);
117 t = new_thread (name, priority);
122 /* Stack frame for kernel_thread(). */
123 kf = alloc_frame (t, sizeof *kf);
125 kf->function = function;
128 /* Stack frame for switch_entry(). */
129 ef = alloc_frame (t, sizeof *ef);
130 ef->eip = (void (*) (void)) kernel_thread;
132 /* Stack frame for switch_threads(). */
133 sf = alloc_frame (t, sizeof *sf);
134 sf->eip = switch_entry;
136 /* Add to run queue. */
143 /* Starts a new thread running a user program loaded from
144 FILENAME, and adds it to the ready queue. If thread_start()
145 has been called, then new thread may be scheduled before
146 thread_execute() returns.*/
148 thread_execute (const char *filename)
151 struct intr_frame *if_;
152 struct switch_entry_frame *ef;
153 struct switch_threads_frame *sf;
154 void (*start) (void);
157 ASSERT (filename != NULL);
159 t = new_thread (filename, PRI_DEFAULT);
164 if (!addrspace_load (t, filename, &start))
165 PANIC ("%s: program load failed", filename);
167 /* Interrupt frame. */
168 if_ = alloc_frame (t, sizeof *if_);
173 if_->eflags = FLAG_IF | FLAG_MBS;
174 if_->esp = PHYS_BASE;
177 /* Stack frame for switch_entry(). */
178 ef = alloc_frame (t, sizeof *ef);
181 /* Stack frame for switch_threads(). */
182 sf = alloc_frame (t, sizeof *sf);
183 sf->eip = switch_entry;
185 /* Add to run queue. */
192 /* Transitions a blocked thread T from its current state to the
193 ready-to-run state. This is an error if T is not blocked.
194 (Use thread_yield() to make the running thread ready.) */
196 thread_unblock (struct thread *t)
198 enum intr_level old_level;
200 ASSERT (is_thread (t));
202 old_level = intr_disable ();
203 ASSERT (t->status == THREAD_BLOCKED);
204 list_push_back (&ready_list, &t->elem);
205 t->status = THREAD_READY;
206 intr_set_level (old_level);
209 /* Returns the name of the running thread. */
213 return thread_current ()->name;
216 /* Returns the running thread.
217 This is running_thread() plus a couple of sanity checks.
218 See the big comment at the top of thread.h for details. */
220 thread_current (void)
222 struct thread *t = running_thread ();
224 /* Make sure T is really a thread.
225 If either of these assertions fire, then your thread may
226 have overflowed its stack. Each thread has less than 4 kB
227 of stack, so a few big automatic arrays or moderate
228 recursion can cause stack overflow. */
229 ASSERT (is_thread (t));
230 ASSERT (t->status == THREAD_RUNNING);
235 /* Returns the running thread's tid. */
239 return thread_current ()->tid;
242 /* Deschedules the current thread and destroys it. Never
243 returns to the caller. */
247 ASSERT (!intr_context ());
249 /* Just set our status to dying and schedule another process.
250 We will be destroyed during the call to schedule_tail(). */
252 thread_current ()->status = THREAD_DYING;
257 /* Yields the CPU. The current thread is not put to sleep and
258 may be scheduled again immediately at the scheduler's whim. */
262 struct thread *cur = thread_current ();
263 enum intr_level old_level;
265 ASSERT (!intr_context ());
267 old_level = intr_disable ();
268 list_push_back (&ready_list, &cur->elem);
269 cur->status = THREAD_READY;
271 intr_set_level (old_level);
274 /* Puts the current thread to sleep. It will not be scheduled
275 again until awoken by thread_unblock().
277 This function must be called with interrupts turned off. It
278 is usually a better idea to use one of the synchronization
279 primitives in synch.h. */
283 ASSERT (!intr_context ());
284 ASSERT (intr_get_level () == INTR_OFF);
286 thread_current ()->status = THREAD_BLOCKED;
290 /* Idle thread. Executes when no other thread is ready to run. */
292 idle (void *aux UNUSED)
294 idle_thread = thread_current ();
298 /* Let someone else run. */
303 /* Use CPU `hlt' instruction to wait for interrupt. */
308 /* Function used as the basis for a kernel thread. */
310 kernel_thread (thread_func *function, void *aux)
312 ASSERT (function != NULL);
314 intr_enable (); /* The scheduler runs with interrupts off. */
315 function (aux); /* Execute the thread function. */
316 thread_exit (); /* If function() returns, kill the thread. */
319 /* Returns the running thread. */
321 running_thread (void)
325 /* Copy the CPU's stack pointer into `esp', and then round that
326 down to the start of a page. Because `struct thread' is
327 always at the beginning of a page and the stack pointer is
328 somewhere in the middle, this locates the curent thread. */
329 asm ("movl %%esp, %0\n" : "=g" (esp));
330 return pg_round_down (esp);
333 /* Returns true if T appears to point to a valid thread. */
335 is_thread (struct thread *t)
337 return t != NULL && t->magic == THREAD_MAGIC;
340 /* Creates a new thread named NAME as a child of the running
341 thread. Returns the new thread if successful or a null
342 pointer on failure. */
343 static struct thread *
344 new_thread (const char *name, int priority)
346 struct thread *t = palloc_get (PAL_ZERO);
349 init_thread (t, name, priority);
350 t->tid = allocate_tid ();
356 /* Does basic initialization of T as a blocked thread named
359 init_thread (struct thread *t, const char *name, int priority)
362 ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
363 ASSERT (name != NULL);
365 memset (t, 0, sizeof *t);
366 t->status = THREAD_BLOCKED;
367 strlcpy (t->name, name, sizeof t->name);
368 t->stack = (uint8_t *) t + PGSIZE;
369 t->priority = priority;
370 t->magic = THREAD_MAGIC;
373 /* Allocates a SIZE-byte frame at the top of thread T's stack and
374 returns a pointer to the frame's base. */
376 alloc_frame (struct thread *t, size_t size)
378 /* Stack data is always allocated in word-size units. */
379 ASSERT (is_thread (t));
380 ASSERT (size % sizeof (uint32_t) == 0);
386 /* Chooses and returns the next thread to be scheduled. Should
387 return a thread from the run queue, unless the run queue is
388 empty. (If the running thread can continue running, then it
389 will be in the run queue.) If the run queue is empty, return
391 static struct thread *
392 next_thread_to_run (void)
394 if (list_empty (&ready_list))
397 return list_entry (list_pop_front (&ready_list), struct thread, elem);
400 /* Destroys T, which must be in the dying state and must not be
401 the running thread. */
403 destroy_thread (struct thread *t)
405 ASSERT (is_thread (t));
406 ASSERT (t->status == THREAD_DYING);
407 ASSERT (t != thread_current ());
410 addrspace_destroy (t);
412 if (t != initial_thread)
416 /* Completes a thread switch by activating the new thread's page
417 tables, and, if the previous thread is dying, destroying it.
419 At this function's invocation, we just switched from thread
420 PREV, the new thread is already running, and interrupts are
421 still disabled. This function is normally invoked by
422 thread_schedule() as its final action before returning, but
423 the first time a thread is scheduled it is called by
424 switch_entry() (see switch.S).
426 After this function and its caller returns, the thread switch
429 schedule_tail (struct thread *prev)
431 struct thread *cur = running_thread ();
433 ASSERT (intr_get_level () == INTR_OFF);
435 /* Mark us as running. */
436 cur->status = THREAD_RUNNING;
439 /* Activate the new address space. */
440 addrspace_activate (cur);
443 /* If the thread we switched from is dying, destroy it.
444 This must happen late because it's not a good idea to
445 e.g. destroy the page table you're currently using. */
446 if (prev != NULL && prev->status == THREAD_DYING)
447 destroy_thread (prev);
450 /* Schedules a new process. At entry, interrupts must be off and
451 the running process's state must have been changed from
452 running to some other state. This function finds another
453 thread to run and switches to it. */
457 struct thread *cur = running_thread ();
458 struct thread *next = next_thread_to_run ();
459 struct thread *prev = NULL;
461 ASSERT (intr_get_level () == INTR_OFF);
462 ASSERT (cur->status != THREAD_RUNNING);
463 ASSERT (is_thread (next));
466 prev = switch_threads (cur, next);
467 schedule_tail (prev);
470 /* Returns a tid to use for a new thread. */
474 static tid_t next_tid = 1;
477 lock_acquire (&tid_lock);
479 lock_release (&tid_lock);
484 /* Offset of `stack' member within `struct thread'.
485 Used by switch.S, which can't figure it out on its own. */
486 uint32_t thread_stack_ofs = offsetof (struct thread, stack);