C++ – How to give priority to privileged thread in mutex locking

cc++11multithreadingmutex

First of all: I am completely a newbie in mutex/multithread programming, so
sorry for any error in advance…

I have a program that runs multiple threads. The threads (usually one per
cpu core) do a lot of
calculation and "thinking" and then sometimes they decide to call a
particular (shared) method that updates some statistics.
The concurrency on statistics updates is managed through the use of a mutex:

stats_mutex.lock();
common_area->update_thread_stats( ... );
stats_mutex.unlock();

Now to the problem.
Of all those threads there is one particular thread that need almost
realtime priority, because it's the only thread that actually operates.

With "almost realtime priority" I mean:

Let's suppose thread t0 is the "privileged one" and t1….t15 are the normal
ones.What happens now is:

Thread t1 acquires lock.
Thread t2, t3, t0 call the lock() method and wait for it to succeed.
Thread t1 calls unlock()
One (at random, as far as i know) of the threads t2, t3, t0 succeeds in acquiring
the lock, and the other ones continue to wait.

What I need is:

Thread t1 acquire lock.
Thread t2, t3, t0 call the lock() method and wait for it to succeed.
Thread t1 calls unlock()
Thread t0 acquires lock since it's privileged

So, what's the best (possibly simplest) method to do this thing?

What I was thinking is to have a bool variable called
"privileged_needs_lock".

But I think I need another mutex to manage access to this variable… I dont
know if this is the right way…

Additional info:

my threads use C++11 (as of gcc 4.6.3)
code needs to run on both Linux and Windows (but tested only on Linux at the moment).
performance on locking mechanism is not an issue (my performance problem are in internal thread calculations, and thread number will always be low, one or two per cpu core at maximum)

Any idea is appreciated.
Thanks

The below solution works (three mutex way):

#include <thread>
#include <iostream>
#include <mutex>
#include "unistd.h"

std::mutex M;
std::mutex N;
std::mutex L;

void lowpriolock(){
  L.lock();
  N.lock();
  M.lock();
  N.unlock();
}

void lowpriounlock(){
  M.unlock();
  L.unlock();
}

void highpriolock(){
  N.lock();
  M.lock();
  N.unlock();
}

void highpriounlock(){
  M.unlock();
}

void hpt(const char* s){
  using namespace std;
  //cout << "hpt trying to get lock here" << endl;
  highpriolock();
  cout << s << endl;
  sleep(2);
  highpriounlock();
}

void lpt(const char* s){
  using namespace std;
  //cout << "lpt trying to get lock here" << endl;
  lowpriolock();
  cout << s << endl;
  sleep(2);
  lowpriounlock();
}

int main(){
std::thread t0(lpt,"low prio t0 working here");
std::thread t1(lpt,"low prio t1 working here");
std::thread t2(hpt,"high prio t2 working here");
std::thread t3(lpt,"low prio t3 working here");
std::thread t4(lpt,"low prio t4 working here");
std::thread t5(lpt,"low prio t5 working here");
std::thread t6(lpt,"low prio t6 working here");
std::thread t7(lpt,"low prio t7 working here");
//std::cout << "All threads created" << std::endl;
t0.join();
t1.join();
t2.join();
t3.join();
t4.join();
t5.join();
t6.join();
t7.join();
return 0;
}

Tried the below solution as suggested but it does not work (compile with " g++ -std=c++0x -o test test.cpp -lpthread"):

#include <thread>
#include <mutex>

#include "time.h"
#include "pthread.h"

std::mutex l;

void waiter(){
  l.lock();
  printf("Here i am, waiter starts\n");
  sleep(2);
  printf("Here i am, waiter ends\n");
  l.unlock();
}

void privileged(int id){
  usleep(200000);
  l.lock();
  usleep(200000);
  printf("Here i am, privileged (%d)\n",id);
  l.unlock();  
}

void normal(int id){
  usleep(200000);
  l.lock();
  usleep(200000);
  printf("Here i am, normal (%d)\n",id);
  l.unlock();    
}

