TÉCNICAS DE ADMINISTRACIÓN DEL PLANIFICADOR

En los siguientes subapartados vamos a estudiar ciertos algoritmos utilizados para planificar la CPU, la elección de uno (o de una mezcla de varios) depende de decisiones de diseño. Antes de exponer los algoritmos vamos a explicar ciertas medidas que se utilizan para evaluarlos.

• Porcentaje de utilización de la CPU por procesos de usuario. La CPU es un recurso caro que necesita ser explotado, los valores reales suelen estar entre un 40% y un 90%.

• Rendimiento (throughput) = nº de ráfagas por unidad de tiempo. Se define una ráfaga como el período de tiempo en que un proceso necesita la CPU; un proceso, durante su vida, alterna ráfagas con bloqueos. Por extensión, también se define como el nº de trabajos por unidad de tiempo.

•  Tiempo de espera (E) = tiempo que una ráfaga ha permanecido en estado listo.

• Tiempo de finalización (F) = tiempo transcurrido desde que una ráfaga comienza a existir hasta que finaliza. F = E + t (t = tiempo de CPU de la ráfaga).

• Penalización (P) = E + t / t = F / t, es una medida adimensional que se puede aplicar homogéneamente a las ráfagas independientemente de su longitud.

En general, hay que maximizar los dos primeros parámetros y minimizar los tres últimos. Sin embargo, estos objetivos son contradictorios, el dedicar más tiempo de CPU a los usuarios se hace a costa de llamar menos al algoritmo de planificación (menos cambios de proceso), y de simplificarlo. Esto provoca que la CPU se reparta menos equitativamente entre los procesos, en detrimento de los últimos tres parámetros.
Así pues, dependiendo de los objetivos se elegirá cierto algoritmo. En los sistemas por lotes suele primar el rendimiento del sistema, mientras que en los sistemas interactivos es preferible minimizar, por ejemplo, el tiempo de espera.


TÉCNICAS O ALGORITMOS DE PLANIFICACIÓN

Planificación a  plazo fijo.

            En la planificación a plazo fijo, ciertos trabajos se planifican para ser terminados en un periodo específico. Estos trabajos tienen un alto valor si se entregan a tiempo y pueden carecer  de valor si se entregan después del límite. La planificación a plazo fijo es compleja por muchas razones:

• Los usuarios deben proporcionar por adelantado y en forma precisa las necesidades    de  recursos de su trabajo. Tal información rara vez está disponible.
• El sistema debe ejecutar el programa de plazo fijo sin una severa degradación de servicio  para los otros usuarios.
• El sistema debe planificar cuidadosamente las necesidades de recursos permitiendo un libre tránsito del plazo fijo. Esto puede ser difícil debido a la llegada de programas nuevos con demandas impredecibles.
• Si se activan muchos trabajos de plazo fijo, la planificación puede llegar a ser tan compleja que necesite métodos de optimización sofisticados para asegurar que el plazo fijo se cumpla.
• El manejo intenso de recursos requeridos por la planificación de plazo fijo puede generar una sobrecarga sustancial.

Planificación  Primero   en  llegar - Primero  en  Salir (FIFO).

Los procedimientos son despachados de acuerdo al orden de llegada a la cola de listos. Una vez que un proceso tiene el CPU, se ejecuta hasta su terminación. Esta planificación es No apropiativa; es justa en el sentido formal, pero algo injusta porque los grandes procesos hacen esperar a trabajos pequeños y,  los trabajos sin importancia hacen esperar a los trabajos importantes.

La Planificación FIFO ofrece una varianza en tiempo de respuesta relativamente pequeña y es, por tanto, más predecible que otros esquemas; no es un esquema útil en la planificación de procesos interactivos porque no garantiza buenos tiempos de respuesta.También se puede implementar mediante la utilización de una lista. Se reemplazan las páginas de la cabeza y se agregan al final.

Una vez que el proceso obtiene la cpu, se ejecuta hasta terminar, ya que es una disciplina “no apropiativa”. 

Puede ocasionar que procesos largos hagan esperar a procesos cortos y que procesos no importantes hagan esperar a procesos importantes. 

Es más predecible que otros esquemas. 

No puede garantizar buenos tiempos de respuesta interactivos. 

Suele utilizarse integrado a otros esquemas, por ejemplo, de la siguiente manera: 

• Los procesos se despachan con algún esquema de prioridad.
• Los procesos con igual prioridad se despachan “FIFO”.

Planificación por Prioridad al más corto (SJF, Short Job First).

            La disciplina del trabajo más corto primero es NO apropiativa y en ella el trabajo o proceso con tiempo estimado de ejecución hasta terminación más corto, es el siguiente en ser ejecutado. El SJF reduce el tiempo de espera de los procesos, sin embargo, tiene una varianza mayor (es decir, es menos predecible) que en FIFO, sobre todo para los trabajos largos.

 SJF favorece a los procesos cortos a costa de los procesos largos. Además, selecciona los trabajos que serán atendidos y que dejarán el sistema lo antes posible. Esto último traduce en listas de espera cortas. El SJF es NO apropiativo por lo que resulta de poca utilidad en ambientes de tiempo compartido.

• Es una disciplina no apropiativa y por lo tanto no recomendable en ambientes de tiempo compartido.
• El proceso en espera con el menor tiempo estimado de ejecución hasta su terminación es el siguiente en ejecutarse. 
• Los tiempos promedio de espera son menores que con “FIFO”. 
• Los tiempos de espera son menos predecibles que en “FIFO”. 
• Favorece a los procesos cortos en detrimento de los largos. 
• Tiende a reducir el número de procesos en espera y el número de procesos que esperan detrás de procesos largos. 
• Requiere un conocimiento preciso del tiempo de ejecución de un proceso, lo que generalmente se desconoce. 
• Se pueden estimar los tiempos en base a series de valores anteriores. 

Planificación el Siguiente con Relación de Respuesta Máxima (HRN)

Corrige algunas de las debilidades del SJF, tales como el exceso de perjuicio hacia los procesos (trabajos) largos y el exceso de favoritismo hacia los nuevos trabajos cortos. 

Es una disciplina no apropiativa. 

La prioridad de cada proceso está en función no sólo del tiempo de servicio del trabajo, sino que también influye la cantidad de tiempo que el trabajo ha estado esperando ser servido. 

Cuando un proceso ha obtenido la cpu, corre hasta terminar. 

Las prioridades, que son dinámicas, se calculan según la siguiente fórmula, donde p_r es la “prioridad”, t_e es el “tiempo de espera” y t_s es el“tiempo de servicio”: 

 Planificación del tiempo restante más corto primero (SRT).

            La SRT es apropiativa, en ella el proceso con el tiempo estimado de ejecución menor para llegar a su terminación es el siguiente en ser ejecutado, incluyendo las nuevas llegadas. En la disciplina SJF, una vez que el trabajo comienza su ejecución sigue hasta que termina. En SRT, un proceso en ejecución puede ser apropiado por un nuevo proceso con n tiempo estimado de ejecución menor.

            La SRT tiene una sobrecarga mayor que la SJF. Debe mantener un registro del tiempo de servicio transcurrido del trabajo en ejecución y debe controlar las apropiaciones ocasionales.

Planificación  el  siguiente con relación  de respuesta  máxima (HRT).

            Brinch Hansen (1971) desarrolló la estrategia el siguiente con relación de respuesta máxima (HRT), que corrige algunas de las debilidades de SJF, en especial el favoritismo por los tamaños pequeños. La HRT es una disciplina de planificación NO apropiativa en la cual la prioridad de cada trabajo está en función, no sólo del tiempo de servicio del trabajo, sino del tiempo que un proceso ha estado esperando a ser servido, Una vez que un trabajo obtiene el CPU,  se ejecuta hasta su terminación. Las prioridades dinámicas en HRT se calculan según la fórmula

