PROJECT1-DESIGNDOC

			+--------------------+
                        |        CS5600      |
                        | PROJECT 1: THREADS |
                        |   DESIGN DOCUMENT  |
                        +--------------------+
                                   
---- GROUP ----

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

Guanghao Ding <ding.g@husky.neu.edu>
Wu Jiang <wujiang@ccs.neu.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.
* Busy-waiting
 http://en.wikipedia.org/wiki/Busy_waiting
* Priority inversion
 http://en.wikipedia.org/wiki/Priority_inversion
* Interruption
 http://en.wikipedia.org/wiki/Real-time_operating_system
* RR scheduling
 http://en.wikipedia.org/wiki/Round-robin_scheduling
* Some university’s implementation suggestions
 http://www.ida.liu.se/~TDDB68/labs/lab1.shtml
* Some body's implementation
http://github.com/ChrisKXu/pintos

                             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.
Added to struct thread:
 
   /* add a new variable to store ticks the thread should sleep */
   int64_t sleep_ticks;
 
An ascending order list by sleep_ticks used to store threads that are put to 
sleep struct list sleep_list;

---- ALGORITHMS ----

>> A2: Briefly describe what happens in a call to timer_sleep(),
>> including the effects of the timer interrupt handler.
 
In a call to timer_sleep()
1. The current thread’s sleep_ticks is set to the given sleep ticks plus the 
current ticks. 
2. Disable interrupts
3. The thread is inserted to the sleep list
4. Block the thread
5. Reset interrupts level to its old one
 
So, in timer interrupt handler,
1. Check the list to see if any threads need to be waken up
2. If any, reset the thread’s sleep_ticks
3. Disable interrupts
4. Remove it from the sleep list,
5. Unblock the thread 
6. Reset interrupts level to its old one

>> A3: What steps are taken to minimize the amount of time spent in
>> the timer interrupt handler?
An ordered list which is sorted and inserted by sleep_ticks number is used, 
so that we can check the list from the beginning and stop whenever the 
sleep_ticks is larger than the current ticks, which guarantees the later 
threads in the sleep list don’t need to be checked. By this means, we can 
minimize the time spent. 
 

---- SYNCHRONIZATION ----

>> A4: How are race conditions avoided when multiple threads call
>> timer_sleep() simultaneously?
List operations happen during interrupt is disabled. 

>> A5: How are race conditions avoided when a timer interrupt occurs
>> during a call to timer_sleep()?
The interrupt is disabled.

---- RATIONALE ----

>> A6: Why did you choose this design?  In what ways is it superior to
>> another design you considered?
To have a sleep list to store the sleeping threads are the straight forward 
thought, and following the design of ready_list, things are reasonable and 
implementable. No other designs are actually been considered, the choice 
of a sorted list and to insert by order is made to be more efficient and 
considering as a external static variable, it can only be managed inside 
the functions we write, we think it’s safe and reasonable too. 
 

                         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.
Added to struct thread
   /* Keep track of a thread’s base priority before donation*/
   int priority_original;     
   /* If a thread's priority is donated */        
   bool is_donated;                   
   /* An descending order list ordered by the highest thread priority value in 
its semaphore’s waiters list, represents all locks a thread holds, used in 
multiple donation to set current thread’s priority according to locks it holds */
   struct list locks;
   /* Thread blocked by lock, used in nested donation to find out next 
    * lock */            
   struct lock *lock_blocked_by;      
 
 
Added to struct lock
   list_elem elem_lock;             /* Lock itself as a list elem */
   /* Lock’s priority which is set to the highest priority from its 
    * semaphore’s waiters. Used in multiple donations.*/
   int priority_lock;               
 
in thread.h:
   /* A fake priority, used in priority_lock */
   #define PRIORITY_FAKE -1
   /* Lock deep level */
   #define LOCK_LEVEL 8
 

>> B2: Explain the data structure used to track priority donation.
>> Use ASCII art to diagram a nested donation.  (Alternately, submit a
>> .png file.)
As we mentioned in the above question, we added priority_original, 
is_donated, locks, lock_blocked_by to thread, and added elem_lock and
priority_lock to lock, to help track the priority donation.
 
