1

1 Introducción .......................................................................................................................... 21.1 Breve reseña histórica...................................................................................................... 21.2 Evolución: primera, segunda, tercera y cuarta generación.............................................. 2

2 Estructura ............................................................................................................................. 42.1 Sistemas monolíticos ....................................................................................................... 42.2 Sistemas por capas.......................................................................................................... 5

3 Interfaces de Usuario............................................................................................................ 53.1 Interfaz de línea de comandos......................................................................................... 63.2 Interfaz gráfica.................................................................................................................. 6

4 Modos de procesamiento ..................................................................................................... 64.1 Sistemas Multitareas y Monotareas ................................................................................. 64.2 Sistemas Multiusuario y Monousuario ............................................................................. 74.3 Sistemas Por lotes, Interactivos y de Tiempo compartido ............................................... 7

5 Procesos............................................................................................................................... 85.1 El modelo de procesos..................................................................................................... 85.2 Comunicación entre procesos........................................................................................ 115.3 Concurrencia .................................................................................................................. 115.4 Planificación (scheduling) de procesos.......................................................................... 12

6 Administración de la Memoria ............................................................................................ 156.1 Monoprogramación vs. Multiprogramación .................................................................... 156.2 Utilización de la memoria ............................................................................................... 166.3 Administración de Memoria Real ................................................................................... 166.4 Administración de Memoria Virtual ................................................................................ 18

7 Optimización ....................................................................................................................... 217.1 Fragmentación de archivos ............................................................................................ 217.2 Compresión de datos ..................................................................................................... 217.3 Administración de memoria............................................................................................ 21

2

IntroducciónBreve reseña histórica

Desde su creación, las computadoras digitales han utilizado un sistema de codificación deinstrucciones en sistema de numeración binaria, es decir con los 0s y 1s. Esto se debe a quelos circuitos integrados funcionan con este principio, es decir, hay corriente (1) o no haycorriente (0).En el origen de la historia de las computadoras (hace unos cuarenta años), los sistemasoperativos no existían y la introducción de un programa para ser ejecutado se convertía en unincreíble esfuerzo que solo podía ser llevado a cabo por muy pocos expertos. Esto hacia quelas computadoras fueran muy complicadas de usar y que se requiriera tener altosconocimientos técnicos para operarlas. Era tan complejo su manejo, que en algunos casos elresultado llegaba a ser desastroso.Además, el tiempo requerido para introducir un programa en aquellas grandes máquinas delento proceso superaba por mucho el de ejecución y resultaba poco provechosa la utilizaciónde computadoras para resolución de problemas prácticos.Se buscaron medios más elaborados para manipular la computadora, pero que a su vezsimplificaran la labor del operador o el usuario. Es entonces cuando surge la idea de crear unmedio para que el usuario pueda operar la computadora con un entorno, lenguaje y operaciónbien definido para hacer un verdadero uso y explotación de esta. Surgen los sistemasoperativos.Un sistema operativo es el encargado de brindar al usuario una forma amigable y sencilla deoperar, interpretar, codificar y emitir las ordenes al procesador central para que este realice lastareas necesarias y especificas para completar una orden.El sistema operativo, es el instrumento indispensable para hacer de la computadora un objetoútil. Bajo este nombre se agrupan todos aquellos programas que permiten a los usuarios lautilización de este enredo de cables y circuitos, que de otra manera serian difíciles de controlar.Un sistema operativo es un conjunto de programas que hacen al hardware utilizable. El sistemaoperativo es un administrador de recursos: cpu, dispositivos de E/S, memoria, datos. Lasfunciones del sistema operativo son:

Interfaz con el usuario Compartir información entre usuarios Compartir el hardware Recuperarse ante errores Etc.

Evolución: primera, segunda, tercera y cuarta generaciónLos Sistemas Operativos, al igual que el Hardware de las computadoras, han sufrido una seriede cambios revolucionarios llamados generaciones. En el caso del Hardware, las generacioneshan sido marcadas por grandes avances en los componentes utilizados, pasando de válvulas(primera generación) a transistores (segunda generación), a circuitos integrados (tercerageneración), a circuitos integrados de gran y muy gran escala (cuarta generación). Cadageneración sucesiva de hardware ha ido acompañada de reducciones substanciales en loscostos, tamaño, emisión de calor y consumo de energía, y por incrementos notables envelocidad y capacidad.

Primera generación (1945-1955).Las maquinas eran construidas con valvulas, eran enormes, ocupaban toda una habitación.La maquina era diseñada, construida, programada y operada por un pequeño grupo depersonas.La programación se realizaba en lenguaje de maquina, y con frecuencia se utilizabanconexiones para controlar las funciones básicas de la maquina. El sistema operativo aun no seconocía.

3

Los problemas que resolvían eran cálculos numéricos, como por ejemplo una tabla con lasfunciones seno y coseno.El modo usual de operación consistía en que un programador reservaba cierto tiempo en unahoja de reservación pegada a la pared, iba al cuarto de la maquina, insertaba su conexión en lacomputadora y pasaba unas horas esperando que ninguna de las 20000 o mas bulbos sequemara durante la ejecución.A partir de la década del 50, la rutina mejoro un poco con la aparición de las tarjetasperforadas, que permitían escribir los programas en las tarjetas y leerlas, en vez de usarconexiones.

Segunda generación (1955-1965).Aparece el transistor. Los programadores escribían sus programas primero en papel (fortran oassembler) y lo pasaban a tarjetas perforadas. Luego le entregaban la tarjeta perforada aloperador.El operador le entregaba al programador la salida por impresora del programa. Se perdíamucho tiempo mientras el operador hacia sus tareas de cargar programas y retirar la salida dela impresora. Dado que el costo de estos equipos eran muy altos, se buscaron formas dereducir el tiempo perdido.La solución fue el sistema por lotes (figura 1.1), que consistía en juntar conjuntos o lotes detareas similares que se leían con el lector de tarjetas perforadas y se almacenaban en unacinta, esta tarea se realizaba en una maquina económica, de baja capacidad deprocesamiento, que eran útiles para leer tarjetas, copiar cintas e imprimir.Luego de armar el lote de tareas, se llevaba la cinta a la maquina que realizaba elprocesamiento, esta era muy cara y de alta capacidad de procesamiento para esos tiempos.El operador cargaba un programa especial que leía la primer tarea de la cinta y la ejecutaba, lasalida se escribía en una segunda cinta. Este programa fue el precursor de los sistemasoperativos. Después que finalizaba cada tarea, el sistema operativo cargaba la siguiente y asísucesivamente hasta finalizar todas la tareas contenidas.Luego el operador remplazaba las cintas de entrada y salida, la cinta de entrada se remplazabacon una nueva que contenía otro lote para su ejecución, la cinta de salida se llevaba a unamaquina económica de bajo procesamiento, que realizaba la impresión off-line.Las grandes computadoras de segunda generación se utilizaron principalmente para loscálculos científicos y de ingeniería, por ejemplo, en la resolución de ecuaciones diferencialesparciales. Por lo general se programaba en lenguaje FORTRAN y assembler.

Tercera generación (1956-1980).Aparecen los circuitos integrados. Aparecen nuevas técnicas, como la multiprogramación ylos sistemas de tiempo compartido.Antiguamente mientras un proceso esperaba que finalice alguna operación de entrada-salida,el procesador permanecía inactivo. La multiprogramación consiste en dividir la memoria ensectores y cargar varios procesos, cada uno en un sector de memoria, cuando uno de ellosnecesita esperar que una operación de entrada-salida finalice, otro proceso puede utilizar elprocesador. Si la cantidad de procesos que se cargan en memoria simultáneamente son lossuficientes, el procesador permanecerá ocupado casi el 100% del tiempo. En los sistemas de

4

