OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 10:14 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 19 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 4:03 am 
Offline
Member
Member

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 587
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?


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 4:07 am 
Offline
Member
Member

Joined: Tue Mar 04, 2014 5:27 am
Posts: 1108
https://en.wikipedia.org/wiki/Priority_inversion ?


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 4:24 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
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)

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 4:33 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
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

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 6:11 am 
Offline
Member
Member

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 587
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.


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 8:36 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
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

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 11:00 am 
Offline
Member
Member

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 587
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?


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 12:12 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
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

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 3:33 pm 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
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.

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 4:30 pm 
Offline
Member
Member

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 587
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?


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 10:26 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
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

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Tue Jun 07, 2016 11:22 pm 
Offline
Member
Member

Joined: Sat Nov 07, 2015 3:12 pm
Posts: 145
Why do you use assembly while you could use atomic functions ( __sync_fetch_and_add and the like )? Are those bad ?


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Wed Jun 08, 2016 6:11 am 
Offline
Member
Member

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 587
I understand that, Brendan. However, Combuster seems to have said that ticket locks don't require busy-waiting.


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Wed Jun 08, 2016 11:09 am 
Offline
Member
Member

Joined: Sat Nov 07, 2015 3:12 pm
Posts: 145
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


Top
 Profile  
 
 Post subject: Re: Thread safety with priorities
PostPosted: Wed Jun 08, 2016 11:50 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
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:
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.

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 19 posts ]  Go to page 1, 2  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 26 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group