Comunicación y sincronización

## Página 61

<!-- source-page: 61 -->

GNUFDL • PID_00214803                                                                                  61                                                                                         Comunicación y sincronización

Anexo







1.￿El￿soporte￿de￿hardware￿para￿la￿exclusión￿mutua


Hemos visto que la sincronización es necesaria para conseguir que el acceso
a la sección crítica en exclusión mutua se lleve a cabo de manera correcta.
También hemos visto que los semáforos son una herramienta bastante fácil
de utilizar que soluciona el problema de la sincronización de manera elegante
para cualquier número de procesos. Ahora bien, para implementar los semá-
foros es necesario asegurar la indivisibilidad en la ejecución del código de las
operaciones sem_wait y sem_signal.


A continuación, presentamos soluciones de hardware para ejecutar el código
de manera indivisible. Indirectamente ello nos permite la implementación de
los semáforos.


1.1.￿Modo￿de￿ejecución￿privilegiado:￿la￿inhibición￿de￿las￿interrupciones


En la mayoría de los ordenadores hay instrucciones del lenguaje máquina que
dan la posibilidad de inhibir (deshabilitar) y desinhibir (habilitar) las interrup-
ciones. Con estas instrucciones, la implementación de la exclusión mutua es
trivial.


Hemos visto que el problema de la exclusión mutua en general radica en la
desasignación del procesador a un proceso en ejecución cuando éste está mo-
dificando una variable compartida, ya que entonces la actualización de esta
variable queda a medio hacer. El procesador necesita el mecanismo de las in-
terrupciones para implementar la multiplexación de procesos. Si un proceso
desactiva las interrupciones, éste siempre tendrá asignado el procesador hasta
que las vuelva a activar.


Con este funcionamiento, se puede garantizar la exclusión mutua de una sec-
ción crítica mediante el esquema siguiente (figura 47).


    inhibir interrupciones    /* desactivar las interrupciones */

    sección crítica
    desinhibir interrupciones /* activar de nuevo las interrupciones */


Figura 47. Implementación de la entrada y salida de la exclusión mutua inhibiendo y desin-
hibiendo interrupciones

Estas instrucciones son muy peligrosas si se hace un uso indebido o malinten-
cionado de ellas. Podrían llevar al sistema fácilmente al caos al no permitir la
ejecución de ningún proceso. Por este motivo, interesa que estas instrucciones

## Página 62

<!-- source-page: 62 -->

GNUFDL • PID_00214803                                                                                  62                                                                                         Comunicación y sincronización

no estén al alcance de los programadores de aplicaciones. Lo más habitual es
que sean instrucciones privilegiadas del lenguaje máquina y puedan ser utili-
zadas únicamente por el sistema operativo.


En el caso de los semáforos, el sistema operativo puede utilizar estas instruc-
ciones para asegurar la indivisibilidad en la ejecución de las llamadas al siste-
ma sem_wait y sem_signal.


1.2.￿Modo￿de￿ejecución￿no￿privilegiado


A continuación se presentan dos instrucciones de lenguaje máquina no privi-
legiadas que pueden ser utilizadas para implementar el acceso en exclusión
mutua a una región crítica. Por lo tanto, estas instrucciones pueden ser utili-
zadas directamente por los programas de usuario.


1.2.1￿Test￿and￿set


La instrucción test and set está pensada para dar un soporte de hardware al
problema del acceso a la zona crítica en exclusión mutua. Está diseñada ex-
presamente para resolver conflictos de acceso a zonas críticas y asegurar que
tan sólo un proceso pueda acceder a la vez a la sección crítica.

La idea básica es definir una variable de control (global para todos los proce-                            (21)Recordad que la sección crítica
sos) asociada a la sección crítica21 que determine si el acceso es posible o no.                           es un trozo de código asociado a
                                                                                                           la utilización de un recurso com-
La variable se inicializa en libre e indica que el recurso compartido está dis-                            partido.
ponible. Cada proceso que quiere acceder al recurso ejecuta la instrucción test
and set (TS) y le pasa por parámetro la variable de control asociada al recurso.


Esta operación se escribe TS variable y funciona comparando el valor de la
variable con ocupado. Si está en libre, lo modifica a ocupado. Los bits de
condición (flags de estado del procesador) se modifican para indicar el estado
de la variable justo antes de ejecutar la operación TS.


Un semáforo binario que utilice espera activa podría implementar la operación
utilizando TS de la manera siguiente (figura 48 y figura 49):


    sem_wait: TS S
       BNF sem_wait
       return


Figura 48. Implementación de sem_wait utilizando test_and_set


    sem_signal: mov S, libre


Figura 49. Implementación de sem_signal utilizando test_and_set

## Página 63

