Multiprocessor Scheduling
Chapter 10
Nota: Material en Revisión, con notas propias y
laminas del Stalling y del Tanenbaum
Classifications of
Multiprocessor Systems
• Loosely coupled multiprocessor
– Each processor has its own memory and I/O
channels
• Functionally specialized processors
– Such as I/O processor
– Controlled by a master processor
• Tightly coupled multiprocessing
– Processors share main memory
– Controlled by operating system
Coarse and Very CoarseGrained Parallelism
• Synchronization among processes at a
very gross level
• Good for concurrent processes running
on a multiprogrammed uniprocessor
– Can by supported on a multiprocessor with
little change
Medium-Grained Parallelism
• Parallel processing or multitasking
within a single application
• Single application is a collection of
threads
• Threads usually interact frequently
Fine-Grained Parallelism
• Highly parallel applications
• Specialized and fragmented area
Consideraciones para la Planificación
en Multiprocesadores
•
•
•
•
Qué vamos a planificar: hilos o procesos
En qué procesador se va a ejecutar?
Dónde se ejecuta el SOP?
Cuál será el próximo proceso o hilo a
ejecutar?
Procesos
• No se vinculan a los procesadores.
• Una sola cola de la que escogen todos
los procesadores o una lista de colas
basadas en prioridades.
• Se puede usar cualquier algoritmo, pero
los estudios demuestran que la disciplina
de planificación es menos importante.
Planificación de Hilos
• Modo kernel o modo usuario?
• Están o no relacionados todos los hilos?
– No hay relación alguna.
– Pertenecen a la misma aplicación, cooperan.
Es importante que se ejecuten en conjunto.
Ejem. Make.
Planificación de Hilos
• En qué procesador se va a ejecutar:
– Planificación estática o dinámica
– Uso de la multiprogramación: tiene sentido
si el paralelismo es de grano medio, fino?
• Dónde se ejecuta el SOP?
– Maestro/Esclavo
– Camaradas
• Cómo se hace la planificación de los
Hilos?
Timesharing (Tiempo
Compartido)
Figure 8-12. Using a single data structure
for scheduling a multiprocessor.
Tanenbaum, Modern Operating
Systems 3 e, (c) 2008 Prentice-Hall,
Inc. All rights reserved. 0-136006639
Tiempo Compartido
Estrategia para hilos independientes.
Se usa una sola estructura de datos: lista o
conjunto de listas.
- Ventajas: simple, balance de carga, en las
colas se puede utilizar cualquier estrategia de
planificación conocida.
- Desventajas: Contención, si hay
multiprogramación es poco probable que los
hilos retomen la ejecución en el mismo
procesador, no necesariamente ganan acceso
en grupo
Tiempo Compartido
Mejoras:
- Planificación Inteligente.
- Planificación por Afinidad.
Espacio Compartido
• Estrategia para hilos relacionados
• Al momento de crear un conjunto de
hilos relacionados, se comprueba si hay
tantos CPUs como hilos en el conjunto.
• Si los hay, a cada hilo se le asigna un CPU
dedicado (sin multiprogramación)
• Si no hay suficientes procesadores no se
inicia ningún hilo
Espacio Compartido
Las particiones del multiprocesador van
cambiando según varía el conjunto de hilos
que se crea.
Desventajas: CPUs ociosos, una aplicación
puede tardar en comenzar a ejecutarse.
Ventajas: no hay overhead por cambios de
contexto..
Sol: a) planificación en pandilla, b) que el grado
de paralelismo sea dinámico y se ajuste según
la carga (puede no ser posible en todas las
palicaciones)
Space Sharing (Espacio
Compartido)
Figure 8-13. A set of 32 CPUs split into
four partitions,
with two CPUs available.
Tanenbaum, Modern Operating
Systems 3 e, (c) 2008 Prentice-Hall,
Planificación por Pandilla
- Sirve para hilos relacionados, los cuales
forman una pandilla.
Gang Scheduling (1)
Figure 8-14. Communication between two
threads belonging to thread A that are
running out of phase.
Tanenbaum, Modern Operating
Systems 3 e, (c) 2008 Prentice-Hall,
Inc. All rights reserved. 0-136006639
Planificación por Pandilla
- Todos los miembros de una pandilla se
ejecutan en CPUs multiprogramados
pero en forma simultánea.
- Todos los miembros de una pandilla se
inician y terminan en conjunto.
- El planificador trabaja con quantums, al
inicio de los cuales todas las CPUs se
reprograman y se inician nuevos hilos
Planificación por Pandilla
Si durante un quantum un hilo se bloquea,
éste conserva el procesador hasta
finalizar el mismo. El CPU permanece
ocioso.
Gang Scheduling
(Planificación por Pandilla)
Figure 8-15. Gang scheduling.
Tanenbaum, Modern Operating
Systems 3 e, (c) 2008 Prentice-Hall,
Inc. All rights reserved. 0-136006639
Descargar

Introduction to Object Technology