Версия для печати темы

Автор: -Базилио- 17.07.2007 22:48

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

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

Автор: -Базилио- 17.07.2007 22:58

У препода в лекциях, например, приведено.
Приведем решение, использующее семафоры:
#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);
}
Но если ему сдавать в таком виде он не очень обрадуется, или очень удивиться. Можно ее написать в другом виде? Так, чтобы он не догадался откуда это. И кроме того остается еще второй пункт...

Автор: Tan 18.07.2007 13:34

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

Автор: Гость 18.07.2007 18:07

Да, я знаю. -) Но переделывать Си в Дельфи одно удовольствие.

Автор: volvo 18.07.2007 18:13

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

Автор: Гость 18.07.2007 18:24

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

Автор: -Базилио- 18.07.2007 18:28

Нашел. Спасибо за подсказку.

Автор: volvo 18.07.2007 18:30

Я брал http://www.natahaus.ru/index.php?do=register (зарегистрируйся, введи фамилию автора в поиске, и получишь ссылку на книгу - я надеюсь, она еще жива...)

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

Автор: Гость 1.10.2008 18:08

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

Автор: volvo 1.10.2008 21:16

Что такое 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.

(переносилось с Ады, так что может быть не совсем оптимально)