Еще задачка :)

← →
Игорь Шевченко © (2004-04-22 11:05) [0]

Некий университет решил продемонстрировать свою политкорректность, применив известную доктрину верховного суда США "Равенство порознь равенством не является" не только к цвету кожи, но и к полу. Результатом этого решения явились совместные ванные комнаты в общежитиях. Тем не менее, в поддержку исторически сложившейся традиции университет постановляет, что если в ванной комнате есть женщина, то другая женщина может туда зайти, а мужчина не может, и наоборот. На двери ванной есть индикатор, показывающий, в каком из трех состояний находится ванная:
а) никого нет
б) в ванной женщины
в) в ванной мужчины
Напишите на своем любимом языке программирования следующие процедуры:
woman_wants_to_enter, man_wants_to_enter, woman_leaves, man_leaves.
Вы можете использовать любые счетчики и объекты синхронизации.

(с) Эндрю Таненбаум

← →
Sergey Masloff (2004-04-22 11:24) [1]

Ага я вчера как раз до этого места дочитал.
Кстати пока все примеры похоже приводятся так, что предполагается что каждая процедура выполняется в отдельном потоке? Потому что если в общем потоке то какие конфликты за ресурсы а если в разных процессах то с какого бодуна они переменные друг друга видят ;-) Это конечно можно смоделировать используя глобальные объекты ядра но... Хотя а как еще универсальные независящие от платформы описывать не знаю. Или я где-то глубоко не прав?

← →
Vlad Oshin © (2004-04-22 11:32) [2]

а где подвох?
ничего не понял

woman_wants_to_enter
1:
если (а или б)
то захожу
иначе {жду выхода М, goto 1}

man_wants_to_enter
1:
если (а или в)
то захожу
иначе {жду выхода Ж, goto 1}

woman_leaves, man_leaves
если помылся то выхожу

← →
Игорь Шевченко © (2004-04-22 11:46) [3]

Sergey Masloff (22.04.04 11:24)

> а если в разных процессах то с какого бодуна они переменные
> друг друга видят

Если переменные - это объекты синхронизации (например, семафоры), то прекрасно друг друга видят. С точки зрения реализации, кстати, не имеет значения, является ли каждый посетитель ванной комнаты отдельным процессом или отдельным потоком :))

← →
Юрий Зотов © (2004-04-22 12:21) [4]

Удобно использовать 2 семафора - один со счетчиком мужчин, другой - со счетчиком женщин (а вместе, они показывают состояние ванной комнаты). Остальное - дело техники.

← →
Юрий Зотов © (2004-04-22 12:39) [5]

> Игорь Шевченко

Вообще, симпатичная задачка, например, для курсового по теме "Моделирование систем массового обслуживания". И по сравнению с супермаркетом довольно-таки несложная.

← →
Игорь Шевченко © (2004-04-22 12:42) [6]

Юрий Зотов © (22.04.04 12:39)

У Таненбаума очень много забавных задач, причем, нетривиальных.

Еще хорошие задачки есть в книжке Гудмана и Хидетниеми: "Введение в разработку и анализ алгоритмов", тоже нетривиальные :)

← →
Reindeer Moss Eater © (2004-04-22 12:51) [7]

Двумя семафорами кажется не обойтись.
Тем более что у обеих maxcount должен быть 1.
Иначе как подошедшая женщина сможет проверить, что мужчин внутри нет?

← →
Reindeer Moss Eater © (2004-04-22 12:56) [8]

Первый посетитель должен сделать waitforsingleoblect семафору противоположного пола.
Если получилось - можно входить.
Но надо тут же сделать wait для своего семафора, что бы не входил человек противоположного пола и освободить семафор противоположного пола, что бы входили однополые студенты.

Второй судент того же пола кончно поймет, что входить можно, но waitforsingleobject для своего семафора поставит его в ступор, так как он уже занят.

← →
Reindeer Moss Eater © (2004-04-22 13:01) [9]

Ах, да.
Конечно же.
Ждать своего семафора с маленьким таймаутом

← →
Reindeer Moss Eater © (2004-04-22 13:02) [10]

Все равно нужен третий семафор - максимальное количество людей в ванной комнате.

← →
Юрий Зотов © (2004-04-22 13:05) [11]

> Reindeer Moss Eater © (22.04.04 12:51) [7, 8]

> у обеих maxcount должен быть 1.
Не 1, а предельная вместительность ванной.

