Форум: "Потрепаться";
Текущий архив: 2004.12.12;
Скачать: [xml.tar.bz2];

Вниз

Перечитывая Таненбаума (задачка)   Найти похожие ветки 

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

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

---

← →
OneFragLeft   (2004-11-18 22:30) [1]

Блин, пока прочитаешь "проголодаешься", пойду-ка заточу пару бабуинов:)

---

← →
Мирон ©   (2004-11-18 22:32) [2]

Э-э, а в качестве каната здесь что?

---

← →
Alx2 ©   (2004-11-18 22:36) [3]

>Мирон ©   (18.11.04 22:32) [2]

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

Работу светофора программируем :)

---

← →
Гаврила ©   (2004-11-18 22:49) [4]

Оффтопик
бабуины - это такие обезьяны или такое племя ?

---

← →
Мирон ©   (2004-11-18 22:57) [5]

Гаврила ©   (18.11.04 22:49) [4]
Нет, бабуины - это такие одичавшие заросшие африканские программисты

---

← →
OneFragLeft   (2004-11-18 23:03) [6]

Внимание. Внимание.
Прекратились поставки свежих бабуинов в восточную часть каньона. Что делать, но ведь верёвка порвалась. (А я её даже не успел намылить).
Граждане! Вышлите мне свежих бабуинов, кто сколько может. А то у меня всего 5 штук осталось.
>Нет, бабуины - это такие одичавшие заросшие африканские программисты
Дедушку моего попрошу не трогать.

---

← →
Гаврила ©   (2004-11-18 23:05) [7]

> Нет, бабуины - это такие одичавшие заросшие африканские
> программисты


Они одичали, пока пытались написать программку с семафорами ?

---

← →
OneFragLeft   (2004-11-18 23:07) [8]

>Гаврила ©   (18.11.04 23:05) [7]
Щас пойду у деда спрошу.

---

← →
123 ©   (2004-11-19 00:50) [9]

Я вообще не вчихлил, что тут программировать.. :/

---

← →
GuAV ©   (2004-11-19 03:52) [10]

unit Unit1;

interface

uses
 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
 Dialogs, StdCtrls;

type
 TForm1 = class(TForm)
   Button1: TButton;
   Memo1: TMemo;
   Memo2: TMemo;
   procedure Button1Click(Sender: TObject);
 private
   { Private declarations }
 public
   { Public declarations }
 end;

var
 Form1: TForm1;

implementation

{$R *.dfm}

type
 TSemaphore = THandle;

 TCanyon = class;
 TBabuin = class;

 TSideOfCanyon = class
 private
   FCanyon: TCanyon;
   FBabuins: TThreadList;
   FAnotherSide: TSideOfCanyon;
   FSemaphore: TSemaphore;
 public
   constructor Create(Canyon: TCanyon; Opposite: TSideOfCanyon);
   destructor Destroy; override;
   property AnotherSide: TSideOfCanyon read FAnotherSide;
   property Babuins: TThreadList read FBabuins;
   property Semaphore: TSemaphore read FSemaphore;
 end;

 TBabuin = class(TThread)
 private
   FCanyon: TCanyon;
   FSide: TSideOfCanyon;
   FName: string;
   procedure DrawState;
 public
   constructor Create(Name: string; Canyon: TCanyon; Side: TSideOfCanyon);
   property Name: string read FName;
   property Side: TSideOfCanyon read FSide;
   procedure Execute; override;
   procedure WantToClimbToAnotherSide;
   procedure ClimbToAnotherSide(FromSide, ToSide: TSideOfCanyon);
 end;

 TCanyon = class
 private
   FWest, FEast: TSideOfCanyon;
 public
   constructor Create;
   destructor Destroy; override;
   property West: TSideOfCanyon read FWest;
   property East: TSideOfCanyon read FEast;
 end;

{ TCanyon }

