Respaldo y Recuperacion, Sistemas de Archivo, Tendencias SO

– Chequeo de consistencia – compara los datos en la estructura del directorio con los bloques de datos en disco, y trata de arreglar inconsistencias.

– Uso de programas del sistema para sacar backup de los datos de disco a otro dispositivo de almacenamiento (disquete, cinta, etc).

– Recuperación de archivos perdidos o disco al recuperar datos desde el backup.

– Respaldo total vs respaldo incremental.

Esquema Abuelo-padre-hijo.

• D1….D4
• S1….S3
• M1….M5
• S1
• A1….

Otros esquemas de respaldo y recuperación

• Protección a nivel de disco: Múltiples copias de FAT; arreglo en caliente para detección y corrección de bloques malos.
• Duplexión.
• Disco espejo.
• Sistemas RAID: Redundant array of inexpensive/independent disks. Conjunto de drives que aparecen como uno solo. El nivel de redundancia depende del nivel RAID.

RAID 0

 

Data Stripping without parity (DSA). Datos copiados en distintos discos sin redundancia, datos en banda de discos sin paridad sin corrección de errores, no tolerancia a fallos, se aprovecha todo el disco.

RAID 1 (Espejo)

Mirrored Disk Array (MDA). Los datos son copiados en un arreglo de drives y cada drive tiene su backup espejo. Cuando se describen datos en una unidad, también se escriben con la otra. El disco redundante es una réplica exacta del disco de datos, por lo que se conoce también como disco espejo. Caro ya que necesitamos el doble de espacio que el necesario.

RAID 2 (Redundancia por código Hamming)

Datos copiados a nivel de bit en todos los drives. No usado. Este nivel cuenta con varios discos para bloques de redundancia y corrección de errores. La división es a nivel de bits, cada byte se graba con un bit cada uno de los discos y un bit de paridad en el noveno y el acceso es simultáneo a todas las unidades tanto en operaciones de escritura como lectura.

RAID 3 (bit de paridad intercalado)

Datos copiados a nivel de bit o byte en todos los drives excepto uno que es el drive de paridad. Lento escritura. Utiliza también un disco de protección de información separado para almacenar información de control codificada con lo que se logra una forma más eficaz de proporcionar redundancia de datos. Este control de información codificada o paridad proviene de los datos almacenadas en los discos y permite la reconstrucción de información en caso de fallas. Se requieren como mínimo 3 discos y se utiliza la capacidad de un disco para la información de control.

RAID 4 (Paridad a nivel de bloque)

Independient Disk Array (IDA) Similar al anterior pero a nivel de sectores, mejora rendimiento. En este nivel los bloques de datos pueden ser distribuidos a través de un grupo de discos para reducir el tiempo de transferencia y explotar toda la capacidad de transferencia de datos de la matriz de disco. El nivel 4 de Raid es preferible al nivel 2 de Raid para pequeños bloques de datos, porque en este nivel, los datos son distribuidos por sectores y no por bits.

RAID 5 (Paridad distribuida a nivel de bloque)

Datos escritos a nivel de sectores. Se incluyen códigos de corrección de error en todos los drives. Los datos y la paridad son guardados en los mismos discos por lo que conseguimos aumentar la velocidad de demanda, ya que cada disco puede satisfacer una demanda independiente de los demás. A diferencia del RAID 3, el RAID 5 guarda la paridad del dato dentro de los discos y no hace falta un disco para guardar dichas paridades.

RAID 6 (Redundancia dual)

Sistemas independientes de disco con integración de código de error mediante una doble paridad. Es esencialmente una extensión del RAID 5, para ello guarda, una segunda paridad. Este nivel proporciona muy buena integridad de los datos y repara diversos errores en los discos. Añade un nivel más de disco, resultando una organización con dos dimensiones de disco y una tercera que corresponde a los sectores de los discos la ventaja de este nivel consiste que no solamente se puede recuperar un error de entre dos discos, sino que es posible recuperar muchos errores de 3 discos. La operación de escritura es difícil debido a la necesidad de sincronizar todas las dimensiones.

RAID de nivel superior

• RAID 10:  La información se distribuye en bloques como el RAID 0 y adicionalmente, cada disco se duplica como RAID 1, creando un segundo nivel de arreglo se conoce como “Strippng de arreglos duplicados”. Se requieren dos canales, dos discos para cada canal y se utilizan el 50% de la capacidad para información de control.
• RAID 30: ES ideal para aplicaciones no interactiva, tal como señales de gráfico e imágenes. Se conoce también como Stripping de arreglos de paridad dedicada. La información es distribuida a través de los discos, como en RAID 0 y utiliza paridad dedicada, como RAID 3, en un segmento canal, requiere mínimo 6 discos.
• RAID 50: Está diseñado para aplicaciones que requieren un almacenamiento altamente confiable una elevada tasa de lectura y un buen rendimiento en la transferencia de datos con un nivel de RAID 50, la información se reparte en los discos y se usa paridad distribuida, por eso se conoce como Stripping de arreglo de paridad distribuidas. Se requiere mínimo 6 discos.

 

 

 

RAID 10

SISTEMAS DE ARCHIVOS DE ALGUNOS SOS

El sistema de archivos determina la forma como se nombran los archivos, como se ubican en los dispositivos de

 

TENDENCIAS EN SISTEMAS OPERATIVOS

–        Las principales abstracciones de hoy día: procesos, hilos, sockets, y archivos no manejan adecuadamente los problemas de administración de la localidad, disponibilidad y tolerancia a fallos. Los sistemas operativos distribuidos pueden resolver estos problemas.

–        Cualquier fragmento de código debe poder correr en cualquier parte.

–        El sistema debe manejar localidad, replicación y migración de datos y operaciones.

–        Los SO del futuro de3ben estar listos para internet, comercio electrónico, intranet/extranet, operaciones basadas en internet, servidores de correo electrónico, web, servicios web, etc.

–        El sistema debe ser:

• Auto configurable.
• Autoajustable.
• Automonitoreable.
• Escalable.
• Confiable.
• Seguro.
• Robusto.
• Escalable (a nivel mundial).
• Tolerante a fallos.
• Persistente.
• Preparado para la red.
• Favorable a la movilidad.
• Extensible.
• Orientado a objetos.
• Orientado a GUI.
• Mayores longitudes de palabra.
• Ambientes multitarea.
• Reconocimiento automático de componentes.
• Autodiagnostico.
• RISC.
• Múltiples ambientes operativos.
• Múltiples idiomas.
• Kernel paginable.
• Interoperatividad.
• Procesamiento paralelo.
• Dispositivos ópticos multiescritura.
• Gestión de comunicaciones y bases de datos de Kernel.
• Configuración en caliente.
• Registro y seguimiento de operaciones, log, journal.
• Abstracción agresiva.
• Irrelevancia en el almacenamiento.
• Irrelevancia en ubicación.
• Vinculación justo a tiempo.
• Introspección.
• Gran semántica.
• Arquitecturas descentralizadas: Mejora relación precio beneficio PC- redes.
• Estándares.

Elementos de la Administración de Archivos

Un disco no se lee por bytes ni por bits. El disco se lee por sectores.

Las organizaciones posibles de archivos: Archivo apilado, pila, secuencial, secuencial indexado, directorio/aleatorio, particionado.

Métodos de acceso: pila, secuencia, secuencial indexado, directorio/aleatorio

Atributos de los archivos

