apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.968 seguidores
Pré-visualização50 páginas
59 27
60 88
61 12
62 12

Figura 4.1: Uma fotografia da memo´ria.

Para melhor entendimento, e´ importante que o leitor tenha em mente a diferenc¸a
entre enderec¸o e conteu´do do enderec¸o. Para facilitar a compreensa˜o, vamos adotar
uma notac¸a˜o. Seja p um enderec¸o. Denotamos por [p] o conteu´do do enderec¸o p.
Vejamos alguns exemplos com base na figura 4.1:

[0] = 1
[[0]] = [1] = 54

[[[0]]] = [[1]] = [54] = 235
[0] + 1 = 1 + 1 = 2
[0 + 1] = [1] = 54

[[0] + 1] = [1 + 1] = [2] = 2
[[0] + [1]] = [1 + 54] = [55] = 35

4.2.2 O reperto´rio de instruc¸o˜es

Conforme mencionado, o modelo Von Neumann pressupo˜e que o computador que esta´
em uso possui um conjunto limitado de instruc¸o˜es programado em hardware.

Cada equipamento tem o seu reperto´rio de instruc¸o˜es. O reperto´rio do computador
da BCC foi definido apo´s longas discusso˜es da equipe te´cnica da empresa e tem um
conjunto extremamente limitado de instruc¸o˜es, na verdade apenas nove.

24 CAPI´TULO 4. O MODELO DO COMPUTADOR

Esta definic¸a˜o levou em conta a capacidade financeira da empresa que na˜o tinha
muita verba para gravar em circuitos integrados um conjunto mais rico de instruc¸o˜es.

As nove instruc¸o˜es do computador da BCC sa˜o apresentadas na figura 4.2.3.

Co´digo Mnemoˆnico Descric¸a˜o Notac¸a˜o
1 load escreva em [p+ 1] o valor do

nu´mero em [p + 2] e some 3
em p

[p+ 1]← [p+ 2].

2 add escreva em [p+ 1] o valor da
soma dos nu´meros em [[p +
2]] e [[p+ 3]] e some 4 em p

[p+ 1]← [[p+ 2]] + [[p+ 3]].

3 sub escreva em [p + 1] o valor
da subtrac¸a˜o do nu´mero em
[[p+2]] pelo nu´mero em [[p+
3]] e some 4 em p

[p+ 1]← [[p+ 2]]− [[p+ 3]].

4 mult escreva em [p + 1] o valor
do produto dos nu´meros em
[[p + 2]] e [[p + 3]] e some 4
em p

[p+ 1]← [[p+ 2]]× [[p+ 3]].

5 div escreva em [p+ 1] o valor da
divisa˜o do nu´mero em [[p +
2]] pelo nu´mero em [[p + 3]]
e some 4 em p

[p+ 1]← [[p+2]]
[[p+3]]

.

6 sqrt escreva em [p+ 1] o valor da
raiz quadrada de [[p + 2]] e
some 3 em p

[p+ 1]←√[[p+ 2]].
7 read leia um nu´mero do teclado,

escreva-o em [p + 1] e some
2 em p

[p+ 1]← ∨.

8 write escreva [[p + 1]] na tala e
some 2 em p

�← [[p+ 1]].

9 stop pare •
Figura 4.2: O reperto´rio de instruc¸o˜es do computador da BCC.

3Os concorrentes comerciais famosos da BCC implementam algumas centenas de instruc¸o˜es, e
ainda nenhuma delas e´ a de bater claras em neve.

4.2. PRINCI´PIOS DO MODELO 25

4.2.3 O ciclo de execuc¸a˜o de instruc¸o˜es

O ciclo de execuc¸a˜o de instruc¸o˜es define o comportamento do computador. Funciona
assim (no computador da BCC):

1. comece com p = 0;

2. interprete [p] de acordo com a tabela de instruc¸o˜es e pare somente quando a
instruc¸a˜o for uma ordem de parar (instruc¸a˜o 9, stop).

Devemos lembrar que este comportamento tambe´m esta´ implementado nos circui-
tos eletroˆnicos do computador da BCC.

4.2.4 Exemplo de execuc¸a˜o de um programa

A grande surpresa por tra´s do modelo de Von Neumann e´ que, mesmo que o leitor
ainda na˜o compreenda, o que existe na verdade “disfarc¸ado” na fotografia da memo´ria
da figura 4.1 e´ um programa que pode ser executado pelo computador, desde que todo
o processo siga as instruc¸o˜es descritas na sec¸a˜o anterior.

Vamos tentar acompanhar passo a passo como e´ o funcionamento deste esquema.
Para isto, o leitor talvez queira ir marcando, a la´pis, as alterac¸o˜es que sera˜o feitas
a seguir em uma co´pia da “fotografia da memo´ria” acima. E´ recomendado neste
momento se ter uma versa˜o impressa daquela pa´gina.

