Planificación de Procesos

SRT (Shortest Remaining Time)

El siguiente proceso a entrar en el procesador es el que tenga el tiempo de ejecución restante más corto. Cuando llega un proceso nuevo que es más corto que el que se está ejecutando, este último es desalojado de la CPU y se empieza a ejecutar el nuevo. Es una variante apropiativa de la política SJN (Shortest Job Next).

Características:

• Variante apropiativa de SJN.
• Excelente tiempo medio de servicio.
• Política muy eficiente.
• Posibilidad de asignar prioridades, multiplicando o dividiendo el tiempo restante (número de quantums) según la prioridad.

Problema: Algunos procesos pueden sufrir una postergación indefinida, convirtiéndose en procesos zombies si no hay un control de prioridades.

Cuando se utilizan prioridades, los algoritmos pueden ser apropiativos o no apropiativos. En el caso de ser apropiativos, el proceso postergado puede ser retirado de memoria y reservado si es necesario. En el caso no apropiativo, el proceso se ejecuta o se convierte en zombie.

HRN (High Response Next)

Esta política selecciona para la ejecución al proceso con el índice de respuesta más alto. Se asigna una prioridad a cada proceso en función de su índice de respuesta:

Prioridad = w * t / t_a

• w: tiempo de espera en la cola de procesos preparados.
• t_a: tiempo de ejecución del proceso.

Para evitar la postergación indefinida, si w aumenta, la prioridad también aumenta. Inicialmente, w vale 1 y luego incrementa.

Cuando un proceso en ejecución abandona el procesador (por finalización o por una operación de entrada/salida), el siguiente proceso con mayor prioridad entra en ejecución. Esta política es no apropiativa, pero puede comportarse como apropiativa si un programa con prioridad suficientemente alta ejecuta una interrupción.

Inconvenientes:

• Un proceso corto después de uno largo puede sufrir una larga espera.
• Alto costo de implementación, ya que la prioridad debe calcularse para todos los procesos en espera.
• Sobrecarga el sistema debido a los cálculos.

Características:

• Básicamente no apropiativa, excepto en caso de interrupción.
• Justa, no favorece a un proceso sobre otro.
• Costosa y sobrecarga el sistema.

Colas Múltiples

Cuando los procesos se pueden agrupar por características similares, se pueden definir distintas colas de ejecución con diferentes algoritmos de planificación. Se necesita un algoritmo para gestionar la cola múltiple. Cada cola puede tener su propia memoria asignada. Un algoritmo de procesamiento de colas dará prioridad a una u otra cola según el sistema.

Colas Múltiples con Retroalimentación (FB)

Todas las colas tienen acceso al procesador. El algoritmo ejecuta según la política de cada cola, asignando tiempos específicos a cada una (por ejemplo, 3 unidades de tiempo a la cola 1, 2 a la cola 2, 1 a la cola 3). El último nivel es el que se ejecuta con menos frecuencia. Los procesos pueden pasar de una cola a otra (niveles) dependiendo de su comportamiento. Si un proceso incumple una regla, pasa de nivel. Intenta favorecer a los procesos más cortos y a los trabajos limitados por entrada/salida.

Cuando un proceso termina su quantum, se selecciona un nuevo proceso de la cola de nivel más bajo que tenga procesos. Si un proceso consume su quantum un determinado número de veces sin terminar, pasa a la cola de nivel inmediatamente superior (asignación en cascada).

Características:

• Soporta bien la sobrecarga.
• Apropiativa.
• Adaptable a las necesidades del sistema, ya que cada cola puede gestionarse de forma diferente.

Gestión de Memoria RAM (Primaria)

Usos Generales:

• Ejecutar programas: El procesador necesita que los datos y programas estén en la memoria principal para acceder a ellos.
• Incrementar el rendimiento del procesador (Multiprogramación): La memoria principal se segmenta en n partes, y cada proceso se ejecuta en uno de estos segmentos.
• Punto de encuentro del procesador con datos o recursos de dispositivos secundarios.

La velocidad de la memoria principal es un factor limitante (cuello de botella) para la velocidad de proceso del ordenador.

