Decade Old Design Error

[arakji]

Your RTOS has a decade old design error.

Note first that in ThreadX semaphore Blocked Lists are not sorted and application developers must call tx_semaphore_prioritize() on a semaphore before calling tx_semaphore_put() on it to ensure the highest priority task blocked on it is unblocked.

1. A semaphore has an unsorted Blocked List that contains (in the following order) thread d, thread c, thread b, and thread a. thread a is the highest priority thread in this list and thread b is the second highest one. The rest are lower priority.

2. thread 1 calls tx_semaphore_prioritize() on the semaphore. This places thread a at the head of the semaphore's Blocked List.

3. An interrupt occurs and it's ISR calls tx_semaphore_prioritize() on the semaphore. This does not change the semaphore's Blocked List as the highest priority thread is already at the head.

4. The ISR then calls tx_semaphore_put() on the semaphore and unblocks thread a.

5. thread 1 resumes. thread 1 calls tx_semaphore_put() on the semaphore and unblocks thread d. thread b should have unblocked.

This is an error.

The solution is to provide a tx_semaphore_prioritized_put() function that:

1. Disables interrupts
2. Prioritizes
3. Puts
4. Enables interrupts

[fdesbiens]

Hi @arakji.

Thank you for providing this feedback. We will discuss it in out weekly meeting.

[billlamiework]

Hi Arakji,

Thank you for your input. This is not a design error. In fact, it was intentionally designed this way. The base design of ThreadX relies on FIFO blocking across all resources. As you probably understand, this is mainly for performance and determinism reasons. The tx_*_prioritize API calls were introduced several years ago as a mechanism to unblock the highest-priority, suspended thread. This is a point-in-time service, meaning that subsequent suspension or resumption of activities on the same object can cause the highest-suspended thread NOT to be at the front of the list. And in your case, the second of two successive prioritize API calls has no effect.

Going back to your example, you have two producers for the same semaphore, which isn't the most common use case. That said, to prevent the exact race condition you described, you can do exactly what you suggest at the application level, e.g.:

tx_interrupt_control(TX_INT_DISABLE);
tx_semapore_prioritize(&your_semaphore);
tx_semaphore_put(&your_semaphore);
tx_interrupt_control(TX_INT_ENABLE);

Another design goal of ThreadX is simplicity. We deliberately keep the number of APIs to a minimum and avoid more complex functionality. That said, the documentation for all the tx_*_prioritize APIs should be updated to clearly state that asynchronous activities may also modify the suspension list, and that successive prioritize API calls will have no effect.

I hope that helps!

Best regards,

Bill

[arakji]

Just to be clear, you will still have problems for more common use cases. Concretely, there is a problem even with a single prioritize() API call and even if called by a single thread context (i.e only one producer).

Assuming thread n is higher priority than thread n+1:

1. thread 12 calls prioritize() on a semaphore with threads 10-5 (in that order) in its Blocked List. This places thread 5 at the head.
2. Before thread 12 calls put(), thread 1 becomes ready and calls get() on the semaphore.
3. Now when thread 12 resumes and calls put(), thread 5 will be unblocked rather than thread 1.

Of course one can say that, semantically, the end of prioritize() is the same as the start of put(). So in the previous example, thread 12 was really able to unblock thread 5 before thread 1 became ready.

However, if we accept such semantics, a contradiction arises:

1. thread 12 calls prioritize() on a semaphore with threads 10-5 (in that order) in its Blocked List. This places thread 5 at the head.
2. Before thread 12 calls put(), thread 1 becomes ready and unblocks thread 11.
3. thread 1 then calls get() on the semaphore and blocks.
4. Now thread 11 will run to completion before thread 5 (which will run to completion before thread 1).

In general, a priority-sorted Blocked List is a better data structure for an RTOS.

[billlamiework]

Yes, that is the reason my response said "...asynchronous activities...", which includes other threads preempting and suspending between prioritize and put API calls. If the user of the prioritize APIs require an atomic operation, they must guarantee that either with interrupt lockout or mutex protection (if only threads are interacting with the mutex). Note that if an ISR or the highest priority thread is the single producer, no additional protection is required.

Regarding your comment that a priority-sorted blocked list is a better data structure, that's a matter of opinion. Making that the default guarantees the additional (and variable) overhead for every use case. While you might think that is the way to go, many developers don't need priority suspension and would not appreciate having that overhead forced upon them.

[arakji]

Considering the example from my previous reply, even if only threads are interacting (no ISRs), interrupt lockout is required to guarantee thread 5 will run before thread 11.

Ultimately, this is another flexibility/complexity tradeoff. I would advise keeping the RTOS simple (and conventional as disabling and enabling interrupts around 2 API calls is not at all typical). Otherwise, the flexibility/complexity should be well documented.

With regard to overhead, even with FIFOs there can be an O(n) latency imposed upon the highest priority thread in the worst case. The reason is that n threads could become ready.

One idea, however, would be to specify the data structure of the Blocked List (priority-sorted or FIFO) when a semaphore is created.

[billlamiework]

There are many developers using ThreadX, so no current APIs can be changed. It would even be problematic to change internal functionality. Given everything, I'm of the opinion that adding more to the documentation is a better way to address this than adding a new API. Thanks again for your input.