Libro Sistemas Operativos-cap 2

8/16/2019 Libro Sistemas Operativos-cap 2

http://slidepdf.com/reader/full/libro-sistemas-operativos-cap-2 1/42

Excelencia Académica

1

TABLA DE CONTENIDO

TABLA DE CONTENIDO ............................................................................................................................... 5

INTRODUCCION A LOS SISTEMAS OPERATIVOS................................................................................ 9 ¿QUÉ ES UN SISTEMA OPERATIVO? ........................................................................................................ 9HISTORIA DE LOS SISTEMAS OPERATIVOS: GENERACIONES....................................................... 11

Generación Cero (década de 1940): ........................................................................................................ 11 Primera generación (1945-1955): bulbos y conexiones .......................................................................... 11 Segunda generación (1955-1965): transistores y sistemas de procesamiento por lotes (batch) ........... 11 Tercera generación (1965-1980): circuitos integrados y multiprogramación ....................................... 12 Cuarta generación (1980-1990): computadoras personales: ................................................................. 13

CONCEPTOS DE LOS SISTEMAS OPERATIVOS ................................................................................... 13 Procesos .................................................................................................................................................... 14 Archivos: ................................................................................................................................................... 14 Llamadas al sistema: ................................................................................................................................ 14

ESTRUCTURA DE LOS SISTEMAS OPERATIVOS ................................................................................ 15Sistemas monolíticos:................................................................................................................................ 15 Sistemas con capas: .................................................................................................................................. 16

Máquinas virtuales: .................................................................................................................................. 18 Modelo cliente - servidor .......................................................................................................................... 18

MÁS ESTRUCTURAS DE SISTEMAS OPERATIVOS............................................................................. 19 El sistema operativos DOS ....................................................................................................................... 19 El sistema operativo UNIX ....................................................................................................................... 20

EL SISTEMA OPERATIVOOS/2 ................................................................................................................ 20 Arquitectura de Windows NT.................................................................................................................... 21

PLANIFICACION DE PROCESOS 3 ........................................................................................................... 25

CONCEPTOS DE PLANIFICACIÓN.......................................................................................................... 25COLAS DE PLANIFICACIÓN ................................................................................................................. 26

Planificadores ........................................................................................................................................... 28 PLANIFICACIÓN DE LA UCP ................................................................................................................... 29

Ciclo de ráfagas de UCP y de E/S............................................................................................................ 30 Planificador de la ucp............................................................................................................................... 31 Estructura de planificación ...................................................................................................................... 31 Cambio de contexto................................................................................................................................... 32

Despachador ............................................................................................................................................. 32 ALGORITMOS DE PLANIFICACIÓN....................................................................................................... 32

Planificación “ servicio por orden de llegada”........................................................................................ 33 Planificación “ Primero el trabajo más breve”........................................................................................ 34 Planificación por prioridades................................................................................................................... 37 Planificación circular ............................................................................................................................... 38 Planificación de colas de múltiples niveles.............................................................................................. 40 Planificación de colas de múltiples niveles con realimentación ............................................................. 42

PLANIFICACIÓN DE PROCESADORES MÚLTIPLES .......................................................................... 43



8




9


INTRODUCCION A LOS SISTEMAS OPERATIVOS

¿QUÉ ES UN SISTEMA OPERATIVO?

Una de las definiciones más comúnmente aceptadas expresa:“Un Sistema Operativo (S. O.) es un grupo de programas de proceso con las rutinas de controlnecesarias para mantener continuamente operativos dichos programas”. El objetivo primario de un Sistema Operativo es optimizar todos los recursos del sistema parasoportar los requerimientos.

A los efectos de situar a los S. O. en el conjunto del software para computadoras, podemosclasificar a este de la siguiente manera: Programas de sistema: Controlan la operación de la computadora en sí.

Programas de aplicación: Resuelven problemas para los usuarios.

En este contexto, el Sistema Operativo es el programa fundamental de todos los programas desistema. El S. O. protege y libera a los programadores de la complejidad del hardware, colocándoseun nivel de software por sobre el hardware para: Controlar todas las partes del sistema.

Presentar al usuario una interfaz o máquina virtual.

El esquema típico de un sistema de cómputos incluye: Programas de aplicación: Sistema bancario, reservaciones en una línea aérea, juegos, etc.

Programas de sistema: Compiladores, editores, intérpretes de comandos y el SistemaOperativo.

Hardware: Lenguaje de máquina, microprogramación y los dispositivos físicos.

Las principales características del microprograma son: Se trata de software que generalmente se localiza en la memoria de solo lectura.

Busca las instrucciones de lenguaje de máquina para ejecutarlas como una serie depequeños pasos.

El conjunto de instrucciones que interpreta define al lenguaje de máquina.

En ciertas máquinas se implanta en el hardware y no es en realidad una capa distinta.

Respecto del lenguaje de máquina es preciso señalar que: Generalmente posee entre 50 y 300 instrucciones, sirviendo la mayoría para desplazar datos,

hacer operaciones aritméticas y comparar valores.

Los dispositivos de e / s (entrada / salida) se controlan al cargar valores en registros deldispositivo especiales.



1


Una de las principales funciones del S. O. es ocultar toda esta complejidad y brindar alprogramador un conjunto más conveniente de instrucciones para trabajar.El S. O. se ejecuta en modocentral o modode supervisión, con máxima prioridad y generalmentecon protección por hardware.Los compiladores, editores y demás programas se ejecutan en modousuario.El S. O. es la serie de programas, dispuestos ya sea en el software o en la memoria fija

(microcódigo), que hacen al hardware utilizable.Según Deitel1 los S. O. ponen el “ poder computacional básico” del hardware convenientemente adisposición del usuario, pero consumen parte de ese poder computacional para funcionar.Los S. O. son, en primer lugar, administradores de recursos, siendo el recurso primario elhardware del sistema (ver Figura.1).

Figura.1. Recursos administrados por el S.O.Las principales características de los S. O. son: Definir la “Interfaz del Usuario”.

Compartir el hardware entre usuarios.

Permitir a los usuarios compartir los datos entre ellos.

Planificar recursos entre usuarios.

Facilitar la entrada / salida.

1 Deitel M. Introducción a los Sistemas Operativos. España: Addison Wesley Iberoamericana,Segunda Edición; 1998.



1




1


Recuperarse de los errores.

Los principales recursos administrados por los S. O. son: Procesadores.

Almacenamiento.

Dispositivos de e / s.

Datos.

Los S. O. son una interfaz con: Operadores.

Programadores de aplicaciones.

Programadores de sistemas (administradores del S. O.).

Programas.

Hardware.

Usuarios.

El S. O. debe presentar al usuario el equivalente de una máquina extendida o máquina virtual que sea más fácil de programar que el hardware subyacente.

HISTORIA DE LOS SISTEMAS OPERATIVOS: GENERACIONES

Los S. O. han estado relacionados históricamente con la arquitectura de las computadoras en lascuales se ejecutan, razón por la cual su historia puede analizarse según las generaciones y susprincipales características1.

Generación Cero (década de 1940): Carencia total de S. O.

Completo acceso al lenguaje de máquina.

Primera generación (1945-1955): bulbos y conexiones

Carencia de S. O.

En los años cincuenta comienzan como transición entre trabajos, haciendo la misma mássimple.

Segunda generación (1955-1965): transistores y sistemas deprocesamiento por lotes (batch)

En los años sesenta aparecen los S. O. para sistemas compartidos con:






12

o Mult iprogramación : varios programas de usuarios se

encuentran al mismo tiempo en el almacenamiento principal,cambiando el procesador rápidamente de un trabajo a otro.

o Mult iprocesamiento : varios procesadores se utilizan en un

mismo sistema para incrementar el poder de procesamiento. Posteriormente aparece la independencia de dispositivo:

o El programa del usuario especifica las características de los dispositivosque requieren los archivos.

o El S. O. asigna los dispositivos correspondientes según los requerimientos ylas disponibilidades.

Tercera generación (1965-1980): circuitos integrados y

multiprogramación Difusión de la multiprogramación:

o Partición de la memoria en porciones, con trabajos distintos en cada unade ellas.

o Aprovechamiento del tiempo de espera consecuencia de operaciones de e / s, para utilizar la CPU para otros procesos.

Protección por hardware del contenido de cada partición de memoria.

Aparición de técnicas de spooling:

o Simultaneous Peripheral Operation On Line: operación simultánea y en

línea de periféricos.

o Almacenamiento de trabajos de entrada y de salida en dispositivostransitorios rápidos (discos), para disminuir el impacto de los periféricosmás lentos.

Son sistemas de modos múltiples, es decir que deben soportar sistemas de propósitosgenerales; son grandes y complejos pero muy poderosos.

Interponen una capa de software entre el usuario y el hardware.

Aparecen los lenguajes de control de trabajos, necesarios para especificar el trabajo y losrecursos requeridos.

Soportan timesharing (tiempo compartido), variante de la multiprogramación con usuariosconectados mediante terminales en línea, permitiendo la operación en modo interactivo oconversacional.

Aparecen los sistemas de tiempo real, que requieren tiempos de respuesta muy exigentes,especialmente para usos industriales o militares.




13

Se difunden las computadoras de rango medio.

Cuarta generación (1980-1990): computadoras personales:

Aparición de software amigable con el usuario, destinado a usuarios no profesionales y conuna interfase gráfica muy desarrollada.

Desarrollo de sistemas operativos de red y sistemas operativos distribuidos.

Sistemas operativos de red:

o Los usuarios están conscientes de la existencia de varias computadorasconectadas.

o Cada máquina ejecuta su propio S. O. local.

o Son similares a los S. O. de un solo procesador pero con el agregado de