Conceptos:

• Tiempo de acceso a memoria: Tiempo entre el inicio y el fin de una operación de lectura o escritura.
• Tiempo de ciclo de memoria: Tiempo mínimo entre el fin de una operación y el inicio de la siguiente, impuesto por el hardware (tiempo para reseteo y restitución de parámetros).

Direccionamiento

Errores, pantallazo azul: 0A01:ABFC (dirección virtual) = V*65453 + desplazamiento, donde V es la dirección virtual.

Definición de direccionamiento: Correspondencia entre una dirección de memoria y su ubicación física.

Tipos de direcciones:

• Simbólica: Nombre o etiqueta asignada por el programador. Solo tiene sentido en el código fuente. Durante la compilación, se pasa de direcciones absolutas a relativas.
• Relativa: Valores asignados por el compilador con respecto al orden de compilación del programa.
• Absoluta: Dirección real a la que accede el procesador. Se calcula como (Tamaño * (Número – 1) + D), donde Tamaño es el tamaño del segmento, Número es el número de segmento y D es el desplazamiento dentro del segmento.

La memoria caché forma parte de la memoria principal y acelera el acceso a datos. La caché y la memoria principal forman la memoria primaria. La caché es más rápida pero de menor tamaño.

Concepto de Multiprogramación

Multiprogramación es la ejecución concurrente de varios programas en memoria principal. La memoria se divide en particiones o regiones donde se cargan los procesos. El número de particiones indica el grado de multiprogramación. Cada segmento puede tener su propia caché de entrada/salida (el sistema controla n cachés).

Protección de Memoria

Al segmentar la memoria y cargar un proceso en cada segmento, es necesario controlar el rango de acceso de cada proceso para evitar superposición de programas o datos, y accesos no autorizados.

Solución 1: Para cada partición, se usan dos registros límite que apuntan a la parte superior e inferior. Cualquier dirección generada por el proceso debe estar entre estos márgenes. Esta técnica requiere direcciones absolutas, generadas en tiempo de compilación o ejecución (asignación estática).

Solución 2: Se usa un registro base con la dirección de inicio de la partición y un registro límite con el tamaño. Esto permite la asignación dinámica de direcciones, actualizando el registro base. Cada dirección generada debe ser menor que el registro límite.

Gestión de Memoria