tiempo compartido, cada usuario tenía una terminal online, donde podía enviar comandos yver su salida en forma interactiva. Igual que en multiprogramación, se cargan varios procesossimultaneamente en memoria, la conmutación entre procesos no solo sucedía cuando elproceso estaba esperando que alguna operación de entrada-salida finalice, también seconmutaba de proceso cada cierto intervalo, dándole la apariencia a cada usuario que poseíala maquina para el solo.Gracias a los circuitos integrados, hicieron su aparición la minicomputadoras, que erancomputadoras muy reducidas en sus capacidades de procesamiento, pero muy económicas(solo 120.000 dólares, el 5% de una computadora de gran porte). De esta forma, lacomputación dejo de ser una industria solo para las grandes corporaciones.

Cuarta generación (1980-presente).Aparecen los circuitos integrados de gran escala (contienen miles de transistores en uncentímetro cuadrado de cilicio), esto hace disminuir costos y aparecen las computadoraspersonales. También aparece el software para computadoras personales, desarrollado paragente que no conoce nada de computadoras y no tiene intenciones de aprender.Aparecen los sistemas multiprocesador, los procesadores comparten la memoria y el reloj.Se incrementa la capacidad de procesamiento y la confiabilidad, así como baja su precio.

Multiprocesamiento simétrico: Cada procesador ejecuta una copia del sistemaoperativo

Multiprocesamiento asimétrico: Cada procesador tiene asignado una tarea especifica,existe un procesador master que asigna tareas a los procesadores esclavos.

Aparecen los sistemas operativos para redes, donde el usuario puede dar ordenes a unacomputadora en forma remota, copiar archivos de una computadora a otra, etc.Aparecen los sistemas distribuidos. Cada procesador tiene su memoria y reloj local, secomunican con otros procesadores a través de una red. Los procesos se ejecutan en distintosprocesadores, unidos mediante una red, sin que el usuario se entere.Aparecen los sistemas en tiempo real, se utiliza cuando las tareas se deben realizar dentrode un limite de tiempo.

EstructuraInternamente los sistemas operativos estructuralmente se clasifican según como se hayanorganizado internamente en su diseño, por esto la división más común de los S.O. es:o Sistemas monolíticoso Sistemas por capas

Sistemas monolíticosEn este esquema, el sistema operativo se describen como un conjunto de procedimientos,cada uno de los cuales puede llamar a cualquiera de los otros siempre que lo necesite. Cuandose emplea esta técnica, cada procedimiento del sistema tiene una interfaz bien definida entérminos de parámetros y resultados, y cada una tiene la libertad de llamar a cualquiera otra, sila última ofrece algún cálculo útil que la primera necesite.Para construir el programa objeto real del sistema operativo cuando se usa este método, secompilan todos los procedimientos individuales a archivos que contienen los procedimientos ydespués se combinan todos en un solo archivo objeto con el enlazador.En términos de ocultamiento de información, esencialmente no existe ninguno; todoprocedimiento es visible para todos (al contrario de una estructura que contiene módulos opaquetes, en los cuales mucha información es local a un módulo y sólo pueden llamar puntosde registro designados oficialmente del exterior del módulo)Esta organización sugiere una estructura básica del sistema operativo:1.- Un programa central que invoque el procedimiento de servicio solicitado (Shell o Kernel)2.- Un conjunto de procedimientos de servicios que realice las llamadas al sistema.3.- Un conjunto de procedimientos de uso general que ayude a los procedimientos de servicio.

5

Sistemas por capasEstos sistemas operativos se organizan como una jerarquía de estratos, cada uno construidoarriba del que está debajo de él. Un ejemplo puede ser un sistema de 6 capas, que se detalla acontinuación:

o El estrato 0 trabaja con la distribución del procesador, cambiando entre procesos cuandoocurren interrupciones o los relojes expiran. Sobre el estrato 0, el sistema consta de procesossecuenciales, cada uno de los cuales puede programarse sin tener que preocuparse por elhecho de que múltiples procesos estén corriendo en un solo procesador. En otras palabras, elestrato 0 ofrece la multiprogramación básica de la CPU.o El estrato 1 realiza el manejo de memoria. Este distribuye el espacio de memoria paraprocesos. Sobre el estrato 1, los procesos no necesitan preocuparse si esta en la memoria o enel disco; el software del estrato 1 se hace cargo de asegurar que las porciones del proceso setrajeran a memoria (desde el disco) siempre que se necesitaran.o El estrato 2 manejaba la comunicación entre cada proceso y la consola de operador. Porencima de este estrato, cada proceso tiene su propia consola de operador.o El estrato 3 se hace cargo de manejar los dispositivos de E/S y de separar la informaciónentrante y saliente de ellos. Para realizar la comunicación, utiliza búferes de memoria en cadaproceso, para guardar la información que no puede ser pasada directamente entre ellos. Sobreel estrato 3 cada proceso puede trabajar con dispositivos de E/S abstractos con propiedadesagradables, en vez de dispositivos reales con muchas peculiaridades.o El estrato 4 es donde se encuentran los programas de los usuarios. Estos no tienen quepreocuparse por el manejo de los procesos, memoria, consola o E/S.o El proceso operador del sistema se localiza en el estrato 5.Esta estructura se utiliza actualmente, y se puede visualizar mejor si realizamos círculosconcéntricos representando cada capa:

Interfaces de UsuarioTodo sistema Operativo necesita tener una interfaz de Usuario. Ésta es la encargada deinterpretar los comandos ingresados por el usuario y traducirlos en instrucciones al sistemaoperativo. Existen diferentes tipos de interfaces de usuario:

Interfaz de línea de comandos

6

Interfaz gráfica Interfaz por menú

Los dos tipos más comunes de interfaces son la interfaz de línea de comandos y la interfazgráfica.

Interfaz de línea de comandosEs la forma de interfaz entre el sistema operativo y el usuario en la que el usuario escribe loscomandos utilizando un lenguaje de comandos especial (ver figura 3.1). Los sistemas coninterfaces de líneas de comandos se consideran más difíciles de aprender y utilizar que los delas interfaces gráficas. Sin embargo, los sistemas basados en comandos son por lo generalprogramables, lo que les otorga una flexibilidad que no tienen los sistemas basados en gráficoscarentes de una interfaz de programación.Los Sistemas Operativos más comunes que tienen interfaz de línea de comandos son elD.O.S., Unix y Linux (vale aclarar que tanto Unix como las distintas distribuciones de Linux,proveen una interfaz gráfica que se puede instalar como adicional).

Interfaz gráficaEs el tipo de visualización que permite al usuario elegir comandos, iniciar programas y ver listasde archivos y otras opciones utilizando las representaciones visuales (iconos) y las listas deelementos del menú.Generalmente se encuentran organizadas en “ventanas” (secciones de la pantalla) querepresentan una aplicación (o parte de una). Las selecciones pueden activarse bien a travésdel teclado o con el mouse.Para los autores de aplicaciones, las interfaces gráficas de usuario ofrecen un entorno que seencarga de la comunicación con el ordenador o computadora.Esto hace que el programador pueda concentrarse en la funcionalidad, ya que no esta sujeto alos detalles de la visualización ni a la entrada a través del mouse o el teclado. También permitea los programadores crear programas que realicen de la misma forma las tareas másfrecuentes, como guardar un archivo, porque la interfaz proporciona mecanismos estándar decontrol como ventanas y cuadros de diálogo. Otra ventaja es que las aplicaciones escritas parauna interfaz gráfica de usuario son independientes de los dispositivos: a medida que la interfazcambia para permitir el uso de nuevos dispositivos de entrada y salida, como un monitor depantalla grande, una nueva impresora o un dispositivo óptico de almacenamiento, lasaplicaciones pueden utilizarlos sin necesidad de cambios.Los Sistemas Operativos más comunes que tienen interfaz gráfica son Microsoft Windows,MacOS (de Apple), OS/2 (de IBM) y las interfaces gráficas para Unix y Linux (GNOME, KDE,CDE)

