9

Lic. I. Vedia

Lic.C. Mollinedo

Unidad II

Actualmente las computadoras pueden realizar varias tareas al mismo tiempo.

Es decir, mientras ejecuta el programa de un usuario, una computadora puede

asimismo estar leyendo un disco e imprimiendo en una impresora.

En un sistema de multiprogramación, la unidad central de procesamiento

(CPU) ejecuta varios procesos a la vez, ejecutando cada uno de los procesos en

decenas o cientos de milisegundos (aunque realmente la CPU ejecuta en cierto

instante un solo proceso).

En cualquier instante de tiempo la CPU está ejecutando solo un programa, por

eso en el curso de un segundo puede trabajar en varios programas, con lo que

se da al usuario la ilusión de paralelismo. Algunas veces las personas hablan de pseudo paralelismo para referirse a estos cambios que la CPU realiza entre programas, a fin de compararlo con el

verdadero paralelismo del hardware de la operación de esta unidad mientras

corren uno o más dispositivos de entrada o salida.

2.1 CONCEPTO

Uno de los conceptos más importantes que gira en torno a un sistema operativo

es el de proceso. Este concepto surgió por primera vez con la

multiprogramación, donde se puede ejecutar más de un programa

simultáneamente con el fin de aprovechar al máximo los recursos de la

computadora.

Un proceso es un programa en ejecución junto con el entorno

asociado (registros, variables, etc.) o más específicamente

como una unidad de procesamiento ejecutada por el sistema

operativo.

10

Lic. I. Vedia

Lic.C. Mollinedo

Para que un programa pueda ser ejecutado debe residir con sus datos en

memoria principal. Durante su ejecución el proceso va modificando los registros

del modelo de programación de la computadora de acuerdo a las instrucciones

de máquina involucrados. El SO mantiene por cada proceso una serie de

estructuras de información que permiten identificar las características de éste,

así como los recursos que tiene asignados.

El corazón de un sistema operativo es el núcleo, un programa de control que

reacciona ante cualquier interrupción de eventos externos y que da servicio a

los procesos, creándolos, terminándolos y respondiendo a cualquier petición de

servicio por parte de los mismos.

2.2 MODELO DE PROCESOS

• Todo el software ejecutable, inclusive el Sistema Operativo, se organiza

en varios procesos secuenciales o procesos.

• Un proceso incluye al programa en ejecución y a los valores activos del

contador, registros y variables del mismo.

• Conceptualmente cada proceso tiene su propia CPU virtual.

• Si la CPU alterna entre los procesos, la velocidad a la que ejecuta un

proceso no será uniforme, por lo que es necesario aclarar lo siguiente:

� Que los procesos no deben programarse con hipótesis implícitas

acerca del tiempo.

� Que normalmente la mayoría de los procesos no son afectados por

la multiprogramación subyacente de la CPU o las velocidades

relativas de procesos distintos.

• Un proceso es una actividad de un cierto tipo, que tiene un programa,

entrada, salida y estado.

• Un solo procesador puede ser compartido entre varios procesos con cierto

“algoritmo de planificación”, el cual determina cuándo detener el trabajo

en un proceso y dar servicio a otro distinto.

11

Lic. I. Vedia

Lic.C. Mollinedo

En este modelo todo el software ejecutable inclusive el sistema operativo se

organiza en varios procesos secuenciales.

En este modelo la CPU alterna los procesos; es decir el conjunto de procesos en

ejecución, la CPU alterna entre un proceso y otro rápidamente, a esta forma de

alternar se denomina multiprogramación.

La diferencia entre un programa (conjunto de instrucciones) y un

proceso (instrucciones ejecutándose) es obvio, pero crucial para

entender el funcionamiento de los sistemas operativos. Hacemos

hincapié en que un programa por si solo no es un proceso; un

programa es una entidad pasiva, como contenido de un archivo

guardado en disco, mientras que un proceso es una entidad activa,

con el contador de programa especificando la siguiente instrucción

que se ejecutará y un conjunto de recursos asociados.

2.2.1 CREACION DE PROCESOS

Los cuatro principales sucesos que provocan la creación de nuevos procesos son: 1. La inicialización del sistema

