Módulo 1

INTRODUCCIÓN A LOS
SISTEMAS OPERATIVOS
Definición e historia
• ¿Qué es un sistema operativo?

• Conjunto de módulos o funciones (software), que, instalados en la

computadora, se ocupan de controlar y administrar la ejecución de los
programas sobre los recursos que brinda el equipo (hardware), tales como:
memoria, procesador, periféricos, etc.

• Conjunto de programas que ordenadamente relacionados entre sí,

contribuyen a que la computadora lleve a cabo correctamente su trabajo
para nosotros en un ambiente dado.
Definición e historia
Evolución de los sistemas operativos
• Proceso por lotes
• Los sistemas operativos eran denominados sistemas de control o sistemas monitor, y
básicamente asistían a los operadores en la carga y monitoreo de las tareas, además de
notificar los resultados y algunas medidas básicas de control.
• Posteriormente se evolucionó con el uso de un spool (Simultaneous Peripheral Operations
On-Line).
• Sistemas multiprogramados
• Buscan maximizar el tiempo de uso del procesador, aprovechando los períodos de tiempo
en que los procesos hacen uso de los dispositivos. (CPU Bound – I/O Bound).
• Se logra otorgando el uso del procesador a otros procesos, pero eso genera nuevas
problemáticas de seguridad.
• Sistemas de tiempo compartido
• Es una evolución de lo anterior. Con la llegada de las terminales, se convierten en sistemas
interactivos y multiusuario.
• Los programadores ya podían compilar y editar sus programas ellos mismos.
Definición e historia

Evolución de los sistemas operativos

• La llegada de las computadoras personales

• En un principio, equipos muy específicos programables mediante interruptores y con salidas de LEDs.
• La revolución de los 8 bits
• Computadoras personales con teclado y monitor (lo más usual era una salida a los televisores).
• Se populariza el lenguaje BASIC.
• Estos equipos tenían un software mínimo de gestión: un proto-sistema operativo.
• La llegada de la PC
• Se populariza PC-DOS y MS-DOS.
• Se brinda al usuario una sencilla interfaz de línea de comandos para gestionar archivos y programas.
• El entorno WIMP (Windows, Icons, Menus, Pointer)
• Se incorpora un entorno gráfico.
• Ojo: Tener múltiples ventanas no significaba que el sistema operativo fuese multitarea.
Definición e historia
Evolución de los sistemas operativos
• Dispositivos móviles

• Las características de estos equipos obligaron a diseñar interfaces específicas y tener

consideraciones que no se presentan en computadoras de escritorio o servidores,
por ejemplo: gestión de energía, tamaño y rotación de las pantallas, etc.

• Apple fue el pionero en sistemas multitouch (iOS).

• Google diseña el S.O. Android, principalmente basado en GNU/Linux.

• Otros fabricantes también lanzaron sus sistemas operativos para móviles, sin el éxito
comercial de los dos anteriores: Windows Phone, Symbian, Firefox OS, etc.
Funciones y
objetivos
• Las funciones de los S.O. son básicamente
cuatro:

• Inicialización

• Máquina extendida (abstracción)

• Administración de recursos

• Aislamiento (seguridad)
 • La inicialización preparara la máquina y la lleva a un estado tal que pueda
ejecutar el primer trabajo.

Inicialización • Existen el cold boot y el warm boot. Difieren en las tareas de control
realizadas previa carga del sistema operativo.

• Menos del 1 % de las tareas del S.O. se destinan a esta función.

• A mediados de los años 90 surge UEFI, un nuevo estándar para PCs. Surge
como sucesor de BIOS.
Máquina extendida
(interfase hombre – máquina)

Se refiere al código del sistema operativo Típicamente, se clasifican en:

que se encarga de ofrecer al usuario una • GUI (Graphical User Interface)
interfaz para operar con la computadora. • Ejemplos: Gnome – KDE – XFCE – LXQT – Aero –
Sus principales funciones son: Modern UI
• CLI (Command Line Interface)
• Proveer abstracción de la complejidad del
hardware subyacente. • Ejemplos: bash – bourne Shell – Emacs – Ksh –
cmd – Powershell
• Facilitar la comunicación con el usuario.
• NUI (Natural User Interface)
• Aceptar entradas de nuevos trabajos.
 Admini Es la función principal de
cualquier sistema operativo.

stració Más del 70% del código está

dedicado a esta función.
n de Gestiona políticas de
recurso asignación de los recursos.

Optimiza la utilización de los

s recursos.
Aislamiento (seguridad)

• Objetivo: Garantizar la integridad de los Recursos y de los Procesos, como también validar
los usuarios en el sistema.

• Originalmente, la seguridad se refería únicamente a la integridad del propio sistema

operativo y a la protección entre usuarios.
• Los mecanismos fundamentales para lograr esto son:
• Modo dual de ejecución del procesador.
• Juego de Instrucciones diferenciadas del Procesador.

• Actualmente, además de lo anterior, muchos sistemas operativos incluyen herramientas

para mitigar ataques (p. ej: malware, exploits), por ejemplo, con la automatización de
actualizaciones, incorporación de software antimalware, application firewalls, etc.
 • A partir de la arquitectura de Intel 80286, se incorpora un
nuevo modo de trabajo, denominado “modo protegido”, que
incluye una clasificación de las instrucciones del procesador y un
bit para indicar el modo de operación:

• Modo usuario o no privilegiado

Modo • Este es el modo normal de operación para los procesos

del usuario.
• Si se intenta ejecutar una instrucción privilegiada la
dual de CPU interrumpe la ejecución y genera una excepción o
trap, pasando el control al S.O.

operación • Modo kernel o privilegiado

• Cuando se necesita utilizar alguna instrucción
privilegiada, sólo podrá hacerlo el S.O., ya que primero
habrá que cambiar de modo usuario a modo
privilegiado. Y esta función es exclusiva del S.O.
• La mayoría de las funciones realizadas por el S.O.
requieren este modo de operación.
Tipos de • Según la cantidad de usuarios que
soporta:
Sistemas • Monousuario: un solo
Operativos usuario.

• Multiusuario: más de un
usuario trabajando
simultáneamente con el
computador.
Tipos de Sistemas Operativos

Según la cantidad de procesadores que soporta:

• Uniprocesador: Un sistema operativo uniprocesador es aquél capaz de

manejar solamente un procesador de la computadora, de manera que si
la computadora tuviese más de uno le sería inútil. El ejemplo más típico
de este tipo de sistemas es el DOS y MacOS.

• Multiprocesador: Son sistemas capaces de administrar más de un

procesador, compartiendo memoria y periféricos. La mayoría de los
sistemas operativos actuales se diseñan para sacar provecho del
multiprocesamiento.
Tipos de Sistemas Operativos

Según la cantidad de procesos que ejecutan concurrentemente(*):

• Monoprogramados: Sólo se puede ejecutar un proceso a la vez. Recién cuando

éste finalice, se puede ejecutar otro proceso. Se los conoce también como sistemas
operativos monotarea.
• Multiprogramados: También llamados multitarea o multitask, se refiere a sistemas
operativos capaces de maximizar el uso del procesador. Cuando un proceso se
encuentra haciendo uso de algún dispositivo, se otorga el procesador a otro
proceso.

(*) No confundir ejecución concurrente con ejecución paralela.

Para esto último se requieren 2 o más procesadores, y un S.O.
capaz de administrarlos.
Tipos de Sistemas Operativos
Según sus aplicaciones, se pueden dividir en:

• De propósito general
• Son los que proporcionan una amplia gama de servicios y
deben adaptarse a cualquier ambiente, tipo de aplicaciones,
modos de operación, dispositivos, etc.
• De propósito especial
• Construidos a medida debido a arquitecturas especiales o
aplicaciones con requerimientos especiales como control de
procesos industriales. Históricamente se clasifican como:
• Sistemas de tiempo real
• Sistemas tolerantes a fallas
• Sistemas virtuales
Tipos de Sistemas Operativos
• S.O. de tiempo real
• Un sistema operativo de tiempo real debe garantizar la respuesta a eventos
externos dentro de límites de tiempo preestablecidos.

• Existen dos tipos de Sistemas de Tiempo Real:

• Aquellos en que el tiempo de respuesta no es muy crítico: reservas de pasajes,
aplicaciones comerciales on-line, control de tránsito vehicular, control de
tráfico telefónico, etc.

• Los que el tiempo de respuesta es muy crítico (sistemas estimulados por

eventos externos deben generar respuestas a estos eventos), control de
procesos industriales, recolección de datos de experimentos, etc.

• Ejemplos: VxWorks – QNX – eCos – RTLinux

Tipos de Sistemas Operativos
S.O. tolerantes a fallas
• Se utilizan en aplicaciones donde se debe proveer un servicio continuo.

• Se suele utilizar un conjunto de redundancias en recursos y chequeos

internos.

• El S.O. detecta y corrige errores.

• Aplicaciones: sistemas de seguridad en el área nuclear, sistemas espaciales,

cajeros automáticos, bases de datos on-line, etc.

• Ejemplos: Stratus VOS (System/88) – Guardian (Tandem)

 Tipos de • Son sistemas operativos capaces de
Sistemas administrar y gestionar otros sistemas
operativos que ejecutan bajo su
Operativos. órbita en forma concurrente usando
S.O. el mismo hardware.

Virtuales • Nacen alrededor de los años 60. El

objetivo principal era poder
ejecutar distintos sistemas
operativos con el hardware
existente, que era caro y escaso.
• Posteriormente, esta tecnología cae en
desuso, ya que el hardware se hacía más
accesible económicamente.
• Hacia fines de los años 90 vuelve a surgir el
concepto y hoy día prácticamente todos los
centros de datos utilizan la virtualización.
• (Se tratará el tema en detalle).
Arquitectura de los S.O.

• Existen dos formas básicas de organización interna de un sistema

operativo, más una concepción híbrida:

• Sistemas monolíticos

• Sistemas microkernel

• Sistemas híbridos
Arquitectura
de los S.O.
• Sistemas monolíticos

• Se tiene un único proceso

que opera en modo
privilegiado, dentro del
cual se encuentran las
rutinas requeridas para
las distintas tareas
realizadas por el S.O.
• Al no requerir muchos
mecanismos de
comunicación, ofrecen
una buena performance
en la ejecución.
Arquitectura
de los S.O.
• Sistemas microkernel

• El núcleo del sistema

operativo se mantiene en el
mínimo posible de
funcionalidad, descargando
en procesos especiales sin
privilegios las tareas que
implementan el acceso a
dispositivos y las diversas
políticas de uso del sistema.
• Poseen una lógica más
“limpia” y resulta más simple
el reemplazo de
componentes.
 Arquitectura de los S.O.
Sistemas híbridos

• Son sistemas que tienen una base monolítica, pero manejan algunos de sus
procesos como componentes a nivel de usuario (fuera del kernel).
• Ejemplos de esto son los sistemas de archivos FUSE, en Linux.
• La mayoría de los sistemas operativos modernos utilizan este tipo de
arquitectura, entre ellos Microsoft Windows.
 Se llama interrupción a la detención del programa en ejecución debido a una condición
externa al procesador, es decir que éste es forzado a reconocer la ocurrencia de un
evento en el sistema (*).

Cuando un dispositivo requiere atención, debe “avisar” al procesador, mediante una

línea (IRQ) conectada al controlador de interrupciones, un hardware dedicado a su
tratamiento.

Interrupciones A partir del número de IRQ, se busca la dirección de memoria de la rutina de atención
que se debe ejecutar para atender la petición. (Vector de Interrupciones).

En general, el procesador después de preservar los contenidos de todos los registros y

cierta información acerca del estado del proceso, reemplaza el contenido del contador
de programa (Program Counter), por la dirección donde se encuentra la RAI.

(*) Estrictamente, esta definición corresponde a las interrupciones de hardware

externas, como se verá en las siguientes filminas.
Clasificación de las
interrupciones
• Clasificación según su prioridad:

• No enmascarables:
• Son las interrupciones de mayor prioridad en el sistema.
• Cuando se detecta una interrupción de este tipo el sistema operativo detiene lo que está haciendo, y se ocupa de atender la interrupción.
• Este tipo de interrupción puede detener hasta la ejecución de rutinas en modo Kernel.
• En general se utilizan para la notificación de errores irrecuperables por parte de algún hardware.

• Enmascarables:
• Son interrupciones de menor prioridad (dentro de las interrupciones, pero siempre tienen mayor prioridad que cualquier proceso usuario).
• Este tipo de interrupciones puede ser interrumpida (valga la redundancia), por una interrupción de mayor prioridad (generalmente del tipo anterior).
Clasificación de las interrupciones

Clasificación según su origen:

• Software:
• Se denominan así a las llamadas al sistema (syscalls) que hacen los procesos.
• Si bien no son eventos que el procesador debe reconocer, se categorizan así porque en definitiva se
interrumpe el código del usuario para dar lugar a la atención de dicha llamada al sistema operativo.

• Hardware:
• Son interrupciones generadas por algún componente físico del sistema. Se subdividen en:
• Internas:
• Se producen dentro del procesador.
• Ejemplos: División por cero, código de operación inválido.
• Externas:
• Se producen fuera del entorno del procesador.
• Ejemplos: Finalización de I/O, falta de papel, error en dispositivos.
Multiprogramación / Multiprocesamiento
Para tener en cuenta y no olvidar !

Procesos secuenciales
Cada proceso ejecuta a continuación del otro.

Multiprogramación
O concurrencia, es la ilusión de simultaneidad.

Multiprocesamiento
Procesadores independientes. Hay paralelismo.

Multiprogramación y multiprocesamiento
Se combinan. La mayoría de las PC actuales funcionan así.
Multiprogramación /
Multiprocesamiento
• Algunas consideraciones sobre cómputo paralelo:

• Multiprocesamiento simétrico (SMP)

• Uniform Memory Access (UMA):

• Varios procesadores compartiendo la memoria, con igualdad de condiciones.
• Utilizan un BUS compartido, por lo que debe administrarse su uso.

• Non-Uniform Memory Access (NUMA):

• Cada procesador tiene afinidad con bancos específicos de memoria.
• Pueden acceder a su memoria “local” más rápido que a la memoria de otros procesadores o compartida.
• El objetivo es mejorar la performance.

• Multiprocesamiento asimétrico

• Varios procesadores con objetivos y hasta arquitecturas diferentes.

• Son considerados coprocesadores. Por ejemplo, los que se incluyen en placas de video avanzadas.
Cómputo distribuido
• El cómputo distribuido se refiere al trabajo realizado por computadoras independientes (o bien, procesadores que no
comparten memoria). Los tipos más comunes son:

• Clústers
• Computadoras conectadas a una red local de alta velocidad, cada una ejecutando su propia instancia de sistema
operativo. Se ven como un único equipo de cómputo.

• Grids
• Computadoras heterogéneas distribuidas geográficamente e interconectadas a una red. Se diseñan para
adaptarse a enlaces de baja velocidad.

• Cómputo en la nube
• Se refiere a la tercerización de servicios.
• La implementación de los servicios deja de ser relevante.
• Se aplican conceptos como:
• SaaS: Se ofrece la aplicación completa (Ej: Office365, Google Apps).
• PaaS: Se ofrece un entorno completo para desarrollo o despliegue de aplicaciones (Ej: OpenShift,
Windows Azure).
• IaaS: Se ofrece un hardware completo (real o virtual), pero con gran flexibilidad para modificar sus
recursos (Ej: RackSpace, Google Compute Engine).
Módulo 2

DE PROGRAMAS
A PROCESOS
 De Programas A Procesos
➢ Definimos como Programa al conjunto ordenado de
instrucciones que pretenden resolver un problema.

➢ Una Instrucción es una unidad de ejecución que dura un

tiempo finito y se ejecuta sobre un procesador (es indivisible,
no se descompone ni se interrumpe y se dice que ejecuta
atómicamente).

➢ Un PROCESO es una porción de un programa cargado en

Memoria Central al cual se le asocia su contexto de ejecución
(run time environment) mediante una estructura de datos
llamada vector de estado o Bloque de Control del Proceso
(Process Control Block - PCB).
 De Programas A Procesos
➢ Un proceso consiste en una secuencia de acciones llevadas a
cabo a través de la ejecución de una serie de instrucciones (un
programa), cuyo resultado consiste en proveer alguna función
del sistema.

➢ Resumiendo, un proceso es una secuencia de acciones y es, en

consecuencia, dinámico, mientras que un programa es una
secuencia de instrucciones y es, por lo tanto, estático.

➢ Un programa es una entidad pasiva.

➢ Un proceso es una entidad activa.

Compilación y carga de un
programa
Trabajos, Procesos y Threads
• Un trabajo (Job) En un sistema por lotes se habla de tareas. Una
tarea requiere mucha menos estructura, típicamente basta con
guardar la información relacionada con la contabilidad de los
recursos empleados. Una tarea no es interrumpida en el transcurso
de su ejecución. - En desuso en los sistemas actuales.

• Un proceso (Process) es la imagen en memoria de un programa,

junto con la información relacionada con el estado de su ejecución.

• Un Hilo o Hebra (thread) también llamado proceso liviano, es un

