IPB
ЛогинПароль:

> ВНИМАНИЕ!

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> «Спящий брадобрей»., Задача по параллельному программированию
сообщение
Сообщение #1


Гость






Помогите, кто может Решить одну из классических проблем межпроцессного взаимодействия:«Спящий брадобрей».
Имеется парикмахерская с двумя дверями и несколькими креслами. Посетители входят в одну дверь и выходят через другую. Парикмахер всю жизнь обслуживает клиентов. Когда клиентов нет, он спит в своем кресле. Когда посетитель приходит в салон и видит спящего парикмахера, он будит его, садится в кресло и спит, пока тот занят стрижкой. Если во время стрижки приходит еще один клиент, он садится в одно из свободных кресел и засыпает. Если свободных мест нет, клиент уходит. После стрижки парикмахер открывает клиенту выходную дверь и закрывает ее за ним. Если есть ожидающие посетители, парикмахер будит одного из них и ждет, пока тот сядет в кресло, после чего стрижет его. Если посетителей нет, парикмахер идет спать до следующего клиента.
Таким образом, эта задача описывает отношения в системах «клиент-сервер», когда клиент посылает запрос и ждет ответа сервера. В свою очередь сервер ожидает запросы клиентов, обрабатывает их и посылает ответ.
Множество запросов клиентов образуют очередь, длина которой ограничена.

При решении учесть, что длительность каждой операции составляет некоторую случайную величину.
Предоставить решение в двух вариантах:
1.с использованием семафоров в условиях разделяемой памяти;
2.с использованием сообщений в условиях распределенной памяти.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






У препода в лекциях, например, приведено.
Приведем решение, использующее семафоры:
#define CHAIRS 5 //количество стульев
semaphore customers=0; // количество ожидающих посетителей
semaphore barbers=0; // количество парикмахеров, ждущих клиентов
mutex m; // контроль доступа к waiting
int waiting=0; // и это количество ожидающих посетителей
process barber() // процесс - парикмахер
{
while(true)
{
down(customers); // если посетителей нет – уйти в ожидание
lock(m); // войти в критическую область
waiting--; // уменьшить количество ожидающих клиентов
up(barbers); // разбудить парикмахера
unlock(m); // выйти из критической области
// обслуживание клиента
}
}
process customer() // процесс - клиент
{
lock(m); // войти в критическую область
if (waiting<CHAIRS) // если есть свободные стулья, то обслуживаться
{
waiting++; // увеличить счетчик ожидающих клиентов
up(customers); //при необходимости – разбудить парикмахера
unlock(m); // выйти из критической области
down(barbers); // если парикмахер занят – уйти в ожидание
// обслуживание клиента
} else // нет свободных стульев - уйти
unlock(m);
}
Но если ему сдавать в таком виде он не очень обрадуется, или очень удивиться. Можно ее написать в другом виде? Так, чтобы он не догадался откуда это. И кроме того остается еще второй пункт...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Профи
****

Группа: Пользователи
Сообщений: 559
Пол: Мужской
Реальное имя: Бруно

Репутация: -  10  +


это форум по Делфи.


--------------------
Цитата
Imagination is more important than knowledge.
Albert Einstein
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Цитата(Tan @ 18.07.2007 9:34) *

это форум по Делфи.


Да, я знаю. -) Но переделывать Си в Дельфи одно удовольствие.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата
У препода в лекциях, например, приведено.
Кстати, твой преподаватель содрал это решение из книги Э. Таненбаума "Современные операционные системы", 2-е издание - стр. 155-156

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Цитата(volvo @ 18.07.2007 14:13) *

Кстати, твой преподаватель содрал это решение из книги Э. Таненбаума "Современные операционные системы", 2-е издение - стр. 155-156


Очень возможно. -) Буду очень благодарен, если напишете ссылочку, где можно было бы скачать эту книгу. Хотя прям сейчас пойду поищу ее в сети. )
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Нашел. Спасибо за подсказку.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






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

Добавлено через 16 мин.
Кстати, -Базилио-, по запросу в Google -> "sleeping barber" можно найти не только описание проблемы, но и ее решение (и даже не одно wink.gif )
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Помогите пожалуйста. Этот алгоритм у меня есть, но мне хотелось бы это приложение полностью рабочее, так как совсем не могу разобраться с семафорами , как описать ф-ии down и up. У кого есть прошу помоч!! Help!!!
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Цитата
как описать ф-ии down и up
Что такое Up и Down написано у Таненбаума на странице 136...
Цитата
мне хотелось бы это приложение полностью рабочее
Вот код на FPC. На Дельфях тоже должно отработать в принципе...
{$mode objfpc}
uses crt, classes;

// задержка в десятых долях секунды
procedure myDelay(sec_div_10: integer);
const
dec_sec = 10;
begin
delay(sec_div_10 * dec_sec);
end;

const
NumChairs = 5;

type
TClient = integer;
TBarberQueue = array[1 .. NumChairs] of TClient;

TBarberChairs = class
constructor Create;

function IsFull: boolean;
function TakeChair(const TheClient: TClient): boolean;
function WaitForClient(var TheClient: TClient): boolean;

private
Queue: TBarberQueue;
NextAvailable: integer;
NextCustomer: integer;
NumWaiting: integer;
end;

TBarber = class(TThread)
procedure Execute; override;
end;
TMaster = class(TThread)
procedure Execute; override;
end;

constructor TBarberChairs.Create;
begin
inherited Create;
NextAvailable := 1;
NextCustomer := 1;
NumWaiting := 0;
end;

function TBarberChairs.IsFull: boolean;
begin
result := NumWaiting = NumChairs;
end;

function TBarberChairs.TakeChair(const TheClient: TClient): boolean;
begin
if not IsFull then begin

Queue[NextAvailable] := TheClient;
if NextAvailable = NumChairs then NextAvailable := 1
else inc(NextAvailable);

inc(NumWaiting);
exit(true);

end;
result := false;
end;

function TBarberChairs.WaitForClient(var TheClient: TClient): boolean;
begin
if NumWaiting > 0 then begin

TheClient := Queue[NextCustomer];
if NextCustomer = NumChairs then NextCustomer := 1
else inc(NextCustomer);

dec(NumWaiting);
exit(true);

end;
result := false;
end;

var
BarberChairs: TBarberChairs;
Barber: TBarber;
Master: TMaster;

procedure TBarber.Execute;
var CurrentClient: TClient;
begin
repeat
if BarberChairs.WaitForClient(CurrentClient) then begin
writeln('Serving client #', CurrentClient);
myDelay(20);
end
else begin
myDelay(10);
if Terminated then break
else begin
writeln('Sleeping !!!');
end
end;

until false;
end;

procedure TMaster.Execute;
const
ClientMax = 20;
var
i_client: integer;
begin
myDelay(20);
for i_client := 1 to ClientMax do begin

myDelay(5);
if not BarberChairs.IsFull then begin
BarberChairs.TakeChair(i_client);
writeln('Client #', i_client, ' goes to the chair...');
end
else begin
writeln('No places left, client #', i_client, ' goes away...');
end
end;
myDelay(30);
Barber.Terminate;
Terminate;
end;


begin
BarberChairs := TBarberChairs.Create;
Barber := TBarber.Create(false);
Master := TMaster.Create(false);
repeat
delay(1);
until Master.Terminated;
end.
(переносилось с Ады, так что может быть не совсем оптимально)
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 20.09.2020 2:57
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name