2. gyakorlat

Kölcsönös kizárás

Az első gyakorlaton bemutatott szószámlálás példája is jól szemléltette, hogy a közös memóriát használó párhuzamos programozás fő kihívása a folyamatok által közösen használt változók kezelése. Amikor több szál ugyanazon a változón vagy adatszerkezeten (erőforráson) osztozik, elkerülhetetlenül felmerülnek olyan problémák, amelyek nem megfelelő kezelés esetén hibás programvégrehajtáshoz vagy helytelen eredményhez vezethetnek.

A versenyhelyzetek akkor jelentkeznek, amikor több szál egy időben próbál hozzáférni és módosítani egy közös erőforrást (pl. egy számlálót), és a végrehajtás sorrendje meghatározza az eredményt.

Race condition

• A képen két szál használja a közös erőforrást (változót), majd (közel) egyidőben kiolvassák a változó értékét, amely 6-ot tartalmaz.
• A Thread-1 2-vel növeli ad az eredeti változót, majd visszaírja az eredményt.
• A Thread-2 4-et ad az eredeti változóhoz, majd szintén visszaírja az eredményt.
• A szálak ütemezését követően Thread-2 művelete történik meg később, így a változó érteke 10 lesz az elvárt (6+4+2=) 12 helyett.

Ez a probléma abból adódik, hogy a kiolvasás-módosítás-visszaírás folyamata nem megszakíthatatlanul történik, így szükség lehet olyan mechanizmusokra, amelyek képesek kezelni a kölcsönös kizárást (mutual exclusion). További gyakorlati példák, ahol szükség lehet a versenyhelyzetek kezelésére:

• Banki tranzakciók során: Egy számlaegyenleg frissítése hibás lehet, ha két tranzakció egyszerre hajtódik végre.

• Fájlkezelésben: Egy fájlhoz való egyidejű írás megsértheti az adatok integritását.

• Többfelhasználós rendszerekben: Egy erőforrás (pl. adatbázis) egyidejű használata helytelen állapotot eredményezhet.

A párhuzamos programozás során azokat a kódrészleteket, amelyek hozzáférnek és módosítanak közös változókat (tipikusan az erőforrásokat kezelő programrészeket) kritikus szakaszoknak nevezzük. Ezeket a szakaszokat kell megfelelő módon jelölni, hogy a végrehajtás során egy időpillanatban csak egy szál férhessen hozzájuk.

Folyamatinterakciók: kölcsönös kizárás

A kölcsönös kizárás célja, hogy megakadályozza több szál egyidejű hozzáférését egy kritikus szakaszhoz. Ez azt jelenti, hogy az erőforrás kritikus szekciójában bármely időpillanatban legfeljebb egy folyamat tartózkodhat. A kölcsönös kizárás megvalósítására több eszköz és mechanizmus áll rendelkezésre, ezek közül a leggyakoribbak a semaphore, a lock és a monitor.

• Semaphore: Egy számláló alapú szinkronizációs mechanizmus, amely lehetővé teszi, hogy több szál osztozzon egy erőforráson, de korlátozza, hogy hány szál férhet hozzá egyszerre.

• Lock: A kritikus szakaszokat zárolással védjük - egy szálnak először meg kell szereznie a zárat (lock) egy függvényhívással, majd a kritikus szakasz végrehajtása után el kell engednie (unlock) a zárolást.

• Monitor: A monitor egy magasabb szintű szinkronizációs mechanizmus, amely a lock felett helyezkedik el, és általában egy objektumhoz vagy adatstruktúrához tartozik, biztosítva a szálak közötti kölcsönös kizárást és az együttműködést.

A monitor Java-ban

Monitor

A monitor egy olyan objektumnak tekinthető, amelynek minden adattagja privát, és rendelkezik publikus metódusokkal, valamint konstruktorral. A privát adattagok jelentik a szálak által használt közös erőforrást, és a hozzá tartozó kritikus szakaszokat a publikus metódusok törzseiben helyeztük el. Ez lehetővé teszi, hogy a fordítóprogram impliciten elhelyezzen olyan utasításokat a monitor metódusai előtt és után, amelyek végrehajtják az erőforrás zárolását és feloldását. A monitor működésének fontos része a feltételváltozó (condition variable), amely egy várakozási sor formájában működik. A szálak a feltételváltozó segítségével várakoznak, amíg egy bizonyos esemény vagy feltétel teljesül, például amíg egy erőforráshoz való hozzáférés lehetősége újra elérhetővé válik.

