Procesy

Úlohou správy procesov v distribuovaných systémoch je, okrem úloh bežných z jednoprocesorových systémov, spoločne využívať výpočtovú silu systému, rozdeľovať záťaž na jednotlivé procesory, uskutočňovať operácie na vzdialených procesoch, synchronizovať procesy a viesť evidenciu ich stavu.

Vlákna

V mnohých ohľadoch sú vlákna ako mini-procesy. Každé vlákno beží sekvenčne a má svoj zásobník. Vlákna spoločne používajú procesor, tak ako procesy: beží prvé vlákno, potom ďalšie. Iba na multiprocesore bežia paralelne. Na obrázku 1(a) vidíme počítač s troma procesmi. Každý proces má svoj vlastný zásobník, vlastný zoznam registrov a vlastný adresný priestor. Tieto procesy nemajú nič spoločné, môžu byť ale schopné spolu komunikovať pomocou semaforov, monitorov alebo správ. Na obrázku 1(b) vidíme ďalší počítač s jedným procesom. Tento proces ale obsahuje viacero vlákien.

Obrázok 1: (a) Tri procesy každý s jedným vláknom. (b) Jeden proces s troma vláknami.


Rozdielne vlákna v procese ale nie sú tak nezávislé ako rozdielne procesy. Všetky vlákna majú rovnaký adresný priestor, čo znamená, že majú spoločné rovnaké globálne premenné. Keďže každé vlákno môže pristupovať ku každej virtuálnej adrese, jedno vlákno môže čítať, písať, alebo dokonca zmazať zásobník iného vlákna. Ako u tradičných procesov (procesy s jedným vláknom), vlákna môžu byť v týchto štádiách:
  • Bežiace vlákno používa procesor a je aktívne.
  • Blokované vlákno čaká, kým ho ďalšie vlákno odblokuje.
  • Pripravené vlákno je vlákno, ktoré je naplánované pre spustenie.
  • Ukončené vlákno je vlákno, ktoré skončilo svoju činnosť.

Systémové modely umiestnenia procesov

V multiprocesorových a distribuovaných systémoch je metóda umiestnenia procesov na procesory jednou zo základných otázok návrhu celého systému. Existujú dva zásadne odlišné modely umiestnenia procesov:
  • Model pracovných staníc (angl. Workstation model)
  • Procesor pool model

Model pracovných staníc

Model pracovných staníc je založený na myšlienke, že každý užívateľ má svoj počítač, ktorý je mu plne k dispozícii. Okrem užívateľských uzlov bývajú v takýchto systémoch ešte uzly určené pre nejaké servery – napríklad súborový server. Vzhľadom k tomu, že väčšina distribuovaných systémov využíva akýsi súborový server, je otázkou, čo s lokálnymi diskami jednotlivých užívateľských staníc, ak nie sú bezdiskové. Možnosti využitia lokálnych diskov je niekoľko, každá má svoje výhody a nevýhody (tab. 2).

Tabuľka 1: Výhody a nevýhody využitia lokálnych diskov pri modely pracovných staníc.

Výhody Nevýhody
Bezdiskové stanice Lacné, ľahká údržba Vyťaženie siete, záťaž súborových serverov
Stránkovanie, dočasné súbory Znižuje zaťaženie siete Väčšie náklady na disky
Stránkovanie, dočasné súbory, systémové programy Ešte viac znižuje zaťaženie siete Väčšie náklady, údržba systémových programov
Stránkovanie, dočasné súbory, systémové programy, cachovanie súborov Redukcia záťaže súborových systémov Udržovanie súdržnosti cache
Súčasť distribuovaného súborového systému Výrazná redukcia záťaže ostatných súborových serverov Udržovanie súdržnosti celého súborového systému
Kompletný lokálny súborový systém Eliminácia potreby súborových serverov Strata transparentnosti

Procesor pool model

V tomto modely používateľ nemá svoj vlastný počítač. Tento prístup realizovaný väčšinou poľom procesorov, ku ktorým sú lokálnou sieťou pripojené užívateľské terminály. Takto sa rovnomerne rozdelí výpočtová záťaž medzi dostupné procesory, je ale potrebný špeciálny hardvér.

Vzdialené spúšťanie procesov

