Kilpailutilanne

Mureakuha

Kilpailutilanne on rinnakkain suoritettavissa ohjelmistoissa esiintyvä tilanne, joka saattaa aiheuttaa ohjelmiston lukkiintumisen tai tietorakenteiden eheyden rikkoontumisen.

Esimerkki kilpailutilanteesta:

Asiakkaat := 2;

task T1 (sisääntulevien asiakkaiden laskuri):
   Asiakkaat := Asiakkaat + 1;

task T2 (uloslähtevien asiakkaiden laskuri):
   Asiakkaat := Asiakkaat - 1;

Esimerkissä eri tehtävät laskevat sisääntulevien ja uloslähtevien asiakkaiden määrää. Kilpailutilanne syntyy esimerkiksi näin (asiakkaita alussa 2):

1. Asiakas kävelee sisään, jolloin tehtävä T1 aktivoituu.
2. T1 laskee Asiakkaat + 1 (2 + 1 = 3)
3. Toinen asiakas kävelee ulos, jolloin tehtävä T2 aktivoituu, ja tehtävän T1 suoritus keskeytyy.
4. T2 laskee Asiakkaat - 1 (2 - 1 = 1).
5. T2 suorittaa sijoituksen Asiakkaat := 1.
6. T2 suoritus päättyy, jää odottamaan seuraavan asiakkaan poistumista.
7. T1 suoritus jatkuu, jolloin suoritetaan sijoitus Asiakkaat := 3 (kohdassa 2 laskettu arvo).
8. T1 suoritus päättyy, jää odottamaan seuraavan asiakkaan sisääntuloa.

Alkutilanteessa kaupassa oli kaksi henkilöä, sisään tuli yksi ja ulos lähti yksi, joten kaupassa on edelleen kaksi henkilöä. Asiakkaat-muuttujan arvo on kuitenkin 3 eikä 2.

Kilpailutilanteet voidaan välttää kolmea perussääntöä noudattaen:

1. tehtävän muuttaessa tietorakenteen tietoja, muut tehtävät eivät saa aloittaa saman tietorakenteen muuttamista
2. tehtävän muuttaessa tietorakenteen tietoja, muut tehtävät eivät saa aloittaa saman tietorakenteen tietojen lukemista
3. tehtävän lukiessa tietorakenteen tietoja, muut tehtävät eivät saa aloittaa saman tietorakenteen tietojen muuttamista.

Näiden sääntöjen toteutumisen varmistamiseksi voidaan käyttää keskinäistä poissulkemista (mutual exclusion).

Kilpailutilanteiden umpikuja

Kun useat oliot käyttävät aikaisemmin esiteltyä tietokantaa, syntyy edellä mainittu ongelma. Pelisääntöjen kehityttyä liikennejärjestys täsmentyy, mutta uusi uhka vaanii nurkan takana. Kuvitellaan, että ollaan tekemässä liikenneohjelmaa, jossa on tasa-arvoinen risteys, johon saapuu neljästä ilmansuunnasta auto-oliot, jotka kaikki haluavat ajaa suoraan. Tällöin idästä tuleva väistää pohjoisesta tulevaa ja pohjoisesta tuleva lännestä tulevaa jne. Tälläisetkin tilanteet tulee ottaa huomioon.

Linkkejä

• Wikipedian artikkeli kilpailutilanteesta