Merge branch 'task1/themis/thread-create-refactor' into 'master'

Refactor thread_create () to call thread_get_priority in order to retrieve priority

See merge request lab2425_autumn/pintos_22!21

.gitignore

@@ -31,3 +31,6 @@
 *.nav
 *.toc
 
+#ignore files from CLion/VSCode IDEs
+.idea
+.vscode

.gitlab-ci.yml

@@ -0,0 +1,44 @@
+stages:
+  - test
+
+.pintos_tests:
+  stage: test
+  image: gitlab.doc.ic.ac.uk:4567/lab2425_autumn/pintos_22/pintos-testing:latest
+  artifacts:
+    when: always
+    paths:
+      - src/$DIR/build/tests/$DIR/
+  before_script:
+    - cd src/utils
+    - make
+    - export PATH=$PWD:$PATH
+    - cd ../..
+  script:
+    - cd src/$DIR
+    - make check | tee build.log
+    - grep -q "FAIL tests/$DIR" build.log && exit 1 || exit 0
+
+test_devices:
+  extends: .pintos_tests
+  variables:
+    DIR: devices
+
+test_filesys:
+  extends: .pintos_tests
+  variables:
+    DIR: filesys
+
+test_threads:
+  extends: .pintos_tests
+  variables:
+    DIR: threads
+
+test_userprog:
+  extends: .pintos_tests
+  variables:
+    DIR: userprog
+
+test_vm:
+  extends: .pintos_tests
+  variables:
+    DIR: vm

Dockerfile.devel

@@ -0,0 +1,3 @@
+FROM debian:12-slim
+
+RUN apt update && apt install gcc perl make qemu-system-i386 gdb -y

src/devices/timer.c

@@ -119,9 +119,6 @@ timer_sleep (int64_t ticks)
                        NULL);
   intr_set_level (old_level);
   sema_down (&st.semaphore);
-  old_level = intr_disable ();
-  list_remove (&st.elem);
-  intr_set_level (old_level);
 }
 
 /* Sleeps for approximately MS milliseconds.  Interrupts must be
@@ -204,7 +201,10 @@ timer_interrupt (struct intr_frame *args UNUSED)
     {
       struct asleep_thread *st = list_entry (e, struct asleep_thread, elem);
       if (ticks >= st->end_at)
-        sema_up (&st->semaphore);
+        {
+          list_remove (&st->elem);
+          sema_up (&st->semaphore);
+        }
       else
         break;
     }

src/threads/fixed-point.h

@@ -0,0 +1,100 @@
+#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_FACTOR (1 << NUM_FRAC_BITS) /* f = 2^q, (2^14) */
+
+/* Fixed Point Arithmetic conversion operations */
+/* Converts an integer n to a fixed point number */
+inline fp32_t
+fp_from_int (int32_t n)
+{
+  return (fp32_t){ n * CONVERSION_FACTOR };
+}
+
+/* Handles conversion of fixed point to integer,
+   with truncation */
+inline int32_t
+fp_floor (fp32_t x)
+{
+  return x.raw / CONVERSION_FACTOR;
+}
+
+/* Handles conversion of fixed point to integer,
+   with rounding */
+inline int32_t
+fp_round (fp32_t x)
+{
+  if (x.raw >= 0)
+    return (x.raw + CONVERSION_FACTOR / 2) / CONVERSION_FACTOR;
+  else
+    return (x.raw - CONVERSION_FACTOR / 2) / CONVERSION_FACTOR;
+}
+
+/* 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 };
+}
+
+
+
+/* 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_FACTOR };
+}
+
+/* Divide two fixed points */
+inline fp32_t
+fp_div (fp32_t x, fp32_t y)
+{
+  return (fp32_t){ ((int64_t)x.raw) * CONVERSION_FACTOR / 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 };
+}
+
+/* Add fixed point to integer */
+inline fp32_t
+fp_add_int (fp32_t x, int32_t n)
+{
+  return (fp32_t){ x.raw + n * CONVERSION_FACTOR };
+}
+
+/* Subtract integer from fixed point */
+inline fp32_t
+fp_sub_int (fp32_t x, int32_t n)
+{
+  return (fp32_t){ x.raw - n * CONVERSION_FACTOR };
+}
+
+#endif //FIXED_POINT_H

src/threads/synch.c

