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