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

← →
Игорь Шевченко © (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]

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

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

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

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

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

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

← →
uw © (2004-04-22 13:54) [30]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

← →
Igorek © (2004-04-22 15:02) [34]

> Игорь Шевченко © (22.04.04 11:05)

NCF (Not correctly formulated) © Igorek

← →
Verg © (2004-04-22 15:02) [35]

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

← →
}|{yk © (2004-04-22 15:07) [36]

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

← →
Игорь Шевченко © (2004-04-22 15:35) [37]

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]

> Verg © (22.04.04 15:02) [35]

И это... Плохо масштабируется на случай процессов.

← →
}|{yk © (2004-04-22 15:51) [40]

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

← →
Verg © (2004-04-22 16:22) [41]

> }|{yk © (22.04.04 15:51) [40]

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

Насчет "слабо":
Берем тот же код, меняем два места

TBathRoom = class private FCount : integer; Cs : TCriticalSection; MenWait, WMenWait : TEvent; MQueSize, WMQueSize : integer; procedure ProcessFCount; public MQMax, // Макс размер мужской очереди WMQMax : integer; // Макс размер женской constructor Create; destructor Destroy; override; procedure ManEnter(MSex : integer); procedure ManLeave; end;
............
procedure TBathRoom.ManEnter(MSex : integer); var Que : boolean; begin if MSex = 0 then exit; Que := false; repeat Cs.Enter; try if (FCount = 0) or not ((FCount < 0) xor (MSex < 0)) then begin Inc(FCount, MSex); ProcessFCount; if Que then if Msex < 0 then Dec( WMQueSize ) else Dec( MQueSize ); break; end; if Msex < 0 then Inc( WMQueSize ) else Inc( MQueSize ); Que := true; if WMQueSize > WMQMax then WMQMax := WMQueSize; if MQueSize > MQMax then MQMax := MQueSize; finally Cs.Leave; end; if MSex < 0 then WMenWait.WaitFor(INFINITE) else MenWait.WaitFor(INFINITE); until false; end;

← →
}|{yk © (2004-04-22 16:33) [42]

ОК, добавьте в программу распределение нагруженности "линии" в зависимости от часа дня

← →
mrcat © (2004-04-22 16:34) [43]

>Игорь Шевченко © (22.04.04 11:05)
хм. где бы такую книжку приобрести ?

← →
Verg © (2004-04-22 16:38) [44]

> }|{yk © (22.04.04 16:33) [42]
> ОК, добавьте в программу распределение нагруженности "линии"
> в зависимости от часа дня

Все, бесплатный цирк закончился... Каков гонорар?

← →
}|{yk © (2004-04-22 16:42) [45]

Зачем гонорар? Я завтра могу принести условие задачи и ее решение с помощью GPSS. Попробуйте решить ту же задачу на Delphi. Рискнете?

← →
Reindeer Moss Eater © (2004-04-22 16:45) [46]

Дурь какая-то.
Откуда некий могучий GPSS знает лучше Delphi про интенсивность посещения ванной студентами в течении дня.

← →
Игорь Шевченко © (2004-04-22 16:49) [47]

mrcat © (22.04.04 16:34)

Эндрю Таненбаум, Современные операционные системы, 2-ое издание

http://www.findbook.ru

← →
}|{yk © (2004-04-22 16:56) [48]

Этот инструмент предназначен специально для решения задач подобного типа. У нас в универе его изучают, правда слабее чем раньше (раньше еще и курсак по моделированию процессов на производстве писали). Почему юзают именно его? Просто завкаф для рассчетов в своей докторской его использовал

← →
Verg © (2004-04-22 16:57) [49]

> }|{yk © (22.04.04 16:42) [45]
> Зачем гонорар? Я завтра могу принести условие задачи и ее
> решение с помощью GPSS. Попробуйте решить ту же задачу на
> Delphi. Рискнете?

Вы все еще сомневаетесь? :))
Или вам нужно ее решить при помощи Дельфи, а у вас никак не получается?
Или Вы таким образом рекламируете GPSS на сайте www.delphimaster.ru?

Или просто мозг поклевать захотелось? :)))

← →
Reindeer Moss Eater © (2004-04-22 16:57) [50]

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