• Nombre simbólico: información en forma legible por los humanos
• Tipo: diferencia los archivos dentro de un sistema.
• Ubicación: señalador de ubicación del archivo en un disco
• Tamaño:
• Protección: controla quien puede leer, escribir o ejecutar
• Hora, fecha e identificación de usuario: datos para protección, seguridad y monitoreo de uso.
• Organización
• Tipo de dispositivo
• Tipo (archivos de datos, prog objeto, cola, etc.)
• Tratamiento (temporal o permanente)
• Conteo de actividad
• La información acerca de los archivos se guarda en la estructura del directorio, que se guarda en disco

Estructura de Directorio

• Una colección de nodos que contienen información acerca de todos los archivos

• Tanto la estructura de directorio como los archivos residen en disco.
• Las copias de estas dos estructuras se mantienen fuera de línea.

Los directorios o catalogo es una agrupación lógica de archivos, es decir, contiene la lista de la ubicación de archivos. Una librería es una agrupación física de archivos.

Elementos de información de un directorio.

Directorio de nivel simple

El primer tipo de directorio que se tiene es el Directorio Simple

• Un solo directorio para todos los usuarios
• Problemas de denominación
• Problemas de agrupamiento

Directorio en dos niveles

• Separar los directorios por usuario
• Mejora sustancialmente, tiene una capa del usuario y una capa donde ese encuentra el archivo. Pero sigue con problemas ya que el usuario no puede tener dos archivos con el mismo nombre

Directorios estructurados en árbol

Los que usa Windows. En el nodo está el archivo, puede bajar los niveles que quiera. Esta estructurada es útil para manejar agrupamiento

Para buscar archivos se navega por el árbol, se que llego el fondo cuando encuentro una hoja. Para referirme a un archivo tengo que direccionar toda la trayectoria.

 

Arquitectura Software de un Sistema de Archivos

Atributos de los Archivos

• Nombre Simbólico: Información en forma leible por los humanos.
• Tipo: Diferencia los archivos dentro de un sistema.
• Ubicación: Señalador de ubicación del archivo en un dispositivo.
• Tamaño
• Protección: Controla quien puede leer, escribir o ejecutar.
• Hora, Fecha e identificación de Usuario: Datos para protección, seguridad y monitoreo de uso.
• Organización
• Tipo de Dispositivo
• Tipo (archivos de datos, programa objeto, cola, etc.)
• Tratamiento (temporal o permanente)
• Conteo de Actividades
• La información acerca de los archivos se guarda en la estructura del directorio, que se guarda en el disco.

Estructura de Directorio

• Una colección de nodos que contienen información acerca de todos los archivos.

• Tanto la estructura de directorio como los archivos residen en disco.
• Las copias de estas dos estructuras se mantienen fuera de línea.

Elementos de información de un directorio

Directorio de nivel simple

• Un solo directorio para todos los usuarios.

• Problemas de denominación.
• Problemas de agrupamiento.

Directorios estructurados en árbol

• Búsqueda eficiente.
• Capacidad de agrupamiento.
• Directorio actual (directorio de trabajo).

• Trayectoria absoluta o relativa.
• La creación de un nuevo archivo se hace en el directorio actual.

Directorio en Grafos Acíclico

• Tiene subdirectorio y archivos compartidos.
• Este concepto no existe en Windows.
• Dos nombres diferentes (alias).

Directorio de grafo General

• Como podemos evitar los ciclos:
  • Permita solo enlaces a los archivos no a los directorios.
  • Usar el recolector de basura.

Asignación de espacio para archivos

• Contigua, Enlazada, Indexada

Contigua

• Cada archivo ocupa un conjunto de bloques contiguos en el disco.
• Se asigna un unico conjunto contiguo de bloques en tiempo de creación.
• Simple-Solo se requiere la ubicación inicial (nro de bloque) y la longitud (nro de bloques)
• Existirá fragmentación externa.
• Desperdicio de espacio (problema con la asignación dinámica del espacio).
• Los archivos pueden crecer.

Asignación enlazada/encadenada

• Cada archivo es una lista enlazada de bloques de disco: los bloques pueden estar dispersos en cualquier parte del disco.
• En lo que respecta a la administración de espacio libre, no hay desperdicio de espacio.
• No hay acceso aleatorio.
• No hay fragmentación externa.
• Se adapta mejor a archivos secuenciales.

Asignación indexada

Ubicación indexada

• Requiere de tabla índice.
• Acceso aleatorio.
• Acceso dinámico sin fragmentación externa, pero hay sobrecosto en el bloque de índice.
• Qué tan grande debe ser el bloque índice
  • Lo suficiente para contener los distintos índices:
    • Esquema enlazado: Dentro del bloque las últimas direcciones indican otros bloques de dirección.
    • Indice multinivel: Bloque índice de primer nivel y de segundo nivel, el tercero es el de datos. Con 4096 de tamaño de bloque se tienen 1024 punteros de 4 bytes que apuntarían a 1048576 bloques de datos o 4 GB de datos.
    • Esquema combinado: Ej. 17 punteros de bloque en el bloque índice o I-nodo. Los primeros 12 son directos, 3 a bloques indirectos, luego un indirecto doble, e indirecto triple.

Dispositivo de un archivo UNIX en un disco (4K por bloque)

almacenamiento= 10 directo*4kB + 1 indirecto simple* 1024*4kB+indirecto doble*1024*1024*4k+1 indirecto triple*1024*1024*1024*4KB

Descripción física en UNIX (nodo-i)

C=R*Tb+S*(Tb/A)*Tb+D*(Tb/A)^2*Tb+T*(Tb/A)^3*Tb+Q*(Tb/A)^4*Tb

C= Almacenamiento archivo/ Tamaño máximo del archivo

Tb= Tamaño bloque ->4k

A= dirección en bytes ->4

R= directas

S= direcciones simples

D= direcciones dobles

T= direcciones triples

Q= direcciones cuadruples

Ejemplo:

Que capacidad máxima de almacenamiento puedo tener si tengo un sistema de almacenamiento en disco de archivo combinado en el cual se tienen 12 bloques directos, un indirecto simple, dos indirectos dobles y tres indirectos triples. El tamaño del bloque es de 4Kbytes, el tamaño de la dirección es de 4 byte.

c=12*4000+1*(4000/4)*4000+2*(4000/4)^2*4000+3*(4000/4)^3*4000

48kb+4mb+8gb+12tb

48kb+4096kb+8388608kb+

ADMINISTRACION DEL ESPACIO LIBRE

 

El mapa de bits requiere de espacio extra, ejemplo :Tamaño de bloque = 2^12 bytes

Tamaño del disco = 2^30 bytes(1GB)

n = 2^30/2^12 = 2^18 bits (32KB)

Politicas de Recuperacion

• Política de recuperación

– Determina cuándo una página se debería traer a la memoria principal

– Con paginación bajo demanda (demand paging), una página trae a memoria sólo cuando se hace referencia a una posición en dicha página.

•Se producen muchos fallos cuando un proceso se arranca inicialmente

– Con paginación adelantada (preparing), se traen a memoria más páginas de las que se necesitan.

Algoritmos de reemplazo de páginas

•Las faltas de página forzan el cambio

–Que página debe ser removida

–Establecer espacio para la página que entra

•Las páginas modificadas deben ser guardadas las otras pueden sobreescribirse

–Es aconsejable no reemplazar una página usada con frecuencia, seguramente la necesitaremos.

Algoritmo optimo de reemplazo de página

•Reemplaza la página que se requerirá en el punto mas lejano

–Optimo pero no lograble

•La estimación se basa en el registro de uso de las corridas anteriores de los proceso.

•Sigue siendo poco práctico

Algoritmo de página no recientemente usada (NRU)

•Cada página tiene un bit de referencia , un bit de modificación

•Las páginas se clasifican

