Algoritmos de Planificación de Procesos: Round Robin, FCFS, SJF y Prioridades

Algoritmos de Planificación de Procesos

La planificación de procesos es una función crucial del sistema operativo que determina qué proceso obtiene tiempo de CPU en un momento dado. Existen diversos algoritmos, cada uno con sus ventajas y desventajas. A continuación, se describen algunos de los más comunes:

Round Robin (RR)

Round-Robin, también conocido como RR, Carrusel o planificación por rondas, reparte el tiempo de CPU en quantums o rodajas. El funcionamiento consiste en dar una rodaja a cada proceso de forma secuencial. La selección entre los procesos activos se gestiona según una cola FIFO (First-In, First-Out), es decir, se elige el que más tiempo lleva esperando. Si llega un proceso nuevo mientras otro está en ejecución, los ciclos de CPU se distribuyen entre ambos, pero se ejecuta un ciclo para el proceso en ejecución e inmediatamente se le asigna un ciclo al recién llegado. Este algoritmo es expropiativo y no emplea prioridades.

First Come, First Served (FCFS)

FCFS (First Come, First Served) o primero en llegar, primero en ser atendido, es un algoritmo no expropiativo que no emplea prioridades. Es muy sencillo de implementar, basta con usar una cola FIFO. Sin embargo, un proceso muy largo puede monopolizar la CPU durante mucho tiempo, generando tiempos de espera mayores a los deseables.

Shortest Job First (SJF)

SJF (Shortest Job First) o trabajo más corto primero, selecciona el proceso que requiere menor tiempo de ejecución (si dos tienen el mismo tiempo, se decide por FIFO). El problema puede aparecer con procesos muy largos que están siempre bloqueados por procesos más cortos. Este algoritmo puede ser expropiativo o no. La variante expropiativa, SRTN (Shortest Remaining Time Next), mide el tiempo restante que le queda a cada proceso.

Shortest Remaining Time Next (SRTN)

SRTN es la variedad expropiativa de SJF. El proceso con menor tiempo para acabar es el siguiente en ejecutarse, expropiando la CPU inmediatamente al proceso que esté en ejecución. El problema surge si un proceso que requiere un tiempo de ejecución igual a un proceso nuevo que entra. Existen dos soluciones: dar prioridad a los procesos nuevos o a los procesos en ejecución.

Planificación por Prioridades

En estos algoritmos, el proceso de mayor prioridad es el que se ejecuta. Con prioridades estáticas, los procesos con menor prioridad podrían no ejecutarse si entran continuamente procesos de mayor prioridad. Para solucionar esto, se utiliza la prioridad dinámica, que consiste en modificar la prioridad inicial de los procesos a medida que transcurre el tiempo, atendiendo a diferentes criterios:

Según la categoría del usuario
Según el tipo de proceso
Según la ocupación de CPU de los procesos

La prioridad puede ser apropiativa o no apropiativa (apropiativo, expulsivo o expropiativo son sinónimos). En caso de conflicto (varios procesos con la misma prioridad), se suele usar FIFO.

Virtualización

El concepto de máquina virtual surge de la necesidad de trabajar con sistemas interactivos. El fracaso del sistema TSS/360 por su gran complejidad abrió las puertas a una nueva idea, dando origen en 1979 al SO VM/370 basado en máquinas virtuales que corrían sobre un programa monitor común. En la actualidad, las máquinas virtuales están muy difundidas (ej: IBM z/VM).

Las aplicaciones web llevaron a la implantación de sistemas con múltiples servidores virtuales en una misma plataforma de hardware. Empresas como Hewlett Packard y Sun Microsystems fueron pioneras. En el caso de las PCs que permiten la ejecución de varios sistemas operativos, la función de Monitor del sistema VM/370 cambió por el nombre de «Hypervisor» (una capa de software que permite instalar varios sistemas operativos). El hardware debe ser virtualizable; esto se conoce como hipervisor de tipo 1.