controlador de interfaz de la red, su software de bajo nivel y el software para conexión y acceso a archivos remotos, etc.

Sistemas operativos distribuidos:

o Aparece ante los usuarios como un S. O. de un solo procesador, aúncuando de soporte a varios procesadores.

o Los usuarios no son conscientes del lugar donde se ejecutan sus

programas o donde se encuentran sus archivos, ya que lo debe administrarel S. O. automáticamente.

o

Deben permitir que un programa se ejecute mediante varios procesadores ala vez, maximizando el paralelismo.

Aparición de emuladores de terminal para el acceso a equipos remotos desde computadoraspersonales (PC).

Gran énfasis en la seguridad, en especial por el desarrollo de los sistemas decomunicaciones de datos.

El S. O. crea un ambiente de trabajo según el concepto de máquina virtual, que lo aísla delfuncionamiento interno de la máquina.

Proliferación de sistemas de bases de datos, accesibles mediante redes de comunicación.

CONCEPTOS DE LOS SISTEMAS OPERATIVOS

La interfaz entre el S. O. y los programas del usuario se define como el conjunto de“instrucciones ampliadas” que proporciona el S. O. y son las “llamadas al sistema”:2

Crean, eliminan y utilizan objetos del software controlados por el S. O.: Los más importantesson procesos y archivos.

2 Tanenbaum A. Sistemas Operativos Modernos. Mexico: Pearson Educación, Segunda Edición; 2003.




14

Procesos

Es el concepto central de todos los S. O.

Es básicamente un programa en ejecución.

Consta del programa ejecutable, sus datos y pila, contador y otros registros, además de lainformación necesaria para ejecutar el programa.

La información de control relacionada con los procesos se almacena en la tabla deprocesos:

o Es administrada por el S.O.

o Posee un arreglo de estructuras, una por cada proceso existente en esemomento.

Un proceso (suspendido) consta de:

o Un espacio de dirección.

o Los datos pertinentes de la tabla de procesos.

Un proceso puede crear procesos hijo y estos nuevos procesos hijo, conformando un árbolde procesos.

Archivos:

Una de las funciones principales del S. O. es brindar independencia de dispositivo.

Muchos S. O. soportan el concepto de directorio como una forma de agrupar archivos.

Los directorios se estructuran jerárquicamente, por lo que a cada archivo le corresponde unaruta de acceso.

Existen distintos esquemas de seguridad de archivos en los distintos S. O.

Llamadas al sistema:

Permiten a los programas comunicarse con el S. O. y solicitarle servicios.

A cada llamada le corresponde un procedimiento:

o Pone los parámetros de la llamada en un lugar especí…co para luegoejecutar una instrucción tipo “t rap” de llamada a procedimiento protegido

para iniciar el S. O.

o Luego de “trap” el S. O. recupera el control , examina los parámetros y sison válidos ejecuta el trabajo solicitado.




15

o Luego de terminar, el S. O. coloca un código de estado en un registroindicando si tuvo éxito o fracaso y ejecuta una instrucción del tipo “r eturnfrom tr ap” para regresar el control al procedimiento.

o El procedimiento regresa al programa llamador con un código de estado

como un valor de función; dentro de los parámetros pueden regresarvalores adicionales.

ESTRUCTURA DE LOS SISTEMAS OPERATIVOS

Se considera la organización interna de los S. O. y conforme a ella se los clasifica de la siguientemanera, destacándose sus principales características:

Sistemas monolíticos:

Es muy común: no existe estructura propiamente dicha o es mínima.

El S. O. es una colección de procedimientos que se pueden llamar entre sí (ver Figura.22).

Figura.2. Modelo de estructura simple para un sistema monolítico.

Cada procedimiento tiene una interfaz bien definida en términos de parámetros y resultados.




16

Figura.3. Forma de llamada al sistema en un sistema monolítico.

Para ejecutar los servicios del S. O. (llamadas al sistema)2: (ver Figura.3).

o Se solicitan colocando los parámetros en lugares bien definidos (registros o pilas).

o Se ejecuta una instrucción especial de trampa: l lamada al núcleo o l lamada al supervis or.

o La instrucción cambia la máquina del modo usuario al modo núcleo (omodo supervisor)2 .

o Se transfiere el control al S. O.

o El S. O. examina los parámetros de la llamada para determinar cuál deellas se desea realizar.

o El S. O. analiza una tabla que contiene en la entrada “k” un apuntador al procedimiento que realiza la “k-ésima” llamada al sistema:

o Identifica al procedimiento de servicio llamado.

o La llamada al sistema termina y el control regresa al programa del usuario.

Sistemas con capas:

Es una generalización del modelo de estructura simple para un sistema monolítico.

Consiste en organizar el s. o. como una jerarquía de capas, cada una construida sobre la

inmediata inferior.

El primer sistema con este esquema fue el “THE” (Holanda - Dijkstra -1968)2: (ver Tabla.1).“THE”: Technische Hogeschool Eindhoven. Capa 0:

o Trabaja con la asignación del procesador.

o Alterna entre los procesos cuando ocurren las interrupciones o expiran loscronómetros.

Proporciona la multiprogramación básica.

Capa 1:

o Administra la memoria.

o Asegura que las páginas (porciones de memoria) requeridas de los procesos lleguen a memoria cuando fueran necesarias.




17

Tabla.1. Estructura del S.O. en capas “THE”

5 - Operador

4 - Programas del

Usuario3 - Control de Entrada -Salida

2 - ComunicacionesOperador - Proceso

1 - Administración de laMemoria y del Disco

0 - Asignación delProcesador y

Multiprogramación Capa 2:

o Administra la comunicación entre cada proceso y la consola del operador.

o Por sobre esta capa, cada proceso tiene su propia consola de operador.

Capa 3:

o Controla los dispositivos de e / s y almacena en buffers los flujos deinformación entre ellos.

o Por sobre la capa 3 cada proceso puede trabajar con dispositivosabstractos de e / s en vez de con dispositivos reales.

Capa 4:

o Aloja los programas del usuario.

o Los programas. del usuario no tienen que preocuparse por el proceso,memoria, consola o control de e / s.

Capa 5:

o Localiza el proceso operador del sistema.

Una generalización mas avanzada del concepto de capas se presento con “Multics” (MIT, BellLabs y General Electric): “Multics”: multiplexed information and computing service.

Presenta una estructura en anillos concéntricos, siendo los interiores los privilegiados.

Un procedimiento de un anillo exterior, para llamar a un procedimiento de un anillo interior,debe hacer el equivalente a una llamada al sistema.




18

Máquinas virtuales:

Se separan totalmente las funciones de multiprogramación y de máquina extendida.Existe un elemento central llamado monitor de la máquina virtual que: Se ejecuta en el hardware.

Realiza la multiprogramación.

Proporciona varias máquinas virtuales a la capa superior.

Las máquinas virtuales instrumentan copias “exactas” del hardware simple, con su modo núcleo /usuario, e / s, interrupciones y todo lo demás que posee una máquina real.Pueden ejecutar cualquier S. O. que se ejecute en forma directa sobre el hardware.Las distintas máquinas virtuales pueden ejecutar distintos S. O. y en general así lo hacen.Soportan periféricos virtuales.Un ejemplo de S. O. representativo de esta estructura (“VM/370” de IBM2), se muestra en laFigura.4.

Figura.4. La estructura de VM-370 con CMS.

Las VM generalmente utilizaran, entre otros, el S. O. “CMS”: Conversational Monitor System.Cuando un programa “CMS” ejecuta una llamada al sistema: La llamada es atrapada por el S. O. en su propia máquina virtual; no pasa directamente al

“VM/370”.

“CMS” proporciona las instrucciones de e / s en hardware para la lectura del disco virtual o lonecesario para efectuar la llamada.

“VM/370” atrapa estas instrucciones de e / s y las ejecuta sobre el hardware verdadero.

Modelo cliente - servidor

Una tendencia en los S. O. modernos es la de explotar la idea de mover el código a capassuperiores y mantener un núcleo mínimo, de manera similar al “VM/370”.Implantar la mayoría de las funciones del S. O. en los procesos del usuario.La Figura.5 muestra la solicitud de un servicio (por ej.: lectura de un bloque de cierto archivo)

según el modelo cliente - servidor 2.El proceso del usuario (proceso cliente) envía la solicitud a un proceso servidor : Realiza el trabajo y regresa la respuesta.

El núcleo controla la comunicación entre los clientes y los servidores.

Se fracciona el S. O. en partes, cada una controlando una faceta: servicio a archivos, a procesos,a terminales, a memoria, etc., cada parte pequeña y más fácilmente controlable.Los servidores se ejecutan como procesos en modo usuario:




19

No tienen acceso directo al hardware.

Se aíslan y acotan más fácilmente los problemas.

Figura.5. El modelo cliente – servidor.

Se adapta para su uso en los sistemas distribuidos: (ver Figura.6).

Figura.6. El modelo cliente – servidor en un sistema distribuido.

Si un cliente se comunica con un servidor mediante mensajes: No necesita saber si el mensaje se atiende localmente o mediante un servidor remoto, situado

en otra máquina conectada.

Envía una solicitud y obtiene una respuesta.

Algunas funciones del S. O., por ejemplo el cargado de comandos en los registros físicos deldispositivo de e / s, presentan problemas especiales y distintas soluciones: Ejecución en modo núcleo, con acceso total al hardware y comunicación con los demás

procesos mediante el mecanismo normal de mensajes.

Construcción de un mínimo de mecanismos dentro del núcleo manteniendo las decisionesde política relativas a los usuarios dentro del espacio del usuario.

MÁS ESTRUCTURAS DE SISTEMAS OPERATIVOS

El sistema operativo se divide lógicamente en pequeños módulos y se crea una interfase biendefinida para estos módulos. Cada uno de estos módulos o piezas deben tener su función, susinputs y outputs cuidadosamente definidos.

El sistema operativos DOS

El sistema operativos DOS no cuenta con una buena división de estos módulos ya que no seencuentra bien particionado permitiendo el acceso directo de los programas de aplicación a rutinas




20

básicas de E/S para grabar directamente en el display o en los discos, por ello el sistema esvulnerable a estos programas los que pueden provocar el crash del sistema.La estructura de este sistema puede verse en la Figura.7.

Figura.7. Estructura del sistema operativo DOS.

El sistema operativo UNIX

Otro ejemplo de un sistema operativo que no fue bien construido lo constituye el UNIX. Este sistemase encuentra divido en dos partes una de ellas comprende los programas del sistema y la otra elkernel. El kernel se encuentra divido en drivers de dispositivos y en las interfases (ver Figura.8).

Lamentablemente este kernel combina demasiada funcionalidad en un solo nivel. Las llamadas alsistema definen la interfase del programador al UNIX. El conjunto de programas de sistemausualmente disponibles definen la interfase del usuario. Ambas definen el contexto al cual el kerneldebe dar soporte.Otras mejoras posteriores al UNIX han separado el kernel en más módulos, por ejemplo en elsistema operativo AIX de IBM se lo dividió en dos partes. El MACH de Carnegie-Mellon redujo elkernel a un conjunto pequeño de funciones básicas trasladando todo lo no esencial a los nivelesdel sistema o incluso al del usuario.

EL SISTEMA OPERATIVO OS/2

El OS/2 un descendiente directo del MS-DOS fue creado para superar las limitaciones de esteúltimo. El OS/2 provee multitasking y operación en modo dual como así también otras nuevasmejoras.En contraposición a la estructura del MS-DOS la estructura del OS/2 se encuentra diseñada encapas que por ejemplo, no permiten el acceso directo del usuario a facilidades de bajo nivel lo queotorga un mayor control al sistema operativo sobre el hardware y un mayor conocimiento de quérecursos está utilizando cada programa de usuario.En la Figura.9 podemos ver la estructura en capas del sistema operativo OS/2.




21

Figura.8. Estructura del UNIX.

Figura.9. Estructura de capas del OS/2.

Arquitectura de Windows NT

La familia de los sistemas operativos Windows NT de Microsoft está constituida por versionescomo Windows Vista, Windows Server 2003, Windows XP, Windows 2000 y Windows NT. Todostienen multitarea apropiativa y son sistemas operativos reentrantes que han sido diseñados paratrabajar tanto con ordenadores con un sólo procesador como ordenadores de multiprocesamientosimétrico que en inglés es el Symmetrical Multi Processor o SMP. Para procesar las peticiones deentrada/salida (en inglés Input/Output, I/O) acude a una dirección de paquetes de E/S que utilizapeticiones (IRPs) y E/S asíncrona. A partir de Windows XP, Microsoft comenzó a desarrollarsistemas operativos que soportaban 64-bits. Antes sus sistemas operativos estaban basados en unmodelo de 32-bits.La arquitectura de Windows NT es altamente modular y se basa en dos capas principales(Figura.10):




22

Modo usuario: Cuyos programas y subsistemas están limitados a los recursos del sistema alos que tienen acceso.

Modo núcleo: Tiene acceso total a la memoria del sistema y los dispositivos externos. Losnúcleos de los sistemas operativos de esta línea son todos conocidos como núcleos híbridos,aunque hay que aclarar que este término está en discusión ya que este núcleo es

esencialmente un núcleo monolítico que está estructurado al estilo de un micronúcleo. Laarquitectura dentro del modo núcleo se compone de lo siguiente:

Un núcleo híbrido.

Una Capa de Abstracción de Hardware (HAL).

Drivers.

Executive: Sobre el cual son implementados todos los servicios de altonivel.

Figura.10. La arquitectura de Windows NT.

El modo núcleo de la línea de Windows NT está compuesto por subsistemas capaces

de pasar peticiones de E/S a los drivers apropiados usando el gestor de E/S. Dossubsistemas crean la capa del modo usuario de Windows 2000: el subsistema deEntorno (ejecuta aplicaciones escritas para distintos tipos de sistemasoperativos), y el subsistema Integral (maneja funciones específicas de sistema de

parte del subsistema de Entorno). El modo núcleo en Windows 2000 tiene accesototal al hardware y a los recursos del sistema del ordenador. El modo núcleo impidea los servicios del modo usuario y las aplicaciones acceder a áreas críticas delsistema operativo a las que no deberían tener acceso.




23

El Executive se relaciona con todos los subsistemas del modo usuario. Se ocupade la entrada/salida, la gestión de objetos, la seguridad y la gestión de procesos.El núcleo se sitúa entre la Capa de Abstracción de Hardware y el Executive para

proporcionar sincronización multiprocesador, hilos y programación y envío deinterrupciones, y envío de excepciones.

El núcleo también es responsable de la inicialización de los drivers de dispositivosal arrancar. Hay tres niveles de drivers en el modo núcleo: drivers de alto nivel,drivers intermedios y drivers de bajo nivel. El Modelo de Drivers de Windows (eninglés Windows Driver Model, WDM) se encuentra en la capa intermedia y fuediseñado principalmente para mantener la compatibilidad en binario y en códigofuente entre Windows 98 y Windows 2000. Los drivers de más bajo nivel tambiénson un legado de los drivers de dispositivos de Windows NT que controlandirectamente un dispositivo o puede ser un bus hardware PnP.

Un Sistema Operativo (S. O.) es un grupo de programas de proceso con lasrutinas de control necesarias para mantener continuamente operativos dichosprogramas.El objetivo primario de un Sistema Operativo es optimizar todos los recursos delsistema para soportar los requerimientos.

El lector explica los fundamentos de los Sistemas Operativos.

Deitel M. Introducción a los Sistemas Operativos. España: Addison WesleyIberoamericana, Segunda Edición; 1998.

Tanenbaum A. Sistemas Operativos Modernos. Mexico: Pearson Educación,Segunda Edición; 2003.

La siguiente unidad académica analiza la planificación de procesos.




AUTOEVALUACIÓN FORMATIVA

Supongamos que usted a sido designado para implementar un sistema operativo,¿cuál sería la arquitectura que usted recomendaría?; justifique su respuesta.

1----------------------




25

PLANIFICACION DE PROCESOS 3

Un proceso es un programa que se está ejecutando y hoy en día los sistemas operativos tienenvarios procesos en ejecución; por lo que se requiere realizar la planificación de la ejcución deestos procesos.

CONCEPTOS DE PLANIFICACIÓN

El objetivo de la multiprogramación es que en todo momento se ejecute un proceso para maximizarla utilización de la UCP (Unidad Central de Proceso). En un sistema monoprocesador nunca habrámás de un proceso en ejecución. Si hay más procesos, tendrán que esperar a que la UCP esté librey pueda volver a planificarse.

El concepto de multiprogramación es bastante sencillo: un proceso se ejecuta hasta que tenga queesperar, generalmente a que termine una solicitud de E/S. En un sistema de computación sencillo,la UCP permanecería inactiva; todo este tiempo de espera se desperdicia sin efectuar ningunaactividad útil. Con la multiprogramación tratamos de emplear productivamente este tiempo. Variosprocesos se conservan en memoria a la vez, y cuando uno de ellos tiene que esperar, el sistemaoperativo le quita la UCP al proceso y se la da a otro; este modelo continúa. Cada vez que unproceso tiene que esperar, otro puede utilizar la UCP.Los beneficios de la multiprogramación son un aumento de la utilización de la UCP y una mayorproductividad. La productividad es la cantidad de trabajo desarrollada en un intervalo de tiempo(por ejemplo, 17 procesos por hora). Como ejemplo extremo, supongamos que tenemos dosprocesos, P0 y P1 por ejecutar (Figura.11). Cada proceso se ejecuta durante un segundo, y luegoespera otro segundo; este modelo se repite 60 veces. Si primero ejecutamos el proceso P0 ydespués el P1 uno tras otro, costaría cuatro minutos ejecutar ambos procesos (Figura.12); elproceso P0 tarda dos minutos en ejecutarse y el proceso P1 otros dos minutos, pero en realidad

sólo se efectúan cálculos durante dos minutos, mientras que los otros dos representan tiempoinactivo. Así, nuestra utilización de la UCP es sólo del 50%.

Figura.11. Dos procesos, P0 y P1, listos para su ejecución.

Si multiprogramamos los procesos P0 y P1 podemos mejorar en granmedida el rendimiento del sistema

Figura.13). Comenzamos con el proceso P0 que se ejecuta durante un segundo; luego, mientrasel proceso P0 espera durante otro segundo, ejecutamos el proceso P1. Mientras el proceso P1




26

espera, el P0 está listo para la ejecución. Ahora el tiempo transcurrido para la ejecución de ambosprocesos es sólo dos minutos, y no hay tiempo inactivo de la UCP de manera que hemosmejorado su utilización del 50 al 100%, incrementando también la productividad. Observe que elproceso P0 no termina antes, pero ahora el proceso P1 finaliza en dos minutos.

Figura.12. Ejecución de procesos sin multiprogramación

Figura.13. Ejecución de procesos con multiprogramación.

Este ejemplo es un caso extremo y es poco probable que ocurra en la práctica, pero ilustra elconcepto de la multiprogramación.

COLAS DE PLANIFICACIÓN