Every time a lock is acquired by a thread, the lock will be inserted into the 
thread’s locks field, which is an descending ordered list sorted by priority_lock
 field in the lock. Correspondingly, when a lock is released, it’s removed from 
it’s holder’s locks list. And this is also where the elem_lock inside lock struct
 plays a role. 
 
In a single donation, when the lock is being acquired, the lock holder’s priority
 is checked, if it’s lower than the one who is acquiring lock, donation happens. 
In our implementation, thread’s priority_original will change with priority except
 donation, so we can assume priority_original already preserves the current 
priority. Then donee-thread’s priority is set donor-thread’s priority; is_donated
 is set to true, if it’s not true already. The lock’s priority_lock is set to be 
donor’s priority, to keep track of the highest priority in the lock’s waiter list.
 And the donor-thread’s lock_blocked_by is set to be this lock. 
 
Then it’s checked that whether the donne-thread is blocked by another lock, which 
is needed for nested donation. If yes, another donation case will happen in the 
same procedure above except the new donor is the current donee, the new donee is 
the lock holder whose lock blocks the current donee. The nested case will keep 
being checking iteratively untill no donee is blocked by some other thread or it 
reaches the highest level(LOCK_LEVEL, we defined “globally” to determine how many 
level we can search up to), whatever comes first.  
 
When a lock is released, the lock will be removed from the holder thread’s locks 
list and then comes the checking of whether multiple donation happened to this 
thread before. If the locks list is empty, no locks are held, it simply means no 
multiple donation happened, the thread should relinquish its donated priority 
using priority_original. Otherwise, get the first lock from the locks list, if the
 priority_lock field of it is unchanged (equal to the initial value PRIORITY_FAKE,
 which means no donation happened), the thread relinquish it’s priority too. If 
the field is changed, which means a donation was happened and the holder’s 
priority should be reset to it. Since locks is a descending order list sorted by 
the priority_lock field, we can guarantee that the first lock in the list has the
 highest priority among all the waiters of all locks, which is the priority the 
holder should have. 
 
Using the data structure and algorithm above, priority donation, including the 
simplest donation, multiple donation, and nest donation, can be achieved.
 
take example like this
A thread, priority 31, has lock lock_1. 
B thread, priority 32, has lock lock_2, and acquire lock_1
C thread, priority 33, acquire lock_2 
 
Step 1: At the beginning:
=========================
.---------------------------------------------------.
|                Thread A (Beginning)               |
+-------------------+-------------------------------+
| member            | value                         |
+-------------------+-------------------------------+
| priority          |                            31 |
| priority_original |                            31 |
| is_donated        | false                         |
| locks             | {lock_1 (priority_lock = -1)} |
| lock_blocked_by   | NULL                          |
'-------------------+-------------------------------'
.---------------------------------------------------.
|                Thread B (Beginning)               |
+-------------------+-------------------------------+
| member            | value                         |
+-------------------+-------------------------------+
| priority          |                            32 |
| priority_original |                            32 |
| is_donated        | false                         |
| locks             | {lock_2 (priority_lock = -1)} |
| lock_blocked_by   | NULL                          |
'-------------------+-------------------------------'
.---------------------------.
|    Thread C (Beginning)   |
+-------------------+-------+
| member            | value |
+-------------------+-------+
| priority          |    33 |
| priority_original |    33 |
| is_donated        | false |
| locks             | {}    |
| lock_blocked_by   | NULL  |
'-------------------+-------'
==================================================================
 
Step 2: B acquires lock_1:
==========================
.---------------------------------------------------.
|              Thread A (B acquires L1)             |
+-------------------+-------------------------------+
| member            | value                         |
+-------------------+-------------------------------+
| priority          |                            31 |
| priority_original |                            32 |
| is_donated        | true                          |
| locks             | {lock_1 (priority_lock = 32)} |
| lock_blocked_by   | NULL                          |
'-------------------+-------------------------------'
.---------------------------------------------------.
|              Thread B (B acquires L1)             |
+-------------------+-------------------------------+
| member            | value                         |
+-------------------+-------------------------------+
| priority          |                            32 |
| priority_original |                            32 |
| is_donated        | false                         |
| locks             | {lock_2 (priority_lock = -1)} |
| lock_blocked_by   | &lock1                        |
'-------------------+-------------------------------'
.---------------------------.
|  Thread C (B acquires L1) |
+-------------------+-------+
| member            | value |
+-------------------+-------+
| priority          |    33 |
| priority_original |    33 |
| is_donated        | false |
| locks             | {}    |
| lock_blocked_by   | NULL  |
'-------------------+-------'
==================================================================
 
