U2 Administración de Procesos y del procesador.pptx.pdf

Presentación de la Unidad dos de la materia de Sistemas Operativos en el Tecnológico de Tepic por el docente Efraín Padilla Valera

1. Unidad Dos : Administración de procesos y
del procesador
Ing. Efraín Padilla Valera

Sistemas Operativos 1

Departamento de Sistemas y Computación

2. Instituto
Tecnológico
Tepic
Contenido
Concepto de proceso.1
Estados y transiciones de los procesos2
Procesos ligeros (Hilos o hebras)3
Técnicas de administración del planificador6
Concurrencia y secuenciabilidad.4
Niveles, objetivos y criterios de planificación5

3. Instituto
Tecnológico
Tepic
Introducción.
❖Todos los sistemas operativos de multiprogramación, desde los
sistemas monousuario, como Windows NT, hasta los sistemas de
grandes computadores, como MVS, que puede dar soporte a miles de
usuarios, están construidos en torno al concepto de proceso

▪El sistema operativo debe intercalar la ejecución de un conjunto de
procesos para maximizar la utilización del procesador ofreciendo a la vez
un tiempo de respuesta razonable.
▪El sistema operativo debe asignar los recursos a los procesos en
conformidad con una política especifica (por ejemplo, ciertas funciones o
aplicaciones son de prioridad más alta), evitando, al mismo tiempo, el
interbloqueo.
▪El sistema operativo podría tener que dar soporte a la comunicación entre
procesos y la creación de procesos por parte del usuario, labores que
pueden ser de ayuda en la estructuración de las aplicaciones.

4. Instituto
Tecnológico
Tepic
Concepto de proceso.
❖Un sistema operativo es muy complejo en cuanto a su funcionalidad
▪Concepto de proceso es fundamental para modularizar y
estructurar el sistema operativo, que por su naturaleza es
dinámico.
❖Un sistema operativo ejecuta una variedad de programas:
▪Sistemas por lote – trabajos
▪Sistemas de tiempo compartido – programas de usuario o tareas

❖Proceso – un programa en ejecución; la ejecución del proceso avanza
de manera secuencial

❖Un proceso es una entidad activa, que puede solicitar recursos
(archivos, dispositivos, etc.)

5. Instituto
Tecnológico
Tepic
Características de un Proceso
❖Los servicios superiores del SO se estructuran en base a
procesos

❖Permite modularizar y aislar fallas de programas durante
su ejecución

❖Soporta concurrencia de actividades, lo que permite un
mejor aprovechamiento de los recursos

❖Denominaremos como procesos a los trabajos (jobs) en
sistemas de lotes, como a las tareas en sistemas de tiempo
compartido.

6. Instituto
Tecnológico
Tepic
Abstracción de Proceso
❖El proceso es una abstracción creada por el SO, que se
compone de:
▪La ejecución de un proceso se realiza en forma secuencial en su
propia CPU.
▪Programa: Código y datos del programa cargado en memoria
principal
▪Contexto de Ejecución: PC, registros del procesador, un stack para
invocación de procedimientos Y sección de datos.

7. Instituto
Tecnológico
Tepic
Proceso en memoria

8. Instituto
Tecnológico
Tepic
Estados de un Proceso
❖ Nuevo: El proceso está siendo creado.
❖ Ejecutándose: Proceso ejecuta instrucciones de
máquina.
❖ Listo: El proceso está listo para recibir el
procesador para iniciar o continuar su ejecución.
❖ Esperar: El proceso deja de competir por el
procesador, esperando un evento externo (e.g. E/S,
sincronización con otro proceso, una señal, etc.)
❖ Terminado: El proceso ha terminado su
ejecución

9. Instituto
Tecnológico
Tepic
Estados y Transiciones de un Proceso

10. Instituto
Tecnológico
Tepic
Transiciones de un Proceso
❖Admitir: Proceso entra a competir por recursos
❖Despachar: Planificador elige de cola listo el próximo
proceso, cargando el procesador con su contexto.
❖Expropiar: Interrupción del temporizador(timeout), por
fin de cuanto de tiempo, guardándose el estado del
proceso.
❖Despertar: Proceso vuelve a competir por el procesador al
ocurrir el evento esperado.
❖Salir: El proceso termina su ejecución(normalmente o con
error).

11. Instituto
Tecnológico
Tepic
Tabla de Procesos
❖El sistema administra los procesos a través
de una tabla que contiene para cada proceso
existente en el sistema un descriptor.
▪Este descriptor se denomina Bloque de
Control de Proceso (PCB).
❖ La tabla es una estructura de datos
localizada en el núcleo del sistema.

12. Instituto
Tecnológico
Tepic
Bloque de Control de Proceso (PCB)
❖Identificación del Proceso (número único: PID)
❖Estado del Proceso (Ejecutándose, listo, esperando, etc.)
❖Contador de programa (Próxima instrucción)
❖Registros de trabajo (para guardar los registros)
❖Planificación de CPU (prioridades, punteros a colas de
planificación y otros parámetros)
❖Administración de Memoria (registros base y límite,
tablas de página o segmento, etc.)
❖Contabilidad (CPU usada, límites de tiempo, # cuenta,
etc.)
❖ Estado de recursos (Lista de recursos asignados y
estado)