trozo o sección de un proceso que tiene sus propios registros, pila y
program counter y puede compartir la memoria con todos aquellos
threads que forman parte del mismo proceso.
Diagrama de transición de
estados de un proceso
 Estados de un proceso
• Nuevo: Se solicitó al sistema operativo la creación de un proceso, y sus
recursos y estructuras están siendo creadas.
• Listo: Está listo para iniciar o continuar su ejecución pero el sistema no le
ha asignado un procesador.
• En ejecución: El proceso está siendo ejecutado en este momento. Sus
instrucciones están siendo procesadas en algún procesador.
• Bloqueado: En espera de algún evento para poder continuar su ejecución
(aun si hubiera un procesador disponible, no podría avanzar).
• Zombie: El proceso ha finalizado su ejecución, pero el sistema operativo
debe realizar ciertas operaciones de limpieza para poder eliminarlo de la
lista.
• Terminado: El proceso terminó de ejecutarse; sus estructuras están a la
espera de ser limpiadas por el sistema operativo.
Razones de un cambio de estado
de Proceso

• Pueden ser 3:

➢Por interrupciones de hardware externas

➢Por una excepción (trap)
➢Por una llamada al sistema.
 Transiciones de Estado
• Todo proceso a lo largo de su existencia puede cambiar de
estado varias veces.
• Cada uno de estos cambios se denomina transición de estado.
• Estas transiciones pueden ser las siguientes:
✓ Comienzo de la ejecución
✓ Paso a estado listo o preparado
✓ Paso a estado de ejecución
✓ Paso a estado bloqueado
✓ Paso a estado suspendido bloqueado
✓ Paso a estado suspendido listo
✓ Finalización
 Modelo de Siete Estados

Suspendido
NEW EXIT
Interrumpido
Admitido
Admitido por time out Abandono

Activado
READY RUNNING
READY/
SUSPEND Suspendido
Planificador despacha
Evento o E/S Evento o E/S
Completado espera
Activado BLOCKED
BLOCKED/
SUSPEND
Suspendido

Los estados agregados READY/SUSPEND y BLOCKED/SUSPEND

corresponden a situaciones relativas a la administración de memoria
 Estados activos
Son aquellos que compiten por el procesador o están en
condiciones de hacerlo

➢ Ejecución (Running): Estado en el que se encuentra un

proceso cuando tiene el control del procesador.
➢ Listo o Preparado (Ready): Aquellos procesos que están
dispuestos para ser ejecutados. Disponen de todos los
recursos para su ejecución y aguardan su turno en una cola de
listos (Ready Queue).
➢ Bloqueado (Blocked): Son los procesos que no pueden
ejecutarse de momento por necesitar algún recurso no
disponible (generalmente recursos de entrada/salida).
 Estados inactivos:
Son aquellos que no pueden competir por el uso del procesador.

➢ Suspendido bloqueado (Suspend – Blocked): Es el proceso

que fue suspendido en espera de un evento, sin que hayan
desaparecido las causas de su bloqueo.

➢ Suspendido programado (Suspended – Ready): Es el

proceso que ha sido suspendido, pero no tiene causa para
estar bloqueado.
 Administración de procesos
➢ Los datos sobre el proceso se guardan en una estructura de
datos llamado vector de estado o PCB (Process Control
Block).

➢ El PCB se almacena en el STACK (pila) del proceso.

➢ El Stack es un área de memoria utilizada para la ejecución del

proceso.

➢ Del Stack se copia una imagen del proceso que se carga sobre
CPU y se ejecuta.

➢ El sistema operativo utiliza colas con punteros a los PCBs para

mantener el registro de estado de los procesos (ej: cola de
listos, cola de bloqueados, etc)
El Bloque de Control del Proceso
(PCB)

➢ El Sistema Operativo mantiene para cada proceso un bloque

de control o process control block (PCB).

➢ En el PCB se guarda para cada proceso la información

necesaria para reanudarlo (cuando es suspendido o
desalojado del uso del procesador), y otros datos.

➢ La información contenida en el PCB varia de S.O. en S.O.

 Objetivos del PCB

• Localización de la información sobre el proceso por parte del

Sistema Operativo.

• Mantener registrados los datos del proceso en caso de tener

que suspender temporalmente su ejecución o reanudarla.

• Los datos relativos al estado del proceso siempre se

encuentran en memoria central.
 Contenido del PCB
✓ Identificación (única en el sistema)
✓ Identificadores varios del proceso (identificador del dueño,
padre, hijos, etc)
✓ Estado (ejecutando, listo, bloqueado)
✓ Program Counter
✓ Registros de CPU
✓ Información para planificación ([Link]., prioridad)
✓ Información para administración de memoria ([Link]., registros
base y límite)
✓ Información de I/O: dispositivos y recursos asignados al
proceso, archivos abiertos en uso, etc.
✓ Estadísticas y otros: tiempo real y tiempo de CPU usado, etc.
✓ Privilegios.
✓ Otros objetos vinculados al proceso.
 Cambio de contexto
• Se denomina cambio de contexto al mecanismo mediante el
cual el sistema almacena la información del proceso que se
está ejecutando (en registros de la CPU), y pasa a ejecutar
otra rutina (un ejemplo típico es la atención del movimiento
del mouse).

Cambio de proceso
• Cuando el Sistema Operativo entrega a la CPU un nuevo
proceso, debe guardar el estado del proceso que estaba
ejecutando, y cargar el estado del nuevo.

• Cuando hay un process switch hay un context switch

• Pero si hay context switch, no necesariamente habrá process
switch.
 Creación de procesos:
• Todos los procesos son creados por el SO

• Sin embargo, puede ser útil permitir que un proceso pueda

originar la creación de otros procesos

• Cuando un proceso genera a otro, el proceso generador se

conoce como proceso padre y el proceso generado es el
proceso hijo.

• Normalmente estos procesos necesitan comunicarse y

cooperar.
 Existen dos tipos de creación:
➢ Jerárquica : Cada proceso que se crea es hijo del proceso
creador y hereda el entorno de ejecución de su padre.

❖El Padre continúa ejecutando concurrentemente

(paralelo) con sus hijos; o

❖El padre espera a que todos sus hijos hayan terminado y

luego sigue él.

➢ No Jerárquica: cada proceso creado por otro proceso se

ejecuta independientemente de su creador en un entorno
diferente. (no es muy común).
Hay cuatro motivaciones o razones
para que un proceso sea creado:
• Llega un trabajo nuevo al sistema: generalmente en forma de
batch entonces el S.O. debe recibirlo y comenzarlo a ejecutar
creando una secuencia de procesos nuevos.

• Llegada de un usuario al sistema: Entonces el S.O. ejecuta un

proceso llamado login.

• Un servicio al programa en ejecución: Creado por el S.O. por

ejemplo realizar una lectura en disco (en ese caso el proceso
que solicitó el servicio es bloqueado).

• Por un proceso existente: por razones de modularidad o

paralelismo.
Una vez que el SO decide por alguna razón crear un
nuevo proceso sigue los siguientes pasos:

➢ Asignar un único identificador al nuevo proceso.

➢ Asignar espacio para el proceso.

➢ Inicializar el bloque de control de proceso.

➢ Establecer los enlaces apropiados con otras estructuras de

datos.

➢ Ampliar o crear otras estructuras de dato en el caso que

fueran necesarias.
 Muerte de procesos
Cuando un proceso muere ocurren los siguientes pasos:
• Desaparece el PCB
• Recursos comunes son liberados
• Recursos locales son destruidos

Terminación en cascada: Cuando un proceso termina (muere)

también deben terminar sus hijos (normal o anormalmente).

En el caso de los demonios (Daemons ) o servicios, en la creación

muere el proceso padre y pasa a depender del proceso INIT (ej.
En Linux).
Un proceso se puede eliminar manualmente por su propietario o
un superuser con el comando "kill" en Unix
 Hilo o Hebra (Threads)
➢ Un thread es llamado también proceso liviano
(lightweight process) debido a que mantiene la
estructura de un proceso con su PCB
➢ Pero dispone de otra estructura más pequeña
llamada TCB (Thread Control Block) que contiene
una información reducida del PCB, lo que hace que
se ejecute más eficientemente
➢ En sí un proceso es igual a uno o más tareas
(tasks) cada una con su Hilo (thread) asociado.
➢Un Thread (hilo), es una unidad elemental
de uso de CPU

➢Cada hilo posee TID (Thread IDentifier)

un Contador de Programa (PC - Program
Counter), un juego de Registros de CPU
(Register Set) y una Pila (Stack)

➢En muchos sentidos los hilos son como

pequeños miniprocesos.
➢ Cada thread se ejecuta en forma estrictamente
secuencial compartiendo la CPU de la misma forma que
lo hacen los procesos

➢ Solo en un multiprocesador se pueden realizan en

paralelo

➢ Los hilos pueden crear hilos hijos y se pueden bloquear

en espera de llamadas al sistema, al igual que los
procesos regulares

➢ Mientras un hilo está bloqueado se puede ejecutar otro

hilo del mismo proceso

➢ Puesto que cada hilo tiene acceso a cada dirección

virtual (comparten un mismo espacio de
direccionamiento), un hilo puede leer, escribir o limpiar
la pila de otro hilo.
➢ No existe protección entre los hilos debido a que
es imposible y no es necesario, ya que
generalmente cooperan entre sí la mayoría de
las veces

➢ Aparte del espacio de direcciones, comparten el

mismo conjunto de archivos abiertos, procesos
hijos, relojes, señales, etc.

➢ Los procesos livianos dentro de un mismo

proceso pesado no son independientes, pues
cualquiera puede acceder toda la memoria
correspondiente al proceso
 Ventajas con respecto a los
procesos :

• Toma menos tiempo realizar el cambio

para procesar un nuevo thread (del mismo
proceso)- Context switch liviano

• Comparten un mismo espacio de memoria

y datos entre sí debido a que forman parte
de un mismo proceso.
Implementación de hilos ( Threads )

Los hilos pueden ser implementados en dos niveles por la forma

en que son generados y tratados:

➢ Nivel usuario (ULT – User Level Thread) (Green Threads)

➢ Nivel kernel (KLT – Kernel Level Thread)

 Hilos a Nivel de Usuario (ULT):
➢ Todo el trabajo del hilo es manejado por la aplicación, el
kernel no se entera de la existencia de los hilos

➢ Cualquier aplicación puede ser programada para ser

multithreaded mediante el uso de threads library
(paquete de rutinas para ULT)

➢ La generación de los ULT se hace en el momento de

compilación y no se requiere la intervención del Kernel

➢ El kernel no se entera de lo anterior, continúa con la

planificación del proceso como unidad y le asigna un
solo estado de ejecución. (Listo, corriendo, etc.).
 Ventajas:
➢ El cambio de hilo no requiere el modo kernel
➢ El proceso no cambia al modo kernel para
manejar el hilo.
➢ El algoritmo de planificación puede ser
adaptado sin molestar la planificación del SO.
➢ ULT puede correr en cualquier SO.
➢ Es muy rápido en la ejecución
➢ No necesita mecanismos de IPC para
comunicarse con otros threads del mismo
proceso
 Desventajas:
➢ En un SO típico, la mayoría de los system call
son bloqueantes. Cuando un hilo ejecuta un
system call no sólo se bloquea ese hilo, sino
que también se bloquean todos los hilos del
proceso. Se puede utilizar Jacketing
Jacketing: convierte un syscall bloqueante en no bloqueante ->
demora las operaciones de I/O
➢ En una estrategia pura de ULT, una aplicación
multithreaded no puede tomar ventaja del
multiprocesamiento. Un kernel asigna un
proceso a sólo un procesador por vez.
Hilos a nivel de Kernel (KLT):
➢ Todo el trabajo de manejo de hilos es hecho por
el kernel
➢ No hay código de manejo de hilo en el área de
aplicación
➢ Cualquier aplicación puede ser programada
para ser multithreaded
➢ Todos los hilos dentro de una aplicación son
soportados dentro de un solo proceso
➢ El kernel mantiene la información de contexto
para el proceso e individualmente para los hilos
dentro del proceso.
 Ventajas:
➢ Simultáneamente el kernel puede
planificar múltiples hilos del mismo
proceso en múltiples procesadores

➢ Si un hilo de un proceso se bloquea, el

kernel puede planificar otro hilo del
mismo proceso

➢ Las rutinas mismas del kernel pueden

ser multithreaded.
 Desventaja:

• La transferencia de control de un hilo a

otro dentro del mismo proceso le requiere
al kernel un cambio de modo.
Estado de los threads
Dentro de los diferentes estados, los threads se encuentran en la
parte correspondiente al short term schedule.

Entonces los estados en los que puede estar un thread son: listo
(Spawn) , bloqueado (Block), ejecutando ( Running ) o terminado
(Finish).

TERMINADO -
EJ ECUTANDO FINIS H
- RUNNING

LISTO -
SPAWN BLOQUEADO -
BLOCKED
 Uso de los Hilos
• Estructura Servidor Trabajador. Existe un hilo en el
servidor que lee las solicitudes de trabajo en un buzón
del sistema, examina éstas y elige a un hilo trabajador
inactivo y le envía la solicitud. El servidor despierta
entonces al trabajador dormido (un signal al semáforo
asociado).

• Estructura en Equipo. Todos los hilos son iguales y

cada uno obtiene y procesa sus propias solicitudes.

• Estructura de Entubamiento (pipeline). El

primer hilo genera ciertos datos y los transfiere al
siguiente para su procesamiento. Los datos
pasan de hilo en hilo y en cada etapa se lleva a
cabo cierto procesamiento. Esta puede ser una
buena opción para el modelo
productor/consumidor, no así para los servidores
de archivos.
Módulo 3

PLANIFICACIÓN DE
PROCESOS
 Concepto de Planificación
La planificación de procesos se refiere a cómo determina el sistema
operativo al orden en que irá cediendo el uso del procesador a los
procesos que lo vayan solicitando, y a las políticas que empleará para
que el uso que den a dicho tiempo no sea excesivo respecto al uso
esperado del sistema.
 Objetivos de la planificación
• Ser justo: Debe tratarse de igual manera a todos los procesos que
compartan las mismas características, y nunca postergar indefinidamente
uno de ellos (inanición o starvation)
• Maximizar el rendimiento: Dar servicio a la mayor parte de procesos por
unidad de tiempo
• Ser predecible: Un mismo trabajo debe tomar aproximadamente la
misma cantidad de tiempo en completarse independientemente de la
carga del sistema
• Minimizar la sobrecarga: El tiempo que el algoritmo pierda en burocracia
(overhead) debe mantenerse al mínimo, dado que éste es tiempo de
procesamiento útil perdido
• Equilibrar el uso de recursos: Favorecer a los procesos que empleen
recursos subutilizados, penalizar a los que peleen por un recurso
sobreutilizado causando contención en el sistema
• Evitar la postergación indefinida (starvation): Aumentar la prioridad de
los procesos más viejos, para favorecer que alcancen a obtener algún
recurso por el cual estén esperando
 Objetivos de la planificación (cont.)
• Favorecer el uso esperado del sistema: En un sistema con usuarios
interactivos, maximizar la prioridad de los procesos que sirvan a
solicitudes iniciadas por éstos (aún a cambio de penalizar a los
procesos de sistema)
• Dar preferencia a los procesos que podrían causar bloqueo: Si un
proceso de baja prioridad está empleando un recurso del sistema por
el cual más procesos están esperando, favorecer que éste termine de
emplearlo más rápido
• Favorecer a los procesos con un comportamiento deseable: Si un
proceso causa muchas demoras (por ejemplo, atraviesa una ráfaga
de entrada/salida que le requiere hacer muchas llamadas a sistema o
interrupciones), se le puede penalizar porque degrada el rendimiento
global del sistema
• Degradarse suavemente: Si bien el nivel ideal de utilización del
procesador es al 100%, es imposible mantenerse siempre a este nivel.
Un algoritmo puede buscar responder con la menor penalización a
los procesos preexistentes al momento de exceder este umbral
 Tipos de Planificación
• A largo plazo
• Era frecuente en los sistemas por lotes
• Decide qué procesos (o trabajos) serán iniciados
• Se ejecuta periódicamente una vez cada varios segundos, minutos o
incluso horas
• En los sistemas modernos ya no se utiliza más debido a que el usuario
es quien elige qué procesos se ejecutarán
• A mediano plazo
• Decide qué procesos suspender y despertar/activar
• Esto ocurre debido a que los procesos típicamente se bloquean por
escasez de algún recurso (típicamente la memoria principal o
primaria)
• En algunas bibliografías también llamado agendador o scheduler
 Tipos de Planificación (cont.)
• A corto plazo
• Decide cómo compartir momento a momento la CPU entre los
procesos que la requieren
• Se ejecuta decenas de veces por segundo
• Se lo conoce también como despachador o dispatcher

• Relación entre los planificadores y los estados de los

procesos
• El planificador de largo plazo admite nuevos procesos. Se
encarga de la transición del estado nuevo a listo.
• El planificador de mediano plazo maneja las transiciones entre
estados suspendidos y estados activos, y viceversa.
• El planificado de corto plazo administra las transiciones entre
listo y ejecutando.
 Tipos de Procesos