Conforme los procesos entran en el sistema, se colocan en una cola de trabajos formada portodos los procesos que residen en almacenamiento secundario esperando la asignación de lamemoria principal. Los procesos que residen en la memoria principal y que están listos y esperandosu ejecución se mantienen en una lista llamada cola de procesos listos; esta lista es generalmenteuna lista ligada. Un encabezado de la cola de procesos listos contendrá apuntadores alprimer y último PCB de la lista. Cada PCB tiene un campo apuntador que indica el siguiente procesoen la cola de procesos listos.

También hay otras colas en el sistema. Cuando la UCP se asigna a un

proceso, se ejecuta durante un tiempo y después termina o espera a queocurra un suceso determinado, como la conclusión de una solicitud de E/S.En este caso, la E/S puede estar dirigida a una unidad de cinta dedicada o aun dispositivo compartido, por ejemplo un disco. Puesto que en el sistemahay varios procesos, el disco puede estar ocupado con la solicitud de E/Sde otro proceso, por lo que el proceso tendrá que esperar al disco. La listade procesos que espera a un dispositivo de E/S determinado se denominacola del dispositivo, y cada dispositivo tiene su propia cola




27

Figura.14). Si se trata de un dispositivo dedicado, como una unidad de cinta, la cola del dispositivonunca tendrá más de un proceso. Si, por el contrario, el dispositivo se puede compartir, como es elcaso de un disco, en la cola del dispositivo puede haber varios procesos.Una representación común para analizar la planificación de procesos es el diagrama de colas,como se muestra en la Figura.15. Cada rectángulo representa una cola, y hay dos tipos de colas:la cola de procesos listos y un conjunto de colas de dispositivo. Los círculos representan los

recursos que dan servicio a las colas y las flechas indican el flujo de los procesos en el sistema.

Figura.14. Cola de procesos listos y varias colas de dispositivo de E/S.

Un proceso nuevo se coloca inicialmente en la cola de procesos listos y allí espera hasta que seselecciona para su ejecución y se le entrega la UCP; una vez que ésta se asigna al proceso y seejecuta, puede ocurrir uno de estos sucesos: El proceso puede emitir una solicitud de E/S y colocarse en una cola de dispositivo.

El proceso puede crear un nuevo proceso y esperar a que éste termine.

El proceso podría ser extraído de la UCP por la fuerza, como resultado de una interrupción, ycolocarse de nuevo en la cola de procesos listos.

En los dos primeros casos, el proceso cambia eventualmente del estado de espera al estado delisto y se coloca de nuevo en la cola de procesos listos. Un proceso continúa con este ciclo hastaque termina, y es entonces cuando sale del sistema.



28


Figura.15. Representación de la planificación de procesos mediante un diagrama de colas.

Planificadores

En el transcurso de su vida, un proceso transita entre las distintas colas de planificación,y el sistema operativo de alguna manera debe seleccionar procesos de estas colas. Esta

actividad de selección es realizada por el planificador correspondiente. En un sistema por lotes, con frecuencia se presentan más procesos que los que se

pueden ejecutar de inmediato; estos procesos se envían a un spooler en un dispositivode almacenamiento masivo (un disco, normalmente), donde se conservan para su

posterior ejecución. El planificador a largo plazo (o planificador de trabajos) seleccionaprocesos de este depósito y los carga en memoria para su ejecución. El planificador a

corto plazo (o planificador de la UCP) selecciona uno de los procesos listos para

ejecución y le asigna la UCP. La principal diferencia entre estos dos planificadores es la frecuencia de su ejecución. El

planificador a corto plazo debe seleccionar con mucha frecuencia un nuevo proceso para

la UCP, y el proceso quizá se ejecute única mente durante unos milisegundos antes de

esperar una solicitud de E/S; en muchos casos, este planificador de la UCP se ejecutapor lo menos una vez cada 10 milisegundos. Debido al breve lapso de tiempo entre

ejecuciones, el planificador de la UCP debe ser muy rápido. Si cuesta un milisegundodecidir la ejecución de un proceso de 10 milisegundos, entonces 1/(10 + 1) = 9% de la

UCP se usa (se desperdicia) simplemente para que la planificación funcione. Por otra parte, el planificador a largo plazo se ejecuta con una frecuencia mucho menor. Pueden transcurrir minutos entre la creación de nuevos procesos en el sistema. El planificadora largo plazo controla el grado de multiprogramación (el número de procesos en memoria);si el grado de multiprogramación es estable, entonces la tasa promedio de creación deprocesos debe ser igual a la tasa promedio de salida para los procesos que dejan elsistema, de modo que sólo hay que invocar al planificador a largo plazo cuando un procesosale del sistema. Debido al mayor intervalo de tiempo entre ejecuciones, el planificador alargo plazo puede emplear más tiempo para decidir qué proceso se debe seleccionar parasu ejecución. También puede ser más importante que el planificador a largo plazo efectúe una selección cuidadosa. Por lo general, la mayoría de los procesos pueden describirse como

limitados por la UCP o limitados por E/S. Un proceso limitado por E/S es aquel que



29


emplea más tiempo en realizar E/S que en efectuar cálculos. Por otra parte, un proceso

limitado por la UCP es el que genera solicitudes de E/S con poca frecuencia, invirtiendola mayor parte de su tiempo en efectuar cálculos que los procesos limitados por E/S. Es

importante que el planificador a largo plazo seleccione una buena mezcla de procesoslimitados por la UCP y limitados por E/S. Si todos los procesos están limitados por E/S, la

cola de procesos listos estará casi vacía y el planificador a corto plazo tendrá poco que

hacer. Si todos los procesos están limitados por la UCP, la cola de espera de E/S casi siemprepermanecerá vacía, y una vez más se desequilibrará el sistema. El sistema con el mejorrendimiento tendrá una combinación de procesos limitados por la UCP y limitadospor E/S. En algunos sistemas es posible que no exista el planificador a largo plazo oque su función sea mínima. Por ejemplo, los sistemas de tiempo compartido muchasveces no cuentan con un planificador a largo plazo, y colocan cada nuevo procesoen la memoria para que lo manipule el planificador a corto plazo. La estabilidad de estossistemas depende de una limitación física (como el número de terminales disponibles) o deque las características de los usuarios se ajusten automáticamente. Si el rendimiento bajahasta niveles inaceptables, algunos usuarios abandonarán y se dedicarán a otra cosa.

Algunos sistemas operativos, como los de tiempo compartido, pueden presentar un nivel intermedio adicional de planificación. El diagrama de este planificador a mediano plazo se

presenta en la Figura.16. La idea clave de un planificador a mediano plazo es que en ocasiones puede

ser ventajoso eliminar procesos de la memoria (y reducir la contienda por el uso de la

UCP) y de este modo reducir el grado de multiprogramación. Más tarde el proceso sevolverá a introducir en la memoria y continuará su ejecución a partir del punto donde se

quedó. A este esquema comúnmente se le denomina intercambio (swapping). Elplanificador a mediano plazo intercambia el proceso, sacándolo y volviéndolo a introducir

más tarde. Los intercambios pueden ser necesarios para mejorar la mezcla de procesos,o porque un cambio en los requisitos de memoria ha comprometido en exceso la

memoria disponible, lo que requiere que se libere la memoria. Los intercambios se

analizan con mayor detalle en el capítulo de Administración de memoria.

Figura.16. Adición de la planificación a mediano plazo al diagrama de colas.

PLANIFICACIÓN DE LA UCP

La planificación es una función fundamental del sistema operativo. Casi todos los

recursos de un computador se planifican antes de usarse. Por supuesto, la UCP es unode los principales recursos del computador, de modo que su planificación es parte

medular del diseño de los sistemas operativos.



30


Ciclo de ráfagas de UCP y de E/S

El éxito de la planificación de la UCP depende de la siguiente propiedad observada de losprocesos: la ejecución de un proceso consiste en un ciclo de ejecución de la UCP y

espera de E/S, y los procesos se alternan entre estos dos estados. La ejecución delproceso se inicia con una ráfaga de UCP; a ésta le siguen una ráfaga de E/S, otra ráfaga

de UCP, una más de E/S, etc. Finalmente, la última ráfaga de UCP terminará con una solicitudal sistema para que concluya la ejecución, en vez de otra ráfaga de E/S (Figura.17). Las duraciones de estas ráfagas de UCP se han medido, y, aunque varían considerablemente de un proceso a otro y entre computadores, tienden a presentar una

curva de frecuencias similar a la que se muestra en la Generalmente la curva se

caracteriza como exponencial o hiperexponencial. Hay un gran número de ráfagas de

UCP de corta duración y un pequeño número de ráfagas de larga duración. Un programa

limitado por E/S normalmente tendrá muchas ráfagas de UCP breves, mientras que unprograma limitado por la UCP tendrá pocas ráfagas de muy larga duración. Esta

distribución puede ser muy importante al seleccionar un algoritmo adecuado para la

planificación de la UCP.

Figura.17. Secuencia alterna de ráfagas de UCP y E/S.



31


FiFigura.18. Histograma de tiempos de ráfaga de la UCP.

Planificador de la ucp

Siempre que la UCP queda inactiva, el sistema operativo debe seleccionar para su ejecución unode los procesos de la cola de procesos listos. El proceso de selección es realizado por elplanificador a corto plazo (o planificador de la UCP). El planificador selecciona uno de los procesosen memoria que están listos para ejecución y le asigna la UCP.Observe que la cola de procesos listos no es necesariamente una cola “primero que entra, primeroque sale” (Fifo, first-in, first-out). Como veremos cuando tratemos los distintos algoritmos deplanificación, una cola de procesos listos puede implantarse como una cola FIFO, una cola deprioridades, un árbol o simplemente como una lista ligada desordenada. Sin embargo,conceptualmente todos los procesos de la cola de procesos listos están en fila esperando unaoportunidad para ejecutarse en la UCP. Los registros de las 1as suelen ser los PCB de los

