Problema sección crítica y posibles soluciones

De Departamento de Informatica
Saltar a: navegación, buscar

"La sección crítica es la parte que debe protegerse de interferencias de otros procesos. También se define como a la porción de código de un programa de computador el cual accede a un recurso compartido (estructura de datos o dispositivo) que no debe de ser accedido por más de un hilo en ejecución (thread). La sección crítica por lo general termina en un tiempo determinado y el hilo, proceso o tarea solo tendrá que esperar un período determinado de tiempo para entrar."[1]

Contenido

El problema

Estructura general de un proceso representativo Pi.

El problema de la sección crítica es la consecuencia del uso óptimo de la CPU al ejecutar procesos concurrentes, esto es, la multiprogramación.

Se necesita de un mecanismo de sincronización en la entrada y salida de la sección crítica para asegurar la utilización exclusiva del recurso. El no tener un control por sobre esta sección puede conllevar a inconsistencias y/o corrupción de datos (contenidos en variables) compartidos por un conjunto de procesos.

El problema de la sección crítica es uno de los problemas que con mayor frecuencia aparece cuando se ejecutan procesos concurrentes (o también en programación con multithread donde los hilos deben llevar a cabo una sincronización para procesar datos en el orden correcto, y aprovecha la característica de multiprocesamiento de computadoras que tienen multicores).

Para entender un poco mejor el concepto se presenta el siguiente ejemplo: Se tiene un Sistema Operativo que debe asignar un identificador de proceso (PID) a dos procesos en un sistema multicore. Cuando el SO realiza esta acción en dos procesadores de forma simultánea sin ningún tipo de control, se pueden producir errores, ya que se puede asignar el mismo PID a dos procesos distintos. Este problema se debe a que constituyen una sección crítica que debe ejecutarse en forma atómica, es decir, de forma completa e indivisible y ningún otro proceso podrá ejecutar dicho código mientras el primero no haya acabado su sección.

Soluciones

Entonces es necesario diseñar un protocolo que los procesos puedan usar, y los requisitos que éste tiene son los siguientes:

  1. Mutua exclusión: Si un proceso se ejecuta en su sección crítica entonces ningún otro proceso puede estar en su sección crítica.
  2. Progreso: Si no hay procesos en su sección crítica y hay procesos que quieren ingresar se tiene que sólo aquellos que estén en su sección restante puede participar de la decisión de qué proceso ingresa.
  3. Espera limitada: Existe un límite para permitir que otros procesos ingresen en sus zonas críticas.

Para 2 procesos

Por simplicidad primero nos centraremos en resolver este problema para 2 procesos llamados P0 y P1:

Algoritmo 1

Algoritmo 1

La solución radica en que ambos procesos compartan una variable, la que si toma el valor de uno entonces P1 se ejecuta en la zona crítica y así se asegura que solamente un proceso a la vez puede estar en su zona crítica. Sin embargo no se resuelve el requisito de progreso.

Algoritmo 2

Algoritmo 2

Recordar la información suficiente de los procesos que ingresan en su sección crítica, lo que se soluciona cambiando la variable que se crea en Algoritmo 1 por un arreglo:

var indicador: array[0...1] of boolean;

El valor inicial es falso, mientras que si su indicador [i] es igual a true entonces Pi está listo para entrar a la sección crítica. Con este algoritmo no se logran satisfacer todos los requisitos enunciados anteriormente.

Algoritmo 3

Algoritmo 3

Solución que combina las dos variables compartidas de los algoritmos anteriores, satisface los 3 requisitos y resuelve el problema de Sección Crítica para dos procesos

Para n procesos

Algoritmo de la Panadería

Algoritmo Panadería

Antes de entrar en su Sección Crítica, el proceso recibe un número de ticket. Entra en la Sección Crítica el proceso con menor número de ticket.

Si Pi y Pj, con i < j reciben el mismo número, entonces Pi es servido primero.

El esquema de numeración siempre genera números en orden creciente de enumeración.

Declaración de variables:

  var elec: array[0..n-1] of boolean
  num: array[0..n-1] of integer

Valores iniciales:

  elec[i]:= false, i=0,1,...,n-1
  num[i]:= 0, i=0,1,...,n-1

Otros problemas de Sincronización

Además del problema de sección crítica, es posible encontrar otro tipos de problemas de control de concurrencia en la sincronización de procesos. Los problemas como sección crítica y los que se mencionan a continuación son usados actualmente para poner a prueba todos los nuevos esquemas de sincronización propuestos.

Problema de los lectores-escritores

El problema trata de dos perfiles de procesos que interactúan simultáneamente, es decir, imaginando una Base de Datos donde se tiene un proceso que desea leer los datos y otro proceso que desea actualizar los datos, a los cuales le llamaremos lector y escritor. Si los lectores acceden simultáneamente no habrá problema alguna, pero el problema surge cuando quiere interactuar con la base de datos el lector y escritor al mismo tiempo, generando así el problema.

Para asegurar que no ocurra este tipo de problemas, se debe asegurar que los procesos escritores tengan acceso exclusivo a la base de datos.

Problema de los 5 filósofos

Problema de los 5 filósofos

El problema de los filósofos es una representación sencilla de la necesidad de repartir varios recursos entre varios procesos de una forma que no se produzcan interbloqueos ni bloqueos indefinidos.

Se consideran cinco filósofos en una mesa redonda, donde existe un solo plato de arroz al medio de la mesa, luego entre cada par de filósofos hay 1 solo palillo, teniendo un total de 5 palillos en la mesa (Al igual que la cantidad de filósofos). El problema surge cuando un filósofo quiere comenzar a comer, el cual toma los 2 palillos entre el y los filósofos de la izquierda y derecha. Los demás filósofos no podrán comer, ya que, un filosofo no tomará un palillo que está ocupado por otro. Ergo, no pueden existir dos filósofos contiguos comiendo arroz.

Referencias

Bibliografía Utilizada

“Fundamentos de Sistemas Operativos”, Silberschatz, Galvin, Gagne, Séptima Edición, 2005.

http://lsi.ugr.es/~jagomez/index_archivos/3SincronizacionComm.pdf

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas