Lygiagretusis programavimas

Lygiagretusis programavimas – kompiuterių mokslo (informatikos) sritis, tirianti algoritmų lygiagretinimą. Lygiagretinimas – skirtingų operacijų vykdymo paskirstymas keliems procesoriams ar kompiuteriams. Pastarasis atvejis vadinamas paskirstytuoju skaičiavimu.

Šiame straipsnyje naudojami diskutuotini terminai. Daugiau apie kompiuterinius terminus skaitykite žodynėlyje.

Šiam straipsniui ar jo daliai trūksta išnašų į patikimus šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais.

Lygiagrečiojo programavimo taikymas prasmingas tik tada, jei darbai gali būti padalinami ir vykdomi vienu metu, jei darbai priklauso vienas nuo kito (turi būti vykdomi iš eilės), lygiagretusis programavimas nėra efektyvus.

Lygiagrečiojo programavimo pagrindinės problemos

sinchronizacija – užtikrinimas, kad darbai netrukdytų vienas kitam;

apsikeitimas informacija tarp lygiagrečių procesų.

Kritinės sekcijos

Informacijos apsikeitimui naudojamos kritinės sekcijos – apsaugotos kodo atkarpos, į kurias vienu metu gali patekti tik vienas vykdytojas (gija arba procesas). Kiti procesai, norintys atlikti šiuos veiksmus, yra pristabdomi. Baigus darbą kritinėje sekcijoje, vienas iš pristabdytų procesų yra pažadinamas ir tęsia darbą kritinėje sekcijoje. Šioje vietoje veiksmus gali atlikti tik vienas procesas vienu metu, o kiti procesai laukia ir tokiu būdu lėtina programos veikimą.

Neatsargiai naudojamos kritinės sekcijos gali sulėtinti sistemos darbą. Pagreitinti programą galima atsisakius perteklinių kritinių sekcijų, jas supaprastinus iki minimumo, kad joje procesas užtruktų tik tiek, kiek reikia informacijos apsikeitimui ir apsaugojimui.

Kritinių sekcijų apsaugai yra sukurta daug priemonių. Bene pirmoji sukurta – semaforas.

Kritinių sekcijų pavyzdžiai

Pateikiami keli pavyzdžiai Java kalba. Pirmame pavyzdyje kritinės sekcijos apsauga nenaudojama (rezultatas – nenuspėjamas):

package testas;
class BendriDuomenys {
	public static int skaicius = 0;
	public static void keisti() {
		skaicius++;
		skaicius--;
	}
	public static boolean arNulis() {
		return skaicius == 0;
	}
}
class Gija1 extends Thread {
	private long pradzia;
	public void run() {
		pradzia = System.currentTimeMillis();
		while (System.currentTimeMillis() – pradzia < 1000) {
			BendriDuomenys.keisti();
		}		
	}
}

class Gija2 extends Thread {
	private long pradzia;
	public void run() {
		pradzia = System.currentTimeMillis();
		while (System.currentTimeMillis() – pradzia < 1000) {
			if (!BendriDuomenys.arNulis()) {
				System.out.println(„Ne nulis“);
			}
		}		
	}	
}

public class Testas {
	public static void main(String[] args) {
		Gija1 gija1 = new Gija1();
		Gija2 gija2 = new Gija2();
		gija1.start();
		gija2.start();
	}
}

Šiek tiek pakoregavus, gaunamas kodas, kuriame naudojama kritinės sekcijos apsauga:

...
public synchronized static void keisti()
...
public synchronized static boolean arNulis()
...

Šiuo atveju monitorius apsaugo duomenis, kad jie nebūtų keičiami kelių gijų vienu metu, taigi rezultatai tampa nuspėjami. Nesunkiai galime apskaičiuoti, kiek kartų kiekvieną kartą bus kviečiami metodai (naudojant monitorių ir nenaudojant). Tačiau, kaip minėta, kritinių sekcijų apsauga yra labai brangi laiko atžvilgiu. Įprastame asmeniniame kompiuteryje su Windows XP operacine sistema ir Sun kompanijos JRE 1.5 antrasis pavyzdys su monitoriais veikė 3 kartus lėčiau nei pirmasis be monitorių, tačiau priklausomai nuo JVM (Java kalbos Virtualios Mašinos) realizacijos ir operacinės sistemos teikiamų galimybių rezultatai gali skirtis.

Užraktas

Pagrindinis straipsnis – Užraktas (programavimas)

Minėtuose pavyzdžiuose kritinės sekcijos yra apsaugotos sinchronizavimo raktažodžiu. Toks apsaugos būdas labai paprastas, tačiau jis gali netikti jei reikia saugoti ne kodo sekciją nuo vykdymo, o duomenų struktūrą nuo lygiagretaus manipuliavimo įvairiomis kodo sekcijomis. Tuomet vartojamas užraktas, kuris paprastai būna susietas su tokia saugoma duomenų struktūra. Užraktai prireikus leidžia suteikti skaitymo leidimus, kurie vienu metu gali būti išduodami ir daugeliui gijų) ir rašymo leidimą (kuris vienu metu gali būti suteiktas tik vienai gijai ir tik tada, jei nėra išduotų skaitymo leidimų).

Semaforas

Pagrindinis straipsnis – Semaforas (programavimas)

Semaforai naudojami, kuomet pageidaujama, jog su tam tikra duomenų struktūra ar kompiuterio įrenginiu nedirbtų daugiau nei nurodytas ribotas skaičius lygiagrečių gijų.

Semaforas yra struktūra, turinti ją sukuriant nustatytą leidimų skaičių dirbti su saugoma duomenų struktūra ar vykdyti saugomą kodo sekciją. Kiekviena gija, prieš pradėdama darbą su saugoma sekcija, turi gauti iš semaforo leidimą (kviesdama semaforo metodą), o baigusi darbą su saugomu objektu – leidimą grąžinti. Jei semafore daugiau šiuo metu leidimų nebėra (jo likusių leidimų skaitiklis lygus nuliui), leidimo prašanti gija blokuojama, kol kokia nors kita gija anksčiau pasiimtą leidimą grąžins.

Jei semaforas turi tik vieną leidimą, jo darbas daug nesiskiria nuo užrakto. Tačiau, skirtingai nuo užraktų, semaforai paprastai leidžia grąžinti leidimą ir ne tai gijai, kuri jį pasiėmė. Kai kuriuose algoritmuose tai gali būti reikalinga, nors šiai galimybei reikalingi sinchronizavimo veiksmai gali sąlygoti lėtesnį darbą nei naudojant užraktus.

Lakūs kintamieji

Pagrindinis straipsnis – Lakus kintamasis

Kai kuriose sistemose yra efektyviau visus kiekvienos gijos naudojamus duomenis saugoti atskiroje, su ta gija susietoje atminties dalyje. Jei tie patys duomenys skaitomi bei keičiami ir iš kitos gijos, visų kopijų reikšmės automatiškai sulyginamos.

Jei algoritmas reikalauja, jog kintamojo reikšmė skirtingose gijose niekada net ir trumpam netaptų skirtinga, toks kintamasis vadinamas lakiu (angl. volatile). Lakūs kintamieji deklaruojami specialiu raktažodžiu (java tas raktažodis yra „volatile“).

Nuorodos

• Konkurentinė modifikacija
• Lygiagretaus programavimo mitai