13. Instituto
Tecnológico
Tepic
Cambio de Contexto
❖Corresponde a la reasignación del procesador de un
proceso a otro, donde se requiere cambiar el contexto de
ejecución.
❖ El cambio de contexto no corresponde a trabajo
productivo, sino que es burocracia (overhead).
❖ Tiempos típicos van de 1 a 1000 [μseg].

14. Instituto
Tecnológico
Tepic
Una primera clasificación de procesos
❖Procesos Sistema:
▪No asignados a ninguna terminal
▪Creados en la inicialización del sistema
❖Procesos Usuarios:
▪Lanzados por un usuario desde una terminal
determinada.
❖Procesos tipo threads (hilos)
▪ocupan el mismo espacio de memoria

15. Instituto
Tecnológico
Tepic
Otra clasificación de procesos
❖Otra forma de clasificar los procesos es de
acuerdo:
▪al uso y la forma en que haya construido el
código ejecutable
▪según la capacidad de acceso al procesador y a
los recursos
▪según la forma de ejecución

16. Instituto
Tecnológico
Tepic
Tipos procesos de acuerdo al uso y forma código ejecutable
❖Reutilizables:
▪son aquellos en los que pueden cambiar los
datos, pero necesitan comenzar desde el
principio.
❖Reentrantes:
▪sólo contienen código puro. Los datos se
encuentran en registros internos y no pueden
ser modificados (programas compartidos por
varios usuarios)

17. Instituto
Tecnológico
Tepic
Tipos procesos de acuerdo a su capacidad acceso al
procesador y recursos
❖Apropiativos
▪no permiten compartir recursos, hasta que hayan
acabado.
❖No apropiativos
▪permiten a otros procesos el uso de un recurso que
estén ultilizando.

18. Instituto
Tecnológico
Tepic
Tipos procesos de acuerdo a su forma de ejecución
❖Residentes
▪permanecen en memoria mientras se ejecutan
❖Intercambiables
▪pueden ser llevados al disco mientras estén
bloqueados

19. Instituto
Tecnológico
Tepic
Planificación de Procesos
❖Objetivos de la Planificación de Procesos:
▪Multiprogramación: Tener siempre un proceso ejecutándose con el
propósito mejorar utilización CPU y otros recursos.
▪Tiempo Compartido: Cambiar rápidamente la CPU entre procesos para
mantener buena interactividad.

❖ No pueden existir más procesos en ejecución que el número de
procesadores
▪Sistemas de multiprocesamiento permiten tener más de un proceso en
ejecución.

❖Entre los objetivos que se suelen perseguir están los siguientes:
▪Reparto equitativo del procesador.
▪Eficiencia (optimizar el uso del procesador).
▪Menor tiempo de respuesta en uso interactivo.
▪Menor tiempo de espera en lotes (batch).
▪Mayor número de trabajos por unidad de tiempo (batch).
▪Cumplir los plazos de ejecución de un sistema de tiempo real.

20. Instituto
Tecnológico
Tepic
Colas de planificación de procesos
❖Para realizar las funciones de planificación, el sistema operativo
organiza los procesos listos en una serie de estructuras de información
que faciliten la búsqueda del proceso a planificar. Es muy frecuente
organizar los procesos en colas de prioridad y de tipo

❖Cola de trabajos – conjunto de todos los procesos en el
sistema

❖Cola de listos – conjunto de procesos que residen en
memoria principal, listos y en espera de ser ejecutados

❖Colas de dispositivos – conjunto de procesos esperando
por un dispositivo de E/S

❖Los procesos migran entre las distintas colas

21. Instituto
Tecnológico
Tepic
Cola listos y varias de dispositivos E/S
.las colas de procesos se construyen con unas cabeceras y con unos punteros que
están incluidos en los PCB. Dado que un proceso está en cada instante en una
sola cola de planificación, es necesario incluir un solo espacio de puntero en su
PCB

22. Instituto
Tecnológico
Tepic
Modelo de Colas

23. Instituto
Tecnológico
Tepic
Planificadores (schedulers)

24. Instituto
Tecnológico
Tepic
Planificador de Largo Plazo
❖Actúa con poca frecuencia (normalmente cuando termina
un proceso), creando un proceso y cargándolo en la
memoria.

❖Controla el grado de multiprogramación.

❖ Determina una buena mezcla de procesos de uso intensivo
de CPU y de E/S.

❖Algunos sistemas no tienen este planificador (e.g. Sistemas
de tiempo compartido).

25. Instituto
Tecnológico
Tepic
Planificador de Corto Plazo
❖Decide a qué proceso asignarle la CPU, el cual es
seleccionado de la cola listo.
❖Se ejecuta con alta frecuencia, cada vez que un
proceso abandona la CPU:
▪salida del proceso (exit)
▪timeout (expira su ranura de tiempo)
▪solicitud de E/S o espera por un evento
❖Asegura la interactividad en un sistema

26. Instituto
Tecnológico
Tepic
Planificador de Mediano Plazo
❖Permite regular la carga reduciendo o aumentando el
grado de multiprogramación, usando técnica de
swapping.

❖Un factor de decisión importante es la demanda por
memoria de los procesos.

❖Se usa en sistemas de tiempo compartido

