Obsah

35 - Plánování a synchronizace procesů, transakce

Export page to Open Document format Plánování procesů je jeden z úkolů operačního systému. Týká se systémů s více současně běžícími procesy, které podporují multitasking (schopnost provádět více úloh současně). Plánování řeší výběr procesů, kterým má být aktuálně přidělen procesor a pamět. V oblastech operačních systémů se setkáváme s oblastí správy procesů (process managmentú, který zahrnuje:

Proces

Proces je běžící program, který je v OS definován:

Běžně se rozlišují následující stavy procesů (schéma pro UNIX)

V OS bývá proces reprezentován strukturou PCB (Process control block), která zahrnuje:

Plánovač

Plánovač je software, který přiděluje procesorový čas procesům:

Využívají se různé plánovací algoritmy, např.:

Při plánování avšak může dojít k některým z následujícíh problémů.

Problém vyhladovění

Proces, který je připraven k běhu, se k procesoru nedostane, protože ten je neustále přilován jiným, více priotivním procesům. (Tento proces tedy hladoví a neustále čeká na přidělení procesoru). Nabízí se následující řešení:

Inverze priorit

V operačních systémech UNIXového typu probíhá víceúrovňové prioritní plánování a dynamická změna priorit. Toho se využívá například pokud proces v poslední době spotřeboval hodně CPU (např. čekání na V/V), proto se jeho priorita dynamicky sníží (nebo naopak zvýší). Toto má za důsledek rychlejší reakce interaktivních procesů, které většinou čekají na vstup, a proto mají malou spotřebu času CPU. Inverze priorit nastane pokud si nízko prioritní proces naalokuje nějaký zdroj, více prioritní procesy ho blokují a on nemůže dokončit práci se zadaným zdrojem. Časem tento zdroj potřebují i více prioritní procesy a nutně jsou zablokovány a musí čekat na tento nízko prioritní proces. Pokud tento zdroj nepotřebují nějaké další procesy, mohou běžet, i když mají nízkou prioritu. Řešením proto bývá priority ceiling, priority inheritance a další.

Další problémy

Další výrazné komplikace plánování představují

Synchronizace procesů

Současný přístup několika paralerních procesů ke sdíleným zdrojů může vést k nekonzistencím zpracovaných dat. Vznikají různé chyby, například race condition (časově závislá chyba), tj. chyba vznikající při přístupu ke sdíleným zdrojům kvůli různému pořadí provádění jednotlivých paralelních výpočtů v systému (kvůli jejich různé relativní rychlosti). Příkladem je například probnlém producent - konzument. Proto jsou vyžadovány mechanismy zajišťující správné pořadí provádění procesů, které se označují jako mechanismy synchronizace procesů.

Kritická sekce

Každý proces, který soutěží o přístup ke sdíleným zdrojů, je řízen určitým programem. Sdílené kritické sekce daných procesů rozumíme ty úseky jejich řídících programů, jejichž prováděním jedním procesem vylučuje současné provádění libovolného z těchto úseků ostatními procesy. Obecným případem je situace, kdy sdílené sekce nejsou vzájmenně zcela vyloučeny, ale může se jich současně provádět nejvýše určitý počet. Problém KS je nutnost zajistit:

Zvláštním případem stárnuí je livelock, kdy všechny procesy z určité množiny běží, ale provadějí jen omezený úsek kódu, které by mohly opustit jen tehdy, kdyby získaly zdroj vlastněný některým z procesů dané skupiny.

Petersonův algoritmus

Možné řešení problému KS pro 2 procesy (existuje i jeho zobecnění pro n procesů). 

bool flag[2] = {false, false};
int turn = 0;
 
// process i (i==0 or i==1)
do {
  //...
 
  flag[i] = true;
  turn = 1-i;
 
  while (flag[1-i] && turn != i); // proces je zaneprazdnen, ceka
  // KRITICKA SEKCE
  flag[i] = false;
  // konec KS  
} while (1);
Bakery algoritmus L. Lamporta

Vzájemné vyloušení pro n procesů: 

bool flag[N] = { false }; // sdilene pole
int ticket[N] = { 0 };    // sdilene pole
int j, max = 0;           // lokalni (nesdilene) promenne
 
// proces i
while(1) {
  // ... pred KS
  flag[i] = true; // najdu max ticket
  for(j = 0; j < N; j++) {
    if(ticket[j] > max) {
      max = ticket[j];
    }
  }
  ticket[i] = max+1; // pridelim novy listek
 
  flag[i] = false;
  // prideleni priority procesu s nejmensim cislem listku (pripadne s nejmensim PID)
  for (j = 0; j < N; j++) {
    while (flag[j]);
    if (tickek[j] > 0 &&
        (ticket[j] < ticket[i] ||
        (ticket[j] == ticket[i] && j<i))) {
          while(ticket[j] > 0);
        }
  }
  // KS
  ticket[i] = 0;
  // konec KS
}
Využití hardware pro synchornizaci

Používá se častěji než specializované algortimy bez podpory HW.

Příkladem je atomická instrukce typu TestAndSet 

boot TestAndSet (bool &target) {
  bool rv = target;
  target = true;
  return rv;
}
 
// vyuziti TestAndSet pro synchronizaci na KS:
 
bool lock = false;
 
// ...
while(TestAndSet(lock));
// KS
lock = false;
// ...

Dalším příklade je atomická instrukce typu Swap 

void Swap(bool &a, bool &b) {
  bool temp = a;
  a = b;
  b = temp;
}
 
// vyuziti Swap pro synchronizaci na KS
 
bool lock = false;
 
// ...
bool key = true;
while (key == true)
  Swap(lock, key);
// KS
lock = false;
// ...

Uvedená řešení vzájemného vyloučení založená na sepcializovaných instrukcích zahrnují možnost aktivního čekání, proto se také tato řešení často označují za spinlock. Lže je užít na krátných, neblokujících KS bez preemce (aspoň bez preempce na použitém procesoru). Opakovaný zápis paměťového místa je problematický z hlediska zajištění konzistence cache v multiprocesorových systémech (zatěžuje datovou sběrnici) - řešením je aktivním čekáním pouze číst. Uvedená řešení nevyločují možnost stárnutí: to bývá tolerováno, ale existují řešení s frontou čekajících procesů, které tento problém odstraňují.

Semafory

Jedná se o synchronizační nástroj nevyžadující aktivní čekání. Typicky jde o celočíselnou proměnnou přístupnou dvěmi základními atomickými operacemi:

Sémantika celočíselné proměnné S odpovídající semaforu

Využití semaforů pro synchonizaci KS: 

semaphore mutex; // sdileny semafor
 
init (mutex,1);
// ...
lock (mutex);
// KS
unlock (mutex);
// ...

Konceptuální implementace semaforu: 

typedef struct {
  int value;
  process_queue *queue;
} semaphore;
 
 
lock(S) {
  S.value--;
  if (S.value < 0) {
    // prida proces volanim lock(S) do S.queue
    append(S.queue, current_process);
    // prepne kontext a zavola proces
    switch();
  }
}
 
unlock (S) {
  S.value++;
  if (S.value <= 0) {
    // vezme a odebere prvni proces z fronty cekajicich
    P = get(S.queue);
    // proces vlozi do aktualni fronty pripravenych procesu
    append(ready_queue, P);
  }
}

Provádění lock a unlock musí být atomické (jejich tělo totiž také představuje KS!)! Atomicita se řeší:

Používají se také read-write zámky (pro čtení lze zamknout vícenásobně) či. např. reentrantní zámky (proces může stejný zámek zamknout opakovaně) Semafory jsou podle POSIXu dostupné prostřednictvím volání:

Monitory

Monitory jsou jeden z vysokoúrovňových synchronizačních prostředků. Zapouzdřuje data, má definované operace, jen jeden proces může provádět nějakou operaci nad chráněnými daty: 

monitor monitor-name {
  shared variable declarations
 
  procedure body P1 (...) {
    ...
  }
  procedure body P2 (...) {
    ...
  }
  {
    initialization code
  }
}

Pro možnost čekání uvnitř monitoru jsou k dispozici tzv. podmínky (conditions), nad kterými je možné provádět operace:

Klasické synchornizační problémy

Producent a konzument

Komunikace přes vyrovnávací paměť s kapacitou omezenou na N položek. Synchronizační prostředky jsou: 

sempahore full, empty, mutex;
 
// initialization
init(full,0);
init(empty,N);
init(mutex,1);

Producent x Konzument 

do {                                       do {
  ...                                        lock(full);
  // produce an item I                       lock (mutex);
  ...                                        ...
  lock(empty);                               // remove I from buffer
  lock(mutex);                               ...
  ...                                        unlock(mutex); 
  // add I to buffer                         unlock(empty);
  ...                                        ...
  unlock(mutex);                             // consume I
  unclock(full);                             ...
} while(1);                                } while(1);
Čtenáři a písaři

Libovolný počet čtenářů může čict, ale pokud někdo píše, tak nikdo další nesmí psát ani číst. Synchronizační prostředky: 

int readcount;
semaphore mutex, wrt;
 
// Initialization
readcount = 0;
init(mutex,1);
init(wrt,1);

Algoritmus: Písař x Čtenář 

do {
  lock(mutex);
  readcount++;
  if (readcount == 1) {
     lock(wrt);
  }
  do {
    unlock(mutex);
    ...                               ...
    lock(wrt);                        // reading is performed
    ...                               ...
    // writing is performed
    lock(mutex);
    ...
    readcount--;
    unlock(wrt);
    if (readcount == 0)
      ...
      unlock(wrt);
  } while(1);
  unlock (mutex);
  ...
} while(1);

!!! do algoritmu doplnit problém vyhladovění

Problém večeřících filozofů

Algoritmus s možností uváznutí: 

semaphore chopstick[5];
 
// initialization:
for (int i = 0; i < 5; i++)
  init(chopstick[i],1);
 
// philospher i:
do {
  lock(chopstick[i]);
  lock(chopstick[(i+1) % 5]);
  ...
  /// eat
  ...
  unlock(chopstick[i]);
  unlock(chopstick[(i+1) % 5]);
  ...
  // think
  ...
} while (1);

Modelování synchronizačních problémů

K popisu a analýze synchronizačních problémů je možné použít např. Petriho sítě (a řadu dalších formalismů). Petriho síť (P/T) má charakter bipartního grafu: dva typy uzlů (místa a přechody), hrany propojují různé typy uzlů (nelze propojit místo s místem):

Uváznutí (deadlock)

Situace, kdy ve skupině procesů každý čeká na uvolnění prostředků s výlučným přístupem přiděleného některému procesu z dané množiny (vzniká cyklická závislost na sebe čekajících procesů) a ani jeden proces z této množiny proto nemůže pokračovat

Nutné podmínky uváznutí

  1. vzájemné vyloučení při používání prostředků
  2. vlastnictví alespoň jednoho zdroje a čekání na další
  3. prostředky vrací proces, který je vlastní, a to po dokončení jejich využití
  4. cyklická závislost na sebe čekajících procesů

Řešení:

Stárnutí/hladovění procesů (starvation)

Proces čeká na podmínku u níž není zaručeno, že nastane (např. protože příslušné procesy mohou bát neustále přebírány jinými procesy)

Zdroje

IOS - Přednáška č. 5: Správa procesů

IOS - Přednáška č. 6: Synchronizace procesů

http://www.wikipedia.org http://www.google.com

35
Celé jménoOK!!!
Tom Ofeig2011-03-25 18:50:03 
Jirka Hynek2011-03-25 18:57:27 
roman jasho2011-03-31 00:30:16 
 3