Migrácia procesov

Migrácia procesov je špecializovaná forma riadenia procesov, kde sú procesy presunuté z jedného výpočtového prostredia do druhého. Migrácia procesov sa delí na:
  • Preemtívna migrácia procesov – migrácia procesu, ktorý sa už začal vykonávať. Tento typ migrácie procesu je pomerne drahý, pretože zahŕňa migráciu a obnovenie stavu procesu, aj obnovenie medziprocesových komunikačných kanálov, ku ktorým je migrovaný proces pripojený
  • Nepreemptívna migrácia procesov – migrácia procesu, pred začiatkom jeho vykonávania. Tento typ migrácie je relatívne lacný, pretože sa prenáša relatívne malá záťaž

Mechanizmus migrácie

Mechanizmus migrácie procesu sa skladá z nasledujúcich krokov:
  1. Pozastavenie procesu na zdrojovom uzle a jeho reštartovanie na cieľovom uzle.
  2. Prenesenie adresného priestoru procesu z jeho zdrojového uzla na cieľový uzol.
  3. Preposielanie správ určených migrovanému procesu.
  4. Presmerovanie a obnovenie komunikačných kanálov.


Obrázok 1: Mechanizmus migrácie.


Doručovanie správ

Behom migrácie a krátko po nej, musia byť v správnom poradí doručené všetky správy určené pre migrovaný proces. Je to možné zabezpečiť týmito spôsobmi:
  • Zaslať všetkým potenciálnym odosielateľom správu, že proces je migrovaný. Procesy, ktoré by chceli zasielať správu migrovanému procesu budú suspendované až do ukončenia migrácie a naviazania nových spojení. Problém tohto riešenia je v tom, že odosielatelia nemusia byť zdrojovému jadru známi. Takýchto odosielateľov môže byť veľké množstvo. Táto metóda by bola komunikačne veľmi náročná, a to i v prípade, že behom migrácie s migrovaným procesom nikto nekomunikuje.
  • Nechať v zdrojovom jadre odkaz na cieľový počítač s tým, že všetky správy budú presmerované. To však vytvára reziduálnu závislosť. Reziduálna závislosť vzniká keď proces ktorý migroval, stále k svojej činnosti potrebuje spoluprácu zdrojového počítača.
  • Všetky správy prijaté behom migrácie vracať späť odosielateľovi s poznámkou „adresát je migrovaný“ a s adresou cieľového počítača. Tento spôsob však tiež vytvára reziduálnu závislosť, preto je potrebné, aby adresa migrovaného procesu bola známa len určitý časový interval a po uplynutí tohto intervalu je prípadným odosielateľom správa vrátená s poznámkou „adresát neznámy“. Je potom na odosielateľovi, aby si zistil novú adresu príjemcu.

Výber cieľa migrácie

Na výber cieľa pre migráciu je potrebné zbierať veľké množstvo rôznych dát:
  • Dáta, ktoré sa týkajú samotného procesu a jeho činnosti – využitie procesora, siete.
  • Faktory týkajúce sa hardvérovej konfigurácie.
  • Stav diskových cache.
  • Doba, počas ktorej bola stanica používateľom nepoužívaná.
Tieto informácie je potrebné zbierať, sledovať a vychádzať z nich pri rozhodovaní o migrácii. Návrh funkcie migračného politika, to je tej časti migračného mechanizmu, ktorý toto rozhodovanie robí, musí zohľadniť nasledujúce požiadavky:
  • Výkonnosť – nie je možné sa dlho rozhodovať o voľbe procesu a jeho cieľa pre migráciu.
  • Rozšíriteľnosť – mechanizmus by mal počítať s veľkým počtom staníc, ktoré bude obsluhovať.
  • Odolnosť proti chybám – výpadok jedného komponentu by nemal ohroziť rozhodovanie vo zvyšnej funkčnej časti siete.
  • Spravodlivosť – rozhodovací systém by nemal dovoliť, aby procesy, ktorých zdrojom je jedna stanica, ovládli sieť do tej miery, že by iné stanice nemohli robiť svoju činnosť.

Vyvažovanie záťaže

Vyvažovanie záťaže je rozdelenie úloh medzi procesormi, pre efektívne využitie zdrojov. Vyvažovanie záťaže je dosiahnuté migráciou procesov, ale je nutné merať záťaž jednotlivých uzlov v sieti. Po nameraní záťaže každého uzla, sú uzly označené ako:
  • málo zaťažené - nevyužívané
  • preťažené - obsadené

Algoritmy vyvažovania záťaže

Algoritmy vyvažovania záťaže možno rozdeliť z hľadiska dostupných informácií, ktoré systém pozná v okamihu rozhodovania sa pri vyvažovaní záťaže. Tu je možné algoritmy rozdeliť na:
  • statický algoritmus – snaží sa efektívne rozdeliť nové úlohy pre každý uzol počítačového klastra na základe statických informácií o štruktúre distribuovaného systému. Statické informácie sú také, ktoré systém pozná na začiatku a sú pevne dané. Jedná sa o relatívny výkon každého uzla z hľadiska jeho hardvérovej konfigurácie, topológie systému, rýchlosti prenosových zberníc.
  • dynamický algoritmus – využíva aktuálne informácie získané o systéme dynamicky. Informácie sú získané monitorovaním systému a sú pri každom takom ďalšom meraní aj priebežne aktualizované. Takýto systém sa potom vie oveľa lepšie a pružnejšie prispôsobiť každým zmenám v záťaži a je zrejmé, že je efektívnejší, ako statický. Nevýhodou oproti statickému systému je, že tu vzniká časové omeškanie, ktoré vzniká monitorovaním systému.

Algoritmy pre výber cieľového uzla pri migrácii

  • Párový algoritmus

    Hlavná myšlienka je v dynamickom vytváraní párov, ktoré sa navzájom vyvažujú:
    1. Počítač A pošle nejakému počítaču B žiadosť o vytvorenie páru. Žiadosť obsahuje výpis bežiacich procesov a ich základné charakteristiky.
    2. B po prijatí správy:
      • Odmietne žiadosť - A musí skúšať inde.
      • Vytvorí s A pár – pokiaľ nebude tento pár zrušený, A aj B odmietajú ďalšie žiadosti.
      • Oznámi počítaču A, že práve migruje – A čaká, až sa B rozhodne.
    3. Po vytvorení páru zaťaženejší procesor vyberie proces na migráciu, podľa miery vylepšenia: ki=T_Ai/ (T_Bi+ T_ABi )
      • T_Ai je očakávaný čas odpovedi procesu i na počítači A,
      • T_Bi je očakávaný čas odpovedi procesu i na počítači B,
      • T_ABi je čas prenosu z A na B.
    4. V prípade, že sa migráciou nedosiahne zlepšenie, pár je zrušený. Inak je vybraný proces prenesený a pokračuje sa od bodu 3.
  • Vektorový algoritmus

    Každý počítač má pevný vektor záťaže ostatných počítačov, každý počítač sám periodicky meria vlastnú záťaž. Pri požiadavke na migráciu sa k záťaži jednotlivých procesorov pripočíta komunikačná réžia a vyberie sa najvýhodnejší procesor.
  • Centralizovaný algoritmus

    Jeden centrálny server pozná záťaž všetkých uzlov, tento potom rozhoduje čo a kam migrovať.
  • Lokálny algoritmus

    Každý uzol zisťuje len svoju vlastnú záťaž. Ak záťaž prekročí prahovú hodnotu, náhodne sa vyberie n uzlov, ktorým sa zašle žiadosť o migráciu. Prvá alebo najlepšia odpoveď sa akceptuje.


1Aké požiadavky treba zohľadniť pri výbere cieľa migrácie?









2Aké sú algoritmy pre výber cieľového uzla pri migrácii?