Problemas clásicos de condiciones de competencia

Problema de la cena de los filósofos

En 1965 Dijkstra planteó y resolvió un problema de sincronización llamado el problema de la cena de los filósofos, que se puede enunciar como sigue. Cinco filósofos se sientan a la mesa, cada uno con un plato de espaghetti. El espaghetti es tan escurridizo que un filósofo necesita dos tenedores para comerlo. Entre cada dos platos hay un tenedor. En la figura se muestra la mesa.



La vida de un filósofo consta de periodos alternos de comer y pensar. Cuando un filósofo tiene hambre, intenta obtener un tenedor para su mano derecha, y otro para su mano izquierda, cogiendo uno a la vez y en cualquier orden. Si logra obtener los dos tenedores, come un rato y después deja los tenedores y continúa pensando. La pregunta clave es: ¿puede el lector escribir un programa para cada filósofo que permita comer equitativamente a los filósofos y no se interbloquee?

El problema de los lectores y los escritores

El problema de la cena de los filósofos es útil para modelar procesos que compiten por el acceso exclusivo a un número limitado de recursos, como una unidad de cinta u otro dispositivo de E/S. Otro problema famoso es el de los lectores y escritores (Courtois et al., 1971), que modela el acceso a una base de datos. Supóngase una base de datos, con muchos procesos que compiten por leer y escribir en ella. Se puede permitir que varios procesos lean de la base de datos al mismo tiempo, pero si uno de los procesos está escribiendo (es decir, modificando) la base de datos, ninguno de los demás debería tener acceso a ésta, ni siquiera los lectores. La pregunta es ¿ cómo programaría los lectores y escritores ? La solución se muestra en la figura 4.18.

En esta solución, el primer lector que obtiene el acceso a la base de datos realiza un wait sobre el semáforo bd. Los lectores siguientes sólo incrementan un contador, nl. Al salir los lectores, éstos decrementan el contador, y el último en salir realiza un signal sobre el semáforo, lo que permite entrar a un escritor bloqueado, si existe.

Una hipótesis implícita en esta solución es que los lectores tienen prioridad sobre los escritores. Si surge un escritor mientras varios lectores se encuentran en la base de datos el escritor debe esperar. Pero si aparecen nuevos lectores, y queda al menos un lector accediendo a la base de datos, el escritor deberá esperar hasta que no haya más lectores interesados en la base de datos.

Procesos

Procesos

Un proceso puede informalmente entenderse como un programa en ejecución. Formalmente un proceso es "Una unidad de actividad que se caracteriza por la ejecución de una secuencia de instrucciones, un estado actual, y un conjunto de recursos del sistemas asociados".

Para entender la diferencia entre un programa y un proceso, A. S. Tanenbaum propone la analogía "Un científico computacional con mente culinaria hornea un pastel de cumpleaños para su hija; tiene la receta para un pastel de cumpleaños y una cocina bien equipada con todos los ingredientes necesarios, harina, huevo azúcar, leche, etcétera." Situando cada parte de la analogía se puede decir que la receta representa el programa (el algoritmo), el científico computacional es el procesador y los ingredientes son las entradas del programa. El proceso es la actividad que consiste en que el científico computacional vaya leyendo la receta, obteniendo los ingredientes y horneando el pastel.
Cada proceso tiene su contador de programa, registros y variables, aislados de otros procesos, incluso siendo el mismo programa en ejecución 2 veces. Cuándo este último caso sucede, el sistema operativo usa la misma región de memoria de código, debido a que dicho código no cambiará, a menos que se ejecute una versión distinta del programa.

Jerarquía de procesos

En un sistema lo suficientemente sencillo es posible que todos los procesos que podrían ser necesarios en algún momento pueden estar presentes durante la inicialización del sistema, pero en la mayoría de los sistemas, es necesario una forma de crear y destruir procesos, cundo se requiera durante la operación.

Desde el punto de vista macro, los procesos son las actividades claves que se requieren para manjar y, o dirigir una organización, es necesario mostrar la jerarquía de proceso en la siguiente grafica.

Esta jerarquía muestra cinco niveles: nivel macroproceso, nivel proceso, nivel subproceso, nivel actividades y nivel de tareas específicas a realizar en un proceso concreto.

Llamadas al sistema

En informática, llamada al sistema es el mecanismo usado por una aplicación para solicitar un servicio al sistema operativo.


Las llamadas al sistema comúnmente usan una instrucción especial de la CPU que causa que el procesador transfiera el control a un código privilegiado, previamente especificado por el mismo código. Esto permite al código privilegiado especificar donde va a ser conectado así como el estado del procesador.
Cuando una llamada al sistema es invocada, la ejecución del programa que invoca es interrumpida y sus datos son guardados, normalmente en su PCB (Bloque de Control de Proceso del inglés Process Control Block), para poder continuar ejecutándose luego. El procesador entonces comienza a ejecutar las instrucciones de código de alto nivel de privilegio, para realizar la tarea requerida. Cuando esta finaliza, se retorna al proceso original, y continúa su ejecución. El retorno al proceso demandante no obligatoriamente es inmediato, depende del tiempo de ejecución de la llamada al sistema y del algoritmo de planificación de CPU.

Generalmente, los sistemas operativos proveen bibliotecas que relacionan los programas de usuario y el resto del sistema operativo, usualmente una biblioteca C como glibc o el runtime de Microsoft C. Esta biblioteca maneja los detalles de bajo nivel para transferir información al kernel y conmutar a modo supervisor, así como cualquier procesamiento de datos o tareas que deba ser realizada en modo supervisor. Idealmente, esto reduce la dependencia entre el sistema operativo y la aplicación, e incrementa su portabilidad.