Date post: | 25-Jun-2015 |
Category: |
Documents |
Upload: | rodrigomartin5943 |
View: | 375 times |
Download: | 1 times |
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
RESUMEN DE SISTEMAS OPERATIVOSUTN – FRBA
Antes de empezar a leer el resumen queremos aclarar un par de tips:
o Unicamente con este resumen no van a ningún lado.o Tienen que leer el libro de Stalling igual.o Apoyen dudas con el NOTAS.o Consulten el foro de sisop, muy posiblemente (un 98%) las dudas que tengan ya
fueron consultadas y hay respuestas concretas ;)o Practiquen mucha práctica xD, consulten dudas (el foro es el centro de la
sabiduría). o Pidan revisión del examen SIEMPRE ;o)o Y Matías Cabellón es un capo. o Good Luck.
1
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO I: “Sistemas Informáticos”
Elementos: Procesador: Procesa datos y controla a las operaciones. Memoria Principal: Almacena datos y programas. Módulos de E/S: Transportan datos entre la computadora y el entorno
exterior. Interconexiones entre componentes: Mecanismos y estructuras de conexión
(Buses).
REGISTROS DESCRIPCIÓN TIPOMAR (Memory Address Register) Especifica la dirección de
memoria a escribir o leer.De Control y Estado. Registro de Dirección.
MBR (Memory Buffer Register) Contiene los datos que van a ser escritos o fueron leidos.
De Control y Estado.Registro de Datos.
I/O MAR (In Out MAR) Especifica un dispositivo de I/O
De Control y Estado.Registro de Dirección.
I/O MBR (In Out MBR) Especifica datos que van a ser escritos o fueron leidos desde el I/O
De Control y Estado.Registro de Datos.
IR (Index Register) Guarda el valor a sumar a un valor base para obtener la dirección efectiva.
Visible de Usuario.Registro Dirección.
SP (Segment Pointer) Guarda el valor de dirección base que apunta a un segmento.
Visible de Usuario.Registro de Dirección.
SP (Stack Pointer) Contiene la dirección de la Visible de Usuario.2
Registros
Tipo según su función
Tipo según su contenido
Visibles de usuario: Son los que están disponibles para los
programas.
De Control y Estado: Se emplean para controlar las operaciones del
procesador.
Registros de Datos: Contienen datos
Registro de Dirección: Contienen direcciones o parte de
una dirección.
Registro de Códigos de Condición: Conjunto de bits activados por el hardware del procesador como
resultado de operaciones.
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
cabeza de la pila. Registro de Dirección.PC (Program Counter) Contiene la dirección de la
intrucción siguiente.De Control y Estado.Registro de Dirección.
IR (Instruction Register) Contiene la última instrucción leida.
De Control y Estado.Registro de Datos.
PSW (Program Status Word) Contiene códigos de condición.
De Control y Estado.Código de Condición.
Interrupciones:
Mejora la eficiencia de procesamiento.
TIPO DESCRIPCIÓNDe Programa Generadas por alguna condición resultado de
la ejecución de una instrucción.De Reloj Generadas por el reloj interno del procesador.De E/S Generadas por un controlador de E/S para
indicar ACK o NAK.Por fallo de Hardware Generadas por un error en el Hardware.
Clasificación de las Instrucciones:
1. Procesador ~ Memoria: Transferencia.2. Procesador ~ E/S: Transferencia.3. Tratamiento de Datos: Operación aritmética o lógica.4. Control: Alterar la secuencia de ejecución.
Jerarquía de Memoria
3
Enfoques de interrupciones
múltiples
Por secuencia: Inhabilitar las interrupciones mientras se procesa una.
Por prioridades: Definir prioridades para las interrupciones y permitir la interrupción entre interrupciones.
BEGINCiclo de Lectura
(Fetch)Ciclo de Ejecución
(Execute)Int.
Enabled?
Comprobación de Interrupción del
Proceso.
NO
SI
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Soluciona el dilema de utilizar tecnología de memoria de gran capacidad pero con tiempos de acceso mayores vs memorias rápidas pero costosas si son de mucha capacidad.
Principio de Cercanía de Referencia: En la ejecución de un programa las referencias a memoria por parte del procesador tienden a estar agrupadas durante un período corto de tiempo.Principio de Cercanía Temporal: Es la tendencia del procesador a acceder a posiciones de memoria que ya han sido utilizadas anteriormente.
CACHÉ
o Es invisible para el SO.o Contiene una copia de la Memoria Principal, se deben aplicar técnicas de actualización
de los datos a la Memoria Principal si fuese necesario (Políticas de Escritura).
Ejemplo:
CACHÉ MEMORIA PRINCIPALCantidad de Sección: C Longitud de palabra: n bitsLongitud de Sección: K palabras + 1 etiqueta que identifica al bloque
Cantidad de palabras direccionables: 2n
Longitud de bloque: K palabrasCantidad de bloques: 2n/K = B
CPU
CACHE
Memoria Principal
Transferencia de palabras
Transferencia de bloques
4
MemoriaInterna
MemoriaExterna
Almacenamiento Secundario
- Costo del Bit+ Capacidad- Velocidad de Acceso.- Frecuencia de Acceso
por parte del procesador.
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Diseño de la CACHÉ:
o Tamaño de Caché: + Tamaño => (+ Tasa de Aciertos ^ + Costo)o Tamaño de Bloque: Hay que equilibrar o se desaprovecha el principio de referencia.o Función de Traducción (mapping): Determina la posición de la Caché que ocupará el
bloque.o Algoritmo de Reemplazo: Elige el bloque a reemplazar. Debe ser el que tenga menor
probabilidad de ser usado en el futuro.
Técnicas de Comunicación con dispositivos de E/S
E/S PROGRAMADA E/S POR INTERRUPCIONES DMA
5
CACHÉ MEMORIA PRINCIPAL0
c-1
0
K
2n-1
B > C
Emitir orden LEER(CPU ~ E/S)
Leer estado (E/S ~ CPU)
EstadoOK
Leer Palabra (E/S ~ CPU)
Escribir Palabra
OK
Next
SI
ErrorNO
NO
Interrupción
Emitir orden LEER(CPU ~ E/S)
Leer estado (E/S ~ CPU)
EstadoOK
Leer Palabra (E/S ~ CPU)
Escribir Palabra
OK
Next
SI
Error
NO
Hacer Otra cosa
Emitir orden LEER(CPU ~ E/S)
Leer estado de módulo DMA
Next
Hacer Otra cosa
Interrupción
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO II: “Introducción a los SO”
Definición de SO: Programa que controla ejecución de los programas de aplicación y actúa como interfaz entre las aplicaciones del usuario y el Hardware de la computadora.
SISTEMAOPERATIVO
Comodidad: Hace que una computadora sea más fácil de utilizar.
Eficiencia: Hace que los recursos de un
Sistema Informático se utilicen mejor.
Capacidad de Evolución: Permite el desarrollo
efectivo, la verificación y la introducción de nuevas
funciones sin interferir en los servicios que brinda.
Proceso en Serie
Proceso por Lotes
Proceso por lotes con multiprogramación
Tiempo Compartido
Los Procesos
Gestión de Memoria
Seguridad y protección de Información
Planificación y gestión de recursos
Estructura del Sistema
Evolución
Objetivos
Logros Principales
6
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Objetivos de un SO
SO como interfaz Usuario / Computadora: Servicios que ofrece (Comodidad): o Creación de Programas: Ofrece múltiples funcionalidades y
servicios para ayudar al programador en la creación de programas en general estos servicios son programas de utilidad que no forman parte del SO pero se acceden a través de él.
o Ejecución de Programas: El SO administra la preparación de los recursos para la ejecución de un programa.
o Acceso a los dispositivos de E/S: El SO oculta al programador las particularidades de los dispositivos de E/S, de este modo se los utiliza como lecturas y escrituras simples.
o Acceso controlado a los archivos: El SO oculta las estructuras de los datos en los archivos y en el medio de almacenamiento. Protege los archivos en un ambiente multiusuario.
o Detección y respuesta a errores: El SO da una respuesta a errores eliminando la condición de error con el menor impaco posible sobre las aplicaciones.
o Contabilidad: Recoge estadísticas de utilización de recursos y supervisa ciertos parámetros de rendimiento.
SO como administrador de recursos: Servicios que ofrece (Facilidad): o Control de funciones básicas de la computadora: Para lograr
esto, administra los recursos.o Dirige al procesador en el empleo de otros recursos del sistemao Controla el tiempo de ejecución de otros programas: Para ello
cesa su ejecución y ejecuta otros programas.o Aspectos no habituales como mecanismos de control: El SO
funciona de la misma manera que cualquier otro Software y abandona el control del procesador y depende de él para recuperarlo.
Facilidad de evolución de un SO: Razones de evolución: o Actualizaciones del Hardware y nuevos tipos de Hardware: El
SO debe ser capaz de soportarlos.o Nuevos Servicios: En respuesta a las demandas del usuario o
necesidades de los administradores del Sistema.o Correciones: Soluciones a fallas descubiertas con el curso del
tiempo.
Evolución de un SO
Proceso en Serie o El programador interactuaba directamente con el Hardware, no
había SO.o Problemas principales:
Planificación: El usuario reservaba un tiempo para utilizar la máquina que no era el necesario.
Tiempo de preparación: El usuario realizaba un proceso de preparación que al producirse un error debía volver a realizar.
Proceso por Lotes o El usuario entregaba su trabajo al operador de la computadora.
Éste los agrupaba secuencialmente en lotes y los ejecutaba mediante un elemento de Software llamado MONITOR.
o MONITOR Controla la secuencia de Sucesos: lee uno a uno los
trabajos y les pasa el control que es devuelto cuando termina el procesamiento.
Gran parte siempre está en memoria principal y disponible para su ejecución: monitor residente
También posee utilidades y funciones comunes que se cargan cuando se las necesita.
7
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Características necesarias- Protección de memoria: El programa de usuario
no debe modificar la zona de memoria del monitor.
- Temporizador: Al expirarse cierto tiempo de ejecución de un programa de usuario, se produce una interrupción y el control vuelve al monitor.
- Instrucciones privilegiadas: Ciertas instrucciones de máquina se consideran privilegiadas y solo las ejecuta el monitor. Un programa de usuario debe solicitárselo al Monitor.
- Interrupciones: Aporta mayor flexibilidad para ceder y retomar el control de los programas de usuario.
Sistema por Lotes con multiprogramación o Se ejecutan más de un programa concurrentemente y se
intercambian cuando uno pide un servicio de E/S.o Objetivo principal: Maximizar la utilización del procesador.o Origen de las instrucciones: Instrucciones de un lenguaje de
control de trabajos incluidas en el trabajo.o Características necesarias:
E/S por Interrupciones y DMA: El procesador envía una orden de E/S para un trabajo y continúa con la ejecución de otro. Cuando termina la operación de E/S el procesador debe ser interrumpido.
Gestión de Memoria: Para tener varios trabajos listos para ejecutarse.
Algoritmo de planificación: Para decidir que trabajo ejecutar.
Sistemas de tiempo compartido o Múltiples usuarios acceden simultáneamente al sistema por
medio de terminales y el SO intercala su ejecución en ráfagas cortas.
o Objetivo principal: minimizar el tiempo de respuesta.o Origen de las instrucciones: órdenes dadas por un terminal.o Características necesarias:
Protección de la memoria entre programas. Protección del disco entre programas. Controlar la disputa por los recursos. Protección de usuarios no deseados
o Características: Cada usuario dispone en promedio 1/n de la velocidad
de la computadora. Donde n es la cantidad de usuarios. El tiempo de respuesta debería ser comparable al de
una computadora dedicada.
8
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Los procesos
Definición básica de Proceso: Un programa en ejecución, con un estado actual asociado a un conjunto de recursos.
Sincronización Incorrecta: Perdida de señales o recepción de señales duplicadas por un
diseño incorrecto (esto afectaría el aviso de finalización de E/S por ej)
Fallos de exclusión mutua: Sólo una rutina puede realizar una transacción al mismo
tiempo sobre una determinada parte de los datos.
Funcionamiento no determinista del programa: El orden en que se organiza la
ejecución de varios programas puede influir en los resultados de un programa en
particular.
DEAD-LOCK: 2 o más programas suspendidos a la espera uno del otro.
Programa ejecutable (código)
Datos asociados al programa (variables, espacio de
trabajo, Buffer, etc) Contexto de ejecución (toda
la información que el SO necesita para administrar al proceso y el procesador para
ejecutarlo)
El concepto ayuda a controlas errores
Componentes
Proceso
9
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Gestión de Memoria
Aislamiento del Proceso: Cada proceso independiente no debe interferir en los datos y la memoria de ningún dato.
Asignación y Gestión automática: A los programas se les debe asignar memoria dinámicamente según las vayan
necesitando.
Soporte para la programación modular: Los programadores deben ser capaces de definir módulos de programa y de crear, destruir y alterar el tamaño de los
módulos dinámicamente.
Protección y Control de Acceso: El SO debe permitir que las secciones de memoria estén accesibles de diferentes
maneras para los diversos usuarios.
Almacenamiento a Largo Plazo: Muchos programas requieren almacenar información después de apagar la
computadora.
FileSystem: Incorpora un almacenamiento a
largo plazo en el que se almacena la información
en archivos.
Virtual Memory: Servicio que permite a los programas
direccional la memoria desde un punto de vista
lógico.
Paginación: Divide los procesos en bloques de tamaño
fijo (páginas) y proporciona una traducción dinámica entre la dirección virtual y la real.
Se solucionan mediante
Responsabilidades del SO
Gestión de Memoria
10
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Planificación y Gestión de Recursos
Equidad: Otorgar accesos a recursos de forma igual y equitativa entre trabajos con demandas similares.
Sensibilidades Diferenciales: Discriminar dinámicamente entre trabajos con demandas diferentes
para satisfacer la totalidad de sus requerimientos.
Eficiencia: Maximizar la productividad, minimizar el tiempo de respuesta y alojar a tantos usuarios
como sea posible (tiempo compartido).
Cola a corto plazo: Procesos que están en memoria principal, listos para
ejecutarse.
Cola a largo plazo: Procesos nuevos que esperan para usar el procesador.
Cola de E/S: Cada dispositivo de E/S tiene una cola donde se alojan los procesos que
están esperando para utilizarlo.
Dispatcher: Planificador a corto plazo, escoge el siguiente proceso que va a utilizar el procesador.
Gestor de Peticiones de Servicio: Maneja las
peticiones de los procesos y luego llama a Dispatcher.
Gestor de Interrupciones: Maneja las interrupciones de los procesos
y de los dispositivos de E/S y luego llama a Dispatcher.
Factores a tener en cuenta
Elementos Principales
Planificación y gestión de Recursos
11
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Seguridad y Protección de la Información
Control de Acceso: Regulación del acceso del usuario al sistema y de los recursos.
Control del Flujo de Información: Regulación del flujo de datos dentro del sistema y su distribución a
los usuarios.
Certificación: Relativo a la demostración de que el acceso y el flujo de información se llevan a cabo de acuerdo con las
especificaciones y que éstas cumplen las políticas de protección y seguridad deseadas.
Seguridad y Protección de la Información
12
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Características de los SO modernos
Arquitectura del Núcleo o Núcleo monolítico: Un único proceso que centraliza con cantidad de
funcionalidades y que sus componentes comparten el mismo espacio de direcciones.
o Micronúcleo: Asigna unas pocas funciones esenciales al núcleo. Otros servicios del SO las proporcionan procesos que se ejecutan en
modo usuario y son tratados como cualquier otra aplicación. Se adapta bien a sistemas distribuidos
MultiThreads: Técnica por la cual un proceso se divide en threads que pueden ejecutarse concurrentemente.
o Proceso: Conjunto de 1 o más threads y los recursos del sistema asociados.o Thread: Unidad de trabajo que se puede ejecutar. Incluye un contexto del
procesador y sus propias áreas de datos para una pila. Multiprocesamiento simétrico (SMP)
o Características Existen múltiples procesadores. Estos procesadores comparten la misma memoria principal y
dispositivos de E/S. Estos procesadores pueden ejecutar las mismas funciones.
o Ventajas Rendimiento: Se ejecuta más de un proceso en paralelo. Disponibilidad: El fallo de un procesador no detiene la máquina, se
puede continuar con un rendimiento reducido Crecimiento Incremental: Se puede aumentar el rendimiento al
agregar más procesadores. Escalabilidad: Los conductores pueden ofrecer una variedad de
productos con diferentes precios y rendimientos. SO Distribuido: Proporciona la ilusión de un único espacio de memoria principal y
secundaria, además de otros mecanismos de acceso unificados para un conjunto de entidades (computadoras).
Diseño Orientado a Objetos: Impone una disciplina para añadir extensiones a un pequeño núcleo.
13
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO III: “Descripción y Control de Procesos”
La inclusión de estados en los procesos permite modelar sus comportamientos y guíar al procesador hacía una correcta implementación del sistema conjuntamente, minimizando sus tiempos de ocio y maximizando el tiempo de respuesta del sistema.
Listo: El proceso está listo para la ejecución. Bloqueado: El proceso está esperando un suceso. Suspendido: El proceso está en memoria secundaria Listo y Suspendido: El proceso está en memoria secundaria listo para ejecutarse ;o) si
se lo traer a MP.
Nuevo -> Listo y Suspendido, Nuevo -> Listo: Cuando se crea un proceso, se lo pasa a estado Listo. Si no hay suficiente memoria principal, se lo puede pasar a Listo y suspendido directamente (generalmente esta es la que se utiliza, Just Time).
Bloqueado -> Bloqueado y Suspendido: Un proceso que está en memoria principal se pasa a suspendido para dar espacio a otro que se pueda ejecutar y no esté bloqueado.
Bloqueado y Suspendido -> Listo y Suspendido: Cuando se produce el suceso que estaba esperando.
Listo y Suspendido -> Listo: Cuando no hay procesos listos en memoria principal, el SO tiene que taer alguno para que se pueda ejecutar.
Listo -> Listo y Suspendido: Puede optar por esta opción, por prioridades o porque supone que un proceso que está en estado Bloqueado se desbloqueará rápidamente.
Bloqueado y Suspendido -> Bloqueado: Igual condición anterior. Listo -> Ejecución: El dispatcher lo escogió así. Ejecución -> Listo: Timeout, System Call, etc. Ejecución -> Listo y Suspendido: Por timeout y hay un proceso en suspendido que
posee mayor prioridad como para estar en Listo.
Listo y Suspendido
Listo
BloqueadoBloqueado y suspendido
Terminado
Nuevo
Ejecución
AdmitirAdmitir
Expedir
Timeout
Esperar Suceso
Activar
Suspender
Salir
Ocurre Suceso
Activar
Suspender
MODELO DE 7 ESTADOSSuspender
Memoria: Controlan la memoria principal y secundaria.
E/S: Controlan los dispositivos y los canales de E/S
Tablas que sirven para tener información sobre el estado actual de cada proceso y
de cada recurso.
Archivos: Controlan información relacionada con los archivos. Procesos: Los administra y controla.
Categorías
Descripción de Proceso: Estructuras
de Control del SO
14
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Estructuras de Control de Procesos
Datos de Usuario: La parte modificable por el usuario.
Programa de Usuario: Código a ejecutar.
Bloque de Control de Proceso: Informe necesaria para que el SO controle al proceso.
Un error en una rutina puede dañarlos.
Un cambio de su diseño afecta a módulos del SO.
SOLUCION: Rutina de gestión que los protege ya que ella solamente los lee o escribe.
Depende del esquema de gestión de memoria
utilizado.
Deben mostrar la ubicación de cada segmento o página de
cada imagen de proceso, ya sea en memoria principal o
secundaria.
Identificador (PID)
Información del Estado del
procesador
Información de Control del
Proceso
Estructuras de Control de
Procesos
Imagen de un Proceso
Problemas de
Protección
Ubicación de los
Procesos.
Atributos de los
Procesos.
15
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Atributos de los procesos
Identificador (PID) o Identificador numérico del proceso.o Identificador numérico del proceso padre.o Identificador del usuario.
Información del estado del procesador o Sirve para guardar la información de los registros del procesador cuando se
interrumpe al proceso.o Registros del procesador (Visibles del Usuario, De Control y Estado y Puntero de
la Pila). Información de Control del Proceso
o Planificación y Estado: Información necesaria para la planificación del SO.o Elementos típicos.
Estado de Proceso: alguno del modelo de estados. Prioridad Información de planificación: depende del algoritmo de planificación. Suceso: identidad de un suceso que se está esperando para reanudar la
ejecución.o Estructuración de datos: Enlace con otros procesos en un tipo de estructura
(cola, anillo, etc).o Comunicación entre Procesos: información de comunicación almacenada.o Privilegios de los Procesos: Memoria, instrucciones, servicios y utilidades que
puede utilizar.o Gestión de Memoria: Punteros que indican la memoria virtual asignada.o Propiedad de los recursos y utilización: Indica los recursos controlados. También
puede incluir un historial.
Control de Procesos
Modos de Ejecución: Al ejecutarse una interrupción o un System Call se cambia a modo Kernel. Al finalizarse se cambia a modo Usuario.
o Motivo: Proteger al SO y a sus tablas de los programas de usuario.o Tipos
Modo Usuario: no ejecuta ciertas instrucciones privilegiadas Modo Kernel: Control completo del procesador, ejecuta todo tipo de
instrucciones.o El procesador sabe en que modo ejecutar mediante el registro PSW.
Pasos en la creación de un proceso: 1. Asignar ID al Proceso (PID).2. Asignar espacio para el proceso.3. Iniciar el bloque de control de proceso.4. Establecer los enlaces apropiados.5. Crear o ampliar otra estructura de datos.
Cambio de Proceso: Motivos o Interrupciones
Origen de la causa: externa a la ejecución de la instrucción en curso. Uso: Reacción a un suceso asincrónico externo.
o Trap (cepo) Origen de la causa: asociada a la ejecución de la instrucción en curso. Uso: Tratamiento de un error o una condición excepcional.
o System Call Origen de la causa: Solicitud explicita. Uso: Llamada a una función del SO.
Cambio de Estado de Proceso
Ejecución del SO o Características
Salvar el Contexto del Procesador.
Actualizar el bloque de control de Proceso que
estaba en ejecución.
Mover el bloque de control a la cola apropiada.
Seleccionar otro proceso para su
ejecución
Actualizar el bloque de control del proceso
seleccionado
Actualizar las estructuras de datos de la gestión de memoria.
Restaurar el Contexto del procesador al estado en que estaba para este
proceso.
16
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
- El SO funciona de la misma forma que un Software corriente.
- El SO abandona el control y depende del procesador para recuperarlo.
o Enfoques Núcleo fuera de todo proceso: El concepto de proceso se aplica solo a los
programas de usuario. El código del SO se ejecuta como una entidad separada en modo privilegiado.
Ejecución dentro de los procesos de usuario: Casi todo el Software del SO es ejecutado en el contexto de un proceso de usuario.
- Las imágenes de los procesos incluyen zonas de programa, datos y de pila para los programas de Kernel.
- Hay una pequeña cantidad de código de cambio de proceso que se ejecuta fuera de todo proceso.
- Al suceder una interrupción o System Call solamente se realiza un cambio de modo, ahorrando 2 cambios de proceso.
Sistema operativo basado en Procesos: - El SO es una colección de procesos del sistema.- Las funciones más importantes se organizan en procesos
separados.- Impone una norma de diseño modular de programas con
interfaces mínimas y claras.- Es útil en entorno de multiprocesador o de varios
computadoras.
P1 P2 P3 Pn-1 Pn
NÚCLEO
P1
SO
P2
SO
P3
SO
Pn-1
SO
Pn
SO
FUNCIONES DE CAMBIO DE PROCESO
P1 P2 Pn SO1 SOn
FUNCIONES DE CAMBIO DE PROCESO
17
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO IV: “Hilos, SMP y Micronúcleos”
Proceso e Hilos
Comunicación con otros procesos.
Un espacio de direcciones virtuales.
Acceso protegido a los procesadores.
Archivo y recursos de
E/S.
Estado de ejecución.
Contexto del Procesador.
Pila de ejecución.
Almacenamiento estático de variables
locales.
Puede acceder a memoria y recursos del Proceso.
Toma menos tiempo
crearlos.
Toma menos tiempo
borrarlos.
Toma menos tiempo hacer un Context
Switch.Pueden comunicarse entre si sin invocar al kernel ya que
comparten memoria y archivo.
Simplifican la estructura de un programa de
diferentes funciones.
Trabajo interactivo y en segundo plano.
Procesamiento asincrono.
Aceleración de la ejecución.
Estructuración modular de los programas
Proceso: Unidad de propiedad de recursos.
Thread: Unidad de expedición.
Ejemplos de Uso
Ventajas
18
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Tipos de Threads
User Lever Thread (ULT): o Características
La gestión de estos threads se hace en la aplicación, el kernel no es consciente de la existencia de estos threads.
Se utiliza una biblioteca para: crear, borrar, comunicar, planificar y manejar el contexto de los threads.
La biblioteca se ejecuta en el espacio de usuario y dentro del proceso. Si en un thread se produce un System Call o un Timeout, este thread
queda en estado de ejecución pero el proceso que lo contiene pasa al estado bloqueado.
o Ventajas El intercambio de threads evita 2 cambios de modo ya que no necesita
los privilegios del kernel. Se puede realizar una planificación específica sobre la aplicación. Se pueden ejecutar en cualquier SO, sin cambiar al kernel teniendo la
biblioteca necesaria.o Desventajas
La mayoría de System Calls son bloqueantes y esto bloquea a todo el proceso.
No aprovecha las ventajas de los multiprocesadores, ya que el SO no puede planificar a estos Threads.
o Formas de Evitar los problemas Jacketing: Convierte un System Call bloqueante en uno no-bloqueante
para el proceso. En lugar de realizar un System Call directo, se llama a una rutina de gestión que se fija si está ocupado el recurso de E/S, si es así entonces pasa el thread al estado Listo y cede el control a otro thread. Si el anterior thread recibe de nuevo el control, verifica si se desocupó el recurso.
Kernel Level Thread (KLT): o Características
Lo implementan W2k, Linux, OS/2, entre otros. La gestión de hilos la hace el Kernel. En el área de la aplicación hay una API para las funciones de gestión. El Kernel mantiene la información de contexto del proceso como un todo
y la de cada thread dentro del proceso. El Kernel realiza la planificación en función de los threads.
o Ventajas: Soluciona las desventajas de ULT.o Desventajas: Las ventajas de ULT negadas.
Combinadas (ULT + KLT): o Características
Lo implementa Solaris La gestión de threads se realiza por completo en el espacio de usuario. Múltiples ULT se asocian con varios KLT (de menor o igual número). El programador adapta la cantidad de KLT.
P P PP
User
Kernel
ULT KLT ULT + KLT
19
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Otras Estructuras
1 Proceso ~ 1 Thread: Cada thread de ejecución es un único proceso con sus propios recursos y espacio de direcciones. Lo implementa el viejo UNIX.
1 Proceso ~ N Threads: Un proceso define un espacio de direcciones y unos recursos dinámicos propios. Pueden crearse varios threads que ejecutan en dicho proceso. Lo implementa Win NT, Solaris, Linux, OS/2, OS/390, Mach, entre otros.
N Procesos ~ 1 Thread: Un Thread puede emigrar del entorno de un proceso a otro. Esto permite que un thread se pueda mover facilmente entre sistemas distintos. Lo implementa Clouds, Esmerald, entre otros.
M Procesos ~ N Threads: Combina los atributos de los casos 1:N y N:1. Lo implementa TRIX.
Multiprocesamiento
Categorías
SISD: 1 Procesador ejecuta 1 Flujo de instrucciones para operar en 1 secuencia de datos.
SIMD: N Procesadores ejecutan 1 Flujo de instrucciones para P secuencia de datos. MISD: N Procesadores ejecutan M Flujo de instrucciones para 1 secuencia de datos. MIMD: N Procesadores ejecutan simultaneamente M Flujo de instrucciones sobre P
secuencias de datos.
MIMD
Memoria compartida (fuertemente acoplados): Se comunican mediante la
memoria
Memoria distribuida (débilmente acoplados): Se comunican mediante líneas dedicadas o algún tipo de red.
Son las agrupaciones.
Master/Slave
SMP
Clasificación según la asignación de procesos
a los procesadores.
Clasificación según la comunicación
entre procesadores
20
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Master/Slave
El núcleo del SO siempre se ejecuta en un procesador
determinado.
El resto de procesadores ejecutan programas de
usuario y utilidades del SO.
El Master planifica.
Ventajas
Necesita menos modificaciones sobre
un SO monoprocesador
multiprogramado.
Un fallo en el Master puede
producir una caída del sistema.
El Master puede ser un cuello de botella.
Características
Master/Slave
Desventajas
21
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
SMP
Ventajas
También pueden intercambiar
señales directamente. El núcleo se ejecuta en
cualquier procesador.
Cada Procesador se autoplanifica.
El usuario ve al sistema como si fuera un monoprocesador multiporogramado.
El SO es más complejo.
Si no se aplica alguna técnica, se pierde la
coherencia de cachés.
Las desventajas del Master/Slave
negadas.
Procesos o Threads concurrentes: es necesario que las funciones del Kernel sean reentrantes para permitir el
paralelismo entre procesadores.
Planificación: hay que tener cuidado en la planificación, ya que se pueden realizar desde
distintos procesadores. Se pueden planificar muchos
threads del mismo proceso.
Sincronización: hay que sincronizar el acceso a
recursos y posiciones de memoria compartidas.
Gestión de Memoria: hay que coordinar los mecanismos de
paginación de los diferentes procesadores.
Fiabilidad y tolerancia a fallos: Se deben reestructurar
las tablas de gestión en función del mismo.
SMP
Características
Desventajas
Cuestiones de Diseño
22
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Ventajas de un MicroKernel
Uniformidad de interfaces: Los servicios se utilizan mediante paso de mensajes esto impone una interfaz uniforme.
Extensibilidad: Facilita la extensibilidad ya que sólo es necesario modificar o añadir los servicios implicados.
Flexibilidad: Se pueden añadir o reducir características del SO.
Portabilidad: Los cambios necesarios para portar un SO a un nuevo procesador (no intel) son menores.
Fiabilidad: Se puede probar de un modo más riguroso.
Soporte a sistemas distribuidos: Un proceso puede enviar un mensaje sin saber en que máquina reside el destinatario.
Soporte para Sistemas Operativos Orientados a Objetos (OOOS)
Ventajas de un
MicroKernel
23
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Rendimiento de MicroKernels
o La desventaja potencial es que consume tiempo la comunicación a través del microkernel respecto a un simple SystemCall.o Las experiencias indican que más allá de la desventaja el rendimiento es igual o mayor a un sistema por capas.
El microkernel puede reconocer interrupciones, convertirlas en mensajes pero no gestionarlas, las gestiona el proceso receptor del mensaje.
Los procesos se comunican mediante
mensajes
Header: PID origen y PID destino.
Body: Puntero a un bloque de datos, datos
y información de control.Si los procesos no
comparten memoria implica copiar el mensaje
en la memoria.
Mach incorporó la idea de tener al Paginador como proceso aparte.
Cesión: un proceso puede ceder varias de sus páginas a otro proceso, el Kernel se encarga de reasignarlas.
Asociación: Se puede compartir memoria entre los procesos.
Rellenado: un proceso puede reclamar cualquier página concedida o asociada a
otro.
Diseño de MicroKernel
Gestión de Memoria a Bajo Nivel
Comunicación entre Procesos
Gestión de interrupciones y E/S
24
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO V: “Concurrencia: exclusión mutua y sincronización”
Compartir recursos globales tiene riesgos
Múltiples aplicaciones
Aplicaciones estructuradas : implementadas como un
conjunto de procesos o hilos
Estructura del SO : implementado como un
conjunto de procesos o hilos
Dificultades
1.0
Seguir la pista a los procesos (Por medio del
PCB)
Asignar y retirar recursos a cada proceso activo
Proteger los datos y recursos de los
procesos
Evitar el race condition
Interacción entre
procesos2.0
Solo un proceso a la vez puede estar ejecutando
en su región crítica
DefinicionMétodos para
conseguirla3.0
Debe cumplirse la exclusión mutua.Un proceso que se interrumpe en una sección no
crítica debe hacerlo sin interferir con los otros procesos.
Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente, no puede permitirse el deadlock o startvation.
Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar a la suya debe poder hacerlo sin problema.
No se deben hacer suposiciones sobre la velocidad relativa de los procesos o el número de procesadores.
Un proceso permanece en su sección crítica sólo por un tiempo finito.
Requisitos
Labores del SO
Concurrencia
Exclusión mutua : Es necesaria al
tener concurrencia
Contextos en que puede presentarse
25
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Es difícil la gestión óptima de recursos
Es difícil localizar un error de programación. Los
resultados en general no son deteministas reproducibles
Dificultades
1.0
Monoprocesador
Multiprocesador
Interrupciones
Procesos que simultáneamente acceden
a una variable global
Motivos
26
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Definiciones
Race condition : Situación en la cual el resultado de 2 o + procesos concurrentes depende del orden de ejecución
Región crítica : Parte de un proceso en la que tiene acceso a un recurso crítico
Recurso crítico : Recurso que solo puede ser utilizado por 1 proceso a la vez
Grado de conocimiento de los procesos
Relación Influencia de un proceso en los otros Posibles problemas de control
No tienen conocimiento de los demás
Competencia Los resultados de un proceso son independientes de las acciones de los otros
Los tiempos de los procesos pueden verse afectados
Exclusión mutua
Deadlock Starvation
Tienen conocimiento indirecto de los otros (por ejemplo, objetos compartidos)
Cooperación por compartimiento
Los resultados de un proceso pueden depender de la información obtenida de los otros
Los tiempos de los procesos pueden verse afectados
Exclusión mutua
Deadlock Starvation Coherencia
de datosTienen conocimiento directo de los otros (hay disponibles unas primitivas de comunicación)
Cooperación por comunicación
Los resultados de un proceso pueden depender de la información obtenida de los otros
Los tiempos de los procesos pueden verse afectados
Deadlock Starvation
Interacción entre
procesos2.0
27
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Definiciones
Live-lock : dos procesos están bloqueados, pero cualquier cambio en la velocidad relativa de los dos procesos rompería este ciclo y permitiría a uno entrar en la sección crítica.
S es el semáforo, que en si es una estructura. Las primitivas Wait y Signal SON PRIMITIVAS (NADIE LAS PUEDE INTERRUMPIR).
Con Busy-Waiting
Sin Busy-Waiting
Por SW
Alg. de Dekker
Alg. de Peterson
Por HW
Deshabilitar interrupciones
Instrucciones especiales del
procesador
Métodos para
conseguirla3.0
Test and Set : una variable global iniciada en 0. TS la cambia de 0 a 1 y viceversa. Si la pone en 1, devuelve true y se entra a la
región crítica, sino devuelve false
Intercambiar : una variable global iniciada en 0. INTERCAMBIAR cambia esa
variable por otra en iniciada en 1. Si se cambio a 1 se entra a la región critica, sino
no.
Por SO
Semáforos3.1
Monitores3.2
Paso de mensajes
3.3
28
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Un semáforo débil es aquel que no especifica como se retiran los elementos de la cola de bloqueados del wait(s);Un semáforo robusto es aquel que implementa FIFO en la cola de bloqueados del wait(s);Los semáforos binarios toman valores entre 1 y 0.Los semáforos generales o contadores toman valores cualquieras > 0.
Dos o + procesos cooperan por medio de simples señales, de forma que se obliga a un proceso a detenerse en un determinado lugar a la espera de una señal específica.
Signal(S), V (S) o Up(S): Aumenta el valor del semáforo. Si el valor < 0 => se
desencola a un proceso que había quedado bloqueado para que continúe.
Wait(S), P(S) o Down(S): Disminuye el valor del semáforo. Si
el valor es < 0 => el proceso se bloquea.
Semáforos3.1
Problemilla: es jodido distribuir las funciones wait y signal sin advertir el efecto global de estas operaciones, pueden producir deadlock y starvation, hay que tener cuidado.
29
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Monitores
Monitores
Las variables de datos locales están solo accesibles para los procedimientos del monitor y no para procedimientos externos.
Un proceso entra en el monitor invocando a uno de sus procedimientos.
Sólo un proceso puede estar ejecutando en el monitor en un instante dado, cualquier otro proceso que haya invocado al monitor quedará suspendido mientras espera a que el monitor esté disponible.
Puede ofrecer exclusión mutua fácilmente.
Características
Se proporcionan dos herramientas de sincronización atómicas
cwait(condicion); bloquea al proceso que llama a la condición c. El monitor está ahora disponible para ser usado por otro proceso.csignal(condicion); reanuda la ejecución de un proceso bloqueado por un cwait bajo la MISMA condición. Si no hay ninguno, no hace nada.El monitor tiene un único
punto de entrada. Solo un proceso puede estar en el monitor en cada instante.
Luego de hacer csignal(condicion) sale del monitor, si no está al final del procedimiento, el proceso que da la señal se bloquea según Hoare. Se los sitúa en una cola de urgentes para usar el monitor por separado.
Si el monitor está programado OK, el acceso al recurso protegido es correcto para TODOS los procesos.
El problema surge en:Si el proceso no terminó su ejecució, se suspenderá y luego se reanudará de nuevo (2 process switch).La planificación de los procesos debe ser fiable, cuando se ejecuta un csignal(cond); hay que garantizar que entre al monitor un proceso que se quedó bloqueado por la condición (si hay) y no otro.
Para eso surge cnotify(cond); que indica que el proceso notifica a los demás que liberó la condición y continúa ejecutando, el elegido de la cola de blokeados por la condición intentará entrar al monitor hasta que lo logrará. Puede haber starvation si el proceso que notifica no sale nunca del monitor, por eso se implementa un temporizador que obliga al proceso a dejarle el monitor a quien pueda ejecutarse.
30
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Paso de mensajes
Fácil de implementarse en sistemas distribuidos.Se usan dos primitivas:
Send(destino, mensaje) Receive(origen, mensaje)
La comunicación entre mensajes implementa un grado de sincronización.Las funciones pueden ser blokeantes o no blokeantes
Send blokeante y receive blokeante: Se conoce como rendezvous. Permite una fuerte sincronización entre procesos. Send no blokeante y receive blokeante: Esta es la combinación más útil. Send no blokeante y receive no blokeante: nadie espera nada.
Hay que tener cuidado con el send no blokeante ya que puede originar que un proceso genere mensajes repetidamente si no se lo recata. El send no blokeante obliga al programador el peso de determinar que mensaje se recibió: los procesos deben emplear un ACK de messages.
Direccionamiento directo
La primitiva send incluye una identificación del proceso destino. Receive puede gestionarse de dos formas: una es que se aclare de quien se está esperando el message (direccionamiento explicito), y la otra es que el parámetro ‘origen’ nos retorne de quien recibió el mensaje que recibió y así chequear que hacer (direccionamiento implicito).
Direccionamiento indirecto
Se envían los messages a una estructura de datos compartida, formada por colas llamadas mailboxes o buzones. Así, un proceso envía messages al mailbox apropiado y el que le gustaría recibir los mensajes de ese proceso, los recoge de ese mailbox respectivo.
Se permite mayor flexibilidad en el uso de mensajes.Puede permitir interacciones 1:1 , 1:N o N:M entre emisores y receptores.Si es N:M se denomina port o puerto al mailbox.Si es 1:N es un emisor que difunde sus mensajes a muchos receptores.
31
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO VI: “Concurrencia: deadlock y starvation”
Puede ser usado con seguridad por un proceso y no se agota con el uso. Ej: Procesador, canal de E/S,
memoria principal, semáforos, etc
Puede ser creado (producido) y destruido (consumido). Ej:
Interrupciones, señales, mensajes, información de
buffers de E/S, etc.
Exclusión mutua: solo un proceso puede usar un recurso cada vez.
Retención y esperar: un proceso puede retener recursos mientras espera que le asignen otros.
No apropiación: ningún proceso puede ser forzado a abandonar un recurso que retenga.
Círculo vicioso de espera: existe una cadena cerrada de procesos.
PrevenciónPredicción
Detección
Condiciones
Formas de tratalo
Consumibles
Reutilizables
Recursos
DEADLOCK: bloqueo permanente de un conjunto de procesos que compiten
por los recursos del sistema o bien se
comunican unos con otros.
A cada recurso se le asocia un índice, si un proceso tiene solo un recurso puede pedir recursos con índice mayor.
Exclusión mutua: no puede anularse porque es necesaria.
Retención y esperar: se exige que todos los procesos soliciten de un saque todos los recursos que necesiten y se bloqueen hasta obtenerlos a TODOS.
No apropiación: solo se aplica a recursos cuyo estado puede salvarse y restaurarse fácilmente. Al bloquearse un proceso debe liberar los recursos de los que se apropió, o sino, si un proceso está usando el recurso, se le puede pedir que lo libere (si el proceso tiene mayor prioridad).
Recursos sin uso durante un período considerable.Mucho tiempo de suspensión para obtener los recursos, pudiendo haber ejecutado algo de código.Puede no conocerse por adelantado todos los recursos que se necesitan.
Problemas
Directa: evita alguna de las tres condiciones primeras.
Prevención: elimina la posibilidad de que
ocurra deadlock.
Indirecta: evita la cuarta condición.
32
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
33
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Vector Recurso: (R1,R2,R3,... ,Rn)Vector Disponible: (D1,D2,D3,…,Dn)
Matriz Demanda Máxima (exigencias de c/proceso para cada recurso):
Matriz Asignación (cant de recursos asignados a cada proceso):
Cada columna representa a un recurso.Cada fila representa a un proceso.
Un proceso solo iniciará si para cada recurso i:
Ri ≥ E(ProcesoNuevo, Ri) + ∑E(ProcesoK,Ri) (Sumatoria desde K=1 hasta N)
Se tiene que cumplir además que:Ri ≥ E(ProcesoNuevo, Ri) ≥ A(ProcesoNuevo, Ri)
Se necesitan conocer las peticiones futuras de recursos.Permite mayor concurrencia que la prevención.Los procesos NO deben estar sincronizados.
Chequeo si puedo ejecutar a algún proceso con los recursos que tengo disponibles y lo que el proceso demandó y se le fue asignado, si es así, lo ejecuto hasta el final.Libero los recursos que se le asignaron, y descartó a proceso.Comienzo de nuevo.Si algún proceso no se puede ejecutar, hay un estado no seguro.Hay que considerar que los procesos liberan TODOS los recursos que usaron, o no finalizan
Algoritmo del banquero
Predicción: se hacen elecciones acertadas para nunca llegar a deadlock, y se la
evita.
NO ASIGNAR UN
RECURSO
Enfoques
NO INICIAR UN PROCESO
Se asume que todos los procesos expresan su demanda máxima a la
vez. Estado Seguro: existe al menos una secuencia que no lleva a deadlock. Todos los procesos se pueden ejecutar.Estado inseguro: no existe ninguna.
34
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Marcar procesos con fila de matriz asignación nula.Vector auxiliar W = Vector disponible.Buscar un proceso no marcado que: su fila en la matriz solicitud sea <= W , si no se encuentra a ningún proceso => END.W = W + MatrizFilaAsignacion, volver a 3.
Si algún proceso no queda marcado => DEADLOCK
Abortar todos los procesos bloqueados.
Retroceder cada proceso bloqueado hasta un punto de control y volver a ejecutar.
Abortar sucesivamente procesos bloqueados hasta que no haya deadlock.
Menor tiempo de procesador consumido.Menor número de líneas de salida producidas.Mayor tiempo restante estimado.Menor número de recursos asignados.Prioridad más baja.
Criterio de Selección.
Estrategias de recuperaciónDetección: el SO ejecuta una rutina de detección de deadlock y si lo detecta intenta recuperarse.
Apropiarse de recursos sucesivamente hasta que no haya deadlock.
35
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Estrategia Integrada de DeadLock:
o Agrupar los recursos en clases (memoria principal, recursos internos, etc).o Ordenación líneal de las clases (prevención directa).
Cada clase emplea un algoritmo apropiado.
36
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO VII: “Gestión de Memoria”
En un sistema multiprogramado, la memoria se divide en: SO y Área de usuario (para sus procesos).
Requisitos de la gestión de memoria
Tipos de direcciones
Estática Dinámica
Paginación
Segmentación
Carga y Montaje de Procesos
Buddy System Partición de memoria.
Técnicas de administración de
Memoria
Gestión de Memoria: llevar a cabo dinámicamente la tarea de subdividir a los procesos
para facilitar la multiprogramación y el
swapping.
37
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Requisitos de la gestión de memoria
Reubicación
Un proceso no debe tener asignado un espacio fijo en la memoria principal. Cuando es “Suspendido” y vuelto luego a “Listo” debe poderse ubicar en otro espacio de
memoria.
El SO debe conocer la ubicación de la imagen de cada proceso.El SO y el HW del procesador deben ser capaces de traducir las referencias del programa a las direcciones físicas reales donde se encuentre actualmente el programa en la memoria principal.
Cada proceso debe protegerse contra interferencias no deseadas de otros procesos (accidental o intencionadas).
El HW del procesador debe ser capaz de abortar estas instrucciones en el momento de ejecución.
Es respaldado por los mecanismos de reubicación.
Compartimiento
Se debe tener la flexibilidad de permitir el acceso de varios procesos a la misma zona de memoria principal,
sin comprometer la protección básica.
Es respaldada por los mecanismos de reubicación.
Protección
38
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Requisitos de la gestión de memoria
La memoria principal se organiza como un espacio de direcciones lineal que consta de una secuencia de bytes o palabras.
La memoria secundaria se organiza de forma similar.La mayoría de los programas se organizan en módulos.
Los módulos pueden escribirse y compilarse independientemente.
El sistema resuelve las referencias entre módulos.
Ofrece distintos grados de protección a módulos con un
escaso coste adicional.
Mecanismos de compartición de módulos.
La memoria principal mantiene los programas y datos de uso actual, la memoria secundaria mantiene
los programas y datos a largo plazo.
La responsabilidad del flujo entre la memoria principal y la memoria secundaria no se le asigna al programador porque:
En un entorno multiprogramado, durante la codificación no se conoce cuanto espacio habrá disponible o donde estará el programa.La memoria principal disponible para un programa y sus datos puede ser insuficiente (se puede usar overlaying, pero gasta tiempo de programador).
Organización física
Organización lógica
El SO y el HW pueden tratar a los programas en memoria en forma de módulos de algún tipo.
Ventajas
39
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Fragmentación Interna: malgastar espacio dentro de una partición.
La memoria se divide en regiones con límites fijos durante la generación del sistema. Un proceso se carga en una partición de
menor o igual tamaño.
Tipos
De igual tamaño
Algoritmo de ubicación: un proceso se carga en
cualquier partición libre.
Algoritmo de ubicación: se asigna a cada proceso la partición más pequeña a la que quepa. Hay una cola de procesos por partición.se asigna a cada proceso la partición más pequeña en la que quepa y esté disponible. Hay una cola única de procesos.
Ventajas
Poco overhead y sencillo de implementar.
Un programa puede no caber en la partición más
grande. Se debe usar overlaying.
Fragmentación Interna
La cantidad de procesos concurrentes está limitada por
el número de particiones.
Desventajas
De distinto tamaño
Estática
Partición de Memoria
40
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Fragmentación externa: la memoria fuera de toda partición se fragmenta cada vez más, tanto que no se puede ubicar a ningún proceso.Compactación: Desplazar los procesos y ponerlos contiguos para que la memoria libre quede toda junta y así eliminar la fragmentación externa. Consume mucho tiempo de CPU hacerlo.
Partición de memoria
Las particiones son variables en número y longitud. Cuando se carga un proceso se le asigna exactamente tanta memoria como necesite, no más.
No hay fragmentación interna.
Hay fragmentación externa, solucionada por la compactación, aunque esto consume tiempo.
Best-Fit: Se elige la partición más chica y disponible donde quepa el proceso. Es el peor, se llena de bloques
muy pequeños como para ubicar a algún proceso futuro.
First-Fit: Recorre la memoria desde el principio y escorge la primer partición donde quepa el proceso. Es el más sencillo y el más rápido. Aunque asigna en el inicio de la memoria y la barre
continuamente.
Next-Fit: Recorre la memoria desde el lugar de la última ubicación y elige la siguiente partición donde quepa el proceso.
El bloque final de memoria se particiona más rapidamente.
Worst-Fit: Asigna el bloque más grande posible.
Algoritmo de ubicación
Dinámica
Desventajas
Ventajas
41
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Partición de memoria
Es inferior a la paginación y segmentación, pero es útil en sistemas paralelos con un eficiente método de asignar y liberar programas en paralelo. Genera fragmentación interna, e intenta mejorar la fragmentación externa.
Me cae un proceso que ocupa X memoria.Lo debo ubicar en un bloque tal que:
Si es = X, lo ubico tranka.Si es > X, me fijo si lo puedo partir en 2 pedazos al bloque, tal que en una mitad se pueda meter a X.
Si se libera un bloque que se había partido antes y tiene a su buddy (colega) libre, se unen.
Buddy System
42
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Referencia a una posición de memoria independiente de la asignación actual de la memoria.
Se debe hacer una traducción a una dirección física.
Caso particular de dirección lógica, se conoce un punto de dirección física (en gral el comienzo del proa) y se referencia a un offset desde ese
punto.
Se necesita un mecanismo de HW para hacer una traducción a una dirección física.
Para obtener la dirección física:RegistroBase + DirecciónRelativa < RegistroLímite
Sino se genera una excepción que el SO debe atender. Esto es por protección.
Posición real de la memoria.
Dirección lógica
Tipos de direcciones
Dirección relativa
Dirección física
43
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
No hay fragmentación interna.
Pequeña cantidad de fragmentación
interna.
La memoria principal se divide en un conjunto de pequeños frames de igual tamaño, y cada proceso se divide en un conjunto de páginas de igual tamaño que los frames.
Un proceso se carga situando sus páginas en frames libres pero no necesariamente contiguos.
El SO mantiene por cada proceso una tabla de páginas (MPT)
Se utilizan referencias a direcciones lógicas: NroPag|Offset
El procesador debe saber como acceder a la MPT del proceso. Posee un registro para esto.
El SO mantiene una
lista de frames libres.
El tamaño de page y frame son potencia de 2. La dirección relativa al inicio del
programa y la dirección lógica son iguales.Bus de direcciones: n bits
el tamaño de la página 2k
k: nro de bits en el offset.n-k: nro de bits por page.2n-k nro de pages
TRADUCCION DE DIRECCION POR HW
Me llega: Page|OffsetUtilizo page como índice en la MPT del proceso y obtengo el frame asignado.Nro de Frame * 2k concatenado con offset = DIR FÍSICA!
Paginación Simple
Ventajas
Desventajas
44
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Cada proceso se divide en una serie de segmentos (que pueden ser de diferente tamaño). Se los carga situándolos en memoria principal y no tienen
porque ser contiguas.
Fragmentación externa, menor que la partición dinámica.
No hay fragmentación interna.
Se utilizan referencias a direcciones lógicas: Número de Segmento|Offset
El SO mantiene por cada proceso una tabla de segmentos.
El SO mantiene una lista de bloques libres con su longitud.
Ventaja: permite organizar los programas y datos.
Desventaja: el programador debe ser consciente de la limitación de tamaño máximo de los segmentos.
Traducción de direcciones por HWMe llega NroSegmento|Offset Utilizo el nro de Segmento como índice en la tabla de segmentos y obtengo la posición física del segmento.Sumar posición física del segmento con offset.Si supera la longitud del segmento, la dir. no es válida.
Visible al programador.
Ventajas
Desventajas
Segmentación
45
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Carga y Montaje
Código Objeto: código de programa y datos.Carga: Llevar un único código objeto a memoria principal y crear una imagen de proceso.Montaje: Toma como entrada una colección de módulos objeto y genera un módulo de carga.
CargadorTiempo de enlace Función
Tiempo de programación El programador especifica direcciones físicas en el programa.
Tiempo de compilación o ensamblaje El programa contiene referencias simbólicas a direcciones y el compilador o ensamblador las convierte en direcciones físicas reales.
Tiempo de carga El compilador o ensamblador genera direcciones relativas. El cargador traduce éstas a direcciones absolutas en el instante de carga del programa.
Tiempo de ejecución El programa cargado conserva direcciones relativas, el hw del procesador las traduce dinámicamente a direcciones físicas reales.
MontadorTiempo de montaje Función
Tiempo de programación No se permiten referencias a programas o datos externos, el programador sitúa dentro del programa el código de todos los subprogramas referenciados.
Tiempo de compilación o ensamblaje El ensamblador debe ir a buscar el código fuente de cada subrutina que sea referenciada y la ensambla como unidad.
Creación del módulo de carga Todos los módulos objeto se han ensamblado usando direcciones relativas. Estos módulos se montan todos juntos y todas las referencias se declaran de nuevo relativas al origen del módulo de carga final.
Tiempo de carga Las referencias externas no se resuelven hasta que el módulo de carga sea ubicado en la memoria principal.
Tiempo de ejecución Las referencias externas no se resuelven hasta que el procesador ejecute las llamadas externas. En ese momento, se interrumpe el proceso y se monta el programa llamador con el módulo que se necesita.
46
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO VIII: “Memoria Virtual”
Conjunto Residente: Parte de un proceso que está en Memoria Principal, su tamaño es la cantidad de Memoria Principal asignada a un proceso. Son los frames asignados.Hiperpaginación (Trashing): El procesador consume más tiempo intercambiando frames que ejecutando instrucciones.Principio de cercanía: las referencias a datos y programas tienden a agruparse.
Memoria Virtual
Avances de la paginación y la segmentación
Todas las referencias de un proceso son direcciones lógicas traducidas a físicas en tiempo de ejecución. Así se puede reubicar un proceso.
Un proceso puede dividirse en partes (páginas o segmentos) que pueden estar dispersas en Memoria
PrincipalComo resultado no será necesario que todas las
páginas o segmentos de un proceso estén en Memoria
Principal durante la ejecución.
El procesador con la tabla de páginas o segmentos, siempre es capaz de determinar si una referencia está o no en el conjunto residente. Si encuentra una referencia que no está en el conjunto residente genera una excepción “fallo de
acceso a memoria” (en paginación Page Fault). Pone al proceso a “Bloqueado” , y trae a Memoria Principal la parte del proceso referenciada mediante una
operación de E/S y puede expedir otro proceso.
Ventajas:Se pueden mantener más procesos en MP.Un proceso puede ser más grande que la MP.Necesita soporte de HW y el SO debe gestionar los frames.
El principio de cercanía sugiere
que este esquema funciona.
47
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Estructuras utilizadas en Paginación Virtual
MPT (Memory Page Table): contiene todas los frames que posee un proceso, indicando si están en memoria principal o secundaria y el número de frame o la dirección en disco. Se consulta mediante una correspondencia directa con el número de página de la dirección lógica.TLB (Translation Lookaside Buffer): Contiene aquellas entradas a la MPT usadas hace poco, indicando a que Proceso pertenecen. Reside en la CACHÉ. El procesador consulta simultáneamente varias entradas de la TLB (correspondencia asociativa), si no encuentra nada, entonces verifica la MPT del proceso y actualiza TLB.
Tamaño de Página – Factores a considerar
1. Fragmentación interna: a menor tamaño de página, menos fragmentación interna y más número de páginas => mayor grado de multiprogramación => más procesos en la cola de listos. La MPT por proceso es más grande.
2. Características físicas de los dispositivos de memoria secundaria: Son propicios para mayores tamaños de página, transfieren por bloques de datos.
3. Efecto en el Page Fault
4. Tamaño de la memoria física
P M # Frame Bits de Control
MPT (Memory Page Table)
Diferentes Páginas (es el subíndice)
Dirección Virtual o Lógica de Memoria:
NroPagina|Offset
Con el número de página, tenés el subíndice en la MPT, luego obtenés el #Frame y la dirección física es: NroFrame*TamañoPágina|Offset
Tamaño Página es 2cantidad_de_bits_para_offset
48
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Estructura de la MPT (Memory Page Table)
Las MPT también están sujetas a paginación (pueden estar en Memoria Principal o en Memoria Virtual):
Por una referencia a memoria pueden haber dos fallos -> 1 para MPT, otro Page Fault de página de proceso.
Tabla de páginas invertidas
Tabla de páginas Raiz: siempre en MP y una por cada proceso.
PTE a UserTable
Tabla Raiz
Dirección virtual:OffsetTablaRaiz|OffsetUserTable|
OffsetMP
Procesador tiene un registro que contiene un puntero a la tabla raiz que se actualiza cuando se
carga el proceso.
Se emplea una HashTable. La parte de número de página se le aplica la función
hash(x), el índice de la HashTable tiene un puntero a Página de la Tabla Invertida, y
luego un campo encadenamiento a la siguiente página correspondiente. A la
misma función hash.
Se emplea una parte fija para las tablas. Puede haber collision, se
la soluciona con el encadenamiento
Estructura de la MPT
Esquema de 2 niveles
Enfoques
49
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Segmentación Virtual – Implicaciones
o Simplifica la gestión de datos crecientes. Un segmento puede crecer y si toca a otro el SO lo mueve a un área mayor. Si no puede hacerlo lo descarga y será devuelto en otro momento.
o Los módulos pueden escribirse y compilarse independientemente. El sistema resuelve las referencias entre módulos.
o Proporciona mecanismos de compartición de módulos.o Proporciona mecanismos de protección entre módulos.
Estructura de la Tabla de Segmentos
PAGINACION Y SEGMENTACION COMBINADAS
El espacio de direcciones del usuario se divide en segmentos según el programador. Cada segmento se divide en páginas.
Algoritmo de traducción
1. Al ponerse en ejecución el proceso, se carga de la PCB un puntero a la tabla de segmentos en un registro del procesador (SP – Segment Pointer).
2. Al llegar una dirección virtual: SP+NroSegmento obtengo un pointer a la base de una de las tablas de páginas del proceso (la MPT), hay una MPT por segmento.
3. Luego hago, BaseMPT+NroPagina y puedo obtener el número de frame o Page Fault :(
4. Si hago (NroFrame*TamañoDePagina)+Offset = DIRECCION FISICA POSTA!!!!
Estructuras
Dirección Virtual
NroSegmento|Offset
P M Otros Bits de control Base de Segmento Long de Segment
Dirección Virtual
NroSegmento|NroPage|Offset
BitsControl Long Segment Base Segment P M Bits Control # Frame
50
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Software del SOEmplear o no memoria
virtual
Uso de paginación, segmentación o ambas.
Algoritmos empleados para problemas de
gestión de memoria
Dependen del HW
Políticas de lectura: Relacionada con la decisión de cuando se debe
cargar una página en MP.
Paginación por demanda: se trae una página a la MP sólo cuando se hace
referencia a esa página.
Si las páginas de un proceso se cargan secuencialmente en memoria secundaria es más eficiente traer un bloque que de a una.
No es efectiva si las páginas extras que se traen, no se referencian… se hizo una sobrecarga en la E/S al dope.
Para segmentación pura, son los mismos que en Particiones dinámicas.
Para paginación pura o paginación con segmentación es
innecesaria.
TIPOS
Políticas de ubicación: Determinar donde va a recidir una parte del proceso en la MP
Paginación por previa: se cargan otras páginas distintas a las demandadas, debido a un
PageFault
El diseño depende de…
Software del SO
51
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Software del SO (Continuación) – Políticas de Reemplazo
Bloqueo de Frames: se asocia un bit de BLOQUEO a cada frame, puede guardarse en una tabla de frames o en la MPT. Si el bit está activado, no puede ser reemplazada la página. Generalmente el SO bloquea sus frames, así no se autoreemplaza.Políticas de reemplazo: Trata de la selección de la página a reemplazar en la MP cuando se debe cargar una nueva página y no hay un frame Libre. Su objetivo es reemplazar la página que tenga una menor posibilidad de ser referenciada en un futuro cercano. Cuanto más elaborada y más sofisticada es la política de reemplazo, mayor overhead de SW del SO y HW del procesador.Anomalía de Belady: Es una cosa medio loka, que ocurre solamente en el algoritmo FIFO… es cuando al aumentar la cantidad de frames que se le asignaron a un proceso, aumenta la cantidad de page faults. Buscar en google ejemplos si no lo creen.
Algoritmos de reemplazo:
o OPT – Optimal: Selecciona la página que más tiene que esperar para ser referenciada. Es la que produce la menor cantidad de Page Faults, por eso es la ideal. Resulta imposible de implementar pero sirve para comparar con los demás algoritmos.
o LRU (Least Recently Used): Selecciona la página que no ha sido referenciada desde hace más tiempo. Es cercana a la OPT en eficiencia. Es difícil de implementar, pero se puede simularla en SW usando dos métodos:
PILA: Se guarda en la cima de la pila a las páginas que se van referenciando, cuando hay que reemplazar a alguna página se selecciona la última que se encuentra en la PILA. Es difícil de implementar, y produce un overhead terrible.
TIMESTAMP: Se guarda la última referencia en un campito para saber cuando fue la última vez que se referenció la página.
o FIFO: Selecciona la página que ha estado más tiempo en la memoria. Apesta, ya que que haya estado más tiempo en la memoria no significa que no se referencie mucho. Apesta mucho ya que se puede producir la Anomalía de Belady. Fácil de implementar.
o CLOCK: Se asocia un bit a cada frame (bit de uso). Cuando se carga una page por 1era. vez se pone en 1. Si se hace alguna referencia a algun frame, se lo pasa a 1 si está en el conjunto residente. Hay un puntero del clock que va dando vueltas por el conjunto de frames de la MP… va buscando un frame con bit de uso = 0, si lo encuentra entonces reemplaza a ese frame!... mientras vaya barriendo los frames, los que tienen el bit en 1 los pasa a 0.
o CLOCK CON BIT DE MODIFICACION: Además del bit de uso se agrega un bit de modificación, recorre sin cambiar el bit de uso, buscando bitdeuso=0 ^ bitdemodificacion=0. Si falla, entonces recorre poniendo bitdeuso=0 y busca: bitdeuso=0 ^ bitdemodificacion=1. Si falla, entonces repite de nuevo todo. Intenta evitar escrituras en memoria secundaria.
52
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Políticas del tamaño del conjunto residente.
El núm. de frames asignados a un proceso es fijo, determinado por el tipo de proceso, el programmer o el
admin. del SO
La página a reemplazar se elige del conjunto residente del proceso que tuvo el Page Fault
Desventaja: Es necesario decidir por anticipado la cantidad de memoria asignada a un proceso. Si te equivocaste, cagaste
En un principio se le asigna un núm. de frames a cada proceso, manteniendo el SO frames libres.
Cuando se produce un Page Fault se agrega un frame libre al proceso y se carga la page.
Si no hay más frames libres, la page a reemplazar se elige de todos los frames excepto de los blocked.
Desventaja: No hay ninguna disciplina que determine que proceso debe perder un frame cuando ya no hay más frames libres. Se contrarresta con el almacenamiento intermedio de pages, que sería tener una lista de pages reemplazadas por si las dudas alguien la referencia.
En un principio se le asigna un núm. de
frames a cada proceso.
La página a reemplazar se elige del conj.
residente del proceso que tuvo el PageFault
De vez en cuando, se vuelve a evaluar las asignaciones de frames a los procesos. Se aumenta o disminuye para
mejorar el rendimiento global
Asignación Variable y Alcance Local
Políticas del tamaño del
conjunto residente
Asignación Fija yAlcance Local
Asignación Variable y Alcance Global
53
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Estrategias para equilibrar en Asignación Variable y Alcance Local
Tiempo virtual: tiempo en el que el proceso está realmente en ejecución, por ejemplo: ciclos de instrucciones.
Si un frame no fue referenciado en ∆ veces se lo saca del conj. de trabajoSi un frame se referencia y no está en el conj. de trabajo, se lo agrega.
Supervisar el conjunto de trabajo de cada proceso.
Eliminar periódicamente frames que no pertenezcan al conj .de trabajo.
Un proceso puede ejecutar si su conj. residente incluye a su conj. de trabajo
El pasado no siempre predice al futuro.
Es impracticable una medida real del conj. de trabajo para cada proceso.
El valor de es ∆ desconocido y puede variar.
Desventajas
Estrategias para Asignación Variable
y Alcance Local
Estrategia motivada
Conjunto de Trabajo: Conjunto de páginas calculadas en un instante de tiempo virtual T, a las que un proceso ha hecho referencia en las últimas ∆ unidades de tiempo virtual
54
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Estrategias para equilibrar en Asignación Variable y Alcance Local (continuación).
Ningún frame se retira antes de que pase F unidades de tiempo.
Se asocia un bit de uso a cada frame, que se pone en 1 cuando se lo accede.
Cuando se produce un PageFault el SO anota el tiempo virtual (contadora) transcurrido desde el último PageFault
de ese proceso
Si ese tiempo virtual es:< a un umbral F => se le agrega un frame>= a un umbral F => se le quitan frames con bituso=0 y se ponen bituso=0 a todos los frames que quedaron en el conj. residente.
Puede mejorarse con un umbral superior para evitar el crecimiento.
Mejora aun más si se le pone un Almacenamiento Intermedio de Páginas
No rinde cuando se produce un desplazamiento a una nueva
ubicación.
PFF (Page Fault Frecuency): se verifica cada T tiempo los
PFF de un proceso y se lo compara contra un umbral.
Desventajas
Estrategias para Asignación Variable y
Alcance Local
55
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Estrategias para equilibrar en Asignación Variable y Alcance Local (continuación).
Grado de multiprogramación: Se refiere a la cantidad de procesos que pueden estar en MP.
Control de Carga – Otra cosa medio loka que hace el SO
Al comienzo de un intervalo de muestreo a los frames se le ponen bitdeuso=0
Si una página es referenciada => bitdeuso=1
Si se produce un PageFault se agrega un frame y se setea la page con bitdeuso=1
Al final del intervalo de muestreo se sacan los frames con bitdeuso=0
Variable Interval Sampled Working Set (VSWS): Intenta
solucionar el fenómeno de transición entre ubicaciones
Estrategias para Asignación Variable
y Alcance Local
Modera el grado de multiprogramación.
Si hay pocos procesos en MP => Mucho SwappingSi hay muchos procesos en MP => Mucho Trashing!!!
Estrategias (to be continued in next
page)
Control de Carga
56
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Estrategias para Controlar la carga
Estrategias para control de Carga
El conjunto de trabajo o el PFF: solo se puede ejecutar los procesos con conj. residentes suficientemente grandes
Criterio L = S
L: Tiempo medio entre PageFaultsS: Tiempo medio exigido para procesar un PageFault.Se deja de cargar procesos.
50%
El uso del dispositivo de paginación a 50%
Reloj adaptado
Se controla su velocidad
Si es < a umbral F
Se producen pocos PageFaults o hay muchas páginas sin referencias. Debe aumentar el grado de multiprogramación.
Se debe bajar el grado de multiprogramación.
Si es >= a umbral F
Para bajar el grado de multiprogramación, suspendo procesos.¿Qué proceso saco?El de prioridad menor.El que tiene más PageFault.El que se cargó a lo último en MP.El que tiene el menor tamaño de conj. residente.El que tiene el mayor tamaño de conj. residente.Al que le falte el mayor tiempo de ejecución.
57
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO IX: “Planificación en Monoprocesador”
Es recomendable ver la figura 9.2 de la página 386 de st.
Planificador de Largo Plazo: Organizar a los procesos que
van a ingresar al sistema.Decisión de pasar:
De “Nuevo” a cualquiera, y de cualquiera a “Terminado”
Planificador de E/S: decisión sobre que petición de E/S
será tratada por un dispositivo de E/S disponible.
Planificador de Media Plazo: Se encarga del swapping de los procesos.
Decisión de pasar: Cualquiera a “Bloqueado y Suspendido” y
Cualquiera a “Listo y Suspendido”, y viceversa.
Planificador de Corto Plazo: El famoso Dispatcher que determina que proceso va a
tomar el CPU.Decisión de pasar:
De Cualquiera a “Ejecutado”.
Criterios de Planificación
(a corto plazo).
Planificación de Monoprocesadores: consiste en
asignar los procesos al procesador de forma de cumplir
el tiempo de respuesta, la productividad y la eficiencia del
procesador.
Tipos
58
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Criterios orientados al UsuarioDe rendimiento Tiempo de retorno (Turnarround
Time)Intervalo entre el lanzamiento de un proceso y su finalización.Turnarround Time = Tiempo de Finalización – Tiempo de Llegada
De rendimiento Tiempo de respuesta (responsive Time)
Intervalo entre que se emite una solicitud y se recibe una respuesta.
De rendimiento Plazos Se deben cumplir los plazos de finalización especificados.
Otros Previsibilidad Un Trabajo se debe ejecutar aprox. en el mismo tiempo y con el mismo coste.
Criterios orientados al SistemaDe rendimiento Productividad Maximizar el núm. de procesos
terminados por unidad de tiempo.
De rendimiento Utilización del procesador Maximizar el tiempo que está ocupado el procesador.
Otros Equidad Los procesos deben ser tratados de igual forma y ninguno debe sufrir starvation.
Otros Prioridades Se debe favorecer a los de mayor prioridad.
Otros Equilibrio de Recursos Se debe mantener ocupados los recursos del sistema.
Algoritmos de planificación en el dispatcher
Non-Preemtive: Puede otro Proceso robarle el procesador con aprobación del SO.Preemtive: El proceso solo deja el procesador si termina o se bloquea en una E/S.
Algoritmo Tipo DescripciónFCFS (First Come First Serve) Non-Preemtive Es un FIFO apestoso.PRI (Prioridades) Puede ser cualquiera. Se ejecuta al proceso con más
prioridad. El algoritmo varía si es o no Preemtive.
RR (Round Robin) Preemtive Se basa en un Quantum (Q), se trata a la cola de listos como un FIFO, se ejecuta un proceso y se lo saca del procesador si se le acaba el Q o se bloquea antes que se le acabe.
SPN (Shortest Process Next) Non-Preemtive Se ejecuta al proceso de la cola de listos con mayor Burst de CPU.
SRT (Shortest Remaing Time) Preemtive(Solo en los momentos de llegada de nuevos proc.)
Se ejecuta al proceso de la cola de listos que le quede el menor Burst de CPU.
HRRN (Highest Response Ratio Next)
Non-Preemtive Se elige al que tenga el menor R = (w + s)/s
VRR (Virtual Round Robin) Preemtive Es como un RR, solo que si un proceso se bloquea por una E/S y no termino su Q, pasa a una cola auxiliar luego de desbloquearse por la E/S, donde ejecuta el Q que le restaba ejecutar. La cola auxiliar tiene más prioridad de ejecución.
FeedBack Preemtive Maneja muchas colas de listos
59
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
con prioridad N.Cuando un proceso ingresa al sistema, se mete en la cola RQ0 que es la que tiene más prioridad. Luego de que un proceso se ejecute, pasa a la cola de RQn+1 (la siguiente con menor prioridad).Cada proceso puede ejecutar el mismo Q, o diferentes Q según la cola “i” en la que esté = 2i
ATENCIÓN (IMPORTANTE): No es lo mismo SJF (Shortest Job First) que SPN (Shortest Process Next) ya que uno es para un LTS (Long Term Scheduler) y el otro para un STS (Short Term Scheduler), respectivamente. Pero el criterio es el mismo.
60
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CAPITULO X: “Planificación en Multiprocesador”
Este capítulo tiene MUCHA trash.Granularidad: frecuencia de sincronización entre los procesos del sistema.
Tipos de Multiprocesadore
s
Granularidad
Asignación de procesos a los procesadores
Uso de multiprogramación en cada procesador
Expedición real de procesos
Planificación de procesos
Planificación de threads
Reparto de carga
Planificación por grupos
Asignación dedicada de procesadores
Planificación dinámica
Características Requisitos
Métodos
Planificación de Multiprocesadores
Elementos de Diseño
Planificación en tiempo real
61
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Tipos de multiprocesadores
Clustering: Conjunto de procesadores relativamente autónomos. Cada uno tiene su propia memoria y sus canales de E/S. SMP: Conjunto de procesadores que comparten una MP y son controlados por un SO. Master/Slave: Hay un procesador de propósito general y otro que solo ejecuta al SO (Master). Si el Master cae, se cae todo a la mierda
Asignación de procesos a los procesadores
Tipo de Asignación: por demanda
Ningún procesador posee ninguna ventaja física en el acceso a la MP o dispositivos de E/S. Se tratan a los procesadores como un recurso reservado.
Tipos
Estática: Existe una cola a corto plazo para cada procesador, la asignación al procesador se hace una sola vez.
VentajasSobrecarga menor. Permite la planificación por grupos.
Un procesador puede estar ocioso con su cola vacía mientras que otros están pendientes.
Desventajas
Dinámica: Existe una cola global. Cada proceso se ejecuta en un procesador que esté libre.
Forma de asignación
Master/Slave
El Master es el responsable de la planificación y de la ejecución del SO. El resto de los procesadores
ejecutan programas de usuarios.
SMP
El SO se ejecuta en cualquier procesador. Cada procesador se autoplanifica.
62
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Uso de Multiprogramación en cada procesador
Expedición real de los procesos
Habla que una estrategia sencilla como ser FIFO puede ser más efectiva que una compleja como SRT, HRRN, RR, etc.
Planificación de Procesos
Habla de nuevo que la planificación es menos importante al ser N procesadores, dice que si uno se queda al pedo no es tanto problema… dice que una disciplina FIFO con prioridades basta.
Mejora el rendimiento con la multiprogramación.
No resulta tan importante que cada procesador esté ocupado al máximo. Se debe tratar de obtener el
mejor rendimiento para las aplicaciones.
Grano medio
Uso de multiprogramación en cada procesador
Grano Grueso o independiente
63
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Planificación de Threads
Al ejecutarse varios threads en diferentes procesadores se obtiene un paralelismo real y aumenta drásticamente el rendimiento.
Aunque si los threads exigen una considerable interacción (grano medio), diferencias en la planificación y gestión tienen un impacto importante.
METODOSSe mantiene una cola global de threads listos y cada procesador cuando está ocioso, selecciona un thread de la cola.
La carga se distribuye uniformemente. Ningún procesador estará ocioso.
No es necesario un planificador centralizado.
La cola global puede organizarse y accederse a ella mediante diferentes algoritmos.
Ventajas
La cola central ocupa región de MP que se debe acceder mediante exclusión mutua y puede convertirse en un cuello de botella.
Es improbable que los threads expulsados reanuden su ejecución en el mismo
procesador. La Caché será menos eficiente.
FCFS
Primero el de menor número
de threads
Primero el de menor número de threads
(Preemtive). Se ejecuta al llegar un
nuevo thread.
Planificación de Threads
Reparto de Carga
Desventajas
Tipos
64
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Continuación de planificación de threads – Métodos
Se reduce el overhead de planificación. Una decisión afecta a varios procesos y procesadores.
Métodos
Se planifica un conjunto de threads afines para su ejecución con un conjunto de procesadores uno a uno, esto es simultáneamente.
Se reducen los bloqueos por sincronización, se necesitan menos context switch y esto incrementa el rendimiento. Esto es porque los procesos próximos se ejecutan en paralelo.
Uniforme: a cada grupo se le asigna 1/num.grupos del tiempo disponible de
los procesadores.
Por pesos: a cada grupo se le asigna cantthreadsdegrupo/canthreadstotale
s
División de tiempo del procesador
VentajasPlanificación por grupos
65
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
Continuación de planificación de threads - Métodos
Es una planificación por grupos pero además:Se asigna a cada thread un procesador fijo hasta que termine.No hay multiprogramación de procesadores.Se dedica un grupo de procesadores a una aplicación mientras dura.
En un sistema con muchos procesadores la utilización del procesador no es importante como medida de rendimiento.
La anulación total del Context Switch en la ejecución de un programa acelera la ejecución.
Se emplea un lenguaje y unas herramientas del sistema que permiten cambiar dinámicamente el número de threads de un proceso.
Si hay procesadores desocupados se usan para satisfacer la petición.
Si el trabajo está recién llegado se le asigna un procesador quitándoselo a otro proceso que tenga más de uno (en caso de que todos los
procesadores estén ocupados).
Si no se satisface parte de una petición quedan pendiente hasta que un procesador se libere o hasta que se anule la petición.
Al liberarse un procesador: se explota las peticiones no satisfechas => se asigna un procesador a cada trabajo sin procesador. Después se asigna al resto de procesadores mediante FIFO a los procesos en cola.
Política de asignación de procesadores
Planificación dinámica
Asignación dedicada de procesadores
Métodos
Observaciones
66
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
PLANIFICACIÓN EN TIEMPO REAL (SUELEN TOMARLO EN TEORIA DE FINALES)
La exactitud del sistema no depende solo del resultado lógico de un cálculo sino también del instante en que se produzca el resultado.Tarea de tiempo real: debe ir al paso de los sucesos que se ocupa.
o Tipos Rígida: si no se cumple el plazo, el sistema se considera en falla. Flexible: se tiene un plazo asignado, pero se permiten desvíos.
o Tipos2 Aperiódica: puede ocurrir en un momento que no se puede predecir. Periódica: se produce cada período T
REQUISITOS1. Determinismo: Consiste en realizar las operaciones en instantes fijos y
predeterminados o en intervalos predeterminados. Velocidad de respuesta a interrupciones. Poseer la capacidad para gestionar todas las peticiones en tiempo requerida.
2. Sensibilidad: Tiempo que consume un SO en dar servicio a una interrupción. Tiempo para iniciar la gestión de interrupción y comenzar la ISR (Interrupt Service Routine). Tiempo para ejecutar la ISR.
3. Control de usuario: es mucho mayor que en un SO ordinario, ya que el tipo puede controlar las prioridades y demás frutas.
4. Fiabilidad: No se aceptan pérdidas o degradaciones del rendimiento.5. Tolerancia a fallos: conserva la máxima capacidad y los máximos datos posibles en
caso de fallos. El SO intentará corregir el problema o minimizar sus efectos mientras se ejecute.
6. De las otras dos surge el TIEMPO DE RESPUESTA
CARACTERISTICAS DE UNA PLANIFICACION DE TIEMPO REAL
1. Cambio rápido de procesos o threads2. Pequeño tamaño del SO (con mínima funcionalidad asociada).3. Rápida respuesta a interrupciones externas.4. Multitarea con herramientas de comunicación entre procesos.5. Uso de archivos secuenciales especiales (de alta velocidad).6. Planificación preemptive con prioridades.7. Reducción de tiempo de inhabilitación de interrupciones.8. Primitivas para demorar tareas y detenerlas y reanudarlas.9. Alarmas especiales y temporizadores.
PLANIFICACION EN TIEMPO REALDependen de si lleva a cabo un análisis de planificación, si la planificación es estática o
dinámica y si el resultado del análisis genera un plan de expedición de procesos.
o TIPOS DE ALGORITMOS Contables estáticas: determina en tiempo de ejecución cuando debe
comenzar una tarea. Preemptive con prioridades estáticas: el análisis asigna prioridades a
tareas y se utiliza un planificador convencional preemptive con prioridades.
Planificación dinámica: se acepta una nueva tarea para ejecutar solo si es factible cumplir sus restricciones de tiempo
Dinámicos del mejor resultado: intenta cumplir todos los plazos, abandona procesos iniciados cuyos plazos se hayan vencido (APESTA).
o TIPOS DE PLANIFICACIONES Por plazos: se dispone información adicional de cada tarea para minimizar
la proporción de tareas que no cumplen sus plazos. RMS (monotona por frecuencia): la tarea de más alta prioridad es la del
período más corto. La 2º es la del 2º período más corto y asi asi amén.
67
Resumen de SO – 2006 ( by Damián Nardelli & Rodrigo Velaz)
CUALQUIER DUDA LES DEJO MSN:
pregunten lo que no entiendan, no les quede claro, de práctica, de lo que se les cante, si arman fiestas inviten… si sos mina y sos linda agreganos tmb, si tenés apuntes de otra materia agreganos tmb!!!
Con respecto a lo de Security… chequeen el FORO ya que hay una resolución de “Nadia ;o)” (un jpg) muy bueno!!!!!!!
GOOD LUCK!
68