tasks with priority execution order

[dulantha_f]

I'm trying to schedule tasks with priorities. I have a class that inherits from tbb::task with execute() method overriden. For testing purposes it's only printing out a line.

tbb::task* execute() {

cout<<"Task Number "<<_taskNumber<<" Priority: "<<_priority<

return NULL;

}

Then I create 30 task objects and use tbb::task::enqueue(taskObj, priority) to execute them. If I'm using incorrect syntax please correct me.

TestTask& task1 = *new(tbb::task::allocate_root()) TestTask(1,"low");

tbb::task::enqueue(task1,tbb::priority_t::priority_low);

I use low, high and normal priorities in random order.

But according to the output normal tasks execute first, and then highs and then lows. I would expect highs first, then normals and finally lows but that's not my output.

Thanks for ideas guys.

[RafSchietekat]

Most curious... execution order would not be exact, but it should not exhibit inverted tentencies. Please provide a small self-contained program to reproduce this, making sure to test it also on the latest TBB version (and of course specify at least TBB version, if not hardware architecture, operating system and compiler).

[jimdempseyatthecove]

Without seeing all the code (working test code) it is hard to assess the situation.

Possible hypothesis:

Your priority queues are exhibiting a "sticky" property. Meaning, once queue at priority x starts, it runs until all entries at that priority are consumed. As a quick-and-dirty test for this, enqueue 10 low, then 10 normal, then 10 high (your 30 tasks). Then switch the orders of the 10's (normal,low,high; normal, high, low; high, now, normal; high, normal, low). "sticky" would result in the first enqueues first.

Jim Dempsey

[dulantha_f]

here's my code guys:

#include "stdafx.h"

#include

#include

#include

using namespace System;

using namespace std;

class MyTask : public tbb::task

{

public :

MyTask(int val, string priority):_taskNumber(val),_priority(priority) {};

~MyTask() {};

tbb::task* execute() {

cout<<"Task Number "<<_taskNumber<<" Priority: "<<_priority<

return NULL;

}

private:

int _taskNumber;

string _priority;

};

int main(array<:STRING> ^args)

{

for (int i=0; i<3; i++)

{

MyTask& task1 = *new(tbb::task::allocate_root()) MyTask(1,"low");

tbb::task::enqueue(task1,tbb::priority_t::priority_low);

MyTask& task2 = *new(tbb::task::allocate_root()) MyTask(i*10+2,"high");

tbb::task::enqueue(task2,tbb::priority_t::priority_high);

MyTask& task3 = *new(tbb::task::allocate_root()) MyTask(i*10+3,"normal");

tbb::task::enqueue(task3,tbb::priority_t::priority_normal);

MyTask& task4 = *new(tbb::task::allocate_root()) MyTask(i*10+4,"normal");

tbb::task::enqueue(task4,tbb::priority_t::priority_normal);

MyTask& task5 = *new(tbb::task::allocate_root()) MyTask(i*10+5,"low");

tbb::task::enqueue(task5,tbb::priority_t::priority_low);

MyTask& task6 = *new(tbb::task::allocate_root()) MyTask(i*10+6,"high");

tbb::task::enqueue(task6,tbb::priority_t::priority_high);

MyTask& task7 = *new(tbb::task::allocate_root()) MyTask(i*10+7,"high");

tbb::task::enqueue(task7,tbb::priority_t::priority_high);

MyTask& task8 = *new(tbb::task::allocate_root()) MyTask(i*10+8,"normal");

tbb::task::enqueue(task8,tbb::priority_t::priority_normal);

MyTask& task9 = *new(tbb::task::allocate_root()) MyTask(i*10+9,"low");

tbb::task::enqueue(task9,tbb::priority_t::priority_low);

MyTask& task10 = *new(tbb::task::allocate_root()) MyTask(i*10+10,"normal");

tbb::task::enqueue(task10,tbb::priority_t::priority_normal);

}

return 0;

}

The output I get is:

Task Number 13 Priority: normal

Task Number 3 Priority: normal

Task Number 18 Priority: normal

Task Number 4 Priority: normal

Task Number 30 Priority: normal

Task Number 8 Priority: normal

Task Number 10 Priority: normal

Task Number 14 Priority: normal

Task Number 20 Priority: normal

Task Number 23 Priority: normal

Task Number 24 Priority: normal

Task Number 28 Priority: normal

Task Number 27 Priority: high

Task Number 26 Priority: high

Task Number 22 Priority: high

