Diferencia entre revisiones de «Semáforos»

De Wiki de Sistemas Operativos
Saltar a: navegación, buscar
m (Semáforos)
 
(No se muestran 31 ediciones intermedias de 12 usuarios)
Línea 1: Línea 1:
 
= Planificador de procesos: Diagrama de estados simplicado =
 
= Planificador de procesos: Diagrama de estados simplicado =
  
Para comprender apropiadamente cómo funcionan los semáforos vamos a recordar el diagrama de estados simplificado que emplea el planificador de procesos del sistema operativo.
+
Para comprender apropiadamente cómo funcionan los semáforos es importante recordar cómo funciona el [[Estados de los procesos|diagrama de estados de los procesos]]
 
 
                          |---------------|
 
  pendiente              |              |              recibido
 
    evento      ---------> |  bloqueado  |-----------    evento
 
    externo    |          |              |          |    externo
 
                |          |---------------|          |
 
                |                                    |
 
                |            planificador          \/
 
        |--------------|      retira CPU    |---------------|
 
        |              | -------------------> |              |
 
        |    activo    |                      |  preparado  |
 
        |              | <------------------- |              |
 
        |--------------|                      |---------------|
 
                            planificador
 
                              asigna CPU
 
 
 
La vida de un proceso pasa por tres estados:
 
 
 
* Activo: el proceso está empleando la CPU, por tanto, está ejecutandose. Hay tantos procesos activos como recurso de procesamiento disponible. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
 
* Preparado: el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
 
* Bloqueado: el proceso está pendiente de un evento externo, tales como la espera de finalización de un proceso hijo, una señal, una operación sobre un semáforo o una operación de lectura/escritura.
 
 
 
La transición de activo a preparado y viceversa depende de decisiones tomadas por el planificador del sistema operativo (que emplea algún criterio visto en clases teóricas, tales como el turno rotatorio), el programador no puede interferir en estas decisiones. Mientras que la transición de activo a bloqueado, y de bloqueado a preparado pueden ser controladas por el programador mediante llamadas al sistema.
 
  
 
= Semáforos =
 
= Semáforos =
  
Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra]. Los semáforos nos permiten '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que nos permiten sincronizar la ejecución de dos o más procesos.
+
Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra] en 1965. Los semáforos permiten al programador '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que permiten sincronizar la ejecución de dos o más procesos. A diferencia de los [[cerrojos]], los semáforos nos ofrecen un mecanismo de espera no ocupada.
  
 
Los semáforos son un tipo de datos que están compuestos por dos atributos:
 
Los semáforos son un tipo de datos que están compuestos por dos atributos:
  
 
* Un contador, que siempre vale >= 0.
 
* Un contador, que siempre vale >= 0.
* Una lista de procesos, inicialmente vacía.
+
* Una cola de procesos inicialmente vacía.
  
 
+
Y disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:
Los semáforos disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:
 
  
 
<source lang="c">
 
<source lang="c">
Línea 42: Línea 18:
 