• CPU Bound u Orientados al uso de CPU
• Los que típicamente realizan mucho cómputo interno y su ejecución
está típicamente alternada por ráfagas o bursts

• I/O Bound u Orientados a la E/S

• Los que centran su atención en transmitir datos desde o hacia los
dispositivos externos

• Procesos largos
• Aquéllos que por "mucho tiempo" han estado en listos o en ejecución.
Los que han estado en una larga ráfaga de CPU

• Procesos cortos
• Aquéllos que son de tipo I/O Bound pero ocasionalmente se
encuentran en ejecución o tienden a estar bloqueados a la espera de
eventos, típico de los procesos interactivos
 Tipos de Procesos (cont.)
• Generalmente lo que se busca en un planificador a corto plazo es dar
un tratamiento preferente a los procesos cortos, en particular a los
interactivos.
 Midiendo la respuesta
• Cada patrón de uso del sistema debe seguir políticas de planificación
diferentes.
Por ejemplo, para los procesos interactivos se pretende tener una cola
preferente, aunque cuando hay demoras es preferible dar una respuesta
consistente, aunque el promedio del tiempo de respuesta sea mayor.
• Se definen como medidas de tiempo el tick y el quantum

• Tick: Una fracción de tiempo en donde se puede realizar trabajo útil, es

decir, usar la CPU sin interrupción. Su duración lo determina el timer del
sistema.
En Linux el tick es de 1 milli segundo, y en Windows entre 10 y 15 ms

• Quantum: El tiempo máximo que se le permitirá a un proceso el uso del

procesador (por cada turno de ejecución).
En Linux el quantum varía entre 10 y 200 ticks (10 y 200 ms), y en Windows
entre 2 y 12 ticks (10 y 180 ms)
 Métricas Utilizadas
Para un proceso p que requiere de un tiempo t de ejecución:

• Tiempo de respuesta (T): Tiempo total necesario para completar el

trabajo pendiente de un proceso p, incluyendo el tiempo que está
inactivo esperando ejecución (pero está en la cola de procesos
listos).
• Tiempo en espera (E = T − t): También tiempo perdido. Del tiempo de
respuesta total, cuánto tiempo p está listo y esperando ejecutar.
Desde la óptica de p, se desearía que Ep → 0
• Proporción de penalización : Proporción del tiempo de
respuesta en relación al tiempo de uso del procesador (en qué
proporción fue penalizado el proceso).
• Proporción de respuesta : Inverso de P. Fracción del tiempo
de respuesta durante la cual p pudo ejecutarse.
 Métricas Utilizadas (cont.)
• Tiempo núcleo o kernel: Tiempo que pasa el sistema en espacio de
núcleo, incluyendo entre otras funciones el empleado en decidir e
implementar la política de planificación y los cambios de contexto.
Este tiempo no se contabiliza cuando se calcula el tiempo del CPU
utilizado por un proceso
• Tiempo de sistema: Tiempo que pasa un proceso en espacio núcleo
atendiendo el pedido de un proceso (syscall). Se incluye dentro del
tiempo de uso del CPU de un proceso y suele discriminarse del
tiempo de usuario
• Tiempo de usuario: Tiempo que pasa un proceso en modo usuario,
es decir, ejecutando las instrucciones que forman parte explícita y
directamente del programa
• Tiempo de uso del procesador: Tiempo durante el cual el
procesador ejecutó instrucciones por cuenta de un proceso (sean en
modo usuario o en modo núcleo)
• Tiempo desocupado (idle): Tiempo en que la cola de procesos listos
está vacía y no puede realizarse ningún trabajo
 Métricas Utilizadas (cont.)
• Utilización del CPU: Porcentaje del tiempo en que el CPU está
realizando trabajo útil
• Valor de saturación: Relación entre la frecuencia α de llegada
promedio de nuevos procesos y el tiempo de servicio requerido
promedio β (letra griega beta). Se define el valor de saturación ρ
como ρ = α/ β.
Cuando ρ = 0 nunca llegan procesos nuevos. Sistema desocupado.
Cuando ρ = 1 los procesos se despachan al ritmo que van llegando.
• Cuando ρ > 1 el sistema estará saturado. La cola de listos comenzará
a crecer y la calidad de servicio, proporción de respuesta R para cada
proceso se decrementará
 Algoritmos de Planificación
Dos tipos de sistemas o de planificación:

• Sistemas Cooperativos, no expropiativos o Non-Preemptive: Son

aquellos en donde el SO NO interrumpe al proceso en ejecución. Es
éste el que cede el uso del procesador, o bien a través de una
instrucción Yield (ceder paso) o debido a un Syscall (llamada al
sistema)
• Sistemas expropiativos o Preemptive: Son aquellos donde el reloj
(timer) del sistema interrumpe periódicamente al proceso en
ejecución para devolver el control al SO y que éste decida qué
proceso será el próximo en ejecutarse
 Algoritmos de Planificación (cont.)
¿Cuándo se ejecuta el planificador de corto plazo?

1. Cuando el proceso pasa de ejecutando a bloqueado (ej. Syscall)

2. Cuando el proceso pasa de ejecutando a listos (ej. Interrupción por
Quantum)
3. Cuando el proceso pasa de bloqueado a listos (ej. Interrupción de
finalización de E/S)
4. Cuando el proceso pasa de ejecutando a terminado (ej. exit())
Primero en llegar, primero servido (FCFS)
• Utiliza multitarea no apropiativa o non-preemtive
• Es el algoritmo más simple. El primero que llega a la cola de listos es
el primero en ser atendido (First Come, First Serve)
• Reduce al mínimo la sobrecarga administrativa (overhead) ya que es
muy simple de implementar
• El rendimiento percibido por los últimos procesos en llegar resulta
muchas veces inaceptable
• Este algoritmo da salida a todos los procesos siempre que ρ ≤ 1.
Si ρ > 1 la demora en iniciar a los nuevos procesos aumentará cada
vez produciéndose inanición
Primero en llegar, primero servido (FCFS) (cont.)
Ejemplo:

• Notar qué malo es para los procesos interactivos (proceso C), donde
la proporción de respuesta R es muy mala
 Ronda (Round Robin)
• Emplea multitarea apropiativa o preemptive
• Busca dar una relación de respuesta buena para los procesos largos
y cortos
• Cada proceso listo a ejecutarse puede hacerlo por un solo quantum
• Si un proceso no ha concluido dentro de su quantum se lo expulsará
y será puesto al final en la cola de listos donde deberá esperar
su turno nuevamente
• Los procesos que son despertados de estado de suspensión son
también puestos al final de la cola de listos
 Ronda (Round Robin) (cont.)
Ejemplo:

Ejemplo de Round Robin con quantum de 1 tick

 Ronda (Round Robin) (cont.)
Ejemplo:

Ejemplo de Round Robin con quantum de 4 ticks

 Ronda (Round Robin) (cont.)
Conclusiones:

• La ronda puede ajustarse modificando la duración del quantum

• Cuando más grande es el quantum, más se parece a FCFS
• Se puede observar que aumentar el quantum mejora los tiempos
promedios de respuestas, pero penaliza a los procesos cortos
pudiendo llevar a la inanición (si ρ > 1)
• Mediciones estadísticas indican que el quantum debería mantenerse
por debajo al 80% a la duración promedio de los procesos
(Silberschatz, Galvin y Gagne 2010: 188)
 El proceso más corto a continuación
(SPN, Shortest Process Next)
• Utiliza multitarea no apropiativa o non-preemtive
• Se necesita información por adelantado acerca del tiempo requerido
por cada proceso
• Es más justo que FCFS
• Como es difícil contar con la duración del proceso, se tiende a
caracterizar sus necesidades. Para eso se nutre de la información de
contabilidad del propio proceso (examina las ráfagas pasadas y
concluye si es un proceso tendiendo a I/O Bound o CPU Bound)
• Para la estimación de la próxima ejecución se utiliza el promedio
exponencial ep . Además, se define un factor atenuante 0 ≤ f ≤ 1 que
indica cuán reactivo será dicho promedio a la última ráfaga de
ejecución. Si por ejemplo el proceso p empleó q quantums en su
última ráfaga de ejecución:
e′p = f e p + ( 1 − f ) q

Para el primer ep (semilla) se puede tomar el ep de los procesos

actualmente en ejecución.
 El proceso más corto a continuación
(SPN, Shortest Process Next) (cont.)
Ejemplo:
 El proceso más corto a continuación
(SPN, Shortest Process Next) (cont.)
Conclusiones:

• SPN favorece a los procesos cortos

• Un proceso largo puede esperar mucho para su ejecución,
especialmente con un ρ = 1 ó superior
• Un proceso más largo que el promedio está predispuesto a sufrir
inanición
• En un sistema poco ocupado, con una cola de listos corta, SPN tiende
a arrojar resultados similares a FCFS
 SPN apropiativo
(PSPN, Preemptive Shortest Process Next)
• Combina las estrategias de SPN con un esquema apropiativo
• El comportamiento obtenido es similar para la amplia mayoría de los
procesos
• A los procesos muy largos no los penaliza mucho más que el Round
Robin
• Obtiene mejores promedios en forma consistente debido a que
mantiene la cola más corta por despachar a los procesos más cortos
primeros
 El más penalizado a continuación
(HPRN, Highest Penalty Ratio Next)
• Trabaja con esquemas No Apropiativos o Non-Preemptive
• Intenta situarse en un nivel de justicia entre el FCFS (que favorece a
los procesos largos) y SPN (que favores a los procesos cortos)
• Al comienzo todos los procesos tienen una penalización P = 1. Cada
vez que un proceso espera un tiempo w, la penalización del mismo se
ajusta por P = (w + t) / t. El proceso que se elige como el próximo será
el que tenga mayor P
• Mientras que ρ < 1 este algoritmo incluso evita que los procesos más
largos sufran inanición
• Se han realizado experimentos (Finkel) y los resultados siempre
arrojan que este algoritmo se sitúa entre FCFS y SPN
• Su principal desventaja se presenta cuando la cola de listos es muy
larga ya que el planificador tiene que calcular P para cada uno de los
procesos cada vez que se ejecuta
Ronda Egoísta (SRR, Selfish Round Robin)
• Intenta favorecer a los procesos que ya han pasado tiempo
ejecutando sobre los que recién llegan al sistema
• Los procesos nuevos entran en una cola de Procesos Nuevos y sólo se
avanza con la ejecución de los procesos en la cola Procesos Aceptados
• Trabaja con dos parámetros principales. El parámetro a indica cómo
se incrementará la prioridad de los procesos en la cola Procesos
Nuevos.
El parámetro b indica cómo se incrementa la prioridad de los
procesos aceptados
• Cuando la prioridad de un proceso nuevo alcanza la prioridad de un
proceso aceptado el proceso nuevo se convierte en aceptado
• Si la cola de procesos aceptados queda vacía se acepta el proceso
nuevo con mayor prioridad
Ronda Egoísta (SRR, Selfish Round Robin) (cont.)
Ejemplo:

Ronda Egoísta con a = 2 y b = 1

Ronda Egoísta (SRR, Selfish Round Robin) (cont.)
Conclusiones:
• Mientras que b/a < 1 la prioridad de un proceso nuevo eventualmente
alcanzará a la de los procesos aceptados
• Si b/a ≥ 1 el proceso en ejecución termina y el nuevo es aceptado y
pasa a ejecutarse. En este caso el algoritmo se convierte en FCFS
• Si b/a = 0 los procesos nuevos serán aceptados inmediatamente
conviertiéndose en un Round Robin normal.
• Mientras que 0 < b/a < 1 la ronda se comporta relativamente en forma
egoísta aceptando a los procesos nuevos incluso si los que llevan
mucho tiempo ejecutando son muy largos (y por ende con mucha
prioridad)
Algoritmos con múltiples colas de listos
Para poder entender el próximo algoritmo, multilevel feedback), primero
se analiza cómo funciona típicamente un sistema con múltiples colas de
listos.

• Se definen múltiples colas (en el ejemplo 5) cada una con una

prioridad
• Se atienden sólo los procesos de la cola de más prioridad hasta que
ésta se vacía (por terminación de sus procesos o porque los mismos
fueron migrados a una de menor prioridad). Luego se pasa a ejecutar
los procesos de la cola siguiente
• Puede haber colas vacías
 Retroalimentación multinivel
(FB, multilevel FeedBack)
• Múltiples colas según la prioridad (C0 a Cn)
• Se escoge al primer proceso de la cola más prioritaria con procesos
en ella (Ci)
• Tras un predeterminado de ejecuciones del proceso escogido, el
mismo es degradado a la siguiente cola (Ci+1) y se ejecuta el siguiente
proceso en la cola más prioritaria
• Favorece a los procesos cortos, ya que éstos terminan antes de
degradarse
• Permite ajustar dos variables:
• Cantidad de ejecuciones del proceso antes de ser degradado
• Duración del quantum
 Retroalimentación multinivel
(FB, multilevel FeedBack) (cont.)
Ejemplo:

Retroalimentación multinivel (FB) básica

Cantidad de ejecuciones antes de degradar = 1; quantum = 1
 Retroalimentación multinivel
(FB, multilevel FeedBack) (cont.)
Otro ejemplo:

Retroalimentación multinivel (FB) básica

Cantidad de ejecuciones antes de degradar = 1; quantum = 2nq
 Retroalimentación multinivel
(FB, multilevel FeedBack) (cont.)
Notas sobre el ejemplo anterior y consideraciones generales
• En este caso el quantum = 2nq, donde n es el identificador de la cola y
q la longitud del quantum base
• Con estos valores un proceso llevará un total de cambios de contexto
igual a log (t(p)/q) lo cual es más atractivo que el caso anterior donde
la cantidad de cambios de contexto de un proceso era igual a t(p)/q
• Mejor mucho el rendimiento general sobre el primer caso con q=1
• En la práctica se elijen incrementos de q más suaves como nq o
incluso [Link](n)
• Para evitar la inanición se puede utilizar la retroalimentación en
sentido inverso, donde un proceso en la cola Cp que pasa un
determinado tiempo sin recibir servicio de lo promueve a una cola
más prioritaria Cp-1
• Los sistemas de hoy en día utilizan alguna variación de sistemas con
retroalimentación multinivel y con hasta docenas de colas
 Lotería
• Se basa en un esquema de probabilidades para escoger al próximo
proceso a ejecutar
• A cada proceso se le asigna un número determinado de boletos
• Cada vez que el planificador de corto plazo se ejecuta, elije un
número aleatorio. El proceso que tiene el boleto con ese número es el
que obtiene el siguiente quantum de ejecución (el algoritmo de
generación de números aleatorios no es tan refinado, siendo en
realidad pseudoaleatorio, y con solo 12 instrucciones RISC se ejecuta)
• Cuantos más números de boleto tiene un proceso, más prioridades
tiene de ser elegido
• A pesar de ser simple, es muy justo, tanto para procesos cortos como
largos
• No se puede poner un ejemplo ya que su base radica en la
aleatoriedad
Resumen y características de los algoritmos
Hasta ahora los algoritmos vistos se podrían calificar según dos criterios:
1. Aquellos que se utilizan en sistemas preemptive y otros que se
utilizan en sistemas non-preemptive
2. Aquellos que utilizan información intrínseca a los procesos (son
tratados de diferente manera según si historial de ejecución) y
aquellos no consideran esa información

Como resumen:
 Algoritmos híbridos
En la filmina anterior vimos las características de cada algoritmo y los
encasillamos según éstas.
Sin embargo, las mismas se pueden combinar dentro de un mismo
algoritmo dando lugar a lo que llamamos "Algoritmos Híbridos".

Algoritmo por cola dentro de FB

A diferencia del FB tradicional, cada cola tiene un tratamiento diferente.

Por ejemplo, parte de las colas podría tener una especie de algoritmo
PSPN que empuje a los procesos más largos a colas que le permitan
tener menos interrupciones.
Las colas de menor prioridad podrían aplicar un SRR ya que ahí residen
procesos que ya han esperado mucho tiempo para su ejecución, para
que terminen lo antes posible su ejecución, sin esto alterar los tiempos
de respuesta de procesos cortos que van entrando a las colas superiores
 Algoritmos híbridos (cont.)
Métodos dependientes del estado del sistema

La idea de estos es que algoritmo se nutra del estado actual del sistema
e incluso de variables ajenas al dispatcher. Algunas ideas:
• Si los procesos listos son en promedio no muy largos y la saturación
del sistema en baja (ρ < 1) elegir algoritmos con poco overhead
(FCFS o SPN). Si la cola de listos comienza a crecer o el sistema
comienza a saturarse, cambiar por ejemplo a RR con quantum corto o
PSPN que garantiza una mejor distribución de la atención
• Usar un RR simple con quantum variable periódicamente (por
ejemplo con cada cambio de contexto o un cálculo periódico) de tal
manera que sea proporcional a la cantidad de procesos en la cola de
listos: Q = q/n.
Si hay pocos procesos esperando, su quantum será mayor, lo que
reduce la cantidad de cambios de contexto. Si hay muchos, cada uno
de ellos deberá esperar menos para comenzar con sus tareas.
 Algoritmos híbridos (cont.)
• Utilizar un RR pero con quantum proporcional a la prioridad externa
(definida por el usuario). A más prioridad, quantum más largo
• Peor Servicio a Continuación (WSN, Worst Service Next). Su principal
diferencia con respecto a HPRN es que no sólo se considera
penalización al tiempo esperado, sino que también considera las
veces que el temporizador lo interrumpió o su prioridad externa y se
considera (a favor o en contra) el tiempo esperado por E/S.
La gran desventaja es el overhead de tener que considerar tantas
variables. Una solución a otra es acudir a WNS periódicamente y no
en cada intervención del dispatcher, para que reordene las colas
según los criterios generales, aunque esto repercute negativamente
con respecto al tiempo de reacción del algoritmo antes cambios de
comportamiento.
• Algunas versiones de Unix utilizan un esquema en donde la
prioridade definida por el usuario era matizada y reevaluada durante
el transcurso de su ejecución. Se maneja una prioridad interna que
depende de la externa y el tiempo consumido recientemente por el
proceso (conocido como lindura o niceness. Ver comando nice)
 Planificación de hilos
Para la planificación de hilos depende de cómo éstos son mapeados a
procesos desde el punto de vista del planificador.
Los hilos pueden ser de dos tipos:
• Hilos de usuario o hilos verdes (ULT): Sólo son conocidos por el
proceso que los crea y gestionados por él
• Hilos de núcleo o kernel (KLT): Son conocidos por el SO y gestionados
por él. El SO tiene que tener soporte para la creación y gestión de
este tipo de hilos

En base a este tipo de hilos existen los siguientes tipos de mapeos:

 Planificación de hilos (cont.)
• Muchos a uno: Muchos hilos son agrupados dentro de un mismo
proceso. Los ULT entran dentro de esta categoría. Para el SO hay un
solo proceso en ejecución. En este tipo de hilos no se aprovecha
realmente el paralelismo.
Si un hilo se bloquea hace que todos los demás también se tengan
que bloquear.
• Uno a uno: Cada hilo es ejecutado como un proceso ligero
(lightweight process o LWP). Son más rápidos de crear y gestionar que
un proceso pesado ya que la información de estado que se necesita
para esto es mucho menor.
Comparten el espacio de memoria, descriptores de archivos y demás
estructuras.
Aprovechan el paralelismo ya que cada hilo puede ejecutar en un
procesador diferente.
 Planificación de hilos (cont.)
• Muchos a muchos: Este mecanismo permite que haya hilos de ambos
modelos:
• Hilos unidos (bound threads): Cada hilo corresponde a un solo LWP
• Hilos no unidos (unbound threads): Uno o más hilos están mapeados a cada LWP
 Planificación de multiprocesadores
Básicamente para la planificación de múltiples procesadores se manejan
dos enfoques:
• Mantener una sola lista de procesos y despacharlos a cada
procesador como si éstos fueran unidades de ejecución equivalentes
e idénticas
• Mantener listas de procesos separadas para cada procesador
Planificación de multiprocesadores (cont.)
Afinidad a procesador

Los procesadores actuales contienen varios niveles de cache (L1, L2 y L3).

Resulta obvio tratar de mantener a un proceso ejecutando en el mismo
procesador para no tener que invalidad sus entradas en el cache cuando el
mismo es migrado a otro procesador.
La afinidad a un procesador indica la preferencia de un proceso a ejecutarse en
un determinado procesador. Puede ser:
• Afinidad suave: El planificador setea una preferencia a que determinado
proceso se ejecute en un determinado procesador. Sin embargo, diferentes
patrones de carga en el sistema pueden hacer que el proceso sea migrado a
otro procesador
• Afinidad dura: Se da cuando en determinados SO se le permite al usuario
declarar una afinidad en la cual se restringe el/los procesador/es a ser
utilizado/s para un determinado proceso
Un entorno NUMA funcionará mejor si el sistema maneja un esquema de
afinidad dura que le permita al proceso ejecutar donde sus datos estén más
"cerca"
Planificación de multiprocesadores (cont.)
Balanceo de carga

El balanceo de carga actúa cuando la divergencia en la carga de cada uno de los

procesadores se vuelve grande, migrando procesos entre las colas de listos de un
procesador a otro para homogeneizarlas.
Esta técnica puede ir en sentido contrario a la afinidad que vimos anteriormente.
Existen dos técnicas de balanceo de carga:
• Migración activa o por empuje (push migration): Periódicamente se ejecuta una
tarea que analiza la ocupación de los procesadores, y si la misma pasa de
determinado umbral, migra el proceso de la cola de dicho procesador a la cola
del procesador más desocupado. Linux ejecuta esta tarea cada 200 ms
• Migración pasiva o por jalón (pull migration): Cuando un procesador queda
ocioso, ejecuta la tarea idle, que entre otras cosas en lugar de parar al
procesador analiza la ocupación de los procesadores activos. Si hay
procesadores muy ocupados, jala algún proceso para migrarlo a su propia
cola
Ambas tareas son generalmente utilizadas en los SO modernos.
Nota: Cualquier tipo de migración conlleverá una penalización en términos de
afinidad de CPU.
Planificación de multiprocesadores (cont.)
Una sola cola de listos para todos los procesadores

En esta técnica se utiiza una sola cola de listos para todos los procesadores. A
medida que un procesador queda libre se escoge el primer proceso en la cola.
Esto hace que incluso se ahorre la implementación de las tareas de migración
vistas anteriormente.
Sin embargo, este enfoque no es utilizado hoy en día en ningún SO masivo.
Básicamente porque el mismo casi imposibilita la afinidad de CPU.
Planificación de multiprocesadores (cont.)
Procesadores con soporte de hilos de hardware

Este tema puede llevar a confusión con los hilos de los procesos que se han visto
anteriormente. Éste es un concepto diferente. Se refiere a que un mismo
procesador le presenta al sistema operativo dos unidades de ejecución
diferentes. Esto se conoce en el mercado como HyperThreading.
La idea sobre la cual se cimienta esto es que el procesador tiene múltiples
unidades de ejecución (pipelines por ejemplo, o incluso otras unidades), las
cuales muchas veces algunas se mantienen ociosas mientras se ejecuta una
determinada instrucción que sólo utiliza unas pocas.
Por lo tanto, si se logra intercalar instrucciones que utilicen diferentes unidades,
entonces dichas instrucciones se podrán ejecutar en paralelo.

Obsérvese cómo aparecen tiempos muertos por espera del procesador. En estos
casos, ambas instrucciones están queriendo utilizar las mismas unidades de
ejecución, por lo tanto, una de las dos debe esperar
MODULO 4

SINCRONIZACIÓN Y
COMUNICACIÓN ENTRE
PROCESOS
 Sincronización y comunicación
entre procesos

➢En los sistemas operativos, en general, los procesos que trabajan

juntos comparten con frecuencia un espacio común para
almacenamiento, en el que cada uno puede leer o escribir, o
también comparten un recurso.

➢El acceso a estos recursos compartidos generan problemas de uso

y de comunicación entre los procesos.

➢Para resolver estos problemas de competencia entre procesos, se

utilizan dos mecanismos: la sincronización y la comunicación.
 Definimos a ambos términos como:

➢SINCRONIZACIÓN ENTRE PROCESOS: Ordenamiento de las

operaciones en el tiempo debido a las condiciones de carrera
(acceder a los diversos recursos asincrónicamente).

➢COMUNICACIÓN ENTRE PROCESOS: Intercambio de Datos.

La comunicación permite que los procesos cooperen entre sí en
la ejecución de un objetivo global, mientras que la sincronización
permite que un proceso continúe su ejecución después de la
ocurrencia de un determinado evento.
 Problemas Concurrentes:
Los programas pueden ser clasificados en secuenciales y en concurrentes.

Un programa secuencial especifica una secuencia de instrucciones que se

ejecutan sobre un procesador que definimos como proceso o tarea.
Un programa concurrente especifica dos o más procesos secuenciales que
pueden ejecutarse concurrentemente como tareas paralelas.

Un proceso secuencial se caracteriza por no ser dependiente de la velocidad

de ejecución y de producir el mismo resultado para un mismo conjunto de
datos de entrada, mientras que en un proceso concurrente (o lógicamente
paralelo) las actividades están superpuestas en el tiempo (una operación
puede ser comenzada en función de la ocurrencia de algún evento, antes de
que termine la operación que se estaba ejecutando).

La programación concurrente requiere de mecanismos de sincronización y

comunicación entre los procesos.
 Concurrencia
• Desde un punto de vista formal, la concurrencia no se
refiere a dos o más eventos que ocurren a la vez sino a dos
o más eventos cuyo orden es no determinista, esto es,
eventos acerca de los cuales no se puede predecir el orden
relativo en que ocurrirán.

• Si bien dos procesos (o también dos hilos) completamente

independientes entre sí ejecutándose simultáneamente
son concurrentes, nos ocuparemos principalmente de
procesos cuya ejecución está vinculada de alguna manera.
 Algunos conceptos de concurrencia
Operación atómica: Manipulación de datos que requiere la garantía de que se ejecutará como una
sola unidad de ejecución, o fallará completamente, sin resultados o estados parciales
observables por otros procesos o el entorno. Esto no necesariamente implica que el sistema no
retirará el flujo de ejecución en medio de la operación, sino que el efecto de que se le retire el
flujo no llevará a un comportamiento inconsistente

Race condition: Situación en la cual el resultado de la ejecución de 2 o más

procesos interactuantes depende del orden de ejecución de los mismos.

Sección (o región) crítica : Es la fase o etapa en la vida de ese proceso concurrente en la cual
accede a un recurso crítico para modificarlo o alterarlo El área de código que requiere ser
protegida de accesos simultáneos donde se realiza la modificación de datos compartidos.

Recurso compartido: Un recurso al que se puede tener acceso desde más de un

proceso. En muchos escenarios esto es un variable en memoria (como cuenta en el jardín
ornamental), pero podrían ser archivos, periféricos, etcétera.

Mutua exclusión: sólo un proceso a la vez puede estar ejecutando en su región crítica (lo accede y
lo usa).
• Es función del programador asegurar la atomicidad
de forma explícita, mediante la sincronización de
los procesos.

• El sistema no debe permitir la ejecución de parte

de esa área en dos procesos de forma simultánea
(sólo puede haber un proceso en la sección crítica
en un momento dado).
 Especificaciones concurrentes:

Instrucciones FORK - JOIN

La instrucción fork (tenedor, horqueta, separador) indica el

comienzo de la concurrencia

join recombina (junta) la concurrencia en una sola instrucción

indicando que ha concluido la concurrencia.

La instrucción fork etiq produce dos ejecuciones concurrentes en

un programa.
• sent1;
• sent2;
• fork etiq;
fork etiq
• ...
• join; ... etiq
• ...
• end; join ...

• etiq: sent1; quit

• sent2;
• ...
• sentn;
• quit;
 Resumen de fork y join
➢fork es, en esencia, un goto que simultáneamente bifurca y
continúa la ejecución.

➢quit y join permiten que dos ramas de actividad vuelvan a

juntarse.

➢quit: Lo ejecuta el proceso hijo cuando terminó su tarea.

➢join: Lo ejecuta el proceso padre para esperar a que termine el

hijo.

No es estructurado por su estructura de control.

 Grafos de precedencia
Un grafo de precedencia es un grafo sin ciclos donde cada nodo
representa una única sentencia o un conjunto secuencial de
instrucciones
Condiciones de concurrencia (Bernstein)
• Definición: Dos sentencias cualesquiera Si y Sj pueden
ejecutarse concurrentemente produciendo el mismo
resultado que si se ejecutaran secuencialmente sí sólo sí se
cumplen las siguientes condiciones:

• 1. R (Si)  W (Sj) = (ø )
• 2. W(Si)  R (Sj) = (ø )
• 3. W(Si)  W (Sj) = (ø )

• Si las tres condiciones producen conjunto vacío, podemos

asegurar que no hay dependencia entre las sentencias.
➢Conjunto de Lectura: R (Si) = ( a1, a2,... , am)
El conjunto de lectura de la sentencia Si es aquel formado por
todas las variables que son referenciadas por la sentencia Si
durante su ejecución sin sufrir cambios.

➢Conjunto de escritura: W (Si) = (b1, b2,... , bn)

El conjunto de escritura de la sentencia Si es aquel formado por
todas las variables cuyos valores son modificados durante la
ejecución de Si.
Problema del jardín ornamental
 Problema del jardín ornamental

Lo esperable es que el valor de la variable cuenta termine

en 40, pero no siempre ocurre. ¿Cuál es la razón?

La instrucción cuenta = cuenta + 1 se descompone en

las siguientes instrucciones (en arquitecturas Intel x86):
LEER Leer cuenta desde la memoria (mov $cuenta,%rax).
INC Incrementar el registro (add $1,%rax).
GUARDAR Guardar el resultado nuevamente en memoria (mov%rax,$cuenta).

Supongamos que en medio de estas operaciones ocurre un

process-switch … ¿Qué ocurre con el valor de cuenta?
Las soluciones comunes al problema de
mutua exclusión siguen un protocolo de
tres pasos.

Protocolo de negociación (de entrada

a la Región Critica)
Mutua exclusión (RC)
• {
Uso de la Región Critica
• entradaRC();
• usarRecurso();
• salidaRC(); Protocolo de Liberación (salida de la
Región critica)
}
 Posibles soluciones al problema del
Jardín ornamental
Problema: cuenta = cuenta + 1 Debe ser atómica!

• Intento 1: No utilizar multitarea

En este sencillo ejemplo una posible solución es utilizar únicamente

una entrada (o torniquete). Esto podría ser una solución en tanto que
no haya mucha gente que haga cola para entrar.
Sin embargo, en un sistema análogo de reserva de pasajes aéreos no
parece tener mucho sentido que todos los pasajeros deban ir a Japón
a sacar su pasaje. Por otro lado, ya deberían ser claras las ventajas de
la multitarea y el poseer distintos núcleos.
! Costoso
• Intento 2: Suspender la multitarea durante la sección
crítica

Una versión más relajada de la alternativa anterior es

suspender la multitarea durante la ejecución de la sección
crítica. Así, un torniquete deberá hacer:

• 1 disable(); /* Suspender temporal las interrupciones */

• 2 cuenta = cuenta + 1;
• 3 enable(); /* Habilitar nuevamente las interrupciones */

• ! Inviable en multiusuarios:
• Deshabilitar en forma indefinida y capturar el CPU
• No funciona en multicore ya que solo se deshabilitan interrupciones por procesador
• Posibles errores de dispositivos si el tiempo en la sección crítica es muy largo
• Intento 3: Utilizar una bandera

Utilizar una bandera parece ser una solución muy sencilla: mediante
una variable de bandera se indica si hay un proceso en la región
crítica:

1 int bandera = 0; /* 0 => región crítica libre, 1 => ocupada */

2 int cuenta = 0;
3 /* ... */
4
5 /* Torniquete1 */
6 /* ... */
7 if (bandera) wait;
8 /* Aquí bandera=0 */ Falla!!!
9 bandera = 1; /* Inicio de la sección crítica */ bandera es un
10 cuenta = cuenta + 1; rec compartido y
11 bandera = 0; /* Fin de la sección crítica */ su acceso no es
atómico
• Intento 4: Manejar la bandera con instrucciones
atómicas

Algunas arquitecturas de computadoras permiten

