# Design Document for Project 2: Scheduling

## Group Members
* Marcus Plutowski <[e-mail]>
* Richard Huang <[e-mail]>
* Willis Wang <[e-mail]>
* Siddharth Gollapudi <[e-mail]>

## Table of Contents
- [Task 1](#task-1-efficient-alarm-clock)
- [Task 2](#task-2-priority-scheduler)

## Task 1: Efficient Alarm Clock

### Data Structures & Functions
- Add a global `sleep_list` linked list of threads for keeping track of sleeping threads
- Sorted from least to greatest `thread->sleep_timer`
- Add a `int64_t sleep_timer` instance variable per thread to keep track of how many more ticks left to sleep

### Algorithms
- Logic in `timer_sleep(time_to_sleep)`:

    if time_to_sleep > 0:
        thread->sleep_timer = timer_ticks() + time_to_sleep
        add thread to sleep_list in sorted sleep_timer order
        thread_block()

- When a thread calls `timer_sleep(ticks)` we want to set the thread member `sleep_timer` to the time the timer will expire, add the thread onto the `sleep_list` in order from smallest to largest `sleep_timer`, and then block the thread.
- Logic in `timer_interrupt()`:

    for thread in sleep_list:
        if thread->sleep_timer <= ticks:
                remove thread from sleep_list
                thread_unblock()
        else break

- During each `timer_interrupt` we loop through all threads inside `sleep_list` until the first thread that has a `sleep_timer` that has not expired yet
- If the thread's `sleep_timer` is equal to or less than the current tick, we will remove the thread from `sleep_list` and unblock it, letting it back onto the ready queue
- We stop at the first thread that has not expired. Since the the list is sorted, the rest of the threads after are also not expired.
### Synchronization
- We disable interrupts when adding threads to `wait_list` in `timer_sleep()`.
- We do this to avoid race conditions when multiple threads call sleep at once.
- Also because `thread_block` is must be called with interrupts turned off.
- Since external interrupts generated by devices outside the CPU, such as the timer are run with interrupts turned off, they never nest nor get pre-empted so we don't need to manually turn off interrupts or lock when modifying `sleep_list` in `timer_interrupt`.

### Rationale
- We want to implement `timer_sleep` such that there is no busy waiting. Therefore, we keep the sleeping threads off the ready queue with `thread-block` so that the sleeping threads will not be called (and busy wait). We keep track of these sleeping threads in our list called `sleep_list`.
- In `timer_interrupt` we want to make it as fast as possible so we only loop through `sleep_list` until the first unexpired thread. Since `sleep_list` is sorted thanks to `timer_sleep` adding to the list in an ordered fashion, `timer_interrupt` should be O(n), n = number of sleeping threads with expired timers. This way we avoid iterating through all timer slept threads which would take longer.

## Task 2: Priority Scheduler

### Data Structures & Functions

#### List Helper Functions

In order to facilitate the use of `list_max` on the lists of locks and threads we have access to, we will define the following two helper functions (each of type `list_less_func`):
- `bool compare_thread_priority(const list_elem *a, const list_elem *b, void *aux)`
- `bool compare_lock_priority(const list_elem *a, const list_elem *b, void *aux)`

#### Thread Modifications

We will add the following two instance variables to `struct thread`, defined in `thread.h`:

- `struct list owned_locks`
- Contains all locks the thread is currently holding.
- Used to restore priority properly after releasing lock
- `struct lock waiting_lock`
- Contains the locks the thread is currently waiting for.
- Note that a thread can only wait for one lock at a time.
- `int effective_priority`
- The effective priority of the thread, taking priority donations.
- Used by the scheduler

Changes would be made to the following functions in thread.c:

- `static void init_thread (~)`
- Extend to initialize new struct data members.

- `int thread_get_priority (void)`
- Change to return the effective priority of the current thread

- `int thread_base_priority (void)`
- New function, will return the original base priority of the current thread.
#### Semaphore Modifications
Changes would be made to the following functions in synch.c:
- void `sema_up(struct semaphore *)`
- Change to have sema_up wake up the correct thread based on effective priority
- See algorithms section

#### Lock Modifications
To facilitate priority donation, threads will need to be able to be track which locks they own, we will thus add the following two elements to the end of `struct lock`, defined in `synch.h`:

- `struct list_elem elem`
- To allow locks to be added to linked lists
- `int curr_max_priority`
- Contains the priority of the highest priority thread waiting for the lock.
- Used in priority donation.

Changes will be made to the following functions:
- `void lock_init (struct lock *)`
- Change to handle the additional members and elements we're adding into the design.
- `void lock_acquire (struct lock *)`, `bool lock_try_acquire (struct lock *)`
- Extend to donate priority to dependent lower-priority threads.
- Will modify `curr_max_priority` accordingly
- `void lock_release (struct lock *)`
- Extend to also recompute priority donation info and wake a waiting thread.

#### Condition Variable Modifications
- `void cond_signal (struct condition *, stuct lock *)`
- Change to signal the correct waiting thread based on effective priority.

### Algorithms

#### Selecting Thread to Execute
The scheduler decides which thread to run within `next_thread_to_run()`. We will change this function to pop off and return the tread with highest `effective_priority` attribute using the `list_max()` function on `ready_list`.

In order to apply `list_max()`, we will need to create a secondary helper function which `list_max()` will use to find the maximum in the list of locks, `bool compare_thread_priority(const list_elem *a, const list_elem *b, void *aux)`:
1. Acquire the overlying thread pointer from each list_elem;
2. Acquire the value of thread->effective_priority for each thread;
3. Compare each of the two priority values and return true if a's is higher than b's, or false otherwise.

#### Acquiring a Lock
As mentioned, locks will each keep track of their current thread owner. When a thread tries to acquire a lock, it first checks for an owner; if the lock is ownerless, it is necessarily unlocked and as such can simply be acquired, with the owner being set to the acquiring thread.

If the lock is _not_ ownerless -- that is, it's currently owned by an existing thread -- the new thread will:
1. Disable interrupts;
2. Add the new thread to the list `waiters`, located inside the lock's underlying semaphore;
3. If the lock's `curr_max_priority` is less than `thread_current().get_eff_priority()`, update the value of `curr_max_priority` within the lock to the new thread's effective priority.
4. If we changed `curr_max_priority` in the previous step, apply the following iterative algorithm to propogate the priority donation downstream to any threads which this lock is blocked by:

lock target_lock = the_lock
thread* target_thread = Null
do {
    target_thread = target_lock.holder
    target_lock.curr_max_priority =
                    (int)list_max(target_lock.semaphore.waiters,
                                  compare_lock_priority, Null)
    if (target_thread is not Null) {
        recalculate_priority(target_thread)
        target_lock = target_thread.waiting_lock
    } else {
        target_lock = Null
    }
} while (target_lock is not Null)

6. Enable interrupts;
7. Call `sema_down()`.

#### Releasing a Lock

When a lock is released by a thread, we will, in order:
1. Disable interrupts;
2. Unset the lock owner variable;
3. Remove the lock from the thread's `owned_locks` list;
5. Call `recalculate_priority` on the current thread to apply any potential priority changes that would result from no longer holding the lock;
6. Enable interrupts;
7. Call `sema_up()`.

#### Computing the Effective Priority

This functionality will be implemented in the new function `int recalculate_priority(struct thread* thread)`. In short, this function evaluates every lock that `thread` has ownership of and will raise `thread`'s priority to account for priority donations made by threads waitong on those locks. This function must be run with interrupts off to avoid synchronization issues with the locks in the list `owned_locks`.

In brief,

int recalculate_priority(struct thread* thread):
    asssert intr_get_level() is INTR_OFF
    if thread is NULL:
        return ERROR
    thread_set_priority(thread_base_priority())
    donated_prio = list_max(thread->owned_locks, helper, NULL)
    thread->priority = max(thread_base_priority(), donated_prio)
    return SUCCESS

In order to apply `list_max()`, we will need to create a secondary helper function which `list_max()` will use to find the maximum in the list of locks, `bool compare_lock_priority(const list_elem *a, const list_elem *b, void *aux)`:
1. Acquire the overlying lock pointer from each `list_elem`;
2. Acquire the value of `curr_max_priority` for each lock;
3. Compare each of the two priority values and return true if a's is higher than b's, or false otherwise.

#### Semaphore & Lock Priority Scheduling
As all synchronization primitives are implemented using a semaphore, implementing priority within semaphores would automatically follow for locks and condition variables.

When releasing a semaphore, we will prioritize letting processes with higher priority decrement the semaphore before those with lower priority.
- Modify `sema_up()`to use `list_max` to find highest effective priority waiting thread in the semaphore's instance variable `struct list waiters` and unblock that thread, rather than just unblocking first entry of `waiters`
- Note that this does not consider the `base_priority` of the thread, but rather the `effective_priority`, as we want to be able to take priority donations into account.

#### Condition Variable Priority Scheduling
The only necessary change for condition variables is to `cond_signal()`: when a condition variable is signalled, we want to signal the highest effective priority waiter.

Specifically, we will modify `cond_signal()` to use `list_max` to signal the highest effective priority waiting thread in condition instance variable `struct list waiters`. This will use the same helper function as used by locks and semaphores,

### Synchronization
#### Priority Scheduler
The entire priority scheduler is implemented in `next_thread_to_run()`, which runs within the scheduler itself and as such will already always run with interrupts disabled.
- Therefore there will be no race conditions.

#### Priority Donation Management
We disable interrupts around `lock_acquire` and `lock_release` in order to be able to modify the necessary threads' and locks' effective priorities.
- Each function edits at least one list of:
- The list of waiting threads held by each lock
- The list of owned locks held by each thread
- These lists are not thread secure, and as such if a context switch occured midway, we'd be in a bit of trouble monkaS
- The relevant helper function that both call to manage priority donation, `recalculate_priority`, must be called with interrupts disabled (as asserted within the definition).
- This ensures that the list accesses within the helper function are secure.

### Rationale

- A major alternative to the priority donation system we used would be to use a recursive function on the locks & threads rather than an iterative one; we chose to use an iterative function because we felt that the overhead, both in terms of stack allocation and in terms of code complexity, of a recursive function wasn't worth the upsides, as C does not have any special handling for tail recursive functions.
- As all synchronization primitives in Pintos are implemented using a semaphore at some level, we chose to implement the prioritization functionality in the semaphore object; this way, condition variables and locks will automatically also follow the same functionality.
- We decided to include `curr_max_priority` within each lock to maximize efficiency; while it would certainly be possible to recompute `list_max` every time a thread releases a lock, this would be somewhat inefficient for any situations where threads are holding more than a small handful of locks at a time. Our design allows the thread to only call `list_max` once per call of `lock_release`, as opposed to calling `list_max` `n` times per call of `lock_release`, where `n` is the number of locks held by the thread.

## Additional Questions
### 1
We define a struct specially for when we switch threads in `thread_create()`, called `sf`. The struct will contain the data we need to save when we context switch. Then, in `switch.S` (`switch_threads`), we save the registers of the current thread onto the thread's stack, and save the stack pointer in the thread struct.

### 2
When calling `thread_exit`, after removing the thread from the list of all threads (`allelem`), we set the thread status to `THREAD_DYING`, and call `schedule()`. Since the current thread's status is dying, we then free the thread page in `thread_schedule_tail()`, since the thread is dying.

We can't free the thread data in `thread_data()` itself because we don't want to confuse the scheduler -- as a result, the scheduler is the one who is responsible for destroying thread data. Also, we want to free as late as possible, since in the words of the pintos comments, it's "so that `thread_exit()` doesn't pull out the rug under itself."
### 3
The `thread_tick()` function is called in the current (kernel) thread's stack, since it is called in `timer_interrupt` and `timer_interrupt` is called from `intr_handler`.

### 4

Denote threads 1 through 4 with 1 having the lowest base priority and 4 having the highest base priority.
We will have each thread printing out their own thread ID <b>after obtaining lock A</b>. Furthermore, we have each thread releasing all locks after printing.
We first run thread 1 and have thread 1 obtaining lock A. Then, we create threads 2, 3, and 4 simultaneously. Thread 2 first obtains lock B then trying to obtain lock A. Then, thread 3 trys to obtain lock A. Lastly, thread 4 trys to obtain lock B. Note that thread 4 would donate its priority to thread 2, making thread 2's effective priority the highest.
The correct printout should be `1 2 3`, as thread 2 has a higher effective priority after the priority donation from 4, and thus should be woken before thread 3. If the printout is `1 3 2`, this would indicate that the `sema_up()` in `lock_acquire()` does not signal the correct thread, signaling based on base priority rather than effective priority, as thread 3 has the higher base priority.