Modos de procesamientoLos S.O. pueden procesar las tareas y comunicarse con el usuario de diferentes modos. Entrelos diferentes modos podemos nombrar: monotareas, multitareas, monousuario, multiusuario,interactivos, por lotes, de tiempo compartido, etc.En este Tema vamos a ver cada uno de estos modos, pero vamos a organizarlos de acuerdo asus características comunes. Primero veremos las distintas formas de procesar las tareas,donde veremos las características de los sistemas multitareas y monotareas. Luego veremoslas distintas formas de aceptar los usuarios (sistemas monousuarios y multiusuarios) y porúltimo veremos la forma en que ejecutan los comandos (en tiempo real, por lotes, de tiempocompartido).

Sistemas Multitareas y MonotareasSistema Operativo Multitareas: Es el modo de funcionamiento disponible en algunos sistemasoperativos, mediante el cual la computadora procesa varias tareas al mismo tiempo. Existenvarios tipos de multitareas, la conmutación de contextos, la multitarea cooperativa y multitareade tiempo compartido. La conmutación de contextos (context Switching) es un tipo muy simplede multitarea en el que dos o más aplicaciones se cargan al mismo tiempo, pero en el que solo

7

se esta procesando la aplicación que se encuentra en primer plano (la que ve el usuario). Paraactivar otra tarea que se encuentre en segundo plano, el usuario debe traer al primer plano laventana o pantalla que contenga esa aplicación. Dos ejemplos de Sistemas Operativos conmultitarea por conmutación de contextos son el Novell DOS y la dupla D.O.S.-Windows 3.x.En la multitarea cooperativa, la que se utiliza en el sistema operativo Macintosh, las tareas ensegundo plano reciben tiempo de procesado durante los tiempos muertos de la tarea que seencuentra en primer plano (por ejemplo, cuando esta aplicación esta esperando información delusuario), y siempre que esta aplicación lo permita. En los sistemas multitarea de tiempocompartido, como OS/2, cada tarea recibe la atención del microprocesador durante unafracción de segundo. Para mantener el sistema en orden, cada tarea recibe un nivel deprioridad o se procesa en orden secuencial. Dado que el sentido temporal del usuario esmucho más lento que la velocidad de procesamiento del ordenador, las operaciones demultitarea en tiempo compartido parecen ser simultáneas.Sistema Operativo Monotareas: Los sistemas operativos monotareas son más primitivos y estodo lo contrario al visto anteriormente, es decir, solo pueden manejar un proceso en cadamomento o que solo puede ejecutar las tareas de una en una. Por ejemplo cuando lacomputadora esta imprimiendo un documento, no puede iniciar otro proceso ni responder anuevas instrucciones hasta que se termine la impresión. El Sistema Operativo monotareas máscomún es el D.O.S.

Sistemas Multiusuario y MonousuarioSistemas Operativos Monousuario: Los sistemas monousuarios son aquellos que nada máspuede atender a un solo usuario, gracias a las limitaciones creadas por el hardware, losprogramas o el tipo de aplicación que se este ejecutando.Estos tipos de sistemas son muy simples, porque todos los dispositivos de entrada, salida ycontrol dependen de la tarea que se esta utilizando, esto quiere decir, que las instrucciones quese dan, son procesadas de inmediato; ya que existe un solo usuario. Y están orientadosprincipalmente por los microcomputadores. Ejemplo de un sistema operativo monousuarios esel D.O.S.Sistema Operativo Multiusuario: Es todo lo contrario a monousuario; y en esta categoría seencuentran todos los sistemas que cumplen simultáneamente las necesidades de dos o másusuarios, que comparten mismos recursos. En otras palabras consiste en el fraccionamientodel tiempo (timesharing). Este tipo de sistemas se emplean especialmente en redes.Generalmente piden una identificación de ingreso al sistema (lo que comúnmente se llamalogin) que puede estar acompañado por una contraseña, y mantienen distintos perfiles para losusuarios donde se especifican los distintos permisos de acceso a archivos o ejecución deprogramas. Cada usuario puede configurar ciertas características de funcionalidad del S.O. quese cargarán cada vez que inicie el sistema. Existen varios Sistemas operativos multiusuario, ylos mas comunes son Windows NT/2000, Unix, Linux.

Sistemas Por lotes, Interactivos y de Tiempo compartidoSistemas de Secuencia por Lotes: La secuencia por lotes o procesamiento por lotes en

microcomputadoras es la eje cución de una lista de comandos del sistema operativo uno trasotro sin intervención del usuario. Procesamiento por lotes también puede referirse al procesode almacenar transacciones durante un cierto lapso antes de su envío a un archivo maestro,por lo general una operación separada que se efectúa durante la noche. Los sistemasoperativos por lotes (batch) tratan los programas por grupos (lotes) en vez de individualmente.La función de estos sistemas operativos consiste en cargar en memoria un programa desde launidad de almacenamiento (cinta, disco, etc.) y ejecutarlo. Al final de la ejecución, se realiza unsalto a una dirección de memoria desde donde el S.O. reasumía el control y cargaba elsiguiente programa y lo ejecutaba. De esta manera el tiempo entre un trabajo y otro disminuyeconsiderablemente. Un ejemplo de Sistema Operativo por lotes es el antiguo OS/360 de IBM.Sistemas en Tiempo Real: Un sistema operativo en tiempo real procesa las instruccionesrecibidas al instante, y una vez que han sido procesadas muestra el resultado. Este tipo deS.O. tiene relación con los sistemas operativos con actividades críticas, donde se necesita unarespuesta inmediata a los requerimientos, sin tener que esperar por su turno de ejecución o

8

turnar su procesamiento con otros procesos. Generalmente son sistemas monousuarios, yaque existe un solo operador y no necesita compartir el procesador entre varias solicitudes.Su característica principal es dar respuestas rápidas; por ejemplo en un caso de peligro senecesit arían respuestas inmediatas para evitar una catástrofe.Sistemas de Tiempo Compartido: El tiempo compartido en ordenadores o computadorasconsiste en el uso de un sistema por más de una persona al mismo tiempo. El tiempocompartido ejecuta programas separados de forma concurrente, intercambiando porciones detiempo asignadas a cada programa (usuario). En este aspecto, es similar a la capacidad demultitareas que es común en la mayoría de los microordenadores o las microcomputadoras.Sin embargo el tiempo compartido se asocia generalmente con el acceso de varios usuarios acomputadoras más poderosas (mainframes o servidores) y a organizaciones de servicios,mientras que la multitarea esta relacionada con las microcomputadoras e implica la realizaciónde múlt iples tareas por un solo usuario.

ProcesosEl concepto central dentro de cualquier sistema operativo es el de proceso: una abstracción deun programa en ejecución. Todo lo demás se articula en torno de este concepto. Por estemotivo dedicaremos un capitulo completo al estudio de ellos.

El modelo de procesos

Proceso vs. programa.Un programa es un archivo o conjunto de archivos que contienen código ejecutable, elprograma normalmente esta ubicado en un disco. Se denomina proceso a un programa cuandose encuentra en ejecución. Los sistemas modernos pueden ejecutar varios procesos a la vez,el procesador ejecuta un proceso durante un determinado tiempo y luego conmuta a otro, estoda la sensación de paralelismo. Por eso muchos programadores hablan de seudoparalelismo.Puede suceder que el mismo programa se ejecute varias veces simultáneamente, produciendovarios procesos.Por ejemplo supongamos dos usuarios en un sistema unix , user1 y user2, ambos estánutilizando el programa ls, user1 esta listando sus archivos (ls /home/user1) y el user2 también(ls /home/user2). Ambos utilizan el mismo programa pero generan dos procesos distintos.Ambos procesos se están ejecutando simultáneamente (en realidad, utilizando el concepto deseudoparalelismo).

Memoria utilizada por un proceso.Los procesos tienen su memoria dividida en 3 segmentos: segmento de texto (códigoejecutable), segmento de datos (variables, etc) y segmento de stack, como se muestra en lafigura.

Entre los segmentos de datos y stack hay un espacio de memoria libre, se deja para que elsegmento de datos pueda crecer hacia arriba y el segmento de snack puede crecer haciaabajo.

9