Planificación Round Robin (RR)

             Los procesos son despachados en FIFO, pero, se les otorga una cantidad limitada de tiempo de CPU llamada división de tiempo (time - slice) o cuanto (quantum). Si un proceso no termina antes de que se termine su tiempo de CPU, el CPU es apropiado y asignado al siguiente proceso en espera. El proceso apropiado se coloca al final de la lista de listos.

 Planeación round robin.

            El  esquema Round  robin es efectivo en un ambiente de tiempo compartido en el cual el sistema necesita garantizar un tiempo de respuesta razonable para los usuarios interactivos. La sobre carga  de la apropiación se mantiene baja mediante eficientes mecanismos de cambio de contexto y proporcionado suficiente memoria para que los procesos residan en ella al mismo tiempo.

            Existe una variante de este esquema llamada selfish round robin (SRR). En este esquema los procesos que entran al sistema se colocan primero en una lista de espera hasta que su prioridad alcanza el nivel de proceso para la lista de activos. Mientras un proceso está en la lista de espera, su prioridad aumenta en una relación a; cuando un proceso entra a la lista de activos su prioridad se incrementa en una relación b.

Tamaño del Cuanto o Quantum

La determinación del tamaño del cuanto es decisiva para la operación efectiva de un sistema computacional 

Los interrogantes son: ¿cuanto pequeño o grande?, ¿cuanto fijo o variable? y ¿cuanto igual para todos los procesos de usuarios o determinado por separado para cada uno de ellos?. 

Si el cuanto se hace muy grande, cada proceso recibe todo el tiempo necesario para llegar a su terminación, por lo cual la asignación en rueda (“RR”) degenera en “FIFO”. 

Si el cuanto se hace muy pequeño, la sobrecarga del intercambio de contexto se convierte en un factor dominante y el rendimiento del sistema se degrada, puesto que la mayor parte del tiempo de cpu se invierte en el intercambio del procesador (cambio de contexto) y los procesos de usuario disponen de muy poco tiempo de cpu. 

El cuanto debe ser lo suficientemente grande como para permitir que la gran mayoría de las peticiones interactivas requieran de menos tiempo que la duración del cuanto, es decir que el tiempo transcurrido desde el otorgamiento de la cpu a un proceso hasta que genera una petición de Entrada / Salida debe ser menor que el cuanto establecido, de esta forma, ocurrida la petición la cpu pasa a otro proceso y como el cuanto es mayor que el tiempo transcurrido hasta la petición de Entrada / Salida, los procesos trabajan al máximo de velocidad, se minimiza la sobrecarga de apropiación y se maximiza la utilización de la 

Entrada / Salida. 

El cuanto óptimo varía de un sistema a otro y con la carga, siendo un valor de referencia 100 mseg (cien milisegundos)

Queves multi-level

Planificación de Dos Niveles 

Los esquemas analizados hasta ahora suponen que todos los procesos ejecutables están en la memoria principal. 

Si la memoria principal es insuficiente, ocurrirá lo siguiente

Habrá procesos ejecutables que se mantengan en disco. 

• Habrá importantes implicaciones para la planificación, tales como las siguientes:
• El tiempo de alternancia entre procesos para traer y procesar un proceso del disco es considerablemente mayor que el tiempo para un proceso que ya está en la memoria principal.
• Es más eficiente el intercambio de los procesos con un planificador de dos niveles.

El esquema operativo de un planificador de dos niveles es como sigue: 

1. Se carga en la memoria principal cierto subconjunto de los procesos ejecutables.
2. El planificador se restringe a ellos durante cierto tiempo.
3. Periódicamente se llama a un planificador de nivel superior para efectuar las siguientes tareas:
1. Eliminar de la memoria los procesos que hayan permanecido en ella el tiempo suficiente.
2. Cargar a memoria los procesos que hayan estado en disco demasiado tiempo.
4. El planificador de nivel inferior se restringe de nuevo a los procesos ejecutables que se encuentren en la memoria.
5. El planificador de nivel superior se encarga de desplazar los procesos de memoria a disco y viceversa.

Los criterios que podría utilizar el planificador de nivel superior para tomar sus decisiones son los que se indican a continuación:

• ¿Cuánto tiempo ha transcurrido desde el último intercambio del proceso?.
• ¿Cuánto tiempo de cpu ha utilizado recientemente el proceso?.
• ¿Qué tan grande es el proceso? (generalmente los procesos pequeños no causan tantos problemas en este sentido).
• ¿Qué tan alta es la prioridad del proceso?.