Evolución à Todos los SO  utilizan gran parte de su software a la gestión de la memoria.Monoprogramacion : Ejecución de los programas uno detrás de otro. Mediante memoria dedicada (se carga el programa se va ejecutando y el resto de memoria queda sin utilizar) Primero lo cargo todo.División de memoria.  (hay problemas de frontera) al poner varios procesos se tienen que asignar una política de división de limites. Reasignación de direccionesà en la reasignación de direcciones el registro frontera indicara el punto a partir del cual se debe cargar el programa del usuario, para ello es necesario reasignar las direcciones del programa en función de la frontera.Reasignación estática-> la reasignación se realizara durante la compilación o la carga del programa en memoria, esto implica que cualquier variación de tamaño en el sistema operativo exige una nueva compilación o carga del programa. Es una técnica fácil de realizar pero demasiado rígida.Reasignación dinámica-> esta se realiza durante la ejecución del programa. Un dispositivo especial del hardware del sistema interceptará cada dirección lógica generada por el programa y le sumara el contenido del registro frontera para obtener la dirección real correspondiente. El SO con la ayuda del hardware del sistema establecerá la correspondencia entre las direcciones relativas y reales que configuran el espacio físico de direcciones.Gestión de particiones de memorias de tamaño fijoUna de las formas mas sencillas de gestionar la memoria es realizar particiones de tamaño fijo contiguas (una detrás de otra), de tal forma que el número de ellas y los tamaños se definirán al inicializar el sistema y quedar inamovibles mientras dure la sesión. Cuando un programa tiene que cargarse el sistema operativo le asignara una partición que pueda contenerlo, para ello es necesario un programa que declare sus necesidades al sistema. Los primeros sistemas que utilizaron este tipo de gestión realizaban la gestión de la memoria mediante colas de espera, el SO asignaba cada programa a una cola dependiendo del tamaño de memoria solicitado.Esta técnica es simple y fácil de desarrollar pero su eficacia esta muy condicionada por las exigencias de memoria de los programas y su orden de llegada. Factores limitantes de este procesoà que pasa cuando una aplicación no cabe en las memorias diseñadas¿? No se puede ejecutar se tiene que esperar al final de proceso y que el supervisor del sistema reasigne particiones de memoria mas grandes.Cuando se carga un programa que es mas pequeña que la partición asignada, hay un desperdicio de memoria. Cada vez que perdamos memoria, le llamaras fragmentación de la memoria. Fragmentación externaà es el segmento de memoria no aprovechable después de realizar todas las segmentaciones de la memoria principal. (lo que sobra de la reasignación de los segmentos)Fragmentación internaà aquella memoria no aprovechada dentro del segmento de ejecución del proceso. Si cargo un programa pequeño el trozo de memoria que no utilizo es la fragmentación interna.Métodos para optimizar la fragmentación (que no haya fragmentación)Particiones contiguas de tamaño variable: Asignan dinámicamente la memoria a los trabajos de acuerdo con su tamaño. El SO mantendrá una tabla interna donde registrara las zonas de memoria disponible, asignando a cada trabajo una partición del tamaño solicitado. Funcionamiento: Al arrancar el sistema le va asignando a cada programa un segmento en función al tamaño que necesita, nos queda un segmento de fragmentación externa. A medida que se van acabando los procesos va substituyendo los procesos por otros en un segmento que estaba dimensionado para el anterior, este proceso estará desperdiciando memoria, aparece la fragmentación interna. Puede tener dos políticas distintas : FIRST FIT  à coloca el programa en la primera partición libre sin tener en cuenta el tamaño, tiene el peligro que si la primera partición libre era muy grande, desperdicio mucha memoria.BEST FIT à busca la primera partición libre que mas se ajusta al tamaño del programa que se quiere ejecutar. El gestor de memoria va juntando particiones vacías contiguas. Junta a partir de los registros base. Tiene el problema de las fragmentaciones externas que se van acumulando. Es necesaria una compactación periódica para eliminar la fragmentación externa. ( esto ralentiza mucho el rendimiento general del proceso ). Cada cierto tiempo tiene que haber una reasignación. La paginación Es una forma de asignación de memoria discontinua que permite asignar a los procesos páginas de memoria ubicadas en distintos frames.Frame o armazón: Es un segmento físico de memoria que tendrá el tamaño exacto de n páginas de memoria que se definirán en él. Páginas: Particiones lógicas en las que se divide un frame. Para cada programa se le asignaran las páginas necesarias de memoria para su ejecución, independientemente de en que frame se encuentre. Con este metodo se logra evitar una fragmentacion externa excesiva, pero se seguira produciendo una fragmantacion interna, ya que es imposible que todos los procesos se adapten a la pagina.Si se quiere optimizar le rendiemiento de  la memoria tendremos que tender a disminuir el tamaño de las páginas, cuanto mas pequeño es el tamaño de las páginas, menos memoria interna se desperdicia; pero esto implica un numero mayor de tablas para controlar las páginas.El sistema de paginación funciona de la siguiente forma:Para cada uno de los trabajos activos utiliza un registro especial llamado “registro base” para indicar la dirección de la tabla de páginas del trabajo en ejecución en este momento; así cuando se conmuta un trabajo se restaura la tabla del siguiente proceso.Para transformar cada dirección lógica generada por el procesador en su dirección real, necesita recurrir a la tabla de páginas correspondiente, y luego a la dirección real, así que cada acción provoca dos accesos de memoria y se multiplican los tiempos de ejecución.Para evitar esto, o para acelerar la información, hay dos soluciones básicas:guardar en memoria cache las direcciones de las páginas más utilizadas, así se reduce el retraso de la paginación. El problema que tiene esto es que la memoria cache es muy cara y hay que añadir a todo este proceso la gestión de esta memoria.En el caso de sistemas pequeños con tablas de páginas con pocas entradas, se pueden usar memorias asociativas para contener dichas tablas. Estas memorias constan de un conjunto de registros de hard (que son los registros asociativos) de forma que son capaces de hacer una comparación con todos los registros a la vez (búsqueda por contenido).Una ventaja que tiene la paginación es que tiene fragmentación externa minima y fragmentación interna solo en la última página de cada programa y recuperable.La segmentaciónLos programas se desarrollan normalmente en torno a un núcleo central del cual se bifurcan las rutinas o las áreas de datos (pilas, tablas), de forma que desde el punto de vista lógico, es un conjunto de componentes de tamaño variable, es decir, un espacio lógico de direcciones.Ventaja: la fragmentación externa es puntual, ya que al terminar cada rutina se libera la memoria, recuperando esta fragmentación externa fácilmente. Sistemas combinadosPaginación segmentada: consiste en segmentar la tabla de páginas adecuándola al tamaño del programa. Para ello se mantiene una tabla de segmentos cuyas entradas indican la dirección de inicio de cada tabla de página y su tamaño. Se utiliza con un hard especial.Segmentación paginada: utiliza segmentos cuyo tamaño es siempre u numero entero de páginas, de esta forma se evita la fragmentación externa, propia de la segmentación.Memoria virtual: es una técnica de gestión que combina hard y soft. Las ventajas de esto son: La memoria lógica puede ser mayor que la real disponible.Se puede elevar el nivel de multiprogramación y por tanto la eficiencia del sistema.Se necesitan menos operaciones de E/S en las operaciones de carga e intercambio de programas. Las diferentes partes del programa se van cargando en memoria a medida que se necesitan. Para ello hay que considerar 3 aspectos: Carga: Las porciones de programa se cargan cuando se necesitan. Si es este el caso se llama petición de página. Si se cargan por anticipado se denomina prepaginación.Colocación: Los sistemas de memoria virtual que utilizan segmentación deben decidir donde cargar el nuevo segmento, es decir, si utilizan la política de best fit o de first fit.Sustitución: Cuando se necesita cargar una nueva parte de un programa tendremos que tomar alguna decisión, eliminar la última parte del programa, eliminar la más antigua o la que hace más tiempo que no se utiliza. La memoria virtual puede funcionar de dos formasCarga por petición de páginas: es lo más habitual. El algoritmo no cargara todo el programa, sino solo las paginas que le pida, y solo cargara una nueva pagina cuando la dirección generada por el procesador no este en memoria.Carga por reemplazamiento de página: La rutina del sistema que gestiona la interrupción de falta de pagina trabaja de la siguiente forma: Tiene que encontrar la página solicitada en almacenamiento secundario.Tiene que encontrar un frame libre. Si existe este frame, utilizarlo, si no existe, usar el algoritmo de reemplazamiento para seleccionar la pagina a sustituir. Salvar la pagina reemplazada en la memoria, actualizando las tablas afectadas. Llevar la página solicitada al frame libre y actualizar las tablas correspondientes. Algoritmos de reemplazamientoEl algoritmo óptimo de reemplazamiento es aquel que sustituye la página que vaya a tardar más en ser utilizada, sin embargo, es imposible preveer el comportamiento futuro de los procesos.Los algoritmos que se han empleado para controlar el reemplazamiento parten de la utilización pasada de las páginas para intentar aproximarse a una solución óptima. Su idoneidad vendrá definida por dos factores:El número de faltas de páginas que provoca el proceso.El coste de su utilización.Política FIFO: Esta política, cuando necesita sustituir una página elige aquella que lleva mas tiempo en memoria. Para poder gestionar el tiempo de proceso en memoria utiliza una cola de llegada a memoria, es un algoritmo muy fácil y sencillo de llevar. Provoca poca sobrecarga y es de eficacia relativa.Política LRU Es la menos utilizada. Sustituye aquellas páginas que haya sido menos utilizada recientemente. Considera que aquellas páginas que hayan sido  muy usadas en el pasado reciente serán también las más usadas en el futuro.Para poder controlar la antigüedad de las páginas tiene que recurrir a un método