> Иначе как подошедшая женщина сможет проверить, что мужчин
> внутри нет?
Ожидая, когда освободится мужской семафор. Вы же сами написали - WaitForSingleObject.

> Но надо тут же сделать wait для своего семафора,
Не Wait, а CreateSemaphore. А при выходе - CloseHandle.

← →
Verg © (2004-04-22 13:06) [12]

unit Room; interface uses Windows, Classes, SysUtils, SyncObjs; type TBathRoom = class private FCount : integer; procedure ProcessFCount; public Cs : TCriticalSection; MenWait, WMenWait : TEvent; constructor Create; destructor Destroy; override; procedure ManEnter(MSex : integer); procedure ManLeave; end; implementation constructor TBathRoom.Create; begin inherited Create; Cs := TCriticalSection.Create; MenWait := TEvent.Create(nil, true, true, ""); WMenWait := TEvent.Create(nil, true, true, ""); end; destructor TBathRoom.Destroy; begin MenWait.Free; WMenWait.Free; Cs.Free; inherited; end; procedure TBathRoom.ProcessFCount; begin if FCount < 0 then MenWait.ResetEvent else MenWait.SetEvent; if FCount > 0 then WMenWait.ResetEvent else WMenWait.SetEvent; end; procedure TBathRoom.ManEnter(MSex : integer); begin if MSex = 0 then exit; repeat Cs.Enter; try if (FCount = 0) or not ((FCount < 0) xor (MSex < 0)) then begin Inc(FCount, MSex); ProcessFCount; break; end; finally Cs.Leave; end; if MSex < 0 then WMenWait.WaitFor(INFINITE) else MenWait.WaitFor(INFINITE); until false; end; procedure TBathRoom.ManLeave; begin Cs.Enter; try if FCount <> 0 then if FCount < 0 then Inc(FCount) else Dec(FCount); ProcessFCount; finally Cs.Leave; end; end; end.

← →
Reindeer Moss Eater © (2004-04-22 13:12) [13]

> Иначе как подошедшая женщина сможет проверить, что мужчин
> внутри нет?
Ожидая, когда освободится мужской семафор. Вы же сами написали - WaitForSingleObject.

Создался мужской семафор. Счетчик его стал N. ( N > 0)

Подошла женщина, сделала ему wait, и у нее получилось. Так как в ванной было по крайней мере одно свободное место.
Разве нет?

← →
Reindeer Moss Eater © (2004-04-22 13:14) [14]

И только если мужской семафор создан со счетчиком 1, она поймет, что входить нельзя

← →
Reindeer Moss Eater © (2004-04-22 13:15) [15]

Кроме того, любой вышедший мужик (причем непоследний) и сделавший CloseHandle своему семафору даст свисток женщинам что входить можно.

← →
-SeM- (2004-04-22 13:17) [16]

> Подошла женщина, сделала ему wait, и у нее получилось

:)

← →
Паниковский © (2004-04-22 13:19) [17]

посадить бабушку на входе!

← →
Игорь Шевченко © (2004-04-22 13:20) [18]

Юрий Зотов © (22.04.04 13:05)

> Не 1, а предельная вместительность ванной.

Не указана в условии задачи, если только из здравого смысла исходить :))

← →
Reindeer Moss Eater © (2004-04-22 13:22) [19]

Все таки два "половых" семафора со счетчиком единица.
И дополнительный семафор если хотим ограничить кол-во моющихся.

← →
Verg © (2004-04-22 13:26) [20]

Там, в ProcessFCount при желании можно вложить предельную вместимость ванной.

