UNIDAD 3 ADMINISTRACIÓN DEL PROCESADOR.

3.1 PLANEACIÓN DE TRABAJOS (JOBSCHEDULING).

Cuando hay más de un proceso que está en condiciones de ejecutarse en la CPU, se debe escoger alguno. El encargado de tomar esa decisión es el planificador o scheduler, y el algoritmo que usa se llama algoritmo de planificación. (Scheduler = planificación)

Posibles objetivos (algunos de ellos contradictorios) del algoritmo de planificación son:

Justicia: Asegurarse que todos los procesos tengan su turno de CPU.

Eficiencia: Mantener la CPU ocupada todo el tiempo.

Tiempo de respuesta: Minimizar el tiempo de respuesta de los usuarios interactivos.

Rendimiento o productividad (throughput): Maximizar el número de trabajos terminados por hora.

Tiempo de espera: Minimizar el tiempo medio de espera (en la cola READY) de los procesos.

Una complicación adicional que hay que tener presente es que cada proceso es único e impredecible. Algunos son procesos limitados por I/O, es decir, pierden la mayor parte del tiempo esperando por I/O; otros son procesos limitados por CPU, es decir, requieren principalmente tiempo de CPU. En cualquier caso, todos los procesos alternan entre una fase de ejecución de CPU y otra de espera por I/O. Aunque la duración de las fases de CPU es impredecible y varía mucho entre un proceso y otro, tiende a tener una frecuencia como la de la siguiente figura:

Hay un gran número de fases de CPU cortos, y muy pocos largos. Esta información puede ser importante para seleccionar un algoritmo de planificación adecuado.

¿Cuándo hay que planificar?

Una decisión de planificación puede o debe tomarse cuando ocurre cualquiera de las siguientes transiciones entre estados de un proceso:

•EJECUTANDO a BLOQUEADO.

•EJECUTANDO a TERMINADO.

•EJECUTANDO a LISTO.

•BLOQUEADO a LISTO.

En los casos 1 y 2, necesariamente hay que escoger un nuevo proceso, pero en los casos 3 y 4 podría no tomarse ninguna decisión de scheduling, y dejar que continúe ejecutando el mismo proceso que estaba ejecutando. En ese caso, se habla de planificación no-expropiadora. Si en cambio se toma una decisión de scheduling en los casos 3 y 4, entonces se habla de planificación expropiadora.

Esta última es más segura y más justa, pero tiene un problema: consideremos dos procesos que comparten información, y que a uno de ellos se le quita la CPU justo cuando estaba en medio de una actualización de los datos compartidos. Cuando sea el turno del segundo proceso, éste podría intentar leer los datos cuando están en un estado inconsistente. Este problema se remedia con sincronización.

3.2 CONCEPTOS BÁSICOS.

Un planificador de tareas es una aplicación de software empresarial que se encarga de las ejecuciones de fondo sin vigilancia, comúnmente conocido por razones históricas como“el procesamiento por lotes”.

Que es un procesamiento por lotes?
Es la ejecución de una serie de programas.
Hay muchos conceptos que son centrales para la aplicación casi todos los trabajos
Planificador y que son ampliamente reconocidos con variaciones mínimas:

• Empleos
• Dependencias
• Flujos de trabajo
• Usuarios

Más allá de la básica, herramientas de programación única instancia de SO hay dos arquitecturas principales que existen para el software de planificación de trabajo.
Maestro / Agente de la arquitectura: El software Job Scheduling se instala en una sola máquina (Master), mientras que en equipos de producción sólo un componente muy pequeño (agente) está instalado que le espera a las órdenes del Maestro, los ejecuta, y devuelve el código de salida de nuevo al maestro.

Arquitectura Cooperativa: Esto permite equilibrar la carga de trabajo dinámico para maximizar la utilización de los recursos de hardware y de alta disponibilidad para garantizar la prestación de servicios.

3.3 TIPOS DE PLANEACIÓN.

•Planeación a Plazo Fijo

Este planificador está presente en algunos sistemas que admiten además de procesos interactivos trabajos por lotes. Usualmente , se les asigna una prioridad baja a los trabajos por lotes, utilizándose estos para mantener ocupados a los recursos del sistema durante períodos de baja actividad de los procesos interactivos. Normalmente, los trabajos por lotes realizan tareas rutinarias como el cálculo de nóminas; en este tipo de tareas el programador puede estimar su gasto en recursos, indicándoselo al sistema. Esto facilita el funcionamiento del planificador a largo plazo.