Task Number 16 Priority: high

Task Number 17 Priority: high

Task Number 12 Priority: high

Task Number 7 Priority: high

Task Number 2 Priority: high

Task Number 6 Priority: high

Task Number 15 Priority: low

Task Number 1 Priority: low

Task Number 1 Priority: low

Task Number 5 Priority: low

Task Number 29 Priority: low

Task Number 9 Priority: low

Task Number 1 Priority: low

Task Number 19 Priority: low

Task Number 25 Priority: low

I'm using TBB 4.0 Update 1 commercial-aligned release downloaded from the website. Like I said I queue up tasks in random order but I get normals first and then highs.

And jimdempseyatthecoveeven when I queue high's first then low's and finally normals, still the normals get executed first.

A side note, I had the following code in the file because I was playing around with tbb_thread. When I commented that code out and ran I got the high's first - the expected order. But after I ran the same program a few times it went back to normals first. I tried to get high's first again but can't. That behaviour I only saw once.

#include

class ThreadTask

{

void operator()(int i, string val)

{

cout<<"Task Number "<<<" Priority: "<<

}

};

I'm building this in Visual Studio and when I say "ran the program" I mean hit the green Run button in Visual Studio.

Thanks for looking into this guys. Really appreciate it.

[jimdempseyatthecove]

Try changing your main such that it instantiates a launching task, high priority. The contents of that task being the loop that launches all of the other tasks. Seems unusual to nest an additional task level, but this may be an issue of main() running at normal level, enqueuing the tasks, then continuing to run at normal level consuming the tasks at that level. In your above code,after enqueuing the 30 tasks, you have main still running at normal priority. Because TBB does not preempt tasks, this normal level task runs to completion (taking the remainder of normal level tasks with it).

This may mean that once any low level task begins, all currently remaining low level tasks will run (via the first one run).

Jim Dempsey

[dulantha_f]

hey Jim, I tried your idea but still got the same results - normal first. Here's my code:

#include "stdafx.h"

#include

#include

#include

//#include

using namespace System;

using namespace std;

// object the 30 tasks execute

class MyTask : public tbb::task

{

public :

MyTask(int val, string priority):_taskNumber(val),_priority(priority) {};

~MyTask() {};

tbb::task* execute() {

cout<<"Task Number "<<_taskNumber<<" Priority: "<<_priority<

return NULL;

}

private:

int _taskNumber;

string _priority;

};

class CreateTasks : public tbb::task

{

public :

CreateTasks(int val, string priority):_taskNumber(val),_priority(priority) {};

~CreateTasks() {};

tbb::task* execute() {

MyTask& task21 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task21,tbb::priority_t::priority_high);

MyTask& task22 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task22,tbb::priority_t::priority_high);

MyTask& task23 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task23,tbb::priority_t::priority_high);

MyTask& task24 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task24,tbb::priority_t::priority_high);

MyTask& task25 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task25,tbb::priority_t::priority_high);

MyTask& task26 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task26,tbb::priority_t::priority_high);

MyTask& task27 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task27,tbb::priority_t::priority_high);

MyTask& task28 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task28,tbb::priority_t::priority_high);

MyTask& task29 = *new(tbb::task::allocate_root()) MyTask(1,"high");

tbb::task::enqueue(task29,tbb::priority_t::priority_high);

MyTask& task1 = *new(tbb::task::allocate_root()) MyTask(1,"low");

tbb::task::enqueue(task1,tbb::priority_t::priority_low);

MyTask& task2 = *new(tbb::task::allocate_root()) MyTask(2,"low");

tbb::task::enqueue(task2,tbb::priority_t::priority_low);

MyTask& task3 = *new(tbb::task::allocate_root()) MyTask(2,"low");

tbb::task::enqueue(task3,tbb::priority_t::priority_low);

MyTask& task4 = *new(tbb::task::allocate_root()) MyTask(2,"low");

tbb::task::enqueue(task4,tbb::priority_t::priority_low);

MyTask& task5 = *new(tbb::task::allocate_root()) MyTask(2,"low");

tbb::task::enqueue(task5,tbb::priority_t::priority_low);

MyTask& task6 = *new(tbb::task::allocate_root()) MyTask(2,"low");

tbb::task::enqueue(task6,tbb::priority_t::priority_low);

MyTask& task7 = *new(tbb::task::allocate_root()) MyTask(2,"low");

tbb::task::enqueue(task7,tbb::priority_t::priority_low);

