senaus wrote:I personally use the method Brendan described, coupled with a little bitmap which tells the scheduler which queues are non-empty. I can then use a library function to find the most significant bit (a single instruction on i386), to save searching through the array. This is truly O(1) in both the number of tasks and the number of priorities.
The only problem is starvation, as mentioned above. I've been thinking about two possible solutions, described below.
One is to 'boost' the priority of tasks below the current maximum, every time we schedule a task which has greater than or equal priority to that of the previous. Using doubly linked lists this is easy, but this would make the algorithm O(#priorities).
Another is to 'rotate' the queues, by adding an offset (which is incremented periodically) to the priority before we queue a task, and then by bit rotating the bitmap when we schedule. This has the drawback of turning the highest priority tasks into the lowest priority when we increment the offset, so we need to move all tasks in the previous highest priority queue into the new highest queue.
Sean
Well, like you said, it has starvation issues, that need to be worked around. My post above describes a very similar method of having a list of queue's that will never starve a process, and it's O(1). I also support variable time slices, so for example, you could do 7ms for high priority, 5ms for medium, and 3ms for idle, so not only are the high priority queue's called more often, it's also run for a slightly longer time. I can tweek the settings by changing a few variables very easily, and I can even change mappings based on system setup or thread counts. Like I said, I may re-implement this method because it's very easily extensible, fast time to find next thread O(1), and relatively easy to implement (and can also add priority levels if I find the current isn't good enough).
An example of how to use in practice:
Code: Select all
#deifne MAX_PRIORITY 4 //sleep, idle, normal, high
List_S ThreadList[MAX_PRIORITY];
u32 PriorityTiming[MAX_PRIORITY] = {0,5,5,5};
u32 PriorityList[6] = {3,2,3,1,3,2};
u32 PriorityListLen = 6;
u32 PriorityListIndex =0;
Thread_S *FindNextThread(void)
{
Thread_S *ptrThread;
do //Until we find a list with threads!
{
++PriorityListIndex;
if (PriorityListIndex>PriorityListLen)
PriorityListIndex = 0;
}
while (ThreadList[PriorityList[PriorityListIndex]].Head == NULL);
ptrThread = NextInList(&ThreadList[PriorityList[PriorityListIndex]]);
ptrThread->TimeToRun = PriorityTiming[PriorityList[PriorityListIndex]];
return ptrThread;
}
NextInList just returns the next element in the list (the data, not the list container). Now, you can make your priority queue's, the time they are called, how long they are each run for, what order they are run very easy to modify, you will never have thread starvation (as long as you set it up right), and it will always move onto the next priority if this one doesn't have any left, so say in my example, high priority has no current threads, it will call it like so: (3 being high, 2 being normal, 1 being idle), and assuming equal timing
2,1,2,2,1,2,2,1 so normal priority would get 66% of the CPU, while idle would get 33%, now if normal had none, and both high and idle had some in the list it'd go like so:
3,3,1,3,3,3,1,3 so high priority would get 75% of the CPU and idle would get 25% (this assumes the timing's are equal, which they don't have to be). Now, if normal and high are the only 2:
3,2,3,3,2,3,3,2 so we are back to 66% vs. 33%, which can easily be modifed using the variable time slice, or making a different priority list (which can even be variable depending on whatever criteria you want to use). It's relatively extensible, fast and compact.
In your 2 "work arounds", the first is O(# of priorities), which is fine if there aren't to many, but with my method you can have 20 priorities, with very little slow-down (especially if you are smart and create a list based on priorities that aren't in use, like shown below). The second sounds like a pain, and moving data around is never fun
. Below is an example to help speed up based on missing priorities (only needs to be called whena priority list is emptied or a first element is added to a list).
Code: Select all
#deifne MAX_PRIORITY 4 //sleep, idle, normal, high
List_S ThreadList[MAX_PRIORITY];
u32 PriorityTiming[MAX_PRIORITY] = {0,5,5,5};
u32 ListNotEmpty[MAX_PRIORITY] = {0,0,0,0}; //Mark them all as empty
u32 MasterPriorityList[6] = {3,2,3,1,3,2};
u32 PriorityList[6]; //Enough to fit the entire list if needed
u32 MasterListLen = 6;
u32 PriorityListLen = 0;
u32 PriorityListIndex = 0;
//ListNotEmpty is updated when tasks are added/removed!
void GeneratePriorityList(void)
{
u32 Ctr;
PriorityListLen = 0;
for (Ctr=0;Ctr!=MasterListLen;++Ctr)
{
if (ListNotEmpty[MasterPriorityList[Ctr]]) //NotEmpty?
{
PriorityList[PriorityListLen] = MasterPriorityList[Ctr];
++PriorityListLen;
}
}
}
Now, if we add a thread to a priority level (excluding sleeping threads), we simply check if the list was empty first, if it was, then we call the GeneratePriorityList function and we can remove the blank list check since it will never be empty, and we no longer have ANY loops at all in our FindNextThread, bringing it back to the O(1) in all cases, with no thread starvation if you didn't mess up building your lists. Also, idle threads will get 100% cpu if no other threads are active, which is how it should be, without any special case code.
, this is essentially O(1) for any amount of processors, with priorities and round-robin within each priority. You can even limit the amount of time spent on each priority level this way.