Update cond_wait to insert into waiters list in sorted order of priority

.gitignore

@@ -4,6 +4,13 @@
 #ignore pdf files (just keep source files)
 *.pdf
 
+#ignore Mac OS generated files
+.DS_Store
+
+#ignore code editor generated directories
+.idea
+.vscode
+
 #ignore junk files from latex output
 *.out
 *.log
@@ -24,6 +31,3 @@
 *.nav
 *.toc
 
-#ignore files from CLion/VSCode IDEs
-.idea
-.vscode

src/threads/fixed-point.h

@@ -1,95 +0,0 @@
-#include <stdint.h>
-#ifndef FIXED_POINT_H
-#define FIXED_POINT_H
-
-typedef struct
-{
-  int32_t raw;
-} fp32_t;
-
-/* Fixed Point Arithmetic bit count constants */
-#define NUM_FRAC_BITS 14
-#define NUM_INT_BITS (31 - NUM_FRAC_BITS)
-#define CONVERSION_CONST (1 << NUM_FRAC_BITS) /* f = 2^q, (2^20) */
-
-/* Fixed Point Arithmetic conversion operations */
-/* Converts an integer n to a fixed point number */
-inline fp32_t
-int_to_fp (int32_t n)
-{
-  return (fp32_t){ n * CONVERSION_CONST };
-}
-
-/* Handles conversion of fixed point to integer. First version truncates, second one rounds */
-inline int32_t
-fp_floor (fp32_t x)
-{
-  return x.raw / CONVERSION_CONST;
-}
-
-inline int32_t
-fp_round (fp32_t x)
-{
-  if (x.raw >= 0)
-    return (x.raw + CONVERSION_CONST / 2) / CONVERSION_CONST;
-  else
-    return (x.raw - CONVERSION_CONST / 2) / CONVERSION_CONST;
-}
-
-/* Add two fixed points */
-inline fp32_t
-fp_add (fp32_t x, fp32_t y)
-{
-  return (fp32_t){ x.raw + y.raw };
-}
-
-/* Subtract two fixed points */
-inline fp32_t
-fp_sub (fp32_t x, fp32_t y)
-{
-  return (fp32_t){ x.raw - y.raw };
-}
-
-/* Add fixed point to integer */
-inline fp32_t
-fp_add_int (fp32_t x, int32_t n)
-{
-  return (fp32_t){ x.raw + n * CONVERSION_CONST };
-}
-
-/* Subtract integer from fixed point */
-inline fp32_t
-fp_sub_int (fp32_t x, int32_t n)
-{
-  return (fp32_t){ x.raw - n * CONVERSION_CONST };
-}
-
-/* Multiple two fixed points */
-inline fp32_t
-fp_mul (fp32_t x, fp32_t y)
-{
-  return (fp32_t){ ((int64_t)x.raw) * y.raw / CONVERSION_CONST };
-}
-
-/* Divide two fixed points */
-inline fp32_t
-fp_div (fp32_t x, fp32_t y)
-{
-  return (fp32_t){ ((int64_t)x.raw) * CONVERSION_CONST / y.raw };
-}
-
-/* Multiply fixed point and integer */
-inline fp32_t
-fp_mul_int (fp32_t x, int32_t n)
-{
-  return (fp32_t){ x.raw * n };
-}
-
-/* Divide fixed point by integer */
-inline fp32_t
-fp_div_int (fp32_t x, int32_t n)
-{
-  return (fp32_t){ x.raw / n };
-}
-
-#endif //FIXED_POINT_H

src/threads/synch.c

@@ -68,7 +68,8 @@ sema_down (struct semaphore *sema)
   old_level = intr_disable ();
   while (sema->value == 0) 
     {
-      list_push_back (&sema->waiters, &thread_current ()->elem);
+      list_insert_ordered(&sema->waiters, &thread_current ()->elem,
+                          priority_more, NULL);
       thread_block ();
     }
   sema->value--;
@@ -113,11 +114,22 @@ sema_up (struct semaphore *sema)
   ASSERT (sema != NULL);
 
   old_level = intr_disable ();