2. La ejecución por parte de un proceso (en ejecución) de una llamada al

sistema de creación de un nuevo proceso.

3. La petición por parte del usuario de la creación de un nuevo proceso.

4. El inicio de un trabajo en batch.

Cuando un sistema operativo arranca, se crean típicamente varios procesos.

Adicionalmente a los procesos creados en el momento del arranque, también

pueden crearse nuevos procesos después

12

Lic. I. Vedia

Lic.C. Mollinedo

2.2.2 TERMINACIÓN DE LOS PROCESOS

Tras la creación de un proceso comienza su ejecución realizando el

trabajo que se le ha encomendado. Sin embargo nada dura para siempre, ni

siquiera los procesos. Pronto o tarde el nuevo proceso debe terminar,

usualmente debido a una de las siguientes causas:

1. El proceso completa su trabajo y termina (voluntariamente).

2. El proceso detecta un error y termina (voluntariamente).

3. El sistema detecta un error fatal del proceso y fuerza su terminación.

4. Otro proceso fuerza la terminación del proceso (por ejemplo en UNIX

mediante la llamada al sistema kill).

La mayoría de los procesos terminan debido a que han completado su

trabajo.

2.2.3 JERARQUIA DE PROCESOS En cuanto a las jerarquías de procesos es necesario señalar que los Sistemas

Operativos deben disponer de una forma de crear y destruir procesos cuando se

requiera durante la operación, teniendo además presente que los procesos

pueden generar procesos hijos mediante llamadas al Sistema Operativo,

pudiendo darse ejecución en paralelo.

La secuencia de creación de procesos genera un árbol de procesos, como el de la

siguiente figura:

13

Lic. I. Vedia

Lic.C. Mollinedo

Para referirse a las relaciones entre los procesos de la jerarquía se emplean los

términos de padre, hijo, hermano o abuelo. Cuando el proceso A solicita al

sistema que cree el proceso B, se dice que A es padre de B y que B es hijo de A.

Bajo ésta óptica la jerarquía de procesos puede considerarse como un árbol

genealógico.

2.2.2 ENTORNO DE PROCESOS

El entorno de procesos consiste en un conjunto de variables que se le pasan al

proceso en el momento de su creación. El entorno está formado por una tabla

NOMBRE-VALOR que se incluye en la pila del proceso. El NOMBRE especifica

el nombre de la variable y el VALOR su valor.

En el grafico anterior por ejemplo; PATH indica la lista de directorios en los

que el sistema operativo busca los programas ejecutables, TERM el tipo de

terminal, HOME el directorio inicial asociado al usuario y PWD el directorio de

trabajo actual.

2.2.3 GRUPOS DE PROCESOS

Los procesos forman grupos qu tienen diversas propiedades. El conjunto de

procesos creados a partir de un Shell puede formar un grupo de procesos.

Entonces se abre la posibilidad de realizar operaciones sobre todos los procesos

de un determinado grupo

2.3 MULTITAREA

Un SO monotarea también llamado monoproceso, solamente permite que

exista un proceso en cada instante. Si se quieren ejecutar varios procesos o

tareas hay que lanzar la ejecución de la primera y esperar a que termine

antes de poder lanzar la siguiente. El ejemplo típico del SO monoproceso es

el MSDOS.

Por el contrario un SO multitarea o multiproceso permite que coexistan

varios procesos activos a la vez. El SO se encarga de ir repartiendo el tiempo

del procesador entre estos procesos, para que todos ellos vayan avanzando

en su ejecución.

Un sistema monousuario está previsto para dar soporte a un solo

usuario. Estos sistemas pueden ser monoproceso o multiproceso. En este

último caso el usuario puede solicitar varias tareas al mismo tiempo.

14

Lic. I. Vedia

Lic.C. Mollinedo

Un SO multiusuario da soporte a varios usuarios que trabajan

simultáneamente desde varios terminales. A su vez, cada usuario puede

tener activos más de un proceso, por lo que el sistema obligatoriamente ha

de ser multitarea. Los sistemas multiusuario reciben también el nombre

de tiempo compartido.

La multitarea se basa en las tres siguientes características:

• Paralelismo real entre E/S y procesador

