Monitor (sincronizare)

Î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ă

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

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

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 de asemenea 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.

În majoritatea implementărilor moderne (cunoscute sub numele de semantică Mesa), notificarea nu ia controlul asupra procesului de rulare, ci doar face executabil un proces de așteptare. Procesul de notificare continuă să țină blocarea până când iese din funcția de monitor. Efectele secundare ale acestei abordări sunt că procesul de notificare nu trebuie să configureze monitorul invariant înainte de a notifica, iar procesul de așteptare trebuie să verifice din nou starea pe care o aștepta. Mai exact, dacă o funcție de monitor include expresia if test then wait(cv), un alt proces ar putea intra în monitor după notificare și poate face din nou condiția neadevărată înainte ca procesul de așteptare să ruleze. Expresia trebuie rescrisă ca while test do wait(cv) , astfel încât condiția să fie din nou verificată înainte ca procesul să continue.

Implementările oferă, de asemenea, o operațiune „notifyAll” sau „broadcast” care notifică fiecare proces care așteaptă într-o anumită condiție. Această operațiune este utilă, de exemplu, atunci când mai multe procese așteaptă ca diferite cantități de stocare să devină disponibile. Eliberarea stocării poate permite oricât de multe dintre aceste procese să continue, dar planificatorul nu știe care dintre ele.

Un exemplu de implementare pentru o variabilă de condiție este după cum urmează:

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

Istorie

Per Brinch Hansen a fost primul care a descris și implementat monitoare, bazându-le pe ideile lui C. A. R. Hoare. Ulterior, Hoare a dezvoltat cadrul teoretic și a demonstrat echivalența acestora cu semafoarele (atunci când se folosește semantica originală).

Limbajele de programare care au suportat monitoare includ:

• Ada
• C# (si alte limbaje care folosesc .NET Framework)
• Concurrent Pascal
• Java
• Mesa
• Modula-3
• Squeak Smalltalk

Vezi și

• Mutual exclusion

Bibliografie

• 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

• "Monitors: An Operating System Structuring Concept Arhivat în 30 august 2006, la Wayback Machine." by Charles Antony Richard Hoare
• "Signalling in Monitors" by John H. Howard
• "Experience with Processes and Monitors in Mesa" by Butler W. Lampson and David D. Redell
• pthread_cond_wait - description from the Open Group Base Specifications Issue 6, IEEE Std 1003.1
• "Block on a Condition Variable Arhivat în 11 martie 2007, la Wayback Machine." by Dave Marshall
• "Strategies for Implementing POSIX Condition Variables on Win32" by Douglas C. Schmidt and Irfan Pyarali
• Condition Variable Routines from the Apache Portable Runtime Library
• wxCondition description
• boost::condition class description Arhivat în 7 martie 2007, la Wayback Machine.
• ZThread Condition Class Reference
• Wefts::Condition Class Reference
• ACE_Condition Class Template Reference Arhivat în 1 aprilie 2006, la Wayback Machine.
• QWaitCondition Class Reference
• Common C++ Conditional Class Reference Arhivat în 1 februarie 2010, la Wayback Machine.
• at::ConditionalMutex Class Reference Arhivat în 4 februarie 2012, la Wayback Machine.
• threads::shared - Perl extension for sharing data structures between threads