Sistemas Operativos
Sistemas Operativos
SISTEMAS
OPERATIVOS
2006 – 2018
ii
INDICE
iii
3.2.7. Monitores 32
3.2.8. Paso de mensajes 34
3.3. Problemas clásicos de sincronización 34
3.3.1. Productor-consumidor con buffer limitado 34
3.3.2. Lector-Escritor 36
3.3.3. Los filósofos comensales 37
3.3.4. Peluquero (barbero) dormilón 38
iv
6.1.3. Tipos de Archivos 72
6.1.4. Atributos de un archive 72
6.1.5. Operaciones con archivos 73
6.2. Directorios 73
6.2.1. Sistemas de directorio jerárquicos 73
6.2.2. Nombres de ruta de Accesos 75
6.2.3. Operaciones con directories 75
6.3. Implementación de Sistemas de Archivos 76
6.3.1. Implementación de archivos 76
6.3.2. Implementación de directories 78
6.3.3. Administración del espacio en disco 80
6.3.4. Confiabilidad del sistema de archivos 81
6.3.5. Desempeño del sistema de archivos 84
6.4. Ejemplos de Sistemas de Archivos 84
6.4.1. Sistemas de archivos Windows 84
6.4.1.1. FAT (File Allocation Table) 84
6.4.1.2. HPFS (sistemas de archivos de alto rendimiento) 86
6.4.1.3. NTFS (New Technology File System) 88
6.4.1.4. ReFS (Sistema de archivos resistente a errores) 92
6.4.2. Sistemas de archivos UNIX 94
6.4.2.1. MINIX 94
6.4.2.2. Extended file system 95
6.4.2. 3. ext2 (second extended filesystem) 95
6.4.2.4. ext3 (third extended filesystem) 96
6.4.2.5. ext4 (fourth extended filesystem) 98
v
vi
Sistemas Operativos - UMSS
Tema I
INTRODUCCIÓN A LOS SISTEMAS OPERATIVOS
A pesar de que se usan sistemas operativos casi a diario en dispositivos móviles, celulares,
computadoras, etc.; es difícil definir qué es un sistema operativo ya que realizan dos funciones
diferentes y al mismo tiempo complementarias:
• Proveer una máquina virtual o extendida (interfaz), es decir, un ambiente en el cual el
usuario pueda ejecutar programas de manera conveniente, protegiéndolo de los detalles y
complejidades del hardware.
• Administrar eficientemente (optimizar) los recursos del computador (componentes tanto
físicos como lógicos: el procesador, memoria, dispositivos de entrada/salida o archivos) para
soportar los requerimientos.
El primer computador fue diseñado por el matemático inglés Charles Babbage hace cerca de siglo
y medio. Era un computador totalmente mecánico, que Babbage nunca pudo construir,
principalmente debido a que la tecnología de la época no era capaz de producir las piezas con la
precisión requerida.
Después de eso, poco se hizo hasta la segunda guerra, alrededor de 1940 se construyeron las
primeras máquinas calculadoras usando tubos de vacío.
Estas máquinas de varias toneladas de peso eran
diseñadas, construidas, programadas y operadas por el
mismo grupo de personas. No había ni lenguajes de
programación, ni compiladores; mucho menos sistema
operativo. Cada programa se escribía en lenguaje de
máquina, usando tableros con enchufes e interruptores
y tenía que manejar todo el sistema (lo que era factible
gracias a que el programador era el mismo que diseñó y
construyó la máquina). Con el tiempo se introdujeron las
tarjetas perforadas, para reemplazar al tablero, pero el
sistema era esencialmente el mismo.
Ahora los programadores, en vez de decirle al operador qué programa cargar, debían informárselo
al monitor (mediante tarjetas de control especiales). Esto se conoce como procesamiento por lotes,
donde, el programador deja su grupo de tarjetas, y después vuelve a retirar la salida que se emite
por la impresora (y que puede ser nada más que la notificación de que el programa tenía un error
de sintaxis).
Pero el sistema sigue siendo esencialmente un sistema de procesamiento por lotes; los
programadores no interactúan en línea con el computador, los tiempos de respuesta desde que se
deja un trabajo para ejecución hasta conocer el resultado son demasiado grandes. De ahí nace el
concepto de tiempo compartido que es una variante de la multiprogramación en la cual una CPU
atiende simultáneamente los requerimientos de varios usuarios conectados en línea a través de
terminales tontas.
Ya que los usuarios humanos demoran bastante entre la emisión de un comando y otro, una sola
CPU es capaz de atender, literalmente, a cientos de ellos simultáneamente (bueno, en realidad,
uno después de otro, pero los usuarios tienen la ilusión de la simultaneidad). Por otra parte,
cuando no hay ningún comando que ejecutar proveniente de un usuario interactivo, la CPU puede
cambiar a algún trabajo por lote.
En 1974, Intel presentó el microprocesador 8080 de ocho bits y buscó un sistema operativo para
1
ese procesador. Gary Kildall y un amigo construyeron primero un controlador para la unidad de
disco flexible de ocho pulgadas recién salida de Shugart Associates, enganchando así el disquete
al 8080, y dando lugar al primer microcomputador con disco. Luego Kildall escribió un sistema
1
Gary Kildall (1942 - 1994) fue el creador del sistema operativo CP/M (posteriormente DR-DOS y de la interfaz gráfica de usuario GEM
Desktop, y fundador de Digital Research)
operativo basado en disco llamado CP/M (Control Program for Microcomputers). Intel no pensó que
los microcomputadores basados en disco fueran a tener mucho futuro, de manera que cuando
Kildall pidió quedarse con los derechos del CP/M, Intel se lo concedió. Kildall formó entonces una
compañía, Digital Research, para seguir desarrollando y vender el sistema operativo CP/M. En
1977, Digital Research reescribió CP/M para que pudiera ejecutarse en los numerosos
microcomputadores que utilizaban el 8080, el Zilog Z80 u otros microprocesadores. Se escribieron
muchos programas de aplicación para ejecutarse sobre CP/M, lo que permitió a este sistema
operativo dominar por completo el mundo de los microcomputadores durante unos cinco años.
A principios de la década de 1980, IBM diseñó el PC (Personal Computer) y buscó software que se
2
ejecutara en él. Gente de IBM se puso en contacto con Bill Gates para utilizar bajo licencia su
intérprete de BASIC. También le preguntaron si sabía de algún sistema operativo que funcionara
sobre el PC. Gates sugirió a IBM que se pusiera en contacto con Digital Research, que entonces
era la compañía de sistemas operativos dominante. Kildall rechazó reunirse con IBM.
Consecuentemente, IBM fue de vuelta con Gates para preguntarle si podría ofrecerle un sistema
operativo. Gates se percató de que un fabricante de computadores local, Seattle Computer
Products, tenía un sistema operativo apropiado, DOS (Disk Operating System). Gates se reunió
con el fabricante y se ofreció a comprarle el sistema (supuestamente por 50.000 dólares). Luego
Gates ofreció a IBM un paquete DOS/BASIC, que IBM aceptó. IBM pidió que se hicieran ciertas
modificaciones en el sistema, por lo que Gates contrató a la persona que había escrito DOS, Tim
3
Paterson , como empleado de su naciente compañía, Microsoft, para que las llevara a cabo. El
sistema revisado se rebautizó con el nombre de MS-DOS (Microsoft Disk Operating System) y
pronto dominó el mercado del IBM PC. Para cuando el PC/AT de IBM salió a la venta el 1983 con
la CPU 80286 de Intel, MS- DOS estaba firmemente afianzado mientras que CP/M agonizaba. Más
tarde se utilizó ampliamente MS-DOS en el 80386 y el 80486. Aunque la versión inicial de MS-DOS
era más bien primitiva, sus versiones posteriores incluyeron funciones más avanzadas, incluyendo
muchas procedentes de UNIX. (Microsoft tenía perfecto conocimiento de UNIX, e incluso vendió
durante los primeros años de la compañía una versión para microcomputador a la que llamó
XENIX.)
CP/M, MS-DOS y otros sistemas operativos para los primeros microcomputadores obligaban al
usuario a introducir comandos a través del teclado. En un momento dado la cosa cambió, gracias a
4
las investigaciones hechas por Doug Engelbart en el Stanford Research Institute, en los años
sesenta. Engelbart invento la GUI (Graphical User Interface; Interfaz Gráfica de Usuario), provista
de ventanas, iconos, menús y ratón. Los investigadores de Xerox PARC adoptaron estas ideas,
5
incorporándolas a las máquinas que fabricaban. Steve Jobs , coinventor de la computadora Apple
en el garaje de su casa, visitó PARC, vio la GUI, y de inmediato se dio cuenta de su valor
potencial, algo que, de forma asombrosa, no hizo la gerencia de Xerox. Jobs se dedicó entonces a
construir el computador Lisa, que resultó demasiado caro y fracasó comercialmente. El segundo
intento de Jobs, el Apple Macintosh, fue un enorme éxito, no sólo porque era mucho más
económico que Lisa, sino también porque era amigable con el usuario (user friendly), lo que
significa que iba dirigido a usuarios que no sólo carecían de conocimientos sobre computadores,
sino que además no tenían ni la más mínima intención de aprender. Microsoft decidió desarrollar
un sucesor para MS-DOS y estuvo fuertemente influenciado por el éxito del Macintosh. La
compañía produjo un sistema basado en una GUI al que llamó Windows, y que originalmente se
ejecutaba por encima de MS-DOS (es decir, era más un shell que un verdadero sistema operativo).
Durante cerca de 10 años, de 1985 a 1995, Windows no fue más que un entorno gráfico por
encima de MS-DOS. Sin embargo, en 1995 salió a la circulación una versión autónoma de
Windows, Windows 95, que incluía muchas funciones del sistema operativo y sólo utilizaba el
2 William Henry Gates III (1955), conocido como Bill Gates, es un empresario, informático y filántropo estadounidense, cofundador de la
empresa de software Microsoft
3 Tim Paterson (1956) ingeniero informático, que escribió el sistema operativo QDOS.
4 Douglas Carl Engelbart (1925 - 2013) fue un inventor estadounidense, descendiente de noruegos. Es conocido por inventar el ratón, y fue
un pionero de la interacción humana con las computadoras, incluyendo el hipertexto y las computadoras en red.
5 Steven Paul Jobs (1955- 2011), más conocido como Steve Jobs, fue un empresario y magnate de los negocios del sector informático y de
la industria del entretenimiento estadounidense. Fue cofundador y presidente ejecutivo de Apple Inc.
sistema MS-DOS subyacente para arrancar y ejecutar programas antiguos de MS-DOS. En 1998
salió una versión ligeramente modificada de este sistema, llamada Windows 98. No obstante tanto
Windows 95 como Windows 98 contienen todavía una buena cantidad de lenguaje ensamblador
Intel de 16 bits. Otro sistema operativo de Microsoft es Windows NT (Nueva Tecnología), que es
compatible hasta cierto punto con Windows 95, pero que internamente está reescrito desde cero.
Se trata de un sistema completamente de 32 bits. Microsoft confiaba en que la primera versión de
NT exterminaría a MS-DOS y todas las demás versiones anteriores de Windows porque se trata de
un sistema enormemente superior, pero no fue así. Sólo con Windows NT 4.0 comenzó a
adoptarse ampliamente el sistema, sobre todo en redes corporativas. La versión 5 de Windows NT
se rebautizó como Windows 2000 a principios de 1999, con la intención de que fuera el sucesor
tanto de Windows 98 como de Windows NT 4.0. Eso tampoco funcionó como se pensaba, así que
Microsoft sacó una versión más de Windows 98 llamada Windows Me (Millennium edition). Las
versiones de Windows XP, Vista, 7, 8 y 10 están basados en Windows NT.
Un sistema operativo crea el entorno en el que se ejecutan los programas. Podemos crear un
sistema tan grande y complejo como un sistema operativo sólo si lo dividimos en porciones más
pequeñas. Cada una de estas partes deberá ser un componente bien delineado del sistema, con
entradas, salidas y funciones cuidadosamente definidas. La interfaz entre el S. O. y los programas
del usuario se define como el conjunto de instrucciones ampliadas que proporciona el S. O. y son
las “llamadas al sistema”.
6
Linus Benedict Torvalds (1969) es un ingeniero de software finlandés estadounidense, conocido por iniciar y mantener el desarrollo
del kernel Linux
7
Andrew Stuart Tanenbaum (1944), es profesor de ciencias de la computación de la Universidad Libre de Ámsterdam, Países Bajos. Es el
creador de Minix, una réplica gratuita del sistema operativo UNIX con propósitos educativos, y por sus libros sobre ciencias de la
computación.
En general, un programa puede alterar el normal funcionamiento del sistema de las siguientes
formas:
• Ejecutando una instrucción de E/S ilegal (por ejemplo, que borre todos los archivos del disco).
• Sobrescribiendo áreas de la memoria que pertenecen al sistema operativo.
• No devolviendo el control de la CPU al sistema operativo.
Para evitar esto, es indispensable el apoyo del hardware, a través de los siguientes mecanismos:
• Modo usuario.
• Modo sistema (o privilegiado, protegido o supervisor).
El bit de modo indica el modo de operación actual. Cuando se enciende el computador y se carga
el sistema operativo, se comienza en modo sistema. El sistema operativo siempre cambia a modo
usuario antes de pasar el control a un proceso de usuario. Cuando ocurre una interrupción, el
hardware siempre cambia a modo sistema. De esta manera, el sistema operativo siempre ejecuta
en modo sistema. Hay ciertas operaciones críticas que sólo pueden ser ejecutadas en modo
sistema.
El kernel es grande y cumple todas las funciones del sistema operativo. Es el caso de MS-DOS y
de las primeras versiones de Unix.
Incluso en los sistemas monolíticos es posible tener al menos un poco de estructura. Los servicios
(llamadas al sistema) proporcionados por el sistema operativo se solicitan colocando los
parámetros en lugares bien definidos, como en registros o en la pila, y ejecutando después una
instrucción de trampa especial conocida como llamada al kernel o llamada al supervisor.
Esta instrucción conmuta la máquina del modo de usuario al modo de kernel y transfiere el control
al sistema operativo, lo cual se muestra como evento (1) en la figura. (La mayor parte de las CPU
tienen dos modos: modo de kernel, para el sistema operativo, en el que se permite todas las
instrucciones; y modo de usuario, para programas de usuario, en el que no se permiten
instrucciones de E/S y de ciertos otros tipos.)
A continuación, el sistema operativo examina los parámetros de la llamada para determinar cuál
llamada al sistema se ejecutará; esto se muestra como (2) en la figura. Acto seguido, el sistema
operativo consulta una tabla que contiene en la ranura k un apuntador al procedimiento que lleva a
cabo la llamada al sistema k. Esta operación, marcada con (3), identifica el procedimiento de
servicio, mismo que entonces se invoca. Una vez que se ha completado el trabajo y la llamada al
sistema ha terminado, se devuelve el control al programa de usuario (paso 4) a fin de que pueda
continuar su ejecución con la instrucción que sigue a la llamada al sistema.
La Capa 2 administra la comunicación entre cada proceso y la consola del operador (Por sobre
esta capa, cada proceso tiene su propia consola de operador).
La Capa 3 controla los dispositivos de e / s y almacena en buffers los flujos de información entre
ellos (Por sobre la capa 3 cada proceso puede trabajar con dispositivos abstractos de E/S en vez
de con dispositivos reales).
La Capa 4 aloja los programas del usuario, los programas. del usuario no tienen que preocuparse
por el proceso, memoria, consola o control de e / s.
La Capa 5 localiza el proceso operador del sistema.
Pero estas máquinas virtuales no son máquinas extendidas (con archivos y otras abstracciones),
como es lo habitual, sino copias exactas de la máquina original. Cada máquina virtual puede
ejecutar un sistema operativo diferente, construido para operar en la máquina original. La CPU se
comparte con planificación de CPU, la memoria con memoria virtual, y el disco se particiona.
No es simple de implementar. La máquina original tiene dos modos: monitor y usuario. El monitor
de la máquina virtual opera en modo monitor, y cada máquina virtual puede operar sólo en modo
usuario. En consecuencia se debe proveer un modo usuario virtual y un modo monitor virtual. Las
acciones que en la máquina real causan el paso de modo usuario a modo monitor deben causar el
paso de modo usuario virtual a modo monitor virtual. ¿Cómo? Cuando un proceso de usuario hace
una llamada al sistema, el control se transfiere al monitor de la máquina virtual, quien devuelve el
control a la máquina virtual, simulando una llamada al sistema. Si en esas condiciones (operando
en modo monitor virtual, que en realidad no es más que modo usuario físico), se intenta accesar el
hardware (por ejemplo, una operación de E/S), el control vuelve al monitor de la máquina virtual,
quien efectúa, controladamente, la operación).
Las ventajas son que facilita el desarrollo de sistemas operativos (cuando la máquina es cara y no
se puede entregar una a cada programador). Sin este esquema, es necesario bajar la máquina
cada vez que quiere probar una modificación al sistema. También permite resolver problemas de
compatibilidad. Por ejemplo, si se quiere desarrollar un nuevo sistema operativo, pero se quiere
que los miles de programas DOS que existen sigan corriendo, se puede usar esta solución,
asignando una máquina virtual a cada programa DOS que se ejecute. Se puede ir más lejos, y
crear una máquina virtual distinta a la original. Así es como Windows para arquitectura Intel se
puede ejecutar, por ejemplo en una Silicon Graphics. El problema es que, en este caso, hay que
interpretar cada instrucción (en lugar de ejecutarla directamente).
1.4.2.3. Exokernel
Con el VM/370, cada proceso de usuario obtiene una copia exacta del computador real. Con el
modo 8086 virtual del Pentium, cada proceso de usuario obtiene una copia exacta de un
computador diferente. Yendo un paso más lejos, algunos investigadores del M.I.T. construyeron un
sistema que proporciona a cada usuario un clon del computador real, pero con un subconjunto de
los recursos. Así, una máquina virtual podría obtener los bloques de disco del 0 al 1023, la
siguiente podría recibir los bloques del 1024 al 2047, y así de forma sucesiva.
En la capa más baja, ejecutándose en modo núcleo, está un programa llamado exokernel. Su labor
consiste en asignar recursos a las máquinas virtuales y luego comprobar cualquier intento de
utilizarlos para garantizar que ninguna máquina trate de utilizar los recursos de cualquier otra.
Cada máquina virtual a nivel de usuario puede ejecutar su propio sistema operativo, como sobre el
VM/370 y los 8086 virtuales del Pentium, sólo que cada una está limitada a los recursos que
solicitó y que le fueron asignados.
La ventaja del esquema de exokernel es que ahorra una capa de conversión. En los otros diseños,
cada máquina virtual cree que tiene su propio disco, cuyos bloques van desde 0 hasta algún
máximo, lo que obliga al monitor de la máquina virtual a mantener tablas para convertir las
direcciones de disco (y todos los demás recursos). Con el exokernel no es necesario efectuar esa
conversión, pues lo único que tiene que hacer es mantenerse al tanto de qué recursos se han
asignado a qué máquinas virtuales. Este método sigue teniendo la ventaja de separar la
multiprogramación (en el exokernel) y el código del sistema operativo del usuario (en el espacio del
usuario), pero con menos sobrecarga porque la única tarea del exokernel es evitar que las
máquinas virtuales se interfieran mutuamente.
procesos de usuario. Para solicitar un servicio, tal como la lectura de un bloque de un archivo, un
proceso de usuario (que ahora se denomina proceso cliente) envía una solicitud a un proceso
servidor, que realiza el trabajo y devuelve la repuesta.
Para solicitar un servicio (por ej.: lectura de un bloque de cierto archivo) según el modelo cliente –
servidor, el proceso del usuario (proceso cliente) envía la solicitud a un proceso servidor, realiza el
trabajo y regresa la respuesta.
Algunas funciones del S. O., ( por ej. el cargado de comandos en los registros físicos del
dispositivo de e/s), presentan problemas especiales y distintas soluciones:
• Ejecución en modo núcleo, con acceso total al hardware y comunicación con los demás
procesos mediante el mecanismo normal de mensajes.
• Construcción de un mínimo de mecanismos dentro del núcleo manteniendo las decisiones de
política relativas a los usuarios dentro del espacio del usuario.
Minix [Tanenbaum, 1998], Mach [Accetta, 1986] y Amoeba [Mullender, 1990] son ejemplos de
sistemas operativos que siguen este modelo. Windows NT también sigue esta filosofía de diseño,
aunque muchos de los servidores (el gestor de procesos, gestor de E/S, gestor de memoria, etc.)
se ejecutan en modo núcleo por razones de eficiencia.
Tema II
GESTIÓN DE PROCESOS
2.1. PROCESO.
En todos los computadores actuales, se pueden hacer varias cosas a la vez, mientras está
ejecutando un programa de usuario, puede perfectamente también estar leyendo de un disco e
imprimiendo texto en una pantalla o una impresora. En un sistema multiprogramado la CPU
(Unidad Central de Proceso) también conmuta de unos programas a otros, ejecutando cada uno de
ellos durante decenas o cientos de milisegundos. Aunque, estrictamente hablando, en cualquier
instante de tiempo la CPU sólo está ejecutando un programa, en el transcurso de un segundo ha
podido estar trabajando sobre varios programas, dando entonces a los usuarios la impresión de un
cierto paralelismo (pseudoparalelismo), en contraste con el auténtico paralelismo del hardware de
los sistemas multiprocesador (que tienen dos o más CPUs compartiendo la misma memoria física).
Seguir la pista de múltiples actividades paralelas resulta muy complicado, por ese motivo los
diseñadores de los sistemas operativos han desarrollado un modelo conc eptual evolucionado (el
de los procesos secuenciales) que permite tratar el paralelismo de una forma más fácil.
Debe hacerse una distinción entre un programa y un proceso. Un programa es una entidad estática
constituida por sentencias de programa que definen la conducta del proceso cuando se ejecutan
utilizando un conjunto de datos. Un proceso es una entidad dinámica que ejecuta un programa
sobre un conjunto de datos utilizando los recursos del sistema operativo. Dos o mas procesos
podrían estar ejecutando el mismo programa, empleando sus propios datos y recursos, por
ejemplo, si dos o más usuarios están usando simultáneamente el mismo editor de texto. El
programa es el mismo, pero cada usuario tiene un proceso distinto (y con distintos datos).
Por analogía al preparar una receta de una torta. El programa es la receta, el proceso es la
actividad que consiste en leer la receta, mezclar los ingredientes y hornear la torta.
Cuando un sistema operativo arranca, se crean típicamente varios procesos. Algunos de esos
procesos son procesos foreground (en primer plano), esto es, procesos que interactúan con los
usuarios y realizan trabajo para ellos. Otros son procesos background (en segundo plano), que no
están asociados con usuarios particulares, sino que tienen alguna función específica. Los procesos
que se ejecutan como procesos background para llevar a cabo alguna actividad tal como el correo
electrónico, las páginas web, la impresión de archivos de salida, etc., se denominan demonios en
Unix o servicios en Windows. Los sistemas grandes tienen comúnmente docenas de ellos. En
UNIX, el programa ps puede utilizarse para listar los procesos que están en marcha. En Windows
se utiliza el administrador de tareas.
Adicionalmente a los procesos creados en el momento del arranque, también pueden crearse
nuevos procesos después. A menudo un proceso en ejecución puede hacer llamadas al sistema
para crear uno o más procesos nuevos para que le ayuden en su trabajo.
En sistemas interactivos los usuarios pueden arrancar un programa tecleando un comando o
haciendo clic (dos veces) con el ratón sobre un icono. Realizando cualquiera de esas acciones se
consigue que comience un nuevo proceso y se ejecute el programa correspondiente. En sistemas
UNIX basados en comandos y ejecutando X-Windows, el nuevo proceso creado se ejecuta sobre
la ventana en la cual se le activó. En Windows, cuando un proceso comienza no tiene ninguna
ventana asignada, aunque puede crear una o más. En ambos sistemas, los usuarios pueden tener
múltiples ventanas abiertas a la vez, cada una de ellas ejecutando algún proceso. Utilizando el
ratón, el usuario puede seleccionar una ventana e interactuar con el proceso, por ejemplo,
proporcionando datos de entrada cuando sean necesarios.
La última situación que provoca la creación de procesos se aplica sólo a los sistemas en batch (por
lotes) que podemos encontrar en los grandes mainframes. En esos sistemas los usuarios pueden
lanzar (submit) al sistema trabajos en batch (posiblemente de forma remota). Cuando el sistema
operativo detecta que dispone de todos los recursos necesarios para poder ejecutar otro trabajo,
crea un nuevo proceso y ejecuta sobre él el siguiente trabajo que haya en la cola de entrada.
En UNIX sólo existe una llamada al sistema para crear un nuevo proceso: fork. Esta llamada crea
un clon (una copia exacta) del proceso que hizo la llamada. Después del fork, los dos procesos, el
padre y el hijo, tienen la misma imagen de memoria, las mismas variables de entorno y los mismos
archivos abiertos. Eso es todo lo que hay. Usualmente, a continuación el proceso hijo ejecuta
execve o una llamada al sistema similar para cambiar su imagen de memoria y pasar a ejecutar un
nuevo programa. En Windows, una única llamada al sistema de Win32, CreateProcess, realiza
tanto la creación del proceso como la carga del programa correcto dentro del nuevo proceso. Tanto
en UNIX como en Windows, después de crear un proceso, tanto el padre como el hijo cuentan con
sus propios espacios de direcciones disjuntos.
• Nuevo (new).
• Ejecutándose (running). El proceso está siendo ejecutado en la CPU. Por lo tanto a lo
más un proceso puede estar en este estado en un computador uniprocesador.
• Listo para ejecutar (ready). El proceso está en condiciones de ejecutarse, pero debe
esperar su turno de CPU.
• Bloqueado o En espera (waiting) El proceso no está en condiciones de ejecutarse. Está
esperando que algún evento ocurra, como la finalización de una operación de E/S.
También se dice que está suspendido o en espera.
• Terminado (terminated)
Se puede establecer una cola de Listos para los procesos “listos” y una cola de Bloqueados para
los “bloqueados”. La cola de Listos se mantiene en orden prioritario y la cola de Bloqueados está
desordenada, ya que los procesos se desbloquean en el orden en que tienen lugar los eventos que
están esperando.
Al admitirse un trabajo en el sistema se crea un proceso equivalente y es insertado en la última
parte de la cola de Listos.
La asignación de la CPU al primer proceso de la cola de Listos se denomina “Despacho”, que es
ejecutado por una entidad del Sistema Operativo llamada “Despachador” (dispatcher).
El “Bloqueo” es la única transición de estado iniciada por el propio proceso del usuario, puesto que
las otras transiciones son iniciadas por entidades ajenas al proceso.
El planificador (scheduler) forma parte del núcleo del sistema operativo. Entra en ejecución cada
vez que se activa el sistema operativo y su misión es seleccionar el proceso que se ha de ejecutar
a continuación.
El activador (dispatcher) también forma parte del sistema operativo y su función es poner en
ejecución el proceso seleccionado por el planificador. Debe ser muy rápido pues una de sus
funciones es encargarse del cambio de contexto (context switch). Al tiempo entre detener un
proceso y comenzar a correr otro se le llama dispatch latency.
El dispatcher es también el que se encarga de pasar a modo usuario el proceso que esta activando
y “saltar” a la dirección de la instrucción que comienza la ejecución del programa.
con el contador de programa, esta información de estado se debe guardar cuando ocurre una
interrupción, para que el proceso pueda continuar correctamente después.
• Información para planificación: Esta información incluye una prioridad del proceso, punteros a
colas de planificación y cualquier otro parámetro de planificación que haya.
• Información para administración de memoria: Esta información puede incluir datos tales como
el valor de los registros de base y límite, las tablas de páginas o las tablas de segmentos,
dependiendo del sistema de memoria empleado por el sistema operativo.
• Información de estado de E/S: La información incluye la lista de dispositivos de E/S asignadas
a este proceso, una lista de archivos abiertos, etcétera.
• Estadísticas y otros: tiempo real y tiempo de CPU usado, identificador del proceso, identificador
del dueño, tiempo real consumido, límites de tiempo, números de cuenta, números de trabajo
o proceso, y demás.
Cuando el Sistema Operativo cambia la atención de la CPU entre los procesos, utiliza las áreas de
preservación del PCB para mantener la información que necesita para reiniciar el proceso cuando
consiga de nuevo la CPU.
botella tan importante para el desempeño del sistema operativo se emplean estructuras nuevas
(hilos) para evitarla hasta donde sea posible.
Por ejemplo, en Unix, cuando se carga el sistema operativo, se inicializa un proceso init. Este
proceso lee un archivo que dice cuántos terminales hay, y crea un proceso login para cada
terminal, que se encarga de solicitar nombre y contraseña. Cuando un usuario entra, login
determina qué shell le corresponde al usuario, y crea otro proceso para ejecutar esa shell. A su
vez, la shell crea más procesos según los comandos que ejecute el usuario, generándose así todo
un árbol de procesos: cada proceso tiene cero o más hijos, y exactamente un padre (salvo init, que
no tiene padre). Haciendo una analogía en Windows, aun cuando este sistema operativo no
mantiene esta jerarquía y todos son iguales, unos de los primeros procesos seria System, luego
Winlogon para crear una sesión y sobre ella crea su shell que es el Explorer, en el cual se
ejecutaran todos los demás programas como hijos de este proceso.
En muchos aspectos los procesos livianos son similares a los procesos pesados, comparten el
tiempo de CPU, y a lo más un thread está activo (ejecutando) a la vez, en un monoprocesador. Los
otros pueden estar listos o bloqueados. Pero los procesos pesados son independientes, y el
sistema operativo debe proteger a unos de otros, lo que acarrea algunos costos. Los procesos
livianos dentro de un mismo proceso pesado no son independientes, cualquiera puede acceder a
toda la memoria correspondiente al proceso pesado. En ese sentido, no hay protección entre
threads, nada impide que un thread pueda escribir, por ejemplo, sobre el stack de otro.
POSIX (Linux) especifica una serie de políticas de planificación, aplicables a procesos pesados y
procesos ligeros, que debe implementar cualquier sistema operativo que ofrezca esta interfaz. En
Windows la unidad básica de ejecución es el proceso ligero y, por tanto, la planificación se realiza
sobre este tipo de procesos.
Un proceso retiene el control de la CPU hasta que ocurra alguna de las siguientes situaciones:
• La libera voluntariamente.
• El reloj la interrumpe.
• Alguna otra interrupción atrae la atención de la CPU.
• Planificación de alto nivel (largo plazo o long term). Determina a qué trabajos se les va a
permitir competir activamente por los recursos del sistema, lo cual se denomina Planificación
de admisión.
• Planificación de nivel intermedio (mediano plazo o medium term). Determina a qué procesos se
les puede permitir competir por la CPU. Responde a fluctuaciones a corto plazo en la carga del
Los distintos Sistemas Operativos utilizan varias Políticas de Planificación, que se instrumentan
mediante Mecanismos de Planificación.
• Batch (lotes)
• Interactivo
• Tiempo Real.
En los sistemas en batch, no existen usuarios que estén esperando impacientemente por una
rápida respuesta ante sus terminales. En consecuencia, son aceptables los algoritmos no
expulsores, o los algoritmos expulsores con largos periodos de tiempo para cada proceso. Con
este enfoque se reduce el número de cambios de proceso, mejorando por tanto el rendimiento.
En un entorno con usuarios interactivos es indispensable que haya expulsiones para impedir que
un proceso acapare la CPU, negando cualquier servicio de la CPU a los demás. Incluso aunque
ningún proceso tenga intención de ejecutarse eternamente, es posible que debido a un error en el
programa un proceso mantenga parados a todos los demás indefinidamente. La expulsión es
necesaria para impedir ese comportamiento.
En los sistemas con restricciones de tiempo real, por extraño que parezca, la expulsión es algunas
veces innecesaria debido a que los procesos saben que no pueden ejecutarse durante largos
periodos de tiempo y usualmente hacen su trabajo y rápidamente se bloquean. La diferencia con
los sistemas interactivos es que los sistemas en tiempo real sólo ejecutan programas pensados
como parte de una misma aplicación. Los sistemas interactivos por el contrario son sistemas de
propósito general y pueden ejecutar programas arbitrarios no cooperantes o incluso maliciosos.
Es un algoritmo que no usa expropiación, y atiende a los procesos por estricto orden de llegada a
la cola de listos (READY). Cada proceso se ejecuta hasta que termina, o hasta que hace una
llamada bloqueante (de E/S), o sea, ejecuta su fase de CPU completa. El código para implementar
este algoritmo es simple y comprensible. Pero el tiempo promedio de espera puede ser largo.
Considerando que los procesos P1, P2 y P3 están LISTOS para ejecutar su siguiente fase de CPU,
cuya duración será de 24, 3 y 3 milisegundos, respectivamente. Si ejecutan en el orden P1, P2, P3,
entonces los tiempos de espera son: 0 para P1, 24 para P2 y 27 para P3, o sea, en promedio, 17
ms. Pero si se ejecutan en orden P2, P3, P1, entonces el promedio es sólo 3 ms. En consecuencia,
FCFS no asegura para nada que los tiempos de espera sean los mínimos posibles; peor aún, con
un poco de mala suerte pueden llegar a ser los máximos posibles.
Suponiendo que se tiene un proceso intensivo en CPU (CPU bound) y varios procesos intensivos
en E/S (I/O bound). Entonces podría pasar lo siguiente: El proceso intensivo en CPU toma la CPU
por un período largo, suficiente como para que todas las operaciones de E/S pendientes se
completen. En esa situación, todos los procesos están LISTOS, y los dispositivos desocupados. En
algún momento, el proceso intensivo en CPU va a solicitar E/S y va a liberar la CPU. Entonces van
a ejecutar los otros procesos, pero como son intensivos en E/S, van a liberar la CPU muy
rápidamente y se va a invertir la situación: todos los procesos van a estar BLOQUEADOS, y la
CPU desocupada. Este fenómeno se conoce como efecto convoy, y se traduce en una baja
utilización tanto de la CPU como de los dispositivos de E/S. Obviamente, el rendimiento mejora si
se mantienen ocupados la CPU y los dispositivos (o sea, conviene que no haya colas vacías).
Suponiendo que se tiene tres procesos cuyas próximas fases de CPU son de a, b y c milisegundos
de duración. Si ejecutan en ese orden, el tiempo medio de espera es:
(0 + a + (a + b))/3 = (2a+b)/3
El primer proceso que se ejecute es el que tiene mayor incidencia en el tiempo medio, y el último,
tiene incidencia nula. En conclusión, el tiempo medio se minimiza si se ejecuta siempre el proceso
con la menor próxima fase de CPU que esté LISTO. Además, es una buena manera de prevenir el
efecto convoy. Lo malo es que para que esto funcione, hay que adivinar el futuro, pues se requiere
conocer la duración de la próxima fase de CPU de cada proceso.
Lo que se hace es predecir la próxima fase de CPU en base al comportamiento pasado del
proceso, usando un promedio exponencial. Suponiendo que la predicción para la n-ésima fase es
Tn, entonces, se actualiza el estimador para predecir Tn+1
El parámetro alpha, entre 0 y 1, controla el peso relativo de la última fase en relación a la historia
pasada.
j n+1
Tn+1 = (1-alpha) Tn + alpha(1-alpha) Tn-1 + ... + alpha (1-alpha) Tn-j + ... + alpha T0
Mientras más antigua la fase menos incidencia tiene en el estimador. Un valor atractivo para alpha
es 1/2, ya que en ese caso sólo hay que sumar los valores y dividir por dos.
Si el proceso no va a usar todo ese tiempo, usa lo necesario y libera la CPU. Se elige entonces
otro proceso de la cola. Si excede el quantum, se produce una interrupción.
En ambos casos al dejar la CPU hay un cambio de contexto. El tiempo promedio de espera puede
ser largo. Su performance depende fuertemente de la elección del quantum. Y el tiempo gastado
en el cambio de contexto es una variable que se debe tener muy en cuenta. Se debe determinar un
quantum que sea mucho mayor que el tiempo de cambio de contexto. Se utiliza en los sistemas de
tiempo compartido (time-sharing). El punto interesante es encontrar el quantum adecuado. Si es
muy grande, se degenera en FCFS, pero tampoco puede ser demasiado pequeño, porque
entonces el costo en cambios de contexto es preponderante.
Por ejemplo, si un cambio de contexto toma 5 ms, y se fija el quantum en 20 ms, entonces 20% del
tiempo de la CPU se perderá en sobrecosto. Un valor típico es 100 ms. Una regla que suele usarse
es que el 80% de las fases de CPU deben ser de menor duración que un quantum. Con respecto a
FCFS, se mejora el tiempo de respuesta y la utilización de la CPU, ya que se mantienen más
balanceadas las colas listos (READY) y bloqueadas (BLOCKED). Pero RR tampoco asegura que
los tiempos de espera sean los mínimos posibles. Usando el mismo ejemplo anterior, y
considerando un quantum de 4ms, pero sin considerar costos de cambio de contexto, si el orden
es P1, P2, P3 entonces el tiempo medio de espera es 5.66ms (P1 espera 6ms, P2 espera 4ms. y
P3 espera 7ms.)
Existen algoritmos que contemplan esta situación dividiendo la cola de listos (ready) en distintas
colas según el tipo de proceso, estableciendo una competencia entre las colas y entre los procesos
del mismo tipo entre si. Por ejemplo, se puede tener una cola para
• Procesos de sistema.
• Procesos interactivos.
• Procesos de los alumnos.
• Procesos por lotes.
Cada cola usa su propio algoritmo de planificación, pero se necesita un algoritmo de planificación
entre las colas. Una posibilidad es prioridad absoluta con expropiación. Otra posibilidad: asignar
tajadas de CPU a las colas. Por ejemplo, a la cola del sistema se le puede dar el 60% de la CPU
para que haga RR, a la de procesos por lotes el 5% para que asigne a sus procesos según FCFS,
y a las otras el resto.
Por otra parte, se podría hacer que los procesos migren de una cola a otra. Por ejemplo: varias
colas planificadas con RR, de prioridad decreciente y quantum creciente. La última se planifica con
FCFS. Un proceso en la cola i que no termina su fase de CPU dentro del quantum asignado, se
pasa al final de la siguiente cola de menor prioridad, pero con mayor quantum. Un proceso en la
cola i que sí termina su fase de CPU dentro del quantum asignado, se pasa al final de la siguiente
cola de mayor prioridad, pero con menor quantum. Ejemplo:
En este modelo con retroalimentación, un proceso puede “moverse” entre colas, es decir, según
convenga puede llegar a asignarse a otra cola. Los procesos se separan de acuerdo a la ráfaga de
CPU que usan. Si esta usando mucha CPU se lo baja a una cola de menor prioridad. Se trata de
mantener los procesos interactivos y de mucha E/S en las colas de mayor prioridad.
Si además un proceso estuvo demasiado tiempo en una cola de baja prioridad puede moverse a
una cola de mayor prioridad para prevenir inanición (starvation).
se está perfectamente informado por anticipado sobre el trabajo que debe realizarse y los plazos
que deben cumplirse. Los algoritmos de planificación dinámica no tienen estas restricciones.
En Unix, por ejemplo se espera que se termine de ejecutar el system call para permitir apropiación.
puedan pasarse procesos de la cola de otro procesador a este, o hacer una cola común, y la
atención se realiza de acuerdo a la actividad de cada uno.
• Dejar que sólo uno de los procesadores planifique y decida qué procesos deben correr los
demás: multiprocesamiento asimétrico. Se asume una estructura de procesadores master-
slave que asigna a un procesador la toma de decisiones en cuanto a scheduling y otras
actividades, dedicándose los otros procesadores a ejecutar código de usuario. La ventaja es
que solo el procesador master accede a estructuras del kernel, evitando inconsistencias.
Windows utiliza una planificación basada en colas múltiples de prioridades. Posee 32 niveles de
colas, clasificadas en clase de Tiempo Real fija (16-31) y prioridad dinamica (0-15). Las colas se
recorren de mayor a menor ejecutando los hilos asociados. Cada cola es manejada por medio de
un algoritmo de Round Robin, aun así, si un hilo de mayor prioridad llega, el procesador le es
asignado a éste. La prioridades más altas son favorecidas. La prioridades de un thread no pueden
ser reducidas.
Los procesos en Linux pueden ser divididos en tres categorías, relacionadas con la prioridad:
interactivos, por lotes y de tiempo real. Los procesos en Tiempo Real son manejados bien por un
algoritmo FIFO o Round Robin. Los demás procesos son despachados utilizando planificación
Round Robin con un sistema de envejecimiento basado en créditos, donde el siguiente proceso a
ejecutar es aquel que más créditos posea. Los procesos en Tiempo Real son considerados
prioritarios sobre cualquier otro proceso en el sistema, por lo que serán ejecutados antes que los
demás. Algunos aspectos de la estructura interna del kernel que caben destacarse son:
• La PCB está representada por la estructura task_struct. Ésta indica el tipo de planificación
(FIFO,RR) por medio del campo policy, la prioridad (priority), el contador del programa
(counter), entre otros.
• La función goodness otorga una “calificación” al proceso pasado como parámetro. Dicha
puntuación oscila entre -1000 (no elegible) y +1000 (TR). Los procesos que comparten una
zona de memoria ganan una puntuación equivalente a su prioridad.
• El quantum varía según el proceso y su prioridad. La duración base es de aprox. 200ms.
• La función switch_to es la encargada de salvar la información de un proceso y cargar el
siguiente.
• Las funciones sched_{get/set}scheduler se refieren al mecanismo de planificación asociado a
ese proceso.
• Una nueva copia del proceso actual es creada mediante la llamada al sistema fork. Para
ejecutar un nuevo programa se utiliza la función execve.
• Las prioridades bajas son favorecidas. La mayoría de los procesos usan políticas de prioridad
dinámica. El valor “nice” establece la prioridad base de un proceso. Los valores de nice van
desde -20 a +20 (más grande = menor prioridad). Los usuarios no privilegiados sólo pueden
especificar valores de nice positivos. Los procesos normales se ejecutan sólo cuando no
quedan procesos de tiempo real (de prioridad fija) en la cola de listos.
Tema III
COMUNICACIÓN Y SINCRONIZACIÓN DE PROCESOS
Los procesos que se ejecutan de forma concurrente en un sistema se pueden clasificar como
procesos independientes o cooperantes. Un proceso independiente es aquel que ejecuta sin
requerir la ayuda o cooperación de otros procesos. Los procesos son cooperantes cuando están
diseñados para trabajar conjuntamente en alguna actividad, para lo que deben ser capaces de
comunicarse e interactuar entre ellos.
Tanto si los procesos son independientes como cooperantes, pueden producirse una serie de
interacciones entre ellos. Estas interacciones pueden ser de dos tipos:
• Interacciones motivadas porque los procesos comparten o compiten por el acceso a recursos
físicos o lógicos. Por ejemplo, dos procesos totalmente independientes pueden competir por el
acceso a disco, en este caso, el sistema operativo deberá encargarse de que los dos procesos
accedan ordenadamente sin que se cree ningún conflicto.
• Interacción motivada porque los procesos se comunican y sincronizan entre sí para alcanzar
un objetivo común. Por ejemplo, un compilador se puede construir mediante dos procesos: el
compilador propiamente dicho, que se encarga de generar código ensamblador, y el proceso
ensamblador, que obtiene código en lenguaje máquina a partir del ensamblador.
Estos dos tipos de interacciones obligan al sistema operativo a incluir mecanismos y servicios que
permitan la comunicación y la sincronización entre procesos (IPC InterProcess Communication).
Siendo numPrimos una variable global, podemos ejecutar primos(1,5000) en paralelo con
primos(5001,10000) para saber cuántos números primos hay entre 1 y 10000. ¿El problema?
numPrimos es una variable compartida que se accesa concurrentemente, y puede quedar mal
actualizada si se dan determinadas intercalaciones de las operaciones de las dos hebras.
Suponiendo que, más o menos simultáneamente, las dos hebras encuentran su primer número
primo. Podría darse el siguiente timing (inicialmente, numPrimos==0).
• Cada proceso debe solicitar permiso para entrar en la sección crítica mediante algún fragmento
de código, que se denomina de forma genérica entrada en la sección crítica.
• Cuando un proceso sale de la sección crítica debe indicarlo mediante otro fragmento de
código, que se denomina salida de la sección crítica. Este fragmento permitirá que otros
procesos entren a ejecutar el código de la sección crítica. La estructura general, por tanto, de
cualquier mecanismo que pretenda resolver el problema de la sección crítica es la siguiente:
Entrada en la sección crítica
Código de la sección crítica
Salida de la sección crítica
Cualquier solución que se utilice para resolver este problema debe cumplir los tres requisitos
siguientes:
• Exclusión mutua: si un proceso está ejecutando código de la sección crítica, ningún otro
proceso lo podrá hacer.
• Progreso (Ausencia de postergación innecesaria): si ningún proceso está ejecutando
dentro de la sección crítica, la decisión de qué proceso entra en la sección se hará sobre los
procesos que desean entrar. Los procesos que no quieren entrar no pueden formar parte de
esta decisión. Además, esta decisión debe realizarse en tiempo finito.
• Espera acotada (Entrada garantizada -ausencia de inanición): debe haber un límite en el
número de veces que se permite que los demás procesos entren a ejecutar código de la
sección crítica después de que un proceso haya efectuado una solicitud de entrada y antes de
que se conceda la suya.
A continuación se examinan varias propuestas de solución, de manera que mientras un proceso
esté ocupado actualizando la memoria compartida en su región crítica, ningún otro proceso pueda
entrar en su región crítica y provocar algún problema.
multiprocesadores.
Suponiendo que un proceso lee el turno y observa que vale 0. Antes de que pueda poner el turno a
1, se planifica otro proceso que pasa a ejecución y pone el turno a 1. Cuando el primer proceso se
ejecute de nuevo, pondrá a 1 también el turno, y se tendrá a dos procesos en sus regiones críticas
al mismo tiempo.
Tampoco funciona ya que si ambos procesos ponen interesado[i] en TRUE al mismo tiempo,
ambos quedan esperando para siempre. Se podría cambiar el orden, verificar primero y setear
después la variable interesado, pero entonces se podría terminar con los dos procesos en la
sección crítica.
Antes de utilizar las variables compartidas (es decir, antes de entrar en su región crítica), cada
proceso invoca entrar_en_region con su propio número de proceso, 0 o 1, como parámetro. Esta
llamada puede provocar su espera, si es necesario, hasta que sea seguro entrar. Cuando termine
de utilizar las variables compartidas, el proceso invoca abandonar_region para indicar que ha
terminado y para permitir a los demás procesos entrar, si así lo desean.
Inicialmente, la variable lock está en 0. Este protocolo provee exclusión mutua sin postergación
innecesaria, y sirve para n procesos, pero puede haber inanición.
3.2.6 Semáforos
Los inconvenientes de las soluciones anteriores, son que es difícil generalizarlas para problemas
de sincronización más complejos, o simplemente distintos, de la sección crítica y derrochan CPU,
ya que usan espera ocupada (busy waiting); cuando un proceso quiere entrar a la sección crítica,
está permanentemente chequeando si puede hacerlo.
8 9
puede manipularse mediante dos operaciones: P (o wait o down) y V (o signal o up), y cuyo
efecto es equivalente a:
La operación wait sobre un semáforo comprueba si el valor es mayor que 0. Si lo es, simplemente
decrementa el valor (es decir utiliza una de las señales guardadas). Si el valor es 0, el proceso
procede a dormirse sin completar la operación wait por el momento. La comprobación del valor del
semáforo, su modificación y la posible acción de dormirse, se realizan como una única acción
atómica indivisible. Está garantizado que una vez que comienza una operación sobre un semáforo,
ningún otro proceso puede acceder al semáforo hasta que la operación se completa o hasta que el
proceso se bloquea. Esta atomicidad es absolutamente esencial para resolver los problemas de
sincronización y evitar que se produzcan condiciones de competencia.
La operación signal incrementa el valor del semáforo al cual se aplica. Si uno o más procesos
estuviesen dormidos sobre ese semáforo, incapaces de completar una anterior operación de wait,
el sistema elige a uno de ellos (por ejemplo de forma aleatoria) y se le permite completar esa
operación wait pendiente. Entonces, después de ejecutarse un signal sobre un semáforo con
procesos dormidos en él, el semáforo sigue valiendo 0, pero habrá un proceso menos, dormido en
él. La operación de incrementar el semáforo y despertar un proceso es también indivisible. La
operación de signal nunca bloquea al proceso que la ejecuta.
El problema de la sección crítica se puede resolver fácilmente con un semáforo S, con valor inicial
1.
A nivel de sincronización, si se quiere que un proceso P2 ejecute un trozo de código C2 pero sólo
después que P1 haya completado otro trozo C1, se usa un semáforo para sincronizar con valor
inicial 0.
3.2.7. Monitores
Los semáforos son una herramienta general y eficiente para sincronizar procesos, pero siguen
siendo de bajo nivel. Las soluciones mediante semáforos no son ni muy limpias ni muy claras, y
siempre están sujetas a errores como la omisión o mala ubicación de una operación wait o signal.
Los monitores son una herramienta de sincronización más estructurada que encapsula variables
compartidas en conjunto con los procedimientos para accesar esas variables.
8
Prolaag que es una combinación de probeer te verlagen en holandés que significa intentar decrementar
9
Verhogen en holandés que significa incrementar
Los monitores tienen una importante propiedad que los hace útiles para conseguir exclusión
mutua: en cualquier instante solamente un proceso puede estar activo dentro del monitor. Los
monitores son construcciones del lenguaje, por lo que el compilador sabe que son especiales, de
manera que puede tratar las llamadas a los procedimientos del monitor de forma diferente que a
otras llamadas a procedimientos normales. En la mayoría de los casos, cuando un proceso llama a
un procedimiento de un monitor, las primeras instrucciones del procedimiento comprueban si
cualquier otro proceso está actualmente activo dentro del monitor. En ese caso, el proceso que
hizo la llamada debe suspenderse hasta que el otro proceso abandone el monitor. Si ningún otro
proceso está utilizando el monitor, el proceso que hizo la llamada puede entrar inmediatamente.
Corresponde al compilador implementar la exclusión mutua sobre las entradas al monitor. La forma
más común de implementarla es utilizando una variable de exclusión mutua o un semáforo binario.
Debido a que es el compilador y no el programador el que organiza las cosas para conseguir la
exclusión mutua, resulta mucho más difícil que se produzcan errores. En cualquier caso, la
persona que escribe el monitor no tiene que preocuparse de cómo consigue asegurar la exclusión
mutua el compilador dentro del monitor. Es suficiente con que sepa que metiendo todas las
regiones críticas en procedimientos del monitor, nunca habrá dos procesos que ejecuten sus
regiones críticas a la vez.
Para esperar eventos (sincronización por condición) se usan variables de condición. Una variable
de condición c tiene asociada una cola de procesos, y soporta dos operaciones:
• waitC(c): suspende al proceso invocador, lo pone al final de la cola asociada a c, y libera el
monitor. O sea, aunque no se haya completado un procedimiento, el proceso deja de estar
activo dentro del monitor, y por lo tanto otro proceso puede ejecutar dentro del monitor.
• signalC(c): despierta al proceso al frente de la cola asociada a c, si es que existe. En
monitores con semántica signal-and-continue, el proceso que hace signal continúa dentro del
monitor; el proceso despertado, si existe, debe esperar su oportunidad para volver a entrar al
monitor y continuar después del wait. En monitores con semántica signal-and-wait, si es que
el signal despierta a un proceso, entonces el proceso señalizador suspende su ejecución en
favor del proceso señalizado; el señalizador debe esperar (posiblemente compitiendo con otros
procesos) para poder volver al monitor.
Las variables de condición no son contadores, ya que no acumulan las señales para un uso
posterior como hacen los semáforos. Entonces si una variable de condición recibe una señal sin
que haya ningún proceso esperándola, la señal se pierde para siempre. En otras palabras el waitC
debe ocurrir antes que el signalC. Esta regla simplifica mucho la implementación, y en la práctica
no representa ningún problema ya que, si es necesario, es fácil seguir la pista del estado de cada
proceso utilizando variables adicionales. Antes de llevar a cabo un signalC, el proceso puede ver si
esa operación es necesaria, o no, inspeccionando esas variables.
Algunos lenguajes de programación reales soportan los monitores, aunque no siempre en la forma
diseñada, por ejemplo Java. Java es un lenguaje orientado a objetos que soporta threads a nivel
de usuario y que permite agrupar juntos varios métodos (procedimientos) formando clases.
Añadiendo la palabra reservada synchronized a la declaración de un método, Java garantiza que
una vez que un thread comienza a ejecutar ese método, no se le permite a ningún otro thread
comenzar a ejecutar cualquier otro método synchronized de esa clase.
Los métodos sincronizados de Java difieren de los monitores clásicos en un aspecto esencial: Java
no dispone de variables de condición. En su lugar, ofrece dos procedimientos wait y notify que son
los equivalentes de waitC(c) y signalC(c) salvo que cuando se utilizan dentro de métodos
sincronizados no están expuestos a que se produzcan condiciones de competencia.
Este método de comunicación entre procesos utiliza dos primitivas, enviar y recibir, que igual que
los semáforos y de forma diferente a los monitores son llamadas al sistema en vez de
construcciones del lenguaje de programación. Como tales, pueden incluirse fácilmente en librerías
de procedimientos, tales como
enviar(destinatario, &mensaje);
recibir(remitente, &mensaje);
int reciente = 0;
int colaProduccion[tamBuffer];
semaphore semProductor = 1; // Si el buffer esta lleno, lo duerme
semaphore semConsumidor = 0; // Si el buffer esta vacio, lo duerme
semaphore semBuffer = 1; // controla la estricta alternancia, Si esta en 1 el consumidor consume
// Si esta en 0, el productor produce y el consumidor deja de consumir
void main() {
cobegin {
productor(1);
productor(2);
consumidor(1);
consumidor(2);
}
}
y su ejecución sería:
3.3.2. Lector-Escritor
Un objeto, tal como un archivo o un registro de una base de datos, es compartido por varios
procesos concurrentes. Hay procesos escritores, que modifican el objeto, y procesos lectores, que
sólo lo consultan. Puede haber múltiples procesos leyendo el objeto simultáneamente, pero cuando
hay un proceso escribiendo, no puede haber ningún lector ni ningún otro escritor. La solución se
puede alcanzar por medio de la comunicación entre procesos, usando monitores:
monitor LectorEscritor {
int contadorLector; // lectores concurrentes
int ocupado;
condition OKleer, OKescribir;
void EmpiezaLeer() {
if (ocupado || !empty(OKescribir))
waitc(OKleer);
contadorLector = contadorLector + 1;
cout << "Numero lectores concurrentes " << contadorLector << '\n';
signalc(OKleer);
}
void FinLeer() {
contadorLector = contadorLector - 1;
if (contadorLector == 0)
signalc(OKescribir);
}
void EmpiezaEscribir() {
if (ocupado || (contadorLector != 0))
waitc(OKescribir);
ocupado = 1;
}
void FinEscribir() {
ocupado = 0;
if (empty(OKleer))
signalc(OKescribir);
else
signalc(OKleer);
}
init {
contadorLector = 0; ocupado = 0; //inicializacion
}
} // fin monitor
void Lector(int N) {
int I;
for (I = 1; I < 2; I++) {
EmpiezaLeer();
cout << N << " esta leyendo" << '\n';
FinLeer();
}
}
void Escritor(int N) {
int I;
for (I = 1; I < 2; I++) {
EmpiezaEscribir();
cout << N << " esta escribiendo" << '\n';
FinEscribir();
}
}
void main() {
cobegin {
Lector(1); Lector(2); Lector(3);
Escritor(1); Escritor(2);
}
}
y su ejecución sería:
#include "gdefs.cm"
const
int PEN = 0; int HAM = 1; int COM = 2;
int Mesa = 100;
int pos[5][4];
int inc = 0;
int i;
monitor FilosofoComensal {
int estFil[5];//estado de todos los filósofos
condition libre[5];//condicion del cubierto de cada filósofo
void main(){
create(Mesa, CIRCLE, BLACK, 250, 200, 50, 50);
cobegin{
filosofo(0);
filosofo(1);
filosofo(2);
filosofo(3);
filosofo(4);
}
}
y su ejecución sería:
semaphore peluqueros=1;
int cantClientes=0;
int clientesAtendidos=0;
int cantSillas=2; //puede ser la cantidad de sillas que se desea en la barberia
int cantSillasOcupadas=0;
int tiempoDeLlegada=0;
int tiempoDeAtencion=0;
void peluquero(){
int p;
if(tiempoDeAtencion==0){
if(cantSillasOcupadas>0){
wait(peluqueros);
clientesAtendidos=clientesAtendidos+1;
cantSillasOcupadas=cantSillasOcupadas-1;
tiempoDeAtencion=random(50);
if(cantClientes==1){
cout<<"+-------------------------------------------------------------------+"<<endl;
cout<<" el "<<clientesAtendidos<<" º cliente"<<" esta despertando al peluquero"<<endl;
cout<<" el "<<clientesAtendidos<<" º cliente"<<" pasa a ser atendido"<<endl;
cout<<" se esta atendiendo al " <<clientesAtendidos<<" º cliente"<<"\n"<<endl;
}else{
cout<<"+-------------------------------------------------------------------+"<<endl;
cout<<" el "<<clientesAtendidos<<" º cliente"<<"pasa a ser atendido"<<endl;
cout<<" se esta atendiendo al " <<clientesAtendidos<<" º cliente"<<"\n"<<endl;
recorre(clientesAtendidos);
}
signal(peluqueros);
}else{
cout<<"-----------------<PELUQUERO DURMIENDO>-------------------"<<"\n"<<endl;
}
}else{
for(p=0;p<tiempoDeAtencion;p++){
tiempoDeAtencion=tiempoDeAtencion-1;
if(tiempoDeAtencion==0){
cout<<"******************************************************"<<endl;
cout<<" se termino de atender al "<<clientesAtendidos<<"º cliente"<<endl;
peluquero();
}
}
}
}
void main(){
cobegin{
while(1){
peluquero();
llega(1);
}
}
}
y su ejecución sería:
Tema IV
BLOQUEOS IRREVERSIBLES
(Bloqueos mutuos, Deadlocks, Interbloqueos o Abrazo mortal)
La administración de los recursos es una de las principales tareas del sistema operativo, ya que
tienen que ofrecer mecanismos que permitan a los procesos acceder de forma exclusiva a los
recursos. Cuando un proceso solicita ciertos recursos y éstos no están disponibles en ese
momento, entra en un estado de espera. Si se tienen muchos procesos que compiten por recursos
finitos, puede darse una situación en la que un proceso está bloqueado esperando por un recurso
que nunca se liberará, porque lo posee otro proceso también bloqueado.
Un sistema se compone de un número finito de recursos que son distribuidos entre un número de
procesos que compiten por ellos. Los recursos pueden ser:
Los recursos son clasificados en diferentes tipos, cada uno de los cuales se compone de algún
número de instancias iguales. Si un sistema tiene dos CPU’s, entonces el tipo CPU tiene dos
instancias. Similarmente, el tipo impresoras puede tener cinco instancias. Si un proceso pide una
instancia de un tipo de recurso, la asignación de cualquier instancia de ese tipo atenderá la
petición. Si este no es el caso, entonces las instancias no son idénticas y las clases de tipos de
recursos no están bien definidas. Un proceso debe solicitar un recurso antes de usarlo y liberarlo
después de usarlo. Un proceso puede solicitar tantos recursos como sean necesarios para llevar a
cabo la tarea para la cual ha sido diseñado. Obviamente el número de recursos solicitados no debe
exceder el número de recursos disponibles en el sistema. En otras palabras, un proceso no debe
pedir tres impresoras si en el sistema solo existen dos.
Una computadora normalmente tendrá varios recursos que pueden ser otorgados. Algunos podrán
tener varias referencias idénticas, como en el caso de las unidades de cinta. Si se tienen varias
copias disponibles de un recurso, cualquiera de ellas se puede utilizar para satisfacer cualquier
solicitud de recurso. Los recursos son de dos tipos:
• Apropiativos
• No apropiativos
Recursos apropiativos. Los recursos apropiativos son aquellos que se pueden tomar del proceso
que le posee sin efectos dañinos. La memoria es un ejemplo de recurso apropiativo. Por ejemplo
considerar un sistema con 512 Kb de memoria de usuario, una impresora, y dos procesos de 512
Kb que se desean imprimir cada uno.
• El proceso A solicita y obtiene la impresora, para entonces comienza a calcular los valores que
va a imprimir. Antes de terminar el cálculo excede su quantum de tiempo y se intercambia.
• El proceso B se empieza a ejecutar e intenta sin éxito adquirir la impresora.
• Potencialmente se tendría una situación de bloqueo, puesto que A tiene la impresora y B la
memoria y ninguno puede continuar sin el recurso que posee el otro.
• Por fortuna es posible apropiarse de la memoria de B y sacarlo de ella e intercambiarlo con A.
• A puede ejecutarse entonces, imprimir y liberar después la impresora. No ocurre un bloqueo.
Recursos no apropiativos . Los recursos no apropiativos son aquellos que no se pueden tomar
de su poseedor activo sin provocar un fallo de cálculo. Por ejemplo, si un proceso comienza a
imprimir una salida, se toma la impresora y se le da otro proceso, el resultado será una salida
incomprensible. Las impresoras no son apropiables. En general los bloqueos se relacionan con los
recursos no apropiables.
• Petición. Si la petición no puede ser satisfecha inmediatamente (por ejemplo, el recurso esta
siendo utilizado por otro proceso), entonces el proceso solicitante debe esperar hasta que
pueda adquirir el recurso.
• Uso. El proceso puede utilizar un recurso (por ejemplo, si el recurso es una impresora, el
proceso puede imprimir).
• Liberación. El proceso libera el recurso. Si el recurso no esta disponible cuando es requerido,
el proceso solicitante se ve forzado a esperar. En algunos sistemas operativos, el proceso se
bloquea automáticamente cuando falla la solicitud el recurso y se desbloquea cuando esta
disponible. En otros sistemas, la solicitud falla en un código de error y corresponde al recurso
solicitante esperar un poco y volverlo a intentar.
La petición y liberación del recurso son peticiones al sistema. El uso de recursos puede también
hacerse sólo a través de llamadas al sistema. Por lo tanto, para cada uso, el sistema operativo
chequea para asegurarse de que el proceso usuario ha pedido y se le han asignado los recursos.
Una tabla del sistema registra cuando un recurso está libre o asignado, y si está asignado, a qué
proceso. Si un proceso pide un recurso que está asignado en ese momento a otro proceso, éste
puede ser agregado a una cola de procesos en espera de ese recurso.
4.1. Bloqueos
Un conjunto de procesos se encuentra en estado de interbloqueo cuando cada uno de ellos espera
un suceso que sólo puede originar otro proceso del mismo conjunto. Por ejemplo, si dos procesos
desean imprimir cada uno un enorme archivo leído de cinta.
• El proceso A solicita permiso para utilizar la impresora (recurso 1), el cual se le concede.
• El proceso B solicita permiso para utilizar la unidad de cinta (recurso 2) y se le otorga.
• El proceso A solicita entonces la unidad de cinta (recurso 2), pero la solicitud es denegada
hasta que B la libere. En este momento, en vez de liberar la unidad de cinta, el proceso B
solicita la impresora (recurso 1).
Los procesos se bloquean en ese momento y permanecen así por siempre. A esta situación se le
llama BLOQUEO.
Se presenta una contradicción entre la conveniencia y lo que es correcto. Es muy difícil encontrar
teóricamente soluciones prácticas de orden general aplicables a todos los tipos de S.O. Un criterio
10
Coffman, Edward G., Jr.; Elphick, Michael J.; Shoshani, Arie. System Deadlocks
de orden general utilizado por los S.O. que no hacen tratamiento específico del bloqueo consiste
en:
• Intentar acceder al recurso compartido.
• De no ser factible el acceso:
o Esperar un tiempo aleatorio.
o Reintentar nuevamente.
Principalmente, existen cuatro métodos para manejar el interbloqueo. Podemos usar algún
protocolo para asegurar que el sistema nunca entrará en un estado de abrazo mortal.
Alternativamente, podemos permitir que el sistema entre en un estado de abrazo mortal (bloqueo)
y después recuperarse. Pero el recuperarse puede ser muy difícil y muy caro.
Retener y esperar. Con el fin de asegurar que la condición de retener y esperar nunca ocurra en
el sistema, se debe garantizar que siempre que un proceso solicite un recurso, éste no pueda
retener otros recursos.
Un protocolo que puede ser usado requiere que cada proceso solicite y le sean asignados todos
los recursos antes de que empiece su ejecución. Esto puede ser implantado haciendo que las
llamadas al sistema solicitando recursos se hagan antes que todas las otras llamadas al sistema.
Un protocolo alternativo permite que un proceso solicite recursos cuando no tiene ningún recurso
asignado. Un proceso puede solicitar algunos recursos y utilizarlos, pero, antes de que pueda
volver a pedir recursos adicionales, debe liberar todos los recursos que tiene previamente
asignados.
Para ejemplificar la diferencia entre estos dos protocolos, consideremos un proceso que copia un
archivo de una unidad de cinta(1) a una unidad de disco, ordena el archivo en disco, después
imprime los resultados a una impresora en línea y finalmente copia el archivo de disco a la unidad
de cinta(2).
Si todos los recursos deben ser solicitados al inicio del proceso, entonces el proceso debe iniciar
solicitando la unidad de cinta(1), la unidad de disco, la impresora y la unidad de cinta(2). Este
proceso mantendrá las unidades de cinta (1) y (2) durante la ejecución completa aunque sólo las
utilice al principio y al final de su ejecución respectivamente.
El segundo método permite al proceso el solicitar inicialmente solo la unidad de cinta(1) y la unidad
de disco. Ahora puede copiar el archivo de la unidad de cinta (1) a la unidad de disco y ordenarlo,
posteriormente debe liberar la unidad de cinta(1) y la unidad de disco. El proceso debe volver a
solicitar la unidad de disco y la impresora para hacer la impresión. Después de imprimir debe
liberar la unidad de disco y la impresora. Ahora debe de volver a solicitar la unidad de disco y la
unidad de cinta(2) para copiar el archivo a cinta, debe liberar ambos recursos y terminar.
Existen dos desventajas principales en estos protocolos:
• La primera, la utilización de los recursos puede ser muy baja, debido a que varios de los
recursos pueden estar asignados pero no son utilizados la mayor parte del tiempo.
• Segundo, puede ocurrir Inanición (Starvation). Un proceso que necesite varios recursos que
sean muy solicitados puede tener que esperar indefinidamente mientras al menos uno de los
recursos que necesita esté asignado siempre a algún otro proceso. En esta segunda
condición, retener y esperar, si se puede impedir que los procesos que tienen los recursos
esperen la llegada de más recursos podemos erradicar los estancamientos. La solución que
exige que todos los procesos soliciten todos los recursos que necesiten a un mismo tiempo y
bloqueando el proceso hasta que todos los recursos puedan concederse simultáneamente
resulta ineficiente por dos factores:
o En primer lugar, un proceso puede estar suspendido durante mucho tiempo,
esperando que concedan todas sus solicitudes de recursos, cuando de hecho podría
haber avanzado con sólo algunos de los recursos.
o Y en segundo lugar, los recursos asignados a un proceso pueden permanecer sin
usarse durante periodos considerables, tiempo durante el cual se priva del acceso a
otros procesos.
sobre recursos cuyo estado puede ser fácilmente salvado y restablecido posteriormente, ejemplo
de ellos son los registros del CPU y el espacio en la memoria. Este no puede ser aplicado a
recursos tales como impresoras. Si a un proceso se le ha asignado la impresora y se encuentra a
la mitad de la impresión, y tomamos a la fuerza la impresora, se engendraría una confusión.
Espera circular. Con el fin de asegurarse de que la condición de espera circular nunca se
presente, se puede imponer un ordenamiento total sobre todos los tipos de recursos. Esto es,
asignamos a cada tipo de recurso un número entero único, el cual permita comparar dos recursos
y determinar cuándo uno precede al otro en el ordenamiento.
Más formalmente, sea R = {r1, r2,..., rn} el conjunto de tipos de recursos. Puede definirse una
función uno a uno F:R->N, donde N es el conjunto de números naturales. Por ejemplo, si el
conjunto R de tipos de recursos incluye unidades de disco (UDD), unidades de cinta (UDC),
lectoras ópticos (LO) e impresoras (I), entonces la función F puede ser definida como sigue:
F(LO) =1 F(UDD) = 5 F(UDC) = 7 F(I) = 12
Se puede considerar el siguiente protocolo para prevenir interbloqueo:
Cada proceso puede solicitar recursos solamente en un orden creciente de numeración. Esto es un
proceso puede solicitar inicialmente cualquier número de instancias de un tipo de recurso, digamos
ri. Después de esto, el proceso puede solicitar instancias de recursos del tipo rj si y solo si F(rj) >
F(ri). Si varias instancias del mismo tipo de recurso son necesitadas, debe hacerse una sola
petición para todas las instancias. Por ejemplo, usando la función definida anteriormente, un
proceso que quiere usar el lector óptico (LO) y la impresora (I) debe solicitar primero el (LO) y
después la (I).
Alternativamente, se puede requerir simplemente que siempre que un proceso solicite una
instancia del recurso tipo rj, éste tenga que liberar cualquier recurso del tipo ri tal que F(ri) >= F(rj).
Debe notarse que la función F debe definirse de acuerdo al ordenamiento de uso normal de los
recursos en el sistema. Por ejemplo, usualmente se utiliza primero una (UDD) antes que la (I), por
lo cual es razonable definir F(UDD) < F(i).
Esta última condición (espera circular) se puede eliminar en varias formas. Una manera consiste en
simplemente tener una regla que afirme que un proceso sólo tiene derechos a un recurso único en
cualquier momento. Si necesita un segundo recurso debe devolver el primero.
Otra manera de evitar la espera circular es la de ofrecer una numeración global de todos los
recursos. Ahora la regla es que los procesos pueden solicitar recursos siempre y cuando devuelva
el recurso que tenga y el que solicite sea mayor que el que está utilizando.
realice una solicitud de recursos, el sistema se los concederá sólo en el caso de que la
solicitud mantenga al sistema en un estado seguro.
• Un estado inseguro es aquel en el que puede presentarse un interbloqueo.
11
Algoritmo del banquero para un sólo recurso Este algoritmo fue ideado por Dijkstra . Se creó
en la forma en que un banquero trata a un grupo de clientes, a quienes les otorga líneas de crédito.
El banquero sabe que no todos los clientes (4) A, B, C y D necesitarán su limite de crédito máximo
de inmediato, de manera que sólo ha reservado 10 unidades en lugar de 22 (total máximo
disponible) para darles servicios (con este ejemplo asumiremos que los clientes son los procesos,
las unidades de crédito son los recursos y el banquero es el sistema operativo). Los clientes
emprenden sus respectivos negocios y solicitan préstamos de vez en cuando, es decir solicitan
recursos. En cierto momento, la situación es como se muestra en el siguiente cuadro:
Este estado es seguro, puesto que con dos unidades restantes, el banquero puede retrasar todas
las solicitudes excepto la de C lo cual permite que C termine y libere sus cuatro recursos. Con
cuatro unidades disponibles, el banquero puede permitir que B ó D tengan las unidades
necesarias. Considerar lo que ocurriría si se otorgara una solicitud de B de una unidad adicional,
analizando esto en el esquema anterior se tendría este nuevo esquema:
Se tendría un estado inseguro, ya que si todos los clientes solicitaran de pronto su máximo
préstamo, el banquero no podría satisfacerlas y se tendría un bloqueo.
Un estado inseguro no tiene que llevar a un bloqueo, puesto que un cliente podría no necesitar
toda su línea de crédito, pero el banquero no puede contar con ese comportamiento.
El algoritmo del banquero consiste entonces en estudiar cada solicitud al ocurrir ésta y ver si su
otorgamiento conduce a un estado seguro. En caso afirmativo, se otorga la solicitud; en caso
contrario, se le pospone. Para ver si un estado es seguro, el banquero verifica si tiene los recursos
suficientes para satisfacer a otro cliente. En caso afirmativo, se supone que estos préstamos se le
volverán a pagar; entonces verifica al siguiente cliente cercano al límite y así sucesivamente. Si en
cierto momento se vuelve a pagar todos los préstamos, el estado es seguro y la solicitud original
debe ser aprobada.
Algoritmo del banquero para varios recursos. El algoritmo del banquero se puede generalizar
para el control de varios recursos. Por ejemplo, dado un sistema con cinco procesos, P1 a P5, y
tres tipos de recursos, A, B y C, de los que existen 10, 5 y 7 instancias, respectivamente.
Supongamos que en el instante actual se tiene la siguiente situación del sistema:
11
Dijkstra, Edsger W. The mathematics behind the Banker's Algorithm
Disponible = (3 3 2)
Se puede atender a P2 o P4, se elige P2 = - (1 2 2)
Nuevo disponible después de la asignación = (2 1 0)
Se recupera todos los recursos asignados a P2 = + (3 2 2)
Nuevo disponible después de recuperar recursos = (5 3 2)
Se puede atender a P3 = - (6 0 0)
Nuevo disponible después de la asignación = (1 4 5)
Se recupera todos los recursos asignados a P2 = + (9 0 2)
Nuevo disponible después de recuperar recursos = (10 4 7)
Se puede atender a P1 = - (7 4 3)
Nuevo disponible después de la asignación = (3 0 4)
Se recupera todos los recursos asignados a P2 = + (7 5 3)
Nuevo disponible después de recuperar recursos = (10 5 7)
El orden de atención de los procesos es P2, P4, P5, P3 y P1; secuencia que permite un estado
seguro de asignación de recursos.
• El algoritmo requiere que los procesos garanticen que los préstamos van a ser pagados (o sea
que los recursos van a ser devueltos) dentro de un intervalo de tiempo finito. También en este
caso se necesitan garantías mucho mayores que ésta para sistemas reales.
• El algoritmo requiere que los usuarios indiquen sus necesidades máximas por adelantado. Al
irse haciendo más dinámica la asignación de recursos resulta cada vez más difícil conocer las
necesidades máximas de un usuario.
Una vez liberado el sistema, se deja que los trabajos restantes terminen su procesamiento;
luego, los trabajos detenidos se inician de nuevo desde el principio.
• El cuarto procedimiento se puede poner en efecto sólo si el trabajo mantiene un registro, una
instantánea de su progreso, de manera que se pueda interrumpir y después continuar sin tener
que reiniciar desde el principio. En general, este método es el preferido para trabajos de
ejecución larga, a fin de ayudarlos a tener una recuperación rápida.
Hasta ahora los cuatro procedimientos anteriores comprenden los trabajos que se encuentran en
interbloqueo. Los dos métodos siguientes se concentran en trabajos que no están en interbloqueo
y los recursos que conservan.
• Uno de ellos, el quinto método de la lista, selecciona un trabajo no bloqueado, retira los
recursos que contiene y los asigna a procesos bloqueados, de manera que pueda reanudarse
la ejecución (esto deshace el interbloqueo).
• El sexto método detiene los trabajos nuevos e impide que entren al sistema, lo que permite que
los que no estén bloqueados sigan hasta su terminación y liberen sus recursos. Con menos
trabajos en el sistema, la competencia por los recursos se reduce, de suerte que los procesos
bloqueados obtienen los recursos que necesitan para ejecutarse hasta su terminación. Este
método es el único aquí listado que no necesita una víctima. No se garantiza que funcione, a
menos que el número de recursos disponibles exceda los necesarios en por lo menos uno de
los trabajos bloqueados para ejecutar (esto es posible con recursos múltiples).
Deben considerarse varios factores al elegir la víctima para que tengan el efecto menos negativo
sobre el sistema. Los más comunes son:
• La prioridad del trabajo en consideración. Por lo general no se tocan los trabajos de alta
prioridad.
• El tiempo de CPU utilizado por el trabajo. No suelen tocarse los trabajos que están a punto
de terminar.
• La cantidad de tareas en que repercutiría la elección de la víctima.
Además, los programas que trabajan con bases de datos también merecen un trato especial. Los
trabajos que están modificando datos no se deben elegir para su terminación, ya que la
consistencia y validez de la base de datos se pondría en peligro. Afortunadamente, los diseñadores
de muchos sistemas de bases de datos han incluido mecanismos complejos de recuperación, por
lo que se minimiza el daño a la base de datos si se interrumpe una transacción o se termina antes
de completarse.
Tema V
ADMINISTRACIÓN DE MEMORIA
La memoria es un recurso escaso, y para aprovecharla bien hay que administrarla bien. A pesar de
que la memoria es más barata cada día, los requerimientos de almacenamiento crecen en
proporción similar.
La organización y administración de la memoria principal, memoria primaria, memoria real o
almacenamiento de un sistema ha sido y es uno de los factores más importantes en el diseño de
los Sistemas Operativos y sus funciones son:
• Llevar un control de las partes de memoria que se están utilizando y de aquellas que no.
• Asignar espacio en memoria a los procesos cuando estos la necesitan y liberarla cuando
estos finalicen.
• Administrar el intercambio entre memoria principal y secundaria (swapping).
• Caché de nivel 1: 8 a 288 kb. empaquetados dentro del chip; por lo mismo, la velocidad de
acceso es de unos pocos nanosegundos.
o L1 DC: (Level 1 date cache) se encarga de almacenar datos usados
frecuentemente y cuando sea necesario volver a utilizarlos, inmediatamente los
utiliza, por lo que se agilizan los procesos.
o L1 IC: (Level 1 instruction cache): se encarga de almacenar instrucciones usadas
frecuentemente y cuando sea necesario volver a utilizarlas, inmediatamente las
recupera, por lo que se agilizan los procesos.
• Caché de nivel 2: 256 Kb a 8 Mb, la velocidad de acceso es de 12-20 ns (L2 viene
integrada en el microprocesador, se encarga de almacenar datos de uso frecuente y
agilizar los procesos)
• Caché de nivel 3: hasta 14 Mb, la velocidad de acceso es de 15-35 ns Con este nivel de
memoria se agiliza el acceso a datos e instrucciones que no fueron localizadas en L1 ó L2.
Si no se encuentra el dato en ninguna de las 3, entonces se accederá a buscarlo en la
memoria RAM.
• Memoria RAM: hasta 32 Gb, la velocidad de acceso es de 60-70ns
• Disco duro. Para almacenamiento estable, y también para extender la RAM de manera
virtual, hasta 2 Tb en discos internos, la velocidad de acceso es de 8ms.
• Cinta magnética. Hasta 2,5 Tb.
La cache L2 utiliza gran parte del espacio del chip, ya que se necesitan millones de transistores
para formar una memoria caché grande; ésta se crea utilizando SRAM (RAM estática)
en oposición a la RAM normal, que es dinámica (DRAM). Mientras que la DRAM puede crearse
utilizado un transistor por bit (además de un condensador), son necesarios 6 transistores (o más)
para crear un bit de SRAM. Por lo tanto, 256 KB de memoria caché L2 necesitarían más de 12
millones de transistores.
Tanto Intel como AMD no han incluido memoria caché L2 en algunas series para hacer productos
más baratos. Sin embargo, no hay duda de que cuanto mayor es la memoria caché (tanto L1 como
L2), más eficiente será la CPU y mayor será su rendimiento.
En la figura se muestran tres variaciones sobre este tema. El sistema operativo puede estar en la
base de la memoria en RAM (memoria de acceso aleatorio), como se muestra en (a), o puede
estar en ROM (memoria sólo de lectura) en la parte superior de la memoria, como en (b), o los
controladores de dispositivos pueden estar en la parte superior de la memoria en una ROM con el
resto del sistema en RAM hasta abajo, como se muestra en (c). Este último modelo es utilizado por
los sistemas MS-DOS pequeños, por ejemplo. En las IBM PC, la porción del sistema que está en
ROM se llama BIOS (Basic Input Output System, sistema básico de entrada salida).
Una organización alternativa sería mantener una sola cola. Cada vez que se libera una partición,
se selecciona el trabajo más cercano al inicio de la cola que cabe en esa partición, se carga en
dicha partición y ejecuta. Puesto que no es deseable desperdiciar una partición grande en un
trabajo pequeño, una estrategia diferente consiste en examinar toda la cola de entrada cada vez
que se libera una partición y escoger el trabajo más grande que cabe en ella. Este último algoritmo
discrimina contra los trabajos pequeños, considerándolos indignos de recibir toda la partición, en
tanto que usualmente es deseable dar el mejor servicio, y no el peor, a los trabajos más pequeños
(que supuestamente son interactivos).
Una posible solución es modificar realmente las instrucciones en el momento en que el programa
se carga en la memoria. Se suma 100K a cada una de las direcciones de un programa que se
carga en la partición 1, se suma 200K a las direcciones de los programas cargados en la partición
2, etc. A fin de efectuar la reubicación durante la carga, de esta manera el enlazador debe incluir
en el programa binario una lista o mapa de bits que indique cuáles bytes del programa son
direcciones que deben reubicarse y cuáles con códigos de operación, constantes u otros
elementos que no deben reubicarse. La reubicación durante la carga no resuelve el problema de la
protección. Un programa mal intencionado siempre puede construir una nueva instrucción y saltar
a ella. Dado que los programas en este sistema usan direcciones de memoria absolutas en lugar
de direcciones relativas a un registro, no hay forma de impedir que un programa construya una
instrucción que lea o escriba cualquier byte de la memoria. En los sistemas multiusuario, no es
conveniente permitir que los procesos lean y escriban en memoria que pertenece a otros usuarios.
5.2.2.2. Fragmentación
La mayor dificultad con las particiones fijas esta en encontrar una buena relación entre los tamaños
de las particiones y la memoria requerida para los trabajos. La fragmentación de almacenamiento
ocurre en todos los sistemas independientemente de su organización de memoria. Existen dos
tipos de desaprovechamiento de memoria:
a) La fragmentación interna, que consiste en aquella parte de la memoria que no se está usando
pero que es interna a una partición asignada a una tarea; por ejemplo si una tarea necesita m
bytes de memoria para ejecutarse y se le asigna una partición de n bytes (con n>m), está
desaprovechando n-m bytes.
b) La fragmentación externa, que ocurre cuando una partición disponible no se emplea porque es
muy pequeña para cualquiera de las tareas que esperan.
La selección de los tamaños de las particiones es una relación entre estos dos casos de
fragmentación. Por ejemplo, 7 Mb asignados a los usuarios se reparten en 7 particiones de 1 Mb, y
la cola de tareas contiene tareas con requerimientos de 400 Kb, 1600 Kb, 300 Kb, 900 Kb, 200 Kb,
500 Kb y 800 Kb. Se ve que hay un trabajo de 1600 Kb que no se podrá ejecutar nunca, los otros
sin embargo si se ejecutaran pero en conjunto desperdiciaran 3044 Kb, casi la mitad de memoria
disponible. Hay, pues en este caso 1024 Kb de fragmentación externa y 3044 Kb de fragmentación
interna. Si se divide la memoria en cuatro particiones de 512 Kb, dos de 1 Mb y una de 3 Mb, todos
los trabajos se ejecutarían sin fragmentación externa y con una pérdida de memoria en
fragmentación interna de 2648 Kb.
No hay límites fijos de memoria, es decir que la partición de un trabajo es su propio tamaño. Se
consideran “esquemas de asignación contigua”, dado que un programa debe ocupar posiciones
adyacentes de almacenamiento. Los procesos que terminan dejan disponibles espacios de
memoria principal llamados “agujeros” o áreas libres:
• Pueden ser usados por otros trabajos que cuando finalizan dejan otros agujeros menores.
• En sucesivos pasos los agujeros son cada vez más numerosos pero más pequeños, por lo
que se genera un desperdicio de memoria principal.
La combinación de agujeros (áreas libres), consiste en fusionar agujeros adyacentes para formar
uno sencillo más grande. Se puede hacer cuando un trabajo termina y el almacenamiento que
libera tiene límites con otros agujeros.
• Podría ser suficiente (el total global disponible) para alojar a procesos encolados en espera
de memoria.
• Podría no ser suficiente ningún área libre individual.
La técnica de compresión de memoria implica pasar todas las áreas ocupadas del almacenamiento
a uno de los extremos de la memoria principal:
• Deja un solo agujero grande de memoria libre contigua.
• Esta técnica se denomina “recogida de residuos”.
Una de las principales desventajas de la compresión es que consume recursos del sistema.
El sistema debe detener todo mientras efectúa la compresión, lo que puede afectar los tiempos de
respuesta.
Implica la relocalización (reubicación) de los procesos que se encuentran en la memoria. La
información de relocalización debe ser de accesibilidad inmediata. Una alta carga de trabajo
significa mayor frecuencia de compresión que incrementa el uso de recursos.
5.2.4. Paginación
El que los procesos tengan que usar un espacio contiguo de la memoria es un impedimento serio
para optimizar el uso de la memoria. Se podría considerar que las direcciones lógicas sean
contiguas, pero que no necesariamente correspondan a direcciones físicas contiguas. Es decir,
dividir la memoria física en bloques de tamaño fijo, llamados marcos (frames), y dividir la memoria
lógica (la que los procesos ven) en bloques del mismo tamaño llamados páginas.
Se usa una tabla de páginas para saber en qué marco se encuentra cada página. Obviamente, se
requiere apoyo del hardware. Cada vez que la CPU intenta accesar una dirección, la dirección se
divide en número de página p y desplazamiento d (offset). El número de página se transforma en el
marco correspondiente, antes de accesar físicamente la memoria.
El tamaño de las páginas es una potencia de 2, entre 512 bytes y 8 kb. Si las direcciones son de
m bits y el tamaño de página es 2n, entonces los primeros m-n bits de cada dirección forman p, y
los restantes n forman d. Este esquema es parecido a tener varios pares de registros base y límite,
uno para cada marco.
Cada proceso tiene su propia tabla, cuando la CPU se concede a otro proceso, hay que cambiar la
tabla de páginas a la del nuevo proceso. La paginación en general encarece los cambios de
contexto. La seguridad sale gratis, ya que cada proceso sólo puede accesar las páginas que están
en su tabla de páginas. Hay fragmentación interna, y de media página por proceso, en promedio.
Esto sugeriría que conviene usar páginas chicas, pero eso aumentaría el sobrecosto de administrar
las páginas. En general, el tamaño de página ha ido aumentando con el tamaño de la memoria
física de una máquina típica.
Por ejemplo, en la figura siguiente, el computador genera direcciones de 24 bits, lo que permite un
espacio de direcciones de 16 Mb; se consideran marcos de páginas y páginas de 4 Kb. Un proceso
de 14 kb necesita, pues, cuatro páginas numeradas de 0 a 3 y cada página se le asigna un marco
de página de la memoria física. Para hacer esta asignación se usa una tabla de páginas, que se
construye cuando se carga el proceso y que contiene tantas entradas como paginas tenga este.
La tabla de páginas tiene cuatro entradas. Cada dirección lógica se divide en dos partes: el número
de página, que se emplea como un índice en la tabla de páginas y un desplazamiento dentro de la
página. La dirección lógica 002 0FF se descompone en dos campos: 002, que es el número de
página y 0FF que es el desplazamiento relativo dentro de esta página. De la tabla de páginas se
comprueba que a la pagina 002 le corresponde el marco de pagina 104, luego la dirección física se
construye sustituyendo, en el primer campo en el que se divide la dirección, el numero de pagina
por el marco de pagina correspondiente, resultando así la dirección física 104 0FF.
La solución típica es equipar las computadoras con un pequeño dispositivo de hardware para
transformar las direcciones lógicas en físicas sin pasar por la tabla de páginas. El dispositivo,
llamado TLB (buffer de consulta para traducción, en inglés, Translation Lookaside Buffer) o
también memoria asociativa.
La memoria asociativa guarda pares (clave, valor), y cuando se le presenta la clave, busca
simultáneamente en todos sus registros, y retorna, en pocos nanosegundos, el valor
correspondiente. Obviamente, la memoria asociativa es cara; por eso, los TLBs rara vez contienen
más de 64 registros. El TLB forma parte de la unidad de administración de memoria (MMU), y
contiene los pares (página, marco) de las páginas más recientemente accesadas. Cuando la CPU
genera una dirección lógica a la página p, la MMU busca una entrada (p,f) en el TLB. Si está, se
usa marco f, sin acudir a la memoria. Sólo si no hay una entrada para p la MMU debe accesar la
tabla de páginas en memoria (e incorporar una entrada para p en el TLB, posiblemente eliminando
otra).
Por pequeño que sea el TLB, la probabilidad de que la página esté en el TLB (tasa de aciertos) es
alta, porque los programas suelen hacer muchas referencias a unas pocas páginas. Si la tasa de
aciertos es el 90% y un acceso al TLB cuesta 10ns, entonces, en promedio, cada acceso a
memoria costará 87ns. Es decir, sólo un 24% más que un acceso sin paginación. Una Intel 80486
tiene 32 entradas en el TLB; Intel asegura una tasa de aciertos del 98%. En cada cambio de
contexto, hay que limpiar el TLB, lo que puede ser barato, pero hay que considerar un costo
indirecto: si los cambios de contexto son muy frecuentes, la tasa de aciertos se puede reducir.
5.2.5. Segmentación
Cuando se usa paginación, el sistema divide la memoria para poder administrarla, no para
facilitarle la vida al programador. La vista lógica que el programador tiene de la memoria no tiene
nada que ver con la vista física que el sistema tiene de ella. El sistema ve un sólo gran arreglo
dividido en páginas, pero el programador piensa en términos de un conjunto de subrutinas y
estructuras de datos, a las cuales se refiere por su nombre: la función coseno, el stack, la tabla de
símbolos, sin importar la ubicación en memoria, y si acaso una está antes o después que la otra.
La segmentación es una forma de administrar la memoria que permite que el usuario vea la
memoria como una colección de segmentos, cada uno de los cuales tiene un nombre y un tamaño
(que, además, puede variar dinámicamente). Las direcciones lógicas se especifican como un par
(segmento, desplazamiento).
Las direcciones especifican el nombre del segmento y el desplazamiento dentro del segmento; por
ello. El usuario debe especificar cada dirección mediante dos cantidades, el nombre del segmento
y un desplazamiento. Por ejemplo: una dirección del segmento de la tabla de símbolos es:
[segmento s, elemento 4]
5.2.5.1. Implementación
El programa de usuario se compila y el compilador construye automáticamente los segmentos de
acuerdo a la estructura del programa. Por ejemplo, un compilador de Pascal creará segmentos
separados para las variables globales, la pila de llamadas a los procedimientos (para almacenar
parámetros y direcciones de retorno), el código de cada uno de los procedimientos y funciones.
El cargador tomara todos los segmentos y le asignara números de segmento. Por propósito de
reubicación cada uno de los segmentos se compila comenzando por su propia dirección lógica 0.
Las direcciones lógicas, por tanto, constaran de un número de segmento y un desplazamiento
dentro de él.
En la figura se puede observar el uso de la tabla de segmentos donde se mantienen registrados los
descriptores de cada segmento: la base, correspondiente a la dirección física en que comienza el
segmento (obtenida durante la creación de la partición) y el tamaño del mismo.
El número de segmento, primer parámetro de la dirección lógica, se emplea como un índice dentro
de la tabla de segmentos. La dirección física se obtiene añadiendo el desplazamiento a la base del
segmento. Este desplazamiento no debe sobrepasar el tamaño máximo del segmento, si superara
el tamaño máximo registrado en la tabla se producirá una error de direccionamiento.
La realización de las tablas de segmentos es parecida a las tablas de páginas, teniendo en cuenta
que los segmentos son de diferentes tamaños. Así, una tabla de segmentos que se mantiene en
registros especiales puede ser referenciada muy rápidamente; la suma a la base y la comparación
con el tamaño se puede hacer simultáneamente. Este método puede llevarse a cabo mientras el
numero de segmentos no sea grande, pero cuando este crece la tabla de segmentos se deja en
memoria; en este caso, un registro base de la tabla de segmentos apunta a la tabla de segmentos;
además, como el numero de segmentos usados por un programa puede variar, también se emplea
un registro de la longitud de la tabla de segmentos.
La solución a este problema es disponer también de una memoria asociativa para retener las
entradas de la tabla de segmentos usadas más recientemente (análogamente a como se hacía en
las páginas) y conseguir rendimientos tan solo un poco peor que si tuviera acceso directo. La
segmentación no produce fragmentación interna, pero si externa, la cual ocurre cuando todos los
bloques de memoria libre son muy pequeños para acomodar a un segmento. En esta situación, el
proceso solo puede esperar a disponer de más memoria, agujeros más grandes, o usar estrategias
de compactación para crear huecos más grandes.
Para el proceso de la figura, el espacio de direcciones lógicas está constituido por seis segmentos
situados en memoria según se indica. La tabla de segmentos tiene una entrada para cada
segmento, indicándose la dirección de comienzo del segmento en la memoria física (base) y la
longitud del mismo (tamaño). El segmento 3 empieza en la dirección 1048576 y tiene un tamaño de
100 kb; si se hace una referencia a la dirección 115000 del segmento 3 se producirá un error de
direccionamiento, puesto que esta dirección supera el tamaño del segmento.
De forma absoluta no se puede decir que una técnica sea superior a otra, por ellos hay sistemas
que combinan los dos métodos para recoger lo mejor de ambos.
Una técnica muy extendida consiste en usar la segmentación desde el punto de vista del usuario
pero dividiendo cada segmento en páginas de tamaño fijo para su ubicación. Esta técnica es
adecuada en el caso de que los segmentos sean muy grandes y resuelve un grave inconveniente,
o sea casi imposible mantenerlos en su totalidad dentro de la memoria.
Hace muchos años las personas enfrentaron por primera vez programas que eran demasiado
grandes para caber en la memoria disponible. La solución que normalmente se adoptaba era dividir
el programa en fragmentos, llamados superposiciones (overlay). Algunos sistemas de
superposición eran muy complejos, pues permitían varias superposiciones en la memoria a la vez.
Las superposiciones se mantenían en disco y el sistema operativo las intercambiaba con la
memoria dinámicamente, según fuera necesario.
Aunque el trabajo real de intercambiar las superposiciones corría por cuenta del sistema, la tarea
de dividir el programa en fragmentos tenía que ser efectuada por el programador. La división de
programas grandes en fragmentos modulares pequeños consumía tiempo y era tediosa. No pasó
mucho tiempo antes de que a alguien se le ocurriera una forma de dejar todo el trabajo a la
computadora.
12
El método que inventó Fotheringham , se conoce ahora como memoria virtual. La idea en que se
basa la memoria virtual es que el tamaño combinado del programa, los datos y la pila puede
exceder la cantidad de memoria física disponible para él. El sistema operativo mantiene en la
memoria principal las partes del programa que actualmente se están usando, y el resto en el disco.
Por ejemplo, un programa de 16M puede ejecutarse en una máquina de 4M si se escogen con
cuidado los 4M que se mantendrán en la memoria en cada instante, intercambiando segmentos del
programa entre el disco y la memoria según se necesite.
La memoria virtual también puede funcionar en un sistema de multiprogramación, manteniendo
segmentos de muchos programas en la memoria a la vez. Mientras un programa está esperando
que se traiga a la memoria una de sus partes, está esperando E/S y no puede ejecutarse, así que
puede otorgarse la CPU a otro proceso, lo mismo que en cualquier otro sistema de
multiprogramación.
Mucho mejor sería poder extender la memoria de manera virtual, es decir, hacer que el proceso
tenga la ilusión de que la memoria es mucho más grande que la memoria física (o que el trozo de
memoria física que le corresponde, si tenemos multiprogramación). El sistema operativo se
encarga de mantener en memoria física los trozos (páginas) que el proceso está usando, y el resto
en disco. Ya que el disco es barato, podemos tener espacios de direccionamiento enormes.
o Estrategias de búsqueda: Tratan de los casos en que una página o segmento deben ser
traídos del almacenamiento secundario al primario.
§ Las estrategias de “búsqueda por demanda” esperan a que se haga referencia a una
página o segmento por un proceso antes de traerlos al almacenamiento primario.
§ Los esquemas de “búsqueda anticipada” intentan determinar por adelantado a qué
páginas o segmentos hará referencia un proceso para traerlos al almacenamiento
primario antes de ser explícitamente referenciados.
o Estrategias de colocación: Tratan del lugar del almacenamiento primario donde se colocará
una nueva página o segmento. Los sistemas toman las decisiones de colocación de una forma
trivial ya que una nueva página puede ser colocada dentro de cualquier marco de página
disponible.
o Estrategias de sustitución o reposición: Tratan de la decisión de cuál página o segmento
desplazar para hacer sitio a una nueva página o segmento cuando el almacenamiento primario
está completamente comprometido.
5.3.1.1. Paginación por demanda. Las páginas son cargadas por demanda. No se llevan páginas
del almacenamiento secundario al primario hasta que son referenciadas explícitamente por un
proceso en ejecución.
La memoria virtual se implementa con un poco de ayuda del hardware. Se agrega un bit a la tabla
de páginas, que indica si la página en cuestión es válida o inválida. Válida significa que está en
memoria (en el marco que indica la tabla), e inválida significa que no está.
12
J. Fotheringham. Dynamic Storage Allocation in the Atlas Computer, Including an Automatic Use of a Backing Store.
Commun. ACM, 1961.
El acceso a las páginas válidas funciona igual que antes, pero si la CPU intenta accesar una
página inválida, se produce una falta de página (page fault) que genera un trap al sistema
operativo, quien debe encargarse de ir a buscar esa página al disco, ponerla en la memoria, y
reanudar el proceso. El sistema operativo debe:
o Bloquear al proceso.
o Ubicar un marco libre. Si no hay, tiene que liberar uno.
o Ordenar al controlador de disco que lea la página (de alguna manera, el sistema operativo
debe saber dónde la guardó).
o Cuando se completa la lectura, modificar la tabla de páginas para reflejar que ahora la
página si es válida.
o Pasar el proceso a la cola READY. Cuando le toque ejecutar, no notará ninguna diferencia
entre esta falta de página y una simple expropiación de la CPU.
Con este mecanismo, ya no se necesita superposiciones para ejecutar programas grandes, sólo se
carga en memoria las partes del programa que se usan, reduciendo costos de lectura desde disco
y ya que no es necesario tener el programa completo en memoria para poder ejecutarlo, se puede
aumentar el nivel de multiprogramación.
5.3.1.3. Tablas de páginas. Ahora que la memoria lógica puede ser mucho más grande que la
física, se acentúa el problema del tamaño de la tabla de páginas. Con direcciones de 32 bits, la
memoria virtual puede alcanzar los 4GB. Con páginas de 4 KB, se necesita hasta 1M entradas. Si
cada entrada usa 32 bits, entonces la tabla podría pesar 4 MB. Además, cada proceso tiene su
tabla, y esta tabla debe estar siempre en memoria física mientras se ejecuta.
La solución es usar tablas de varios niveles. El 386 usa dos niveles: una dirección lógica de 32 bits
se divide en (p1, p2, d), de 10, 10 y 12 bits respectivamente. p1 es un índice a una tabla de tablas,
metatabla, o tabla de primer nivel, que contiene 210=1024 entradas de 32 bits, o sea, exactamente
una página. La entrada correspondiente a p1 en esta tabla indica el marco donde se encuentra otra
tabla (de segundo nivel), donde hay que buscar indexando por p2, el marco donde está la página
que finalmente se necesita.
Es indispensable mantener en memoria la tabla de primer nivel. Las otras se tratan como páginas
ordinarias, es decir, pueden estar en disco. Así, al utilizar la propia memoria virtual para estas
páginas, se mantienen en memoria física sólo las más usadas. Sin embargo, se está agregando un
acceso más a la memoria para convertir cada dirección lógica a una física, pero con un TLB con
tasa de aciertos alta el impacto es mínimo.
5.3.1.4. Tablas de páginas invertidas. Las tablas de páginas tradicionales del tipo que hemos
descrito hasta ahora requieren una entradas por cada página virtual, ya que están indizadas por
número de página virtual. Si el espacio de direcciones consta de 232 bytes, con 4096 bytes por
página, se necesitará más de un millón de entradas de tabla. Como mínimo, la tabla de páginas
tendrá que ocupar 4 megabytes. En los sistemas grandes, este tamaño probablemente será
manejable.
Sin embargo, en computadoras de 64 bits, la situación cambia drásticamente. Si el espacio de
direcciones ahora tiene 264 bytes, con páginas de 4K, se necesitara más de 1015 bytes para la
tabla de páginas. Sacar de circulación un millón de gigabytes sólo para la tabla de páginas no es
razonable. Por tanto, se requiere una solución distinta para los espacios de direcciones virtuales de
64 bits paginados.
Una solución es la tabla de páginas invertida. En este diseño, hay una entrada por marco de
página de la memoria real, no por cada página del espacio de direcciones virtual. Por ejemplo, con
direcciones virtuales de 64 bits, páginas de 4K y 32MB de RAM, una tabla de páginas invertida
sólo requiere 8192 entradas. La entrada indica cuál (proceso, página virtual) está en ese marco de
página.
Aunque las tablas de páginas invertidas ahorran enormes cantidades de espacio, al menos cuando
el espacio de direcciones virtual es mucho más grande que la memoria física, tienen una
desventaja importante: la traducción de virtual a física se vuelve mucho más difícil. Cuando el
proceso n hace referencia a la página virtual p, el hardware ya no puede encontrar la página física
usando p como índice de la tabla de páginas. En vez de ello, debe buscar en toda la tabla de
páginas invertida una entrada (n, p). Además, esta búsqueda debe efectuarse en cada referencia a
la memoria, no sólo cuando hay una falla de página. Examinar una tabla de 8K cada vez que se
hace referencia a la memoria no es la forma de hacer que una máquina sea vertiginosamente
rápida.
La solución a este dilema es usar el TLB. Si el TLB puede contener todas las páginas de uso
pesado, la traducción puede efectuarse con tanta rapidez como con las tablas de páginas
normales. Sin embargo, si ocurre una falla de TLB, habrá que examinar la tabla de páginas
invertida. Si se usa una tabla de dispersión como índice de la tabla de páginas invertida, esta
búsqueda puede hacerse razonablemente rápida.
5.3.2.2. Algoritmo de sustitución de páginas de primera que entra, primera que sale (FIFO)
Consiste en reemplazar la página más vieja (la que lleva más tiempo en memoria física). Es simple,
pero no es bueno, ya que la página más antigua no necesariamente es la menos usada. Además
sufre de la Anomalía de FIFO (Belady, Nelson y Shedler descubrieron que con el algoritmo FIFO,
ciertos patrones de referencias de páginas causan más fallos de páginas cuando se aumenta el
13
número de marcos de páginas asignados a un proceso) .
El sistema operativo mantiene una lista de todas las páginas que están en la memoria, siendo la
página que está a la cabeza de la lista la más vieja, y la del final, la más reciente. Cuando hay una
falla de página, se elimina la página que está a la cabeza de la lista y se agrega la nueva página al
final. En la siguiente figura, se considera la secuencia de acceso a las paginas (8, 1, 2, 3, 1, 4, 1,
5, 3, 4, 1, 4). Tiene 3 marcos de página. Si inicialmente la memoria esta vacía, las primeras tres
transferencias causaran fallos de pagina, que provocaran que se traigan las tres paginas (8,1, 2) a
la memoria. Para la siguiente referencia no se tiene espacio y se tendrá que elegir una pagina para
sustituir, se elige la 8 que fue la primera que se cargo en memoria. Cuando se accede a la 1, esta
ya esta en memoria y no hay que hacer nada, pero al referenciar la pagina 4, se sustituye la 1 y así
sucesivamente.
13
An anomaly in space-time characteristics of certain programs running in a paging machine. Communications of the ACM.
Volume 12 Issue 6, June 1969
nuevo inicio. Se vuelve vulnerable al reemplazo aún a las páginas activas, pero solo brevemente,
mientras se reajustan los bits. Los “bits modificados” no se ajustan periódicamente según esta
estrategia.
También se apaga su bit R. La búsqueda de una página apropiada continúa con B. Lo que hace el
algoritmo de segunda oportunidad es buscar una página vieja a la que no se, haya hecho
referencia en el intervalo de reloj anterior. Si se ha hecho referencia a todas las páginas, este
algoritmo pasa a ser FIFO puro. Específicamente, imaginemos que todas las páginas de la primera
figura tienen su bit R encendido. Una por una, el sistema operativo pasará' páginas al final de la
lista, apagando el bit R cada vez que anexa una página al final de la lista. Tarde o temprano,
regresará a la página A, que ahora tiene su bit R apagado. En este punto, A será desalojada. Así,
el algoritmo siempre termina.
Cuando ocurre una falla de página, se inspecciona la página a la que apunta la manecilla. Si su bit
R es 0, se desaloja la página, se inserta la nueva página en el reloj en su lugar, y la manecilla
avanza una posición. Si R es 1, se pone en 0 y la manecilla se avanza a la siguiente página. Este
proceso se repite hasta encontrar una página con R = 0. No resulta sorprendente que este
algoritmo se llame de reloj. La única diferencia respecto al de segunda oportunidad es la
implementación.
Tema VI
SISTEMA DE ARCHIVOS
Todas las aplicaciones de computadora necesitan almacenar y recuperar información, y las
condiciones esenciales para el almacenamiento de información a largo plazo son:
• Debe ser posible almacenar una cantidad muy grande de información. Mientras un
proceso se está ejecutando, puede almacenar una cantidad de información limitada dentro de
su propio espacio de direcciones. Sin embargo, la capacidad de almacenamiento está
restringida al tamaño del espacio de direcciones virtual. En el caso de algunas aplicaciones,
este tamaño es adecuado, pero en el de otras, dicho tamaño resulta excesivamente pequeño.
• La información debe sobrevivir a la conclusión del proceso que la utiliza. Al mantener la
información dentro del espacio de direcciones de un proceso, sucede que cuando el proceso
termina la información se pierde. En muchas aplicaciones (como las bases de datos), la
información debe retenerse durante semanas, meses, o incluso eternamente. No es aceptable
que la información desaparezca cuando el proceso que la está usando termina. Además, la
información no debe perderse cuando una caída de la computadora termina el proceso.
• Debe ser posible que varios procesos tengan acceso concurrente a la información. En
muchos casos es necesario que múltiples procesos accedan a la información al mismo tiempo.
6.1. Archivos
Es una colección o conjunto de datos relacionados lógicamente. Se considerará el punto de vista
del usuario. Los archivos son un mecanismo de abstracción; proporcionan una forma de almacenar
información en el disco y leerla después. Esto debe hacerse de tal manera que el usuario no tenga
que ocuparse de los detalles de cómo y dónde se almacena la información, ni de cómo funcionan
realmente los discos.
• Secuencia de bytes (a). El archivo es una serie no estructurada de bytes. El sistema operativo
no sabe (ni le importa) qué contiene el archivo; lo único que ve es bytes. Cualquier significado
que tenga deberán imponerlo los programas en el nivel de usuario. Tanto UNIX como MS-DOS
adoptan este enfoque. Windows usa básicamente el sistema de archivos de MS-DOS,
agregándole un poco de azúcar sintáctica (nombres de archivo largos), así que casi todo lo que
se diga acerca de MS-DOS también aplica a WINDOWS.
• Secuencia de registros (b). Un archivo es una secuencia de registros de longitud fija, cada
uno con cierta estructura interna. La idea de que un archivo es una secuencia de registros se
apoya en el concepto de que la operación de lectura devuelve un registro y que la operación de
escritura sobreescribe o anexa un registro. En el pasado, cuando existía la tarjeta perforada de
80 columnas, muchos sistemas operativos tenían archivos compuestos por registros de 80
caracteres, que eran imágenes de tarjetas. Estos sistemas también daban soporte a archivos
con registros de 132 caracteres, pensados para la impresora de líneas. Los programas leían
las entradas en unidades de 80 caracteres y las escribían en unidades de 132 caracteres Un
sistema (antiguo) que consideraba los archivos como secuencias de registros de longitud fija
era CP/M. Éste utilizaba registros de 128 caracteres. Hoy día, la idea de un archivo como una
secuencia de registros de longitud fija es prácticamente cosa del pasado.
eso también es posible, sino obtener el registro que tiene una llave dada. En el caso del
archivo de zoológico de la figura (c), podríamos pedirle al sistema que obtenga el registro cuya
llave es pony, por ejemplo, sin tener que preocuparnos por su posición exacta en el archivo.
Además, es posible agregar nuevos registros al archivo dejando que el sistema operativo, y no
el usuario, decida dónde deben colocarse. Este tipo de archivo obviamente es muy distinto de
los flujos de bytes no estructurados que se emplean en UNIX y MS-DOS, pero se utiliza
ampliamente en las macrocomputadoras que todavía se usan en algunas aplicaciones
comerciales de procesamiento de datos.
6.2. Directorios
Los sistemas de archivos casi siempre tienen directorios para organizar los archivos, En muchos
sistemas, son también archivos.
• Directorio Único. El diseño más sencillo es aquel en el que el sistema mantiene un solo
directorio que contiene todos los archivos de todos los usuarios. Si hay muchos usuarios, y
éstos escogen los mismos nombres de archivo (correo y juegos), los conflictos y la confusión
resultante pronto harán inmanejable el sistema. Este modelo se utilizó en los primeros
sistemas operativos de microcomputadoras, pero ya casi nunca se encuentra.
• Un directorio por usuario. Este diseño elimina los conflictos de nombres entre usuarios pero
no es satisfactorio para quienes tienen un gran número de archivos. Es muy común que los
usuarios quieran agrupar sus archivos atendiendo a patrones lógicos. Un profesor, por
ejemplo, podría tener una colección de archivos que juntos constituyan un libro que está
escribiendo para un curso, una segunda colección de archivos que contenga programas que
los estudiantes de otro curso hayan presentado, un tercer grupo de archivos que contenga el
código de un sistema avanzado de escritura de compiladores que él esté construyendo, un
cuarto grupo de archivos que contenga propuestas para obtener subvenciones, así como otros
archivos para correo electrónico, minutas de reuniones, artículos que esté escribiendo, juegos,
etc.
Se requiere algún método para agrupar estos archivos en formas flexibles elegidas por el usuario.
• Árbol de directorios. Cada usuario puede tener tantos directorios como necesite para poder
agrupar sus archivo) según patrones naturales. Los directorios contenidos en el directorio raíz,
pertenecen cada uno a un usuario distinto.
cp /datos/joa/mailbox /datos/joa/mailbox.bak
y el comando
cp mailbox mailbox.bak
harán exactamente lo mismo si el directorio de trabajo es /datos/joa. La forma relativa suele ser
más cómoda, pero hace lo mismo que la forma absoluta.
Algunos programas necesitan acceder a un archivo específico sin considerar el directorio de
trabajo. En tal caso, siempre deben usar nombres de ruta absolutos. Por ejemplo, un revisor
ortográfico podría necesitar leer /usr/lib/dictionary para efectuar su trabajo. En este caso, el
programa deberá usar el nombre de ruta absoluto completo porque no sabe cuál será el directorio
de trabajo cuando sea invocado. El nombre de ruta absoluta siempre funciona, sea cual sea el
directorio de trabajo.
La mayor parte de los sistemas operativos que manejan un sistema de directorios jerárquico tiene
dos entradas especiales en cada directorio, "." y "..", generalmente pronunciados "punto" y "punto
punto". Punto se refiere al directorio actual; punto punto se refiere a su padre.
CRÉATE. Se crea un directorio, que está vacío con la excepción de punto y punto, punto,
que el sistema (o, en unos pocos casos, el programa mkdir) coloca ahí automáticamente.
DELETE. Se elimina un directorio. Sólo puede eliminarse un directorio vacío. Un directorio
que sólo contiene punto y punto punto se considera vacío, ya que éstos normalmente no
pueden eliminarse.
OPENDIR. Los directorios pueden leerse. Por ejemplo, para listar todos los archivos de un
directorio, un programa para emitir listados abre el directorio y lee los nombres de los
archivos que contiene. Antes de poder leer un directorio, es preciso abrirlo, de forma
análoga a como se abren y leen los archivos.
CLOSEDIR. Una vez que se ha leído un directorio, debe cerrarse para liberar espacio de
tablas internas.
READDIR. Esta llamada devuelve la siguiente entrada de un directorio abierto. Antes, era
posible leer directorios empleando la llamada al sistema READ normal, pero ese enfoque
tiene la desventaja de obligar al programador a conocer y manejar la estructura interna de
los directorios. En contraste, READDIR siempre devuelve una entrada en un formato
estándar, sin importar cuál de las posibles estructuras de directorio se esté usando.
RENAME. En muchos sentidos, los directorios son iguales que los archivos y podemos
cambiar su nombre tal como hacemos con los archivos.
LINK. El enlace (linking) es una técnica que permite a un archivo aparecer en más de un
directorio. Esta llamada al sistema especifica un archivo existente y un nombre de ruta, y
crea un enlace del archivo existente al nombre especificado por la ruta. De este modo, el
mismo archivo puede aparecer en múltiples directorios.
UNLINK. Se elimina una entrada de directorio. Si el archivo que está siendo desvinculado
sólo está presente en un directorio (el caso normal), se eliminará del sistema de archivos.
Si el archivo está presente en varios directorios, sólo se eliminará el nombre de ruta
especificado; los demás seguirán existiendo. En UNIX, la llamada al sistema para eliminar
archivos (que ya vimos antes) es, de hecho, UNLINK.
saber dónde están los bloques de un archivo basta con recordar un número( la dirección en
disco del primer bloque) y que el rendimiento es excelente porque es posible leer todo el
archivo del disco en una sola operación. Las desventajas son que se debe conocer el tamaño
máximo del archivo al crearlo y que produce una gran fragmentación de los discos.
• Asignación por lista enlazada. Consiste en guardar cada archivo como una lista enlazada de
bloques de disco. La primera palabra de cada bloque se emplea como apuntador al siguiente.
El resto del bloque se destina a datos. Las ventajas son que es posible utilizar todos los
bloques (No se pierde espacio por fragmentación del disco, excepto por fragmentación interna
en el último bloque) y que el directorio sólo debe registrar el primer bloque de cada archivo (No
es necesario declarar el máximo tamaño que puede llegar a tener un archivo, puesto que
puede crecer sin problemas, mientras queden bloques libres). Las desventajas son que,
aunque la lectura secuencial de un archivo es sencilla, el acceso aleatorio es extremadamente
lento y que la cantidad de almacenamiento de datos en un bloque ya no es una potencia de
dos porque el apuntador ocupa unos cuantos bytes.
• Asignación por lista enlazada empleando un índice. Para eliminar las desventajas del
método anterior, en vez de tener esparcidos los punteros en cada bloque, se pueden agrupar y
poner todos juntos en una tabla o FAT (Tabla de asignación de archivos).
En la figura se muestra un ejemplo de la tabla con dos archivos. El archivo A usa los bloques
de disco 4,7,2,10 y 12, en ese orden, y el archivo B usa los bloques de disco 6, 3, 11 y 14, en
ese orden. Se puede comenzar en el bloque 4 y seguir la cadena hasta el final. Lo mismo
puede hacerse comenzando en el bloque 6. Si se emplea esta organización, todo el bloque
está disponible para datos. Además, el acceso directo es mucho más fácil. Aunque todavía hay
que seguir la cadena para encontrar una distancia dada dentro de un archivo, la cadena está
por completo en la memoria, y puede seguirse sin tener que consultar el disco. Al igual que con
el método anterior, basta con guardar un solo entero (el número del bloque inicial) en la
entrada de directorio para poder localizar todos los bloques, por más grande que sea el
archivo. MS-DOS emplea este método para la asignación en disco. La desventaja es que toda
la tabla debe estar en la memoria todo el tiempo para que funcione. En el caso de un disco
grande con, digamos, 500 000 bloques de 1K (500M), la tabla tendrá 500 000 entradas, cada
una de las cuales tendrá que tener un mínimo de 3 bytes. Si se desea acelerar las búsquedas,
se necesitarán 4 bytes. Así, la tabla ocupará de 1.5 a 2 megabytes todo el tiempo,
dependiendo de si el sistema se optimiza en cuanto al espacio o en cuanto al tiempo. Aunque
MS-DOS emplea este mecanismo, evita manejar tablas muy grandes empleando bloques
grandes (de hasta 32K) en los discos de gran tamaño.
• Nodos-I. Consiste en mantener juntos los punteros de cada archivo, en una tabla llamada
nodo-i (nodo-índice), asociada al archivo, y que se guarda en un bloque como cualquiera
(esta tabla es análoga a la tabla de páginas). Además, en ese bloque se puede guardar
información de los otros atributos del archivo. El directorio sólo contiene un puntero al
bloque que contiene la tabla.
Las primeras pocas direcciones de disco se almacenan en el nodo-i mismo, así que en el
caso de archivos pequeños toda la información está contenida en el nodo-i, que se trae del
disco a la memoria principal cuando se abre el archivo. En el caso de archivos más
grandes, una de las direcciones del nodo-i es la dirección de un bloque de disco llamado
bloque de indirección sencilla. Este bloque contiene direcciones de disco adicionales. Si
esto todavía no es suficiente, otra dirección del nodo-i, llamada bloque de indirección
doble, contiene la dirección de un bloque que contiene una lista de bloques de indirección
sencilla. Cada uno de estos bloques de indirección sencilla apunta a unos cuantos cientos
de bloques de datos. Si ni siquiera con esto basta, se puede usar también un bloque de
dirección triple. UNIX emplea este esquema. Las ventajas son que lo único que hay que
registrar en el directorio es un puntero al nodo-i, además que el acceso aleatorio es rápido
para archivos pequeños y que el sobrecosto fijo es bajo (no hay FAT, entradas en
directorios pequeñas). Las desventajas es que es relativamente complejo, además hay
mayor sobrecosto variable (cada archivo, por pequeño que sea, necesita al menos dos
bloques) y que el acceso aleatorio es más complicado para archivos grandes (en todo
caso, los bloques con índices pueden guardarse en memoria para agilizar el acceso).
Directorios en MS-DOS
La figura muestra una entrada de directorio de MS-DOS, la cual tiene 32 bytes de longitud y
contiene el nombre de archivo, los atributos y el número del primer bloque de disco. El primer
número de bloque se emplea como índice de una tabla del tipo FAT. Siguiendo la cadena, se
pueden encontrar todos los bloques.
En MS-DOS, los directorios pueden contener otros directorios, dando lugar a un sistema de
archivos jerárquico. En este sistema operativo es común que los diferentes programas de
aplicación comiencen por crear un directorio en el directorio raíz y pongan ahí todos sus archivos,
con objeto de que no haya conflictos entre las aplicaciones.
Directorios en UNIX
En la estructura de directorios UNIX, cada entrada contiene sólo un nombre de archivo y su
número de nodo-i. Toda la información acerca del tipo, tamaño, tiempos, propietario y bloques de
disco está contenida en el nodo-i.
Algunos sistemas UNIX tienen una organización distinta, pero en todos los casos una entrada de
directorio contiene en última instancia sólo una cadena ASCII y un número de nodo-i.
Cuando se abre un archivo, el sistema de archivos debe tomar el nombre que se le proporciona y
localizar sus bloques de disco. Consideremos cómo se busca el nombre de ruta /usr/ast/mbox. Lo
primero que hace el sistema de archivos es localizar el directorio raíz. En UNIX su nodo-i está
situado en un lugar fijo del disco. A continuación, el sistema de archivos busca el primer
componente de la ruta, “usr”, en el directorio raíz para encontrar el número de nodo-i del archivo
/usr. La localización de un nodo-i, una vez que se tiene su número es directa, ya que cada uno
tiene una posición fija en el disco. Con la ayuda de este nodo-i, el sistema localiza el directorio
correspondiente a /usr y busca el siguiente componente, “ast”, dentro de él. Una vez que el sistema
encuentra la entrada para “ast”, obtiene el nodo-i del directorio /usr/ast. Con este nodo, el sistema
puede encontrar el directorio mismo y buscar el archivo mbox.
Luego se trae a la memoria el nodo-i de este archivo y se mantiene ahí hasta que se cierra el
archivo. El proceso de búsqueda se ilustra en la siguiente figura:
Los nombres de ruta relativos se buscan de la misma forma que los absolutos, sólo que el punto de
partida es el directorio de trabajo en lugar del directorio raíz. Cada directorio tiene entradas para “.”
y “..”, que se colocan ahí cuando se crea el directorio. La entrada “.” tiene el número de nodo-i del
directorio actual, y la entrada “..” tiene el número de nodo-i del directorio padre. Así, un
procedimiento que busque ../dick/prog.c simplemente buscará “..” en el directorio de trabajo,
encontrará el número de nodo-i de su directorio padre y buscará dick en ese directorio. No se
requiere ningún mecanismo especial para manejar estos nombres. En lo que al sistema de
directorios concierne, se trata de cadenas ASCII ordinarias, lo mismo que los demás nombres.
Tamaño de bloque
Una vez que se ha decidido almacenar archivos en bloques de tamaño fijo, surge la pregunta de
qué tamaño deben tener los bloques. Dada la forma como están organizados los discos, el sector,
la pista y el cilindro son candidatos obvios para utilizarse como unidad de asignación. En un
sistema con paginación, el tamaño de página también es un contendiente importante.
Tener una unidad de asignación grande, como un cilindro, implica que cada archivo, incluso un
archivo de un byte, ocupará todo un cilindro. Estudios realizados (Mullender y Tanenbaum, 1984)
han demostrado que la mediana del tamaño de los archivos en los entornos UNIX es de alrededor
de 1K, así que asignar un cilindro de 32K a cada archivo implicaría un desperdicio de 31/32 = 97%
del espacio en disco total. Por otro lado, el empleo de una unidad de asignación pequeña implica
que cada archivo consistirá en muchos bloques. La lectura de cada bloque normalmente requiere
una búsqueda y un retardo rotacional, así que la lectura de un archivo que consta de muchos
bloques pequeños será lenta.
Por ejemplo, consideremos un disco con 32 768 bytes por pista, tiempo de rotación de 16.67 ms y
tiempo de búsqueda medio de 30 ms. El tiempo en milisegundos requerido para leer un bloque de
k bytes es la suma de los tiempos de búsqueda, retardo rotacional y transferencia:
30 + 8.3 + (k/32768) x 16.67
La curva continua de la siguiente figura muestra la tasa de datos para un disco con estas
características en función del tamaño de bloque. Si utilizamos el supuesto burdo de que todos los
bloques son de 1K (la mediana de tamaño medida), la curva de guiones de la siguiente figura
indicará la eficiencia de espacio del disco. La mala noticia es que una buena utilización del espacio
(tamaño de bloque < 2K) implica tasas de datos bajas y viceversa. La eficiencia de tiempo y la
eficiencia de espacio están inherentemente en conflicto. El término medio usual es escoger un
tamaño de bloque de 512, 1K o 2K bytes. Si se escoge un tamaño de bloque de 1K en un disco
cuyos sectores son de 512 bytes, el sistema de archivos siempre leerá o escribirá dos sectores
consecutivos y los tratará como una sola unidad, indivisible. Sea cual sea la decisión que se tome,
probablemente convendrá reevaluarla periódicamente, ya que, al igual que sucede con todos los
aspectos de la tecnología de computadoras, los usuarios aprovechan los recursos más abundantes
exigiendo todavía más.
La otra técnica de administración del espacio libre es (b) el mapa de bits. Un disco con n bloques
requiere un mapa de bits con n bits. Los bloques libres se representan con unos en el mapa, y los
bloques asignados con ceros (o viceversa). Un disco de 200M requiere 200K bits para el mapa,
mismos que ocupan sólo 25 bloques. No es sorprendente que el mapa de bits requiera menos
espacio, ya que sólo usa un bit por bloque, en vez de 32 como en el modelo de lista enlazada. Sólo
si el disco está casi lleno el esquema de lista enlazada requerirá menos bloques que el mapa de
bits. Si hay suficiente memoria principal para contener el mapa de bits, este método generalmente
es preferible. En cambio, si sólo se puede dedicar un bloque de memoria para seguir la pista a los
bloques de disco libres, y el disco está casi lleno, la lista enlazada podría ser mejor. Con sólo un
bloque del mapa de bits en la memoria, podría ser imposible encontrar bloques libres en él,
causando accesos a disco para leer el resto del mapa de bits. Cuando un bloque nuevo de la lista
enlazada se carga en la memoria, es posible asignar 255 bloques de disco antes de tener que traer
del disco el siguiente bloque de la lista.
Para manejar bloques defectuosos se utilizan soluciones por hardware y por software.
• La solución en hardware consiste en dedicar un sector del disco a la lista de bloques
defectuosos. Al inicializar el controlador de hardware por primera vez, este lee la “lista de
bloques defectuosos” y elige un bloque (o pista) de repuesto para reemplazar los
defectuosos, registrando la correspondencia en la lista de bloques defectuosos. A partir de
entonces, todas las solicitudes que pidan el bloque defectuoso usarán el de repuesto.
Cada vez que se descubren nuevos errores se actualiza esta lista como parte de un
formato de bajo nivel.
• La solución en software requiere que el usuario o el sistema de archivos construyan un
archivo con todos los bloques defectuosos. Se los elimina de la lista de bloques libres y se
crea un “archivo de bloques defectuosos que está constituido por los bloques defectuosos
que no debe ser leído ni escrito y no se debe intentar obtener copias de respaldo de este
archivo.
Otra estrategia es el vaciado por incrementos o respaldo incremental, donde se obtiene una copia
de respaldo periódicamente (una vez por mes o por semana), llamada copia total. Se obtiene una
copia diaria solo de aquellos archivos modificados desde la última copia total; en estrategias
mejoradas, se copian solo aquellos archivos modificados desde la última vez que dichos archivos
fueron copiados. Se debe mantener en el disco información de control como una lista de los
tiempos de copiado de cada archivo, la que debe ser actualizada cada vez que se obtienen copias
de los archivos y cada vez que los archivos son modificados. Puede requerir una gran cantidad de
cintas de respaldo dedicadas a los respaldos diarios entre respaldos completos.
También se puede usar métodos automáticos que emplean múltiples discos, como la creación de
espejos que emplea dos discos. Las escrituras se efectúan en ambos discos, y las lecturas
provienen de uno solo. La escritura en el disco espejo se retrasa un poco, efectuándose cuando el
sistema está ocioso. Un sistema así puede seguir funcionando en "modo degradado" si un disco
falla, y esto permite reemplazar el disco que falló y recuperar los datos sin tener que parar el
sistema.
todos o algunos de los discos y pueden efectuar verificaciones a nivel de bloques y a nivel de
archivos. La consistencia del sistema de archivos no asegura la consistencia interna de cada
archivo, respecto de su contenido. Generalmente pueden verificar también el sistema de directorios
y / o de bibliotecas.
Otra situación que podría ocurrir es la de la figura (c). Aquí vemos un bloque, el número 4, que
ocurre dos veces en la lista libre. (Sólo puede haber duplicados si la lista libre es realmente una
lista; si es un mapa de bits esto es imposible.) La solución en este caso también es simple:
reconstruir la lista libre. Lo peor que puede suceder es que el mismo bloque de datos esté presente
en dos o más archivos, como se muestra en la figura (d) con el bloque 5. Si cualquiera de estos
archivos se elimina, el bloque 5 se colocará en la lista libre, dando lugar a una situación en la que
el mismo bloque está en uso y libre al mismo tiempo. Si se eliminan ambos archivos, el bloque se
colocará en la lista libre dos veces. La acción apropiada para el verificador del sistema de archivos
es asignar un bloque libre, copiar en él el contenido del bloque 5, e insertar la copia en uno de los
archivos. De este modo, el contenido de información de los archivos no cambiará (aunque casi con
toda seguridad estará revuelto), y la estructura del sistema de archivos al menos será consistente.
Se deberá informar del error, para que el usuario pueda inspeccionar los daños.
Además de verificar que cada bloque esté donde debe estar, el verificador del sistema de archivos
también revisa el sistema de directorios. En este caso también se usa una tabla de contadores,
pero ahora uno por cada archivo, no por cada bloque. El programa parte del directorio raíz y
desciende recursivamente el árbol, inspeccionando cada directorio del sistema de archivo; Para
cada archivo de cada directorio, el verificador incrementa el contador correspondiente í nodo-i de
ese archivo. Una vez que termina la revisión, el verificador tiene una lista, indizada por número de
nodo que indica cuántos directorios apuntan a ese nodo-i. Luego, el programa compara estos
números con los conteos de enlace almacenados en los nodos-i mismos. En un sistema de
archivos consistente, ambos conteos coinciden.
Estas dos operaciones, verificar bloques y verificar directorios, a menudo se integran por razones
de eficiencia (una sola pasada por los nodos-i).
El sistema de archivos FAT es uno de los sistemas más simples que se implementan por los
sistemas operativos. Esta sencillez viene dada por el reducido número de estructuras que lo
conforman. FAT nació como una solución a la gestión de archivos y directorios para los sistemas
DOS. Posteriormente su uso fue extendido a los sistemas operativos Windows en sus diferentes
versiones, así como para sistemas UNIX.
El nombre de FAT viene dado porque su principal estructura es precisamente una tabla de
asignación de archivos (FAT, File Allocation Table). Dependiendo del tamaño de las entradas de
esta tabla distinguiremos tres variantes de este sistema. Si las entradas son de 12 bits nos
estaremos refiriendo a FAT12. Si las entradas son de 16 bits hablaremos de FAT16. Finalmente, si
las entradas son de 32 bits (realmente se utilizan 28) nos dirigiremos a FAT32.
La tabla de asignación de archivos (FAT), reside en la parte más "superior" del volumen. Para
proteger el volumen, se guardan dos copias de la FAT por si una resultara dañada. Además, las
tablas FAT y el directorio raíz deben almacenarse en una ubicación fija para que los archivos de
arranque del sistema se puedan ubicar correctamente.
Un disco con formato FAT se asigna en clústeres, cuyo tamaño viene determinado por el tamaño
del volumen. Cuando se crea un archivo, se crea una entrada en el directorio y se establece el
primer número de clúster que contiene datos. Esta entrada de la tabla FAT indica que este es el
último clúster del archivo o bien señala al clúster siguiente.
Si el archivo fuese mas grande que un cluster se informa sobre la ubicación del cluster inicial y
luego se busca otro cluster (en lo posible consecutivo) para seguir almacenando el dato, colocando
este numero en la posición inicial para indicar donde continuar la búsqueda al momento de
recuperar el archivo y repitiendo este proceso hasta llegar al fin del archivo donde se colocara la
sentencia EOF.
. " / \ [ ] : ; | = ,
Ventajas de FAT
No es posible realizar una recuperación de archivos eliminados en Windows NT en ninguno de los
sistemas de archivos compatibles. Las utilidades de recuperación de archivos eliminados intentan
tener acceso directamente al hardware, lo que no se puede hacer en Windows NT. Sin embargo, si
el archivo estuviera en una partición FAT y se reiniciara el sistema en MS-DOS, se podría
recuperar el archivo. El sistema de archivos FAT es el más adecuado para las unidades y/o
particiones de menos de 200 MB aproximadamente, ya que FAT se inicia con muy poca
sobrecarga.
Desventajas de FAT
Cuando se utilicen unidades o particiones de más de 200 MB, es preferible no utilizar el sistema de
archivos FAT. El motivo es que a medida que aumente el tamaño del volumen, el rendimiento con
FAT disminuirá rápidamente. No es posible establecer permisos en archivos que estén en
particiones FAT.
Las particiones FAT tienen un tamaño limitado a un máximo de 4 Gigabytes (GB) en Windows NT y
2 GB en MS-DOS.
El sistema de archivos HPFS se presentó por primera vez con OS/2 1.2 para permitir un mejor
acceso a los discos duros de mayor tamaño que estaban apareciendo en el mercado. Además, era
necesario que un nuevo sistema de archivos ampliara el sistema de nomenclatura, la organización
y la seguridad para las crecientes demandas del mercado de servidores de red. HPFS mantiene la
organización de directorio de FAT, pero agrega la ordenación automática del directorio basada en
nombres de archivo. Los nombres de archivo se amplían hasta 254 caracteres de doble byte.
HPFS también permite crear un archivo de "datos" y atributos especiales para permitir una mayor
flexibilidad en términos de compatibilidad con otras convenciones de nomenclatura y seguridad.
Además, la unidad de asignación cambia de clústeres a sectores físicos (512 bytes), lo que reduce
el espacio perdido en el disco.
En HPFS, las entradas de directorio contienen más información que en FAT. Además del archivo
de atributos, esto incluye información sobre la fecha y la hora de modificación, de creación y de
acceso. En lugar de señalar al primer clúster del archivo, en HPFS las entradas del directorio
señalan a FNODE. FNODE puede contener los datos del archivo, o bien punteros que pueden
señalar a datos del archivo o a otras estructuras que, a su vez, señalarán a datos del archivo.
operaciones de E/S de disco (es decir, la aplicación nunca sabe que hubo problemas con el disco
duro). Al utilizar un sistema de archivos que admite revisiones, se eliminarán mensajes de error
como el de FAT "¿Desea interrumpir, reintentar o cancelar?" que aparece cuando se encuentra un
sector defectuoso. La versión de HPFS incluida con Windows NT no admite revisiones.
Ventajas de HPFS
• HPFS es la mejor opción para las unidades comprendidas entre 200 y 400 MB.
• Permite nombres de archivos de hasta 256 caracteres.
• El volumen está estructurado en bandas.
• La estructura de directorios es una estructura de árbol binario cuyos nodos se denominan
Fondees. Estas estructuras contienen un nombre de archivo, su longitud, atributos, ACL
(Access Control List) y situación de los datos del archivo, es decir, el número de banda en
el que se encuentran.
Desventajas de HPFS
• Debido a la sobrecarga que implica HPFS, no es una opción muy eficaz para un volumen
de menos de unos 200 MB. Además, con volúmenes mayores de unos 400 MB, habrá una
ligera degradación del rendimiento. No se puede establecer la seguridad en HPFS con
Windows NT.
• HPFS solo es compatible con las versiones 3.1, 3.5 y 3.51 de Windows NT. Windows NT
4.0 no puede tener acceso a particiones HPFS.
• Fragmentación externa. Depende del tamaño del archivo de los usuarios y de su
disposición en las bandas.
Desde el punto de vista de un usuario, NTFS sigue organizando los archivos en directorios que, al
igual que ocurre en HPFS, se ordenan. Sin embargo, a diferencia de FAT o de HPFS, no hay
ningún objeto "especial" en el disco y no hay ninguna dependencia del hardware subyacente, como
los sectores de 512 bytes. Además, no hay ninguna ubicación especial en el disco, como las tablas
de FAT o los superbloques de HPFS.
mantienen varias copias (el número depende del tamaño del volumen) de la tabla maestra de
archivos. De manera similar a las versiones OS/2 de HPFS, NTFS admite revisiones.
Mayor funcionalidad Uno de los principales objetivos de diseño de Windows NT en cada nivel es
proporcionar una plataforma a la que se pueda agregar e integrar funciones, y NTFS no es ninguna
excepción. NTFS proporciona una plataforma enriquecida y flexible que pueden utilizar otros
sistemas de archivos. Además, NTFS es totalmente compatible con el modelo de seguridad de
Windows NT y admite varias secuencias de datos. Ya no es un archivo de datos en una única
secuencia de datos. Por último, en NTFS un usuario puede agregar a un archivo sus propios
atributos definidos por él mismo.
Compatibilidad con POSIX NTFS es el sistema de archivos compatible que mejor se adhiere a
POSIX, ya que cumple los requisitos siguientes de POSIX.:
Es un sistema adecuado para las particiones de gran tamaño requeridas en estaciones de trabajo
de alto rendimiento y servidores puede manejar volúmenes de, teóricamente, hasta 264–1
clústeres. En la práctica, el máximo volumen NTFS soportado es de 232–1 clústeres
(aproximadamente 16 TiB usando clústeres de 4 KiB).
Hay tres versiones de NTFS: v1.2 en NT 3.51, NT 4, v3.0 en Windows 2000 y v3.1 en Windows
XP, Windows 2003 Server, Windows Vista y v5.1 en Windows 2008. Estas versiones reciben en
ocasiones las denominaciones v4.0, v5.0, v5.1, v 5.2, y v 6.0 en relación con la versión de
Windows en la que fueron incluidas
• Sector de arranque. Esta zona no ocupa generalmente un único sector sino varios. Contiene
información sobre la disposición del volumen así como de las diferentes estructuras que
forman el sistema de archivos. También contiene información para el arranque del sistema.
• Master File Table (MFT). Se trata de una tabla, tal y como su nombre indica, que contiene
información de todos los archivos y directorios del sistema.
• Archivos de sistema. Los archivos del sistema contienen estructuras útiles para la gestión del
sistema de archivos, así como para la recuperación del mismo en caso de fallida.
• Zona de datos. Zona para la ubicación de los diferentes archivos de datos.
Master File Table (MFT) La tabla MFT está organizada en registros que contienen información de
todos los archivos del volumen. El tamaño de un registro es de 1 KB. La tabla MFT se basa en el
concepto de tabla de una base de datos relacional. Cada registro contiene información de un
archivo, incluyendo la tabla MFT que es tratada como un archivo más. De este modo se consigue
que la tabla sea de tamaño variable.
Límites
32
Máximo número de 4.294.967.295 (2 –1)
archivos
Tamaño máximo del 256 TiB con la actual implementación (16 EiBsegún su arquitectura)
volumen
1
Caracteres permitidos en Cualquier carácter excepto '\0' (NULO) y '/'
nombres de archivo
Windows también excluye el uso de \: * ? " < > |
Funcionamiento
Todo lo que tiene que ver con los archivos se almacena en forma de metadatos. Esto permitió una
fácil ampliación de características durante el desarrollo de Windows NT. Un ejemplo lo hallamos en
la inclusión de campos de indizado añadidos para posibilitar el funcionamiento de Active Directory.
Estructuras
Se emplea un registro transaccional (journal) para garantizar la integridad del sistema de archivos
(pero no la de cada archivo). Los sistemas que emplean NTFS han demostrado tener una
estabilidad mejorada, que resultaba un requisito ineludible considerando la naturaleza inestable de
las versiones más antiguas de Windows NT. Sin embargo, a pesar de lo descrito anteriormente,
este sistema de archivos posee un funcionamiento prácticamente secreto, ya que Microsoft no ha
liberado su código como hizo con FAT.
Gracias a la ingeniería inversa, aplicada sobre el sistema de archivos, se desarrollaron
controladores como el NTFS-3G que actualmente proveen a sistemas
operativos GNU/Linux, Solaris, MacOS X o BSD, entre otros, de soporte completo de lectura y
escritura en particiones NTFS.
El procedimiento que lleva a cabo NTFS cuando se quiere almacenar un archivo o un directorio es
el siguiente. Se pueden dar dos casos.
• Si se quiere almacenar un archivo en el que sus atributos son de poco tamaño, se coloca
automáticamente en un registro MFT. Es importante recordar que los archivos tienen como
atributo a su contenido. Los atributos que son guardados directamente en un registro MFT son
denominados atributos residentes.
• Si, por el contrario, el tamaño de los atributos de un archivo supera la capacidad de un registro,
los atributos son almacenados en clústeres de datos contiguos de la zona de datos. En este
caso, el registro MFT contiene referencias a dichos clústeres. El registro también contiene un
identificador denominado número de clúster virtual. Este identificador da información sobre el
primer clúster que ocupa el archivo así como el número de clústeres que ocupa. Dado que los
clústeres que están contiguos no tendremos que realizar consultas de la ubicación del
siguiente clúster del archivo.
Se podría dar la posibilidad de que el número de referencias a los clústeres de un archivo también
fuera elevado. Éstas serían almacenadas también en la zona de datos, y se mantendría en el
registro MFT una referencia al bloque que las contiene. En general, los atributos que son
guardados en la zona de datos se denominan atributos no residentes.
ReFS (Resilient File System, originalmente con nombre en código «Protogon») es un nuevo
sistema de archivos en Windows Server 2012 inicialmente previsto para servidores de archivos que
mejora en NTFS. El sistema presenta limitaciones frente a su predecesor, como se detalla más
adelante, pero también novedades en varios campos.
Los clientes de Windows desean disponer de una plataforma rentable que maximice la
disponibilidad de los datos, que escale de manera eficiente a conjuntos de datos de gran tamaño
en diversas cargas de trabajo y que garantice la integridad de los datos por medio de la resistencia
a los daños (independientemente de los errores de software o hardware). ReFS es un nuevo
sistema de archivos que está diseñado para satisfacer estas necesidades de los clientes y, al
mismo tiempo, proporcionar una base para importantes innovaciones en el futuro. Mediante una
pila de almacenamiento integrada que incluye ReFS y la nueva característica de Espacios de
almacenamiento, los clientes ahora pueden implementar la plataforma más rentable para obtener
un acceso a los datos escalable y disponible utilizando almacenamiento.
La característica Espacios de almacenamiento protege los datos contra errores de disco parciales
y totales mediante la conservación de copias en varios discos. ReFS establece una interfaz con
Espacios de almacenamiento para reparar los daños de manera automática.
• Mantiene los más altos niveles posibles de disponibilidad y confiabilidad del sistema,
suponiendo que el almacenamiento subyacente puede ser, de forma inherente, poco confiable.
• Ofrece una arquitectura resistente a errores completa cuando se usa junto con Espacios de
almacenamiento para que estas dos características amplíen las funcionalidades y la
confiabilidad de la otra cuando se usan juntas.
• Mantiene la compatibilidad con las características de NTFS que se adoptan ampliamente y con
resultados óptimos, además de reemplazar las características que aportan un valor limitado.
Además, existe una nueva herramienta de línea de comandos Integrity.exe para administrar la
integridad y las directivas de limpieza de discos.
Aplicaciones prácticas
ReFS ofrece funcionalidades que ayudan a los clientes a almacenar y proteger los datos,
independientemente de la confiabilidad de la pila subyacente de hardware y software. Esto
minimiza el costo del almacenamiento y reduce los gastos de capital para las empresas. Las
siguientes son algunas de las aplicaciones prácticas:
• Servidor de archivos de uso general. El cliente implementa un servidor de archivos
conectado a una configuración de almacenamiento JBOD con unidades serie ATA (SATA)
o SCSI conectado en serie (SAS).
• Almacenamiento remoto consolidado de datos de aplicaciones. El cliente implementa un
clúster de servidor de archivos de dos nodos y escalabilidad horizontal con Espacios de
almacenamiento, en el cual el clúster usa una configuración de almacenamiento JBOD con
unidades SATA o SAS.
Funcionalidad importante
La funcionalidad importante que se incluye con ReFS se describe a continuación:
• Integridad: ReFS almacena los datos de modo que los protege contra muchos de los
errores comunes que normalmente ocasionan pérdida de datos. Cuando ReFS se usa
junto con un Espacio de almacenamiento reflejado, los daños detectados (tanto en los
metadatos como en los datos de usuario, cuando están habilitadas las secuencias de
integridad) se pueden reparar de forma automática mediante la copia alternativa
proporcionada por los Espacios de almacenamiento. En caso de que se produzca un error
del sistema, ReFS se recupera rápidamente del error sin que haya pérdida de datos de
usuario.
• Disponibilidad. ReFS prioriza la disponibilidad de los datos. Históricamente, los sistemas
de archivos a menudo son susceptibles a daños en los datos que requieren que el sistema
se desconecte para la reparación. Con ReFS, si se producen daños, el proceso de
reparación se localiza en el área del daño y se ejecuta en línea, por lo que no se requiere
tiempo de inactividad de los volúmenes. Pese a que no es algo habitual, si un volumen se
daña, o si el usuario decide no usar Espacios de almacenamiento reflejados, ReFS
implementa un rescate, una característica que elimina los datos dañados del espacio de
nombres en un volumen activo sin que los datos en estado óptimo se vean afectados por
los datos dañados que no se pueden reparar. Además, no hay chkdsk con ReFS.
• Escalabilidad. Dado que la cantidad y el tamaño de los datos que se almacenan en los
equipos sigue aumentando con rapidez, ReFS está diseñado para funcionar correctamente
con conjuntos de datos extremadamente grandes, petabytes y volúmenes aún mayores,
sin afectar al rendimiento. No obstante, las preocupaciones prácticas en torno a las
configuraciones del sistema (como la cantidad de memoria), los límites que imponen
diversos componentes del sistema y el tiempo que se necesita para rellenar los conjuntos
de datos o las horas de copia de seguridad pueden definir limitaciones prácticas. El
formato en disco de ReFS está diseñado para admitir tamaños de volúmenes de hasta
2^78 bytes usando tamaños de clúster de 16 KB, mientras que el direccionamiento de la
pila de Windows permite 2^64 bytes. Este formato también admite tamaños de archivo de
2^64-1 bytes, 2^64 archivos en un directorio y la misma cantidad de directorios en un
volumen.
• Identificación proactiva de errores. Las funcionalidades de integridad de ReFS las
aprovecha un escáner de integridad, cuyo proceso se conoce como limpieza. La utilidad de
limpieza examina de forma periódica el volumen e intenta identificar los daños latentes y
luego desencadena automáticamente una reparación de los datos dañados.
Principales novedades
• Mejora de la fiabilidad de las estructuras en disco. ReFS utiliza árboles B+ para todas
las estructuras en disco incluyendo metadatos y los datos de los archivos. El tamaño de
archivo, el tamaño total de volumen, el número de archivos en un directorio y el número de
directorios en un volumen están limitados a números de 64 bits, lo que se traduce en un
tamaño máximo de archivo de 16 exbibytes, un tamaño máximo de volumen de 1 yobibyte
(con clústeres de 64 KiB), que permite gran escalabilidad prácticamente sin límites en el
tamaño de archivos y directorios (las restricciones de hardware siguen aplicando). Los
metadatos y los archivos son organizados en tablas, de manera similar a una base de
datos relacional. El espacio libre se cuenta mediante un asignador jerárquico que
comprende tres tablas separadas para trozos grandes, medianos y pequeños. Los
nombres de archivo y las rutas de acceso de archivo están limitados a una cadena de texto
Unicode de 32 KiB.
• Capacidad de resiliencia incorporada. ReFS emplea estrategia de actualización de
metadatos de asignación en escritura, que asigna los nuevos bloques para transacción de
actualización y utiliza lotes grandes de entrada y salida (IO). Todos los metadatos de ReFS
tienen sumas de verificación de 64 bits incorporadas, que son almacendas de forma
independiente. Los datos de los archivos opcionalmente pueden tener una suma de
verificación en una “corriente de integridad” separada, en cuyo caso la estrategia de
actualización de archivo también implementa asignación en escritura; esto es controlado
por un nuevo atributo “integridad” aplicable a archivos y directorios. Si los datos de archivo
o los metadatos resultaran dañados, el archivo puede ser eliminado sin tener que
desmontar el volumen por mantenimiento, y así restaurarlos desde una copia de seguridad.
Con la resiliencia incorporada, los administradores no necesitan ejecutar periódicamente
herramientas de comprobación de errores en el sistema de archivos (como CHKDSK) en
los volúmenes con sistemas de archivos ReFS.
• Compatibilidad con las APIs y tecnologías existentes. ReFS no requiere de nuevas
APIs de sistema y la mayoría de los filtros de sistema de archivos continuarán trabajando
con volúmenes ReFS. ReFS soporta muchas características existentes de Windows y
NTFS, como el cifrado BitLocker, Listas de Control de Acceso, diario USN, notificaciones
de cambio, enlaces simbólicos, puntos de unión, puntos de montaje, puntos de reanálisis,
instantáneas de volumen, IDs de archivo y oplock. ReFS se integra adecuadamente con
los «espacios de almacenamiento», una capa de virtualización de almacenamiento que
permite la realización de espejos de datos (mirroring), así como compartir las agrupaciones
de almacenamiento entre máquinas. Las características de resiliencia de ReFS mejora la
función de duplicación (mirroring) provista por los espacios de almacenamiento, y puede
detectar si las copias espejo de los archivos llegan a corromperse usando un proceso de
depuración de datos en segundo plano, que periódicamente lee todas las copias espejos y
verifica sus sumas de verificación, luego remplaza las copias dañadas por copias en buen
estado de los archivos implicados.
6.4.2.1. MINIX
Minix fue el primer sistema de archivos de Linux. Se origino con el sistema operativo Minix de ahí
su nombre. Fue escrito desde 0 por Andrew S. Tanenbaum en la década de los 80s, como un
sistema operativo tipo UNIX, donde su código fuente puede ser usado libremente para la
educación. El sistema de archivos MINIX fue diseñado para usarse en MINIX; copia la estructura
básica del Sistema de archivos UNIX (UFS), pero evita características complejas para mantener el
código fuente limpio, claro y simple, donde su objetivo total es ser de Minix una ayuda útil de
enseñanza.
Cuando Linus Torvalds comenzó a escribir el núcleo Linux en 1991, él trabajaba en una máquina
corriendo MINIX, así el lanzamiento inicial estuvo basado en las funcionalides de éste último
sistema operativo. Hasta que en abril de 1992 se realiza la introducción del Extended file system
(sistema de archivos extendido, conocido como ext). Este sistema de ficheros es aún usado por
algunas distribuciones GNU/Linux para arrancar discos y en otras situaciones, donde se necesite
un sistema de archivos simple y compacto.
El sistema de archivos extendido más comúnmente conocido como ext o EXTFS. El sistema de
archivos extendido (extended file system o ext), fue el primer sistema de archivos creado
específicamente para el sistema operativo Linux. Fue diseñado para vencer las limitaciones del
sistema de archivos MINIX. Fue reemplazado tanto por ext2 como xiafs, entre los cuales había una
competencia, que finalmente ganó ext2, debido a su viabilidad a largo plazo.
ext
Estructuras
ext2 "segundo sistema de archivos extendido" es un sistema de archivos para el kernel Linux.. La
principal desventaja de ext2 es que no implementa el registro por diario (en inglés Journaling) que
sí poseen sus posteriores versiones ext3 y ext4. ext2 fue el sistema de ficheros por defecto de las
distribuciones de Linux Red Hat, Fedora y Debian.
El sistema de archivos tiene una tabla donde se almacenan los i-nodos. Un i-nodo almacena
información del archivo (ruta o path, tamaño, ubicación física). En cuanto a la ubicación, es una
referencia a un sector del disco donde están todas y cada una de las referencias a los bloques del
archivo fragmentado. Estos bloques son de tamaño especificable cuando se crea el sistema de
archivos, desde los 512 bytes hasta los 4 KiB, lo cual asegura un buen aprovechamiento del
espacio libre con archivos pequeños. Los límites son un máximo de 2 terabytes de archivo, y de 4
para la partición.
ext2
Estructuras
Límites
18
Máximo número de archivos 10
ext3 "tercer sistema de archivos extendido" es un sistema de archivos con registro por diario
(journaling). Es el sistema de archivo más usado en distribuciones Linux. Es una extensión del
sistema de ficheros ext2. Este sistema de archivos está incluido en los kernels 2.4.x.
La principal diferencia con ext2 es el registro por diario. Un sistema de archivos ext3 puede ser
montado y usado como un sistema de archivos ext2. Otra diferencia importante es que ext3 utiliza
un árbol binario balanceado (árbol AVL) e incorpora el asignador de bloques de disco Orlov.
Ventajas
Tiene la ventaja de permitir actualizar de ext2 a ext3 sin perder los datos almacenados ni tener que
formatear el disco. Tiene un menor consumo de CPU y está considerado más seguro que otros
sistemas de ficheros en Linux dada su relativa sencillez y su mayor tiempo de prueba.
Límites de tamaño
Ext3 tiene dos límites de tamaño distintos. Uno para archivos y otro para el tamaño del sistema de
32
archivos entero. El límite del tamaño del sistema de archivos es de 2 bloques
Tamaño del bloque Tamaño máximo de los archivos Tamaño máximo del sistema de ficheros
1 KiB 16 GiB 2 TiB
2 KiB 256 GiB 8 TiB
4 KiB 2 TiB 16 TiB
8 KiB 2 TiB 32 TiB
Desventajas
Funcionalidad
Como ext3 está hecho para ser compatible con ext2, la mayoría de las estructuras del archivación
son similares a las del ext2. Por ello, ext3 carece de muchas características de los diseños más
recientes como las extensiones, la localización dinámica de los inodos, y la sublocalización de los
bloques. Hay un límite de 31998 subdirectorios por cada directorio, que se derivan de su límite de
32000 links por inodo. Ext3, como la mayoría de los sistemas de archivos actuales de Linux, no
puede ser chequeado por el fsck mientras el sistema de archivos está montado para la escritura. Si
se intenta chequear un sistema de ficheros que está montado puede detectar falsos errores donde
los datos no han sido volcados al disco todavía, y corromper el sistema de archivos al intentar
arreglar esos errores.
Fragmentación
No hay herramienta de desfragmentación online para ext3 que funcione en nivel del sistema de
archivos. Existe un desfragmentador offline para ext2, e2defrag, pero requiere que el sistema de
archivos ext3 sea reconvertido a ext2 antes de iniciarse. Además, dependiendo de los bits
encendidos en el sistema, e2defrag puede destruir datos.
Compresión
El soporte para la compresión está disponible como un parche no oficial para ext3. Este parche es
un aporte directo de e2compr pero necesita un mayor desarrollo ya que todavía no implementa el
journaling.
ext3
Sistemas operativos
Linux, BSD, Windows (a través de IFS)
compatibles
Estructuras
Límites
ext4 “cuarto sistema de archivos extendido” es un sistema de archivos transaccional (en inglés
journaling). El 25 de diciembre de 2008 se publicó el kernel Linux 2.6.28, que elimina ya la etiqueta
de "experimental" de código de ext4.
Mejoras
Extents
Los extents han sido introducidos para reemplazar al tradicional esquema de bloques usado por los
sistemas de archivos ext2/3. Un extent es un conjunto de bloques físicos contiguos, mejorando el
rendimiento al trabajar con ficheros de gran tamaño y reduciendo la fragmentación. Un extent
simple en ext4 es capaz de mapear hasta 128 MiB de espacio contiguo con un tamaño de bloque
igual a 4 KiB.
Journal checksumming
ext4 usa checksums en el registro para mejorar la fiabilidad, puesto que el journal es uno de los
ficheros más utilizados en el disco. Esta función tiene un efecto colateral beneficioso: permite de
forma segura evitar una lectura/escritura de disco durante el proceso de registro en el journal,
mejorando el rendimiento ligeramente. La técnica del journal checksumming está inspirada en la
investigación de la Universidad de Wisconsin en sistemas de archivos IRON (Sección 6, bajo el
nombre "checksums de transacciones").
Desfragmentación online
Incluso haciendo uso de diversas técnicas para evitar la fragmentación, un sistema de larga
duración tiende a fragmentarse con el tiempo. Ext4 dispondrá de una herramienta que permite
desfragmentar ficheros individuales o sistemas de ficheros enteros sin desmontar el disco.
En ext4, los grupos de bloques no asignados y secciones de la tabla de inodos están marcados
como tales. Esto permite a e2fsck saltárselos completamente en los chequeos y en gran medida
reduce el tiempo requerido para chequear un sistema de archivos del tamaño para el que ext4 está
preparado. Esta función está implementada desde la versión 2.6.24 del kernel Linux.
Asignador multibloque
Ext4 asigna múltiples bloques para un fichero en una sola operación, lo cual reduce la
fragmentación al intentar elegir bloques contiguos en el disco. El asignador multibloque está activo
cuando se usa 0_DIRECT o si la asignación retrasada está activa. Esto permite al fichero tener
diversos bloques "sucios" solicitados para escritura al mismo tiempo, a diferencia del actual
mecanismo del kernel de solicitud de envío de cada bloque al sistema de archivos de manera
separada para su asignación.
Timestamps mejorados
Puesto que los ordenadores se tornan en general cada vez más rápidos y que Linux está pasando
a ser cada vez más usado en aplicaciones críticas, la granularidad de los timestamps basados en
segundos se está volviendo insuficiente. Para resolver esto, ext4 tendrá timestamps medidos en
nanosegundos. Ésta función está actualmente implementada en la versión 2.6.23 del kernel.
ext4
Estructuras
Límites
Caracteres permitidos en
Todos los bytes excepto NULL y '/'
nombres de archivo
Tema VII
SISTEMAS DE ENTRADA/SALIDA
Las aplicaciones utilizan los dispositivos (devices) para realizar la E/S (entrada-salida). Estos
dispositivos son variados y trabajan de manera diferente: secuencialmente, random; transfieren
datos asincrónicamente o sincrónicamente; pueden ser de sólo lectura ( read only) o lectura-
escritura ( read-write), etc. El sistema operativo debe permitir que las aplicaciones puedan utilizar
esos dispositivos, proveyendo una interfaz que los presente de la manera mas simple posible. Los
dispositivos son una de las partes mas lentas de un sistema de computo. Por lo tanto, el SO, debe
manejar la situación como para salvar esa diferencia de velocidad.
Las principales funciones relacionadas son: Enviar comandos a los dispositivos, Detectar las
interrupciones, Controlar los errores y Proporcionar una interfaz entre los dispositivos y el resto del
sistema.
• Dispositivos por bloques. Almacena información en bloques de tamaño fijo, cada uno con su
propia dirección. Los tamaños de bloque comunes van desde 512 bytes hasta 32768 bytes. La
propiedad esencial de un dispositivo por bloques es que es posible leer o escribir cada bloque
con independencia de los demás. Los discos son los dispositivos por bloques más comunes.
• Dispositivos por caracteres. Suministra o acepta una corriente de caracteres, sin contemplar
ninguna estructura de bloques; no es direccionable y no tiene una operación de búsqueda. Las
impresoras, interfaces de red, ratones y casi todos los demás dispositivos que no se parecen a
los discos pueden considerarse como dispositivos por caracteres.
Algunos dispositivos no se ajustan a este esquema de clasificación, por ejemplo los relojes, que no
tienen direcciones por medio de bloques y no generan o aceptan flujos de caracteres. El sistema
de archivos solo trabaja con dispositivos de bloque abstractos, por lo que encarga la parte
dependiente del dispositivo a un software de menor nivel, el software manejador del dispositivo.
La tarjeta controladora casi siempre tiene un conector en el que puede insertarse un cable que
conduce al dispositivo. Muchos controladores pueden manejar dos, cuatro o incluso ocho
dispositivos idénticos. Si la interfaz entre el controlador y el dispositivo es de un tipo estándar, ya
sea una norma oficial como ANSI, IEEE o ISO, o una norma de facto, las compañías pueden
fabricar controladores y dispositivos que se ajustan a esa interfaz. Por ejemplo, muchas compañías
producen unidades de disco que se ajustan a las interfaces de controlador de disco IDE (Integrated
Drive Electronics) o SCSI (Small Computer System Interface).
Los modelos más frecuentes de comunicación entre la cpu y los controladores son para la mayoría
de las micro y mini computadoras el modelo de bus del sistema y para la mayoría de los
mainframes el modelo de varios buses y computadoras especializadas en E/S llamadas canales de
E/S.
La interfaz entre el controlador y el dispositivo suele ser de nivel muy bajo. Un disco, por ejemplo,
podría formatearse con 16 sectores de 512 bytes en cada pista. Sin embargo, lo que realmente
sale de la unidad es un flujo de bits en serie que comienza con un preámbulo seguido de los 4096
bits del sector y por último una suma de verificación, llamada también código para corrección de
errores (ECC: error-correcting code). El preámbulo se escribe cuando se da formato al disco y
contiene el número de cilindro y de sector, el tamaño de sector y datos similares, así como
información de sincronización.
La función del controlador consiste en convertir un flujo de bits a un bloque de bytes y realizar las
acciones de corrección de errores necesarias. Generalmente, primero se arma el bloque de bytes,
bit por bit, en un buffer dentro del controlador. Una vez que se ha cotejado su suma de verificación
y se le declara libre de errores, el bloque puede copiarse en la memoria principal.
Cada controlador tiene unos cuantos registros que sirven para comunicarse con la CPU. En
algunas computadoras estos registros forman parte del espacio de direcciones de la memoria
normal. Este esquema se denomina E/S mapeada en memoria.
Además de los puertos de E/S, muchos controladores usan interrupciones para indicarle a la CPU
cuándo están listos para que sus registros sean leídos o escritos. Una interrupción es, en primera
instancia, un suceso eléctrico. Una línea de petición de interrupción (IRQ) de hardware es una
entrada física del chip controlador de interrupciones. El número de tales entradas es limitado; las
PC de tipo Pentium sólo tienen 15 entradas disponibles para dispositivos de E/S. Algunos
controladores están alambrados físicamente en la tarjeta madre del sistema, como, por ejemplo, el
controlador del teclado en una PC. En el caso de un controlador que se enchufa en el plano
posterior, a veces pueden usarse interruptores o puentes de alambre en el controlador de
dispositivo para seleccionar la IRQ que usará el dispositivo, a fin de evitar conflictos (aunque en
algunas tarjetas, como Plug ‘n Play, las IRQ pueden establecerse en software). El chip controlador
de interrupciones establece una correspondencia entre cada entrada IRQ y un vector de
interrupción, que localiza la rutina de servicio de interrupción correspondiente.
Una vez que el controlador ha leído todo el bloque del dispositivo, lo ha colocado en su buffer y ha
calculado la suma de verificación, copia el primer byte o palabra en la memoria principal en la
dirección especificada por la dirección de memoria de DMA. Luego, el controlador incrementa la
dirección de DMA y decrementa la cuenta de DMA en el número de bytes que se acaban de
transferir. Este proceso se repite hasta que la cuenta de DMA es cero, y en ese momento el
controlador causa una interrupción. Cuando el sistema operativo inicia, no tiene que copiar el
bloque en la memoria; ya está ahí.
El proceso con almacenamiento intermedio de dos pasos tiene implicaciones importantes para el
rendimiento de E/S. Mientras los datos están siendo transferidos del controlador a la memoria, sea
por la CPU o por el controlador, el siguiente sector estará pasando bajo la cabeza del disco y los
bits estarán llega al controlador. Los controladores sencillos simplemente no pueden efectuar
entrada y salida al mismo tiempo, de modo que mientras se está realizando una transferencia a la
memoria el sector/que pasa bajo la cabeza del disco se pierde.
En consecuencia, el controlador sólo puede leer bloques de manera intercalada, es decir, uno sí y
uno no, de modo que la lectura de toda una pista requiere dos rotaciones completas, una para los
bloques pares y otra para los impares. Si el tiempo que toma transferir un bloque del controlador a
la memoria por el bus es más largo que el que toma leer un bloque del disco, puede ser necesario
leer un bloque y luego saltarse dos (o más) bloques. Saltarse bloques para dar al controlador
tiempo de transferir los datos a la memoria se denomina intercalación. Cuando se da formato al
disco, los bloques se numeran teniendo en cuenta el factor de intercalación. En la figura (a) hay un
disco con ocho bloques por pista y cero intercalación. En (b) el mismo disco con intercalación
sencilla. En (c) la intercalación doble.
El objetivo de numerar los bloques de este modo es permitir que el sistema operativo lea N bloques
numerados consecutivamente y aun así logre la máxima velocidad de que el hardware es capaz. Si
los bloques se numeraran como en (a) pero el controlador sólo pudiera leer bloques alternados, un
sistema operativo que se encargara de distribuir un archivo de ocho bloques en bloques de disco
consecutivos requeriría ocho rotaciones de disco para leer los bloques 0 al 7 en orden.
• Las capas inferiores se encarguen de ocultar las peculiaridades del hardware a las capas
superiores.
• Las capas superiores deben presentar una interfaz agradable, limpia y regular a los usuarios.
En la figura se resume el sistema de E/S, con todas las capas y las funciones principales de cada
capa. Comenzando por abajo, las capas son el hardware, los manejadores de interrupciones, los
controladores de dispositivos, el software independiente del dispositivo y por último los procesos de
usuario. Las flechas indican el flujo de control. Por ejemplo, cuando un proceso de usuario trata de
leer un bloque de un archivo, se invoca el sistema operativo para que ejecute la llamada. El
software independiente del dispositivo busca, por ejemplo, en el caché de bloques. Si el bloque
que se necesita no está ahí, ese software invoca el controlador de dispositivo para que emita la
petición al hardware. A continuación el proceso se bloquea hasta que se lleva a cabo la operación
de disco. Cuando el disco termina, el hardware genera una interrupción. Se ejecuta el manejador
de interrupciones para descubrir qué ha sucedido, es decir, cuál dispositivo debe atenderse en este
momento. El manejador extrae entonces el estado del dispositivo y despierta al proceso dormido
para que finalice la petición de E/S y permita al proceso de usuario continuar.
Una vez que se ha emitido el comando o comandos, se presentará una de dos situaciones. En
muchos casos el controlador en software debe esperar hasta que el controlador en hardware
realice cierto trabajo, así que se bloquea hasta que llega la interrupción para desbloquearlo. En
otros casos, sin embargo, la operación se lleva a cabo sin dilación, y el controlador no necesita
bloquearse. En el primer caso, el controlador bloqueado será despertado por la interrupción; en el
segundo, nunca se dormirá. De cualquier manera, una vez que se ha efectuado la operación el
controlador debe determinar si no ocurrieron errores. Si todo está bien, el controlador puede tener
datos que pasar al software independiente del dispositivo (el bloque que acaba de leerse). Por
último, el controlador devuelve información de estado para informar de errores a su invocador. Si
hay otras peticiones en cola, puede seleccionarse e inicia una de ellas. Si no hay nada en la cola,
el controlador se bloquea esperando la siguiente petición.
La función básica del software independiente del dispositivo es realizar las funciones de E/S
comunes a todos los dispositivos y presentar una interfaz uniforme al software de nivel de usuario.
Un aspecto importante de cualquier sistema operativo es cómo se nombran los objetos tales como
archivos y dispositivos de E/S. El software independiente del dispositivo se encarga de establecer
la correspondencia entre los nombres simbólicos de dispositivo y el controlador apropiado. En
UNIX un nombre de dispositivo, como /dev/tty00, especifica de manera única el nodo-i de un
archivo especial, y este nodo-i contiene el número principal del dispositivo, que sirve para localizar
el controlador apropiado.
El nodo-i también contiene el número secundario del dispositivo, que se pasa como parámetro al
controlador a fin de especificar la unidad que se leerá o escribirá.
El software independiente del dispositivo debe ocultar a los niveles superiores los diferentes
tamaños de sector de los distintos discos y proporcionar un tamaño uniforme de los bloques, por
ej.: considerar varios sectores físicos como un solo bloque lógico.
El almacenamiento intermedio también es una cuestión importante, tanto para los dispositivos por
bloques como para los de caracteres. En el primer caso, el hardware generalmente insiste en leer y
escribir bloques completos a la vez, pero los procesos de usuario están en libertad de leer y
escribir en unidades arbitrarias. Si un proceso de usuario escribe medio bloque, el sistema
operativo normalmente guardará los datos internamente hasta que se escriba el resto de los datos,
y en ese momento se podrá grabar el bloque en el disco. En el caso de los dispositivos por
caracteres, los usuarios podrían escribir los datos al sistema con mayor velocidad que aquella a la
que pueden salir, lo que requeriría almacenamiento intermedio (buffers). De igual manera, la
entrada del teclado que llega antes de que sea necesaria también requiere buffers.
Cuando se crea un archivo y se llena con datos, es preciso asignar nuevos bloques de disco al
archivo. Para poder realizar esta asignación, el sistema operativo necesita una lista o un mapa de
bits de los bloques libres del disco, pero el algoritmo para localizar un bloque libre es independiente
del dispositivo y se puede efectuar en un nivel más alto que el del manejador.
El manejo de errores generalmente lo realizan los controladores. La mayor parte de los errores son
altamente dependientes del dispositivo, de modo que sólo el controlador sabe qué debe hacerse
(p. ej., reintentar, ignorar, situación de pánico). Un error típico es el causado por un bloque de disco
que se dañó y ya no puede leerse. Después de que el controlador ha tratado de leer el bloque
cierto número de veces, se da por vencido e informa de ello al software independiente del
dispositivo. La forma como el error se trata de aquí en adelante es independiente del dispositivo. Si
el error ocurrió mientras se estaba leyendo un archivo de usuario, puede ser suficiente informar del
error al invocador. Sin embargo, si el error ocurrió durante la lectura de una estructura de datos
crítica del sistema, como el bloque que contiene el mapa de bits que indica cuáles bloques están
libres, puede ser que el sistema operativo no tenga más opción que imprimir un mensaje de error y
terminar.
mundo que se comunican empleando muchas redes de computadoras. Si se desea enviar correo a
alguien, se invoca un programa como send, que acepta la carta que se desea enviar y la deposita
en un directorio de spool para ser transmitida posteriormente. Todo el sistema de correo se ejecuta
fuera del sistema operativo.
7.3 Discos
Las siguientes son las principales ventajas con respecto del uso de la memoria principal como
almacenamiento:
• Mucha mayor capacidad de espacio de almacenamiento.
• Menor precio por bit.
• La información no se pierde al apagar la computadora.
Un uso inapropiado de los discos puede generar ineficiencia, en especial en sistemas con
multiprogramación.
Los discos duros modernos de gran capacidad también tienen más sectores por pista en las pistas
exteriores que en las interiores. Éstas son las unidades IDE (Integrated Drive Electronics), y el
complejo procesamiento que los circuitos incorporados en la unidad realizan enmascara los
detalles. Para el sistema operativo, estas unidades aparentan tener una geometría sencilla con un
número constante de sectores por pista. Los circuitos de la unidad y del controlador en hardware
son tan importantes como el equipo mecánico. El principal elemento de la tarjeta controladora que
se instala en el plano posterior de la computadora es un circuito integrado especializado, en
realidad una microcomputadora pequeña. En el caso de un disco duro puede ser que los circuitos
de la tarjeta controladora sean más sencillos que para un disco flexible, pero esto es así porque la
unidad de disco duro en sí tiene un potente controlador electrónico incorporado. Una característica
del dispositivo que tiene implicaciones importantes para el controlador del disco en software es la
1. El tiempo de búsqueda (el tiempo que toma mover el brazo al cilindro correcto).
2. El retraso rotacional (el tiempo que tarda el sector correcto en girar hasta quedar bajo la
cabeza).
3. El tiempo real de transferencia de datos.
En casi todos los discos, el tiempo de búsqueda es mucho mayor que los otros dos, así que si
reducimos el tiempo de búsqueda mejoraremos sustancialmente el rendimiento del sistema.
Los dispositivos de disco son propensos a errores. Siempre se graba junto con los datos de cada
sector de un disco algún tipo de verificación de errores, una suma de verificación o una verificación
de redundancia cíclica. Incluso las direcciones registradas cuando se formatea un disco cuentan
con datos de verificación. El controlador en hardware de un disco flexible puede informar cuando
se detecta un error, pero el software debe decidir qué se hará al respecto. Los controladores en
hardware de los discos duros con frecuencia asumen gran parte de esta carga. Sobre todo en el
caso de los discos duros, el tiempo de transferencia de sectores consecutivos dentro de la misma
pista puede ser muy rápido. Por ello, la lectura de más datos de los que se solicitan y su
almacenamiento en un caché de la memoria puede ser una estrategia muy eficaz para acelerar el
acceso a disco.
Planificación FCFS First come - first served (Primero en Llegar, Primero en Ser Servido)
Si el controlador en software del disco acepta peticiones una por una y las atiende en ese orden,
es decir, el primero que llega, el primero que se atiende, poco puede hacerse por optimar el tiempo
de búsqueda. Sin embargo, cuando el disco está sometido a una carga pesada puede usarse otra
estrategia. Es probable que, mientras el brazo está realizando una búsqueda para atender una
petición, otros procesos generen otras peticiones de disco. Muchos controladores de disco
mantienen una tabla, indizada por número de cilindro, con todas las peticiones pendientes para
cada cilindro encadenadas en listas enlazadas cuyas cabezas son las entradas de la tabla. Dado
este tipo de estructura de datos, podemos utilizar un mejor algoritmo que el del primero que llega,
primero que se atiende. Para entender este algoritmo, consideremos un disco de 40 cilindros.
Llega una petición para leer un bloque que está en el cilindro 11. Mientras se está realizando la
búsqueda del cilindro 11, llegan peticiones nuevas para los cilindros 1, 36, 16, 34, 9 y 12, en ese
orden, y se introducen en la tabla de peticiones pendientes, con una lista enlazada individual para
cada cilindro.
Cuando se termina de atender la petición en curso (para el cilindro 11), el controlador de disco
puede escoger la petición que atenderá a continuación. Si el controlador usara FCFS, iría después
al cilindro 1, luego al 36, y así sucesivamente. Este algoritmo requeriría movimientos del brazo de
10, 35, 20, 18, 25 y 3, respectivamente, para un total de 111 cilindros.
Planificación SCAN
Los edificios altos también tienen que enfrentar el trueque del algoritmo anterior. El problema de
planificar un elevador de un edificio alto es similar al de planificar un brazo de disco.
Continuamente llegan llamadas que reclaman al elevador que se dirija a otros pisos al azar. El
microprocesador que controla el elevador fácilmente podría usar FCFS para seguir la pista a la
secuencia en que los clientes oprimen el botón de llamada y atenderlos; también podría usar SSF.
Sin embargo, la mayor parte de los elevadores usan un algoritmo distinto para conciliar los
objetivos en conflicto de eficiencia y equitatividad: continúan desplazándose en la misma dirección
hasta que no hay más peticiones pendientes en esa dirección, y luego se mueven en la dirección
opuesta.
El algoritmo, conocido como algoritmo del elevador, requiere que el software mantenga un bit: el
bit de dirección actual, UP o DOWN. Cuando termina de atenderse una petición el controlador del
disco o del elevador examina el bit. Si éste es UP, el brazo o el elevador se mueve a la petición
pendiente más cercana hacia arriba. Si no hay peticiones pendientes en posiciones más altas, se
invierte el bit de dirección. Si el bit está en DOWN, el movimiento es hacia la siguiente posición
solicitada hacia abajo, si la hay. La siguiente figura muestra el algoritmo del elevador usando las
mismas siete peticiones anteriores, suponiendo que el bit de dirección inicialmente estaba en UP.
El orden en que se atienden los cilindros es 12, 16, 34, 36, 9 y 1, que produce movimientos del
brazo de 1, 4, 18, 2, 27 y 8, para un total de 60 cilindros. En este caso el algoritmo del elevador es
un poco mejor que SSF, aunque usualmente es peor.
Una propiedad agradable del algoritmo del elevador es que, dada cualquier colección de
peticiones, el límite superior del movimiento total está fijo: no puede ser mayor que dos veces el
número de cilindros.
Generalmente, las mejoras tecnológicas de los discos, acortan los tiempos de búsqueda (seek),
pero no acortan los tiempos de demora rotacional (search). En algunos discos, el tiempo promedio
de búsqueda ya es menor que el retraso rotacional. El factor dominante será el retraso rotacional,
por lo tanto, los algoritmos que optimizan los tiempos de búsqueda (como el algoritmo del
elevador) perderán importancia frente a los algoritmos que optimicen el retraso rotacional. Una
tecnología importante es la que permite el trabajo conjunto de varios discos. Una configuración
interesante es la de treinta y ocho (38) unidades ejecutándose en paralelo. Cuando se realiza una
operación de lectura, ingresan a la cpu 38 bit a la vez, uno por cada unidad. Los 38 bits conforman
una palabra de 32 bits junto con 6 bits para verificación. Los bits 1, 2, 4, 8, 16 y 32 se utilizan como
bits de paridad. La palabra de 38 bits se puede codificar mediante el código Hamming, que es un
código corrector de errores. Si una unidad sale de servicio, se pierde un bit de cada palabra y el
sistema puede continuar trabajando; se debe a que los códigos Hamming se pueden recuperar de
un bit perdido. Este diseño se conoce como RAID; siglas en inglés de “arreglo redundante de
discos no costosos”.
Si se tiene en cuenta que el disco duro está constantemente girando, junto a que el cabezal debe
estar alineado sobre un área concreta del disco para la lectura o escritura del mismo, el tiempo de
acceso no es inmediato. Esta situación se ve perjudicada por los sistemas de ahorro de energía,
que reducen la velocidad del disco, o incluso pueden llegar a pararlos. Este es el motivo por el que
los discos de mayores revoluciones tienen tasas de lectura, escritura y tiempo de acceso más
rápidas. Además, para aumentar este incremento de rendimiento se busca utilizar platos más
pequeños, y memoria caché más grande y rápida. En cualquier caso, el tiempo de acceso de los
discos duros, que suele medirse en milisegundos, es claramente más elevado que el del
procesador.
Dadas unas limitaciones físicas imposibles de superar (incluso ahora) por esta tecnología, lo cierto
es que siempre que se requiera de partes móviles para su funcionamiento no es posible conseguir
mejores prestaciones que las que ya se han conseguido.
Y es aquí cuando la memoria NAND hace su aparición. Esta memoria basa su estructura en
transistores de puerta flotante (o transistores floating-gate). La diferencia entre este tipo de
transistores y los que usan la memoria DRAM, es que estos últimos deben tener una carga
eléctrica con una frecuencia de refresco constante para mantener los datos almacenados. Este es
el motivo por el que la memoria RAM de nuestro computador se vacía al apagarlo.
La memoria NAND está diseñada para mantener su estado de carga aun cuando no está
recibiendo corriente eléctrica, con lo que se consigue mantener la información. Por lo tanto, es un
tipo de memoria no volátil, al igual que lo era la que se podría decir que es su precursora, la
EEPROM.
El funcionamiento de la memoria NAND tiene sus particularidades en el diseño de cada celda de
memoria. Los electrones son almacenados en el puente flotante, de forma que toma una lectura de
0 cuando está cargado, o 1 si está vacío. Son unos valores opuestos a lo que se suelen utilizar.
La memoria NAND está organizada como una matriz. Si bien la matriz completa se entiende como
un bloque, las filas que componen esta son referidas como páginas. Lo normal es que las páginas
tengan tamaños que varían entre los 2K y 16K, con unas 256 páginas por bloque, de forma que el
tamaño de estos varía entre los 256KB y los 4 MB.
La mayor ventaja de los SSD con los HDD reside en la ausencia de partes móviles, lo que les
permite obtener unas velocidades que son inalcanzables por los discos duros.
Para entender qué es el TRIM, se puede hablar de cómo borra datos un SSD. Si bien se sabe que
escribir y leer datos de un SSD es un proceso muy rápido, no lo es tanto el hecho de reescribir
sobre una celda ya escrita.
Mientras que un SSD puede escribir en una fila, solo puede borrar a nivel de bloque, sin poder
determinar el contenido útil. La única manera que tiene para eliminar el contenido de una página
concreta es copiar el contenido de las filas útiles en memoria, borrar el bloque y volver a escribir
los contenidos del bloque antiguo en el nuevo. Este proceso es conocido como Gargabe Collection.
En caso que el disco esté lleno, el SSD debe escanear en busca de bloques que estén marcados
para su borrado, y entonces borrarlos y escribir el contenido. Este es el motivo por el que los
discos SSD se degradan conforme pasa el tiempo y realizamos diferentes escrituras.
TRIM es una tecnología que establece una intercomunicación entre el sistema operativo y el
controlador del SSD para decirle que bloques han sido borrados. Hay que tener en cuenta que
cuando borramos un archivo en nuestro sistema operativo, el sistema operativo lo que hace es
marcar los bloques como no usados, pero esto no quiere decir que estén borrados de la unidad.
Para hacer esto, es el sistema operativo el que le dice al SSD cuáles son los bloques de debe
borrar.
Como es una tecnología dependiente del sistema operativo, es este el que debe integrar esta
característica. En el caso de Microsoft este lleva integrado desde Windows 7, mientras que Apple
lo incluyo a partir de Snow Leopard.
El controlador
Si un SSD fuera una persona, el controlador sería el cerebro. Es el verdadero artífice de la gestión
de los archivos, y la velocidad con la que estos son almacenados. A nivel técnico no dista en
exceso de lo que es un propio ordenador, ya que cuenta con una interfaz de entrada, un
procesador, memoria caché, además de memoria ram de tipo DDR2 o DDR3 para manejar la
NAND.
Algunos modelos utilizan sus propios algoritmos de compresión para que el número de escrituras
sea menor y así prolongar la esperanza de vida de los mismos, compensando la teórica debilidad
de las memorias MLC o TLC.
Si bien existen fabricantes independientes como marvell o sandforce que realizan los controladores
para que después los fabricantes los integren en sus propios diseños, hoy en día la tendencia es
que sea el fabricante el que realice su propio controlador.
Formatos y protocolos
En un principio es cierto que podíamos encontrar primigenios SSD funcionando sobre interfaces
IDE, pero no fue hasta la llegada de los discos sata donde se popularizó el uso de los SSD. Para
ser más concretos, fue el protocolo SATA 2 el que abrió la puerta a los SSD para usuarios, que con
una velocidad máxima de hasta 300 MB/s, sólo estos eran capaces de alcanzar tales velocidades,
sumado al tiempo de acceso infinitamente más rápido, fueron acogidos como el futuro de la
informática.
I
Posteriormente surgieron el SATA 3 que duplico la tasa de transferencia hasta 600 MB/s, y los
SSD han seguido llegando al límite que ofrecía el protocolo, haciendo la diferencia con los discos
duros magnéticos más y más grande.
Parece que es cuestión de pocos años para que el SSD conquiste el mercado del
almacenamiento en los ordenadores. Aunque aún están lejos de alcanzar los tamaños de los
discos magnéticos, estos cada vez ofrecen precios más competitivos, donde en apenas pocos
años han pasado de soñar por un precio por debajo de 1 gigabyte por un euro a conseguir casi 4
por el mismo dinero.
La duda surge con la utilización de la NAND. Su funcionamiento sigue siendo efectivo, y el
rendimiento que son capaces de ofrecer es realmente espectacular en comparación con los discos
magnéticos, hasta el punto que según el uso al que destinemos nuestro SSD, no apreciaremos una
gran diferencia de rendimiento en el día a día con un SSD con protocolo NVMe que con un modelo
SATA de hace unos años.
Pero es cierto que nuevas tecnologías están por venir como la ya presente 3D NAND, o la
memoria de cambio de fase recientemente presentada por IBM pueden ser hitos que cambien la
concepción que tenemos de los ordenadores. Pero hasta entonces, comprar un SSD es una
garantía de tener un rendimiento superior y una experiencia de uso que poco tiene que ver
respecto a un disco magnético.
Cuando se mira la cara brillante de un CD, uno se pregunta cómo se almacenan las cadenas de
bits sobre él y, en el siguiente nivel, cómo se combinan para formar bloques lógicos. Además, por
encima, se encuentra el sistema de archivos que agrupa los bloques en archivos y escribe y
mantiene la información sobre los archivos almacenados en directorios.
La base de partida de todo esto es el llamado Red Book, publicado en 1982 por los inventores del
CD, Sony y Phillips, y que describe el formato de los CD de audio en todas sus facetas. A partir de
este formato se han desarrollado otros que, por no ser menos, se han escrito en otros tantos libros
de colores. El Yellow Book con el formato de los CD-ROM de datos, el Green Book con el formato
CD-I y el Orange Book con el formato para los CD grabables y los Photo-CD. Todos ellos se basan
en el Red Book y en el formato de sector desarrollado por este, aunque con algunas pequeñas
diferencias.
El formato físico
La descripción de un CD comienza necesariamente con el formato físico, idéntico para todo tipo de
CD. El diámetro de estos discos es de 12 cm y su espesor es de 1,2 mm. El agujero que hay en
medio del CD tiene un diámetro de 15 mm. El CD tiene una capa metálica reflectante recubierta
por una capa protectora a base de barniz transparente.
La información a almacenar se graba sobre la capa metálica en forma de los llamados pits y lands,
que son pequeñas protuberancias y cavidades que representan los diferentes bits. Los pits y lands
se alinean a los largo de una única espiral que va desde dentro hacia fuera y cubre todo el CD.
Dado que los pits tienen una anchura de sólo 0,6 µm (un µm corresponde a una millonésima de
metro), las diferentes vueltas de esta espiral están separadas únicamente 1,6 µm. La densidad de
un CD alcanza casi las 16.000 pistas por pulgada (tracks per inch TPI).
CAV y CLV
En el almacenamiento de datos sobre medios giratorios se diferencian dos procesos cuyos
nombres son CAV y CLV, ambos se refieren a la velocidad de rotación del medio de
almacenamiento.
• CAV: Constant Angular Velocity
• CLV Constant Linear Velocity
Los discos duros y disketes que están divididos en pistas y sectores, trabajan bajo el principio
CAV. Este se basa en una velocidad angular constante (es decir, el mismo número de vueltas por
unidad de tiempo). Independientemente de dónde se encuentre la cabeza de lectura y escritura, el
medio gira siempre con una velocidad constante. Por tanto, si la cabeza se encuentra sobre una
pista de la zona interior, escribirá una pista más corta que la que escribiría de encontrarse en la
zona exterior. Esto lo utilizan los modernos discos duros empaquetando más sectores en las pistas
exteriores. En comparación con el procedimiento CLV, lo determinante del procedimiento CAV es
que la velocidad de rotación del medio no varía, independientemente de dónde se encuentre la
cabeza de lectura y escritura. En cambio, en el procedimiento CLV, que es el que utiliza la
tecnología CD, sucede exactamente lo contrario. En este caso el cabezal de escritura recorre
exactamente la misma distancia por unidad de tiempo independientemente de si se encuentra en el
margen interior o en el margen exterior del CD. Para ello, la velocidad de rotación debe ajustarse
continuamente a la posición actual del cabezal (Velocidad de rotación es lo mismo que velocidad
angular).
De todas maneras, la conversión vía tabla EFM no contempla un problema: la separación de bits
unitarios. Cuando por ejemplo un primer byte con un channel 1 y con ello el cambio de pit a land (o
al revés) acaban, el siguiente Byte no puede empezar de nuevo con el mismo tipo de cambio
puesto que en medio no hay ningún espacio. Por este motivo, a cada Byte con sus 14 channel bit
se le añaden tres channel bit más que se denominan merging bit. Estos separan un byte de otro y
con ello elevan el número de channel bit a 17 por byte.
Formato CD-DA
De los bytes, codificados en forma de 17 channel bit, se obtiene el bloque de información
coherente más pequeño de un CD, lo que se denomina como frame. Vamos a ver el formato
original de los CD DA (Digital Audio) en el que se basan todos los de audio (Un frame contiene 24
bytes, cada uno con 17 channel bit, que junto con alguna otra información, constituyen el frame
como bloque de datos) :
• El inicio del frame está formado por lo que se denomina Sync-Pattern, un diseño concreto de
en total 27 channel bit, que indica a la unidad el comienzo de un nuevo frame.
• A continuación se encuentran los 24 Bytes de datos del frame.
• Un frame acaba con 8 bytes de corrección de errores que a su vez están también constituidos
por 17 channel bit.
Así, de esta manera se llega a un total de 588 channel bit por frame.
Sectores
Un sector lo forman 98 frames, donde por un lado se juntan los distintos Bytes de datos de los
frames y por otro los Bytes de control y los Bytes para la corrección de errores. De esta manera se
obtiene un sector, que en total está constituido por 3234 Bytes, de los cuales 2358 Bytes están
disponibles como Bytes de datos útiles mientras que los restantes 882 Bytes se componen de los
datos para la corrección de errores y de 98 Bytes de control.
Capacidad de almacenamiento
Del número de sectores se obtiene la capacidad total de un CD-ROM, hay varios números en
circulación que van desde los 640 a los 700 MB, y que depende de si se utiliza o no toda la
superficie grabable del CD-ROM. Al principio, los dispositivos tenían problemas para trabajar en los
5 mm exteriores del CD-ROM, y por eso no se utilizaban. La capacidad se limitó por tanto a 550
MB. Con el tiempo se llegó a poder utilizar la anchura total del CD con lo que se pudo alcanzar la
máxima capacidad de un CD-ROM, 682MB.
Formato de CD-ROM
El formato según el Yellow Book a nivel de sectores sólo se diferencia del formato CD-DA en la
zona de datos. para disminuir el número de errores, el formato del Yellow Book almacena más
información para la corrección y detección de errores. La zona de datos se reduce, por este motivo
a 2048 Bytes (2 KBytes), lo cual es mucho mejor de manejar para los computadores que los 2352
Bytes del formato de los CD-DA. Como efecto adicional de incorporar más bytes para la corrección
de errores, la velocidad de transferencia de datos de una unidad aumenta.
El formato lógico
La base de todo medio de almacenamiento de datos la constituye siempre el formato físico del
soporte de datos, pero además, si se quiere acceder a los datos almacenados no en forma de
sectores sino como archivos y directorios, se precisa un formato lógico. Cada fabricante puede
asignar libremente el formato lógico que desee a sus CD-ROM, pero entonces se precisará
siempre del controlador apropiado para poder leer esos CD-ROM bajo un Sistema Operativo y, si
hablamos de la posibilidad de utilización de los CD bajo diferentes Sistemas Operativos, se
precisará un controlador específico por cada sistema operativo y cada tipo de formato de CD.
Por este motivo, en 1985, diferentes distribuidores de software y fabricantes de hardware
trabajaron conjuntamente obteniendo como fruto el formato HSG, vigente hoy en día para
computadores PC y también para muchos sistemas UNIX. Todos los CD-ROM que se insertan en
la unidad de CD están provistos de este formato. Las autoridades de normalización ISO
estandarizaron la propuesta bajo la norma ISO 9660.
Quien desee acceder a los títulos y archivos de un CD-ROM desde el Sistema Operativo pocas
veces entrará en contacto con todo este conjunto de conceptos, pues para ello los CD se han
transformado en un medio de almacenamiento de lo más normal, direccionable, como lo es un
disco duro. pero si lo que se pretende es acceder directamente al hardware del controlador de una
unidad CD-ROM para, por ejemplo, iniciar la reproducción de unas pistas de audio, tendrá que
conocer estos conceptos.
Sectores lógicos
Para no perderse en el nivel de los sectores físicos, el formato HSG define en primer lugar el sector
lógico. Éste, en cuanto a su tamaño está orientado a los sectores físicos del Yellow Book y
contiene 2048 Bytes, es decir 2KB. Cada sector posee un número inequívoco, el denominado
Logical Sector Number, abreviado LSN. El primer LSN direccionable es el número 0 y se
corresponde con el sector físico cuya dirección, según el Red Book, es 00:02:00. Es decir, los
primeros 150 sectores físicos que corresponden a los dos primeros segundos de un CD-DA no
pueden direccionarse desde el nivel de formato lógico.
Bloques lógicos
Para poder direccionar mejor los elementos de los sectores lógicos, la norma divide nuevamente el
sector lógico en varios bloques lógicos. Cada bloque lógico (LBN) puede tener un tamaño de 512
bytes, 1024 Bytes o 2048 Bytes lo cual, en el último caso, se corresponde con el tamaño del sector
lógico. Los LBN también se direccionan con números. El tamaño de bloque de 512 bytes es el que
mejor se presta para mostrar un ejemplo. En este caso, hay un 0 para el primer LBN del primer
LSN, un 1 para el segundo, un 2 para el tercero, un 3 para el cuarto, un 4 para el primero del
segundo LSN, y así sucesivamente.
Directorios y subdirectorios
Para la estructuración de los archivos almacenados, un CD contiene un directorio principal a partir
del cual se pueden declarar cuantos subdirectorios se desee que, a su vez, pueden contener
subdirectorios, obteniéndose una estructura de árbol, con la única limitación de que el número
máximo de niveles de directorios se restringe a 8. El directorio principal, así como los directorios
que cuelgan de él se almacenan como archivos. Estos archivos-directorios pueden por tanto
disponerse en el lugar que se desee entre los archivos del CD. Para que al buscar un archivo en
un directorio éste se pueda encontrar de manera más rápida, es recomendable no poner más de
40 archivos dentro del mismo directorio, puesto que este número de entradas de directorio caben
en un solo sector lógico y por tanto para encontrar un archivo determinado sólo es necesario
cargar el primer sector de un archivo de directorio.
Path Table
Guardar los directorios como si de archivos se tratase es un procedimiento tan sencillo como
elegante, pero no exento de inconvenientes. Sobretodo en la búsqueda de archivos en
subdirectorios de niveles profundos dentro de la estructura, pues se tienen que buscar y leer
demasiados archivos de directorios hasta que se acierta con el directorio que contiene el archivo
buscado. Por este motivo se construye una especie de abreviación de los subdirectorios que se
conoce como Path Table. En el Path Table se enumeran los nombres de todos los directorios y
subdirectorios de un CD juntamente con el número de sector lógico en que comienza cada uno de
ellos. Si se tiene esa tabla en la memoria, basta la lectura de un sector para averiguar la dirección
de un archivo.
Al igual que ocurre con los CD convencionales, no existe una compañía propietaria del DVD que se
encargue de establecer los sellos de homologación. Es un consorcio de varias empresas en donde
encontramos a Hitachi, JVC, Phillips, Pioneer, Sony, Time Warner, etc.
La incorporación masiva de los entornos gráficos y, sobre todo, de las aplicaciones multimedia, con
grandes cantidades de vídeo y audio hacen que los 650 MB de un CD-ROM se queden cortos. Por
otra parte, el soporte CD también se había incorporado al mundo del cine y a pesar de grabar las
Tipos de DVD
DVD-Audio
Hay que hacer una distinción entre DVD-Audio, DVD-Vídeo y DVD-ROM. Los primeros es posible
que no tengan demasiada difusión, pues un álbum seguirá teniendo la misma duración aunque el
soporte permita más. Tan sólo los dobles LP y las recopilaciones que ahora ocupan 10 discos se
verán beneficiadas por este soporte, pues en un solo disco podrá hacerse la colección completa e
incluso más amplia. No obstante, las compañías discográficas no tienen intención de utilizar el
DVD mientras no se garantice la imposibilidad de copiar los discos.
DVD-Vídeo
Los DVD de vídeo deben ser capaces de satisfacer los exigentes requisitos de Hollywood. En
primer lugar en cuanto a capacidad, pues sumando los requisitos de vídeo comprimido, varias
pistas de sonido, y de subtítulos, se obtiene que es necesario alrededor de medio Megabyte por
cada segundo. Considerando una duración de unos 135 minutos para las películas más largas, se
requiere una capacidad de unos 4 GB. Es decir, algo inferior a los 4,7 GB del DVD más sencillo.
Será posible, por tanto, grabar cualquier película en un solo disco, con compresión MPEG-2 y una
resolución de 720x480 (más del doble que la proporcionada por el sistema de vídeo VHS),
consiguiéndose calidad de estudio. Admite tres canales de sonido con calidad de CD o hasta 8
canales reduciendo la calidad. Además, se pueden incluir entre 4 y 32 canales de subtítulos para
mostrar la transcripción del sonido o comentarios sobre la película.
La elevada capacidad del DVD permite nuevas posibilidades en la distribución de vídeo. Por
ejemplo, se puede grabar una escena desde distintos ángulos, para que sea el usuario final el que
elija desde cuál quiere verlo. Por otra parte, estamos hablando de vídeo digital grabado en un
soporte de acceso aleatorio. Esto permite una interacción total, pudiendo saltar de una escena a
otra instantáneamente. El DVD permite dar el salto definitivo a la televisión de alta definición y al
formato 16:9, pues otra de las posibilidades es seleccionar este formato o el clásico 4:3. En cuanto
al sonido, no queda limitado a sonido estéreo, sino que se incorporan dos sistemas de codificación
con mayor número de altavoces: el Dolby AC3 o Dolby digital y el MPEG-2 Audio. En el AC3 se
utiliza un sistema 5:1, es decir, cinco canales de sonido más un canal de subwoofer. De los cinco
canales, tres se distribuyen en la parte delantera (izquierda, centro y derecha), y los dos restantes
en la parte posterior (izquierda y derecha) para crear el efecto surround. En el subwoofer no tiene
tanta importancia su colocación, aunque suele colocarse en el centro, ya sea delante o detrás.
Además, la salida de sonido AC3 es óptica, lo que elimina los posibles ruidos electromagnéticos. El
sistema MPEG-2 utiliza dos altavoces más, situados en la parte delantera entre los tres ya
comentados. Así, utiliza una configuración 7:1 que es compatible con la 5:1 del Dolby digital.
DVD-ROM
En el caso del DVD-ROM, están disponibles todas las posibilidades del DVD-Video, pues basta
con incorporar una tarjeta decodificadora MPEG-2 y el software apropiado, para poder ver las
películas grabadas en este formato. Además, hay que añadir las posibilidades de este soporte al
unirlo a un sistema informático, pues el hecho de que el vídeo este almacenado en forma digital,
nos permite su edición de forma sencilla. Como soporte de datos genéricos, nos encontramos con
un sistema de alta capacidad (por el momento) y reducidas dimensiones. La longitud de onda del
láser de lectura se ha reducido de 780 nm (infrarrojo) a 650 nm (rojo). Esto hace que los nuevos
láser no sean capaces de leer los discos CD-R, cuyo método de grabación se basa en variar las
propiedades reflectantes de una superficie de color (generalmente verdoso), precisamente debido
a este color.
El DVD más sencillo puede almacenar 133 minutos de vídeo digital, con tres canales de sonido
estéreo de calidad CD y 4 canales de subtítulos. Los discos de 17 GB alcanzan hasta 481 minutos
de vídeo con las mismas condiciones.
El Blu Ray no es otra cosa que un disco de almacenamiento óptico de 12 cm. de diámetro, el
mismo tamaño que el DVD o el CD, y que fue desarrollado por un consorcio llamado Blu-Ray Disc
Association con el fin de obtener un medio de almacenamiento capaz de contener la gran cantidad
de datos requeridos por las películas realizadas en la espectacular alta definición, además de otros
actores inherentes a la reducción de costes.
Este medio de almacenamiento puede contener hasta 50 Gb. de información, pero en la actualidad
se están desarrollando técnicas para elevar esta cantidad hasta casi 70 Gb.
Cabe destacar que el Blu-Ray es un soporte de una sola capa que puede contener 25 Gb de
información, que traducidos significan cerca de 6 horas de vídeo de alta definición más los audios
correspondientes. El soporte de más capacidad es el Blu Ray de doble capa, que sí puede
almacenar aproximadamente 50 GB.
Como mencionamos, este estándar de disco óptico fue desarrollado por la Blu-ray Disc Association
(BDA), pero se trabajó en conjunto con un grupo de empresas del ámbito electrónico, de la
informática y el entretenimiento como Sony, Apple, Samsung y Walt Disney Pictures, entre otras.
El Blu Ray dejó en el camino a sus principales contendientes como el DVD o el HD DVD, si bien el
primero todavía es un firme competidor, ya que ofrece una resolución de 720x480 en NTSC o
720x576 en PAL, apta para la reproducción en la mayoría de los equipamientos presentes en
hogares de todo el mundo, mientras que el formato HD DVD prácticamente ha desaparecido.
En cuanto a la calidad, Blu Ray, ofrece una calidad de visualización de alta definición, es decir de
1920x1080, también llamada 1080p, un salto increíblemente alto con respecto al DVD.
Esto permite un enfoque del haz del láser aproximadamente una quinta parte más pequeño que el
láser rojo, el que se usa para grabar discos DVD. Esta combinación permite grabaciones mucho
más pequeñas y una mayor densidad de puntos en los discos BD.
Asimismo, como la primera capa de datos está en la parte superior del disco, deja más espacio
libre debajo para otra capa adicional. Así, permite almacenar datos en 2 capas distintas (hasta 50
GB).
• Escritura estable y alta protección: en la fabricación del disco la capa superior se aplica
de forma precisa y uniforme. Así se evita que el haz láser sensible se desvíe durante la
lectura o la escritura. También asegura que la protección de la capa de grabación sea
uniforme.
• Capa protectora antirrozaduras: los discos Blu-ray están cubiertos por una capa superior
antirrozaduras con repelente de suciedad y polvo. Esta capa evita que el disco se manche
con huellas dactilares que impidan la correcta lectura del disco.
• Nueva capa de grabación resistente a la luz: la capa de grabación de los discos BD es
menos sensible a la luz ultravioleta. Está fabricada con un material especial distinto al
material de pigmentos utilizado en los discos DVD/CD.
• Fiabilidad de la sobrescritura: el nuevo material de la capa de grabación permite
reescribir hasta 10.000 veces sobre un disco BD-RE con buena calidad.
Blu-ray 3D
Una de las aplicaciones más impresionantes que se puede obtener del disco Blu Ray es la capacidad de
reproducir contenidos en 3D, una característica muy solicitada en su momento por los más importantes
desarrolladores de software, estudios y productoras de cine.
BIBLIOGRAFIA
PROBLEMAS RESUELTOS
Capítulo 2. Gestión de Procesos
Solución
a) FCFS
A
B
C
D
0
6
16
29
37
SJF
A
D
B
C
0
6
14
24
37
PRIORIDADES
A
B
D
C
0
6
16
24
37
b)
Solución
a) COLA D-A-D-B-C-F-A-E-D
D
A
D
B
C
F
A
E
D
0-‐1
5-‐6
10-‐11
15-‐16
20-‐21
25-‐26
30-‐31
35-‐36
40-‐41
45-‐46
B-C-F-A-E-D-B-C-E-B
COLA
B
C
F
A
E
D
B
C
E
B
46
50-‐51
55-‐56
57-‐58
59-‐60
64-‐65
69-‐70
74-‐75
77-‐78
81-‐82
84
b)
2.1.3. Se tienen que realizar 5 trabajos según la tabla siguiente. Despreciar el tiempo por cambio
de contexto. Se pide:
Se tienen 4 colas para ejecución Cola 0: RR quantum=5 ms, Cola 1: RR quantum=8 ms, Cola
2: RR quantum=12 ms, Cola 3: FCFS. Representar diagramas que ilustren el orden de
ejecución de estos trabajos y los tiempos de espera asociados
Solución
Round
Cola
0
A
B
C
D
E
A
Robin
0
5
10
15
20
25
30
Q=
5
Round
Cola
1
B
C
D
E
Robin
0
8
16
22
30
Q=
8
Round
Cola
2
B
E
Robin
0
12
24
Q=
12
Round
Cola
3
E
Robin
0
14
Q=
12
Tiempo de
Parcial Espera
A 0+20 20
B 5+0+0 5
C 10+8 18
D 15+16 31
E 20+22+12+0 54
3.1.1. En una tienda de pájaros tienen problemas para tener a todos sus canarios felices. Ellos
comparten una jaula donde hay solo un plato de alpiste y un columpio para ejercitarse.
Todos los canarios quieren inicialmente comer y luego ejercitarse, pero tienen el
inconveniente que solo 3 de ellos pueden comer del plato y solo 1 columpiarse. Definir un
proceso que ejecuten los canarios concurrentemente de forma que sincronicen sus
actividades usando semáforos
Solución
semaphore comida=1;
semaphore columpio=1;
int num=0, i =0;
void main()
{
cobegin
{
come(1); columpia(1); come(2); columpia(2); come(3);
columpia(3); come(4);columpia(4);
}
}
3.1.2. Considerar dos procesos. Alumno 1 y Alumno 2 y tres recursos disponibles, un libro de
“sistemas operativos”, un libro de “Bases de Datos” y una computadora, los procesos se
comportan de la siguiente manera:
Process Alumno1
begin
while true do
begin
/*toma el libro de SO */;
/*toma el libro de BD */;
/*utiliza la computadora */;
/*deja el libro de BD*/;
Solución
semaphore mutex=1;
semaphore libro_BD=1;
semaphore libro_SO=1;
semaphore compu=1;
void Alumno1()
{
int i;
for(i=1;i<10;i++) {
wait(mutex);
wait(libro_SO);
cout<<"Alumno 1 toma el libro de SO" << "\n";
wait(libro_BD);
cout<<"Alumno 1 toma el libro de BD" << "\n";
signal(mutex);
wait(compu);
cout<<"Alumno 1 utiliza la computadora" << "\n";
signal(libro_BD);
cout<<"Alumno 1 DEJA el libro de BD" << "\n";
signal(compu);
cout << "Alumno 1 DEJA la computadora" << "\n";
signal(libro_SO);
cout<<"Alumno 1 DEJA el libro de SO" << "\n";
}
}
void Alumno2()
{
int j;
for(j=1;j<10;j++) {
wait(mutex);
wait(libro_BD);
cout<<"Alumno 2 toma el libro de BD" <<"\n";
wait(libro_SO);
cout<<"Alumno 2 toma el libro de SO" <<"\n";
signal(mutex);
signal(libro_SO);
cout<<"Alumno 2 DEJA el libro de SO" <<"\n";
signal(libro_BD);
cout<<"Alumno 2 DEJA el libro de BD" <<"\n";
wait(compu);
cout<<"Alumno 2 utiliza la computadora" <<"\n";
signal(compu);
cout<<"Alumno 2 DEJA la computadora" <<"\n";
}
}
void main(){
cobegin{
Alumno1(); Alumno2();
}
}
3.1.3. Dado un consultorio médico, considerar la llegada de N pacientes que deben ser atendidos
en estricto orden de llegada, considerando que solo un paciente es atendido a la vez con
un tiempo aleatorio de atención, los pacientes restantes deben esperar que el médico se
desocupe, no hay límite de espacio de espera. Si no hay pacientes, el médico se pone a
navegar en internet hasta la llegada del siguiente paciente, que tocara la puerta de su
consultorio para avisarle de su llegada. Resolver este problema con monitores.
Solución
monitor Doctor {
const int N = 1; //La cantidad de pacientes que el medico atendera
int Count; //Indica el numero de pacientes en consultorio
condition NoVacio;
condition NoLleno;
int enConsultorio;
void Diagnosticar() {
if (Count == 0)
waitc(NoVacio);
cout<<"Medico atendiendo al Paciente "<<enConsultorio <<endl;
Count = 0; //Consultorio vacio
signalc(NoLleno);
}
init {
Count = 0;
}
}
int Values = 10;
void main() {
cobegin {
Paciente(1);Paciente(2);Paciente(3);Paciente(4);Paciente(5);Paciente(6);
Paciente(7);Paciente(8);Paciente(9);Paciente(10);Medico(100);
}
}
3.1.4. Considerar un parque infantil que tiene una piscina y un columpio. Los niños pueden
columpiar o nadar en la piscina. Pero se encuentran con el inconveniente de que todos
ellos pueden nadar al mismo tiempo pero sólo uno puede columpiar. Definir un proceso
que ejecuten los niños concurrentemente de forma que sincronicen estas actividades
usando monitores.
Solución
monitor Parque {
const int N = 1;
const int M = 10;
int suma=0;
int columpio;
int piscina;
condition libreP;
condition libreC;
init {
piscina = 0; columpio = 0;
}
}
//fin del monitor
void main() {
cobegin {
jugar(1);jugar(2);jugar(3);jugar(4);jugar(5);jugar(6);jugar(7);jugar(8);jugar(9);jugar(10);
}
}
3.1.5. En una clínica de traumatología hay tres secciones diferentes: Médico, Yeso y Rayos-X.
Los enfermos acceden a la clínica y esperan a que les atienda una enfermera que les
indica la sala a la que deben acceder. De forma que la sección Medico tiene una sala de
espera para 20 enfermos, Yeso tiene una sala de espera para 6 enfermos y Rayos-X No
espera. Realizar un programa concurrente de forma que utilizando semáforos coordine las
tareas de los enfermos.
Solución
semaphore enfermera=1;
semaphore salaMedico=1;
semaphore salaYeso=1;
int destino;
void main()
{
cobegin
{
enfermo(1);enfermo(2);enfermo(3);enfermo(4);enfermo(5);
enfermo(6);enfermo(7);enfermo(8);enfermo(9);enfermo(10);
}
}
4.1.1. Dado un sistema con cinco procesos, P1 a P5, y tres tipos de recursos, A, B y C, de los que
existen 10, 5 y 7 ejemplares, respectivamente. Supongamos que en el instante actual tenemos la
siguiente situación del sistema:
Solución
Disponible = (3 3 2)
Se puede atender a P2 o P4, se elige P2 = - (1 2 2)
Nuevo disponible después de la asignación = (2 1 0)
Se recupera todos los recursos asignados a P2 = + (3 2 2)
Nuevo disponible después de recuperar recursos = (5 3 2)
Se puede atender a P3 = - (6 0 0)
Nuevo disponible después de la asignación = (1 4 5)
Se recupera todos los recursos asignados a P2 = + (9 0 2)
Nuevo disponible después de recuperar recursos = (10 4 7)
Se puede atender a P1 = - (7 4 3)
Nuevo disponible después de la asignación = (3 0 4)
Se recupera todos los recursos asignados a P2 = + (7 5 3)
Nuevo disponible después de recuperar recursos = (10 5 7)
El orden de atención de los procesos es P2, P4, P5, P3 y P1; secuencia que permite un estado
seguro de asignación de recursos.
4.1.2. Se tiene un sistema formado por tres procesos: P1 (que necesita como máximo 5
recursos), P2 (que necesita como máximo 6 recursos) y P3 (que necesita como máximo 4
recursos). Considerando 10 recursos disponibles. Utilizando el algoritmo del banquero.
Determinar si las dos situaciones siguientes corresponden a estados seguros:
a) El proceso P1 usa 3 recursos, P2 usa 2 recursos y P3 usa 1 recurso
b) El proceso P1 usa 3 recursos, P2 usa 4 recursos y P3 usa 2 recursos
Solución
a)
Procesos Maximo Asignado Necesario
P1 5 3 2
P2 6 2 4
P3 4 1 3
Libre 4
Total Rec 10
b)
Procesos Maximo Asignado Necesario
P1 5 3 2
P2 6 4 2
P3 4 2 2
Libre 1
Total Rec 10
Recursos existentes=(8 8 4 3)
Recursos disponibles=(2 2 2 2)
Solución
Recursos necesarios
R1 R2 R3 R4
P1 2 0 1 3
P2 3 2 1 2
P3 1 1 2 0
Disponible = (2 2 2 2)
Se puede atender a P3 = - (1 1 2 0)
Nuevo disponible después de la asignación = (1 1 0 2)
Se recupera todos los recursos asignados a P3 = + (3 4 3 1)
Nuevo disponible después de recuperar recursos = (4 5 3 3)
Se puede atender a P2 = - (3 2 1 2)
Nuevo disponible después de la asignación = (4 5 2 1)
Se recupera todos los recursos asignados a P2 = + (4 3 2 2)
Nuevo disponible después de recuperar recursos = (8 8 4 3)
El orden de atención de los procesos es P3, P1 y P2; secuencia que permite un estado seguro de
asignación de recursos
Solución
Existe un ciclo de asignaciones y solicitudes que no pueden ser reducidas, por lo tanto, existe
interbloqueo
4.2.2. Dada la siguiente asignación y solicitud de recursos pro procesos, determinar si existe
interbloqueo:
Solución
4.2.3. Analizar si existe interbloqueo en la siguiente asignación y solicitud de recursos por los
procesos:
Solución
Solución
Como el recurso R2 esta asignado a P4, este proceso termina y libera el recurso, al igual que el
recurso R3 que esta asignado a P3, por lo tanto una vez liberados estos recursos pueden ser
asignados a P2
Al tener todos los recursos, el proceso P2 termina liberando sus recursos, por lo que el recurso R1
se asigna al proceso P1 y este puede terminar, por lo que se concluye que no existe interbloqueo
5.1.1. Considerar la memoria principal de un computador con la siguiente lista de huecos libres de
tamaño: 12 Kb, 14 Kb, 2 Kb, 21 Kb, 5 Kb, 18 Kb, 13 Kb y 32 Kb ¿Cuáles huecos de la memoria son
utilizados para los siguientes requerimientos de memoria de 5 Kb, 29 Kb y 7 Kb. Al utilizar un
algoritmo para la asignación de segmentos de tipo: First Fit, Next Fit, Best Fit y Worst Fit?
Solución
2 2 2 2
14
21 21 21 21 7
5 5 5 5 5
18 18 18 18
13 13 13 13
3 3 3 27
32 29 32 29 32 29 32 5
5.1.2. Considerar un sistema con intercambio en el que la memoria posee agujeros libres de
tamaño: 1250 Kb, 845 Kb, 1750 Kb, 850 Kb y 1200 Kb, dispuestos en el orden dado. Se requieren
5 segmentos de tamaños 1210 Kb, 845 Kb, 1225 Kb, 800 Kb y 1650 Kb. Para los algoritmos
primero en ajustarse, siguiente en ajustarse, mejor ajuste y peor ajuste ¿Que agujeros serán
asignados? y ¿qué algoritmo aprovecha mejor la memoria, considerando la fragmentación?
Solución
5.2.1. Un proceso genera las siguientes direcciones lógicas: 252, 62, 125 y (2,265). Indique las
direcciones físicas correspondientes según la técnica de paginación, con un tamaño de
página de 64 bytes. La tabla de páginas del proceso es la siguiente:
Pagina Marco
0 520
1 430
2 230
3 610
Solución
a) #pagina= 252/64 = 3
Desplazamiento = 252 mod 64 = 60
(3,60) = (610,60)= 610 * 64 + 60 = 39100
b) #pagina= 62/64 = 0
Desplazamiento = 62 mod 64 = 62
(0,62) = (520,62)= 520 * 64 + 62 = 33342
c) #pagina= 125/64 = 1
Desplazamiento = 125 mod 64 = 61
(1,61) = (430,61)= 430 * 64 + 61 = 27581
5.2.2. Un proceso genera las siguientes direcciones lógicas: 65, 31, 100 y (4,25). Indique las
direcciones físicas correspondientes según la técnica de paginación, con un tamaño de
página de 32 bytes. La tabla de páginas del proceso es la siguiente:
Pagina Marco
0 70
1 65
2 99
3 65
Solución
a) #pagina= 65/32 = 2
Desplazamiento = 65 mod 32 = 1
(2,1) = (99,1)= 99 * 32 + 1 = 3169
b) #pagina= 31/32 = 0
Desplazamiento = 31 mod 32 = 31
(0,31) = (70,31)= 70 * 32 + 31 = 2271
c) #pagina= 100/32 = 3
Desplazamiento = 100 mod 32 = 4
(3,4) = (65,4)= 65 * 32 + 4 = 2084
Solución
5.3.2. En un sistema que utiliza gestión de memoria segmentada, se tiene la siguiente tabla de
segmentos:
¿A qué direcciones físicas corresponden las siguientes direcciones virtuales?: (0,128) (3,558) (0,
950) El formato corresponde a (no de segmento, desplazamiento).
Solución
5.4.1. Se tiene un sistema que utiliza gestión de memoria con segmentación paginada, con un
tamaño de pagina de 256 bytes. A continuación se muestra la tabla de segmentos de un proceso y
la tabla de paginas de todos los segmentos:
Se pide calcular las direcciones físicas para las siguientes direcciones lógicas. El formato de la
dirección lógica es (N segmento, desplazamiento):
a) (0,259)
b) (0,518)
c) (1,10)
d) (0,600)
e) (3,150)
Solución
5.5.1. En un sistema con memoria virtual con 3 marcos de memoria que tiene la siguiente
información:
Pagina Tiempo de Tiempo de última Bit Referencia Bit
carga inicial referencia Modificación
0 120 250 1 0
1 155 210 0 0
2 140 260 1 1
3 185 190 0 1
¿Qué pagina es candidata a reemplazar el algoritmo LRU (Ultimo Recientemente Usado), al
terminar esta sustitución?
¿Qué pagina es candidata a reemplazar el algoritmo de reloj, al terminar esta sustitución
Solución
LRU
0
2
1
3
3
1
0
2
0
2
1
3
3
1
0
2
0
2
1
1
3
1
0
0
2
2
2
3
1
X
X
X
X
X
X
Candidato a salir, pagina 1
Reloj
2
1
1
0
0
1
Candidato a salir, pagina 0
5.5.2. Considera un programa que genera una secuencia de referencias a direcciones virtuales
que corresponde a la siguiente secuencia de referencias de páginas:
1, 2, 3, 4, 1, 2, 5, 6, 1, 3, 1, 2, 5
Aplicar sustitución de paginas para los algoritmos siguientes LRU (Ultimo Recientemente Usado) y
Optimo. Inicialmente se dispone de 5 marcos vacíos.
Solución
LRU
1
2
3
4
1
2
5
6
1
3
1
2
5
1
2
3
4
1
2
5
6
1
3
1
2
5
1
2
3
4
1
2
5
6
1
3
1
2
1
2
3
4
1
2
5
6
6
3
1
1
2
3
4
1
2
5
5
6
3
3
4
4
2
2
5
6
X
X
X
X
X
X
X
OPTIMO
1
2
3
4
1
2
5
6
1
3
1
2
5
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
3
3
4
4
4
4
6
6
6
6
6
6
5
5
5
5
5
5
5
X
X
X
X
X
X
Se generan 6 fallos
de
pagina
5.5.3. En un sistema que implementa memoria virtual mediante demanda de páginas se utiliza el
algoritmo LFU (Ultimo Frecuentemente Usado) para la sustitución de páginas. Un proceso
genera la siguiente secuencia de referencias a páginas en memoria:
1 2 3 4 5 3 4 1 6 7 8 9 7 8 9 6 1 2 3 5 4 3 7
Determinar cuántos fallos de página se producen disponiendo 3 marcos de memoria para este
proceso.
Solución
LFU
1
2
3
4
5
3
4
1
6
7
8
9
7
8
9
6
1
2
3
5
4
3
7
1
1
1
1
1
1
4
1
5
1
5
1
5
1
1
1
6
1
7
1
8
1
9
1
7
1
8
1
9
1
6
1
1
1
2
1
2
1
5
1
5
1
5
1
7
1
2 1 2 1 2 1 4 1 4 1 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 3 4 3 4 3
3 1 3 1 3 1 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 3 3 3 3 3 3 3 3 3
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
7.1.1. Suponga que un manejador de disco recibe peticiones de bloques de disco para las
siguientes pistas: 52, 35, 46, 23, 90, 102, 13, 134, 20, 42, 100, 55, 70, 180, 150. Si el disco tiene
200 pistas, el tiempo de acceso entre pistas consecutivas es 4 ms y el tiempo de acceso de la pista
0 a la 199 es 8 ms. Calcule los desplazamientos y tiempos de acceso para los algoritmos de
planificación de disco FCFS (First Come First Served), SSFT (Shortest Seek First), SCAN(up), C-
SCAN(up), LOOK(up) y C-LOOK(up). El cabezal de lectura esta en la pista 30.
Solución
FCFS
SSFT
SCAN
C-SCAN
LOOK
C-LOOK