# Project 2: Threads
## Preliminaries
If you have any preliminary comments on your submission, notes for the TAs, 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
### Alarm Clock - Data Structures
- 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.
### Alarm Clock - Algorithms
- Briefly describe what happens in a call to `timer_sleep()`, including the effects of the
timer interrupt handler.
- What steps are taken to minimize the amount of time spent in the timer interrupt handler?
### Alarm Clock - Synchronization
- How are race conditions avoided when multiple threads call `timer_sleep()` simultaneously?
- How are race conditions avoided when a timer interrupt occurs during a call to
`timer_sleep()`?
### Alarm Clock - Rationale
- Why did you choose this design? In what ways is it superior to another design you
considered?
## Priority Scheduling
### Priority Scheduling - Data Structures
- 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.
- Explain the data structure used to track priority donation. Use ASCII art to diagram a
nested donation. (Alternately, submit a .png file.)
### Priority Scheduling - Algorithms
- How do you ensure that the highest priority thread waiting for a lock, semaphore, or
condition variable wakes up first?
- Describe the sequence of events when a call to `lock_acquire()` causes a priority
donation. How is nested donation handled?
- Describe the sequence of events when `lock_release()` is called on a lock that a
higher-priority thread is waiting for.
### Priority Scheduling - Synchronization
- Describe a potential race in `thread_set_priority()` and explain how your implementation
avoids it. Can you use a lock to avoid this race?
### Priority Scheduling - Rationale
- Why did you choose this design? In what ways is it superior to another design you
considered?
## Advanced Scheduler
### Advanced Scheduler - Data Structures
- 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.
### Advanced Scheduler - Algorithms
- How is the way you divided the cost of scheduling between code inside and outside interrupt
context likely to affect performance?
### Advanced Scheduler - Rationale
- 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?
- 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?
## Changes
Discuss any changes you made since your initial design document. Explain why you made those changes. Feel free to reiterate what you discussed with your TA during the design review if necessary.
## Reflection
Discuss the contribution of each member. Make sure to be specific about the parts of each task each member worked on. Reflect on the overall working environment and discuss what went well and areas of improvement.
## Testing
For the test case you write, provide
- Description of the feature your test case is supposed to test.
- Overview of how the mechanics of your test case work, as well as a qualitative description
of the expected output.
- Output and results of your own PintOS kernel when you run the test case. These files will
have the extensions .output and .result.
Two non-trivial potential kernel bugs and how they would have affected the output of this test case. Express these in the form "If my kernel did X instead of Y, then the test case would output Z instead". You should identify two different bugs for your test case. These bugs should be related to your test case (e.g. syntax errors don't count).
In addition, tell us about your experience writing tests for PintOS. What can be improved about the PintOS testing system? What did you learn from writing test cases?
## Concept Check Questions
- When a kernel thread in PintOS calls `thread_exit`, when and where is the page containing
its stack and TCB (i.e. `struct thread`) freed? Why can't we just free this memory by
calling `palloc_free_page` inside the `thread_exit` function?
- When the `thread_tick` function is called by the timer interrupt handler, in which stack
does it execute?
- Suppose there are two kernel threads in the system, thread A running `functionA` and thread
B running `functionB`. Give a scheduler ordering in which the following code can lead to
deadlock.
>
> ```c
> struct lock lockA; // Global lock
> struct lock lockB; // Global lock
>
> void functionA() {
> lock_acquire(&lockA);
> lock_acquire(&lockB);
> lock_release(&lockB);
> lock_release(&lockA);
> }
>
> void functionB() {
> lock_acquire(&lockB);
> lock_acquire(&lockA);
> lock_release(&lockA);
> lock_release(&lockB);
> }
> ```
- Consider the following scenario: there are two kernel threads in the system, Thread A and
Thread B. Thread A is running in the kernel, which means Thread B must be on the ready
queue, waiting patiently in `threads/switch.S`. Currently in PintOS, threads cannot
forcibly kill each other. However, suppose that Thread A decides to kill Thread B by taking
it off the ready queue and freeing its thread stack. This will prevent Thread B from
running, but what issues could arise later from this action?