MyTask& task8 = *new(tbb::task::allocate_root()) MyTask(2,"low");

tbb::task::enqueue(task8,tbb::priority_t::priority_low);

MyTask& task9 = *new(tbb::task::allocate_root()) MyTask(2,"low");

tbb::task::enqueue(task9,tbb::priority_t::priority_low);

MyTask& task10 = *new(tbb::task::allocate_root()) MyTask(1,"low");

tbb::task::enqueue(task10,tbb::priority_t::priority_low);

MyTask& task11 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task11,tbb::priority_t::priority_normal);

MyTask& task12 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task12,tbb::priority_t::priority_normal);

MyTask& task13 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task13,tbb::priority_t::priority_normal);

MyTask& task14 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task14,tbb::priority_t::priority_normal);

MyTask& task15 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task15,tbb::priority_t::priority_normal);

MyTask& task16 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task16,tbb::priority_t::priority_normal);

MyTask& task17 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task17,tbb::priority_t::priority_normal);

MyTask& task18 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task18,tbb::priority_t::priority_normal);

MyTask& task19 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task19,tbb::priority_t::priority_normal);

MyTask& task20 = *new(tbb::task::allocate_root()) MyTask(3,"normal");

tbb::task::enqueue(task20,tbb::priority_t::priority_normal);

return NULL;

}

private:

int _taskNumber;

string _priority;

};

#include "stdafx.h"#include #include #include //#include
using namespace System;using namespace std;

//I execute CreateTask.execute() which in turn creates the other 30 tasks.

int main(array<:STRING> ^args)

{

//execute task with high priority

CreateTasks& task = *new(tbb::task::allocate_root()) CreateTasks(1,"high");

tbb::task::enqueue(task,tbb::priority_t::priority_high);

return 0;

}

[dulantha_f]

I'm curious did anyone else try to run the code I have and got the same results?

[RafSchietekat]

