Algoritmo de Peterson

Docente: Mario Gauna Chino

UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN

Primeras aproximaciones a la solución de los problemas de la programación concurrente

El A.D. resuelve el problema de la E.M. para dos procesos pero con un programa complejo, difícil se seguir y de probar sus correcciones. G.L. Peterson descubrió una forma mas sencilla y elegante de resolver le mencionado problema dando lugar al algoritmo de Peterson.

process Po repeat Co=quiereentrar; turno=1; while (C1=quiereentrar) and (turno=1) do Sección Critica Co=restoproceso; resto0 forever

process P1 repeat C1=quiereentrar; turno=0; while (C0=quiereentrar) and (turno=0) do Sección Critica C1=restoproceso; resto1 forever

Primeras aproximaciones a la solución de los problemas de la programación concurrente

Las V. compartidas por los procesos son las mismas que el algoritmo anterior, cada proceso dispone su propia variable, a través de la cual indica su estado con respecto a la sección critica.

Cuando esta variable tiene el valor quiereentrar significa que el proceso correspondiente esta dentro o desea entrar en su sección critica. Cuando vale restoproceso el proceso no esta ni quiere entrar en su sección critica. Por otra parte la variable turno resuelve conflictos de simultaniedad.

• C0=restoproceso, C1=restoproceso

• Turno= 0 ó 1 ( es indiferente) Se verifica la Exclusión mutua: pues si Pi está en la

S.C. se cumple q’ Ci=quiereentrar por la primera asignacion Pi no ha podido pasar del while mas extremo.

verifica la Condición Proceso de Ejecución: ya que cuando un proceso quiere acceder a u sección critica entra si Pj no quiere entrar y si Pj quiere entrar entra el primero que dio paso al otro a traves de la signacion a la variable turno.

la espera es limitada: pues cuando Pi sale de la S.C. pone su indicador Ci=restoproceso y Pj podra entrar.

Algoritmo Incorrecto de Hyman

Algoritmo Incorrecto de Hyman

• Encontrar un solución de software al problema de exclusión mutua ha sido un desafío

• Las V. globales C0, C1 y turno deben inicializarse de la Sgte. Manera. • C0 y C1 son inicializadas a restoproceso.

• Turno es inicializada a 0 ó 1 (es indiferente)

Algoritmo Incorrecto de Hyman

• A primera vista el algoritmo parece correcto, sin embargo se puede dar la sgte. situación.

1. turno = 0 P1 hace C1 0 quiereentrar y encuentra C0 =restoproceso superando la sentencia 1.3 y se para.

2. A continuación Po hace C1=quiereentrar, encuentra turno=0 y entra en la seccion critica.

3. P1 hace turno=1 y entra también en la S.C.