# Final Report

## Part 1

For the first part of the project (where we edited timer.c), we luckily didn't have to make any real changes between what we had on the initial design document and the code that we were supposed to implement. This part went smoothly, but the next part was a little bit more turbulent.

## Part 2

There were many things we changed from our initial design, as per Alex's feedbeck.

- While we didn't explicitly mention the following in our design document, we have chosen to design the representation of the priority donation as such: Each thread has a list of donation priorities and the only thing a given thread does to its list is to remove elements. Other threads are responsible for donating priorities to thread (if a thread attempts to acquire a held lock, it will donate a priority, say what priority it are donating, give an identifier, and provide the lock that this donation relates to). So when a thread clears its lock (when it releases a lock), it checks if it has been donated to by anyone (the thread_tid) that was waiting on that lock, and then you clear that element from that array (with proper checks).

- In the spec, we have a very inefficient approach to the Round Robin approach, where we repeatedly insert threads and manually try to determine the scheduling via iterating through the round robin list. However, in our project we instead changed the round robin list to be a sorted list (sorted descending on the thread's effective priority). We also have a global variable, `int current_rr_index`, that stores the index of the thread (in this sorted list) that we just ran. As we reschedule, we move the index down until we reach an index of lower priority than the thread that we just ran. In this case, we reset to othe beginning of the list (which, as mentioned before, has the highest priority). We removed the `int in_rr_list` variable to update this code. This updates the `struct list ready_list` a lot faster than before and doesn't waste unnecessary computation.

- Another thing we changed was we removed our original design of having a struct waiting_on waiting in our thread struct and donation_priority struct, and instead replaced it with a lock. Our new code is seen here:

struct thread {
   struct lock *waiting;
   struct list donation_priorities;
   struct list_elem rr_elem;
   int effective_priority;

   /* Owned by thread.c. */
   unsigned magic; /* Detects stack overflow. */
};

typedef struct donation_priority {
   // The priority being donated
   int priority;
   // The lock that the donating thread is waiting on
   struct lock *waiting;
   // The donating thread
   tid_t donating_thread_tid;
   struct list_elem elem;
} donation_priority_t;

- This is because we misread the project spec originally and didnt realize we only had to deal with locks for donations (and not the other primitive types)

- We also improved our implemetation of `set_priority` to account for the need to recursively propogate the priority of waiting thread (if it is high enough) to threads that are hold lock(s) that are lower priority to start off with. Essentially we are trying to overcome the problems of nested donation with this updated implemetation of `set_priority`.

## Final Comments (Reflection)

- In this project, Rithwik and Kushagra did Part 1 (Efficient Alarm Clock), the Scheduling Lab, and helped debug small parts of Part 2 (Priority Scheduler), while Adam and Edward did Part 2.
- Due to a few factors, most prominently the effect of COVID-19 on some team members' families, we weren't able to be as efficient or as communicative as possible and while this is something that could be improved, due the circumstances, I feel like there was so real way to avoid this.
- We tried to split up the work more evenly this time and we believe that we successfully did that.