1 5. unidades de programas. 2 unidades de programas estudiar mecanismos de control de secuencia:...
Post on 22-Jan-2016
221 Views
Preview:
TRANSCRIPT
1
5. UNIDADES DE PROGRAMAS
2
Unidades de programas
Estudiar mecanismos de control de secuencia:
Invocaciones
Retornos
Entre:PP SPa)
I
R
SP1 SP2b)I
R
3
Unidades subordinadas Considera un estructura jerárquica entre las
unidades (árbol).
Un PP, durante la ejecución, puede llamar a varios SP.
Estos SP pueden, a su vez, llamar a otros SP, y así sucesivamente.
Al término de la ejecución de un SP, debe retornar el control al PP o SP que lo invocó.
Se pueden desarrollar en forma independiente del PP u otro SP y cumplen un objetivo bien definido.
4
Unidades subordinadas La ejecución del programa invocador se detiene
temporalmente, mientras se ejecuta un SP.
El punto inmediatamente siguiente a la llamada al subprograma.
Al terminar la ejecución de un SP, continúa la ejecución del programa invocador en :
5
Subprogramas
La definición del SP corresponde al código que es traducido por un compilador o intérprete
S P
La activación del SP corresponde al uso o invocación del SP durante la ejecución.
6
Activación
SEGMENTO DE CÓDIGO Invariante
Código ejecutable Almacenado en parte fija
de la RAM En la ejecución, se usa
pero NO se modifica. Cada activación del SP
utiliza el mismo segmento de código.
Contenido variable.
Contiene información necesaria para ejecutar el SP
Parámetros formales
Variables locales
Dirección de retorno.
*Valor de retorno.
ACTIVACIÓN
REGISTRO DE ACTIVACIÓN
7
Variables locales
Corresponde a los datos declarados al interior de un subprograma
Pertenecen al registro de activación de la rutina en la que fueron declarados
8
Variables globales
Corresponde a los datos declarados en OTRA rutina
Pueden ser referenciadas por el SP
Pertenecen al registro de activación de otra rutina que está activa durante toda la ejecución del SP.
9
Entorno de referencia
Objetos a los que una unidad puede acceder
Para una activación de una unidad S:
entorno de referencia
Entorno Local
Entorno Global
ODD contenidos en el RA de S
ODD contenidos en OTROS RA de unidades activas
10
Ejemplo
PPVar x,y: Integer;
Rutina UnoVar a,b: Real;
Rutina DosVar z,a: Integer;
End;
End;Rutina TresVar c,d: Char;
End;End.
x:y:
Uno
Tres
a:b: Dos
z:a:
c:d:
PP
11
Entornos de referencia
x:y:
Uno
Tres
a:b: Dos
z:a:
c:d:
PP1. PP: x,y
2. Uno: EG x,y EL a,b
4. Tres: EG x,y EL c,d
3. Dos: EG x,y,b EL z,a
No se tendrá acceso a la vble a de Uno
12
Motivación
¿Cómo resuelven los LP semánticamente la problemática entre:
activación y código-RA
Estructuras tipo FORTRAN
Estructuras tipo Algol
13
Estructuras tipo FORTRAN
Explicación: La regla de la copia
A lo más UNA activación de cualquier SP está en uso en cuaquier momento de la ejecución del PP
Al compilar, en forma estática, se le asigna a la unidad de programa:
El segmento de código
El registro de activación (RA)
El RA forma parte del Segmento de código (en el bloque)
El RA permanece ligado al SP durante TODA la ejecución del programa, aunque la unidad NO esté activa
PP
R1
Datos
R2
R3
14
Estructuras tipo FORTRAN
El mismo RA se utiliza repetidamente en cada invocación
El ámbito de una variable se reduce a la unidad en la que fue declarada.
Las unidades pueden tener acceso a variables globales, utilizando la sentencia COMMON. Estas variables son tratadas como si pertenecieran a un RA global para todas las unidades.
PP
R1
Datos
R2
R3
15
Características
Este método resuelve en forma simple el problema de la relación: Registro de Activación-Unidad
Permite una ejecución eficiente
Consume mucha memoria
No permite recursividad
El tamaño de registro de activación se determina en tiempo de compilación.
PP
R1
Datos
R2
R3
16
Llamadas
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
17
Recursividad Indirecta
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:
18
Estructuras tipo Algol
Datos declarados en una unidad no son accesibles por otras
Unidad contenida en otra.
La unidad más interna tiene acceso a los datos de las unidades que la contienen. (EG)
El código fuente puede tener
Unidades Disjuntas
C
Unidades Anidadas
Pascal
PP
X
Y
Z
Contexto de validez o ámbito de una vble: La unidad que la declara: U
Todas las unidades al interior de U, para las cuales la vble tiene caracter de global.
19
Características
Las variables locales se crean implícitamente (en forma automática) al activarse la unidad.
La cantidad de almacenamiento requerido por las variables locales se determina en tiempo de compilación.
El tamaño del registro de activación se determina en tiempo de compilación, al igual que en FORTRAN
El Registro de Activación es asignado y ligado dinámicamente al respectivo código con cada nueva activación.
El RA se crea cada vez que un programa llama a la unidad
El RA es destruido cuando se retorna al programa invocado
20
Características Cont...
El tratamiento de los RA es de tipo LIFO (last in-first out), por lo que la estructura de soporte es el stack, lo que favorece la implementación de algoritmos recursivos.
Sintácticamente, las llamadas ordinarias y las recursivas, son iguales
La llamada recursiva crea una segunda activación del SP durante la existencia de la primera.
Si la segunda activación realiza otra llamada recursiva, se crea una tercera activación para el SP, y así sucesivamente...
Pueden existir varias activaciones para el mismo SP
21
Llamadas
Call A
PP
d0:
A
Call Bd2:
d1:B
Call Cd4:
d3:C
d5:
d0
d2
d4
22
Llamadas Recursivas
Call A
PP
d0:
A
Call Bd2:
d1:B
Call Cd4:
d3:
d0
d2
d4
Call B
Cd5:
d6:
d6
23
Cadena dinámica
d0
d2
d4
d6
Cadena de punteros que enlazan las activaciones del SP, en el orden de su creación dinámica durante la ejecución del programa
24
Áreas de Memoria
Área de datos
estática
Área de datos automáticos
Área de datos Dinámicos
HeapStack
25
Stack de RA estático
d0
d2
d4
d6
Almacenamiento contiguo.
El tamaño de los RA es variable, pero conocido.
Los RA se almacenan en el área de datos automáticos.
RA PP RA A RA B RA C
26
Stack de RA dinámico
d0
d2
d4
d6
Almacenamiento en área heap. (datos dinámicos)
d0 d2 d4 d6
Se debe tener en cuenta el "enlace dinámico" que se agrega a todos los RA.
27
Invocaciones explícitas
Comunicación entre unidades de programa
Los parámetros permiten la variabilidad de los elementos transferidos en diferentes llamadas.
Los parámetros formales constituyen parte del registro de activación.
mediante
parámetros.
Actuales (argumentos)Formales
28
Modalidades
Relación entre parámetros actuales y formales:
Correspondencia posicional
Los argumentos se corresponden uno a uno con los parámetros de la declaración de la rutina. La más utilizada por los LP
Correspondencia nominal
Se indica explícitamente en la invocación la correspondencia entre parámetros actuales y formales.
29
Ejemplos
Correspondencia posicional (Pascal, C)
Procedure Suma(a,b:Integer; x:Real)Definición:
Suma(r,t,s)Invocación:
procedure Inicializar(Limite: in integer; Tabla: in out Arreglo);
Definición:
Invocación:
Inicializar (Tabla is V, Limite is N);
Correspondencia nominal (Ada)
PA
30
Invocaciones implícitas
Condición de excepción
Invocación implícita a una unidad
Excepción:
Condición que marca un suceso inusual o no esperado durante la ejecución del programa
realizar una acción especial
Las unidades que se activan cuando se detecta alguna irregularidad se denominan manejadores de excepciones
31
Invocaciones implícitas
Permite excluir aquellos errores que podrían desviar la atención del objetivo principal del programa.
Los lenguajes tienen excepciones pre-definidas (entrada-salida, rangos de índice, almacenamiento dinámico, etc)
Algunos LP permiten declarar otras excepciones, específicas para el programa en construcción. Éstas deberán ser "invocadas" en forma explícita:
raise <nombre de la excepción>
32
EjemploSe desea abrir un archivo para lectura en Pascal. La excepción se producirá si éste no ha sido creado, o bién, no está en el directorio indicado
Assign(ent,"c:\ejemplos\Tarea1"{$I-}Reset(ent);{$I+}x:=IOResult();if (x<>0)then
Writeln("Archivo NO existe");elseBegin
Reset(ent);While (Not Eof(ent)) doBegin
Read(ent,r);:
End
Permite atrapar el error
33
Ejemplos
try-end exception....when exception On condition ....
34
Unidades Simétricas (Corrutinas)
Unidades que se activanmutua,
alternada y
explícitamente.
No existe una relación jerárquica entre los SP
Ambos SP son equivalentes: Se traspasan el control uno a otro y ninguno controla al
otro.
35
Unidades Simétricas (Corrutinas)
Cuando una corrutina (Y) recibe el control desde otra corrutina (X), ésta se ejecuta parcialmente, y se detiene al retornar el control a la corrutina invocadora (X), utilizando la sentencia resume.
Más tarde, si la corrutina (X) pasa nuevamente el control a la corrutina (Y), (resume) ésta comienza su ejecución desde el punto en que fue anteriormente detenida.
36
Unidades Simétricas (Corrutinas)
corroutine X;begin ··· resume Y; ··· resume Y; ···end;
corroutine Y;begin ··· resume X; ··· resume X;end;
El código, :
Resume Y
Resume Y
Corrutina X
Resume x
Resume x
Corrutina y
Modula-2 - Algol68
37
Resume
La sentencia "resume" tiene un comportamiento similar al de una sentencia "call" con la salvedad de que el punto de entrada a la corrutina es variable.
PF
D reinicio x
VL
D reinico y
RA:
38
Resume
La ejecución de una sentencia "resume y" en X involucra dos acciones:
Almacenar en la dirección de reinicio la dirección de la sentencia inmediatamente posterior a resume Y.
Accesar la dirección de reinicio de Y para obtener la dirección en la cual debe continuar la ejecución.
39
Procesos paralelos:
Unidades Concurrentes
Procesos que se pueden ejecutar en forma, conceptualmente, simultánea.
Procesos paralelos: Disjuntos
Procesos que durante la ejecución, no acceden a recursos compartidos.
Procesos paralelos: Concurrentes
Durante ejecución, interactúan compitiendo por el acceso a recursos compartidos y cooperando para alcanzar un objetivo común.
Compartir!!!
Cada proceso tiene acceso a los mismos recursos pero sólo uno a la vez
40
La ilusión de ejecución concurrente en monoprocesadores
Unidades Concurrentes
Se ejecuta sólo una parte del código de cada proceso
Intercalando la ejecución de procesos independientes
se logra
41
1. La sentencia and (evaluación completa)
Ejemplo
If (sentencia-1 and sentencia-2 and ... and sentencia-n)
Cada sentencia-i puede ser ejecutada en paralelo
La siguiente sentencia (a If) no podrá ser ejecutada mientras NO finalice la ejecución de las n sentencias-i
42
Ejemplo
y puede finalizar con valor 2:
si se ejecuta primero (y:=x+x) y luego (x:=2)
x:=1;
if (x:=2) and (y:=x+x)...
print y;
Las sentencias (x:=2) y (y:=x+x) pueden ser ejecutadas en paralelo:
y puede finalizar con valor 4:
si se ejecuta primero (x:=2) y luego (y:=x+x)
y puede finalizar con valor 3:
si la asignación (x:=2) se realiza entre los dos accesos a x en (y:=x+x)
Siempre debiera dar el mismo valor
43
Los procesos concurrentes
Unidades Concurrentes
Mecanismos de sincronizaciónMedios utilizados para que un proceso pueda
informar a otro si completó o no parte de la ejecución de su código crítico.
una adecuada sincronización entre ellos.
requieren
Asegurar que ningún otro proceso entre a su región crítica si el proceso en ejecución, que usa los recursos compartidos, está en su región crítica
Parte del código en el que accede a
datos compartidos
Semáforos
Monitores
Randezvous
44
Mecanismos de sincronización
Semáforos (Algol, Dijkstra)
Mecanismo de bajo nivel
Se define como un objeto de dato que toma valores enteros no negativos (contador)
Posee un valor inicial y dos operaciones atómicas P y V (Up, Down)
45
Mecanismos de sincronización
Monitores (TAD)
Módulo separado que coordina procesos en ejecución.
TAD con operadores que consideran la exclusión mutua (Si un proceso está en su región crítica, ningún proceso puede entrar el la suya).
Contiene una cola de solicitudes de acceso.
Este mecanismo puede hacer esperar la ejecución de una rutina (delay) hasta que esté disponible el recurso y entonces "reavivar" el proceso. (continue).
46
Mecanismos de sincronización
Randezvous (Ada)
Es un punto de reunión que incluye:
Sincronización Comunicación Ejecución
de un bloque de código de procesos concurrentes
Coordina las llamadas de procedimientos remotos:
Cliente
Servidor
top related