constructor TCanyon.Create;
begin
 FWest := TSideOfCanyon(TSideOfCanyon.NewInstance);
 try
   FEast := TSideOfCanyon.Create(Self, FWest);
   FWest.Create(Self, FEast)
 except
   FWest.Free;
   raise;
 end;
 TBabuin.Create("Babuin 1", Self, West);
 TBabuin.Create("Babuin 2", Self, West);
 TBabuin.Create("Babuin 3", Self, West);
 TBabuin.Create("Babuin 4", Self, West);

 TBabuin.Create("Babuin A", Self, East);
 TBabuin.Create("Babuin B", Self, East);
 TBabuin.Create("Babuin C", Self, East);
 TBabuin.Create("Babuin D", Self, East);
end;

destructor TCanyon.Destroy;
begin
 FWest.Free;
 FEast.Free;
end;

{ TBabuin }

constructor TBabuin.Create(Name: string; Canyon: TCanyon; Side: TSideOfCanyon);
begin
 inherited Create(False);
 FreeOnTerminate := True;
 FName := Name;
 FCanyon := Canyon;
 FSide := Side;
 Side.FBabuins.Add(Self);
end;

procedure TBabuin.Execute;
begin
 while not Terminated do
 begin
   Sleep(Random(1000));
   WantToClimbToAnotherSide;
 end;
end;

procedure TBabuin.WantToClimbToAnotherSide;
var S: TSemaphore;
begin
 S := Side.Semaphore;
 if Side = FCanyon.West then
 // почему не рабоетает как ожидалось если это раскоментировать ?
 //  if WaitForSingleObject(S, 0) = WAIT_OBJECT_0 then
   try
     ClimbToAnotherSide(Side, Side.AnotherSide);
   finally
    // ReleaseMutex(S);
   end
 else
  // if WaitForSingleObject(S, INFINITE) = WAIT_OBJECT_0 then
   try
     ClimbToAnotherSide(Side, Side.AnotherSide);
   finally
  //   ReleaseMutex(S);
   end;
end;

procedure TBabuin.ClimbToAnotherSide(FromSide, ToSide: TSideOfCanyon);
begin
 FromSide.Babuins.Remove(Self);
 Synchronize(DrawState);
 Sleep(500 + Random(200));
 ToSide.Babuins.Add(Self);
 FSide := ToSide;
 Synchronize(DrawState);
end;

procedure FormList(S: TStrings; Side: TSideOfCanyon);
var I: Integer;
begin
 S.BeginUpdate;
 try
   with Side.Babuins.LockList do
   try
     S.Clear;
     for I := 0 to Count - 1 do
       S.Add(TBabuin(Items[I]).Name);
   finally
     Side.Babuins.UnlockList;
   end;
 finally
   S.EndUpdate;
 end;
end;

procedure TBabuin.DrawState;
begin
 FormList(Form1.Memo1.Lines, FCanyon.West);
 FormList(Form1.Memo2.Lines, FCanyon.East);
end;

{ TSideOfCanyon }

constructor TSideOfCanyon.Create(Canyon: TCanyon; Opposite: TSideOfCanyon);
begin
 FAnotherSide := Opposite;
 FBabuins := TThreadList.Create;
 FCanyon := Canyon;
 FSemaphore := CreateMutex(nil, False, nil);
end;

destructor TSideOfCanyon.Destroy;
begin
 if FSemaphore <> 0 then CloseHandle(FSemaphore);
 FBabuins.Free;
end;

var DeepCanyon: TCanyon;

procedure TForm1.Button1Click(Sender: TObject);
begin
 DeepCanyon := TCanyon.Create;
end;

initialization
 Randomize;
end.

PS: три часа ночи, только второй раз работаю с объектами синхронизации.. не бейте сильно ;)

---

← →
GuAV ©   (2004-11-19 04:11) [11]

я понял что не так, оказывается всё несколько сложнее, попытаюсь уже сделать завтра, если никто не опередит...

---

← →
KilkennyCat ©   (2004-11-19 08:15) [12]

Дайте им еще одну веревку и не мучайтесь...

---

Страницы: 1 вся ветка

Форум: "Потрепаться";
Текущий архив: 2004.12.12;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.49 MB
Время: 0.04 c