El planificador de nivel superior podría utilizar cualquiera de los métodos de planificación analizados.

Multi-level feedback queves.

Colas de Retroalimentación de Niveles Múltiples 

Cuando un proceso obtiene la CPU, sobre todo cuando todavía no ha tenido oportunidad de establecer un patrón de comportamiento, elplanificador no tiene idea de la cantidad de tiempo de CPU que necesitará el proceso. Los procesos limitados por la E/S normalmente usan la CPU sólo un momento antes de generar una solicitud de E/S; los procesos limitados por la CPU pueden usar el procesador durante horas si está disponible en forma no apropiativa.

Un mecanismo de planificación debe:

•  Favorecer a los trabajos cortos.

•  Favorecer a los trabajos limitados por la E/S para lograr un mejor aprovechamiento de los dispositivos de E/S.

• Determinar la naturaleza de un trabajo lo más pronto posible y planificarlo de acuerdo con su naturaleza.  

Las colas de retroalimentación de niveles múltiples son ideales para separar procesos en categorías basadas en su necesidad de la CPU. En un sistema de tiempo compartido, cada vez que un proceso abandona la red de colas puede "marcarse" con la identidad de la última cola en donde estuvo, y cuando el proceso entra de nuevo en la red de colas, puede enviarse directamente a la cola en la cual terminó su operación por última vez. En este caso, el planificador está usando un razonamiento heurístico, según el cual el comportamiento anterior del proceso es un buen indicador de su comportamiento en un futuro inmediato. De esta forma, un proceso limitado por la CPU que regresa a la red de colas no se coloca en las colas de nivel alto donde interferiría con el servicio a los procesos cortos de prioridad alta o con los limitados por la E/S.

REFERENCIAS:

https://sites.google.com/site/materiasisoperativo/unidad-2-administrador-del-proceso-y-del-procesador/2-6-tecnicas-de-administracion-del-planificador

PROCESOS CONCURRENTES

PROCESO

Analizar mediante ejemplos de la vida real el concepto de procesos, programa y procesador y trasladarlo al concepto de computadoras

ACTIVIDAD 2

Act.2 Investiga los mecanismos y funciones de los manejadores de dispositivos

Mecanismos y funciones de los manejadores de dispositivos: device drivers

El controlador es el componente más importante desde el punto de vista del sistema operativo, ya que constituye la interfaz del dispositivo con el bus de la computadora y es el componente que se ve desde la CPU. El Sistema Operativo generalmente trabaja con el controlador y no con el dispositivo.

Técnicas de E/S

E/S programada: El procesador emite una orden de E/S de parte de un proceso a un módulo de E/S; el proceso espera entonces a que termine la operación, antes de seguir.

E/S dirigida por interrupciones: El procesador emite una orden de E/S de parte de un proceso, continua la ejecución de las instrucciones siguientes y el módulo de E/S lo interrumpe cuan do completa su trabajo.

Acceso Directo a la Memoria (DMA): un módulo de DMA controla el intercambio de datos entre la memoria principal y un módulo de E/S. El procesador envía una petición de transferencia de un bloque de datos al módulo DMA y se interrumpe solo cuando se ha transferido el bloque entero.

Funciones de los manejadores de dispositivos

Funciones generalmente realizadas por el software independiente del dispositivo:

• Interfaz uniforme para los manejadores de dispositivos.
• Nombres de los dispositivos.
• Protección del dispositivo.
• Proporcionar un tamaño de bloque independiente del dispositivo.
• Uso de buffer.
• Asignación de espacio en los dispositivos por bloques.
• Asignación y liberación de los dispositivos de uso exclusivo.
• Informe de errores.

Las funciones básicas del software independiente del dispositivo son:

• Efectuar las funciones de e / s comunes a todos los dispositivos.
• Proporcionar una interfaz uniforme del software a nivel usuario.

El software independiente del dispositivo asocia los nombres simbólicos de los dispositivos con el nombre adecuado.
Un nombre de dispositivo determina de manera única el nodo-i de un archivo especial:

• Este nodo-i contiene el número principal del dispositivo, que se utiliza para localizar el manejador apropiado.
• El nodo-i contiene también el número secundario de dispositivo, que se transfiere como parámetro al manejador para determinar la unidad por leer o escribir.

El software independiente del dispositivo debe:

• Ocultar a los niveles superiores los diferentes tamaños de sector de los distintos discos.

• Proporcionar un tamaño uniforme de los bloques, por ej.: considerar varios sectores físicos como un solo bloque lógico.

REFERENCIA:

https://sites.google.com/site/materiasisoperativo/unidad-4-administracion-de-entrada-salida/4-2-mecanismos-y-funciones-de-los-manejadores-de-dispositivos-device-drivers

http://sistemasoperativos.angelfire.com/html/4.2.html

Act.1 Realiza e investiga cuales son los dispositivos y manejadores de dispositivos mediante conceptos e imágenes

UNIDAD 4

Act.1

Realiza e investiga  cuales son los dispositivos y manejadores de dispositivos mediante conceptos e imágenes.

Valor: 8%  individual-blog

Act.2

Investiga los mecanismos y funciones de los manejadores de dispositivos.

Valor: 7% individual-blog

El sistema de E/S es la parte del sistema operativo que se ocupa de facilitar el manejo de los dispositivos de E/S ofreciendo una visión lógica simplificada de los mismos que pueda ser usada por otros componentes del sistema operativo (como el sistema de archivos) o incluso por el usuario.

El sistema operativo debe controlar el funcionamiento de todos los dispositivos de E/S para alcanzar los siguientes objetivos:

·         Facilitar el manejo de los dispositivos de E/S. Para ello debe ofrecer una interfaz entre los dispositivos y el resto del sistema que sea sencilla y fácil de utilizar.

·         Optimizar la E/S del sistema, proporcionando mecanismos de incremento de prestaciones donde sea necesario.

·         Proporcionar dispositivos virtuales que permitan conectar cualquier tipo de dispositivo físico sin que sea necesario remodelar el sistema de E/S del sistema operativo.

·         Permitir la conexión de dispositivos nuevos de E/S, solventando de forma automática su instalación usando mecanismos del tipo plug&play.

·         Conexión de un dispositivo de E/S a una computadora En la siguiente figura se muestra el esquema general de conexión de periféricos a una computadora. En el modelo de un periférico se distinguen dos elementos:

 Periféricos o dispositivos de E/S: Elementos que se conectan a la unidad central           de proceso a través de las unidades de entrada/salida. Son el componente mecánico  que se conecta a la computadora.

Controladores de dispositivos o unidades de E/S: Se encargan de hacer la transferencia de información entre la memoria principal y los periféricos. Son el componente electrónico a través del cual se conecta el dispositivo de E/S. Tienen una conexión al bus de la computadora y otra para el dispositivo (generalmente mediante cables internos o externos).

Dispositivos de E / S

Se denomina periféricos a los aparatos o dispositivos auxiliares e independientes conectados a la unidad central de procesamiento de

Se pueden clasificar en dos grandes categorías:

• Dispositivos de bloques: dispositivos que almacenan la información en bloques de tamaño fijo (discos)
• Dispositivos de caracteres: maneja la información mediante un flujo de caracteres sin estructurarlos en bloques (mouse, teclado, impresora)

Las principales características de los dispositivos de bloque son:

• La información se almacena en bloques de tamaño fijo.
• Cada bloque tiene su propia dirección.
• Los tamaños más comunes de los bloques van desde los 128 bytes hasta los 1.024 bytes.
• Se puede leer o escribir en un bloque de forma independiente de los demás, en cualquier momento.
• Un ejemplo típico de dispositivos de bloque son los discos.

Las principales características de los dispositivos de caracter son:

• La información se transfiere como un flujo de caracteres, sin sujetarse a una estructura de bloques.
• No se pueden utilizar direcciones.
• No tienen una operación de búsqueda.
• Unos ejemplos típicos de dispositivos de caracter son las impresoras de línea, terminales, interfaces de una red, ratones, etc.