Mivel a monitor egy osztály jellegű konstrukció, a Java tervezői azt a megoldást választották, hogy bármelyik Java osztály felruházható monitor jellegű tulajdonságokkal. Java-ban a synchronized kulcsszót használhatjuk kölcsönös kizáráshoz. A synchronized kulcsszóval ellátott blokkok vagy metódusok csak akkor biztosítanak kölcsönös kizárást egymás között, ha ugyanazon objektum zárolására vonatkoznak.

Névütközés

Az elnevezések szerencsétlenül keverednek mostantól, mert a Java arra használja a szinkronizált kulcsszót, amit mindenki más a Java megjelenéséig kölcsönös kizárásnak nevezett. Szinkronizációnak viszont azt neveztük, amikor egy folyamat bevár egy másikat.

Synchronized blokk

Ebben az esetben explicit módon meg kell mondani, hogy mely osztályból példányosított objektum lesz a monitor, amelynek az implicit zárja felhasználásra kerül, amikor a synchronized kulcsszóval ellátott kódrészlet van végrehajtás alatt. Ha ezidő alatt egy másik szál próbálja zárolni ugyanazt az objektumot, akkor annak várakoznia kell, amíg a zárolás fel nem szabadul.

public class SynchronizedBlock {
    private Object object = new Object();

    public void perform() {
        synchronized (object) {
            // Kritikus szakasz
        }
    }
}

object objektum

Ebben a példában az object elnevezésű objektum biztosítja (ez lesz a monitor), hogy egyszerre csak egy szál léphessen be a kritikus szakaszba. A synchronized blokkban nem szükséges külön object változót definiálni, használhatjuk az aktuális objektumot is (synchronized (this) { .. }). Ez egyszerűbb szinkronizációs eseteknél megfelelő lehet, de ha "finomabb" vezérlésre van szükség, akkor érdemes dedikált objektumot használni.

Synchronized metódus

A metódus szintű kölcsönös kizárás egyszerűbbé teszi a kritikus szakasz használatát, mivel az egész metódus automatikusan kritikus szakaszként fog viselkedni. A metódus szintű kölcsönös kizárás szintén a synchronized kulcsszóval érhető el.

public class SynchronizedMethod {

    public synchronized void perform() {
        // Kritikus szakasz
    }
}

Az előző órán már megtanultuk azt, hogy egy szál az életciklusa során különböző állapotokat vehet fel. Most nézzük meg az alábbi példa segítségével, hogy kölcsönös kizárást alkalmazva milyen módon kerül egy szál a BLOCKED állapotba:

public class ThreadStateBlocked {
    public static void main(String[] args) throws InterruptedException {
        Object lock = new Object();
        Thread thread1 = new BlockedThread(lock);
        Thread thread2 = new BlockedThread(lock);

        thread1.start();
        Thread.sleep(100); // Biztosítjuk, hogy thread1 szerezze meg a zárat először
        thread2.start();

        Thread.sleep(100); // Rövid várakozás, hogy thread2 blokkolt állapotba kerüljön
        System.out.println(thread1.getState()); // TIMED_WAITING
        System.out.println(thread2.getState()); // BLOCKED
    }
}

class BlockedThread extends Thread {
    final Object lock;

    public BlockedThread(Object lock) {
        this.lock = lock;
    }

