OSDev.org

Hello,

When stress testing my OS (200 system threads each writing a 4mb file in blocks of 16 bytes) I have come up with an interesting issue.

Disregard the stress test and consider the following theoretical example: lots of base priority threads doing the same kind of work that every once in a while requires a mutex to be locked in order to protect a certain function (for example locking the heap mutex in order to allocate and free memory while the cache is being flushed or expanded) and a high priority thread that every once in a while needs to lock the same mutex in order to use that function.

If this high priority thread tries to lock the mutex while a fair amount of base priority threads are already held waiting for it it will not be released until all the queued threads unlock it, thus, this scenario completly ignores the thread's priority!

Although I have a specific example where this is happening, this problem is generic and can be reproduced in many ways so I tried to be general as much as I can.

While a lot of threads are trying to lock the same mutex there is no reference to the actual priority of these threads inside the mutex, I was thinking of implementing a special priority mutex where each thread that needs to wait for a mutex will be inserted to the mutex' thread waiting list position according to its priority, ie, high priority threads will own the mutex as soon as possible even if there are many threads that are already waiting on that mutex before them.

I later decided not to implement such a thing, because that will break dynamic priority boosters - each time a thread's priority changes its position in all the mutexes will have to be changed which is suboptimial.

So I decided to raise the topic, considering the theoretical problem how do you suggest to solve such a thing - where a lot of mixed priority threads needs to lock the same mutex and making sure the high priority threads will not wait too much for the lesser priority threads.

Thanks.

Daniel.

doesn't a thread normally block on a taken mutex? (assuming i understand correctly -- haven't done it yet myself) so why not dump this on your scheduler? it already has logic for handling thread priority,

assuming the mutex priority will be closely related to thread priority, simply allow your scheduler to select the highest priority thread blocking on that particular mutex, and switch to it (the thread cannot take a mutex unless it is running anyway right?)

as for dynamic-priority, you already have solved this in some way for your scheduler, right? are you using a single list (in order of priority) or multiple lists (one for each priority)

if your using a single list, it will need to be adjusted everytime you change priority anyway, correct? (its not likely to be that a very large number of threads are blocking on the same mutex -- if so then they are prob holding it to long!)

if your using multiple list, then you could prob use the same technique here as well

You'd have to ask DennisCGc, since he borrowed my main OSDev books, about the specifics, but I'm certain I've seen the problem pass by in theoretical review. Your problem doesn't capture the deeper lying consequence of such priority stuff. It can lead to something called priority inversion, which can be found on the internet in various places as well as on Google.

It comes down to mutexes interacting such that higher priority threads don't get to run because two lower priority threads together decide that it can't.

The problem you delineated can be handled with priorities on the given mutexes together with a priority queue for efficient insertion and removal of an ordered set of items (threads in this case). IIRC it's the most optimal way to do priority scheduling.

Hi,

Well then what you are both suggesting is exactly what I was considering and wrote about: "priority mutexes" as in a queue sorted by threads priority.

(funny that both of you replied and suggested the same idea that I mentioned in the original post - "priority mutexes" while completly disregarding the fact that I have already thought and wrote about it and am looking for something more elaborate).

Candy, I remember too seeing a theoretical paragraph about high priority threads unable to run because low priority threads, I believe it was in the book "Modern operating systems".

Do you have any cool insight on a theoretical solution that will try to maintain fairness?

Thank you very much for your replies!

Daniel.

My OS provides both priority and fifo-based mutexes for similar purposes. Among other things, actually (message queues, semaphores, etc). I think it's, generally, a good idea to provide an option.

Also, for these reasons, I generally try to ensure mutexes (mutexen?) will be used only among certain privelege types (ie, only OS, or only apps). If you have a microkernel setup (and therefore, possibly, only one server doing the actual hardware interaction for each device) this isn't too difficult to ensure (tasks get buffered in a message queue and executed synchronously).

--Jeff

Trashey wrote: Do you have any cool insight on a theoretical solution that will try to maintain fairness?

Well...

The condition is a problem given the implicit requirements. To break the condition, you invalidate one of the requirements.

One of the requirements is that a thread must lock a mutex, and be interrupted before giving it back. There are two ways to prevent this, one is by making the period very short and the other is by making threads with a mutex uninterruptible. The first can't be enforced and if you enforce the second, a single thread can lock up the entire cpu.

The way to do this, in my opinion, is the middle road. Make mutexes uninterruptible for a short while. That way, you can give an upper limit to the amount of cycles an application can take for a mutexed section, and you can ensure that the given priority inversion should not occur when people follow the programming standard.

I was considering doing this using a low overhead "system call" that sets a bit at a given location in user space that's thread specific. Upon being interrupted in the kernel the OS will check the location, and if it's set it'll mark a userprocess specific bit in kernel space. The mutex-free function checks whether both are set to 1 (the user space and kernel space bits) and if so, it calls the kernel to notify it of mutex freeing (need to find some way to nest this stuff).

This fixes the interruption problem. Also, the kernel can determine whether it was the first or a later time that it ended up interrupting that process/thread. If it's the first time, it marks a bit and returns. If it's the second, it still interrupts it.