Construção de ficheiros executáveis
Compilação
Ligação
Carregamento (loading)
Bibliotecas estáticas e dinâmicas
Construção do executável
1
Construção e execução de programas
Unidades de
compilação
Memória
(espaço lógico ou virtual)
00101
11010
00101
obj
Compilador
00101
11010
00101
stack
Linker
00101
11010
00101
obj
exe
00101
11010
00101
obj
Ficheiros
fonte
código
Loader
dados
Bibliotecas
externas
00101
11010
00101
lib
Construção do executável
2
Ligação de unidades de compilação
Exportações
x
Recolocações
x
Código
main:
...
r1  &foo
...
call foo
...
r2  x (300)
...
Dados
...
x:
...
...
void foo( )
{
y = x;
...
bar( )
}
void bar( )
{
...
}
Construção do executável
Importações
x
Exportações
foo
bar
y
Recolocações bar
y
600h
400h
500h
300h
800h
void main( )
{
...
foo( )
...
x = ...
...
}
400h
foo
...
int y;
1000h
Importações
1600h
...
int x;
Código
foo:
r1  x
r2  y (400)
...
call bar (1000)
...
bar:
...
Dados
...
y:
...
3
Ligação de unidades de compilação (cont.)
Código
main:
...
r1  &foo (c00)
...
call foo (c00)
...
r2  x (2300)
...
foo:
r1  x (2300)
r2  y (2900)
...
call bar (1800)
...
bar:
...
Dados
...
x:
...
y:
...
Construção do executável
Memória
(lógica ou virtual)
Serviços do SO
Stack
“Loading”
Heap
4 GB
1800h
b00h
900h
300h
2000h
1e00h
c00h
Imagem executável
bibliotecas
dinâmicas
Dados
endereços
crescentes
Código
4
Bibliotecas estáticas e dinâmicas

Bibliotecas estáticas
 O código é incorporado no ficheiro executável pelo “linker”
 Se a mesma biblioteca for usada por vários programas o código é repetido
nos ficheiros executáveis
 O código também é repetido na memória nos vários processos que as
utilizarem
 Simples de criar e com execução ligeiramente mais rápida

Bibliotecas dinâmicas
 O código reside apenas no ficheiro da biblioteca
 É carregado e mapeado no processo quando da execução de um programa
 O código é partilhado por todos os processos que o utilizam (pode haver
diversas cópias dos dados)
 “Loading” e inicialização mais complicados e demorados
 Ligeiramente menos eficientes
Construção do executável
5
Bibliotecas dinâmicas
Memória lógica
(processo 1)
Mapeamento
(tabelas de
páginas)
Memória física
.
.
.
Dados DLL
Código DLL
Mapeamento
(tabelas de
páginas)
Memória lógica
(processo 2)
Dados DLL
Dados proc. 2
Código DLL
Dados proc. 1
Código DLL
Dados
Dados
.
.
.
Código
Construção do executável
Código
6
Bibliotecas dinâmicas - implementação
...
---call foo:
push gp
t9  *(gp+A)
jalr t9
pop gp
D
---load x:
t0  *(gp+C)
E
...
foo:
gp  t9+E-D
...
...
---load y:
t0  *(gp+F)
t0  *t0
...
código da DLL
(partilhado)
---load y:
t0  *(gp+B)
t0  *t0
...
gp
gp
B A
tabela de
ligação
(linkage table)
C
x
F
1 cópia por
processo
(adjacente)
y
Construção do executável
1 cópia por
processo
7
Organização da memória em run-time
Memória de dados
Registos de activação
Procedimentos embutidos e acessos não locais
Passagem de parâmetros
Organização da memória em run-time
8
Execução de programas

Geralmente é possível fazer as seguintes suposições acerca da
execução de um programa:
 Alguns blocos de código constituem procedimentos (ou funções) que
podem ser invocados de diversos locais no programa;
 Quando um procedimento é invocado, o controlo regressa após a sua
execução, ao ponto imediatamente após a invocação;




Esta suposição leva a que o fluxo de controlo entre procedimentos possa ser
modelizado através de uma árvore.
Os procedimentos podem conter dados locais e também (de
forma embutida) outros procedimentos (nalgumas linguagens).
Durante a execução de um procedimento constitui-se o que se
designa por uma activação do procedimento.
Num dado instante podem existir várias activações de
procedimentos (inclusivé do mesmo, em linguagens recursivas).
Organização da memória em run-time
9
Algumas definições