    @Override
    public void run() {
        synchronized (lock) {
            try {
                Thread.sleep(500); // A másik szál blokkolva lesz, amíg a zár használatban van
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
    }
}

Hatékony zárolás

A túlzott vagy rosszul megválasztott stratégia a kölcsönös kizárásra problémákhoz vezethet, és hibákat is okozhat. Ha feleslegesen zárolsz erőforrásokat, az csökkenti a program teljesítményét, mivel a zárolás és a feloldás költsége jelentős lehet a művelet időtartamához képest. Ha a zárolás nem egyértelműen ugyanazt az erőforrást védi mindenhol, például, ha két metódus különböző monitorokat használ ugyanahhoz az erőforráshoz, a kölcsönös kizárás nem érvényesül.

Ajánlás

• Ahelyett, hogy egy teljes metódust zárolnál, csak a kritikus szakaszhoz tartozó kódot zárold.
• Használj különálló zárolásokat az egymástól független erőforrásokhoz.
• Minden közös erőforrást ugyanazzal a monitorral védj.
• Ne zárold hosszú időre az objektumokat.
• A versenyhelyzetek és más szinkronizációs problémák gyakran csak bizonyos körülmények között jelentkeznek, ezért a párhuzamos programokat alapos tesztelésnek kell alávetni.

public class ExcessiveSynchronization {
    private final Object object = new Object();

    public synchronized void method1() {
        System.out.println(Thread.currentThread().getName() + " executing method1");
    }

    public void method2() {
        System.out.println("Ez a kiíratás nem része a kritikus szakasznak!");
        synchronized (object) {
            System.out.println(Thread.currentThread().getName() + " executing method2");
        }
    }
}

Holtpont (deadlock)

A deadlock akkor következik be, amikor két vagy több szál egymásra várakozik, mert mindegyik egy olyan objektum zárolására törekszik, amelyet egy másik szál már zárolt. Ilyenkor körkörös függés alakul ki a szálak között, ami azt eredményezi, hogy egyik szál sem képes felszabadítani a szükséges erőforrásokat, és így nem tud továbbhaladni. Ennek következtében a program futása megakad, és a rendszer holtpontba kerül.

public class DeadlockExample {
    private final Object object1 = new Object();
    private final Object object2 = new Object();

    public void method1() {
        synchronized (object1) {
            System.out.println(Thread.currentThread().getName() + " got object1");
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            synchronized (object2) {
                System.out.println(Thread.currentThread().getName() + " got object2");
            }
        }
    }

    public void method2() {
        synchronized (object2) {
            System.out.println(Thread.currentThread().getName() + " got object2");
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            synchronized (object1) {
                System.out.println(Thread.currentThread().getName() + " got object1");
            }
        }
    }

    public static void main(String[] args) {
        DeadlockExample example = new DeadlockExample();

        Thread thread1 = new Thread(new Runnable() {
            @Override
            public void run() {
                example.method1();
            }
        }, "Thread-1");

        Thread thread2 = new Thread(new Runnable() {
            @Override
            public void run() {
                example.method2();
            }
        }, "Thread-2");

        thread1.start();
        thread2.start();
    }
}

Magyarázat

• Thread-1 megszerzi a object1 zárat és vár a object2-re.
• Thread-2 megszerzi a object2 zárat és vár a object1-re.
• Mindkét szál megpróbálja megszerezni a másik szál által zárolt objektumot, és egyik sem tud továbbhaladni: a vezérlés holtpontba került.

Deadlock elkerülése

• Mindig ugyanabban a sorrendben szerezd meg a zárakat: Például mindig object1, majd object2 sorrendben.
• Kerüld a különböző monitorok kombinált használatát, minimalizáld az egyidejűleg használt monitorok számát.

A holtponthoz hasonló nemkívánatos jelenség az ún. éhezés (starvation), amikor ugyan nem alakul ki holtpont, de egy vagy több folyamat (szinte) soha nem kapja meg a szükséges erőforrásokat, mert más folyamatok folyamatosan megelőzik vagy kizárják a hozzáférésből, így nem tudja elvégezni feladatát.

A szálak várakoztatása és felébresztése

Bizonyos esetekben a monitor zárját megszerző szál nem tudja folytatni folytatni a futását, mert valamilyen feltétel nem teljesül. Ebben az esetben a szálat várakoztatni kell egy várakozási soron (condition variable) a feltétel teljesüléséig.

BLOCKED vs. WAITING

Képzeljük el, hogy egy parkolóház bejáratához egy sorompó (erőforrás) tartozik, amely az autókat (szálakat) engedi be. Az autó addig nem tud továbbhaladni, amíg a sorompó fel nem nyílik (tehát a szál blokkolva van). Miután a sorompó felnyílik és az autó behajtott, kiderül, hogy nincs szabad parkolóhely. Ilyenkor az autót félreállítják, és várakozó listára kerül, amíg egy parkolóhely felszabadul. Amikor egy autó elhagyja a parkolóházat a sorompó felnyitásával, a sofőr értesítést kap, hogy felszabadult egy hely.

• A wait() metódus Java-ban szolgál arra, hogy a szálakat várakoztassa egy adott feltétel teljesüléséig.

• Amikor egy szál a wait()-et hívja, felszabadítja a monitor zárolását, hogy más szálak hozzáférhessenek az erőforráshoz.

• A várakoztatott szál (amely ilyenkor WAITING állapotban van) egy másik szál notify() vagy notifyAll() hívására vár, hogy folytathassa a futását a zár ismételt megszerzésével.

• Ezek a metódusok csak synchronized blokk vagy metódus belsejében hívhatóak meg, különben IllegalMonitorStateException dobódik.

notify vs. notifyAll

A notify hatására a JVM választ egy szálat a várakozási sorból és feléleszti. A notifyAll hatására az összes várakozó szál felélesztésre kerül. Ha csak egy szálra van szükség, hogy folytassa a munkát, és nem számít melyik, akkor használjunk notify-t. Azonban ha a várakozó szálak különböző feltételek teljesülésére várnak, akkor használjunk notifyAll-t. Például:

A korábbi parkolóházas példát bővítsük ki a parkolóhely/autó méretével (kicsi vagy nagy). Tegyük fel, hogy várakozik 9 darab nagy és 1 darab kicsi méretű jármű. Egy kicsi méretű autó távozásakor, a notify csak egy szálat választ ki, így a nagyobb autók nem tudnák folytatni a parkolást. Ezzel szemben a notifyAll biztosítja, hogy minden várakozó szál értesítést kapjon, és a megfelelő szál (a nagy autó) folytathatja a munkát.

• Mivel a wait() hívása után a szál bármikor felébredhet, fontos, hogy a várakoztatási feltételt minden esetben újra ellenőrizzük, hogy biztosak legyünk abban, hogy a végrehajtás folytatható. Ezt if helyett while ciklus segítségével érthetjük el a legbiztosabban (hiszen egy felélesztett szál könnyen "versenyt" veszíthet egy másik felélesztett szállal szemben, ami így előbb megszerzi a monitort és módosítja a feltételt).

Termelő-fogyasztó probléma

A probléma általános definíciója szerint két különböző típusú szál létezik: termelő és fogyasztó. Mindkét típusból tetszőleges számú lehet. A termelők folyamatosan előállítanak valamilyen "terméket" (adatot), amelyeket a fogyasztók "feldolgoznak". A termékek az előállítás és a feldolgozás közötti időszakban egy tárolóban (buffer) kerülnek tárolásra, amely a közös erőforrást képviseli. Mivel a bufferhez minden folyamatnak hozzá kell férnie működése közben, annak hozzáférését megfelelően szabályozni szükséges a helyes működés érdekében. Ennek két fő feltétele van: egyrészt biztosítani kell a kölcsönös kizárást, másrészt garantálni kell, hogy üres bufferből a fogyasztók ne próbáljanak kivenni, illetve hogy tele bufferbe a termelők ne próbáljanak új elemet betenni.

A probléma kulcspontjai:

• A buffer nem tárolhat végtelen számú elemet.

• Ha megtelik, a termelőnek várakoznia kell (wait), amíg a fogyasztó helyet nem szabadít fel.

• Ha kiürül, a fogyasztónak várakoznia kell (wait), amíg a termelő új elemet nem helyez el.

• Az elemek bufferbe történő behelyezése és kivétele kizárólagos művelet kell, hogy legyen, azaz más szálak nem férhetnek hozzá a bufferhez, amíg a művelet be nem fejeződik (másszóval az egyidejű hozzáférés ki van zárva).

• Amikor új elem kerül a bufferbe, vagy egy elem kikerül, a várakozó szálakat értesíteni kell (notifyAll).

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class ProducerConsumerProblem {
    public static void main(String[] args) {
        int numberOfProducers = 20;
        int numberOfConsumers = 10;
        Buffer buffer = new Buffer(10);

        ArrayList<Thread> threads = new ArrayList<>();
        for (int i = 0; i < numberOfProducers; i++) {
            Producer producer = new Producer("Producer-" + i, buffer);
            threads.add(producer);
        }
        for (int i = 0; i < numberOfConsumers; i++) {
            Consumer consumer = new Consumer("Consumer-" + i, buffer);
            threads.add(consumer);
        }

        // Szálak indítása véletlenszerű sorrendben
        Collections.shuffle(threads);
        for (Thread thread : threads) {
            thread.start();
        }
    }
}

class Buffer {
    private final int maxSize;
    private final ArrayList<Integer> list;

    Buffer(int maxSize) {
        this.maxSize = maxSize;
        this.list = new ArrayList<Integer>();
    }

    synchronized void deposit() {
        while (list.size() == maxSize) { // Ha a buffer tele van, várakozunk
            System.out.println(Thread.currentThread().getName() + " is waiting for free space.");
            try {
                wait();
                // System.out.println(thread.getState()); // WAITING
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
        int item = new Random().nextInt(100); // Elem hozzáadása
        try {
            Thread.sleep(100); // Szimuláljuk a munkát
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        list.add(item);
        System.out.println(Thread.currentThread().getName() + " buffer: " + list);
        notifyAll();
    }

    synchronized void extract() {
        while (list.isEmpty()) { // Ha a buffer üres, várakozunk
            System.out.println(Thread.currentThread().getName() + " is waiting for an item.");
            try {
                wait();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }
        list.removeFirst(); // Elem kivétele a pufferből
        try {
            Thread.sleep(100); // Szimuláljuk a munkát
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        System.out.println(Thread.currentThread().getName() + " buffer: " + list);
        notifyAll();
    }
}

class Producer extends Thread {
    private final Buffer buffer;

    Producer(String name, Buffer buffer) {
        super(name);
        this.buffer = buffer;
    }

    @Override
    public void run() {
        buffer.deposit();
    }
}

class Consumer extends Thread {
    private final Buffer buffer;

    Consumer(String name, Buffer buffer) {
        super(name);
        this.buffer = buffer;
    }

    @Override
    public void run() {
        buffer.extract();
    }
}

Gondoljuk végig!

• Cseréljük le a while ciklust if-re és növeljük meg a producerek számát mondjuk 30-ra. Mit tapasztalunk a buffer tartalmával kapcsolatban?

• Helyes lenne-e a program, ha notifyAll helyett csak notify-t használnánk? Állítsuk a buffer méretét 1-re, a termelők és fogyasztók számát pedig 10-re és futtassuk a programot notify hívással. Mit tapasztalunk?

Gyakorló feladatok

Feladat

Készíts egy SharedInt nevű osztályt, amely monitorként fog viselkedni. Rendelkezik egy privát adataggal egész számok tárolására illetve a következő metódusokkal:

• setValue(int newValue) - beállítja a value változó értékét, a szálbiztos módosítást metódus szintű kölcsönös kizárással történjen
• decrement() - csökkenti a value változó értékét, a szálbiztos módosítást blokk szintű kölcsönös kizárással, ami a SharedInt objektum zárjával történjen

Készíts egy Modifier nevű osztályt, amely megvalósítja a Runnable interfészt. A szál feladata, hogy véletlenszerűen meghívja a konstruktorában átadott SharedInt objektum két metódusának egyikét.

Teszteld a programot a main metódusban! Hozz létre egy SharedInt objektumot, majd indíts el 20 párhuzamosan futó szálat. A szálak befejeződése után írd ki az objektum értékét.

Feladat

Implementálj egy osztályt egy parkoló reprezentálására, ParkingLot néven, amely 10 kocsit képes befogadni. Készíts el a következő metódusokat:

• enter(): beenged egy kocsit a parkolóba, amennyiben van szabad hely, egyéb esetben a kocsinak várakoznia kell.

• leave(): kiléptet egy kocsit a parkolóból, és értesíti az esetlegesen várakozókat a parkolóhely felszabadulásáról.

A szükséges metódusokat lásd el kölcsönös kizárással a Monitor metódus szintű koncepcióját használva. Csak és kizárólag a szükséges kódrészlet legyen része a kritikus szakasznak.

Készíts egy Car osztályt, amely a Thread osztályból származik. Az osztály a konstruktorában egy ParkingLot objektumot kap. A szál feladata az enter() és a leave() metódusok meghívása ebben a sorrendben.

Teszteld a programot a main metódusban! Hozz létre egy ParkingLot-ot, majd indíts 100 párhuzamosan futó Car szálat. Ne használd a megvalósításhoz a join és a sleep metódusokat.

---

Utolsó frissítés: 2025-03-09 09:46:28