about summary refs log tree commit diff
path: root/nptl/DESIGN-condvar.txt
blob: 303807be6d049c070be16fd50cef7a5fca615301 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
Conditional Variable pseudocode.
================================

       int pthread_cond_timedwait (pthread_cond_t *cv, pthread_mutex_t *mutex);
       int pthread_cond_signal    (pthread_cond_t *cv);
       int pthread_cond_broadcast (pthread_cond_t *cv);

struct pthread_cond_t {

   unsigned int lock:

         internal mutex

   unsigned int nr_wakers:

         number of threads signalled to be woken up.

   unsigned int nr_sleepers:

         number of threads waiting for the cv.

}

#define ALL_THREADS (1 << (BITS_PER_LONG-1))

cond_wait_timeout(cv, mutex, timeout):
{
   lll_lock(cv->lock);
   mutex_unlock(mutex);

   cv->nr_sleepers++;
   for (;;) {

       if (cv->nr_wakers) {
           cv->nr_wakers--;
           break;
       }
       val = cv->nr_wakers;

       lll_unlock(cv->lock);

       ret = FUTEX WAIT (cv->nr_wakers, val, timeout)

       lll_lock(cv->lock);

       if (ret == TIMEOUT)
         break;
       ret = 0;
   }
   if (!--cv->nr_sleepers)
     cv->nr_wakers = 0; /* no memory of wakeups */
   lll_unlock(cv->lock);
   mutex_lock(mutex);

   return ret;
}

cond_signal(cv)
{
   int do_wakeup = 0;

   lll_lock(cv->lock);
   if (cv->nr_sleepers) {
     if (!++cv->nr_wakers) /* overflow detection for the nutcase */
       cv->nr_wakers = ALL_THREADS;
     do_wakeup = 1;
   }
   lll_unlock(cv->lock);
   if (do_wakeup)
     FUTEX WAKE (cv->nr_wakers, 1)
}

cond_broadcast(cv)
{
   int do_wakeup = 0;

   lll_lock(cv->lock);
   if (cv->nr_sleepers) {
     cv->nr_wakers |= ALL_THREADS;
     do_wakeup = 1;
   }
   lll_unlock(cv->lock);
   if (do_wakeup)
     FUTEX WAKE (cv->nr_wakers, ALL_THREADS);
}

weaknesses of the implementation:

 it might generate spurious wakeups in the broadcast case, but those are
 allowed by POSIX.