X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Fthreads%2Fthread.c;h=0861e29533b67a59e3b4a248311735deeb2b6d5b;hb=f0612244c44f4b4f0bc79e3fc882e9f74bd4a3f4;hp=2694a10959ba9ccd9965f498197ec5add8905a5f;hpb=349cc721b17effa62c8b18a7dccc5defc44472d3;p=pintos-anon diff --git a/src/threads/thread.c b/src/threads/thread.c index 2694a10..0861e29 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -1,26 +1,38 @@ -#include "thread.h" +#include "threads/thread.h" +#include #include -#include "debug.h" -#include "interrupt.h" -#include "intr-stubs.h" -#include "lib.h" -#include "mmu.h" -#include "palloc.h" -#include "random.h" -#include "switch.h" +#include +#include +#include +#include "threads/flags.h" +#include "threads/interrupt.h" +#include "threads/intr-stubs.h" +#include "threads/mmu.h" +#include "threads/palloc.h" +#include "threads/switch.h" +#include "threads/synch.h" #ifdef USERPROG -#include "gdt.h" +#include "userprog/process.h" +#include "userprog/gdt.h" #endif -#define THREAD_MAGIC 0x1234abcdu +/* Random value for struct thread's `magic' member. + Used to detect stack overflow. See the big comment at the top + of thread.h for details. */ +#define THREAD_MAGIC 0xcd6abf4b /* List of processes in THREAD_READY state, that is, processes that are ready to run but not actually running. */ -static struct list run_queue; +static struct list ready_list; /* Idle thread. */ -static struct thread *idle_thread; /* Thread. */ -static void idle (void *aux UNUSED); /* Thread function. */ +static struct thread *idle_thread; + +/* Initial thread, the thread running init.c:main(). */ +static struct thread *initial_thread; + +/* Lock used by allocate_tid(). */ +static struct lock tid_lock; /* Stack frame for kernel_thread(). */ struct kernel_thread_frame @@ -32,15 +44,17 @@ struct kernel_thread_frame static void kernel_thread (thread_func *, void *aux); +static void idle (void *aux UNUSED); static struct thread *running_thread (void); static struct thread *next_thread_to_run (void); -static struct thread *new_thread (const char *name); -static void init_thread (struct thread *, const char *name); +static struct thread *new_thread (const char *name, int priority); +static void init_thread (struct thread *, const char *name, int priority); static bool is_thread (struct thread *); static void *alloc_frame (struct thread *, size_t size); static void destroy_thread (struct thread *); static void schedule (void); void schedule_tail (struct thread *prev); +static tid_t allocate_tid (void); /* Initializes the threading system by transforming the code that's currently running into a thread. Note that this is @@ -54,17 +68,18 @@ void schedule_tail (struct thread *prev); void thread_init (void) { - struct thread *t; - ASSERT (intr_get_level () == INTR_OFF); + lock_init (&tid_lock, "tid"); + /* Set up a thread structure for the running thread. */ - t = running_thread (); - init_thread (t, "main"); - t->status = THREAD_RUNNING; + initial_thread = running_thread (); + init_thread (initial_thread, "main", PRI_DEFAULT); + initial_thread->status = THREAD_RUNNING; + initial_thread->tid = allocate_tid (); /* Initialize run queue. */ - list_init (&run_queue); + list_init (&ready_list); } /* Starts preemptive thread scheduling by enabling interrupts. @@ -72,31 +87,39 @@ thread_init (void) void thread_start (void) { - /* Create idle thread. */ - idle_thread = thread_create ("idle", idle, NULL); - idle_thread->status = THREAD_BLOCKED; - - /* Enable interrupts. */ + thread_create ("idle", PRI_DEFAULT, idle, NULL); intr_enable (); } -/* Creates a new kernel thread named NAME, which executes - FUNCTION passing AUX as the argument, and adds it to the ready - queue. If thread_start() has been called, then the new thread - may be scheduled before thread_create() returns. Use a - semaphore or some other form of synchronization if you need to - ensure ordering. */ -struct thread * -thread_create (const char *name, thread_func *function, void *aux) +/* Creates a new kernel thread named NAME with the given initial + PRIORITY, which executes FUNCTION passing AUX as the argument, + and adds it to the ready queue. If thread_start() has been + called, then the new thread may be scheduled before + thread_create() returns. It could even exit before + thread_create() returns. Use a semaphore or some other form + of synchronization if you need to ensure ordering. Returns + the thread identifier for the new thread, or TID_ERROR if + creation fails. + + The code provided sets the new thread's `priority' member to + PRIORITY, but no actual priority scheduling is implemented. + Priority scheduling is the goal of Problem 1-3. */ +tid_t +thread_create (const char *name, int priority, + thread_func *function, void *aux) { struct thread *t; struct kernel_thread_frame *kf; struct switch_entry_frame *ef; struct switch_threads_frame *sf; + tid_t tid; ASSERT (function != NULL); - t = new_thread (name); + t = new_thread (name, priority); + if (t == NULL) + return TID_ERROR; + tid = t->tid; /* Stack frame for kernel_thread(). */ kf = alloc_frame (t, sizeof *kf); @@ -115,59 +138,11 @@ thread_create (const char *name, thread_func *function, void *aux) /* Add to run queue. */ thread_unblock (t); - return t; + return tid; } -#ifdef USERPROG -/* Starts a new thread running a user program loaded from - FILENAME, and adds it to the ready queue. If thread_start() - has been called, then new thread may be scheduled before - thread_execute() returns.*/ -bool -thread_execute (const char *filename) -{ - struct thread *t; - struct intr_frame *if_; - struct switch_entry_frame *ef; - struct switch_threads_frame *sf; - void (*start) (void); - - ASSERT (filename != NULL); - - t = new_thread (filename); - if (t == NULL) - return false; - - if (!addrspace_load (t, filename, &start)) - PANIC ("%s: program load failed", filename); - - /* Interrupt frame. */ - if_ = alloc_frame (t, sizeof *if_); - if_->es = SEL_UDSEG; - if_->ds = SEL_UDSEG; - if_->eip = start; - if_->cs = SEL_UCSEG; - if_->eflags = FLAG_IF | FLAG_MBS; - if_->esp = PHYS_BASE; - if_->ss = SEL_UDSEG; - - /* Stack frame for switch_entry(). */ - ef = alloc_frame (t, sizeof *ef); - ef->eip = intr_exit; - - /* Stack frame for switch_threads(). */ - sf = alloc_frame (t, sizeof *sf); - sf->eip = switch_entry; - - /* Add to run queue. */ - thread_unblock (t); - - return true; -} -#endif - /* Transitions a blocked thread T from its current state to the - ready-to-run state. If T is not blocked, there is no effect. + ready-to-run state. This is an error if T is not blocked. (Use thread_yield() to make the running thread ready.) */ void thread_unblock (struct thread *t) @@ -177,24 +152,22 @@ thread_unblock (struct thread *t) ASSERT (is_thread (t)); old_level = intr_disable (); - if (t->status == THREAD_BLOCKED) - { - list_push_back (&run_queue, &t->rq_elem); - t->status = THREAD_READY; - } + ASSERT (t->status == THREAD_BLOCKED); + list_push_back (&ready_list, &t->elem); + t->status = THREAD_READY; intr_set_level (old_level); } -/* Returns the name of thread T. */ +/* Returns the name of the running thread. */ const char * -thread_name (struct thread *t) +thread_name (void) { - ASSERT (is_thread (t)); - return t->name; + return thread_current ()->name; } /* Returns the running thread. - This is running_thread() plus a couple of sanity checks. */ + This is running_thread() plus a couple of sanity checks. + See the big comment at the top of thread.h for details. */ struct thread * thread_current (void) { @@ -211,6 +184,13 @@ thread_current (void) return t; } +/* Returns the running thread's tid. */ +tid_t +thread_tid (void) +{ + return thread_current ()->tid; +} + /* Deschedules the current thread and destroys it. Never returns to the caller. */ void @@ -218,6 +198,8 @@ thread_exit (void) { ASSERT (!intr_context ()); + /* Just set our status to dying and schedule another process. + We will be destroyed during the call to schedule_tail(). */ intr_disable (); thread_current ()->status = THREAD_DYING; schedule (); @@ -235,14 +217,18 @@ thread_yield (void) ASSERT (!intr_context ()); old_level = intr_disable (); - list_push_back (&run_queue, &cur->rq_elem); + list_push_back (&ready_list, &cur->elem); cur->status = THREAD_READY; schedule (); intr_set_level (old_level); } /* Puts the current thread to sleep. It will not be scheduled - again until awoken by thread_unblock(). */ + again until awoken by thread_unblock(). + + This function must be called with interrupts turned off. It + is usually a better idea to use one of the synchronization + primitives in synch.h. */ void thread_block (void) { @@ -257,16 +243,17 @@ thread_block (void) static void idle (void *aux UNUSED) { + idle_thread = thread_current (); + for (;;) { - /* Wait for an interrupt. */ - DEBUG (idle, "idle"); - asm ("hlt"); - /* Let someone else run. */ intr_disable (); thread_block (); intr_enable (); + + /* Use CPU `hlt' instruction to wait for interrupt. */ + asm ("hlt"); } } @@ -302,31 +289,36 @@ is_thread (struct thread *t) return t != NULL && t->magic == THREAD_MAGIC; } -/* Creates a new thread named NAME and initializes its fields. - Returns the new thread if successful or a null pointer on - failure. */ +/* Creates a new thread named NAME as a child of the running + thread. Returns the new thread if successful or a null + pointer on failure. */ static struct thread * -new_thread (const char *name) +new_thread (const char *name, int priority) { - struct thread *t; - - ASSERT (name != NULL); - - t = palloc_get (PAL_ZERO); - if (t != NULL) - init_thread (t, name); + struct thread *t = palloc_get (PAL_ZERO); + if (t != NULL) + { + init_thread (t, name, priority); + t->tid = allocate_tid (); + } return t; } -/* Initializes T as a new thread named NAME. */ +/* Does basic initialization of T as a blocked thread named + NAME. */ static void -init_thread (struct thread *t, const char *name) +init_thread (struct thread *t, const char *name, int priority) { + ASSERT (t != NULL); + ASSERT (PRI_MIN <= priority && priority <= PRI_MAX); + ASSERT (name != NULL); + memset (t, 0, sizeof *t); + t->status = THREAD_BLOCKED; strlcpy (t->name, name, sizeof t->name); t->stack = (uint8_t *) t + PGSIZE; - t->status = THREAD_BLOCKED; + t->priority = priority; t->magic = THREAD_MAGIC; } @@ -351,25 +343,24 @@ alloc_frame (struct thread *t, size_t size) static struct thread * next_thread_to_run (void) { - if (list_empty (&run_queue)) + if (list_empty (&ready_list)) return idle_thread; else - return list_entry (list_pop_front (&run_queue), struct thread, rq_elem); + return list_entry (list_pop_front (&ready_list), struct thread, elem); } -/* Destroys T, which must be in the dying state and must not be - the running thread. */ +/* Destroys T, which must not be the running thread. */ static void destroy_thread (struct thread *t) { ASSERT (is_thread (t)); - ASSERT (t->status == THREAD_DYING); ASSERT (t != thread_current ()); #ifdef USERPROG - addrspace_destroy (t); + process_destroy (t); #endif - palloc_free (t); + if (t != initial_thread) + palloc_free (t); } /* Completes a thread switch by activating the new thread's page @@ -391,12 +382,17 @@ schedule_tail (struct thread *prev) ASSERT (intr_get_level () == INTR_OFF); + /* Mark us as running. */ cur->status = THREAD_RUNNING; #ifdef USERPROG - addrspace_activate (cur); + /* Activate the new address space. */ + process_activate (); #endif + /* If the thread we switched from is dying, destroy it. + This must happen late because it's not a good idea to + e.g. destroy the page table you're currently using. */ if (prev != NULL && prev->status == THREAD_DYING) destroy_thread (prev); } @@ -420,6 +416,20 @@ schedule (void) prev = switch_threads (cur, next); schedule_tail (prev); } + +/* Returns a tid to use for a new thread. */ +static tid_t +allocate_tid (void) +{ + static tid_t next_tid = 1; + tid_t tid; + + lock_acquire (&tid_lock); + tid = next_tid++; + lock_release (&tid_lock); + + return tid; +} /* Offset of `stack' member within `struct thread'. Used by switch.S, which can't figure it out on its own. */