SCHED_FIFO and pthread_cond_broadcast

SCHED_FIFO and pthread_cond_broadcast

[Tadeus Prastowo]

[-- Attachment #1: Type: text/plain, Size: 1578 bytes --]

Hello,

AFAIK, POSIX specifies that pthread_cond_broadcast should wake up
waiting threads in their scheduling orders.  So, in the attached
program, main is expected to always return 1 because:

1. When main performs pthread_cond_broadcast(&b) in line 52, the
condition variable b already has threads task_1 and task_2 waiting.

2. Both task_1 and task_2 are scheduled using SCHED_FIFO such that
task_2 has a priority higher than task_1.

3. Since pthread_cond_broadcast wakes up waiting threads in their
scheduling orders, task_2 runs first and sets the value to be returned
to 2 and then task_1 runs and sets the value to be returned to 1.

4. The main function returns the last value written, which is 1.

However, I observe that the main function can return the value 2,
indicating that task_1 can run before task_2 despite POSIX
specification by the following steps:
$ gcc -O2 -o z z.c -pthread
$ sudo chown root z
$ sudo chmod u+s z
$ for ((i = 0; i < 1000000; ++i)); do ./z; if [ $? -eq 2 ]; then echo
It is two at $i; break; fi; done

When I follow the steps in my Ubuntu 16.04.6 (the output of uname -a
is: Linux Eus 4.15.0-75-generic #85~16.04.1-Ubuntu SMP Wed Jan 15
12:30:12 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux), which uses Glibc
2.23 (obtained by executing /lib/x86_64-linux-gnu/libc-2.23.so -v) and
GCC 9.2.1, I get an output like the following, indicating that task_1
can run before task_2:

It is two at 22718

Could someone help me figure out why pthread_cond_broadcast does not
respect the POSIX specification, please?

Thank you.

-- 
Best regards,
Tadeus

[-- Attachment #2: z.c --]
[-- Type: text/x-csrc, Size: 1598 bytes --]

#include <pthread.h>
#include <sched.h>

struct data {
  const int my_value;
  pthread_mutex_t *m;
  pthread_cond_t *b;
  pthread_cond_t *c;
  int *value;
};

void *fn(void *arg) {
  struct data *data = arg;
  pthread_mutex_lock(data->m);
  pthread_cond_signal(data->c);
  pthread_cond_wait(data->b, data->m);
  *data->value = data->my_value;
  pthread_mutex_unlock(data->m);
  return NULL;
}

int main() {
  pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
  pthread_cond_t b = PTHREAD_COND_INITIALIZER,
                 c = PTHREAD_COND_INITIALIZER;
  int value = 0;
  pthread_t task_1, task_2;
  pthread_attr_t attr_1, attr_2;
  struct sched_param prm_1, prm_2;
  struct data data_1 = {1, &m, &b, &c, &value},
              data_2 = {2, &m, &b, &c, &value};

  pthread_attr_init(&attr_1);
  pthread_attr_setinheritsched(&attr_1, PTHREAD_EXPLICIT_SCHED);
  pthread_attr_setschedpolicy(&attr_1, SCHED_FIFO);
  prm_1.sched_priority = sched_get_priority_min(SCHED_FIFO);
  pthread_attr_setschedparam(&attr_1, &prm_1);

  pthread_attr_init(&attr_2);
  pthread_attr_setinheritsched(&attr_2, PTHREAD_EXPLICIT_SCHED);
  pthread_attr_setschedpolicy(&attr_2, SCHED_FIFO);
  prm_2.sched_priority = sched_get_priority_max(SCHED_FIFO);
  pthread_attr_setschedparam(&attr_2, &prm_2);
  
  pthread_mutex_lock(&m);
  pthread_create(&task_1, &attr_1, fn, &data_1);
  pthread_cond_wait(&c, &m);
  pthread_create(&task_2, &attr_2, fn, &data_2);
  pthread_cond_wait(&c, &m);
  pthread_mutex_unlock(&m);
  
  pthread_cond_broadcast(&b);
 
  pthread_join(task_1, NULL);
  pthread_join(task_2, NULL);

  return value;
}

Re: SCHED_FIFO and pthread_cond_broadcast

[Adhemerval Zanella]

On 16/01/2020 19:59, Tadeus Prastowo wrote:
> Hello,
> 
> AFAIK, POSIX specifies that pthread_cond_broadcast should wake up
> waiting threads in their scheduling orders.  So, in the attached
> program, main is expected to always return 1 because:
> 
> 1. When main performs pthread_cond_broadcast(&b) in line 52, the
> condition variable b already has threads task_1 and task_2 waiting.
> 
> 2. Both task_1 and task_2 are scheduled using SCHED_FIFO such that
> task_2 has a priority higher than task_1.
> 
> 3. Since pthread_cond_broadcast wakes up waiting threads in their
> scheduling orders, task_2 runs first and sets the value to be returned
> to 2 and then task_1 runs and sets the value to be returned to 1.
> 
> 4. The main function returns the last value written, which is 1.
> 
> However, I observe that the main function can return the value 2,
> indicating that task_1 can run before task_2 despite POSIX
> specification by the following steps:
> $ gcc -O2 -o z z.c -pthread
> $ sudo chown root z
> $ sudo chmod u+s z
> $ for ((i = 0; i < 1000000; ++i)); do ./z; if [ $? -eq 2 ]; then echo
> It is two at $i; break; fi; done
> 
> When I follow the steps in my Ubuntu 16.04.6 (the output of uname -a
> is: Linux Eus 4.15.0-75-generic #85~16.04.1-Ubuntu SMP Wed Jan 15
> 12:30:12 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux), which uses Glibc
> 2.23 (obtained by executing /lib/x86_64-linux-gnu/libc-2.23.so -v) and
> GCC 9.2.1, I get an output like the following, indicating that task_1
> can run before task_2:
> 
> It is two at 22718
> 
> Could someone help me figure out why pthread_cond_broadcast does not
> respect the POSIX specification, please?
> 
> Thank you.
> 

It is a known issues and it is being tracked at BZ#11588 [1]. Currently
condition variable does not have PI awareness (such as userland wait
queues) and issues default futex wait/wake calls that do not take in 
consideration the waiters priority.

There were an interesting discussion about how to make condition variables
PI enabled [2], and currently there is no easy way to fulfil both POSIX
requirements and PI expectation with current kernel futex primitives.

Last Linux Plumbers Darren Hart presented an alternative conditional
variable implementation [3] that enables PI awareness, but it has its
own drawbacks (it has different semantic than POSIX conditional variable
at API level and afaik it is subject the very issue the new glibc
conditional variable implementation solved, discussed at [4]).

If your usage does not require all the POSIX specification about partial
ordering regarding signaling, you might consider use librtpi (your example
seems to show the expected output adapating to use it).

[1] https://sourceware.org/bugzilla/show_bug.cgi?id=11588
[2] https://www.youtube.com/watch?v=D1hGc8qJCcQ&list=UL-cj2JDu_Ac4&index=1208
[3] https://github.com/dvhart/librtpi
[4] https://www.austingroupbugs.net/view.php?id=609

Re: SCHED_FIFO and pthread_cond_broadcast

[Tadeus Prastowo]

Hello,

On Fri, Jan 17, 2020 at 4:09 PM Adhemerval Zanella
<adhemerval.zanella@linaro.org> wrote:
>
> It is a known issues and it is being tracked at BZ#11588 [1].

Thank you very much for your information.

> Currently
> condition variable does not have PI awareness (such as userland wait
> queues) and issues default futex wait/wake calls that do not take in
> consideration the waiters priority.
>
> There were an interesting discussion about how to make condition variables
> PI enabled [2], and currently there is no easy way to fulfil both POSIX
> requirements and PI expectation with current kernel futex primitives.
>
> Last Linux Plumbers Darren Hart presented an alternative conditional
> variable implementation [3] that enables PI awareness, but it has its
> own drawbacks (it has different semantic than POSIX conditional variable
> at API level and afaik it is subject the very issue the new glibc
> conditional variable implementation solved, discussed at [4]).
>
> If your usage does not require all the POSIX specification about partial
> ordering regarding signaling, you might consider use librtpi (your example
> seems to show the expected output adapating to use it).
>
> [1] https://sourceware.org/bugzilla/show_bug.cgi?id=11588
> [2] https://www.youtube.com/watch?v=D1hGc8qJCcQ&list=UL-cj2JDu_Ac4&index=1208
> [3] https://github.com/dvhart/librtpi
> [4] https://www.austingroupbugs.net/view.php?id=609

Thank you very much for your pointers.

Once again, thank you very much for your information.  I reallly appreciate it.

-- 
Best regards,
Tadeus