Cuando varios Sistemas Operativos/Procesos o Sistemas Operativos/Hilos comparten datos, surge la necesidad de comunicación entre procesos (IPC) y de sincronizarlos. Tanenbaum identifica tres problemas: cómo pasar información, cómo evitar que se estorben y cómo ordenar correctamente sus acciones.

Condiciones de carrera

Una condición de carrera (race condition) ocurre cuando dos o más procesos leen o escriben datos compartidos y el resultado final depende del orden exacto de ejecución.

Ejemplo del spooler de impresión: dos procesos A y B leen in = 7 (siguiente ranura libre). A es interrumpido antes de actualizar in; B escribe su archivo en la ranura 7 y pone in = 8; A reanuda, escribe también en la ranura 7 y pone in = 8. El trabajo de B se pierde y nadie se entera.

Regiones críticas

La región crítica (o sección crítica) es la parte del programa donde se accede a memoria compartida. Para evitar carreras hace falta exclusión mutua. Una buena solución debe cumplir cuatro condiciones:

1. Dos procesos no pueden estar simultáneamente dentro de sus regiones críticas.
2. No se pueden hacer suposiciones sobre velocidades o número de CPUs.
3. Ningún proceso fuera de su región crítica puede bloquear a otros.
4. Ningún proceso debe esperar indefinidamente para entrar a su región crítica.

Exclusión mutua con espera ocupada

Deshabilitar interrupciones

Sencillo en monoprocesador, pero peligroso dar ese poder a procesos de usuario y no funciona en multiprocesadores. Útil sólo dentro del Sistemas Operativos/Kernel.

Variables de candado

Un simple lock = 0/1 tiene la misma condición de carrera que pretende resolver.

Alternancia estricta

/* Proceso 0 */                 /* Proceso 1 */
while (TRUE) {                  while (TRUE) {
    while (turn != 0) ;             while (turn != 1) ;
    critical_region();              critical_region();
    turn = 1;                       turn = 0;
    noncritical_region();           noncritical_region();
}                               }

Viola la condición 3: un proceso lento fuera de su región crítica bloquea al otro. Una variable que se consulta en bucle es un spin lock.

Solución de Peterson

int turn;
int interested[2];

void enter_region(int process) {
    int other = 1 - process;
    interested[process] = TRUE;
    turn = process;
    while (turn == process && interested[other] == TRUE) ;
}

void leave_region(int process) {
    interested[process] = FALSE;
}

Instrucción TSL (Test and Set Lock)

Soporte de hardware: TSL REGISTER,LOCK lee la palabra LOCK en un registro y guarda un valor distinto de cero, de forma atómica (bloquea el bus de memoria). XCHG en x86 es equivalente.

enter_region:
    TSL REGISTER,LOCK   | copia lock al registro y pone lock a 1
    CMP REGISTER,0      | ¿era cero?
    JNE enter_region    | si no, el candado estaba puesto: repetir
    RET
leave_region:
    MOVE LOCK,0
    RET

Problema de la espera ocupada

Desperdicia CPU y sufre el problema de inversión de prioridades: un proceso H de alta prioridad hace espera ocupada mientras L, de baja prioridad, tiene el candado pero nunca es planificado.

La alternativa es dormir y despertar (sleep/wakeup), que lleva a los Sistemas Operativos/Semáforos y a los Sistemas Operativos/Mutex y monitores.

Otras formas de IPC

• Paso de mensajes: send(destino, &mensaje) y receive(origen, &mensaje). Funciona entre máquinas.
• Barreras: ningún proceso pasa a la siguiente fase hasta que todos han llegado.
• RCU (read-copy-update): lectores sin candados mientras los escritores publican versiones nuevas.

Ver Sistemas Operativos/Problemas clásicos de IPC e Sistemas Operativos/Interbloqueos.

#sistemas-operativos #tanenbaum #concurrencia