STEP 3-1: C acquires lock_2:
============================
.---------------------------------------------------.
|          Thread B (C acquires L2, Step 1)         |
+-------------------+-------------------------------+
| member            | value                         |
+-------------------+-------------------------------+
| priority          |                            32 |
| priority_original |                            33 |
| is_donated        | true                          |
| locks             | {lock_2 (priority_lock = 33)} |
| lock_blocked_by   | &lock1                        |
'-------------------+-------------------------------'
.----------------------------------.
| Thread C (C acquires L2, Step 1) |
+----------------------+-----------+
| member               | value     |
+----------------------+-----------+
| priority             |        33 |
| priority_original    |        33 |
| is_donated           | false     |
| locks                | {}        |
| lock_blocked_by      | &lock_2   |
'----------------------+-----------'
.---------------------------------------------------.
|          Thread A (C acquires L2, Step 1)         |
+-------------------+-------------------------------+
| member            | value                         |
+-------------------+-------------------------------+
| priority          |                            31 |
| priority_original |                            32 |
| is_donated        | true                          |
| locks             | {lock_1 (priority_lock = 32)} |
| lock_blocked_by   | NULL                          |
'-------------------+-------------------------------'
==================================================================
 
STEP 3-2: C acquires lock_2:
============================
.---------------------------------------------------.
|          Thread B (C acquires L2, Step 2)         |
+-------------------+-------------------------------+
| member            | value                         |
+-------------------+-------------------------------+
| priority          |                            32 |
| priority_original |                            33 |
| is_donated        | true                          |
| locks             | {lock_2 (priority_lock = 33)} |
| lock_blocked_by   | &lock1                        |
'-------------------+-------------------------------'
.----------------------------------.
| Thread C (C acquires L2, Step 2) |
+----------------------+-----------+
| member               | value     |
+----------------------+-----------+
| priority             |        33 |
| priority_original    |        33 |
| is_donated           | false     |
| locks                | {}        |
| lock_blocked_by      | &lock_2   |
'----------------------+-----------'
.---------------------------------------------------.
|          Thread A (C acquires L2, Step 2)         |
+-------------------+-------------------------------+
| member            | value                         |
+-------------------+-------------------------------+
| priority          |                            31 |
| priority_original |                            33 |
| is_donated        | true                          |
| locks             | {lock_1 (priority_lock = 32)} |
| lock_blocked_by   | NULL                          |
'-------------------+-------------------------------'
==================================================================
 
STEP 4: A releases lock_1:
==========================
.-------------------------------.
| Thread A (A releases lock_1)) |
+---------------------+---------+
| member              | value   |
+---------------------+---------+
| priority            |      31 |
| priority_original   |      31 |
| is_donated          | false   |
| locks               | {}      |
| lock_blocked_by     | NULL    |
'---------------------+---------'
.----------------------------------------------------.
|            Thread B (A releases lock_1)            |
+-------------------+--------------------------------+
| member            | value                          |
+-------------------+--------------------------------+
| priority          |                             32 |
| priority_original |                             33 |
| is_donated        | true                           |
| locks             | {&lock_2 (priority_lock = 33), |
|                   |  &lock_1 (priority_lock = 32)} |
| lock_blocked_by   | NULL                           |
'-------------------+--------------------------------'
.------------------------------.
| Thread C (A releases lock_1) |
+--------------------+---------+
| member             | value   |
+--------------------+---------+
| priority           |      33 |
| priority_original  |      33 |
| is_donated         | false   |
| locks              | {}      |
| lock_blocked_by    | &lock_2 |
'--------------------+---------'
==================================================================
 
