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

#include <stdio.h>
#include <conio.h>

int p,z,i,j,flaga,zwolnic,A[100][100],H[100][100],D[100],f[100];


void main()
{
printf("Podaj liczbe procesow (max. 100)\n");
scanf("%d",&p);
printf("Podaj liczbe zasobow (max. 100)\n");
scanf("%d",&z);
//pobranie danych
for (i=0; i<p; i++)
	for (j=0; j<z; j++)
		{
		printf("Podaj ile zasobu %d posiada proces %d\n", j+1, i+1);
		scanf("%d",&A[i][j]);
		}
for (i=0; i<p; i++)
	for (j=0; j<z; j++)
		{
		printf("Podaj ile zasobu %d moze jeszcze zazadac proces %d\n", j+1, i+1);
		scanf("%d",&H[i][j]);
		}
for (i=0; i<z; i++)
	{
	printf("Podaj ile zasobu %d jest jeszcze wolne w systemie\n",i+1);
	scanf("%d",&f[i]);
	}
//algorytm Habermana
flaga=1;
//zainicjuj D:={1,2,...,p}
for (i=0; i<p; i++) D[i]=i+1;
while (flaga==1)
	{
	flaga=0;
	for (i=0; i<p; i++)
		if (D[i]!=0)
			{
			zwolnic=1;
			for (j=0; j<z; j++)   //sprawdz czy mozna zwolnic zasoby procesu i
				if (f[j]<H[i][j])
					{
					zwolnic=0;
					break;
					}
			if (zwolnic==1)      //jezeli mozna to zwolnij zasoby proesu i
				{
				D[i]=0;
				flaga=1;
				for (j=0; j<z; j++)
					{
					f[j]=A[i][j]+f[j];
					H[i][j]=0;
					A[i][j]=0;
					}
				printf("Zwalniam zasoby procesu %d\n",i+1);
				break;
				}
			}

	}
//sprawdz czy D jest zbiorem pustym: jesli tak to brak zakleszczenia
flaga=1;
printf("Zbior zadan zakleszczonych: {");
for (i=0; i<p; i++)
	if (D[i]!=0)
		{
		flaga=0;
		printf(" %d",i+1);
		}
printf(" }\n");
if (flaga==1) printf("Zbior zadan zakleszczonych jest pusty zatem w tym systemie nie ma zakleszczenia\n");
getch();
}