• Alternancia en los procesos de fases de E/S y de procesamiento

• Memoria principal capaz de almacenar varios procesos.

2.4 ESTADO DE LOS PROCESOS

Los estados de los procesos son internos del sistema operativo y transparentes

al usuario. Para éste, su proceso estará siempre en ejecución

independientemente del estado en que se encuentre internamente en el

sistema.

Un proceso puede tomar básicamente tres estados:

1. Ejecución. Estado en el que se encuentra un proceso cuando tiene el control del procesador, es decir, utiliza la CPU en el instante dado.

2. Preparado o Listo. Aquellos procesos que están dispuestos para ser ejecutados, pero no están en ejecución por alguna causa (interrupción,

haber entrado en la estando otro proceso en ejecución, etc.).

3. Bloqueado. Son los procesos que no pueden ejecutarse de momento

por necesitar algún recurso no disponible (generalmente recursos de

entrada/salida).

15

Lic. I. Vedia

Lic.C. Mollinedo

Desde un punto de vista lógico, los dos primeros estados son similares. En

ambos casos el proceso está dispuesto a ejecutarse, sólo que en el segundo caso

temporalmente no existe ninguna CPU disponible para él. El tercer estado es

diferente de los dos primeros ya que el proceso no puede ejecutarse, ni siquiera

en el caso de que la CPU no tuviera ninguna otra cosa que hacer.

Esta perspectiva el nivel inferior del sistema operativo es el planificador, con

una variedad de procesos por encima de él. Todo el manejo de las

interrupciones y los detalles de cómo arrancar y detener los procesos quedan

ocultos bajo lo que hemos denominado aquí el planificador de procesos, el cual

no representa realmente demasiado código. El resto del sistema operativo está

bonitamente estructurado en forma de múltiples procesos. Sin embargo son

pocos los sistemas operativos reales que están tan estructurados como este.

2.5 TRANSICIONES ENTRE LOS PROCESOS

Todo proceso a lo largo de su existencia puede cambiar de estado varias

veces. Cada uno de estos cambios se denomina transición de estados.

Existen cuatro transiciones entre los estados de un proceso.

1. El proceso se bloquea en espera de datos. 2. El planificador elige otro proceso. 3. El planificador elige este proceso. 4. Los datos están disponibles.

La transición 1 ocurre cuando un proceso descubre que no puede

continuar, ya sea por falta de datos, en este caso el proceso realiza una llamada

al sistema Block para pasar al estado bloqueado.

16

Lic. I. Vedia

Lic.C. Mollinedo

La transición 2 ocurre cuando el planificador de procesos decide que el

proceso en ejecución ya cumplió su tiempo asignado.

La transición 3 ocurre cuando los demás procesos ha tenido su parte y es

tiempo de que el primer proceso vuelva a ejecutarse.

La transición 4 ocurre cuando el evento externo por el que espera un

proceso; por ejemplo la llegada de nuevos datos ya se encuentra disponible.

2.5 IMPLEMENTACION DE PROCESOS

2.5.1 EL BLOQUE DE CONTROL DE PROCESOS (PCB)

Para implantar el modelo de procesos el sistema operativo utiliza una

tabla llamada “tabla de procesos” o “Bloque de Control de Procesos”. El PCB

contiene información relativa: al estado del proceso, asignación de memoria,

estado de los archivos abiertos, información de contabilidad y planificación. Por

tanto, el sistema operativo por cada proceso mantiene su identificación e

información relacionada con sus características propias.

En general, la información contenida en el bloque de control es la

siguiente:

• Estado del Proceso: En Ejecución, Bloqueado o Listo.

• Contador del Programa: dirección de la siguiente instrucción a ser

ejecutada por el proceso.

• Registros de la CPU.

• Información de Planificación de la CPU: prioridad del proceso,

apuntadores a las colas de planificación y otros parámetros de

planificación.

• Información de Administración de Memoria: registros límites y

tablas de páginas.

• Información Contable: cantidad de tiempo real y de la CPU

utilizado, límites de tiempo, números de cuenta y números de

proceso o trabajo.

• Información del Estado de la E-S: solicitudes de E-S

pendientes, dispositivos de E-S (como discos o unidades de

cinta) asignados al proceso y una lista de archivos abiertos.

