LINUX.ORG.RU
Форум — Development  

семафоры


0

0 

В школе задали написать упражнение в котором есть доступ к общему 
ресурсу (через shmget и т.п.) X писателей и Y читателей которые в 
бесконечных циклах делают sleep и пишут/читают.

При этом заданы такие условия: писатель в данный момент может писать 
только один (что логично), а читателей читать может сколько угодно, но 
не тогда когда кто-нибудь пишет.

И если с писателями все просто:

    struct sembuf sb[2];
    sb[0].sem_num = 0;
    sb[0].sem_op = -1;
    sb[0].sem_flg = SEM_UNDO;
    sb[1].sem_num = 1;
    sb[1].sem_op =  1;

.....

    for (i = 0; ; ++i) {
        ....
        semop(sem_id, &sb[0], 1);
        strcpy((char*) data, buf);
        semop(sem_id, &sb[1], 1);
    }

То с читателями я что-то зашел в какой-то тупик. Читатели могут
читать одновременно, так что вроде бы при помощи semctl можно
было бы проверить нет ли в данный момент писателя и висеть,
но этого явно недостаточно:

а) что если сразу после semctl нарисуется писатель?
б) писатель не должен входить в критическую секцию
пока там кто-то читает

Напрашивается еще один семафор, но как сделать так чтобы
читатели могли входить в довольном количестве пока
не войдет писатель?

Что-то я запутался совсем... RFH (Request For Help!)

Ответ на: комментарий от cvv

А можно подробнее? В условиях задачи боком упомянуты семафоры. На самом деле мне просто нужен rwlock, такой как например есть в последней Жабе. Как его написать при помощи семафоров я совсем не представляю.... Есди бы читатели были тоже синхронизованы между собой ок. Если бы данные были циклическим буфером то тоже понятно как сделать в принципе.

dissident ★★
() автор топика
Ответ на: комментарий от dissident

>А можно подробнее?

man fcntl

>Как его написать при помощи семафоров я совсем не представляю....

надо подобрать подходящий тип семафоров

cvv ★★★★★
() 

Могу предложить такой алгоритм (не мой): 
sem1, sem2 - семафоры. 
down(), up() - опустить, поднять семафор. 
int rc = 0 - переменная в разделяемой памяти (и писателей и читателей). 
изначально семафоры подняты. 

читатель: 

while (1) {
  down(sem1);
  ++rc;
  if (rc == 1)
    down(sem2);
  up(sem1);
  read_data();
  down(sem1);
  --rc;
  if (rc == 0)
    up(sem2);
  up(sem2);
} 

писатель: 

while (1) {
  down(sem2);
  write_data();
  up(sem2); 
} 

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

Legioner ★★★★★
()

У читателя в последней строчке цикла up(sem1); вместо up(sem2);

Legioner ★★★★★
()
Ответ на: комментарий от Legioner

Legioner:

Если по условию задачи можно получать значение семафора, то вместо rc можно использовать просто еще один семафор.

Die-Hard ★★★★★
()

2dissident (*) (20.12.2005 11:34:39):

Дык, ты понял все?

Задачка типичная, и просится в FAQ (как сделать WR lock на семафорах)

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

Алгоритм понял, с fcntl не до конца - нужно обязательно иметь файл? Или можно устанавливат блокировку на id, полученном через shmget? Хотел еще сегодня полюбопытствовать у автора задачи, но он таки не пришел.

Но в первой взятой с полки книжки про программирование в Unix (Брюс Молли) нашел решение похожей проблемы (правда там один писатель). Задача действительно классическая, не подумал об этом. Но спасибо за алгоритм и fcntl!

dissident ★★
() автор топика
Ответ на: комментарий от dissident

Иными словами:

Писатель:
[0] ждать пока num_writers станет нулем
[1] ждать пока num_readers станет нулем
[2] добавить 1 к num_writers
...
[2] вычесть 1 из num_writers

Читатель:
[0] ждать пока num_writers станет нулем
[1] добавить 1 к num_readers
...
[2] вычесть 1 из num_readers

Если semop(..) атомарна независимо от количества операций указанных в sembuf, то как-то примерно в таком ключе это должно работать. Я просто не обнаружил сразу этих операций "ждать пока" без изменения значения (sem_op = 0) и атомарности semop (разве что я неправ с этой атомарностью?). В этом случае все сильно упрощается и нет необходимости мудрить с алгоритмами.

А fcntl видимо имелся ввиду вместе со "вспомогательным файлом"?

dissident ★★
() автор топика
Ответ на: комментарий от dissident

>с fcntl не до конца - нужно обязательно иметь файл?

не файл а файловый дескриптор. вполне подойдёт кусок posix shared memory.

cvv ★★★★★
()
Ответ на: комментарий от dissident

2dissident:

semop действительно атомарна, и поэтому сложные алгоритмы на SysV семафорах писАть легко.

Но, заметь, это -- не _классические_ Дийстровские семафоры!

Die-Hard ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development