PRÁCTICA DE SISTEMAS OPERATIVOS
ALGORITMO DE LA PANADERÍA
En esta página veremos un ejemplo de cómo se pueden implementar dos procesos que comparten una zona de memoria común ( memoria compartida ).
Este algoritmo de espera activa, soluciona el problema de acceso concurrente.
PLANTEAMIENTO
DEL PROBLEMA
|
Tenemos dos procesos, padre e hijo,
que comparten un mismo recurso (una zona de memoria).
El valor inicial de esta variable es 0, el cual es incrementado
por el proceso padre y decrementado por el proceso hijo un mismo número
de veces ( número finito ), de forma que su valor final será
igualmente 0.
Cada proceso posee además
otras dos variables: c(i) y n(i), i=1,2 sobre las que puede leer y escribir,
pero únicamente puede leer las del otro proceso.
Las variables
enteras n(i) representan el orden de llegada a la sección crítica
( menor valor indica mayor preferencia en la entrada ).
Las variables c(i), llamadas variables de cerradura,
son variables booleanas que toman los valores T o F indicando la intención
de cada proceso de entrar en su sección crítica, la cual
es la función incrementa.
(Volver)
PROGRAMA
|
El programa que hemos implementado es el siguiente:
_________________________________________________________________________________________
#include "rshmem.h"
void incrementa (int *mem, int k){
int i;
i = *mem;
i = i+k;
TP
TP TP TP
*mem = i;
}
int main () {
int * recurso; /*
Puntero al inicio de la zona de memoria compartida
*/
char * marcaFin;
/* Puntero al símbolo que nos indica si ha finalizado el hijo: 'x'
o no: 'p'*/
int *n1;
/* Orden del llegada del proceso padre a la sección
crítica
*/
int *n2; /*
Orden del llegada del proceso hijo a la sección crítica */
char *c1; /*
Variable de cerradura del proceso padre */
char *c2;
/* Variable de cerradura del proceso hijo */
/* Crear zona de memoria compartida */
if ( !crearMemoria ())
fprintf (stderr,
"Error de crear memoria\n");
recurso = (int *) memoria;
n1 = (int *) recurso + sizeof (int);
n2 = (int *) n1 + sizeof (int);
marcaFin = (char *) n2 + sizeof (int);
c1 = (char *) marcaFin + sizeof (char);
c2 = (char *) c1 + sizeof (char);
* marcaFin = 'p';
* n1 = 0;
* n2 = 0;
* c1 = 'T';
* c2 = 'T';
/* proceso padre */
if ( 0!= fork ()) {
int i; /* Variable
contador de iteraciones
*/
for
( i=0; i< 1000; i++) {
TP
TP TP /*
Tiempos de retardo */
/*
Sección de entrada*/
*c1
= 'F'; /*
Quiere coger numero
*/
*n1
= (*n2) +1;
/* Coge numero
*/
*c1
= 'T';
/* Se pone a la cola
*/
while
( *c2 != 'T');
/* Espera a que el otro proceso coja número*/
while
( *n2 !=0 && *n2 < *n1); /* Espera hasta
que sea su turno */
/*Sección
crítica */
incrementa
( recurso , 5);
/*
Sección de salida */
TP
TP TP /*
Tiempos de retardo */
*n1
=0;
}
while
( *marcaFin != 'x');
/* Espera al hijo si no ha acabado */
printf
("El recurso valia 0 y ahora vale %d \n", *recurso );
/* eliminar memoria compartida */
if
( !eliminarMemoria () )
fprintf
(stderr, "\nError en eliminar memoria \n");
exit
(0);
} else {
/*
proceso hijo */
int i;
/* Variable
contador de iteraciones
*/
for
( i=0; i<1000; i++) {
TP
TP TP /*
Tiempos de retardo */
*c2
= 'F'; /*
Quiere coger numero
*/
*n2
= (*n1) +1; /*
Coge numero
*/
*c2
= 'T'; /*
Se pone a la cola
*/
while
( *c1!= 'T'); /*
Espera a que el otro proceso coja número*/
while
( *n1!=0 && *n1 < *n2 );/* Espera hasta que sea su
turno */
/*seccion
Critica* /
incrementa(
recurso, -5);
/*
Sección de salida */
TP
TP TP
/*
Tiempos de retardo */
*n2
= 0;
}
*
marcaFin = 'x'; /*
El hijo ha acabado */
exit
(0);
} /* fin fork */
} /* fin main */
(Volver)____________________________________________________________________________________________
¿Cuando un proceso entra en la seccion critica?
Debemos hacer notar que para que un proceso pueda entrar en su sección critica , es necesario que se cumpla:
-Que su c(i) sea T
-Que la c(j) del otro proceso sea T
-Que su n(i) sea estrictamente mayor que 0 y menor que el n(i) del otro proceso.
(Volver al a 1ª
Sección Critica)
(Volver al a 2ª Sección Critica)
POSIBLES PROBLEMAS
|
Existen varios posibles problemas que podrían darse en este algoritmo:
ESTUDIO
DEL TIEMPO
|
Hemos realizado un estudio sobre
los tiempos de ejecución del programa al variar el numero de iteraciones
de los procesos, obteniendo el siguiebte grafico, donde la linea azul es
el tiempo real y la rosa es el tiempo de ejecución de CPU de los
procesos.
Se observa que a medida que crece el numero de iteraciones crecen los tiempos, cosa que es evidente; también observamos que a medida que aumentan las iteraciones las curvas de tiempo real y tiempo de CPU se separan más, esto es debido a que no siguen el mismo ritmo de crecimiento.
Podemos concluir afirmando que cuando los procesos son de larga duración la CPU los interrumpe para dar paso a otros procesos y es por esto por lo que el tiempo real difiere del tiempo de CPU de manera mas clara a mayor numero de iteraciones.
AUTORES:
Mª Victoria Córdoba Alvarez.
Marcos Valtuille Fernández.