realizar determinadas operaciones sencillas (como
actualizar una bandera) de forma atómica (p. ej.: VAX tiene
la instrucción test_and_set y el i386 tiene la instrucción INC.
Usando esto, la solución es:

1 int bandera; /* 0 => desocupada */

Falla!!!
2
Puede generar
3 while (++bandera != 1) { inanición si un
4 bandera--; /* Debe generar "INC" */ proceso no libera
5 } el recurso.
6 /* Sección crítica */ También usa
7 cuenta = cuenta + 1;
"espera
8
ocupada"
9 bandera--;
• Intento 5: Utilizar turnos

Una alternativa para evitar el problema de la actualización múltiple a una

bandera es emplear una variable adicional que indique a qué proceso
corresponde avanzar en todo momento, esto es, utilizar turnos:

Asumimos la existencia de dos procesos 0 y 1.

• 1 while (turno != i) {
• 2 esperar(); /* ¿Otro proceso? */
• 3}
• 4 /* Sección crítica */
• 5 cuenta = cuenta + 1;
• 6 turno = 1-i;

Si turno = 0 y P1 está listo para entrar entonces debe esperar, aunque P0

no esté en Región Critica.
 Semáforos

• Edsger Dijkstra, en 1968, propuso los semáforos

Un semáforo es una herramienta genérica de sincronización de

procesos, o sea, permite el ordenamiento de las operaciones que
realizan los procesos en el tiempo.

Un semáforo es una variable de tipo entero que tiene definida la

siguiente interfaz:
• Inicialización Se puede inicializar el semáforo a cualquier valor
entero, pero después de esto, su valor no puede ya ser leído. Un
semáforo es una estructura abstracta, y su valor es tomado
como opaco (invisible) al programador.
• Decrementar Cuando un hilo decrementa el semáforo, si el
valor es negativo, el hilo se bloquea y no puede continuar hasta
que otro hilo incremente el semáforo. Según la
implementación, esta operación puede denominarse wait,
down, acquire o incluso P (por ser la inicial de proberen te
verlagen, intentar decrementar en holandés, del planteamiento
original en el artículo de Djkstra).
• Incrementar Cuando un hilo incrementa el semáforo, si hay
hilos esperando, uno de ellos es despertado. Los nombres que
recibe esta operación son signal, up, release, post o V (de
verhogen, incrementar).

• La característica fundamental de estos operadores:

Su ejecución es indivisible o sea atómica
Un semáforo permite la implementación de varios patrones,
entre los cuales se mencionarán los siguientes:

Señalizar

Un hilo debe informar a otro que cierta condición está ya

cumplida
—por ejemplo, un hilo prepara una conexión en red mientras
que otro calcula lo que tiene que enviar. No se puede arriesgar a
comenzar a enviar antes de que la conexión esté lista. Se
inicializa el semáforo a 0, y:
• 1 # Antes de lanzar los hilos
• 2 from threading import Semaphore
• 3 senal = Semaphore(0)
• 4
• 5 def envia_datos():
• 6 calcula_datos()
• 7 P(senal)
• 8 envia_por_red()
• 9
• 10 def prepara_conexion():
• 11 crea_conexion()
• 12 V(senal)
 Rendezvous

Así se denomina en francés (y ha sido adoptado al inglés) a

quedar en una cita. Este patrón busca que dos hilos se esperen
mutuamente en cierto punto para continuar en conjunto —por
ejemplo, en una aplicación GUI, un hilo prepara la interfaz gráfica
y actualiza sus eventos mientras otro efectúa cálculos para
mostrar. Se desea presentar al usuario la simulación desde el
principio, así que no debe empezar a calcular antes de que el GUI
esté listo, pero preparar los datos del cálculo toma tiempo, y no
se quiere esperar doblemente. Para esto, se implementan dos
semáforos señalizándose mutuamente:
• 1 from threading import Semaphore, Thread
• 2 guiListo = Semaphore(0)
• 3 calculoListo = Semaphore(0)
• 4
• 5 Thread(target=maneja_gui, args=[ ]).start()
• 6 Thread(target=maneja_calculo, args=[ ]).start()
• 7
• 8 def maneja_gui():
• 9 inicializa_gui()
• 10 V(guiListo)
• 11 P(calculoListo)
• 12 recibe_eventos()
• 13
• 14 def maneja_calculo():
• 15 inicializa_datos()
• 16 V(calculoListo)
• 17 P(guiListo)
• 18 procesa_calculo()
 Mutex

El uso de un semáforo inicializado a uno puede implementar

fácilmente un mutex

• 1 mutex = Semaphore(1)
• 2 # ...Inicializar estado y lanzar hilos
• 3 P(mutex)
• 4 # Aquí se está en la region de exclusión mutua
• 5x=x+1
• 6 V(mutex)
• 7 # Continúa la ejecucion paralelaex. En Python:
 Multiplex

Permite la entrada de no más de n procesos a la región

crítica. Si se lo ve como una generalización del mutex, basta
con inicializar al semáforo al número máximo de procesos
deseado. Su construcción es idéntica a la de un mutex, pero
es inicializado al número de procesos que se quiere permitir
que ejecuten de forma simultánea.
 Torniquete
Una construcción que por sí sola no hace mucho, pero resulta útil para patrones
posteriores. Esta construcción garantiza que un grupo de hilos o procesos pasa
por un punto determinado de uno en uno (incluso en un ambiente
multiprocesador):

• 1 torniquete = Semaphore(0)
• 2 # (...)
• 3 if alguna_condicion():
• 4 V(torniquete)
• 5 # (...)
• 6 P(torniquete)
• 7 V(torniquete)

En este caso, se ve primero una señalización que hace que todos los procesos
esperen frente al torniquete hasta que alguno marque que alguna_condicion()
se ha cumplido y libere el paso. Posteriormente, los procesos que esperan
pasarán ordenadamente por el torniquete. El torniquete por sí solo no es tan
útil, pero su función se hará clara a continuación.
 Apagador

Cuando se tiene una situación de exclusión categórica

(basada en categorías y no en procesos individuales —varios
procesos de la misma categoría pueden entrar a la sección
crítica, pero procesos de dos categorías distintas deben
tenerlo prohibido), un apagador permite evitar la inanición
de una de las categorías ante un flujo constante de procesos
de la otra.
El apagador usa, como uno de sus componentes, un
torniquete. Para ver una implementación ejemplo de un
apagador, referirse a la solución presentada para el
problema de los lectores y los escritores
 Problema de los lectores y los escritores
Primera aproximación
• 11 def lector():
• 1 import threading
• 12 P(mutex)
• 2 lectores = 0
• 13 lectores = lectores + 1
• 3 mutex = [Link](1)
• 14 if lectores == 1:
• 4 cuarto_vacio = [Link](1)
• 15 P(cuarto_vacio)
• 5
• 16 V(mutex)
• 6 def escritor():
• 17
• 7 P(cuarto_vacio)
• 18 lee()
• 8 escribe()
• 19
• 9 V(cuarto_vacio)
• 20 P(mutex)
• 10
• 21 lectores = lectores - 1
• 22 if lectores == 0:
• 23 V(cuarto_vacio)
• 24 V(mutex)
 Solución
• 1 import threading • 18 //Continúa
• 2 lectores = 0 • 19 P(mutex)
• 3 mutex = [Link](1) • 20 lectores = lectores + 1
• 4 cuarto_vacio = [Link](1) • 21 if lectores == 1:
• 5 torniquete = [Link](1) • 22 P(cuarto_vacio)
• 6 • 23 V(mutex)
• 7 def escritor(): • 24
• 8 P(Torniquete) • 25 lee()
• 9 P(cuarto_vacio) • 26
• 10 escribe() • 27 P(mutex)
• 11 V(cuarto_vacio) • 28 lectores = lectores - 1
• 12 V(torniquete) • 29 if lectores == 0:
• 13 • 30 V(cuarto_vacio)
• 14 def lector(): • 31 V(mutex)
• 15 global lectores
• 16 P(torniquete)
• 17 V(torniquete)
 Barrera
Una barrera es una generalización de rendezvous que permite la
sincronización entre varios hilos (no sólo dos), y no requiere que el
papel de cada uno de los hilos sea distinto.
Esta construcción busca que ninguno de los hilos continúe
ejecutando hasta que todos hayan llegado a un punto dado.
Para implementar una barrera, es necesario que ésta guarde algo de
información adicional además del semáforo, particularmente, el
número de hilos que se han lanzado (para esperarlos a todos). Esta
será una variable compartida y, por tanto, requiere de un mutex. La
inicialización (que se ejecuta antes de iniciar los hilos) será:

• 1 num_hilos = 10
• 2 cuenta = 0
• 3 mutex = Semaphore(1)
• 4 barrera = Semaphore(0)
Ahora, suponiendo que todos los hilos tienen que realizar, por
separado, la inicialización de su estado, y ninguno de ellos debe
comenzar el procesamiento hasta que todos hayan efectuado su
inicialización:

• 1 inicializa_estado()
• 2
• 3 P(mutex)
• 4 cuenta = cuenta + 1
• 5 V(mmutex)
• 6
• 7 if cuenta == num_hilos:
• 8 V(barrera)
• 9
• 10 P(barrera)
• 11 V(barrera)
• 12
• 13 procesamiento()
Las barreras son una construcción suficientemente útil como
para que sea común encontrarlas “prefabricadas”. En los
hilos POSIX (pthreads), por ejemplo, la interfaz básica es:

• 1 int pthread_barrier_init(pthread_barrier_t *barrier,

• 2 const pthread_barrierattr_t
• *restrict attr,
• 3 unsigned count);
• 4 int pthread_barrier_wait(pthread_barrier_t *barrier);
• 5 int pthread_barrier_destroy(pthread_barrier_t *barrier);
 Cola

Se emplea cuando se tienen dos clases de hilos que deben

proceder en pares. Este patrón es a veces referido como
baile de salón: para que una pareja baile, hace falta que haya
un líder y un seguidor. Cuando llega una persona al salón,
verifica si hay uno de la otra clase esperando bailar.
En caso de haberlo, bailan, y en caso contrario, espera a que
llegue su contraparte.
El código para implementar esto es muy simple:
1 colaLideres = Semaphore(0)
2 colaSeguidores = Semaphore(0)
3 # (...)
4 def lider():
5 V(colaSeguidores)
6 P(colaLideres)
7 baila()
8 def seguidor():
9 V(colaLideres)
10 P(colaSeguidores)
11 baila()

El patrón debe resultar ya familiar: es un rendezvous. La distinción

es meramente semántica: en el rendezvous se necesitan dos hilos
explícitamente, aquí se habla de dos clases de hilos.
 Monitores

• Los monitores son estructuras provistas por el lenguaje o

entorno de desarrollo que encapsulan tanto los datos como
las funciones que los pueden manipular, impidiendo el
acceso directo a las funciones potencialmente peligrosas.

• En otras palabras, son tipos de datos abstractos (Abstract

Data Types, ADT), clases de objetos, y exponen una serie de
métodos públicos, además de poseer métodos
privados que emplean internamente.
Como ejemplo, el lenguaje de programación Java implementa
sincronización vía monitores entre hilos como una propiedad de la
declaración de método, y lo hace directamente en la JVM. Si se
declara un método de la siguiente manera:
1 public class SimpleClass {
2 // . . .
3 public synchronized void metodoSeguro() {
4 /* Implementación de metodoSeguro() */
5 // . . .
6 }
7 }
Y se inicializa a un SimpleClass sc =new SimpleClass(), cuando se
llame a [Link](), la máquina virtual verificará si ningún
otro proceso está ejecutando metodoseguro(); en caso de que no
sea así, le permitirá la ejecución obteniendo el candado, y en caso
de sí haberlo, el hilo se bloqueará hasta que el candado sea
liberado.
 Comunicaciones entre procesos
(IPC – Inter Process Communication)
La comunicación entre dos procesos puede ser realizada de dos
maneras:
1. Comunicación a través de un área común de memoria.
2. Comunicación mediante el intercambio de mensajes.
El propósito es permitir que dos procesos se
sincronicen o simplemente se envíen datos mediante un
mecanismo explícito
Definimos como mensaje a una porción discreta de datos
(generalmente compuesto por un conjunto de bits)
Los mensajes tienen una cabecera (header) y un cuerpo. El header
tiene el identificador del transmisor, el identificador del receptor,
la longitud, y el tipo
 Existen dos tipos de comunicaciones entre procesos:

Comunicación directa
Los procesos envían y reciben los mensajes entre sí. Dependen de las
velocidades relativas entre sí (si son distintas requieren un buffer de
mensajes para su sincronización).

Comunicación indirecta
Los mensajes son enviados a un buzón o mailbox y se retiran del buzón
Mailbox 1
recive
send

Proceso A Proceso B

recive
send
Mailbox 2

Mailbox: interfase entre procesos y S.O.. Se crea y quita facilmente.

Procesos: A Pide un mailbox y envía MSG, B se activa y recibe MSG
 Tipos de sincronizaciones mediante mensajes
• Comunicación Sincrónica
El proceso emisor es bloqueado hasta que el receptor esté listo para recibir el
mensaje. Cuando el proceso receptor ejecuta el receive y el mensaje no se
encuentra disponible queda bloqueado hasta la llegada del mismo. Una vez
que se ha producido el intercambio de mensajes ambos procesos continúan su
ejecución concurrentemente.

• Comunicación Asincrónica
Las primitivas de este tipo de comunicación se caracterizan por no bloquear a
los procesos que las ejecutan. Así cada uno sigue su ejecución. Esto es
importante en el caso del receptor ya que sigue ejecutando aunque no le
llegue ningún mensaje. Depende de la implementación si los mensajes
siguientes serán atendidos o no.

• Comunicación semi-sincrónica.
Se usa un send no bloqueante y receive bloqueantes. Esto es riesgoso pues se
pueden acumular una gran cantidad de mensajes en colas.
 Modelo productor-consumidor

Usado para describir dos procesos ejecutando en forma concurrente:

[Link]: Genera un conjunto de datos necesarios para la ejecución de otro
proceso.
[Link]: Toma los datos generados por el productor y los utiliza para su
procesamiento.

Actividades
p producir( ) Secuencia de mensajes (FIFO)

depositar( )
Asumimos que no se pierde, ni
Cola se modifica ningún bit del MSG
FIFO Buffer
Los datos son transmitidos entre
recuperar( ) ellos en porciones discretas que
llamaremos MENSAJES (MSG)
consumir( )
c

Capacidad del Buffer = MAX

• Productor: Genera elementos mediante producir() y los ingresa en el
buffer mediante depositar().

• Buffer: Zona de memoria utilizada para amortiguar las diferencias de velocidad

entre dos procesos. Almacena temporalmente los elementos generados por p.

• Consumidor: Retira los elementos del buffer mediante recuperar() y los

consume con consumir().

• Ejemplos:

• 1. ls | more

2. El spooler del SO y los procesos que quieren imprimir.

 Algunos algoritmos para el modelo productor-consumidor

A. Con sleep() & wakeup()

sleep(): Llamada al sistema que bloquea al proceso solicitante.
wakeup(): tiene como parámetro el PID del proceso a desbloquear.
Usa una variable cont que indica la cantidad de lugares ocupados que
tiene el buffer, donde N es el total de lugares
p() c()
{ {
while (1) while (1)
{
{
if (cont == 0)
x = producir();
sleep();
if (cont == N) x = sacar();
sleep(); cont--;
cont++; if (cont == N - 1)
ingresar(x); wakeup(p);
if (cont == 1) consumir(x);
wakeup(c); }
} }
}
Presenta al menos una condición de concurso. El
algoritmo falla.

La condición de concurso está dada cuando el buffer está

vacío y el consumidor acaba de leer cont para verificar si es
0. Ahí, lo interrumpen y pasa al productor; éste ingresa un
elemento en el buffer por lo que razonando que cont era 0,
despierta al consumidor, pero esa señal se pierde por lo
que el consumidor probará el viejo valor de cont y se
bloqueará.
 B. Con Contadores de eventos
Un contador de eventos e es una variable especial que tiene 3 operaciones
definidas en las siguientes primitivas:
1. read(e): Devuelve el valor de e.
2. advance(e): Incrementa atómicamente el valor de e en 1.
3. await(e, v): Espera hasta que e >= v.
• Solo incrementan el valor, nunca lo disminuye.
• Siempre se inician en cero.
Ejemplo para productor y consumidor:

p() c()
{ {
int prod; int sec;
while (1) while (1)
{ {
x = producir(); sec++;
prod++; await(ing, sec);
await(N,prod - sacados); x = sacar();
ingresar(x); advance(sacados);
advance(ing); consumir(x);
} }
} }

ing: Cuenta el número acumulativo de elementos que el productor colocó en el buffer.

sacados: Cuenta el número acumulativo de elementos que el consumidor retiró del buffer .
 C. Con Semáforos
Usa tres semáforos:
semáforo mutex = 1, vacío = N, lleno = 0;

p() c()
{ {
while (1) while(1)
{ {
x = producir(); P(lleno);
P(vacío); P(mutex);
P(mutex); x = sacar()
ingresar(x); V(mutex);
V(mutex); V(vacío);
V(lleno); consumir(x);
} }
} }

Cualesquiera de estos algoritmos propuestos sincronizan el modelo de productor-consumidor

que se presentan en múltiples situaciones dentro de un computador. Por ejemplo la CPU
produciendo mensajes para un módulo de E/S o viceversa.
 Mecanismos de IPC

• Pipes y fifos
• Señales
• Memoria compartida
• Sockets
• RPC / RMI
 Bloqueos mutuos e inanición

Bloqueo mutuo (o interbloqueo; en inglés, deadlock):

Situación que ocurre cuando dos o más procesos poseen
determinados recursos, y cada uno queda detenido, a la espera
de alguno de los que tiene el otro. El sistema puede seguir
operando normalmente, pero ninguno de los procesos
involucrados podrán avanzar.

Inanición (resource starvation): Situación en que un proceso no

puede avanzar en su ejecución dado que necesita recursos que
están (alternativamente) asignados a otros procesos.
Un deadlock puede darse por dos motivos:

• Comunicación entre procesos

• Petición de Recursos

Observemos que el deadlock se debe fundamentalmente por

el uso de recursos. Se pueden distinguir dos categorías
generales de recursos: reutilizables y consumibles.
• Recursos reutilizables

Un recurso reutilizable es aquel que puede ser usado por un proceso y

no se agota con el uso. Los procesos obtienen unidades de recursos que
liberan posteriormente para que otros procesos las reutilicen. Como
ejemplos se tienen los procesadores, canales de E/S, memoria principal
y secundaria, dispositivos y estructuras de datos tales como archivos,
bases de datos y semáforos.

• Recursos consumibles

• Un recurso consumible es aquel que puede ser creado (producido) y

destruido (consumido).
Normalmente, no hay límite en el número de recursos consumibles de
un tipo en particular. Un proceso productor que no esta bloqueado
puede liberar cualquier numero de recursos consumibles. Cuando un
proceso adquiere un recurso este deja de existir. Como ejemplos están
las interrupciones, señales, mensajes, e información en buffer de E/S.
 Condiciones necesarias y suficientes
Para que se produzca un estado de deadlock las cuatro
condiciones de Coffman deben producirse simultáneamente. Estas
condiciones son las siguientes:

• 1. Mutua exclusión: Los procesos reclaman control exclusivo de los

recursos que piden
• 2. Retener y esperar Los procesos mantienen los recursos que ya les
han sido asignados mientras esperan por recursos adicionales
• 3. No expropiación Los recursos no pueden ser extraídos de los
procesos que los tienen hasta su completa utilización
• 4. Espera circular: Hay una cadena circular de procesos en la que
cada uno mantiene a uno o más recursos que son requeridos por el
siguiente proceso de la cadena
 Grafo de asignación de recursos
Otra manera de definir deadlocks es a través de grafos. Estos grafos están formados
básicamente por dos elementos:
• Un conjunto de vértices formado por los procesos y los recursos del sistema;
• Un conjunto de arcos que representan la asignación o solicitud de recursos.

Para ilustrar la situación (ver figura 4.13) se utiliza un grafo dirigido llamado Resource
Allocation Graph (Grafo de Asignación de Recursos). En él se representan :
• 1. Conjunto de vértices V con los procesos (Px) y los recursos (Ry) del sistema
P = {P1, P2, ..., Pn} Procesos
R = {R1, R2, ..., Rn} Recursos
• 2. Conjunto de arcos A que unen los procesos con los recursos.
• A continuación podemos ver tres grafos de asignación de recursos. Los
recursos fueron representados con cuadrados y los procesos con
círculos. Un arco de Pi a Rj significa que el proceso Pi solicito el recurso
Rj. Un arco de Rj a Pi significa que el recurso Rj esta asignado al
proceso Pi .

P1 A
P1 R1 P2

A A A
A
P1 R2
A
R1 R1 Fig. 4.13c
Fig. 4.13a
Fig. 4.13b
Un arco dirigido de P1 a R1 indica que P1 pidió el recurso R1 y está esperando. (Fig 4.13a)
Un arco dirigido de R1 a P1 indica que P1 pidió el recurso R1 y R1 está asignado a P1. (Fig 4.13b)
Un conjunto de arcos como se indica en la Fig 4.13c indica que está en deadlock
 Estrategias para tratar deadlocks
• Hay 3 estrategias:

➢Ignorarlos y pensar que en el sistema nunca ocurrirán.

La mayoría de los sistemas operativos utilizan esta
técnica, incluyendo UNIX.

➢Por medio de la prevención o evasión se asegura que

el sistema nunca entrará en estado de deadlock.

➢Permitir que ocurra un estado de deadlock y luego

recuperarlo
 Ignorarlo
• Es la forma más simple para tratarlo

• Algunas veces el costo de ignorarlo es mucho menor al

costo que implicaría prevenirlo o detectarlo y recuperarlo

• Tanenbaum propone como “algoritmo del avestruz” y dice

“Si los deadlocks no son frecuentes entonces puede ser
más conveniente esconder la cabeza bajo la arena”.
 Prevención
• Siendo las cuatro condiciones necesarias para que ocurra un
Deadlock basta con asegurarnos que una de ellas no ocurrirá
• Mutua Exclusión: Las soluciones para aquellos recursos que no
pueden ser compartidos son diversas, pero todas se basan en que
un proceso no quede esperando en caso de la falta de
disponibilidad de dicho recurso
• Control y espera (Hold & Wait): Para solucionar este problema, se
trata de garantizar que cuando un proceso tenga un recurso
asignado no pueda solicitar otro. Hay dos caminos para lograrlo:
• 1 - Los procesos solicitan todos los recursos en el momento previo a comenzar la
ejecución, de no poder ser entregados el proceso queda bloqueado.
• Asignación estática completa de todos los recursos que necesita para su
ejecución (caso COBOL).
• 2 - Un proceso primero debe liberar aquellos recursos que posee y luego recién
podrá solicitar otros, es decir solo está en condiciones de solicitar un recurso
cuando no tiene ninguno asignado.
No expropiación (No Preemption): Para ésta
condición también existen dos métodos:

1. Si un proceso solicita un recurso que no está disponible, éste

debe devolver todos aquellos recursos que tenía previamente
asignados.

2. Si un proceso pide un recurso que tiene otro proceso, el Sistema

Operativo puede obligar a liberar los recursos al otro proceso.

El primer método es viable sólo en aquellos procesos cuyos estados

pueden ser fácilmente grabados y restaurados. El segundo método
presenta el inconveniente del estado de inanición (Starvation), en
caso
de que a un proceso siempre le quiten los recursos y nunca pueda
finalizar su tarea.
Espera circular: Consiste en imponer un orden lineal de ejecución
que evite las esperas circulares

• Este problema puede ser resuelto de la siguiente manera:

1. Estableciendo un orden lineal de los recursos:

Si tenemos una lista de recursos R1, R2,......Rn, un proceso que
solicitó Rh, sólo puede pedir aquellos recursos Rk, con k > h. Esto
evita que se forme un círculo .

2. Otra forma de resolverlo es lo propuesto en Hold & Wait: un

proceso sólo está en condiciones de solicitar un recurso cuando no
tiene ninguno asignado.

El problema del orden lineal es que también es en cierto grado ineficiente ya que
estaría negando recursos a procesos, innecesariamente .
 Detectar y recuperar
• Consiste en abortar un proceso cuando se detecta o se presupone
que puede ocurrir el deadlock.

• La ventaja de esta táctica es que no limita el acceso a los recursos

• Presenta ciertos inconvenientes como el de decidir la frecuencia

con que se llevará a cabo el algoritmo de detección.

• El algoritmo podría ser ejecutado cada vez que se solicita un

recurso, a cada hora, etc.
Hay varios métodos para recuperar a los procesos y a los
recursos una vez detectada la situación:

➢Abortar todos los procesos involucrados

➢Abortar los procesos uno a uno, hasta que el deadlock

desaparezca.

➢Hacer un backup de cada proceso en un punto anterior: ChekPoint.

A este proceso de reinicio se lo llama Rollback. Consiste en llevar el
proceso a un punto anterior al de haberle sido asignado el recurso
causante del Deadlock.

➢Quitar un recurso a un proceso y entregárselo a otro que lo haya

solicitado. También hay que ejecutar el algoritmo de detección
luego de que se quitó algún recurso.
Módulo 5

ADMINISTRACIÓN DE
MEMORIA CENTRAL
Funciones y Operaciones
Funciones y Operaciones del Adm. Mem
Consideraciones
• Por cuestiones de diseño, el único espacio de memoria que el procesador
puede utilizar es la Memoria central (MC)
• Uhhhmmmm... y los Caches??
• Son para mejorar la performance y en general replican el contenido de la MC
• Uhhhmmmm (si... otro!) …. y los registros del procesador??
• Sí!!!! Esos sí, pero son muy pequeños y solo los utiliza para realizar sus operaciones
• ...pero los discos....????
• No… no…. esos NO!!. Es almacenamiento secundario. No es accesible directamente por el procesador. Están conectados
al sistema mediante el módulo de I/O. lo vemos mas adelante

• Los programas deben cargarse a la MC antes de ser ejecutados

• …Todo completo???
• Depende.... de como se gestione la memoria (de eso se trata el tema)
• También está relacionado con el HW que disponga el equipo, en especial con el MMU
Funciones y Operaciones del Adm. Mem
Espacio de direccionamiento
• La Memoria Central está estructurada como un arreglo direccionable de BYTES.
• Cada operación de lectura/escritura se hará de a 8 bits (no menos)
• Un procesador que soporta un espacio de direccionamiento de 16 bits puede
referirse directamente a hasta 216 bytes, esto es, hasta 65 536 bytes (64 KB).
• En procesadores de 32 bits, sus registros pueden referenciar hasta 4 294 967
296bytes (4 GB) de RAM
• No obstante, a través de un mecanismo llamado PAE (extensión de direcciones físicas,
Physical Address Extension) permite extender esto a rangos de hasta 252 bytes a cambio de
un nivel más de indirección.
• Un procesador de 64 bits podría direccionar hasta 18 446 744 073 709 551 616
bytes (16 Hexabytes).
• En la práctica, por cuestiones económicas van desde 240 a 248 (1 a 256 Terabytes).
Funciones y Operaciones del Adm. Mem
Hardware: el MMU
• ¿Por qué hace falta un Memory Manager Unit (MMU) ?
• Multitarea (multiprogramación) => Múltiples programas en MC => El S.O debe
resolver como ubicar los programas en la memoria física disponible.
• Ir mas allá de la memoria física disponible (Memoria virtual)
• Verificar los límites entre los que un proceso puede acceder al espacio asignado
(ejemplo: Registro base/límite)
• Uhhmmmm … pero no lo hace el SO???
• Es muy costoso delegarlo en el SO
Funciones y Operaciones del Adm. Mem
Hardware: memora Cache
• ¿Por qué un cache?
• La velocidad del procesador >> que la de la MC. Influye directamente en el
rendimiento ya que si no está el dato, el sistema detiene su ejecución (stall)
• ¿Qué es?
• Memoria de alta velocidad que está entre el Procesador y la MC que guarda
copias de las páginas accedidas partiendo del principio de localidad de
referencia:
• Loc. Temporal: probabilidad de reutilizar un recurso recientemente utilizado
• Localidad espacial: La probabilidad de que un recurso aún no requerido sea accedido
es mucho mayor si fue requerido algún recurso cercano.
• Localidad secuencial: Un recurso, y muy particularmente la memoria, tiende a ser
requerido de forma secuencial.
• El precio de un sistema varía significativamente dependiendo de los
tamaños de caches de Nivel 2 y Nivel 1 con el que cuenta.
Funciones y Operaciones del Adm. Mem
Espacio de Memoria de un proceso
• Cuando se crea un proceso, la carga se realiza con la
siguiente estructura:
• Sección (o segmento) de texto o código Es la imagen en memoria
de las instrucciones a ser ejecutadas. Usualmente, ocupa las
direcciones más bajas del espacio en memoria.
• Sección de datos Espacio fijo preasignado para las variables
globales y datos inicializados (como las cadena de caracteres por
ejemplo). Se fija en tiempo de compilación, y no puede cambiar
(aunque los datos que cargados allí sí cambian en el tiempo de vida
del proceso).
• Espacio de libres (HEAP) Espacio para la asignación dinámica de
memoria durante la ejecución del proceso. Este espacio se ubica por
encima de la sección de datos, y crece hacia arriba.
• Lenguajes dinámicos (C )-> Free/Malloc
• Lenguajes gestión automática (java)->, garbage collector.
• Pila de llamadas (stack) Espacio de memoria que se usa para
almacenar la secuencia de funciones que han sido llamadas dentro
del proceso, con sus parámetros, direcciones de retorno, variables
locales, etc. La pila ocupa la parte más alta del espacio en memoria,
y crece hacia abajo.
Funciones y Operaciones del Adm. Mem
Resolución de direcciones
• El compilador reemplaza las variables/funciones
simbólicas por las direcciones de memoria a donde se
ubican.
• Para poder coexistir con otros procesos, esas
direcciones deben ser traducidas a la posición relativa,
con alguna de las siguientes estrategias:
• En tiempo de compilación: Las direcciones son
absolutas/fijas. Ej: [Link]
• En tiempo de carga: El loader calcula las ubicaciones al
momento del inicio del programa (ej: Reg Base + offset)
• En tiempo de ejecución: El programa NUNCA hace
referencia a una ubicación fija (ej: base_frame +offset)
Asignación de memoria
contigua
 Asignación de Memoria
contigua
Monoprogramados/por lotes-> El SO casi no necesitaba
gestionar la memoria.
• Por qué???
 Asignación de Memoria
contigua
• Particiones fijas : Se parte la memoria en
espacios fijos predeterminados.
• Algunas cuestiones
• ¿¿Cuántos programas puedo ejecutar??
• Si el programa necesita X bytes y tengo Y
bytes...
• Si X > Y??
• Si X = Y ??
• Si X < Y ??
• ¿¿Cuál es el tamaño máximo de los
programas??
• Pueden usar Memoria virtual
• … Y las I/O pendientes??
• Es costoso en tiempo/recursos??
Asignación de Memoria
contigua
• Particiones variables: asignación dinámica de acuerdo al tamaño a
ubicar Compactación
• Algunas cuestiones:
• ¿Qué pasa cuando los procesos terminan y los
bloques se reusan??
• Si tengo varios frames libres de diversos tamaños en
cuál ubico el proceso?
• ¿Cuál es el tamaño máximo de los programas?
• Fragmentación externa -> defragmentación/compactación
(Muy costoso!)
• Tamaño máximo determinado de los programas
• Algoritmos:
• First Fit
• Best Fit
• Worst Fit
• Pueden usar Memoria virtual

Compactación: Para minimizar la fragmentación,

el sistema puede realizar una “compactación”,
que implica reubicar la memoria de los procesos
juntando el espacio libre
Segmentación
Segmentación
• Divide la memoria en "segmentos de tamaño variables"
• Los segmentos se corresponden con las distintas partes de un
programa (código, tabla de símbolos, stack, heap)
• Los segmentos pueden tener distintos tipos de acceso (read only,
write, execution).
• Se pueden compartir segmentos entre distintos procesos.
• Las bibliotecas ligadas dinámicamente (link edited) se representan
en segmentos independientes
• Se puede utilizar memoria virtual
• El espacio libre se gestiona en forma similar a particiones
variables
 Segmentación

• Las direcciones están compuestas por Nro de segmento + Desplazamiento (s:d)

• El sistema operativo mantiene una SMT (Segment Memory Table) por proceso
¿Cómo se administra? que tiene el Nro de segmento, el tamaño y la dirección de inicio. El espacio
libre se gestiona con el criterio de particiones variables
• Cuando se requiere una dirección, se recupera el inicio del segmento en la SMT
y se le suma el desplazamiento (Offset) y se obtiene la dirección en la MC
(memoria central)

Cuestiones: ??? • ¿Qué pasa con la fragmentación?

• ¿Se necesita soporte de Hardware?
Paginación
Paginación pura o simple
• El proceso se divide en bloques de tamaño fijo llamados
"páginas" (pages)
• La memoria física se divide en una serie de marcos (frames) del
mismo tamaño que las páginas
• Por lo general, los frames/pages se dividen en porciones de entre
512B (29) y 16MB (224) - Siempre son potencias de 2
• Para el direccionamiento se divide el bus de direcciones
considerando N bits para la página y M bits para el
desplazamiento (Offset)
Paginación pura
o simple

• Las direcciones están compuestas por Nro de Página+ Desplazamiento (p:d)

• El sistema operativo mantiene una MPT (Memory Page Table) por proceso que
¿Cómo se administra? tiene el Nro de página, el tamaño y la dirección de inicio. El espacio
ocupado/libre se administra con una tabla de bits por frame MFT (Memory
Frame Table)
• Cuando se requiere una dirección, se recupera el inicio del frame en la MPT y
se le suma el desplazamiento (Offset) y se obtiene la dirección en la MC
(memoria central)
• ¿Necesita Soporte de HW?
• ¿Qué pasa con la fragmentación?

Cuestiones: ??? •
•
¿Cuál es el tamaño de página óptimo?
¿Cuánto ocupa la tabla de páginas?
• ¿Puedo compartir memoria entre procesos?
 Paginación pura o simple
• ¿Necesita Soporte de HW?
• ¡Obvio! Leer/cargar las tablas para calcular las direcciones es sumamente costoso, el overhead es muy grande
• Soluciones: Además del MMU, se pueden implementar TLBs y caches
• ¿Qué pasa con la fragmentación?
• Se reduce mucho respecto de la asignación contigua, solo se fragmentan porciones de páginas.
• No tiene el problema de la segmentación. Cuando un frame se libera, se puede volver a reasignar
• ¿Cuál es el tamaño de página óptimo?
• Uhhhmmm... Páginas grandes -> mucha fragmentación interna, páginas chicas -> tabla de páginas muy grande, PCB
también más grande, transferencias entre MC y Disco más costosas
• ¿Cuánto ocupa la tabla de páginas?
• Ejemplos: Procesador 16 bits y páginas de 13bits (8KB) => 2^3 = 8 entradas. ¡Insignificante!
Procesador 32 bits y páginas de 12bits(4KB) => 2^20 = 1.048.576 entradas . x (20b frame + 20b pág ) ¡Unos
5MB!
¿¿¿Procesador de 64bits ??? ¡Inmanejable!
• Solución: Paginación multinivel
• ¿Puedo compartir memoria entre procesos como en segmentación?
• Si... Por ejemplo, cuando se crea un proceso hijo se copia el espacio de memoria del padre, apuntado a las páginas del
padre, cuando se modifican se reescriben en un frame nuevo, de esta forma, las páginas de solo lectura y/o ejecución
son compartidas por ambos procesos
Direccionamiento con TLB
Translation Lookaside Buffer (TLB)/Buffer de
traducción anticipada: El TLB es una tabla
asociativa (un hash) en memoria de alta
velocidad, una suerte de registros residentes
dentro de la MMU, donde las llaves son las
páginas y los valores son los marcos
correspondientes. De este modo, las
búsquedas se efectúan en tiempo constante

Direccionamiento con
TLB y Cache
Paginación Multinivel
Se definen tablas de directorios, que a su vez
apuntan a tablas de páginas

Ejemplo: Sistema de 32 bits, con 10 para la

tabla externa, 10 para la interna y 12 para el
desplazamiento

Direccionamiento
Memoria compartida
Se pueden compartir solo las
páginas que son de solo
lectura

Copiar al escribir (copy on write, CoW)

(a) Inmediatamente después de la creación del proceso (b) Cuando el proceso hijo modifica información en la primer
hijo por fork() página de su memoria, se
crea como una página nueva.
 Memoria Virtual

Paginación sobre demanda

 En general, memoria virtual es la utilización de una memoria
secundaria (por ejemplo, parte de un disco). De esta forma, los
procesos trabajan con una “idealización de la memoria”, en el cual
pueden ocupar hasta el 100% de la capacidad de direccionamiento,
independiente de la memoria física con la que cuenta el sistema.

Memoria La memoria virtual es gestionada de forma automática y

transparente por el sistema operativo. No se considera memoria

Virtual
virtual, por ejemplo, si un proceso pide explícitamente intercambiar
determinadas páginas

Swapping : Es el intercambio entre la memoria entre distintos

niveles de memoria
Swapping
Es el intercambio de información entre 2 niveles de memoria
• Swap-in: Es cuando el intercambio se hace desde un dispositivo de menor jerarquía a
uno de mayor jerarquía (ej. De Disco duro a MC)
• Swap-out: Es cuando el intercambio se hace desde un dispositivo de mayor jerarquía a
uno de menor jerarquía (ej. De Cache L1 a MC)

Algunas consideraciones:
• ¿Qué pasa si el proceso a suspender tiene
I/O pendiente?
• Solo se pueden pasar a suspendidos los
procesos que no tengan pendientes
operaciones de I/O, o
• Ejecutar operaciones de I/O sobre
buffers del S.O Políticas de Administración de Memoria Virtual
• ¿Que pasa si el intercambio es excesivo? • Fetch (búsqueda) → Cuando debe llevarse una pagina a MC
• Eso es HIPERPAGINACION O TRASHING! • Placement (colocación) → A donde debe ubicarse en la MC
• ¿Y la performance? • Replacement (reemplazo)→Cual es la página que se va a
• ¿Dónde se guardan las páginas descargadas? reemplazar
Paginación bajo demanda
• En paginación sobre demanda, el sistema emplea
espacio en almacenamiento secundario (típicamente,
disco duro), mediante un esquema de intercambio
(swap) guardando y trayendo páginas enteras.
• Utiliza un cargador (pager) “lazy” (flojo/perezoso). Al
comenzar la ejecución de un proceso, solo se cargan a
memoria las páginas necesarias a medida que se van
requiriendo.
• Si la página requerida no se encuentra en memoria, el
pager deberá cargarla

La técnica opuesta a Lazy es Eager (ansioso/glotón) en

el que se carga todo al momento inicial

Direccionamiento
Fallo de página
1. Verifica en el PCB si esta solicitud corresponde a una página que ya ha sido
asignada a este proceso.
2. En caso de que la referencia sea inválida, se termina (suspende) el proceso.
3. Procede a traer la página del disco a la memoria. El primer paso es buscar
un marco disponible (por ejemplo, por medio de una tabla de asignación
de marcos).
4. Solicita al disco la lectura de la página en cuestión hacia el marco
especificado.
5. Una vez que finaliza la lectura de disco, modifica tanto al PCB como al TLB
para indicar que la página está en memoria.
6. Termina la suspensión del proceso, continuando con la instrucción que
desencadenó al fallo. El proceso puede continuar sin notar que la página
había sido intercambiada.
Rendimiento
te: Tiempo efectivo de acceso a memoria.
p: Probabilidad de fallo de página
ta: Tiempo de acceso a memoria (entre 10 y 200 ns)
tf : Tiempo que toma atender a un fallo de página (aprox 8 ms – posicionado de cabeza + latencia, descartando ta )

Si p = 1/1000 (Un fallo cada 1000 accesos) =>

En promedio el te es 40 veces mayor que sin usar swapping

Reemplazo de páginas
Situación:
Profe: El sistema está comprometido mas allá de la memoria física disponible, y necesita cargar una
página que no está presente!
Alumno: Fácil!!! Reemplazo una de las páginas que está en memoria, y listo!
Profe: Ahhh… ok!!! Cuál?? Porqué??
Alumno: ehhhh… ehhhh…

Elección de la víctima
• La página ya se encuentra en MV (memoria virtual)??
• Fue modificada en MC ?
• Es del mismo proceso o de otro?
• Cuándo se la accedió por última vez?
• Cuándo se modificó?

Considerando esto, se pueden implementar diferentes algoritmos para

la elección de la página víctima.
Reemplazo de páginas
¿Si se le otorgan más frames a un proceso, entonces deberían haber más o menos
fallos??
Anomalía de Belady:
En general, si se le asignan más frames a un proceso, en consecuencia deberían producirse menos fallos
de página, pero en algunos algoritmos, con determinada secuencias de llamadas, se pueden presentar más
fallos de página

Ejemplo: 3 frames y la cadena de referencia: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Relación ideal entre el número de marcos Comportamiento del algoritmo *fifo* exhibiendo la
y fallos de página. anomalía de Belady al pasar de tres a cuatro marcos.
Reemplazo de páginas . Algoritmos
Primero en entrar, primero en salir - FIFO

Ejemplo: 3 frames y la cadena de referencia: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

• Simple
• Vulnerable a la anomalía de Belady
Reemplazo de páginas . Algoritmos
Reemplazo de páginas óptimo (OPT, MIN)

Ejemplo: 3 frames y la cadena de referencia: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

• Requiere conocer la cadena de referencias a priori (futurismo!!)

• Solo sirve para comparación con respecto a otros algoritmos
Reemplazo de páginas . Algoritmos
Menos recientemente utilizado (LRU)
Ejemplo: 3 frames y la cadena de referencia: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• Busca acercarse a OPT prediciendo cuándo
será la próxima vez en que se emplee cada
una de las páginas que tiene en memoria
basado en la historia reciente de su
ejecución
• Elige la página que no ha sido empleada
desde hace más tiempo
• Por su complejidad, requiere soporte de
HW

Más frecuentemente utilizada (MFU)/Menos

frecuentemente utilizada (LFU)
• Se implementa como LRU pero en lugar de
registrar tiempo se registran las
invocaciones
• Costoso de implementar
• Bajo rendimiento
Reemplazo de páginas . Algoritmos
Aproximaciones a LRU Segunda oportunidad (o reloj)
• Similar a BIT de referencia.
Bit de referencia • Mantiene un Apagador del BIT de
• La tabla de páginas tiene un bit adicional “referencia de referencia.
acceso” • Ante un fallo, si el bit está apagado, es la
• Cuando inicia la ejecución el bit de “referencia” está víctima, sino, se enciende para darle una
apagado segunda oportunidad
• Cada vez que se referencia el frame, el bit se enciende
• Periódicamente el SO resetea el bit de referencia.
• Ante un fallo, se aplica FIFO entre los que tengan el bit Segunda oportunidad mejorado
de referencia apagado • Similar a 2da oportunidad, pero implementa 2bits (referencia,
modificación)
Columna de referencia
• (0, 0) Candidato ideal para su reemplazo.
• Similar a BIT de referencia, pero usando
• (0,1) No es tan buena opción, porque es necesario
una “columna de bits” (ejemplo 4b)
escribir la página a disco antes de reemplazarla, pero
• Cuando ejecuta el SO el RESET, hace un
puede ser elegida.
right shift del valor a la siguiente posición y
• (1,0) fue empleado recientemente, por lo que
se descarta el bit menos significativo
probablemente se vuelva a requerir pronto.
• Ante un fallo, se aplica FIFO entre los que
• (1,1) sería necesario escribir la página a disco antes de
tengan el valor de la columna mas bajo
reemplazar, hay que evitar reemplazarla.
• Ante un fallo, si el bit está apagado, es la víctima, sino, se
enciende para darle una segunda oportunidad
Asignación de marcos
• ¿cómo se asignan los marcos existentes a los procesos del sistema?
• ¿qué esquemas se pueden definir para que la asignación inicial (y, de ser posible, en el
transcurso de la ejecución) sea adecuada?
• ¿Cuál es el mínimo de frames que puede requerir un proceso?
Mínimo de marcos:
Por ejemplo si una instrucción de CPU permite la suma de 2 operandos directos en
memoria y la asignación del resultado en otro, ➔ se necesitarán un mínimo de 4 frames (1 para el
Código, 2 para los operandos y 1 para el resultado

Ámbitos del algoritmo de reemplazo de páginas

• Reemplazo local: EL objetivo: es mantener tan estable como sea posible el cálculo hecho por el esquema de
asignación empleado. Las únicas páginas que se considerarán para su intercambio serán aquellas
pertenecientes al mismo proceso que el que causó el fallo.
• Reemplazo global: Los algoritmos de asignación determinan el espacio asignado a los procesos al ser
inicializados. Los algoritmos de reemplazo de páginas operan sobre el espacio completo de memoria, y la
asignación física de cada proceso puede variar según el estado del sistema momento a momento.
• Reemplazo global con prioridad: Es un esquema mixto, en el que un proceso puede sobrepasar su límite
siempre que le robe espacio en memoria física exclusivamente a procesos de prioridad inferior a él. Esto es
consistente con el comportamiento de los algoritmos planificadores, que siempre dan preferencia a un
proceso de mayor prioridad por sobre de uno de prioridad más baja.
Hiperpaginación
Sucede cuando la frecuencia de reemplazo de páginas es tan alto que el Sistema no puede avanzar.
Todo (o casi todo) el trabajo realizado es overhead.
• Si la política es de asignación es local, alguno/s proceso/s tiene/n poco/s frames asignado/s
• Si la política es de asignación es global, hay demasiados procesos en ejecución

Síntomas
• la tasa de page faults aumenta considerablemente;
• se incrementa el tiempo de acceso efectivo a memoria;
• la utilización del procesador decae;
• no se realiza ningún trabajo ya que los procesos se
dedican a paginar

Solución posible
• Reducir el grado de multiprogramación (suspender
procesos)
Sistemas mixtos
Segmentación con paginación por demanda
• Combinan las técnicas de Segmentación y de paginación.
• En general los segmentos tienen un tamaño múltiplo de páginas.
• No se necesitan tener cargadas en memoria central todas las Páginas de los segmentos.
• La dirección virtual se organiza en tres partes:

Ventajas:
1. Permite compartir segmentos. Direccionamiento
2. No es necesario cargar la totalidad de los
segmentos en memoria central ni la totalidad de
las
Páginas. Solo lo que se necesite.
3. No se requiere compactación.

Desventajas:
1. Requiere más Hardware para el
direccionamiento.
2. Es más lento en la ejecución (por el mecanismo
de traducción de las direcciones virtuales)
3. El S.O. ocupa más Memoria.
4. Aumenta la fragmentación interna.
Módulo 6

-ADMINISTRACIÓN DE ENTRADA/SALIDA

-FILE SYSTEM
¿Por qué los periféricos no se conectan directamente al bus del sistema?

✓ Hay una amplia variedad de periféricos con varios métodos de operación. Sería
poco práctico incorporar la lógica necesaria dentro del procesador para
controlar un rango de dispositivos uno por uno.

✓ La velocidad de transferencia de datos de los periféricos es a menudo bastante

menor que la de la memoria central o del procesador.

✓ Los periféricos generalmente emplean distintos formatos de datos y longitudes

de palabra que los utilizados en el computador al que se conecta.
En consecuencia, es necesario un módulo de E/S, que tiene dos funciones
principales desde el punto de vista del Hardware:

✓ Proveer una interfase con el procesador y la memoria central vía el bus del
sistema.

✓ Proveer una interfase a uno o más dispositivos periféricos por vínculos

especialmente diseñados.

El Sistema de Gestión de la Entrada / Salida se

ocupa de la organización, administración y operación
de los dispositivos de E/S
Este “módulo” de E/S gestiona el acceso de los dispositivos a los distintos
buses del sistema. Hace ya varios años, estas comunicaciones se
gestionan mediante los chips denominados Puente Norte y Puente Sur:

Puente Norte (Northbridge):

✓ Conectado directamente a la CPU
✓ Gestiona los dispositivos de más velocidad

Puente Sur (Southbridge):

✓ Se conecta al puente norte
✓ Gestiona el resto de los dispositivos
 Funciones del Módulo
✓ Control y Temporización
✓ Comunicación con el procesador
✓ Comunicación con el dispositivo
✓ Amortiguación (buffering) de datos
✓ Detección de errores.
✓ Manejo de Interrupciones a bajo nivel.
 Control y temporización
En general, incluye los siguientes pasos:

1. El procesador interroga al módulo de E/S para verificar el

estado (status) del dispositivo conectado.

2. El módulo de E/S devuelve el estado del dispositivo.

3. Si el dispositivo está operable y listo para transmitir, el

procesador solicita la transferencia de datos, por medio de un
comando al módulo de E/S.

4. El módulo de E/S obtiene una unidad de datos (por

ejemplo, 8 ó 16 bits) del dispositivo externo.

5. Los datos son transferidos desde el módulo de E/S al

procesador.
 Comunicación con el procesador
Incluye:
• Decodificación del comando: El módulo de E/S acepta
comandos desde el procesador. Estos comandos
generalmente son enviados como señales a través del bus
de control.

• Datos: Los datos son intercambiados entre el procesador

y el módulo de E/S a través del bus de datos.

• Informe de Estados: Por ser los periféricos tan lentos,

resulta importante saber el estado del módulo de E/S. Las
señales de estados más comunes son BUSY y READY.

• Reconocimiento de direcciones: De la misma forma que

cada palabra en la memoria tiene una dirección, también la
tiene cada dispositivo de E/S.
 Comunicación con el dispositivo
De manera muy similar a la comunicación con el
procesador, también se realiza:

✓ Intercambio de comandos
✓ Informe de estados
✓ Transferencia de datos

➢ Los dispositivos funcionan independientemente del procesador y no

utilizan el reloj del procesador, sino el suyo propio.

➢ Esto constituye una operación asincrónica manejada por las señales de

control que son generadas por los dispositivos y sus interfases.

➢ A estas señales se las conoce como señales de dialogo (handshaking)

que son intercambiadas entre el controlador - dispositivo y el procesador
antes de comenzar y al finalizar cada operación de E/S.
 Amortiguación (buffering) de datos

✓ Es una tarea esencial del un módulo de E/S.

✓ Mientras que la velocidad de transferencia hacia y

desde la memoria o el procesador es bastante
alta, la velocidad es varios órdenes de magnitud
inferior para la mayoría de los dispositivos.

✓ El módulo de E/S debe ser capaz de operar a

ambas velocidades.
 Detección de errores
✓ Una clase de error puede ser el mal
funcionamiento, mecánico o eléctrico, reportado
por el dispositivo.

✓ Otra clase de error consiste en los cambios no

intencionales de los patrones de bits tal como son
transmitidos desde el dispositivo al módulo de
E/S.
 Manejo de Interrupciones

El manejo de interrupciones al mas bajo nivel

debe ser realizado por el módulo de Entrada /
Salida.

Por ejemplo:
Cuando un disco finalizó una escritura, no es el
propio disco quien notifica al procesador, sino el
módulo de E/S.
 Componentes principales
Controlador o Driver
✓ Es la interfase del sistema de E/S con el S.O. a nivel de software.
✓ Se ocupa de convertir el flujo de bits en bloques de bytes o caracteres.

Software Independiente del Dispositivo

✓ Presenta al dispositivo como un conjunto de registros dedicados que se leen
o escriben en cada operación de E/S.
✓ A estos registros generalmente se los denominan puertos de E/S.
 Procesadores de E/S (IOP)

✓ En los grandes equipos (Mainframe) generalmente se conectan

mediante varios buses y a un procesador especial de E/S que se
ocupa de toda la gestión.

✓ A esta configuración se denomina subsistema de E/S que hace

de interfase con el procesador y memoria central.

✓ Todas las operaciones sobre periféricos se arrancan con una

orden generada en el procesador para el procesador de E/S o
canal, quien realizará las transacciones en forma independiente
asumiendo el completo control de las mismas.
 TÉCNICAS DE E/S
Hay tres técnicas posibles para las operaciones de E/S:

E/S Programada, también llamada Polling (Escrutinio)

✓ Los datos son intercambiados entre el procesador y el módulo de E/S. El
procesador ejecuta el programa que otorga el control directo de la operación
de E/S, incluyendo el sensado del estado del dispositivo, enviar un comando
READ o WRITE, y la transferencia de los datos.
✓ Cuando el procesador emite un comando al módulo de E/S, debe esperar
hasta que la operación de E/S se complete.
✓ Si el procesador es más rápido que el módulo de E/S, se desperdicia tiempo
de la CPU.

E/S dirigida por interrupciones (Interrupt Driven)

✓ El procesador emite un comando de E/S, continúa con la ejecución de otras
instrucciones, y es interrumpida por el módulo de E/S cuando éste ha
completado su trabajo.

Tanto en la E/S programada o por interrupciones, el procesador es responsable

de extraer los datos de la memoria central para el output o almacenar los datos en
la memoria central para el input.
 TÉCNICAS DE E/S
Acceso directo a Memoria (DMA)
✓ El módulo de E/S y la memoria central intercambian datos directamente, sin
involucrar a la CPU.

✓ El DMA requiere un módulo adicional en el bus del sistema.

✓ El módulo de DMA es capaz de simular al procesador y tomar el control del

sistema desde la CPU.

✓ Cuando el procesador desea leer o escribir un bloque de datos, emite un

comando al módulo de DMA, enviándole la siguiente información:
▪ Si la operación solicitada es una lectura o una escritura.
▪ La dirección del dispositivo de E/S involucrado.
▪ La posición inicial en memoria a leer o a escribir.
▪ El número de palabras a ser leído o escrito.
 Transferencia de datos mediante DMA
¿Cómo se resuelve la competencia por el acceso al Bus?

✓ Por ráfagas: Cuando el DMA toma el control del bus, no lo libera

hasta haber transmitido el bloque de datos pedido. Se consigue la
mayor velocidad de transferencia, pero se tiene inactiva la CPU
(parada del procesador).

✓ Por robo de ciclos: Cuando el DMA toma el control del bus, lo

retiene durante un solo ciclo. Transmite una palabra y libera el bus.
Es la forma más usual. Reduce al máximo la velocidad de
transferencia y la interferencia del DMA sobre la actividad del
procesador.

✓ DMA transparente: Se elimina completamente la interferencia entre

el DMA y la CPU. Sólo se roban ciclos cuando la CPU no está
utilizando el bus del sistema. No se obtiene una velocidad de
transferencia muy elevada.
 Discos

¿Por qué nos interesa estudiar sobre los discos rígidos?

✓ Son el principal medio de almacenamiento desde hace más de 40 años.

✓ Se utilizan para la denominada área de intercambio (swap).

✓ Prácticamente todo el software hace uso de este tipo de

almacenamiento, sea en forma permanente o temporal.
 Hardware del Disco
✓ Los discos se constituyen sobre láminas de óxido ferroso.
✓ Poseen distintas superficies (platos), que pueden tener
dos caras.
✓ Estas caras se dividen en pistas y las pistas en sectores.
✓ Las pistas equivalentes sobre distintas superficies se
denominan cilindro.
✓ La cabeza lecto-grabadora se mueve a la pista correcta
(tiempo de búsqueda) y electrónicamente se selecciona la
cara correcta; entonces, esperamos (tiempo de latencia)
que el sector requerido pase bajo la cabeza.
Tiempos que intervienen en una lectura de disco y la
transferencia de datos a la memoria central

MC Dis co

9 8 7 6 5 4 3 2 1

1 Tiempo de transferencia (Lectura magnética u óptica)

2 Tiempo de latencia (Rotational delay time or search time)

3 Tiempo de posicionado de la cabeza (Seek time)

4 Tiempo de armado y formateo de datos

5 Tiempo de Controlador o Canal (Channel time)

6 Tiempo de llenado de Buffers ( Queueing time)

7 Tiempo de transferencia de datos (Data transfer time)= Long. de datos/ tasa de transferencia

8 Tiempo de acceso a la Memoria Central.

9 Tiempo de escritura en Memoria.

1+2+3+4 Tiempo de servicio del disco

1+2+3+4+5+6 Tiempo de acceso de E/S

1a9 Tiempo de respuesta de la E/S.

 Performance en los discos
De todos los tiempos involucrados en una lectura/escritura a
disco, queda claro que los dos tiempos a optimizar son:

Tiempo de Latencia
✓ Con discos que giren más rápido.
✓ Interleaving (obsoleto)
✓ Técnicas de cache (como caché de una pista por vez)

Tiempo de búsqueda
✓ Logrando que la cabeza lecto-grabadora deba moverse lo menos posible.
✓ ¿Y cómo hacemos eso? Algoritmos de Planificación de Brazo de Disco
 Planificador FCFS
(First Come First Served)
Cola de Pedidos:100, 200, 45, 120, 10, 130, 60, 70, 30 y 20
Posición de arranque de las cabezas: 50
pistas
Cantidad de pistas recorridas por las cabezas: 745
200 

150


100 

50



 
0
tiempo
 Planificador SSTF
(Shortest Seek Time First)
Planificador SCAN
Planificador C-SCAN
 Planificador LOOK-UP
(Algoritmo del Ascensor)
 Planificador C-LOOK-UP
(Algoritmo del Ascensor Modificado)
 Algoritmos de Planificación
Uno de los cambios más importantes de los últimos tiempos es que las
propias controladoras de los discos tienen sus propios algoritmos para
optimizar el acceso a los bloques de datos, ya que poseen más y mejor
información sobre la ubicación de éstos.

Los S.O. modernos poseen algoritmos de planificación que incluyen

mejoras, como división en múltiples colas, división entre lecturas y
escrituras, entre otras. Algunos ejemplos:
✓ Noop
✓ CFQ
✓ Deadline
✓ BFQ
✓ Anticipatory

¿Qué algoritmo está usando mi distribución GNU/Linux?

cat /sys/block/sda/queue/scheduler
 Dispositivos de estado sólido

✓ Son dispositivos de almacenamiento que no incluyen piezas móviles.

✓ Los tiempos de búsqueda y latencia son muy bajos (no cero!).
✓ Existen implementaciones basadas en:
▪ NVRAM
▪ Memorias Flash
▪ SSD

Para pensar:

Si tengo un S.O. con un dispositivo de estado sólido,

¿qué algoritmo de planificación de I/O me conviene usar?
 File system

➢ Las computadoras pueden almacenar información

en diferentes soportes físicos: disco, cintas, etc. Cada
uno de estos dispositivos tiene su propia
característica y organización física.

➢ El sistema operativo hace una abstracción de las

características físicas de los dispositivos de
almacenamiento para definir una unidad lógica de
almacenamiento llamada archivo (file).

➢ Un archivo es una estructura abstracta de datos que

el Sistema Operativo vincula en el aspecto lógico y en
el físico
• El Sistema de Gestión de Archivos (File System)
se integra con el Kernel, el Administrador de
Memoria Central y el Gestor de Entrada / Salida.
 Sistemas basados en Disco
o Un disco se divide en pistas
o Cada pista se divide en sectores.
o El sector es la mas pequeña unidad de información que
puede ser leída o escrita en un disco.
o Los sectores varían de 512 bytes a 1024
o De 9 a 65 sectores por pista
o Y desde 75 a 3000 pistas por cada superficie.
o Los sistemas mas grandes pueden tener varios platos de
discos (cada plato con 2 superficies: superior e inferior).
o Para acceder a un sector se debe especificar la pista
(cilindro), la superficie o cara (Cabeza Lectora/ Escritora) y
el sector.
o Estos elementos constituyen la dirección en el soporte
(Cylinder, Head, Sector).
o Un cilindro es un conjunto de pistas que están en la
misma posición en el disco, pero en diferentes
platos

o El S.O. trata al disco como a un arreglo

unidimensional de bloques de disco, donde cada
bloque contiene uno más sectores.

o Típicamente las direcciones de un bloque se

incrementan a partir de todos los sectores de una
pista, luego todas las pistas de un cilindro y
finalmente desde cilindro 0 al último del disco.
• Si ns es el número de sectores por pista y np el número
de pistas por cilindro, entonces podemos convertir una
dirección de disco (CHS) dado por cilindro c, superficie h,
sector s a un número de bloque unidimensional b (LBA)

b = s + ns * (h + c * np)
 Objetivos y Funciones del Sistema
de Gestión de Archivos

• El principal objetivo de un Sistema de archivos es

permitir las operaciones y accesos en forma
segura sobre los soportes para almacenar,
modificar, eliminar o recuperar la información

Y administrar el espacio de almacenamiento

secundario.
 Catalogación de los archivos en el
soporte
• Para poder asignar y desasignar espacio en el soporte el Sistema
Operativo divide el disco básicamente en tres áreas:

Área de datos fijos. (Fixed Data Area - FDA, que incluye la

Tabla de Particiones y el Sector de Booteo (partition table
y Boot Sector)

Área de catálogo: área del Espacio libre y del Espacio

ocupado (Free Space List y File Allocation Table). Esta
última está compuesto por un área específico de Directorio
(File Directory Block) de varios niveles, que incluye al
Master File Directory y al User File Directory. (Dinámica)

Área de datos (Donde se localizan físicamente los datos de

los archivos).
 Administración del espacio de
almacenamiento
• La Gestión del Almacenamiento Secundario, básicamente
está representado por la asignación del espacio, cuyo
objetivo es utilizar eficazmente al espacio y posibilitar el
acceso rápido a la información almacenada.

• El espacio de almacenamiento se relaciona entre lo que no

está asignado (libre) y el que está ocupado por los archivos
(asignado) y generalmente se utiliza una tabla para
administrar ese espacio llamada FAT (File Allocation Table).
 Administración Del Espacio Libre
• Bit Map O Bit Vector (Mapa De Bits)

✓Frecuentemente se implementa como un

vector o mapa de bits en la FAT.
✓ Cada bloque del disco se representa con un
bit.
✓Si el bloque está libre se le asigna al bit un
“0”, caso contrario el bit vale un “1” que indica
que está ocupado.
• Ventajas:

• Sencilla implementación.
• Relativamente poco espacio ocupado

• Desventajas:

• No posee grandes desventajas.

(Utilizado por DOS)

 Lista Enlazada de Bloques Libres

• Otra solución es vincular (-link-) todos

los bloques libres, guardando un puntero
al primer bloque libre. Este bloque tiene
un puntero al siguiente bloque libre y así
sucesivamente

• El comienzo de la lista lo marca el puntero

Free Space List Head (FSLH).
• Ventajas:

• Muy poco espacio ocupado

• Desventajas:

Es muy poco eficiente ya que para recorrer

la lista, debemos leer cada bloque del disco

Altamente vulnerable
 Bloques de Direcciones Libres

• Almacena las direcciones de n bloques libres

en el primer bloque libre disponible en el
soporte (en el área de catálogo)
• Se apuntan con un puntero a los primeros
(n-1) bloques que están realmente libres
• Luego el ultimo puntero contiene la dirección
del próximo bloque que contiene las
direcciones de otros n bloques libres

(Utilizado por Linux)

• Ventajas:
• Es mas eficiente en cuanto a velocidad ya
que con leer un solo bloque se conoce la
dirección de una gran cantidad de bloques
libres
• Mientras más espacio haya ocupado en
disco, menos espacio requiere la lista de
bloques libres.
• Desventajas:
Cuando el disco está poco ocupado, la lista
es muy grande y lleva tiempo recorrerla.
 Bloques De Direcciones Libres Contiguas

• Se guarda la dirección del primer bloque

libre y el número de bloques contiguos libres
que le siguen. (en el área de catálogo)
• Cada entrada en la lista de espacios
libres consiste entonces en una dirección en
disco y un número
• Este método es particularmente útil cuando
se utiliza almacenamiento continuo o
secuencial.
Ventajas:

Utiliza menos espacio de almacenamiento

que el método anterior
Muy eficiente para almacenamiento
continuo.
Desventajas:

Si los sectores están muy dispersos, es

poco eficiente
 Métodos de Asignación de espacio
para los Archivos

Se usan tres métodos de asignación de

espacio en disco:

• Contiguo
• vinculado -link-
• indexado.
 Asignación Contigua
• Este método requiere que cada archivo ocupe un conjunto
de direcciones contiguas o consecutivas en disco cuyo
espacio debe ser declarado en la creación del archivo
• La posición del archivo en el disco queda definida por la
dirección del primer bloque y su longitud
• El acceso al bloque b+1 luego del b normalmente no
requiere movimiento de cabeza y a lo sumo solo una pista
• Para un acceso directo al bloque i de un archivo que
comienza en el bloque b, se accede inmediatamente al
bloque b+i.
• Así vemos que para asignación contigua es posible tanto el
acceso secuencial como el directo
• Tabla de archivos: Nombre – Bl. Inicio - Cant. Bl.
Ventajas:
• Es muy fácil acceder a los archivos
• Es ideal para accesos secuenciales ya que la
cabeza no tiene que viajar mucho.
Desventajas:
• A medida que el disco se llena, se torna difícil
encontrar espacio para un nuevo archivo.
• Cuando un archivo se crea, generalmente no se
sabe cuantos bloques va a ocupar.
• Si un archivo tiene que crecer y no tiene mas
espacio consecutivo al final, hay que moverlo a
una nueva localización.
• Hay fragmentación externa
Asignación Dinámica de Almacenamiento
• El espacio en disco puede considerarse como una
colección de segmentos libres y usados, siendo cada
segmento un conjunto contiguo de bloques

• Un segmento libre se lo conoce como un hueco

• El conjunto de huecos es examinado para determinar cual

es el mejor a asignar. Las estrategias mas comunes son:

• First-fit

• Best-fit

• Worst-fit.
• Las simulaciones han demostrado que tanto el First-fit
como el Best-fit son mejores que el Worst-fit tanto en
tiempo como en utilización de espacio

• Compactación o Defragmentación.

• Se compactan todos los huecos en uno solo.

• El costo de este proceso es el tiempo necesario para

efectuarlo.
 Asignación Enlazada o Vincular
(Linkeada)
• Cada archivo es una lista enlazada de
bloques de disco.

• Los bloques pueden estar distribuidos en

cualquier parte del soporte.

• La tabla de archivos contiene el nombre del

archivo, un puntero al primer bloque y un
puntero al último bloque (si corresponde).
 Ventajas:
• No hay fragmentación externa.
• Tampoco es necesario declarar la longitud al
crearlo, ya que puede crecer en tanto existan
bloques libres
• Un archivo puede continuar creciendo tanto como
bloques libres haya en el disco.
Desventajas:
• Los punteros ocupan espacio extra
• Es contraproducente implementar acceso directo
con este método.
• Altamente vulnerable (Una solución parcial es
usar una lista doblemente enlazada )
 Asignación Indexada

• Cada archivo tiene su propio bloque de índice (index

block), en el área de catálogo, que es un vector de
direcciones de bloques en el disco.
• La i-ésima entrada en el l bloque de índices apunta al i-
ésimo bloque del archivo.
• El directorio contiene la dirección del index block.
• Para un archivo más grande se utilizaría un puntero a otro
index block, y para archivos aún más grandes se podría
tener un tercer index block y así sucesivamente.
• Una variante es usar un bloque de índices separado que
apuntan a los distintos bloques índices que a su vez
apuntan a los bloques del archivo
Ventajas:
• Soporta acceso directo y secuencial
• No tiene fragmentación externa
Desventajas:
• El espacio ocupado por punteros del index
block es generalmente mayor que el
ocupado por la asignación enlazada
• Es ineficiente para bases de datos grandes
• Sufre de desperdicio de espacio en disco,
debido al bloque de índices
 Acceso Secuencial
• Es el método mas simple, la información del
archivo se procesa ordenadamente y de a
un registro por vez

• Un read lee la próxima porción del archivo y

automáticamente avanza el puntero de
archivo

• un write agrega datos al final del archivo y

avanza al nuevo fin de archivo
 Acceso Directo
• El archivo esta formado por registros
lógicos de tamaño fijo para permitir que los
programas lean y escriban rápidamente y
sin un orden en particular. Este método se
basa en el modelo de archivo de disco
• El acceso directo permite leer o escribir
bloques en forma arbitraria. Así se puede
leer el bloque 14 y luego el 53 y luego
escribir el 7
 I - Nodos
• Los atributos del archivo se almacenan en el I-nodo
• Cuando se abre un archivo se trae su I-nodo a
memoria
• Un I-nodo incluye 39 bytes de información de
direcciones:
– 10 punteros a bloques de datos
– 1 indirección simple
– 1 indirección doble
– 1 indirección triple
• En UNIX System V el bloque mide 1 Kb

• Cada bloque puede contener 256 punteros a bloque

• Por lo tanto el tamaño máximo de un archivo es:

(10 + 256 + 2562 + 2563) x 1kb ≈ 16 Gb

 Ventajas
• El I-nodo es de tamaño fijo y relativamente
pequeño, por lo tanto puede almacenarse en
memoria durante períodos largos

• A los archivos mas pequeños se puede

acceder con pocas o ninguna indirección

• El tamaño máximo teórico de un archivo es

suficientemente grande para satisfacer
prácticamente todas las aplicaciones
• Soft link (Acceso directo) link simbólico
Crea un nuevo archivo con un bloque de disco
que contiene la información del archivo al que
apunta
• Hard link
Es una referencia nueva en la tabla de archivos
a un archivo que ya existe. (No se puede hacer
en windows)
Un archivo se borra recién cuando se borre el
último hard link de ese archivo
Cada hard link puede tener distintos permisos