Algorisme de Dekker

De Viquipèdia

L'algorisme de Dekker, és un algorisme de programació concurrent que permet que dos processos accedeixin sense conflicte a un recurs compartit, utilitzant només memòria compartida per a comunicar-se. Aquest algorisme fou inventat pel matemàtic holandès T. J. Dekker i fou un dels primers algorismes dissenyats per garantir exclusió mútua.

[edita] L'Algorisme

Si dos processos intenten accedir a una secció crítica al mateix temps, l'algorisme decidirà quin d’ells té preferència i bloquejarà a l’altre. Si un procés ja es troba en la secció crítica, el segon procés estarà en espera activa fins que el primer procés acabi. Per aconseguir aquest comportament, s'utilitzen dues variables que indiquen la intenció d'entrar a la secció critica, i una variable de torn que indica quin procés té prioritat sobre l'altre. Siguin f0 i f1 les variables que dos processos p0 i p1 utilitzen respectivament per senyalitzar l'accés a la secció crítica i sigui turn la variable utilitzada per expressar que un procés (per exemple p0) té prioritat. Llavors, l'algorisme funciona tal com iŀlustra el següent pseudocodi:

 f0 := false
 f1 := false
 turn := 0   // or 1

 p0:                                      p1:
     f0 := true                              f1 := true
     while f1 {                              while f0 {
         if turn ≠ 0 {                           if turn ≠ 1 {
             f0 := false                             f1 := false
             while turn ≠ 0 {                        while turn ≠ 1 {
             }                                       }
             f0 := true                              f1 := true
         }                                       }
     }                                       }

    // secció crítica                        // secció crítica
    ...                                          ...
    turn := 1                                turn := 0
    f0 := false                              f1 := false

Com es pot veure, un procés, per exemple p0, indica la seva intenció d'entrar a la secció crítica mitjançant la seva variable f0. El bucle exterior comprova si el procés p1 també té intenció d'accedir-hi (o si ja l'està executant). Si no és així, el procés p0 passa directament a executar la secció crítica. Si p1 també vol accedir-hi (o ja l’està executant), es verifica el valor de la variable turn. Si la prioritat es per p1 (turn = 1), el procés p0 senyalitza mitjançant f0 que temporalment desisteix i entra en espera activa fins que turn canvii de valor. Llavors, senyalitzarà l'accés a la secció crítica (f0 = true) i l'executarà. En canvi, si el torn era per p0 (turn = 0), llavors aquest procés passa a executar la secció crítica. Després d'executar el codi crític, els processos assignen el torn a l'altre i senyalitzen que ja no necessiten tornar -lo a executar.

L'algorisme de Dekker garanteix exclusió mútua, evitant interbloqueig (deadlock) i inanició (starvation). Fixem-nos que l'exclusió mútua es garanteix en tot moment perquè cap dels dos processos pot esdevenir crític sense abans haver-ho senyalitzat. L'absència de d'inanició es garanteix perquè els dos processos comproven si no és el seu torn abans de senyalitzar que no s'estan executant i entrar en espera activa.

[edita] Comentaris

Un avantatge de l'algorisme de Dekker és que no requereix operacions especials de lectura/escriptura atòmiques (en un sol pas, sense alliberar el bus de memòria) i per tant es molt portable entre llenguatges de programació i arquitectures de computadors. Malgrat tot, molts compiladors poden executar optimitzacions que poden causar que aquest algorisme falli. Per exemple, el compilador podria detectar que les variables f0 i f1 no s'hi accedeix mai dins del bucle i podria eliminar l'escriptura a aquestes variables. Per tant, és necessari anar amb compte si es vol usar aquesta algorisme i activar les opcions d'optimització del compilador. En C o C++, es poden marcar les variables com a volàtils (volatile), però això només serà efectiu per sistemes amb un sol processador.

Dos desavantatges de l'algorisme són la limitació a dos processos i l'ús d'espera activa en comptes la suspensió dels processos. Els sistemes operatius moderns proveeixen primitives d'exclusió mútua que són mes generals i flexibles que l'algorisme de Dekker, i per tant l'algorisme és poc utilitzat. De totes formes, l'absència de contenció entre els dos processos fa que l'entrada i la sortida de la secció crítica siguin molt eficients, permeten-lo usar on no sigui factible l'ús de crides de sistema.

Altres algorismes semblants al de Dekker, però més avançats, són per exemple l'algorisme de Peterson o l'algorisme de Lamport.

[edita] Referències i enllaços externs

• Codi font de l'algorisme de Dekker