@@ -32,6 +32,10 @@
 #include "threads/interrupt.h"
 #include "threads/thread.h"
 
+static bool
+priority_less (const struct list_elem *a_, const struct list_elem *b_,
+               void *aux UNUSED);
+
 /* Initializes semaphore SEMA to VALUE.  A semaphore is a
    nonnegative integer along with two atomic operators for
    manipulating it:
@@ -68,8 +72,7 @@ sema_down (struct semaphore *sema)
   old_level = intr_disable ();
   while (sema->value == 0) 
     {
-      list_insert_ordered(&sema->waiters, &thread_current ()->elem,
-                          priority_more, NULL);
+      list_push_back (&sema->waiters, &thread_current ()->elem);
       thread_block ();
     }
   sema->value--;
@@ -107,25 +110,31 @@ sema_try_down (struct semaphore *sema)
 
    This function may be called from an interrupt handler. */
 void
-sema_up (struct semaphore *sema) 
+sema_up (struct semaphore *sema)
 {
   enum intr_level old_level;
 
   ASSERT (sema != NULL);
 
   old_level = intr_disable ();
-
-  /* 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);
+      /* Enforces wake-up of the highest priority thread waiting for the
+         semaphore. */
+      struct list_elem *e = list_max (&sema->waiters, priority_less, NULL);
+      list_remove (e);
+      thread_unblock (list_entry (e, struct thread, elem));
     }
-
   sema->value++;
   intr_set_level (old_level);
-  thread_yield ();
+
+  /* Yields the CPU in case the thread that has been woken up has a higher
+     priority that the current running thread, including the case when called
+     within an interrupt handler. */
+  if (intr_context ())
+    intr_yield_on_return ();
+  else
+    thread_yield ();
 }
 
 static void sema_test_helper (void *sema_);
@@ -189,6 +198,47 @@ lock_init (struct lock *lock)
   sema_init (&lock->semaphore, 1);
 }
 
+/* Current thread donates its priority to donee, iteratively
+   propagating the donation in the case of chains in the wait-for graph.
+   Also keeps track of the donation by updating the donors list. Expects
+   interrupts to be disabled. */
+static void
+donate_priority (struct thread *donee) {
+  ASSERT (intr_get_level () == INTR_OFF);
+
+  struct thread *donor = thread_current ();
+  list_push_back (&donee->donors_list, &donor->donor_elem);
+  
+  while (donee != NULL)
+    {
+      /* Stop propagation of donation once a donee is reached that has
+         a higher effective priority (as its donees can't have less
+         priority than that being donated). */
+      if (donor->priority <= donee->priority)
+          break;
+
+      /* Also stop propagation of donation once a donee is reached with
+         no donees of its own (sink node in WFG). */
+      if (donee->waiting_lock == NULL)
+        {
+          /* Only the sink node of the WFG isn't waiting for a lock and
+             could be on the ready list. Thus, as its priority changed,
+             it must be reinserted into the list. */
+          enum intr_level old_level = intr_disable ();
+          donee->priority = donor->priority;
+          ready_list_reinsert (donee);
+          intr_set_level (old_level);
+          
+          donee = NULL;
+        }
+      else
+        {
+          donee->priority = donor->priority;
+          donee = donee->waiting_lock->holder;
+        }
+    }
+}
+
 /* Acquires LOCK, sleeping until it becomes available if
    necessary.  The lock must not already be held by the current
    thread.
@@ -204,8 +254,19 @@ lock_acquire (struct lock *lock)
   ASSERT (!intr_context ());
   ASSERT (!lock_held_by_current_thread (lock));
 
+  struct thread *t = thread_current ();
+
+  enum intr_level old_level = intr_disable ();
+  if (lock->holder != NULL)
+    {
+      t->waiting_lock = lock;
+      donate_priority (lock->holder);
+    }
+  intr_set_level (old_level);
+
   sema_down (&lock->semaphore);
   lock->holder = thread_current ();
+  t->waiting_lock = NULL;
 }
 
 /* Tries to acquires LOCK and returns true if successful or false
@@ -239,8 +300,54 @@ lock_release (struct lock *lock)
   ASSERT (lock != NULL);
   ASSERT (lock_held_by_current_thread (lock));
 
+  struct thread *current_thread = thread_current ();
+  struct thread *max_donor = NULL;
+
+  struct list orphan_list;
+  list_init (&orphan_list);
+
+  enum intr_level old_level = intr_disable ();
+  /* Loop through current thread's donors, removing the ones waiting for the
+     lock being released and keeping track of them (within orphan_list).
+     Also identifies the highest priority donor thread among them. */
+  struct list_elem *tail = list_tail (&current_thread->donors_list);
+  struct list_elem *e = list_begin (&current_thread->donors_list);
+  while (e != tail)
+    {
+      struct thread *donor = list_entry (e, struct thread, donor_elem);
+      struct list_elem *next = list_next (e);
+
+      /* Excludes donors that aren't waiting for the lock being released,
+         and tracks the rest. */
+      if (donor->waiting_lock == lock)
+        {
+          list_remove (e);
+          list_push_back (&orphan_list, e);
+
+          /* Identify highest priority donor. */
+          if (max_donor == NULL || donor->priority > max_donor->priority)
+            max_donor = donor;
+        }
+
+      e = next;
+    }
+
+  /* If there exists a maximum donor thread waiting for this lock to be
+     released, transfer the remaining orphaned donors to its donor list. */
+  if (max_donor != NULL)
+    {
+      while (!list_empty (&orphan_list))
+        list_push_back (&max_donor->donors_list, list_pop_front (&orphan_list));
+    }
+
+  intr_set_level (old_level);
+  /* Removal of donors to this thread may change its effective priority,
+     so recalculate. */
+  thread_recalculate_priority ();
+
   lock->holder = NULL;
   sema_up (&lock->semaphore);
