1

5. UNIDADES DE PROGRAMAS

2

Uso de mecanismos de control de secuencia de:

Invocaciones Retornos

Entre:PP SP1a)

I

R

SP1 SP2b)I

R

Unidades subordinadas

3

Se establece una estructura jerárquica entre las unidades Durante la ejecución, un PP puede llamar a múltiples SPs Cada SP puede, a su vez, llamar a otros SPs Al terminar la ejecución de un SP, se debe retornar el

control a la unidad que lo invocó Cada SP se puede desarrollar en forma independiente del

resto de las unidades y cumple un objetivo bien definido La ejecución de la unidad que invoca se suspende

mientras se ejecuta la unidad invocada Al terminar la ejecución de un SP, la unidad que lo invocó

continúa ejecutándose desde el punto inmediatamente posterior al de la llamada al SP

Unidades subordinadas

4

La definición del SP corresponde al código fuente a ser traducido por el compilador

La activación del SP corresponde al uso o invocación del SP durante ejecución

SP

Subprogramas

5

Invariante Código ejecutable Almacenado en RAM en

una parte fija Se usa pero NO se

modifica durante la ejecución

Cada activación del SP utiliza el mismo segmento de código

Variable Contiene los datos

necesarios para ejecutar el SP

Parámetros formales Variables locales Dirección de retorno Valor de retorno* Enlace dinámico*

ACTIVACIÓN

SEGMENTO DE CÓDIGO

REGISTRO DE ACTIVACIÓN

Subprogramas

6

Para un subprograma SVariables locales

Son los datos declarados al interior de S, es decir, aquellos pertenecientes al registro de activación del S

Variables globales Son los datos declarados en una unidad de

jerarquía superior, los cuales pueden ser referenciados en S pues pertenecen al registro de activación (RA) de otro SP que permanece activo mientras se ejecuta S

Variables locales y globales

7

Objetos de datos a los cuales puede acceder una unidad de programaEl entorno de referencia correspondiente a la activación de cierta unidad S, está conformado por

Entorno Local

Entorno Global

ODD contenidos en el RA de S

ODD contenidos en los RAs de otras unidades

activas

Entorno de referencia

8

Existen diferentes semánticas de solución al problema del compromiso entre activación y código-RA. Las más significativas, por su connotación conceptual, son las conocidas como:

Estructura modo FORTRAN Estructura modo ALGOL

Registros de activación

9

Mientras se encuentra activo un SP, NO puede ser activado nuevamente

Para cada unidad, durante compilación, se genera, estáticamente,

el segmento de código y

el registro de activación

Sin importar que el SP sea o no activado, su RA permanece ligado al código durante TODA la ejecución del programa

PP

R1

Datos

R2

R3

Estructura FORTRAN

10

Todas las invocaciones de un SP utilizan el mismo RA, debido a lo cual permanecen los valores que tomaron los datos en la mas reciente activación

El entorno de referencia de un SP se reduce sólo al entorno local

Los SPs pueden acceder a variables globales declaradas mediante COMMON, las cuales se consideran pertenecientes a un RA global para todas las unidades

No soporta recursividad

PP

R1

Datos

R2

R3

Estructura FORTRAN

11

Call A

PP

d0:

A

Call Bd2:

d1:

Goto d1

Goto d0

B

Call Cd4:

Goto d3

d3: Goto d2

C

Goto d5

d5: Goto d4

Estructura FORTRAN

12

Call A

PP

d0:

A

Call Bd2:

d1:

Goto d1

Goto d0

B

Call Cd4:

Goto d3

d3: Goto d2

Loop!!!

d6C

Goto d5

d5: Goto d4

Call Bd6:

Estructura FORTRAN

13

Un código fuente puede constar de unidades

disjuntas (C), o bien

anidadas (Pascal)

El ámbito de una variable x declarada en cierta unidad S es:

S, y

todas las unidades al interior de S, para las cuales x tiene el carácter de global

Estructura ALGOL PP

T

S

R

14

El tamaño del RA de un SP S se determina en tiempo de compilación

El RA de S es ligado dinámicamente al respectivo código con cada nueva activación, es decir,

se crea cada vez que S es invocado y

se destruye cada vez que S transfiere el control a quien lo invocó

Las activaciones se rigen por el comportamiento LIFO el control se logra mediante un stack de RAs, forma natural de soporte de la recursividad

Estructura ALGOL PP

T

S

R

15

A

PP

d0:

A

Bd2:

d1:B

Cd4:

d3:C

d5:

d0

d2

d4

Estructura ALGOL

16

A

PP

d0:

A

Bd2:

d1:B

Cd4:

d3:

d0

d2

d4

B

Cd5:

d6:

d6

Estructura ALGOL

17

Área de datos

estáticos

Área de datos

automáticos

Área de datos

dinámicosHeapStack

Estructura ALGOL

Áreas de memoria

18

d0

d2

d4

d6

Almacenamiento contiguo

El tamaño de los RAs es variable, pero conocido

Los RAs se almacenan en el área de datos automáticos

