From 6bae0ee083ed3ef0a1df7e892c6509e47a0ad2dc Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 1 Sep 2004 05:38:55 +0000 Subject: [PATCH] Clean up threads. --- src/threads/interrupt.c | 3 +- src/threads/synch.c | 4 +- src/threads/thread.c | 371 ++++++++++++++++++++++++---------------- src/threads/thread.h | 16 +- 4 files changed, 238 insertions(+), 156 deletions(-) diff --git a/src/threads/interrupt.c b/src/threads/interrupt.c index 885d250..9f71b8c 100644 --- a/src/threads/interrupt.c +++ b/src/threads/interrupt.c @@ -279,7 +279,8 @@ intr_kill (struct intr_frame *f) { case SEL_UCSEG: printk ("%s: dying due to interrupt %#04x (%s).\n", - thread_current ()->name, f->vec_no, intr_name (f->vec_no)); + thread_name (thread_current ()), + f->vec_no, intr_name (f->vec_no)); dump_intr_frame (f); thread_exit (); diff --git a/src/threads/synch.c b/src/threads/synch.c index c3b46a8..b304244 100644 --- a/src/threads/synch.c +++ b/src/threads/synch.c @@ -70,8 +70,8 @@ sema_up (struct semaphore *sema) old_level = intr_disable (); if (!list_empty (&sema->waiters)) - thread_ready (list_entry (list_pop_front (&sema->waiters), - struct thread_elem, elem)->thread); + thread_wake (list_entry (list_pop_front (&sema->waiters), + struct thread_elem, elem)->thread); sema->value++; intr_set_level (old_level); } diff --git a/src/threads/thread.c b/src/threads/thread.c index bae893d..36f33da 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -9,40 +9,37 @@ #include "random.h" #include "switch.h" -/* Offset of `stack' member within `struct thread'. - Used by switch.S, which can't figure it out on its own. */ -uint32_t thread_stack_ofs = offsetof (struct thread, stack); +#define THREAD_MAGIC 0x1234abcdu /* List of processes in THREAD_READY state, that is, processes that are ready to run but not actually running. */ static struct list run_queue; -/* Thread to run when nothing else is ready. */ -static struct thread *idle_thread; +/* Idle thread. */ +static struct thread *idle_thread; /* Thread. */ +static void idle (void *aux UNUSED); /* Thread function. */ -static struct thread *find_next_to_run (void); +/* Stack frame for kernel_thread(). */ +struct kernel_thread_frame + { + void *eip; /* Return address. */ + void (*function) (void *); /* Function to call. */ + void *aux; /* Auxiliary data for function. */ + }; -/* Idle thread. Executes when no other thread is ready to run. */ -static void -idle (void *aux UNUSED) -{ - for (;;) - { - /* Wait for an interrupt. */ - DEBUG (idle, "idle"); - asm ("hlt"); +static void kernel_thread (void (*function) (void *aux), void *aux); - /* Let someone else run. */ - intr_disable (); - thread_sleep (); - intr_enable (); - } -} +static struct thread *next_thread_to_run (void); +static struct thread *new_thread (const char *name); +static bool is_thread (struct thread *t); +static void *alloc_frame (struct thread *t, size_t size); +static void destroy_thread (struct thread *t); +static void schedule (void); +void schedule_tail (struct thread *prev); -/* Initializes the threading system and starts an initial thread - which is immediately scheduled. Never returns to the caller. - The initial thread is named NAME and executes FUNCTION passing - AUX as the argument. */ +/* Initializes the threading system. After calling, create some + threads with thread_create() or thread_execute(), then start + the scheduler with thread_start(). */ void thread_init (void) { @@ -56,10 +53,13 @@ thread_init (void) idle_thread->status = THREAD_BLOCKED; } +/* Starts the thread scheduler. The caller should have created + some threads with thread_create() or thread_execute(). Never + returns to the caller. */ void thread_start (void) { - struct thread *t = find_next_to_run (); + struct thread *t = next_thread_to_run (); if (t->status == THREAD_READY) list_remove (&t->rq_elem); t->status = THREAD_RUNNING; @@ -67,64 +67,13 @@ thread_start (void) NOT_REACHED (); } - -/* Stack frame for kernel_thread(). */ -struct kernel_thread_frame - { - void *eip; /* Return address. */ - void (*function) (void *); /* Function to call. */ - void *aux; /* Auxiliary data for function. */ - }; - -/* Function used as the basis for a kernel thread. */ -static void -kernel_thread (void (*function) (void *aux), void *aux) -{ - ASSERT (function != NULL); - - intr_enable (); /* The scheduler runs with interrupts off. */ - function (aux); /* Execute the thread function. */ - thread_exit (); /* If function() returns, kill the thread. */ -} - -/* Creates a new thread named NAME and initializes its fields. - Returns the new thread if successful or a null pointer on - failure. */ -static struct thread * -new_thread (const char *name) -{ - struct thread *t; - - ASSERT (name != NULL); - - t = palloc_get (PAL_ZERO); - if (t != NULL) - { - strlcpy (t->name, name, sizeof t->name); - t->stack = (uint8_t *) t + PGSIZE; - t->status = THREAD_INITIALIZING; - } - - return t; -} - -/* Allocates a SIZE-byte frame within thread T's stack and - returns a pointer to the frame's base. */ -static void * -alloc_frame (struct thread *t, size_t size) -{ - /* Stack data is always allocated in word-size units. */ - ASSERT (size % sizeof (uint32_t) == 0); - - t->stack -= size; - return t->stack; -} /* Creates a new kernel thread named NAME, which executes - FUNCTION passing AUX as the argument. The thread is added to - the ready queue. Thus, it may be scheduled even before - thread_create() returns. If you need to ensure ordering, then - use synchronization, such as a semaphore. */ + 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, void (*function) (void *aux), void *aux) { @@ -152,20 +101,16 @@ thread_create (const char *name, void (*function) (void *aux), void *aux) sf->eip = switch_entry; /* Add to run queue. */ - thread_ready (t); + thread_wake (t); return t; } -struct thread * -thread_current (void) -{ - uint32_t *esp; - asm ("movl %%esp, %0\n" : "=g" (esp)); - return pg_round_down (esp); -} - #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) { @@ -203,15 +148,20 @@ thread_execute (const char *filename) sf->eip = switch_entry; /* Add to run queue. */ - thread_ready (t); + thread_wake (t); return true; } #endif +/* Transitions T from its current state to THREAD_READY, the + ready-to-run state. On entry, T must be ready or blocked. + (Use thread_yield() to make the running thread ready.) */ void -thread_ready (struct thread *t) +thread_wake (struct thread *t) { + ASSERT (is_thread (t)); + ASSERT (t->status == THREAD_READY || t->status == THREAD_BLOCKED); if (t->status != THREAD_READY) { list_push_back (&run_queue, &t->rq_elem); @@ -219,94 +169,225 @@ thread_ready (struct thread *t) } } -static struct thread * -find_next_to_run (void) +/* Returns the name of thread T. */ +const char * +thread_name (struct thread *t) { - if (list_empty (&run_queue)) - return idle_thread; - else - return list_entry (list_pop_front (&run_queue), struct thread, rq_elem); + ASSERT (is_thread (t)); + return t->name; } +/* Returns the running thread. */ +struct thread * +thread_current (void) +{ + uint32_t *esp; + struct thread *t; + + /* Copy the CPU's stack pointer into `esp', and then round that + down to the start of a page. Because `struct thread' is + always at the beginning of a page and the stack pointer is + somewhere in the middle, this locates the curent thread. */ + asm ("movl %%esp, %0\n" : "=g" (esp)); + t = pg_round_down (esp); + + /* Make sure T is really a thread. + If this assertion fires, then your thread may have + overflowed its stack. Each thread has less than 4 kB of + stack, so a few big automatic arrays or moderate recursion + can cause stack overflow. */ + ASSERT (is_thread (t)); + + return t; +} + +/* Deschedules the current thread and destroys it. Never + returns to the caller. */ void -thread_destroy (struct thread *t) +thread_exit (void) { - ASSERT (t->status == THREAD_DYING); - ASSERT (t != thread_current ()); + ASSERT (!intr_context ()); - palloc_free (t); + intr_disable (); + thread_current ()->status = THREAD_DYING; + schedule (); + NOT_REACHED (); } -void schedule_tail (struct thread *prev); +/* Yields the CPU. The current thread is not put to sleep and + may be scheduled again immediately at the scheduler's whim. */ +void +thread_yield (void) +{ + struct thread *cur = thread_current (); + enum if_level old_level; + + ASSERT (!intr_context ()); + old_level = intr_disable (); + list_push_back (&run_queue, &cur->rq_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_wake(). */ void -schedule_tail (struct thread *prev) +thread_sleep (void) { + ASSERT (!intr_context ()); ASSERT (intr_get_level () == IF_OFF); -#ifdef USERPROG - addrspace_activate (&thread_current ()->addrspace); -#endif + thread_current ()->status = THREAD_BLOCKED; + schedule (); +} + +/* Idle thread. Executes when no other thread is ready to run. */ +static void +idle (void *aux UNUSED) +{ + for (;;) + { + /* Wait for an interrupt. */ + DEBUG (idle, "idle"); + asm ("hlt"); - if (prev != NULL && prev->status == THREAD_DYING) - thread_destroy (prev); + /* Let someone else run. */ + intr_disable (); + thread_sleep (); + intr_enable (); + } } +/* Function used as the basis for a kernel thread. */ static void -thread_schedule (void) +kernel_thread (void (*function) (void *aux), void *aux) { - struct thread *cur, *next, *prev; - - ASSERT (intr_get_level () == IF_OFF); + ASSERT (function != NULL); - cur = thread_current (); - ASSERT (cur->status != THREAD_RUNNING); + intr_enable (); /* The scheduler runs with interrupts off. */ + function (aux); /* Execute the thread function. */ + thread_exit (); /* If function() returns, kill the thread. */ +} + +/* Returns true if T appears to point to a valid thread. */ +static bool +is_thread (struct thread *t) +{ + return t != NULL && t->magic == THREAD_MAGIC; +} - next = find_next_to_run (); +/* Creates a new thread named NAME and initializes its fields. + Returns the new thread if successful or a null pointer on + failure. */ +static struct thread * +new_thread (const char *name) +{ + struct thread *t; - next->status = THREAD_RUNNING; - if (cur != next) + ASSERT (name != NULL); + + t = palloc_get (PAL_ZERO); + if (t != NULL) { - prev = switch_threads (cur, next); + strlcpy (t->name, name, sizeof t->name); + t->stack = (uint8_t *) t + PGSIZE; + t->status = THREAD_BLOCKED; + t->magic = THREAD_MAGIC; + } + + return t; +} - /* Prevent GCC from reordering anything around the thread - switch. */ - asm volatile ("" : : : "memory"); +/* Allocates a SIZE-byte frame at the top of thread T's stack and + returns a pointer to the frame's base. */ +static void * +alloc_frame (struct thread *t, size_t size) +{ + /* Stack data is always allocated in word-size units. */ + ASSERT (is_thread (t)); + ASSERT (size % sizeof (uint32_t) == 0); - schedule_tail (prev); - } + t->stack -= size; + return t->stack; } -void -thread_yield (void) +/* Chooses and returns the next thread to be scheduled. Should + return a thread from the run queue, unless the run queue is + empty. (If the running thread can continue running, then it + will be in the run queue.) If the run queue is empty, return + idle_thread. */ +static struct thread * +next_thread_to_run (void) { - enum if_level old_level; - - ASSERT (!intr_context ()); + if (list_empty (&run_queue)) + return idle_thread; + else + return list_entry (list_pop_front (&run_queue), struct thread, rq_elem); +} - old_level = intr_disable (); - thread_ready (thread_current ()); - thread_schedule (); - intr_set_level (old_level); +/* Destroys T, which must be in the dying state and 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 ()); + + palloc_free (t); } +/* Completes a thread switch by activating the new thread's page + tables, and, if the previous thread is dying, destroying it. + + At this function's invocation, we just switched from thread + PREV, the new thread is already running, and interrupts are + still disabled. This function is normally invoked by + thread_schedule() as its final action before returning, but + the first time a thread is scheduled it is called by + switch_entry() (see switch.S). + + After this function and its caller returns, the thread switch + is complete. */ void -thread_exit (void) +schedule_tail (struct thread *prev) { - ASSERT (!intr_context ()); + struct thread *cur = thread_current (); + + ASSERT (intr_get_level () == IF_OFF); - intr_disable (); - thread_current ()->status = THREAD_DYING; - thread_schedule (); - NOT_REACHED (); + cur->status = THREAD_RUNNING; + if (prev != NULL && prev->status == THREAD_DYING) + destroy_thread (prev); + +#ifdef USERPROG + addrspace_activate (&cur->addrspace); +#endif } -void -thread_sleep (void) +/* Schedules a new process. At entry, interrupts must be off and + the running process's state must have been changed from + running to some other state. This function finds another + thread to run and switches to it. */ +static void +schedule (void) { - ASSERT (!intr_context ()); + struct thread *cur = thread_current (); + struct thread *next = next_thread_to_run (); + ASSERT (intr_get_level () == IF_OFF); + ASSERT (cur->status != THREAD_RUNNING); + ASSERT (is_thread (next)); - thread_current ()->status = THREAD_BLOCKED; - thread_schedule (); + if (cur != next) + { + struct thread *prev = switch_threads (cur, next); + schedule_tail (prev); + } } + +/* Offset of `stack' member within `struct thread'. + Used by switch.S, which can't figure it out on its own. */ +uint32_t thread_stack_ofs = offsetof (struct thread, stack); diff --git a/src/threads/thread.h b/src/threads/thread.h index a5308aa..5cfbadf 100644 --- a/src/threads/thread.h +++ b/src/threads/thread.h @@ -11,7 +11,6 @@ enum thread_status { - THREAD_INITIALIZING, THREAD_RUNNING, THREAD_READY, THREAD_BLOCKED, @@ -20,13 +19,14 @@ enum thread_status struct thread { - enum thread_status status; - char name[16]; - uint8_t *stack; - list_elem rq_elem; + enum thread_status status; /* Thread state. */ + char name[16]; /* Name (for debugging purposes). */ + uint8_t *stack; /* Saved stack pointer. */ + list_elem rq_elem; /* Run queue list element. */ #ifdef USERPROG - struct addrspace addrspace; + struct addrspace addrspace; /* Userland address space. */ #endif + unsigned magic; /* Always set to THREAD_MAGIC. */ }; void thread_init (void); @@ -37,8 +37,8 @@ struct thread *thread_create (const char *name, void (*) (void *aux), void *); bool thread_execute (const char *filename); #endif -void thread_destroy (struct thread *); -void thread_ready (struct thread *); +void thread_wake (struct thread *); +const char *thread_name (struct thread *); struct thread *thread_current (void); void thread_exit (void) NO_RETURN; -- 2.30.2