procesos.

Estructura de planificación

Las decisiones de planificación de la UCP pueden efectuarse en una de las cuatro circunstanciassiguientes:1. Cuando un proceso cambia del estado de ejecución a estado de espera (por ejemplo, solicitudde E/S, petición de esperar la terminación de uno de los procesos hijo).2. Cuando un proceso cambia del estado de ejecución al estado listo (por ejemplo, cuando ocurreuna interrupción).3. Cuando un proceso cambia del estado de espera al estado listo (por ejemplo, al completarse laE/S)4. Cuando termina un procesoPara los casos 1 y 4 no hay opción en términos de planificación: se debe seleccionar un nuevo

proceso para su ejecución (si existe en la cola de procesos listos). Sin embargo, esto no se aplicaa los casos 2 y 3.Cuando la planificación tiene lugar únicamente en las situaciones 1 y 4, decimos que el esquemade planificación es no apropiativo; de lo contrario decimos que es apropiativo. En la planificaciónno apropiativa, una vez que la UCP se ha asignado a un proceso, éste la conserva hasta que lalibera, ya sea por terminar o por cambiar al estado de espera.



32


Cambio de contexto

Para cambiar la UCP a otro proceso se requiere guardar el estado del proceso anterior y cargar elestado guardado para el nuevo proceso. Esta tarea se conoce como cambio de contexto. El tiempode cambio de contexto es un puro gasto adicional, y varía de una máquina a otra, dependiendo dela velocidad de la memoria, del número de registros y de la existencia de instrucciones especiales

(como una sola instrucción para cargar o almacenar todos los registros). Típicamente se encuentraen el intervalo de uno a cien microsegundos.Los tiempos de cambio de contexto dependen en gran medida del apoyo del hardware; por ejemplo,algunos procesadores ofrecen varios conjuntos de registros, y un cambio de contextoimplica únicamente cambiar el apuntador al conjunto actual de registros. Por supuesto, si hay másprocesos activos que conjuntos de registros, el sistema copia los datos usando la memoria, comose mencionó antes. Además, cuanto más complejo sea el sistema operativo, más trabajo hay querealizar durante un cambio de contexto. Como veremos en capítulos posteriores, las técnicasavanzadas de administración de memoria pueden requerir que con cada contexto se cambienotros datos adicionales.

Despachador

Otro componente que participa en la función de planificación de la UCP es el despachador. Eldespachador es el módulo que realmente entrega el control de la UCP al proceso seleccionadopor el planificador a corto plazo. Esta función implica:• Cambiar de contexto• Cambiar a modo usuario• Saltar a la posición adecuada del programa del usuario para reiniciar el programaObviamente, el despachador debe ser lo más rápido posible.

ALGORITMOS DE PLANIFICACIÓN

La planificación de la UCP tiene que ver con el problema de decidir a cuál de los procesos queestán en la cola de procesos listos se le asignará la UCP. Se cuenta con varios algoritmos deplanificación de la UCP, algunos de los cuales describiremos en esta sección.Los distintos algoritmos de planificación tienen propiedades diferentes y pueden favorecer a untipo de proceso en lugar de a otro, así que al elegir qué algoritmo se aplicará en una situacióndeterminada debemos considerar las propiedades de los diversos algoritmos.Para comparar los algoritmos de planificación de la UCP se han propuesto varios criterios, y lascaracterísticas que se utilicen para la comparación pueden representar diferencias considerablesen la determinación del mejor algoritmo; los criterios que se emplean incluyen los siguientes: Utilización de la UCP. Queremos que la UCP se mantenga tan ocupada como sea posible.

Su utilización puede variar del O al 100% y en un sistema real debe fluctuar entre el 40%(para un sistema con poca carga) y el 90% (para un sistema con gran carga de trabajo).

Productividad. Si la UCP se encuentra ocupada, se está efectuando algún trabajo. Unamedida del trabajo es el número de procesos que se completan por unidad de tiempo, llamadaproductividad. Para procesos largos, esta tasa puede ser un proceso por hora; paratransacciones más breves, la productividad puede ser de 10 procesos por segundo.

Tiempo de retorno. Desde el punto de vista de un proceso en particular, el criterio másimportante es cuánto tiempo tarda en ejecutarse ese proceso. El intervalo entre el momentode ofrecerlo hasta el momento en que termina es el tiempo de retorno, es decir, la suma delos periodos transcurridos esperando entrar en la memoria, esperando en la cola de procesoslistos, ejecutándose en la UCP y efectuando la E/S.

Tiempo de espera. El algoritmo para la planificación de la UCP no afecta realmente a lacantidad de tiempo durante el cual un proceso se ejecuta o lleva a cabo E/S. El algoritmoafecta únicamente a la cantidad de tiempo que el proceso espera en la cola de procesos



33


listos, de modo que en vez de tener en cuenta el tiempo de retorno, podemos considerar sóloel tiempo de espera para cada proceso.

Tiempo de respuesta. En un sistema interactivo, es posible que el tiempo de retorno no seael mejor criterio. Con frecuencia un proceso puede producir alguna salida en los primerosinstantes y continuar calculando nuevos resultados mientras se presentan al usuario los

resultados anteriores. Por esto, otra medición es el tiempo transcurrido desde la presentaciónde una solicitud hasta que se produce la primera respuesta. Esta medición, llamada tiempo derespuesta, es la cantidad de tiempo para comenzar a responder, pero no el tiempo necesariopara mostrar esa respuesta. El tiempo de retorno generalmente se encuentra limitado por lavelocidad del dispositivo de salida.

Es deseable maximizar la utilización de la UCP y la productividad, y minimizar los tiempos deretorno, de espera y de respuesta; en la mayoría de los casos optimizamos el promedio, pero enocasiones puede ser deseable optimizar los valores mínimos o máximos, en vez del promedio. Porejemplo, para garantizar que todos los usuarios obtengan un buen servicio podríamos minimizar elmáximo tiempo de respuesta.También se ha propuesto que, para sistemas interactivos (como los sistemas de tiempocompartido), es más importante minimizar la varianza en el tiempo de respuesta que minimizar supromedio. Un sistema con tiempo de respuesta razonable y predecible puede considerarse más

deseable que un sistema que en promedio sea más rápido, pero muy variable. Sin embargo, espoco lo que se ha hecho respecto a los algoritmos para la planificación de la UCP que minimicenla varianza.

A medida que analicemos los distintos algoritmos para la planificación de la UCP, ilustraremos sufuncionamiento. Una ilustración precisa podría incluir muchos procesos, y cada uno de ellos unasecuencia de centenares de ráfagas de UCP y de E/S. Para simplificar las ilustraciones, ennuestros ejemplos consideramos sólo una ráfaga de UCP (en milisegundos). Nuestra medida decomparación es el tiempo promedio de espera.

Planificación “servicio por orden de llegada”

Definitivamente, el algoritmo más sencillo para la planificación de la UCP es el algoritmo “serviciopor orden de llegada” (FCFS, first -come, first-served). Con este esquema, el proceso que primerosolicita la UCP es el primero al que se le asigna. La política FCFS se implanta fácilmente con una

cola FIFO: cuando un proceso entra en la cola de procesos listos, su PCB se enlaza al final de lacola; cuando la UCP está libre se asigna el proceso colocado al inicio de la cola de procesos listos,y entonces el proceso en ejecución se elimina de esa misma cola. El código para la planificaciónFCFS es sencillo de escribir y comprender.En la política FCFS el tiempo promedio de espera esbastante largo, sin embargo. Considere el siguiente conjunto de procesos que llegan en el instanteO, donde la duración de la ráfaga de uci se expresa en milisegundos:

Proceso Duración de la ráfaga P1 24 P2 3 P3 3

Si los procesos llegan en el orden P1, P2 y P3 y se les da servicio por orden de llegada,

obtenemos el resultado que se presenta en la siguiente gráfica de Gantt:

El tiempo de espera es 0 milisegundos para el proceso P1, 24 milisegundos para el proceso P2 y27 milisegundos para el proceso P3, de manera que el tiempo promedio de espera es (0 + 24 +



34


27)/3 = 17 milisegundos. Sin embargo, si los procesos llegan en el orden P2, P3 y P1, losresultados serán los que se muestran en la siguiente gráfica de Gantt:

El tiempo promedio de espera es ahora (6 + 0 + 3)/3 = 3 milisegundos, lo que representa unareducción considerable. Por esto, el tiempo promedio de espera en la política FCFS generalmenteno es mínimo y puede variar bastante si los tiempos de ráfagas de UCP de los procesos varíanmucho.

Además, considere el rendimiento de la planificación FCFS en una situación dinámica. Supongaque tenemos un proceso limitado por la UCP y varios procesos limitados por E/S. Al pasar losprocesos por el sistema, se puede presentar la siguiente situación: el proceso limitado por la UCPobtendrá la UCP y la retendrá; durante este tiempo, todos los demás procesos terminarán su E/S ypasarán a la cola de procesos listos, en espera de la UCP. Mientras esperan en la cola de procesoslistos, los dispositivos de E/S permanecen inactivos. Finalmente, el proceso limitado porla UCP termina su ráfaga de UCP y pasa a un dispositivo de E/S. Todos los procesos limitados porE/S, que tienen ráfagas de UCP breves, se ejecutan rápidamente y regresan a las colas dedispositivos de E/S. En este momento la UCP está inactiva. El proceso limitado por la UCP

