Szerkesztő:GyPeti

Operációs rendszerek kötelező program dokumentáció[szerkesztés]

Kötegelt processzus szimulátor (legrövidebb hátralévő idejű)[szerkesztés]

Bemutatás[szerkesztés]

Kötegelt ütemező algoritmusok céljai:

Áteresztő képesség - maximalizálni az időegység alatt végrehajtott feladatok számát
Áthaladási idő - minimalizálni a feladat beküldése és befejeződése között eltelt időt
CPU-kihasználtság - a CPU mindig ki legyen használva

Fajtái:

Sorrendi ütemezés
A legrövidebb feladat végrehajtása először
A legrövidebb hátralévő idejű kiválasztása

A legrövidebb hátralévő idejű kiválasztása tulajdonságai:

Megszakítható
Ha az új processzus teljes ideje rövidebb, mint ami éppen a CPU‐t birtokló processzus hátralévő ideje lecseréli azt
Az új, rövid feladatok jó kiszolgálásban részesülnek

Bemeneti specifikáció[szerkesztés]

A bemenetet az initialize.txt-ben kell elhelyezni és a programmal egy mappába másolni.

A fájl első sorába be kell írni először h mennyi ideig futhat a szimulátor, a következő szám bármi lehet (az interaktív ütemezőre vonatkozik), továbbá meg kell adni a processzusok számát és végül az erőforrások számát.

Az imént megadott processzus számnak megfelelően kell további sorokat beírni. Egy ilyen sor egy processzus adatait tartalmazza. A sor felépítése:

processzus azonosító (célszerű 1-től növekvő sorrendben számokat megadni)
szülőprocesszus azonosítója (interaktív ütemezőben van jelentősége)
processzus indulási ideje
processzus hossza
erőforrás használatok száma (ha nem 0 akkor továbbá ennyiszer 3 érték:)
- erőforrás lefoglalásának kezdete (processzus indulásához képest relatív)
- erőforrás azonosítója (nem lehet nagyobb mint az első sorban megadott érték)
- erőforrás használatának hossza (ha tovább tart mint a processzus, akkor a processzus befejezésekor feloldódik)

Amennyiben nem ezeknek a feltételeknek megfelelő értéket adunk meg, a program hibásan működhet.

Kimenet[szerkesztés]

A kimenetet a kotegeltUtemezes.txt-ben kapjuk meg. A fájl elején kevés tájékoztató szöveg található. A következő sorokban kontextuscserék és egyéb események némi információval, a végén összegző adatok vannak.

Adatstruktúra modell[szerkesztés]

A processzusok egy struktúrából létrehozott tömbben vannak eltárolva (proc[]).

Minden processzusról a következő adatok vannak eltárolva:

azonosító (ID)
indulási idő (start)
eddigi futási idő (runtime)
hossz (length)
erőforrás használatok száma (IOBlockNum)
erőforrás használatok adatai tömbben(IOBlock[ ][ ])
processzus státusza (state[ ])

Erőforráshoz fordulási adatok felépítése:

időpont (IOBlock[ ][0])
azonosító (IOBlock[ ][1])
időtartam (IOBlock[ ][2])

Ez egy erőforrás használatonként dinamikusan lefoglalt mátrix.

Processzusok státusza:

futtatható/még nem indult el/erőforrásra vár (state[0]=0/1/2)
ha erőforrásra vár akkor az erőforrás azonosítója (state[1])

Az erőforrásokról elvan tárolva, hogy használatban van e (resources[ ]). Ha egy erőforrás használatban van akkor resources[azonosító]=1, egyébként 0.

Egyéb változók:

maximális szimulátoridő (maxTime)
hátralévő szimulátoridő (maxRuntime)
utolsó kontextuscsere óta eltelt idő (Time)
aktuálisan futó processzus (actual)
segédváltozók (min,i,j,kontextuscserek,numOfResources,numOfProcess,file,out)

C kód:

typedef struct process
{
	int ID;
	int start;
	int runtime;
	int length;
	int IOBlockNum;
	int **IOBlock;
	int *state;
} Process;

Process *proc;
int *resources;
int numOfProcess;
FILE *out;
FILE *file;
int i,j;
int numOfResources;
int maxRuntime;
int Time;
int min;
int actual;
int maxTime;
int kontextuscserek=0;

Működés[szerkesztés]

Memóriafoglalás és beolvasás után inicializálásként az algoritmus megkeresi a leghosszabb hátralévő idejű processzust, majd innen indulva a legrövidebb futtathatót.

	min=0;	
	for(i=0;i<numOfProcess;i++)
	{
		
		if( proc[i].state[0]==0 &&  ( (proc[min].length-proc[min].runtime) < (proc[i].length-proc[i].runtime) ) )
		{
			min=i;
		}
	}
	for(i=0;i<numOfProcess;i++)
	{
		
		if( proc[i].state[0]==0 && (proc[i].length-proc[i].runtime!=0) && ( (proc[min].length-proc[min].runtime) > (proc[i].length-proc[i].runtime) ) )
		{
			min=i;
		}
	}
	actual=min;
	Time=0;
	maxTime=maxRuntime;