27. Instituto
Tecnológico
Tepic
Operaciones con Procesos
❖Procesos pueden ser creados y destruidos
dinámicamente, i.e. Se requieren operaciones
para:
▪Creación de proceso
▪Destrucción de proceso
❖ Otras operaciones importantes son:
▪Comunicación entre procesos
▪Manejo de hilos
▪Control de la ejecución de los procesos
▪Según el SO, existen múltiple alternativa de realizar
estas operaciones.
id est Expresión latina que significa "esto es" y que, escrita abreviadamente, "i. e.", se emplea a veces en escritos
científicos o doctrinales.

28. Instituto
Tecnológico
Tepic
Creación de Procesos
❖Formación de jerarquías de procesos (relación
padre-hijo)
▪ En Unix se forma un árbol a partir de proceso INIT
❖ Respecto a los recursos:
▪Hijos pueden heredar los recursos (compartir), o
▪Reciben nuevos recursos
❖ Al crearse un hijo, puede suceder
▪Hijo se ejecuta concurrentemente con el padre
▪Padre espera que el hijo termine

29. Instituto
Tecnológico
Tepic
Árbol de procesos típico en Solaris

30. Instituto
Tecnológico
Tepic
Jerarquía procesos
❖Unix
▪Cuando un proceso crea otro proceso, el proceso padre y
el proceso hijo continúan asociados.
▪El proceso hijo puede crear otro proceso, formando una
jerarquía de procesos
▪Un proceso y todos sus hijos forman un grupo de
procesos.
❖Windows
▪No cuenta con una jerarquía de procesos
▪Todos los procesos son iguales
▪Cuando proceso es creado, al padre se le otorga un
token especial (handle) que puede usar para controlar
al proceso hijo
•Sin embargo el proceso es libre de pasar este token a otro
proceso.

31. Instituto
Tecnológico
Tepic
Creación de proceso en POSIX

32. Instituto
Tecnológico
Tepic
Creación de proceso en Win32

33. Instituto
Tecnológico
Tepic
Creación de proceso en Java

34. Instituto
Tecnológico
Tepic
Término del Proceso
❖Suicidio: Se autoelimina
▪Invocación explícita, normal o anormal (i.e.
exit en Unix).
▪Se deben liberan recursos del proceso.
❖ Asesinato: Otro proceso lo elimina
▪Normalmente lo hace un antepasado directo
(más seguro).
▪Eliminación puede ser normal o anormal
▪Término de un proceso puede significar el
término de toda su descendencia (i.e. Unix:
shutdown y shell).

35. Instituto
Tecnológico
Tepic
Procesos Cooperativos
❖Un proceso es independiente si este no es afectado por otro proceso
que se esta ejecutando en el sistema o también cuando no comparte
datos con otro proceso es independiente.

❖Procesos cooperativos
▪Son aquellos que comparten datos
▪Hay varias razones para que se de un ambiente que permita la
cooperación entre procesos ejemplos:
•Compartición de información (e.g. archivos)
•Aceleración de la computación (ejecución paralela)
•Modularidad (cuando se construye el sistema en un modo modular
dividiendo las funciones del sistema en procesos separados o hilos)
•Conveniencia (cuando un usuario requieren realizar varias tareas
simultáneas un usuario editando, imprimiendo y compilando en
paralelo)
❖ Cooperación requiere de mecanismos de comunicación entre
procesos (IPC) y la sincronización entre procesos

36. Instituto
Tecnológico
Tepic
Comunicación entre procesos(IPC)
❖Hay 2 modelos fundamentales de IPC

Paso de Mensajes Memoria compartida

37. Instituto
Tecnológico
Tepic
Ejemplo de Cooperación:
Problema Productor-Consumidor
❖Paradigma para procesos cooperativos, proceso productor
genera información para un proceso consumidor
•Ejemplo: un compilador puede producir codigo ensamblador el cual es
consumido por un ensamblador. El ensamblador en turno puede producir
objectos de modulo los cuales son consumidos por el cargador.
•Se puede ver este problema como una metafora para el paradigma
cliente-servidor: Ejemplo un servidor web produce (proporciona) archivos e
imagenes en HTML y son consumidos por el navegador (cliente web) que solicito
el recurso
▪Con buffer no-acotado no impone un límite práctico para el
tamaño del buffer
▪Con buffer acotado asume que existe un buffer de tamaño fijo

38. Instituto
Tecnológico
Tepic
Simulando memoria compartida en Java

39. Instituto
Tecnológico
Tepic
❖Solución buffer acotado – memoria compartida
Simulando memoria compartida en Java

40. Instituto
Tecnológico
Tepic
❖Solución buffer acotado – memoria compartida

Simulando memoria compartida en Java

41. Instituto
Tecnológico
Tepic
Simulando memoria compartida en Java
❖Buffer acotado -- Figure 3.16 – método insert()

42. Instituto
Tecnológico
Tepic
Simulando memoria compartida en Java
❖Buffer acotado – Figure 3.17 – método remove()