Para lograr mayor funcionalidad, se desarrollaron productos como VMware Workstation, que proporciona un ambiente montado sobre un sistema operativo anfitrión («host») donde se crean distintas máquinas virtuales con sus sistemas operativos huésped («guest»). A esta solución se la denomina hipervisor de tipo 2.

Exclusión Mutua y Zona Crítica

La zona crítica es la parte del código de un proceso donde se accede a un recurso compartido (generalmente memoria). Esta porción de código debe ejecutarse de forma atómica (sin interrupciones). En contextos de IPC (Inter-Process Communication), solo un proceso puede ejecutar su región crítica; los demás deben esperar.

Para lograr la exclusión mutua (que solo un proceso acceda a la zona crítica a la vez), se han propuesto varias soluciones:

Deshabilitar interrupciones (no conveniente para procesos de usuario)
Variable candado (requiere verificación y asignación atómica)
Alternancia estricta (no funciona bien con prioridades distintas)
Solución de Peterson (mejora la alternancia estricta)
Instrucción TSL (solución de hardware)

Estructura de Directorios de Linux

La estructura de directorios típica de segundo nivel de Linux incluye:

/bin: Comandos y programas principales del sistema
/boot: Herramientas y configuración de arranque
/dev: Controladores de dispositivos
/etc: Archivos de configuración del sistema
/home: Directorio para espacio de usuarios
/lib: Bibliotecas usadas en el sistema
/lost+found: Recuperación de problemas en el sistema de archivos
/media: Montaje de dispositivos removibles
/mnt: Directorio para montaje
/opt: Instalación de software adicional
/proc: Procesos y recursos del sistema
/root: Directorio de usuario root
/sbin: Comandos de administración del sistema
/sys: Directorios de recursos del sistema
/tmp: Archivos temporales
/usr: Configuración y programas para usuarios
/var: Archivos variables del sistema (logs, mail, spool)

Terminales de Consola en Linux

Se abre una terminal con Ctrl+Alt+Fx (x de 1 a 6). La terminal gráfica suele ser Ctrl+Alt+F7. Se vuelve al modo gráfico con Alt+F7.

Precompilador

Un precompilador procesa los encabezados (archivos .h) del lenguaje y convierte el código portable a las condiciones particulares de la máquina donde se va a compilar.

Permisos de Shell Script

El comando chmod 764 miscript.sh asigna los siguientes permisos: Usuario (rwx), Grupo (rw-), Otros (r–).

Modelos de Núcleos de Sistemas Operativos

Sistemas Monolíticos: El sistema operativo se escribe como una colección de procedimientos enlazados en un solo programa binario.
Sistemas de Capas: El sistema se organiza en capas jerárquicas.
Microkernels: Basado en capas, reduce la complejidad del núcleo a módulos pequeños y confiables.
Modelo Cliente-Servidor: Divide los procesos en clientes y servidores.
Exokernels: Programa de capa inferior que asigna recursos a máquinas virtuales.
Máquinas Virtuales: Programa monitor que permite virtualizar distintas máquinas.

Dormir y Despertar en IPC

Para evitar la inversión de prioridad, se utilizan las acciones de dormir («sleep») y despertar («wakeup»). En el ejemplo del productor-consumidor, el productor se duerme si el buffer está lleno, y el consumidor se duerme si está vacío. Se despiertan cuando las condiciones cambian. La sincronización se puede hacer con semáforos, mensajes o monitores.

Prompt de Terminal

$ indica usuario común; # indica usuario root (superusuario).

Editores en Linux

vi: Editor nativo de Unix.
vim: Editor Vi mejorado.
gvim: Editor Vi mejorado gráfico.
nano o pico: Editores livianos.
gedit: Editor gráfico de consola.

Extensiones de Archivo

.c: Fuente C
.C o .cc: Fuente C++
.i: Código fuente C preprocesado
.ii: Código fuente C++ preprocesado
.S, .s: Código fuente ensamblador
.o: Código objeto compilado

Comando grep

grep filtra cadenas de texto (ASCII y UNICODE). Su equivalente en Windows es find, aunque grep tiene más prestaciones.