1. En que consiste el algoritmo de Peterson y generalización para N procesos.
2. El problema de la sección crítica.
3. El programa.
4. La documentación.
6. Autores
Ilustramos aquí en que consiste el algoritmo de Perterson para dos procesos y el correspondiente algoritmo para N procesos es una generalización del mismo.
Utilizamos las siguientes variables:
c[i], que es un array y turno, que solo puede valer 1o 2.
Inicialmente, c[0]=c[1]= falso, y el valor de turno no tiene relevancia (pero de be ser 0 o 1). Para entrar en la seccion crítica, el proceso Pi primero asigna el valor verdadero a c[i] y luego afirma que es el turno del otro proceso para entrar si así lo desea (turno = j). Si ambos procesos tratan de entrar a la vez, se asignará turno como i y j aproximadamente al mismo tiempo. Sólo una de estas asignaciones durará; la otra ocurrirá, pero será reemplazada de inmediato. El valor eventual de turno decide a cuál de los dos procesos se le permitirá entrar primero en su sección crítica.
En el algoritmo para N procesos las variables c[i] además de valer "verdadero" y "falso", pueden valer "en sección critica" y turno desde 1 hasta N. El procedimiento es una generalización de este.
Consideremos un sistema compuesto por Nprocesos. Cada proceso tiene un segmento de código, llamado sección crítica, en el cual el proceso puede estar modificando variables comunes, actualizando una tabla, escribiendo en un archivo, etc. Cuando un proceso se ejecuta en su sección crítica, no se permite que ningún otro proceso se ejecute en su sección. De esta manera, la ejecución de las seciones críticas de los procesos es mutuamente excluyente en el tiempo. El problema de la sección crítica consiste en diseñar un protocolo que los procesos puedan usar para cooperar. Cada proceso debe solicitar permiso para entrar en su sección crítica; la seccion de código que implanta esta solicitud es la sección de entrada. A la sección crítica puede seguir una sección de salida y el código que queda es la sección restante.
Una solución al problema de la sección crítica debe cumplir los tres requisitos siguientes:
1. Exclusión mutua: si un proceso se está ejecutando en su seccion crítica, entonces nigún otro proceso se puede estar ejecutando en la suya.
2. Progreso: si nigún proceso se está ejecutando en su sección crítica y hay otros procesos que desean entrar en las suyas, entonces solo aqulos procesos que no se están ejecutando en su sección restante pueden participar en la decisión de cual será el siguiente en entrar en la sección crítica, y esta decisión no puede postergarse indefinidamente.
3. Espera limitada: debe haber un límite en el número de veces que se permite que los demás procesos entren en su sección crítica después de que un proseso haya efectuado una solicitud para entrar en la suya y antes de que se concada esa solicitud.
Para ver que la demostración de este algoritmo es correcto pinchar aquí:
Para demostrar es propiedad obserbamos que cada Pi entra en su sección crítica únicamente si c[j]!= "en seción crítica" para toda j!=i. Como sólo Pi puede asignar c[i]="en seción crítica", y puesto que Pi examina c[j] sólo cuando c[i]="en sección crítica", se obtiene el resultado.
Para demostar esta propiedad observamos que el valor de turno solo puede modificarse cuando un proceso entra en su sección crítica y cuando sale de ella. Por tanto si ningún proceso se está ejecutando en su sección crítica o saliendo de ella, el valor de turno permanece constante. El primer proceso en contienda en la ordenación cíclica (turno,turno+1, .....,n-1,0...,turno-1) entrará en al sección crítica.
Para demostrar esta propiedad observamos que, cuando un proceso sale de la sección crítica, debe designar como su únicio sucesor al primer proceso contendiente en la ordenación cíclica turno+1, .....,n-1,0...,turno-1,turno, asegurando que cualquier proceso que quira entrar en su sección critica lo hará dentro de n-1 turnos como máximo.
Programa que implementa el Algoritmo de Peterson para N procesos.
Nos permite asimilar la concurrencia de procesos.
Los N procesos comparten una zona de memoria, por lo que hay que tener cuidado de no coincidir en su petición. La solución de este problema se hace con variables de cierre, que nos indican la intención de cada proceso en querer entrar en su sección crítica, y con otra variable indicadora de quien tiene el turno de entrada. Los procesos van cediendose el turno, una vez que hayan ejecutado sus instrucciones, esperando mientras otro proceso quiera entrar a su sección crítica y tenga el turno correspondiente.
El número de iteraciones para los procesos y el nombre de fichero de salida de los resultados se dan como argumentos por línea de comandos.
El número de procesos "Nproc" se define como un macro(define) al principio del programa.
Para el desarrollo correcto del programa necesitamos el fichero "rshmem.c" .
Por linea de comandos se pasará el nombre del fichero de salida de los resultados.
El uso de memoria alineada trae problemas. Por eso hay que utilizar direcciones de memoria impares.
crearMemoria()
eliminarMemoria()
fork()
Raúl Mateo Junquera
Begoña Mª Benito Garcia
Funcuones que se utilizan:
void incrementa(int *mem, int k)
mem -> Puntero a entero, dirección de la memoria compartida.
k -> Entero, incremento de la memoria.
1. Asigna la direccion de la memoria compartida a un entero.
2. Incrementa el entero.
3. Devuelve la posicion de memoria incrementada.
Hace uso de TP, un retardo aleatorio que alarga el tiempo de los calculos.