Aby mohla byť efektívne využitá výpočtová sila celého systému, je občas nutné spustiť nový proces na inom procesore. Na obrázku 2 je algoritmus pre spustenie procesu na voľnom počítači. Domovský počítač je počítač, na ktorom bol proces spustený, ale pre jeho vyťaženie, požiada register o voľný počítač na beh tohto procesu. „Voľný počítač“ je typicky počítač, na ktorom sa nikto nedotkol klávesnice alebo myši niekoľko minút a nebežia žiadne užívateľské procesy.

Obrázok 2: Nájdenie a využitie voľného počítača.


Pridelenie procesorov

V okamihu vzniku procesu je potrebné určiť, na ktorom procesore pobeží. Algoritmy riešiace tento problém sa nazývajú algoritmy pridelenia procesorov. Opíšeme si tieto algoritmy:
  • Deterministický grafový algoritmus.
  • Hierarchický algoritmus.
  • Bidding algoritmus.

Deterministický grafový algoritmus

Deterministický grafový algoritmus minimalizuje vzdialenú komunikáciu. Každá dvojica vzájomne komunikujúcich procesov je ohodnotená veľkosťou vzájomnej komunikácie. Potom celý systém môže byť reprezentovaný grafom s ohodnotenými hranami. Úlohou algoritmu je nájsť také vzájomné priradenie procesov a procesorov, aby komunikácia medzi jednotlivými procesormi bola minimálna. Nevýhoda tohto algoritmu je, že potrebuje poznať vopred pre každú dvojicu procesov ich komunikačnú zložitosť, preto je použiteľný len pre veľmi špeciálne prípady.

Obrázok 3: Dva spôsoby alokácie deviatich procesov na tri procesory.


Na obrázku 3(a) je graf s procesmi A, E a G na prvom procesore, procesy B, F, a H na druhom, a procesy C, D a I na treťom. Celková komunikácia je suma hodnôt nad čiarami, ktoré prechádzajú čiarkovanou čiarou, teda 30. Na obrázku 3(b) je iné rozdelenie, ktoré má len 28 jednotiek komunikácie. To znamená, že toto je lepší spôsob, pretože požaduje menej komunikácie.

Hierarchický algoritmus

Príkladom hierarchického algoritmu je alokačný algoritmus použitý v systéme MICROS. Je založený na logickej hierarchii procesorov nezávisle na fyzickom rozmiestnení jednotlivých počítačov. Procesory na najnižšej úrovni vykonávajú vlastnú prácu, procesory na vyšších úrovniach sú manažéri. V prípade, že manažér dostane požiadavku na pridelenie procesora, zistí, či je niektorý z jemu pridelených procesorov voľný. V prípade, že áno, tak ho alokuje, v prípade že nie, pošle požiadavku vyššiemu manažérovi. Keď nejaký manažér vypadne, musí sa nahradiť niektorým z jeho podriadených. Ktorý z nich to bude určia podriadený sami, alebo ho môže určiť manažér vypadnutého procesora. Pre zabezpečenie väčšej stability, nemusí existovať manažér najvyššej úrovne, ale je niekoľko vysokých manažérov s rovnakými právomocami.

Bidding algoritmus

Bidding algoritmus sa snaží zmeniť počítačový systém na miniatúrnu ekonómiu, s kupujúcimi a predajcami služieb, a cenami nastavenými podľa ponuky a dopytu. Kľúčovými hráčmi tu sú procesy, ktoré musia kupovať čas procesora pre ich beh, a procesory, ktoré sa predávajú najvyššej ponuke. Každý procesor vkladá svoju približnú cenu do verejného súboru. Rôzne procesory môžu mať rôznu hodnotu, to závisí napríklad na ich rýchlosti, veľkosti pamäte atď. Keď proces chce spustiť dcérsky proces, hľadá procesor, ktorý ponúka služby čo potrebuje. Vylúči procesory, ktorých služby si nemôže dovoliť. Zo zvyšku je najlepším kandidátom ten, ktorý je najlacnejší, najrýchlejší, alebo má najlepší pomer cena/výkon. Potom proces vytvorí ponuku a pošle ju najlepšiemu procesoru. Táto ponuka môže byť väčšia alebo menšia ako odporúčaná cena. Procesory zbierajú všetky ponuky, ktoré sú im zaslané, a vyberú si proces s najvyššou ponukou. Víťazi a porazený sú informovaný a víťazný proces je vykonávaný.

1Aké sú systémové modely rozmiestnenia procesov?






2V akých štádiách môže byť vlákno?





3Deterministický grafový algoritmus: