Rev 43 | Rev 45 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 43 | Rev 44 | ||
---|---|---|---|
1 | <?xml version="1.0" encoding="UTF-8"?> |
1 | <?xml version="1.0" encoding="UTF-8"?> |
2 | <chapter id="sync"> |
2 | <chapter id="sync"> |
3 | <?dbhtml filename="sync.html"?> |
3 | <?dbhtml filename="sync.html"?> |
4 | 4 | ||
5 | <title>Mutual exclusion and synchronization</title> |
5 | <title>Mutual exclusion and synchronization</title> |
6 | 6 | ||
7 | <section> |
7 | <section> |
8 | <title>Introduction</title> |
8 | <title>Introduction</title> |
9 | 9 | ||
10 | <para>The HelenOS operating system is designed to make use of parallelism |
10 | <para>The HelenOS operating system is designed to make use of parallelism |
11 | offered by hardware and to exploit concurrency of both the kernel and |
11 | offered by hardware and to exploit concurrency of both the kernel and |
12 | userspace tasks. This is achieved through multiprocessor support and |
12 | userspace tasks. This is achieved through multiprocessor support and |
13 | several levels of multiprogramming (i.e. multitasking, multithreading and |
13 | several levels of multiprogramming (i.e. multitasking, multithreading and |
14 | through userspace pseudo threads). However, such a highly concurrent |
14 | through userspace pseudo threads). However, such a highly concurrent |
15 | environment needs safe and efficient ways to handle mutual exclusion and |
15 | environment needs safe and efficient ways to handle mutual exclusion and |
16 | synchronization of many execution flows.</para> |
16 | synchronization of many execution flows.</para> |
17 | </section> |
17 | </section> |
18 | 18 | ||
19 | <section> |
19 | <section> |
20 | <title>Active kernel primitives</title> |
20 | <title>Active kernel primitives</title> |
21 | 21 | ||
22 | <section> |
22 | <section> |
23 | <title>Spinlocks</title> |
23 | <title>Spinlocks</title> |
24 | 24 | ||
25 | <para>The basic mutual exclusion primitive is the spinlock. Spinlock |
25 | <para>The basic mutual exclusion primitive is the spinlock. Spinlock |
26 | implements busy waiting for an availability of a memory lock (i.e. |
26 | implements busy waiting for an availability of a memory lock (i.e. |
27 | simple variable) in a multiprocessor-safe manner. This safety is |
27 | simple variable) in a multiprocessor-safe manner. This safety is |
28 | achieved through the use of a specialized, architecture-dependent, |
28 | achieved through the use of a specialized, architecture-dependent, |
29 | atomic test-and-set operation which either locks the spinlock (i.e. sets |
29 | atomic test-and-set operation which either locks the spinlock (i.e. sets |
30 | the variable) or, provided that it is already locked, leaves it |
30 | the variable) or, provided that it is already locked, leaves it |
31 | unaltered. In any case, the test-and-set operation returns a value, thus |
31 | unaltered. In any case, the test-and-set operation returns a value, thus |
32 | signalling either success (i.e. zero return value) or failure (i.e. |
32 | signalling either success (i.e. zero return value) or failure (i.e. |
33 | non-zero value) in acquiring the lock. Note that this makes the |
33 | non-zero value) in acquiring the lock. Note that this makes the |
34 | fundamental difference between the naive algorithm that doesn't use the |
34 | fundamental difference between the naive algorithm that doesn't use the |
35 | atomic operation and the spinlock algortihm. While the naive algorithm |
35 | atomic operation and the spinlock algortihm. While the naive algorithm |
36 | is prone to race conditions on SMP configuratinos and thus is completely |
36 | is prone to race conditions on SMP configuratinos and thus is completely |
37 | SMP-unsafe, the spinlock algorithm eliminates the possibility of race |
37 | SMP-unsafe, the spinlock algorithm eliminates the possibility of race |
38 | conditions and is suitable for mutual exclusion use.</para> |
38 | conditions and is suitable for mutual exclusion use.</para> |
39 | 39 | ||
40 | <para>The semantics of the test-and-set operation is that the spinlock |
40 | <para>The semantics of the test-and-set operation is that the spinlock |
41 | remains unavailable until this operation called on the respective |
41 | remains unavailable until this operation called on the respective |
42 | spinlock returns zero. HelenOS builds two functions on top of |
42 | spinlock returns zero. HelenOS builds two functions on top of |
43 | test-and-set operation. The first is the unconditional attempt to |
43 | test-and-set operation. The first is the unconditional attempt to |
44 | acquire the spinlock and is called <emphasis>spinlock_lock</emphasis>. |
44 | acquire the spinlock and is called <emphasis>spinlock_lock</emphasis>. |
45 | It simply loops until test-and-set returns zero. The other operation, |
45 | It simply loops until test-and-set returns zero. The other operation, |
46 | <emphasis>spinlock_trylock</emphasis>, is the conditional lock operation |
46 | <emphasis>spinlock_trylock</emphasis>, is the conditional lock operation |
47 | and calls the test-and-set only once to find out wheter it managed to |
47 | and calls the test-and-set only once to find out wheter it managed to |
48 | acquire the spinlock or not. The conditional operation is useful in |
48 | acquire the spinlock or not. The conditional operation is useful in |
49 | situations in which an algorithm cannot acquire more spinlocks in the |
49 | situations in which an algorithm cannot acquire more spinlocks in the |
50 | proper order and a deadlock cannot be avoided. In such a case, the |
50 | proper order and a deadlock cannot be avoided. In such a case, the |
51 | algorithm would detect the danger and instead of possibly deadlocking |
51 | algorithm would detect the danger and instead of possibly deadlocking |
52 | the system it would simply release some spinlocks it already holds and |
52 | the system it would simply release some spinlocks it already holds and |
53 | retry the whole operation with the hope that it will succeed next time. |
53 | retry the whole operation with the hope that it will succeed next time. |
54 | The unlock operation, <emphasis>spinlock_unlock</emphasis>, is quite |
54 | The unlock operation, <emphasis>spinlock_unlock</emphasis>, is quite |
55 | easy - it merely clears the spinlock variable.</para> |
55 | easy - it merely clears the spinlock variable.</para> |
56 | 56 | ||
57 | <para>Nevertheless, there is a special issue related to hardware |
57 | <para>Nevertheless, there is a special issue related to hardware |
58 | optimizations that modern processors implement. Particularily |
58 | optimizations that modern processors implement. Particularily |
59 | problematic is the out-of-order execution of instructions within the |
59 | problematic is the out-of-order execution of instructions within the |
60 | critical section protected by a spinlock. The processors are always |
60 | critical section protected by a spinlock. The processors are always |
61 | self-consistent so that they can carry out speculatively executed |
61 | self-consistent so that they can carry out speculatively executed |
62 | instructions in the right order with regard to dependencies among those |
62 | instructions in the right order with regard to dependencies among those |
63 | instructions. However, the dependency between instructions inside the |
63 | instructions. However, the dependency between instructions inside the |
64 | critical section and those that implement locking and unlocking of the |
64 | critical section and those that implement locking and unlocking of the |
65 | respective spinlock is not implicit on some processor architectures and |
65 | respective spinlock is not implicit on some processor architectures and |
66 | the processor needs to be explicitly told about each occurrence of such |
66 | the processor needs to be explicitly told about each occurrence of such |
67 | a dependency. Therefore, HelenOS adds architecture-specific hooks to all |
67 | a dependency. Therefore, HelenOS adds architecture-specific hooks to all |
68 | <emphasis>spinlock_lock</emphasis>, |
68 | <emphasis>spinlock_lock</emphasis>, |
69 | <emphasis>spinlock_trylock</emphasis> and |
69 | <emphasis>spinlock_trylock</emphasis> and |
70 | <emphasis>spinlock_unlock</emphasis> to prevent the instructions inside |
70 | <emphasis>spinlock_unlock</emphasis> to prevent the instructions inside |
71 | the critical section from bleeding out. On some architectures, these |
71 | the critical section from bleeding out. On some architectures, these |
72 | hooks can be a no-op because the dependencies are implicitly there |
72 | hooks can be a no-op because the dependencies are implicitly there |
73 | because of the special properties of locking and unlocking instructions. |
73 | because of the special properties of locking and unlocking instructions. |
74 | However, other architectures need to instrument these hooks with |
74 | However, other architectures need to instrument these hooks with |
75 | different memory barriers, depending on what operations can bleed |
75 | different memory barriers, depending on what operations can bleed |
76 | out.</para> |
76 | out.</para> |
77 | 77 | ||
78 | <para>Spinlocks have one significant drawback: when held for longer time |
78 | <para>Spinlocks have one significant drawback: when held for longer time |
79 | periods, they harm both parallelism and concurrency. Processor executing |
79 | periods, they harm both parallelism and concurrency. Processor executing |
80 | <emphasis>spinlock_lock</emphasis> does not do any fruitful work and is |
80 | <emphasis>spinlock_lock</emphasis> does not do any fruitful work and is |
81 | effectively halted until it can grab the lock and proceed. Similarily, |
81 | effectively halted until it can grab the lock and proceed. Similarily, |
82 | other threads cannot execute on the processor that holds the spinlock |
82 | other threads cannot execute on the processor that holds the spinlock |
83 | because the kernel disables preemption on that processor when a spinlock |
83 | because the kernel disables preemption on that processor when a spinlock |
84 | is held. The reason behind disabling preemption is priority inversion |
84 | is held. The reason behind disabling preemption is priority inversion |
85 | problem avoidance. For the same reason, threads are strongly discouraged |
85 | problem avoidance. For the same reason, threads are strongly discouraged |
86 | from sleeping when they hold a spinlock.</para> |
86 | from sleeping when they hold a spinlock.</para> |
87 | 87 | ||
88 | <para>To summarize, spinlocks represent very simple and essential mutual |
88 | <para>To summarize, spinlocks represent very simple and essential mutual |
89 | exclusion primitive for SMP systems. On the other hand, spinlocks scale |
89 | exclusion primitive for SMP systems. On the other hand, spinlocks scale |
90 | poorly because of the active loop they are based on. Therefore, |
90 | poorly because of the active loop they are based on. Therefore, |
91 | spinlocks are used in HelenOS only for a short-time mutual exclusion and |
91 | spinlocks are used in HelenOS only for a short-time mutual exclusion and |
92 | in cases where the mutual exclusion is required out of thread context. |
92 | in cases where the mutual exclusion is required out of thread context. |
93 | Lastly, spinlocks are used in the construction of passive |
93 | Lastly, spinlocks are used in the construction of passive |
94 | synchronization primitives.</para> |
94 | synchronization primitives.</para> |
95 | </section> |
95 | </section> |
96 | </section> |
96 | </section> |
97 | 97 | ||
98 | <section> |
98 | <section> |
99 | <title>Passive kernel synchronization</title> |
99 | <title>Passive kernel synchronization</title> |
100 | 100 | ||
101 | <section> |
101 | <section> |
102 | <title>Wait queues</title> |
102 | <title>Wait queues</title> |
103 | 103 | ||
104 | <para>A wait queue is the basic passive synchronization primitive on |
104 | <para>A wait queue is the basic passive synchronization primitive on |
105 | which all other passive synchronization primitives build. Simply put, it |
105 | which all other passive synchronization primitives build. Simply put, it |
106 | allows a thread to sleep until an event associated with the particular |
106 | allows a thread to sleep until an event associated with the particular |
107 | wait queue occurs. Multiple threads are notified about incoming events |
107 | wait queue occurs. Multiple threads are notified about incoming events |
108 | in first come, first served fashion. Moreover, should the event come |
108 | in first come, first served fashion. Moreover, should the event come |
109 | before any thread waits for it, it is recorded in the wait queue as a |
109 | before any thread waits for it, it is recorded in the wait queue as a |
110 | missed wakeup and later forwarded to the first thread that decides to |
110 | missed wakeup and later forwarded to the first thread that decides to |
111 | wait in the queue. The inner structures of the wait queue are protected |
111 | wait in the queue. The inner structures of the wait queue are protected |
112 | by a spinlock.</para> |
112 | by a spinlock.</para> |
113 | 113 | ||
114 | <para>The thread that wants to wait for a wait queue event uses the |
114 | <para>The thread that wants to wait for a wait queue event uses the |
115 | <emphasis>waitq_sleep_timeout</emphasis> function. The algorithm then |
115 | <emphasis>waitq_sleep_timeout</emphasis> function. The algorithm then |
116 | checks the wait queue's counter of missed wakeups and if there are any |
116 | checks the wait queue's counter of missed wakeups and if there are any |
117 | missed wakeups, the call returns immediately. The call also returns |
117 | missed wakeups, the call returns immediately. The call also returns |
118 | immediately if only a conditional wait was requested. Otherwise the |
118 | immediately if only a conditional wait was requested. Otherwise the |
119 | thread is enqueued in the wait queue's list of sleeping threads and its |
119 | thread is enqueued in the wait queue's list of sleeping threads and its |
120 | state is changed to <emphasis>Sleeping</emphasis>. It then sleeps until |
120 | state is changed to <emphasis>Sleeping</emphasis>. It then sleeps until |
121 | one of the following events happens:</para> |
121 | one of the following events happens:</para> |
122 | 122 | ||
123 | <orderedlist> |
123 | <orderedlist> |
124 | <listitem> |
124 | <listitem> |
125 | <para>another thread calls <emphasis>waitq_wakeup</emphasis> and the |
125 | <para>another thread calls <emphasis>waitq_wakeup</emphasis> and the |
126 | thread is the first thread in the wait queue's list of sleeping |
126 | thread is the first thread in the wait queue's list of sleeping |
127 | threads</para> |
127 | threads</para> |
128 | </listitem> |
128 | </listitem> |
129 | 129 | ||
130 | <listitem> |
130 | <listitem> |
131 | <para>another thread calls |
131 | <para>another thread calls |
132 | <emphasis>waitq_interrupt_sleep</emphasis> on the sleeping |
132 | <emphasis>waitq_interrupt_sleep</emphasis> on the sleeping |
133 | thread</para> |
133 | thread</para> |
134 | </listitem> |
134 | </listitem> |
135 | 135 | ||
136 | <listitem> |
136 | <listitem> |
137 | <para>the sleep timeouts provided that none of the previous occurred |
137 | <para>the sleep timeouts provided that none of the previous occurred |
138 | within a specified time limit; the limit can be infinity</para> |
138 | within a specified time limit; the limit can be infinity</para> |
139 | </listitem> |
139 | </listitem> |
140 | </orderedlist> |
140 | </orderedlist> |
141 | 141 | ||
142 | <para>All five possibilities (immediate return on success, immediate |
142 | <para>All five possibilities (immediate return on success, immediate |
143 | return on failure, wakeup after sleep, interruption and timeout) are |
143 | return on failure, wakeup after sleep, interruption and timeout) are |
144 | distinguishable by the return value of |
144 | distinguishable by the return value of |
145 | <emphasis>waitq_sleep_timeout</emphasis>. The ability to interrupt a |
145 | <emphasis>waitq_sleep_timeout</emphasis>. The ability to interrupt a |
146 | sleeping thread is essential for externally initiated thread termination |
146 | sleeping thread is essential for externally initiated thread termination |
147 | and the ability to wait only for a certain amount of time is used, for |
147 | and the ability to wait only for a certain amount of time is used, for |
148 | instance, to passively delay thread execution by several microseconds or |
148 | instance, to passively delay thread execution by several microseconds or |
149 | even seconds in <emphasis>thread_sleep</emphasis> function. Because all |
149 | even seconds in <emphasis>thread_sleep</emphasis> function. Because all |
150 | other passive kernel synchronization primitives are based on wait |
150 | other passive kernel synchronization primitives are based on wait |
151 | queues, they also have the option of being interrutped and, more |
151 | queues, they also have the option of being interrutped and, more |
152 | importantly, can timeout. All of them also implement the conditional |
152 | importantly, can timeout. All of them also implement the conditional |
153 | operation. Furthemore, this very fundamental interface reaches up to the |
153 | operation. Furthemore, this very fundamental interface reaches up to the |
154 | implementation of futexes - userspace synchronization primitive, which |
154 | implementation of futexes - userspace synchronization primitive, which |
155 | makes it possible for a userspace thread to request synchronization |
155 | makes it possible for a userspace thread to request synchronization |
156 | operation with a timeout or a conditional operation.</para> |
156 | operation with a timeout or a conditional operation.</para> |
157 | 157 | ||
158 | <para>From the description above, it should be apparent, that when a |
158 | <para>From the description above, it should be apparent, that when a |
159 | sleeping thread is woken by <emphasis>waitq_wakeup</emphasis> or when |
159 | sleeping thread is woken by <emphasis>waitq_wakeup</emphasis> or when |
160 | <emphasis>waitq_sleep_timeout</emphasis> succeeds immediatelly, the |
160 | <emphasis>waitq_sleep_timeout</emphasis> succeeds immediatelly, the |
161 | thread can be sure the event has come and the thread need not and should |
161 | thread can be sure the event has come and the thread need not and should |
162 | not verify this fact. This approach is called direct hand-off and is |
162 | not verify this fact. This approach is called direct hand-off and is |
163 | characteristic for all passive HelenOS synchronization primitives with |
163 | characteristic for all passive HelenOS synchronization primitives with |
164 | one exception described below.</para> |
164 | one exception described below.</para> |
165 | </section> |
165 | </section> |
166 | 166 | ||
167 | <section> |
167 | <section> |
168 | <title>Semaphores</title> |
168 | <title>Semaphores</title> |
169 | 169 | ||
170 | <para>The interesting point about wait queues is that the number of |
170 | <para>The interesting point about wait queues is that the number of |
171 | missed wakeups is equal to the number of threads that will not block in |
171 | missed wakeups is equal to the number of threads that will not block in |
172 | <emphasis>watiq_sleep_timeout</emphasis> and would immediately succeed |
172 | <emphasis>watiq_sleep_timeout</emphasis> and would immediately succeed |
173 | instead. On the other hand, semaphores are synchronization primitives |
173 | instead. On the other hand, semaphores are synchronization primitives |
174 | that will let predefined amount of threads in its critical section and |
174 | that will let predefined amount of threads in its critical section and |
175 | block any other threads above this count. However, these two cases are |
175 | block any other threads above this count. However, these two cases are |
176 | exactly the same. Semaphores in HelenOS are therefore implemented as |
176 | exactly the same. Semaphores in HelenOS are therefore implemented as |
177 | wait queues with a single semantic change: their wait queue is |
177 | wait queues with a single semantic change: their wait queue is |
178 | initialized to have so many missed wakeups as is the number of threads |
178 | initialized to have so many missed wakeups as is the number of threads |
179 | that the semphore intends to let into its critical section |
179 | that the semphore intends to let into its critical section |
180 | simultaneously.</para> |
180 | simultaneously.</para> |
181 | 181 | ||
182 | <para>In the semaphore language, the wait queue operation |
182 | <para>In the semaphore language, the wait queue operation |
183 | <emphasis>waitq_sleep_timeout</emphasis> corresponds to |
183 | <emphasis>waitq_sleep_timeout</emphasis> corresponds to |
184 | <emphasis><emphasis>semaphore</emphasis> down</emphasis> operation, |
184 | <emphasis><emphasis>semaphore</emphasis> down</emphasis> operation, |
185 | represented by the function <emphasis>semaphore_down_timeout</emphasis> |
185 | represented by the function <emphasis>semaphore_down_timeout</emphasis> |
186 | and by way of similitude the wait queue operation waitq_wakeup |
186 | and by way of similitude the wait queue operation waitq_wakeup |
187 | corresponds to semaphore <emphasis>up</emphasis> operation, represented |
187 | corresponds to semaphore <emphasis>up</emphasis> operation, represented |
188 | by the function <emphasis>sempafore_up</emphasis>. The conditional down |
188 | by the function <emphasis>sempafore_up</emphasis>. The conditional down |
189 | operation is called <emphasis>semaphore_trydown</emphasis>.</para> |
189 | operation is called <emphasis>semaphore_trydown</emphasis>.</para> |
190 | </section> |
190 | </section> |
191 | 191 | ||
192 | <section> |
192 | <section> |
193 | <title>Mutexes</title> |
193 | <title>Mutexes</title> |
194 | 194 | ||
195 | <para>Mutexes are are sometimes referred to as binary sempahores. That |
195 | <para>Mutexes are are sometimes referred to as binary sempahores. That |
196 | means that mutexes are like semaphores that allow only one thread in its |
196 | means that mutexes are like semaphores that allow only one thread in its |
197 | critical section. Indeed, mutexes in HelenOS are implemented exactly in |
197 | critical section. Indeed, mutexes in HelenOS are implemented exactly in |
198 | this way: they are built atop semaphores. From another point of view, |
198 | this way: they are built atop semaphores. From another point of view, |
199 | they can be viewed as spinlocks without busy waiting. Their semaphore |
199 | they can be viewed as spinlocks without busy waiting. Their semaphore |
200 | heritage provides good basics for both conditional operation and |
200 | heritage provides good basics for both conditional operation and |
201 | operation with timeout. The locking operation is called |
201 | operation with timeout. The locking operation is called |
202 | <emphasis>mutex_lock</emphasis>, the conditional locking operation is |
202 | <emphasis>mutex_lock</emphasis>, the conditional locking operation is |
203 | called <emphasis>mutex_trylock</emphasis> and the unlocking operation is |
203 | called <emphasis>mutex_trylock</emphasis> and the unlocking operation is |
204 | called <emphasis>mutex_unlock</emphasis>.</para> |
204 | called <emphasis>mutex_unlock</emphasis>.</para> |
205 | </section> |
205 | </section> |
206 | 206 | ||
207 | <section> |
207 | <section> |
208 | <title>Reader/writer locks</title> |
208 | <title>Reader/writer locks</title> |
209 | 209 | ||
210 | <para>Reader/writer locks, or rwlocks, are by far the most complicated |
210 | <para>Reader/writer locks, or rwlocks, are by far the most complicated |
211 | synchronization primitive within the kernel. The goal of these locks is |
211 | synchronization primitive within the kernel. The goal of these locks is |
212 | to improve concurrency of applications in which threads need to |
212 | to improve concurrency of applications in which threads need to |
213 | synchronize access to a shared resource and that access can be |
213 | synchronize access to a shared resource and that access can be |
214 | partitioned into a read-only mode and a write mode. Reader/writer locks |
214 | partitioned into a read-only mode and a write mode. Reader/writer locks |
215 | should make it possible for several, possibly many, readers to enter the |
215 | should make it possible for several, possibly many, readers to enter the |
216 | critical section, provided that no writer is currently in the critical |
216 | critical section, provided that no writer is currently in the critical |
217 | section, or to be in the critical section contemporarily. Writers are |
217 | section, or to be in the critical section contemporarily. Writers are |
218 | allowed to enter the critical section only individually, provided that |
218 | allowed to enter the critical section only individually, provided that |
219 | no reader is in the critical section already. Applications in which the |
219 | no reader is in the critical section already. Applications in which the |
220 | majority of operations can be done in the read-only mode can benefit |
220 | majority of operations can be done in the read-only mode can benefit |
221 | from increased concurrency created by reader/writer locks.</para> |
221 | from increased concurrency created by reader/writer locks.</para> |
222 | 222 | ||
223 | <para>During reader/writer locks construction, a decision should be made |
223 | <para>During reader/writer locks construction, a decision should be made |
224 | whether readers will be prefered over writers or whether writers will be |
224 | whether readers will be prefered over writers or whether writers will be |
225 | prefered over readers in cases when the lock is not currently held and |
225 | prefered over readers in cases when the lock is not currently held and |
226 | both a reader and a writer want to gain the lock. Some operating systems |
226 | both a reader and a writer want to gain the lock. Some operating systems |
227 | prefer one group over the other, creating thus a possibility for |
227 | prefer one group over the other, creating thus a possibility for |
228 | starving the unprefered group. In the HelenOS operating system, none of |
228 | starving the unprefered group. In the HelenOS operating system, none of |
229 | the two groups is prefered. The lock is granted on the first come, first |
229 | the two groups is prefered. The lock is granted on the first come, first |
230 | served basis with the additional note that readers are granted the lock |
230 | served basis with the additional note that readers are granted the lock |
231 | in biggest possible batches.</para> |
231 | in biggest possible batches.</para> |
232 | 232 | ||
233 | <para>With this policy and the timeout modes of operation, the direct |
233 | <para>With this policy and the timeout modes of operation, the direct |
234 | hand-off becomes much more complicated. For instance, a writer leaving |
234 | hand-off becomes much more complicated. For instance, a writer leaving |
235 | the critical section must wake up all leading readers in the rwlock's |
235 | the critical section must wake up all leading readers in the rwlock's |
236 | wait queue or one leading writer or no-one if no thread is waiting. |
236 | wait queue or one leading writer or no-one if no thread is waiting. |
237 | Similarily, the last reader leaving the critical section must wakeup the |
237 | Similarily, the last reader leaving the critical section must wakeup the |
238 | sleeping writer, if there are any sleeping threads at all. As another |
238 | sleeping writer, if there are any sleeping threads at all. As another |
239 | example, if a writer at the beginning of the rwlock's wait queue |
239 | example, if a writer at the beginning of the rwlock's wait queue |
240 | timeouts and the lock is held by at least one reader, the timeouting |
240 | timeouts and the lock is held by at least one reader, the timeouting |
241 | writer must first wake up all readers that follow him in the queue prior |
241 | writer must first wake up all readers that follow him in the queue prior |
242 | to signalling the timeout itself and giving up.</para> |
242 | to signalling the timeout itself and giving up.</para> |
243 | 243 | ||
244 | <para>Because of the issues mentioned in the previous paragraph, the |
244 | <para>Because of the issues mentioned in the previous paragraph, the |
245 | reader/writer locks imlpementation needs to walk the rwlock wait queue's |
245 | reader/writer locks imlpementation needs to walk the rwlock wait queue's |
246 | list of sleeping threads directly in order to find out the type of |
246 | list of sleeping threads directly in order to find out the type of |
247 | access that the queueing threads demand. This makes the code difficult |
247 | access that the queueing threads demand. This makes the code difficult |
248 | to understand and dependent on the internal implementation of the wait |
248 | to understand and dependent on the internal implementation of the wait |
249 | queue. Nevertheless, it remains unclear to the authors of HelenOS |
249 | queue. Nevertheless, it remains unclear to the authors of HelenOS |
250 | whether a simpler but equivalently fair solution exists.</para> |
250 | whether a simpler but equivalently fair solution exists.</para> |
251 | 251 | ||
252 | <para>The implementation of rwlocks as it has been already put, makes |
252 | <para>The implementation of rwlocks as it has been already put, makes |
253 | use of one single wait queue for both readers and writers, thus avoiding |
253 | use of one single wait queue for both readers and writers, thus avoiding |
254 | any possibility of starvation. In fact, rwlocks use a mutex rather than |
254 | any possibility of starvation. In fact, rwlocks use a mutex rather than |
255 | a bare wait queue. This mutex is called <emphasis>exclusive</emphasis> |
255 | a bare wait queue. This mutex is called <emphasis>exclusive</emphasis> |
256 | and is used to synchronize writers. The writer's lock operation, |
256 | and is used to synchronize writers. The writer's lock operation, |
257 | <emphasis>rwlock_write_lock_timeout</emphasis>, simply tries to acquire |
257 | <emphasis>rwlock_write_lock_timeout</emphasis>, simply tries to acquire |
258 | the exclusive mutex. If it succeeds, the writer is granted the rwlock. |
258 | the exclusive mutex. If it succeeds, the writer is granted the rwlock. |
259 | However, if the operation fails, the writer must check for potential |
259 | However, if the operation fails (e.g. times out), the writer must check |
260 | readers at the head of the list of sleeping threads associated with the |
260 | for potential readers at the head of the list of sleeping threads |
261 | mutex's wait queue and proceed according to the procedure outlined |
261 | associated with the mutex's wait queue and proceed according to the |
262 | above.</para> |
262 | procedure outlined above.</para> |
263 | 263 | ||
264 | <para>The exclusive mutex plays an important role in reader |
264 | <para>The exclusive mutex plays an important role in reader |
265 | synchronization as well. However, a reader doing the reader's lock |
265 | synchronization as well. However, a reader doing the reader's lock |
266 | operation, <emphasis>rwlock_read_lock_timeout</emphasis>, may bypass |
266 | operation, <emphasis>rwlock_read_lock_timeout</emphasis>, may bypass |
267 | this mutex when it detects that:</para> |
267 | this mutex when it detects that:</para> |
268 | 268 | ||
269 | <orderedlist> |
269 | <orderedlist> |
270 | <listitem> |
270 | <listitem> |
271 | <para>there are other readers in the critical section</para> |
271 | <para>there are other readers in the critical section</para> |
272 | </listitem> |
272 | </listitem> |
273 | 273 | ||
274 | <listitem> |
274 | <listitem> |
275 | <para>there are no sleeping threads waiting for the exclusive |
275 | <para>there are no sleeping threads waiting for the exclusive |
276 | mutex</para> |
276 | mutex</para> |
277 | </listitem> |
277 | </listitem> |
278 | </orderedlist> |
278 | </orderedlist> |
279 | 279 | ||
280 | <para>If both conditions are true, the reader will bypass the mutex, |
280 | <para>If both conditions are true, the reader will bypass the mutex, |
281 | increment the number of readers in the critical section and enter the |
281 | increment the number of readers in the critical section and enter the |
282 | critical section. Note that if there are any sleeping threads at the |
282 | critical section. Note that if there are any sleeping threads at the |
283 | beginning of the wait queue, the first of them must be a writer. If the |
283 | beginning of the wait queue, the first of them must be a writer. If the |
284 | conditions are not fulfilled, the reader normally waits until the |
284 | conditions are not fulfilled, the reader normally waits until the |
285 | exclusive mutex is granted to it.</para> |
285 | exclusive mutex is granted to it.</para> |
286 | </section> |
286 | </section> |
287 | 287 | ||
288 | <section> |
288 | <section> |
289 | <title>Condition variables</title> |
289 | <title>Condition variables</title> |
290 | 290 | ||
291 | <para>Condvars explanation</para> |
291 | <para>Condvars explanation</para> |
292 | </section> |
292 | </section> |
293 | </section> |
293 | </section> |
294 | 294 | ||
295 | <section> |
295 | <section> |
296 | <title>Userspace synchronization</title> |
296 | <title>Userspace synchronization</title> |
297 | 297 | ||
298 | <section> |
298 | <section> |
299 | <title>Futexes</title> |
299 | <title>Futexes</title> |
300 | 300 | ||
301 | <para></para> |
301 | <para></para> |
302 | </section> |
302 | </section> |
303 | </section> |
303 | </section> |
304 | </chapter> |
304 | </chapter> |