Algunos de los campos de una entrada típica de la tabla de procesos.

17

Lic. I. Vedia

Lic.C. Mollinedo

2.7 COMUNICACIÓN ENTRE PROCESOS

Frecuentemente los procesos requieren una comunicación entre ellos IPC (Inter Process Comunication)., por ejemplo: en un entubamiento donde la salida del

primer proceso debe transferir al segundo, y este al tercero y así

sucesivamente. Existe la comunicación entre procesos de preferencia en una

forma estructurada sin utilizar interrupciones.

Muy brevemente, hay tres cuestiones:

• Cómo puede un proceso pasar información a otro.

• Asegurar que dos o más procesos no se interfieran mientras realizan

tareas críticas (pensemos en dos procesos que intentan apoderarse del

último megabyte de memoria disponible).

• Secuenciamiento correcto cuando existen dependencias: (P.ej. si el

proceso A produce datos que el proceso B imprime, B tiene que esperar

hasta que A produzca algún dato antes de comenzar a imprimir)

2.7.1 CONDICIONES DE CARRERA O COMPETENCIA

La condición de carrera ocurre cuando dos o más procesos

accesan a un recurso compartido sin control, de manera que el

resultado combinado de este acceso depende del orden de

llegada.

18

Lic. I. Vedia

Lic.C. Mollinedo

En algunos sistemas operativos los procesos que trabajan juntos

comparten con frecuencia un espacio común para almacenamiento, en el que

cada uno puede leer o escribir dentro del espacio compartido; este puede

encontrarse en la memoria principal o ser un archivo compartido.

Las condiciones de competencia se manifiestan cuando dos o mas

procesos leen o escriben en ciertos datos compartidos y el resultado final

depende de quien ejecuta y en que momento. Por ejemplo cuando dos procesos

desean tener aaceso a la memoria compartida al mismo tiempo, el proceso B

comienza a utilizar una de las variables compartidas, antes que el proceso A

termine con ella.

La clave para evitar problemas de condiciones de competencia y

situaciones relacionadas con la memoria compartida, archivo compartidos y

cualquier otra cosa compartida, es determinar una forma de prohibir que más

de algún proceso lea o escriba en los datos compartidos a la vez.

2.7.2 SECCIÓN CRÍTICA ¿Cómo podemos evitar las condiciones de carrera? Aquí y en muchas otras

situaciones donde se comparte memoria, ficheros, o cualquier otra cosa, la clave

19

Lic. I. Vedia

Lic.C. Mollinedo

para evitar problemas es encontrar alguna forma de impedir que más de un

proceso lea y escriba sobre el dato compartido al mismo tiempo. Dicho en otras

palabras, lo que necesitamos es exclusión mútua, esto es alguna manera de

asegurar que si un proceso está utilizando una variable compartida (o fichero

compartido) los demás procesos estarán excluidos de hacer uso de esa misma

variable.

Se denomina sección critica a todas aquellas áreas compartidas,

como memoria compartida, archivos compartidos y cualquier

otra cosa compartida, es decir, existe sección crítica donde hay

un recurso compartido.

2.7.3 EXCLUSIÓN MUTUA Es un mecanismo que permite que una secuencia de instrucciones, donde

participan variables compartidos, sean ejecutados por un solo proceso sin ser

alterados por las actividades de otros procesos. Dicho de otra manera, la

exclusión mutua asegura de que si un proceso está utilizando una variable o

archivo compartido, es que los otros procesos no puedan hacer lo mismo.

Para tener una solución adecuada al problema de la Exclusión mutua se

necesitan que cumplan cuatro condiciones:

1. Nunca dos procesos pueden encontrase simultáneamente dentro de

sus secciones criticas.

2. No se hacen suposiciones acerca de las velocidades relativas de los procesos o del número de CPU.

3. Ningún proceso suspendido fuera de la sección critica debe bloquear a otros procesos.

4. Nunca un proceso debe querer entrar en forma arbitraria en su

sección critica.

Existen varios métodos para lograr la exclusión mutua, entre ellas tenemos:

a) La exclusión mutua con espera ocupada Entre estos podemos destacar a:

• Desactivación de interrupciones

• Variables de cerradura

• Alternancia estricta

• Solución de Peterson

• La instrucción TSL.

20

Lic. I. Vedia

Lic.C. Mollinedo

En esencia todos estos métodos lo que hacen dar solución a lo siguiente:

Cuando un proceso desea entrar a su región critica verifica la entrada. Si no

el proceso se queda esperando hasta obtener el permiso. Este punto de vista

no solo desprecia el punto de vista de la CPU, sino que también tiene efectos

inesperados.

b) Sleep (bloqueo) y wakeup (desbloqueo)

El bloqueo y desbloqueo son primitivas de comunicación entre procesos que

bloquean a la CPU, en vez de desperdiciar su tiempo cuando no se le

permite entrar a su secciones criticas, como ejemplo de usos de estas

primitiva tenemos:

• El problema del productor y consumidor

• Semáforos

• Solución al problema del consumidor mediante Contadores de evento

• Monitores

• Transferencia de mensajes

2.8. PLANIFICACIÓN El mecanismo más común que poseen los sistemas operativos actuales para

realizar la gestión del procesador se conoce con el nombre de planificación, cuyo

objetivo principal es el de dar un buen servicio a todos los procesos que existan

en un momento dado en el sistema.

La planificación del procesador que es una parte del sistema operativo, es el

que decide que proceso conviene ejecutar primero, es decir, se refiere a la

manera de decidir cuánto tiempo de ejecución y cuando se le asignan a cada

proceso del sistema. Obviamente, si el sistema es monousuario y monotarea no

hay mucho que decidir, pero en el resto de los sistemas esto es crucial para el

buen funcionamiento del sistema.

2.8.1. Niveles de planificación

En los sistemas de planificación generalmente se identifican tres niveles: el

alto, el medio y el bajo.

• El nivel alto decide que trabajos (conjunto de procesos) son candidatos a convertirse en procesos compitiendo por los recursos del sistema.

21

Lic. I. Vedia

Lic.C. Mollinedo

• El nivel intermedio decide que procesos se suspenden o reanudan para lograr ciertas metas de rendimiento.

• El nivel bajo es el que decide que proceso, de los que ya están listos (y que en algún momento pasó por los otros dos planificadores) es al que le

toca ahora estar ejecutándose en la unidad central de procesamiento.

En adelante se revisaran principalmente los planificadores de bajo nivel porque

son los que finalmente eligen al proceso en ejecución.

2.8.2. Objetivos de la planificación

Las políticas de planificación intentan cubrir los siguientes objetivos:

• Justicia o Imparcialidad: Todos los procesos son tratados de la misma

forma, asegurando que cada proceso tenga la parte que le corresponde de la

CPU, obteniéndose así su turno de ejecución o intervalos de tiempo de

ejecución hasta su terminación exitosa.

• Maximizar la Producción: El sistema debe de finalizar el mayor numero

de procesos en por unidad de tiempo.

• Minimizar el Tiempo de Respuesta: Cada usuario o proceso debe observar que el sistema les responde consistentemente a sus

requerimientos.

• Evitar el aplazamiento indefinido: Los procesos deben terminar en un

plazo finito de tiempo.

• El sistema debe ser predecible: Ante cargas de trabajo ligeras el sistema

debe responder rápido y con cargas pesadas debe ir degradándose

paulatinamente. Otro punto de vista de esto es que si se ejecuta el mismo

proceso en cargas similares de todo el sistema, la respuesta en todos los

casos debe ser similar.

2.8.3. Criterios de planificación

Los criterios que se deben tener en cuenta a la hora de elegir o diseñar un

algoritmo de planificación son los siguientes:

• Tiempo de respuesta. Velocidad con que el ordenador da respuesta a

una petición. Depende mucho de la velocidad de los dispositivos de

entrada/salida.

22

Lic. I. Vedia

Lic.C. Mollinedo

• Tiempo de servicio. Es el tiempo que tarda en ejecutarse un proceso,

donde se incluye el tiempo de carga del programa en memoria, el tiempo

de espera en la cola de procesos listos; el tiempo de ejecución en el

procesador y el tiempo consumido en operaciones de E/S.

