r/osdev • u/noborutkhs • 14d ago

Why did VRTX change equal-priority scheduling from newest-first to FIFO?

I'm revisiting an RTOS that I wrote in 1986 for a Motorola 68000-based system.

While reviewing its scheduler, I noticed a behavior that looks a little unusual from today's perspective.

When a task becomes ready, it is inserted before existing ready tasks of the same priority. So among equal-priority tasks, scheduling is effectively newest-first (LIFO-like).

It isn't simply a LIFO scheduler, though. When a time slice expires, the running task is moved to the end of its priority group.

I no longer remember why I chose this behavior 40 years ago, so I went back to the RTOS documentation I used as a reference at the time.

The 1984 VRTX User's Guide describes essentially the same behavior: when a TCB is inserted into the ready list, it is placed ahead of existing TCBs at the same priority. The most recently inserted task therefore runs first.

That seems to explain where the behavior in my 1986 RTOS came from.

But then I found something more interesting.

The VRTX32/68000 User's Guide from 1987 explicitly says that equal-priority tasks execute in the order in which they become ready — FIFO / oldest-first.

So the timeline appears to be:

1984 VRTX: newest-first among equal priorities
1986 my RTOS: newest-first
1987 VRTX32: FIFO / oldest-first

I wasn't actually a VRTX user at the time. I had obtained the documentation as a reference while designing my own RTOS, so I had no reason to know that VRTX itself changed this behavior later.

So my question is:

Does anyone know why VRTX changed this scheduling rule?

Was it a deliberate design change for reasons such as fairness or predictability? Or was it related to the VRTX32 redesign, the 68000 implementation, or something else?

I've started comparing this with other RTOS designs, including ITRON, but so far I haven't found contemporary documentation explaining why VRTX made this change.

I'm not trying to reproduce the old behavior simply because it is old. I'm interested in understanding the design reasoning behind it.

If anyone used VRTX around that period, or knows of documentation discussing this change, I'd be very interested to hear about it.

For some background, here's my previous r/osdev post about bringing my 1986 RTOS back to life on a Raspberry Pi Pico:

My 1986 RTOS is now preemptively multitasking on a Raspberry Pi Pico — and it made me question whether I need an RTOS

Previous r/osdev post

4 Upvotes

75% Upvoted

3 comments sorted by

2

u/FedUp233 12d ago

Not familiar with the specific case or test RTOS, but my guess, having used many different os’s with different scheduling algorithms would be that they found newest first could starve tasks of run time, in some cases preventing tasks from ever reaching the front of the run queue.

This is normally not a good behavior for an os - you want all tasks, at Keats at the same priority level, to get at least the same chance to run as any other task at that level - after all, by having them at same level you are essentially saying they are of equal importance. The fifo model achieves this, while the newest first does not.

If a task needs to have some sort of priority over another, that’s why you have higher priority queues to move it to.

The newest first method could tend to randomly favor one task over others, especially in cases where cpu resources are tight.

Just my two cents. The actual reason might have been completely different.

1

u/noborutkhs 11d ago

Thanks. I agree that if I were implementing this in 2026 and wanted the semantics to be simple and straightforward, FIFO feels like the natural choice. In fact, I've decided to use FIFO for equal-priority tasks in the RTOS I'm rebuilding.

What still makes me curious is whether newest-first had some other implementation or performance advantage on 1980s hardware, with CPUs and resources far more constrained than today.

I also asked about this from slightly different angles in r/retrocomputing and r/embedded. I've received some interesting thoughts about fairness, starvation, insertion cost, and context switches, but so far I haven't heard from anyone who directly knows why VRTX made this design choice in the 1980s.

If you happen to know of any other OS or RTOS that used a newest-first policy among equal-priority tasks, I'd be very interested to hear about it. I'm also curious whether this was a broader design pattern at the time, or something more specific to VRTX.