← →
McSimm © (2004-04-22 17:03) [51]

хм. где бы такую книжку приобрести ?

http://www.delphimaster.ru/books/978531800299/

← →
Verg © (2004-04-22 17:08) [52]

Ладно, все, оставляю исходник с демкой:

unit Room; interface uses Windows, Classes, SysUtils, SyncObjs; type TBathRoom = class private FCount : integer; Cs : TCriticalSection; MenWait, WMenWait : TEvent; MQueSize, WMQueSize : integer; procedure ProcessFCount; public MCount, WCount : integer; MQMax, WMQMax : integer; constructor Create; destructor Destroy; override; procedure ManEnter(MSex : integer); procedure ManLeave; procedure PrintState(MAdd, WAdd : integer); 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.PrintState(MAdd, WAdd : integer); begin Cs.Enter; try Inc(MCount, MAdd); Inc(WCount, WAdd); Writeln("Man : ", MCount," WMen : ",WCount," FC : ", FCount, " MaxMQue ", MQMax, " MaxWQSize ", WMQMax ); if (MCount<>0) and (WCount<>0) then begin Windows.Beep(1000, 50); ReadLn; end; finally Cs.Leave; end; 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); var Que : boolean; begin if MSex = 0 then exit; Que := false; repeat Cs.Enter; try if (FCount = 0) or not ((FCount < 0) xor (MSex < 0)) then begin Inc(FCount, MSex); ProcessFCount; if MSex < 0 then PrintState(0, 1) else PrintState(1, 0); if Que then if Msex < 0 then Dec( WMQueSize ) else Dec( MQueSize ); break; end; if not Que then begin if Msex < 0 then Inc( WMQueSize ) else Inc( MQueSize ); Que := true; if WMQueSize > WMQMax then WMQMax := WMQueSize; if MQueSize > MQMax then MQMax := MQueSize; end; finally Cs.Leave; end; if MSex < 0 then WMenWait.WaitFor(INFINITE) else MenWait.WaitFor(INFINITE); until false; end; procedure TBathRoom.ManLeave; var F : boolean; begin Cs.Enter; try F := FCount < 0; if FCount = 0 then Windows.Beep(1000, 50); if FCount <> 0 then if FCount < 0 then Inc(FCount) else Dec(FCount); ProcessFCount; if F then PrintState(0, -1) else PrintState(-1, 0); finally Cs.Leave; end; end; end.

← →
Verg © (2004-04-22 17:09) [53]

program BathRoom; {$APPTYPE CONSOLE} uses Windows, Classes, SysUtils, Room; type TMan = class(TThread) FSex : integer; Br : TBathRoom; constructor Create(ASex : integer; Abr : TBathRoom); procedure Execute; override; end; constructor TMan.Create(ASex : integer; Abr : TBathRoom); begin FSex := ASex; Br := Abr; FreeOnTerminate := true; inherited Create(False); end; procedure TMan.Execute; begin Sleep(random(500)); Br.ManEnter(FSex); Sleep(random(50)); Br.ManLeave; end; var BtRoom : TBathRoom; I : integer; begin Randomize; BtRoom := TBathRoom.Create; For I := 1 to 2000 do begin if Random(100) < 50 then TMan.Create(1, BtRoom) else TMan.Create(-1, BtRoom) end; sleep(INFINITE); end.

← →
}|{yk © (2004-04-22 17:19) [54]

Таки принесу завтра задание и решение. посмотрим...

← →
Reindeer Moss Eater © (2004-04-22 17:26) [55]

Знал я одного зав. вычислительно кафедрой. Доцент, КТН.
Свёл в конечном итоге весь учебный процесс на кафедре фактически к подготовке пользователей MS Office.

Тоже по страшной силе тащился от GPSS. До дрожи в руках.

← →
Игорь Шевченко © (2004-04-22 17:41) [56]

GPSS (GENERAL PURPOSE SIMULATING SYSTEM) - система
симуляции генерала Пурпоса (генерал Пурпос - сотрудник
фирмы IBM).

Иными словами, GPSS - это как бы компонент, который надо только кинуть на форму и чуть-чуть настроить.

Но приходит момент, когда модель усложняется... и GPSS начинает решать ее неделями. Не потому, что он плохой, а потому что он - GENERAL purpose. И нет возможности заставить считать его быстрее.

Аналог - MathLab. Выход - руки + компилятор.

P.S.
Все то, что не превращается в конечный машинный код, языком программирования НЕ является.
(с) Юрий Зотов.
:о)

