4. feladat

Feladva okt. 26-nov. 1., 2009

Határidő nov. 21., 2009

Szemaforok és osztott memória

 

Feltöltendő állomány(ok) neve: S04_nn_xxxxxxxx(_aa).c, ahol nn - feladat száma; xxxxxxxx - felhasználó azonosítója a linux szerveren; (aa - az illető állomány funkcionalitásának valamilyen ismertető jegye több modul használata esetén)

Megjegyzés:

  • Az alábbi feladatokban, valahányszor arról van szó, hogy egy osztott-memória területhez konkurens módon több folyamat is próbál hozzáférni, a helytelen adatok elkerülése végett szemafort fogunk használni. Kerüljük az aktív várakozást!
  • A leadott laborfeladat forrásszövegében minden egyes deklarált szemafor mellé írjuk oda megjegyzésként, hogy a feladatban mire használjuk az illető szemafort.

 

 

  1. Írjunk programot, mely létrehoz egy osztott-memória területet, amely egy p egész számot, illetve egy m elemű, 0-értékekkel inicializált számsorozatot tartalmaz. Egy másik program a következőket hajtja végre egy végtelen ciklusban: az osztott-memória területen levő p értéktől függően megváltoztatja a sorozat p. pozíciójában levő 0 elem értékét 1-re és fordítva, majd generál egy 1 és m közötti véletlen számot, és beírja az osztott memória területre a p értékét felülírva.

Az első program ellenőrzi időnként az osztott-memória területet, és ha egy n számnál több 1-es van a tömbben, akkor felszabadítja az osztott-memória területet és SIGTERM jelzést küld az osztott-memória területhez hozzárendelt többi folyamatnak.

  1. Hozzunk létre egy osztott-memória területet, melyet két "torpedózó" játékos használ. Az osztott-memória terület tartalmazzon egy játékos-azonosítót, a célpont sor- és oszlopszámát, és egy 0 (ha az előző lövés talált) vagy 1 (ha az előző lövés nem talált) vagy -1 (ha az előző lövés teli találat volt) értéket. Egy játékos csak akkor lép be a játékba, ha nincs még két játékos, aki már játszik. A játékosnak megfelelő programban egy 12x12-es mátrixot generálunk, melyen 7 egymás utáni (vízszintes vagy függőleges) pozíciót megjelölünk. A következő célpont kijelölése vagy a billentyűzetről történik vagy egy intelligens algoritmus segítségével.

 

 

  1. Írjunk programot, mely létrehoz egy osztott-memória területet, egy 0 és 1 értékeket tartalmazó mátrixszal. Egy másik program n másodpercenként soronként végigjárja a mátrixot, és amennyiben valamelyik mátrixelem szomszédságában több, mint 5 1-es érték van, akkor ez az elem értéke is 1 lesz, ha pedig több, mint 5 0-s szomszédja van, 0-vá válik ő is. Az a folyamat, amelyik létrehozta az osztott-memória területet kiírja a mátrixot mindaddig, ameddig már nem változik többé. (vigyázat! A mátrixot módosító folyamat külön tartsa nyilván a mátrix korábbi értékét, és annak alapján módosítsa az osztott memóriába írt mátrixelemeket.)

 

 

  1. Létrehozunk két osztott-memória területet, melyeken három folyamat osztozik majd. Az A folyamat mindkét osztott-memória területhez hozzáférhet, a B és C folyamat pedig csak egy-egy meróriaterülethez kettő közül. A B és a C folyamatok egy-egy számot generálnak, és beírják azt arra az osztott-memória területre, amelyhez hozzá vannak rendelve. Az A folyamat olvassa a számokat a két osztott-memória területről és kiírja azokat. Ezután (miután az A folyamatnak sikerült kiolvasnia az általuk korábban beírt számot) a B és C folyamat újból generál egy-egy számot. Mindez 10-15 alkalommal ismétlődik.

 

 

  1. Hozzunk létre egy 9*sizeof(int) méretű osztott-memória területet. Két folyamat fog hozzákapcsolódni ehhez és X-0-t játszanak. A két folyamat szemafor segítségével is kommunikál, jelezve a másik folyamatnak, hogy most ő a soros. Az osztott-memória terület tartalmát írjuk ki a képernyőre miden lépés után.

 

 

  1. Egy program létrehoz egy osztott-memória területet, egy 0 és 1 értékeket tartalmazó mátrixszal. Egy másik program n másodpercenként oszloponként végigjárja a mátrixot, és amennyiben valamelyik mátrixelem szomszédságában 5 db. 1-es érték van, akkor ez az elem értéke is 1 lesz, ha pedig 5db. 0-s szomszédja van, 0-vá válik ő is. Az a folyamat, amelyik létrehozta az osztott-memória területet, kiírja a mátrixot mindaddig, ameddig az már nem változik többé. (vigyázat! A mátrixot módosító folyamat külön tartsa nyilván a mátrix korábbi értékét, és annak alapján módosítsa az osztott memóriába írt mátrixelemeket.)

 

 

  1. Egy program létrehoz egy osztott-memória területet, egy 0 és 1 értékeket tartalmazó mátrixszal. Egy másik program n másodpercenként spirál formájában végigjárja a mátrixot, és amennyiben valamelyik mátrixelem szomszédságában kevesebb, mint 3 db. 1-es érték van, akkor ennek az elemnek az értéke 1 lesz, ha pedig kevesebb, mint 3 db. 0-s szomszédja van, akkor 0-vá válik. Az a folyamat, amelyik létrehozta az osztott-memória területet, kiírja a mátrixot mindaddig, ameddig az már nem változik többé. (vigyázat! A mátrixot módosító folyamat külön tartsa nyilván a mátrix korábbi értékét, és annak alapján módosítsa az osztott memóriába írt mátrixelemeket.)

 

 

  1. Hozzunk létre három osztott-memória területet. Két folyamat fog hozzájuk kapcsolódni. Az A folyamat a három osztott-memória terület közül véletlenszerűen választ egyet, amelyikbe 1-et ír, a másik kettőbe 0-t, majd jelzi egy szemafor segítségével a B folyamatnak, hogy ő következik. A B folyamat találomra választ egyet a három osztott-memória terület közül, melynek kiolvassa a tartalmát. Ha éppen azt olvasta, amelyiknek az értéke 1, kiírja a képernyőre, hogy nyert, különben azt, hogy veszített. A játék 10-15 alkalommal megismétlődik.

 

 

  1. A termelő/fogyasztó problémája:

A termelő fogyasztási cikkeket termel, melyeket elhelyez egy futószalagon (véges puffer).

A fogyasztó sorban leveszi a szalagról a termékeket és elfogyasztja őket.

A fenti tevékenység a következő feltételek közt megy végbe:

  • a termelő bármilyen időpillanatban termelhet fogyasztási cikket
  • a fogyasztó csak akkor vehet terméket a szalagról, ha az nem üres
  • a fogyasztó ugyanabban a sorrendben fogyasztja el a termékeket, mint amilyen sorrendben termelte őket a termelő
  • a termelő telített fotószalagra (tel pufferbe) nem helyezhet újabb cikket
  • minden egyes megtermelt fogyasztási cikk el lesz fogyasztva

 

 

  1.  Az író/olvasó probléma:

Tekintsünk egy könyvet, melyhez több író és olvasó szeretne hozzáférni. Megengedett, hogy egyszerre több olvasó olvassa a könyvet, viszont ha egy író dolgozik a könyvön (hozzáír, töröl, módosít, stb.), akkor rajta kívül sem más író sem más olvasó nem férhet hozzá a könyvhöz. Pontosabban:

  • egy olvasó akkor és csakis akkor foghat hozzá az olvasáshoz, ha egyetlen író sem írja éppen a könyvet.
  • egy író akkor és csakis akkor foghat hozzá az íráshoz, ha egyetlen olvasó és egyetlen más író sem foglalkozik a könyvvel.

Szimuláljuk a könyvolvasás, illetve írás műveleteit.

 

  1.  A kínai filozófusok problémája:

Egy kerek asztalnál 5 kínai filozófus ül. Legfőbb tevékenységük a gondolkodás, de természetesen időnként enniük is kell valamit. Az evéshez két pálcát használ mindenikük. Tudva, hogy minden két filozófus között van egy pálcika, és hogy egy filozófus csak akkor ehet, ha mind a jobboldalán, mind a baloldalán levő pálcikát felemelte, szimuláljuk az asztalnál ülő filozófusok tevékenységét.

 

  1.  Az álmos borbély problémája:

Egy borbély borbélyüzlete két helységből áll: az egyik a váróterem, a másik pedig az, ahol a kliensek a borbélyszékbe ülnek, hogy megborotválják őket. Ha nincs kliense, az álmos borbély lefekszik és alszik. Pontosabban:

  • a borbély kezdetben, illetve miután megborotvált valakit, kinéz a váróterembe. Ha van kliens, betessékeli az elsőt, és leülteti a borbélyszékre; ha nincs kliens, akkor a borbély maga ül a székbe, és alszik.
  • minden kliens, amikor belép a váróterembe, leül a sor végére; ha egyedül van a szobában, akkor kopog a borbélyszékes szoba ajtaján és felébreszti a borbélyt