1.No referenciadas, no modificadas

2.No referenciadas, modificadas

3.Referenciadas, no modificadas

4.Referenciadas, modificadas

•NRU  remueve las páginas aleatoriamente desde el número mas bajo en clases no  vacias.

FIFO(First-In, First-Out)

•Conserva una lista encadenada de todas las páginas en el orden en que llegaron a la memoria.

–Trata los marcos de página ocupados como si se tratase de un buffer circular

–Las páginas se remplazan mediante una estrategia cíclica de tipo round-robin

–Es una de las políticas de reemplazo más sencilla de implementar

–Se reemplaza la página que lleva en memoria más tiempo

–Estas páginas podrían necesitarse de nuevo muy pronto

•

•Se reemplazan las páginas al principio de la lista

•Desventaja

–Las páginas que mas esten en la memoria no necesariamente son las mas usadas

Reloj, Segunda oportunidad

LRU(Least Recently Used )

•Asume que las páginas recientemente usadas serán usadas de nuevo, elimina las páginas que no han sido usadas por mucho tiempo.

• Reemplaza la página que no se haya referenciado desde hace más tiempo

•Por el principio de proximidad referenciada, esta página sería la que tiene menos probabilidad de volver a tener referencias en un futuro próximo

•Debe conservar una lista de páginas enlazadas

–Las páginas usadas recientemente de primeras y las menos usadas de últimas.

–Actualiza estos enlaces en cada referencia de memoria

•De forma alternativa puede llevar un contador en cada entrada de la tabla de páginas, seleccionando la página con el menor valor.

–Cada página podría etiquetarse con el instante de tiempo de su última referencia. Esto podría suponer una gran sobrecarga

Algoritmo del conjunto de trabajo

•El conjunto de trabajo se refiere al conjunto de páginas usadas por las k referencias de memoria mas recientes.

•w(k,t)  es el tamaño del conjunto de trabajo en el tiempo t.

Algoritmo del conjunto de trabajo

Reloj mejorado

Se toma el algoritmo del reloj pero con los 2 bit, el de referencia y el de modificación:

0,0 No referenciadas, no modificadas

0,1 No referenciadas, modificadas

1,0 Referenciadas, no modificadas

1,1 Referenciadas, modificadas

Se reemplaza el de la clase mas baja (Macintosh)
Otros algoritmos de reemplazo de paginas M

Aleatorio (Random): Reemplaza las paginas de forma aleatoria, se trabaja en el OS/360 cuando se degenera el LRU,también se uilizo en extinto i860 de intel(risc).

No frecuentemente usada (NFU) :C/pagina tiene un contador , en cada intervalo de reloj se incrementa en 1 el contador de las paginas  referenciadas, así cuando se requiere intercambio se saca la de menor contador.

Envejecimiento(Aging): Similar al anterior pero tiene en cuenta el tiempo, primero se desplaza a la derecha(/2) antes de incrementar. Con lo cual se compensan las paginas mas recientemente usadas.

•La menos usada fecuentemente (LFU): Reemplaza la pagina que menos intensivamente ha sido referenciada, se basa en la heuristica de que una pagina no referenciada con frecuencia es probable que no sea referenciada en el futuro.

•Reemplazo de pagina mas lejana FPR (Far page replacement) : Crea un grafo de acceso que caracteriza los patrones de referencia de un proceso. Reemplaza la pagina no referenciada que esta mas lejana de cualquier pagina referenciada en el grafo de acceso. Es compleja de manejar sin soporte en hw, no ha sido implementada en sistemas comerciales.

Windows XP

•Utiliza paginación por demanda con clustering.El agrupamiento trae las paginas alrededor de la pagina fallada.

•A los procesos se les asigna un working set minimum y un working set maximum.

•El conjunto de trabajo minimo  es el número de paginas que se le garantiza a un proceso tener en memoria.

•A un proceso se le pueden asignar tantas paginas hasta alcanzar su conjunto de trabajo maximo.

•Cuando la cantidad de memoria en el sistema cae por debajo de un umbral, se realiza un recorte automatico del conjunto de trabajo para recuperar memoria disponible.

•Este recorte  remueve las paginas de exceso de los procesos que estan sobre su conjunto de trabajo minimo.

Solaris

•Mantiene una lista de paginas libres para asignarle a los procesos con faltas de pagina.

•Lotsfree –parametro umbral(cantida de memoria) para empezar a paginar.

•Desfree – parametro umbral para incrementar la paginación

•Minfree – parametro umbral para empezar el intercambio

•La paginación es realizada por el proceso pageout

•Pageout busca las paginas utilizando el algoritmo del reloj modificado.

•Scanrate es la velocida con la cual las paginas son buscadas. Varia de slowscan a fastscan.

• Pageout se utiliza con mas frecuencia de acuerdo a la cantidad de memoria libre disponible.

Reemplazo de paginas en Linux

•Linux utiliza una variante del algoritmo del reloj para aproximarse a la estrategia de reemplazo de paginas LRU.

•El Administrador de memoria utiliza dos listas enlazadas

–La lista activa

TContiene las paginas activas

TLas paginas mas recientemente usadas estan cerca de la cabeza de la lista de activas.

–La lista de inactivas

TContiene las paginas inactivas

TLas paginas menos recientemente usadas estan cerca de la cola de la lista de paginas inactivas

–Solo se reemplazan las paginas en la lista de inactivas

Almacenamiento Secundario, Características de Discos, Planificación de Disco, Algoritmos de Planificación de Disco

Parámetros

Características de discos sobre distintos dispositivos

Ejemplo de disco duro

Planificación del disco

• El sistema operativo es responsable por el uso eficiente del hw- para los discos duros, esto significa tener un tiempo de acceso mas rápido y un mayor ancho de banda para el disco.
• El tiempo de acceso tiene dos componentes principales
  • El tiempo de búsqueda es el tiempo en el que el disco debe mover las cabezas hasta el cilindro que contiene el sector deseado.
  • Latencia rotacional es el tiempo adicional de espera para que el disco rote sus cabezas hasta el sector deseado.
• Minimizando el tiempo de búsqueda
• El ancho de banda del disco es el nro total de bytes transferidos, dividido por el tiempo total entre la primera solicitud del servicio y el completado de la transferencia.
• Existen diversos algoritmos para planificar el servicio de las solicitudes de entrada y salida del disco.
• Las ilustraremos con una cola de solicitudes (0-199).
  98, 183, 37, 122, 14, 124, 65, 67Puntero de la cabeza 53

FCFS (First come first serve)

La ilustración muestra el movimiento total de la cabeza de 640 cilindros.

SSTF(Shortest seek time first)

La ilustración muestra el movimiento total de la cabeza de 236 cilindros.

SCAN

La ilustración muestra un total de 208 movimientos de la cabeza.

SCAN de N pasos

C-SCAN

Trata los cilindros como una lista circular que se envuelve desde el último cilindro al primero.

C-LOOK

El brazo solo va tan lejos como este la última solicitud en cada dirección, entonces se devuelve sin ir al extremo.

Comparativo de rendimiento de algoritmos de planificación de disco

Selección de Algoritmos de planificación de disco

Buffer de Traducción Anticipada (TLB)

• La tabla de páginas se mantiene en memoria principal.
• El registro base de la tabla de páginas (PTBR) señala la tabla de páginas.
• El registro de longitud de tabla de páginas (PRLR) indica el tamaño de la tabla de páginas.
  • Uno para buscar en la tabla de página apropiada.
  • Uno para buscar los datos solicitados.