El segmento de stack crece o disminuye automáticamente cuando sea necesario, el de datoscrece o disminuye cuando el proceso lo solicita, generalmente mediante una llamada alsistema. Además de estos segmentos, cada proceso posee un PCB (process control block).Si en el sistema se ejecuta un programa varias veces, genera varios procesos, que compartenel segmento de texto.Tomemos el ejemplo anterior que decía así: Dos usuarios en un sistema unix, user1 y user2,están utilizando el programa ls. user1 esta listando sus archivos (ls /home/user1) y el user2también (ls /home/user2). Esto genera dos procesos distintos, pero comparten el segmento detexto (código del programa).

Estados de un proceso.Un proceso puede estar en 3 estados:

Corriendo Listo Bloqueado

Un proceso se encuentra en el estado denominado corriendo, cuando el procesador lo estaejecutando, o sea esta haciendo uso del procesador. Después de permanecer en el estadocorriendo durante un cierto intervalo de tiempo, el sistema operativo conmuta a otro proceso,quedando el anterior en estado listo, es decir listo para ser ejecutado próximamente.La conmutación entre procesos la realiza una parte del sistema operativo llamada scheduler yla selección del proceso al cual se conmuta se realiza utilizando un algoritmo denominadoalgoritmo de scheduling.Los procesos poseen mecanismos para intercomunicarse, por ejemplo el siguiente comandoproduce una intercomunicación entre dos procesos en un unix:cat file | moreEl proceso cat genera una salida, la cual se redirecciona al proceso more, el proceso moreespera por los datos enviados por cat y los visualiza en pantalla, estos dos procesos seintercomunican mediante un pipe (representado por el carácter “|”).Dependiendo de la velocidad de ambos procesos, puede suceder que el proceso more seencuentre en el estado corriendo, pero no tenga datos en su entrada para visualizar, entoncesdebe pasar al estado bloqueado hasta que haya datos disponibles en su entrada.Cuando un proceso se encuentra en el estado bloqueado, debe pasar primero al estado listopara luego poder pasar al estado corriendo. En la figura se visualiza un diagrama de estados ylas flechas indican las posibles transiciones.

Un proceso se bloquea cuando no puede continuar su ejecución, generalmente se producecuando espera por datos en su entrada y aun no están disponibles.Por ejemplo el intérprete de comandos (shell) permanece bloqueado hasta que el usuarioingresa una orden.Se visualizan cuatro posibles transiciones indicadas por las flechas, veamos cuando seproducen estas transiciones. Las transiciones 1 y 2 entre los estados corriendo y listo lasrealiza el scheduler. La transición de corriendo a listo se produce cuando el scheduler decide

10

que el proceso corrió lo suficiente y conmuta a otro proceso en estado listo. La transición delisto a corriendo se produce cuando el scheduler decide entregarle el procesador a un procesoque se encuentra listo.La transición 4, de corriendo a bloqueado se produce cuando el proceso no puede continuar,debido a que debe esperar que suceda algún evento externo, el scheduler conmuta a otroproceso que se encuentre listo.Por ultimo, la transición 3, de bloqueado a listo se produce cuando sucede el evento que seestaba esperando, una vez en el estado listo el proceso esta dentro del conjunto de loselegibles por el scheduler para pasar a corriendo. Cuando se crea un proceso nuevo, se cargaen memoria y se le asigna el estado listo, la finalización de un proceso se produce cuando estaen el estado ejecutando, devolviendo los recursos que utilizaba.Veamos como ejemplo el intérprete de comandos: supongamos que el intérprete de comandose encuentra en el estado corriendo, pero pasa a bloqueado, esperando que el usuario ingreseuna orden Cuando el usuario pulsa una tecla, se produce una interrupción de teclado, estohace que el procesador deje de ejecutar el proceso en curso y ejecute el proceso de atenciónde teclado.El intérprete de comandos pasa al estado listo, esperando que el scheduler le asigne elprocesador para leer la tecla pulsada.El scheduler le entrega el procesador al intérprete de comandos, este último lee la teclapulsada.

PCB.Como ya dijimos, el sistema operativo administra todos los recursos de la computadora, paraello debe saber qué recursos están siendo utilizados y por quien. Para realizar esta tareamantiene un conjunto de estructuras de datos para los recursos que administra, por ej.:dispositivos de entrada-salida, memoria, procesos, archivos, etc.Para administrar procesos, el sistema operativo mantiene por cada uno de ellos, una estructurade datos, denominada PCB (process control block), la cual contiene información de losrecursos utilizados por el proceso. El PCB de un proceso se debe actualizar antes de conmutardel estado corriendo a listo o bloqueado, para luego poder continuar la ejecución desde el lugardonde se abandonó.Después que se conmutó a otro, se debe actualizar el PCB del proceso, como por ejemplocambiar su estado de listo a corriendo.Algunos de los datos contenidos en la estructura serán:

Registros del procesador. Program counter y stack pointer. Estado del proceso. Tiempo que utilizó el procesador. Identificador de proceso (PID). etc.

El proceso, además de utilizar el procesador, utiliza otros recursos, como memoria, archivos,etc. Por esto, el PCB contendrá punteros a otras estructuras, que almacenan información delos recursos utilizados por él.

Hilos de ejecución.Hasta ahora, solo existía un program counter (PC) en cada proceso, esto se denominaheavyweight processes.Existe la posibilidad de que dentro de un proceso existan varios hilos de ejecución, cada unocon su PC, conjunto de registros del procesador y segmento de stack, pero comparten con losdemás hilos de ejecución el segmento de datos, el segmento de texto, recursos del sistema y elPCB. Este tipo de procesamiento se denomina threads o lightweight processes. El PCBcontendrá información por cada hilo de ejecución, como el PC, registros del procesador, estadodel hilo de ejecución, etc. Ventajas:

11

Se puede compartir la memoria de datos entre procesos. La conmutación entre distintos hilosde ejecución de un mismo proceso es mas rápida que la conmutación de procesos, solo serequiere del cambio de los registros del procesador y el estado. Implementación:Los hilos de ejecución se pueden implementar a nivel usuario o a nivel kernel.A nivel usuario el sistema operativo no se entera de la existencia de hilos de ejecución. Laconmutación entre hilos se realiza sin intervención del sistema operativo, esto hace que seamuy rápido. La desventaja es que si un hilo de ejecución se bloquea, el sistema operativobloquea todo el proceso, bloqueando los demás hilos.A nivel kernel, el sistema operativo conoce la existencia de ellos, la conmutación se realizamediante la intervención del sistema operativo, como por ejemplo mediante una llamada alsistema, la cual es mas lenta, pero si un hilo se bloquea el scheduler seleccionara un hilo delmismo proceso o de algún otro proceso. El kernel debe mantener una zona de memoria porhilo de ejecución, conteniendo registros del procesador, estado, etc.Algunos sistemas soportan ambos tipos de implementación.

Comunicación entre procesosEl sistema operativo nos provee mecanismos para que los procesos se puedan intercomunicar.La intercomunicación se puede realizar utilizando o no almacenamiento compartido.

Almacenamiento compartido.Se comparte algún medio de almacenamiento entre ambos procesos, como un archivo,variable o buffer. Ambos procesos pueden leer y escribir el recurso compartido, esto puedetraer problemas de concurrencia, dado que si ambos procesos intentan escribir en el espaciode almacenamiento, pueden bloquearse mutuamente.

Sistema de intercambio de mensajes.Mecanismo de comunicación entre procesos sin utilizar variables compartidas. Se utilizanllamadas al sistema para enviar y recibir mensajes:send(destino, &mensaje)recieve(origen, &mensaje)Se puede implementar de distintas formas: Comunicación directa.Los mensajes se envían directamente entre procesos, cada proceso debe ser identificado conun nombre. En las llamadas al sistema se especifica el nombre de los procesos.send(destino, &mensaje)recieve(origen, &mensaje) Comunicación indirecta.Los mensajes son enviados indirectamente, mediante una casilla de mensajes (mailbox), lacual almacena los mensajes que aun no aceptó el proceso destino.Estas casillas pueden almacenar hasta cierta cantidad de mensajes, especificado cuando secrea.En los parámetros dirección de las llamadas al sistema, se especifica el nombre de la casilla demensajes.send(mailbox, &mensaje)recieve(mailbox, mensaje)Si la casilla esta llena, la llamada a send() bloqueará al proceso origen.