•Planeación del Primero en Entrar Primero en Salir (FIFO)

Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que llevara más tiempo listo. El proceso se mantiene en la CPU hasta que se bloquea voluntariamente.

La ventaja de este algoritmo es su fácil implementación, sin embargo, no es válido para entornos interactivos ya que un proceso de mucho cálculo de CPU hace aumentar el tiempo de espera de los demás procesos . Para implementar el algoritmo sólo se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada. Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola.

•Planeación  de Asignación en Rueda (RR: Round Robin)

Este es uno de los algoritmos más antiguos, sencillos y equitativos en el reparto de la CPU entre los procesos, muy válido para entornos de tiempo compartido. Cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado cuantum o cuánto. Si el proceso agota su cuantum de tiempo, se elige a otro proceso para ocupar la CPU. Si el proceso se bloquea o termina antes de agotar su cuantum también se alterna el uso de la CPU. El round robin es muy fácil de implementar.

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

Al igual que en el algoritmo FIFO las ráfagas se ejecutan sin interrupción, por tanto, sólo es útil para entornos batch. Su característica es que cuando se activa el planificador, éste elige la ráfaga de menor duración. Es decir, introduce una noción de prioridad entre ráfagas. Hay que recordar que en los entornos batch se pueden hacer estimaciones del tiempo de ejecución de los procesos.

3.3.1 FIRST IN FIRST OUT (FIFO).

El primero que llega se atiende primero (FIFO) por sus siglas en inglés. Es un algoritmo que no usa expropiación, y que consiste en atender a los procesos por estricto orden de llegada a la cola READY. Cada proceso se ejecuta hasta que termina, o hasta que hace una llamada bloqueante (de I/O), o sea, ejecuta su fase de CPU completa. La gracia es que se trata de un algoritmo muy simple: la cola READY se maneja como una simple cola FIFO. El problema es que el algoritmo es bastante malo.

Tiempo de espera: Consideremos que los procesos P1, P2 y P3 están LISTOS para ejecutar su siguiente fase de CPU, cuya duración será de 24, 3 y 3 milisegundos, respectivamente. Si ejecutan en el orden P1, P2, P3, entonces los tiempos de espera son: 0 para P1, 24 para P2 y 27 para P3, o sea, en promedio, 17 ms. Pero si ejecutan en orden P2, P3, P1, entonces el promedio es sólo 3 ms.

 En consecuencia, FIFO no asegura para nada que los tiempos de espera sean los mínimos posibles; peor aún, con un poco de mala suerte pueden llegar a ser los máximos posibles. Utilización de CPU: Ahora supongamos que tenemos un proceso intensivo en CPU y varios procesos intensivos en I/O.

Entonces podría pasar lo siguiente. El proceso intensivo en CPU toma la CPU por un período largo, suficiente como para que todas las operaciones de I/O pendientes se completen. En esa situación, todos los procesos están LISTOS, y los dispositivos desocupados. En algún momento, el proceso intensivo en CPU va a solicitar I/O y va a liberar la CPU.

 Entonces van a ejecutar los otros procesos, pero como son intensivos en I/O, van a liberar la CPU muy rápidamente y se va a invertir la situación todos los procesos van a estar BLOQUEADOS, y la CPU desocupada. Este fenómeno se conoce como efecto convoy, y se traduce en una baja utilización tanto de la CPU como de los dispositivos de I/O.

