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

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:

• plánovač (scheduler), který přiděluje CPU procesům
• správu paměti (memory management), přidělující pamět
• podporu meziprocesorové komunikace (IPC) - signály, roury, sockety …

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

• identifikátorem (PID)
• stavem jeho plánování
• programem, kterým je řízen
• obsahem registrů
• daty a zásobníkem

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:

• identifikátor procesu
• stav plánování procesu
• obsah registrů
• plánovací informace
• informace spojené se správou paměti
• informace spojené s účtováním (spotřeba procesoru …)
• využití V/V zdrojů

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

• preemtivní - při přerušení (např. od časovače)
• nepreemtivní - přepnutí jen při volání jádra

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

• FCFS (First-come, first-served = První přijde, první obsloužen)
  • rozhoduje se pouze podle pořadí žádostí o procesor
• round-robin
  • preemptivní varianta FCFS
  • algoritmus přidělí procesu kvantum času (to je přiděleno na začátku algoritmu), po který zablokuje procesor pro proces; po uplynutí doby se procesor uvolní a předá dalšímu procesu
• víceúrovňové prioritní plánování

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

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í:

• Procesy dle priorit dostanou určitý násobek kvanta, stejně prioritní procesy se střídají do jeho vyčerpání, pak dostanou šanci níže prioritní procesy.
• Explicitní kontrola, zda někdo nehladoví.

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ší výrazné komplikace plánování představují

• více procesorové systémy, které vyžadují vyvažování výkonu
• hard real-time systémy, kde je nutné zajistit garantovanou odezvu některých akcí

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ů.

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:

• vzájemné vyloučení : nanejvýš jeden proces je v daném okamžiku v KS
• dostupnost KS
• je-li KS volná, proces nemůže neomezeně čekat na přístup do ní
• je zapotřebí se vyhnout
  • uváznutí (deadlock) - situace, kdy každý ze skupiny procesů čeká na uvolnění zdrojje s výlučným (omezeným) přístupem vlastněným nějakým procesem z dané skupiny

• bloknutí (blocking) - situace, kdy proces, jenž žádá o vstup do KS, musí čekat, přestože KS je volná (tj. žádný proces se v ní nenachází) a ani o žádnou z dané množiny sdílených KS žádný další proces nežádá
• stárnutí (hladovění, starvarion) - situace, kdy proces čeká na podmínku, která nemusí nastat

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.

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);

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

• před vstupem do KS proces získá lístek, jehož číselná hodnota je větší než čísla přidělená již čekajícím procesům (jako lístky na poště)
• držitel nejmenšího čísla s nejmenším PID může vstoupit do KS (protože více procesů může získat jeden lístek současně)
• čísla přidělovaná procesům mohou teoreticky neomezeně růst

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
}

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í.

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:

• lock (P nebo také down)
• unlock (V nebo up)

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

• S > 0 : odemknuto (hodnota S > 1 se používá u zobecněných semaforů, jež mohou propustit do KS více než jeden proces)
• S ⇐ 0 : zamknuto (jeli S < 0, pak hodnota |S| udává počet procesů čekajících na 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ší:

• zákazem přerušení
• vzájemným vyloučením s využitím atomických instrukcí a aktivním čekáním (spinlock)
  • používá se u miltiprocesorových systémů
  • vložení tohoto mechanismu vyžaduje změnu if kódu lock na while: proces uvolněný z fronty soutěží s dalšími procesy, které mohou nově zavolat lock

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í:

• u starších rozhraní: semhet, semop, semctl
• novější: sem_opne, sem_init, sem_post, sem_wait, sem_getvalue, sem_close, sem_unlink, sem_destroy
• POSIXová vlákna: pthread_mutex_lock, pthread_mutex_unlock

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:

• wait()
• signal(), příp. notify()

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);

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í

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);

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):

• Místa : reprezentují možné stavy procesů a proměnných
• Přechody : reprezentují možné akce
• Značení sítě (tečky v místech) : stavy procesů a proměnných
• Provedení přechodu (přesuv značek ze všech vstupních do všech výstupních míst) : reprezentuje provedení nějaké akce

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í:

• prevence uváznutí
  • zrušíme platnost některého z nutných podmínek uváznutí
    1. nepoužívat sdílené prostředky nebo používat sdílené prostředky, které umnožňují sdílený přístup a u kterých tedy není nutné vzájmené vyloučení procesů
    2. proces může žádat o prostředky pouze pokud žádné nevlastní
    3. pokud proces požádá o prostředky, které nemůže momentálně získat, je pozastaven, všechny prostředky jsou mu odebrány a čeká se, až mu mohou být všechny potřebné prostředky přiděleny
    4. prostředky jsou očíslovány a je možné je získávat pouze od nejnižších čísel k vyšším
• vyhýbání se uváznutí
  • procesy předem deklarují určité informace o způsobu, jakým budou využívat zdroje: v nejjednodušším případě se jedná o maximální počet současně požadovaných zdrojů jednotlivých typů
  • předem známé informace o možnách požadavcích jednotlivých procesů a o aktuálním stavu přidělování se využívají k rozhodování o tom, které požadavky mohou být uspokojeny (a které musí počkat) tak, aby nevznikla cyklická závislo na sebe čekajících procesů
• detekce a zotavení
  • uváznutí může vzniknout; periodicky se přitom detekuje, zda k tomu nedošlo, a pokud ano, provede se zotavení
  • detekce uváznutí: graf čekání pro sytémy s jednou instancí každého zdroje (který proces čeká na uvolnění zdroje kterým procesem: cyklus implikuje deadlock)
  • zotavení z uváznutí
    • ukončení všech nebo některých zablokovaných procesů
    • odebrání zdrojů některým procesům, jejich pozastavení a později umožnění pokračovat (případně jejich restart)
• ověření, že uváznutí nemůže nastat

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)