<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html lang="en" style="--code-editor-font: var(--default-mono-font, "GitLab Mono"), JetBrains Mono, Menlo, DejaVu Sans Mono, Liberation Mono, Consolas, Ubuntu Mono, Courier New, andale mono, lucida console, monospace;">
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
<title>
GitLab
</title>
<style data-premailer="ignore" type="text/css">
a { color: #1068bf; }
</style>
<style>img {
max-width: 100%; height: auto;
}
body {
font-size: .875rem;
}
body {
-webkit-text-shadow: rgba(255,255,255,.01) 0 0 1px;
}
body {
font-family: "GitLab Sans",-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,"Noto Sans",Ubuntu,Cantarell,"Helvetica Neue",sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol","Noto Color Emoji"; font-size: inherit;
}
</style>
</head>
<body style="font-size: inherit; -webkit-text-shadow: rgba(255,255,255,.01) 0 0 1px; font-family: "GitLab Sans",-apple-system,BlinkMacSystemFont,"Segoe UI",Roboto,"Noto Sans",Ubuntu,Cantarell,"Helvetica Neue",sans-serif,"Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol","Noto Color Emoji";">
<div class="content">
<p style="color: #777777;">
<a href="https://gitlab.rtems.org/aptacc2421">Xinhong Hu</a>
commented on a
<a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/issues/3791#note_142957">discussion</a>:
</p>
<div class="md" style="position: relative; z-index: 1; color: #3a383f; word-wrap: break-word;">
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">Hi <a href="https://gitlab.rtems.org/gedare" title="Gedare Bloom" class="gfm gfm-project_member js-user-link" data-user="8" data-original="@gedare" data-container="body" data-placement="top" data-reference-type="user" style="color: #284779; background-color: #cbe2f9; border-radius: .25rem; margin-top: 0; padding: 0 2px;">@gedare</a> ,</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">Thank you for your guidance. I've investigated how FreeBSD and Linux implement POSIX message queues regarding thread wake‑up order, and here's what I found:</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial"><strong style="font-weight: 600; margin-top: 0;">FreeBSD：</strong></p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">FreeBSD <strong style="font-weight: 600; margin-top: 0;">explicitly follows the POSIX specification</strong>. Its <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">mq_receive</code> man page states:</p>
<blockquote dir="auto" style="font-size: inherit; color: #626168; padding-top: 0.5rem; padding-bottom: 0.5rem; padding-left: 1rem; border-left-style: solid; margin: 0.5rem 0; border-color: #bfbfc3; border-width: 0 0 0 4px;" align="initial">
<p style="color: inherit; line-height: 1.5; margin: 0 0 1rem;">"If more than one thread is waiting to receive a message when a message arrives at an empty queue and the Priority Scheduling option is supported, then the <strong style="font-weight: 600; margin-top: 0;">thread of highest priority that has been waiting the longest</strong> will be selected to receive the message."</p>
<p style="color: inherit; line-height: 1.5; margin: 0;">(Source: <a href="https://man.freebsd.org/cgi/man.cgi?query=mq_receive&sektion=2&manpath=FreeBSD+16.0-CURRENT" rel="nofollow noreferrer noopener" target="_blank" style="margin-top: 0;">FreeBSD 16.0-CURRENT man page</a>)</p>
</blockquote>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">Internally, FreeBSD <strong style="font-weight: 600; margin-top: 0;">does not maintain an explicit waiting thread queue</strong>; instead, it uses a simple counter (<code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">mq_receivers</code>) and relies on the kernel scheduler to select the appropriate thread when a message arrives. This design naturally yields the POSIX-mandated behavior.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial"><strong style="font-weight: 600; margin-top: 0;">Linux:</strong></p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial"><a href="https://github.com/torvalds/linux/blob/master/ipc/mqueue.c" rel="nofollow noreferrer noopener" target="_blank" style="margin-top: 0;">Linux’s implementation</a> is more complex and <strong style="font-weight: 600;">does not fully comply with the POSIX requirement</strong>.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">The waiting queue (<code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; margin-top: 0; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">struct ext_wait_queue</code>) is a <strong style="font-weight: 600;">linked list, but threads are inserted in priority order</strong> (higher priority first). The insertion code (<code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">wq_add</code> in <code style="font-size: 90%; color: #18171d; word-wrap: break-word; background-color: #ececef; border-radius: .25rem; font-weight: inherit; overflow-wrap: break-word; white-space: break-spaces; font-family: "GitLab Mono", "JetBrains Mono", "Menlo", "DejaVu Sans Mono", "Liberation Mono", "Consolas", "Ubuntu Mono", "Courier New", "andale mono", "lucida console", monospace; font-variant-ligatures: none; word-break: keep-all; padding: 0.125rem 0.25rem;">ipc/mqueue.c</code>) traverses the list and places a new thread <strong style="font-weight: 600;">before the first thread with lower or equal priority</strong>.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">As a result, the list is sorted by descending priority, so when a message arrives, the <strong style="font-weight: 600; margin-top: 0;">highest-priority thread</strong> (the first in the list) is woken.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">However, <strong style="font-weight: 600; margin-top: 0;">within the same priority level, the insertion order is LIFO</strong> (later waiters are placed ahead of earlier ones), so it does <strong style="font-weight: 600;">not</strong> guarantee that the longest-waiting thread is chosen.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial"><br style="margin-top: 0;">
This suggests that both FreeBSD and Linux prioritize threads by priority (Linux even within same priority uses LIFO rather than FIFO), aligning with the POSIX requirement to wake the highest priority thread. Linux's LIFO behavior for equal priorities may be a performance optimization but deviates from “longest waiting” part.</p>
<p dir="auto" style="color: #3a383f; margin: 0 0 1rem;" align="initial">Given these examples, I think RTEMS's current FIFO behavior for waiting threads is a deviation, and our proposal to add a priority-based discipline (either globally or per‑queue via `mq_attr`) would bring us closer to what other systems implement and what POSIX intends.</p>
<p dir="auto" style="color: #3a383f; margin: 0;" align="initial">I'd appreciate any further thoughts on this.</p>
</div>
</div>
<div class="footer" style="margin-top: 10px;">
<p style="font-size: small; color: #626168;">
—
<br>
<a href="https://gitlab.rtems.org/rtems/rtos/rtems/-/issues/3791#note_142957">View it on GitLab</a>.
<br>
You're receiving this email because of your account on <a target="_blank" rel="noopener noreferrer" href="https://gitlab.rtems.org">gitlab.rtems.org</a>. <a href="https://gitlab.rtems.org/-/sent_notifications/2-45j2699xc64t1pgb0omffanot/unsubscribe" target="_blank" rel="noopener noreferrer">Unsubscribe</a> from this thread · <a href="https://gitlab.rtems.org/-/profile/notifications" target="_blank" rel="noopener noreferrer" class="mng-notif-link">Manage all notifications</a> · <a href="https://gitlab.rtems.org/help" target="_blank" rel="noopener noreferrer" class="help-link">Help</a>
<span style="color: transparent; font-size: 0; display: none; overflow: hidden; opacity: 0; width: 0; height: 0; max-width: 0; max-height: 0;">
Notification message regarding https://gitlab.rtems.org/rtems/rtos/rtems/-/issues/3791#note_142957 at 1771433623
</span>
<script type="application/ld+json">{"@context":"http://schema.org","@type":"EmailMessage","action":{"@type":"ViewAction","name":"View Issue","url":"https://gitlab.rtems.org/rtems/rtos/rtems/-/issues/3791#note_142957"}}</script>
</p>
</div>
</body>
</html>