Trabalho Pratico 1- 2014-1

Prévia do material em texto

Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação
Disciplina Software Básico (DCC008) - 2014/1
Trabalho Prático 1 - Emulador
1 Descrição Geral
Este trabalho envolve a implementação de um emulador para uma máquina básica, com arquitetura
baseada em acumulador, capaz de realizar um pequeno conjunto de operações.
Atenção: todos os trabalhos práticos da disciplina dependerão deste emulador. Implemente-o com
cuidado, pois erros na máquina podem impactar nas notas de todos os trabalhos.
2 Informações Importantes
• O trabalho deve ser feito em duplas, podendo ser discutido entre as duplas, mas código fonte
não pode ser compartilhado.
• A data de entrega será especificada através de uma tarefa no Moodle.
• Política de atrasos: os trabalhos poderão ser entregues até a meia-noite do dia especificado
para a entrega. O horário de entrega deve respeitar o relógio do sistema Moodle, ou seja, a
partir de 00:01 do dia seguinte à entrega no relógio do Moodle, os trabalhos já estarão sujeitos
a penalidades. O valor do trabalho irá decrementar 5% a cada hora de atraso. Para um aluno
que entregou o trabalho à 1:38, ou seja, com 1:38 de atraso, iremos descontar 10%, empregando
a fórmula a seguir:
Nota = valor_correção× (1− 0.05× horas_atraso)
• O trabalho deve ser implementado obrigatoriamente na linguagem C.
• Deverá ser entregue o código fonte com os arquivos de dados necessários para a execução e um
arquivo Makefile que permita a compilação do programa nas máquinas Linux do DCC.
• Além disso, deverá ser entregue uma pequena documentação contendo todas as decisões de projeto
que foram tomadas durante a implementação, sobre aspectos não contemplados na especificação,
assim como uma justificativa para essas decisões. Esse documento não precisa ser extenso (entre
3 e 5 páginas).
• A ênfase do trabalho está no funcionamento do sistema e não em aspectos de programação ou
interface com o usuário. Assim, não deverá haver tratamento de erros no programa de entrada.
• Todas as dúvidas referentes ao trabalho serão esclarecidas por meio do fórum disponível no
ambiente Moodle da disciplina.
• A entrega do trabalho deverá ser realizada pelo Moodle, na tarefa criada especificamente para tal.
As instruções de submissão, alguns arquivos de teste e o esqueleto da organização dos arquivos
estão presentes no arquivo “tp1_login1_login2.tar.gz”, disponível para download no Moodle.
1
• Atenção: trabalhos que descumprirem esse padrão serão penalizados.
3 Especificação da Máquina SimpleAcc
A máquina a ser emulada é a SimpleAcc (SA), projetada exclusivamente para a disciplina. Seguem as
especificações:
• A menor unidade endereçável nessa máquina é um inteiro (uma palavra de 4 bytes).
• Os tipos de dados tratados pela máquina também são somente inteiros.
• A máquina possui uma memória de 1000 posições, 5 registradores de propósito específico e 5
registradores de propósito geral.
• Cada posição da memória armazena uma palavra (4 bytes). Cada registrador também possui
tamanho 4 bytes, exceto o PSW, que ocupa apenas 2 bits.
• Os registradores de propósito específico são:
– ACC (acumulador): é o principal registrador aritmético, no qual a maioria dos resultados
computados é armazenada.
– PC (contador de programa): contém o endereço da próxima instrução a ser executada.
– PI (instrução prévia): contém o código da última instrução executada (anterior à atual).
– SP (apontador da pilha): aponta para o elemento no topo da pilha.
– PSW (palavra de status do processador): consiste em 2 bits que armazenam o estado da
última operação lógica/aritmética realizada na máquina, sendo um dos bits para indicar que
a última operação resultou em zero e outro bit para indicar que a última operação produziu
um resultado negativo.
• Os registradores de propósito geral são indexados por um valor que varia de 0 a 4.
• A única forma de endereçamento existente na máquina é o endereçamento indexado, relativo ao
PC.
• As instruções READ e WRITE leem e escrevem um inteiro na entrada/saída padrão do emulador.
• As instruções são codificadas em um inteiro, podendo ter 1 operando (como as instruções ADD
e SUB) ou nenhum (como as instruções RET e HALT).
• Os operandos podem ser uma posição de memória (M, codificado como inteiro) ou um registrador
(R, codificado como um inteiro entre 0 e 4).
• Dois formatos de instrução são possíveis: um com 4 bytes e outro com 8 bytes. Instruções que
contêm um operando possuem tamanho 8 bytes, sendo 4 bytes para o código da instrução e 4
bytes para o operando. Instruções sem operando possuem tamanho 4 bytes, isto é, somente o
tamanho ocupado pelo código da instrução.
O conjunto de instruções da Máquina SimpleAcc está detalhado na Tabela 1. As operações marcadas
com * atualizam o valor do PSW de acordo com o resultado da operação.
2
Cód. Símbolo Oper. Tam. Significado Ação
01 LOAD M 8 bytes Carrega o valor armazenado em M
para o acumulador
ACC ←Mem[PC +M ]
02 STORE M 8 bytes Armazena valor do acumulador para
o endereço de memória M
Mem[PC +M ]← ACC
03 READ 4 bytes Lê valor para o acumulador ACC ← Valor lido
04 WRITE 4 bytes Escreve valor do acumulador Imprime ACC
05 COPY R 8 bytes Copia valor do acumulador para o
registrador R
Reg[R]← ACC
06 XCH * R 8 bytes Troca valor do acumulador com o do
registrador R
Temp ← ACC
ACC ← Reg[R]
Reg[R]← Temp
07 ADD * R 8 bytes Soma valor de R ao valor do acumu-
lador
ACC ← ACC +Reg[R]
08 SUB * R 8 bytes Subtrai valor de R do acumulador ACC ← ACC −Reg[R]
09 AND * R 8 bytes AND (bit a bit) do valor de R com
o valor do acumulador
ACC ← ACC AND Reg[R]
10 OR * R 8 bytes OR (bit a bit) do valor de R com o
valor do acumulador
ACC ← ACC OR Reg[R]
11 XOR * R 8 bytes XOR (bit a bit) do valor de R com
o valor do acumulador
ACC ← ACC XOR Reg[R]
12 NOT * 4 bytes NOT (bit a bit) do valor do acumu-
lador
ACC ← NOT ACC
13 JMP M 8 bytes Desvio incondicional PC ← PC +M
14 JZ M 8 bytes Desvia se zero Se PSW [zero], PC ← PC +M
15 JNZ M 8 bytes Desvia se não zero Se !PSW [zero], PC ← PC +M
16 JN M 8 bytes Desvia se negativo Se PSW [negativo], PC ← PC+M
17 JNN M 8 bytes Desvia se não negativo Se !PSW [negativo], PC ← PC+M
18 PUSH 4 bytes Empilha valor do acumulador SP ← SP − 1
Mem[SP ]← ACC
19 POP 4 bytes Desempilha valor no acumulador ACC ←Mem[SP ]
SP ← SP + 1
20 CALL M 8 bytes Chamada de sub-rotina SP ← SP − 1
Mem[SP ]← PC
PC ← PC +M
21 RET 4 bytes Retorno de sub-rotina PC ←Mem[SP ]
SP ← SP + 1
22 DUMP 4 bytes Imprime os valores atuais de todos
os registradores
23 HALT 4 bytes Interrompe execução
Tabela 1: Conjunto de instruções da máquina SimpleAcc. Na coluna de operandos (Oper.), M é uma posição de
memória e R é um registrador. As operações marcadas com * atualizam o valor do PSW de acordo com o resultado
da operação.
3
4 Descrição da Tarefa
Sua tarefa é implementar um programa interpretador que emule a máquina SimpleAcc, ou seja, uma
máquina virtual que execute programas na linguagem de máquina definida na seção anterior.
O trabalho pode ser visto como possuindo duas partes: a primeira é o interpretador da máquina
propriamente dito, que contém uma representação da memória da máquina, e o interpretador do
programa na memória. Os registradores PC e SP devem estar apropriadamente inicializados para
execução, o primeiro com a posição inicial do programa e o segundo com uma posição qualquer da
memória (os valores são fornecidos no programa de entrada, conforme explicado na próxima seção).
Observe que a pilha cresce decrementando o SP, e decresce incrementando o SP. Os registradores ACC,
PI e PSW e os registradores gerais devem ser inicializados com o valor zero.
A segunda parte é o carregador do programa, que consiste em ler de um arquivo um programa em
linguagem de máquina contendo as instruções.Essas duas “peças” são fundamentais para a continuidade dos trabalhos práticos da disciplina. Os
outros trabalhos dependerão delas.
5 Formato da Entrada de Dados
A entrada do programa é um arquivo binário, que será um executável da SA. Observe que, por ser
um arquivo binário, não existe o conceito de linha. O arquivo é simplesmente um grande vetor de
bytes. O formato do arquivo é o seguinte:
[ASSINATURA] - 2 bytes (‘S’ e ‘A’)
[PC] - 4 bytes
[SP] - 4 bytes
[INSTRUÇÕES] - 4 bytes para cada ID de instrução ou operando
Os dois primeiros bytes do arquivo contêm a assinatura, que é um valor fixo que deve estar presente
em todos os executáveis da máquina virtual (os valores de byte que equivalem aos caracteres S e A),
servindo apenas como um verificador, não tendo efeito na execução. Os 4 bytes seguintes armazenam
o valor inicial do PC, que será usado pela máquina virtual no início da execução, correspondente à
posição de memória em que será lida a primeira instrução a ser executada. Os próximos 4 bytes
armazenam o valor inicial do SP, que também será usado pela máquina virtual no início da execução.
Finalmente, os bytes seguintes são relativos ao programa propriamente dito, que contém as instruções
e seus respectivos operandos, sempre de tamanho 4 bytes cada, devendo ser carregado no início da
memória da máquina (Mem[0]).
OBS1: Assuma que uma codificação little-endian será utilizada. Se você usar uma máquina de CPU
Intel, não deverá ter problemas. Caso contrário, pode ser necessário tratar a conversão de codificação
de sua máquina. Nesse caso, em vez de tratar a conversão, provavelmente será mais fácil utilizar uma
das máquinas dos laboratórios do DCC.
OBS2: O conteúdo da memória do programa, armazenado a partir do 11o byte no executável, deve
ser totalmente carregado na memória da máquina virtual antes da execução.
4
Exemplo de executável:
S - Lemos 1 byte, verifica que é igual a ‘S’ --> OK
A - Lemos 1 byte, verifica que é igual a ‘A’ --> OK
0 - Lemos 1 inteiro (4 bytes), PC = 0
500 - Lemos 1 int (4 bytes), SP = 500
3 - Lemos 1 int (4 bytes), identifica instrução READ, PC = 1, instrução READ é executada
5 - Lemos 1 int (4 bytes), ident. instrução COPY, PC = 2
0 - Lemos 1 int (4 bytes), ident. operando R de COPY, PC = 3, instrução COPY é executada
1 - Lemos 1 int (4 bytes), ident. instrução LOAD, PC = 4
4 - Lemos 1 int (4 bytes), ident. operando M de LOAD, PC = 5, instrução LOAD é executada
7 - Lemos 1 int (4 bytes), ident. instrução ADD, PC = 6
0 - Lemos 1 int (4 bytes), ident. operando R de ADD, PC = 7, instrução ADD é executada
4 - Lemos 1 int (4 bytes), ident. instrução WRITE, PC = 8, instrução WRITE é executada
23 - Lemos 1 int (4 bytes), ident. instrução HALT, execução finalizada
100 - Valor literal armazenado na memória. Não é executado, apenas carregado usando a
instrução LOAD acima.
O programa deve ser interpretado da seguinte forma: (1) leia um inteiro da entrada padrão (ex: scanf);
(2) copie o conteúdo do acumulador (ou seja, o valor lido da entrada) para o registrador 0; (3) carregue
o conteúdo da posição de memória PC + M (neste caso, M = 4, PC = 5 e PC + M = 9, que é a
posição em que está o valor literal 100); (4) some o valor do registrador 0 com o valor armazenado no
acumulador (no caso, R[0] = Valor lido e ACC = 100); (5) imprima na entrada padrão (ex: printf) o
valor do acumulador.
O arquivo binário correspondente a esse programa de exemplo está disponível no pacote do trabalho
prático, em tst/tp1ex1.sa, e pode ser utilizado como teste. Outro programa de teste igualmente
disponível no pacote é o tst/tp1teste1.sa. Ao executá-lo no emulador, o programa deve pedir dois
inteiros, imprimir os dois na ordem em que foram informados e depois imprimir o maior deles. Observe
que tais programas não testam todas as instruções, então outros programas devem ser obrigatoria-
mente implementados com o objetivo de cobrir todo o conjunto de instruções. A qualidade dos testes
implementados será levada em conta na correção.
6 Formato da Saída de Dados
A saída das instruções WRITE e DUMP deve ser sempre numérica, ocupando uma única linha.
No caso da instrução WRITE, uma linha é impressa contendo um único número (o valor do acumula-
dor). No caso da instrução DUMP, uma linha é impressa contendo 11 números, separados um do outro
por um espaço em branco. Esses números são os valores de todos os registradores, na seguinte ordem:
ACC, PC, PI, SP, PSW[zero], PSW[negativo] e registradores gerais (de 0 a 4). A título de exemplo,
considere o programa abaixo:
S
A
0 - PC = 0
500 - SP = 500
1 - PC = 1, PI = 0
9 - PC = 2, instrução LOAD 9 é executada, PI = 1
6 - PC = 3
0 - PC = 4, instrução XCH 0 é executada, PI = 6
1 - PC = 5
4 - PC = 6, instrução LOAD 4 é executada, PI = 1
8 - PC = 7
0 - PC = 8, instrução SUB 0 é executada, PI = 8
22 - PC = 9, instrução DUMP é executada, PI = 22
23 - HALT
42
100
5
Ao final da execução, a saída do programa, dada pela instrução DUMP, deverá ser:
-58 9 8 500 0 1 100 0 0 0 0
Se substituirmos a instrução DUMP pela instrução WRITE, a saída deverá ser simplesmente:
-58
O arquivo binário do programa descrito acima está disponível para testes no pacote do trabalho, em
tst/tp1ex2.sa.
7 Formato de Chamada do Emulador
O único parâmetro recebido pelo emulador é o nome do arquivo contendo o programa a ser executado
pela máquina virtual. Exemplo de chamada:
./emulador teste1.sa
8 Sobre a Documentação
• Deve conter todas as decisões de projeto.
• Deve conter informações sobre como executar o emulador. Obs: é necessário cumprir os for-
matos definidos acima para a execução, mas tais informações devem estar presentes também na
documentação.
• Deve conter elementos que comprovem que o emulador foi testado (ex: imagens das telas de
execução). Os arquivos relativos a testes devem ser enviados no pacote do trabalho. A docu-
mentação deve conter referências a esses arquivos, explicação do que eles fazem e dos resultados
obtidos.
• O código fonte não deve ser incluído no arquivo de documentação.
9 Considerações Finais
Os testes de funcionamento da máquina virtual possivelmente serão automatizados, o que torna neces-
sário o cumprimento fiel de todas as especificações de interface descritas neste documento. As decisões
de projeto devem fazer parte apenas da estrutura interna da SA, não podendo afetar a interface de
entrada e saída.
6