How to Give Priority to Privileged Thread in Mutex Locking

How to give priority to privileged thread in mutex locking?

I can think of three methods using only threading primitives:

Triple mutex

Three mutexes would work here:

data mutex ('M')
next-to-access mutex ('N'), and
low-priority access mutex ('L')

Access patterns are:

Low-priority threads: lock L, lock N, lock M, unlock N, { do stuff }, unlock M, unlock L
High-priority thread: lock N, lock M, unlock N, { do stuff }, unlock M

That way the access to the data is protected, and the high-priority thread can get ahead of the low-priority threads in access to it.

Mutex, condition variable, atomic flag

The primitive way to do this is with a condition variable and an atomic:

Mutex M;
Condvar C;
atomic bool hpt_waiting;

Data access patterns:

Low-priority thread: lock M, while (hpt_waiting) wait C on M, { do stuff }, broadcast C, unlock M
High-priority thread: hpt_waiting := true, lock M, hpt_waiting := false, { do stuff }, broadcast C, unlock M

Mutex, condition variable, two non-atomic flag

Alternatively you can use two non-atomic bools with a condvar; in this technique the mutex/condvar protects the flags, and the data is protected not by a mutex but by a flag:

Mutex M;
Condvar C;
bool data_held, hpt_waiting;
Low-priority thread: lock M, while (hpt_waiting or data_held) wait C on M, data_held := true, unlock M, { do stuff }, lock M, data_held := false, broadcast C, unlock M
High-priority thread: lock M, hpt_waiting := true, while (data_held) wait C on M, data_held := true, unlock M, { do stuff }, lock M, data_held := false, hpt_waiting := false, broadcast C, unlock M

C++ mutex locking thread priority

Thread priority says how much time the thread gets on the CPU as determined by the scheduler, which will preferentially schedule higher priority threads - it doesn't affect the behaviour of mutexes, and I'm not aware of any means of making it do so.

How to allow certain threads to have priority in locking a mutex use PTHREADS

As I understand it, the only way you can truly guarantee this would be to write a lock that works like that yourself. However @xryl669's answer that suggests using thread priority and priority inheritance is certainly worthy of consideration if it works for your use case.

To implement it yourself, you will need condition variables and counts of the number of waiting low / high priority threads.

In terms of the concepts and APIs you'll need, it is relatively similar to implementing a read/write lock (but the semantics you need are completely different, obviously - but if you understood how the r/w lock is working, you'll understand how to implement what you want).

You can see an implementation of a read write lock here:

http://ptgmedia.pearsoncmg.com/images/0201633922/sourcecode/rwlock.c

In the lower priority threads, you'd need to wait for high priority threads to finish, in the same way readers wait for writers to finish.

