Классические задачи синхронизации

Лекция 7. Классические задачи синхронизации. 2 часа.

Классические задачи синхронизации. Задача об обедающих философах, читатели-писатели, проблема спящего брадобрея [6: 245-249; 7: 150-157]

Проблема обедающих философов. Сформулирована в 1965 году Дейкстрой. Пять философов сидят за круглым столом и у каждого есть тарелка со спагетти. Чтобы пообедать, необходимо две вилки. Между каждыми тарелками лежит по одной вилке. Философы в течение дня размышляют и обедают. Когда философ голоден, он берет правую вилку, затем левую, съедает спагетти, кладет вилки и какое-то время размышляет. Однако, если философы подойдут к столу одновременно, и одновременно возьмут правые вилки, никто из них не сможет начать кушать: нет ни одной свободной вилки. Произошла взаимоблокировка. Фактически каждый из процессов (философов) захватил часть критического ресурса (одну из двух вилок). Решение:

#define N 5// число философов

#define LEFT (i+N)%N                  // левый сосед философа i

#define RIGHT (I+1)%N                // правый сосед философа i

#define THINKING 0                      // думает

#define HUNGRY 1                         // голодает

#define EATING 2                           // ест

typedef int semaphore;

int state[N];                                     // состояния философов

semaphore mutex=1;                     // взаимное исключение для критич. обл.

semaphore s[N];                                            // семафоры для каждого философа

void philosopher(int i)                   // процессы для философов

{while(1)

{think();                                      // размышляет

  take_forks(i);                           // берет вилки

  eat();                                         // ест

  put_forks();}}                          // кладет вилки

void take_forks(int i)                      // взятие вилки

{P(&mutex);                                     // закрыть мьютекс

  state[i]=HUNGRY;                       // состояние философа – нужен ресурс

  test(i);                                             // попытка получить вилки

  V(&mutex);                                    // открытие мьютекса, выход из КС

  P(&s[i]);}                                       // философ в ожидании или использовании вилок

void put_forks(int i)                       // отпустить вилки

{P(&mutex);                                     // вход в КС

  state[i]=THINKING;                    // перестал есть, размышляет

  test(LEFT);                                     // может ли есть сосед справа

  test(RIGHT);                                  // может ли есть сосед слева

  V(&mutex);}                                   // выход из КС

void test(int i)                                  // если хочет есть и соседи не едят

{if(state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING)

{state[i]=EATING;                      // есть

  V(&s[i]);}}                                  // философ не использует и не требует вилок

Задача читатели-писатели. Ситуация типична при доступе к БД. Например, бронирование билетов. Чтение может быть разрешено одновременно, однако при записи доступ для всех процессов, в. т.ч. и на чтение, должен быть закрыт. Решение:

typedef int semaphore;

semaphore mutex = 1;                   // контроль доступа к переменной rc

semaphore db=1;                           // контроль доступа к базе данных

int rc=0;                                           // кол-во процессов читающих или желающих читать

void reader(void)                                          // процесс читатель

{while(1)

{P(&mutex);                   // закрыть доступ к счетчику читателей

  rc++;                                           // увеличить его

  if (rc==1) P(&db);// если процесс первый, закрыть доступ к БД

  V(&mutex);                                  // открыть доступ к счетчику

  read_database();                       // чтение БД

  P(&mutex);               // закрыть доступ к счетчику

  rc=rc-1;                                      // уменьшить его

  if (rc==0) V(&db);                    // если нет других читателей (процесс последний) открыть доступ к БД

  V(&mutex);                                 // открыть доступ к счетчику

  use_read_data();}}                   // использование данных

void writer(void)                                            // процессы писатели

{while(1)

{make_data();                              // подготовка данных к записи

  P(&db);                                       // закрыть доступ

  write_database();                      // записать данные

  V(&db); }}                                   // открыть доступ

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

Пусть одновременно начали работу 2 читателя и 1 писатель. Ч1 успевает первым получить доступ к счетчику rc, наращивает его. Ч2 ожидает доступа к rc. Ч1 пытается получить доступ к БД, однако писатель успевает получить доступ 1.  Ч1 блокируется. Ч2 продолжает ожидать доступа к счетчику, поскольку он все еще закрыт. П1 записывает данные и открывает доступ к БД. Ч1 получает доступ, открывает доступ к счетчику, читает данные. Ч2 разблокируется, получает доступ к счетчику, увеличивает его. Поскольку rc=2, блокировки на БД не происходит,  хотя доступ к БД закрыт. Ч1 заканчивает чтение, уменьшает счетчик, однако БД не открывает, поскольку rc=1. Ч2 читает данные, уменьшает счетчик, открывает доступ к БД.

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

typedef int semaphore;

semaphore mutex = 1;                   // контроль доступа к переменной rc

semaphore db=1;                           // контроль доступа к базе данных

semaphore mutexwr=1;                 // контроль доступа если работает писатель

int rc=0;                                           // кол-во процессов читающих или желающих читать

void reader(void)                                          // процесс читатель

{while(1)

{P(&mutexwr);                             // если есть писатель, доступ будет закрыт

  P(&mutex);               // закрыть доступ к счетчику читателей

  rc++;                                           // увеличить его

  if (rc==1) P (&db);// если процесс первый, закрыть доступ к БД

  V(&mutexwr);

  V(&mutex);                                 // открыть доступ к счетчику

 read_database();                       // чтение БД

  P(&mutex);                                  // закрыть доступ к счетчику

  rc=rc-1;                                      // уменьшить его

  if (rc==0) V(&db);                    // если нет других читателей (процесс последний) открыть доступ к БД

  V(&mutex);                   // открыть доступ к счетчику

  use_read_data();}}                   // использование данных

void writer(void)                                            // процессы писатели

{while(1)

{make_data();                              // подготовка данных к записи

  P(&mutexwr);                             // блокировка доступа читателям

  P(&db);                                       // закрыть доступ

  write_database();                      // записать данные

  V(&mutexwr);

  V(&db);}}               // открыть доступ

Пусть одновременно начали работу 3 читателя и 1 писатель. Ч1 успевает первым получить доступ к счетчику rc, наращивает его. Ч2 ожидает доступа к rc. Ч1 получает доступ к БД, открывает доступ к счетчику. Ч2 получает доступ к счетчику, изменяет его, получает доступ к БД не  проверяя семафор, открывает доступ к счетчику. П1 блокирует доступ новых читателей, и пытается получить доступ к базе. Поскольку она занята, он переходит в ожидание. Ч3 пытается получить доступ к счетчику, однако блокируется на семафоре mutexwr. Ч1 читает данные, изменяет счетчик, но поскольку в работе остается Ч2, доступ к БД не изменяется. П1 по прежнему блокирован и Ч3 также. Ч2 читает данные, поскольку он последний из читателей, работающих с БД, то после получения доступа к счетчику, и изменения его, он открывает доступ к БД. П1 получает доступ , производит запись, открывает доступ читателям. Ч3 проходит семафор mutexwr, но блокируется на доступе к счетчику. Только когда Ч2 открывает доступ, Ч3 получает его, однако, поскольку это уже первый процесс, читающий данные, проверяется семафор доступа к БД. Она закрыта. Ч3 блокируется. П1 открывает доступ к БД, Ч3 получает его. Дальше все элементарно.

Недостаток решения в том, что снижается производительность