+  thread_yield ();
 }
 
 /* Returns true if the current thread holds LOCK, false
@@ -261,6 +368,19 @@ struct semaphore_elem
     struct semaphore semaphore;         /* This semaphore. */
   };
 
+/* Function that compares the two threads associated with the provided
+   pointers to their 'elem' member. Returns true if the thread associated
+   with a_ has a lower priority than that of b_. */
+static bool
+priority_less (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;
+}
+
 /* 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_
@@ -270,43 +390,25 @@ struct semaphore_elem
     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)
+sema_priority_more(const struct list_elem *a, const struct list_elem *b,
+                   void *inserting_telem)
 {
-  int a_priority, b_priority;
+  struct list_elem *te_a, *te_b;
+  
+  te_b = list_front (
+    &list_entry (b, struct semaphore_elem, elem)->semaphore.waiters);
 
-  /* 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;
+  if (inserting_telem == NULL)
+    {
+      te_a = list_front (
+        &list_entry (a, struct semaphore_elem, elem)->semaphore.waiters);
+    }
   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;
+      te_a = inserting_telem;
     }
 
-  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;
+  return priority_more (te_a, te_b, NULL);
 }
 
 /* Initializes condition variable COND.  A condition variable
@@ -320,38 +422,6 @@ cond_init (struct condition *cond)
   list_init (&cond->waiters);
 }
 
-/* Returns true iff the priority of the only thread in the first singleton
-   semaphore is greater than the priority of the only thread in the second
-   singleton semaphore.
-   
-   Where this function is used for insertion in a singleton semaphore list, the
-   third argument may specify a list_elem * to assume corresponds to the thread
-   waiting for the inserting semaphore. For correctness, ensure this thread
-   calls sema_down () for this semaphore before future list accesses. */
-
-static bool
-singleton_sema_priority_greater (const struct list_elem *a, 
-                                 const struct list_elem *b,
-                                 void *insertingThread)
-{
-  struct list_elem *te_a, *te_b;
-  
-  te_b = list_front (
-    &list_entry (b, struct semaphore_elem, elem)->semaphore.waiters);
-
-  if (insertingThread == NULL)
-    {
-      te_a = list_front (
-        &list_entry (a, struct semaphore_elem, elem)->semaphore.waiters);
-    }
-  else
-    {
-      te_a = insertingThread;
-    }
-
-  return thread_priority_greater (te_a, te_b, NULL);
-}
-
 /* Atomically releases LOCK and waits for COND to be signaled by
    some other piece of code.  After COND is signaled, LOCK is
    reacquired before returning.  LOCK must be held before calling
@@ -383,14 +453,7 @@ cond_wait (struct condition *cond, struct lock *lock)
   ASSERT (lock_held_by_current_thread (lock));
   
   sema_init (&waiter.semaphore, 0);
-
-  /* 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);
-
+  list_push_back (&cond->waiters, &waiter.elem);
   lock_release (lock);
   sema_down (&waiter.semaphore);
   lock_acquire (lock);
@@ -411,9 +474,14 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
   ASSERT (!intr_context ());
   ASSERT (lock_held_by_current_thread (lock));
 
-  if (!list_empty (&cond->waiters)) 
-    sema_up (&list_entry (list_pop_front (&cond->waiters),
-                          struct semaphore_elem, elem)->semaphore);
+  if (!list_empty (&cond->waiters))
+    {
+      /* Enforce wake-up of highest priority thread within the singleton 
+         semaphores waiting for condvar. */
+      struct list_elem *e = list_min (&cond->waiters, sema_priority_more, NULL);
+      list_remove (e);
+      sema_up (&list_entry (e, struct semaphore_elem, elem)->semaphore);
+    }
 }
 
 /* Wakes up all threads, if any, waiting on COND (protected by

src/threads/thread.c

@@ -4,6 +4,8 @@
 #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"
@@ -49,9 +51,11 @@ 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. */
+#define PRI_UPDATE_FREQ 4       /* # of timer ticks to update priorities. */
 static unsigned thread_ticks;   /* # of timer ticks since last yield. */
 
 /* If false (default), use round-robin scheduler.
@@ -64,12 +68,18 @@ 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 priority);
+static void init_thread (struct thread *, const char *name, int nice,
+                         int priority, fp32_t recent_cpu);
 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 update_recent_cpu (struct thread *t, void *aux UNUSED);
+static void recalculate_priority (struct thread *t);
 static void schedule (void);
 void thread_schedule_tail (struct thread *prev);
 static tid_t allocate_tid (void);
+static bool donor_priority_less (const struct list_elem *a_,
+                                 const struct list_elem *b_, void *aux UNUSED);
 
 /* Initializes the threading system by transforming the code
    that's currently running into a thread.  This can't work in
@@ -95,7 +105,9 @@ thread_init (void)
 
   /* Set up a thread structure for the running thread. */
   initial_thread = running_thread ();