RA PP RA A RA B RA C

Estructura ALGOL

19

d0

d2

d4

d6

Los RAs se almacenan en el área de datos dinámicos, es decir, el Stack se representa al interior del Heap

Cada RA debe incluir un enlace dinámico que apunte al RA precedente

Estructura ALGOL

d6 d4 d2 d0

20

La comunicación entre unidades de programa se efectúa mediante parámetros:

formales o de definición y

actuales o de invocación

Los parámetros permiten la variabilidad de los datos transferidos en diferentes instancias de activación

Los parámetros formales constituyen parte del RA

Invocaciones explícitas

21

Los parámetros actuales y formales establecen entre sí una relación de correspondencia posicional o nominal

En correspondencia posicional los parámetros se asocian según el orden en que aparecen (Pascal y C)

En correspondencia nominal los parámetros se asocian según una indicación explícita de nombres. Si, en lenguaje Ada se define

procedure P(Limite: in integer; Tabla: in out Arreglo)

entonces, se puede invocar

P(Tabla is V, Limite is N)

Invocaciones explícitas

22

Una excepción es es un evento que impide la continuidad de ejecución de un programa

Las excepciones proporcionan una manera limpia de verificar errores

Se puede capturar y manejar una excepción en un intento por evitar que se detenga la ejecución del programa

Las unidades que se activan implícitamente al detectarse una irregularidad se denominan manejadores de excepciones

Invocaciones implícitas

23

// Ejemplo en Javatry {// Código que puede generar excepciones} catch (TipoException1 e_1) {// Controlador de excepciones de tipo 1} catch (TipoException1 e_2) {// Controlador de excepciones de tipo 2}....catch (TipoException1 e_n) {// Controlador de excepciones de tipo n} finally {// Trozo de código que se ejecutará siempre}

Invocaciones implícitas

24

Son unidades que se activan en forma mutua, alternada y explícita

Tienen un comportamiento cooperativo secuencial

También se les conoce como corrutinas

Son útiles para

simular eventos discretos

implementar servidores

Las proveen los lenguajes Algol, Simula, Ada, Modula y Occam

Unidades simétricas

25

Ejemplo en Algol

corroutine X;begin ··· resume Y; ··· resume Y; ···end;

corroutine Y;begin ··· resume X; ··· resume X;end;

resume Y

resume Y

corroutine X

resume X

resume X

corroutine Y

Unidades simétricas

26

Mediante "resume Y", la corrutina X le transfiere el control a la corrutina Y

Cada instancia de "resume Y" activa la corrutina Y a partir de una nueva dirección de inicio, es decir, de una dirección de reinicio (DR de Y)

La ejecución de "resume Y" en X provoca dos acciones:

Almacenar, en el RA de Y, como DR de X la dirección de la sentencia inmediatamente posterior a "resume Y"

Capturar, en el RA de X, la DR de Y a partir de la cual debe continuar la ejecución

Unidades simétricas

27

Proceso es una unidad de código en lenguaje de máquina, la cual se encuentra en ejecución

Proceso pesado (o simplemente proceso) es una unidad que cuenta con un contador de programa, un stack, un conjunto de registros, un espacio de direcciones, procesos hijos, descriptores de archivos, señales, semáforos, relojes e indicadores estadísticos

Proceso liviano (o hilo) es un miniproceso contenido en un proceso, el cual se ejecuta en modo estrictamente secuencial y cuenta con un contador de programa, un stack, un estado, registros e hilos hijos

Unidades concurrentes

28

Desde la aparición de las arquitecturas multiprocesadoras, se han propuesto variados modelos de ejecución simultánea, sintetizados en tres niveles de paralelismo:

Paralelismo a nivel de bloques

Granularidad fina

Paralelismo a nivel se subprogramas

Granularidad media

Paralelismo a nivel de programas

Granularidad gruesa

Unidades concurrentes

29

Procesos paralelos (PPs) son aquellos procesos que se pueden ejecutar, conceptualmente, en forma simultánea

PPs disjuntos son aquellos procesos paralelos que, durante su ejecución, no acceden a recursos compartidos

PPs concurrentes son aquellos procesos paralelos que, durante su ejecución, interactúan compitiendo por el acceso a recursos compartidos y cooperando para alcanzar un objetivo común

Requieren una adecuada sincronización entre ellos

Unidades concurrentes

30

En un proceso concurrente, región crítica es el segmento de código en el cual se accede a recursos compartidos

Cuando un proceso concurrente ejecuta su región crítica, los demás procesos no pueden ejecutar la propia

Exclusión mutua

Sincronización

Semáforos

Monitores

Rendezvous

Unidades concurrentes

31

Semáforo

Mecanismo de bajo nivel, definido como un dato entero no negativo sobre el que actúan las operaciones atómicas P y V

Monitor

Mecanismo de alto nivel, definido como un objeto con uno o más procedimientos, datos locales y código de inicialización

Rendezvous

Primitiva de comunicación de datos entre un conjunto de procesos, mediante el paso de mensajes en modo síncrono

Unidades concurrentes