OSDev.org

Posted: **Tue Jun 07, 2016 4:03 am**

We're thinking of designing a new O(1) scheduler for Glidix, with support for priorities. I have noticed a problem whixh i am unsure how to solve.

When acquiring a mutex, a higher-priority task wilk wait to allow a lower-priority task to release the mutex if it holds it; because the highr-priority task will go to sleep until the mutex is released.

However, mutexes are protected by spinlocks. If a lower-priority task is holding the spinlock, and a higher-priority task attempts to acquire it, there will be a deadlock. The high priority task will never allow the low priority task to run, and so the spinlock will never be released, and hence never acquired.

How would I go about solving this problem? How can i safely implement a mutex when different priority tasks contend on it?

Posted: **Tue Jun 07, 2016 4:07 am**

https://en.wikipedia.org/wiki/Priority_inversion ?

Posted: **Tue Jun 07, 2016 4:24 am**

Spinlocks are a Bad Idea(tm), for reasons you just discovered.

Implement your mutexes with your CPU's concurrency primitives (i.e. LOCKed BTS/CMPXCHG/XADD/XCHG)

Posted: **Tue Jun 07, 2016 4:33 am**

Hi,

mariuszp wrote:When acquiring a mutex, a higher-priority task wilk wait to allow a lower-priority task to release the mutex if it holds it; because the highr-priority task will go to sleep until the mutex is released.

However, mutexes are protected by spinlocks. If a lower-priority task is holding the spinlock, and a higher-priority task attempts to acquire it, there will be a deadlock. The high priority task will never allow the low priority task to run, and so the spinlock will never be released, and hence never acquired.

How would I go about solving this problem? How can i safely implement a mutex when different priority tasks contend on it?

The basic idea is that you atomically either acquire the mutex or put the task to sleep (to be woken when the mutex is released). That "atomically" part is the only thing you use the spinlock for. Essentially; the kernel disables task switches (and/or maybe interrupts) and acquires the spinlock; then does the "either acquire the mutex or put task to sleep" part; then releases the spinlock and enables task switches again.

Cheers,

Brendan

Posted: **Tue Jun 07, 2016 6:11 am**

Combuster wrote:Spinlocks are a Bad Idea(tm), for reasons you just discovered.

Implement your mutexes with your CPU's concurrency primitives (i.e. LOCKed BTS/CMPXCHG/XADD/XCHG)

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.

Brendan wrote: The basic idea is that you atomically either acquire the mutex or put the task to sleep (to be woken when the mutex is released). That "atomically" part is the only thing you use the spinlock for. Essentially; the kernel disables task switches (and/or maybe interrupts) and acquires the spinlock; then does the "either acquire the mutex or put task to sleep" part; then releases the spinlock and enables task switches again.

So all I'd have to do is disable interrupts before acquiring the spinlock, and then enabling them once it's releaseed? I don't see a reason to disable task switching on other CPUs; so disabling interrupts on the CPU acquiring the lock should be enough.

Posted: **Tue Jun 07, 2016 8:36 am**

Hi,

mariuszp wrote:
Brendan wrote:The basic idea is that you atomically either acquire the mutex or put the task to sleep (to be woken when the mutex is released). That "atomically" part is the only thing you use the spinlock for. Essentially; the kernel disables task switches (and/or maybe interrupts) and acquires the spinlock; then does the "either acquire the mutex or put task to sleep" part; then releases the spinlock and enables task switches again.
So all I'd have to do is disable interrupts before acquiring the spinlock, and then enabling them once it's releaseed? I don't see a reason to disable task switching on other CPUs; so disabling interrupts on the CPU acquiring the lock should be enough.