regresará a la cola de procesos listos y se le asignará la UCP. Una vez más, los procesos limitadospor E/S se encuentran en la cola de procesos listos esperando a que termine el proceso limitadopor la UCP. Esto se conoce como efecto de convoy, ya que todos los demás procesosesperan a que un proceso de gran tamaño salga de la UCP. Este efecto provoca que la UCP y losdispositivos se aprovechen menos que si se permitiera que los procesos más cortos pasaran antes.El algoritmo de planificación FCFS es no apropiativo. Una vez que se ha asignado la UCP a unproceso, éste la conserva hasta que desee liberarla, ya sea por terminación o por solicitud de E/S.El algoritmo FCFS es especialmente problemático en los sistemas de tiempo compartido, dondees importante que cada usuario reciba una porción de la UCP a intervalos regulares. Seríadesastroso permitir que un proceso retuviera la UCP por un periodo largo.

Planificación “Primero el trabajo más breve”

Un enfoque distinto para la planificación de la UCP es el algoritmo “primero el trabajo más breve”

(SJF, shortest-job-first). (No empleamos el término primero el proceso más breve porque la mayoríade las personas y los textos se refieren a este tipo de disciplina de planificación como primero eltrabajo más breve.) Este algoritmo asocia a cada proceso la longitud de su siguiente ráfaga deUCP. Cuando la UCP está disponible, se le asigna al proceso que tiene la ráfaga siguiente de UCPmenor. Si dos procesos tienen la misma longitud para la siguiente ráfaga de UCP se utiliza laplanificación FCFS para romper el empate.Como ejemplo, considere el siguiente conjunto de procesos, donde la longitud de ráfaga de UCPse presenta en milisegundos:

Proceso Duración de la ráfaga P1 6 P2 8 P3 7 P4 3

Usando la planificación SJF, planificaríamos estos procesos de acuerdo con la siguiente gráfica deGantt:



35


El tiempo de espera es tres milisegundos para el proceso P1, 16 milisegundos para el proceso P2nueve milisegundos para P3 y 0 para P4. De esta manera, el tiempo promedio de espera es (3 +16 + 9 + 0)/4 = 7 milisegundos. Si usáramos la planificación FCFS, el tiempo promedio de esperasería de 10.25 milisegundos.

Puede comprobarse que el algoritmo SJF es Óptimo, ya que ofrece el mínimo

tiempo promedio de espera para un conjunto de procesos dado. La comprobaciónmuestra que poniendo un proceso breve antes de uno largo se reduce el tiempo de

espera del proceso corto más de lo que aumenta el tiempo de espera del proceso

largo

Figura ¡Error ! No hay texto con el estilo especificado en el documento..19). Por tanto,se reduce el tiempo de espera promedio.El problema real con el algoritmo SJF es conocer la longitud de la siguiente solicitud de la UCP.

Para la planificación a largo plazo de (trabajos) en un sistema por lotes, podemos utilizar el tiempolímite del proceso. De esta manera se motiva a los usuarios a estimar con precisión el tiempolímite del proceso, ya que un valor menor representa una respuesta más rápida. (Un valordemasiado bajo ocasionará un error de tipo “tiempo límite excedido” y se tendrá que ofrecer denuevo el proceso.) La planificación SJF se usa frecuentemente en la planificación de procesos.

Figura ¡Error! No hay texto con el estilo especificado en el documento..19.

Comprobación de que el algoritmo de planificación SJF es óptimo.

Aunque el algoritmo SJF es óptimo, no puede implantarse al nivel de la planificación a corto plazode la UCP. No hay manera de conocer la longitud de la siguiente ráfaga de UCP, pero se puedetratar de efectuar una aproximación a la planificación SJF. Aunque no conocemos la longitud de lasiguiente ráfaga de UCP, podemos predecir su valor, esperando que sea de longitud similar a lasanteriores. Así, al calcular una aproximación de la longitud de la siguiente ráfaga de UCP podemoselegir el proceso con la ráfaga de UCP prevista más breve.En general, la siguiente ráfaga de UCP se predice como un promedio exponencial de las longitudes

medidas de las ráfagas de UCP anteriores. Sea tn la longitud de la enésima ráfaga de UCP, y τn+1nuestro valor previsto para la siguiente ráfaga de UCP. Entonces, para α, 0<=α<=1, se define:

n1 t n 1 n



36


0

Esta fórmula define un promedio exponencial. El valor de tn contiene nuestra información másreciente, y τn contiene nuestros datos históricos. El parámetro α controla la ponderación de lahistoria reciente y antigua para nuestra predicción. Si α=O, entonces τn+1 = τn, y la historia recienteno tiene efecto (se supone que las condiciones actuales son transitorias); si α=1, entonces τn+1 = tny sólo tiene importancia la ráfaga de UCP más reciente (se supone que los datos históricos sonviejos e irrelevantes). Es más habitual que α = ½, por lo que la historia reciente y antigua se

ponderan de igual manera. LaFigura ¡Error! No hay texto con el estilo especificado en el documento..20 muestra un promedio exponencial para α = ½. El valor inicial de τ0 puede definirse como una constante o como un promedio global delsistema.Para comprender el comportamiento del promedio exponencial, podemos desarrollar la fórmulapara τn+1 sustituyéndolo por τn; para encontrar

n1 t n 1 t n1

1

j

t

n1

1

n1

Puesto que tanto α como (1 - α) son menores o iguales a 1, cada término sucesivo tiene menorpeso que su predecesor.

Figura 20 Predicción de la siguiente ráfaga de UCP utilizando un promedioexponencial.

El algoritmo SJF puede ser apropiativo o no apropiativo. La alternativa se plantea cuando un nuevoproceso llega a la cola de procesos listos mientras se está ejecutando otro proceso. El nuevoproceso puede tener una ráfaga de UCP menor que lo que resta del proceso que se ejecuta en esemomento. Un algoritmo SJF apropiativa desplazará al proceso que se ejecuta, mientras que unalgoritmo SJF no apropiativo permitirá que el proceso que se ejecuta termine su ráfaga de UCP. Laplanificación SJF apropiativa en ocasiones se denomina planificación “primero el que tenga elmenor tiempo restante” (shortest remaining-time-first).Como ejemplo, considere los cuatro procesos siguientes, donde la longitud de las ráfagas de UCPse proporciona en milisegundos:



37


Proceso Instante de llegada Duración de la ráfaga P1 0 8 P2 1 4



38


P3 2 9 P4 3 5

Si los procesos llegan a la cola de procesos listos en los tiempos mostrados y necesitan los tiemposde ráfaga indicados, entonces la planificación SJF apropiativa que resulta se muestra en la

siguiente gráfica de Gantt:

El proceso P1 comienza en el instante 0, ya que es el único proceso en la cola. El proceso P2 llegaen el instante 1. El tiempo restante para el proceso P1 (siete milisegundos) es mayor que el tiempoque requiere el proceso P2 (cuatro milisegundos), por lo que el proceso P1 se expulsa y el procesoP2 se planifica. El tiempo promedio de espera para este ejemplo es ((10 - 1) + (1 - 1) + (17 - 2) +(5 - 3))/4 = 26/4 = 6.5 milisegundos. El resultado de una planificación SJF no apropiativa sería 8.75milisegundos.

Planificación por prioridades

El algoritmo SJF es un caso especial del algoritmo general para la planificación por prioridades. Seasocia una prioridad a cada proceso y la UCP se asigna al de mayor prioridad. Los procesos conigual prioridad se planifican en orden FCFS.Un algoritmo SJF es sencillamente un algoritmo de prioridades, donde la prioridad ( p) es la inversade la siguiente ráfaga (prevista) de UCP (τ): p=1/τ. Si la ráfaga de UCP es mayor, la prioridad serámenor y viceversa.Observe que analizamos la planificación en términos de una alta prioridad y una baja prioridad. Lasprioridades generalmente corresponden a un intervalo fijo de números, como 0 a 7 o 0 a 4095. Sinembargo, no existe ningún consenso respecto a si 0 es la prioridad más alta o la más baja.

Algunos sistemas emplean números bajos para representar una prioridad baja; otros utilizannúmeros bajos para representar una prioridad alta. Esta diferencia puede prestarse a confusiones.

En este libro supondremos que los números bajos representan prioridades altas.Como ejemplo, considere el siguiente conjunto de procesos, que se supone llegaron en el instante0, en el orden P1, P2,..., P5 y cuyas longitudes de ráfaga de UCP se indican en milisegundos:

Proceso Duración de la ráfaga Prioridad P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2

Usando la planificación por prioridades, planificaríamos estos procesos de acuerdo con la

siguiente gráfica de Gantt:

El tiempo promedio de espera es de 6.2 milisegundos.



39


Las prioridades pueden definirse interna o externamente. Las prioridades definidas internamenteutilizan alguna cantidad o cantidades mensurables para calcular la prioridad del proceso. Porejemplo, para calcular prioridades se han utilizado los límites de tiempo, requisitos de memoria, elnúmero de archivos abiertos y la tasa de intervalos entre ráfagas de E/S y de UCP. Lasprioridades externas se fijan empleando criterios ajenos al sistema operativo, como la importanciadel proceso, el tipo y cantidad de fondos que se pagan por utilizar el computador, el departamento