Todos los dispositivos de E/S se pueden agrupar en tres grandes grupos:

• Dispositivos de interfaz de usuario. Se llama así a los dispositivos que permiten la comunicación entre los usuarios y la computadora.
• Dispositivos de almacenamiento. Se usan para proporcionar almacenamiento no volátil de datos y memoria. Su función primordial es abastecer de datos y almacenamiento a los programas que se ejecutan en la UCP.
• Dispositivos de comunicaciones. Permiten conectar a la computadora con otras computadoras a través de una red. Algunos dispositivos de entrada y salida:
  
  

• Entrada:
• Teclado
• Ratón
• Joystick
• Lápiz óptico
• Micrófono
• Webcam
• Escáner
• Escáner de código de barras
• Salida:
• Monitor
• Altavoz
• Auriculares
• Impresora
• Plotter
• Proyector

• Entrada/salida (mixtos):
• Unidades de almacenamiento: CD,DVD, Blu-ray, Memory cards, Disco Duro Externo, Disco duro, Pendrive USB.
• Módem
• Router
• Pantalla táctil
• Tarjeta de red

MANEJADORES DE DISPOSITIVOS

Cada dispositivo de E/S, o cada clase de dispositivos, tiene un manejador asociado en el sistema operativo.

Dicho manejador incluye: código independiente del dispositivo para proporcionar al nivel superior del sistema operativo una interfaz de alto nivel y el código dependiente del dispositivo necesario para programar el controlador del dispositivo a través de sus registros y datos.

La tarea de un manejador de dispositivo es aceptar peticiones en formato abstracto, de la parte del código de E/S independiente del dispositivo, traducir dichas peticiones a términos que entienda el controlador, enviar al mismo las órdenes adecuadas en la secuencia correcta y esperar a que se cumplan.

Todos los manejadores tienen una lista de peticiones pendientes por dispositivo donde se encolan las peticiones que llegan de niveles superiores. El manejador explora la lista de peticiones, extrae una petición pendiente y ordena su ejecución. La política de extracción de peticiones de la lista es dependiente de manejador y puede ser FIFO. Una vez enviada la petición al controlador, el manejador se bloquea o no, dependiendo de la velocidad del dispositivo. Para los lentos (discos) se bloquea esperando una interrupción. Para los rápidos (pantalla, discos RAM, etcétera) responde inmediatamente.

Figura 4.1.1

Todo el código que depende de los dispositivos aparece en los manejadores de dispositivos. (Ver-figura-4.1.1)

Cada controlador posee uno o más registros de dispositivos:

• Se utilizan para darle los comandos.
• Los manejadores de dispositivos proveen estos comandos y verifican su ejecución adecuada.

La labor de un manejador de dispositivos es la de:

• Aceptar las solicitudes abstractas que le hace el software independiente del dispositivo.
• Verificar la ejecución de dichas solicitudes.

Si al recibir una solicitud el manejador está ocupado con otra solicitud, agregara la nueva solicitud a una cola de solicitudes pendientes. 
La solicitud de e / s, por ej. Para un disco, se debe traducir de términos abstractos a términos concretos:

• El manejador de disco debe: (ver figura 4.1.2)

figura 4.1.2

• Estimar el lugar donde se encuentra en realidad el bloque solicitado.
• Verificar si el motor de la unidad funciona.
• Verificar si el brazo está colocado en el cilindro adecuado, etc.
• Resumiendo: debe decidir cuáles son las operaciones necesarias del controlador y su orden.
• Envía los comandos al controlador al escribir en los registros de dispositivo del mismo.
• Frecuentemente el manejador del dispositivo se bloquea hasta que el controlador realiza cierto trabajo; una interrupción lo libera de este bloqueo.
• Al finalizar la operación debe verificar los errores.
• Si todo esta o.k. transferirá los datos al software independiente del dispositivo.
• Regresa información de estado sobre los errores a quien lo llamo.
• Inicia otra solicitud pendiente o queda en espera.

REFERENCIAS: https://sites.google.com/site/materiasisoperativo/unidad-4-administracion-de-entrada-salida/4-1-dispositivos-y-manejadores-de-dispositivos-device-drivers