It can be enough to disable task switches on the current CPU only, without disabling IRQs (as long as IRQ handlers don't do anything that uses the mutex). If you do disable IRQs then you don't need to disable task switching on the current CPU.

Cheers,

Brendan

Posted: **Tue Jun 07, 2016 11:00 am**

OK, I will partially redesign my interrupt-handling mechanisms as part of the scheduler redesign, to e.g. preempt an interrupted task if a higher-priority task is woken up to handle an IRQ, etc. and I will ensure that it is possible to safely disable task switches without disabling IRQs and so on.

Also, after researching the baker's algorithm that Combuster mentioned, I decided to replace all spinlocks (if possible) with "ticket lines" implementing that algorithm. This algorithm is significantly more fair and I can optimise CPU use by yield()ing whenever the lock cannot yet be acuired, minizing the busy-wait.

Thank you for all the feedback

EDIT: Also, instead of blocking all task switches, would it be enough to simply block higher-priority threads temporarily?

Posted: **Tue Jun 07, 2016 12:12 pm**

Hi,

mariuszp wrote:EDIT: Also, instead of blocking all task switches, would it be enough to simply block higher-priority threads temporarily?

If it's impossible for a lower priority task to preempt the currently running task; then there's no difference between blocking all task switches and only blocking task switches that aren't already blocked.

If it's possible for a lower priority task to preempt the currently running task; then it's not safe. E.g. you'll acquire the spinlock, add the task to the mutex, and then do a task switch before you can block the task; then some other task can release the mutex and try to unblock a task that hasn't blocked yet.

Note that it's probably more accurate to say "postpone task switches". What I do is have a counter (per CPU) and postpone task switches by increasing the counter. If any other code (e.g. an IRQ handler) wants to do a task switch it checks this counter - if the counter is zero the task switch happens, and if the counter is non-zero it sets a "task switch/es were postponed" flag instead. When you want to enable task switches again you decrement the counter and if it becomes zero you check the "task switch/es were postponed" flag, and if that flag is set you do the task switch that something wanted to do earlier. That way a task switch happens as soon as possible (and nothing happens if no task switches were postponed).

Cheers,

Brendan

Posted: **Tue Jun 07, 2016 3:33 pm**

mariuszp wrote:
Combuster wrote:Spinlocks are a Bad Idea(tm), for reasons you just discovered.

Implement your mutexes with your CPU's concurrency primitives (i.e. LOCKed BTS/CMPXCHG/XADD/XCHG)
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.

Posted: **Tue Jun 07, 2016 4:30 pm**

Combuster wrote:
mariuszp wrote:
Combuster wrote:Spinlocks are a Bad Idea(tm), for reasons you just discovered.

Implement your mutexes with your CPU's concurrency primitives (i.e. LOCKed BTS/CMPXCHG/XADD/XCHG)
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?

Posted: **Tue Jun 07, 2016 10:26 pm**

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

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

Posted: **Tue Jun 07, 2016 11:22 pm**

Why do you use assembly while you could use atomic functions ( __sync_fetch_and_add and the like )? Are those bad ?

Posted: **Wed Jun 08, 2016 6:11 am**

I understand that, Brendan. However, Combuster seems to have said that ticket locks don't require busy-waiting.

Posted: **Wed Jun 08, 2016 11:09 am**

Don't schedule while a spin lock is held. Those locks are *meant* to be quick.
Count the number of spin locks held, when it becomes non null, disable the scheduler, and re enable it when it becomes zero .
That way a higher priority task will never preempt a lower task on a spin lock.

As for the mutex , the only thing you need to protect by a spin lock is:
* setting a " should I sleep " flag
*being registered as the new holder of mutex/ in a to-be-waked task list

Posted: **Wed Jun 08, 2016 11:50 am**

Tickets with target threads is as simple as dropping in circular_buffer[ticket_number % buffer_size] = my_thread_id before checking if you have the lock or you have to sleep instead. The exiting thread can remove its thread id slot and wake the next thread if there happens to be one registered.

Just to follow up on that, sleeping-waking code is a caveat. Something as simple as:

Code: Select all

if (needs_to_sleep)
{
    sleep();
}
(...)
    wake_thread_if_sleeping();

Is a race condition, if the wake is performed between the if and the sleep. Instead you can modify wake to prevent the next sleep() call from occurring if the thread is running, or you can do something else/more complicated. It's actually a more fundamental primitive than setting up mutexes.

OSDev.org

Thread safety with priorities

Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities

Re: Thread safety with priorities