Tempo de vida de uma activação de procedimento: intervalo
durante o qual essa activação existe; compreende:
 a execução de todas as instruções do procedimento;
 os tempos de vida das activações dos procedimentos invocados por ele.



Tempo de vida de uma variável: intervalo durante o qual existe
o espaço de memória necessário ao armazenamento dos valores
associados à variável; se a variável for local a um
procedimento, a regra é fazer corresponder o seu tempo de vida
ao tempo de vida da activação do procedimento (há excepções).
A associação de um nome ao local de armazenamento, e a
associação deste local ao seu conteúdo (valor), designam-se
genericamente por binding (ligação) da variável.
O scope (alcance) de uma variável, é o conjunto de locais, no
código, onde é possível aceder a essa variável.
Organização da memória em run-time
Noções estáticas
Noções dinâmicas (execução)
procedimento
nome
scope
activação
binding
tempo de vida
10
Exemplo
program sort;
var a : array[0..10] of integer;
procedure readarray;
var i : integer;
begin
for i:=1 to 9 do read(a[i])
end;
s
r
p(1,9)
function partition(y, z : integer) : integer;
var i, j, x, v : integer;
begin …
end;
procedure quicksort(m, n : integer);
var i : integer;
begin
if (n > m) then begin
i := partition(m, n);
quicksort(m, i-1); quicksort(i+1, n)
end
end;
begin
a[0] := -9999; a[10] := 9999;
readarray;
quicksort(1, 9)
end.
q(1,9)
q(1,3)
q(5,9)
p(1,3) q(1,0) q(2,3)
p(5,9) q(5,5) q(7,9)
p(2,3) q(2,1) q(3,3)
p(7,9) q(7,7) q(9,9)
Árvore de activação para o programa escrito ao lado
Em cada instante só existem os registos de activação de
procedimentos que estão no caminho desde a raiz até ao
que está em execução no momento.
Quando a activação da chamada quicksort(2,3) (q(2,3)) está
em execução apenas existem as activações de s, q(1,9) e
q(1,3).
Organização da memória em run-time
11
Organização da memória de dados

A organização da memória de dados depende grandemente da
resposta às seguintes perguntas, para uma dada linguagem:
 A linguagem é recursiva ?
 O que acontece aos nomes locais quando termina a activação de um
procedimento ?
 Um procedimento pode aceder a nomes não locais ?
 Como são passados os parâmetros de um procedimento ?
 É possível passar procedimentos como parâmetros ?
 É possível retornar um procedimento como resultado ?
 É possível alocar memória dinamicamente ?
 É necessário libertar explicitamente memória alocada dinamicamente ?

Para a maioria das linguagens actualmente em utilização, as
activações dos procedimentos é perfeitamente embutida pelo
que é comum adoptar-se uma organização geral destas
activações baseada numa stack (geralmente suportada
directamente pelo hardware do processador).
Organização da memória em run-time
12
Organização da memória de dados (cont.)
Dados estáticos - Esta parte da memória contém os
dados globais (constantes e variáveis inicializadas ou
endereços
não) cujo tamanho pode ser determinado inteiramente
mais altos
durante a compilação. Na compilação geram-se
apenas “offsets” para o início desta área de memória.
stack
Stack - Implementado no stack suportado
directamente pelo processador; contém os
chamados registos de activação dos procedimentos,
refletindo a estrutura intrínseca das suas chamadas e
retornos; as variáveis locais dos procedimentos são
criadas e destruídas nesta área.
heap
dados estáticos
ou globais
Heap - Área utilizada para todo o restante
armazenamento de dados. São colocados aqui os
dados alocados dinamicamente, ou variáveis locais
cujo tamanho só é conhecido durante a execução, ou
ainda cujo tempo de vida não se coaduna com o
armazenamento nos registos de activação.
Organização da memória em run-time
endereços
mais baixos
código
13
Registos de activação
apontador de controlo
Chamada de procedimento:
…
push parn
…
push par1
push access
call proc
add sp,n1
…
valor de retorno
parâmetros
do
procedimento
No procedimento proc:
apontador de acesso
push bp
mov bp,sp
sub sp,n2
pusha
…
…
popa
add sp,n2
pop bp
ret
endereço de retorno
código de
entrada
registo de
activação
apontador de controlo
chamador
hardware
frame pointer
(bp)
dados locais
chamado
temporários
código
de saída
salvaguarda
de registos do
processador
stack pointer
(sp)
Organização da memória em run-time
14
Alocação de registos de activação