• Para solventar este problema, la mayoría de esquemas de memoria virtual utilizan una caché especial de alta velocidad para las entradas de la tabla de página.
  • Se le denomina buffer de traducción anticipada ( Translation Lookaside Buffer (TLB)), también llamado registros asociativos.
• Contiene aquellas entradas de la tabla de páginas que han sido usadas de forma más reciente.
• Dada una dirección virtual, el procesador primero examina la TLB.
• Si la entrada de la tabla de páginas solicitada está presente (acierto en TLB), entonces se recupera el número de marco y se construye la dirección real.
• Si la entrada de la tabla de páginas solicitada no se encuentra (fallo en la TLB), el procesador utiliza el número de página para indexar la tabla de páginas del proceso.
• Primero comprueba si la página solicitada está todavía en la memoria principal
  • Si no se encuentra en la memoria principal, se produce un fallo en la memoria, llamado fallo de página.
• La TLB se actualiza para incluir esta nueva entrada de tabla de páginas.

Operación de paginación y TLB

Registros asociativos/Tiempo de acceso efectivo sin intercambio

Sea:

• E=Tiempo de búsqueda asociativa.
• t=Tiempo ciclo de memoria, tiempo de acceso a un dato en memoria.
• a=Tasa de aciertos: porcentaje de veces que un número de página se encuentra en los registros asociativos; está relacionada con el número de registros asociativos.
• EAT=Tiempo de acceso efectivo

EAT=(t+E)a + (2t+E)(1-a)

Traducción de direcciones (A’,A”…)

• Si A’ es un registro asociativo, saque el marco #.
• De otra forma obtenga el marco # de la tabla de páginas de memoria.

Esquema de tablas de páginas de dos niveles

Ventajas de tablas multinivel

Si un proceso usa una parte pequeña de su espacio lógico: Ahorro en espacio para almacenar TPs.

Sea un proceso con dir lógica de 32b de 2 niveles (10b cada nivel), TP de 4KB, entrada a TP es 4B.

Si el proceso usa 12 MB superiores y 4MB inferiores:

Tenemos

Cada página N2 direcciona 4MB

Tamaño tablas de página:

1 TP N1 + 4 TP N2=5*4KB=20KB (frente a 4MB si utilizará todas las páginas).

• Una dirección lógica  (en una máquina de 32 bit con tamaño de página de 4K) está dividida en:
  • Un número de página de 20 bit.
  • Un desplazamiento de página de 12 bit.
• Dado que la tabla de páginas es paginada, el número de página adicionalmente se divide en:
  • Un numero de página de 10 bits.
  • Un desplazamiento de página de 10 bit.
• Así, la dirección lógica es como sigue:

Paginación multinivel y rendimiento (sin intercambio)

Establecer el EAT para un procesador con 4 niveles de paginación con tiempo de acceso a memoria de 100ns, tiempo de búsqueda es de 20ns y una tasa de aciertos en caché de 98%

Para 4 nivele de paginación

Dado que cada nivel es almacenado como una tabla separada en memoria, el convertir una dirección lógica a una física requiere 4 accesos a memoria. No obstante el tiempo requerido para el acceso a memoria es quintuplicado, el caché permite que el rendimiento permanezca razonable.

Si t=100ns,E=20ns,a=98% da:

Tiempo de acceso efectivo=(t+E)a + ((n+1)t+E)(1-a)

EAT=120*0.98+520*0.02=128ns

Que es solamente un 28% de reducción en tiempo de acceso a memoria.

Rendimiento en paginación por demanda con intercambio

• Tasa de fallo de página 0<=p<=1.0
  • si p=0 no hay fallo de página
  • si p=1,cada referencia es un fallo de página.

Tiempo de acceso efectivo con intercambio

EATS=(1-p)*t+p*f

f:el tiempo de fallo de página.

Tamaño de páginas

SEGMENTACIÓN

• Esquema de administración de memoria que soporta la visión del usuario de la memoria.
• Un programa es una colección de segmentos. Un segmento es una unidad lógica como por ejemplo:
  • Programa principal.
  • Procedimientos.
  • Funciones.
  • Variables locales, variables globales.
  • Bloques comunes.
  • Pila.
  • Tabla de símbolos, arreglos,etc.

 

Esquema de traducción usando segmentación

 

Vista lógica de la segmentación

Tabla de correspondencia de segmentos

Dirección virtual=(s,d), los segmentos se intercambian como unidades.

Programa: núcleo principal, rutinas, datos(tablas,pilas, etc).

r=0 si segmento no está en real, 1 si está.

Bits de protección: 1-si 0-no.

R-acceso lectura, W-escritura, E-ejecución, A-adición.

Arquitectura de la segementación

• Las direcciones lógicas se conforman por una dupla: <Número del segmento, Desplazamiento>
• Tabla de segmento: Mapea direcciones físicas de dos dimensiones; cada entrada de tabla tiene:
  • Base: Contiene el principio de la dirección física donde reside el segmento en memoria.
  • Límite: Especifica la longitud del segmento.
• Registro base de la tabla de segmentos (STBR) señala a la ubicación en memoria de la tabla de segmentos.
• Registro de longitud de la tabla de segmentos (STLR) que indica el número de segmentos usados por el programa. El número de segmentos es válido si s<STLR.
• Dado que un segmento varía en longitud, la ubicación de memoria es un problema de ubicación dinámica de memoria.

 

Segmentos compartidos

 

Segmentación con paginación

• La segmentación con paginación intenta aunar lo mejor de los dos esquemas anteriores.
• La segmentación proporciona soporte directo a las regiones del proceso y la paginación permite un mejor aprovechamiento de la memoria y una base para construir un esquema de memoria virtual.
• Un segmento está formado por un conjunto de páginas y, por tanto, no tiene que estar contiguo en memoria.
• La MMU utiliza una tabla de segmentos, tal que cada entrada de la tabla apunta a una tabla de páginas.
• Requiere un hardware más complejo.
• El sistema Multics resolvió la fragmentación externa y largos tiempos de búsqueda  paginando los segmentos.
• Esta solución difiere de la segmentación pura en que la entrada de la tabla de segmentos no contiene la dirección base de la tabla de páginas para este segmento.

 

Traducción dinámica de direcciones en sistema segmentado/paginado con TLB

 

Segmentación con paginación Pentium

El pentium soporta 16K segmentos, cada uno  hasta 2^32 bytes de direccionamiento virtual. Puede determinarse por S.O usar solo segmentación, solo paginación o ambos.

 

 

Problema de la asignación dinámica de memoria

Partición variable

Compresión/compactación de memoria

Problema de la asignación dinámica de la memoria

Cómo satisfacer la solicitud de un tamaño n a partir de huecos libres.

Estrategias de colocación:

• Mejor ajuste: hueco que mejor quepa y menor desperdicio. Busca en toda la lista (puede estar ordenada).
• Primer ajuste: El primer hueco que le sirva. Búsqueda al principio o a partir de este punto.
• Peor ajuste: Hueco más grande.
• Siguiente ajuste.
• Estrategia más sofisticada: Sistema Buddy.
  • Listas de huecos con tamaños potencias de 2.

El primer ajuste y el mejor ajuste son mejores que el peor ajuste en términos de velocidad y utilización de almacenamiento.

Primer ajuste

Mejor ajuste

Peor ajuste

Sistema Buddy

• El espacio completo  disponible se trata como un único bloque de tamaño 2U.
• Si se realiza una petición de tamaño s, tal que 2U-1<s<=2U, se asigna el bloque entero
  • En otro caso, el bloque se divide en dos bloques buddy iguales de tamaño.
  • El proceso continúa hasta que el bloque más pequeño mayor o igual que s se genera.