Concurrencia

Introducción.Estudiaremos que sucede cuando varios eventos ocurren simultáneamente, por ejemplo:

Varios procesos acceden al mismo tiempo a una zona de memoria compartida(comunicación entre procesos).

12

Varios procesos utilizan al mismo tiempo un dispositivo de entrada-salida. Varios usuarios leen o escriben al mismo tiempo el mismo archivo. etc.

Normalmente cuando se escribe un programa, no se tiene en cuenta que otros programas seejecutarán al mismo tiempo. Por ejemplo si se necesita escribir un archivo a disco, se asumeque el disco esta disponible para el solo, pero en realidad otros programas pueden tratar deescribir el disco simultáneamente.Estudiaremos los mecanismos que nos provee el sistema operativo para que varios procesospuedan acceder simultáneamente a un recurso.

Condiciones de carrera.Consideremos un ejemplo, dos procesos acceden a una variable compartida, incrementando suvalor en uno. El incremento de una variable consiste de 3 pasos:1. Cargar el valor de la variable en un registro del procesador.2. Incrementar el contenido del registro.3. Escribir el contenido del registro a memoriaCuando un proceso trata de incrementar el valor de la variable, ejecutará:readincwriteConsideremos un caso de dos procesos A y B que tratan de incrementar al mismo tiempo elvalor de la variable:El proceso A quiere incrementar el valor de la variable y ejecuta read.El scheduler conmuta al proceso B, que también quiere incrementar el valor de la variable,ejecuta read, inc y write.Luego se conmuta al proceso A, que aún no finalizó de realizar el incremento, ejecuta inc ywrite.La variable sólo se incrementó en una unidad, se perdió uno de los incrementos. El problemase produjo porque el proceso B accedió al recurso compartido cuando el proceso A aun nohabía terminado. Situaciones como esta, donde dos o mas procesos acceden a un recursocompartido y el resultado final depende como se ejecuten los procesos se llaman condicionesde carrera.

secciones críticas.Cualquier recurso que puede ser alterado por dos o mas procesos al mismo tiempo sedenomina recurso crítico.Una sección crítica es la parte del programa que accede al recurso compartido. Debemosencontrar alguna manera de prohibir que dos procesos accedan a un recurso compartido almismo tiempo, o sea una exclusión mutua.Esta condición es suficiente para eliminar condiciones de carreras, pero no para que losprocesos usen eficientemente el recurso compartido. Las condiciones son las siguientes:

Solo un proceso debe estar dentro de la sección crítica (exclusión mutua). No se debe asumir nada acerca de la velocidad y el número de procesadores. Un proceso fuera de su sección crítica no puede bloquear a otros procesos. Los procesos no deben esperar indefinidamente para acceder a su sección crítica.

Planificación (scheduling) de procesosCuando hay más de un proceso que está en condiciones de ejecutarse en la CPU, se debeescoger alguno. El encargado de tomar esa decisión es el planificador o scheduler, y elalgoritmo que usa se llama algoritmo de planificación.Existen varios criterios que puede tomar el planificador para seleccionar el siguiente proceso aejecutar. Algunos de ellos pueden ser: Equidad. Asegurarse que todos los procesos tengan su turno de CPU. Eficacia. Mantener la CPU ocupada todo el tiempo. Tiempo de respuesta. Minimizar el tiempo de respuesta de los usuariosinteractivos.

13

Rendimiento (throughput). Maximizar el número de trabajosterminados por hora. Tiempo de espera. Minimizar el tiempo medio de espera (en la colaREADY) de los procesos.

Una complicación adicional que hay que tener presente es que cada proceso es único eimpredecible. Algunos son intensivos en entrada/salida, es decir, pierden la mayor parte deltiempo esperando por E/S; otros son intensivos en CPU, es decir, requieren más que nadatiempo de CPU. En cualquier caso, todos los procesos alternan entre una fase de ejecución deCPU y otra de espera por E/S. Aunque la duración de las fases de CPU es impredecible y varíamucho entre un proceso y otro, tiende a tener una frecuencia como la de la figura 5.3: hay ungran número de fases de CPU cortos, y muy pocos largos. Esta Información puede serimportante para seleccionar un algoritmo de planificación adecuado.¿Cuándo hay que planificar? Recordando el diagrama de estados, una decisión deplanificación puede o debe tomarse cuando ocurre cualquiera de las siguientes transicionesentre estados de un proceso:1. EJECUTANDO a BLOQUEADO.2. EJECUTANDO a TERMINADO.3. EJECUTANDO a LISTO.4. BLOQUEADO a LISTO.En los casos 1 y 2, necesariamente hay que escoger un nuevo proceso, pero en los casos 3 y4 podría no tomarse ninguna decisión de scheduling, y dejar que continúe ejecutando el mismoproceso que estaba ejecutando. En ese caso, se habla de planificación no-expropiadora (non-preemptive, como en Windows 3.x).Si en cambio se toma una decisión de scheduling en los casos 3 y 4, entonces se habla deplanificación expropiadora (porque se suspende un proceso sin dejarlo terminar para asignarletiempo de CPU a otro).Esta última es más segura y más justa, pero tiene un problema: consideremos dos procesosque comparten Información, y que a uno de ellos se le quita la CPU justo cuando estaba enmedio de una actualización de los datos compartidos.Cuando sea el turno del segundo proceso, éste podría intentar leer los datos cuando están enun estado inconsistente. Este problema se remedia con sincronización.Analizaremos ahora algunos algoritmos específicos de scheduling:

El primero que llega se atiende primeroFCFS (First-come, first-served) por sus siglas en inglés. Es un algoritmo que no usaexpropiación, y que consiste en atender a los procesos por estricto orden de llegada a la colaREADY. Cada proceso se ejecuta hasta que termina, o hasta que hace una llamadabloqueante (de E/S), o sea, ejecuta su fase de CPU completa.La ventaja de este algoritmo es que se trata de un algoritmo muy simple: la cola READY semaneja como una simple cola FIFO. El problema es que el algoritmo no es adecuado para lossistemas de propósito general.

Primero el trabajo más cortoSJN (shortest-job-next) por sus siglas en inglés. En este algoritmo se procesa primero el trabajoque tenga el menor tiempo de CPU de los que se encuentran el la cola READY.O sea, el primer proceso que se ejecute es el que tiene mayor incidencia en el tiempo medio, yel último, tiene incidencia nula. En conclusión, el tiempo medio se minimiza si se ejecutasiempre el proceso con el menor tiempo de procesamiento que esté LISTO. Además, es unabuena manera de prevenir el efecto convoy. Lo malo es que para que esto funcione, hay queadivinar el futuro, pues se requiere conocer la duración de la próxima fase de CPU de cadaproceso. Lo que se hace es predecir la próxima fase de CPU en base al comportamientopasado del proceso, y ejecutar el proceso con menor tiempo estimado de ejecución.Es importante aclarar que este algoritmo es óptimo unicamente cuando se dispone de todas lastareas de forma simultánea.

14

Round-robin (RR)Volviendo a FCFS, una forma obvia de mejorarlo es agregando expropiación o preemption demanera que cada proceso no retenga la CPU por más de un quantum o cantidad de tiempopredefinida. FCFS con tajada de tiempo se conoce como round-robin, y se implementa igualque FCFS, sólo que antes de cederle la CPU a un proceso se mantiene un contador de tiempo(timer) para que provoque una interrupción dentro de un quantum de tiempo. El proceso seejecuta hasta que haga una llamada bloqueante o hasta que use todo su quantum. Encualquiera de los dos casos, la CPU se entrega al siguiente proceso en la cola READY. Elround-robin es muy fácil de implementar. Odo lo que necesita el planificador es mantener unalista de procesos ejecutables. Cuando el quantum de un proceso se consume, se le coloca alfinal de la lista.

