POSIX Message Queue Priority Scheduling

POSIX Message Queue Priority Scheduling

[Jonathan Haws]

Can someone explain to me how message queues handle waking multiple
threads blocked on a single message queue?

My situation is I have multiple writers blocking on a full message
queue, each posting messages with priority equal to the thread
priority.  I want to make sure they wake and post in priority order,
however my application is behaving as if they are waking in FIFO order
(i.e. the order in which they blocked).  Each blocking thread is
scheduled with the SCHED_FIFO policy with a different priority with
system level scope.

I've searched the Internet high and low for something describing how
this should work and all I can find is POSIX man pages describing that
multiple blockers wake in priority order **if Priority Scheduling is
supported**.  Since the kernel scheduler is a priority scheduler I
would think that the threads would wake in priority order and post to
the queue, however that doesn't appear to be the case.  I'm sure I'm
just missing some subtle detail and was hoping the experts here on
this list can help shine some light on what I'm seeing, since its at
the kernel level that these threads are made ready to run.

I have a small test application that I can post here if necessary.  If
this isn't the right place to ask this, by all means let me know and
direct me to the right forum.

Thanks!
Jon

Re: POSIX Message Queue Priority Scheduling

[Jonathan Haws]

You're right about that - but my thread priorities are set such that I
have one thread at priority 25, one at 30, one at 35, etc.  Each of
those ends up blocking on the mq_send at the same time.  When space
becomes available in the queue, I would expect the thread with the
highest priority to wake up and post its message.  The priority of the
message posted simply matched the priority of the thread posting so
that I could tell who posted.

I'm seeing that the thread who blocks first wakes up first, even if
they have a lower priority.  This is not as expected - I expect the
threads to wake in priority order, but that doesn't seem to be the
case.

Would it help if I sent over my test application?

Re: POSIX Message Queue Priority Scheduling

[Jonathan Haws]

> > Can someone explain to me how message queues handle waking multiple
> > threads blocked on a single message queue?
> > 
> > My situation is I have multiple writers blocking on a full message
> > queue, each posting messages with priority equal to the thread
> > priority.  I want to make sure they wake and post in priority
> > order,
> > however my application is behaving as if they are waking in FIFO
> > order
> > (i.e. the order in which they blocked).  Each blocking thread is
> > scheduled with the SCHED_FIFO policy with a different priority with
> > system level scope.
> > 
> > I've searched the Internet high and low for something describing
> > how
> > this should work and all I can find is POSIX man pages describing
> > that
> > multiple blockers wake in priority order **if Priority Scheduling
> > is
> > supported**.  Since the kernel scheduler is a priority scheduler I
> > would think that the threads would wake in priority order and post
> > to
> > the queue, however that doesn't appear to be the case.  I'm sure
> > I'm
> > just missing some subtle detail and was hoping the experts here on
> > this list can help shine some light on what I'm seeing, since its
> > at
> > the kernel level that these threads are made ready to run.
> > 
> > I have a small test application that I can post here if
> > necessary.  If
> > this isn't the right place to ask this, by all means let me know
> > and
> > direct me to the right forum.

Bump...anyone have any thoughts on this?  I haven't been able to find
anything on this.

Re: POSIX Message Queue Priority Scheduling

[Jonathan Haws]

Yeah - I was looking at that code and was having a hard time following
it.  It appears to me that if the queue is full, it goes into this
wq_sleep(), but then never comes back to post - however it has to come
back at some point when it wakes.  The wq_sleep() function calls wq_add
which appears to add in priority order, however it uses static_prio of
the task_struct.

Looking at task_struct, there are four priorities defined --

	int prio, static_prio, normal_prio;
	unsigned int rt_priority;

What I'd like to know is the details of what each of those mean.  It
seems that if the static_prio of each thread is the same, even if the
rt_priority is different, they would wake in FIFO order (since all
static_prios are equal).  Some searching doesn't quite answer the
question fully.  Does the message queue implementation ignore the fact
that some threads are RT threads?  It sure seems to...

I'm going to post this on the linux-kernel list as well.  It seems that
there may be a bug here, or maybe the thread's static_prio isn't
getting set right.


