[Bug nptl/4274] Performance issue: pthread_cond_signal() causes three context switches instead of one

["bart dot vanassche at gmail dot com" <sourceware-bugzilla at sourceware dot org>]

------- Additional Comments From bart dot vanassche at gmail dot com  2007-08-28 10:14 -------
(In reply to comment #8)
> Whatever you think you are measuring has nothing to do with glibc.  Should there
> actually be extra wake-ups this happens entirely in the kernel.  glibc uses
> FUTEX_WAKE_OP which prevents unnecessary delays.  If the kernel schedules
> freshly woken threads right away before finishing the futex call something of
> course can go wrong.  But all this happens in the kernel.  glibc gives the
> kernel all the information it needs to avoid any problem.
> 
> Talk to the kernel people.

So what we agree about is that one context switch for waking up another thread
would be better than two or three. What we don't agree about is where this
should be solved. My opinion about this is as follows:
- This is a performance issue that can be solved in glibc.
- This is a performance issue that should be solved in glibc and not in the kernel.

Let me further clarify this by starting from typical POSIX threads code for
waking up a thread via a signal:

Thread 1:
  pthread_mutex_lock(&m);
  pthread_cond_wait(&cv, &m);
  pthread_mutex_unlock(&m);

Thread 2:
  pthread_mutex_lock(&m);
  pthread_cond_signal(&cv);
  pthread_mutex_unlock(&m);

Let us assume that thread two obtains a lock on mutex m after thread 1 entered
pthread_cond_wait(). In that case thread 2 will wake up thread 1 twice instead
of just one time: after pthread_cond_signal() wakes up pthread_cond_wait() via
the futex() system call, pthread_cond_wait() will try to lock the mutex m. But
since the mutex m is still locked at that time, thread 2 will be scheduled again
until it unlocks mutex m via another futex() system call. At that time thread 1
will be rescheduled. Or: three context switches have happened where one context
switch would have been sufficient. At least this is what I assume that happens.

My proposal is to change the implementation of the POSIX threads mutex and
condition variable primitives in such a way that waking up another thread is
deferred from pthread_cond_wait(cv) or pthread_cond_broadcast(cv) until
pthread_mutex_unlock(m) is called. And this for the mutex m that was associated
to condition variable cv via one or more threads calling pthread_cond_wait(). I
know this is nontrivial, and that several cases have to be considered:
- signal is sent from same process as the process waiting in pthread_cond_wait().
- signal is sent from another process than the one waiting in pthread_cond_wait().
- signal is sent to condition variable cv while the mutex m from the call to
pthread_cond_wait(cv, m) is locked.
- signal is sent to condition variable cv while the mutex m from the call to
pthread_cond_wait(cv, m) is not locked (software that shows such runtime
behavior is highly suspicious since this is a race condition, but the POSIX
standard does not forbid this kind of behavior).
- Note: in POSIX threads software where signals are only sent while the
appropriate mutex is held, there is exactly one mutex m associated with each
condition variable cv for threads blocked in pthread_cond_wait(cv, m).

One way to implement a solution is to keep track for each mutex m of all
condition variables cv for which a thread is blocked in pthread_cond_wait(cv,
m). In case only one process is involved this could be implemented by modifying
the pthread_cond_wait() implementation such that it allocates space for a list
element on the stack of the thread it is executed on. These list elements can
than be linked together via pointers, with a pointer to the head of the list
stored in the mutex data structure. When pthread_cond_signal(cv2) is called with
a lock held on mutex m2 by the same thread, this information is stored in the
data structures of cv2 and m2. At the time pthread_mutex_unlock() is called this
last function can then wake up the appropriate threads blocked in
pthread_cond_wait(). Or: no thread wakeup by pthread_cond_signal(), only by
pthread_mutex_unlock(). This optimization would have been a lot easier to
implement if the POSIX threads standard would have defined one single operation
pthread_cond_signal_and_mutex_unlock(cv, m).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|WONTFIX                     |


http://sourceware.org/bugzilla/show_bug.cgi?id=4274

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.