STEP 5: B releases lock_2:
==========================
.-------------------------------.
| Thread A (B releases lock_2)) |
+---------------------+---------+
| member              | value   |
+---------------------+---------+
| priority            |      31 |
| priority_original   |      31 |
| is_donated          | false   |
| locks               | {}      |
| lock_blocked_by     | NULL    |
'---------------------+---------'
.----------------------------------------------------.
|            Thread B (B releases lock_2)            |
+-------------------+--------------------------------+
| member            | value                          |
+-------------------+--------------------------------+
| priority          |                             32 |
| priority_original |                             32 |
| is_donated        | false                          |
| locks             | {&lock_1 (priority_lock = 32)} |
| lock_blocked_by   | NULL                           |
'-------------------+--------------------------------'
.----------------------------------------------------.
|            Thread C (B releases lock_2)            |
+-------------------+--------------------------------+
| member            | value                          |
+-------------------+--------------------------------+
| priority          |                             33 |
| priority_original |                             33 |
| is_donated        | false                          |
| locks             | {&lock_2 (priority_lock = 33)} |
| lock_blocked_by   | NULL                           |
'-------------------+--------------------------------'
==================================================================
 

---- ALGORITHMS ----

>> B3: How do you ensure that the highest priority thread waiting for
>> a lock, semaphore, or condition variable wakes up first?
A: Change the waiters list to a sorted list, which is ordering by priority.
Every time waking up the waiter, threads are put to ready list from the
beginning to the end, which is actually from the highest priority to a 
the lowest priority.
 

>> B4: Describe the sequence of events when a call to lock_acquire()
>> causes a priority donation.  How is nested donation handled?
A: Steps:
   1. Disable interrupts
   2. Donation
     2.1 IF lock_holder is NULL
     2.1.1  sema_down: if sema value is 0, put all threads acquiring this
            lock into the sema’s waiters list until sema value becomes 
            positive 
     2.1.2  Set the current thread to this lock’s holder
     2.2 ELSE compare lock_holder’s (L) priority with current thread’s (C)
         priority:
     2.2.1  IF L’s priority > C’s priority
     2.2.1.1  Does sema_down until the sema value becomes positive
              which means lock is released             
     2.2.1.2  Set the current thread to this lock’s holder
     2.2.2  ELSE:
     2.2.2.1  [Donation] Set L’s priority to C’s priority
     2.2.2.2  Does sema_down, until the lock is released
     2.2.2.3  The current thread becomes this lock’s holder
   3. Set interrupts to the status before it was disabled
 
If the current lock holder is blocked by another lock, then using thread->
lock_blocked_by to find out that lock, does the above donation process to that 
lock. Repeat this process until thread->lock_blocked_by is NULL or it reaches a
certain depths set by users (in our program, since there are 8 threads, we set 
the nest depths to 8). After this process, all locks holders have the same 
priority as the thread which acquires the first lock.

>> B5: Describe the sequence of events when lock_release() is called
>> on a lock that a higher-priority thread is waiting for.
A: Steps:
   1. Make sure this thread is the holder of this lock. If it is not the
      holder, report error.
   2. Disable interrupts.
   3. Set the lock holder to NULL
   4. Does sema_up: increase the sema value by 1, which means this
      lock which can be get by its semaphore.waiters or any thread is
      going to acquire it
   5. Set the original lock_holder’s priority value
     5.1 IF no donation happened
           Set lock_holder’s priority value to its original priority value
     5.2 ELSE
     5.2.1  IF original lock_holder holds only this lock
     5.2.1.1  Set original lock_holder’s priority value to its original 
              priority value
     5.2.2  ELSE (Nested donation)
     5.2.2.1  Set original lock_holder’s priority to the highest priority
              in its locks list.
 
After this lock is released, this lock’s sema value will increased by 1 and sema 
value becomes positive. The waited highest-priority thread will get this lock.

---- 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?

A: During priority donation, the lock holder’s priority may be set by it’s donor,
at the mean time, the thread itself may want to change the priority.
If the donor and the thread itself set the priority in a different order, may 
cause a different result. 
 
We disable the interrupt to prevent it happens. It can not be avoided using a lock
in our implementation, since we didn’t provide the interface and structure to 
share a lock between donor and the thread itself. If we add a lock to the thread 
struct, it may be avoided using it. 
 