<!-- source-page: 63 -->

GNUFDL • PID_00214803                                                                                  63                                                                                         Comunicación y sincronización

Supongamos que inicialmente S tiene el valor libre. Cuando el primer pro-
ceso ejecuta sem_wait sucede lo siguiente:


1) La instrucción TS S mira el estado de S, y como S está en libre lo pasa a
ocupado. La instrucción TS modifica los flags para indicar que S estaba libre.


2) La instrucción BNF (branch if not free) salta a la etiqueta sem_wait si el valor
de S estaba en ocupado. En nuestro caso, como está en libre no salta, el
proceso vuelve de la llamada sem_wait y, por lo tanto, se le asigna el recurso
compartido.


Si otros procesos quieren acceder al recurso, cuando ejecuten la operación
sem_wait sucederá lo siguiente:


1) La instrucción TS S mira el estado de S y, como S está en ocupado, no
se cambia la variable. La instrucción TS modifica los flags para indicar que S
estaba ocupado.


2) La instrucción BNF salta a la etiqueta sem_wait, ya que el valor de S estaba
en ocupado. De esta manera, todos los procesos se quedan ejecutando el bucle
sem_wait a la espera de que alguien libere el recurso compartido. Para liberar
el recurso compartido, lo único que se debe hacer es poner en libre el valor
de S. El código de la operación sem_signal que lo puede hacer es el que
mostramos en la figura 49.


Es importante señalar que el código de la instrucción sem_wait funciona por-
que la instrucción TS es indivisible o porque mientras el hardware ejecuta el
microcódigo asociado a esta instrucción las interrupciones están inhibidas.


1.2.2.￿El￿intercambio￿(swap)


La instrucción swap intercambia el contenido de dos palabras de memoria ató-
micamente y se define tal como se indica en la figura 50.


    swap (A,B){
       temp = A;

       EN = B;
       B = temp;
    }


Figura 50. Definición de la instrucción de lenguaje máquina swap

Si el lenguaje máquina ofrece una instrucción de intercambio (swap), enton-
ces la exclusión mutua se puede conseguir de la manera siguiente: definimos
una variable global a la que denominamos lock, que puede tomar los valores

## Página 64

<!-- source-page: 64 -->

GNUFDL • PID_00214803                                                                                  64                                                                                         Comunicación y sincronización

cierto o falso. La variable se inicializa en falso. Además, cada proceso tie-
ne una variable local denominada clave, que puede tomar los valores cierto
o falso.


Todo proceso que quiere acceder a una zona crítica en exclusión mutua debe
ejecutar el código de la figura 51.


    /* entrada sección crítica */

    clave = cierto;
    do {

       swap (lock, clave);
    } until (clave == falso);
    /* sección crítica */

    ...
    /* salida sección crítica */
    lock = falso;


Figura 51. Implementación de la entrada y la salida de la sección crítica utilizando la ins-
trucción

2.￿Ejemplo:￿procesos￿productores￿y￿consumidores



    En un sistema es habitual encontrar procesos con relaciones de produc-
    tor-consumidor. En general, un proceso￿productor genera información
    que será consumida (tratada/manipulada) por el proceso￿consumidor.



El problema que se quiere resolver se podría formular en los términos siguien-
tes: consideramos un grupo de procesos consumidores y productores que se
están ejecutando de manera concurrente y que pueden producir y consumir
a diferentes velocidades. Queremos proponer un protocolo de sincronización
que permita ejecutar los procesos productores y consumidores de manera con-
currente a sus respectivas velocidades y que los datos se consuman en el mis-
mo orden en el que se han generado.


Todas las versiones propuestas para conseguirlo están basadas en semáforos.
En concreto, se presentan las tres versiones que se indican a continuación:


1) Un productor y un consumidor con vector de memoria intermedia (buffer)
ilimitado.


2) Diferentes productores y diferentes consumidores con vectores de memoria
intermedia ilimitados.


3) Diferentes productores y diferentes consumidores con vectores de memoria
intermedia limitados.

## Página 65

<!-- source-page: 65 -->

GNUFDL • PID_00214803                                                                                  65                                                                                         Comunicación y sincronización

Para permitir a los procesos productores y consumidores trabajar de manera
concurrente, supondremos que disponemos de vectores de memoria interme-
dia, espacios de memoria que los productores llenan con los datos generados
y de los que los consumidores obtienen los datos que deben ser tratados.


2.1.￿Un￿productor￿y￿un￿consumidor￿con￿un￿vector￿de￿memoria￿intermedia
ilimitada


En una primera versión, consideraremos que la medida del vector de memoria
intermedia es ilimitada y que tenemos un único productor y un único consu-
midor. Una vez inicializado el sistema, el primer proceso que se debe poder
ejecutar es el productor.