-  if (!list_empty (&sema->waiters)) 
-    thread_unblock (list_entry (list_pop_front (&sema->waiters),
-                                struct thread, elem));
+
+  /* Wake up (unblock) the highest priority thread from the waiters list */
+  struct thread *t = NULL;
+  if (!list_empty (&sema->waiters))
+    {
+      t = list_entry (list_pop_front (&sema->waiters), struct thread, elem);
+      thread_unblock (t);
+    }
+
   sema->value++;
   intr_set_level (old_level);
+
+  /* If the unblocked thread has higher priority than the current running thread
+     then yield the CPU to the unblocked thread */
+  if (!intr_context() && t != NULL && t->priority > thread_get_priority ())
+    thread_yield ();
 }
 
 static void sema_test_helper (void *sema_);
@@ -233,7 +245,6 @@ lock_release (struct lock *lock)
 
   lock->holder = NULL;
   sema_up (&lock->semaphore);
-  thread_yield ();
 }
 
 /* Returns true if the current thread holds LOCK, false
@@ -254,6 +265,54 @@ struct semaphore_elem
     struct semaphore semaphore;         /* This semaphore. */
   };
 
+/* Function that compares the two *semaphores* associated with the provided
+   list_elem structures. [i.e., takes list_elem of semaphore_elem, and]
+   Returns true if the thread associated with the semaphore associated with a_
+   has a higher priority than that of b_.
+
+    If aux is provided, then it is a pointer to an integer representing the
+    priority of the first semaphore. This is useful when the thread has not been
+    sema'd down yet. */
+static bool
+sema_priority_more(const struct list_elem *a_, const struct list_elem *b_,
+                   void *aux)
+{
+  int a_priority, b_priority;
+
+  /* If an aux is provided, then use it as the priority of the first semaphore.
+     Otherwise, get the priority of the first semaphore. */
+  if (aux != NULL)
+    a_priority = *(int *) aux;
+  else
+    {
+      struct semaphore_elem *a = list_entry(a_, struct semaphore_elem, elem);
+
+      /* If waiters list is empty, return false (i.e., a has lower priority) */
+      if (list_empty(&a->semaphore.waiters))
+        return false;
+
+      /* Otherwise, get the thread with the highest priority from the waiters
+         list. By design, this is the first one in the list (See sema_down). */
+      struct thread *a_thread =
+        list_entry(list_front(&a->semaphore.waiters), struct thread, elem);
+
+      a_priority = a_thread->priority;
+    }
+
+  struct semaphore_elem *b = list_entry(b_, struct semaphore_elem, elem);
+
+  /* If waiters list is empty, return true (i.e., a has higher priority) */
+  if (list_empty(&b->semaphore.waiters))
+    return true;
+
+  struct thread *b_thread =
+    list_entry(list_front(&b->semaphore.waiters), struct thread, elem);
+
+  b_priority = b_thread->priority;
+
+  return a_priority > b_priority;
+}
+
 /* Initializes condition variable COND.  A condition variable
    allows one piece of code to signal a condition and cooperating
    code to receive the signal and act upon it. */
@@ -296,7 +355,14 @@ cond_wait (struct condition *cond, struct lock *lock)
   ASSERT (lock_held_by_current_thread (lock));
   
   sema_init (&waiter.semaphore, 0);
-  list_push_back (&cond->waiters, &waiter.elem);
+
+  /* Insert the semaphore_elem into the waiters list in order of priority.
+     We pass the priority of the current thread as aux to sema_priority_more
+     because the thread has not been sema'd down yet (See sema_priority_more) */
+  int priority = thread_current ()->priority;
+  list_insert_ordered (&cond->waiters, &waiter.elem, sema_priority_more,
+                       &priority);
+
   lock_release (lock);
   sema_down (&waiter.semaphore);
   lock_acquire (lock);

src/threads/thread.c

@@ -4,8 +4,6 @@
 #include <random.h>
 #include <stdio.h>
 #include <string.h>
-#include "devices/timer.h"
-#include "threads/fixed-point.h"
 #include "threads/flags.h"
 #include "threads/interrupt.h"
 #include "threads/intr-stubs.h"
