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.