Roteiro de Aulas Teóricas- Software Básico

ATENÇÃO: O roteiro de aulas práticas está aqui.

17/08 e 19/08

Apresentação do Curso

programa do curso
critério de avaliação e DATAS DE PROVAS
bibliografia
introdução: hierarquia de abstrações em um sistema de computação

referência: Aho & Ullman, 4.2.

Representação de Dados

representação de inteiros não negativos: uso da base 2
representação de caracteres

24/08 e 26/08

Arquitetura Típica de uma Máquina

Elementos Básicos

CPU
memória principal
memória secundária
dispositivos de E/S

CPU

ALU
registradores
unidade de controle
- ciclo de instrução

Registradores no MIPS

32 registradores de propósito geral
convenções de uso facilitam entendimento de programas e interação entre rotinas escritas por diferentes programadores
registradores podem ser nomeados $r0,...,$r31, oude acordo com suas convenções de uso:
- $t0...$t9 - temporários
- $s0..$s7 - armazenamento de variáveis
- ...

Memória Principal

bytes
palavras
ordenação de bytes dentro de uma palavra
- Máquinas big-endian armazenam os bytes de uma palavra na ordem do mais significativo para menos significativo.
- Máquinas little-endian armazenam os bytes de uma palavra na ordem do menos significativo para mais significativo.

Instruções do MIPS

Instruções Aritméticas