• Tiempo de ejecución. Es idéntico al tiempo de servicio menos el

tiempo de espera en la cola de procesos preparados; es decir, es el tiempo

teórico que necesitaría el procesos para ser ejecutado si fuera el único

presente en el sistema.

• Tiempo de procesador. Es el tiempo que un proceso está utilizando el

procesador si contar el tiempo que se encuentra bloqueado por

operaciones de E/S.

• Tiempo de espera. Es el tiempo en que los procesos están activos pero

sin ser ejecutados, es decir, los tiempos de espera en las distintas colas.

• Eficiencia. Se refiere a la utilización del recurso más caro en un

sistema, el procesador, que debe estar el mayor tiempo posible ocupado

para lograr así un gran rendimiento, es decir, mantener la CPU ocupada

100% del tiempo.

• Rendimiento. Es el número de trabajos o procesos realizados por

unidad de tiempo, que debe ser lo mayor posible.

2.8.4 Medidas Para estudiar el comportamiento de las distintas políticas de planificación,

definiremos dos medidas relacionadas entre sí que nos indiquen como estamos

tratando un proceso concreto.

Consideremos :

Tiempo de servicio (T): T = tf - ti

Tiempo de espera (E): E = T – t t: El tiempo que un proceso P necesita estar en ejecución para llevar a

cabo su trabajo.

ti : Instante en que el usuario da la orden de ejecución del proceso.

tf : Instante en que el proceso termina su ejecución.

2.8.5 Políticas de planificación Las políticas de planificación se agrupan en:

23

Lic. I. Vedia

Lic.C. Mollinedo

Planificación apropiativa

Son las que producen un cambio de proceso con cada cambio de contexto;

es decir, el proceso que esta haciendo uso del procesador puede ser

temporalmente suspendido y permitir que otro proceso se apropie del

procesador.

Planificación no apropiativa Son aquellas en las que un proceso no abandona nunca el procesador

desde su comienzo hasta su fin.

En una planificación no apropiativa, un trabajo muy grande aplaza mucho a uno pequeño, y si entra un proceso de alta prioridad esté también debe

esperar a que termine el proceso actual en ejecución.

2.9 ALGORITMOS DE PLANIFICACIÓN

2.9.1 Primero en llegar, primero en ser servido (FCFS) En esta política de planificación FCFS (First Come, First Served), el

procesador ejecuta cada proceso hasta que termina; por tanto, los procesos que

entran en cola de procesos preparados permanecerán encolados en el orden en

que lleguen hasta que les toque su ejecución. Este método se conoce también

como “primero en entrar, primero en salir” (First Input, First Output - FIFO).

Cola de preparados

Fin de la

E D C B A � Procesador �

ejecución

Nombre Instante Tiempo Instante Proceso Llegada ejecución Finalizació

n T E

A 0 3 3 3 0

B 1 5 8 7 2

C 4 2 10 6 4

D 5 6 46 11 5

E 8 4 20 12 8

24

Lic. I. Vedia

Lic.C. Mollinedo

Media 7.8 3.8

E

D

C

B

A

A B C D E 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Las características de esta política son las siguientes:

- No es apropiativa.

- Es justa, aunque los procesos largos hacen esperar mucho a los cortos.

- Es una política predecible.

- El tiempo medio de servicio es muy variable en función del número de

procesos y su duración.

2.9.2 El siguiente proceso, el más corto (SJN) El método SJN (Shortest Job Next) es una política de planificación no

apropiativa que trata de cubrir los mismos objetivos que la RR.

Esta política toma de la cola de procesos preparados el que necesite menos

tiempo de ejecución para realizar su trabajo. Para ello debe saber el tiempo de

procesador que necesita cada proceso, lo cual es tarea nada fácil, pero posible a

través de diversos métodos como puede ser la información suministrada por el

propio usuario o por el propio programa.

El tiempo de servicio T en esta política es bueno para los procesos cortos,

saliendo perjudicado los procesos largos.

E

D

25

Lic. I. Vedia

Lic.C. Mollinedo

C

B

A

A B C E D 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Nombre Instante Tiempo Instante Proceso llegada ejecución Finalizació

n T E

A 0 3 3 3 0