@@ -51,7 +49,6 @@ struct kernel_thread_frame
 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. */
-static fp32_t load_avg = { 0 }; /* System load average. */
 
 /* Scheduling. */
 #define TIME_SLICE 4            /* # of timer ticks to give each thread. */
@@ -67,14 +64,9 @@ 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 void init_thread (struct thread *, const char *name, int nice,
-                         int priority, fp32_t recent_cpu);
+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 int calculate_bsd_priority (fp32_t recent_cpu, int nice);
-static void thread_update_recent_cpu (struct thread *t, void *aux UNUSED);
-static bool thread_priority_less (const struct list_elem *a,
-                                  const struct list_elem *b, void *aux UNUSED);
 static void schedule (void);
 void thread_schedule_tail (struct thread *prev);
 static tid_t allocate_tid (void);
@@ -103,9 +95,7 @@ thread_init (void)
 
   /* Set up a thread structure for the running thread. */
   initial_thread = running_thread ();
-  fp32_t initial_thread_recent_cpu = { 0 };
-  init_thread (initial_thread, "main", NICE_DEFAULT, PRI_DEFAULT,
-               initial_thread_recent_cpu);
+  init_thread (initial_thread, "main", PRI_DEFAULT);
   initial_thread->status = THREAD_RUNNING;
   initial_thread->tid = allocate_tid ();
 }
@@ -155,28 +145,6 @@ thread_tick (void)
   else
     kernel_ticks++;
 
-  /* Update system load_avg and all threads recent_cpu every second. */
-  int64_t ticks = timer_ticks ();
-  if (thread_mlfqs && (ticks % TIMER_FREQ == 0))
-    {
-      size_t ready = threads_ready ();
-      if (t != idle_thread)
-        ready++;
-      fp32_t old_coeff = fp_mul (fp_div_int (int_to_fp (59), 60), load_avg);
-      fp32_t new_coeff = fp_div_int (int_to_fp (ready), 60);
-      load_avg = fp_add (old_coeff, new_coeff);
-
-      thread_foreach (thread_update_recent_cpu, NULL);
-    }
-
-  /* Update current thread's recent_cpu. */
-  if (thread_mlfqs && (t != idle_thread))
-    {
-      t->recent_cpu = fp_add_int (t->recent_cpu, 1);
-      if (ticks % 4 == 0) // recent_cpu was updated, update priority.
-        t->priority = calculate_bsd_priority (t->recent_cpu, t->nice);
-    }
-
   /* Enforce preemption. */
   if (++thread_ticks >= TIME_SLICE)
     intr_yield_on_return ();
@@ -224,8 +192,7 @@ thread_create (const char *name, int priority,
     return TID_ERROR;
 
   /* Initialize thread. */
-  struct thread *pt = thread_current ();
-  init_thread (t, name, pt->nice, priority, pt->recent_cpu);
+  init_thread (t, name, priority);
   tid = t->tid = allocate_tid ();
 
   /* Prepare thread for first run by initializing its stack.
@@ -253,6 +220,10 @@ thread_create (const char *name, int priority,
   /* Add to run queue. */
   thread_unblock (t);
 
+  /* Yield if the new thread has a higher priority than the current thread. */
+  if (priority > thread_get_priority ())
+    thread_yield ();
+
   return tid;
 }
 
@@ -289,10 +260,10 @@ thread_unblock (struct thread *t)
 
   old_level = intr_disable ();
   ASSERT (t->status == THREAD_BLOCKED);
-  if (thread_mlfqs)
-    list_insert_ordered (&ready_list, &t->elem, thread_priority_less, NULL);
-  else
-    list_push_back (&ready_list, &t->elem);
+
+  /* Insert the thread back into the ready list in priority order. */
+  list_insert_ordered(&ready_list, &t->elem, priority_more, NULL);
+
   t->status = THREAD_READY;
   intr_set_level (old_level);
 }
@@ -362,14 +333,11 @@ thread_yield (void)
   ASSERT (!intr_context ());
 
   old_level = intr_disable ();