---- RATIONALE ----

>> B7: Why did you choose this design?  In what ways is it superior to
>> another design you considered?
A: At the beginning, in order to avoid making struct thread and struct lock 
bigger, we did not added is_donated in struct thread, did not add priority_lock in
 struct lock. 
 
Instead of using is_donated, we use the changes of priority_original to indicate 
whether or not a thread’s priority is donated. For example, we initialize 
priority_original to -1 when it is created. Whenever a donation happens, we set it
to the thread’s priority just before donation happening. We compare the value of 
priority and priority_original -- if they are different and priority_original has 
been changed from -1 to other value, then it means a donation happened. Thus, 
priority_original has two functions: 1. store the priority value just before 
donation; 2. indicate whether or not a donation happened. There will be a problem 
when priority lower involved: if the new priority is higher than the current 
donated priority, both priority and priority and priority_original need to change 
to the new priority. This is still inside of a donation process, but their values 
are the same, by which, we know there is no donation happened. But it’s not true. 
Thus, we added a bool is_donated to indicate if a donation happens.
 
For struct lock, instead of adding a new memeber in lock, we can get the highest 
priority in its waiters list by doing this 
list_entry (list_front (lock->semaphore.waiters), struct thread, elem)->priority. 
But the code will be more complex.
 
For multiple donations, after the thread releases one lock, its priority should be
 the highest thread priority in the next lock’s waiters
In order to achieve multiple donations, we need to keep track of the highest 
priority for that lock. At the beginning, instead of using a lock list inside of 
struct thread, we thought it would make the list smaller if we keep track of the 
highest-priority thread in the lock’s waiters list. But it did not work because 
after a while, another higher-priority thread acquires this lock, we need to 
replace the thread (or priority) just put in the list. We can not find that thread
(or priority) from the list. Replacement can not be done.

                          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.
struct thread
   int nice;                             /* Thread nice value */
   int recent_cpu;                       /* Thread recent CPU */
 
In thread.h
/* Nice value boundary */
#define NICE_MIN -20
#define NICE_DEFAULT 0
#define NICE_MAX 20
 
In thread.c
static int load_avg; /* load_avg for BSD scheduling. Fixed-point number */

---- 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:

.-------------------------------------------------------------------------.
|             |  recent_cpu  |   priority   |               |             |
+-------------+----+----+----+----+----+----+---------------+-------------+
| timer ticks | A  | B  | C  | A  | B  | C  | thread to run | Note        |
+-------------+----+----+----+----+----+----+---------------+-------------+
|           0 |  0 |  1 |  2 | 63 | 61 | 59 | A             |             |
|           4 |  4 |  1 |  2 | 62 | 61 | 59 | A             |             |
|           8 |  7 |  2 |  4 | 61 | 61 | 58 | B             | Round robin |
|          12 |  6 |  6 |  6 | 61 | 59 | 58 | A             |             |
|          16 |  9 |  6 |  7 | 60 | 59 | 57 | A             |             |
|          20 | 12 |  6 |  8 | 60 | 59 | 57 | A             |             |
|          24 | 15 |  6 |  9 | 59 | 59 | 57 | B             | Round robin |
|          28 | 14 | 10 | 10 | 59 | 58 | 57 | A             |             |
|          32 | 16 | 10 | 11 | 58 | 58 | 56 | B             | Round robin |
|          36 | 15 | 14 | 12 | 59 | 57 | 56 | A             |             |
'-------------+----+----+----+----+----+----+---------------+-------------'
 

>> 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?
A: recent_cpu here is ambiguous here. When we calculate recent_cpu, we did not 
consider the time that CPU spends on the calculations every 4 ticks, like 
load_avg, recent_cpu for all threads, priority for all threads in all_list, 
resort the ready_list. When CPU does these calculations, the current thread needs 
to yield, and not running. Thus, every 4 ticks, the real ticks that is added to 
recent_cpu (recent_cpu is added 1 every ticks) is not really 4 ticks -- less than 
4 ticks. But we could not figure out how much time it spends. What we did was 
adding 4 ticks to recent_cpu every 4 ticks.
 
