View
216
Download
0
Category
Preview:
Citation preview
Extendiendo Minix a Extendiendo Minix a Arquitecturas SMPArquitecturas SMP
Extendiendo Minix a Extendiendo Minix a Arquitecturas SMPArquitecturas SMP
Jesús M. Álvarez Llorente
Juan Carlos Díaz Martín
José Manuel Rodríguez García
Departamento de Informática
Universidad de Extremadura
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
Minix SMP
1. Motivación y objetivos
2. Arquitectura multiprocesador de Intel
3. Arquitectura de Minix 2.0.0
4. Principios de diseño
5. Detalles de implementación
6. Conclusiones.
7. Trabajo futuro.
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
1. Motivación y objetivos
• Minix es la referencia por excelencia para la docencia de Sistemas Operativos.
Microkernel, POSIX, Intel, manejable, gratuito, documentado, real...
• Las arquitecturas multiprocesador se están popularizando.
• Es difícil encontrar bibliografía sobre multiprocesadores (hardware y sistemas operativos).
1. Motivación y objetivos
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
1. Motivación y objetivos
• Repetimos el planteamiento de Tanenbaum:
fabricamos un S.O. Multiprocesador para
aprender.
• No partimos de cero: aprovechamos Minix.
– Aprovechamos lo aprendido.
– Aprendemos las diferencias.
– Es una buena base, dará un buen resultado.
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
2. Arquitectura Intel MP
• Especificación Intel MP 1.4 para Pentium*.
• Memoria compartida. Coherencia de cache.
• Instrucciones atómicas.
• El BIOS configura para simular
monoprocesador y proporciona información en
una Tabla de Configuración MP.
• El BSP arranca, los AP esperan.
2. Arquitectura Intel MP
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
2. Arquitectura Intel MP
• Se perfecciona el hardware de interrupciones: APIC local, I/O APIC, IPI,...
C P U 0 C P U 1 C P U 2
A P IC loca l
B U S IC C (In te rru p t C o n tro lle r C o m u n ic a t io n s )
A P IC loca l A P IC loca l
I/O A PIC
PIC s (8259)
Fu entes de Interrupción
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
3. Arquitectura de Minix 2.0.0
• Microkernel, 3 niveles de procesos
H a rdw are
M icro -n úc leo M in ix
S erv id o res
P ro c. u sua r io
Tarea s E /S
H a rdw are
M icro -n úc leo M in ix
S erv id o res
P ro c. u sua r io
Tarea s E /S
3. Arquitectura de Minix 2.0.0
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
3. Arquitectura de Minix 2.0.0
• Modo protegido: indispensable para MP.
• Planificador:
C O L A TA R E A S E /S
ID L E
C O L A S E R V ID O R E S
C O L A U S U A R IO
Tarea 1
S e rv id o r 1
P ro ceso 1 P ro ceso 2 P ro ceso 3
S e rv id o r 2
Tarea 2 Tarea 3C O L A TA R E A S E /S
ID L E
C O L A S E R V ID O R E S
C O L A U S U A R IO
Tarea 1
S e rv id o r 1
P ro ceso 1 P ro ceso 2 P ro ceso 3
S e rv id o r 2
Tarea 2 Tarea 3
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
3. Arquitectura de Minix 2.0.0
• Núcleo reentrante: interrupciones retenidas.
d isp atch er
In terru p ció n
save:
restart:
restart1:
s_call:
Trap
E n tr a d aR e e n tr a d a
¿ In t. re ten id a s?
R estau rar con tex to de p roceso oentrad a an ter io r al n ú cleo
N o
S í
d isp atch er
In terru p ció n
save:
restart:
restart1:
s_call:
Trap
E n tr a d aR e e n tr a d a
¿ In t. re ten id a s?
R estau rar con tex to de p roceso oentrad a an ter io r al n ú cleo
N o
S í
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
4. Principios de diseño
• Objetivo principal: mantener la estructura original de Minix 2.0.0 lo más intacta posible.
• Escalable y condicional.
• Para un doble Pentium III (Intel MP 1.4).
4. Principios de diseño
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
4. Principios de diseño
• Alcance de la extensión:
E xtensión SM P
H a rdw are
M icro -n úc leo M in ix
S erv id o res
P ro c. u su a r io
Tarea s E /S
E xtensión SM P
H a rdw are
M icro -n úc leo M in ix
S erv id o res
P ro c. u su a r io
Tarea s E /S
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
4. Principios de diseño
• Nuevo código para el nuevo hardware:– Tabla de Configuración MP.– Acceso a APIC (local, I/O).– Arranque/Detención.– Primitivas de sincronización: spinlocks (primitivas LOCK, UNLOCK)
• Código modificado:– Sincronización de regiones críticas.– Modificación del planificador.– Replicación de recursos.
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
4. Principios de diseño
• Regiones críticas: el micronúcleo completo.
d isp atch er
In terru p ció n
save:
restart:
restart1:
s_call:
Trap
E n tr a d aR e e n tr a d a
¿ In t. re ten id a s?
R estau rar con tex to de p roceso oentrad a an ter io r al n ú cleo
N o
S í
LOCK LOCK
UNLOCK
d isp atch er
In terru p ció n
save:
restart:
restart1:
s_call:
Trap
E n tr a d aR e e n tr a d a
¿ In t. re ten id a s?
R estau rar con tex to de p roceso oentrad a an ter io r al n ú cleo
N o
S í
LOCK LOCK
UNLOCK
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
4. Principios de diseño
• Planificador:– SMP: “Ninguno de los procesadores es distinto
de los demás”.– Cada procesador toma trabajo sin conocer la
existencia de los demás.– Un procesador sólo toma procesos listos que no
pertenezcan a otro.– Sincronización del planificador: métodos son
regiones críticas.
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
4. Principios de diseño
• Bloqueo del planificador desde las tareas E/S
sys_call
sys_call2
UNLOCK
LOCK
lock_mini_send
mini_send
UNLOCK
LOCK
lock_ready
ready
UNLOCK
LOCK
lock_unready
unready
UNLOCK
LOCK
lock_pick_proc
pick_proc
UNLOCK
LOCK
lock_sched
sched
UNLOCK
LOCK
lock_mini_rec
mini_rec
UNLOCK
LOCK
interrupt
UNLOCK
LOCK
In te r r u p c ió n
L la m a d a a ls is te m a
sys_call
sys_call2
UNLOCK
LOCK
lock_mini_send
mini_send
UNLOCK
LOCK
lock_ready
ready
UNLOCK
LOCK
lock_unready
unready
UNLOCK
LOCK
lock_pick_proc
pick_proc
UNLOCK
LOCK
lock_sched
sched
UNLOCK
LOCK
lock_mini_rec
mini_rec
UNLOCK
LOCK
interrupt
UNLOCK
LOCK
In te r r u p c ió n
L la m a d a a ls is te m a
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
4. Principios de diseño
• Algunos recursos se replican para cada procesador:– Variables pasan a ser vectores (array).– Cada procesador accede a su índice.– Identificación del procesador mediante su APIC
local.
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
5. Detalles de implementación
• Implementación de cerrojos: LOCK, UNLOCK mediante instrucciones atómicas.
#define MP_LOCK(semaphore_var) ;\0: clc ;\
lock bts (semaphore_var), 0 ;\jnc 2f ;\
1: cmp (semaphore_var), 0 ;\jne 1b ;\jmp 0b ;\
2:
#define MP_UNLOCK(semaphore_var) ;\lock btr (semaphore_var), 0
#define MP_LOCK(semaphore_var) ;\0: clc ;\
lock bts (semaphore_var), 0 ;\jnc 2f ;\
1: cmp (semaphore_var), 0 ;\jne 1b ;\jmp 0b ;\
2:
#define MP_UNLOCK(semaphore_var) ;\lock btr (semaphore_var), 0
5. Detalles de implementación
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
5. Detalles de implementación
• Estructuras replicadas:– Puntero de proceso proc_ptr.– Puntero de tarificación bill_ptr.– Pila del núcleo.– Contador de reentradas k_reenter.– Estructura TSS (Task State Segment).– Tarea IDLE.
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
5. Detalles de implementación
• Procedimiento de arranque:– El BIOS arranca el BSP como si estuviera solo y dispone una
Tabla de Configuración MP en memoria.– El BSP prepara el código inicial del AP en una dirección
determinada (pista de aterrizaje, trampoline).– El BSP envía interrupciones IPI a los AP indicando la dirección.– Cada AP comienza a ejecutar desde esa dirección:
• Paso a modo protegido• Clonación de estructuras de memoria.• Habilitación de interrupciones.• Salto al dispatcher
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
5. Detalles de implementación
A rranqu enorm al
m onoprocesad or
d isp atch er
B S P
mp_start()
L eer Tab la C on fig u ració n M P
P ara cad a C P UE n via r IP Is d e a rran q u e
P rep ara r P is ta aterr izaje
L a en tre g a d e la s IP Ip ro d u c e e l a r ra n q u e d e l A P
A rranq u e en m o d o realP aso a m o d o p ro teg id oC o n fig . e stru c tu ra s d e m em oria
C o n fig u rac ió n d e in terru p cio nes
A P 1A P 2
A P...
LOCK
LOCK
UNLOCK
A rranqu enorm al
m onoprocesad or
d isp atch er
B S P
mp_start()
L eer Tab la C on fig u ració n M P
P ara cad a C P UE n via r IP Is d e a rran q u e
P rep ara r P is ta aterr izaje
L a en tre g a d e la s IP Ip ro d u c e e l a r ra n q u e d e l A P
A rranq u e en m o d o realP aso a m o d o p ro teg id oC o n fig . e stru c tu ra s d e m em oria
C o n fig u rac ió n d e in terru p cio nes
A P 1A P 2
A P...
LOCK
LOCK
UNLOCK
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
6. Conclusiones
• La extensión de Minix a SMP resulta sencilla de comprender.
• Se parece mucho a la extensión de Linux.
• Lo más complejo es entender el hardware.
• Esto reafirma nuestro interés en este trabajo, que nos aporta:– Un sistema SMP para uso docente.– Una valiosa experiencia y documentación.
6. Conclusiones
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
7. Trabajo futuro
• Publicación del código (¡inminente!).
• Perfeccionamiento del código:– Utilización del I/O APIC.– Optimización y mejora del código.– Ampliación de arquitecturas.
• Integración con Pthreads (proyecto PONNHI).
7. Trabajo futuro
Extendiendo Minix a Arquitecturas SMP - XIII Jornadas de Paralelismo - Lleida, septiembre de 2002
Agradecimientos
Financiado por el proyecto CICYT nº TIC99-0960, “Diseño e Implementación de Algoritmos de
Procesado de Señal de Altas Prestaciones para Reconocimiento de Voz en Condiciones Adversas”
Agradecimientos
Recommended