-diff -u src/devices/timer.c~ src/devices/timer.c
---- src/devices/timer.c~ 2005-05-24 15:52:43.000000000 -0700
-+++ src/devices/timer.c 2005-05-26 15:19:20.000000000 -0700
-@@ -23,6 +23,9 @@ static volatile int64_t ticks;
+diff --git a/src/devices/timer.c b/src/devices/timer.c
+index befaaae..1aebae7 100644
+--- a/src/devices/timer.c
++++ b/src/devices/timer.c
+@@ -24,6 +24,9 @@ static int64_t ticks;
Initialized by timer_calibrate(). */
static unsigned loops_per_tick;
static intr_handler_func timer_interrupt;
static bool too_many_loops (unsigned loops);
static void busy_wait (int64_t loops);
-@@ -43,6 +46,8 @@ timer_init (void)
- outb (0x40, count >> 8);
-
+@@ -37,6 +40,8 @@ timer_init (void)
+ {
+ pit_configure_channel (0, 2, TIMER_FREQ);
intr_register_ext (0x20, timer_interrupt, "8254 Timer");
+
+ list_init (&wait_list);
}
/* Calibrates loops_per_tick, used to implement brief delays. */
-@@ -87,15 +92,36 @@ timer_elapsed (int64_t then)
+@@ -84,16 +89,37 @@ timer_elapsed (int64_t then)
return timer_ticks () - then;
}
+ return a->wakeup_time < b->wakeup_time;
+}
+
- /* Suspends execution for approximately TICKS timer ticks. */
+ /* Sleeps for approximately TICKS timer ticks. Interrupts must
+ be turned on. */
void
timer_sleep (int64_t ticks)
{
+ sema_down (&t->timer_sema);
}
- /* Suspends execution for approximately MS milliseconds. */
-@@ -132,6 +158,16 @@ timer_interrupt (struct intr_frame *args
+ /* Sleeps for approximately MS milliseconds. Interrupts must be
+@@ -172,6 +198,17 @@ timer_interrupt (struct intr_frame *args UNUSED)
{
ticks++;
thread_tick ();
+ if (ticks < t->wakeup_time)
+ break;
+ sema_up (&t->timer_sema);
++ thread_yield_to_higher_priority ();
+ list_pop_front (&wait_list);
+ }
}
/* Returns true if LOOPS iterations waits for more than one timer
-diff -u src/threads/fixed-point.h~ src/threads/fixed-point.h
---- src/threads/fixed-point.h~ 1969-12-31 16:00:00.000000000 -0800
-+++ src/threads/fixed-point.h 2005-06-02 14:11:21.000000000 -0700
+diff --git a/src/threads/fixed-point.h b/src/threads/fixed-point.h
+new file mode 100644
+index 0000000..ca88f97
+--- /dev/null
++++ b/src/threads/fixed-point.h
@@ -0,0 +1,120 @@
+#ifndef THREADS_FIXED_POINT_H
+#define THREADS_FIXED_POINT_H
+}
+
+#endif /* threads/fixed-point.h */
-diff -u src/threads/synch.c~ src/threads/synch.c
---- src/threads/synch.c~ 2005-05-24 20:47:28.000000000 -0700
-+++ src/threads/synch.c 2005-06-02 14:20:15.000000000 -0700
-@@ -114,10 +114,28 @@ sema_up (struct semaphore *sema)
+diff --git a/src/threads/synch.c b/src/threads/synch.c
+index 317c68a..53197bb 100644
+--- a/src/threads/synch.c
++++ b/src/threads/synch.c
+@@ -113,10 +113,28 @@ sema_up (struct semaphore *sema)
ASSERT (sema != NULL);
old_level = intr_disable ();
intr_set_level (old_level);
}
-@@ -200,6 +218,23 @@ lock_acquire (struct lock *lock)
+@@ -192,12 +210,33 @@ lock_init (struct lock *lock)
+ void
+ lock_acquire (struct lock *lock)
+ {
++ enum intr_level old_level;
++
+ ASSERT (lock != NULL);
+ ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
- old_level = intr_disable ();
++ old_level = intr_disable ();
+
+ if (lock->holder != NULL)
+ {
+
sema_down (&lock->semaphore);
lock->holder = thread_current ();
- intr_set_level (old_level);
-@@ -238,13 +273,37 @@ void
++ intr_set_level (old_level);
+ }
+
+ /* Tries to acquires LOCK and returns true if successful or false
+@@ -228,11 +267,39 @@ lock_try_acquire (struct lock *lock)
+ void
lock_release (struct lock *lock)
{
- enum intr_level old_level;
++ enum intr_level old_level;
+ struct thread *t = thread_current ();
+ struct list_elem *e;
-
++
ASSERT (lock != NULL);
ASSERT (lock_held_by_current_thread (lock));
- old_level = intr_disable ();
++ old_level = intr_disable ();
+
+ /* Return donations to threads that want this lock. */
+ for (e = list_begin (&t->donors); e != list_end (&t->donors); )
+ thread_recompute_priority (t);
+ thread_yield_to_higher_priority ();
+
- intr_set_level (old_level);
++ intr_set_level (old_level);
}
-@@ -264,6 +323,7 @@ struct semaphore_elem
+ /* Returns true if the current thread holds LOCK, false
+@@ -251,6 +318,7 @@ struct semaphore_elem
{
struct list_elem elem; /* List element. */
struct semaphore semaphore; /* This semaphore. */
};
/* Initializes condition variable COND. A condition variable
-@@ -308,12 +368,26 @@ cond_wait (struct condition *cond, struc
+@@ -295,12 +363,26 @@ cond_wait (struct condition *cond, struct lock *lock)
ASSERT (lock_held_by_current_thread (lock));
sema_init (&waiter.semaphore, 0);
+ const struct semaphore_elem *b
+ = list_entry (b_, struct semaphore_elem, elem);
+
-+ return a->thread->priority > b->thread->priority;
++ return a->thread->priority < b->thread->priority;
+}
+
/* If any threads are waiting on COND (protected by LOCK), then
this function signals one of them to wake up from its wait.
LOCK must be held before calling this function.
-@@ -330,8 +404,12 @@ cond_signal (struct condition *cond, str
+@@ -317,8 +399,12 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
ASSERT (lock_held_by_current_thread (lock));
if (!list_empty (&cond->waiters))
}
/* Wakes up all threads, if any, waiting on COND (protected by
-diff -u src/threads/thread.c~ src/threads/thread.c
---- src/threads/thread.c~ 2005-06-02 14:35:12.000000000 -0700
-+++ src/threads/thread.c 2005-06-02 14:55:56.000000000 -0700
-@@ -5,12 +5,14 @@
+diff --git a/src/threads/thread.c b/src/threads/thread.c
+index 87f22b8..86614f5 100644
+--- a/src/threads/thread.c
++++ b/src/threads/thread.c
+@@ -5,11 +5,13 @@
#include <stdio.h>
#include <string.h>
#include "threads/flags.h"
+#include "threads/init.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"
+#include "devices/timer.h"
+ #include "threads/vaddr.h"
#ifdef USERPROG
#include "userprog/process.h"
- #endif
-@@ -24,6 +26,9 @@
- that are ready to run but not actually running. */
- static struct list ready_list;
-
-+/* List of all threads. */
-+static struct list all_threads_list;
-+
- /* Idle thread. */
- static struct thread *idle_thread;
-
-@@ -49,6 +54,7 @@ static long long user_ticks; /* # of
+@@ -53,6 +55,7 @@ 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. */
+static fixed_point_t load_avg; /* Load average. */
- static void kernel_thread (thread_func *, void *aux);
-
-@@ -79,12 +85,15 @@ thread_init (void)
-
+ /* If false (default), use round-robin scheduler.
+ If true, use multi-level feedback queue scheduler.
+@@ -92,6 +95,7 @@ thread_init (void)
lock_init (&tid_lock);
list_init (&ready_list);
-+ list_init (&all_threads_list);
+ list_init (&all_list);
+ load_avg = fix_int (0);
/* 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 ();
-+ list_push_front (&all_threads_list, &initial_thread->all_elem);
+@@ -117,6 +121,18 @@ thread_start (void)
+ sema_down (&idle_started);
}
- /* Starts preemptive thread scheduling by enabling interrupts.
-@@ -101,9 +110,48 @@ void
++/* Adjust recent CPU of a thread based on load factor
++ and recompute its priority. */
++static void
++adjust_recent_cpu (struct thread *t, void *aux)
++{
++ fixed_point_t load_factor = *(fixed_point_t *)aux;
++
++ t->recent_cpu = fix_add (fix_mul (load_factor, t->recent_cpu),
++ fix_int (t->nice));
++ thread_recompute_priority (t);
++}
++
+ /* Called by the timer interrupt handler at each timer tick.
+ Thus, this function runs in an external interrupt context. */
+ void
+@@ -134,9 +150,41 @@ thread_tick (void)
else
kernel_ticks++;
- /* Enforce preemption. */
- if (++thread_ticks >= TIME_SLICE)
- intr_yield_on_return ();
-+ if (enable_mlfqs)
++ if (thread_mlfqs)
+ {
+ /* Update load average. */
+ if (timer_ticks () % TIMER_FREQ == 0)
+ /* Update recent_cpu and thread priorities once per second. */
+ if (timer_ticks () % TIMER_FREQ == 0)
+ {
-+ struct list_elem *e;
+ fixed_point_t twice_load = fix_scale (load_avg, 2);
+ fixed_point_t twice_load_plus_1 = fix_add (twice_load, fix_int (1));
+ fixed_point_t load_factor = fix_div (twice_load, twice_load_plus_1);
-+ for (e = list_begin (&all_threads_list);
-+ e != list_end (&all_threads_list); e = list_next (e))
-+ {
-+ struct thread *t = list_entry (e, struct thread, all_elem);
-+ t->recent_cpu = fix_add (fix_mul (load_factor, t->recent_cpu),
-+ fix_int (t->nice));
-+ thread_recompute_priority (t);
-+ }
++
++ thread_foreach (adjust_recent_cpu, &load_factor);
+ }
+ }
+
+ /* Switch threads if time slice has expired. */
+ if (++thread_ticks >= TIME_SLICE)
+ {
-+ if (enable_mlfqs)
++ if (thread_mlfqs)
+ thread_recompute_priority (thread_current ());
+ intr_yield_on_return ();
+ }
}
/* Prints thread statistics. */
-@@ -143,10 +191,12 @@ tid_t
+@@ -166,6 +214,7 @@ 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;
-+ enum intr_level old_level;
- tid_t tid;
-
- ASSERT (function != NULL);
-@@ -157,8 +207,10 @@ thread_create (const char *name, int pri
+@@ -180,8 +229,10 @@ thread_create (const char *name, int priority,
return TID_ERROR;
/* Initialize thread. */
- init_thread (t, name, priority);
-+ init_thread (t, name, enable_mlfqs ? cur->priority : priority);
++ init_thread (t, name, thread_mlfqs ? cur->priority : priority);
tid = t->tid = allocate_tid ();
+ t->nice = cur->nice;
+ t->recent_cpu = cur->recent_cpu;
/* Stack frame for kernel_thread(). */
kf = alloc_frame (t, sizeof *kf);
-@@ -174,8 +226,15 @@ thread_create (const char *name, int pri
- sf = alloc_frame (t, sizeof *sf);
- sf->eip = switch_entry;
+@@ -200,6 +251,8 @@ thread_create (const char *name, int priority,
-+ /* Add to list of all threads. */
-+ old_level = intr_disable ();
-+ list_push_front (&all_threads_list, &t->all_elem);
-+ intr_set_level (old_level);
-+
/* Add to run queue. */
thread_unblock (t);
-+ if (priority < thread_get_priority ())
++ if (priority > thread_get_priority ())
+ thread_yield ();
return tid;
}
-@@ -196,6 +255,19 @@ thread_block (void)
+@@ -220,6 +273,19 @@ thread_block (void)
schedule ();
}
+ const struct thread *a = list_entry (a_, struct thread, elem);
+ const struct thread *b = list_entry (b_, struct thread, elem);
+
-+ return a->priority > b->priority;
++ return a->priority < b->priority;
+}
+
/* 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.) */
-@@ -260,6 +332,7 @@ thread_exit (void)
- /* Just set our status to dying and schedule another process.
- We will be destroyed during the call to schedule_tail(). */
- intr_disable ();
-+ list_remove (&thread_current ()->all_elem);
- thread_current ()->status = THREAD_DYING;
- schedule ();
- NOT_REACHED ();
-@@ -282,11 +355,26 @@ thread_yield (void)
- intr_set_level (old_level);
+ make the running thread ready.)
+@@ -331,11 +397,26 @@ thread_foreach (thread_action_func *func, void *aux)
+ }
}
-/* Sets the current thread's priority to NEW_PRIORITY. */
+thread_set_priority (int priority)
{
- thread_current ()->priority = new_priority;
-+ if (!enable_mlfqs)
++ if (!thread_mlfqs)
+ {
+ struct thread *t = thread_current ();
+
}
/* Returns the current thread's priority. */
-@@ -298,33 +386,93 @@ thread_get_priority (void)
+@@ -347,33 +428,98 @@ thread_get_priority (void)
/* Sets the current thread's nice value to NICE. */
void
+ const struct thread *a = list_entry (a_, struct thread, donor_elem);
+ const struct thread *b = list_entry (b_, struct thread, donor_elem);
+
-+ return a->priority > b->priority;
++ return a->priority < b->priority;
+}
+
+/* Recomputes T's priority in terms of its normal priority and
+{
+ int old_priority = t->priority;
+ int default_priority = t->normal_priority;
-+ int donation = PRI_MAX;
-+ if (enable_mlfqs)
++ int donation = PRI_MIN;
++ if (thread_mlfqs)
+ {
-+ default_priority = fix_round (t->recent_cpu) / 4 + t->nice * 2;
++ default_priority = PRI_MAX - fix_round (t->recent_cpu) / 4 - t->nice * 2;
+ if (default_priority < PRI_MIN)
+ default_priority = PRI_MIN;
+ else if (default_priority > PRI_MAX)
+ if (!list_empty (&t->donors))
+ donation = list_entry (list_max (&t->donors, donated_lower_priority, NULL),
+ struct thread, donor_elem)->priority;
-+ t->priority = donation < default_priority ? donation : default_priority;
-+ if (t->priority < old_priority && t->donee != NULL)
++ t->priority = donation > default_priority ? donation : default_priority;
++ if (t->priority > old_priority && t->donee != NULL)
+ thread_recompute_priority (t->donee);
+}
+
+ struct thread *max = list_entry (list_max (&ready_list,
+ thread_lower_priority, NULL),
+ struct thread, elem);
-+ if (max->priority < cur->priority)
-+ thread_yield ();
++ if (max->priority > cur->priority)
++ {
++ if (intr_context ())
++ intr_yield_on_return ();
++ else
++ thread_yield ();
++ }
+ }
+ intr_set_level (old_level);
}
\f
- /* Idle thread. Executes when no other thread is ready to run. */
-@@ -399,8 +547,10 @@ init_thread (struct thread *t, const cha
+ /* Idle thread. Executes when no other thread is ready to run.
+@@ -461,9 +607,10 @@ init_thread (struct thread *t, const char *name, int priority)
t->status = THREAD_BLOCKED;
strlcpy (t->name, name, sizeof t->name);
t->stack = (uint8_t *) t + PGSIZE;
- t->priority = priority;
+ t->priority = t->normal_priority = priority;
t->magic = THREAD_MAGIC;
+-
+ sema_init (&t->timer_sema, 0);
+ list_init (&t->donors);
- }
-
- /* Allocates a SIZE-byte frame at the top of thread T's stack and
-@@ -426,8 +576,14 @@ next_thread_to_run (void)
+ old_level = intr_disable ();
+ list_push_back (&all_list, &t->allelem);
+ intr_set_level (old_level);
+@@ -492,8 +639,14 @@ next_thread_to_run (void)
{
if (list_empty (&ready_list))
return idle_thread;
}
/* Completes a thread switch by activating the new thread's page
-diff -u src/threads/thread.h~ src/threads/thread.h
---- src/threads/thread.h~ 2005-06-02 14:32:36.000000000 -0700
-+++ src/threads/thread.h 2005-06-02 14:38:46.000000000 -0700
+diff --git a/src/threads/thread.h b/src/threads/thread.h
+index 7965c06..6601963 100644
+--- a/src/threads/thread.h
++++ b/src/threads/thread.h
@@ -4,6 +4,8 @@
#include <debug.h>
#include <list.h>
/* States in a thread's life cycle. */
enum thread_status
-@@ -87,11 +89,26 @@ struct thread
+@@ -87,12 +89,26 @@ struct thread
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
uint8_t *stack; /* Saved stack pointer. */
+ struct lock *want_lock; /* Lock we're waiting to acquire. */
+ int nice; /* Niceness. */
+ fixed_point_t recent_cpu; /* Recent amount of CPU time. */
-+ struct list_elem all_elem; /* all_threads list element. */
+ struct list_elem allelem; /* List element for all threads list. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
+ /* Alarm clock. */
+ int64_t wakeup_time; /* Time to wake this thread up. */
-+ struct list_elem timer_elem; /* Element in timer_wait_list. */
++ struct list_elem timer_elem; /* Element in wait_list. */
+ struct semaphore timer_sema; /* Semaphore. */
-+
++
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint32_t *pagedir; /* Page directory. */
-@@ -118,6 +135,10 @@ const char *thread_name (void);
+@@ -125,6 +141,10 @@ const char *thread_name (void);
void thread_exit (void) NO_RETURN;
void thread_yield (void);
+bool thread_lower_priority (const struct list_elem *, const struct list_elem *,
+ void *aux);
- int thread_get_priority (void);
- void thread_set_priority (int);
+ /* Performs some operation on thread t, given auxiliary data AUX. */
+ typedef void thread_action_func (struct thread *t, void *aux);
projects / pintos-anon / blobdiff