que patrocina el trabajo y otros factores, con frecuencia de carácter político.La planificación por prioridades puede ser apropiativa o no apropiativa. Cuando un proceso llega ala cola de procesos listos, su prioridad se compara con la del proceso en ejecución. Un algoritmoapropiativo para la planificación por prioridades se apropiará de la UCP si la prioridad del procesorecién llegado es mayor que la del proceso en ejecución. Un algoritmo no apropiativo para laplanificación por prioridades únicamente dejará al nuevo proceso al inicio de la cola de procesoslistos.Un serio problema de los algoritmos para la planificación por prioridades es el bloqueo indefinido oinanición. Un proceso que está listo para ejecutarse pero no obtiene la UCP puede considerarsecomo bloqueado, en espera de la UCP. Un algoritmo para la planificación por prioridades puededejar a un proceso de baja prioridad esperando indefinidamente a la UCP. En un sistema decomputación con gran carga, un flujo constante de procesos de alta prioridad puede evitar que unproceso de baja prioridad obtenga la UCP. Por lo general sucederá una de estas dos cosas: o elprograma finalmente se ejecuta (a las 2 AM del domingo, cuando por fin disminuye la carga del

sistema) o el sistema de computación falla y pierde todos los procesos de baja prioridad. (Segúnalgunos rumores, cuando dieron de baja el computador IBM del MIT en 1973, encontraron unproceso de baja prioridad que se había enviado en 1967 y que todavía no se había ejecutado.)Una solución para el problema del bloqueo indefinido de los procesos de baja prioridad es elenvejecimiento, técnica por la cual aumenta gradualmente la prioridad de los procesos queesperan durante mucho tiempo en el sistema. Por ejemplo, si las prioridades varían entre 0 (baja)y 127 (alta), podríamos incrementar en uno la prioridad de un proceso en espera cada 15 minutos.Tarde o temprano, incluso un proceso con prioridad inicial 0 podría alcanzar la prioridad más altadel sistema y ejecutarse. De hecho, no costaría más de 32 horas que un proceso pasara deprioridad 0 a prioridad 127.

Planificación circular

El algoritmo de planificación circular (RR, round-robin) está diseñado especialmente para sistemas

de tiempo compartido. Se define una pequeña unidad de tiempo, llamada cuanto de tiempo oporción de tiempo, que generalmente varía entre 10 y 100 milisegundos. La cola de procesos listosse trata como una cola circular, el planificador de la UCP la recorre asignando la UCP a cadaproceso por un intervalo de hasta un cuanto de tiempo.Para poner en práctica la planificación mantenemos la cola de procesos listos como una cola“primero que entra, primero que sale” (FIF0). Los nuevos procesos se agregan al final de la colade procesos listos. El planificador de la UCP toma el primer proceso de la cola, programa uncronómetro para que interrumpa después de un cuanto de tiempo y despacha el proceso.Entonces sucederá una de estas dos cosas: el proceso puede tener una ráfaga de UCP menor queun cuanto de tiempo, en cuyo caso el proceso liberará voluntariamente a la UCP y elplanificador continuará con el siguiente proceso de la cola de procesos listos. Por otra parte, si laráfaga de UCP del pro ceso en ejecución es mayor que un cuanto de tiempo, el cronómetro seactivará y provocará una interrupción para el sistema operativo. Se ejecutará un cambio decontexto y el proceso se colocará al final de la cola de procesos listos. El planificador de la UCP

seleccionará entonces el siguiente proceso de la cola.Sin embargo, el tiempo promedio de espera es bastante grande en la política RR. Considere elsiguiente conjunto de procesos que llegan en el instante 0, donde la longitud de la ráfaga de UCPse expresa en milisegundos:

Proceso Duración de ráfaga P1 24 P2 3



40


P3 3

Si usamos un cuanto de tiempo de cuatro milisegundos, el proceso P1 obtiene los primeros cuatromilisegundos. Puesto que necesita otros 20 milisegundos, se expulsa tras el primer cuanto detiempo y la UCP se otorga a P2 el siguiente proceso de la cola. Como el proceso P2 no requierecuatro milisegundos, sale antes de que termine el cuanto de tiempo. Entonces se proporciona la

UCP al siguiente proceso, P3 Una vez que cada proceso ha recibido un cuanto de tiempo, sedevuelve la UCP al proceso P1 durante un cuanto de tiempo adicional. El resultado obtenido de laplanificación RR es:

El tiempo promedio de espera es 17/3 = 5.66 milisegundos.En el algoritmo de planificación RR, la UCP no se asigna a ningún proceso por más de un cuantoconsecutivo de tiempo. Si la ráfaga de UCP de un proceso excede de un cuanto, se expulsa yregresa a la cola de procesos listos. El algoritmo de planificación RR es apropiativo.

Si existen n procesos en la cola de procesos listos y el cuanto de tiempo es q, cada proceso recibe1/n de tiempo de la UCP en trozos de q unidades de tiempo como máximo. Ningún proceso debeesperar más de (n - 1) x q unidades de tiempo antes de recibir su siguiente cuanto. Por ejemplo, sihay cinco procesos, con un cuanto de tiempo de 20 milisegundos, entonces cada proceso recibiráhasta 20 milisegundos cada 100 milisegundos.El rendimiento del algoritmo RR depende en gran medida del tamaño del cuanto de tiempo. En unextremo, si el cuanto es muy grande (infinito), la política RR es la misma que la FCFS. Si el cuantode tiempo es muy pequeño digamos un microsegundo), el enfoque RR se llama compartir elprocesador, y para los usuarios parece (en teoría) que cada uno de los n procesos tiene su propioprocesador que se ejecuta a 1/n de la velocidad del procesador real. Este enfoque se utilizó en elcomputador de Control Data Corporation (CDC) para implantar 10 procesadores periféricos consólo un equipo de hardware y 10 conjuntos de registros. El hardware ejecuta una instrucción paraun conjunto de registros y luego pasa al siguiente. Este ciclo continúa, dando como resultado 10procesadores lentos en vez de uno rápido. (En realidad, como el procesador era mucho más

rápido que la memoria y cada instrucción hacia referencia a ella, los procesadores no eran muchomás lentos de lo que habría sido un solo procesador.)

Sin embargo, en el software tenemos que considerar el efecto del cambio decontexto en el rendimiento de la planificación RR. Supongamos quetenemos sólo un proceso de 10 unidades de tiempo. Si el cuanto de tiempoes de 12 unidades de tiempo, el proceso termina en menos de un cuanto, sintiempo de procesamiento adicional; pero si el cuanto de tiempo es de seisunidades, el proceso requiere 2 cuantos, produciendo un cambio decontexto. Si el cuanto de tiempo es una unidad, ocurrirán nueve cambios decontexto, lo que hará más lenta la ejecución del proceso

Figura ¡Error! No hay texto con el estilo especificado en el documento..21).



41


Figura ¡Error! No hay texto con el estilo especificado en el documento..21 Un cuanto de tiempomenor incrementa el número de cambios de contexto.

Por lo anterior, queremos que el cuanto de tiempo sea grande respecto al tiempo de cambio decontexto. Si el tiempo de cambio de contexto es aproximadamente 10% del cuanto, entonces en el

cambio de contexto se invierte cerca de un 10% del tiempo de la UCP.El tiempo de retorno también depende del tamaño del cuanto de tiempo.Como podemos ver en la

Figura ¡Error! No hay texto con el estilo especificado en el documento..22, el tiempo de retorno promedio de unconjunto de procesos no necesariamente mejora al aumentar el cuanto de tiempo. En general, eltiempo de retomo promedio puede mejorar si la mayoría de los procesos terminan su siguienteráfaga de UCP en un solo cuanto de tiempo. Por ejemplo, dados tres procesos de 10 unidades detiempo cada uno y un cuanto de tiempo de una unidad, el tiempo de retorno promedio es 29, perosi el cuanto es 10, el tiempo de retorno promedio se reduce a 20. Si se añade el tiempo de cambiode contexto, el tiempo de retorno promedio aumenta para un cuanto de tiempo más pequeño,puesto que se requieren más cambios de contexto.

Figura.22 El tiempo de retorno promedio varía con el cuanto de tiempo.

Por otra parte, si el cuanto de tiempo es demasiado grande, la planificación RR degenera hasta

convertirse en una política FCFS. Una regla empírica es que el 80% de las ráfagas de UCP debenser menores que el cuanto de tiempo.

Planificación de colas de múltiples niveles

Se ha creado otra clase de algoritmos de planificación para aquellas situaciones donde losprocesos se pueden clasificar fácilmente en distintos grupos. Por ejemplo, una división habitualconsiste en diferenciar los procesos de primer plano (interactivos) de los procesos de segundo



42


plano (por lotes). Estos dos tipos de procesos tienen requisitos de tiempo de respuesta bastantediferentes, por que pueden presentar distintas necesidades de planificación. Además, los procesosde primer plano pueden tener una prioridad superior (definida externamente) a la de los procesosde segundo plano.

Un algoritmo de planificación de colas de múltiples niveles divide la cola deprocesos listos en diversas colas

Figura ¡Error! No hay texto con el estilo especificado en el documento. .23). Los procesos se asignan en formapermanente a una cola, generalmente a partir de alguna propiedad del proceso, como puede ser eltamaño de la memoria o el tipo de proceso. Cada cola tiene su propio algoritmo de planificación;por ejemplo, pueden emplearse colas distintas para los procesos de primer y segundo planos. Lacola de primer plano puede planificarse con un algoritmo RR, mientras que la de segundo plano seplanifica con un algoritmo FCFS.Debe existir además una planificación entre las colas, la cual generalmente es una planificaciónapropiativa de prioridad fija. Por ejemplo, la cola de procesos de primer plano puede tener prioridadabsoluta sobre la cola de procesos de segundo plano.Veamos un ejemplo de algoritmo de planificación de colas de múltiples niveles con cinco colas:• Procesos del sistema• Procesos interactivos• Procesos interactivos de edición

• Procesos por lotes• Procesos de estudiantesCada cola tiene prioridad absoluta sobre las colas de menor prioridad. Por ejemplo, no podríaejecutarse ningún proceso de la cola de procesos por lotes a menos que las colas de procesos delsistema, procesos interactivos y procesos interactivos de edición estuvieran vacías. Si un procesointeractivo de edición entrara en la cola de procesos listos durante la ejecución de un proceso porlotes, este último se expulsaría.