{
 
{
 
       si s.contador == 0:
 
       si s.contador == 0:
 +
              añade proceso a s.cola_procesos
 
               proceso a estado bloqueado
 
               proceso a estado bloqueado
              añade proceso a s.lista
 
 
       sino:
 
       sino:
 
               s.contador--
 
               s.contador--
Línea 49: Línea 25:
 
</source>
 
</source>
  
Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.
+
Nótese que siempre que queramos forzar una transición de un proceso ha estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.
  
 
<source lang="c">
 
<source lang="c">
 
up(semáforo s)
 
up(semáforo s)
 
{
 
{
       si hay procesos en s.lista
+
       si hay procesos en s.cola_procesos:
               retira proceso de s.lista
+
               retira proceso de s.cola_procesos
 
               proceso a estado preparado
 
               proceso a estado preparado
 
       sino:
 
       sino:
Línea 62: Línea 38:
 
</source>
 
</source>
  
Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.
+
Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su cola resulta en que se retire uno de los procesos (el primero de la cola, es decir, el que lleva más tiempo en la cola), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la cola pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.
 +
 
 +
Además, se disponen de un constructor y un destructor que permiten la creación y la liberación de un semáforo.
 +
 
 +
=== Ejemplo de uso de semáforos ===
 +
 
 +
Suponga el siguiente ejemplo en el que se quieren sincronizar dos hilos de un proceso, de manera que se dé la siguiente secuencia de ejecución: A, B, A, B, ... y así sucesivamente. El siguiente código resolvería el problema:
 +
 
 +
<source lang="c">
 +
semaforo a = semaforo.create(1);
 +
semaforo b = semaforo.create(0);
 +
 
 +
/* código del hilo A */
 +
while (1) {
 +
      a.down();
 +
      printf("hilo A\n");
 +
      b.up();
 +
}
 +
 
 +
/* código del hilo B */
 +
while (1) {
 +
      b.down();
 +
      printf("hilo B\n");
 +
      a.up();
 +
}
 +
</source>
 +
 
 +
=== Tipos de semáforos ===
 +
 
 +
Dependiendo de la función que cumple el semáforo, vamos a diferenciar los siguientes tipos:
  
Los semáforos son un mecanismo de esperas no ocupadas, lo que significa que permite sincronizar a los procesos de forma que no se desperdician recursos de CPU cuando un cierto no proceso no tiene actividad a realizar (la espera ocupada, también conocida como espera activa, es en la que se queda comprobando la condición hasta verificarla).
+
* Semáforo de exclusión mutua, inicialmente su contador vale 1 y permite que haya un único proceso simultáneamente dentro de la sección crítica.
 +
* Semáforo contador, permiten llevar la cuenta del número de unidades de recurso compartido disponible, que va desde 0 hasta N.
 +
* Semáforo de espera, generalmente se emplea para forzar que un proceso pase a estado bloqueado hasta que se cumpla la condición que le permite ejecutarse. Por lo general, el contador vale 0 inicialmente, no obstante, podría tener un valor distinto de cero.
  
 +
=== Ventajas e inconvenientes ===
  
'''Granularidad''': número de recursos controlados por un semáforo
+
La principal ventaja de los semáforos frente a los [[cerrojos]] es que permiten sincronizar dos o más procesos de manera que no se desperdician recursos de CPU realizando comprobaciones continuadas de la condición que permite progresar al proceso.
  
'''Problemas''': El uso de semáforos también tiene algunos inconvenientes, entre los que destacan:
+
Los inconvenientes asociados al uso de semáforos son los siguientes:
  
* Facilidad para emplearlos incorrectamente.
+
* Los programadores tienden a usarlos incorrectamente, de manera que no resuelven de manera adecuada el problema de concurrencia o dan lugar a interbloqueos.
* Son independientes del lenguaje de programación, y por tanto no hay comprobación ninguna en tiempo de compilación.
+
* No hay nada que obligue a los programadores a usarlos.
* No hay nada que obligue a usarlos.
+
* Los compiladores no ofrecen ningún mecanismo de comprobación sobre el correcto uso de los semáforos.
* Son independientes del recurso compartido al que intentan regular.
+
* Son independientes del recurso compartido al que se asocian.
  
 +
Debido a estos inconvenientes, se desarrollaron los [[Monitores|monitores]].
  
 +
=== Granularidad ===
 +
Número de recursos controlados por cada semáforo. Hay de dos tipos:
 +
* Granularidad fina: Un recurso por semáforo. Hay un mayor grado de paralelismo, lo que puede mejorar la rapidez de ejecución de la protección. Aunque a mayor número de semáforos existe una mayor probabilidad de que se dé un interbloqueo entre semáforos, que no sería una mejora de lo que intentamos evitar.
 +
* Granularidad gruesa: Un semáforo para todos los recursos. Caso totalmente inverso al anterior: Ahora al tener un semáforo no se produce interbloqueo entre ellos, aunque los tiempos de ejecución son excesivamente largos.
  
'''Ejemplo productor-consumidor''': Supongamos un proceso que produce y otro que consume lo producido. Lo deseable es que el productor actúe primero, y no más de 1 vez consecutiva, puesto que el consumidor consume de 1 en 1.
 
  
{|cellpadding="4"
+
5.6[[Monitores | Monitores]]
!style="border-style: solid; border-width: 0 1px 1px 1px"|Inicializacion
 
!style="border-style: solid; border-width: 0 1px 1px 0"|Productor
 
!style="border-style: solid; border-width: 0 1px 1px 0"|Consumidor
 
|-
 
|width="200"|semaforo prod,cons;
 
|width="90"|while(1){
 
|width="90"|while(1){
 
|-
 
|semaforo_create(cons,0);
 
|align="center"| down (prod);
 
|align="center"| down (cons);
 
|-
 
|semaforo_create(prod,1);
 
|align="center"| produce();
 
|align="center"| consume();
 
|-
 
|
 
|align="center"| up(cons);
 
|align="center"| up(prod);
 
|-
 
|
 
| }
 
| }
 
|}
 

Revisión actual del 17:30 2 abr 2020

Planificador de procesos: Diagrama de estados simplicado

Para comprender apropiadamente cómo funcionan los semáforos es importante recordar cómo funciona el diagrama de estados de los procesos

Semáforos

Los semáforos son un mecanismo de sincronización de procesos inventados por Edsger Dijkstra en 1965. Los semáforos permiten al programador asistir al planificador del sistema operativo en su toma de decisiones de manera que permiten sincronizar la ejecución de dos o más procesos. A diferencia de los cerrojos, los semáforos nos ofrecen un mecanismo de espera no ocupada.

Los semáforos son un tipo de datos que están compuestos por dos atributos:

  • Un contador, que siempre vale >= 0.
  • Una cola de procesos inicialmente vacía.

Y disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:

down(semáforo s)
{
       si s.contador == 0:
              añade proceso a s.cola_procesos
              proceso a estado bloqueado
       sino:
              s.contador--
}

Nótese que siempre que queramos forzar una transición de un proceso ha estado bloqueado, tenemos que hacer que dicho proceso realice una operación down sobre un semáforo cuyo contador vale cero.

up(semáforo s)
{
       si hay procesos en s.cola_procesos:
              retira proceso de s.cola_procesos
              proceso a estado preparado
       sino:
              s.contador++
}

Nótese que una operación up sobre un semáforo en el que hay procesos en su cola resulta en que se retire uno de los procesos (el primero de la cola, es decir, el que lleva más tiempo en la cola), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación up resulte en que el proceso retirado de la cola pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.

Además, se disponen de un constructor y un destructor que permiten la creación y la liberación de un semáforo.

Ejemplo de uso de semáforos

Suponga el siguiente ejemplo en el que se quieren sincronizar dos hilos de un proceso, de manera que se dé la siguiente secuencia de ejecución: A, B, A, B, ... y así sucesivamente. El siguiente código resolvería el problema:

semaforo a = semaforo.create(1);
semaforo b = semaforo.create(0);

/* código del hilo A */
while (1) {
       a.down();
       printf("hilo A\n");
       b.up();
}

/* código del hilo B */
while (1) {
       b.down();
       printf("hilo B\n");
       a.up();
}

Tipos de semáforos

Dependiendo de la función que cumple el semáforo, vamos a diferenciar los siguientes tipos:

  • Semáforo de exclusión mutua, inicialmente su contador vale 1 y permite que haya un único proceso simultáneamente dentro de la sección crítica.
  • Semáforo contador, permiten llevar la cuenta del número de unidades de recurso compartido disponible, que va desde 0 hasta N.
  • Semáforo de espera, generalmente se emplea para forzar que un proceso pase a estado bloqueado hasta que se cumpla la condición que le permite ejecutarse. Por lo general, el contador vale 0 inicialmente, no obstante, podría tener un valor distinto de cero.

Ventajas e inconvenientes

La principal ventaja de los semáforos frente a los cerrojos es que permiten sincronizar dos o más procesos de manera que no se desperdician recursos de CPU realizando comprobaciones continuadas de la condición que permite progresar al proceso.

Los inconvenientes asociados al uso de semáforos son los siguientes:

  • Los programadores tienden a usarlos incorrectamente, de manera que no resuelven de manera adecuada el problema de concurrencia o dan lugar a interbloqueos.
  • No hay nada que obligue a los programadores a usarlos.
  • Los compiladores no ofrecen ningún mecanismo de comprobación sobre el correcto uso de los semáforos.
  • Son independientes del recurso compartido al que se asocian.

Debido a estos inconvenientes, se desarrollaron los monitores.

Granularidad

Número de recursos controlados por cada semáforo. Hay de dos tipos:

  • Granularidad fina: Un recurso por semáforo. Hay un mayor grado de paralelismo, lo que puede mejorar la rapidez de ejecución de la protección. Aunque a mayor número de semáforos existe una mayor probabilidad de que se dé un interbloqueo entre semáforos, que no sería una mejora de lo que intentamos evitar.
  • Granularidad gruesa: Un semáforo para todos los recursos. Caso totalmente inverso al anterior: Ahora al tener un semáforo no se produce interbloqueo entre ellos, aunque los tiempos de ejecución son excesivamente largos.


5.6 Monitores