← →
}|{yk © (2004-04-22 13:35) [21]

Опять...
Выучите например GPSS
Потом у вас такие задачки будут решаться за 1 минуту

← →
Тимохов © (2004-04-22 13:36) [22]

ничего не понимаю - что мешает заходящему человеку установить индикатор.
к двери подходит женщина:
1. если никого - входит и меняет состояние на "женщина"
2. если "женщина" - входит
3. если "мужик" - ждет

выходит:
1. если она была одна - меняет состоияние на "никого"
2. если не одна - оставляет "женщина".

и наоброт

В чем подвох?

← →
Юрий Зотов © (2004-04-22 13:38) [23]

> Reindeer Moss Eater © (22.04.04 13:12) [13]

Освежил память по справке. Вы правы, семафоры работают наоборот, поэтому здесь надо делать обратную логику.

← →
Тимохов © (2004-04-22 13:41) [24]

Господа,
одарите меня несколькими словами - в чем подвох?
Заранее спасибо?

← →
}|{yk © (2004-04-22 13:43) [25]

Внагрузку к программе:
1. Каков поток мужчин/женщин
2. Какая максимальная очередь может создаться
3. Сколько мужчин/женщин помоется
4. Какой закон распределения использовать

← →
Юрий Зотов © (2004-04-22 13:48) [26]

> Тимохов © (22.04.04 13:41) [24]

> в чем подвох?

В синхронизации. Вот Вы написали:
"если "мужик" - ждет"
и тут же возникают вопросы:
- ждет ЧЕГО именно?
- как он узнает, что это ЧТО-ТО уже произошло?
- и как все это реализовать программно?

← →
Матлабист (2004-04-22 13:51) [27]

Все равно, есть три процесса

1. Женщина
1. Проверяет семафор (есть ли мужчины)
1. Устанавливает семафор (женщины)
2. Мужчина
2. Ждет семафор (женщины)
3. Женщина
1. Женщина сбрасывает семафор (женщин нет)
3. Проверяет семафор (есть ли мужчины)
2. Устанавливает семафор (мужчины)
3. Устанавливает семафор (женщины)
2 и 3: Наслаждаются прелестями жизни

2. Пореряет семафор женщин
3. Подходит

← →
Тимохов © (2004-04-22 13:52) [28]

Ждет, пока индикатор не станет равным "свободно" или "жо".

> - и как все это реализовать программно?

Согласен, здесь есть над чем подумать.

ЗЫ.Когда общаются такие гуру есть ощущение, что все намного сложнее.

вот народ упёртый...

>Тимохов © (22.04.04 13:36) [22]

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

Еще 2 проблемы.

1. Как очередному выходящему определить, что надо делать релис семафору его пола? Если сделать это выходя не последним, в ванную ворвется толпа женщин.

2. В ванной никого нет.
Подходит к двери М. Делает вэйт женского семафора и понимает, что внутри женщин нет. Он - в ванной комнате.
Вторая операция - вэйт своему семафору, что бы не вошли женщины.
Но он не успевает это сделать, так как подошедшая женщина уже проверяет мужской семафор, а он еще не занят. Она тоже принимает решение, что можно входить.

> uw © (22.04.04 13:54) [30]

Да ясен перец, что это задача. Не знал, что типичная, т.к. никогда не решал словесно поставленные аналогичные задачи. Обычно решал, что-то конкретное. И мой вопрос был понять, что нужно получить в результате.
Теперь понял

Семафор №1. "Операция рассматривания индикаторов на двери ванной". Счетчик = 1;

Семафоры № 2,3 - "мужской" и "женский". счетчик = 1

Очередной желающий помыться ждет семафор №1 (INFINITY)
Дожавшись, ждет семафор противоположного пола (INFINITY)
Дождавшись ждет семафор своего пола без таймаута.
Дождавшись его или по таймауту освобождает семафор у двери.

Остается придумать реализацию выхода из ванной.

А что, мое решение не подходит по каким-то параметрам?
Мои посетители - это потоки. Чтобы войти в ванную они должны вызвать ManEnter, указав свой пол ( 1 - мужчины, -1 - женщины).
Чтобы выйти из ванной - просто вызвать ManLeave.
Ну там не хватает проверок на достоверность (чтобы 2 или -3 задать в качестве пола не могли, например). А так - вроде рабочий вариант? Нет?

http://delphimaster.net/view/14-1082631956/

Igorek © (22.04.04 15:02) [34]

Не надо лишний раз утверждаться в ламерстве, ей-богу, не стОит.

По поводу некорректной формулировки, обращайся к автору, он там указан. Его email ast@cs.vu.nl

---
LMD

← →
Матлабист (2004-04-22 15:40) [38]

Вариант рабочий, но требует три объекта синхронизации... Двух, скорее всего, не хватает --- возможно [27].

← →
Матлабист (2004-04-22 15:43) [39]

Все это ламерство - написание никому не нужного кода
и решение задач, решаемых элементарно другими средствами
причем эти средства бесплатны, и позволяют ответит на куда большее число вопросов. Вот добавьте в свою программу функцию выдачи максимальной очереди, которая возникнет за день. Слабо?

Еще задачка :) Найти похожие ветки