unit SexRoomU; // :) interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, ExtCtrls, StdCtrls; const MY_MESSAGE = WM_USER + 101; type TForm1 = class(TForm) Button1: TButton; Button2: TButton; Timer1: TTimer; procedure FormCreate(Sender: TObject); procedure Timer1Timer(Sender: TObject); procedure ButtonClick(Sender: TObject); procedure MyMessage(var Msg : TMessage); message MY_MESSAGE; private Count: array[boolean] of integer; end; var Form1: TForm1; implementation {$R *.dfm} procedure TForm1.FormCreate(Sender: TObject); begin; Timer1.Enabled:=false; end; procedure TForm1.Timer1Timer(Sender: TObject); begin; SendMessage(Self.Handle,MY_MESSAGE,0,0); end; procedure TForm1.ButtonClick(Sender: TObject); begin; SendMessage(Self.Handle,MY_MESSAGE,1,ord(Sender=Button2)); end; procedure TForm1.MyMessage(var Msg: TMessage); const sex: array[boolean] of string= ("женщин","мужчин"); place: array[boolean] of string= ("в очереди","в бане"); var IsMan: boolean; begin; Msg.Result:=-1; if Msg.WParam=0 then begin; IsMan:=(Count[true]<0); inc(Count[IsMan]); end else begin; IsMan:=(Msg.LParam<>0); if Count[IsMan]>=0 then begin; inc(Count[IsMan]); IsMan:=not IsMan; end else dec(Count[IsMan]); end; IsMan:=IsMan xor (Count[IsMan]=0); if Count[IsMan]>0 then Count[IsMan]:=-Count[IsMan]; Timer1.Enabled:=(Count[IsMan]<>0); Button1.Caption:=Format("%d %s %s",[abs(Count[false]),sex[false],place[Count[false]<0]]); Button2.Caption:=Format("%d %s %s",[abs(Count[true]),sex[true],place[Count[true]<0]]); end; end. object Form1: TForm1 Left = 294 Top = 103 Width = 253 Height = 109 Caption = "Form1" Color = clBtnFace Font.Charset = DEFAULT_CHARSET Font.Color = clWindowText Font.Height = -11 Font.Name = "MS Sans Serif" Font.Style = [] OldCreateOrder = False OnCreate = FormCreate PixelsPerInch = 96 TextHeight = 13 object Button1: TButton Left = 8 Top = 16 Width = 225 Height = 25 Caption = "0 женщин в очереди " TabOrder = 0 OnClick = ButtonClick end object Button2: TButton Left = 8 Top = 48 Width = 225 Height = 25 Caption = "0 мужчин в очереди " TabOrder = 1 OnClick = ButtonClick end object Timer1: TTimer OnTimer = Timer1Timer Left = 24 Top = 32 end end

PS Забыл сказать: это мой симулятор, только к поставленной задаче он отношения не имеет.

← →
Сергей Суровцев. (2004-04-23 00:00) [60]

>Reindeer Moss Eater © (22.04.04 14:02) [33]
>Остается придумать реализацию выхода из ванной.

Возможно я глубоко не прав, но вроде бы две простые глобальные переменные спасут отца русской демократии. :))
Два числовых счетчика М и Ж. Вошел: +1, вышел -1. Каждый при входе проверяет счетчик другого пола - если он 0, входит сам.
И все.
А уж к этому принципу столько статистики подвязать можно, насколько фантазии хватит. И по времени, и по количеству. А можно и ограничения подвязать на максимум внутри одновременно.
Код писать не буду ибо лень, а идею и так видно. :))

