Question on Linux and SCHED_FIFO scheduling for POSIX threads

Question on Linux and SCHED_FIFO scheduling for POSIX threads

[Eirik Nordbrøden]

Hello

Can anybody clarify how SCHED_FIFO scheduling and thread priorities works on Linux? We are novices in this field in the Linux environment and needs help to understand how it works. To verify the behaviour we made up a small test program consisting of four threads and a mutex. We have run the program on both the 2.6.5 and 2.6.7 kernels with same behaviour.

Program:

T-MAIN: scheduling policy=SCHED_FIFO, priority=1
T-LP:   scheduling policy=SCHED_FIFO, priority=10
T-MP:   scheduling policy=SCHED_FIFO, priority=20
T-HP:   scheduling policy=SCHED_FIFO, priority=30

The program runs like this:

T-MAIN locks mutex => T-MAIN runs.
T-MAIN creates T-LP => T-LP runs.
T-LP waits for mutex => T-MAIN runs.
T-MAIN creates T-MP => T-MP runs.
T-MP waits for mutex => T-MAIN runs.
T-MAIN creates T-HP => T-HP runs.
T-HP waits for mutex => T-MAIN runs.
T-MAIN waits 3 seconds and unlocks mutex => T-LP runs.
T-LP waits 3 seconds and unlocks mutex => T-MP runs.
T-MP waits 3 seconds and unlocks mutex => T-HP runs.
:
:

For us this is unexpected behaviour. We would expect that the thread with the highest priority would be scheduled to run when a number of threads is waiting for a mutex and the mutex is unlocked. Can anyone clarify this? Have we missed something?

PS We have also tested this with POSIX and System V semaphores in stead of the mutex with same behaviour.

Eirik Nordbrøden 
moreCom A/S  http://www.moreCom.no/
 

Re: Question on Linux and SCHED_FIFO scheduling for POSIX threads

[Jakub Jelinek]

On Fri, Jul 16, 2004 at 11:11:54AM +0200, Eirik Nordbr?den wrote:
> Can anybody clarify how SCHED_FIFO scheduling and thread priorities works
> on Linux? We are novices in this field in the Linux environment and needs
> help to understand how it works. To verify the behaviour we made up a
> small test program consisting of four threads and a mutex. We have run the
> program on both the 2.6.5 and 2.6.7 kernels with same behaviour.
> 
> Program:
> 
> T-MAIN: scheduling policy=SCHED_FIFO, priority=1
> T-LP:   scheduling policy=SCHED_FIFO, priority=10
> T-MP:   scheduling policy=SCHED_FIFO, priority=20
> T-HP:   scheduling policy=SCHED_FIFO, priority=30
> 
> The program runs like this:
> 
> T-MAIN locks mutex => T-MAIN runs.
> T-MAIN creates T-LP => T-LP runs.
> T-LP waits for mutex => T-MAIN runs.
> T-MAIN creates T-MP => T-MP runs.
> T-MP waits for mutex => T-MAIN runs.
> T-MAIN creates T-HP => T-HP runs.
> T-HP waits for mutex => T-MAIN runs.
> T-MAIN waits 3 seconds and unlocks mutex => T-LP runs.
> T-LP waits 3 seconds and unlocks mutex => T-MP runs.
> T-MP waits 3 seconds and unlocks mutex => T-HP runs.
> :
> :
> 
> For us this is unexpected behaviour. We would expect that the thread with
> the highest priority would be scheduled to run when a number of threads is
> waiting for a mutex and the mutex is unlocked. Can anyone clarify this?
> Have we missed something?

NPTL locking is implemented on top of futex(2).
futex(2) queues are ATM FIFOs, not priority based queues.
Check http://developer.osdl.org/dev/robustmutexes/
for some patches which introduce priority based queues for futexes (well,
AFAIK they introduce new syscalls and call the primitive fusyn instead).

	Jakub