current design doc

            +--------------------+
            |        CS 162      |
            | PROJECT 1: THREADS |
            |   DESIGN DOCUMENT  |
            +--------------------+

---- GROUP ----

>> Fill in the names and email addresses of your group members.

Brandt Sheets <bmsheets@berkeley.edu>
Bruce Zhang <brucezhang@berkeley.edu>
Derek Pierce <dap92@berkeley.edu>
Tayo Olukoya <tolukoya@berkeley.edu>

---- PRELIMINARIES ----

>> If you have any preliminary comments on your submission, notes for the
>> TAs, or extra credit, please give them here.

>> Please cite any offline or online sources you consulted while
>> preparing your submission, other than the Pintos documentation, course
>> text, lecture notes, and course staff.

                 ALARM CLOCK
                 ===========

---- DATA STRUCTURES ----

>> A1: Copy here the declaration of each new or changed `struct' or
>> `struct' member, global or static variable, `typedef', or
>> enumeration.  Identify the purpose of each in 25 words or less.

static struct list blocked_list
This list maintains all threads that are currently blocked by
timer_sleep() and waiting to wake up.

Member of struct thread - int64_t sleep_ticks
sleep_ticks stores the number of ticks the thread must wait prior to
waking so that timer interrupt can check and decrement this value.


---- ALGORITHMS ----

>> A2: Briefly describe what happens in a call to timer_sleep(),
>> including the effects of the timer interrupt handler.
When timer_sleep() is called the following happens:
1. Interrupts are disabled
2. Current thread's sleep_ticks is set to the value passed to timer_sleep()
3. thread_block() is called on the running thread
4. Interrupts are reenabled

With each call of timer_interrupt(), the function looks at each thread
in blocked_list and checks if thread.sleep_ticks == 0. If so it unblocks
that thread, otherwise it simply decrements sleep_ticks by one.

>> A3: What steps are taken to minimize the amount of time spent in
>> the timer interrupt handler?
Rather than iterating through all threads to check for blocked threads to wake,
the interrupt handler only looks through threads in the blocked_list.

---- SYNCHRONIZATION ----

>> A4: How are race conditions avoided when multiple threads call
>> timer_sleep() simultaneously?
Race conditions are avoided by protecting the critical section of
code, namely the thread_block call, by disabling and re-enabling
interrupts immediately prior to and following the call. This is
important to ensure that there are not multiple, simultaneous
attempts to add threads to blocked_list.

>> A5: How are race conditions avoided when a timer interrupt occurs
>> during a call to timer_sleep()?
To ensure that a given thread maintains the correct value of
sleep_ticks, that value is also stored while interrupts are disabled.
This way, there is no possibility of timer interrupt being called
without the successfully decrementing the counter.

---- RATIONALE ----

>> A6: Why did you choose this design?  In what ways is it superior to
>> another design you considered?
While it is generally undesirable to disable and re-enable interrupts,
it is preferable in this case to using a lock or sempahore because
the timer interrupt is responsible for updating the sleep_ticks
value, and if enabled during the critical section, it would increment
ticks without also decrementing all appropriate sleep_ticks.

We also chose to create a new list of blocked threads to speed up
the timer_interrupt, which has to check for threads to unblock.
An alternative is to simply iterate through all existing threads,
but this approach is slower and unnecessary.

             PRIORITY SCHEDULING
             ===================

---- DATA STRUCTURES ----

>> B1: Copy here the declaration of each new or changed `struct' or
>> `struct' member, global or static variable, `typedef', or
>> enumeration.  Identify the purpose of each in 25 words or less.
static struct hash priorityHash; Hash table where the hashing function returns the priority of the thread put in

static struct lock set_lock; Lock used when threads are switching priority

static struct hash oldPriorities; Stores the old priorities of threads that received a priority donation.


>> B2: Explain the data structure used to track priority donation.
>> Use ASCII art to diagram a nested donation.  (Alternately, submit a
>> .png file.)
A hash table is used to hold current priorities, when a thread receives a donation it will update in that hash table. There is also a hash table of original priorities, so when a thread finishes it can revert back to its original priority.