-  init_thread (initial_thread, "main", PRI_DEFAULT);
+  fp32_t initial_thread_recent_cpu = { 0 };
+  init_thread (initial_thread, "main", NICE_DEFAULT, PRI_DEFAULT,
+               initial_thread_recent_cpu);
   initial_thread->status = THREAD_RUNNING;
   initial_thread->tid = allocate_tid ();
 }
@@ -145,6 +157,35 @@ 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)
+    {
+      if (t != idle_thread)
+          t->recent_cpu = fp_add_int (t->recent_cpu, 1);
+
+      if (ticks % TIMER_FREQ == 0)
+        {
+          size_t ready = threads_ready ();
+          if (t != idle_thread)
+            ready++;
+          fp32_t old_coeff = fp_div_int (fp_mul_int (load_avg, 59), 60);
+          fp32_t new_coeff = fp_div_int (fp_from_int (ready), 60);
+          load_avg = fp_add (old_coeff, new_coeff);
+
+          thread_foreach (update_recent_cpu, NULL);
+          /* Priorities have been updated, need to re-sort. */
+          list_sort (&ready_list, priority_more, NULL);
+        }
+
+      /* Recent cpu was updated, update priority. */
+      if (t != idle_thread && ticks % PRI_UPDATE_FREQ == 0)
+        {
+          t->base_priority = calculate_bsd_priority (t->recent_cpu, t->nice);
+          recalculate_priority (t);
+        }
+    }
+
   /* Enforce preemption. */
   if (++thread_ticks >= TIME_SLICE)
     intr_yield_on_return ();