int main(){
  std::thread tw(waiter);
  std::thread t1(normal,1);
  std::thread t0(privileged,0);
  std::thread t2(normal,2);

  sched_param sch;
  int policy; 

  pthread_getschedparam(t0.native_handle(), &policy, &sch);
  sch.sched_priority = -19;
  pthread_setschedparam(t0.native_handle(), SCHED_FIFO, &sch);

  pthread_getschedparam(t1.native_handle(), &policy, &sch);
  sch.sched_priority = 18;
  pthread_setschedparam(t1.native_handle(), SCHED_FIFO, &sch);

  pthread_getschedparam(t2.native_handle(), &policy, &sch);
  sch.sched_priority = 18;
  pthread_setschedparam(t2.native_handle(), SCHED_FIFO, &sch);
  
  tw.join();
  t1.join();
  t0.join();
  t2.join();

  return 0;  
}

Best Answer

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

Related Solutions

C# – How to update the GUI from another thread

The simplest way is an anonymous method passed into Label.Invoke:

// Running on the worker thread
string newText = "abc";
form.Label.Invoke((MethodInvoker)delegate {
    // Running on the UI thread
    form.Label.Text = newText;
});
// Back on the worker thread

Notice that Invoke blocks execution until it completes--this is synchronous code. The question doesn't ask about asynchronous code, but there is lots of content on Stack Overflow about writing asynchronous code when you want to learn about it.

How efficient is locking an unlocked mutex? What is the cost of a mutex

I have the choice in between either having a bunch of mutexes or a single one for an object.

If you have many threads and the access to the object happens often, then multiple locks would increase parallelism. At the cost of maintainability, since more locking means more debugging of the locking.

How efficient is it to lock a mutex? I.e. how much assembler instructions are there likely and how much time do they take (in the case that the mutex is unlocked)?

The precise assembler instructions are the least overhead of a mutex - the memory/cache coherency guarantees are the main overhead. And less often a particular lock is taken - better.

Mutex is made of two major parts (oversimplifying): (1) a flag indicating whether the mutex is locked or not and (2) wait queue.

Change of the flag is just few instructions and normally done without system call. If mutex is locked, syscall will happen to add the calling thread into wait queue and start the waiting. Unlocking, if the wait queue is empty, is cheap but otherwise needs a syscall to wake up one of the waiting processes. (On some systems cheap/fast syscalls are used to implement the mutexes, they become slow (normal) system calls only in case of contention.)

Locking unlocked mutex is really cheap. Unlocking mutex w/o contention is cheap too.

How much does a mutex cost? Is it a problem to have really a lot of mutexes? Or can I just throw as much mutex variables in my code as I have int variables and it doesn't really matter?

You can throw as much mutex variables into your code as you wish. You are only limited by the amount of memory you application can allocate.

Summary. User-space locks (and the mutexes in particular) are cheap and not subjected to any system limit. But too many of them spells nightmare for debugging. Simple table:

Less locks means more contentions (slow syscalls, CPU stalls) and lesser parallelism
Less locks means less problems debugging multi-threading problems.
More locks means less contentions and higher parallelism
More locks means more chances of running into undebugable deadlocks.

A balanced locking scheme for application should be found and maintained, generally balancing the #2 and the #3.

(*) The problem with less very often locked mutexes is that if you have too much locking in your application, it causes to much of the inter-CPU/core traffic to flush the mutex memory from the data cache of other CPUs to guarantee the cache coherency. The cache flushes are like light-weight interrupts and handled by CPUs transparently - but they do introduce so called stalls (search for "stall").

And the stalls are what makes the locking code to run slowly, often without any apparent indication why application is slow. (Some arch provide the inter-CPU/core traffic stats, some not.)

To avoid the problem, people generally resort to large number of locks to decrease the probability of lock contentions and to avoid the stall. That is the reason why the cheap user space locking, not subjected to the system limits, exists.