thread A with priority 5, thread B with priority 10, thread C with priority 20
thread A has lock 1, thread B needs lock 1 and has lock 2, thread C needs lock 2

Step 1. A<-donates--B    C
Step 2. A     B<-donates--C
Step 3. A<-donates C's--B   C

---- ALGORITHMS ----

>> B3: How do you ensure that the highest priority thread waiting for
>> a lock, semaphore, or condition variable wakes up first?
All the waiting threads will be in the hash table with their priorities as
the result of the hash function, the hash table also takes in a less function
which can be used to keep the priorities in the right order. Whenever a thread
is being pulled out of the hash table it will be the highest priority because when we initialize the hash table we can give it a comparator that puts highest priorities first.

>> B4: Describe the sequence of events when a call to lock_acquire()
>> causes a priority donation.  How is nested donation handled?
First a low priority thread acquires the lock, but before it can release the
the lock it is kicked out by a medium priority thread. Now when a high priority
thread comes along and tries to call lock_acquire() it won't be able to because
the low priority thread has not been able to run, so the high priority thread
donates its priority to the low priority thread. This allows for the low
priority thread to get CPU time which allows it to finish and call lock_release()
Once the lock is released the high priority is able to run. If a thread tries to acquire a lock and realizes it is already acquired it will check the priority of the thread with the lock. If it sees the priority is lower than its own it will donate its priority, and the thread with the lock will call thread_set_priority() with the priority it has received. If the donator has a lock that an even higher priority thread needs it will receive a donation and change its priority, when its priority changes it will check if it is still waiting for the first thread to release the lock and if it is it will donate the priority it just received.



>> B5: Describe the sequence of events when lock_release() is called
>> on a lock that a higher-priority thread is waiting for.
Once lock_release() is called the high priority thread that has been sitting
idle until it gets a opportunity to acquire the lock wakes up and calls
lock_acquire(), once it has the lock it is able to run

---- SYNCHRONIZATION ----

>> B6: Describe a potential race in thread_set_priority() and explain
>> how your implementation avoids it.  Can you use a lock to avoid
>> this race?
If a thread is pulled off the ready list while a thread is setting priority it
could trigger a race condition, two different threads could be pulled depending
if the thread setting its priority has already done the change. Locks can be used
and we are using a lock that is acquired when a thread begins to change its priority
and released once it has changed.

---- RATIONALE ----

>> B7: Why did you choose this design?  In what ways is it superior to
>> another design you considered?
We considered building a priority queue to hold the thread priorities but decided
that using the built in hash structure could do everything we needed and would
avoid bugs because it was given to us.

              ADVANCED SCHEDULER
              ==================

---- DATA STRUCTURES ----

>> C1: Copy here the declaration of each new or changed `struct' or
>> `struct' member, global or static variable, `typedef', or
>> enumeration.  Identify the purpose of each in 25 words or less.

---- ALGORITHMS ----

>> C2: Suppose threads A, B, and C have nice values 0, 1, and 2.  Each
>> has a recent_cpu value of 0.  Fill in the table below showing the
>> scheduling decision and the priority and recent_cpu values for each
>> thread after each given number of timer ticks:

timer  recent_cpu    priority   thread
ticks   A   B   C   A   B   C   to run
-----  --  --  --  --  --  --   ------
 0
 4
 8
12
16
20
24
28
32
36

>> C3: Did any ambiguities in the scheduler specification make values
>> in the table uncertain?  If so, what rule did you use to resolve
>> them?  Does this match the behavior of your scheduler?

>> C4: How is the way you divided the cost of scheduling between code
>> inside and outside interrupt context likely to affect performance?

---- RATIONALE ----

>> C5: Briefly critique your design, pointing out advantages and
>> disadvantages in your design choices.  If you were to have extra
>> time to work on this part of the project, how might you choose to
>> refine or improve your design?