43. Instituto
Tecnológico
Tepic
Paso de mensajes
❖Sistema de paso de mensajes – los procesos se comunican entre ellos
sin recurrir a variables compartidas
❖La infraestructura de paso de mensajes ofrece dos operaciones:
▪send(mensaje) – tamaño del mensaje fijo o variable
▪receive(mensaje)
❖Si P y Q quieren comunicarse, deben:
▪Establecer una liga de comunicación entre ellos
▪Intercambiar mensajes via send/receive
❖Implementación de liga de comunicación
▪Física (v.gr., memoria compartida, bus en hardware o red)
▪Lógica (v.gr., propiedades lógicas)
•Comunicación directa o indirecta
• Comunicación simétrica o asimétrica
• Sincronización (con o sin bloqueo)
• Bufferring automático o explícito

44. Instituto
Tecnológico
Tepic
Preguntas de implementación
❖¿Cómo se establecen las ligas?
❖¿Puede asociarse una liga con más de dos
procesos?
❖¿Cuántas ligas pueden existir entre cada par de de
procesos comunicados?
❖¿Cuál es la capacidad de la liga?
❖¿El tamaño de un mensaje que puede manejar la
liga es fijo o variable?
❖¿Las ligas son unidireccionales o bidireccionales?

45. Instituto
Tecnológico
Tepic
Nombramiento (Naming)
❖Comunicación directa
▪Los procesos deben mencionarse mutuamente de manera explícita:
•send (P, mensaje) – envia mensaje al procesos P
•receive(Q, mensaje) – recibe un mensaje del proceso Q
▪Propiedades de la liga de comunicación
•Las ligas se establecen de manera automática
•Una liga está asociada con exactamente un par de procesos
comunicados
•Entre cada par existe exactamente una liga
•La liga puede ser unidirección o bidireccional
▪Hay 2 esquemas
•Simétrica: receptor identifica al emisor
• Asimétrica: receptor no conoce a priori al emisor

46. Instituto
Tecnológico
Tepic
Nombramiento (Naming)
❖Comunicación indirecta
▪Los mensajes son dirigidos y recibidos a/de buzones (también
conocidos como puertos)
•Cada buzón tiene un id único
•Los procesos pueden comunicarse sólo si comparten un buzón
▪Propiedades de la liga de comunicación
•Liga establecida sólo si los procesos comparten un buzón
•Una liga puede asociarse con muchos procesos
•Cada par de procesos puede compartir muchas ligas de
comunicación
•La liga puede ser unidirección o bidireccional

47. Instituto
Tecnológico
Tepic
Nombramiento (Naming)
❖Comunicación indirecta
▪Operaciones
•Crear un buzón
•Enviar y recibir mensajes a través de un buzón
•Destruír un buzón
▪Las primitivas estás definidas así:
send(A, mensaje) – enviar mensaje a buzón A
receive(A, mensaje) – recibir mensaje del buzón A

48. Instituto
Tecnológico
Tepic
Nombramiento (Naming)
❖Comunicación indirecta
▪Compartir buzones
•P
1
, P
2
, y P
3
comparten un buzón A
•P
1
, envía; P
2
y P
3
reciben
•¿Quién obtiene el mensaje?
▪Soluciones
•Permitir la asociación de ligas con a lo más dos procesos
•Permitir a lo más a un proceso ejecutar la operación de recibir
•Permitir al sistema seleccionar de manera arbitraria al receptor.
Se da aviso al remitente quién fue el receptor.

49. Instituto
Tecnológico
Tepic
Sincronización en la Comunicación
❖Paso de mensajes puede o no utilizar bloqueo
❖Bloqueo se considera síncrono
▪Envío con bloqueo mantiene al remitente bloqueado hasta
que el mensaje es recibido
▪Recepción con bloqueo mantiene al receptor bloqueado
hasta que un mensaje está disponible
❖Sin bloqueo es considerado asíncrono
▪Envío sin bloqueo permite al remitente enviar el mensaje y
continuar
▪Recepción sin bloqueo permite al receptor recibir un mensaje
válido o null

50. Instituto
Tecnológico
Tepic
Buffering
❖Cola de mensajes asociada a la liga; se
implementa en una de tres formas
1.Capacidad cero – 0 mensajes
Remitente espera por un receptor
2.Capacidad limitada – longitud finita de n
mensajes. Remitente debe esperar si la liga está
llena
3.Capacidad ilimitada – longitud infinita
Remitente nunca espera

51. Instituto
Tecnológico
Tepic
Solución paso de mensajes – buffer limitado

52. Instituto
Tecnológico
Tepic
Solución paso de mensajes – buffer limitado

53. Instituto
Tecnológico
Tepic
Solución paso de mensajes – buffer acotado
El productor

54. Instituto
Tecnológico
Tepic
Solución paso de mensajes – buffer acotado
El consumidor

55. Instituto
Tecnológico
Tepic
Paso de mensajes en Windows XP

56. Instituto
Tecnológico
Tepic
Comunicación Cliente-Servidor
❖Sockets

❖Llamadas a procedimientos remotos (RPC)

❖Invocación de métodos remotos (RMI)
(Java)

57. Instituto
Tecnológico
Tepic
Sockets
❖Un socket se define como el punto
final de una comunicación
❖Concatenación de una dirección IP y
puerto
❖El socket 161.25.19.8:1625 hace
referencia al puerto 1625 en el host
161.25.19.8
❖La comunicación se da entre un par de
sockets