>}|{yk © (22.04.04 15:51) [40]
>Все это ламерство - написание никому не нужного кода
>и решение задач, решаемых элементарно другими средствами

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

>Сергей Суровцев. (23.04.04 00:00) [60]

Стек на каждую ванну

Подделка?
Ник-то не зарегистрированный. Суровцев с точкой в конце никогда не подписывался.

> Сергей Суровцев. (23.04.04 00:00) [60]
> Два числовых счетчика М и Ж. Вошел: +1, вышел -1. Каждый при
> входе проверяет счетчик другого пола - если он 0, входит сам.

А если он не ноль, то что? Ждет?

Ждет, вероятно. Вот только чего именно он ждет и как именно он ждет? В чем весь фокус и есть.

Надеюсь, такой вариант Вы даже и предлагать не станете:
while OtherCount > 0 do Sleep(0)

Допустим ванная комната вообще пуста....

> если он 0,(вот тут происходит переключение конекста на такой >же поток но противоположного пола, котрый тоже получается >обнаружит 0) входит сам (и второй тоже входит).

Эти (такие) задачи не на логику.

В общем к модели [33] надо добавить один счетчик количества людей в ванной.

Каждый выходящий перед тем как покинуть ванную проверяет, не выходит ли он последним (перед этим сделав waitforsingleobject для семафора входной двери)
Заняв семафор двери, смотрим, равен ли счетчик единице.
Если да, то делаем OpenSemaphore семафору своего пола (если заходили не первым и не заняли его. Тогда его хендл у нас уже есть) после чего делаем релис этому семафору. После этого уменьшаем счетчик посетителей до нуля, и освобождаем семафор у двери (релис).

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

Четыре семафора нужно.

← →
Сергей Суровцев. (2004-04-23 10:11) [67]

>Aristarh © (23.04.04 00:23) [62]
Я это. Я. После смены паролей мой работать перестал. А так проще всего было. :))

>Юрий Зотов © (23.04.04 06:47) [63]
>А если он не ноль, то что? Ждет?
>Ждет, вероятно. Вот только чего именно он ждет и как именно он >ждет? В чем весь фокус и есть.

Очередь возникает ведь в любом случае. По условию. А в условии не сказано, что комната не должна пустовать ни мгновения. Если она может пустовать, то при входе вполне подойдет и вариант с переодическим опросом состояния (раз в 1-3 секунды), Если не должна вообще, то выходящий сам должен оповестить всю очередь, что он вышел и тогда вся очередь активизирует проверки.
По моему так! (с) Винний Пух.

P.S.
Загнал в "Сократ":
woman wants to enter, man wants to enter, woman leaves, man leaves.

и получил:

женщина хочет вводить, мужчины хочет вводить, женщину оставляет, листы человека.

Прямо Басё какой-то. :))

>Иными словами, GPSS - это как бы компонент, который надо только
>кинуть на форму и чуть-чуть настроить.
Вранье или же непонимание

>Но приходит момент, когда модель усложняется... и GPSS начинает
>решать ее неделями. Не потому, что он плохой, а потому что он -
>GENERAL purpose. И нет возможности заставить считать его быстрее.

Да в GPSS такие модели реализованы даже в демках (я давал ссылку, скачайте и посмотрите), которые универсальными методами вы будете неделями реализовывать. Правда бесплатна только student-версия

← →
Матлабист (2004-04-23 11:50) [69]

> Аналог - MathLab

Наверное MATLAB (MATrix LABoratory)

> }|{yk © (23.04.04 10:45) [68]

> Вранье или же непонимание

Непонимание. Но, извините, не мое.

Инструмент готовый? Готовый. Вот это я и назвал - как бы компонент.

Модель и всякие там условия задать требуется? Требуется. Вот это я и назвал - настроить.

Нельзя же все понимать буквально.

> Да в GPSS такие модели реализованы даже в демках (я давал
> ссылку, скачайте и посмотрите), которые универсальными
> методами вы будете неделями реализовывать.

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

Если решать эту задачу применительно к потокам нескольких сортов,
то достаточно одного объекта синхронизации - критической секции
диспетчеризации, символизирующей банщика, впускающего/выпускающего
посетителей, сортирующего их по кабинкам (всех лиц одного пола -
в одну кабинку) и дающего воду в одну выбранную кабинку :)
Все остальное у потоков для старта/стопа (Resume/Suspend) уже есть.
Нам остается лишь вести список потоков и запоминать их сорт.

Реализация процедур примерно следующая:

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

