Határidő: 2019. május 2.
Becsült programozási idő: 2-5 óra

Készítsen egy programot, amely lapcsere algoritmusok működését szimulálja!

A program bemeneteként memóriaműveletek során hivatkozott lapok azonosítóit kapja a hivatkozásuk sorrendjében.
Kimeneteként a végrehajtott lapcserék eredményeképpen lefoglalt fizikai memóriakeretek azonosítóit és a laphibák számát adja vissza.
A rendszerben 4 memóriakeret található, amely kezdetben mind üres. Az induláskor a lapok a cserehelyen találhatók.

A lapokat számok (1-99), a kereteket betűk (A,B,C és D) jelölik.

Bemenet (standard input, stdin)

Egyetlen sorban a lapokra történő hivatkozások egymástól vesszővel elválasztva. Például:

1,2,3,4,1,5,1

A bemenet végét egy üres sor (utána EOF) jelzi. Ekkor kell a kimenetre kiírni az eredményt.

Kimenet (standard output, stdout)

A kimeneten a bemeneti memóriahivatkozások kiszolgálásához lefoglalt memóriakeretek szerepelnek szóközök nélkül egybeírva, majd a következő sorban a laphibák száma.
Amennyiben egy memóriahivatkozáshoz nem kellett új keretet foglalni, a kimeneten az adott pozícióban - jel jelenik meg.
Ha egy memóriafoglalás nem teljesíthető, akkor a kimeneten * karakter jelenik meg (a műveletet nem ismétli meg az algoritmus).

Megvalósítandó algoritmusok, pontozás és kimenetek a fenti bemenetre

 1. FIFO lapcsere (1 pont)

A program kimenetének első és második sorában írja ki a FIFO lapcsere algoritmus szerinti foglalásokat és a laphibák számát.

ABCD-AB
6

2. Legrégebben nem használt (least recently used, LRU) lapcsere (1 pont)

Az előadáson ismertetett egyszerű LRU implementációt kell készíteni, amely hivatkozási idő szerint rendezi csökkenő sorba a kereteket.
A kimenet harmadik és negyedik sorában írja ki az LRU lapcsere algoritmus szerinti foglalásokat és a laphibák számát.

ABCD-B-
5

3. LRU + tárba fagyasztás (page locking) (1 pont)

Módosítsa úgy az LRU programját, hogy alkalmazza a tárba fagyasztás (page locking) technikát (az első hivatkozásig vagy maximum a lapbehozás utáni 5 memóriaművelet idejére).
A program kimenetének ötödik és hatodik sora az LRU algoritmus módosított változatának foglalásait és a laphibák számát tartalmazza.

ABCD-A*
6

Összesen 3 pont szerezhető. 1 IMSc pont jár mind a három feladat hibátlan megoldásáért.

A beadás menete

A megoldásokat a HF portálon kell beadni, ahol automatikusan ellenőrizzük azokat, és rövid időn belül visszajelzést adunk a helyességükről / hibákról. Ezután lehetőség van javításra és új program beküldésére.

Technikai információk

A programot Java nyelven kell elkészíteni, és a HF portálon kell leadni a megadott határidőig.

A beküldött Java programnak tartalmaznia kell egy "Main" nevű osztályt, melynek része a feladatot megoldó "main" függvény. A program tetszőleges számú forrásfájlból állhat. A program nem használhat a standard inputon és outputon kívül semmilyen más erőforrást, így nem végezhet fájlműveleteket és nem nyithat hálózati kapcsolatokat.

A programnak mindhárom részfeladatra kimenetet kell produkálnia (összesen 6 sor). Ha valamelyik algoritmussal nem foglalkozik, akkor adjon meg egy rögzített rövid (hibás) kimenetet.