Download ENtornos Operativos para la Gestión de Recursos de

ENtornos Operativos para la Gestión de
Recursos de Aplicaciones Paralelas
Marisa Gil, Xavier Martorell {marisa,xavim}@ac.upc.es
Curso de Doctorado 2.002/03
Departamento de Arquitectura de Computadores
UPC
UPC/DAC Tardor 2.002
INTRODUCCIÓN
¿Qué es un sistema operativo?
(dibujo sacado de “Operating Systems. Communicating with and Controlling the Computer” Laurie S. Keller, Prentice Hall, 1988, p.7)
Almacenamiento
secundario
Output
Almacenamiento
primario
Gestión de
almacenamiento
secundario
Gestión de
almacenamiento/
almacenamiento
virtual
Gestión de
almacenamiento
real
Output
Input
Procesador
Gestión del
procesador
Entornos Operativos para la Gestión de Recursos ...
2
UPC/DAC Tardor 2.002
INTRODUCCIÓN
¿Qué es un sistema operativo?
Sistema Operativo: conjunto de software (rutinas y “programas”) que hacen de
intermediario entre el hardware y las aplicaciones.
Ap
Ap
Ap
Ap
SO
Hw
Entornos Operativos para la Gestión de Recursos ...
3
UPC/DAC Tardor 2.002
INTRODUCCIÓN
¿Qué es un sistema operativo?
• GESTOR DE RECURSOS:
- Varias aplicaciones y usuarios coexisten:
• Mejor utilización de la máquina, compartiendo todos los recursos.
- Cualquier parte de la máquina se ve como un recurso y todos los recursos
pertenecen al sistema operativo.
- Recursos tradicionales
• Discos, memoria, impresora
- Recursos en auge en la actualidad
• Procesadores: gestión del paralelismo
• Red: protocolos, coordinación en tiempo real
• Consumo de energía: sistemas embedded
• MÁQUINA VIRTUAL:
• modelo más comprensivo para el usuario
• instrucciones más simples de utilizar
Entornos Operativos para la Gestión de Recursos ...
4
UPC/DAC Tardor 2.002
INTRODUCCIÓN
El sistema operativo como gestor de recursos
• Recursos hardware de la máquina en la que está corriendo
• Recursos software (dispositivos lógicos):
buzones
ficheros
terminales virtuales
• Gestión que lleva a cabo:
- Tratar y dirigir los acontecimientos que llegan al sistema.
- Decidir a quién asigna un recurso, cómo y durante cuánto tiempo.
- Permitir la compartición y que sea “la más justa”.
• Además,
- Garantizar la protección de los programas y suya.
Entornos Operativos para la Gestión de Recursos ...
5
UPC/DAC Tardor 2.002
INTRODUCCIÓN
El sistema operativo como máquina virtual
• Ofrecer una visión simplificada -o diferente- de la arquitectura hardware
- Cómo interaccionan los componentes de un sistema, desde la visión del
usuario
- La descripción puede ser muy compleja y se divide en módulos
• división vertical, en base a la funcionalidad y su implementación
• división horizontal, en interficies, sin entrar en la implementación
:
S.O.
Gestión
de Ficheros
Gestión de
Procesos
Gestión de
Dispositivos
Hardware
Entornos Operativos para la Gestión de Recursos ...
CPUs
Dispositivos
Gestión
de Memoria
Memoria
6
UPC/DAC Tardor 2.002
INTRODUCCIÓN
El sistema operativo como máquina virtual
Las abstracciones y modelos, que pueden simplificar la visión y el estudio,
pueden sin embargo dificultar modificaciones de diseño o de nuevas
funcionalidades.
Por ejemplo, mejorar la gestión de memoria a partir de una visión de la
memoria virtual, en lugar de trabajar sobre el recurso “memoria física”
Entornos Operativos para la Gestión de Recursos ...
7
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Estructura de un sistema operativo clásico
Programa de
usuario
Programa de
sistema
Llamadas al
sistema
Llamadas al
sistema
Sistema Operativo
La manera de acceder a los servicios del sistema operativo es a través de las llamadas al sistema.
Todo programa, de usuario o especial, acaba realizando una llamada al sistema si
quiere acceder a los recursos del sistema.
Entornos Operativos para la Gestión de Recursos ...
8
UPC/DAC Tardor 2.002
INTRODUCCIÓN
LLamadas al sistema: Librería de sistema
programa
printf
librería de C
scanf.....
factorial
potencia... librería matemática
read,exec... librería del sistema
Sistema Operativo
En la librería de sistema están todas las llamadas al sistema
La apariencia de externa de una llamada al sistema es exactamente igual a la de la llamada a una función o procedimiento del programa de usuario, o bien de una librería del
lenguaje.
Entornos Operativos para la Gestión de Recursos ...
9
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Cómo el SO realiza un servicio
Petición de un servicio
Información de que el servicio ha
finalizado y de cómo ha finalizado
USUARIO
SISTEMA
Realización del
servicio
Entornos Operativos para la Gestión de Recursos ...
Qué estructuras ha necesitado
Qué algoritmos ha utilizado
Cuánto tiempo ha tardado
A qué dispositivos ha accedido
10
UPC/DAC Tardor 2.002
INTRODUCCIÓN
El Sistema Operativo como máquina virtual
• Modelo más “comprensivo”del sistema operativo.
• La máquina real, es vista y utilizada por las aplicaciones
según la ofrezca el SO:
• modelo proceso/thread
M
M
M
M
K
CPU
CPU
M
CPU
M
CPU
K
MODELO THREAD
MODELO PROCESO
• modelo de memoria compartida/paso de mensajes
M
M
CPU
M
M
K
M
M
CPU
K
CPU
MEMORIA COMPARTIDA
PASO DE MENSAJES
Entornos Operativos para la Gestión de Recursos ...
11
UPC/DAC Tardor 2.002
INTRODUCCIÓN
¿Cómo ven las aplicaciones los recursos?
• El SO simplifica el trabajo de las aplicaciones:
directamente dan una “orden” a su máquina virtual
“ejecutar-programa”
crear-proceso
cargar en memoria
fichero ejecutable
inicializar estructuras
en los diferentes
niveles/módulos/rutinas
• El SO las independiza de las cuestiones de política y asignación de los recursos
• compartición de recursos
• esperas de servicios.
Entornos Operativos para la Gestión de Recursos ...
12
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Estructura interna del sistema operativo
• Organización del código que forma el sistema operativo
• Depende de la metodología de diseño utilizada
• Depende de los objetivos funcionales del producto final
• fácil de comprender
• fácil de distribuir (sistemas distribuidos o en red)
• fácil de replicar y/o diversificar servicios
• fácil de modificar y/o ampliar
• Clasificación (una posible, la más tradicional)
• Monolítico
• Por capas o niveles
• Cliente/servidor
Entornos Operativos para la Gestión de Recursos ...
13
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Sistema operativo monolítico
Programa de
aplicación
.
.
.
Programa de
aplicación
Modo Usuario
Modo Kernel
Servicios del Sistema
Procedimientos
de S.O.
Hardware
• Las principales ventajas: simplicidad y eficiencia
• Buena integración de todos sus componentes
• Cuando el sistema crece, es difícil de ampliar.
• Son sistemas monolíticos: UNIX, DOS, Mach.
Entornos Operativos para la Gestión de Recursos ...
14
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Sistema Operativo por capas o niveles
Programa de
aplicación
.
.
.
Programa de
aplicación
Modo Usuario
Modo Kernel
Servicios del Sistema
Sistema de Ficheros
Administrador de dispositivos de E/S y memoria
Planificador del procesador
Hardware
• Potencia el desarrollo en grupos diferentes
• Fácil de entender y extender (añadir, modificar capas)
• Difícil definir “capas limpias”
• Ineficiencia de ver sólo el nivel inmediato
• Solución: capas porosas.
Entornos Operativos para la Gestión de Recursos ...
15
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Sistema operativo cliente/servidor
usuario
S. de
disco
Servidor
de proceso
S. de
ficheros
NÚCLEO
HW
• Todos los módulos son clientes y servidores del resto
• Permite modificar y ampliar los servicios
• Su principal problema es la sobrecarga de comunicación
• Punto de partida del diseño basado en el kernel
servidor
de
impresora
UNIX
server
usuario
usuario
microkernel
HW
Entornos Operativos para la Gestión de Recursos ...
16
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Estructura del sistema operativo
aplicación
interfaz de llamadas al sistema
vector de interrupciones
planificación
sincronización
sistema de
ficheros
memoria virtual
cola de peticiones de E/S
capa dependiente de la máquina (y dispositivos)
memoria
reloj
disco
Entornos Operativos para la Gestión de Recursos ...
pantalla
TLB
CPU
red
consola
17
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Abstracciones del sistema:
PARALELISMO/ASIGNACIÓN DE RECURSOS
Objeto al que el SO asigna los recursos
• Proceso
• Task-Thread
• Environment
• Realm
• Scheduler activation
Gestión de recursos asociada al objeto
• Espacio de direcciones
• Entornos de ejecución
• Políticas de asignación y compartición
Entornos Operativos para la Gestión de Recursos ...
18
UPC/DAC Tardor 2.002
INTRODUCCIÓN
El Proceso
• Process Control Block: contenedor donde guardar su estado
process
next
previous
state
process id
program counter
registers
memory structure
open file table
etc
Entornos Operativos para la Gestión de Recursos ...
19
UPC/DAC Tardor 2.002
INTRODUCCIÓN
La Task y el Thread en la Máquina Virtual que ofrece el S.O.
• Descomposición de la noción de proceso en dos abstracciones: Task y Thread
• Task
- Conjunto de recursos del sistema, agrupados en una entidad
- Dos Tasks no comparten nada si no se ha tomado una acción específica
- Contiene un cierto número de threads
• Thread
- Punto de un flujo de control dentro de una Task
- Pertenece a una única Task que define su espacio de direcciones
- Tiene acceso a todos los elementos de la Task
- Ejecuta potencialmente en paralelo con otros Threads
- Tiene un estado de ejecución “mínimo” (un PC y un SP)
- No hay relación de parentesco, todos son independientes
- Comunicación por memoria compartida, sincronización explícita
- Es planificado en procesador, posibles mapeos
- Es necesario para operaciones de SO, mantiene el estado
Entornos Operativos para la Gestión de Recursos ...
20
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Tasks/Threads vs. Procesos
• Modelo de proceso (máquina virtual monoprocesador) y
modelo de Task/Thread (máquina virtual multiprocesador)
• Motivación de la multiprogramación: Utilización eficiente de los recursos de la
máquina por parte de las aplicaciones
- concurrencia y paralelismo
- competición por los recursos
• Los procesos poseen espacios de direcciones independientes, privilegios independientes, capacidad de acumular recursos
• Proceso: creación y comunicación costosas, paralelismo de grano grueso
• Threads: concurrencia/paralelismo dentro de la Task
- menores costes de creación y comunicación (grano más fino)
- comunicación por memoria compartida
- gestión eficiente de múltiples situaciones de bloqueo
- cooperación en la planificación
• Propuestas de “procesos de peso variable”
Entornos Operativos para la Gestión de Recursos ...
21
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Task-Thread
• Características del thread en ejecución:
• identificador (pid, thid, puerto)
• estado de ejecución
• registros
• parámetros de planificación
• task que lo contiene
• contador de operaciones suspend
• estadísticas, tiempos
• procesador(es) asociados
• kernel stack
• en algunos sistemas, “memoria privada”
• tratamiento de excepciones (?)
Entornos Operativos para la Gestión de Recursos ...
22
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Aplicación de Mach: Processor_set
• Processor set:
- submáquina física dedicada a flujos (tasks)
- política de planificación propia
Processor Set (pset)
TASK
Runq
Runq
P
32 colas
Runq
P
procesadores inactivos
P
thread
..
Procesadores
.
P
Processor Set (pset)
Runq
Processor set (pset)
Runq
P
procesadores inactivos
P
P
P
Entornos Operativos para la Gestión de Recursos ...
23
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Scheduler Activations
• “Vasijas” que el kernel cede al usuario.
• El “mundo” de una vasija, es equivalente físicamente al de un thread
• Hay políticas y tratamientos que son del usuario, no del kernel
asignación de
flujo a eXc
activación
de upcall
aviso
con
upcall
Usuario
Kernel
eXc
procesador
Entornos Operativos para la Gestión de Recursos ...
24
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Scheduler Activations: ejemplo
asignación de
flujo a eXc
evento
eXc id
procesador
registros
④
activación
de upcall
③
②
Usuario
Kernel
eXc
fin temporización
①
Entornos Operativos para la Gestión de Recursos ...
procesador
25
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Shuttles y activations: migrating threads
• Se distinguen
- Task: objeto pasivo
- Task con thread: objeto activo
• El thread es una entidad de kernel que, ocasionalmente, hace upcalls para ejecutar diferentes códigos de usuario
- Shuttle: parte estática del thread (único por cada objeto thread)
- Activation: parte dinámica del thread (una por task)
• Visión de vínculo entre el recurso lógico (thread) y el recurso físico (procesador)
Entornos Operativos para la Gestión de Recursos ...
26
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Exokernel
• El sistema se convierte en un puro gestor de recursos del hardware
• La abstracción de procesador virtual se ofrece a un nivel superior y puede ser
diversa (para un entorno UNIX, el proceso, etc...)
• Necesita un objeto que represente la aplicación, como cliente que recibe recursos
environment
• Acumula toda la máquina virtual sobre la que corre una aplicación
- memoria virtual
- procesador
- red
Entornos Operativos para la Gestión de Recursos ...
27
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Environment
Representación del procesador como recurso
CPU
quantums
CPUContext
id CPU
curq
free_q
idle_env
curenv
tabla pág.
(bloque de
activación
del kernel)
Cola global: cada cpu tiene su env0, al que apunta:
- la estructura _cpuctxt->idle_env
- el quantum[0] de la cpu
Entornos Operativos para la Gestión de Recursos ...
used
qnum
nticks
envid
Uenv
(r/w por librería)
28
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Espacio de direcciones
• Memoria virtual
- Conjunto de direcciones válidas de la máquina virtual
- Independiente de las limitaciones físicas
- Modificación dinámica del espacio
- Espacio contiguo (Unix) o disperso
- Direccionable a byte, operaciones aplicables a conjuntos de bytes
- Memoria anónima o mapeada
- Protección y herencia
• Técnicas de gestión
- Unidad de asignación, protección
- Reemplazo global o local
- COW
Entornos Operativos para la Gestión de Recursos ...
29
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Multiprocesadores y entornos operativos
• Sistemas multiprocesadores
- Sistemas fuertemente acoplados, con memorias grandes
- Pool de procesadores
• Más CPUS que usuarios
• Asignación bajo demanda
- Estaciones de trabajo
• Procesador(es), memoria, pantalla, red, multimedia
• Sin disco, movilidad, carga dinámica de código y datos
• Entornos operativos multiprocesadores
- Monolíticos y microkernel
- Sobre nuevas abstracciones: thread, task, procesador
- Funcionalidades a nivel de usuario, a nivel de aplicación
- Emulación, extensibilidad y especialización a nivel de aplicación
- Programación dirigida por eventos, tratamiento excepciones, I/O asíncrona
Entornos Operativos para la Gestión de Recursos ...
30
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Modelos de programación paralela (con procesos o threads)
• Memoria compartida
- Procesos y memoria compartida explícita
- Flujos, compartición implícita y total
• Paso de mensajes
- Adaptado a la arquitectura
- Comunicación y sincronización explícita
- Distribución del código y datos
- Balanceo entre cálculo y comunicación
- Eficiente tras un laborioso diseño y realización
- La aplicación funciona sólo al final
- Dependiente de los cambios de velocidad relativa
• En conjunción con la arquitectura, o no: DSM, mensajes en SMP
Entornos Operativos para la Gestión de Recursos ...
31
UPC/DAC Tardor 2.002
INTRODUCCIÓN
Modelo de proceso y modelo de thread
Shared memory
fork()
thread_create()
pc
Procesos y memoria
compartida explícita
pc
sp
sp
pc
sp
Threads: compartición implícita
Entornos Operativos para la Gestión de Recursos ...
32
UPC/DAC Tardor 2.002
Ejemplo de aplicación multiflujo
petición
cálculo
creación
I/O
I/O
fin
Usuario
excepción
upcall
llamada al sistema
Kernel
kernel
thread
Entornos Operativos para la Gestión de Recursos ...
33
UPC/DAC Tardor 2.002
Máquinas reales
Máquinas paralelas
• Memoria local (multicomputadores)
• Memoria local al procesador
• Red de interconexión variada
• Gestión de la comunicación por hardware (ie. transputers)
M
P
M
P
P
M
P
M
• Generalmente SIMD, por no necesitar compartición de datos.
• Computadores “masivamente paralelos”
• cálculo intensivo
Entornos Operativos para la Gestión de Recursos ...
34
UPC/DAC Tardor 2.002
Máquinas reales
Procesadores de memoria local
MIMD de memoria distribuida
Multiprocesador SIMD
P
M
MP
PM
M
P
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
P/M
Entornos Operativos para la Gestión de Recursos ...
........
....
....
...
...
........
........
...
...
...
...
Front End
35
UPC/DAC Tardor 2.002
Máquinas reales
Máquinas paralelas
• Multiprocesadores de memoria compartida
• Memoria visible y accesible por todos los procesadores
• Modelo natural para MIMD
P
P
P
...
P
Shared Memory
• Contención en memoria: diversificar en módulos.
• Contención en el bus: memorias locales cache.
Entornos Operativos para la Gestión de Recursos ...
36
UPC/DAC Tardor 2.002
Máquinas reales
Memorias cache
Memoria
cache
cache
CPU
CPU
• Cache de instrucciones: muy efectivo en multiprocesadores de memoria compartida.
• Cache de datos: problemas de coherencia en los accesos de escritura.
Entornos Operativos para la Gestión de Recursos ...
37
UPC/DAC Tardor 2.002
Máquinas reales
Redes de workstations
• Paralelismo a través de la red
• Gestión de la comunicación por software: protocolos de comunicación
• Criticalidad: tiempo de comunicación/ejecución entre comunicaciones
Pool compartido de recursos:
Procesadores, memoria, discos
workstation
Entornos Operativos para la Gestión de Recursos ...
workstation
....
workstation
38
UPC/DAC Tardor 2.002
Máquinas reales
Otros trabajos paralelos a través de la red: videoconferencia
Cámara
Cámara
Monitor
Monitor
Micrófono
Micrófono
Workstation
Altavoz
Workstation
Red
Altavoz
Aplicación
paralela
Entornos Operativos para la Gestión de Recursos ...
39