(Vacías). Obviamente, el rendimiento mejora si se mantienen ocupados la CPU y los dispositivos (o sea, conviene que no haya colas.

3.3.2 ROUND ROBIN (RR).

Es una de la más simple programación de algoritmos para procesos en un sistema operativo que asigna períodos de tiempo a uno en porciones iguales y en orden circular, manejo de todos los procesos sin prioridad (también conocido como Ejecutivo cíclica). Planificación Round-robin es simple y fácil de implementar y hambre-libre. Programación de turnos puede aplicarse también a otros problemas de programación, tales como los paquetes de datos de programación en redes de computadoras.
El nombre del algoritmo viene desde el principio de round-robin conocido de otros campos, donde cada persona tiene una parte igual de algo a su vez.

Programación de trabajos de round-robin no puede ser conveniente si los tamaños de los puestos de trabajo o las tareas son muy variables. Podría favorecer un proceso que produce trabajos de gran tamaño sobre otros procesos. Este problema puede resolverse por tiempo compartido, es decir, dando a cada trabajo una franja horaria o cuántica (su asignación de tiempo de CPU) y interrumpir el trabajo si no se cumplimenta en ese entonces. El trabajo se reanuda la próxima vez que se asigna un horario a ese proceso.

Ejemplo: La franja horaria podría ser 100 milisegundos. Si job1 toma un tiempo total de 250ms para completar, el programador de round-robin se suspender el trabajo después de 100 MS y otros trabajos de su tiempo en la CPU. Una vez que los otros puestos de trabajo han tenido su igualdad compartir (100ms cada), job1 recibirán otra asignación de tiempo de CPU y se repetirá el ciclo. Este proceso continúa hasta que el trabajo finaliza y no necesita más tiempo de la CPU.

3.3.3 SHORTEST JOB FIRST (SJF).

Más corta-trabajo-First (SJF) es una disciplina no preferente en la que trabajo de espera (o proceso) con la más pequeña estimada run-tiempo-a-finalización se ejecuta siguiente. En otras palabras, cuando la CPU está disponible, se asigna al proceso que tiene más pequeña CPU siguiente ráfaga.

La programación de SJF es especialmente adecuada para trabajos por lotes para que los tiempos de ejecución son conocidos de antemano. Ya que el algoritmo de programación SJF da el tiempo promedio mínimo para un conjunto de procesos, es probablemente óptimo.

El algoritmo SJF favorece cortos de puestos de trabajo (o procesadores) a expensas de los más largos.

El problema evidente con el esquema de SJF es que requiere un conocimiento preciso de cuánto tiempo un trabajo o proceso se ejecutará y esta información no está disponible por lo general.

El algoritmo SJF mejor puede hacer es confiar en las estimaciones de usuario de tiempos de ejecución.

En el entorno de producción, donde los mismos trabajos se ejecutan regularmente, puede ser posible proporcionar una estimación razonable de tiempo de ejecución, basado en el rendimiento pasado del proceso. Pero en los usuarios del entorno de desarrollo rara vez saber cómo va a ejecutar su programa.

Como FCFS, SJF es no preventivo por lo tanto, no es útil en entorno de tiempo compartido en el que hay que garantizar el tiempo de respuesta razonable.

3.3.4 SHORTEST REMAINING TIME(STR).

Menor tiempo restante es un método de la CPU de programación que es una versión preventiva de puestos de trabajo más corta próximo de programación. En este algoritmo de programación, el proceso con la menor cantidad de tiempo que queda hasta la terminación es seleccionado para ejecutar. Dado que el proceso está ejecutando actualmente es el único con el menor lapso de tiempo restante por definición, y desde ese momento sólo debería reducir a medida que progresa de ejecución, procesos siempre va ejecutar hasta que completen o un nuevo proceso se agrega que requiere una menor cantidad de tiempo.

Menor tiempo restante es ventajoso porque procesos cortos se controlan muy rápidamente. El sistema también requiere muy poca carga, ya que sólo hace una decisión cuando un proceso finaliza o se agrega un nuevo proceso, y cuando se agrega un nuevo proceso de que sólo el algoritmo necesita comparar el proceso actualmente en ejecución con el nuevo proceso, haciendo caso omiso de todos los demás procesos actualmente espera de ejecución. Sin embargo, tiene el potencial para el proceso de hambre para los procesos que requieren mucho tiempo para completar si continuamente se agregan procesos cortos, aunque esta amenaza puede ser mínimo cuando tiempos de proceso siguen una distribución de cola pesada

3. 3. 5. HIGHEST RESPONSE RATIO NEXT (HNR)

Proporción más alta de respuesta siguiente (HRRN) la programación es una disciplina no preventiva, similar a la Siguiente trabajo más corta (SJN), en el que la prioridad de cada trabajo es dependiente de su tiempo de ejecución estimado y también la cantidad de tiempo ha pasado a la espera. Puestos de trabajo obtienen mayor prioridad que cuanto más tiempo esperan que impide que el aplazamiento indefinido (proceso de hambre). De hecho, los trabajos que se han pasado un largo tiempo espera compitan contra las que se estima que tienen tiempos de ejecución.

3.4 MULTIPROCESAMIENTO.

Medios de multiprocesamiento que tienen más de un procesador que opera en la misma memoria pero ejecuta procesos simultáneamente. En un sistema de multiprocesamiento procesadores múltiples son empleados a ejecutado más de una actividad en el tiempo, siempre que la informática masiva deba ser realizada con regularidad. Multiprocesador. Como muchas de las actividades principales de la informática se ejecutan simultáneamente por los procesadores diferentes.

Sin embargo, es esencial proporcionar la sincronización entre procesador múltiple ellos tienen acceso a la memoria común tal que ninguna parte del trabajo de informática debería ser descuidada por el procesador individual con una presunción que el otro procesador lo hará.

Un sistema de multiprocesamiento con vario funcionamiento juntos a la vez proporcionará un ambiente de multiprogramación. La multiprogramación permite que programas múltiples residan en áreas separadas de la memoria principal al mismo tiempo. Con este acercamiento, es posible mantener dos o más empleos simultáneamente en la ejecución o en estados de la ejecución.

Los sistemas de ordenador de multiprocesador son caros y encontraron su uso sólo en la aplicación de informática compleja y en la alta velocidad que funda el punto aplicación de cálculo numérica en espacios de Investigación e Industria.

3.5 CONCEPTOS BÁSICOS.

La mayoría de los sistemas de multiprocesamiento tienen como meta principal el incremento de la capacidad de ejecución. La programación sigue siendo esencialmente secuencial y generalmente no se explota la concurrencia.

Las principales razones son las siguientes:

•Las personas piensan en forma secuencial.

•Ningún lenguaje humano proporciona la expresión adecuada de paralelismo, pero existen lenguajes de computación con soporte de concurrencia (por ejemplo, Ada, Pascal Concurrente, etc.).

•Ni el multiprocesamiento ha sido usado con amplitud para explotar el paralelismo.

•El hardware tradicional del computador está orientado hacia la operación secuencial.

•Es muy difícil depurar programas en paralelo.

Los multiprocesadores no se utilizan a menudo para explotar el paralelismo ya que es muy escaso el software que explote el paralelismo.

Lo deseable es que los Sistemas Operativos y compiladores puedan detectar e implementar el paralelismo automáticamente.

Paralelismo Masivo

Se debe disponer de suficientes procesadores como para que todas las operaciones que puedan ser ejecutadas en paralelo puedan ser asignadas a procesadores separados.

Esto ofrece una forma de ejecutar un programa en el menor tiempo posible.

La cuestión central es, disponiendo del paralelismo masivo, ¿cuál es el tiempo mínimo requerido para ejecutar un algoritmo determinado?.

Detección Automática del Paralelismo

Los multiprocesadores hacen posible la explotación del paralelismo. Los sistemas de computación obtienen los beneficios del procesamiento concurrente más por la “multiprogramación” de varios procesos y menos por la explotación del “paralelismo” dentro de un solo proceso.

La detección del paralelismo es un problema complejo y la puede efectuar el programador, el traductor del lenguaje, el hardware o el Sistema Operativo.

El paralelismo dentro de los programas puede ser “explícito” o “implícito”.

Las principales características del paralelismo explícito son: 

Es indicado de forma específica por un programador mediante una “construcción de concurrencia” como la siguiente:

begin;

proposición     1;

proposición n;

end;

Se pueden utilizar procesadores separados para ejecutar cada una de las proposiciones.

Es susceptible de errores de programación difíciles de detectar y depurar.

El programador puede omitir tratar situaciones donde sería aplicable el paralelismo.

Las principales características del paralelismo implícito son:

•La verdadera esperanza está en la detección automática del paralelismo implícito.

•Es el paralelismo intrínseco del algoritmo pero no establecido explícitamente por el programador.

•Los compiladores explotan el paralelismo implícito mediante las técnicas de “distribución de ciclos” y de “reducción de la altura del árbol”.

3.6 PARALELISMO.

El paralelismo es una forma de computación en la cual varios cálculos pueden realizarse simultáneamente, basado en el principio de dividir los problemas grandes para obtener varios problemas pequeños, que son posteriormente solucionados en paralelo. Hay varios tipos diferentes de paralelismo: nivel de bit, nivel de instrucción, de datos y de tarea. El paralelismo ha sido empleado durante muchos años, sobre todo para la Computación de alto rendimiento.

Como la computación paralela se convierte cada día en más grande y rápida, muchos problemas considerados anteriormente muy largos y costosos se han podido solucionar. El paralelismo se ha utilizado para muchas temáticas diferentes, desde bioinformática (para hacer plegamiento de proteínas) hasta economía (para hacer simulaciones en matemática financiera). Los problemas típicos encontrados en el paralelismo son:

·         Simulación de Montecarlo

·         lógica combinaciones (como las técnicas de fuerza bruta)

·         Graph traversal

·         Programación dinámica

·         Métodos de ramificación y poda

·         Modelo en grafico

·         Simulación de autómata finito

3.7 SISTEMAS MULTIPROCESAMIENTO

Un sistema operativo se denomina de multiprocesos cuando muchas "tareas" (también conocidas como procesos) se pueden ejecutar al mismo tiempo.

Las aplicaciones consisten en una secuencia de instrucciones llamadas "procesos". Estos procesos permanecen activos, en espera, suspendidos, o se eliminan en forma alternativa, según la prioridad que se les haya concedido, o se pueden ejecutar en forma simultánea.

Un sistema se considera preventivo cuando cuenta con un programador (también llamado planificador) el cual, según los criterios de prioridad, asigna el tiempo de los equipos entre varios procesos que lo solicitan.

Se denomina sistema de tiempo compartido a un sistema cuando el programador asigna una cantidad determinada de tiempo a cada proceso. Éste es el caso de los sistemas de usuarios múltiples que permiten a varios usuarios utilizar aplicaciones diferentes o similares en el mismo equipo al mismo tiempo. De este modo, el sistema se denomina "sistema transaccional". Para realizar esto, el sistema asigna un período de tiempo a cada usuario.

La técnica de multiprocesamiento consiste en hacer funcionar varios procesadores en forma paralela para obtener un poder de cálculo mayor que el obtenido al usar un procesador de alta tecnología o al aumentar la disponibilidad del sistema (en el caso de fallas del procesador).

Las siglas SMP (multiprocesamiento simétrico o multiprocesador simétrico) hacen referencia a la arquitectura en la que todos los procesadores acceden a la misma memoria compartida.

Un sistema de multiprocesadores debe tener capacidad para gestionar la repartición de memoria entre varios procesadores, pero también debe distribuir la carga de trabajo.

3.8 ORGANIZACIÓN DEL MULTIPROCESADOR.

Se denomina multiprocesador a un computador que cuenta con dos o más microprocesadores (CPUs).

Gracias a esto, el multiprocesador puede ejecutar simultáneamente varios hilos pertenecientes a un mismo proceso o bien a procesos diferentes.

Los ordenadores multiprocesador presentan problemas de diseño que no se encuentran en ordenadores monoprocesador. Estos problemas derivan del hecho de que dos programas pueden ejecutarse simultáneamente y, potencialmente, pueden interferirse entre sí. Concretamente, en lo que se refiere a las lecturas y escrituras en memoria. Existen dos arquitecturas que resuelven estos problemas:

La arquitectura NUMA, donde cada procesador tiene acceso y control exclusivo a una parte de la memoria.

La arquitectura SMP, donde todos los procesadores comparten toda la memoria.

Esta última debe lidiar con el problema de la coherencia de caché. Cada microprocesador cuenta con su propia memoria cache local. De manera que cuando un microprocesador escribe en una dirección de memoria, lo hace únicamente sobre su copia local en caché. Si otro microprocesador tiene almacenada la misma dirección de memoria en su caché, resultará que trabaja con una copia obsoleta del dato almacenado.

Para que un multiprocesador opere correctamente necesita un sistema operativo especialmente diseñado para ello. La mayoría de los sistemas operativos actuales poseen esta capacidad.

3.9 SISTEMAS OPERATIVOS DEL MULTIPROCESADOR.

  Un sistema operativo multiproceso o multitarea es aquel que permite ejecutar varios procesos de forma concurrente, la razón es porque actualmente nuestras CPUs sólo pueden ejecutar un proceso cada vez. La única forma de que se ejecuten de forma simultánea varios procesos es tener varias CPUs (ya sea en una máquina o en varias, en un sistema distribuido).

    La magia de un sistema operativo multiproceso reside en la operación llamada cambio de contexto. Esta operación consiste en quitar a un proceso de la CPU, ejecutar otro proceso y volver a colocar el primero sin que se entere de nada.