//www.algorytm.org
//Algorytm Haberman'a - detekcja zakleszczenia
//(c)2002 Tomasz Lubinski

program Algorytm_Haberman;

uses
  Forms,
  SysUtils,
  math;

{$R *.RES}
{$Apptype console}

var
p,z,i,j: Integer;
A, H : Array [1..100] of Array [1..100] of Integer;
D, f : Array [1..100] of Integer;
flaga, zwolnic: Boolean;

begin
writeln('Podaj liczbe procesow (max. 100)');
readln(p);
writeln('Podaj liczbe zasobow (max. 100)');
readln(z);
//pobranie danych
for i:=1 to p do
        for j:=1 to z do
                begin
                writeln('Podaj ile zasobu '+IntToStr(j)+' posiada proces '+IntToStr(i));
                readln(A[i,j]);
                end;
for i:=1 to p do
        for j:=1 to z do
                begin
                writeln('Podaj ile zasobu '+IntToStr(j)+' moze jeszcze zazadac proces '+IntToStr(i));
                readln(H[i,j]);
                end;
for i:=1 to z do
        begin
        writeln('Podaj ile zasobu '+IntToStr(i)+' jest jeszcze wolne w systemie');
        readln(f[i]);
        end;
writeln; writeln;
//algorytm Habermana
flaga:=true;
//zainicjuj D:={1,2,...,p}
for i:=1 to p do D[i]:=i;
while flaga do
        begin
        flaga:=false;
        for i:=1 to p do
                if D[i]<>0 then
                        begin
                        zwolnic:=true;
                        for j:=1 to z do //sprawdz czy można zwolnic zasoby procesu i
                                if f[j]<H[i,j] then
                                        begin
                                        zwolnic:=false;
                                        break;
                                        end;
                        if zwolnic then //jeżeli można to zwolnij zasoby proesu i
                                begin
                                D[i]:=0;
                                flaga:=true;
                                for j:=1 to z do
                                        begin
                                        f[j]:=A[i,j]+f[j];
                                        H[i,j]:=0;
                                        A[i,j]:=0;
                                        end;
                                writeln('Zwalniam zasoby procesu '+IntToStr(i));
                                break;
                                end
                        end;

        end;
//sprawdz czy D jest zbiorem pustym: jesli tak to brak zakleszczenia
flaga:=true;
write('Zbior zadan zakleszczonych: {');
for i:=1 to p do
        if D[i]<>0 then
                begin
                flaga:=false;
                write(' '+IntToStr(i));
                end;
write(' }');
writeln;
if flaga then writeln('Zbior zadan zakleszczonych jest pusty zatem w tym systemie nie ma zakleszczenia');
readln;
end.