Посетитель помылся
Баншик.Начать
Выпустить посетителя, исключив из списка его данные
Если это был последний посетитель в кабинке,
то если это был последний посетитель в бане
то выключить воду
иначе переключить воду в заполненную кабинку
и разрешить находящимся там мыться
Банщик.Кончить

Verg © (22.04.04 17:08) [52]

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

unit RoomU; interface uses Windows, Classes, SysUtils, SyncObjs; type TRoom = class(TObject) private FSection: TCriticalSection; FEvents: array of TEvent; FCurrentType: integer; protected FCabinetsCount: integer; FCabinets: array of integer; FTotal: integer; public OnEnter: TNotifyEvent; OnLeave: TNotifyEvent; OnThreadTerminate: TNotifyEvent; constructor Create(ACabinetsCount: integer); destructor Destroy; override; end; TRoomThread = class(TThread) protected FType: integer; FRoom: TRoom; procedure Execute; override; procedure DoEnter; procedure DoLeave; procedure EnterRoom; procedure LeaveRoom; public constructor Create(ARoom: TRoom; AType: integer); end; implementation constructor TRoom.Create(ACabinetsCount: integer); var i: integer; begin; inherited Create; FSection:=TCriticalSection.Create; SetLength(FEvents,ACabinetsCount); for i:=0 to ACabinetsCount-1 do FEvents[i]:=TEvent.Create(nil,true,false,""); SetLength(FCabinets,ACabinetsCount); FillChar(FCabinets[0],SizeOf(FCabinets[0])*ACabinetsCount,0); FCabinetsCount:=ACabinetsCount; FCurrentType:=-1; end; destructor TRoom.Destroy; var i: integer; begin; FSection.Free; for i:=FCabinetsCount-1 downto 0 do FEvents[i].Free; FEvents:=nil; FCabinets:=nil; inherited; end; constructor TRoomThread.Create(ARoom: TRoom; AType: integer); begin; FRoom:=ARoom; FType:=AType; Self.OnTerminate:=ARoom.OnThreadTerminate; FreeOnTerminate:=true; inherited Create(false); end; procedure TRoomThread.Execute; begin; EnterRoom; if not Terminated then Sleep(300); LeaveRoom; end; procedure TRoomThread.DoEnter; begin; FRoom.OnEnter(Self); end; procedure TRoomThread.DoLeave; begin; FRoom.OnLeave(Self); end; procedure TRoomThread.EnterRoom; begin; with FRoom do begin; FSection.Enter; inc(FTotal); inc(FCabinets[FType]); if FCurrentType=-1 then begin; FCurrentType:=FType; FEvents[FCurrentType].SetEvent; end; if Assigned(OnEnter) then Synchronize(DoEnter); FSection.Leave; while not Terminated do if FEvents[FType].WaitFor(1000)=wrSignaled then break; end; end; procedure TRoomThread.LeaveRoom; var MaxCount, i: integer; begin; with FRoom do begin; FSection.Enter; dec(FTotal); dec(FCabinets[FType]); if (FCabinets[FType]=0) and (FType=FCurrentType) then begin; FEvents[FCurrentType].ResetEvent; FCurrentType:=-1; if FTotal>0 then begin; MaxCount:=0; for i:=0 to FCabinetsCount-1 do if MaxCount<FCabinets[i] then begin; FCurrentType:=i; MaxCount:=FCabinets[i]; end; FEvents[FCurrentType].SetEvent; end; end; if Assigned(OnLeave) then Synchronize(DoLeave); FSection.Leave; end; end; end.