Cuando ya se han producido datos, el consumidor puede empezar a tratar la
información. En el código que se propone a continuación, se utiliza un único
semáforo, producido, inicializado en 0. Esto quiere decir que no es posible
entrar en la sección crítica o, dicho de otra manera, si un proceso ejecuta la
operación sem_wait sobre el semáforo producido, se bloqueará siempre que
ningún otro proceso haya ejecutado la operación sem_signal sobre el semá-
foro producido antes.


En este primer caso, el código￿propuesto￿para￿el￿proceso￿productor es el de
la figura 52 y el código￿propuesto￿para￿el￿proceso￿consumidor es el de la
figura 53.


    while (cierto){
       /* Producir */
       ...

       /* Dejar en el buffer */
       ...

       sem_signal(producido);
       /* Otras operaciones */
       ...

    }


Figura 52. Código de los productores (versión 1)


    while (cierto){

       sem_wait(producido);
       /* Leer del buffer */
       ...

       /* Consumir */
       ...
       /* Otras operaciones */

       ...
    }


Figura 53. Código de los consumidores (versión 1)

## Página 66

<!-- source-page: 66 -->

GNUFDL • PID_00214803                                                                                  66                                                                                         Comunicación y sincronización

El semáforo producido lleva la cuenta del número de datos producidos y
todavía no consumidos. De hecho, tal como se ha especificado, el proceso
productor no necesita pedir permiso para acceder a la variable compartida
(vector de memoria intermedia) y lo único que debe hacer es señalar que ha
dejado un elemento nuevo en el vector de memoria intermedia. El productor
lo señaliza con la operación sem_signal.


El proceso consumidor, por otra parte, con el fin de que el funcionamiento sea
correcto, se debe asegurar de que hay datos en el vector de memoria intermedia
antes de intentar acceder a ella. La manera que tiene de saberlo es ejecutar la
operación sem_wait.

Supongamos que el consumidor no tiene asignado el procesador y, por lo tan-                           (22)El hecho de tener más de un
to, no se ejecuta durante un cierto tiempo. Mientras el productor va generan-                         dato hace inviable el uso de un se-
                                                                                                      máforo binario.
do datos y metiéndolos en el vector de memoria intermedia para que el con-
sumidor sepa cuántos datos debe procesar una vez vuelva a ejecutarse cada
sem_signal, debe quedar reflejado en el semáforo producido. Es, pues, ab-
solutamente necesario utilizar un semáforo n-ario22 para tener constancia del
número de señales y, por lo tanto, del número de datos pendientes de procesar
que hay en el vector de memoria intermedia.


El proceso consumidor, una vez tiene asignado el procesador, podrá entrar
tantas veces en la sección crítica como datos haya en el vector de memoria in-
termedia. Es decir, la operación sem_wait no lo bloqueará hasta que el vector
de memoria intermedia no se vacíe. Esta primera solución es muy sencilla, de
hecho con ella no aparece ninguna sección crítica.


El vector de memoria intermedia puede considerarse un vector infinito con
los dos punteros siguientes:


•    Un puntero denominado ent, que indica cuál es la posición libre siguiente
    del vector de memoria intermedia.
•    Otro puntero, denominado sal, que indica cuál es la primera posición del
    vector de memoria intermedia que tiene datos válidos pendientes de ser
    tratados.


Inicialmente los dos punteros son inicializados en 0. El productor tan sólo
modifica el puntero ent al ejecutar la función dejar_en_el_buffer, y el consu-
midor modifica el puntero sal al ejecutar la función leer_del_buffer, de manera
que no hay ningún tipo de conflicto.


2.2.￿Diferentes￿productores￿y￿diferentes￿consumidores￿con￿un￿vector￿de
memoria￿intermedia￿ilimitada


En el caso de considerar la posibilidad de tener más de un productor y más
de un consumidor, la cosa cambia un poco y no podemos utilizar el códi-
go que se ha mostrado antes. Todos los productores al ejecutar la función

## Página 67

<!-- source-page: 67 -->

GNUFDL • PID_00214803                                                                                  67                                                                                         Comunicación y sincronización

dejar_en_el_buffer modifican una variable compartida: el puntero ent, y todos
los consumidores al ejecutar la función leer_del_buffer modifican una variable
compartida, el puntero sal.


A continuación, proponemos el código necesario para garantizar la ejecución
concurrente en el caso de tener N procesos productores y M procesos consu-
midores. En este segundo caso, el código￿propuesto￿para￿los￿procesos￿pro-
ductores es el de la figura 54 y el código￿propuesto￿para￿los￿procesos￿con-
sumidores es el de la figura 55.


    while (cierto){
       /* Producir */
       ...

       sem_wait(exclusion);
       /* Dejar en el buffer */
       ...

       sem_signal(exclusion);
       sem_signal(producido);
       /* Otras operaciones */

       ...
    }


