Semàfor (informàtica)

Un semàfor és una variable especial protegida (o tipus abstracte de dades) que constitueix el mètode clàssic per a restringir o permetre l'accés als recursos compartits (per exemple, un recurs d'emmagatzematge del sistema o variables del codi font) en un entorn de múltiples (en què s'executaran diversos processos concurrentment). Van ser inventats per Edsger Dijkstra i es van usar per primera vegada en el sistema operatiu THEOS.

Operacions

Els semàfors només poden ser manipulats usant les següents operacions (aquest és el codi amb espera activa):

Inicia (Semàfor s, Enter v)
{
 s = v;
}

En el que s'iniciarà la variable semàfor s a un valor enter v.

P (Semàfor s)
{
 if (s>0)
 s = s-1;
 else
 wait();
}

La qual mantindrà en espera activa regit pel semàfor si aquest té un valor inferior o igual al nul.

V (Semàfor s)
{
 if (!processos_bloquejats())
 s = s+1;
 else
 signal();
}

Aquestes instruccions es poden modificar per evitar l'espera activa, fent que l'operació P dormi al mateix procés que l'executa si no pot decrementar el valor, mentre que l'operació V desperta a un procés que no és qui l'executa. En un pseudollenguatge més comprensible, l'operació P sol denominar-se "wait" o "espera" i l'operació V "signal" o "senyal".

El perquè dels noms d'aquestes funcions, V i P, té el seu origen en la llengua holandès. "Verhogen" significa incrementar i "proberen" provar, encara que Dijkstra va usar la paraula inventada prolaag[1], que és una combinació deprobeer et Verlagen (intentar decrementar). El valor del semàfor és el nombre d'unitats del recurs que estan disponibles (si només hi ha un recurs, s'utilitza un "semàfor binari" amb els valors 0 i 1).

S'hi ha n recursos, s'inicialitzarà el semàfor al nombre n. Així, cada procés, a l'anar demanant un recurs, comprovarà que el valor del semàfor sigui més gran de 0. Si és així, voldrà dir que hi ha recursos lliures i seguidament acapararà el recurs i decrementarà el valor del semàfor.

Quan el semàfor arriba a 0, significa que tots els recursos estan essent utilitzats, i els processos que vulguin demanar un recurs hauran d'esperar que el semàfor tingui un valor superior a 0, és a dir: algun dels processos que estan utilitzant els recursos haurà acabat amb ell i incrementarà el semàfor amb un signal o V (s).

Inicia s'utilitza per inicialitzar el semàfor abans que es facin peticions sobre ell, i pren per argument un enter. Quan no hi ha un recurs disponible, l'operació P, atura l'execució quedant en espera activa (o dormint) fins que el valor del semàfor sigui positiu, en aquest cas reclama immediatament decrement. V és l'operació inversa: allibera un recurs després que el procés ha acabat d'usar-lo. Les operacions PiV han de ser indivisibles (o atòmiques), i.e. són operacions que poden ser interrompudes enmig de la seva execució.

L'operació V és anomenada a vegades pujar el semàfor (up) i l'operació P es coneix també com baixar el semàfor (down), i també són anomenadessignal i wait o deixar anar i prendre.

Per evitar l'espera activa, un semàfor pot tenir associada una cua de processos (normalment una cua FIFO). Si un procés s'efectua una operació P en un semàfor que té valor zero, el procés és bloquejat i afegit a la cua del semàfor. Quan un altre procés incrementa el semàfor mitjançant l'operació V i hi ha processos a la cua associada, s'extreu un d'ells (el primer que va entrar en una cua FIFO) i es reprèn la seva execució.

Usos

Els semàfors s'empren per permetre l'accés a diferents parts de programes (anomenats 'seccions crítiques') on es manipulen variables o recursos que han de ser accedits de manera especial. Segons el valor amb el que són inicialitzats, es permet utilitzar el recurs de forma simultània a més o menys processos.

Un tipus senzill de semàfor és el binari, que pot prendre només els valors 0 i 1. S'inicialitzen en 1 i són usats quan només un procés pot accedir a un recurs a la vegada. Són essencialment el mateix que els mutex. Quan el recurs està disponible, un procés accedeix i decrementa el valor del semàfor amb l'operació P. El valor queda llavors en 0, el que fa que si un altre procés intenta decrementat s'hagi d'esperar. Quan el procés que decrementa el semàfor realitza una operacióV, algun procés que estava esperant pot despertar i seguir executant.

Per fer que dos processos s'executin en una seqüència es pot utilitzar un semàfor inicialitzats a 0. El procés que ha d'executar primer en la seqüència realitza l'operacióVsobre el semàfor abans del codi que ha de ser executat després de l'altre procés. Aquest executa l'operacióP. Si el segon procés en la seqüència és programat per a executar abans que l'altre, en ferPdormirà fins que el primer procés de la seqüència passi per la seva operacióV. Aquesta manera d'ús s'anomena senyalitació (signaling), i es fa servir perquè un procés o fil d'execució li faci saber a un altre que alguna cosa ha succeït.

Exemple d'ús

Els semàfors poden ser usats per a diferents propòsits, entre ells:

• Implementar forrellats d'exclusió mútua o locks
• Barreres
• Permetre a un màxim de N threads accedir a un recurs, inicialitzant el semàfor en N
• Notificació. Inicialitzant el semàfor en 0 pot usar-se per comunicació entre threads sobre la disponibilitat d'un recurs.

En el següent exemple es creen i executen n processos que intentaran entrar a la seva secció crítica cada vegada que puguin, i ho aconseguiran sempre de a un per primera vegada, gràcies a l'ús del semàfor s inicialitzats a 1. El mateix té la mateixa funció que un lock.

const int n /* nombre de processos */
variable semàfor s; /* declaració de la variable semàfor de valor enter */
Inicia(s, 1) /* Inicialitza un semàfor amb nom s amb valor 1 */

void P(int i) {
 while(true) {
 P(s) /* En semàfors binaris, el correcte és posar un P (s) abans d'entrar a la secció crítica, per restringir l'ús d'aquesta regió del codi */
 /* SECCIÓ CRÍTICA */
 V(s) /* Després de la secció crítica, tornem a posar el semàfor a 1 perquè un altre procés pugui usar */
 /* RESTA DEL CODI */
 }
}
int main(){
 Començar-processos(P(1), P(2),..., P(n));
}

Vegeu també

• El sopar de filòsofs
• Cadenat (informàtica)
• Monitor (concurrència)

Enllaços externs

• The Little Book of Semaphore by Allen B. Downey
• Semàfors en C per a linux

Viccionari