@@ -192,7 +233,8 @@ thread_create (const char *name, int priority,
     return TID_ERROR;
 
   /* Initialize thread. */
-  init_thread (t, name, priority);
+  struct thread *parent_thread = thread_current ();
+  init_thread (t, name, parent_thread->nice, priority, parent_thread->recent_cpu);
   tid = t->tid = allocate_tid ();
 
   /* Prepare thread for first run by initializing its stack.
@@ -219,10 +261,10 @@ thread_create (const char *name, int priority,
 
   /* Add to run queue. */
   thread_unblock (t);
-  thread_yield ();
 
-  /* Yield if the new thread has a higher priority than the current thread. */
-  if (priority > thread_get_priority ())
+  /* Yield if the newly created thread has higher priority than the current
+     thread. */
+  if (t->priority > thread_get_priority ())
     thread_yield ();
 
   return tid;
@@ -263,7 +305,7 @@ thread_unblock (struct thread *t)
   ASSERT (t->status == THREAD_BLOCKED);
 
   /* Insert the thread back into the ready list in priority order. */
-  list_insert_ordered(&ready_list, &t->elem, priority_more, NULL);
+  list_insert_ordered (&ready_list, &t->elem, priority_more, NULL);
 
   t->status = THREAD_READY;
   intr_set_level (old_level);
@@ -335,9 +377,11 @@ thread_yield (void)
 
   old_level = intr_disable ();
 
-  /* 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);
+  if (cur != idle_thread)
+    {
+      /* Insert the thread back into the ready list in priority order. */
+      list_insert_ordered (&ready_list, &cur->elem, priority_more, NULL);
+    }
 
   cur->status = THREAD_READY;
   schedule ();
@@ -362,66 +406,160 @@ 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_. */
+   pointers to their 'elem' member. 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)
+               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) 
+/* Function that compares the two threads associated with the provided
+   pointers to their 'donor_elem' member. Returns true if the thread associated
+   with a_ has a lower priority than that of b_. */
+static bool
+donor_priority_less (const struct list_elem *a_, const struct list_elem *b_,
+               void *aux UNUSED)
 {
-  ASSERT (PRI_MIN <= new_priority && new_priority <= PRI_MAX);
-  int old_priority = thread_get_priority ();
+  struct thread *a = list_entry (a_, struct thread, donor_elem);
+  struct thread *b = list_entry (b_, struct thread, donor_elem);
 
-  thread_current ()->priority = new_priority;
-  if (new_priority < old_priority)
-    thread_yield ();
+  return a->priority < b->priority;
 }
 
-/* Returns the current thread's priority. */
+/* Sets the current thread's base priority to new_base_priority.
+   Updates the current thread's effective priority if necessary. */
+void
+thread_set_priority (int new_base_priority)
+{
+
+  if (thread_mlfqs)
+    return;
+
+  ASSERT (new_base_priority >= PRI_MIN);
+  ASSERT (new_base_priority <= PRI_MAX);
+
+  struct thread *t = thread_current ();
+
+  /* If the base priority is unchanged, do nothing. */
+  if (new_base_priority == t->base_priority)
+    return;
+
+  t->base_priority = new_base_priority;
+  recalculate_priority (t);
+
+  thread_yield ();
+}
+
+/* Returns the current thread's effective priority. */
 int
 thread_get_priority (void) 
 {
   return thread_current ()->priority;
 }
 
+
+/* Updates recent_cpu for a thread. */
+static void
+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->base_priority = calculate_bsd_priority (t->recent_cpu, t->nice);
+  recalculate_priority (t);
+}
+
+/* Recalculates the effective priority of the current thread. */
+void
+thread_recalculate_priority (void)
+{
+  struct thread *t = thread_current ();
+  recalculate_priority (t);
+}
+
+static void
+recalculate_priority (struct thread *t)
+{
+  enum intr_level old_level = intr_disable ();
+  t->priority = t->base_priority;
+
+  /* If there are no donors to the current thread, then the effective
+     priority is just the base priority. */
+  if (!list_empty (&t->donors_list))
+    {
+      int max_donated_priority =
+        list_entry (list_max (&t->donors_list, donor_priority_less, NULL),
+                    struct thread, donor_elem)->priority;
+
+      /* The effective priority is the max donated priority if this is
+         higher than the base priority. */
+      if (max_donated_priority > t->priority)
+        t->priority = max_donated_priority;
+    }
+  intr_set_level (old_level);
+}
+
 /* Sets the current thread's nice value to NICE. */
 void