Figura 54. Código de los productores (versión 2)


    while (cierto){
       sem_wait(producido);
       sem_wait(exclusion);

       /* Leer del buffer */
       ...
       sem_signal(exclusion);

       /* Consumir */
       ...
       /* Otras operaciones */

       ...
    }


Figura 55. Código de los consumidores (versión 2)
El problema que plantea la gestión de tantos procesos se soluciona con un                                (23)El semáforo exclusión es binario.
nuevo semáforo denominado exclusion23 e inicializado en 1, para que el                                   El semáforo producido es n-ario.

primer proceso que intente acceder a la sección crítica tenga la posibilidad de
hacerlo. Como en el caso de antes, un consumidor no intentará entrar en la
zona crítica hasta que algún productor no haya generado datos. En esta solu-
ción, también sería posible utilizar dos semáforos diferentes para asegurar la
exclusión mutua en el acceso de los procesos al vector de memoria intermedia,
uno para los consumidores y otro para los productores. Con dos semáforos, se
conseguiría una mayor concurrencia entre productores y consumidores.

## Página 68

<!-- source-page: 68 -->

GNUFDL • PID_00214803                                                                                  68                                                                                         Comunicación y sincronización

2.3.￿Diferentes￿productores￿y￿diferentes￿consumidores￿con￿un￿vector￿de
memoria￿intermedia￿limitado


En la tercera versión, consideramos que tenemos un número de productores
y consumidores ilimitado y, además, que la medida del vector de memoria
intermedia es limitada, tiene una capacidad máxima. En este caso, el vector
de memoria intermedia es un recurso compartido por todos los procesos y lo
definimos como un vector, buffer[0..capacidad - 1], de capacidad fi-
nita e igual a capacidad, más dos punteros, ent y sal, inicializados en 0.
Los punteros indican cuál es la primera posición libre del vector de memoria
intermedia (ent) y cuál es la primera posición de este vector que contiene in-
formación útil (sal). En este tercer caso, el código￿propuesto￿para￿los￿proce-
sos￿productores es el de la figura 56 y el código￿propuesto￿para￿los￿procesos
consumidores es el de la figura 57.


    while (cierto){

       sem_wait(puedeproducir);
       /* Producir */
       pdata = producir();

       sem_wait(p_exclusion);
       /* Dejar en el buffer */
       buffer[ent] = pdata;

       ent = (ent + 1) mod capacidad;
       sem_signal(p_exclusion);
       sem_signal(puedeconsumir);

       /*Otras operaciones*/
       ...
    }


Figura 56. Código de los productores (versión 3)


    while(cierto){
       sem_wait(puedeconsumir);

       sem_wait(c_exclusion);
       /*Leer del buffer */

       cdata = buffer[sal];
       sal = (sal + 1) mod capacidad;
       sem_signal(c_exclusion);

       sem_signal(puedeproducir);
       /*Consumir*/
       ...

       /*Otras operaciones*/
       ...
    }


Figura 57. Código de los consumidores (versión 3)

## Página 69

<!-- source-page: 69 -->

GNUFDL • PID_00214803                                                                                  69                                                                                         Comunicación y sincronización

En la solución propuesta, se han definido cuatro semáforos:


•  c_exclusion y p_exclusion, que son semáforos binarios inicializados
     en 1. Garantizan la exclusión mutua entre los productores que acceden a
     la variable ent y entre los consumidores que acceden a la variable sal.


•  puedeproducir, que es un semáforo n-ario y se inicializa en la capacidad
     del vector de memoria intermedia, de manera que estamos permitiendo
     llenar el vector de memoria intermedia. Si ésta se llena, el siguiente pro-
     ductor que intente meter alguna cosa más se quedará bloqueado hasta que
     algún consumidor consuma datos, deje espacio libre en el vector de me-
     moria intermedia y ejecute sem_signal(puedeproducir).


•  puedeconsumir, que es un semáforo n-ario inicializado en 0, ya que
     en  un  principio  el  vector  de  memoria  intermedia  está  vacío  y  no
     hay  nada  que  consumir.  Los  procesos  productores  cada  vez  que  de-
     jan alguna cosa en el vector de memoria intermedia lo indican con
     sem_signal(puedeconsumir). El valor del semáforo puedeconsumir
     será como máximo el valor de capacidad, el número de señales (signals) en
     este semáforo que se pueden ejecutar antes de que el vector de memoria
     intermedia se llene.

## Página 70

<!-- source-page: 70 -->