Monitor (sincronizare)

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În domeniul programării, un monitor este o metodă de sincronizare a două sau mai multe sarcini ce folosesc o resursă comună, de obicei un dispozitiv hardware sau o mulțime de variabile. În concurența pentru monitor compilatorul sau interpretorul introduce cod, în mod „transparent” (automat și neexplicit), pentru blocarea sau deblocarea unor proceduri specificate, fără a fi nevoie ca programatorul să acceseze explicit elementele de sincronizare.

A fost inventat de Per Brinch Hansen, implementat pentru prima dată în limbajul Concurrent Pascal și folosit pentru a structura comunicarea între procese in sistemul de operare Solo.

Excludere mutuală[modificare | modificare sursă]

Un monitor este compus din:

  • un set de proceduri ce permite interacțiunea cu o resursă comună
  • un mecanism sau „lacăt” de excludere mutuală (reciprocă)
  • variabilele asociate resursei comune
  • un invariant al monitorului ce definește condițiile necesare evitării unui conflict de acces.

O procedură a monitorului ori obține mai întâi lacătul și-l ține până când procedura se termină, ori așteaptă după un conflict de acces. Dacă fiecare procedură asigură că invariantul este adevărat înainte de eliberarea lacătului, atunci nicio sarcină nu va găsi resursa comună într-o stare ce ar putea duce la un conflict de acces.

Un exemplu este un monitor ce efectueaza o tranzacție asupra unui cont bancar.

monitor cont {
  int balanță := 0
  
  function retrage(int sumă) {
    if sumă < 0 then error "Suma nu poate fi negativă"
    else if balanță < sumă then error "Fonduri insuficiente"
    else balanță := balanță - sumă
  }
  
  function deposit(int sumă) {
    if sumă < 0 then error "Suma nu poate fi negativă"
    else balanță := balanță + sumă
  }
}

Invariantul în acest caz spune că 'balanță' trebuie să reflecte toate operațiile efectuate înainte ca să înceapă o altă operație. Acest lucru nu este specificat în cod, dar poate fi menționat prin comentarii. Există însă limbaje care pot verifica invarianții. Lacătul este adăugat de compilator. Asta face monitorul mai sigur decât abordările unde este necesar ca programatorul să introducă operații de încuiere si descuiere, deoarece programatorul poate greși sau uita acest lucru.

Variabile condiționale[modificare | modificare sursă]

Ca să nu se intre într-o stare de "așteptare ocupată", procesele trebuie sa poată să se semnaleze în legătură cu evenimente notabile. Monitoarele pun la dispoziție această capabilitate prin intermediul variabilelor condiționale. Când o funcție a monitorului are nevoie ca o anumita condiție să fie adevărată înainte de a continua, atunci se asteaptă după o variabilă condițională asociată. Așteptând, el eliberează încuietoarea și este eliminat din mulțimea proceselor care rulează. Orice alt proces care evaluează conditia la adevărat, poate folosi variabila condițională pentru a semnaliza un proces care așteaptă. Astfel, un proces semnalizat obținei iarăși încuietoarea și poate continua.

Următorul monitor foloseste variabile de condiție pentru a implementa o comunicare între procese ce pot reține doar o valoare întreagă la un anumit moment.

monitor canal {
  int continut
  boolean plin := false
  condition snd
  condition rcv

  function trimite(int mesaj) {
    if plin then wait(rcv)   [Sematici Hoare: Vezi explicația mai jos]
    contents := mesaj
    plin := true
    notify(snd)
  }

  function primieste() {
    var int primit

    if not plin then wait(snd)   [Semantici Hoare: Vezi explicația mai jos]
    primit := continut
    plin := false
    notify(rcv)
    return primit
  }
}


Semantici Hoare si Mesa[modificare | modificare sursă]

Din moment ce așteptarea după o variabilă condițională duce la pierderea încuietorii, cel care așteaptă trebuie să se asigure ca invariantul monitorului este satisfăcut înainte ca să aștepte. În exemplul de mai sus, același lucru e valabil pentru notificare.

În primele implementări (cunoscute sub numele de semantici Hoare), notificarea unei variabile condiționale făcea ca procesul care aștepta să primească încuietoarea si să ruleze imediat, garantând astfel contiția. Implementarea acestui comportament este complicată și are un cost mare. Este deasemenea incompatibil cu schedulere ce pot întrerupe un proces în mod arbitrat. Din aceste motive, cercetătorii au luat în considerare alte semantici pentru variabilele condiționale.

In most modern implementations (known as Mesa semantics), notifying does not take control away from the running process, but merely makes some waiting process runnable. The notifying process continues to hold the lock until it leaves the monitor function. The side effects of this approach are that the notifying process does not have to set up the monitor invariant before notifying, and the waiting process must double-check the condition it was waiting for. Specifically, if a monitor function includes the expression if test then wait(cv), another process could enter the monitor after the notification and make the condition untrue again before the waiting process runs. The expression must be rewritten as while test do wait(cv) so that the condition is re-checked before the process continues.

Implementations also provide a "notifyAll" or "broadcast" operation that notifies every process waiting on a given condition. This operation is useful, for example, when several processes are waiting for different amounts of storage to become available. Releasing storage can enable any number of these processes to proceed, but the scheduler does not know which ones.

A sample implementation for a condition variable is as follows:

conditionVariable {
  int queueSize = 0;
  semaphore lock;
  semaphore waiting;
  
  wait() {
     lock.acquire();
     queueSize++;
     lock.release();
     waiting.down();
  }
  
  signal() {
     lock.acquire();
     if (queueSize > 0){
        queueSize--;
        waiting.up();
     }
     lock.release();
  }
}

History[modificare | modificare sursă]

Per Brinch Hansen was the first to describe and implement monitors, basing them on ideas from C. A. R. Hoare. Hoare subsequently developed the theoretical framework and demonstrated their equivalence to semaphores (when using the original semantics).

Programming languages that have supported monitors include

Vezi și[modificare | modificare sursă]

Bibliografie[modificare | modificare sursă]

  • Monitors: an operating system structuring concept, C. A. R. Hoare - Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [1]
  • Monitor classification P.A. Buhr, M. Fortier, M.H. Coffin - ACM Computing Surveys (CSUR), 1995 [2]

Legături externe[modificare | modificare sursă]