On Thu, 2017-11-09 at 21:15 -0800, kevin dankwardt wrote:
> I believe its in the kernel code ipc/mqueue.c. 
> 
> It looks like a sender of a message gets the receiver.
> 
>       receiver = wq_get_first_waiter(info, RECV);
> 
> -kevin
> 
> On Thu, Nov 9, 2017 at 7:13 PM, Jonathan Haws <Jonathan.Haws@sdl.usu.
> edu> wrote:
> > POSIX - I would expect them to wake in thread priority order, but
> > that
> > isn't what I'm seeing.  Is it possible that while the Linux
> > scheduler
> > is priority-based, the queues do not support priority?
> > 
> > A typical Linux man-page for mq_send doesn't say anything about how
> > multiple blockers wake on mq_send, but this link talks about it:
> > 
> > http://pubs.opengroup.org/onlinepubs/009695399/functions/mq_send.ht
> > ml
> > 
> > It seems to me that Linux does not support "Priority Scheduling"
> > when
> > it comes to POSIX message queues, but rather wakes them in FIFO
> > order.
> > 
> > I'm not even sure what code-base to look at to see. It seems that
> > this
> > is a kernel thing - or are POSIX messages queue completely user-
> > space?
> >  Would I want to look at the source for glibc?
> > 
> > 
> > 
> > On Fri, 2017-11-10 at 11:56 +0900, Kevin Dankwardt wrote:
> > > Jonathan,
> > >
> > > The wakeup order need not be based on scheduler priority. The
> > > queueing mechanism determines the wake order. As I recall SYS V
> > > semaphores wake in FIFO order but POSIX semaphors wake in
> > > process/thread priority order.
> > >
> > > Are you really using POSIX msg queues or sys V.
> > >
> > > -kevin
> > >
> > > >
> > > > On Nov 10, 2017, at 11:43 AM, Jonathan Haws <Jonathan.Haws@sdl.
> > usu.
> > > > edu> wrote:
> > > >
> > > > Kevin,
> > > >
> > > > I understand that - they are different.  What I'm doing is
> > having
> > > > multiple threads block on a full queue and those threads should
> > > > wake up
> > > > in *thread priority order* when the queue becomes available.  I
> > > > have
> > > > those threads post a message with a *message priority* equal to
> > the
> > > > *thread priority*.
> > > >
> > > > When messages come out of the queue, I should see that the
> > threads
> > > > woke
> > > > up in thread priority order.  However, I'm seeing them wake up
> > in
> > > > the
> > > > order that they blocked on the queue which seems incorrect to
> > me
> > > > since
> > > > Linux runs a priority-based scheduler.
> > > >
> > > >
> > > > >
> > > > > On Fri, 2017-11-10 at 11:39 +0900, Kevin Dankwardt wrote:
> > > > > Jonathan,
> > > > >
> > > > > Check the man page to see that priority is not process
> > scheduling
> > > > > priority.
> > > > >
> > > > > -kevin
> > > > >
> > > > > >
> > > > > >
> > > > > > On Nov 10, 2017, at 11:34 AM, Jonathan Haws <Jonathan.Haws@
> > sdl.
> > > > > > usu.
> > > > > > edu> wrote:
> > > > > >
> > > > > >
> > > > > > >
> > > > > > >
> > > > > > > >
> > > > > > > >
> > > > > > > > Can someone explain to me how message queues handle
> > waking
> > > > > > > > multiple
> > > > > > > > threads blocked on a single message queue?
> > > > > > > >
> > > > > > > > My situation is I have multiple writers blocking on a
> > full
> > > > > > > > message
> > > > > > > > queue, each posting messages with priority equal to the
> > > > > > > > thread
> > > > > > > > priority.  I want to make sure they wake and post in
> > > > > > > > priority
> > > > > > > > order,
> > > > > > > > however my application is behaving as if they are
> > waking in
> > > > > > > > FIFO
> > > > > > > > order
> > > > > > > > (i.e. the order in which they blocked).  Each blocking
> > > > > > > > thread
> > > > > > > > is
> > > > > > > > scheduled with the SCHED_FIFO policy with a different
> > > > > > > > priority
> > > > > > > > with
> > > > > > > > system level scope.
> > > > > > > >
> > > > > > > > I've searched the Internet high and low for something
> > > > > > > > describing
> > > > > > > > how
> > > > > > > > this should work and all I can find is POSIX man pages
> > > > > > > > describing
> > > > > > > > that
> > > > > > > > multiple blockers wake in priority order **if Priority
> > > > > > > > Scheduling
> > > > > > > > is
> > > > > > > > supported**.  Since the kernel scheduler is a priority
> > > > > > > > scheduler I
> > > > > > > > would think that the threads would wake in priority
> > order
> > > > > > > > and
> > > > > > > > post
> > > > > > > > to
> > > > > > > > the queue, however that doesn't appear to be the
> > case.  I'm
> > > > > > > > sure
> > > > > > > > I'm
> > > > > > > > just missing some subtle detail and was hoping the
> > experts
> > > > > > > > here
> > > > > > > > on
> > > > > > > > this list can help shine some light on what I'm seeing,
> > > > > > > > since
> > > > > > > > its
> > > > > > > > at
> > > > > > > > the kernel level that these threads are made ready to
> > run.
> > > > > > > >
> > > > > > > > I have a small test application that I can post here if
> > > > > > > > necessary.  If
> > > > > > > > this isn't the right place to ask this, by all means
> > let me
> > > > > > > > know
> > > > > > > > and
> > > > > > > > direct me to the right forum.
> > > > > > Bump...anyone have any thoughts on this?  I haven't been
> > able
> > > > > > to
> > > > > > find
> > > > > > anything on this.
> > 
> 
> 

Re: POSIX Message Queue Priority Scheduling

[Jonathan Haws]

> Yeah - I was looking at that code and was having a hard time
> following
> it.  It appears to me that if the queue is full, it goes into this
> wq_sleep(), but then never comes back to post - however it has to
> come
> back at some point when it wakes.  The wq_sleep() function calls
> wq_add
> which appears to add in priority order, however it uses static_prio
> of
> the task_struct.
> 
> Looking at task_struct, there are four priorities defined --
> 
> 	int prio, static_prio, normal_prio;
> 	unsigned int rt_priority;
> 
> What I'd like to know is the details of what each of those mean.  It
> seems that if the static_prio of each thread is the same, even if the
> rt_priority is different, they would wake in FIFO order (since all
> static_prios are equal).  Some searching doesn't quite answer the
> question fully.  Does the message queue implementation ignore the
> fact
> that some threads are RT threads?  It sure seems to...

Did a lot more digging and found the following, which I'll post here
for reference.

prio - holds the actual priority in use (after priority boosting/RT
considerations/etc.) of the process or thread

static_prio - holds the static priority (based on niceness) of the
process or thread

normal_prio - holds the dynamic priority of the process or thread.  In
the testing I did this always equaled prio, but this isn't necessarily
always the case

rt_priority - holds the user-specified RT priority of the thread and
plays into the prio value if using a RT scheduler (such as SCHED_FIFO
or SCHED_RR).


I made a simple change to the ipc/mqueue.c:wq_add() routine.  I changed
static_prio to prio in the if statement comparing priorities.  This was
all it took.

I'm working on getting that change into mainline, but hopefully this
thread on this list will be of help to someone else.

Thanks all!

POSIX Message Queue Priority Scheduling

[Jonathan Haws]

Can someone explain to me how message queues handle waking multiple
threads blocked on a single message queue?

My situation is I have multiple writers blocking on a full message
queue, each posting messages with priority equal to the thread
priority.  I want to make sure they wake and post in priority order,
however my application is behaving as if they are waking in FIFO order
(i.e. the order in which they blocked).  Each blocking thread is
scheduled with the SCHED_FIFO policy with a different priority with
system level scope.

I've searched the Internet high and low for something describing how
this should work and all I can find is POSIX man pages describing that
multiple blockers wake in priority order **if Priority Scheduling is
supported**.  Since the kernel scheduler is a priority scheduler I
would think that the threads would wake in priority order and post to
the queue, however that doesn't appear to be the case.  I'm sure I'm
just missing some subtle detail and was hoping the experts here on
this list can help shine some light on what I'm seeing, since its at
the kernel level that these threads are made ready to run.

I have a small test application that I can post here if necessary.  If
this isn't the right place to ask this, by all means let me know and
direct me to the right forum.

Thanks!
Jon

POSIX Message Queue Priority Scheduling

[Jonathan Haws]

Can someone explain to me how message queues handle waking multiple
threads blocked on a single message queue?

My situation is I have multiple writers blocking on a full message
queue, each posting messages with priority equal to the thread
priority.  I want to make sure they wake and post in priority order,
however my application is behaving as if they are waking in FIFO order
(i.e. the order in which they blocked).  Each blocking thread is
scheduled with the SCHED_FIFO policy with a different priority with
system level scope.

I've searched the Internet high and low for something describing how
this should work and all I can find is POSIX man pages describing that
multiple blockers wake in priority order **if Priority Scheduling is
supported**.  Since the kernel scheduler is a priority scheduler I
would think that the threads would wake in priority order and post to
the queue, however that doesn't appear to be the case.  I'm sure I'm
just missing some subtle detail and was hoping the experts here on
this list can help shine some light on what I'm seeing, since its at
the kernel level that these threads are made ready to run.

I have a small test application that I can post here if necessary.  If
this isn't the right place to ask this, by all means let me know and
direct me to the right forum.

Thanks!
Jon

POSIX Message Queue Priority Scheduling

[Jonathan Haws]

Can someone explain to me how message queues handle waking multiple
threads blocked on a single message queue?

My situation is I have multiple writers blocking on a full message
queue, each posting messages with priority equal to the thread
priority.  I want to make sure they wake and post in priority order,
however my application is behaving as if they are waking in FIFO order
(i.e. the order in which they blocked).  Each blocking thread is
scheduled with the SCHED_FIFO policy with a different priority with
system level scope.

I've searched the Internet high and low for something describing how
this should work and all I can find is POSIX man pages describing that
multiple blockers wake in priority order **if Priority Scheduling is
supported**.  Since the kernel scheduler is a priority scheduler I
would think that the threads would wake in priority order and post to
the queue, however that doesn't appear to be the case.  I'm sure I'm
just missing some subtle detail and was hoping the experts here on
this list can help shine some light on what I'm seeing, since its at
the kernel level that these threads are made ready to run.

I have a small test application that I can post here if necessary.  If
this isn't the right place to ask this, by all means let me know and
direct me to the right forum.

Thanks!
Jon

-- 
Jonathan R. Haws
hawsjr@gmail.com