-  if (cur != idle_thread)
-    {
-      if (thread_mlfqs)
-        list_insert_ordered (&ready_list, &cur->elem, thread_priority_less,
-                             NULL);
-      else
-        list_push_back (&ready_list, &cur->elem);
-    }
+
+  /* Insert the thread back into the ready list in priority order. */
+  if (cur != idle_thread) 
+    list_insert_ordered(&ready_list, &cur->elem, priority_more, NULL);
+
   cur->status = THREAD_READY;
   schedule ();
   intr_set_level (old_level);
@@ -392,13 +360,57 @@ thread_foreach (thread_action_func *func, void *aux)
     }
 }
 
+/* Function that compares the two threads associated with the provided
+   list_elem structures. Returns true if the thread associated with a_ has
+   a higher priority than that of b_. */
+bool
+priority_more (const struct list_elem *a_, const struct list_elem *b_,
+                   void *aux UNUSED)
+{
+  struct thread *a = list_entry (a_, struct thread, elem);
+  struct thread *b = list_entry (b_, struct thread, elem);
+
+  return a->priority > b->priority;
+}
+
 /* Sets the current thread's priority to NEW_PRIORITY. */
 void
 thread_set_priority (int new_priority) 
 {
-  if (thread_mlfqs)
+  ASSERT (new_priority >= PRI_MIN);
+  ASSERT (new_priority <= PRI_MAX);
+
+  int old_priority = thread_get_priority ();
+  if (new_priority == old_priority)
     return;
+
   thread_current ()->priority = new_priority;
+
+  enum intr_level old_level = intr_disable ();
+
+  /* If the thread is in the ready list, the list must be reordered to maintain
+    the priority order. */
+  if (thread_current ()->status == THREAD_READY) {
+    /* Remove from the ready list and reinsert it in priority order. */
+    list_remove (&thread_current ()->elem);
+    list_insert_ordered (&ready_list, &thread_current ()->elem, priority_more,
+                         NULL);
+  }
+
+  if (new_priority < old_priority && !list_empty (&ready_list)) {
+    /* If the new priority is lower than the old priority, check if the current
+       thread no longer has the highest priority. If it doesn't, yield the CPU.
+     */
+
+    struct thread *next_thread =
+      list_entry (list_front (&ready_list), struct thread, elem);
+
+    if (next_thread->priority > new_priority) {
+      thread_yield();
+    }
+  }
+
+  intr_set_level (old_level);
 }
 
 /* Returns the current thread's priority. */
@@ -408,54 +420,35 @@ thread_get_priority (void)
   return thread_current ()->priority;
 }
 
-/* Updates recent_cpu for a thread. */
-static void
-thread_update_recent_cpu (struct thread *t, void *aux UNUSED)
-{
-  fp32_t curr_recent_cpu = t->recent_cpu;
-  fp32_t dbl_load_avg = fp_mul_int (load_avg, 2);
-  fp32_t recent_cpu_coeff
-      = fp_div (dbl_load_avg, fp_add_int (dbl_load_avg, 1));
-  t->recent_cpu
-      = fp_add_int (fp_mul (recent_cpu_coeff, curr_recent_cpu), t->nice);
-  // recent_cpu was updated, update priority.
-  t->priority = calculate_bsd_priority (t->recent_cpu, t->nice);
-}
-
 /* Sets the current thread's nice value to NICE. */
 void