Almacenamiento virtual

• Capacidad de obtener acceso a direcciones en un espacio de almacenamiento mucho mayor que el disponible en el almacenamiento primario del sistema.
• SO Atlas, Manchester 1960.
• Disociación de las direcciones (V) a las que hace referencia un proceso en ejecución de las direcciones disponibles en el almacenamiento primario (R).
• Las direcciones calculadas por procesos no necesariamente las disponibles en el almacenamiento primario

Dirección real: Dirección disponible en memoria.

Dirección virtual: Direcciones usadas por procesos.

Intercambio/swap

• Un proceso puede intercambiarse temporalmente de memoria a un almacenamiento de respaldo y luego puede ser retomado hacia la memoria para continuar su ejecución.
• El almacenamiento de respaldo se hace en el disco, que debe ser rápido y tener suficiente espacio par ubicar copia de todas las imágenes de memoria para todos los usuarios; debe proveer acceso directo a estas imágenes de memoria.
• Descargar (swap out), cargar (swap in): Variante de intercambio en algoritmos de planificaciones de prioridad; los procesos de baja prioridad se sacan de memoria de tal forma que los procesos de mayor prioridad puedan ser cargados y ejecutados.
• La mayor parte del tiempo es tiempo de transferencia; este es directamente proporcional a la cantidad de memoria intercambiada.
• Existen versiones modificadas de intercambio en los diferentes sistemas por ejemplo, Unix, Linux y Windows.

Vista esquemática del intercambio

 

Fundamentos de memoria virtual

• El procesador utiliza y genera direcciones virtuales.
• Parte del mapa de memoria (virtual) está en disco (swap) y parte en memoria principal.
• La MMU (memory management unit) traduces las direcciones virtuales en físicas.
• La MMU produce un fallo de página (trap) cuando la dirección no está en memoria principal.
• El SO trata el fallo de página, haciendo un transvase entre la memoria principal y el área de intercambio (swap disco).

En el esquema de MMU, el valor del registro de reubicación se suma a cada dirección generada por el proceso de usuario al momento de ser enviado a la memoria.

El programa del usuario se preocupaba de las direcciones lógicas; nunca tenía que preocuparse por las direcciones físicas.

Almacenamiento virtual

• Espacio de direcciones virtuales, V: espacio de direcciones a las que puede hacer referencia un proceso.
• Espacio de direcciones reales, R: Almacenamiento físico disponible, en general V>>R.
• Traducción dinámica de direcciones (DAT): V===>R.
• Mapa de correspondencia de traducción de direcciones: por bloques=s páginas, <> segmento.
• Direccionamiento bidimensional: Bloque, desplazamiento.

Evolución de las organizaciones de memoria

DISTRIBUCIÓN DE ALMACENAMIENTO POR PROCESOS

Paginación

• El espacio de direcciones lógicas de un proceso no necesariamente es contigua; los procesos se ubican en memoria física donde luego quedan disponibles.
• Se divide la memoria física en bloques de tamaño fijo llamados marcos (los tamaños son potencias de 2, entre 512 bytes y 8192 bytes).
• Se divide la memoria lógica en bloques del mismo tamaño llamados páginas.
• Se mantiene el rastro de todos los marcos.
• Para correr un programa de tamaño n páginas, se requiere encontrar en marcos libres y cargar el programa.
• Se debe poner a punto una tabla para traducir las direcciones físicas a las lógicas.
• Se puede presentar fragmentación interna.

División de páginas de los espacios de memoria

El espacio virtual se divide en páginas.

Algunas páginas están en la memoria principal

• El SO se encarga de que estén en memoria principal las páginas necesarias.
• Para ello trata los fallos de página producidos por la MMU.

Esquema de traducción de direcciones

• Las direcciones generadas por la CPU se dividen en:
  • Número de página (p): utilizado en la tabla de páginas que contiene las direcciones base de cada página en la memoria física.
  • Desplazamiento de página (d): Combinado con la dirección base definen la dirección de memoria física que es enviada a la unidad de memoria.
• Traducción: proceso referencia (p,d), se busca en la tabla de correspondencia de páginas para ver la p’ (p real), la dirección real es p´+d. Por agilidad tabla de correspondencia en caché.
• Si no hay residencia de la página en memoria principal, sucede una falta de página. r=0 si página no está en real, 1 si está.

Traducción de direcciones en paginación

Ejemplo de paginación

Elementos de la tabla de páginas

• Otras informaciones
  • Copia en escritura.
  • Edad.
  • No página (fija en memoria física).
  • Rellenar a ceros.

Ejemplo de traducción con tablas de páginas

 

 

Administración de Memoria

• Los programas deben ser llevados a la memoria y convertirse en procesos para ser ejecutados
• Cola de entrada- colección de programas en disco que esperan para ser llevados a la memoria para ejecución
• La parte del sistema operativo que administra la memoria se llama administrador de memoria.

Requerimientos de memoria MS Windows
■ Windows 1.0 salió el 20 de noviembre de 1985.
* CGA/Hercules/EGA (o compatible)
* MS-DOS 2.0
* 256 KB Ram
* 2 unidades de dos lados cada una o un disco duro

■ Windows 2.1 fue lanzado el 27 de mayo de 1988.
Algo interesante: las versiones 2.1 fueron lanzados para que se pueda tomar ventaja del procesador 286 de Intel.
* MS-DOS version 3.0 or más
* 512 KB de RAM
* Un disco floppy y un disco duro
* Tarjeta de adaptador de gráficos
* Mouse opcional

■ Windows 3.1x
Varias versiones de Windows 3.1 fueron lanzadas entre 1992 y 1994.
Lo que fue diferente con esta versión de Windows es que si un usuario estaba utilizando un sistema operativo diferente a MS DOS, el instalador podía fallar y el usuario no podría instalar Windows.

* MS-DOS 3.1 o superior
* Procesador Intel 80286 o superior
* 1 MB o más de memoria
* 6.5 MB libres en el disco duro (9 MB recomendados)

■ Windows 95
Windows 95 fue lanzado el 24 de agosto de 1995.
El interfaz gráfico de usuarios fue una de las mayores mejoras con este sistema operativo. De hecho, el formato y estructura general del GUI se sigue utilizando en Windows hoy en día.
* Intel 80386 DX CPU
* 4 MB de RAM del sistema
* 50 MB de espacio en el disco duro

■ Windows 98
Windows 98 fue lanzado el 25 de junio de 1998.
* Procesador 486DX-2/66 MHz o superior (Procesador Pentium recomendado)
* 16 MB de RAM (24MB recomendados)
* 500 MB de espacio disponible en el disco duro
* Monitor VGA o mayor resolución
* CD-ROM or DVD-Rom
* Mouse u otros dispositivos

■ Windows 2000
Windows 2000 fue lanzado el 17 de febrero de 2000. Existieron tres versiones diferentes de Windows 2000 y cada una tuvo diferentes requerimientos.
Con esta versión, fueron introducidas nuevas opciones como Windows Desktop Update, Internet Explorer 5 y Outlook Express.

■ Windows 2000 Professional
* 133 MHz o superior, compatible con Pentium
* 32 MB de RAM (64 MB recomendados)
* 700 MB de espacio en el disco duro (2 GB recomendados)

■ Windows 2000 Server/Advanced Server
* 133 MHz de CPU
* 256 MB de RAM como mínimo
* 2 GB de espacio en disco duro

■ Windows Me
Windows Me fue lanzado el 24 de septiembre de 2000
Windows Me duró muy poco, sólo un año, ya que luego fue reemplazado por Windows XP
* Procesador Pentium de 150 MHz
* 320 MB de espacio en el disco duro
* 32 MB de RAM