Confirmed with tbb40_278oss (update 2 if I'm not mistaken) on x86/Linux/g++.

Some required changes were obvious, but does your compiler really accept "tbb::priority_t::priority_normal"?

[jimdempseyatthecove]

I have not tried your test code, and I have to admit I am not a heavy (or moderate) TBB user. I would like to ask if you have an actual need for prioritization, or are you just exploring this feature and reporting an anomoly/bug?

Have you considered using multiple concurrent queues, one for each priority. These queues can hold your own task functors w/wo arg(s). And your top-level task poll the queues in priority order. While this may not be energy efficient, it may provide you with the prioritization you seek (at least until you get a resolution on your task priority query).

Jim Dempsey

[Anton_M_Intel]

Thanks,

hmm... a quick experiment with my trunk build on MacOs with GCC 4.2.1 does not show the problem. I'll check other systems and builds later.

[SergeyKostrov]

Quoting Raf Schietekat

Confirmed with tbb40_278oss (update 2 if I'm not mistaken) on x86/Linux/g++.

Some required changes were obvious, but does your compiler really accept "tbb::priority_t::priority_normal"?

I'm currently testing a Test-Case #1 andI don't think that an issue is related to this. It looks like TBB uses a
'LIFO' approach when executing created tasks but I can bewrong here. I'm still investigating.

[SergeyKostrov]

>>...MacOS with GCC 4.2.1 does not show the problem...

On a Windows platforma modified Test Case #1 is notworking. TBB v4.0 is used. I'll provide all technical details later.

Note: Expected correctoutput. Produced due to an error in a Test-Case




Best regards,
Sergey

[dulantha_f]

Thanks for confirming Raf. And yes I'm using the C++ compiler that comes with Visual Studio 2010. It threw a warning about it but not an error. I changed that to tbb::priority_normal and the warning went away but still the results are the same.

[dulantha_f]

Hey Sergey,

Can you please tell me the modifications you did for Test Case #1. I'm glad you got it to work.

Thanks a lot.

-Dulantha

[SergeyKostrov]

Guys,

I'm really sorry but I confirm a problem on a 32-bit Windows platform. I had anerror in my Test-Case and
it produced a correct output. I've updated a Post #13 andadded a note forthe screenshot:

"Note: Expected correctoutput. Produced due to an error in a Test-Case"

So, no matter what I tried to do tasks with 'normal' priorities are executed first, followed by 'high' and 'low' priorities.

Here are ALLtechnical details:

- Summary: Tasks with priority 'normal' ( enum value 1073741822 ) are executed first. Since on MacOS
tasks with priority 'high' are executed first I could assume that there is a portability issue
but so farit is not clear what is wrong. Enum values for prioritiesare as follows:
low = 536870911
normal = 1073741822
high = 1610612733
Since all objects of CMyTask are saved in some container it would be nice to find a way of
sorting the containerby priorities of tasksin descending order and thentorun
Test-Cases.

- OS: 32-bit Windows XP SP3
- TBB: version 4.0

tbb_stddef.h
...
#define TBB_VERSION_MAJOR 4
#define TBB_VERSION_MINOR 0
...

- IDE: MS Visual Studio 2005
- MS C/C++ compiler warning
...
tbb::task::enqueue( task01, tbb::priority_t::priority_low );
...
Warning C4482: nonstandard extension used: enum 'tbb::priority_t' used in qualified name
It is not related to the problem.

- There is an interesting comment in 'arena.h' header file:

struct arena_base : intrusive_list_node
{
...
//! Highest priority level containing enqueued tasks
/** It being greater than 0 means that high priority enqueued tasks had to be
bypassed because all workers were blocked in nested dispatch loops and
were unable to progress at then current priority level. **/
tbb::atomic my_skipped_fifo_priority;
...
};

- Test-Cases Outputs:

// Test-Case 1
...
[ Task Number 012 ] [ Priority Code: normal ] [ Priority: 1073741822 ]
[ Task Number 002 ] [ Priority Code: normal ] [ Priority: 1073741822 ]
[ Task Number 022 ] [ Priority Code: normal ] [ Priority: 1073741822 ]
[ Task Number 023 ] [ Priority Code: high ] [ Priority: 1610612733 ]
[ Task Number 013 ] [ Priority Code: high ] [ Priority: 1610612733 ]
[ Task Number 003 ] [ Priority Code: high ] [ Priority: 1610612733 ]
[ Task Number 001 ] [ Priority Code: low ] [ Priority: 536870911 ]
[ Task Number 021 ] [ Priority Code: low ] [ Priority: 536870911 ]
[ Task Number 011 ] [ Priority Code: low ] [ Priority: 536870911 ]
...

// Test-Case 2
...
[ Task Number 032 ] [ Priority Code: normal ] [ Priority: 1073741822 ]
[ Task Number 002 ] [ Priority Code: normal ] [ Priority: 1073741822 ]
[ Task Number 062 ] [ Priority Code: normal ] [ Priority: 1073741822 ]
[ Task Number 062 ] [ Priority Code: high ] [ Priority: 1610612733 ]
[ Task Number 032 ] [ Priority Code: high ] [ Priority: 1610612733 ]
[ Task Number 002 ] [ Priority Code: high ] [ Priority: 1610612733 ]
[ Task Number 001 ] [ Priority Code: low ] [ Priority: 536870911 ]
[ Task Number 061 ] [ Priority Code: low ] [ Priority: 536870911 ]
[ Task Number 031 ] [ Priority Code: low ] [ Priority: 536870911 ]
...

C/C++ codes for Test-Cases are in thenext post.

[SergeyKostrov]

class CMyTask : public tbb::task
{
public :
CMyTask()
{
};

CMyTask( int iNumber, char *szPriorityCode )
{
m_iNumber = iNumber;
strcpy( m_szPriorityCode, szPriorityCode );
m_iPriority = -1;
};

~CMyTask()
{
};

tbb::task * execute()
{
printf( "[ Task Number %03ld ] [ Priority Code: %6s ] [ Priority: %10ld ]\n",
( int )m_iNumber, &m_szPriorityCode[0], ( int )m_iPriority );
return ( tbb::task * )NULL;
};

void SetPriority( int iPriority )
{
m_iPriority = iPriority;
};

private:
int m_iNumber;
char m_szPriorityCode[16];
int m_iPriority;
};

void main( void )
{
printf( "Initialization started\n" );

#if defined ( __TBB_TASK_PRIORITY )
printf( "TBB Task Priorities Enabled\n" );
#else
printf( "TBB Task Priorities Disabled\n" );
#endif

// Test-Case SK1
///*
for( int i = 0; i < 3; i++ )
{
CMyTask &TaskL = *new( tbb::task::allocate_root() ) CMyTask( i*10+1, "low" );
TaskL.SetPriority( ( int )tbb::priority_t::priority_low );
tbb::task::enqueue( TaskL, tbb::priority_t::priority_low );

CMyTask &TaskN = *new( tbb::task::allocate_root() ) CMyTask( i*10+2, "normal" );
TaskN.SetPriority( ( int )tbb::priority_t::priority_normal );
tbb::task::enqueue( TaskN, tbb::priority_t::priority_normal );

CMyTask &TaskH = *new( tbb::task::allocate_root() ) CMyTask( i*10+3, "high" );
TaskH.SetPriority( ( int )tbb::priority_t::priority_high );
tbb::task::enqueue( TaskH, tbb::priority_t::priority_high );
}
//*/

// Test-Case SK2
///*
CMyTask *pTask[9] = {NULL };

for( int i = 0; i < 9; i += 3 )
{
pTask[i ] = new( tbb::task::allocate_root() ) CMyTask( i*10+1, "low" );
pTask[i ]->SetPriority( ( int )tbb::priority_t::priority_low );
tbb::task::enqueue( *pTask[i ], tbb::priority_t::priority_low );

pTask[i+1] = new( tbb::task::allocate_root() ) CMyTask( i*10+2, "normal" );
pTask[i+1]->SetPriority( ( int )tbb::priority_t::priority_normal );
tbb::task::enqueue( *pTask[i+1], tbb::priority_t::priority_normal );

pTask[i+2] = new( tbb::task::allocate_root() ) CMyTask( i*10+2, "high" );
pTask[i+2]->SetPriority( ( int )tbb::priority_t::priority_high );
tbb::task::enqueue( *pTask[i+2], tbb::priority_t::priority_high );
}
//*/

printf( "Initialization completed\n" );
}

[SergeyKostrov]

>>- Summary: Tasks with priority 'normal' ( enum value 1073741822 ) are executed first. Since on MacOS
>> tasks with priority 'high' are executed first I could assume that there is a portability issue
>> but so farit is not clear what is wrong. Enum values for prioritiesare as follows:
>> low = 536870911
>> normal = 1073741822
>> high = 1610612733
>> Since all objects of CMyTask are saved in some container it would be nice to find a way of
>>sorting the containerby priorities of tasksin descending order and thentorun
>> Test-Cases.

Hi Anton,

What do you think? I'm not absolutely confident in some portability issuebut it is clear that on different
OSs thereis adifferent execution order of tasks.

Best regards,
Sergey

[SergeyKostrov]

Quoting Sergey Kostrov

Quoting Raf Schietekat

Confirmed with tbb40_278oss (update 2 if I'm not mistaken) on x86/Linux/g++.

Some required changes were obvious, but does your compiler really accept "tbb::priority_t::priority_normal"?

I'm currently testing a Test-Case #1 andI don't think that an issue is related to this. It looks like TBB uses a
'LIFO' approach when executing created tasks but I can bewrong here. I'm still investigating.

Regarding 'LIFO' - my assumption is wrong. Tasks with 'normal' priorities are always executed first on a
Windows platform.

[Anton_M_Intel]

Hi. Thank you for the confirmation of the bug. We are working to fix other issues also related to the priorities in the scheduler, and will take this one into account of course.

It may be not a portability issue since I tested it with my working copy, not with a TBB release you are using..

[SergeyKostrov]

Quoting Anton Malakhov (Intel)

Hi. Thank you for the confirmation of the bug.

[SergeyK] It looks like this is a feature of the TBB library anda confirmation\explanation is needed.

We are working to fix other issues also related to the priorities in the scheduler, and will take this one into account of course.

[SergeyK] Please take a look at my "workaround" and correct me if I'm wrong because too much
"fuzzy" C/C++ codes in the TBB.I couldn't look everywhere andI don't know if it could
affect something else.

It may be not a portability issue since I tested it with my working copy, not with a TBB release you are using..

Here is a "workaround":

scheduler_common.h

...
static const intptr_t num_priority_levels = 3;

// static const intptr_t normalized_normal_priority = (num_priority_levels - 1) / 2;
static const intptr_t normalized_normal_priority = 2;// priority_high
...

A variable 'normalized_normal_priority' by default was initialized to '1':

( 3 - 1 ) / 2 = 1 and it corresponds to 'normal' priority

In my "workaround" I've changed the variable in the sources and then I've re-built the TBB library.
A runtime modificationis also possible, for example, with some global function or with a simplemodification
of the variable ( don't forget that it has a 'const' specificator).

ATest-Case SK1 produces that output on my development computer. Tryto "play" with the "workaround"
in order to confirm that it works on your computer.

[RafSchietekat]

I'm holding out for a reasoned solution instead.