58. Instituto
Tecnológico
Tepic
Comunicación con Socket

59. Instituto
Tecnológico
Tepic
Comunicación con sockets en Java

60. Instituto
Tecnológico
Tepic
Comunicación con sockets en Java

61. Instituto
Tecnológico
Tepic
Llamada a procedimientos remotos
❖Llamada a procedimientos remotos (RPC) es
una abstracción para llamar procedimientos
entre procesos en un sistema en red.
❖Stubs – proxy del lado del cliente en lugar
del procedimiento real en el servidor.
❖El stub en el lado del cliente localiza el
servidor y marshalls (procesa) los
parámetros.
❖El stub en el lado del servidor recibe el
mensaje, desempaqueta los parámetros
(unmarshalling) y ejecuta el procedimiento
en el servidor.

62. Instituto
Tecnológico
Tepic
Máquina
Cliente
Máquina
Servidor
kerne
l
kerne
l
stub
del
cliente
stub
del
servido
r
client
e
call
retur
n
Pack
parámetr
os
Unpack
resultad
o
Unpack
parámetr
os
Pack
resultad
o
servido
r
call
retur
n
Mensaje transportado en la
red
Principio funcionamiento del
RPC

63. Instituto
Tecnológico
Tepic
Invocación de Métodos Remotos
❖RMI es un mecanismo de Java similar a
RPC.
❖RMI permite que un programa en Java
en una máquina invoque un método
en un objeto remoto.

64. Instituto
Tecnológico
Tepic
Marshalling de parámetros

65. Instituto
Tecnológico
Tepic
Ejemplo de RMI
La interfaz RemoteDate define el protocolo que el objeto remoto debe
implementar se define como sigue:

66. Instituto
Tecnológico
Tepic
Ejemplo de RMI
Como una instancia de esta clase debe accesarse remotamente, esta debe
extender de la clase UnicastRemoteObject del paquete java.rmi.server e
implementar la interfaz RemoteDateImpl.
Registra un nombre
y un lugar de un
objeto remoto. Esto
se realiza a partir de
un servidor que
contiene un objeto
remoto
Naming.rebind(“rmi://host/name”,object);
El primero es el lugar donde se encuentra el objeto y segundo es el objeto que se llama remotamente
Ademas la aplicación rmiregistry debe estar ejecutándose en la misma maquina servidor que la aplicación
servidor que contiene el objeto remoto

67. Instituto
Tecnológico
Tepic
Ejemplo de RMI
La aplicación cliente se liga al objeto remoto mediante el método lookup(), que
retorna un objeto que permite el acceso via un stub al objeto remoto

68. Instituto
Tecnológico
Tepic
Planificación de CPU
❖Conceptos básicos
❖Criterios de planificación
❖Algoritmos de planificación
❖Planificación multi-procesador
❖Planificación de tiempo real
❖Planificación con hilos de control
❖Ejemplos de sistemas operativos
❖Planificación en hilos de Java
❖Evaluación de algoritmos

69. Instituto
Tecnológico
Tepic
Definiciones Básicas
❖Recurso: Objeto que puede ser utilizado por un proceso.

❖Asignación: Un recurso está asignado a un proceso si éste
dispone de un conjunto de operadores para su uso.

❖Administrador: Asigna, recupera y, eventualmente,
expropia un recurso a un proceso.

❖Expropiación: Cuando el administrador puede reasignar
un recurso antes que un proceso lo libere voluntariamente.

70. Instituto
Tecnológico
Tepic
Ejemplos de Recursos
❖Procesador. Se asigna a los procesos. El administrador dispone de dos
procedimientos o componentes: el despachador y el
planificador.

❖Memoria Principal. Puede ser con asignación explícita o implícita
(e.g. memoria virtual)

❖Memoria Secundaria. Se asigna en grupos de bloques de tamaño fijo.
Asignación puede ser explícita o implícita.

❖Canales de Comunicación. Si existen múltiples procesos
compartiendo un servicio de un dispositivo de E/S común, las
solicitudes podrían ser enviadas a un proceso servidor.

71. Instituto
Tecnológico
Tepic
Conceptos básicos

❖En general, el objetivo de la planificación es mejorar el
aprovechamiento de los recursos y lograr una mejor calidad del
servicio.

❖ Específicamente, la multiprogramación intenta mejorar el uso del
procesador
▪Cada vez que un proceso realiza E/S, el procesador queda libre para ser
asignado a otro proceso.
▪ Se requiere de una política de planificación

72. Instituto
Tecnológico
Tepic
Secuencia alternada de CPU y E/S
El éxito de la planificación de la CPU depende de la siguiente propiedad observada de los
procesos: La ejecución de un proceso consiste en un ciclo de ejecución en la CPU y
espera por E/S. los procesos se alternan entre estos 2 estados.
La ejecución de un proceso inicia con una ráfaga de CPU, luego entra una ráfaga de E/S
y así sucesivamente. Tarde o temprano, la ultima ráfaga de CPU termina con una solicitud
al sistema para terminar la ejecución
Burst = ráfaga

73. Instituto
Tecnológico
Tepic
Histograma de tiempos de ráfaga de CPU
Se han hecho mucha mediciones de la duración de esta ráfagas de CPU.
Aunque las duraciones varián considerablemente de un proceso a otro y de
una computadora a otra, tienden a tener una curva de frecuencia similar a la
aquí mostrada.
Hay un gran numero de ráfagas de CPU cortas, y pocas ráfagas de CPU
largas.

74. Instituto
Tecnológico
Tepic
Planificador de CPU
❖Realiza la planificación de corto plazo
(planificador de CPU), encargándose de:
▪Seleccionar el próximo proceso listo que recibe
el procesador.
▪Algunos criterios pueden ser por orden de
llegada, por prioridad, etc.
❖ Es invocado cada vez que un proceso libera
voluntariamente o no el procesador.

75. Instituto
Tecnológico
TepicExpropiación en la Planificación del Procesador
❖El planificador de la CPU puede intervenir cuando un proceso:
1.Pasa voluntariamente a estado de espera (e.g. E/S,
sincronización, etc.)
2.Pasa a estado listo por expiración de tiempo
(timeout)
3.Pasa de estado esperando a listo
4.Cuando termina
❖ Cuando el planificador sólo interviene en 1 y 4, se dice
que la planificación es sin expropiación o
no-prioritaria (nonpreemptive), en caso contrario es
con expropiación y utilizan prioridades (preemptive)

76. Instituto
Tecnológico
Tepic
Despachador
❖El modulo Despachador(dispatcher) le da el
control del CPU al proceso seleccionado por
el planificador a corto plazo; esto involucra:
▪Cambiar el contexto
▪Cambiar a modo de usuario
▪Brincar a la posición adecuada en el programa
del usuario para reiniciar e programa.
❖Latencia de despacho – tiempo que toma al
despachador detener un proceso e iniciar
otro

77. Instituto
Tecnológico
Tepic
Criterios de planificación
❖Utilización de CPU – mantener el CPU tan ocupado como
sea posible.

❖Rendimiento (Throughput) – # de procesos que completan
su ejecución por unidad de tiempo.

❖Tiempo de retorno – cantidad de tiempo para ejecutar un
proceso particular.

❖Tiempo de espera – cantidad de tiempo que un proceso ha
esperado en la cola listos.

❖Tiempo de respuesta – cantidad de tiempo que toma desde
que una solicitud se realiza hasta que se produce la primera
respuesta, no salida (para ambientes de
tiempo-compartido)

78. Instituto
Tecnológico
Tepic
Criterios de optimización
❖Utilización max CPU
❖Rendimiento max
❖Tiempo mínimo de vuelta
(turnaround)
❖Tiempo mínimo de espera
❖Tiempo mínimo de respuesta

79. Instituto
Tecnológico
Tepic
Nomenclatura
❖Tt : Tiempo de tránsito
❖ Tw : Tiempo de espera
❖ Tr : Tiempo de respuesta
❖ Ts : Tiempo de servicio
❖ Ps : Productividad del servidor
❖ Us : Utilización del servidor

80. Instituto
Tecnológico
Tepic
Ejemplo: Un servidor

81. Instituto
Tecnológico
Tepic
Tipos de Algoritmos de Planificación
❖Expropiación (preemption). Existen algoritmos con y sin
expropiación del recurso.
❖Intervalos de tiempo. El proceso puede recibir el recurso por un
cierto lapso de tiempo.
❖Prioridades. A los procesos se les pueden asociar prioridades, las
cuales pueden ser estáticas o dinámicas.
❖Tiempos límites (deadlines). Existen tiempo límites para que
termine un proceso. Contra más cerca se esté de ese límite, más
urgente se hace su planificación.

82. Instituto
Tecnológico
Tepic
Algoritmos de Planificación

83. Instituto
Tecnológico
TepicPlanificación First-Come, First-Served (FCFS)
Proceso rafaga de CPU
P
1
24
P
2
3
P
3
3

❖Supon que los procesos llegan en el orden: P
1
, P
2
, P
3
La gráfica de Gantt del planificador es:






❖Tiempo de espera (Tw) para P
1
= 0; P
2
= 24; P
3
= 27
❖Tiempo promedio de espera: (0 + 24 + 27)/3 = 17
P
1
P
2
P
3

24 27 300

84. Instituto
Tecnológico
Tepic
Planificación FCFS (Cont.)
Supon que los procesos llegan en el orden
P
2
, P
3
, P
1

❖La gráfica de Gantt para el planificador es:




❖Tiempo de espera para P
1
= 6;

P
2
= 0
;
P
3
= 3
❖Tiempo promedio de respuesta: (6 + 0 + 3)/3 = 3
❖Mucho mejor que en el caso anterior
❖Efecto Convoy procesos cortos detrás de procesos largos
P
1
P
3
P
2

63 300

85. Instituto
Tecnológico
Tepic
Efecto Convoy en FCFS
❖Se produce cuando se tiene una mezcla de un proceso
ligado a CPU y varios procesos ligados a E/S.
❖Estos últimos procesos tenderán a ubicarse en la cola
LISTO, donde serán frenados por el proceso que usa
mucha CPU, quedando los recursos de E/S libres.
❖Por el otro lado, cuando el proceso ligado a CPU libera el
procesador, los demás procesos pasan rápido a E/S,
quedando la CPU ociosa.
❖Por lo tanto, se produce baja utilización de CPU y de los
dispositivos de E/S.
❖Una solución requeriría una planificación no FCFS.

86. Instituto
Tecnológico
Tepic
Planificación Shortest-Job-First (SJF)
❖Asociar con cada proceso la longitud de su siguiente explosión de
CPU. Utilizar estas longitudes para planificar el proceso con el
tiempo más corto.
❖Dos esquemas:
▪nonpreemptive – una vez que le damos el CPU a un proceso
dado, no puede quitársele hasta que complete su explosión
de CPU.
▪preemptive – si un proceso nuevo llega al CPU con longitud
de explosión menor al tiempo restante del proceso en
ejecución, lo sacas. Este esquema es conocido como
Shortest-Remaining-Time-First (SRTF)
❖SJF es optimo – da el menor tiempo de espera promedio para un
conjunto de procesos dado

87. Instituto
Tecnológico
Tepic
Proceso Tiempo de llegada Tiempo de rafaga
P
1
0.07
P
2
2.04
P
3
4.01
P
4
5.04
❖SJF (non-preemptive)




❖Tiempo de espera promedio = (0 + 6 + 3 + 7)/4 = 4
Ejemplo de Non-Preemptive SJF
P
1
P
3
P
2

73 160
P
4

8 12

88. Instituto
Tecnológico
Tepic
Ejemplo de Preemptive SJF
Proceso Tiempo de llegada Tiempo rafaga
P
1
0.0 7
P
2
2.0 4
P
3
4.0 1
P
4
5.0 4
❖SJF (preemptive)




❖Tiempo de espera promedio = (9 + 1 + 0 +2)/4 = 3
P
1
P
3
P
2

42
1
1
0
P
4

5 7
P
2
P
1

16

89. Instituto
Tecnológico
Tepic
Características de SJF
❖Desempeño:
▪ SJF es óptimo en cuánto a reducir el tiempo de espera.
▪Demostración: Cualquier permutación aumenta el tiempo de
espera.

❖ Problemas:
▪Es necesario conocer a priori o predecir el tiempo de servicio del
trabajo.
▪Tal cual, el algoritmo es sólo aplicable a planificación de largo
plazo.

90. Instituto
Tecnológico
Tepic
Aplicación de SJF a Planificación del Procesador
❖Se intenta estimar para cada proceso la duración del próximo ciclo o
ráfaga de CPU.
❖ Se asigna el procesador a aquel proceso que tiene el menor tiempo
estimado de CPU.
❖ Estimación se puede hacer usando promedio exponencial:

91. Instituto
Tecnológico
TepicPredicción de longitud de la sig. Exp de CPU
En esta gráfica se muestra un promedio exponencial con =1/2 y
=10

92. Instituto
Tecnológico
Tepic
Planificación con prioridades
❖Una prioridad numérica (entero) se asocia con cada proceso
❖El CPU se asigna al proceso con la prioridad más alta (entero
más pequeño = prioridad más alta)
▪Preemptive
▪nonpreemptive
❖SJF es un planificador con prioridades donde la prioridad es
la explosión de CPU determinada
❖Problema -> hambruna – procesos de baja prioridad pueden
nunca ejecutarse
❖Solución -> Envejecer – conforme pasa el tiempo,
incrementar la prioridad de los procesos

93. Instituto
Tecnológico
Tepic
Round Robin (RR)
❖Cada proceso obtiene una pequeña unidad de tiempo de
CPU (time quantum), usualmente 10-100 milisegundos.
Después que ha pasado este tiempo, el proceso es sacado
(preempted) y se agrega a la cola de listos.
❖Si hay n procesos en la cola de listos y el tiempo quantum es
q, entonces cada proceso obtiene 1/n del tiempo de CPU en
pedazos de a lo más q unidades a la vez. Ningún proceso
espera más de (n-1)q unidades de t.
❖Rendimiento
▪q grande -> FIFO
▪q pequeña -> q debe ser grande con respecto al cambio de
contexto, de otra forma la carga administrativa es muy
grande

94. Instituto
Tecnológico
TepicEjemplo de RR con Time Quantum = 20
ProcesoBurst Time
P
1
53
P
2
17
P
3
68
P
4
24
❖La gráfica de Gantt es:






❖Típicamente, tiempo de vuelta promedio mayor a SJF, pero
mejor respuesta
P
1
P
2
P
3
P
4
P
1
P
3
P
4
P
1
P
3
P
3

02037577797
11
7
12
1
13
4
15
4
16
2

95. Instituto
Tecnológico
Tepic
Tiempo de Quantum y Context Switch
Un cuanto de tiempo mas pequeño aumenta el numero de conmutaciones de
contexto por lo tanto es importante que el cuanto de tiempo se grande en
comparación con el tiempo que tarda una conmutación de contexto.

96. Instituto
Tecnológico
Tepic
Tiempo de vuelta varía con el Quantum
El tiempo de vuelta o retorno depende del tamaño del cuanto de tiempo,
Como puede verse el tiempo de retorno promedio de un conjunto de
procesos no necesariamente se reduce al aumentar el tamaño del cuanto.

97. Instituto
Tecnológico
Tepic
Cola multi-niveles
❖La cola de listos se particiona en varias colas:
foreground (interactive)
background (batch)
❖Cada cola tiene su propio algoritmo de planificación
▪foreground – RR
▪background – FCFS
❖Se debe hacer planificación entre colas
▪Planificación con prioridad fija; (i.e., servir todas las del
foreground y luego background). Posibilidad de
hambruna.
▪Rebanada de tiempo – cada cola obtiene una cierta
cantidad de tiempo de CPU, que puede planificar entre
sus procesos; i.e., 80% para foreground en RR y 20% para
background en FCFS

98. Instituto
Tecnológico
TepicPlanificación con colas de varios niveles

99. Instituto
Tecnológico
TepicColas varios niveles con retro-alimentación
❖Un proceso se puede mover entre las distintas colas; así se puede
implementar envejecimiento
❖Planificador para colas de varios niveles con retroalimentación
con los siguientes parámetros:
▪Número de colas
▪Algoritmos de planificación para cada cola
▪Método utilizado para determinar cuando avanzar un
proceso
▪Método utilizado para determinar cuando retrazar un
proceso
▪Método utilizado para determinar a qué colas entrará un
proceso cuando requiera servicio

100. Instituto
Tecnológico
TepicEjemplo cola varios niveles y retroalimentación
❖Tres colas:
▪Q
0
– RR con quantum de 8 milisegundos
▪Q
1
– RR con de 16 milisegundos
▪Q
2
– FCFS
❖Planificación
▪Un nuevo trabajo entra en cola Q
0
con FCFS. Cuando llega al
CPU, el proceso recibe 8 milisegundos. Si no termina en 8
ms, el trabajo se mueve a la cola Q
1
.
▪En Q
1
el trabajo se atiende con FCFS y recibe 16 ms
adicionales. Si aún no se termina, es sacado del CPU y
encolado en Q
2
.

101. Instituto
Tecnológico
Tepic
Colas con varios niveles y retroalimentación

102. Instituto
Tecnológico
Tepic
Planificación multi-procesador
❖Planificar uso de CPU más complicado
con varios CPUs
❖Procesadores homogéneos dentro de un
multi-procesador
❖Compartir la carga
❖Multi-procesadores asimétricos – sólo
un procesador accede las estructuras de
datos del sistema, aligerando la
necesidad de compartir datos

103. Instituto
Tecnológico
Tepic
Planificación de tiempo real
❖Sistemas de tiempo real duros
– requieren completar un tarea
crítica en un cierto tiempo
garantizado
❖Cómputo de tiempo real suave
– requiere que procesos
críticos sean privilegiados por
sobre otros menos afortunados

104. Instituto
Tecnológico
Tepic
Ejemplos de sistemas operativos

❖Planificación en Solaris
❖Planificación en Windows XP
❖Planificación en Linux

105. Instituto
Tecnológico
Tepic
Planificación en Solaris
❖Solaris usa una planificación de hebras basada en prioridades, definiendo cuatro clases para
planificación. Estas clases son, por orden de prioridad:
▪1. Tiempo real
▪2. Sistema
▪3. Tiempo compartido
▪4. In teractiva

Dentro de cada clase hay diferentes prioridades y diferentes algoritmos de planificación. Los
mecanismos de planificación en Solaris se ilustran en la Figura siguiente

La clase de planificación predeterminada para un proceso es la de tiempo compartido. La
política de planificación para tiempo compartido modifica dinámicamente las prioridades y
asigna cuantos de tiempo de diferente duración usando colas multinivel realimentadas. De
manera predeterminada, existe una relación inversa entre las prioridades y los cuantos de
tiempo. Cuanto más alta sea la prioridad, más pequeño será el cuanto de tiempo; y cuanto
menor sea la prioridad, más larga será la franja. Los procesos interactivos suelen tener la
prioridad más alta; los procesos limitados por la CPU tienen la prioridad más baja. Esta
política de planificación proporciona un buen tiempo de respuesta para los procesos
interactivos y una buena tasa de procesamiento para los procesos limitados por la CPU. La
clase interactiva usa la misma política de planificación que la clase de tiempo compartido,
pero proporciona a las aplicaciones con interfaz de ventanas una prioridad más alta, para
aumentar el rendimiento.

106. Instituto
Tecnológico
Tepic
Planificación en Solaris

107. Instituto
Tecnológico
Tepic
Solaris Tabla de Despacho

108. Instituto
Tecnológico
Tepic
Prioridades en Windows XP

109. Instituto
Tecnológico
Tepic
Planificación en Linux
❖Dos algoritmos: tiempo compartido y tiempo real
❖Tiempo compartido
▪Priorizado basado en crédito – proceso con más créditos se
procesa a continuación
▪Se resta crédito cuando ocurre una interrupción por
tiempo
▪Cuando el crédito = 0, se escoje otro proceso
▪Cuando todos los procesos tienen credito = 0, se re-asignan
créditos
•Basado en factores como prioridad e historia
❖Tiempo real
▪Tiempo real suave
▪Cumple con Posix.1b – dos clases
•FCFS y RR
•Proceso de más alta prioridad siempre corre primero

110. Instituto
Tecnológico
TepicRelación entre prioridades y longitud de rebanada tiempo

111. Instituto
Tecnológico
Tepic
Lista de tareas indexada por prioridades

112. www.themegallery.com