Notem que, no momento, na˜o e´ necessa´rio sabermos qual o programa implemen-
tado, afinal de contas, o computador jamais sabera´. . . Ele executa cegamente as ins-
truc¸o˜es. No´s saberemos logo a` frente, mas, agora, para entendermos como e´ o funci-
onamento deste modelo, vamos nos imaginar fazendo o papel do computador.

1. O programa comec¸a com p = 0

2. Em seguida, e´ preciso interpretar [p], isto e´ [0] = 1. A instruc¸a˜o de co´digo “1” e´
“load”, cujo comportamento e´, segundo a tabela de instruc¸o˜es “escreva em [2]
o valor do nu´mero em [3] e some 3 em p”. Ora, [2] = 54 e [3] = 2. Logo, o valor
2 e´ colocado como sendo o conteu´do da posic¸a˜o 54. Havia nesta posic¸a˜o o valor
235. Apo´s a execuc¸a˜o da instruc¸a˜o, existe um 2 neste lugar. O valor 235 na˜o
existe mais. Ao final foi somado 3 no valor de p, isto e´, agora p = 3.

3. Como p = 3 devemos interpretar [3] = 1. Logo, a instruc¸a˜o e´ novamente “load”.
Analogamente ao que foi feito no para´grafo anterior, o conteu´do de [5] = 4 e´
colocado como sendo o conteu´do da posic¸a˜o [4] = 50. Na posic¸a˜o 50 havia o
valor 76. Apo´s a execuc¸a˜o da instruc¸a˜o o 76 da´ lugar ao 4. Ao final o valor de
p foi atualizado para 6.

4. Como p = 6 devemos interpretar [6] = 7. Logo, a instruc¸a˜o para ser executada
agora e´ “read”, isto e´, esperar o usua´rio digitar algo no teclado e carregar este
valor em [p+ 1] = [7] = 46. Supondo que o usua´rio digitou o valor 5, este agora
substitui o antigo valor, que era 33. Ao final, o valor de p foi atualizado de 6
para 8.

26 CAPI´TULO 4. O MODELO DO COMPUTADOR

5. Como p = 8 devemos interpretar [8] = 4. Logo, a instruc¸a˜o a ser executada
e´ “mult”. Isto faz com que o computador fac¸a a multiplicac¸a˜o do valor em
[[10]] = [46] pelo mesmo valor em [[11]] = [46]. O valor em [46] e´ 5 (aquele
nu´mero que o usua´rio tinha digitado no teclado). O resultado da multiplicac¸a˜o,
5 × 5 = 25, e´ carregado na posic¸a˜o de memo´ria [9] = 47. O valor ali que era 2
agora passa a ser 25. Ao final, ao valor de p foi somado 4, logo neste momento
p = 12.

E´ importante salientar que este e´ um processo repetitivo que so´ terminara´ quando
a instruc¸a˜o “stop” for a da vez. O leitor e´ encorajado a acompanhar a execuc¸a˜o
passo a passo ate´ o final para entender como e´ exatamente o comportamento dos
computadores quando executam programas. Isto e´, fica como exerc´ıcio ao leitor!
Destacamos que os circuitos implementados cuidam da alterac¸a˜o do estado ele´trico
dos circuitos da memo´ria.

4.3 Humanos versus computadores

No´s seres humanos na˜o nos sentimos muito a` vontade com este tipo de trabalho
repetitivo. Temos a tendeˆncia a identificar “meta-regras” e executar a operac¸a˜o com
base em um comportamento de mais alto n´ıvel. Em suma, no´s aprendemos algo neste
processo, coisa que o computador so´ faz em filmes de ficc¸a˜o cient´ıfica.

A primeira coisa que nos perguntamos e´: por qual motivo ora se soma um valor
em p, ora outro? Isto e´, quando executamos a operac¸a˜o “load”, o valor somado em p
foi 3. Depois, quando executada a operac¸a˜o “read” o valor somado foi 2. Em seguida,
para a instruc¸a˜o “mult” o valor somado foi 4.

O estudante atento, notadamente aquele que foi ate´ o final na execuc¸a˜o do ciclo de
operac¸o˜es deixado como exerc´ıcio, talvez tenha percebido uma sutileza por tra´s deste
modelo.

De fato, quando se executa a instruc¸a˜o [p], o conteu´do de [p+1] sempre e´ o enderec¸o
de destino dos dados que sa˜o resultado da operac¸a˜o em execuc¸a˜o. Os enderec¸os
subsequentes apontam para os operandos da operac¸a˜o que esta´ programada para
acontecer.

Assim:

• Se for uma multiplicac¸a˜o, subtrac¸a˜o ou soma, precisamos de dois operandos e
do enderec¸o destino, por isto se soma 4 em p;

• Se for um “load” precisamos de um operando apenas, assim como para a raiz
quadrada, por isto se soma 3 em p;

• Se for uma leitura do teclado ou uma escrita na tela do computador, enta˜o um
u´nico argumento e´ necessa´rio, por isto se soma apenas 2 em p.

Uma outra observac¸a˜o importante e´ que, por questo˜es de hardware, o computador
precisa entender a memo´ria como esta espe´cie de “tripa”. O ser humano, ao contra´rio,

4.3. HUMANOS VERSUS COMPUTADORES 27

uma vez que ja´ identificou pequenos blocos relacionados a`s instruc¸o˜es, pode tentar
entender esta mesma