B 1 5 8 7 2

C 4 2 10 6 4

D 5 6 20 15 9

E 8 4 14 6 2

Media 7.4 3.4

Las características de esta política de planificación son las siguientes:

- No es apropiativa.

- El tiempo se espera aumenta de acuerdo con la longitud de los

procesos, pero el tiempo medio de espera con respecto a otras políticas

es óptimo.

- Es poco predecible.

- No es justa con los procesos largos.

- Buen tiempo de servicio.

2.9.3 Próximo proceso, el de tiempo restante más corto (SRT)

26

Lic. I. Vedia

Lic.C. Mollinedo

La política SRT (shortest Remaining Time) es una mezcla de los dos métodos

anteriores y trata de obtener las ventajas de ambos. Para ello esta técnica

cambia el proceso que esta en ejecución cuando se ejecuta un proceso (paso del

planificador de largo plazo al de corto plazo), Con una exigencia de tiempo de

ejecución total menor que el que está ejecutando en el procesador. El valor del

tiempo de respuesta medio de los procesos largos mejora con respecto a SJN.

El tiempo de Espera E es bastante corto para la mayoria de los procesos. SRT

consigue una buena eficiencia, ya que logra que la lista de procesos preparados

sea lo ma´s corta posible.

E

D

C

B

A

A B C B E D 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Nombre Instante Tiempo Instante Proceso Llegada ejecución Finalizació

n T E

A 0 3 3 3 0

B 1 5 10 9 4

C 4 2 6 2 0

D 5 6 20 15 9

E 8 4 14 6 2

Media 7 3

Esta política presenta las siguientes características:

- Es una variante de SJN, para hacerla apropiativa.

- Puede ser injusta, ya que un proceso corto puede echar a uno largo

que esté haciendo uso del procesador y que además esté terminado.

27

Lic. I. Vedia

Lic.C. Mollinedo

- Presenta una mayor sobrecarga.

- Excelente tiempo medio de servicio.

- Es muy eficiente.

2.9.4 Prioridad En esta política se asocia a cada proceso una prioridad, de manera que el

procesador se asigna al proceso de mayor prioridad.

Las prioridades pueden ser definidas interna o externamente. En el primer

caso, el sistema operativo se basa en una serie de informaciones medibles para

el cálculo y asignación de dichas prioridades (tiempo necesitado de procesador,

necesidad de memoria, etc.)

El principal problema de esta política es el bloqueo o postergación indefinida,

ya que un proceso de baja prioridad puede estar esperando su turno

indefinidamente. Para evitarlo se suele emplear lo que se denomina

envejecimiento de las prioridades, que aumenta gradualmente las prioridades

de los procesos que están a la espera de utilizar el procesador.

Cualquier algoritmo basado en esta política puede ser apropiativo o no

apropiativo. En el primer caso, un proceso puede ser retirado del procesador si

aparece otro de mayor prioridad en la cola de procesos preparados.

Nombre Instante Tiempo Prioridad Instante Proceso llegada ejecución Finalizació

n T E

A 0 3 0 18 18 15

B 1 5 1 12 11 6

C 4 2 0 20 16 14

D 5 6 2 11 6 0

E 8 4 1 16 8 4

Media 11.8 7.8

E

D

C

B

A

28

Lic. I. Vedia

Lic.C. Mollinedo

A B D B E A C 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2.9.5 Planificación a Tres Niveles

Desde una cierta perspectiva, los sistemas en batch permiten planificar a tres

niveles diferentes, como se ilustra en la Figura Tan pronto como llegan los

trabajos al sistema, se los coloca en un primer momento en una cola de entrada

residente en el disco. El planificador de admisión decide qué trabajos se admiten en el sistema. Los demás trabajos se quedan en la cola de entrada

hasta que sean seleccionados. Un algoritmo típico de control de la admisión

puede tener como objetivo obtener una mezcla adecuada de trabajos intensivos

en CPU y trabajos intensivos en E/S. De forma alternativa, el objetivo puede

ser que los trabajos cortos puedan ser admitidos rápidamente mientras que los

largos tengan que esperar. El planificador de admisión es libre para dejar

algunos trabajos en la cola de entrada y admitir otros que llegan después, a su

criterio.

Para optimizar el rendimiento del sistema en conjunto, el planificador

de memoria debe decidir cuidadosamente cuantos procesos desea que

residan en memoria, lo que se denomina el grado de

multiprogramación, y qué tipo de procesos

29

Lic. I. Vedia

Lic.C. Mollinedo

Para tomar sus decisiones, el planificador de memoria inspecciona periódicamente cada

proceso en el disco para decidir si lo carga o no en memoria. Entre los criterios que puede

utilizar para tomar esa decisión están los siguientes:

1. ¿Cuánto tiempo ha pasado desde que el proceso se intercambió al disco?

2. ¿Cuánto tiempo de CPU ha tenido el proceso recientemente?

3. ¿Qué grande es el proceso? (Los procesos pequeños no son problema)

4. ¿Cuán importante es el proceso?

El tercer nivel de planificación consiste realmente en escoger uno de los procesos

preparados que hay en memoria para ejecutarlo a continuación. A menudo se le

denomina el planificador de la CPU y es aquél en el que piensa toda la gente cuando se

habla del “planificador”. Aquí puede utilizarse cualquier algoritmo apropiado, bien

expulsor o no expulsor.

2.9.7 Planificación en Sistemas Interactivos

Vamos a ver ahora algunos algoritmos que pueden utilizarse en los sistemas interactivos.

Todos ellos pueden utilizarse también como planificadores de la CPU en sistemas en

batch. Mientras que la planificación a tres niveles no es posible aquí, sí que es posible e

incluso común una planificación a dos niveles (planificador de memoria y planificador de

la CPU).

A continuación vamos a concentrarnos en el planificador de la CPU.

Planificación Round-Robin

A cada proceso se le asigna un intervalo de tiempo, denominado su quantum (o también

rodaja de CPU), durante el que se le permite ejecutarse. Si el proceso sigue ejecutándose

todavía al final del quantum, se le expulsa de la CPU, concediéndose la CPU a algún otro

proceso. Si el proceso se bloquea (o termina) antes de que transcurra el quantum se

realiza por supuesto la conmutación de la CPU.

30

Lic. I. Vedia

Lic.C. Mollinedo

Supongamos que esta conmutación de proceso o cambio de contexto, como se denomina

a veces, requiere 1 milisegundo, incluyendo la conmutación de los mapas de memoria, el

vaciado y la recarga de la memoria caché, etc. Supongamos también que el quantum se ha

establecido en 4 milisegundos. Con estos parámetros, después de hacer trabajo útil

durante 4 milisegundos, la CPU debe gastar 1 milisegundo en la conmutación del proceso.

Planificación por Prioridades

La necesidad de tener en cuenta factores externos conduce a la planificación por

prioridades. La idea básica es trivial: a cada proceso se le asigna una prioridad, y siempre

es el proceso ejecutable con mayor prioridad al que se le permite ejecutarse. Incluso en

un PC con un único propietario, puede haber múltiples procesos, algunos más importantes

que otros. Para impedir que los procesos de mayor prioridad se ejecuten de manera

indefinida, e planificador podría hacer decrecer la prioridad del proceso que se está

ejecutando en cada tic del reloj (es decir, en cada interrupción de reloj). Si esta acción

provoca que la prioridad descienda por debajo de la del siguiente proceso de mayor

prioridad, tendrá lugar un cambio de proceso.

Alternativamente, se podría asignar a cada proceso un quantum de tiempo máximo

durante el cual puede ejecutarse. Una vez consumido ese quantum, el proceso con la

siguiente prioridad más alta tendrá la oportunidad de ejecutarse. Las prioridades pueden

asignarse a los procesos de forma estática o dinámica.

Un algoritmo sencillo para dar un buen servicio a los procesos intensivos en E/S consiste

en asignarles como prioridad el valor 1/f, donde f es la fracción del último quantum que

utilizó un proceso. Un proceso que utilizó sólo 1 milisegundo de su quantum de 50

milisegundos obtendría una prioridad de 50, mientras que uno que se ejecutó durante 25

milisegundos antes de bloquearse obtendría una prioridad de 2. Un proceso que consumió

todo su quantum obtendría una prioridad de 1.