Справедливость: где это может быть лучше обработано?

Question

Я хотел бы поделиться своим практическим опытом в области мультипрограммирования здесь.

Вчера я написал мультипрограмму. Модификации разделяемых ресурсов были помещены в критические секции, защищенные P (mutex) и V (mutex), и эти критические секции кода были помещены в общую библиотеку. Библиотека будет использоваться параллельными приложениями (моими). ​​

У меня было три приложения, которые будут использовать общий код из библиотеки и делать свое дело независимо.

 my library
 ---------
 work_on_shared_resource
 {
  P(mutex)
  get_shared_resource
  work_with_it
  V(mutex)
 }
     ---------

 my application
 -----------
 application1
 {
   *[
      work_on_shared_resource
      do_something_else_non_ctitical
    ]
 }


 application2
 {
   *[
      work_on_shared_resource
      do_something_else_non_ctitical
    ]
 }


 application3
 {
   *[
      work_on_shared_resource
    ]
 }

 *[...] denote a loop.
 ------------

Мне пришлось запускать приложения на ОС Linux. У меня в голове нависла мысль о том, что ОС будет со всей честностью планировать все процессы, выполняемые под ним. Другими словами, он одинаково хорошо подарит всем процессам и их использование ресурсов.

Когда были запущены первые два приложения, они прекрасно работали без тупиковой ситуации. Но когда запускалось третье приложение, всегда третье получало ресурсы, но, поскольку оно ничего не делает в своей некритической области, оно чаще получает общий ресурс, когда другие задачи делают что-то еще. Таким образом, два других приложения были найдены почти полностью остановленными. Когда третье приложение было принудительно завершено, предыдущие два приложения возобновили свою работу, как и раньше.

Я думаю, это случай голодания, первые два приложения должны были голодать.

Теперь, как мы можем обеспечить справедливость?

Теперь я начал верить, что планировщик ОС невиновен и слеп. Это зависит от того, кто выиграл гонку; он получил самый большой кусок процессора и ресурсов.

Должны ли мы обеспечить честность пользователей ресурсов в коде критического раздела в библиотеке?

Или мы оставим это на усмотрение заявителей, чтобы обеспечить справедливость, будучи либеральным, а не жадным?

Насколько мне известно, добавление кода для обеспечения справедливости в общей библиотеке должно быть непосильной задачей. С другой стороны, вера в заявления также никогда не гарантирует 100% справедливости. Приложение, которое выполняет очень мало задач после работы с общими ресурсами, должно выиграть гонку, в то время как приложение, которое выполняет тяжелую обработку после своей работы с общими ресурсами, всегда будет голодать.

Какая лучшая практика в этом случае? Где мы обеспечиваем справедливость и как?

С уважением,
Сринивас Наяк

Answer 1

Проблема возникает из-за того, что процесс «приложения 3» продолжает выполняться после того, как он разблокирует мьютекс, поэтому он может немедленно получить его снова.

Вы можете реализовать справедливую систему очередей, в которой каждый поток добавляется в очередь, когда он блокируется, и первый поток в очереди всегда получает ресурс, когда становится доступным. Вы можете использовать условные переменные, чтобы построить это. Такой «честный» тикет, построенный на примитивах pthreads, может выглядеть так:

#include <pthread.h>

typedef struct ticket_lock {
    pthread_cond_t cond;
    pthread_mutex_t mutex;
    unsigned long queue_head, queue_tail;
} ticket_lock_t;

#define TICKET_LOCK_INITIALIZER { PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER }

void ticket_lock(ticket_lock_t *ticket)
{
    unsigned long queue_me;

    pthread_mutex_lock(&ticket->mutex);
    queue_me = ticket->queue_tail++;
    while (queue_me != ticket->queue_head)
    {
        pthread_cond_wait(&ticket->cond, &ticket->mutex);
    }
    pthread_mutex_unlock(&ticket->mutex);
}

void ticket_unlock(ticket_lock_t *ticket)
{
    pthread_mutex_lock(&ticket->mutex);
    ticket->queue_head++;
    pthread_cond_broadcast(&ticket->cond);
    pthread_mutex_unlock(&ticket->mutex);
}

Answer 2

Было проведено исследование по отзыву права собственности на мьютексы, чтобы обеспечить равный доступ или обнаружить и предотвратить тупик. Однако это действительно излишне и не стоит затраченных усилий, особенно потому, что оно открывает новую червь червей, например, как должна вести себя программа, если она находилась в процессе некоторых вычислений и потеряла право собственности на свои ресурсы. Приложение действительно должно гарантировать, что его различные потоки будут честно взаимодействовать друг с другом и потреблять ресурсы таким образом, чтобы они не зашли в тупик.

Я должен указать, что есть еще один вариант, хотя и немного другого типа, и это использование стиля параллельного программирования для передачи сообщений. При передаче сообщений синхронизация неявно присутствует в коммуникации; явной синхронизации не требуется, что помогает предотвратить такие ошибки.