Requisito previo: sincronización de procesos, comunicación entre procesos
Para obtener dicha exclusión mutua, espera limitada y progreso, se han implementado varios algoritmos, uno de los cuales es el algoritmo de Dekker. Para comprender el algoritmo, comprendamos primero la solución al problema de la sección crítica.
Un proceso generalmente se representa como:
do {
//entry section
critical section
//exit section
remainder section
} while (TRUE);
La solución al problema de la sección crítica debe asegurar las siguientes tres condiciones:
- Exclusión mutua
- Progreso
- Espera limitada
Una de las soluciones para asegurar por encima de todos los factores es la solución de Peterson .
Otra es la Solución de Dekker . El algoritmo de Dekker fue la primera solución probablemente correcta al problema de la sección crítica. Permite que dos subprocesos compartan un recurso de un solo uso sin conflicto, utilizando solo la memoria compartida para la comunicación. Evita la alternancia estricta de un algoritmo ingenuo de toma de turnos y fue uno de los primeros algoritmos de exclusión mutua que se inventaron.
Aunque existen muchas versiones de la Solución de Dekker, la versión final o 5ª es la que cumple todas las condiciones anteriores y es la más eficiente de todas.
Nota –La solución de Dekker, mencionada aquí, garantiza la exclusión mutua solo entre dos procesos, podría extenderse a más de dos procesos con el uso adecuado de arrays y variables.
Algoritmo: requiere una array de valores booleanos y una variable entera:
var flag: array [0..1] of boolean;
turn: 0..1;
repeat
flag[i] := true;
while flag[j] do
if turn = j then
begin
flag[i] := false;
while turn = j do no-op;
flag[i] := true;
end;
critical section
turn := j;
flag[i] := false;
remainder section
until false;
Primera versión de la solución de Dekker: la idea es usar un número de subproceso común o compartido entre procesos y evitar que el otro proceso ingrese a su sección crítica si el subproceso compartido indica que el anterior ya se está ejecutando.
CPP
Main()
{
int thread_number = 1;
startThreads();
}
Thread1()
{
do {
// entry section
// wait until threadnumber is 1
while (threadnumber == 2)
;
// critical section
// exit section
// give access to the other thread
threadnumber = 2;
// remainder section
} while (completed == false)
}
Thread2()
{
do {
// entry section
// wait until threadnumber is 2
while (threadnumber == 1)
;
// critical section
// exit section
// give access to the other thread
threadnumber = 1;
// remainder section
} while (completed == false)
}
Python3
def Thread1(): doWhile=False while not completed or not doWhile: doWhile=True # entry section # wait until threadnumber is 1 while (threadnumber == 2): pass # critical section # exit section # give access to the other thread threadnumber = 2 # remainder section def Thread2(): doWhile=False while not completed or not doWhile: doWhile=True # entry section # wait until threadnumber is 2 while (threadnumber == 1): pass # critical section # exit section # give access to the other thread threadnumber = 1 # remainder section if __name__ == '__main__': thread_number = 1 startThreads()
El problema que surge en la implementación anterior es la sincronización lockstep, es decir, cada subproceso depende del otro para su ejecución. Si uno de los procesos se completa, entonces el segundo proceso se ejecuta, da acceso al completado y espera su turno, sin embargo, el primer proceso ya se completó y nunca se ejecutaría para devolver el acceso al último. Por lo tanto, el segundo proceso espera infinitamente entonces.
Segunda versión de la solución de Dekker: para eliminar la sincronización de bloqueo, utiliza dos banderas para indicar su estado actual y las actualiza en consecuencia en la sección de entrada y salida.
CPP
Main()
{
// flags to indicate if each thread is in
// its critical section or not.
boolean thread1 = false;
boolean thread2 = false;
startThreads();
}
Thread1()
{
do {
// entry section
// wait until thread2 is in its critical section
while (thread2 == true)
;
// indicate thread1 entering its critical section
thread1 = true;
// critical section
// exit section
// indicate thread1 exiting its critical section
thread1 = false;
// remainder section
} while (completed == false)
}
Thread2()
{
do {
// entry section
// wait until thread1 is in its critical section
while (thread1 == true)
;
// indicate thread2 entering its critical section
thread2 = true;
// critical section
// exit section
// indicate thread2 exiting its critical section
thread2 = false;
// remainder section
} while (completed == false)
}
Python3
def Thread1(): doWhile=False while not completed or not doWhile: doWhile=True # entry section # wait until thread2 is in its critical section while (thread2): pass # indicate thread1 entering its critical section thread1 = True # critical section # exit section # indicate thread1 exiting its critical section thread1 = False # remainder section def Thread2(): doWhile=False while not completed or not doWhile: doWhile=True # entry section # wait until thread1 is in its critical section while (thread1): pass # indicate thread1 entering its critical section thread2 = True # critical section # exit section # indicate thread2 exiting its critical section thread2 = False # remainder section if __name__ == '__main__': # flags to indicate if each thread is in # its critical section or not. thread1 = False thread2 = False startThreads()
El problema que surge en la versión anterior es la exclusión mutua en sí misma. Si los subprocesos se reemplazan (se detienen) durante la actualización de la bandera (es decir, durante current_thread = true), ambos subprocesos ingresan a su sección crítica una vez que se reinicia el subproceso reemplazado, también se puede observar lo mismo al inicio, cuando ambas banderas son falsas. .
Tercera versión de la solución de Dekker: para volver a garantizar la exclusión mutua, establece las banderas antes de la sección de entrada.
C++
Main()
{
// flags to indicate if each thread is in
// queue to enter its critical section
boolean thread1wantstoenter = false;
boolean thread2wantstoenter = false;
startThreads();
}
Thread1()
{
do {
thread1wantstoenter = true;
// entry section
// wait until thread2 wants to enter
// its critical section
while (thread2wantstoenter == true)
;
// critical section
// exit section
// indicate thread1 has completed
// its critical section
thread1wantstoenter = false;
// remainder section
} while (completed == false)
}
Thread2()
{
do {
thread2wantstoenter = true;
// entry section
// wait until thread1 wants to enter
// its critical section
while (thread1wantstoenter == true)
;
// critical section
// exit section
// indicate thread2 has completed
// its critical section
thread2wantstoenter = false;
// remainder section
} while (completed == false)
}
Python3
if __name__=='__main__': # flags to indicate if each thread is in # queue to enter its critical section thread1wantstoenter = False thread2wantstoenter = False startThreads() def Thread1(): doWhile=False while (completed == False or not doWhile): doWhile=True thread1wantstoenter = True # entry section # wait until thread2 wants to enter # its critical section while (thread2wantstoenter == True): pass # critical section # exit section # indicate thread1 has completed # its critical section thread1wantstoenter = False # remainder section def Thread2(): doWhile=False while (completed == False or not doWhile) : doWhile=True thread2wantstoenter = True # entry section # wait until thread1 wants to enter # its critical section while (thread1wantstoenter == True): pass # critical section # exit section # indicate thread2 has completed # its critical section thread2wantstoenter = False # remainder section
El problema con esta versión es una posibilidad de punto muerto. Ambos subprocesos podrían establecer su indicador como verdadero simultáneamente y ambos esperarán infinitamente más adelante.
Cuarta versión de la solución de Dekker: utiliza un pequeño intervalo de tiempo para volver a verificar la condición, elimina el interbloqueo y también garantiza la exclusión mutua.
CPP
Main()
{
// flags to indicate if each thread is in
// queue to enter its critical section
boolean thread1wantstoenter = false;
boolean thread2wantstoenter = false;
startThreads();
}
Thread1()
{
do {
thread1wantstoenter = true;
while (thread2wantstoenter == true) {
// gives access to other thread
// wait for random amount of time
thread1wantstoenter = false;
thread1wantstoenter = true;
}
// entry section
// wait until thread2 wants to enter
// its critical section
// critical section
// exit section
// indicate thread1 has completed
// its critical section
thread1wantstoenter = false;
// remainder section
} while (completed == false)
}
Thread2()
{
do {
thread2wantstoenter = true;
while (thread1wantstoenter == true) {
// gives access to other thread
// wait for random amount of time
thread2wantstoenter = false;
thread2wantstoenter = true;
}
// entry section
// wait until thread1 wants to enter
// its critical section
// critical section
// exit section
// indicate thread2 has completed
// its critical section
thread2wantstoenter = false;
// remainder section
} while (completed == false)
}
Python3
if __name__ == '__main__': # flags to indicate if each thread is in # queue to enter its critical section thread1wantstoenter = False thread2wantstoenter = False startThreads() def Thread1(): doWhile=False while (completed == False or not doWhile): doWhile=True thread1wantstoenter = True while (thread2wantstoenter == True) : # gives access to other thread # wait for random amount of time thread1wantstoenter = False thread1wantstoenter = True # entry section # wait until thread2 wants to enter # its critical section # critical section # exit section # indicate thread1 has completed # its critical section thread1wantstoenter = False # remainder section def Thread2(): doWhile=False while (completed == False or not doWhile): doWhile=True thread2wantstoenter = True while (thread1wantstoenter == True) : # gives access to other thread # wait for random amount of time thread2wantstoenter = False thread2wantstoenter = True # entry section # wait until thread1 wants to enter # its critical section # critical section # exit section # indicate thread2 has completed # its critical section thread2wantstoenter = False # remainder section
El problema de esta versión es el aplazamiento indefinido. Además, una cantidad de tiempo aleatoria es errática según la situación en la que se implemente el algoritmo, por lo que no es una solución aceptable en sistemas críticos para el negocio.
Algoritmo de Dekker: solución final y completa: la idea es usar la noción de hilo favorito para determinar la entrada a la sección crítica. El subproceso favorito alterna entre el subproceso que proporciona la exclusión mutua y evita el interbloqueo, el aplazamiento indefinido o la sincronización de bloqueo.
CPP
Main()
{
// to denote which thread will enter next
int favouredthread = 1;
// flags to indicate if each thread is in
// queue to enter its critical section
boolean thread1wantstoenter = false;
boolean thread2wantstoenter = false;
startThreads();
}
Thread1()
{
do {
thread1wantstoenter = true;
// entry section
// wait until thread2 wants to enter
// its critical section
while (thread2wantstoenter == true) {
// if 2nd thread is more favored
if (favaouredthread == 2) {
// gives access to other thread
thread1wantstoenter = false;
// wait until this thread is favored
while (favouredthread == 2)
;
thread1wantstoenter = true;
}
}
// critical section
// favor the 2nd thread
favouredthread = 2;
// exit section
// indicate thread1 has completed
// its critical section
thread1wantstoenter = false;
// remainder section
} while (completed == false)
}
Thread2()
{
do {
thread2wantstoenter = true;
// entry section
// wait until thread1 wants to enter
// its critical section
while (thread1wantstoenter == true) {
// if 1st thread is more favored
if (favaouredthread == 1) {
// gives access to other thread
thread2wantstoenter = false;
// wait until this thread is favored
while (favouredthread == 1)
;
thread2wantstoenter = true;
}
}
// critical section
// favour the 1st thread
favouredthread = 1;
// exit section
// indicate thread2 has completed
// its critical section
thread2wantstoenter = false;
// remainder section
} while (completed == false)
}
Python3
if __name__ == '__main__': # to denote which thread will enter next favouredthread = 1 # flags to indicate if each thread is in # queue to enter its critical section thread1wantstoenter = False thread2wantstoenter = False startThreads() def Thread1(): doWhile=False while (completed == False or not doWhile) : doWhile=True thread1wantstoenter = True # entry section # wait until thread2 wants to enter # its critical section while (thread2wantstoenter == True) : # if 2nd thread is more favored if (favaouredthread == 2) : # gives access to other thread thread1wantstoenter = False # wait until this thread is favored while (favouredthread == 2): pass thread1wantstoenter = True # critical section # favor the 2nd thread favouredthread = 2 # exit section # indicate thread1 has completed # its critical section thread1wantstoenter = False # remainder section def Thread2(): doWhile=False while (completed == False or not doWhile) : doWhile=True thread2wantstoenter = True # entry section # wait until thread1 wants to enter # its critical section while (thread1wantstoenter == True) : # if 1st thread is more favored if (favaouredthread == 1) : # gives access to other thread thread2wantstoenter = False # wait until this thread is favored while (favouredthread == 1): pass thread2wantstoenter = True # critical section # favour the 1st thread favouredthread = 1 # exit section # indicate thread2 has completed # its critical section thread2wantstoenter = False # remainder section
Esta versión garantiza una solución completa al problema de solución crítica.
Referencias – Algoritmo de Dekker
-csisdmz.ul.ie Algoritmo de
Dekker – Wikipedia
Publicación traducida automáticamente
Artículo escrito por Sudarshan Khasnis y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA