Thread scheduling in unix

Question

In RR scheduling policy what will happen if a low priority thread locks a mutex and is removed by the scheduler because another high priority thread is waiting?

Will it also releases the lock held by low priority thread?

For example consider 3 threads running in a process with priorities 10,20 and 30 in RR scheduling policy.

Now at a given point of time low priority thread 1 locks mutex and is still doing execution mean while the high priority thread pops in and also waits on mutex held by thread 1. Now thread 2 comes in to picture which also needs the same mutex locked by thread 1.

As far as I know as per scheduling algorithm the threads sleeping or waiting for mutex,semaphore etc are removed and the other ones, even having low priority are allowed to execute. Is this correct? If so, in the above example ultimately high priority threads wait for the completion of low priority thread which doesn't make any sense. Is this how the system works if at all threads are designed like I said above?

or the thread priority should be set in such a way that high priority one's will not depend on low priority one's mutexe's ?

Also can anyone please explain me how scheduling works at process level? How do we set priority for a process?

Answer 1

Typically, scheduling and locks are unrelated in any other aspect than a "waiting thread is not scheduled until it's finished waiting". It would be rather daft to have a MUTEX that "stops other thread from accessing my data" but it only works if the other thread has the same or lower priority than the current thread.

The phenomena of "a low priority holds a lock that a high priority thread 'needs'" is called priority inversion, and it's a well known scenario in computer theory.

There are some schemes that "temporarily increase priority of a lock-holding thread until it releases the lock to the highest priority of the waiting threads" (or the priority of the first waiting thread if it's higher than the current thread, or some other variation on that theme). This is done to combat priority inversion - but it has other drawbacks too, so it's not implemented in all OS's/schedulers (after all, it affects other threads than the one that is waiting too).

Edit:

The point of a mutex (or other similar locks) is that it prevents two threads from accessing the same resources at once. For example, say we want to update five different variables with some pretty lengthy processing (complicated math, fetching data from a serial port or a network drive, or some such), but if we only do two of the variables, some other process using these would get an invalid result, then we clearly can't "let go" of the lock.

The high priority thread simply has to wait for all five variables to be updated and the low priority lock.

There is no simple workaround that the application can do to "fix" this problem - don't hold the locks more than necessary of course [and it may be that we can actually fix the problem described above, by performing the lengthy processing OUTSIDE of the lock, and only do the final "store it in the 5 variables" with the lock on. This would reduce the potential time that the high priority thread has to wait, but if the system is really busy, it won't really fix the problem.

There are whole PhD thesis written on this subject, and I'm not a specialist on "how to write a scheduler" - I have a fair idea how one works, just like I know how the engine in my car works - but if someone gave me a bunch of suitable basic shapes of steel and aluminium, and the required tools/workspace and told me to build an engine, I doubt it would work great...Same with a scheduler - I know what the parts are called, but not how to build one.

Answer 2

The high priority thread is not going to have the lock for which it is requesting until the low priority thread will unlock it.

To avoid this we can use semaphore where any other thread can initiate to unlock but in mutex it is not possible.

Answer 3

If a high priority thread needs to wait on a low priority thread (mutex semaphore etc), the low priority thread is temporarily elevated to the same priority as the high priority thread.