A fő algoritmus egy while(1)-ba van ágyazva mely csak akkor szakad meg, ha befejeződtek a processzusok, vagy lejárt a szimulátor ideje.

Az algoritmus minden ciklusban végignézi a processzusokat, és ha kell akkor elindítja a még nem futóakat és futtatható állapotba állítja azokat amelyek erőforrás miatt blokkolódtak, de az erőforrás felszabadult, és ezek után megkeresi a leghosszabb hátralévő idejűt. Ehhez viszonyítva megkeresi a legrövidebbet, kiszűrve azokat melyek éppen lefoglalnának egy már lefoglalt erőforrást, ezzel elkerülve a felesleges kontextuscserét.

	min=actual;
	for(i=0;i<numOfProcess;i++)
	{
		if( (proc[i].start <= maxTime-maxRuntime) && (proc[i].state[0]==1) )
		{
			proc[i].state[0]=0;
		}
		
		if( proc[i].state[0]==2 && resources[ proc[i].state[1] ]==0 )
		{
			proc[i].state[0]=0;
		}
		
			
		if( proc[i].state[0]==0 &&  ( (proc[min].length-proc[min].runtime) < (proc[i].length-proc[i].runtime) ) )
		{
		min=i;
		}
	}
	for(i=0;i<numOfProcess;i++)
	{
		if( proc[i].state[0]==0  &&  (proc[i].length-proc[i].runtime!=0) && ( (proc[min].length-proc[min].runtime) > (proc[i].length-proc[i].runtime) ) )
		{
			for(j=0;j<proc[i].IOBlockNum;j++)
			{
				if(proc[i].IOBlock[j][0]==proc[i].runtime && resources[ proc[i].IOBlock[j][1] ]==1)
				{
					break;
				}
			}
			if(j==proc[i].IOBlockNum)
			{
				min=i;
			}
		}
	}

A következő lépésbe megvizsgálja, hogy lejárt-e a szimulátor ideje vagy befejeződött e az össze processzus.

	if(maxRuntime==0)
	{
		fprintf(out,"%d azonosítójú processzus %d ideig futott és lejárt a szimulátor futási ideje.\n",proc[actual].ID,Time);
		break;			
	} else if( proc[min].length-proc[min].runtime ==0 )
	{
		fprintf(out,"%d azonosítójú processzus %d ideig futott majd véget ért és befejeződött a szimulátor.\n",proc[actual].ID,Time);
		break;
	}

Ezek után megvizsgálja, hogy történt-e valamilyen speciális esemény:

egy processzus blokkolódott, mert az erőforrás foglalt
befejeződött egy processzus és egy másik kapta meg a cpu-t
az aktuálisnál egy rövidebb hátralévő idejű processzus jelent meg, és megkapta a cpu-t

	if( proc[actual].state[0]==2)
	{
		fprintf(out,"%d azonosítójú processzus %d ideig futott majd blokkolódott mert %d azonosítójú erőforrás forglalt, %d azonosítójú kapta meg a cpu-t.\n",proc[actual].ID,Time,proc[actual].state[1],proc[min].ID);
		Time=0;
		actual=min;
		kontextuscserek++;
	} else if(proc[actual].length-proc[actual].runtime==0)
	{
		fprintf(out,"%d azonosítójú processzus %d ideig futott majd véget ért, %d azonosítójú kapta meg a cpu-t.\n",proc[actual].ID,Time,proc[min].ID);
		Time=0;
		actual=min;
		kontextuscserek++;
	}else if( actual!=min )
	{
		fprintf(out,"%d azonosítójú processzus %d ideig futott majd %d azonosítójú kapta meg a cpu-t mert rövidebb a hátralévő ideje.\n",proc[actual].ID,Time,proc[min].ID);
		Time=0;
		actual=min;
		kontextuscserek++;
	} else

Ha ezek közül egyik se következett be, akkor az aktuális processzus dolgozik tovább, és ha kell akkor lefoglalja a szükséges erőforrás, ha az szabad, ha nem akkor a státusza átállítódik blokkoltra és a következő ciklusban másik processzus kapja meg a cpu-t. Továbbá feloldja a feloldandó erőforrásokat és a futási időt számláló változók inkrementálódnak, valamint dekrementálódnak.

	 else
	{
		for(j=0;j<proc[actual].IOBlockNum;j++)
		{
			if( proc[actual].runtime == proc[actual].IOBlock[j][0] )
			{
				if( resources[ proc[actual].IOBlock[j][1] ]==0)
				{
					resources[ proc[actual].IOBlock[j][1] ]=1;
				} else
				{
					proc[actual].state[0]=2;
					proc[actual].state[1]=proc[actual].IOBlock[j][1];
					Time--;
					maxRuntime++;
					proc[actual].runtime--;
					break;
				}
			}
			if( proc[actual].runtime == proc[actual].IOBlock[j][0]+proc[actual].IOBlock[j][2] )
			{
				resources[ proc[actual].IOBlock[j][1] ] = 0;
			}
		}
		proc[actual].runtime++;
		Time++;
		maxRuntime--;
	}