Our implementation of BSD scheduler is the same as this. We just count the ticks 
since system boots, and does all the above calculations every 4 ticks.
 
>> C4: How is the way you divided the cost of scheduling between code
>> inside and outside interrupt context likely to affect performance?
If the CPU spends too much time on calculations for recent_cpu, load_avg and 
priority, then it takes away most of the time that a thread before enforced 
preemption. Then this thread can not get enough running time as expected and it 
will run longer. This will cause itself got blamed for occupying more CPU time, 
and raise its load_avg, recent_cpu, and therefore lower its priority. This may 
disturb the scheduling decisions making. Thus, if the cost of scheduling inside 
the interrupt context goes up, it will lower 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?
A: Our design did not apply the 64 queues. We used only one queue -- the 
ready_list that Pintos originally have. But as the same as what we did for the 
task 2, we keep the ready_list as an priority oriented descending order at the 
every beginning -- that is, whenever we insert a thread into the ready_list, we 
insert it in order. The time complexity is O(n). Every fourth tick, it is required
to calculate priority for all the threads in the all_list. After this, we need to 
sort the ready_list, which will take O(n lgn) time. Since we need to do this job 
every 4 ticks, it will make a thread’s running ticks shorter than it is expected. 
If n becomes larger, thread switching may happen quite often. If we use 64 queues 
for the ready threads, we can put the 64 queues in an array with index equaling to
its priority value. When the thread is first inserted, it only need to index the 
queue by this thread’s priority. This will take only O(1) time. After priority c
alculation for all threads every fourth tick, it takes O(n) time to re-insert the 
ready threads. But our implementation is better than this situation -- ready_list 
is not ordered. Like pintos originally did, for every new unblocked thread, just 
push back to the ready_list. When it need to find next thread to run, it has to 
reorder the ready_list. Sorting takes O(n lgn) time. It needs to repeat this 
sorting whenever we need to call thread_next_to_run, and after calculating all 
threads’ priorities every fourth tick.
 
Thus, we’d like to implement 64 queues instead of 1 queue for ready threads.

>> C6: The assignment explains arithmetic for fixed-point math in
>> detail, but it leaves it open to you to implement it.  Why did you
>> decide to implement it the way you did?  If you created an
>> abstraction layer for fixed-point math, that is, an abstract data
>> type and/or a set of functions or macros to manipulate fixed-point
>> numbers, why did you do so?  If not, why not?
A: As mentioned in the BSD scheduling manual, recent_cpu and load_avg are real 
numbers, but pintos disabled float numbers. Instead using float number, we can 
use fixed-point numbers. So we use fixed-point numbers to represent recent_cpu 
and load_avg.
 
We used #define macro in the new created header fixed-point.h under thread. We 
did not implement them as inline functions in thread.c because
1. They are simple. Every parameter only appears once in the calculation, which 
can avoid the #define macro’s error, which calculate the same parameter 
(expression) multiple times.
2. They are faster than inline functions.

                           SURVEY QUESTIONS
                           ================

Answering these questions is optional, but it will help us improve the
course in future quarters.  Feel free to tell us anything you
want--these questions are just to spur your thoughts.  You may also
choose to respond anonymously in the course evaluations at the end of
the quarter.

>> In your opinion, was this assignment, or any one of the three problems
>> in it, too easy or too hard?  Did it take too long or too little time?
Multiple donation took us a lot of time. We wanted to avoid adding a list of 
locks as a thread member, but failed.

>> Did you find that working on a particular part of the assignment gave
>> you greater insight into some aspect of OS design?
Trying to understand what’s behind thread_create, lock_acquire and lock_release 
is difficult. But it helped us dig deeper and understand more about how a thread 
working on a lock and interact with other threads.

>> Is there some particular fact or hint we should give students in
>> future quarters to help them solve the problems?  Conversely, did you
>> find any of our guidance to be misleading?
Actually, we spent some time on what’s multiple donation. All we saw from the 
manual is one sentence saying that we should implement multiple donation. An 
example provided would work perfect.

>> Do you have any suggestions for the TAs to more effectively assist
>> students, either for future quarters or the remaining projects?

>> Any other comments?