■ Windows XP
Windows XP salió al mercado el 25 de octubre de 2001.
Fue el primer sistema operativo producido por Microsoft que fue creado con la kernel y arquitectura de Windows NT. Abajo se encuentran los requerimientos mínimos para XP Home y Profesional.
* Procesador de 233 MHz
* 63 MB de RAM
* 1.5 GB libres en el disco duro
* Adaptador de video y monitor VGA
* CD-ROM o DVD

■ Windows Vista
Windows Vista salió el 30 de enero de 2007. Este es el sistema que más requerimientos tiene y, por ende, el más criticado.
Vista Premium
* Procesador de 1.0 GHz
* 1 GB de RAM
* Memoria gráfica de 128 MB
* 40 GB de capacidad en el disco duro
* 15 GB libres en el disco duro

Vinculación de las Instrucciones y los datos a la memoria
puede realizarse en tres estados:

■ Tiempo de Compilación: si se conoce previamente la ubicacion de memoria, puede generarse código absoluto, el código debe ser recompilado si la direccion de inicio cambia.

■ Tiempo de Carga: si se conocen las direcciones en tiempo de compilación, debe generarse codigo reubicable.

■ Tiempo de Ejecución: la vinculacion se retarda hasta el tiempo de corrida si los procesos pueden ser movidos durante su ejecucion de una posición de memoria u otra.

Overlays (superposiciones)
■ Mantiene en memoria solo aquellas instrucciones y datos que se requieren en un momento determinado.
■ Se utilizaba cuando el proceso era mayor que la cantidad de memoria destinada para él.
■ Se implementaba por el usuario, no se requería un soporte especial del sistema operativo, su programación era compleja.

Asignacion Contigua(una tras otras)
■ Generalmente la memoria pricipal tiene dos particiones.-Para el sistema operativo residente que puede ser colocado en memoria baja o alta de acuerdo a la ubicacion del vector de interrupciones-Los procesos delos ususarios se colocan en otra particion
■ Asignación de particion unica

• Se usa el esquema de registro de reubicacion para proteger a los procesos de los usuarios entre si, y para proteger el codigo y los datos del SO.
• El registro de ubicacion tiene el valor de la direccion fisica mas pequeña; el registro limite…

■ Asignacion con multiples particiones

• Hueco: Bloque de memoria disponible; se establecen varios huecos(particione) de diferentes tamaños a traves de la memoria.
• Cuando un proceso llega, es asignado a un hueco lo suficientemente grande para contenerlo
• El SO mantiene informacion acerca de las particiones asignadas.

Asignacion con Multiples Particiones Fijas
Particiones configuradas por usuarios predeterminadas, se usó en OS/360/MTF (multiprogramación con un número fijo de tareas).
Recolocación: el enlazador debe determinar que direcciones recolocarse, vs carga absoluta x parte.
Protección: Bloques de 2k con clave, o registro de base y limite.
FRAGMENTACION.
no se puede aplicar overlays en este esquema de administracion de memoriaSistemas de proteccion:
-registro limite y base
-proteccion por clave
fragmentacion interna: desperdicio de espacios de memoria.

Asignacion con Particiones variables

Asignación dinámica de las particiones comprensión (garbage collection): ciber 40 mb/seg micro 1 mb/ seg
Fragmentación: huecos después de ejecución
Condensación: fusión de 2 huecos contiguos

■ El tamaño de la particion se establece en el momento de cargar el programa y dependiendo su tamaño
■ Los procesos tienen que correr en memoria contigua.
■ Tiene un problema de fragmentacion externa, por los huecos que quedan después de ejecución; La solución es mover el proceso, que se están ejecutando, proceso de compresión.

Condensación: Fusión de dos huecos contiguos

El esquema actual de administracion de memoria nace de los dos anteriores. Nace la paginación y la segmentación.

Planificación Múltiples Procesadores

• La planificación es más compleja cuando se tienen varios procesadores.
• Escenarios: Asignación de procesos a procesadores, uso de la multiprogramación en cada procesador individual, activación del proceso.
• La carga se comparte (una cola por procesador?).
• Una cola para todos los procesadores?.
• MUltiprocesamiento simétrico (SMP): Cada procesador tiene sus propias decisiones de planificación y consulta la cola de listos.
• MUltiprocesamiento asimétrico (ASMP): Sólo un procesador accede a las estructuras de datos del sistema, obviando la necesidad de compartir datos.

Asignación de procesos a procesadores

• Trata cada proceso como un recurso colectivo y asigna procesos a procesadores por demanda.
• Un proceso se vincula permanentemente a un procesador
  • Estrategia conocida como planificación de grupo o pandilla (gang).
  • Dedica una cola a corto plazo por cada procesador.
  • Menos sobrecarga.
  • El procesador puede estar ocioso mientras otro procesador tienen trabajo acumulado.
• Cola global
  • Procesos planificados sobre cualquier procesador disponible.
• Arquitectura maestro/esclavo
  • Las funciones clave del núcleo ejecutan siempre en un procesador concreto.
  • El maestro es responsable de la planificación de trabajos.
  • El esclavo envía una solicitud al maestro.
  • Desventajas
    • Un fallo en el maestro hace que falle el sistema completo.
    • El maestro puede llegar a ser un cuello de botella para el rendimiento del sistema.
• Arquitecturas camaradas
  • El núcleo puede ejecutarse en cualquier procesador.
  • Cada procesador se auto-planifica.
  • Complica el sistema operativo
    • Asegura que dos procesadores no escogen el mismo proceso.

Escenarios de Planificación de procesos de tiempo real

Escenarios de Planificación de procesos de tiempo real

Planificación de tiempo real

• Planeación de tiempo real estática
  • No se ajustan las prioridades con el tiempo, poca recarga en el sistema, para procesos donde las condiciones eventualmente cambian.
  • Estática dirigida por tabla (plan): Determina, en tiempo de ejecución, cuando debe comenzar a ejecutarse cada tarea. Se aplica a tareas periódicas.
  • Estática con expropiación dirigida por prioridad (sin plan): Se utiliza un planificado expropiativo tradicional basado en prioridades. Usado en los sistemas multiprogramados que no son de tiempo real. En tiempo real la prioridad se ajusta con base a las restricciones de tiempo de la tarea, ejemplo, planificación monótona en frecuencia (RMS).
• Planeación de tiempo real dinámica
  • Ajusta las prioridades en respuesta a condiciones cambiantes, puede tener una significativa sobrecarga, pero debe asegurar que ella no genere incumplimiento en los tiempos.
  • Dinámica basada en un plan: La factibilidad se determina en tiempo de ejecución.
  • Dinámica basada en el mejor esfuerzo: No se realiza análisis de factibilidad. El sistema trata de cumplir con todos los plazos y abandona cualquier proceso ya iniciado y cuyo plazo no se haya cumplido.

Planificación por plazos

Las aplicaciones de tiempo real no se preocupan tanto de la velocidad de ejecución como de completar sus tareas.

El proceso debe completarse en un tiempo específico.

• Se utiliza cuando los resultados serían inútiles si no se realiza el proceso a tiempo.
• Difícil de implementar
  • Debe prever un plan de requerimientos de recursos.
  • Genera significativa sobrecarga.
  • El servicio proporcionado a los otros procesos se puede degradar.

Información utilizada: Tiempo de activación, plazo de inicio, plazo de conclusión, tiempo de proceso, recursos requeridos, prioridad, estructura de subtareas.

Las prioridades en general se basan en los tiempos límites de los procesos.