Miután kilépett az algoritmus a program felszabadítja a lefoglalt memóriaterületeket, majd kilép.

Példa[szerkesztés]

initialize.cfg tartalma:

1000 9 10 3
1 0 0 64 1 8 1 10
2 1 5 40 1 2 2 10
3 1 10 3 1 0 1 2
4 1 10 4 0
5 2 15 30 1 0 2 2
6 0 20 20 0
7 0 20 10 1 3 3 2
8 0 20 10 1 4 3 2
9 3 15 12 0
10 9 15 14 0

A szimulátor lefuttatása után a kotegeltUtemezes.txt tartalma:

Kötegelt ütemező szimulátor (legrövidebb hátralévő idejű)
	-10 db processzus 
	-1000 időszelet a szimulátor maximális futásideje 

1 azonosítójú processzus 5 ideig futott majd 2 azonosítójú kapta meg a cpu-t mert rövidebb a hátralévő ideje.
2 azonosítójú processzus 5 ideig futott majd 3 azonosítójú kapta meg a cpu-t mert rövidebb a hátralévő ideje.
3 azonosítójú processzus 3 ideig futott majd véget ért, 4 azonosítójú kapta meg a cpu-t.
4 azonosítójú processzus 4 ideig futott majd véget ért, 9 azonosítójú kapta meg a cpu-t.
9 azonosítójú processzus 12 ideig futott majd véget ért, 7 azonosítójú kapta meg a cpu-t.
7 azonosítójú processzus 10 ideig futott majd véget ért, 8 azonosítójú kapta meg a cpu-t.
8 azonosítójú processzus 10 ideig futott majd véget ért, 10 azonosítójú kapta meg a cpu-t.
10 azonosítójú processzus 14 ideig futott majd véget ért, 6 azonosítójú kapta meg a cpu-t.
6 azonosítójú processzus 20 ideig futott majd véget ért, 2 azonosítójú kapta meg a cpu-t.
2 azonosítójú processzus 35 ideig futott majd véget ért, 5 azonosítójú kapta meg a cpu-t.
5 azonosítójú processzus 30 ideig futott majd véget ért, 1 azonosítójú kapta meg a cpu-t.
1 azonosítójú processzus 59 ideig futott majd véget ért és befejeződött a szimulátor.

a szimulátor teljes futási ideje: 207
kontextuscserék száma: 11

Interaktív processzus szimulátor (Round-Robin)[szerkesztés]

Bemutatás[szerkesztés]

Interaktív ütemező algoritmusok céljai:

Válaszidő - a kérésekre való gyors válasz
Arányosság - a felhasználók elvárásainak való megfelelés

Interaktív ütemező algoritmusok fajtái:

Round-robin ütemezés
Prioritásos ütemezés
Többszörös sorok
Legrövidebb processzus a következő
Garantált ütemezés
Sorsjáték-ütemezés
Pártatlan megosztásos (arányos) ütemezés

Round‐Robin ütemezés

Időszelet hossza adott
Kontexus csere – időt igényel
- Tfh. 1 ezred mp
- Az időszelet nagysága 4 ezred mp
- 20% elveszik
- Ha növeljük az időszelet nagyságát, akkor több (10) processzus esetén (100 ezred mp)
  - Sok kérés érkezik be rövid időn belül
  - Előfordulhat, hogy az utolsónak 1 mp kellene várnia, hogy sorra kerüljön
- Átlagos CPU használati periódusnál hosszabbra állítjuk
  - Blokkolódik → kontexus csere → idő
  - 20‐50 ezred mp elfogadott

Bemeneti specifikáció[szerkesztés]

A bemenetet az initialize.txt-ben kell elhelyezni és a programmal egy mappába másolni.

A fájl első sorába be kell írni először h mennyi ideig futhat a szimulátor, a következő szám a processzus maximális időszelete, továbbá meg kell adni a processzusok számát és végül az erőforrások számát.

Az imént megadott processzus számnak megfelelően kell további sorokat beírni. Egy ilyen sor egy processzus adatait tartalmazza. A sor felépítése:

processzus azonosító (célszerű 1-től növekvő sorrendben számokat megadni)
szülőprocesszus azonosítója (ha nincs akkor 0, vagy olyan érték amit nem adtunk meg processzus azonosítóként)
processzus indulási ideje (ügyelve arra hogy ha van szülőprocesszusa, akkor az után induljon)
processzus hossza (ha végtelenített, akkor -1)
erőforrás használatok száma (ha nem 0 akkor továbbá ennyiszer 3 érték:)
- erőforrás lefoglalásának kezdete (processzus indulásához képest relatív)
- erőforrás azonosítója (nem lehet nagyobb mint az első sorban megadott érték)
- erőforrás használatának hossza (ha tovább tart mint a processzus, akkor a processzus befejezésekor feloldódik)