Consideram-se geralmente três estratégias diferentes para
alocação dos registos de activação dos procedimentos:
 Alocação estática, onde os registos de activação de todos os
procedimentos são colocados na zona de dados estáticos;
Este tipo de alocação só é possível se a linguagem não for recursiva e
mantiver os valores das variáveis locais de umas chamadas para as
outras;
 Alocação na stack, a mais geralmente utilizada;
 Alocação no heap, necessária para quando o tempo de vida das variáveis
locais ultrapassa o da activação do respectivo procedimento, ou quando
Considere-se o seguinte código em pseudo-C:
este ultrapassa o do chamador.
O registo de activação de f() não pode ser
descartado após as chamadas f(3) e f(4),
porque a função g() no seu interior depende
do parâmetro com que f() foi chamado.
A linguagem ML permite estas construções.
Organização da memória em run-time
int (*)() f(int x) {
int g(int y) {return x+y}
return g;
}
main() {
int (*h)() = f(3);
int (*j)() = f(4);
int z = h(5);
int w = j(7);
}
15
Alocação na stack
 É a forma mais utilizada de alocação dos
registos de activação;
 Pode requerer espaços para a stack
consideráveis;
 Os parâmetros devem ser colocados na
stack pela ordem inversa, se se
permitirem definições de procedimentos
com número variável de argumentos (a la
C);
 Requer acesso indirecto se existirem
parâmetros cujo comprimento dependa de
um valor passado como parâmetro (ex:
passagem de arrays em Algol e arrays
conformantes em Pascal).
valor de retorno
parâmetros
do
procedimento
apontador de acesso
endereço de retorno
apontador de controlo
apontador para A
frame pointer
(bp)
dados locais
temporários
salvaguarda
de registos do
processador
array A
stack pointer
(sp)
procedure p(A : array[ j..k : integer ] of integer )
begin
var i : integer;
for i := j to k do
A[ i ] := 2*i;
end;
Organização da memória em run-time
16
Acesso a variáveis não locais


Grande parte das linguagens utiliza o que se designa por
estrutura de blocos; os blocos estão embutidos uns nos outros;
O scope (alcance) de uma variável, numa estrutura de blocos,
está sujeito à regra do embutimento mais próximo. Assim:
 O scope de uma declaração num bloco B abrange todo o bloco B;
 Um nome x, acedido em B mas não declarado em B, pertencerá ao scope
de uma declaração de x num bloco mais externo B’, que contenha essa
declaração e seja o bloco mais próximo de B (de dentro para fora)

Algumas linguagens não permitem o embutimento de funções
B0
B1
main() {
int a, b;
{ int b;
{ int a;
B2
…}
{ int b;
B3
…}
…}
…}
Neste tipo de blocos inseridos dentro dos
procedimentos, só existe um registo de activação
para todos os blocos:
Organização da memória em run-time
a0
Variáveis locais a
main( )
b0
b1
a2, b3
17
Acesso a variáveis não locais (embutidas)
Nas linguagens em que é permitido o embutimento de
procedimentos há necessidade de aceder a variáveis
locais existentes em registos de activação anteriores.
program sort;
var a : array[0..10] of integer;
x : integer;
Esses registos são acedidos através de um apontador
de acesso que funciona como mais um parâmetro
(escondido) nas chamadas dos procedimentos.
procedure readarray;
var i : integer;
begin … a … end;
No entanto esses registos podem não estar contíguos
na stack. Vejam-se os seguintes exemplos:
procedure exchange(i, j : integer);
begin
x := a[i]; a[i] := a[j]; a[j] := x
end;
s
nil
a, x
q(1, 9)
acesso
k, v
s
nil
a, x
q(1, 9)
acesso
k, v
q(1, 3)
acesso
k, v
s
nil
a, x
q(1, 9)
acesso
k, v
q(1, 3)
acesso
k, v
p(1, 3)
acesso
i, j
s
nil
a, x
q(1, 9)
acesso
k, v
q(1, 3)
acesso
k, v
p(1, 3)
acesso
i, j
e(1, 3)
acesso
Organização da memória em run-time
procedure quicksort(m, n : integer);
var k, v : integer;
function partition(y, z : integer) : integer;
var i, j : integer;
begin
… a … v … exchange(i, j); …
end;
begin … end;
begin … end.
18
Uso dos apontadores de acesso
 Define-se profundidade de embutimento de um procedimento como o