• El tiempo límite más temprano primero(EDF).
• Mínima laxitud primero
  • Similar a EDF, pero la prioridad se basa en laxitud, la cual se basa en el tiempo límite de los procesos y su tiempo restante para completar su objetivo.

Perfil de ejecución de dos tareas periódicas con plazos de terminación

Considérese un sistema que recoge y procesa datos de 2 sensores, A y B, el plazo para tomar los datos del sensor A debe ser de 20 ms y el B cada 50ms. Se tarda 10 ms, incluyendo la sobrecarga del SO, para procesar cada muestra de datos de A y 25 ms para B. El sistema es capaz de tomar una decisión de planificación c/10ms.

 

Planificación de tareas periódicas de tiempo real con plazos de conclusión

En este caso pueden cumplirse todos los requisitos del sistema por medio de planificación que da prioridad, en los instantes de expropiación, a la tarea que tenga el plazo mas cercano. Dado que las tareas son periódicas y predecibles, se usa un método de planificación con tablas estáticas.

Perfil de ejecución de cinco tareas aperiódicas

Sean 5 tareas con tiempo de ejecución de 20 ms

Planificación de tareas aperiódicas de tiempo real con plazos de inicio

PLANIFICACIÓN DE MÚLTIPLES PROCESADORES

• La planificación es mas compleja cuando se tienen varios procesadores.

• Escenarios: Asignacion de procesos a procesadores, Uso de la multiprogramacion en cada procesador individual, Activacion del proceso, propiamente dicho.

• La carga se comparte (una cola por procesador?)

• Un cola para  todos los procesadores?

• Multiplrocesamiento Simétrico (SMP)- cada procesador tiene sus propias decisiones de planificación y consulta de la cola de listos.
• MultiProcesamiento Asimetrico (ASMP) – Solo un procesador accede a las estructuras de datos del sistema, obviando la necesidad de compartir datos.

Asignación de Procesos a Procesadores

Trata cada procesador como un recurso colectivo y asigna procesos a procesadores por demanda.

Un proceso se vincula permanentemente a un procesador

• estrategia conocida como plantificación de grupo o pandilla (gang)
• dedica una cola a corto plazo por cada procesador
• menos sobrecarga
• el procesador puede estar ocioso mientras otro procesador tiene trabajo acumulado

Cola global

• proceso planificados sobre cualquier procesador disponible.

Arquitectura maestro/esclavo

• las funciones clave del nucleo ejecutan siempre en un procesador concreto
•  El maestro es responsable de la planificacion de trabajos
• El esclavo envía una solicitud al maestro
• Desventajas:

         * Un fallo en el maestro hace que falle el sistema completo
* El maestro puede llegar a ser un cuello de botella para el rendimiento del sistema

Arquitectura camaradas

•  el núcleo puede ejecutarse en cualquier procesador
•  Cada procesador se auto-planifica
• complica el sistema operativo

Escenarios de Planificacion de procesos de tiempo real:

La planificacion en tiempo real tiene sentido cuando se trata de multiprocesadores.

Hoy en dia las maquinas son tan potentes que podemos hablar de multitarea en ambiente real.

PLANIFICACIÓN DE TIEMPO REAL 

Planeacion de tiempo real estática

No se ajustan las prioridades con el tiempo, poca recarga en el sistema, para procesos donde las condiciones eventualmente cambian.

• -Estática dirigida por tabla(plan): Determina, en tiempo de ejecución, cuándo debe comenzar a ejecutarse cada tarea. se aplica a tareas peri+odicas.
• -Estática con expropiación dirigida por prioridad(sin plna): se utiliza un planificador expropiativo tradicional basado en prioridades. Usado en los sistemas multiprogramados que no son de tiempo real. en tiempo real la prioridad se ajusta con base a  las restricciones de tiempo de la tarea. Ej. Planificacion monotona en frecuencua (RMS).

Planeacion de tiempo real dinamica

Ajusta las prioridades en respuesta a condiciones cambiantes, puede tener una significativa sobrecarga, pero debe asegurar que ella no genere incumplimiento en los tiempos.

• -Dinamica basada en un plan: la factibilidad se determina en tiempo de ejecucion.

• -Dinamica basada en el mejor esfuerzo: No se realiza analisis de factibilidad. El sistema trata de cumplir con todos los plazos y abandona cualquier proceso ya iniciado y cuyo plazo no se haya cumplido.

PLANIFICACIÓN POR PLAZOS 

Las aplicaciones de tiempo real no se peocupan tanto de la velocidad de ejecucion como de completar sus tareas.

El proceso debe completarse en un tiempo especifico

• -Se utiliza cuando los resultados serian inutiles si no se realiza el proceso a tiempo.

• -Dificil de implementar:

-Debe prever un plan de requerimientos de recursos

-Genera significativa sobrecarga

-El servicio proporcionado a los otros procesos de puede degradar.

Información utilizada: tiempo de activacion, plazo de incio, plazo de conclusion, tiempo de proceso, recursos requeridos, prioridad, estructura de subtareas.

Las prioridades en general se basan en los tiempos limites de los procesos.

-El tiempo limite mas temprano primero (EDF Earliest-deadline-first)
-Minima laxitud primero

-Similar a EDF, pero la prioridad se basa en la laxitud , la cual se basa en el tiempo limite de los procesos y su restante para completar su objetivo.

Perfil de ejecución de dos tareas periódicas con plazos de terminación.

Considere un sistema que recoge y procesa datos de 2 sensores, A y B, el plazo para tomar los datos del sensor A debe ser de 20 ms y el B 50 ms. Se tarda 10 ms, incluyendo la sobrecarga del so, para procesar cada muestra de datos A y 25 ms para B. El sistema es capaz de tomar una decision de planificacion c/10ms

Posteriormente a esto se utiliza un metodo de planificación de tablas dinamicas.

Colas Multinivel

La cola de listos se divide en colas separadas:

• Primer plano (interactiva).
• Segundo plano (lotes)

Cada cola tiene su propio algoritmo de planificación.

• Primer plano RR
• Segundo plano FCFS

La planificacion debe hacerse entre las colas:

• Planificacion de prioridad fija; es decir, sirva todos los procesos de primer plano y luego los de segundo plano. Existe la n posibilidad de inanicion.

• Cuanto de tiempo -cada cola tiene cierta cantidad de tiempo que puede ser planificado entre sus procesos; por ejemplo:

             80% para primer plano RR

             20% para segundo plano en FCFS

COLAS MULTINIVEL CON RETROALIMENTACIÓN

–Un proceso puede moverse entre varias colas; de esta manera puede implementarse el envejecimiento.

–La planificacion de Colas Multinivel con retroalimentacion esta definida por los siguientes parámetros:

• Numero de colas
• Algoritmos de planificacion por cola
• Método usado para determinar cuando promover un proceso.
• Método usado para determinar cuando degradar un proceso.
• Método usado para determinar que cola entrara en el proceso cuando requiera de servicio.

Las colas de retroalimentacion estan discriminadas por tiempo de ejecucion (entre mas tiempo mas rapido).

Planificacion en Solaris 2

Pueden correr procesos de tiempo real, procesos interactivos, del sistema, etc

Solaris da la mayor prioridad a los procesos de tiempo real.

Tiene diferentes quantum y se asignan con prioridad descendente.

Planificación sistemas tipo Posix ()

– Cada politica de planificacion lleva asociado un rango con al menos 32 niveles de prioridad.

– El planificador elegirá el proceso o proceso ligero con la prioridad más alta.

– Políticas de planificación

• FIFO
• Cíclica
• Otra

Planificación de procesos en Linux

Dos algoritmos: tiempo compartido y tiempo real .