Planificación por prioridadLa planificación por prioridad es la planificación en la cual a cada proceso se le asigna unaprioridad y la CPU se asigna al proceso con mayor prioridad en la cola READY. SJN es uncaso especial de planificación por prioridad. SJN es planificación por prioridad donde laprioridad es función del estimador de la duración de la próxima fase de CPU.Hay muchas criterios para definir la prioridad. Ejemplos: Según categoría del usuario. Según tipo de proceso: sistema, interactivo, o por lotes; o bien, intensivo en CPU o intensivoen E/S. Según cuanto hayan ocupado la CPU hasta el momento Para evitar que un proceso de baja prioridad sea postergado en demasía, aumentar prioridadmientras más tiempo lleve esperando: envejecimiento (aging). Para evitar que un proceso de alta prioridad ejecute por demasiado tiempo, se le puede irbajando la prioridad.

Múltiples colasPara complicar más la cosa, podemos agrupar los procesos en distintas clases, y usar distintosalgoritmos de planificación intra-clase, más algún algoritmo interclases.Por ejemplo, los procesos interactivos y los procesos por lotes tienen distintos requerimientosen cuanto a tiempos de respuesta. Entonces, podemos planificar los procesos interactivosusando Round-Robin, y los procesos por lotes según FCFS, teniendo los primeros prioridadabsoluta sobre los segundos.Una forma de implementar este algoritmo es dividiendo la cola READY en varias colas, segúnla categoría del proceso. Por ejemplo, podemos tener diferentes colas, cada una 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 deplanificación entre las colas. Una posibilidad es prioridad absoluta con expropiación. Otraposibilidad: asignar tajadas de CPU a las colas. Por ejemplo, a la cola del sistema se le puededar el 60% de la CPU para que haga Round-Robin, a la de procesos por lote es el 5% para queasigne a sus procesos según FCFS, y a las otras el resto.Por otra parte, podríamos 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 seplanifica con FCFS. Un proceso en la cola x que no termina su fase de CPU dentro delquantum asignado, se pasa al final de la siguiente cola de menor prioridad, pero con mayorquantum. Un proceso en la cola x 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:Cola 0: quantum=10 ms, 40% de CPU.Cola 1: quantum=20 ms, 30% de CPU.Cola 2: quantum=35 ms, 20% de CPU.Cola 3: FCFS, 10% de CPU.

15

Así los procesos de fases más cortas tienen prioridad. Este algoritmo es uno de los másgenerales, pero también uno de los más complejos de implementar. También es difícil deafinar, pues hay múltiples parámetros que definir.

Administración de la MemoriaMonoprogramación vs. MultiprogramaciónEl esquema más sencillo de administración de memoria es aquel en el que se tiene un soloproceso en memoria en cada instante; pero por contraparte, si el sistema está organizado deesta forma, sólo se puede ejecutar un proceso a la vez. Cuando el proceso termina, se cargaen memoria un nuevo proceso para ser ejecutado.Este modelo tiene muchas desventajas si lo comparamos con sistemas operativosmultiprogramación. Existen muchas razones para utilizar multiprogramación: Facilita la programación de aplicaciones al dividirla en dos o más procesos. Permite proporcionar servicio a varios usuarios simultáneamente. Permite la programación de aplicaciones más complejas. Hace un mejor aprovechamiento del tiempo de procesador.Vamos a centrarnos en el último punto para poder comprenderlo mejor:La mayoría de los procesos tardan una porción sustancial de su tiempo en la espera detrabajos de entrada/salida al disco. Es común que un proceso permanezca en un ciclo, leyendobloques del disco, para poder realizar luego un cálculo con el contenido de los bloques. Si, porejemplo, tarda 40 mseg. en leer un bloque, el cálculo tarda 10 mseg. y si utilizamos lamonoprogramación, la CPU estará inactiva, esperando los datos del disco, el 80% del tiempo.

Si en cambio utilizáramos la multiprogramación, suponiendo que tenemos procesos promediosque realizan cálculos sólo durante un 20% del tiempo que permanecen en memoria y contamoscon 5 procesos en memoria, la CPU estaría ocupada el 100% del tiempo. Sin embargo, esteoptimismo es irreal, porque estamos suponiendo también que nunca los 5 procesos estaránesperando por trabajos de entrada/salida al mismo tiempo. Aún así, de acuerdo a cálculosestadísticos, se estima que el uso de la CPU asciende a un 80-90% manteniendo 5 procesosen memoria.Análisis del rendimiento de un sistema con multiprogramación:Consideremos, por ejemplo, un centro de cómputos que trabaja por lotes, cuyos trabajosesperan la entrada/salida un tiempo promedio del 80%. Una mañana se envían 4 trabajos parasu procesamiento, como lo muestra tabla:Trabajo Tpo. De llegada Minutos necesarios de CPU1 10:00 42 10:10 33 10:15 24 10:20 2El primer trabajo, que llega a las 10:00 requiere 4 minutos de tiempo de CPU.

16

Con un tiempo de entrada/salida de 80%, el trabajo sólo utiliza 12 segundos de tiempo de CPUpor cada minuto que se encuentra en memoria, incluso aunque no haya otros trabajos quecompitan con él por la CPU. Los 48 segundos restantes se gastan en en espera de que terminela operación de entrada/salida.Así, el trabajo debe esperar en memoria durante 20 minutos para finalizar.Desde las 10:00 hasta las 10:10, el trabajo 1 está solo en memoria y ha utilizado 2 minutos deCPU. Cuando el trabajo 2 llega a las 10:10, el uso de CPU aumenta del 20% al 36% (ver figura6.1) debido a la multiprogramación. Sin embargo, con la multiprogramación, cada procesoutiliza un 50% de la CPU, con lo que cada trabajo obtiene un 0.18 minutos de CPU por cadaminuto que permanece en memoria. Se puede notar que, al agregar un segundo trabajo, éstele cuesta al trabajo 1 solo un 10% de su desempeño (baja de 0.20 a 0.18 minutos de CPU).A las 10:15 llega el tercer trabajo. En este momento, el trabajo 1 ha recibido 2.9 minutos deCPU y el trabajo 2 ha tenido 0.9. Con la multiprogramación, cada trabajo ahora obtiene un 16% de CPU. En la tabla siguiente se continuó el ejemplo para los 4 trabajos:

Utilización de la memoriaLos programas residen en disco como ejecutables binarios y deben ser traídos a memoria parasu ejecución. El conjunto de programas residentes en disco esperando para ser cargados enmemoria forman la cola de entrada.Los programas pueden direccionar memoria en varias formas: Direccionamiento al momento de la compilación: se genera código absoluto (es decir quesiempre ejecuta en una dirección de memoria de inicio fija, si esta ocupada no ejecuta). Direccionamiento al momento de la carga: maneja direcciones relativas al momento de cargadel programa (no genera código absoluto). Se generan direcciones relativas a la posición inicialde memoria (desplazamiento). Genera código reubicable. Dynamic Linking: se difiere la link-edición hasta el momento de ejecución: se usanormalmente con bibliotecas del sistema. Al momento de la link edición (generación delejecutable) se entrega un trozo de código indicando la referencia a la rutina que se debecargar. Overlays: Esta técnica permite ejecutar un programa en un espacio de memoria menor quesu tamaño. Mantiene en memoria toda aquella parte del programa que es utilizada en uninstante determinado. Las rutinas independientes son cargadas a medida que se necesitanejecutar (son partes del programa que se dividen en forma independiente).

Administración de Memoria RealEl método mas sencillo para administrar la memoria es cuando tenemos un sistemamonousuario y monoprogramación:

Monoprogramación:Asignación contigua de almacenamiento de un solo usuario: Un solo usuario a la vez Todos los recursos a disposición de un solo usuario El tamaño de los programas está limitado por la cantidad de memoria, aunque se puedenusar overlays para sacar mayor provecho a ésta.Protección de Memoria: Se incorpora un registro de limite (limit register) a la cpu. Cada peticiónde acceso a la memoria realizada por el usuario se compara con el registro limite. Si ladirección a la que se quiere acceder es menor o igual al registro limite se cancela la solicitud.

