-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDESIGNDOC.txt
138 lines (98 loc) · 4.47 KB
/
DESIGNDOC.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
+--------------------+
| CSE231 |
| PROJECT 1: THREADS |
| DESIGN DOCUMENT |
+--------------------+
---- GROUP ----
Bhupesh Singh Kainth <bhupesh17040@iiitd.ac.in>
Shloak Aggarwal <shloak17107@iiitd.ac.in>
Shashwat Jain <shashwat17103@iiitd.ac.in>
---- PRELIMINARIES ----
All changes we have made are preceded and succeeded by comments.
>> 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.
---- TEST CASES ----
priority-donate-one
priority-donate-multiple
priority-donate-multiple2
priority-donate-nest
priority-donate-sema
priority-donate-lower
priority-sema
priority-condvar
priority-donate-chain
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.
---- ALGORITHMS ----
>> A2: Briefly describe what happens in a call to timer_sleep(),
>> including the effects of the timer interrupt handler.
>> A3: What steps are taken to minimize the amount of time spent in
>> the timer interrupt handler?
---- SYNCHRONIZATION ----
>> A4: How are race conditions avoided when multiple threads call
>> timer_sleep() simultaneously?
>> A5: How are race conditions avoided when a timer interrupt occurs
>> during a call to timer_sleep()?
---- RATIONALE ----
>> A6: Why did you choose this design? In what ways is it superior to
>> another design you considered?
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.
struct thread;
struct list lockforthread;
int pri_min;
struct list_elem elem;
>> B2: Explain the data structure used to track priority donation.
>> Use ASCII art to diagram a nested donation. (Alternately, submit a
>> .png file.)
We store our locks and thread priorities in a doubly linked list to
ensure proper priority donation.
---- ALGORITHMS ----
>> B3: How do you ensure that the highest priority thread waiting for
>> a lock, semaphore, or condition variable wakes up first?
The threads are stored in a list of type list_insert_ordered, which
ensures that the thread with the highest priority will always be at
the front of the list. If the priority of any of the waiting threads
is changed, the list will sort itself again in descending order in
terms of highest priority. So, when it is time for a thread to wake
up, the highest priority thread at the front of the list will always
be called.
>> B4: Describe the sequence of events when a call to lock_acquire()
>> causes a priority donation. How is nested donation handled?
If multilevel feedback queue is not required and the lock is not free,
sema_down is called, which waits for sema's value to become positive
and then atomically decrements it. The lock's holder is set to the
current thread.
>> B5: Describe the sequence of events when lock_release() is called
>> on a lock that a higher-priority thread is waiting for.
The holder element of lock structure is set to NULL and sema_up is
called, which increments sema's value and wakes up one thread of those
waiting for sema, if any.
---- 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 more than one thread wants to set priority at the same time, it
will cause a race condition. To avoid this, interrupts are turned off.
---- RATIONALE ----
>> B7: Why did you choose this design? In what ways is it superior to
>> another design you considered?
We had initially planned to keep our doubly linked list unordered and
select the thread with the highest priority at retrieval time. In this
case, list add would have taken O(1) time and retrieval O(n) time in
the worst case. Instead, we used list_insert_ordered to keep our list
sorted after each add or retrieval. This way we were able to optimize
priority donation and starvation because the next thread to be run
will always be at the head of the list. The time for list add and
list retrieve will be O(n) and O(1), respectively