Amennyiben nem ezeknek a feltételeknek megfelelő értéket adunk meg, a program hibásan működhet.

Kimenet[szerkesztés]

A kimenetet az interaktivUtemezes.txt-ben kapjuk meg. A fájl elején kevés tájékoztató szöveg található. A következő sorokban kontextuscserék és egyéb események némi információval, a végén összegző adatok vannak.

Adatstruktúra modell[szerkesztés]

A processzusok egy struktúrából létrehozott tömbben vannak eltárolva (proc[]).

Minden processzusról a következő adatok vannak eltárolva:

azonosító (ID)
indulási idő (start)
eddigi futási idő (runtime)
hossz (length)
erőforrás használatok száma (IOBlockNum)
erőforrás használatok adatai tömbben(IOBlock[ ][ ])
processzus státusza (state[ ])
szülőprocesszus azonosítója (parentID)

Erőforráshoz fordulási adatok felépítése:

időpont (IOBlock[ ][0])
azonosító (IOBlock[ ][1])
időtartam (IOBlock[ ][2])

Ez egy erőforrás használatonként dinamikusan lefoglalt mátrix.

Processzusok státusza:

futtatható/még nem indult el/erőforrásra vár (state[0]=0/1/2)
ha erőforrásra vár akkor az erőforrás azonosítója (state[1])

Az erőforrásokról elvan tárolva, hogy használatban van e (resources[ ]). Ha egy erőforrás használatban van akkor resources[azonosító]=1, egyébként 0.

Egyéb változók:

processzusok maximális időszelete (maxProctime)
processzus hátralevő ideje (TimeLeft)
hátralévő szimulátoridő (maxRuntime)
eltelt idő (Time)
segédváltozók (i,j,kontextuscserek,numOfResources,numOfProcess,file,out)

C kód:

typedef struct process
{
	int ID;
	int start;
	int runtime;
	int length;
	int IOBlockNum;
	int **IOBlock;
	int *state;
	int parentID;
} Process;

Process *proc;
int *resources;
int numOfProcess;
FILE *out;
FILE *file;
int i,j;
int numOfResources;
int maxRuntime;
int maxProctime;
int Time;
int TimeLeft;
int kontextuscserek;

Működés[szerkesztés]

Memóriafoglalás és beolvasás után fő algoritmus egy while(1)-ba van ágyazva mely csak akkor szakad meg, ha befejeződtek a processzusok, vagy lejárt a szimulátor ideje.

Kezdésnek az algoritmus megállapítja az időszeletek számát, majd megvizsgálja hogy ha soron következő processzus blokkolt és az erőforrás még foglalt, akkor átugorja. Ha a processzus még nem indult el akkor megnézi hogy el kell e indítani, ha igen elindítja, egyébként következő processzusra ugrik.

	TimeLeft=(maxRuntime-Time >= maxProctime)?maxProctime:maxRuntime-Time;
	if(proc[i].state[0]==2 && resources[ proc[i].state[1] ] ==1 )
	{
		fprintf(out,"(%d) %d azonosítójú processzus blokkolva van, (%d azonosítójú erőforrásra vár) ezért nem kapja meg a cpu-t.\n",Time,proc[i].ID,proc[i].state[1]);
		Time++;
	} else if(proc[i].state[0]==1)
	{
		Time++;
		if( proc[i].start < Time )
		{
			proc[i].state[0]=0;
			continue;
		}
		(i==numOfProcess-1)?(i=0):(i++);
		continue;
		
	} else