Multiprogramación de partición fija:La memoria se divide en particiones de tamaño fijo (puede ser distinto el tamaño de cadapartición). Originalmente asignaba un proceso a cada partición, es decir que los programas secompilaban y link-editaban para ejecutar en una partición en particular (direcciones absolutas).Posteriormente los compiladores y link editores generaron código reubicable para que unprograma pudiera ejecutarse en cualquier partición de memoria suficientemente grande(direcciones relativas).

17

Figura – Particiones fijas de memoria con colas de procesos independientes para cadapartición.Con esta estructura de administración de memoria se desperdicia memoria y tiempo de CPU (sihay un programa corriendo los demás quedan encolados aunque haya otra partición libre). Verfigura.

Multiprogramación de partición variable:Cada programa o usuario utiliza tanta memoria como sea necesaria siempre que quepa en elalmacenamiento real. Se necesita de alguna estructura tipo índice para referenciar cadaproceso y su ubicación. Es un método mucho mas eficiente que las particiones fijas, pero hacemas compleja la asignación y reasignación de memoria, así como también complica elmantener una registro de esto.Cuando los programas van terminando su ejecución se van generando agujeros en memoriaque quedan desaprovechados. Para solucionar este problema existen distintos enfoques:

Métodos de solución al problema de agujeros en memoria: CombinaciónCuando un programa termina su ejecución el sistema operativo verifica si hay algún bloque dememoria contigua libre (antes o después) en cuyo caso los combina para generar un únicobloque de memoria libre de tamaño igual a la suma de ambos. Compactación o CompresiónAgrupa toda la memoria disponible en un único bloque de memoria al final. Es el método idealen cuanto a aprovechamiento de espacio, pero su gran desventaja es el alto consumo de CPU(casi dedicada exclusivamente a esto). Mientras se ejecuta el algoritmo la actividad del sistemadebe ser detenida. En definitiva no es conveniente utilizar este método para solucionar elproblema de los agujeros en memoria debido al alto costo.

Estrategias de asignación de memoria.Cuando se crea un proceso se debe asignarle una porción de memoria. Si los procesos secrearan con un tamaño fijo, entonces la asignación es muy sencilla: se asigna exactamente losque el proceso utilizará, ni más ni menos. Pero en la realidad, los procesos durante suejecución pueden crecer; si existe un bloque de memoria libre sobre el proceso, éste pasa aser utilizado, pero si no existe un bloque libre contiguo, es necesario hacer una reubicación delproceso creciente, con el consabido gasto de CPU. Entonces, es muy importante realizar unabuena asignación de memoria en la creación del proceso para minimizar las reubicaciones.

18

En cualquiera de estas estrategias cuando a una petición le es asignada una partición y sobramemoria el sistema operativo se da cuenta y deja a este espacio sobrante como una nuevapartición. Best FitLos bloques de memoria son asignados según las necesidades del programa que se estaejecutando. First FitAsignan la primera partición disponible en la que pueda entrar el programa. Esta estrategia esmas rápida pero se desperdicia mucho espacio de memoria. Worst FitConsiste en asignar la partición en la que sobra mas espacio.

Administración de Memoria VirtualLas direcciones de memoria no están necesariamente contenidas en el almacenamiento real.El S.O. se apoya en el almacenamiento secundario (el disco, por ejemplo) para extender el usode la memoria.Las direcciones referidas por los procesos son direcciones virtuales. Los procesos no tienenpor qué saber en que posición de almacenamiento real o secundario están almacenados. Lasdirecciones de memoria que referencian al almacenamiento primario (memoria real) sedenominan "direcciones reales". Por más que los procesos hagan referencia a direccionesvirtuales, estos solo pueden ejecutarse en el almacenamiento primario; por lo tanto lasdirecciones virtuales deben ser transformadas en direcciones reales mientras el proceso estáen ejecución.Como el almacenamiento real es compartido por varios procesos solo se mantiene al mismotiempo una pequeña parte de cada uno de ellos en memoria real.El mecanismo de traducción de direcciones deberá mantener mapas que ilustren quedirecciones del almacenamiento virtual se encuentran en memoria real, y donde se encuentran.La información se agrupa en bloques y el sistema operativo debe estar informado del lugar enque se encuentra almacenada cada página.Bloque: Cuando los bloques son del mismo tamaño se denominan páginas y el mecanismo deadministración del almacenamiento virtual asociado se denomina paginación. Si los bloques son de tamaño variable se denominan segmentos y el mecanismo deadministración del almacenamiento virtual segmentación.Las direcciones en un esquema de almacenamiento virtual son un par (b,d) donde b indica elbloque y d el desplazamiento desde el inicio del bloque.

PaginaciónLas direcciones en un sistema de paginación están dadas por el par: Desplazamiento PáginaLas páginas se transfieren del almacenamiento secundario al primario en bloques llamadospage frames (los cuales tienen el mismo tamaño de las páginas). El sistema lleva una tabla depáginas para cada proceso. De esta forma se asegura la protección.Cuando un proceso debe ser cargado en memoria para ser ejecutado se siguen determinadospasos: Se calcula su tamaño en páginas Se carga el programa en memoria Se construye la tabla de páginas del proceso Soporte de HardwareComo la tabla de páginas de cada proceso puede llegar a tornarse demasiado grande, sebuscan mecanismos que permitan acelerar el tiempo de búsqueda en esa información. Lasolución mas simple es la utilización de un conjunto de registros dedicados (no usar tabla depaginación de cada proceso). El CPU dispatcher será el encargado de cargar y actualizar lainformación de estos registros con cada conmutación de procesos. Esta solución seríarazonable si se hablara de pocos registros pero en la realidad no se utiliza.

19

La solución mas común es apoyarse en un cache de acceso muy rápido llamado TLB(Translation Location Buffer). La TLB solo puede contener algunas entradas de la tabla depáginas. Con cada conmutación de proceso la TLB debe ser variada para evitar que unproceso haga referencia a direcciones de memoria utilizadas por otro proceso (protección). Sise hace referencia a una dirección que no estaba cargada en TLB, se debe cargar en esta,eliminando alguna otra dirección si fuera necesario. ProtecciónPor la forma en que se construyen las tablas de páginas los procesos solo van a hacerreferencia a direcciones de su espacio virtual. La protección se implementa por un conjunto debits que son asociados a cada frame. Un bit puede definir si una página es read-only o read-write y cada vez que se hace una operación sobre un page frame se verifica sobre estos bits. Páginas CompartidasEs posible que los procesos compartan código común (reentrante). El código común no podráser modificado durante su ejecución, por lo cual se deberán proteger mediante los bits deprotección.

SegmentaciónEn un esquema de segmentación un espacio de direcciones lógic as es un conjunto desegmentos. Cada segmento tendrá un nombre y un largo. Las direcciones van a hacerreferencia tanto al nombre como al desplazamiento dentro del segmento.<nro. segmento, desplazamiento>Mecanismo de traducción de direcciones:Se lleva una tabla de segmento por cada proceso, cada entrada a la tabla de segmento lleva lasiguiente información: segment base (dirección base del segmento) segment limit (largo del segmento) ProtecciónLa protección se asegura verificando cada acceso a la memoria con la tabla de segmentospara asegurar que se está direccionando dentro del espacio de direcciones lógicas del proceso.Además el mecanismo de traducción de direcciones asegura que no se direcciones fuera de unsegmento en particular. Existen también bits de protección para cada entrada de la tabla desegmentos que indicaran si el segmento es read onlyo read-write. Segmentos CompartidosSimilar a lo visto para paginación. Se comparte la totalidad de un segmento

