Hi,
mariuszp wrote:
Combuster wrote:
mariuszp wrote:
I don't understand how that would solve the problem. The bakery algorithm still requires busy-wait, and I don't see how it's better than a spinlock - if a higher-priority thread preempts a lower-priority thread holding the current "number", it will still deadlock.
Fetch-and-increment implements the bakery ticket system in
one CPU instruction. Once you have your ticket and it's not your turn yet, you can go to sleep. There's no busy-waiting.
and how will the thread be woken up, if nobody knows which threads are waiting?
It doesn't.
Here's a basic ticket spinlock (with the "single fetch-and-increment instruction"):
Code:
acquire:
mov eax,1
lock xadd [dispenser],eax ;eax = my ticket
cmp [serving],eax ;Am I next?
je .done ; yes
.wait:
pause
cmp [serving],eax ;Am I next?
jne .wait ; no
.done:
ret
release:
inc dword [serving]
ret
You're still spinning. The main benefit of this (rather than a normal spinlock) is "fairness" - CPUs get the lock in the order they arrive, and you can't end up with a few unlucky CPUs that take ages to get the lock because other CPUs keep winning.
For a mutex (and not a spinlock), it'd be completely different - for a mutex you'd want a FIFO queue (and not a pair of counters). Essentially; when you try to acquire the mutex and someone else already has the lock, you add yourself to the FIFO queue and block yourself. Then the code to release the lock checks if the FIFO queue is empty, and if it's not it removes the first task from the queue and unblocks it. That is how you implement a "fair" mutex without busy waiting (and without "single fetch-and-increment instruction").
In this case; you need to atomically do "try to acquire the lock, add the task to the queue, then block the task". This is far too much for a single instruction, so you need some kind of spinlock to ensure atomicity. In a similar way; you also need to atomically do "check if queue is empty, then remove first task on queue, then unblock that task", which is also too much for a single instruction, so you need some kind of spinlock to ensure atomicity for that too.
Note that the problem with "fairness" is that it assumes everyone is equal. Tasks are not equal (higher priority tasks are more important than lower priority tasks). Ideally, you don't want a "fair" mutex at all - what you actually want is for the highest priority task to get the mutex while lower priority tasks wait. If and only if 2 tasks have the same priority you want fairness between those tasks, and for all other cases you want intentional unfairness. I don't know if there's a name for this, so I'm going to call it a "biased mutex".
To implement a "biased mutex", instead of having one FIFO queue of waiting tasks you could have a FIFO queue for each task priority. If you have 256 task priorities then you'd have 256 FIFO queues of waiting tasks; and when you release the mutex you find the first non-empty FIFO queue and remove/unblock the first task on that queue. This is more expensive than having a single FIFO queue, but because a mutex involves task switches (which are very expensive) the extra overhead can be relatively negligible.
Cheers,
Brendan