unit RoomTestU; interface uses SyncObjs, RoomU, Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TForm1 = class(TForm) Button1: TButton; Memo1: TMemo; Label1: TLabel; Label2: TLabel; Label3: TLabel; procedure FormCreate(Sender: TObject); procedure FormDestroy(Sender: TObject); procedure Button1Click(Sender: TObject); procedure RoomEnter(Sender: TObject); procedure RoomLeave(Sender: TObject); procedure ThreadTermitate(Sender: TObject); procedure ShowResults(Sender: TObject); private Room: TRoom; ThreadCount: integer; ThreadToEnter: integer; end; var Form1: TForm1; implementation {$R *.dfm} procedure TForm1.FormCreate(Sender: TObject); begin; Room:=TRoom.Create(10); Room.OnEnter:=RoomEnter; Room.OnLeave:=RoomLeave; Room.OnThreadTerminate:=ThreadTermitate; Randomize; end; procedure TForm1.FormDestroy(Sender: TObject); begin; Room.Free; end; procedure TForm1.RoomEnter(Sender: TObject); begin; dec(ThreadToEnter); ShowResults(Sender); end; procedure TForm1.RoomLeave(Sender: TObject); begin; ShowResults(Sender); end; procedure TForm1.ThreadTermitate(Sender: TObject); begin; dec(ThreadCount); ShowResults(nil); end; type TMyRoom = class(TRoom); TMyThread = class(TRoomThread); procedure TForm1.ShowResults(Sender: TObject); var Text: string; i: integer; begin; Label1.Caption:=IntToStr(ThreadToEnter)+" входят в баню"; Label2.Caption:=IntToStr(TMyRoom(Room).FTotal)+" в бане"; Label3.Caption:=IntToStr(ThreadCount-TMyRoom(Room).FTotal-ThreadToEnter)+" выходят из бани"; if Sender<>nil then begin; Text:=""; for i:=0 to TMyRoom(TMyThread(Sender).FRoom).FCabinetsCount-1 do Text:=Text+IntToStr(TMyRoom(TMyThread(Sender).FRoom).FCabinets[i])+#13#10; Memo1.Lines.Text:=Text; end; end; procedure TForm1.Button1Click(Sender: TObject); var i: integer; begin; for i:=1 to 100 do begin; TRoomThread.Create(Room, Random(TMyRoom(Room).FCabinetsCount)); inc(ThreadCount); inc(ThreadToEnter); ShowResults(nil); end; end; end. -------- object Form1: TForm1 Left = 168 Top = 292 Width = 253 Height = 211 Caption = "Form1" Color = clBtnFace Font.Charset = DEFAULT_CHARSET Font.Color = clWindowText Font.Height = -11 Font.Name = "MS Sans Serif" Font.Style = [] OldCreateOrder = False OnCreate = FormCreate OnDestroy = FormDestroy PixelsPerInch = 96 TextHeight = 13 object Label1: TLabel Left = 136 Top = 48 Width = 6 Height = 13 Caption = "0" end object Label2: TLabel Left = 136 Top = 64 Width = 6 Height = 13 Caption = "0" end object Label3: TLabel Left = 136 Top = 80 Width = 6 Height = 13 Caption = "0" end object Button1: TButton Left = 136 Top = 8 Width = 105 Height = 25 Caption = "+100 посетителей" TabOrder = 0 OnClick = Button1Click end object Memo1: TMemo Left = 8 Top = 8 Width = 113 Height = 169 TabOrder = 1 end end

2Юрий Зотов © (25.04.04 14:09) [70]

>Модель и всякие там условия задать требуется? Требуется. Вот это
> я и назвал - настроить.
Модель в GPSS не задаются тривиальными методами. Посмотрите скрипты

> То есть - и за месяц непрерывного счета можно не дождаться
>результатов.
Не знаю. Неслабенькая задача о б обслуживании в супермаркете решалалась до 5 секунд на моем слабо 500 Мгц

Вообще-то нужны не дрели а дырки :)

> }|{yk
> Модель в GPSS не задаются тривиальными методами.

Ну, если задание НЕтривиальными методами - это как бы уже и не задание вовсе, то, конечно, дело меняется в корне.

нету сил прочитать все выше написанное :)

по-моему, достаточно простое решение такое.

один счетчик (0 - никого нет, >0 - количество мужчин, <0 - количество женщин), защищенный критической секцией или мьютексом (в зависимости от того, как мы реализуем людей - отдельным процессом или отдельным потоком), при изменении счетчика в положение 0 - возбуждается event.

Кол-во женщин и кол-во мужчин знать не нужно.
Достаточно знать кол-во людей в ванной вообще.

>[79] Reindeer Moss Eater
>Кол-во женщин и кол-во мужчин знать не нужно.
>Достаточно знать кол-во людей в ванной вообще.
если ты это мне, то один счетчик, как я предложил, именно так и делает. абсолютное значение - количество людей в ванной, знак - признак мужчины/женщины. если я пропустил и такое уже предлагалось выше - прошу прощения.

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