-thread_set_nice (int nice)
+thread_set_nice (int nice UNUSED) 
 {
-  ASSERT (NICE_MIN <= nice && nice <= NICE_MAX);
-
-  struct thread *t = thread_current ();
-  t->nice = nice;
-  int priority = calculate_bsd_priority (t->recent_cpu, t->nice);
-  struct thread *next_t
-      = list_entry (list_begin (&ready_list), struct thread, elem);
-  if (priority < next_t->priority)
-    thread_yield ();
+  /* Not yet implemented. */
 }
 
 /* Returns the current thread's nice value. */
 int
 thread_get_nice (void) 
 {
-  return thread_current ()->nice;
+  /* Not yet implemented. */
+  return 0;
 }
 
 /* Returns 100 times the system load average. */
 int
 thread_get_load_avg (void) 
 {
-  return fp_round (fp_mul_int (load_avg, 100));
+  /* Not yet implemented. */
+  return 0;
 }
 
 /* Returns 100 times the current thread's recent_cpu value. */
 int
 thread_get_recent_cpu (void) 
 {
-  return fp_round (fp_mul_int (thread_current ()->recent_cpu, 100));
+  /* Not yet implemented. */
+  return 0;
 }
 
 /* Idle thread.  Executes when no other thread is ready to run.
@@ -531,8 +524,7 @@ is_thread (struct thread *t)
 /* Does basic initialization of T as a blocked thread named
    NAME. */
 static void
-init_thread (struct thread *t, const char *name, int nice, int priority,
-             fp32_t recent_cpu)
+init_thread (struct thread *t, const char *name, int priority)
 {
   enum intr_level old_level;
 
@@ -544,10 +536,7 @@ init_thread (struct thread *t, const char *name, int nice, int priority,
   t->status = THREAD_BLOCKED;
   strlcpy (t->name, name, sizeof t->name);
   t->stack = (uint8_t *) t + PGSIZE;
-  t->priority
-      = thread_mlfqs ? calculate_bsd_priority (recent_cpu, nice) : priority;
-  t->nice = nice;
-  t->recent_cpu = recent_cpu;
+  t->priority = priority;
   t->magic = THREAD_MAGIC;
 
   old_level = intr_disable ();
@@ -628,30 +617,8 @@ thread_schedule_tail (struct thread *prev)
     }
 }
 
-/* Calculates BSD priority for a thread */
-static int
-calculate_bsd_priority (fp32_t recent_cpu, int nice)
-{
-  int priority = PRI_MAX - (fp_round (recent_cpu) / 4) - (nice * 2);
-  if (priority < PRI_MIN)
-    return PRI_MIN;
-  if (priority > PRI_MAX)
-    return PRI_MAX;
-  return priority;
-}
-
-/* Returns true if thread a's priority is strictly greater than
-   thread b's priority. */
-static bool
-thread_priority_less (const struct list_elem *a, const struct list_elem *b,
-                      void *aux UNUSED)
-{
-  struct thread *ta = list_entry (a, struct thread, elem);
-  struct thread *tb = list_entry (b, struct thread, elem);
-  return ta->priority > tb->priority;
-}
-
-/* ss's state must have been changed from
+/* 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.
 

src/threads/thread.h

@@ -4,7 +4,6 @@
 #include <debug.h>
 #include <list.h>
 #include <stdint.h>
-#include "threads/fixed-point.h"
 
 /* States in a thread's life cycle. */
 enum thread_status
@@ -25,10 +24,6 @@ typedef int tid_t;
 #define PRI_DEFAULT 31                  /* Default priority. */
 #define PRI_MAX 63                      /* Highest priority. */
 
-#define NICE_MIN -20   /* Lowest niceness. */
-#define NICE_DEFAULT 0 /* Default niceness. */
-#define NICE_MAX 20    /* Highest niceness. */
-
 /* A kernel thread or user process.
 
    Each thread structure is stored in its own 4 kB page.  The
@@ -98,10 +93,6 @@ struct thread
     /* Shared between thread.c and synch.c. */
     struct list_elem elem;              /* List element. */
 
-    /* MLFQS items */
-    int nice;                           /* Nice value for this thread */
-    fp32_t recent_cpu;                  /* Amount of time this process received */
-
 #ifdef USERPROG
     /* Owned by userprog/process.c. */
     uint32_t *pagedir;                  /* Page directory. */
@@ -140,6 +131,8 @@ void thread_yield (void);
 typedef void thread_action_func (struct thread *t, void *aux);
 void thread_foreach (thread_action_func *, void *);
 
+bool priority_more (const struct list_elem *a_, const struct list_elem *b_,
+                    void *aux UNUSED);
 int thread_get_priority (void);
 void thread_set_priority (int);