-thread_set_nice (int nice UNUSED) 
+thread_set_nice (int nice)
 {
-  /* Not yet implemented. */
+  ASSERT (NICE_MIN <= nice && nice <= NICE_MAX);
+
+  struct thread *t = thread_current ();
+  t->nice = nice;
+  t->base_priority = calculate_bsd_priority (t->recent_cpu, t->nice);
+  recalculate_priority (t);
+  struct thread *next_t
+      = list_entry (list_begin (&ready_list), struct thread, elem);
+  if (t->priority < next_t->priority)
+    thread_yield ();
 }
 
 /* Returns the current thread's nice value. */
 int
 thread_get_nice (void) 
 {
-  /* Not yet implemented. */
-  return 0;
+  return thread_current ()->nice;
 }
 
 /* Returns 100 times the system load average. */
 int
 thread_get_load_avg (void) 
 {
-  /* Not yet implemented. */
-  return 0;
+  return fp_round (fp_mul_int (load_avg, 100));
 }
 
 /* Returns 100 times the current thread's recent_cpu value. */
 int
 thread_get_recent_cpu (void) 
 {
-  /* Not yet implemented. */
-  return 0;
+  return fp_round (fp_mul_int (thread_current ()->recent_cpu, 100));
+}
+
+/* Reinsert thread t into the ready list at its correct position
+   in descending order of priority. Used when this thread's priority
+   may have changed. Must be called with interrupts disabled. */
+void
+ready_list_reinsert (struct thread *t)
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+
+  /* If the thread isn't ready to run, do nothing. */
+  if (t->status != THREAD_READY)
+    return;
+
+  list_remove (&t->elem);
+  list_insert_ordered (&ready_list, &t->elem, priority_more, NULL);
 }
 
 /* Idle thread.  Executes when no other thread is ready to run.
@@ -497,7 +635,8 @@ 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 priority)
+init_thread (struct thread *t, const char *name, int nice, int priority,
+             fp32_t recent_cpu)
 {
   enum intr_level old_level;
 
@@ -509,9 +648,17 @@ 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->magic = THREAD_MAGIC;
 
+  t->base_priority
+      = thread_mlfqs ? calculate_bsd_priority (recent_cpu, nice) : priority;
+  list_init (&t->donors_list);
+  t->waiting_lock = NULL;
+
+  t->nice = nice;
+  t->recent_cpu = recent_cpu;
+  t->priority = t->base_priority;
+
   old_level = intr_disable ();
   list_push_back (&all_list, &t->allelem);
   intr_set_level (old_level);
@@ -590,6 +737,21 @@ thread_schedule_tail (struct thread *prev)
     }
 }
 
+/* Calculates BSD priority for a thread */
+static int
+calculate_bsd_priority (fp32_t recent_cpu, int nice)
+{
+
+  ASSERT (thread_mlfqs);
+
+  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;
+}
+
 /* 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
@@ -627,17 +789,6 @@ allocate_tid (void)
   return tid;
 }
 
-/* Returns true iff the priority of the first list element's thread is greater
-   than that of the second list element's thread. */
-bool 
-thread_priority_greater (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;
-}
-
 /* 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);

src/threads/thread.h

@@ -4,6 +4,7 @@
 #include <debug.h>
 #include <list.h>
 #include <stdint.h>
+#include "threads/fixed-point.h"
 
 /* States in a thread's life cycle. */
 enum thread_status
@@ -24,6 +25,10 @@ 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
@@ -90,9 +95,23 @@ struct thread
     int priority;                       /* Priority. */
     struct list_elem allelem;           /* List element for all threads list. */
 
+    /* Donation Related */
+    int base_priority;                  /* Base priority of the thread. */
+    struct list donors_list;            /* List of threads that have donated
+                                           to this thread. */
+    struct lock *waiting_lock;          /* The lock that the current thread is
+                                           waiting for. */
+    struct list_elem donor_elem;        /* List element so that thread can be
+                                           enlisted in other donors list. */
+
+    /* MLFQS items */
+    int nice;                           /* Nice value for this thread */
+    fp32_t recent_cpu;                  /* Amount of time this process received */
+
     /* Shared between thread.c and synch.c. */
     struct list_elem elem;              /* List element. */
 
+
 #ifdef USERPROG
     /* Owned by userprog/process.c. */
     uint32_t *pagedir;                  /* Page directory. */
@@ -135,13 +154,13 @@ 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);
+void thread_recalculate_priority (void);
 
 int thread_get_nice (void);
 void thread_set_nice (int);
 int thread_get_recent_cpu (void);
 int thread_get_load_avg (void);
 
-/* Returns true iff the priority of the first list element's thread is greater
-   than that of the second list element's thread. */
-list_less_func thread_priority_greater;
+void ready_list_reinsert (struct thread *t);
+
 #endif /* threads/thread.h */