formato:
add regdest, regop1, regop2
Para realizar expressões envolvendo mais de uma operação, é necessário armazenar resultados intermediários em registradores temporários
a operação
addi regdest, regop1, const
permite usar como um dos operandos (operando imediato uma constante de até 16 bits.
O registrador $r0 (ou $0) sempre contém a constante 0!
Para colocar uma valor de menos de 16 bits em um registrador:
addi regdest, $0, valor

Instruções de Transferência

instruções do tipo LOAD: transferências memória->registrador
instruções do tipo STORE: transferências registrador->memória
Para carregar uma palavra em regdest:
lw regdest, (rege)
onde rege contém o endereço de memória de onde deve ser copiada a palavra
Para carregar na memória uma palavra que está em regdest:
sw regdest, (rege)
onde rege contém o endereço de memória para onde deve ser copiada a palavra

referência: Patterson&Hennessy, 4.3, 4.4

31/08 e 2/09

Instruções de tomada de decisão

Suponha que as variáveis (int) a, b, c, d e e estão alocadas respectivamente nos registradores $s0, $s1, $s2, $s3 e $s4. Como programar estruturas como:

if (a==b) c=d+e;
d=a+c;

while (a<=b) {
  ...
  a++;
}
d=a+c;

Instruções de desvio do assembler servem para "quebrar" a execução sequencial, fazendo com que, sob certas condições, deixe de valer a regra que diz que sempre a próxima instrução a ser executada é a próxima fisicamente na memória.

Existem instruções de desvio condicional e incondicional. No MIPS os desvios condicionais são chamados branch. Um exemplode branch condicional é a instrução:

	bne $s0, $s1, depois

Nesse caso, se o valor de $s0 não for igual ao valor de $s1, o controle é desviado para o endereço indicado pelo label depois. Para programar o if acima, poderíamos então escrever:


	bne $s0, $s1, depois
        add $s2, $s3, $s4
depois:	add $s3, $s0, $s2

Existem muitas outras instruções de desvio condicional (ver manual), como beq, beqz, bge, bgeu, bgt, etc. Instruções de desvio incondicional são chamadas de jump no MIPS. Um exemplo de desvio incondicional é a instrução:

	j depois

que faz com que o controle seja desviado para o endereço indicado pelo label depois, independentemente de qualquer condição.

Para implementar uma estrutura if ... else ... é necessário utilizar um desvio condicional e um incondicional! Tente fazê-lo!

Para programar o while acima, poderíamos escrever:

loop:	bgt $s0, $s1, depois 	# teste no inicio do loop; como fica o do..while?
	...
	addi $s0, $s0, 1
	j loop 			# desvia para teste
depois:	add $s0, $s1, $s2

A instrução de jump tem várias variantes. Uma delas é a jr, que desvia para um endereço armazenado em um registrador. Outra variante importantíssima é a instrução jal, que antes de desviar armazena o endereço da próxima instrução (sequencial) no registrador $ra. Essa instrução é usada para implementar chamadas de funções.

Por convenção então, uma função é chamada por jal. Para retornar dela, pode-se usar

jr $ra

mas para isso é necessário garantir que a função não alterou o conteúdo de $ra (o que infelizmente vai ocorrer, por exemplo, se ela chamar outra função), ou então "salvar" o conteúdo de $ra em outro local e restaurá-lo antes do retorno:

f:
	... 			# tarefas iniciais a serem discutidas depois
	move $s7, $ra
	... 			# corpo da funcao
        move $ra, $s7
        jr $ra

Outra convenção no retorno de funções: os resultados são colocados em $vo e $v1

referência: Patterson&Hennessy, 3.5

14/09 e 16/09

Representação de Números Inteiros com Sinal

Representação em Sinal e Magnitude

Representação por Complemento a 1

Representação por Complemento a 2

referência: Patterson&Hennessy, 4.2

21/09 e 23/09

Pilha de Execução

Necessidade de "espaço" para salvar valores:

Lembre-se da instrução jal, usada para chamar uma função. Essa instrução armazena o endereço de retorno no registrador $ra. Assim, o retorno da função pode ser feito com

j $ra

No entanto, se a função por sua vez chama outra função, ie, usa jal, o conteúdo de $ra não faz mais sentido na hora do retorno. É necessário salvar o valor de retorno em algum outro lugar.

Como funciona a pilha:

Para isso (e muitas outras coisas) é usada a pilha de execução, ou pilha de ativação. A pilha é uma área de memória principal usada como pilha, com operações de push (empilha) e pop (desempilha).

Em geral, o hardware dá algum suporte à manutenção dessa pilha. No caso da máquina MIPS, um registrador específico, $sp, é dedicado ao enedereço do topo da pilha.

Por motivos históricos, a pilha cresce em direção aos endereços mais baixos de memória. Ou seja, para alocar espaço para um endereço, devemos subtrair 4 de $sp (lembre-se que um endereço ocupa 4 bytes!) e para desalocar devemos somar 4 a $sp.

Por exemplo:


-----------------------------------------------
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
-----------------------------------------------
                                      ^
                                      |
                                     $sp

empilhar: sub $sp, $sp, 4
          sw $ra, ($sp)  # suponha que o valor de $ra e' a13f45c6

resultado:
-----------------------------------------------
 |  |  |  |  |  |  |  |  |a1|3f|45|c6|  |  |
-----------------------------------------------
                          ^
                          |
                         $sp


desempilhar: lw $ra, ($sp)
             add $sp, $sp, 4
             

resultado:
-----------------------------------------------
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
-----------------------------------------------
                                      ^
                                      |
                                     $sp

Voltando ao exemplo da função, uma função como:

int boba1() {
  boba2();
  return 1;
}

pode ser escrita em assembler como:

boba1: 
    #salva valores
    sub $sp, $sp, 4
    sw $ra, ($sp)

    jal boba2
    addi $v0, $0, 1
 
    #restaura valores
    lw $ra, ($sp)
    add $sp, $sp, 4
   
    # retorna
    jr $ra

Como exemplo da necessidade de salvar mais valores além de $ra, imagine que a função boba1 precise utilizar um registrador para alocar uma variável local:

int boba1() {
  int i;
  for (i=10;i>0;i--)
    boba2();
  return 1;
}

Uma possibilidade é usar um $t?, mas a função boba2 poderia utilizar esse registrador e corromper o valor de i (sujar o registrador). Outra possibilidade é usar um $s?, por exemplo, $s0. Mas a função que chamou boba1 pode estar usando esse registrador. Assim, é necessário salvar o valor de no início de boba1 e restaurá-lo no final:

boba1: 
	#salva valores
	sub 	$sp, $sp, 4
	sw 	$ra, ($sp)
	sub 	$sp, $sp, 4
	sw 	$s0, ($sp)
	#inicio do for
	add 	$s0, $0, 10
rep:
	blez 	$s0, depois
	jal 	boba2
	sub 	$s0, $s0, 1
	j 	rep
depois:
	addi 	$v0, $0, 1
	#restaura valores
	lw 	$s0, ($sp)
	add 	$sp, $sp, 4
	lw 	$ra, ($sp)
	add 	$sp, $sp, 4
	# retorna
	jr 	$ra

Em vez de alocar a pilha posição por posição (subtrair 4 de cada vez), é comum alocar de uma vez todo o espaço que a função vai precisar:

boba1: 
	#salva valores
	sub 	$sp, $sp, 8
	sw 	$ra, 4($sp) # armazena em ($sp)+4
	sw 	$s0, ($sp)
	#inicio do for
	add 	$s0, $0, 10
rep:
	blez 	$s0, depois
	jal 	boba2
	sub 	$s0, $s0, 1
	j 	rep
depois:
	addi 	$v0, $0, 1
	#restaura valores
	lw 	$s0, ($sp)
	lw 	$ra, 4($sp)
	add 	$sp, $sp, 8
	# retorna
	jr 	$ra

referência: Patterson&Hennessy, 3.6

5/10 e 7/10

Operadores Bit a Bit

Todas as CPUs oferecem algumas instruções que permitem manipular bits individualmente dentro de palavras. Tipicamente, temos instruções de shift e rotate, que deslocam os bits para a direita ou esquerda dentro de uma palavra, e instruções para operações lógicas (and, or, not, ...) bit a bit.

Shift

As operações de shift left logical e shift right logical permitem deslocar os bits de uma palavra n bits para a direita ou esquerda, completando a palavra com zeros.

	li 	$s0, 22 	# $s0 = 0000 ...  0000 0000 0000 0001 0110
        sll	$s1, $s0, 2	# $s1 = 0000 ...  0000 0000 0000 0101 1000
	srl	$s1, $s0, 2	# $s1 = 0000 ...  0000 0000 0000 0000 0101

A operação shift right arithmetic desloca os bits de uma palavra n bits para a direita replicando à esquerda o valor anterior do bit 31.

	li 	$s0, -6 	# $s0 = 1111 ...  1111 1111 1111 1111 1010
	sra	$s1, $s0, 2	# $s1 = 1111 ...  1111 1111 1111 1111 1110
	li 	$s0, 22 	# $s0 = 0000 ...  0000 0000 0000 0001 0110
	sra	$s1, $s0, 2	# $s1 = 0000 ...  0000 0000 0000 0000 0101

Supondo que não haja problema de overflow, o shift de 1 bit para a esquerda equivale à multiplicação de um número por 2 e o shift aritmético de 1 bit para a direita equivale à divisão inteira de um número por 2.

	li 	$s0, 22 	# $s0 = 0000 ...  0000 0000 0000 0001 0110  22
        sll	$s1, $s0, 1	# $s1 = 0000 ...  0000 0000 0000 0010 1100  44
	sra	$s1, $s0, 1	# $s1 = 0000 ...  0000 0000 0000 0000 1011  11  
	li 	$s0, -6 	# $s0 = 1111 ...  1111 1111 1111 1111 1010  -6
        sll	$s1, $s0, 1	# $s1 = 1111 ...  1111 1111 1111 1111 0100  12
	sra	$s1, $s0, 1	# $s1 = 1111 ...  1111 1111 1111 1111 1101  -3

o arredondamento da divisão inteira é sempre "para baixo", ou seja, por exemplo, (-5 div 2) = -3:

	li 	$s0, -6 	# $s0 = 1111 ...  1111 1111 1111 1111 1011  -5
	sra	$s1, $s0, 1	# $s1 = 1111 ...  1111 1111 1111 1111 1101  -3

Isso ocorre porque estamos sempre "subtraindo 1" antes de fazer a divisão.

E por que o shift funciona para multiplicar e dividir?

Para números positivos, acontece exatamente a mesma coisa na base 10. Para negativos é que não é óbvio...

Se x é negativo, rep(x)=2^k+x:

multiplicação:
2*rep(x) = 2*(2^k+x) = 2^k+1+ 2x = 2^k+2^k+2x
sem overflow, 2x>2^k-1, logo
2^k+2^k+2x > 2^k
logo haverá um carry para fora, descartando 2^k, e ficaremos com
2^k+2x = rep(2x)
divisão:
rep(x) div 2 = 2^k-1+x/2
mas quando fazemos o shift aritmético em um negativo, colocamos 1 no bit mais significativo, o que equivale a somar 2^k-1, logo ficamos com
2^k+x/2 = rep(x/2)

referência: Patterson&Hennessy, 4.4

14/10 e 19/10

Representação Ponto Flutuante

referência: Patterson&Hennessy, 4.8

21/10 e 27/10

Compilação de Mecanismos C

Variáveis Globais

Vamos discutir como fica a declaração e utilização de vários tipos de variáveis.

inteiros
- declaradas em C sem inicialização:
  int i; /* declaração sem inicialização */
  em assembler:
```
      .data
      .align 2 # declara que deve ser colocado no próximo end. múltiplo de 4
i:    .space 4 # ocupa 4 bytes
```
- declaradas em C com inicialização:
  int i = 3; /* declaração sem inicialização */
  em assembler:
```
      .data
      .align 2 # declara que deve ser colocado no próximo end. múltiplo de 4
i:    .word 3
```
- utilização:
```
i += 1;
```
  em assembler:
```
      la   $t0,i
      lw   $t1,($t0)
      add  $t1,1
      sw   $t1,($t0)
```
  obs: O uso do nome i é uma facilidade do assembler: no programa executável não existem nomes, apenas endereços!

ponto flutuante

declaradas em C sem inicialização:

float f; /* declaração sem inicialização */

em assembler:

      # igual à variável inteira!
      .data
      .align 2 # declara que deve ser colocado no próximo end. múltiplo de 4
f:    .space 4 # ocupa 4 bytes

declaradas em C com inicialização:

float f = 3.0; /* declaração sem inicialização */

em assembler:

      .data
      .align 2 # declara que deve ser colocado no próximo end. múltiplo de 4
f:    .float 3.0

utilização análoga à de variável inteira

caracteres
- declaradas em C sem inicialização:
  char c; /* declaração sem inicialização */
  em assembler:
```
      .data
c:    .space 1 
```
- declaradas em C com inicialização:
  char c = 'a'; /* declaração sem inicialização */
  em assembler:
```
      .data
c:    .byte 97
```
- utilização:
```
c += 1;
```
  em assembler:
```
      la   $t0,i
      lb   $t1,($t0)
      add  $t1,1
      sb   $t1,($t0)
```

arrays de inteiros

declarados em C sem inicialização:

int a[10];

em assembler:

      .data
      .align 2
a:    .space 40   # cada inteiro ocupa 4 bytes!

declarados em C com inicialização:
int a[10] = {0,1,2,3,4,5,6,7,8,9}
em assembler:
```
      .data
      .align 2
a:    .word 0,1,2,3,4,5,6,7,8,9
```

utilização:

int a[10]; int i;
...
a[i]++;

em assembler:

      # calcula o endereco
      la   $t0,a
      la   $t1,i
      lw   $t1,($t1)
      sll  $t1,$t1,2    # multiplica por 4
      add  $t0,$t0,$t1
      # agora acessa a variavel
      lw   $t1,($t0)
      add  $t1,1
      sw   $t1,($t0)

e se forem 2 arrays?

int i, a[10], b[10]; 
...
a[i] = b[i];

em assembler:

      # calcula os enderecos
      la   $t0,a
      la   $t1,b
      la   $t2,i
      lw   $t2,($t2)
      sll  $t2,$t2,2    # multiplica por 4
      add  $t0,$t0,$t2
      add  $t1,$t1,$t2
      # agora acessa as variaveis
      lw   $t2,($t1)
      add  $t2,1
      sw   $t2,($t0)

arrays de caracteres

declarados em C sem inicialização:
char ac[10];
em assembler:
```
      .data
ac:   .space 10   
```
declarados em C com inicialização:
int ac[10] = {'0','1','2','3','4','5','6','7','8','9'}
em assembler:
```
      .data
ac:   .byte 48,49,50,51,52,53,54,55,56,57
```

utilização:

char ac[10]; int i;
...
a[i]++;

em assembler:

      # calcula o endereco
      la   $t0,a
      la   $t1,i
      lw   $t1,($t1)
      add  $t0,$t0,$t1
      # agora acessa a variavel
      lb   $t1,($t0)
      add  $t1,1
      sb   $t1,($t0)

structs
- declaração
```
struct {
  int a;
  float b;
  char c[2];
} s;
```
  em assembler:
```
      .data
      .align 2
s:    .space 10    # reserva tamanho total
```
- utilização
```
s.c[i]++; /* i foi declarada como inteira */
```
  em assembler:
```
      la   $t0,i
      lw   $t1,($t0)
      la   $t1,s
      add  $t1,$t1,$t0
      lw   $t0,8($t1)
      addi $t0,$t0,1
      sw   $t0,8($t1)
```
  Estruturas introduzem o problema de alinhamento. Cada campo da estrutura que corresponde a uma palavra deve necessariamente começar em um endereço múltiplo de 4. Assim, se tivermos uma declaração como:
```
struct {
  char c[2];
  int a;
  float b;
} s;
```
  onde um campo ocupando dois bytes precede um campo que corresponde a uma palavra, o compilador terá que deixar dois bytes não utilizado entre o array de caracteres e o inteiro:
```
      .data
      .align 2
s:    .space 12    # reserva tamanho total
```
  Observe que de qualquer forma o início da estrutura tem que ser alinhado, senão não saberemos quantos bytes devem ser "pulados" para chegar a um endereço múltiplo de 4.

26/10 e 4/11

Compilação de Mecanismos C

Variáveis Locais e Pilha

As variáveis declaradas localmente (dentro de funções) são tipicamente alocadas na pilha de ativação.

Antes de dar exemplos de variáveis locais alocadas na pilha, vamos rever o uso da pilha de ativação.

Procedimentos Recursivos

Procedimentos recursivos invocam-se a si mesmos: diretamente ou indiretamente (via uma cadeia de chamadas)
O uso da pilha de execução e de registros de ativação permite a implementação de procedimentos recursivos

Exemplo: fatorial


int fact (int n)
{
  if (n < 1)
    return 1;
  else
    return (n * fact (n - 1));
  }

Este exemplo também ilustra o salvamento, na pilha, do valor de um registrador cuja preservação interessa ao procedimento chamador: $a0

Como o procedimento chamado, por convenção, somente preserva o valor dos registradores $s0-$s7, cabe ao procedimento chamador salvar, na pilha (em seu registro de ativação), o valor do registrador $a0


fact:
sub   $sp,$sp,8         # aloca registro de ativação na pilha
sw    $ra, 4($sp)       # valor de $ra deve ser preservado
sw    $a0, 0($sp)       # o valor do argumento (n, em $a0) é usado pelo
# procedimento após o retorno da chamada recursiva
slt   $t0,$a0,1
beq   $t0,$zero,else
addi  $v0,$zero,1       # se n < 1, inicia volta da recursão
j     fim               #   com valor de retorno = 1 (em $v0)
else:
addi  $a0,$a0,-1        # n >= 1 : chamada recursiva com argumento n-1
jal   fact
lw    $a0, 0($sp)       # recupera valor original do argumento (n), salvo na pilha
mul   $v0,$v0,$a0       #  valor de retorno = n * fact (n-1)
fim:
lw    $ra, 4($sp)       # restaura o endereço de retorno em $ra
addu  $sp,$sp,8         # elimina o registro de ativação
jr    $ra

Relembrando:
- Por convenção, um procedimento chamado deve preservar: $s0-$s7, $sp, $ra e o conteúdo da pilha (inclusive e além da posição apontada por $sp, pois a pilha cresce na direção dos endereços mais baixos)
- Os registradores temporários ($t0-$t9), argumentos ($a0-$a3), retornos ($v0-$v1), não preservados pelo chamado: cabe ao chamador salvá-los, se for necessário

Variáveis Locais

Considere a declaração:


void f() {
  double d[4];
  int i;
  int b[20];
  ...
}

O código gerado pelo compilador para esta função deve reservar espaço, na pilha de ativação, para essas variáveis.


f:
      sub    $sp,$sp,120  # 4 para $ra, 80 para b, 4 para i, 32 para d
                          # ($sp) aponta d, 32($sp) aponta i, 36($sp) aponta b
      sw     $ra,116($sp)
      ...
      ...
      lw     $ra,116($sp)
      add    $sp,$sp,120  # desaloca registro de ativação

O comando C

b[i]++

poderia ser traduzido por:


      # cálculo do endereço de b[i]
      lw     $t0,32($sp)
      sll    $t0,$t0,2
      move   $t1,$sp
      addi   $t1,$t1,36 #inicio de b
      add    $t1,$t1,$t0 #endereco de b[i]
      # atualizacao
      lw     $t0,($t1)
      addi   $t0,$t0,1
      sw     $t0,($t1)

A pilha também deve sempre ficar alinhada. Isso tem que ser levado em conta na hora de calcular o tamanho do registro de ativação. Declarações como:


void f() {
  int i;
  char a,b;
  float f;
  ...
}

poderiam ser traduzidas para:


f:
      sub    $sp,$sp,16  # 4 para $ra, 4 para i, 1 para a, 1 para b, , 4 para f 
                         # ($sp)->i, 4($sp)->a, 5($sp)->b, 8($sp)->f
      sw     $ra,12($sp)
      ...
      ...
      lw     $ra,12($sp)
      add    $sp,$sp,16  # desaloca registro de ativação

referência: Patterson&Hennessy, 3.6, A.6

9/11 e 11/11

Compilação, Montagem, Ligação e Carga de Programas

Alocação de memória para um programa :

Sistemas baseados no processador MIPS tipicamente dividem o espaço de endereçamento virtual de um programa em :
- um segmento de texto, contendo as instruções (começando em 40 000 hexa)
- um segmento de dados (começando em 1000 0000 hexa), dividido em:
  - Dados Estáticos : variáveis globais, e demais objetos, de tamanho conhecido, acessíveis durante toda a execução do programa
  - Dados Dinâmicos : dados alocados dinamicamente pelo programa (via malloc, por exemplo)
- um segmento de pilha, localizado no final do espaço de endereçamento virtual (começando em 7FFF FFFF hexa, crescendo na direção dos endereços mais "baixos").
O espaço de endereçamento virtual é o mesmo para todos os programas. É com base na alocação de memória implementada por um sistema que os endereços referenciados por um programa são especificados
Os mecanismos que implementam Memória Virtual realizam o mapeamento dos endereços físicos reais no espaço de endereçamento virtual dos programas em execução

referências:

Patterson & Hennessy, A.5

Hierarquia de tradução de um programa

Compilação : compilador
- programa (ou módulo) em alto nível é traduzido (compilado) para um programa (ou módulo) em linguagem de montagem
Montagem : montador
- programa (módulo) em linguagem de montagem é traduzido para linguagem de máquina, resultando num módulo objeto
Ligação (link-edição) : editor de ligação (linker)
- Diversos módulos objeto compilados em separado, e bibliotecas, são combinados para compor o programa executável
Carga : carregador (loader)
- O programa executável é colocado na memória,e sua execução é iniciada

Referências Externas

Um programa é tipicamente composto por vários módulos, compilados/montados em separado
Dependências entre os módulos - isto é, o endereço de variáveis e procedimentos definidos em um módulo e referenciados em outro(s) - não podem ser resolvidas nas etapas de compilação/montagem
O módulo objeto deve conter as informações necessárias para que a ligação entre os diversos módulos que comporão o programa possa ser feita (resolução de referências externas)

Relocação

O endereço de "carga" de um módulo (instruções e dados) na memória não é conhecido pelo compilador/montador
- o endereço "base" dos segmentos de texto e dados é arbitrado (0, por exemplo)
Referências "absolutas" à memória deverão ser corrigidas quando o endereço de "carga" do módulo for determinado (na etapa de ligação)
O módulo objeto deve conter as informações necessárias para que as referências à memória possam ser corrigidas (relocação)

Montagem

Tarefas do montador:
- Tradução de pseudo-instruções e expansão de "macros"
- Representação do programa em linguagem de máquina: instruções e dados
- Determinação dos endereços de memória referenciados pelo programa (tradução de labels em offsets e endereços)
  - O montador "arbitra" um endereço inicial para os segmentos de texto e dados!
- Registro das informações necessárias á ligação do programa:
  - Tabela de Símbolos Exportados
  - Tabela de Referências Externas
  - Dicionário de Relocação
Montagem em dois passos

Primeiro passo: construção da Tabela de Símbolos
- a questão das referências "à frente" (forward references)
- Informações registradas na T.S.: símbolo (label), endereço correspondente (se o símbolo é "interno"), etc...
Segundo passo: geração do módulo objeto
- Uso da Tabela de Símbolos contruída no passo anterior

Estrutura de um Módulo Objeto (Genérica)

Cabeçalho (header)
- identificação do módulo
- tamanho e posição dos outros componentes
Segmento de Texto
- Instruções reprentadas em linguagem de máquina
Segmento de Dados
- Representação "binária" dos dados
- Apenas dos dados inicializados precisam estar representados
- Apenas o tamanho dos dados não inicializados precisa ser conhecido
Tabela de Símbolos Exportados
- Nome e endereço (relocável!!!) dos símbolos (labels) definidos pelo módulo e acessíveis "globalmente"
Tabela de Referências Externas
- Contém a localização das instruções (e variáveis) que referenciam símbolos definidos em outros módulos (e os símbolos externos correspondentes)
Dicionário, ou Informação, de Relocação
- Contém a localização das instruções (e variáveis) que utilizam referências absolutas à memória (e que devem ser relocadas)

referências:

Patterson & Hennessy, 3.9, A.1, A.2
Mecanismos de Amarração Entre Módulos, Parte 1: Introdução, Programas: da compilação à carga

Compilação, Montagem, Ligação e Carga de Programas (cont)

Ligação (Link-edição)

Os diversos módulos objeto (e bibliotecas) são reunidos em um único módulo executável
Principais Tarefas :
- Concatenação dos diversos módulos (texto e dados) que compõem o programa
  - os endereços "base" dos segmentos de cada módulo são definidos
- Resolução das referências externas
  - Uso das Tabelas de Símbolos e de Referências Externas
- Relocação das referências absolutas à memória
  - Uso dos Dicionários de Relocação

16/11 e 18/11

Carga

Passos executados:
- Leitura do cabeçalho do programa executável
  - Determinação do tamanho dos segmentos de texto e dados
- Criação do espaço de endereçamento para o programa
  - segmentos de texto, dados e pilha
- Cópia do conteúdo dos segmentos de texto e dados do programa executável para a memória
- Cópia dos argumentos do programa para a pilha
- Inicialização dos registradores
  - stack pointer ($sp no MIPS) deve apontar o topo da pilha de execução do programa
- Desvio para rotina de inicialização (start-up), que:
  - copia os argumentos do programa (na pilha) para os registradores, conforme a convenção utilizada
  - invoca o procedimento main do programa
  - ao retornar de main, termina o programa através de chamada ao Sistema Operacional (exit)

Ligação Dinâmica

Na ligação estática todas as referências externas são resolvidas ao final da ligação
- O programa executável contém todos os módulos utilizados (instruções e dados), inclusive bibliotecas
- Cópias de módulos comuns repetidas na memória não são compartilhadas
Na ligação dinâmica parte do processo de ligação é adiado até o momento de execução do programa
- Módulos de bibliotecas dinâmicas/compartilhadas não são incorporados aos programas executáveis
- A resolução das referências externas a símbolos definidos nesses módulos é feita em tempo de execução
- O programa executável deve conter, além dos segmentos de texto e dados, informações que permitam realizar a resolução dinâmica das referências externas pendentes
Ténicas para ligação dinâmica
- Indexação em tabela
  - MULTICS, DLL's Windows
  - Símbolos (procedimentos e variáveis) acessados indiretamente através de uma tabela
  - No Windows, esta tabela é atualizada quando as bibliotecas dinâmicas são carregadas (em tempo de execução)
  - O compilador (ou programador) deve conhecer os símbolos que serão ligados dinâmicamente, e gerar o código apropriado para referenciá-los
- Modificação de código durante a carga ou execução
  - Shared Libraries (UNIX) no SunOS
    - Executável contém estrutura (link_dynamic) que especifica as referências externas a bibliotecas compartilhadas, nomes e versões das bibliotecas, e outras informações
    - Inicialização do programa (prelúdio) carrega o "ligador dinâmico" na memória (tb uma biblioteca compartilhada, ld.so) e lhe transfere o controle
    - O "ligador dinâmico", usando as informações da estrutura link_dynamic, carrega (e reloca) as bibliotecas usadas pelo programa e resolve (parcialmente) as referências externas pendentes do programa
    - Referências a funções apontam rotina do ligador dinâmico. Esta rotina, quando invocada, resolve a referência com o endereço do símbolo realmente referenciado e re-executa a chamada

referências:

Patterson & Hennessy, 3.9, A.3 e A.4
Mecanismos de Amarração Entre Módulos,
- Parte 1: Introdução, Programas: da compilação à carga
- Parte 2: Variantes de Amarração

Chamadas ao Sistema Operacional

Sistema Operacional

Visão do S.O. como um gerenciador dos recursos da máquina (hardware e software)
- Recursos: CPU, memória, arquivos/espaço em disco, dispositivos de E/S, etc...
- S.O. provê o ambiente para a execução de programas
- Alocação ordenada/controlada dos recursos entre os diversos programas que competem por eles
Para os programas em execução na máquina, o S.O. pode ser visto como um prestador de serviços
- Execução de programas
  - O sistema deve ser capaz de carregar um programa na memória e executá-lo
- Operações de E/S
  - Leitura/escrita de arquivos em disco, terminais, impressoras, rede
  - Para maior eficiência e proteção, os usuários não devem controlar diretamente dispositivos de E/S
- Manipulação de Sistemas de Arquivos
  - Criação,eliminação,acesso e gerência de arquivos
- Gerência de Memória
- Criação e gerência de processos

Chamadas ao Sistema

Programas se comunicam com o S.O para requerer serviços através de chamadas ao sistema (system calls)
- open, close, read, write, fork, etc...
Essas chamadas são geralmente realizadas através de instruções "de máquina" especiais
- O Sistema Operacional (kernel) executa em modo privilegiado, e possui espaço de endereçamento especial
- Uma chamada ao sistema (syscall) é tipicamente tratada como uma exceção, transferindo o controle para o S.O. e provocando a mudança para o modo kernel
- a interface de chamada ao sistema convenciona como os parâmetros são passados (tipo de serviço, parâmetros para o serviço a ser executado) : registradores e/ou pilha
- MIPS: instrução syscall
- DOS (8086): instrução INT
  - INT 21 -> chamada ao sistema operacional

Simulação de system calls no SPIM

O Simulador SPIM provê um pequeno conjunto de serviços típicos de um S.O.
Para que um programa possa requerer um desses serviços (implementados por um "pseudo-kernel") uma interface é convencionada :
- o código do serviço é colocado no registrador $v0
- os argumentos (parâmetros) do serviço são passados nos registradores $a0-$a3 (ou $f12 para valores em ponto flutuante)
- a instrução syscall transfere o controle para o "pseudo-kernel"
- as chamadas ao sistema que retornam valores colocam o resultado da execução do serviço no registrador $v0 (ou $f0)
Serviços simulados pelo SPIM
- "print" na console: print_int, print_float, print_double, print_string
- entrada de valores: read_int, read_float, read_double, read_string
- exit: término de programa
- sbrk: para expandir a área de memória dinâmica

Bibliotecas de Chamadas

As chamadas ao Sistema Operacional podem ser feitas em alto-nível através do uso de bibliotecas que disponibilizam procedimentos que implementam as interfaces com os diversos serviços providos pelo S.O.
Esses procedimentos são responsáveis por preparar apropriadamente os parâmetros para a chamada ao sistema, seguindo a convenção estabelecida para cada syscall, executar essa chamada, e preparar o(s) valor(es) de retorno para o usuário
- os procedimentos da biblioteca de interface com o S.O executam em modo usuário, como uma extensão do programa em execução, e recebem parâmetros segundo as convenções estabelecidas pela implementação da linguagem de alto nível correspondente
- após executar algum processamento (verificação dos parâmetros recebidos, obtenção de dados de controle no espaço de dados do usuário) o procedimento da biblioteca prepara os parâmetros para a chamada apropriada e transfere o controle para o kernel do S.O. executando instrução do tipo syscall
- ao final da execução do serviço, o kernel do S.O. retorna o controle para o procedimento da biblioteca, e a máquina volta a executar em modo usuário
- por sua vez, o procedimento da biblioteca, após preparar o(s) valor(es) de retorno para o usuário, retorna o controle ao procedimento "chamador"
Alguns serviços do S.O. não requerem atuação do kernel, e são executados inteiramente em modo usuário

O padrão POSIX

Iniciativa do IEEE para padronizar/uniformizar a interface (bibliotecas) com o S.O. (UNIX)
- No final dos anos 80, diversas versões (incompatíveis) de UNIX eram disponíveis (BSD, SysV, etc...)
- A não padronização das chamadas ao S.O. impedia que um único programa pudesse ser compilado e executar em qualquer sistema UNIX
- O projeto POSIX (Portable Operating System "IX") foi patrocinado pelo IEEE e suportado por inúmeras organizações (governo,universidades, fabricantes)
- O padrão POSIX, resultado deste projeto, define um conjunto "mínimo" de procedimentos (biblioteca de interface com o S.O.) que TODO sistema UNIX deve implementar, e disponibilizar
Windows NT também segue o padrão POSIX

Manipulação de Arquivos no POSIX

arquivos: sequências de bytes
operações
- open: retorno de um descritor de arquivo
- read
- write
- lseek
- close

Biblioteca ANSI C de Entrada/Saída Bufferizada

Um programa C geralmente não faz chamadas aos serviços read, write, etc;
o mais comum é usar a biblioteca bufferizada (stdio)
operações
- fopen: retorno de um FILE*
- fgetc, fputc
- fgets, fputs
- fread, fwrite
- fflush
- fseek
- fclose