Paginación por demandaEs similar a lo visto para la paginación introduciendo el concepto de swapping. Los procesosresiden en el disco y al ser ejecutados deben ser cargados en memoria. Cuando un proceso vaa ser ejecutado, el mismo es swappeado a memoria, utilizando lazy swapping. El lazy swappingnunca trae páginas a memoria si no van a ser ejecutadas. Se necesita determinar si un páginaesta en memoria o en disco, por lo cual se utiliza el bit de válido/inválido de la tabla de páginas.Si el bit = 1 la página es valida y esta cargada en memoria si es 0 la página es inválida y noesta cargada en memoria (esta en disco).Cuando un proceso intenta acceder a una página que no esta cargada en memoria ocurre unpage fault (fallo de página). Los pasos para manejar un page fault son los siguientes:1. Verificar si la referencia a la página es valida (se utiliza una tabla interna generalmentellevada en PCB) donde se indica las páginas validas.2. Si la referencia no es válida, se suspende la ejecución del proceso.3. Encontrar un frame disponible para cargarla (la página esta en disco).4. Solicitar operación de E/S para leer la página de disco y cargarla en el frame obtenido.5. Modificar la tabla interna y la tabla de páginas para que ahora esta página figure enmemoria.6. Continuar con la ejecución del proceso en la instrucción en la que fue suspendido. Reemplazo de Página

20

Si al momento de generarse un page fault no hubiera ningún frame disponible, se debeproceder a reemplazar una página de memoria. La rutina de page fault debe ser modificadapara incluir reemplazo de páginas: Encontrar un frame disponible. Si hay un frame disponible usarlo. Si no hay frames disponibles utilizar un algoritmo de reemplazo de paginas paraseleccionar la víctima. Escribir la página víctima a disco y actualizar tabla de páginas.

Algoritmos de reemplazo de páginaPara poder seleccionar cuál va ser la página a eliminar de la memoria para ubicar una nueva,existen diferentes algoritmos. Vamos a estudiar los más comunes y ver sus implicancias en laperformance. Primero en entrar, Primero en Salir “FIFO” (Firs In First Out):Asocia a cada página el tiempo en que fue cargada en memoria. Cuando se debe reemplazaruna página, se selecciona la que hace más tiempo que está en memoria. El funcionamiento essimilar al de una cola de tamaño fijo, en la que cuando se necesita agregar un elemento, seagrega al final de la cola y se elimina el primer elemento de ella. Este algoritmo es muy sencillode implementar, pero no es funcional, dado que el hecho de que una página haya sido laprimera en ingresar no implica que vaya a ser la menos utilizada. Algoritmo de Segunda Chance:Es una variante del algoritmo FIFO con el adicional de mantener para cada página un bit dereferencia. Cada vez que se selecciona una página a reemplazar, se inspecciona el bit dereferencia. Si el valor es 0 se procede a reemplazar la página. Si el valor es 1, se da unasegunda oportunidad a la página y se selecciona la siguiente víctima por criterio FIFO. Cadavez que una página recibe una segunda oportunidad, se carga en 0 el bit de referencia. Si unapágina vuelve a ser accedida, se incrementa el bit de referencia a 1. De esta forma, una páginacon muchas referencias constantemente va a tener su bit de referencia en 1 y no va a serreemplazada. De Menor uso reciente “LRU” (Least Recently Used):Se selecciona la página que hace más tiempo que no se utiliza. Asocia a cada página el tiempode la última vez que fue utilizada. En LRU se necesita llevar tiempo de última utilización decada página: Contadores: Se asocia a cada entrada en la tabla de páginas, el tiempo de la última vez quese uso. Cada vez que se accede a una página se actualiza el contador. Stack: Se lleva un stack con los números de página, cada vez que una página es accedida,se quita del stack y se agrega al comienzo. En el tope del stack estará la página que fueutilizada por última vez, y en el fondo la página que hace más tiempo que no se accede.Este método es muy bueno y disminuye notablemente el Page Fault Frequency, pero esprácticamente irrealizable por su costo de implementación. De Menor Uso Frecuente “LFU” (Least Frequently Used):Establece que la página con menos cantidad de referencias debe ser reemplazada. Una contradel algoritmo es que una página puede haber sido muy utilizada en la fase de carga de unproceso, pero no ser vuelta a utilizar, por lo cual se estaría manteniendo en memoria páginasque no son necesarias para la ejecución. MFU (Most Frequently Used):La página con mayor cantidad de referencias es la víctima a ser reemplazada. El argumento esque si una página fue utilizada pocas veces, se debe a que recién fue cargada en memoria yaún deba ser utilizada. Este algoritmo tiene como desventaja que se van a eliminar las páginascon mayor cantidad de referencias, por lo tanto si tenemo s un proceso con repetidos accesosa una página, cada vez que la necesite ocurrirá un fallo. Este algoritmo no se utiliza en lapráctica. PFF (Page Fault Frequency):Se controla el page fault rate de cada proceso. Si un proceso tiene page fault rate muy bajoprobablemente se deba a que este utilizando demasiados frames en memoria. Si el page faultrate es muy alto, probablemente no tenga suficientes frames otorgados. La idea de esta técnicaes definir limite superior e inferior de page fault a cada proceso.

21

Working-Set:Cuando un proceso consume más tiempo paginando que ejecutando se dice que el procesoesta en situación de trash. Una forma de evitar esta situación es utilizar un mecanismo dereemplazo de páginas "local". Cuando un proceso comienza a paginar, no puede robar framesde otros procesos solamente podrá reemplazar páginas de su propio proceso. Un mecanismode reemplazo local es el que define un Working-Set:Es el conjunto de las páginas activas de un proceso que son almacenadas en memoria. Sedefine un número n por proceso. Las n páginas más activas del proceso son mantenidas enmemoria.

OptimizaciónTodo sistema operativo requiere un mantenimiento que debe ser realizado regularmente. CadaSistema Operativo tiene sus características de mantenimiento, pero en general, hay ciertastareas que se deben realizar en todos ellos.

Fragmentación de archivosEs una condición por la que los archivos en el disco se dividen en pequeños segmentosfísicamente separados entre si. Esta condición es una consecuencia natural del crecimiento delos archivos y de su posterior almacenamiento.Cuando el sistema operativo no puede seguir guardando los distintos segmentos de formacontigua debe fragmentar el archivo y guardarlo en posiciones no contiguas. La fragmentaciónde archivos no es un problema de integridad (el archivo no pierde nada de su contenido),aunque a veces puede ocurrir que los tiempos de acceso y de lectura aumenten si el disco estamuy fragmentado.Existen productos de software para organizar u optimizar el almacenamiento de archivos.

Compresión de datosTambién llamada compactación de datos. Es el término que se aplica a diversos métodos paracompartir la información a fin de permitir una transmisión o almacenamiento más eficaces. Lavelocidad de compresión y descompresión y el porcentaje de compresión (la relación entre losdatos comprimidos y sin comprimir) dependen del tipo de los datos y el algoritmo utilizado. Unatécnica de compresión de archivos de texto, la llamada codificación de palabras clave, sustituyecada palabra que aparece con frecuencia como por ejemplo el o dos por un puntero (uno o dosbytes) a una entrada de una tabla (que se guarda en el archivo) de palabras. Las técnicas decompresión fuzzy, utilizadas en compresión de audio y vídeo (por ejemplo JPEG, MP3), tienenun porcentaje de compresión muy elevado (10 a 1), pero son técnicas destructivas, es decirque en la compresión se pierde información y no permiten recuperar exactamente el original.

Administración de memoriaSea cual sea el esquema de organización del almacenamiento que se adopte para un sistemaespecífico, es necesario especificar qué estrategias se deben utilizar para obtener unrendimiento óptimo. Las estrategias de administración del almacenamiento, determinan elcomportamiento de una organización de almacenamiento determinada cuando se siguendiferentes políticas: ¿Cuándo se toma un nuevo programa para colocarlo en la memoria? ¿Setoma el programa cuando el sistema lo solicita específicamente o se intenta anticiparse a laspeticiones del sistema? ¿En que lugar del almacenamiento principal se coloca el siguienteprograma por ejecutar? ¿Se coloca los programas lo más cerca posible uno del otro en losespacios disponibles de la memoria principal para reducir al mínimo el desperdicio de espacio,o se colocan los programas lo más rápido posible para reducir al mínimo el tiempo deejecución?.