número de níveis de embutimento que é necessário transpor para chegar a
esse procedimento; os procedimentos mais externos têm profundidade 1;
no exemplo anterior temos sort - 1, exchange - 2, e partition - 3.
 Estabelcimento dos apontadores de acesso:
Os apontadores de acesso são colocados na stack (registo de activação) pelo
procedimento chamador; Se o procedimento p com profundidade np chama o
procedimento x de profundidade nx então:
- para np < nx (deverá ser nx = np + 1) o apontador de acesso é o apontador de controlo
(frame pointer) actual;
- para np  nx o apontador de acesso a colocar na stack obtém-se seguindo np - nx + 1
apontadores de acesso, começando no do próprio procedimento; (ver figura anterior)
 Utilização dos apontadores de acesso:
O procedimento p com profundidade np pretende aceder a uma variável x, declarada num
procedimento com profundidade nx; deverá sempre ser np  nx;
- se np = nx, então x está no registo de activação corrente;
- se np > nx, então x está num registo de activação cujo endereço se obtém seguindo
np-nx apontadores de acesso, a partir do registo de activação actual. (ver figura anterior)
Organização da memória em run-time
19
Procedimentos como parâmetros
 Quando é possível passar procedimentos como parâmetros, o procedimento
passado pode não estar na cadeia de embutimentos do procedimento que o
vai usar; neste caso quando da passagem do procedimento, deve também
passar-se o apontador de acesso correspondente. Veja-se o exemplo
seguinte:
program param;
param
procedure b(function h(n: integer): integer);
begin writeln(h(2)) end;
c
procedure c;
var m: integer;
m
function f(n: integer) : integer;
begin f := m + n end;
b
<f, acesso>
begin m := 0; b(f) end
h=f
begin
c
end.
n
Organização da memória em run-time
20
Scope dinâmico
Certas linguagens não seguem as regras de scope enunciadas atrás (scope estático ou léxico), mas
determinam que quando há um acesso a uma variável não local, esse acesso refere-se a uma variável com o
mesmo nome que tenha sido criada o mais recentemente possível na stack.
Se o programa seguinte utilizasse este tipo de scope dinâmico, a sua saída seria:
0.250 0.125
0.250 0.125
A implementação deste scope dinâmico é imediata: em vez de se utilizarem os apontadores de acesso
utilizam-se os apontadores de controlo, que ligam os registos de activação pela ordem com que foram
criados; usa-se a variável que esteja definida no registo de activação que menos distar do actual.
program dynamic;
var r: real;
procedure show;
begin writeln(r:5:3) end;
procedure small;
var r: real;
begin r := 0.125; show end;
begin
r := 0.250;
show; small; writeln;
show; small; writeln
end.
Organização da memória em run-time
21
Passagem de parâmetros (1)

Passagem por valor
 Uma cópia dos valores dos parâmetros é colocada nos registos de
activação.

Passagem por referência
 Aquilo que é colocado nos registos de activação é o endereço do local onde
sencontram os valores dos parâmetros (variáveis simples); o acesso a
esses valores faz-se indirectamente; assim é possível passar para o
chamador novos valores através dos parâmetros.

Passagem por copy-restore linkage
 O chamador passa para os registos de activação os r-values dos
parâmetros, ao mesmo tempo que toma nota dos respectivos l-values;
quando a chamada regressa, e antes de eliminar os parâmetros, os
respectivos valores são colocados nos l-values anteriormente calculados.
Organização da memória em run-time
22
Passagem de parâmetros (2)

Passagem por nome
 Aqui o que é colocado nos registos de activação são subrotinas (thunks)
capazes de calcular o l-value e o r-value do parâmetro correspondente.
Sempre que há um acesso ao parâmetro essa subrotina é chamada. Tudo
se passa como se não houvesse qualquer chamada e o código chamado
fosse colocado directamente no local de chamada (como uma macro).
real procedure sum(expr, i, low, high)
value low, high;
real expr;
integer i, low, high;
begin
real rtn;
rtn := 0;
for i := low step 1 until high do
rtn := rtn + expr;
sum := rtn;
end sum
Organização da memória em run-time
...
y := sum(3*x*x-5*x+2, x, 1, 10);
...
y
2
3
x
  5x  2
1 x10
23