(The book the above code is taken from it also a great posix threads book btw, http://www.informit.com/store/product.aspx?isbn=0201633922 )

mutex lock priority

If both threads are equal priority, there is no such guarantee by standard mutex implementations. Some OS's have a lis of "who's waiting", and will pick the "longest waiting" when you release something, but that is an implementation detail, not something you can reliably depend on.

And imagine that you have two threads, each running something like this:

m.lock();

(...)

m.unlock();
(...)    // Clearly not the same code as above (...)
m.lock();

(...)    // Some other code that needs locking against updates. 

m.unlock();

Would you want the above code to switch thread on the second lock, every time?

By the way, if both threads run with lock for the entire loop, what is the point of a lock?

Give access to a resource based on thread priority/privilege

As mentioned in comments its a complicated task.

One way to do it will be to create a class like this one:

class UART_access_manager

{

typedef std::multimap<int, dispatch_semaphore_t> priority_map_t;
public:

 UART_access_manager();
~UART_access_manager();
void access_manager(unsigned int prio, dispatch_semaphore_t pSem);

private:

void amInext(unsigned int prio);
void process_priority(unsigned int prio);
void priority_locker(unsigned int prio);
void priority_unlocker(unsigned int prio);

int count;
std::mutex data_mtx, priority_0_mtx, mtx;
priority_map_t priority_map;
};

note I build the test on OSX and un-named semaphore can't be used, I didn't check if dispatch is available on other OS (probably not as its an apple lib).

UART_access_manager::UART_access_manager()

{

}
UART_access_manager::~UART_access_manager()
{

}

 /*********************************************************************
  *
  * Function:        void UART_access_manager::access_manager(unsigned

int prio, dispatch_semaphore_t pSem)
 *
 * Description:     add an UART access request to the queue based on priority & start process based on type
 *
 * Notes:           0 is highest
 *
 * Returns:         none
 *
 *********************************************************************/

void UART_access_manager::access_manager(unsigned int prio, dispatch_semaphore_t pSem)//, add parameters at will
 {
 int counter = 1; //debug only
 while (counter) //should check for termination criteria
 {
    //check if something was pushed on the file descriptor

    if( counter == 10) //add run condition
    {
        counter = 0; //debug

        priority_locker(prio);

        priority_map_t::iterator it = priority_map.insert(std::pair<int, dispatch_semaphore_t>(prio, pSem) );
        printf("\n thread with priority %d added to queue(size %lu)", prio, priority_map.size());
        amInext(prio);

        priority_unlocker(prio);

        while(dispatch_semaphore_wait(pSem, DISPATCH_TIME_NOW) != 0){};

        priority_locker(prio);
        // do the actual job
        process_priority(prio);
        // done, remove yourself
        priority_map.erase(it);
        if( ! priority_map.empty() )
        {
            // let next guy run:
            dispatch_semaphore_signal((priority_map.begin()->second));
        }
        priority_unlocker(prio);
    }
    else
    {
        std::this_thread::sleep_for(std::chrono::milliseconds(50)); //test purpose only
        counter++;
    }

 }
}

/*********************************************************************
 *
 * Function:       void UART_access_manager::amInext(unsigned int prio)
 *
 * Description:    check if current priority has to run next or not
 *
 * Notes:           0 is highest
 *
 * Returns:        none
 *
 *********************************************************************/
 void UART_access_manager::amInext(unsigned int prio)
{

 if(priority_map.begin()->first == prio) dispatch_semaphore_signal(priority_map.begin()->second);
}

/*********************************************************************
*
* Function:        void UART_access_manager::process_priority(unsigned 
int prio)
*
* Description: TODO
*********************************************************************/
void UART_access_manager::process_priority(unsigned int prio)
{
 printf("\n    Priority_%d running \n",prio);
 //TODO
}

/*********************************************************************
*
* Function:       void UART_access_manager::priority_locker(unsigned 
int prio)
*
 * Description:     lock mutex in a way to guarantee priority event 
 to 
 *                  get the fastest lock possible
 *
 * Notes:           0 is highest
 ******************************************************************/
 void UART_access_manager::priority_locker(unsigned int prio)
 {
 //Low-priority threads: lock mtx, lock priority_0_mtx, lock data_mtx, 
  unlock priority_0_mtx,
 //High-priority thread: lock priority_0_mtx, lock data_mtx, unlock 
  priority_0_mtx,
  //this will insure that max priority level get privileged access to 
 the data

if(!prio)
 {
    priority_0_mtx.lock();
    data_mtx.lock();
    priority_0_mtx.unlock();
 }
else
 {
    mtx.lock();
    priority_0_mtx.lock();
    data_mtx.lock();
    priority_0_mtx.unlock();
 }
}

/*********************************************************************
 *
 * Function:        void 
 UART_access_manager::priority_unlocker(unsigned int prio)
 *
 * Description:     unlock mtx based on the mutex locked by the 
 priority level
 *
 * Notes:           0 is highest
 *
 * Returns:         none
 *
 *********************************************************************/
void UART_access_manager::priority_unlocker(unsigned int prio)
{
if(!prio)
 {
    data_mtx.unlock();
 }
else
 {
    mtx.unlock();
    data_mtx.unlock();
 }
}

Code is verbose to be easy to understand, and will do nothing as it, you are progressing nicely, see it as a assignment, if you have any question don't hesitate to comment, I'll reply.

(HS: what are you trying to do ?)

Things you'll learn:
std::multimap
std::mutex
semaphores
classes

Create a Mutex with Priority Inheritance in C#

That is, at worst, a short term priority inversion problem. Unless, of course, the low priority thread A holds the lock for a very long time. Thread C can't make progress because it's waiting on the lock. As Hans Passant said in his answer, the thread scheduler detects this problem and boosts the priority of the lower-priority thread so that it can release the lock. The first MSDN link he posted explains it quite well.

If your low priority thread A holds the lock for a very long time (i.e. it's doing complex calculations on the list) and that's causing problems in your application, then you can do one of the following:

Increase the priority of thread A
Have thread A lock the list, get an item, unlock the list, and then process the item
Lock the list, make a copy, unlock the list, and process the copy.
some variation on or combination of the above

In any case, the problem isn't the lock. The problem is coding the program so that a high-priorty thread can be left waiting for a long time on a data structure that a lower priority thread needs exclusive access to.

Do condition variables provide priority for mutex locking?

It's deliberately unspecified by the standard to allow freedom of implementation. Specifically, C++11 §30.5.1 Class condition variable [thread.condition.condvar] states:

void notify_one() noexcept;
⁷ Effects: If any threads are blocked waiting for *this, unblocks one of those threads.
void notify_all() noexcept;
⁸ Effects: Unblocks all threads that are blocked waiting for *this.

There is no claim made about preference/fairness/priority to any thread(s), simply "unblocks one" or "unblocks all."

How to Give Priority to Privileged Thread in Mutex Locking