Kickstart 1.x - 3.x and Exec Priority Inversion

[Trev]

(Retyping this because my session timed out the last time. !@#%)

In a nutshell, if a high priority task is waiting on a semaphore held by a low priority task, the high priority task is effectively running at the priority of the low priority task. If a medium priority task comes along before the low priority task releases the semaphore, you end up with a serious case of priority inversion.

Can a simple wrapper be used to implement priority inheritance?

Code: [Select]


VOID ObtainSemaphoreWithInheritance(struct SignalSemaphore * sem)
{
    Forbid();

    if (!AttemptSempahore(sem)) {
        BYTE newPrio = FindTask(NULL)->tc_Node.ln_Pri;
        struct Task * prevTask = sem->ss_Owner;
        BYTE prevPrio = prevTask->tc_Node.ln_Pri;

        if (prevPrio < newPrio)
            SetTaskPri(prevTask, newPrio);

        ObtainSemaphore(sem);
        SetTaskPri(prevTask, prevPrio);
    }

    Permit();
}

Assuming the lower priority task isn't busy looping around AttemptSemaphore(), it will be in a wait state between ObtainSemaphore() and SetTaskPri(), so it's increased priority shouldn't be an issue at that time. Even if it does busy loop, it might still be beneficial.

Has any thought been given to whether ObtainSemaphore could/should be patched to support priority inheritance? I can see where it might break synchronization in existing code that depends on priority inversion as a "feature."

Trev

[Trev]

(And I realize that this simple approach only works for two tasks using a single semaphore. More complicated constructs would require an algorithm to chain and unwind priorities within the semaphore queue.)

[Trev]

And a little more investigation. Creating a global mechanism for priority inheritance would require replacements for the *Semaphore functions.

When a task is blocked waiting for a semaphore (Wait(1<<2)), Exec adds the task to the semaphore's wait queue using a temporary SempahoreRequest structure; however, with only a pointer to the task in hand, there is no way to determine the semaphore upon which the task is waiting.

The replacement *Semaphore functions (wrappers for the existing *Semaphore functions) would necessarily manage a map associating tasks to semaphores.

When a high priority tasks attempts to lock a semaphore owned by a low priority task, the new ObtainSemaphoreWithInheritance function can examine the state of the blocking task (sem->ss_Owner->tc_State), and if it too is blocked (TS_WAIT), it can use the map to determine the address of the semaphore. In this way, it can walk the chain of blocked tasks, willing its priority to all blocked tasks with lower priorities.

ObtainSemaphoreWithInheritance will also store a record of a waiting task's pre-wait state priority. When the task subsequently calls ReleaseSemaphoreWithInheritance, the task's priority is then restore to its state prior to the call to ObtainSemaphoreWithInheritance.

So, it's certainly possible to patch the current *Semaphore functions to support priority inheritance. It would also be fairly straightforward to implement a library that cooperating tasks can use to manage semaphores.

In the simple case of two tasks sharing a single semaphore, an abbreviated ObtainSemaphoreWithInheritance can be used.

[Beast96GT]

Sorry to not provide any insight into your topic, but I was curious as to what C++ compiler you used and if it would work on the A2000 platforms...  Thanks!

BTW:  Line up those braces!   :-D

[Trev]

Eh? Placing the opening brace of an if block on the same line as the if is a pretty common practice. ;-)

I use vbcc and StormC 3 for C. StormC has basic C++ support, but I don't use it for that. StormC 3 should work fine on an A2000. I do most of my development in WinUAE.

[amigaksi]

>by Trev on 2008/9/17 21:09:35
>
>(Retyping this because my session timed out the last time. !@#%)

I have had that happen a few times to me as well.

>In a nutshell, if a high priority task is waiting on a semaphore held by a low priority task, the high priority task is effectively running at the priority of the low priority task. If a medium priority task comes along before the low priority task releases the semaphore, you end up with a serious case of priority inversion.

If the semaphore involves something critical which you are allowing a lower priority task to do then there's nothing wrong with that.  You could enforce some rule that the semaphore has to be released by a lower priority task within a certain time frame-- but that would involve the highest priority task handling all semaphores through inheritance and/or some sort of timer interrupt.

>Can a simple wrapper be used to implement priority inheritance?

I guess if you try a timer sort of set-up so after a while it undoes whatever the lower priority task did (so as to avoid disaster) and gives the semaphore capability over to the next priority task.  I am assuming timers itself won't be allowed to be disabled by lower priority tasks in the call to Forbid() like if it does a Move.w #$7FFF,$DFF09A.

[Trev]

@amigaksi

If the semaphore involves something critical which you are allowing a lower priority task to do then there's nothing wrong with that.

I think that depends on the intent of the code. In this case, I'm polling hardware. As 680x0 Amigas don't have an idle loop, I'm using a low priority task (-128) to simulate idle-time polling; however, I have a higher priority task that attempts to guarantee at least some amount of polling occurs prior to a soft deadline.

Neither task can poll the hardware at the same time, so I need to use a semaphore to coordinate the work. If a medium priority task is running while the low priority task holds the semaphore, the high priority task doesn't run, and the deadline is not met, i.e. priority inversion.

In this specific case, the high priority task has prior knowledge about the low priority task and can manage the low priority task's priority accordingly. The problem started me thinking about the general case, though, and how it might be solved.

Other solutions to my scheduling problem involve the use of hardware interrupts (vblank for interval timing), software interrupts (implicit synchronization), timers (soft real-time scheduling), etc. All have tradeoffs. I haven't done the math yet--I'm treating the software controlling the hardware like a real-time subsystem--so I'm still not sure what arrangement of tasks will meet my needs.