Ekkorra már kiszűrődtek a nem futtatható processzusok. Ha a következő processzus végtelenített, vagy még nem fejeződött be akkor megkapja a cpu-t. Ha erőforrást akar használni akkor megnézi hogy szabad-e, ha igen lefoglalja ellenkező esetben blokkolódik és tovább adja a cpu-t a következő processzusnak. Ha már nincs szüksége az erőforrásra, akkor elengedi azt.

	else if( (proc[i].length==-1) || (proc[i].length-proc[i].runtime>0) )
	{
		proc[i].state[0]=0;
		fprintf(out,"(%d) %d azonosítójú processus megkapta a cpu-t ",Time,proc[i].ID);
		kontextuscserek++;
		for(j=0;j<proc[i].IOBlockNum;j++)
		{
			if( ( proc[i].runtime <= proc[i].IOBlock[j][0] ) && ( proc[i].runtime+TimeLeft > proc[i].IOBlock[j][0]) )
			{
				if(resources[ proc[i].IOBlock[j][1] ]==0)
				{
					resources[ proc[i].IOBlock[j][1] ]=1;
					fprintf(out,", %d időszelet után lefoglalta a(z) %d azonosítójú erőforrást ",proc[i].IOBlock[j][0] - proc[i].runtime, proc[i].IOBlock[j][1] );
					TimeLeft-= proc[i].IOBlock[j][0] - proc[i].runtime;
					proc[i].runtime+=proc[i].IOBlock[j][0] - proc[i].runtime;
				} else
				{
					fprintf(out,", %d időszelet után blokkolódott mert %d azonosítójú erőforrás foglalt.\n",proc[i].IOBlock[j][0] - proc[i].runtime , proc[i].IOBlock[j][1]);
					TimeLeft-= proc[i].IOBlock[j][0] - proc[i].runtime;
					proc[i].runtime+= proc[i].IOBlock[j][0] - proc[i].runtime;
					proc[i].state[0]=2;
					proc[i].state[1]=proc[i].IOBlock[j][1];
					TimeLeft=-TimeLeft;
					break;
				}
			}
			if( ( proc[i].runtime < proc[i].IOBlock[j][0]+proc[i].IOBlock[j][2] ) && ( proc[i].runtime+TimeLeft >= proc[i].IOBlock[j][0]+proc[i].IOBlock[j][2]) )
			{
				resources[ proc[i].IOBlock[j][1] ]=0;
				fprintf(out,", %d időszelet után elengedte a(z) %d azonosítójú erőforrást ",proc[i].IOBlock[j][0]+proc[i].IOBlock[j][2] - proc[i].runtime, proc[i].IOBlock[j][1] );
				TimeLeft-= proc[i].IOBlock[j][0]+proc[i].IOBlock[j][2] - proc[i].runtime;
				proc[i].runtime+=proc[i].IOBlock[j][0]+proc[i].IOBlock[j][2] - proc[i].runtime;
			}	
			if(TimeLeft<=0) break;	
		}

Megvizsgálja, hogy befejeződik-e az adott processzus ebben az időszeletben, ha igen akkor meghívja a leallit() függvényt. Ellenkező esetben futtatja a processzust míg le nem jár az ideje.

		if( (proc[i].length!=-1) && (TimeLeft >= proc[i].length-proc[i].runtime) )
		{
			fprintf(out,", %d időszelet után befejeződött a processzus.\n",proc[i].length-proc[i].runtime);
			fprintf(out,"\t Leállított gyerekprocesszusok azonosítója:\n");
			leallit(i);
			TimeLeft-= proc[i].length-proc[i].runtime;
			proc[i].runtime=proc[i].length;
						
		} else if((TimeLeft>0) && (proc[i].state[0]==0))
		{
			fprintf(out,", még %d időszeletig futott, majd lejárt a cpu ideje.\n",TimeLeft);
			proc[i].runtime+=TimeLeft;
			TimeLeft=0;
			
		} else if(TimeLeft==0)
		{
			fprintf(out,"és lejárt a cpu-ideje.\n");
		}
			
		Time+= maxProctime-((TimeLeft>=0)?(TimeLeft):(-TimeLeft))+1;
			
	} else

Ha nincs futtatható processzus, és nem lesz később se akkor kilép az algoritmus.

	else
	{
		int o=0;
		for(j=0;j<numOfProcess;j++)
		{
			o+= (proc[j].length==-1)?1:(proc[j].length-proc[j].runtime);				
		}
		if(o==0)
		{
			fprintf(out,"\nnincs több futtatandó processus...");
			break;
		}
	}

Mindezek után ha lejárt a szimulátor ideje, kilép az algoritmus. Egyébként a következő processzusra ugrik.

	
	if(Time>=maxRuntime)
	{
		fprintf(out,"\na szimulátor maximális ideje lejárt...");
		break;
	}

	(i==numOfProcess-1)?(i=0):(i++);

Végül a program felszabadítja a lefoglalt memóriaterületeket, majd visszatér.

Példa[szerkesztés]

initialize.cfg tartalma:

1000 9 10 3
1 0 0 64 1 8 1 10
2 1 5 40 1 2 2 10
3 1 10 3 1 0 1 2
4 1 10 4 0
5 2 15 30 1 0 2 2
6 0 20 20 0
7 0 20 10 1 3 3 2
8 0 20 10 1 4 3 2
9 3 15 12 0
10 9 15 14 0

A szimulátor lefuttatása után az interaktivUtemezes.txt tartalma:

Round-Robin ütemező szimulátor
	-10 db processzus 
	-1000 időszelet a szimulátor maximális futásideje 
	-9 időszelet a processus maximális futási ideje

(0) 1 azonosítójú processus megkapta a cpu-t , 8 időszelet után lefoglalta a(z) 1 azonosítójú erőforrást , még 1 időszeletig futott, majd lejárt a cpu ideje.
(11) 2 azonosítójú processus megkapta a cpu-t , 2 időszelet után lefoglalta a(z) 2 azonosítójú erőforrást , még 7 időszeletig futott, majd lejárt a cpu ideje.
(22) 3 azonosítójú processus megkapta a cpu-t , 0 időszelet után blokkolódott mert 1 azonosítójú erőforrás foglalt.
(24) 4 azonosítójú processus megkapta a cpu-t , 4 időszelet után befejeződött a processzus.
	 Leállított gyerekprocesszusok azonosítója:
(30) 5 azonosítójú processus megkapta a cpu-t , 0 időszelet után blokkolódott mert 2 azonosítójú erőforrás foglalt.
(32) 6 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(43) 7 azonosítójú processus megkapta a cpu-t , 3 időszelet után lefoglalta a(z) 3 azonosítójú erőforrást , 2 időszelet után elengedte a(z) 3 azonosítójú erőforrást , még 4 időszeletig futott, majd lejárt a cpu ideje.
(54) 8 azonosítójú processus megkapta a cpu-t , 4 időszelet után lefoglalta a(z) 3 azonosítójú erőforrást , 2 időszelet után elengedte a(z) 3 azonosítójú erőforrást , még 3 időszeletig futott, majd lejárt a cpu ideje.
(65) 9 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(76) 10 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(86) 1 azonosítójú processus megkapta a cpu-t , 9 időszelet után elengedte a(z) 1 azonosítójú erőforrást és lejárt a cpu-ideje.
(96) 2 azonosítójú processus megkapta a cpu-t , 3 időszelet után elengedte a(z) 2 azonosítójú erőforrást , még 6 időszeletig futott, majd lejárt a cpu ideje.
(106) 3 azonosítójú processus megkapta a cpu-t , 0 időszelet után lefoglalta a(z) 1 azonosítójú erőforrást , 2 időszelet után elengedte a(z) 1 azonosítójú erőforrást , 1 időszelet után befejeződött a processzus.
	 Leállított gyerekprocesszusok azonosítója:
	 9
	 10
(110) 5 azonosítójú processus megkapta a cpu-t , 0 időszelet után lefoglalta a(z) 2 azonosítójú erőforrást , 2 időszelet után elengedte a(z) 2 azonosítójú erőforrást , még 7 időszeletig futott, majd lejárt a cpu ideje.
(120) 6 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(130) 7 azonosítójú processus megkapta a cpu-t , 1 időszelet után befejeződött a processzus.
	 Leállított gyerekprocesszusok azonosítója:
(132) 8 azonosítójú processus megkapta a cpu-t , 1 időszelet után befejeződött a processzus.
	 Leállított gyerekprocesszusok azonosítója:
(134) 1 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(144) 2 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(154) 5 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(164) 6 azonosítójú processus megkapta a cpu-t , 2 időszelet után befejeződött a processzus.
	 Leállított gyerekprocesszusok azonosítója:
(167) 1 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(177) 2 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(187) 5 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(197) 1 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(207) 2 azonosítójú processus megkapta a cpu-t , 4 időszelet után befejeződött a processzus.
	 Leállított gyerekprocesszusok azonosítója:
	 5
(212) 1 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(222) 1 azonosítójú processus megkapta a cpu-t , még 9 időszeletig futott, majd lejárt a cpu ideje.
(232) 1 azonosítójú processus megkapta a cpu-t , 1 időszelet után befejeződött a processzus.
	 Leállított gyerekprocesszusok azonosítója:

nincs több futtatandó processus...
a szimulátor teljes futási ideje: 234
kontextuscserék száma: 29

Bankár algoritmus[szerkesztés]

Bemenet[szerkesztés]

A bemenetet a config.txt-ből olvassa be a program.

A fájl első sora tartalmazza az erőforrásosztályok(n) és a processzusok(m) számát.

A második sorban az első sorban megadott erőforrások számának megfelelő(n) szám van. Ezek az egyek erőforrásosztályok példányainak száma.

A következő sorokban(m) minden egyes processzusnak jut egy-egy sor.

A sorban az első érték a processzus erőforrás használatának száma(k). Ezután ennyiszer 3 szám(3*k): erőforrás osztály sorszáma (0 .. n-1); lefoglalás kezdete; használat ideje.

Kimenet[szerkesztés]

Az algoritmus a standard kimenetre írja ki, hogy mi történik ha egy processzus erőforrást igényel.

Fordítás, futtatás[szerkesztés]

Fordítás: javac feladat.BankarAlgoritmus.java

Futtatás: java feladat.BankarAlgoritmus

Működés[szerkesztés]

class process {

    public int[] foglalt;
    public int[] tobbi;
    public int[] max;
    public Request[] req;

    public int T=0;

    public process(int m,int r) {
        foglalt=new int[m];
        tobbi=new int[m];
        max=new int[m];
        req=new Request[r];

        for(int i=0;i<m;i++){
            foglalt[i]=0;
            tobbi[i]=0;
            max[i]=0;
        }
    }
}

Egy osztály a processzusoknak.

foglalt : melyik erőforrás osztályból mennyit foglal

tobbi : egyes erőforrásosztályokból mennyit fog még használni

max : teljes futása során melyik erőforrásosztályból mennyit fog használni

T : processzus futási ideje

class Request{

    public int num;
    public int time;
    public int length;

    public Request(int n,int t,int l) {
        num=n;
        time=t;
        length=l;
    }
}

Egy osztály az erőforrás kérések nyilvántartására.

num : erőforrás osztály azonosítója

