Avoiding priority inversion with software design

Hi Subbarayan,

Let me answer your last question. After boosting priority scheduler checks for the highest priority task for execution. Note that other task even though with same priority is still pending on Mutex and is the pended queue/not in ready queue. Hence sheduler goes on to execute the task with boosted prioirty which ready for execution (in this case is the highest priority task ready for execution at that point of time)

Cheers Gaurav

subbarayan,

Here is a link to a great example of how multi-threading works and what some of the main issues around multithreading (including priority inversion) are and how to avoid them.

Keith

One of the is blocked, one of them isn't.

Only one of them is ready. One is blocked waiting on a resource that's locked by the other.

On Mon, 15 Oct 2007 06:10:09 -0000, ssubbarayan wrote in comp.arch.embedded:

I cannot tell you how UCOS-II was designed, I have not used it, nor have I looked at its source code. I can tell you what I did, to support priority inheritance. This is in a preemptive multitasking kernel with all priorities fixed at system start up, and no two tasks allowed to have the same fixed priority.

A bitmap scheduler, like mine, maintains a "ready" bitmap, where the bit for each task is set if it is ready to run, and not set if the task is blocked, for a shared resource or any other reason.

It is not difficult for a fixed, unique priority kernel to handle priority inheritance, as long as no two tasks with the same priority are never both ready to run at the same time.

When high priority task H tries to get a mutex already held by lower priority task L, it is blocked and its bit is removed from the "ready" bitmap, and the priority of task L is temporarily raised to that of task H.

So when the scheduler looks at only the tasks with bits set in the "ready" bitmap, it does not look at task H because its bit is off, and only sees task L as ready with that priority.

Hi all, Thanks for all your replies.But theres no reply regarding the design stated.Can anyone help me understand this?

Regards, s.subbarayan

Unless the computer hardware supports instructions like "find first bit set" type instructions, what is the point of using a bitmap to indicate if a task is runnable or not.

On ordinary hardware, you still would have to shift one bit at the time to detect if a task is runnable, but stepping through an array is not much time consuming.

The only advantage of using bitmaps to indicate if a task is runnable that I can think of, is that it can easily detect that _no_ tasks are runnable (mask == 0 ), so you can run the Null task. While this might save a _very_ minuscule amount of electric power, stepping through the task list when no activity is required should be irrelevant.

Paul

No you don't -- there are far more efficient ways to do it with no shifting involved. Here's one method (which IIRC is used by uC/OS-II): first you search through the bits a byte at a time to find the first non-zero byte. [That allows you to check 8 tasks in parallel with a single load or test instruction.] Once you find the byte with the first non-zero bit, you use that byte to index into a lookup table that gives you the highest set bit number.

If you've got less than nine tasks total, you can skip the first step altogether and determine the highest priority task in O(1) time time with 2-3 assembly instructions.

Even with 9 or more tasks, the number of bytes is still usually small enough that you can unroll the loop that's searchign for the first non-zero byte and end up with something that's very fast and still takes very little code space (maybe 300 bytes of ROM space including the lookup table?).

If you're stepping through an array one task per index, it's more time consuming than doing it 8 tasks per index.

Yes there were.

Probably not. We've already explained it to death.

If you don't understand it yet, you should probably go read the uC/OS-II book along with some general OS theory texts.

Clever.

So with 64 bit hardware, you first detect the first non-zero 64 word, after that you use 32 bit instructions to detect which 32 bit half contains the nonzero bit and repeating this with 16 bits will bring you down to the 8 bit case and with software to the 4, 2 and 1 bit cases.

I guess that I am getting too old, since I think that using a 256 byte LUT on small hardware to find the highest bit set is quite extraordinary :-).

Paul

Quite. [I don't claim to have invented any of it.]

If you have enough tasks, it might be faster to start out with bigger chunks.

It does seem sort of extravagant. If the 256-byte lookup table is a strain you can play tricks like using only 4 bits of every byte and a 16-byte lookup table. Or you can calculate the highest bit number with 3 ANDs and a little bookeeping:

Here's the Python code for that:

def highestBitSet(m): n = 0 if m & 0xf0: m &= 0xf0 n |= 4 if m & 0xcc: m &= 0xcc n |= 2 if m & 0xaa: n |= 1 return n

On a CPU like an ARM, that's pretty much one CPU instruction per line of code. Others might require a few conditional jumps to be thrown in. At that point, an unrolled shift-and-test loop is probably about as fast.

OTOH, people with ARM CPUs aren't generally given pause by the thought of a 256-byte lookup table. :)

Hi Edward, I do understand whats stated here with respect to bitmap scheduler.What I refered as not able to get reply is with respect to server task design explained to over come priority inheritance.I agree I should have stated it more clear,but still to me this is (server approach) is not understandable. Regards, s.subbarayan