• Tiempo compartido:

 – Prioridad basada en créditos el proceso con mas creditos se despacha.

– Se restan los creditos cuando suceden interrupciones de temporizador.

– Cuando el crédito= 9, se elige otro proceso.

– Cuando todos los procesos tienen credito=0, se reacreditan (Cr=Cr/2+Pr)

      * Con base en factores como prioridad e historia.

• Tiempo real:

– Tiempo real blando

–Cumple con Posix.1b – de dos clases

    * TFCFS y RR

    * TEl proceso de mayor prioridad siempre corre primero.

Planificación en Windows

Las prioridades de Windows se organizan en dos bandas o clases

– Tiempo real

– Variable

Planificador expropiativo basado en prioridades.

Planificación de procesos, CPU

El modulo despachador le da el control de la CPU al proceso seleccionado por el planificador de corto plazo; esto incluye:

• Conmutacion de contexto
• Conmutacion al modo usuario
• Saltar a la ubicación adecuada en el programa del usuario para reiniciar el programa.
  Latencia en el despacho: Es el tiempo que se toma el despachador para parar un proceso e iniciar otro.
  
   
  CRITERIOS DE PLANIFICACIÓN
   
• Utilizacion de CPU: Mantener la cpu tan ocupada como sea posible
• Rendimiento: numero de procesos que culminan su ejecución por unidad de tiempo.
• Tiempo de entrega/estancia/retorno(turnaround time):Tiempo transcurrido desde que se lanza un proceso hasta que finaliza. Incluye el tiempo de jecucion sumado con el tiempo de espera por los recursos, incluyendo el procesador. Es una medidad apropiada para trabajos por lotes.
• Tiempo de Espera: Cantidad de tiempo que un proceso gasta en la cola de listos.
• Tiempo de Respuesta (response time): Para un proceso interactivo, es el tiempo que transcurre desde que se lanza una peticion hasta que se comienza a recibir la respuesta. cantidad de tiempo que se hace desde una solicitud y se produce la primera respuesta, no incluye el tiempo que toma en exhibir la respuesta.
• Previsibilidad: Un trabajo deberia ejecutarse aproximadamente en el mismo tiempo y con el mismo coste a pesar de la carga del sistema. Una gran variacion en el tiempo de respuesta o en el tiempo de estancia es malo desde el punto de vista de los usuarios. Puede significar una gran oscilacion en la sobrecarga del sistema o la necesidad de poner a punto el sistema para eliminar las inestablidades.

CRITERIO DE OPTIMIZACIÓN

• Maxima utilizacion de CPU
• -Maximo rendimiento
• Minimizar el tiempo de entrega
• Minimizar el tiempo de espera
• Minimizar el tiempo de respuesta
• Justicia
• maximo # de usuarios interactivos
• Maxima capacidade de ejecucion
• Predictibilidad
• Minimizacion de sobrecarga
• Equilibrio en uso de recursos
• consistencia en seguridad

ALGORITMOS DE PLANIFICACIÓN

Es el procedimiento que el sistema utiliza para establecer los tiempos de ejecucion y el orden de ejecucion.

• FCFS/PEPS: los procesos Cortos sufren, justa, predecible
• SJF/SPN (short job first): El siguiente proceso el mas corto
• SRTN (short remain time next), el < tiempo restante, compensa cortos
• Round-Robin, RR, asignacion Ciclica/turno. Equilibra FCFS / SRTN, usa cola circular con FCFS/prioridades con slice / quantum para c/proceso
• Por Prioridad, siempre se elige el de > prioridad, hay problema por inanición y es compensada X prioridad de Envejecimiento. Envuelve los demas metodos, excepto RR.
• HRN, Tasa de respuesta mas alto, es costosa Prioridad = (w+s)/s
• MLQ, Colas multinivel: Combinar, proceso del Sistema (x prioridad), interactivos (RR), lotes(FCFS/SRTN)
• MLQ con Retroalimentación: Los procesos se pueden reubicar en diferentes colas de acuerdo a comportamiento. Los procesos limitados por procesador se envían a la cola de < Prioridad, los interactivos ubican la mayor prioridad.
• FSS(Fair share schedule), Porcion justa, o reparto equitativo, los grupos de porcion justa obtiene prioridades de acuerdo con su proximidad al logro de sus metas en la utilizacion de recursos. Los grupos que van mal tienen > prioridad.

w= tiempo de espera y ejecucion hasta el momento

e= tiempo de ejecucion hasta el momento

s = tiempo total se servicio requerido por el proceso incluyendo  e.

turno-quantum-porcion= tiempo que se le da a un proceso.

Planificación el tiempo más corto Primero (SJF)

-Asocia con cada proceso la longitud de su proxima rafaga de cpu. Usa estas longitudes para planificar el proceso con el menor tiempo.

-Hay dos esquemas:

• -No expropiativo – una vez la cpu es asignada al proceso no puede ser expropiado hasta que termine su rafaga(SPN)
• -Expropiativo – Si llega un nuevo proceso con una longitud de rafaga menor que el tiempo restante del proceso en ejecucion, este es expropiado. Este esquema es conocido como EL menor tiempor restante primero (SRTF).

-SJF es optimo  -da un tiempo de espera minimo para un conjunto de procesos.

Planificacion por prioridad

– Se asocia un numero (entero) a cada proceso.

– La CPU es asiganda al proceso con mayor prioridad (por ej, EL numero más pequeño significa mayor prioridad en UNIX o prioridad ascendete como Windows a mayor # mayor prioridad)

*Expropiativo
*No expropiativo

-SJF es un esquema de planificacion por prioridad, donde la prioridad es el tiempo de rafaga de cpu que se calcula.

-Problema = La inanicion- los procesos de baja prioridad puede que nunca se ejecuten.

-Solucion = Envejecimiento – a medida que se transcurre el tiempo aumenta la prioridad.

Turno circular (RR)

-Cada proceso toma una pequeña unidad de tiempo CPU (quantum de tiempo), por lo general  de 10-100ms. Despues de transcurrido este lapso de tiempo, el proceso es expropiado y ubicado en la cola de listos.

-Si hay n procesos en la cola de listos y el quantum es q, entonces cada proceso toma 1/n de tiempo de Cpu en bloques de a lo mas q unidades de tiempo a la vez. Ningun proceso espera mas que (n-1)* q unidades de tiempo.

-Rendimiento:
-* si q>> → FIFO
-*q <<  → q debe ser mayor que la conmutacion de contexto, de otra forma la sobrecarga es grande.
Interrupcion por hardware no por software

Porcion Justa (Fair Share Scheduling)

Divide la capacidad de recursos del sistema en prociones, que son asignadas a planificadores asignados a varios grupos.

*Las aplicaciones o trabajos de usuario se pueden organizar como un conjunto de procesos (hilos), algunos grupos son mas importantes que otros.

*Desde el punto de vista del usuario, la preocupacion es como ejecutan su aplicacion.

*Es necesario tomar decisiones de planificacion basadas en estos conjuntos de procesos, los grupo menos importantes no pueden monopolizar los recursos.

Loteria

Se da a cada proceso un tiquete para varios recursos del sistema, tal como la cpu. Cuando se requiere planificar se selecciona al alzar un tiquete, y el proceso que lo tienen obtiene el recurso. Si queremos que un proceso tenga más oportunidades se le entregan más tiquetes. Los procesos cooperativos pueden intercambiar sus tiquetes.

Un ejemplo es un servidor de video: supongamos que los procesos necesitan velocidades de 10, 20, 25 f/s. Podemos entregar a c/proceso 10, 20 , 25 tiquetes respectivamente