X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=blobdiff_plain;f=src%2Fthreads%2Fthread.c;h=87f22b80607b4faba8ae2b1e9f93dc5d6659d8cc;hp=e31d838da14a3c5012c6f8b5affd582c6885952c;hb=8b801a69f8e0c2c4ef7e32a2476786f80f433b8e;hpb=5fbedf1d20c2b2f2dbc8c7ebd64cc7b4812a44bf diff --git a/src/threads/thread.c b/src/threads/thread.c index e31d838..87f22b8 100644 --- a/src/threads/thread.c +++ b/src/threads/thread.c @@ -1,24 +1,41 @@ -#include "thread.h" +#include "threads/thread.h" +#include #include -#include "debug.h" -#include "interrupt.h" -#include "intr-stubs.h" -#include "lib.h" -#include "gdt.h" -#include "mmu.h" -#include "palloc.h" -#include "random.h" -#include "switch.h" - -#define THREAD_MAGIC 0x1234abcdu +#include +#include +#include +#include "threads/flags.h" +#include "threads/interrupt.h" +#include "threads/intr-stubs.h" +#include "threads/palloc.h" +#include "threads/switch.h" +#include "threads/synch.h" +#include "threads/vaddr.h" +#ifdef USERPROG +#include "userprog/process.h" +#endif + +/* 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; + +/* List of all processes. Processes are added to this list + when they are first scheduled and removed when they exit. */ +static struct list all_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 @@ -28,64 +45,143 @@ struct kernel_thread_frame void *aux; /* Auxiliary data for function. */ }; +/* Statistics. */ +static long long idle_ticks; /* # of timer ticks spent idle. */ +static long long kernel_ticks; /* # of timer ticks in kernel threads. */ +static long long user_ticks; /* # of timer ticks in user programs. */ + +/* Scheduling. */ +#define TIME_SLICE 4 /* # of timer ticks to give each thread. */ +static unsigned thread_ticks; /* # of timer ticks since last yield. */ + +/* If false (default), use round-robin scheduler. + If true, use multi-level feedback queue scheduler. + Controlled by kernel command-line option "-o mlfqs". */ +bool thread_mlfqs; + 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 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 init_thread (struct thread *, const char *name, int priority); +static bool is_thread (struct thread *) UNUSED; +static void *alloc_frame (struct thread *, size_t size); static void schedule (void); -void schedule_tail (struct thread *prev); +void thread_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. This can't work in + general and it is possible in this case only because loader.S + was careful to put the bottom of the stack at a page boundary. -/* Initializes the threading system. After calling, create some - threads with thread_create() or thread_execute(), then start - the scheduler with thread_start(). */ + Also initializes the run queue and the tid lock. + + After calling this function, be sure to initialize the page + allocator before trying to create any threads with + thread_create(). + + It is not safe to call thread_current() until this function + finishes. */ void thread_init (void) { ASSERT (intr_get_level () == INTR_OFF); - /* Initialize run queue. */ - list_init (&run_queue); + lock_init (&tid_lock); + list_init (&ready_list); + list_init (&all_list); - /* Create idle thread. */ - idle_thread = thread_create ("idle", idle, NULL); - idle_thread->status = THREAD_BLOCKED; + /* Set up a thread structure for the running thread. */ + initial_thread = running_thread (); + init_thread (initial_thread, "main", PRI_DEFAULT); + initial_thread->status = THREAD_RUNNING; + initial_thread->tid = allocate_tid (); } -/* Starts the thread scheduler. The caller should have created - some threads with thread_create() or thread_execute(). Never - returns to the caller. */ +/* Starts preemptive thread scheduling by enabling interrupts. + Also creates the idle thread. */ void thread_start (void) { - struct thread *t = next_thread_to_run (); - if (t->status == THREAD_READY) - list_remove (&t->rq_elem); - t->status = THREAD_RUNNING; - switch_threads (NULL, t); + /* Create the idle thread. */ + struct semaphore idle_started; + sema_init (&idle_started, 0); + thread_create ("idle", PRI_MIN, idle, &idle_started); - NOT_REACHED (); + /* Start preemptive thread scheduling. */ + intr_enable (); + + /* Wait for the idle thread to initialize idle_thread. */ + sema_down (&idle_started); } -/* 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) +/* Called by the timer interrupt handler at each timer tick. + Thus, this function runs in an external interrupt context. */ +void +thread_tick (void) +{ + struct thread *t = thread_current (); + + /* Update statistics. */ + if (t == idle_thread) + idle_ticks++; +#ifdef USERPROG + else if (t->pagedir != NULL) + user_ticks++; +#endif + else + kernel_ticks++; + + /* Enforce preemption. */ + if (++thread_ticks >= TIME_SLICE) + intr_yield_on_return (); +} + +/* Prints thread statistics. */ +void +thread_print_stats (void) +{ + printf ("Thread: %lld idle ticks, %lld kernel ticks, %lld user ticks\n", + idle_ticks, kernel_ticks, user_ticks); +} + +/* 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. Returns the thread identifier + for the new thread, or TID_ERROR if creation fails. + + 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. Contrariwise, the original + thread may run for any amount of time before the new thread is + scheduled. Use a semaphore or some other form of + synchronization if you need to ensure ordering. + + 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); + /* Allocate thread. */ + t = palloc_get_page (PAL_ZERO); + if (t == NULL) + return TID_ERROR; + + /* Initialize thread. */ + init_thread (t, name, priority); + tid = t->tid = allocate_tid (); /* Stack frame for kernel_thread(). */ kf = alloc_frame (t, sizeof *kf); @@ -100,108 +196,85 @@ thread_create (const char *name, thread_func *function, void *aux) /* Stack frame for switch_threads(). */ sf = alloc_frame (t, sizeof *sf); sf->eip = switch_entry; + sf->ebp = 0; /* Add to run queue. */ - thread_wake (t); + 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; +/* Puts the current thread to sleep. It will not be scheduled + again until awoken by thread_unblock(). - /* Add to run queue. */ - thread_wake (t); + 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) +{ + ASSERT (!intr_context ()); + ASSERT (intr_get_level () == INTR_OFF); - return true; + thread_current ()->status = THREAD_BLOCKED; + schedule (); } -#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.) */ +/* Transitions a blocked thread T to the ready-to-run state. + This is an error if T is not blocked. (Use thread_yield() to + make the running thread ready.) + + This function does not preempt the running thread. This can + be important: if the caller had disabled interrupts itself, + it may expect that it can atomically unblock a thread and + update other data. */ void -thread_wake (struct thread *t) +thread_unblock (struct thread *t) { + enum intr_level old_level; + 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); - t->status = THREAD_READY; - } + + old_level = intr_disable (); + 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. */ +/* Returns the running thread. + 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) { - 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); - + struct thread *t = running_thread (); + /* 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. */ + If either of these assertions fire, 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)); + ASSERT (t->status == THREAD_RUNNING); 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 @@ -209,7 +282,15 @@ thread_exit (void) { ASSERT (!intr_context ()); +#ifdef USERPROG + process_exit (); +#endif + + /* Remove thread from all threads list, set our status to dying, + and schedule another process. That process will destroy us + when it calls thread_schedule_tail(). */ intr_disable (); + list_remove (&thread_current()->allelem); thread_current ()->status = THREAD_DYING; schedule (); NOT_REACHED (); @@ -226,38 +307,110 @@ thread_yield (void) ASSERT (!intr_context ()); old_level = intr_disable (); - list_push_back (&run_queue, &cur->rq_elem); + if (cur != idle_thread) + 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_wake(). */ +/* Invoke function 'func' on all threads, passing along 'aux'. + This function must be called with interrupts off. */ void -thread_sleep (void) +thread_foreach (thread_action_func *func, void *aux) { - ASSERT (!intr_context ()); + struct list_elem *e; + ASSERT (intr_get_level () == INTR_OFF); - thread_current ()->status = THREAD_BLOCKED; - schedule (); + for (e = list_begin (&all_list); e != list_end (&all_list); + e = list_next (e)) + { + struct thread *t = list_entry (e, struct thread, allelem); + func (t, aux); + } +} + +/* Sets the current thread's priority to NEW_PRIORITY. */ +void +thread_set_priority (int new_priority) +{ + thread_current ()->priority = new_priority; +} + +/* Returns the current thread's priority. */ +int +thread_get_priority (void) +{ + return thread_current ()->priority; +} + +/* Sets the current thread's nice value to NICE. */ +void +thread_set_nice (int nice UNUSED) +{ + /* Not yet implemented. */ +} + +/* Returns the current thread's nice value. */ +int +thread_get_nice (void) +{ + /* Not yet implemented. */ + return 0; +} + +/* Returns 100 times the system load average. */ +int +thread_get_load_avg (void) +{ + /* Not yet implemented. */ + return 0; +} + +/* Returns 100 times the current thread's recent_cpu value. */ +int +thread_get_recent_cpu (void) +{ + /* Not yet implemented. */ + return 0; } -/* Idle thread. Executes when no other thread is ready to run. */ +/* Idle thread. Executes when no other thread is ready to run. + + The idle thread is initially put on the ready list by + thread_start(). It will be scheduled once initially, at which + point it initializes idle_thread, "up"s the semaphore passed + to it to enable thread_start() to continue, and immediately + blocks. After that, the idle thread never appears in the + ready list. It is returned by next_thread_to_run() as a + special case when the ready list is empty. */ static void -idle (void *aux UNUSED) +idle (void *idle_started_ UNUSED) { + struct semaphore *idle_started = idle_started_; + idle_thread = thread_current (); + sema_up (idle_started); + for (;;) { - /* Wait for an interrupt. */ - DEBUG (idle, "idle"); - asm ("hlt"); - /* Let someone else run. */ intr_disable (); - thread_sleep (); - intr_enable (); + thread_block (); + + /* Re-enable interrupts and wait for the next one. + + The `sti' instruction disables interrupts until the + completion of the next instruction, so these two + instructions are executed atomically. This atomicity is + important; otherwise, an interrupt could be handled + between re-enabling interrupts and waiting for the next + one to occur, wasting as much as one clock tick worth of + time. + + See [IA32-v2a] "HLT", [IA32-v2b] "STI", and [IA32-v3a] + 7.11.1 "HLT Instruction". */ + asm volatile ("sti; hlt" : : : "memory"); } } @@ -272,33 +425,48 @@ kernel_thread (thread_func *function, void *aux) thread_exit (); /* If function() returns, kill the thread. */ } +/* Returns the running thread. */ +struct thread * +running_thread (void) +{ + uint32_t *esp; + + /* 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 ("mov %%esp, %0" : "=g" (esp)); + return pg_round_down (esp); +} + /* Returns true if T appears to point to a valid thread. */ static bool -is_thread (struct thread *t) +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. */ -static struct thread * -new_thread (const char *name) +/* Does basic initialization of T as a blocked thread named + NAME. */ +static void +init_thread (struct thread *t, const char *name, int priority) { - struct thread *t; + enum intr_level old_level; + ASSERT (t != NULL); + ASSERT (PRI_MIN <= priority && priority <= PRI_MAX); 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_BLOCKED; - t->magic = THREAD_MAGIC; - } - - return t; + + memset (t, 0, sizeof *t); + t->status = THREAD_BLOCKED; + strlcpy (t->name, name, sizeof t->name); + t->stack = (uint8_t *) t + PGSIZE; + t->priority = priority; + t->magic = THREAD_MAGIC; + + old_level = intr_disable (); + list_push_back (&all_list, &t->allelem); + intr_set_level (old_level); } /* Allocates a SIZE-byte frame at the top of thread T's stack and @@ -322,23 +490,10 @@ 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); -} - -/* 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 ()); - - addrspace_destroy (t); - palloc_free (t); + return list_entry (list_pop_front (&ready_list), struct thread, elem); } /* Completes a thread switch by activating the new thread's page @@ -351,43 +506,77 @@ destroy_thread (struct thread *t) the first time a thread is scheduled it is called by switch_entry() (see switch.S). + It's not safe to call printf() until the thread switch is + complete. In practice that means that printf()s should be + added at the end of the function. + After this function and its caller returns, the thread switch is complete. */ void -schedule_tail (struct thread *prev) +thread_schedule_tail (struct thread *prev) { - struct thread *cur = thread_current (); + struct thread *cur = running_thread (); ASSERT (intr_get_level () == INTR_OFF); + /* Mark us as running. */ cur->status = THREAD_RUNNING; - if (prev != NULL && prev->status == THREAD_DYING) - destroy_thread (prev); + + /* Start new time slice. */ + thread_ticks = 0; #ifdef USERPROG - addrspace_activate (cur); + /* Activate the new address space. */ + process_activate (); #endif + + /* If the thread we switched from is dying, destroy its struct + thread. This must happen late so that thread_exit() doesn't + pull out the rug under itself. (We don't free + initial_thread because its memory was not obtained via + palloc().) */ + if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread) + { + ASSERT (prev != cur); + palloc_free_page (prev); + } } /* 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. */ + thread to run and switches to it. + + It's not safe to call printf() until thread_schedule_tail() + has completed. */ static void schedule (void) { - struct thread *cur = thread_current (); + struct thread *cur = running_thread (); struct thread *next = next_thread_to_run (); + struct thread *prev = NULL; ASSERT (intr_get_level () == INTR_OFF); ASSERT (cur->status != THREAD_RUNNING); ASSERT (is_thread (next)); if (cur != next) - { - struct thread *prev = switch_threads (cur, next); - schedule_tail (prev); - } + prev = switch_threads (cur, next); + thread_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'.