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:

   Si el orden de llegada es el mismo, n(1)=n(2), ¿qué ocurre?¿cuál de los dos procesos entra en su sección crítica ?
   En este caso habría que comparar el pdi ( nº de identificador del proceso ).
El orden quedaría determinado así, de forma que entraría en su sección crítica el que tuviera mayor pdi.
   Este posible problema no se da , puesto que un proceso, al coger número, cede la entrada al otro proceso, de forma que no pueden tener nunca el mismo valor y al salir de su sección crítica, pone su n(i)=0; esto quiere decir que no ha cogido número y, por tanto, no tiene opción de entrar en su sección crítica.
   Sincronización y comunicación entre los procesos:

   Si se cambia el número de iteraciones que se repite cada proceso, tenemos que cuanto menor sea el número (considerando como pequeño menos de 50 iteraciones), la comunicación entre los procesos disminuye en gran medida, es decir, la ejecución de los procesos no se va "intercalando", sino que un proceso realiza todo su trabajo y cuando finaliza, el otro proceso se ejecuta después.

   Para resolver este problema podemos hacer crecer el número de iteraciones o aumentar el tiempo de ejecución de los procesos incluyendo tiempos de retardo ya sea en la sección crítica (función incrementa) o en el resto. Así conseguimos que al aumentar el tiempo de ejecución de un proceso el otro proceso pueda entrar en su sección crítica.

(Volver)

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.

(Volver)

AUTORES:

Mª Victoria Córdoba Alvarez.

Marcos Valtuille Fernández.