time : igénylés ideje

length : használat ideje

    private int[] eroforrasokSzama;
    private int[] szabad;
    private process[] ps;

    private int Time=0;

eroforrasokSzama : az egyes erőforrás osztályok példányainak száma

szabad : az egyes erőforrás osztályokból mennyi áll még rendelkezésre

Time : futási idő

ps: információ a processzusokról

A program betölti a fájlt, majd beállítja a megfelelő változókat és elindul az algoritmus:

            for(;Time<1000;){
                proc: for(int i=0;i<ps.length;i++){
                    boolean s=true;
                    .
                    .
                    .
                    .
                    Time++;
                    if(s)ps[i].T++;
                }
            }

Maximum 1000 időszeletig fut. Minden időszeletben végignézi a processzusokat, majd növeli a futási időket.

                        if(ps[i].req[j].time+ps[i].req[j].length== ps[i].T){
                            int forras=ps[i].req[j].num;
                            szabad[forras]++;
                            ps[i].foglalt[forras]--;
                            System.out.println(Time+". idoszeletben, "+i+". processz elengedte "+ps[i].req[j].num+". eroforrast.");
                        }

Ha egy processzus elenged egy erőforrást, akkor növeli az adott erőforrás osztály példányainak számát és csökkent a processzus által foglaltak számát.

if(ps[i].req[j].time==ps[i].T){
                            if(szabad[ps[i].req[j].num]>0){
                                int forras=ps[i].req[j].num;
                                szabad[forras]--;
                                ps[i].foglalt[forras]++;
                                ps[i].tobbi[forras]--;

                                if(!safety()){
                                    szabad[forras]++;
                                    ps[i].foglalt[forras]--;
                                    ps[i].tobbi[forras]++;
                                    System.out.println(Time+". idoszelet nem biztonsagos, "+i+". processz nem megkapta "+ps[i].req[j].num+". eroforrast, hanem varakozik.");
                                    s=false;
                                } else {
                                    System.out.println(Time+". idoszelet biztonsagos, "+i+". processz megkapta "+ps[i].req[j].num+". eroforrast.");
                                }
                            } else {
                                s=false;
                                System.out.println(Time+". idoszeletben "+i+". processz nem megkapta "+ps[i].req[j].num+". eroforrast, mert az osszes foglalt, ezert varakozik.");
                            }
                        }

Ha egy processzus erőforrást akar foglalni, és abból az erőforrásból van szabad, akkor úgy csinál mintha odaadta volna neki és meghívja a safety() függvényt, ami megvizsgálja, hogy biztonságos e az így kialakult állapot. Ha igen, akkor jóváhagyja az erőforrás igénylést. Ha nem, akkor visszaállítja az állapotot és várakoztatja a processzust. Ha nincs szabad erőforrás, akkor szintén várakoztatja.

    private boolean safety(){
        int[] temp=new int[szabad.length];
        System.arraycopy(szabad, 0, temp, 0, szabad.length);

        boolean[] marks=new boolean[ps.length];
        for(int i=0;i<marks.length;i++){
            marks[i]=false;
        }
        main:while(true){
            boolean s=true;
            for(int i=0;i<marks.length;i++){
                if(!marks[i])s=false;
            }
            if(s)return true;

            for(int i=0;i<ps.length;i++){
                s=true;
                for(int j=0;j<temp.length;j++){
                    if(ps[i].tobbi[j]>temp[j])s=false;
                }
                if(s && !marks[i]){
                    for(int j=0;j<temp.length;j++){
                        temp[j]+=ps[i].tobbi[j];
                    }
                    marks[i]=true;
                    continue main;
                }
            }
            return false;
        }
    }

A safety() függvény:

Létrehoz egy ideiglenes tömböt (temp) amibe belemásolja a szabad erőforrásokat. A marks tömbben tárolja ha egy processzust megjelölt. Ha minden processzus megvan jelölve akkor biztonságos az állapot. Ezután keres egy processzust ami ha most igényelné az összes erőforrását kilehetne szolgálni, majd megjelöli ezt a processzus és arra az állapotra ugrik ahol az ezeket az erőforrásokat mind elengedi. Következő lépésben újra megnézi hogy van e még jelöletlen processzus, ha van akkor újra keres egyet... és így tovább.

Ha nincs ilyen processzus és még van jelöletlen, akkor az állapot nem biztonságos.

Példa[szerkesztés]

config.txt tartalma:

3 4
2 2 2
2 0 10 10 1 11 4
3 0 2 4 1 4 2 2 10 2
1 1 0 1
1 2 3 4

Standard kimenet:

2. idoszelet biztonsagos, 2. processz megkapta 1. eroforrast.
6. idoszeletben, 2. processz elengedte 1. eroforrast.
9. idoszelet biztonsagos, 1. processz megkapta 0. eroforrast.
15. idoszelet biztonsagos, 3. processz megkapta 2. eroforrast.
17. idoszelet biztonsagos, 1. processz megkapta 1. eroforrast.
25. idoszeletben, 1. processz elengedte 0. eroforrast.
25. idoszeletben, 1. processz elengedte 1. eroforrast.
31. idoszeletben, 3. processz elengedte 2. eroforrast.
40. idoszelet biztonsagos, 0. processz megkapta 0. eroforrast.
41. idoszelet biztonsagos, 1. processz megkapta 2. eroforrast.
44. idoszelet biztonsagos, 0. processz megkapta 1. eroforrast.
49. idoszeletben, 1. processz elengedte 2. eroforrast.
60. idoszeletben, 0. processz elengedte 1. eroforrast.
80. idoszeletben, 0. processz elengedte 0. eroforrast.

Kör keresése gráfban[szerkesztés]

Bemenet[szerkesztés]

A gráfot a graf.txt-ből olvassa be.

A fájl első sora a gráf csúcsainak száma.

Ezután minden csúcsnak egy-egy sor melyekben a csúcsból kiinduló élek végpontjai vannak. Ha nincs kiinduló él, akkor üresen kell hagyni.

Erőforrások és processzusok ábrázolhatóak gráfban azzal a feltétellel, hogy minden erőforrás tartozik egy processzushoz. Több erőforrás osztály példány esetén az erőforrásból kiinduló éleknek meg kell egyezni a példányok számával. Ezeknek a feltételek megfelelő bemenet esetén a kör találat egyben holtpontot is jelent.

Kimenet[szerkesztés]

Ha kör van a gráfban, akkor a standard kimeneten megjelenik az üzenet, egyébként nincs kimenet.

Fordítás, futtatás[szerkesztés]

Mélységi keresés:

Fordítás: javac feladat.HoltpontDetektalas.java

Futtatás: java feladat.HoltpontDetektalas

Mátrixos keresés:

Fordítás: javac feladat.HoltpontDetektalasMatrixal.java

Futtatás: java feladat.HolpontDetektalasMatrixal

Működés[szerkesztés]

Mélységi kereső:

    private int[][] graf;
    private int[] jart;

graf : a fájlból beolvasott táblázat a gráfról

jart : minden egyes csúcsról információ (0:még nem jártunk itt ,1:ezen az úton vagyunk ,2: elhagytuk ezt az utat)

Fájl megnyitása és a gráf betöltése után minden egyes pontra meghívódik a bejar() függvény ameddig nem találunk egy kört.

            for(int i=0;i<graf.length;i++){
                for(int j=0;j<jart.length;j++) jart[j]=0;
                if(bejar(i)) break;
            }

A bejar() függvény a paraméterül kapott pont jart tömbbeli rá vonatkozó elemét 1-re állítja, ezzel jelezve hogy itt már voltunk. Ezután a pontból kiinduló éleken elindul és ha talál egy olyan pontot ahol már jártunk (jart[..]==1) akkor kört talált és kilép. Ha olyan pontot talál ahol még nem jártunk akkor rekurzívan meghívja a bejar() függvényt arra a pontra.

    private boolean bejar(int d){
        jart[d]=1;
        for(int i=0;i<graf[d].length;i++){
            if(jart[graf[d][i]]==1){
                System.out.println("Kör van: "+graf[d][i]+".  csúcsnál");
                return true;
            }else if(jart[graf[d][i]]==0){
                if(bejar(graf[d][i])){
                    return true;
                }
            }
        }
        jart[d]=2;
        return false;
    }

Mátrixos kereső:

    private int[][] m,t,s;

m : mátrix az élet nyilvántartására

t : mátrix az x hosszú utak tárolására

s : segédmátrix a szorzáshoz

Miután beöltötte a gráf adatait a mátrixba, feltölti t tömböt az 1 hosszú utakkal, vagyis m-el. Ezután mindaddig meghívja a szoroz() függvény amíg kört nem talál. (maximum 50 hosszú utakat keres)

            for(int k=0;k<50;k++){

                if(szoroz()){
                    System.out.println("Kör van a gráfban");
                    break;
                }
            }

A szoroz() függvény s-be kiszámolja m és t mátrix szorzatát, majd s-t átmásolja t-be. Végül megnézi van e 0-nál nagyobb szám t mátrix átlójában. Ha van akkor ez azt jelenti hogy egy pontból eljuthatunk önmagába egy x hosszú úton, tehát kört talált.

    private boolean szoroz(){

        for(int i=0;i<m.length;i++){
            for(int j=0;j<m.length;j++){
                int v=0;
                for(int k=0;k<m.length;k++){
                    v+=t[i][k]*m[k][j];
                }
                s[i][j]=v;
            }
        }

        for(int i=0;i<m.length;i++){
            t[i]=s[i];
        }
        t=s;

        for(int i=0;i<m.length;i++){
            if(t[i][i]>0){
                return true;
            }
        }
        return false;
    }

Példa[szerkesztés]

graf.txt tartalma:

Mélységi kimenete:

Kör van: 4.  csúcsnál

Mátrixos kimenete:

Kör van a gráfban