Figura 23 Planificación de colas de múltiples niveles.



43


Otra posibilidad es utilizar una porción de tiempo para las colas. Cada cola recibiría cierta porcióndel tiempo de la UCP, la cual se planificaría entre los procesos de su cola. Por ejemplo, en el casode las colas de primer y segundo planos, la cola de primer plano puede recibir el 80% del tiempode la UCP para la planificación RR de sus procesos, mientras que la cola de segundo plano recibeel 20% de la UCP para distribuirlo entre sus procesos de manera FCFS.

Planificación de colas de múltiples niveles con realimentaciónEn un algoritmo para la planificación de colas de múltiples niveles normalmente los procesos seasignan de manera permanente a una cola al entrar al sistema y no se mueven a otras colas. Porejemplo, si hay colas diferentes para los procesos de primer y segundo planos, no cambian de unacola a otra, ya que los procesos no modifican su naturaleza de primer o segundo planos. Estaconfiguración tiene la ventaja de provocar poco gasto de procesamiento adicional durante laplanificación, pero es inflexible.Sin embargo, la planificación de colas de múltiples niveles con realimentación permite a un procesomoverse de una cola a otra. La idea es separar los procesos con diferentes características encuanto a ráfagas de la UCP. Si un proceso utiliza demasiado tiempo de la UCP, se pasará a unacola de menor prioridad. Este esquema deja a los procesos limitados por E/S y a los procesosinteractivos en las colas de mayor prioridad. De igual manera, si un proceso espera demasiadotiempo en una cola de menor prioridad se puede mover a una de mayor prioridad. Esta es una forma

de envejecimiento que evitaría el bloqueo indefinido.

Por ejemplo, considere un planificador de colas de múltiples niveles conrealimentación con tres colas, numeradas del 0 al 2 ( Figura ¡Error! No hay texto con el estilo especificado en el documento. .24). El planificador ejecutará primero todoslos procesos de la cola 0. Sólo cuando ésta se encuentre vacía, se ejecutarán los procesos de lacola 1. En forma similar, los procesos de la cola 2 sólo se ejecutarán si las colas 0 y 1 estánvacías. Un proceso que llegue a la cola 1 expulsará a un proceso de la cola 2. A su vez, unproceso de la cola 1 será expulsado por un proceso que llegue a la cola 0.

Figura 24 Colas de múltiples niveles con realimentación.

A los procesos que entran a la cola de procesos listos se les coloca en la cola 0, y se les asigna uncuanto de tiempo de ocho milisegundos. Si no terminan en este lapso, se mueven al final de lacola 1; si la cola 0 está vacía, se asigna un cuanto de tiempo de 16 milisegundos al proceso que



44


se encuentre al inicio de la cola 1. Si no termina, es expulsado y pasa a la cola 2. Los procesos deesta cola se ejecutan sobre una base FCFS, únicamente cuando estén vacías las colas 0 y 1.Este algoritmo de planificación da mayor prioridad a cualquier proceso con una ráfaga de UCP deocho milisegundos o menos. Este proceso recibirá rápidamente la UCP, terminará su ráfaga deUCP y pasará a su siguiente ráfaga de E/S. Los procesos que requieren más de ocho, pero menosde 24 milisegundos, también son atendidos con rapidez, aunque con menor prioridad que los

procesos más breves. Los procesos de larga duración descienden automáticamente a la cola 2 yson atendidos en orden de llegada utilizando cualquier ciclo de la UCP que no ocupe las colas 0 y1.Por lo general, un planificador de colas de múltiples niveles con realimentación se define con lossiguientes parámetros• El número de colas• El algoritmo de planificación para cada cola• El método utilizado para determinar cuándo promover un proceso a una cola de mayorprioridad• El método utilizado para determinar cuándo degradar un proceso a una cola de menor prioridad• El método utilizado para determinar a cuál cola entrará un proceso cuando necesite servicioLa definición de un planificador de colas de múltiples niveles con realimentación lo convierte en elalgoritmo de planificación de la UCP más general. Se puede configurar para ajustarse a unsistema específico que se esté diseñando, pero por desgracia también requiere alguna forma de

selección de valores para todos los parámetros que definan el mejor planificador. Aunque las colasde múltiples niveles con realimentación son el esquema más general, también son el máscomplejo.

PLANIFICACIÓN DE PROCESADORES MÚLTIPL ES

Hasta ahora nuestro análisis se ha centrado en los problemas de la planificación de la UCP en unsistema con un solo procesador. Si hay múltiples UCP, el problema de planificación se vuelve máscomplejo. Se han probado varias posibilidades y, como hemos visto en la planificación de la UCPcon un solo procesador, no hay una solución única que sea la mejor. A continuación analizaremosbrevemente algunos de los asuntos relacionados con la planificación de procesadores múltiples.Uno de los factores principales es el tipo de procesadores que entran en juego, los cuales puedenser idénticos (un sistema homogéneo) o distintos (un sistema heterogéneo). Si los procesadoresson diferentes, las opciones son relativamente limitadas. Cada procesador tiene su propia cola y

su propio algoritmo de planificación. Los procesos están tipificados intrínsecamente por suestructura, y deben ejecutarse en un procesador determinado; un programa escrito en lenguajeensamblador VAX no puede ejecutarse en un IBM Series/1; hay que ejecutarlo en un VAX. Así, losprocesos se restringen a ciertos procesadores y cada procesador puede planificarse a sí mismo.Si hay varios procesadores idénticos, pueden compartir cargas. Sería posible proporcionar unacola distinta a cada procesador, pero en esta situación un procesador podría estar inactivo, conuna cola vacía, mientras los demás procesadores estuvieran muy activos. Para evitarlo utilizamosuna cola común de procesos listos; todos los procesos entran a esta cola y se planifican encualquier procesador disponible.Con este esquema puede emplearse una de dos estrategias d planificación. En una de ellas, cadaprocesador se planifica a sí mismo. Cada procesador examina la cola común de procesos listos yselecciona un proceso para ejecución. Si tenemos varios procesadores que tratan de acceder auna estructura de datos común y actualizarla, hay que programar con cuidado cada procesador.Debemos asegurar que dos procesadores no elijan el mismo proceso, y que no se pierdan procesos

de la cola. La otra estrategia evita este problema estableciendo un procesador como planificadorpara los demás, creando así una estructura amo-esclavo, esto es, el multiprocesamiento asimétrico.



45


El objetivo de la multiprogramación en los Sistemas Operativos, es que en todomomento se ejecute un proceso para maximizar la utilización de la UCP (UnidadCentral de Proceso); por lo tanto, se debe utilizar algún algoritmo que nos permitaplanificar la UCP.

El lector utiliza los algoritmos de planificación de la UCP.

Deitel M. Introducción a los Sistemas Operativos. España: Addison Wesley

Iberoamericana, Segunda Edición; 1998.

Silberschatz A, Peterson J, Galvin P. Sistemas Operativos. Usa: Editorial Addison Wesley Iberoamericana, 3ra Edición; 1994.

Tanenbaum A. Sistemas Operativos Modernos. Mexico: Pearson Educación,Segunda Edición; 2003.

La siguiente unidad académica analiza el procesamiento concurrente para un sistema

operativo.

Realice una prueba de escritorio a los algoritmos de planificación.




Resuelva los siguientes problemas:PROBLEMA UNO

Considere el siguiente conjunto de procesos, cuyas longitudes de ráfaga de UCP se expresan enmilisegundos:Proceso Duración de

la ráfagaPrioridad

P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2

Se supone que los procesos llegaron en el orden P1, P2, P3, P4, P5 todos en el instante 0.a) Dibuje cuatro gráficas de Gantt que ilustren la ejecución de estos procesos utilizando laplanificación FCFS, SJF, una prioridad no apropiativa (un menor número de prioridad representa

una prioridad mayor) y RR (cuanto = 1).b) ¿Cuál es el tiempo de retomo de cada proceso para cada uno de los algoritmos de planificacióndel apartado a)?c) ¿Cuál es el tiempo de espera de cada proceso para cada uno de los algoritmos de planificacióndel apartado a)?d) ¿Cuál de los esquemas de planificación del apartado a) ofrece el menor tiempo promedio deespera (para todos los procesos)?

PROBLEMA DOS Suponga que los procesos siguientes llegan para su ejecución en los momentos indicados. Cadaproceso se ejecutará en el tiempo indicado. Al responder a estas preguntas, utilice la planificaciónno apropiativa y base todas sus decisiones en la información que tenga en el momento de tomar ladecisión.

Proceso Instante dellegada

Duración dela ráfaga

P1 0.0 8P2 0.4 4P3 1.0 1

a) ¿Cuál es el tiempo de retorno promedio para estos procesos con el algoritmo de planificaciónFCFS?b) ¿Cuál es el tiempo de retorno promedio para estos procesos con el algoritmo de planificaciónSJF?c) Supuestamente, el algoritmo de planificación SJF mejora el rendimiento, pero observe quedecidimos ejecutar el proceso P1 en el instante 0 porque no sabíamos que pronto llegarían dosprocesos más breves. Calcule cuál sería el tiempo de retorno total promedio si la UCP estuviera

inactiva durante la primera unidad de tiempo y luego se aplicara la planificación SJF. Recuerde quelos procesos P1 y P2 están en espera durante este periodo de inactividad, por lo que puedeaumentar su tiempo de espera. A este algoritmo se le podría conocer como planificación conconocimiento del futuro.

Documents

Libro Sistemas Operativos-cap 2