Un semafor este o primitivă de sincronizare [1] a muncii proceselor și firelor de execuție , care se bazează pe un contor, pe care pot fi efectuate două operații atomice : creșterea și scăderea valorii cu unul, în timp ce operația de scădere pentru valoarea zero a contorul se blochează [2 ] . Servește pentru a construi mecanisme de sincronizare mai complexe [1] și este folosit pentru a sincroniza sarcini care rulează în paralel, pentru a proteja transferul de date prin memorie partajată , pentru a proteja secțiunile critice și, de asemenea, pentru a controla accesul la hardware.
Semaforele de calcul sunt folosite pentru a controla resursele limitate [3] . Semaforele binare asigură excluderea reciprocă a execuției secțiunilor critice [4] , iar implementarea lor simplificată este mutexurile , care sunt mai limitate în utilizare [5] . Pe lângă excluderea reciprocă în cazul general, semaforele și mutexurile pot fi utilizate în mulți alți algoritmi tipici, inclusiv semnalizarea către alte sarcini [6] , permițând doar unei sarcini să treacă anumite puncte de control la un moment dat, prin analogie cu un turnichet [7] ] , problema producătorului și consumatorului, care presupune transferul de date de la o sarcină la alta [8] , bariere care permit sincronizarea grupurilor de sarcini la anumite puncte de control [9] , variabile de condiție pentru a notifica alte sarcini de orice eveniment [3] și blocări de citire și scriere care permit citirea simultană a datelor, dar interzice modificarea lor simultană [10] .
Problemele tipice ale utilizării semaforelor sunt blocarea simultană a două sarcini în timp ce se așteaptă una pe cealaltă [11] și lipsa de resurse, ca urmare a căreia o resursă poate fi periodic indisponibilă pentru unele sarcini din cauza utilizării acesteia de către alte sarcini [12] . Atunci când este utilizat în procese în timp real, poate apărea inversarea priorității, ceea ce poate determina blocarea pe termen nelimitat a unui proces cu prioritate mai mare din cauza procesului cu prioritate mai mică care dobândește semaforul, în timp ce timpul CPU este acordat procesului cu prioritate medie [13 ] , soluția pentru care este moștenirea prioritară [14] .
Conceptul de semafor a fost introdus în 1965 de omul de știință olandez Edsger Dijkstra [15] , iar în 1968 a propus utilizarea a doi semafor pentru a rezolva problema producătorului și consumatorului [8] .
Un semafor este un numărător pe care pot fi efectuate două operații: creșterea cu 1 ( English up ) și scădere cu 1 ( English down ). Când se încearcă scăderea unui semafor a cărui valoare este zero, sarcina care a solicitat această acțiune trebuie să se blocheze până când devine posibilă reducerea valorii semaforului la o valoare nenegativă, adică până când un alt proces crește valoarea semaforului [ 16] . Blocarea unei sarcini este înțeleasă ca o schimbare a stării unui proces sau a unui fir de către planificatorul de sarcini astfel încât sarcina își va suspenda execuția [17] .
Operațiile de scădere și creștere a valorii unui semafor au fost inițial notate cu literele P (din olandeză proberen - a încerca) și respectiv V (din olandeză verhogen - a ridica mai sus). Dijkstra a dat aceste notații operațiunilor pe semafore, dar din moment ce nu sunt înțelese de oamenii care vorbesc alte limbi, alte notații sunt de obicei folosite în practică. Denumirile upși downau fost folosite pentru prima dată în limba Algol 68 [18] .
Operațiile de creștere și decrementare ale unui semafor, împreună cu toate verificările, trebuie să fie atomice . Dacă în momentul creșterii valorii semaforului există mai multe procese blocate pe acest semafor, atunci sistemul de operare selectează unul dintre ele și îi permite să finalizeze operația de scădere a valorii semaforului [16] .
Este în general acceptat că valoarea unui semafor este nenegativă, dar există o altă abordare a definirii unui semafor, în care o valoare negativă este înțeleasă ca numărul de sarcini blocate cu semn negativ. Cu această abordare, scăderea semaforului se blochează dacă rezultatul operației a devenit negativ [17] .
Scopul principal al semaforului este de a permite sau de a interzice temporar efectuarea oricăror acțiuni, deci dacă valoarea contorului semaforului este mai mare decât zero, atunci ei spun că este într-o stare de semnal, dacă valoarea este zero - într-un stare fără semnal [19] . Reducerea valorii unui semafor se mai numește uneori și achiziție ( ing. dobândește [20] ), iar creșterea valorii - eliberare sau eliberare ( ing. eliberare [20] ) [21] , ceea ce face posibilă descrierea funcționarea unui semafor mai ușor de înțeles în contextul controlării utilizării unei anumite resurse sau atunci când este utilizat în secțiuni critice.
În general, un semafor poate fi reprezentat ca un obiect format din [22] :
Conceptul de semafor este bine potrivit pentru sincronizarea firelor, poate fi folosit pentru sincronizarea proceselor, dar este complet nepotrivit pentru sincronizarea interacțiunii computerelor. Un semafor este o primitivă de sincronizare de nivel scăzut, astfel încât, cu excepția protejării secțiunilor critice, poate fi dificil de utilizat singur [23] . O altă primitivă de sincronizare de nivel inferior este futex . Poate fi furnizat de sistemul de operare și este foarte potrivit pentru implementarea semaforelor la nivel de aplicație atunci când se utilizează operații atomice pe un contor partajat [24] .
Semaforele pot fi binare și computaționale [3] . Semaforele de calcul pot lua valori întregi nenegative și sunt folosite pentru a lucra cu resurse, al căror număr este limitat [3] , sau pentru a participa la sincronizarea sarcinilor de execuție paralelă. Semaforele binare pot lua numai valorile 0 și 1 [3] și sunt folosite pentru a exclude reciproc două sau mai multe procese de la a se afla în secțiunile lor critice în același timp [4] .
Semaforele Mutex [3] ( mutexurile ) sunt o implementare simplificată a semaforelor, asemănătoare cu semaforele binare cu diferența că mutexurile trebuie eliberate prin același proces sau fir care le achiziționează [25] , totuși, în funcție de tip și implementare, un încercarea de a elibera printr-un alt fir poate să elibereze mutex-ul și să returneze o eroare [26] . Alături de semaforele binare, acestea sunt utilizate în organizarea secțiunilor critice de cod [27] [28] . Spre deosebire de semaforele binare, starea inițială a unui mutex nu poate fi capturată [29] și pot suporta moștenirea prioritară [30] .
Semaforele ușoare sunt semafore care utilizează o buclă de așteptare activă înainte de a executa o blocare. O buclă de așteptare activă în unele cazuri vă permite să reduceți numărul de apeluri de sistem [3] .
Semnalizarea, numită și notificare, este scopul de bază al semaforelor, ea asigură că o bucată de cod dintr-o sarcină este executată după ce o bucată de cod dintr-o altă sarcină este executată [6] . Semnalarea utilizării unui semafor implică de obicei setarea valorii sale inițiale la 0, astfel încât sarcinile care așteaptă starea semnalată să se poată bloca până la producerea evenimentului. Semnalizarea se face prin creșterea valorii semaforului, iar așteptarea se face prin decrementarea valorii [29] .
| curentul principal | |
|---|---|
| |
| Fluxul 1 | Fluxul 2 |
|
Thread 2 a primit mai întâi timpul CPU
|
Semaforele sunt potrivite pentru semnalizarea uneia sau mai multor sarcini, al căror număr este cunoscut în prealabil. Dacă numărul de sarcini care așteaptă o stare de semnal nu este cunoscut în prealabil, atunci sunt utilizate de obicei variabilele de condiție .
Excluderea reciprocăÎn aplicațiile cu mai multe fire, este adesea necesar ca secțiuni separate de cod, numite secțiuni critice , să nu poată rula în paralel, de exemplu, când se accesează o resursă nepartajată sau când se schimbă locațiile de memorie partajată. Pentru a proteja astfel de zone, puteți folosi un semafor binar sau un mutex [3] . Un mutex este mai sigur de utilizat deoarece poate fi eliberat doar de procesul sau firul care l-a dobândit [5] . De asemenea, utilizarea unui mutex în locul unui semafor poate fi mai eficientă datorită optimizării pentru două valori la nivelul implementării codului de asamblare.
Valoarea inițială a semaforului este setată la unu, ceea ce înseamnă că nu este capturat - nimeni nu a intrat încă în secțiunea critică. Intrarea ( în engleză enter ) în secțiunea critică este capturarea semaforului - valoarea acestuia este redusă la 0, ceea ce face o încercare repetată de a intra în blocarea secțiunii critice. La ieșirea ( ing. leave ) din secțiunea critică, semaforul este eliberat, iar valoarea lui devine egală cu 1, permițând reintrarea în secțiunea critică, inclusiv în alte fire sau procese .
Pentru resurse diferite, pot exista diferiți semafori responsabili pentru secțiunile critice. Astfel, secțiunile critice protejate de diferiți semafori pot funcționa în paralel.
| curentul principal | |
|---|---|
| |
| Fluxul 1 | Fluxul 2 |
Thread 1 a primit mai întâi timpul CPU
|
A capturat în fluxul 1
|
Pe lângă semafore, excluderea reciprocă poate fi organizată prin alte metode de sincronizare, de exemplu, prin monitoare , dacă acestea sunt suportate de limbajul de programare utilizat. Monitoarele vă permit să protejați un set de date prin ascunderea detaliilor de sincronizare de la programator și oferind acces la datele protejate doar pentru a monitoriza procedurile, iar implementarea monitoarelor este lăsată la latitudinea compilatorului și se bazează de obicei pe un mutex sau un semafor binar. În comparație cu semaforele, monitoarele pot reduce numărul de erori în programe, dar, în ciuda ușurinței de utilizare, numărul de limbi care acceptă monitoare este mic [31] .
TurnichetEste adesea sarcina de a permite sau de a refuza una sau mai multe sarcini să treacă prin anumite puncte de control. Pentru a rezolva această problemă, se folosește un algoritm bazat pe două semafore, care în funcționarea sa seamănă cu un turnichet, deoarece permite o singură sarcină să fie ignorată la un moment dat. Turnichetul se bazează pe un semafor, care este capturat la punctele de control și eliberat imediat. Dacă este necesară închiderea turnichetului, atunci semaforul trebuie confiscat, drept urmare toate sarcinile care trec prin turnichet vor fi blocate. Dacă doriți să permiteți sarcinilor să treacă din nou prin turnichet, atunci este suficient să eliberați semaforul, după care sarcinile vor continua să se execute pe rând [7] .
Trecerea alternativă prin turnichet are un mare dezavantaj - pentru fiecare pasaj, poate apărea o schimbare inutilă a contextului între sarcini, în urma căreia performanța algoritmului va scădea. În unele cazuri, soluția poate fi utilizarea unui turnichet cu mai multe locuri care deblochează mai multe sarcini simultan, ceea ce se poate face, de exemplu, prin eliberarea ciclică a semaforului dacă implementarea semaforului utilizată nu acceptă o creștere cu un număr arbitrar [ 32] .
Pseudocod turnichet| Inițializare | Turnichet | blocare | Deblocați |
|---|---|---|---|
| turnichet = Semafor(1) | apuca (turnichet) da drumul (turnichet) | apuca (turnichet) | da drumul (turnichet) |
Turnichetele pe bază de semafor pot fi folosite, de exemplu, în mecanismele de barieră [33] sau încuietori de citire/scriere [34] .
ComutareUn alt algoritm tipic bazat pe semafor este implementarea comutatorului. Sarcinile pot apuca comutatorul și îl pot elibera. Prima sarcină care apucă comutatorul este pornirea acestuia. Iar ultima sarcină care îl eliberează îl oprește. Pentru acest algoritm, putem desena o analogie cu un întrerupător de lumină dintr-o cameră. Primul care intră în cameră aprinde lumina, iar ultimul care iese din cameră o stinge [35] .
Algoritmul poate fi implementat pe baza contorului de sarcini care au capturat comutatorul si semaforul comutatorului, operatii asupra carora trebuie protejate de un mutex. Când comutatorul este capturat, contorul este incrementat cu 1, iar dacă valoarea sa s-a schimbat de la zero la unu, atunci semaforul comutatorului este capturat, ceea ce este echivalent cu pornirea comutatorului. În acest caz, creșterea contorului, împreună cu verificarea și captarea semaforului, sunt o operație atomică protejată de un mutex. Când comutatorul este eliberat, contorul scade, iar dacă valoarea lui devine zero, atunci semaforul comutatorului este eliberat, adică comutatorul este comutat în starea oprit. Scăderea contorului împreună cu verificarea lui și eliberarea semaforului trebuie să fie și o operație atomică [35] .
Pseudocod al algoritmului de funcționare a întrerupătorului| Tip de date | Inițializare | Utilizare |
|---|---|---|
| Intrerupator: număr = 0 mutex = semafor (1) Intrerupator, blocare (semafor țintă): apuca (mutex) cantitate += 1 dacă număr == 1: captura (semafor țintă) eliberare (mutex) Intrerupator, deblocare (semafor țintă): apuca (mutex) cantitate -= 1 dacă număr == 0: eliberare (semafor țintă) eliberare (mutex) | comutator = Comutator() semafor = Semafor(1) | bloc (comutator, semafor) // Secțiunea critică a comutatorului, // semaforul este blocat deblocare (comutator, semafor) |
Algoritmul de comutare este utilizat într-un mecanism mai complex - blocări de citire și scriere [35] .
Problema producătorului și consumatoruluiSarcina producatorului consumator presupune producerea unor informatii de catre o sarcina si transferul acestor informatii la o alta sarcina pentru prelucrare. În sistemele cu mai multe fire, producția și consumul simultan poate duce la condiții de cursă , necesitând utilizarea secțiunilor critice sau a altor mijloace de sincronizare. Semaforul este cea mai simplă primitivă de sincronizare care poate fi folosită pentru a rezolva problema producătorului și consumatorului.
Trecerea datelor printr-un buffer inelBuffer-ul inel este un buffer cu un număr fix de elemente, în care datele sunt introduse și procesate pe baza FIFO (primul intrat, primul-ieșit ). Într-o versiune cu un singur thread, 4 celule de memorie sunt suficiente pentru a organiza un astfel de buffer:
Într-o implementare multitasking, algoritmul este complicat de nevoia de sincronizare a sarcinilor. Pentru cazul a două sarcini (producător și consumator), ne putem limita la două celule de memorie și doi semafori [8] :
Valoarea inițială a semaforului responsabil pentru citire este setată la 0 deoarece coada este goală. Și valoarea semaforului responsabil pentru scriere este setată egală cu dimensiunea totală a tamponului, adică întregul tampon este disponibil pentru umplere. Înainte de a umple următorul element din buffer, semaforul de scriere este decrementat cu 1, rezervând următorul element al cozii pentru scrierea datelor, după care se modifică indicele de scriere, iar semaforul de citit este mărit cu 1, permițând citirea elementului adăugat. la coadă. Sarcina de citire, dimpotrivă, captează semaforul pentru citire, după care citește următorul element din buffer și schimbă indexul următorului element pentru citire, iar apoi eliberează semaforul pentru scriere, permițând sarcinii de scriere să scrie în elementul eliberat [8] .
Pseudocod tampon inel| Inițializare | Utilizare |
|---|---|
| dimensiunea tamponului = N permisiune de scriere = Semafor (dimensiunea tamponului) read-permission = Semafor(0) per-scriere = 0 la citire = 0 buffer = matrice (dimensiunea tamponului) | // Sarcina de scriere produs-element = produce-element() captura (permisiune de scriere) buffer[per-write] = produs-articol per-scriere += 1 dacă per-înregistrare >= dimensiunea tamponului: per-scriere = 0 eliberare (permisiune de citire) // Citiți sarcina apuca (permisiune de citire) element-read = buffer[pe-citire] per citire += 1 dacă per-lectura >= dimensiunea tamponului: la citire = 0 eliberare (permisiune de scriere) proces (element de citire) |
Dacă un buffer inel este implementat pentru mai mulți scriitori și cititori, atunci se adaugă un mutex la implementare care blochează tamponul atunci când scrieți sau citiți din el [36] .
Trecerea datelor printr-un buffer arbitrarPe lângă transferul de date printr-un buffer inel, este posibil și transferul printr-unul arbitrar, dar în acest caz, scrierea și citirea datelor trebuie protejate de un mutex, iar semaforul este folosit pentru a notifica sarcina de citire despre prezența a următorului element din buffer. Sarcina de scriere adaugă un element protejat de mutex în buffer și apoi semnalează prezența acestuia. Sarcina de citire captează semaforul și apoi, sub protecția mutexului, primește următorul element. Este demn de menționat că încercarea de a achiziționa un semafor protejat cu mutex poate duce la un blocaj dacă se încearcă citirea dintr-un buffer gol, iar eliberarea semaforului într-o secțiune critică poate degrada ușor performanța. Acest algoritm, ca și în cazul unui buffer inel protejat de un mutex, permite mai multor sarcini să scrie și să citească simultan [37] .
O barieră este un mecanism de sincronizare a punctelor critice pentru un grup de sarcini. Sarcinile pot trece numai prin barieră dintr-o dată. Înainte de a intra într-un punct critic, sarcinile dintr-un grup trebuie să se blocheze până când ultima sarcină din grup ajunge la punctul critic. Odată ce toate sarcinile sunt pe cale să intre în punctele lor critice, ele trebuie să-și continue execuția [9] .
Cea mai simplă soluție pentru organizarea unei bariere în cazul a două sarcini se bazează pe doi semafori binari A și B, inițializați la zero. În punctul critic al primei sarcini, trebuie semnalat semaforul B, iar apoi trebuie capturat semaforul A. În punctul critic al celei de-a doua sarcini trebuie mai întâi semnalizat semaforul A, apoi trebuie capturat B. va semnala o altă sarcină. , permițând executarea acestuia. Odată ce ambele sarcini au atins punctele critice, semaforele lor vor fi semnalizate, permițându-le să-și continue execuția [38] .
Pseudocod de barieră simplu| Inițializare | Sarcina folosind bariera |
|---|---|
| sumă-țintă = N număr = 0 mutex = semafor (1) turnichet de intrare = Semafor(0) | // Prima fază de barieră apuca (mutex) cantitate += 1 if count == numărare-sarcini: eliberare (turnichet de intrare) eliberare (mutex) apuca (turnichet de intrare) eliberare (turnichet de intrare) // Punct critic |
O astfel de implementare este cu o singură trecere, deoarece bariera nu revine la starea inițială, are și performanțe scăzute datorită utilizării unui turnichet cu un singur loc, care necesită un comutator de context pentru fiecare sarcină, astfel încât această soluție este puțin utilizarea în practică [32] .
Barieră în două fazeO caracteristică a barierei în două faze este că, atunci când o utilizați, fiecare sarcină se oprește la barieră de două ori - înainte de punctul critic și după. Două opriri fac bariera să reintre , deoarece a doua oprire permite barierei să revină la starea inițială [39] .
Algoritmul universal de reintrare al mecanismului de barieră în două faze se poate baza pe utilizarea unui contor de sarcini care au atins punctul critic și a două turnichete cu mai multe locuri. Operațiunile pe tejghea și controlul turnichetelor trebuie protejate cu un mutex. În acest caz, numărul total de sarcini trebuie cunoscut în prealabil. Primul turnichet permite trecerea sarcinilor în punctul critic și trebuie inițial blocat. Al doilea omite sarcinile care tocmai au depășit punctul critic și ar trebui, de asemenea, blocat inițial. Înainte de a se apropia de punctul critic, contorul sarcinilor atinse este mărit cu 1, iar de îndată ce ajunge la numărul total de sarcini, primul turnichet este deblocat pentru toate sarcinile, trecându-le în punctul critic, ceea ce se întâmplă atomic prin mutex. împreună cu creşterea contorului şi verificarea acestuia. După punctul critic, dar înainte de al doilea turnichet, contorul pentru numărul de sarcini scade cu 1. Când valoarea ajunge la zero, al doilea turnichet este deblocat pentru toate sarcinile, în timp ce operațiunile la al doilea turnichet au loc și atomic, împreună cu contra decrementării și verificarea acesteia. Ca rezultat, toate sarcinile se opresc mai întâi înainte de punctul critic și apoi după. După trecerea barierei, stările tejghelei și turnichetelor sunt în valorile lor originale [32] .
Pseudocod al algoritmului de barieră cu două faze reintrante| Inițializare | Sarcina folosind bariera |
|---|---|
| mutex = semafor (1) număr = 0 turnichet de intrare = Semafor(0) exit-turnstile = Semafor(0) | // Prima fază de barieră apuca (mutex) cantitate += 1 if count == numărare-sarcini: eliberare(intrare-tornichet, cantitate) eliberare (mutex) apuca (turnichet de intrare) // Punct critic // A doua fază de barieră apuca (mutex) cantitate -= 1 dacă număr == 0: eliberare (turnichet de ieșire, cantitate) eliberare (mutex) apuca (turnichet de ieșire) |
O variabilă de condiție este o modalitate de a notifica sarcinile în așteptare atunci când are loc un eveniment [3] . Mecanismul variabilei de condiție la nivelul aplicației se bazează, de obicei, pe un futex și oferă funcții pentru așteptarea unui eveniment și trimiterea unui semnal despre apariția acestuia, dar părți separate ale acestor funcții trebuie protejate de un mutex sau semafor, deoarece în plus față de futex, mecanismul variabilei de condiție conține de obicei date suplimentare partajate [40] . În implementările simple, futex-ul poate fi înlocuit cu un semafor, care, atunci când este notificat, va trebui eliberat de câte ori este numărul de sarcini abonate la variabila condiție, cu toate acestea, cu un număr mare de abonați, notificarea poate deveni un blocaj [41] .
Mecanismul variabilei de condiție presupune prezența a trei operații: așteptarea unui eveniment, semnalarea unui eveniment unei sarcini și notificarea tuturor sarcinilor despre un eveniment. Pentru a implementa un algoritm bazat pe semafor, veți avea nevoie de: un mutex sau un semafor binar pentru a proteja variabila condiției în sine, un contor pentru numărul de sarcini în așteptare, un mutex pentru a proteja contorul, un semafor A pentru a bloca sarcinile în așteptare și un semafor suplimentar B pentru a trezi la timp următoarea sarcină de așteptare [42] .
La abonarea la evenimente, contorul sarcinilor abonate este incrementat atomic cu 1, după care este eliberat mutexul precapturat al variabilei de condiție. Semaforul A este apoi capturat pentru a aștepta ca evenimentul să aibă loc. La apariția unui eveniment, sarcina de semnalizare verifică atomic contorul sarcinilor abonate și notifică următoarea sarcină despre apariția evenimentului prin eliberarea semaforului A, iar apoi se blochează pe semaforul B, așteptând confirmarea deblocării. Sarcina alertată eliberează semaforul B și redobândește mutex-ul variabilei de condiție pentru a reveni la starea inițială. Dacă se face o notificare de difuzare a tuturor sarcinilor abonate, atunci semaforul A de sarcini blocate este eliberat într-un ciclu în funcție de numărul de sarcini abonate din contor. În acest caz, notificarea are loc atomic sub protecția contorului mutex, astfel încât contorul nu se poate schimba în timpul notificării [42] .
Pseudocod variabil de condiție| Declarație de tip | Utilizare |
|---|---|
| variabilă-condiție(): număr = 0 mutex = semafor (1) wait-event = Semafor(0) primire-eveniment = Semafor(0) variabilă condițională, așteptați(țintă-mutex): apuca (mutex) cantitate += 1 eliberare (mutex) eliberare (target-mutex) apuca (așteptați-evenimente) lansare (get-evenimente) grab(target-mutex) variabilă condițională, notifica(): apuca (mutex) dacă cantitatea > 0: cantitate -= 1 eliberare (evenimente de așteptare) grab(get-evenimente) eliberare (mutex) variabilă condițională, vizitează-toate(): apuca (mutex) dacă cantitatea > 0: eliberare (așteptați-evenimente, numărați) prinde (obține-evenimente, numără) număr = 0 eliberare (mutex) | // inițializare eveniment = condiție-variabilă() mutex = semafor (1) // Așteptați un eveniment apuca (mutex) așteptați (eveniment) // Secțiunea critică a evenimentului eliberare (mutex) // Alertă o sarcină notifica (eveniment) // Notifică toate sarcinile notifica-toata lumea(eveniment) |
Soluția semaforului are o problemă semnificativă - două comutatoare de context de semnalizare, ceea ce reduce foarte mult performanța algoritmului, deci cel puțin la nivelul sistemelor de operare nu este de obicei utilizat [42] .
Un fapt interesant este că semaforul în sine este ușor de implementat pe baza unei variabile de condiție și a unui mutex [24] , în timp ce implementarea unei variabile de condiție bazată pe semafore este mult mai complicată [42] .
Citiți și scrieți încuietoriUna dintre problemele clasice este sincronizarea accesului la o resursă care este disponibilă pentru citire și scriere în același timp. Blocările de citire și scriere sunt concepute pentru a rezolva această problemă și vă permit să organizați blocări separate de citire și scriere pe o resursă, permițând citirea simultană, dar interzicând scrierea simultană. Scrierea blochează, de asemenea, orice citire [10] . Un mecanism eficient nu poate fi construit doar pe baza unui futex, contorul numărului de cititori se poate schimba fără a debloca nicio sarcină [24] . Blocările de citire și scriere pot fi implementate pe baza unei combinații de mutexuri și semafore, sau mutexuri și o variabilă de condiție.
Algoritmul universal, lipsit de problema lipsei de resurse a sarcinilor de scriere, include un comutator semafor binar A pentru a organiza o secțiune critică a sarcinilor de lectură și un turnichet pentru a bloca noi sarcini de lectură în prezența scriitorilor în așteptare. Când sosește prima sarcină de citit, acesta captează semaforul A cu un comutator, împiedicând scrierile. Pentru scriitori, semaforul A protejează secțiunea critică a scriitorului, așa că dacă este capturată de cititori, toți scriitorii blochează intrarea în secțiunea lor critică. Totuși, sarcinile de captare de către scriitor a semaforului A și scrierea ulterioară este protejată de semaforul turnichet. Prin urmare, dacă are loc o blocare a unei sarcini de scriere din cauza prezenței cititorilor, turnichetul este blocat împreună cu noi sarcini de citire. De îndată ce ultimul cititor își termină treaba, semaforul comutatorului este eliberat și primul scriitor din coadă este deblocat. La sfârșitul activității sale, eliberează semaforul turnichetului, permițând din nou munca de citire a sarcinilor [34] .
Pseudocod al algoritmului universal de blocare citire-scriere| Inițializare | Sarcina de citire | Sarcina de scriere |
|---|---|---|
| comutator = Comutator() permisiunea de scriere = Semafor(1) turnichet = Semafor(1) | apuca (turnichet) eliberare (turnichet) blocare (comutator, permisiune-scriere) // Secțiunea critică a sarcinii de citire deblocare (comutator, permisiune-scriere) | apuca (turnichet) captura (permisiune de scriere) // Secțiunea critică a sarcinii de scriere da drumul (turnichet) eliberare (permisiune de scriere) |
La nivelul sistemelor de operare, există implementări de semafore de citire și scriere, care sunt modificate în mod special pentru a crește eficiența în utilizarea în masă [43] .
Una dintre problemele clasice de sincronizare este problema Dining Philosophers. Problema include 5 filozofi care iau masa la o masă rotundă, 5 farfurii, 5 furculițe și un fel de mâncare de paste în mijlocul mesei. Există o farfurie în fața fiecărui filosof și o furculiță la dreapta și la stânga, dar fiecare furculiță este împărțită între doi filosofi vecini și poți mânca paste doar cu două furculițe odată. Mai mult, fiecare dintre filozofi poate fie să gândească, fie să mănânce paste [44] .
Filosofii reprezintă firele care interacționează în program, iar soluția problemei include o serie de condiții [44] :
Pentru a rezolva problema, fiecărei furcături i se poate atribui un semafor binar. Când filosoful încearcă să ridice furculița, semaforul este capturat și, de îndată ce termină de mâncat, se eliberează semaforele furculițelor. Problema este că vecinul ar putea deja să ia furculița, atunci filosoful este blocat până mănâncă vecinul. Dacă toți filozofii încep să mănânce în același timp, blocajul este posibil [44] .
O soluție la impas ar putea fi limitarea la 4 a numărului de filozofi care iau masa în același timp. În acest caz, cel puțin un filozof va putea să ia masa în timp ce ceilalți așteaptă. Restricția poate fi implementată printr-un semafor cu o valoare inițială de 4. Fiecare dintre filosofi va captura acest semafor înainte de a lua furculițele, iar după ce a mâncat, îl va elibera. De asemenea, această soluție garantează că filozofii nu vor muri de foame, deoarece dacă un filosof așteaptă ca un vecin să elibereze furculița, o va elibera mai devreme sau mai târziu [44] .
Există și o soluție mai simplă. Blocarea este posibilă dacă 5 filozofi țin simultan o furculiță în aceeași mână, de exemplu, dacă toți sunt dreptaci și au luat prima furculiță din dreapta. Dacă unul dintre filozofi este stângaci și ia mai întâi bifurcația din stânga, atunci nici blocajul și nici foametea nu sunt posibile. Astfel, este suficient ca unul dintre filosofi să surprindă mai întâi semaforul furcii din stânga, apoi pe cel din dreapta, în timp ce ceilalți filozofi să facă opusul [44] .
Roller coasterO altă problemă clasică este problema roller coasterului , în care un tren de cărucioare se umple complet de pasageri, apoi îi rostogolește și se întoarce pentru mai mulți. În funcție de condițiile problemei, numărul de pasageri dispusi depășește numărul de locuri în tren, astfel încât următorii pasageri stau la coadă în timp ce trenul merge în cerc. Dacă trenul are M locuri, atunci trenul trebuie să aștepte mai întâi până când M pasageri stau pe locurile lor, apoi trebuie să le ofere o plimbare, să aștepte până când toți coboară și să aștepte din nou noi pasageri [45] .
Compoziția cărucioarelor împreună cu pasagerii poate fi reprezentată ca sarcini care interacționează. Fiecare pasager ar trebui blocat în timp ce își așteaptă rândul, iar trenul în sine ar trebui blocat în etapele de umplere și golire a locurilor. Pentru a încărca și descărca trenul se pot folosi două semafore cu comutatoare, fiecare protejat de mutex propriu, iar pentru blocarea călătorilor pentru încărcare și descărcare, se pot folosi două semafore responsabile de locurile din cărucioare. Pasagerii în așteptare confiscă semaforul de încărcare, iar trenul cu semaforul de încărcare îl anunță pe M despre disponibilitatea locurilor. Trenul este apoi blocat de un comutator până când ultimul pasager la îmbarcare semnalează cu semaforul corespunzător, după care începe călătoria. Înainte de călătorie, călătorii sunt blocați de un semafor pentru descărcare, care îi împiedică să părăsească trenul. După călătorie, trenul anunță pasagerii M cu un semafor de descărcare, permițându-le să coboare, apoi blochează semaforul comutatorului pentru descărcare, așteptând până când toți pasagerii au plecat. De îndată ce ultimul pasager părăsește trenul, el va semnaliza semaforul celui de-al doilea comutator și va permite trenului să ia din nou pasagerii [45] .
Conceptul de semafor oferă doar operațiunile de decrementare și incrementare cu 1. În același timp, o sarcină de decrementare a unui semafor de obicei nu poate ști dacă se va bloca sau nu. La semnalizare, nu există nicio modalitate de a ști dacă există sarcini blocate de semafor, iar dacă o sarcină semnalează un alt semafor blocat, atunci ambele sarcini continuă să funcționeze în paralel și nu există nicio modalitate de a ști care dintre ele va primi timpul procesorului următorul [17] .
În ciuda limitărilor conceptului de semafore, implementările specifice ale acestora pot fi lipsite de anumite restricții. De exemplu, capacitatea de a incrementa o valoare a semaforului cu un număr arbitrar este oferită în implementările Linux [46] , Windows [41] și System V (POSIX) [47] . Și semaforele POSIX vă permit să determinați dacă va avea loc o blocare a semaforului [48] .
Pe lângă limitările conceptului de semafor în sine, există și limitări impuse de sistemul de operare sau de o anumită implementare a unui semafor. Programatorul de sarcini al sistemului de operare este de obicei responsabil pentru alocarea timpului procesorului între procese și fire . Utilizarea semaforelor impune o serie de cerințe planificatorului și implementării semaforului în sine pentru a preveni lipsa de resurse, ceea ce este inacceptabil în aplicațiile multitasking [49] .
Primele două cerințe sunt necesare pentru ca orice sarcină să poată obține timp de procesor și să nu fie într-o stare infinită de pregătire, ceea ce vă permite deja să scrieți aplicații fără a lipsi de resurse. A treia cerință este necesară pentru a preveni înfometarea resurselor în excluderea reciprocă bazată pe semafor. Dacă semnalizarea va crește doar contorul de semafor, dar nu va trezi sarcina blocată pe acesta, atunci este posibilă o situație când aceeași sarcină eliberează și captează la infinit semaforul, iar alte sarcini blocate nu au timp să intre în starea gata, sau o fac, dar mult mai rar... Cu toate acestea, chiar dacă a treia cerință este îndeplinită, în cazul unui număr mare de sarcini blocate, lipsa de resurse este posibilă dacă aceleași sarcini sunt deblocate de fiecare dată. Această problemă este rezolvată prin a patra cerință, care se observă, de exemplu, dacă sarcinile blocate de semafor sunt trezite pe rând [49] .
Respectarea primelor trei cerințe permite implementarea așa-numitelor semafore slabe și respectarea tuturor celor patru puternice [49] .
Dacă semaforele sunt folosite incorect, pot apărea blocaje [50] - situații în care două sau mai multe sarcini paralele devin blocate, așteptând un eveniment unul de la celălalt [11] . Într-o astfel de situație, sarcinile nu își vor putea continua execuția în mod normal și, de obicei, unul sau mai multe procese trebuie forțate să se încheie. Blocajele pot fi rezultatul unor erori simple de semafor sau alte erori de sincronizare sau condiții de cursă , care sunt mai dificil de depanat.
O greșeală comună este să apelezi într-o secțiune critică o subrutină care folosește aceeași secțiune critică [51] .
Un exemplu ilustrativ de blocare reciprocă pot fi capturi imbricate ale semaforelor binare A și B care protejează diferite resurse, cu condiția ca acestea să fie capturate în ordine inversă într-unul dintre fire, ceea ce se poate datora, de exemplu, diferențelor de stil în scrierea programului. cod. Bug-ul unei astfel de implementări este o condiție de cursă, care poate determina rularea programului de cele mai multe ori, dar în cazul preluării paralele a resurselor, șansele de blocare sunt mari [52] .
| curentul principal | |
|---|---|
| |
| Fluxul 1 | Fluxul 2 |
|
|
Similar cu blocajul este problema înfometării resurselor, care poate să nu conducă la o încetare completă a muncii, dar se poate dovedi a fi extrem de negativă la implementarea algoritmului. Esența problemei constă în refuzurile periodice sau frecvente de a obține o resursă datorită captării acesteia de către alte sarcini [12] .
Un caz tipic pentru această problemă este o implementare simplă a blocărilor de citire/scriere , care blochează resursa pentru scriere în timpul citirii. Apariția periodică a unor noi sarcini de citire poate duce la o blocare nelimitată a scriere a resursei. Sub sarcină scăzută a sistemului, problema poate să nu se manifeste pentru o lungă perioadă de timp, cu toate acestea, sub sarcină mare, poate apărea o situație când există cel puțin o sarcină de citire la un moment dat, ceea ce va face blocarea scrierea permanentă în timpul timpul de sarcină mare [12] . Având în vedere un semafor care este eliberat atunci când coada de cititori este goală, o soluție simplă ar fi adăugarea unui semafor binar (sau mutex) pentru a proteja codul scriitorilor, acționând în același timp ca un turnichet pentru cititori. Scriitorii vor intra în secțiunea critică și vor lua un semafor de coadă gol, blocând două semafore atâta timp cât există cititori. Sarcinile de cititor se vor bloca la intrarea în turnichet dacă sarcina de scriitor așteaptă ca cititorii să-și termine munca. De îndată ce ultima sarcină de citire și-a terminat activitatea, eliberează semaforul de coadă gol, deblocând sarcina de scriere în așteptare [34] .
Excluderea reciprocă poate suferi și de înfometarea resurselor dacă implementarea sa se bazează pe semafore slabe, dar există algoritmi pentru a ocoli limitările semaforelor slabe în acest caz [49] .
O altă problemă poate fi inversarea priorității care poate apărea atunci când semaforele sunt folosite de procese în timp real. Procesele în timp real pot fi întrerupte de sistemul de operare doar pentru executarea proceselor cu prioritate mai mare. În acest caz, procesul se poate bloca pe semafor, așteptând ca acesta să fie eliberat de un proces cu o prioritate mai mică. Dacă în acest moment rulează un proces cu o prioritate medie între două procese, atunci un proces cu o prioritate mare poate fi blocat pentru o perioadă nelimitată de timp [13] .
Problema inversării priorităților se rezolvă prin moștenirea priorităților [14] . Dacă este posibil, semaforele pot fi înlocuite cu mutexuri, deoarece mutexurile pot avea o moștenire de prioritate predeterminată. Astfel, atunci când un mutex este capturat de un fir cu o prioritate mai mare, prioritatea sarcinii care deține mutex-ul va fi mărită preventiv pentru a-l elibera cât mai curând [30] .
Moștenirea omniprezentă a priorităților este o sarcină extrem de dificil de implementat, astfel încât sistemele care o susțin pot avea doar o implementare parțială. De asemenea, moștenirea priorității creează alte probleme, cum ar fi incapacitatea de a combina codul cu moștenirea prioritară cu codul fără moștenire atunci când se folosește aceeași secțiune critică [54] .
Dacă este necesară utilizarea semaforelor sau dacă nu există suport pentru moștenirea priorităților, algoritmii pot fi modificați pentru a crește în mod independent prioritățile pe sarcini [54] .
Standardele POSIX la nivel de sistem de operare oferă un API în limbaj C pentru tratarea semafoarelor atât la nivel de fir, cât și la nivel de proces prin intermediul memoriei partajate . Standardele definesc un tip de date semafor sem_tși un set de funcții pentru lucrul cu acesta [55] . Semaforele POSIX sunt disponibile pe Linux , macOS , FreeBSD și alte sisteme de operare compatibile cu POSIX.
| Funcţie | Descriere |
|---|---|
| sem_init()[doc. unu] | Inițializarea unui semafor cu o valoare inițială pentru contor și un indicator de utilizare la nivel de proces. |
| sem_destroy()[doc. 2] | Eliberați semaforul. |
| sem_open()[doc. 3] | Creați un nou sau deschideți un semafor denumit existent. |
| sem_close()[doc. patru] | Închiderea semaforului după terminarea lucrului cu el. |
| sem_unlink()[doc. 5] | Eliminarea numelui dintr-un semafor numit (nu îl distruge). |
| sem_wait()[doc. 6] | Descreșteți valoarea semaforului cu 1. |
| sem_timedwait()[doc. 7] | Scăderea valorii unui semafor cu 1, cu o limită a timpului maxim de bloc după care se returnează o eroare. |
| sem_trywait()[doc. opt] | Încercarea de a decrementa un semafor în modul fără blocare returnează o eroare dacă decrementarea fără blocare nu este posibilă. |
| sem_post()[doc. 9] | Creșteți valoarea semaforului cu 1. |
| sem_getvalue()[doc. zece] | Obțineți valoarea curentă a semaforului. |
Unul dintre dezavantajele semaforelor POSIX este specificația funcției predispuse la erori sem_timedwait()care funcționează pe ceasul în timp real ( CLOCK_REALTIME) [56] în loc de timpul de funcționare a sistemului ( CLOCK_MONOTONIC), ceea ce poate provoca blocarea programelor atunci când ora sistemului se modifică și poate fi critică pentru încorporat. dispozitive [57 ] , dar unele sisteme de operare în timp real oferă analogi ai acestei funcții care funcționează cu timpul de funcționare al sistemului [58] . Un alt dezavantaj este lipsa suportului pentru așteptarea pe mai multe semafore în același timp, sau pe un semafor și un descriptor de fișier.
Pe Linux, semaforele POSIX sunt implementate în biblioteca Glibc bazată pe futex [59] .
Semafoare System VStandardele POSIX definesc, de asemenea, un set de funcții din standardul X/Open System Interfaces (XSI) pentru manipularea semaforelor interprocese în cadrul sistemului de operare [60] . Spre deosebire de semaforele obișnuite, semaforele XSI pot fi mărite și micșorate cu un număr arbitrar, sunt alocate în matrice, iar durata lor de viață nu se extinde la procese, ci la sistemul de operare. Astfel, dacă uitați să închideți semaforul XSI când toate procesele aplicației sunt terminate, atunci acesta va continua să existe în sistemul de operare, ceea ce se numește o scurgere de resurse. În comparație cu semaforele XSI, semaforele obișnuite POSIX sunt mult mai ușor de utilizat și pot fi mai rapide [61] .
Seturile de semafoare XSI din sistem sunt identificate printr-o tastă numerică de tip key_t, cu toate acestea, este posibil să se creeze seturi de semafoare anonime pentru a fi utilizate în cadrul unei aplicații prin specificarea unei constante IPC_PRIVATEîn loc de taste numerice [62] .
| Funcţie | Descriere |
|---|---|
| semget()[doc. unsprezece] | Creează sau obține un identificator de set de semafor cu tasta numerică dată [62] . |
| semop()[doc. 12] | Efectuează operații atomice de decrementare și creștere cu numărul dat al contorului semaforului cu numărul acestuia din setul cu identificatorul dat și, de asemenea, permite blocarea așteptării valorii zero a contorului semaforului dacă este specificat 0 [47] ca număr dat. . |
| semctl()[doc. 13] | Vă permite să gestionați un semafor după numărul său dintr-un set cu un anumit identificator, inclusiv obținerea și setarea valorii curente a contorului; responsabil și de distrugerea setului de semafori [63] . |
Sistemele de operare Linux acceptă semaforele POSIX, dar oferă și o alternativă la semafore sub forma unui contor legat la un descriptor de fișier printr-un apel de sistem eventfd()[doc. 14] cu steag EFD_SEMAPHORE. Când un astfel de contor este citit printr-o funcție read(), acesta este decrementat cu 1 dacă valoarea sa a fost diferită de zero. Dacă valoarea a fost nulă, atunci are loc blocarea (dacă nu este specificat steagul EFD_NONBLOCK), așa cum este cazul semaforelor obișnuite. Funcția write()crește valoarea contorului cu numărul care este scris în descriptorul fișierului. Avantajul unui astfel de semafor este capacitatea de a aștepta starea semnalată a semaforului împreună cu alte evenimente folosind apeluri de sistem select()sau poll()[46] .
Nucleul Windows oferă, de asemenea, un API C pentru lucrul cu semafoare. Firele blocate pe un semafor sunt puse în coadă FIFO , dar pot ajunge la sfârșitul cozii dacă firul de execuție este întrerupt pentru a procesa alte evenimente [19] .
| Funcţie | Descriere |
|---|---|
| CreateSemaphoreA()[doc. cincisprezece] | Creați un semafor, specificând valoarea inițială a contorului, valoarea maximă și numele semaforului. |
| OpenSemaphoreW()[doc. 16] | Accesarea unui semafor după numele său dacă acesta există deja. |
| CloseHandle()[doc. 17] | Închiderea semaforului după terminarea lucrului cu el. |
| WaitForSingleObject()[doc. 18] sauWaitForMultipleObjects() [doc. 19] | Decrementează valoarea semaforului cu 1 cu blocare în cazul valorii contorului zero; vă permite să limitați timpul maxim de blocare. |
| ReleaseSemaphore()[doc. douăzeci] | Creșteți valoarea semaforului cu valoarea specificată. |
Caracteristicile semaforului Windows includ abilitatea de a incrementa un semafor cu un număr arbitrar [41] și capacitatea de a aștepta starea semnalului său împreună cu așteptările de blocare pentru alte semafore sau obiecte [64] .
Semaforele nu sunt de obicei acceptate în mod explicit la nivel de limbaj de programare, dar sunt adesea furnizate de biblioteci încorporate sau de la terți. În unele limbi, cum ar fi Ada [65] și Go [66] , semaforele sunt ușor de implementat în limbaj.
| Limba | Modul sau bibliotecă | Tip de date |
|---|---|---|
| Xi | pthread,rt | sem_t[doc. 21] |
| Ada | GNAT.Semaphores[doc. 22] | Counting_Semaphore,Binary_Semaphore |
| C++ | Boost | boost::interprocess::interprocess_semaphore[doc. 23] |
| C# | System.Threading[doc. 24] | Semaphore[doc. 25] |
| D | core.sync.semaphore[doc. 26] | Semaphore[doc. 27] |
| Merge | golang.org/x/sync/semaphore[doc. 28] | Weighted |
| Java | java.util.concurrent[doc. 29] | java.util.concurrent.Semaphore[doc. treizeci] |
| Piton | threading[doc. 31] ,asyncio [doc. 32] | threading.Semaphore[doc. 33] ,asyncio.Semaphore [doc. 34] |
Cel mai simplu exemplu de utilizare a unui semafor este excluderea reciprocă a posibilității de a executa secțiuni critice de cod pentru fire sau procese. Pentru a organiza excluderea reciprocă, un semafor binar și două funcții pot servi: intrarea în secțiunea critică și ieșirea din ea. Pentru simplitate, exemplul nu include capacitatea de a reține ID-ul firului de captură și ID-ul procesului căruia îi aparține firul. De asemenea, se presupune că secțiunea critică are un timp de execuție finit, nu foarte lung, astfel încât întreruperile operației de captare a semaforului ( EINTR) sunt ignorate, iar rezultatele întreruperii pot fi procesate după secțiunea critică. Semaforul în sine este abstractizat într-o structură pentru a îmbunătăți lizibilitatea codului.
În exemplu, sunt lansate două fire, dintre care unul crește contorul, iar celălalt îl decrește. Deoarece contorul este o resursă partajată, accesul la acesta trebuie să se excludă reciproc, altfel un fir poate suprascrie rezultatele operațiunilor altuia, iar valoarea rezultatului final poate fi eronată. Prin urmare, contorul este protejat de un semafor binar abstract care implementează excluderea reciprocă.
Exemplu de implementare simplă a secțiunii critice bazată pe semafor în C (POSIX) #include <errno.h> #include <pthread.h> #include <semafor.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #ifndef __STDC_LIB_EXT1__ typedef int errno_t ; #endif enumerare { EOK = 0 , }; // Implementarea mutex simplificată struct guard_t { sem_t sem_guard ; }; typedef struct guard_t guard_t ; // Inițializează mutexul simplificat errno_t guard_init ( guard_t * guard , bool between_processes ) { int r ; r = sem_init ( & guard -> sem_guard , între_procese , 1 ); dacă ( r == -1 ) { return errno ; } returnează EOK ; } // Eliberează mutexul simplificat void guard_free ( guard_t * guard ) { sem_destroy ( & garda -> sem_guard ); } // Intrarea în secțiunea critică errno_t guard_enter ( guard_t * garda ) { int r ; face { r = sem_wait ( & garda -> sem_guard ); } while (( r == -1 ) && ( errno == EINTR )); dacă ( r == -1 ) { return errno ; } returnează EOK ; } // Ieși din secțiunea critică errno_t guard_leave ( guard_t * garda ) { int r ; r = sem_post ( & garda -> sem_guard ); dacă ( r == -1 ) { return errno ; } returnează EOK ; } // Contor protejat de un mutex simplificat struct safe_counter_t { guard_t blocare ; int counter ; }; enumerare { // Numărul de operațiuni de decreștere/creștere OPERATIONS_COUNT = 100000 , }; // Thread incrementând contorul void * thread_inc_func ( void * thread_data ) { struct safe_counter_t * safe_counter = fire_data ; pentru ( int i = 0 ; i < OPERATIONS_COUNT ; ++ i ) { guard_enter ( & safe_counter -> blocare ); ++ safe_counter -> counter ; guard_leave ( & safe_counter -> blocare ); } } // Thread decrementând contorul void * thread_dec_func ( void * thread_data ) { struct safe_counter_t * safe_counter = fire_data ; pentru ( int i = 0 ; i < OPERATIONS_COUNT ; ++ i ) { guard_enter ( & safe_counter -> blocare ); -- safe_counter -> counter ; guard_leave ( & safe_counter -> blocare ); } } // Afișează un mesaj de eroare conform codului său void print_error ( errno_t errnum , const char * error_text ) { errno = errnum ; eroare ( text_eroare ); } int main ( int argc , char ** argv ) { errno_t errnum ; // inițializare struct safe_counter_t safe_counter ; safe_counter . contor = 0 ; guard_t blocare ; errnum = guard_init ( & safe_counter . lock , false ); dacă ( errnum ) { print_error ( errnum , „Eroare la inițializarea blocării mutex” ); ieșire ( EXIT_FAILURE ); } // Începeți două fire pthread_t thread_inc ; errnum = pthread_create ( & thread_inc , NULL , thread_inc_func , & safe_counter ); dacă ( errnum ) { print_error ( errnum , „Eroare la crearea thread_inc” ); ieșire ( EXIT_FAILURE ); } pthread_t thread_dec ; errnum = pthread_create ( & thread_dec , NULL , thread_dec_func , & safe_counter ); dacă ( errnum ) { print_error ( errnum , „Eroare la crearea thread_dec” ); ieșire ( EXIT_FAILURE ); } // Așteptați ca firele de execuție să se termine errnum = pthread_join ( thread_inc , NULL ); dacă ( errnum ) { print_error ( errnum , „Eroare de așteptare pentru thread_inc” ); ieșire ( EXIT_FAILURE ); } errnum = pthread_join ( thread_dec , NULL ); dacă ( errnum ) { print_error ( errnum , „Eroare de așteptare pentru thread_dec” ); ieșire ( EXIT_FAILURE ); } // Eliberarea datelor guard_free ( & blocare ); // Afișează rezultatul firelor, „0” printf ( "Contor: %d \n " , safe_counter . counter ); returnează EXIT_SUCCESS ; }Sincronizarea buffer-ului inel este puțin mai complicată decât protejarea secțiunii critice: există deja două semafore și le sunt adăugate variabile suplimentare . Exemplul arată structura și funcțiile de bază necesare pentru sincronizarea unui buffer inel C folosind interfața POSIX . Această implementare permite unui fir de execuție să scrie date în tamponul inel în mod ciclic și altui thread să citească din acesta în mod asincron.
Exemplu de implementare a unei primitive de sincronizare pentru un tampon circular folosind semafore în C (POSIX) #include <errno.h> #include <semafor.h> #include <stdio.h> #ifndef __STDC_LIB_EXT1__ typedef int errno_t ; #endif enumerare { EOK = 0 , }; struct ring_buffer_t { size_t lungime ; size_t w_index ; size_t r_index ; sem_t sem_r ; sem_t sem_w ; }; errno_t ring_buffer_init ( struct ring_buffer_t * rbuf , size_t length ) { rbuf -> lungime = lungime ; rbuf -> r_index = 0 ; rbuf -> w_index = 0 ; int r ; r = sem_init ( & rbuf -> sem_r , 1 , 0 ); dacă ( r == -1 ) { return errno ; } errno_t errnum ; r = sem_init ( & rbuf -> sem_w , 1 , lungime ); dacă ( r == -1 ) { errnum = errno ; du- te la aborting_sem_r ; } returnează EOK ; aborting_sem_r : sem_destroy ( & rbuf -> sem_r ); return errnum ; } void ring_buffer_free ( struct ring_buffer_t * rbuf ) { sem_destroy ( & rbuf -> sem_w ); sem_destroy ( & rbuf -> sem_r ); } errno_t ring_buffer_write_begin ( struct ring_buffer_t * rbuf ) { int r ; face { r = sem_wait ( & rbuf -> sem_w ); } while (( r == -1 ) && ( errno == EINTR )); dacă ( r == -1 ) { return errno ; } returnează EOK ; } errno_t ring_buffer_write_end ( struct ring_buffer_t * rbuf ) { ++ rbuf -> w_index ; if ( rbuf -> w_index >= rbuf -> lungime ) { rbuf -> w_index = 0 ; } int r ; r = sem_post ( & rbuf -> sem_r ); dacă ( r == -1 ) { return errno ; } returnează EOK ; } errno_t ring_buffer_read_begin ( struct ring_buffer_t * rbuf ) { int r ; face { r = sem_wait ( & rbuf -> sem_r ); } while (( r == -1 ) && ( errno == EINTR )); dacă ( r == -1 ) { return errno ; } returnează EOK ; } errno_t ring_buffer_read_end ( struct ring_buffer_t * rbuf ) { ++ rbuf -> r_index ; if ( rbuf -> r_index >= rbuf -> lungime ) { rbuf -> r_index = 0 ; } int r ; r = sem_post ( & rbuf -> sem_w ); dacă ( r == -1 ) { return errno ; } returnează EOK ; }În general, sistemele de operare efectuează citiri și scrieri atomice ale valorii contorului semaforului, dar detaliile de implementare pot varia în diferite arhitecturi. La achiziționarea unui semafor, sistemul de operare trebuie să scadă atomic valoarea contorului, după care procesul își poate continua activitatea. Dacă, ca urmare a scăderii contorului, valoarea poate deveni negativă, atunci sistemul de operare trebuie să suspende execuția procesului până când valoarea contorului devine astfel încât operația de scădere să conducă la un rezultat nenegativ [16] . În acest caz, în funcție de arhitectura la nivelul implementării, se poate realiza atât o încercare de reducere a valorii semaforului [67] , cât și scăderea acestuia cu rezultat negativ [68] . La nivelul interfeței aplicației, se presupune în mod obișnuit că valoarea minimă a unui semafor este 0 [3] . Când valoarea semaforului pe care au fost blocate procesele crește, următorul proces este deblocat, iar valoarea semaforului la nivelul aplicației rămâne egală cu zero.
O blocare la nivel de sistem de operare nu implică de obicei o așteptare fizică asupra procesorului, ci transferă controlul procesorului către o altă sarcină, în timp ce un semafor care așteaptă eliberarea intră în coada de sarcini blocate de acest semafor [69] . Dacă numărul de sarcini pregătite pentru execuție este mai mic decât numărul de procesoare, nucleul sistemului de operare poate comuta procesoarele libere în modul de economisire a energiei înainte de a avea loc orice eveniment.
Pentru a sincroniza munca procesoarelor în sistemele multiprocesor, există instrucțiuni speciale care vă permit să protejați accesul la orice celulă. În arhitectura x86 , Intel oferă un prefix pentru o serie de instrucțiuni ale procesorului LOCKcare vă permite să efectuați operații atomice pe celulele de memorie. Operațiile pe celule efectuate cu prefixul LOCKblochează accesul altor procesoare la celulă, ceea ce la un nivel primitiv permite organizarea de semafore ușoare cu o buclă de așteptare activă [70] .
Decrementarea atomică a unei valori a semaforului cu 1 se poate face cu o instrucțiune DECLprefixată cu LOCK, care setează steag-ul semnului CSdacă valoarea rezultată este mai mică decât zero. O caracteristică a acestei abordări este că valoarea semaforului poate fi mai mică decât zero, astfel încât după decrementarea contorului, flag-ul CSpoate fi verificat folosind instrucțiunea JNS, iar dacă semnul este negativ, sistemul de operare poate bloca sarcina curentă [71] .
Instrucțiunea poate fi folosită pentru a crește valoarea unui semafor cu 1 atomic LOCK INCL. Dacă valoarea rezultată este negativă sau egală cu zero, atunci aceasta înseamnă că există sarcini în așteptare, caz în care sistemul de operare poate debloca următoarea sarcină. Pentru a sări peste procesele de deblocare, poate fi folosită instrucțiunea JG, care sare la etichetă dacă steagurile rezultat al operației zero ( ZF) și semnul rezultat ( SF) sunt resetate la 0, adică dacă valoarea este mai mare decât 0 [72] .
În timpul blocării, în cazurile în care nu există sarcini curente, o instrucțiune poate fi folosită pentru a pune HLTprocesorul într-un mod de consum redus în timp ce se așteaptă întreruperi [73] , care trebuie mai întâi activate folosind instrucțiunea STI. Cu toate acestea, în procesoarele moderne, poate fi mai optim să folosiți instrucțiunile MWAITși MONITOR. Instrucțiunea MWAITeste similară HLT, dar vă permite să activați procesorul scriind într-o celulă de memorie la adresa specificată în MONITOR. NWAITpoate fi folosit pentru a monitoriza modificările slotului semaforului, cu toate acestea, pe sistemele de operare multitasking, această instrucțiune este folosită pentru a monitoriza un flag pentru a rula programatorul de sarcini pe un nucleu dat [74] .
Reducerea consumului de energie în timpul ciclului de somn activ poate fi realizată utilizând instrucțiunea PAUSE[75] .
În arhitectura ARMArhitectura ARMv7 folosește așa-numitele monitoare locale și globale exclusive pentru a sincroniza memoria între procesoare, care sunt mașini de stare care controlează accesul atomic la celulele de memorie [76] [77] . O citire atomică a unei celule de memorie poate fi efectuată folosind instrucțiunea LDREX[78] , iar o scriere atomică se poate face prin instrucțiunea STREX, care returnează și steag-ul de succes al operației [79] .
Pentru a reduce valoarea unui semafor, trebuie să așteptați până când contorul său devine mai mare decât zero. Așteptarea poate fi implementată în diferite moduri:
La nivelul unui sistem de operare multitasking, o combinație a acestor metode poate fi utilizată pentru a asigura utilizarea maximă a procesorului cu o tranziție la modul de economisire a energiei în perioadele de inactivitate.
Creșterea valorii unui semafor poate fi o citire ciclică a valorii curente a contorului prin instrucțiunea LDREX, apoi incrementarea unei copii a valorii și încercarea de a scrie înapoi în locația contorului folosind instrucțiunea STREX[84] . După o înregistrare cu succes a contorului, dacă valoarea sa inițială a fost zero, este necesară reluarea execuției sarcinilor blocate [84] , care în cazul unei comutări de context pot fi rezolvate prin intermediul sistemelor de operare [80] . Dacă procesorul a fost blocat folosind instrucțiunea WFE, acesta poate fi deblocat folosind instrucțiunea SEVcare anunță despre prezența oricărui eveniment [85] .
După decrementarea sau creșterea valorii semaforului, instrucțiunea este executată pentru a DMBasigura integritatea memoriei resursei protejate de semafor [86] .
| Comunicarea intraprocesuala | |
|---|---|
| Metode | |
| Protocoale și standarde selectate | |
| Tipuri de date | |
|---|---|
| Ininterpretabil | |
| Numeric | |
| Text | |
| Referinţă | |
| Compozit | |
| abstract |
|
| Alte | |
| subiecte asemănătoare | |