Sistemas Digitais - Sebenta

C-1

CIRCUITOS LÓGICOS BÁSICOS C.1 - INTRODUÇÃO À LÓGICA DIGITAL A informação pode ser veiculada segundo 2 tipos de sinais com características diferentes: sinais analógicos ou sinais digitais. C.1.1 - Características essenciais Sinal analógico - Variação contínua ao longo do tempo, sem saltos bruscos.

Fig 1

Ex.: saída de um microfone, sinal de vídeo, etc.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C-2

Sinal digital - Variação por saltos de uma forma descontínua. Toma apenas um determinado número de valores. V 4 3 2 1 0 -1 -2

nível ALTO

1

nível BAIXO

0 Fig 2

Ex.: informação gravada num CD, fluxo de entre um computador e uma impressora, etc.

dados

Aos circuitos electrónicos que funcionam baseados apenas em 2 valores de amplitude chamam-se Digitais Binários. Normalmente utiliza-se a lógica positiva que atribui ao valor mais elevado de tensão o nível 1 (ou verdadeiro) e ao valor mais baixo de tensão o nível 0 (ou falso).

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C-3

C.1.2 - Circuitos Digitais Binários Uma grande vantagem dos circuitos digitais binários é que com apenas 2 níveis de tensão bem separados consegue-se uma grande imunidade ao ruído. Na figura seguinte apresenta-se uma situação com as correspondências seguintes Nível 1 → 5 Volt Nível 0 → 0 Volt Ruído → ±1 Volt

V 5

3.5 1.5

0 t V 5 0 t Fig 3

Se considerarmos que tensão inferior a 1.5 Volt ⇒ nível 0 tensão superior a 3.5 Volt ⇒ nível 1 então o sinal original corrompido pelo ruído pode ser facilmente regenerado. De notar que um sinal analógico afectado por ruído não pode ser regenerado.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C-4

C.2 - IMPLEMENTAÇÃO DE UM SISTEMA LÓGICO Um circuito digital ou lógico pode ser encarado como uma caixa com n entradas e m saídas que realiza uma determinada função lógica. Entrada 1 Entrada 2

Saída 1 Circuito

Saída 2

Lógico Saída m

Entrada n

Fig 4

Um circuito lógico pode ser materializado com interruptores, com relés, com electroímans, com díodos, com transistores ou com circuitos integrados. No entanto, tanto as entradas como as saídas apenas podem tomar 2 valores ou estados, opostos um ao outro. Exemplo de um circuito lógico AND realizado com interruptores. I1

I2

Interruptores Bateria

Lâmpada

Fig 5

Neste caso as entradas são os interruptores e podem tomar os valores aberto ou fechado. A saída é uma lâmpada que toma os valores acesa ou apagada.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C-5

C.3 - PORTA "AND" C.3.1 - Generalidades O circuito anterior pode tabela de verdade seguinte.

ser

representado

Entradas I1 Aberto Aberto Fechado Fechado

I2 Aberto Fechado Aberto Fechado

pela

Saída L Apagada Apagada Apagada Acesa

Em termos de lógica binária podemos simplificar a tabela anterior se adoptarmos a correspondência seguinte: Interruptores: Aberto ↔ 0 Fechado ↔ 1 Lâmpada:

Entradas I1 I2 0 0 0 1 1 0 1 1

Apagada ↔ 0 Acesa ↔ 1 Saída L 0 0 0 1

Este circuito tem o nome de porta E ou gate AND e realiza a função de produto lógico pois apenas tem saída 1 quando as entradas são ambas 1. C.3.2 - Materialização electrónica O circuito AND pode ser realizado com díodos. Na figura abaixo, as entradas são A e B e a saída é o ponto S. ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C-6

5 V

A S B

Fig 6

Num circuito electrónico representam tensões.

os

valores

1

e

0

De seguida aplicaremos às entradas deste circuito todas as combinações possíveis de valores lógicos utilizando as seguintes correspondências: 0 volt 5 volts

↔ ↔

0 lógico 1 lógico

Observando a tensão obtida em S para cada caso, poderemos construir a tabela de verdade deste circuito.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C-7

1º caso: A=B=0 5 V

A=0 S B=0 0,6 V

Fig 7

Analisando a curva característica do díodo conclui-se que enquanto a tensão no sentido directo for inferior a 0,6V o díodo não conduz. Para além desse valor a corrente aumenta sem que a tensão sofra grande variação. Assim, a tensão na saída S é 0,6V que se encontra na zona do nível lógico 0. I D I D

0,6 V

0,6 V

V D Fig 8

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C-8

2º caso: A=1 e B=0 5 V

A=1 S B=0

Fig 9

O díodo da entrada A está ligado aos 5 volts. Isto significa que está ao corte pois o seu ânodo (S) nunca poderá ter uma tensão superior a 5V. Por outro lado o díodo de B está ligado à massa forçando S a ficar a 0,6 V - nível lógico 0. 3º caso: A=B=1 5 V

A=1 S B=1

Fig 10

Nenhum dos díodos conduz pois têm o ânodo e cátodo ligados ao mesmo potencial. Logo a tensão em S é 5V. Tabela lógica ou de verdade de um circuito AND A

B

S

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C-9

0 0 1 1

0 1 0 1

0 0 0 1

São possíveis outras materializações de circuitos AND utilizando outros componentes electrónicos. No entanto, num projecto de sistemas digitais não interessa conhecer a estrutura interna de cada porta, mas apenas a função lógica por ela realizada. Para além disso é necessário conhecer as características eléctricas das entradas e saídas de cada porta - impedâncias de entrada e saída, correntes de entrada e saída, tempos de propagação. C.3.3 - Simbologia • Símbolos usados para representar lógicos AND de 2 e 3 entradas

os

circuitos

A B

A B C

S

S = A . B

T

T = A . B . C Fig 11

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 10

Tabela de verdade do circuito AND de 3 entradas A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

T 0 0 0 0 0 0 0 1

C.4 - PORTA "OR" C.4.1 - Generalidades O circuito Inclusive OR ou simplesmente OR é outro elemento lógico básico. Exemplo de implementação electromecânica I2

I1

Bateria

Interruptores

Lâmpada

Fig 12

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 11

Tabela de verdade correspondente Entradas I1 I2 0 0 0 1 1 0 1 1

Saída L 0 1 1 1

C.4.2 - Implementação electrónica Na implementação seguinte mantém-se o valor lógico 0 para 0 volt e o valor lógico 1 para 5 volts.

A B

S

C

Fig 13

Se todas as entradas forem ligadas à massa, a saída é 0 uma vez que não há tensão no circuito. Se uma das entradas for ligada a 5 volts (nível lógico 1), o díodo respectivo fica polarizado directamente (conduz). Logo a saída S terá uma tensão de 4,4 volts devido à queda de tensão no díodo de 0,6 volt, o que corresponde ao nível 1 na saída.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 12

5 V 0,6 V

A=1

4,4 V S

B=0 C=0

Fig 14

Basta, portanto, que uma entrada seja 1 para que a saída tenha o valor 1. É o circuito lógico OR. C.4.3 - Simbologia Símbolos usados para representar os circuitos OR de 2 e 4 entradas A S

S = A + B

T

T = A + B + C +

B A B C D

Fig 15

Tabela de verdade do circuito OR de 2 entradas A B S 0 0 0 0 1 1 1 0 1 1 1 1 C.5 - CIRCUITO "NOT" OU INVERSOR C.5.1 - Generalidades ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 13

Um circuito seguinte representa realizada a partir de um relé.

uma

negação

S E Fig 16

A entrada E deste circuito, quando actuada (nível lógico 1), puxa o interruptor. Neste caso o circuito fica aberto e a lâmpada apaga-se saída S a 0. Quando a entrada não está actuada (nível lógico 0) o circuito está fechado, mantendo-se acesa a lâmpada.

A tabela de verdade deste circuito é a tabela da negação. E 0 1

S 1 0

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 14

C.5.2 - Materialização electrónica Não é possível realizar um circuito NOT com díodos, mas pode utilizar-se um transistor. I =βI B C

5 V

5 V

R =1K Ω C

I = C máx

1K Ω

= 5 mA

IC

R =10K Ω B

Para V

IB

β =20

V B 0,6V

B

V C

> 0,6V :

V -0,6V B

V -0,6V B I = C

R

= B

10K Ω Fig 17

Aplicando 0 volt em VB, a corrente de base IB é nula pois a junção base-emissor precisa de 0,6 volts para conduzir. Deste modo IC também é nula, pois IC=βIB. Nesta situação o transistor não conduz (está ao corte) e a tensão VC é 5V. Aplicando 5 volts na entrada VB o transistor passa a conduzir. A queda de tensão na junção baseemissor é de 0,6 volts, logo a queda de tensão em RB é de 4,4 volts. Assim a corrente IB será: IB =

4,4V = 0,44mA 10kΩ

Pela expressão IC=βIB a corrente IC seria 8,8mA que é um valor superior ao seu valor máximo. Diz-se neste caso que o transistor está saturado. A corrente IC atinge o seu valor máximo para IB=0,25mA que corresponde a uma tensão VB=3,1 V. A este valor máximo de IC corresponde o valor mais baixo de VC. ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 15

Característica transistor

entrada-saída

do

circuito

com

V C 5 4 3 2 1

0,6

3,1

5V

V B Fig 18

A electrónica analógica utiliza a zona (intermédia) do funcionamento do transistor.

linear

Em sistemas digitais utiliza-se o transistor como chave pelo que apenas são relevantes as zonas de funcionamento em que o transistor está cortado ou saturado. Símbolo do inversor e variantes

Fig 19

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 16

C.6 - CIRCUITOS LÓGICOS INTEGRADOS Circuito integrado - bloco de cerâmica cinzenta ou preta com o formato paralelipipédico ou prismático. As dimensões variam de poucos mm até alguns cm. O número de pernos vai de algumas unidades até várias dezenas. Os circuitos integrados mais simples contêm apenas algumas portas lógicas elementares. Exemplo de série 7400.

circuitos

integrados

da

família

TTL

• 4 portas AND de 2 entradas 14

13

12

11

10

9

8

V CC

7408 GND 1

2

3

A

B

S

4

5

6

7

S = A . B Fig 20

• 4 portas OR de 2 entradas 14

13

12

11

10

9

8

V CC

7432 GND 1

2

3

A

B

S

4

5

6

7

S = A + B Fig 21

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 17

• 6 portas NOT 14

13

12

11

10

9

8

V CC

7404 GND 1

2

A

S

3

4

5

6

7

S = A Fig 22

• 3 portas AND de 3 entradas 14

13

12

11

10

9

8

V CC

7411 GND 1

2

3

4

5

A

B

C

6

S

7

S = A . B . C Fig 23

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

C - 18

C.7 - PORTA "NAND" O circuito NAND é composto por 2 circuitos básicos: o circuito NOT precedido do circuito AND. Símbolo e equação lógica do circuito NAND

A S = A . B

S

B

Fig 24

A bolinha significa uma negação, pelo que a tabela de verdade do circuito NAND se deduz de imediato. A 0 0 1 1

B 0 1 0 1

S 1 1 1 0

C.8 - PORTA "NOR" O circuito NOR é um circuito OR com a saída negada, pelo que o seu símbolo corresponde a um circuito NOT precedido de um OR.

A S

S = A + B

B Fig 25

Tabela de verdade do circuito NOR A 0 0 1 1

B 0 1 0 1

S 1 0 0 0

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B-1

ÁLGEBRA DE BOOLE B.1 - DIAGRAMA DE VENN No século passado Georges Boole desenvolveu uma teoria matemática com base nas leis da lógica - a Álgebra de Boole - cuja aplicação nos circuitos digitais e computadores é de primordial importância. A lógica matemática tem por base a teoria dos conjuntos, podendo utilizar-se meios gráficos como forma de representar propriedades. Diagrama de Venn

A

A Fig 26

Admitindo que o conjunto Universo é o dos números inteiros, pode definir-se: A - conjunto dos números pares B - conjunto dos múltiplos de 3 Aplicando sobre estes conjuntos lógicas básicas, obtém-se:

as

operações

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B-2

A.B - Conjunto dos números pares e múltiplos de 3 Conjunção, intersecção ou produto lógico

A B Fig 27

A+B - Conjunto dos números pares ou múltiplos de 3 União, disjunção ou soma lógica

A

B Fig 28

_

A

- Conjunto dos números ímpares Complemento ou negação

A

B Fig 29

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B-3

B.2 - AXIOMAS DA ÁLGEBRA DE BOOLE Sendo B≠∅, definem-se as para a estrutura {B, +, .}.

propriedades

seguintes

B.2.1 - Soma e produto são operações fechadas

∀a, b

∈ B : a+b ∈ B

∀a, b

∈ B: a. b ∈ B

B.2.2 - Comutatividade

∀a, b

∈ B : a+b = b+a

∀a, b

∈ B: a. b = b. a

B.2.3 - Existência de elemento neutro

∃u ∈ B, ∀a ∈ B : a + u

= a

∃v ∈ B, ∀a ∈ B : a . v

= a

B.2.4 - Distributividade das duas operações uma em relação à outra

∀a, b, c

∈ B : a + (b . c) = (a + b) . (a + c)

∀a, b, c

∈ B : a . (b + c) = (a . b) + (a . c)

B.2.5 - Complementação

∀a ∈ B, ∃ a ∈ B : a + a _

∀a ∈ B, ∃ a ∈ B : a . _

_

= v

_

a = u

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B-4

B.3 - TEOREMAS DA ÁLGEBRA DE BOOLE B.3.1 - Unicidade dos elementos neutros • O elemento u é único. Demonstração Sejam u1 e u2 dois elementos neutros da soma. u1 + u2 = u1 + u2 = u1 + u2 = u1 =

u1 u2 u2 + u1 u2

(B.2.3) (B.2.3) (B.2.2)

• O elemento v é único. Demonstração Sejam v1 e v2 dois elementos neutros do produto. v1 . v2 = v1 . v2 = v1 . v2 = v1 =

v1 v2 v2 . v1 v2

(B.2.3) (B.2.3) (B.2.2)

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B-5

B.3.2 - Idempotência •

∀a ∈ B : a + a

= a

Demonstração a + a = (a + a) . 1 a + a = (a + a) . (a + a ) = a + (a . a ) = a + 0 = a •

∀a ∈ B : a . a

(B.2.3) (B.2.5) (B.2.4) (B.2.5) (B.2.3)

= a

Demonstração a . a = (a . a) + 0 a . a = (a . a) + (a . a ) = a . (a + a ) = a . 1 = a

(B.2.3) (B.2.5) (B.2.4) (B.2.5) (B.2.3)

B.3.3 - Elementos absorventes •

∀a ∈ B : a + 1

= 1

Demonstração a + 1 = = = = =

(a + 1) . 1 (B.2.3) (a + 1) . (a + a ) (B.2.5) (B.2.4) a + (1 . a ) a (B.2.3) a + 1 (B.2.5)

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

•

∀a ∈ B : a .

B-6

0 = 0

Demonstração a . 0 = = = = =

(a . 0) + 0 (a . 0) + (a . a ) a . (0 + a ) a . a 0

(B.2.3) (B.2.5) (B.2.4) (B.2.3) (B.2.5)

B.3.4 - Absorção •

∀a, b ∈ B : a + (a . b)

= a

Demonstração a + (a . b) = = = =

•

∀a, b ∈ B : a .

(a . 1) + (a . b) a . (1 + b) a . 1 a

(B.2.3) (B.2.4) (B.3.3) (B.2.3)

(a + b) = a

Demonstração a . (a + b) = = = =

(a + 0) + (a + b) a + (0 . b) a + 0 a

(B.2.3) (B.2.4) (B.3.3) (B.2.3)

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B-7

B.3.5 - Princípio da dualidade Toda a afirmação ou identidade algébrica dedutível dos axiomas e definições de uma Álgebra de Boole permanece válida se as operações (+) e (.), e os elementos neutros u e v forem trocados. Este princípio resulta da simetria das definições e axiomas em relação às duas operações e aos dois elementos neutros. B.3.6 - Unicidade do elemento a Demonstração Supor que a 1 e a 2 são ambos complementos de a.

a1 . 1 = a1 a 1 . (a + a 2) = a 1 a1 . a + a1 . a2 = a1 0 + a1 . a2 = a1 a1 . a2 = a1 a2 . a1 = a1 a2 . a1 + 0 = a1 a2 . a1 + a2 . a = a1 a 2 . (a 1 + a) = a 1 a2 . 1 = a1 a2 = a1

(B.2.3) (B.2.5) (B.2.4) (B.2.5) (B.2.3) (B.2.2) (B.2.3) (B.2.5) (B.2.4) (B.2.5) (B.2.3)

B.3.7 - Involução Pela definição de complemento conclui-se que

a = a B.3.8 - Leis de De Morgan a1 + a2

a1 . a2

=

=

a1 . a2

a1 + a2

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B-8

Prova-se o teorema recorrendo às igualdades (a1 + a2) + (a 1 . a 2) = 1 (a1 + a2) . (a 1 . a 2) = 0 que por B.3.6 e B.2.5 permitem concluir que a 1 . a 2 é o complemento único de a1 + a2. Para a demonstração recorre-se aos lemas: L1a : a1 + (a 1 + a2) = 1 L1b : a1 . (a 1 . a2) = 0 Demonstração de L1a a1 + (a 1 + a2) = 1 . [a1 + (a 1 + a2)] = (a1 + a 1).[a1 + (a 1 + a2)] = a1 + [a 1 . (a 1 + a2)] = a1 + a 1 = 1

(B.2.3) (B.2.5) (B.2.4) (B.3.4) (B.2.5)

A demonstração de L1b é dual de L1a.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B-9

Demonstração de B.3.9 (a1+a2)+(a 1.a 2)=[(a1+a2)+a 1].[(a1+a2)+a 2] = 1 . 1 = 1

(B.2.4) (L1a) (B.2.3)

(a1+a2).(a 1.a 2)=a1.(a 1.a 2)+a2.(a 1.a 2) = 0 . 0 = 0

(B.2.4) (L1a) (B.2.3)

Por B.2.5 e B.3.6 conclui-se que a1 + a2

A demonstração anterior. As leis de elementos.

a1 .

Morgan

...

...

a1 . a2

a1 . a2

de

De

a1 +

=

+ an

. an

=

=

a1 + a2

=

é

generalizam-se a1 .

a1 +

...

...

dual para

da n

. an

+ an

B.3.9 - Associatividade

∀a, b, c

∈ B : (a + b) + c = a + (b + c)

∀a, b, c

∈ B : (a . b) . c = a . (b . c)

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 10

B.4 - ÁLGEBRA DE BOOLE A DOIS VALORES A Álgebra de Boole a dois valores baseia-se na utilização de 2 estados - 0 e 1, ou verdadeiro e falso - tal como o funcionamento dos circuitos digitais binários. Convenciona-se representar o conjunto vazio por 0 e o universo por 1. B.4.1 - Tabelas das operações Soma lógica 0 0 1 1

+ + + +

0 1 0 1

= = = =

0 1 1 1

Produto lógico 0 0 1 1

+ + + +

0 1 0 1

= = = =

0 0 0 1

Complementação

0 = 1 1 = 0

B.4.2 - Leis da Álgebra de Boole a 2 valores

El. neutro El. absorvente Idempotência Complementaridade Comutatividade Associatividade Distributividade Absorção Absorção Leis de De Morgan Leis de De Morgan

Soma lógica

Produto lógico

0 + a = a 1 + a = 1 a + a = a a + a = 1 a + b = b + a a + (b + c) = (a + b) + c a + b.c = (a + b).(a + c) a + a.b = a a + a .b = a + b a1 + a 2 = a 1 . a 2

1 . a = a 0 . a = 0 a . a = a a . a = 0 a . b = b . a a . (b . c) = (a . b) . c a.(b + c) = a.b + a.c a.(a + b) = a a.( a + b) = a.b a1 . a 2 = a 1 + a 2

a1 + ... + a n =

a1 . ... . a n

a1 . ... . a n =

a1 + ... + a n

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 11

B.4.3 - Simplificação algébrica de funções lógicas A um circuito lógico corresponde uma determinada expressão lógica ou booleana. Simplificar uma expressão corresponde a chegar-se a um circuito menos complexo e com menos portas. • Exemplo de simplificação d = c.b.a + c. b .a + b.a + c.b.a

Utilizando as propriedades comutativa distributiva (B.2.4) obtém-se

(B.2.2)

e

d = c.a.(b + b ) + b.a .(1 + c)

Pela propriedade de complementação elemento absorvente (B.3.3) vem

(B.2.5)

e

O método algébrico não garante a obtenção expressão mais simples. Para tal utiliza-se método gráfico de simplificação.

da um

d = c.a.1 + b.a .1 Assim d = c.a + b.a

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 12

B.4.4 - Aplicação da Álgebra de Boole aos circuitos digitais • Exemplo de aplicação da propriedade do elemento neutro do produto lógico para transformar uma porta AND de 3 entradas numa porta AND de 2 entradas. 1 A B

S Fig 30

A equação do circuito é

S = 1 . A . B

A saída S só é 1 quando A e B são simultaneamente 1. Logo pode-se considerar que o circuito acima é equivalente a um circuito AND de 2 entradas. 1 A B

A S

B

S Fig 31

Prova-se deste modo que o 1 lógico é o elemento neutro do AND ou produto lógico. • Se ligarmos uma das entradas do circuito AND ao 0 lógico, a equação S = A.B.C fica S = A.B.0 Pela definição do AND basta haver uma entrada a zero para que a saída seja 0. Assim vem

S = A.B.0 = 0.

Esta propriedade indica que 0 é o elemento absorvente do circuito AND ou produto lógico. • Uma outra aplicação da propriedade do elemento neutro permite a transformação de um circuito NAND numa porta NOT.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 13

1

S

S = A . 1

A Fig 32

Sendo

A.1 = A

a equação do circuito reduz-se a

S = A Logo, o circuito anterior é equivalente a uma negação, desde que a outra entrada esteja ligada ao 1 lógico. • Outra forma de realizar uma negação pode ser com base num circuito NAND ou NOR.

A S

S = A . A = A

A S

S = A + A = A Fig 33

• Uma outra propriedade, a involução, verificada com 2 circuitos NOT.

A

A

pode

ser

A S Fig 34

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 14

Quando A=0 então A =1 e A =0, pois é a negação de A . Quando A=1 então A =0 e A =1, pois é a negação de A . Fica assim provado que duas formam uma afirmação, ou seja

negações

seguidas

A = A • Também as leis de De Morgan podem ser aplicadas aos circuitos digitais. A 1ª lei de De Morgan diz que um AND com saída negada é equivalente a um OR com entradas negadas. A

A

T

S

B

B T = A + B

S = A . B

Fig 35

O 2º circuito é dual do 1º mas são ambos NAND. Tabela de verdade dos símbolos NAND A 0 0 1 1

B 0 1 0 1

0 0 1 1

. . . .

A . 0 = 1 = 0 = 1 =

B 0 0 0 1

= = = =

1 1 1 0

0 0 1 1

+ + + +

0 1 0 1

A = = = =

+ 1 1 0 0

B + + + +

1 0 1 0

= = = =

1 1 1 0

As duas colunas da direita são iguais pelo que fica provada a igualdade A . B = A + B A 2ª lei de De Morgan afirma que um OR com a saída negada é equivalente a um AND com as entradas negadas.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 15

A

A S

T

B

B S = A + B

T = A . B Fig 36

O 2º circuito é dual do 1º mas são ambos NOR. Tabela de verdade dos símbolos NOR A 0 0 1 1

B 0 1 0 1

0 0 1 1

+ + + +

A 0 1 0 1

+ = = = =

B 0 1 1 1

= = = =

1 0 0 0

0 0 1 1

. . . .

0 1 0 1

A = = = =

· 1 1 0 0

B . . . .

1 0 1 0

= = = =

1 0 0 0

As duas colunas da direita são iguais pelo que fica provada a igualdade A + B = A . B

• Exemplo de realização de um AND a partir apenas de portas NOR. A

A

A + B

1 3

A + B = A . B

B 2 B Fig 37

Os circuitos NOR 1 e 2 são utilizados para fazer as negações dos sinais de entrada. Tem-se assim à entrada do NOR 3: A e B .

Considerando o NOR 3 composto por um OR seguido de um NOT, à saída do OR tem-se a soma A + B .

À saída do circuito total tem-se então A + B . A 2ª lei de De Morgan diz que

A + B = A . B .

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 16

Do ponto de vista prático pode utilizar-se a seguinte regra: o 2º membro obtém-se do 1º dividindo em duas a barra por cima do sinal (+) e trocando-o por (·). Aplicando esta regra à expressão A + B obtém-se A . B

que por sua vez é

A · B .

• Do mesmo modo pode realizar-se um circuito OR a partir apenas de portas NAND. A

A A . B = A + B

B B Fig 38

Aplicando a 1ª lei de De Morgan divide-se a barra e substitui-se o (·) pelo (+). A . B = A + B = A + B • Exemplo de circuito típico em sistemas digitais

A

A.B

B

S = A.B + C.D

C D

C.D Fig 39

O circuito da figura acima tem a equação S = A.B + C.D ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 17

Para realizar este circuito é necessário utilizar 2 caixas de circuitos integrados: uma com portas OR e outra com portas AND. Através de um artifício pode alterar-se esta situação, uniformizando o tipo de portas a usar. Sabendo que 2 negações seguidas são uma afirmação vem

A

A.B

B

S = A.B + C

C D

C.D Fig 40

Apesar do circuito ser diferente, a função lógica realizada é a mesma.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 18

Substituindo agora a porta da direita (NAND) por outra equivalente tem-se A

A.B

B

S = (A.B) . (C.D)

C D

C.D Fig 41

Aplicando a 1ª lei de De Morgan circuito seguida da involução fica

à

saída

deste

A.B . C.D = A.B + C.D = A.B + C.D

Os circuitos NAND e NOR são os mais largamente utilizados pois permitem construir quaisquer circuitos básicos, nomeadamente AND, OR e NOT. Para além disso têm uma estrutura electrónica mais simples o que é vantajoso em termos de espaço e energia consumida. B.4.5 - Portas "XOR" e Equivalência Um circuito que existe também na forma integrada é o somador de 1 bit, "ou exclusivo" ou XOR (exclusive or).

A

S = A⊕ B

S B

Fig 42

Este circuito tem saída 1 quando uma das entradas é 1, mas tem saída 0 se ambas as entradas forem simultaneamente 0 ou 1. Tabela de verdade do circuito XOR A 0 0 1

B 0 1 0

S 0 1 1

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 19

1

1

0

Como a saída é 1 quando A=0 e B=1 ou A=1 e B=0, então o circuito XOR pode ser realizado pela expressão seguinte: S = A .B + A. B

A 0 0 1 1

B 0 1 0 1

0.0 0.1 1.0 1.1

S + + + +

= A .B 0.0 = 0.1 = 1.0 = 1.1 =

+ 0 1 0 0

A. B + 0 + 0 + 1 + 0

= = = =

0 1 1 0

Para a realização deste circuito são necessários dois AND, um OR e dois NOT. A

A.B S = A.B + A

B

A.B Fig 43

Pode, no entanto, realizar-se a mesma função XOR só com circuitos NAND. A

A.A.B A.B

B

S = (A.A.B).(B.A.B

B.A.B Fig 44

Confirmação: A.A.B . B.A.B = = = = =

A.A.B + B.A.B A.A.B + B.A.B A.( A + B ) + B.( A + B ) A. A + A. B + B. A + B. B 0 + A. B + B. A + 0

(B.3.8) (B.3.7) (B.3.8) (B.2.4) (B.2.5)

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 20

= A. B + B. A

(B.2.3)

Outro circuito simples existente na forma de circuito integrado é o circuito equivalência. É um circuito com 2 entradas que tem saída 1 quando A=B, ou seja, quando A=1 e B=1 ou A=0 e B=0. O circuito equivalência tem uma tabela de verdade que é a negação da tabela do cirucito NOR, logo pode obter-se negando a saída do NOR.

A

S = A ⊕ B = A⊗ B

S B

Fig 45

Tabela de verdade do circuito equivalência A 0 0 1 1 B.4.6 - Funções booleanas

B 0 1 0 1 de 2

S 1 0 0 1 variáveis

Tabela de funções x1 x2 y0 y1 y2 y3 y4 y5 y6

0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 1 1 1

0 1 0 0 1 1 0 0 1

1 1 0 1 0 1 0 1 0

y7 y8

0 1

1 0

1 0

1 0

y9 y10 y11

1 1 1

0 0 0

0 1 1

1 0 1

Designação zero produto lógico, ou AND (y = x1.x2) inibição, ou NIX (y = x1 NIX x2) x2 (y = x2) inibição, ou NIX (y = x2 NIX x1) x (y = x) soma módulo 2, ou exclusivo, ou XOR (y = x1 ⊕ x2) soma lógica, ou OR (y = x1 OR x2) NOR (y = x1 NOR x2 , ou y = x1 + x2) equivalência (y = x1 ⊗ x2) complementação de x1, (y = x1) implicação material (x1 ⇒ x2)

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

B - 21

y12 y13 y14

1 1 1

1 1 1

0 0 1

y15

1

1

1

0 complementação de x2, (y = x2) 1 implicação material (x2 ⇒ x1) 0 NAND (y = x1 NAND x2 , ou y = x1 . x2) 1 unidade ou identidade

Estas funções podem ser escritas com base nas 3 operações básicas AND, OR e NOT. y0 y1 y2 y3 y4 y5 y6 y7

= = = = = = = =

0 x1.x2 x1.x2 x2 x2.x1 x1 x1. x2 + x1.x2 x1 + x2

y8 = x1 + x2 y9 = x1. x2 + x1.x2 y10 = x1 y11 = x1 + x2 y12 = x2 y13 = x1 + x2 y14 = x1 . x2 y15 = 1

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-1

SISTEMAS DE NUMERAÇÃO N.1 - INTRODUÇÃO Sendo os circuitos digitais constituídos por elementos dotados de 2 estados distintos, o sistema de numeração binário tem um papel importante no seu estudo. Os sistemas octal (base 8) e hexadecimal (base 16) desempenham também um papel importante para compactar a escrita de um número binário. N.2 - CONVERSÃO DA BASE B PARA A BASE 10 Seja X um número com a seguinte representação na base b. X = an-1an-2 ... a0,a-1 ... a-p

(b)

Cada um dos n+p símbolos ai exprime um número inteiro entre 0 e b-1, tendo um peso igual a bi. O valor numérico de X será então: X = an-1bn-1+an-2bn-2+...+aibi+...+a0b0+a-1b-1+...+a-pb-p Esta expressão permite conhecer a representação decimal de qualquer número desde que se conheça a representação decimal de b e ai. Exemplos 111000,1100101(2) = 25 + 24 + 23 + 2-1 + 2-2 + 2-5 + 2-7 = 56,7890625(10) 55,46(8) = 5×81 + 5 + 4×8-1 + 6×8-2 = 45,59(10)

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-2

Símbolos usados nas bases 2, 8, 10 e 16 Base 2 8 10 16

Símbolos 0, 0, 0, 0, 8,

1 1, 1, 1, 9,

2, 2, 2, A,

3, 3, 3, B,

4, 4, 4, C,

5, 5, 5, D,

6, 6, 6, E,

7 7, 8, 9 7, F

Exemplo 2D,9A(16) = 2×16 + 13 + 9×16-1 + 10×16-2 = 45,60...

Tabela de potências de 2 2i 2 4 8 16 32 64 128 256 512 1024 2048 4096

i 1 2 3 4 5 6 7 8 9 10 11 12

2-i 0,5 0,25 0,125 0,0625 0,03125 0,015625 0,0078125 0,00390625 0,001953125 0,0009765625 0,00048828125 0,000244140625

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-3

N.3 - CONVERSÃO DA BASE 10 PARA A BASE B As partes inteira e fraccionária consideradas separadamente.

do

número

são

N.3.1 - Método da divisão-multiplicação Parte inteira Considere-se um número cuja constituída por 5 símbolos

parte

inteira

é

I = a4a3a2a1a0(b) I = a4b4 + a3b3 + a2b2 + a1b1 + a0b0 Se se dividir I por b e todos os quocientes sucessivamente obtidos, também por b obtém-se I = b.(a4b3 + a3b2 + a2b + a1) + a0 = b.Q1 + a0 Q1 = b.(a4b2 + a3b + a2) + a1 Q2 = b.(a4b + a3 ) + a2 Q3 = b.a4 + a3 Q4 = a4 Verifica-se que os sucessivos restos correspondem aos símbolos que representam I no sistema de base b. Deste modo é possível a conversão de um sistema onde se tenha prática operatória, para qualquer outro sistema. Basta efectuar as operações no primeiro sistema e saber representar no segundo sistema os restos das divisões. Exemplo: Converter 66(10) para a base 2 66 06 0

2 33 13 1

2 16 0

2 8 0

2 4

2

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-4

0

2 0

2 1

66(10) = 1000010(2) Para hexadecimal será 66 02

16 4

66(10) = 42(16) Parte fraccionária Considere-se a parte fraccionária do número com 4 símbolos F = 0,a-1a-2a-3a-4 Multiplicando-se sucessivamente F fraccionárias resultantes por b vem b.F = b.(0,a-1a-2a-3a-4) b.(0,a-2a-3a-4) b.(0,a-3a-4) b.(0,a-4)

= = = =

e

as

partes

a-1,a-2a-3a-4 a-2,a-3a-4 a-3,a-4 a-4

Obtém-se uma sucessão de números cujas partes inteiras correspondem aos sucessivos símbolos de representação de F. Exemplo: Passar 0,468(10) para base 2 2 2 2 2 2 2 2 2

× × × × × × × ×

0,468 0,936 0,872 0,744 0,488 0,976 0,952 0,904

= = = = = = = =

0,936 1,872 1,744 1,488 0,976 1,952 1,904 1,808

0,468(10) = 0,01110111...(2) ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-5

Salvo algumas excepções a dízima na conversão da base 10 para a base 2 é infinita. N.3.2 - Método da subtracção Subtrai-se, do número decimal dado, o peso da base mais elevado possível, o que dá um 1 na posição binária correspondente a esse peso. Continuam-se as subtracções até que o número dado tenha um valor inferior à base. Exemplo: Converter 4645(10) para base 2 O peso de base 2 mais elevado que se pode subtrair de 4645 é 212=4096, que dá 1 na 13ª (12+1) posição à esquerda da vírgula. Resta 549 (4645-4096), sendo agora o peso mais elevado 29=512, dando um 1 na 10ª posição. Fica 37; subtraindo 25=32 dá um 1 na 6ª posição. Fica 5; subtraindo 22=4 dá um 1 na 3ª posição. Fica 1 que dá origem a um 1 na primeira posição. Então: 4645(10) = 1001 000 100 101(2) Se o número for fraccionário, utiliza-se o mesmo método mas com pesos inferiores a 1. Por exemplo 0,52(10) dá origem a 0,100 001 010(2).

N.3.3 - Capacidade de numeração Um sistema de base b em que os números inteiros são representados por uma quantidade n de símbolos tem uma capacidade de numeração m = bn Para que na mudança de base não resulte uma redução da capacidade de numeração, deve observar-se b'n' ≥ bn ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-6

em que b' é a nova base e n' os símbolos do número inteiro de base b'.

• Em particular na conversão de decimal em binário deve ter-se para a parte inteira 2n' ≥ 10n para o que é suficiente n' ≥ 3,33.n

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-7

Critério de paragem de dízimas conversão de base 10 para base 2

infinitas

na

Admitindo para um número na base 10 um erro igual ou inferior ao peso da posição menos significativa (10-p), deve observar-se para a posição menos significativa da posição binária um erro 2-p ≤ 10-p

⇒

p' ≥ 3,33.p

Portanto, se o número se escrever com p símbolos na base 10, deve-se escrever com p' símbolos na nova base, que para o caso da base 2 será p' ≥ 3,33p.

Exemplo: Converter 0,468(10) para base 2 0,468(10) = 0,011 101 1110(2) pois p=3, p' ≥ 3,33×3=9,99, que se arredonda para o inteiro imediatamente superior, ou seja p'=10.

Exemplo: Converter 0,52(10) para base 2 0,52(10) = 0,100 0011(2) pois p=2 ⇒ p'=7.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-8

N.4 - SISTEMA BINÁRIO, OCTAL E HEXADECIMAL N.4.1 - Relação entre as bases 8 e 2 Considerem-se 3 símbolos sucessivos dum número binário. Seja 23k o peso do menos significativo. a3k+2.23k+2 + a3k+1.23k+1 + a3k.23k = (a3k+2.22 + a3k+1.21 + a3k.20).23k = (a3k+2.22 + a3k+1.21 + a3k.20).8k A expressão entre parentesis tem um valor correspondente a um símbolo do sistema octal, com a representação binária a3k+2 a3k+1 a3k A representação binária dos 8 símbolos do sistema octal é Octal 0 1 2 3 4 5 6 7

Binário 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Usando esta correspondencia binário-octal é imediata.

a

conversão

mútua

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T-9

Dado um número na forma binária, converte-se em octal do seguinte modo: • decompõe-se o número a partir da vírgula nos dois sentidos, em grupos de 3 símbolos; • quando o número de símbolos não for múltiplo de 3, completa-se à esquerda e à direita com zeros; • substitui-se cada grupo pelo respectivo símbolo octal. A conversão inversa é evidente. Exemplos 111000,110010100(2) = 111 000,110 010 100(2)= 70,624(8) 1 110,101 10 (2) = 001 110,101 100(2) = 16,54(8)

N.4.2 - Relação entre as bases 16 e 2 Consideram-se agora grupos de conversão hexadecimal-binário.

4

dígitos

para

a

Os sistemas octal e hexadecimal utilizam-se normalmente como representação abreviada do sistema binário, permitindo reduzir o número de símbolos a 1/3 e 1/4 respectivamente.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 10

Relação entre os símbolos hexadecimais e binários Hexadecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F

Binário 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1

A conversão decimal-binário também é muito facilitada por qualquer dos 2 processos seguintes: • Conversão decimal-octal Conversão octal-binário • Conversão decimal-hexadecimal Conversão hexadecimal-binário Exemplo: Converter 54,1(10) para base 2 54,1(10) = 66,06(8) 66,06(8) = 110 110,000 110(2) Para a parte fraccionária p(10)=1, basta portanto 54,1(10) = 110 110,000 1(2) N.5 - ESTUDO DE ALGUNS CÓDIGOS

p'(2)=4,

N.5.1 - Teoria dos códigos - definições Dada uma fonte de informação caracterizada por m mensagens ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 11

M1 M2 ... Mi ... Mm e dado um conjunto de b símbolos chamado alfabeto s1 s2 ... si ... sb faz-se corresponder a cada mensagem Mi um arranjo diferente Xi desses símbolos M1 → X1 (s1 s2 s3 s4) M2 → X2 (s1 s3 s5) ..................... Mi → Xi (s1 s2 s3 s5) ..................... Mm → Xm (s1) A esta lei de correspondência chama-se código. Cada arranjo de símbolos é uma palavra. Ao número b de símbolos distintos utilizados chama-se valência do código. Ao número n de símbolos existente numa palavra chama-se comprimento da palavra. Por exemplo, o comprimento da palavra X2 no código anterior é 3. Normalmente admite-se que as mensagens são independentes e equiprováveis e formam-se códigos em que todas as palavras têm o mesmo comprimento códigos regulares. Neste caso, o número máximo de palavras que é possível formar é bn. Ter-se-à sempre a desigualdade m ≤ bn, ou seja n ≥ log m log b O comprimento mínimo das palavras será então nmín = log m log b ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 12

Redundância define-se como R = n - n mín n Quando o comprimento das palavras é mínimo R=0. Quando o comprimento tende para infinito, R tende para 1. Num código redundante (R>0) o número de símbolos por palavra é superior ao estritamente necessário. No caso de nmín ser fraccionário, a redundância do código será maior que 0, pois tem que se usar um comprimento superior a nmín. A redundância pode ser aumentada intencionalmente no sentido de preservar a quantidade de informação, quando o ruído produz a destruição de alguns símbolos. A redundância constitui pois um meio de reduzir o efeito do ruído. N.5.2 - Formação de códigos regulares Dado um alfabeto de b símbolos palavras distintas de comprimento n.

formam-se

bn

O número de maneiras como essas bn palavras se ordenam é (bn)!. Podem assim formar-se (bn)! códigos regulares diferentes. Pode obter-se um novo código, a partir de um código dado, trocando duas linhas, duas colunas ou dois símbolos. No exemplo abaixo, cada matriz representa um código diferente e cada linha uma palavra de código, sendo que o número de colunas é igual ao comprimento das palavras e o número de linhas igual ao número de mensagens. Exemplo: Partindo do código de valência 3 A B C

A C B

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 13

A A A A B

C A B A B

B B A A A

pode formar-se outro, por troca das duas primeiras linhas:

A A A A B

B A B A B

C B A A A

B B B B B A

A C B A B A

C A A B B B

por troca das duas últimas colunas: A A A A A B

C B B A A A

B C A B A B

ou por troca dos símbolos A e B:

N.5.3 - Códigos ponderados e não ponderados Os códigos dizem-se ponderados quando cada símbolo tem um significado quantitativo dependendo da coluna em que se encontre. Os sistemas de numeração são exemplos de códigos ponderados. A linguagem escrita é um código não ponderado. N.5.4 - Códigos contínuos N.5.4.1 - Adjacência Considerando um conjunto ordenado de b símbolos X1 X2 X3 ... Xi ... Xb-1 Xb Diz-se que 2 símbolos Xi e Xi+1 são adjacentes quando não existir nenhum símbolo Xj que satisfaça as condições Xj < Xi+1 , Xj > Xi Consideram-se também adjacentes o primeiro e último símbolos do conjunto X1 e Xb. ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 14

Um conjunto assim definido é um alfabeto contínuo. • Num código construído com base num alfabeto contínuo, 2 palavras são adjacentes quando os seus símbolos diferem numa única coluna, sendo adjacentes os símbolos nessa coluna.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 15

Exemplo:

palavras adjacentes X1 X3 X4 X5 X1 X3 X5 X5 palavras não adjacentes

X1 X2 X3 X1 X3 X2

X2 X1 X4 X5 X6 X1 X4 X5

• Com um alfabeto contínuo de valência superior a 2 podem formar-se, em relação a cada palavra de comprimento n, 2n palavras adjacentes. • Com um alfabeto contínuo de valência 2, apenas se podem formar n palavras adjacentes. Exemplo:

Em relação a X1 X2 X1 podem formar-se as três palavras adjacentes X2 X2 X1 , X1 X1 X1 , X1 X2 X2.

N.5.4.2 - Códigos contínuos Num código adjacentes.

contínuo, X1 X2 X3 X3 X2

palavras X2 X2 X2 X2 X2

consecutivas

são

X3 X3 X3 X1 X1

Se num código contínuo a última palavra for adjacente da primeira, esse código diz-se cíclico. X1 X2 X3 X2 X2 X3 ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 16

X3 X3 X2 X1

X2 X2 X2 X2

X3 X1 X1 X1

N.5.4.3 - Códigos reflectidos Nos sistemas de numeração, os algarismos de cada coluna sucedem-se pela ordem natural, repetindo-se um número de vezes igual ao peso da respectiva coluna. pesos ...

Sistema de numeração base 3

32 31 30 0 0 0 0 0 1 0 0 2 0 1 0 0 1 1 0 1 2 0 2 0 0 2 1 0 2 2 1 0 0 1 0 1 .. .. .. 2 2 1 2 2 2

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 17

Os sistemas de numeração não constituem códigos cíclicos, pois 2 números consecutivos podem diferir em mais do que 1 algarismo. No entanto, a partir de um sistema de numeração pode construir-se um código contínuo especial, substituindo cada transição de b-1 para 0 pela repetição b-1 b-1, prosseguindo-se então pela ordem inversa até 0. Depois repete-se o 0 e recomeça-se pela ordem natural. Os códigos assim formados dizem-se reflectidos. Exemplo de código reflectido obtido a partir do código anterior 0 0 0 0 0 1 0 0 2 0 1 2 0 1 1 0 1 0 0 2 0 0 2 1 0 2 2 1 2 2 1 2 1 1 2 0 .. .. .. 2 2 1 2 2 2 Os códigos reflectidos não são códigos ponderados embora sejam obtidos a partir de códigos ponderados.

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 18

N.5.5 - Códigos binários Os códigos binários são códigos de valência Utilizam-se normalmente os símbolos 1 e 0. Há 2 tipos de códigos binários: código natural e códigos decimais binários.

2.

binário

• Código binário natural Traduz-se a palavra escrita num dado sistema de numeração para o sistema de base 2. Exemplo:

12(10) = 1100(2)

• Código decimal binário Faz-se a correspondência entre cada caracter decimal da palavra inicial e a sua configuração binária. Se a palavra tiver n símbolos decimais, codificação obtêm-se 4n símbolos binários.

na

sua

Exemplo: Considerando a correspondência seguinte 0 1 2 3 4 5 6 7 8 9

→ → → → → → → → → →

0 0 1 1 1 1 1 0 0 0

0 0 0 0 1 1 1 0 1 1

0 0 0 0 0 0 1 1 1 0

0 1 0 1 0 1 1 1 1 0

a palavra decimal 532(10), é codificada como 1101 1001 1000 ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 19

N.5.5.1 - Código binário natural O código binário natural é um código ponderado. Corresponde ao sistema de numeração de base 2, em que os pesos são sucessivamente 2n-1 2n-2...22 21 20. Exemplo: Comprimento de palavra = 3 22 21 20 0 1 2 3 4 5 6 7

→

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

← pesos

0 1 0 1 0 1 0 1

N.5.5.2 - Código binário reflectido ou de Gray Regra de conversão de natural para reflectido: • O bit mais significativo da palavra natural mantém-se como sendo o bit mais à esquerda da palavra reflectida. • Em seguida, o bit mais significativo da palavra natural adiciona-se ao bit seguinte, e o resultado, independentemente de qualquer transporte, é o bit seguinte da palavra reflectida. • Então adiciona-se o segundo e terceiro bits do natural e obtém-se o terceiro bit do reflectido, desprezando sempre o transporte, e assim por diante. Exemplo: Conversão de 111001(binário Binário natural Binário reflectido

natural)

→ → → → → 1 + 1 + 1 + 0 + 0 + 1 ↓ ↓ ↓ ↓ ↓ ↓ 1 0 0 1 0 1

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 20

Comparação do código binário natural para palavras de comprimento n=4 com o seu homólogo reflectido. pesos →

23 22 21 20 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Binário natural Um código reflectido não valência par é cíclico.

0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

Reflectido é

ponderado.

Se

tiver

N.5.5.3 - Códigos decimais-binários Num código decimal-binário pretende-se substituir cada símbolo decimal por uma configuração de dígitos binários. Como existem 10 símbolos decimais diferentes, é necessário que cada configuração binária apresente 4 bits. No entanto com 4 bits formam-se possíveis e só 10 são necessárias.

16

combinações

O número total de códigos decimais-binários distintos que se podem obter será então dado por

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 21 16 10

10!.C

= 16! = 3.1010 6!

Dada a grande variedade de códigos decimais-binários possíveis, apresentam-se de seguida os mais usuais.

N.5.5.3.1 - Código decimal-binário 8421 ou DCB Escrevem-se em binário os 10 primeiros números. Apresenta a vantagem simplificações do (simplificação nas aritméticas).

0 1 2 3 4 5 6 7 8 9

de permitir uma parte das código binário natural regras das operações

→

8 0 0 0 0 0 0 0 0 1 1

4 0 0 0 0 1 1 1 1 0 0

2 0 0 1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0 1 0 1

← pesos

N.5.5.3.2 - Código D+3 ou excedente 3 0 1 2 3 4 5 6 7 8 9

→

0 0 0 0 0 1 1 1 1 1

0 1 1 1 1 0 0 0 0 1

1 0 0 1 1 0 0 1 1 0

1 0 1 0 1 0 1 0 1 0

Não é um código ponderado. ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 22

N.5.5.3.3 - Código 2421 ou de Aiken

0 1 2 3 4 → 5 6 7 8 9 N.5.5.3.4 - Código 7421

0 1 2 3 4 5 6 7 8 9

→

2 0 0 0 0 0 1 1 1 1 1

4 0 0 0 0 1 0 1 1 1 1

2 0 0 1 1 0 1 0 0 1 1

1 0 1 0 1 0 1 0 1 0 1

← pesos

7 0 0 0 0 0 0 0 1 1 1

4 0 0 0 0 1 1 1 0 0 0

2 0 0 1 1 0 0 1 0 0 1

1 0 1 0 1 0 1 0 0 1 0

← pesos

Este código tem um número muito pequeno de 1's. N.5.5.4 - Códigos decimais-binários detectores de erros Em qualquer sistema podem ser introduzidos erros devido à presença de ruído. Num código binário, tal alteração é a tranformação de 1 em 0 e vice-versa. Aumentando a redundância é possível detectar, ou mesmo corrigir erros. O controle de paridade é um método geral que se utiliza frequentemente. Consiste em acrescentar a cada configuração binária um bit suplementar de ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 23

controle ao qual se dá o valor 0 ou 1, de modo que o número de 1's em todas as palavras seja da mesma paridade. Normalmente usa-se a paridade ímpar para que nunca surja a combinação formada só por zeros, que poderia surgir devido a uma avaria num dispositivo. Exemplo de códigos 8421 e D+3 modificados de forma a detectarem erros. 8421 det. erros

C 1 0 0 1 0 1 1 0 0 1

8 0 0 0 0 0 0 0 0 1 1

4 0 0 0 0 1 1 1 1 0 0

2 0 0 1 1 0 0 1 1 0 0

D+3 det. erros

1 0 1 0 1 0 1 0 1 0 1

C 1 0 1 1 0 0 1 1 0 1

0 0 0 0 0 1 1 1 1 1

0 1 1 1 1 0 0 0 0 1

1 0 0 1 1 0 0 1 1 0

1 0 1 0 1 0 1 0 1 0

C - coluna de controle Se existir uma palavra que não tenha um número ímpar de 1's, existiu um erro na codificação ou no processamento dessa palavra. Este código permite apenas detectar localizar) um número ímpar de erros.

(e

não

O código biquinário, que é um código ponderado, permite a detecção de mais do que 1 erro. pesos

5

0

4

3

2

1

0

0 0 0 0 0 1 1 1 1 1

1 1 1 1 1 0 0 0 0 0

0 0 0 0 1 0 0 0 0 1

0 0 0 1 0 0 0 0 1 0

0 0 1 0 0 0 0 1 0 0

0 1 0 0 0 0 1 0 0 0

1 0 0 0 0 1 0 0 0 0

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 24

No entanto não detecta a situação, de troca de 2 símbolos, seguinte: 0100100 → 0101000. N.5.6 - Códigos alfanuméricos A informação a processar pode não ser exclusivamente numérica. Existe frequentemente a necessidade de codificar além de números, letras e símbolos especiais (+, !, ?, ...). Um código alfanumérico estabelece uma correspondência entre os vários símbolos e combinações de um certo número de bits. As letras do alfabeto e os dígitos decimais formam um conjunto de 36 elementos, sendo pois necessário palavras de código de comprimento pelo menos igual a 6. De seguida exemplifica-se um código alfanumérico de 6 bits utilizado pela Univac. 0000 00 01 10 11

00 01 10 11

0001

Γ Σ

' // !

0010 . | :

0011 0 ; ) +

0100 1 A J /

0101 2 B K S

0110 3 C L T

0111 4 D M U

1000 5 E N V

1001 6 F O W

1010 7 G P X

1011 8 H Q Y

1100 9 I R Z

1101 , # / %

1110 & ⊄ * =

1111 ( @ ?

Ignora Espaço Retorno

Delete

Usando uma configuração binária de comprimento 6 podem codificar-se 64 caracteres, pelo que as combinações para além das 36 inicialmente necessárias podem ser usadas para codificar símbolos especiais tais como os sinais das operações, de pontuação, etc. Actualmente não existe um código universalmente aceite, embora os códigos ASCII (American Standard Committee on Information Interchange) e EBCDIC ____________________________________________________________________________________________________________ Sistemas Digitais ASP93

T - 25

(Extended Binary Coded Decimal Interchange Code) sejam muito utilizados. São ambos códigos de 8 bits, ou seja, permitem uma codificação de 256 caracteres diferentes. Tabela ASCII para os primeiros 128 caracteres 000 001 010 011 100 101 110 111

000 001 010 011 100 101 110 111

0000 NUL DLE Espaço

0 @ P ` p 1000 BS CAN ( 8 H X h x

0001 SOH DC1 ! 1 A Q a q

0010 STX DC2 " 2 B R b r

0011 ETX DC3 # 3 C S c s

0100 EOT DC4 $ 4 D T d t

0101 ENQ NAK % 5 E U e u

0110 ACK SYN & 6 F V f v

0111 BEL ETB ' 7 G W g w

1001 HT

1010 LF SUB * : J Z j z

1011 VT ESC + ; K [ k {

1100 FF FS , < L \ l |

1101 CR GS = M ] m }

1110 SO RS . > N ^ n ~

1111 SI US / ? O _ o

) 9 I Y i y

____________________________________________________________________________________________________________ Sistemas Digitais ASP93

Apresentação

ARQUITECTURA DE COMPUTADORES

Programa:

Bibliografia:

Avaliação:

• • • • • •

Introdução Organização de Sistemas Computorizados Nível Convencional da Máquina Linguagem Assembly Nível da Microprogramação Sistema Operativo

• "Computer Architecture and Organization", John P. Hayes, McGraw Hill, 1978 • "Structured Computer Organization", Andrew S. Tanenbaum, Prentice-Hall, 1990 • "IA-32 Intel® Architecture Software Developer’s Manual

• 1º Caso: • • •

1º 1ª 2º 2ª

trabalho (25%) frequência (25%) trabalho (25%) frequência (25%)

2º Caso: • Exame

(100%)

Nota de aprovação na cadeira: 10 (dez valores)

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I-1

INTRODUÇÃO I.1 - PRINCIPAIS TIPOS DE ORGANIZAÇÃO As arquitecturas de computadores podem classificadas segundo várias perspectivas.

ser

No entanto a mais usada é a classificação de Flynn. Baseia-se no instruções.

número

de

sequências

de

dados

Sequência de dados

Sequência

Simples

Múltipla

Simples

SISD

SIMD

Múltipla

MISD

MIMD

de instruções

SISD SIMD MISD MIMD

-

Single Instruction Single Instruction Multiple Instruction Multiple Instruction

Single Data Multiple Data - Single Data - Multiple Data

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

e

I-2

I.1.1 - MONOPROCESSAMENTO SISD - Computadores Neumann)

convencionais

(modelo

de

Von

I

UC

D

P

M Fig 1

I UC P D M

-

Instruções Unidade de Controle Processador Dados Memória

A arquitectura de Von Neumann pode evoluir de forma a libertar o processador das acções de entrada e saída de dados (gestão do ecrã, disco e teclado). Para tal recorre-se a controladores específicos ou a processadores de âmbito geral. I

UC

P

UC Pio

D

M

M Fig 1a

Pio - Processador de entrada e saída Exemplos de máquinas: IBM PC, Sun Sparc Station.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I-3

I.1.2 - PROCESSAMENTO COM OPERAÇÕES MÚLTIPLAS A rapidez de um computador pode ser aumentada se se introduzir: • componentes mais rápidos (memória mais rápida ou processador mais rápido); • organização diferente. A execução de mais do que uma operação simultaneamente é a maneira mais usual de aumentar a velocidade. • Factor de aumento de velocidade de computação: Sp A =

T1 A ≥ 1 Tp A

p - nº de operações simultâneas Tp[A] - tempo para a computação A na máquina multioperação T1[A] - tempo para a computação A na máquina série • Eficiência de computação: Ep A =

Sp A ≤ 1 p

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I-4

I.1.2.1 - SIMD - Paralelismo de array P1 D1

P2

D2

UC

M

Pn

Dn

I Fig 2

Os processadores são todos iguais e executam a mesma operação ao mesmo tempo sobre dados diferentes. A memória tem que estar particionada de forma a ser possível o acesso simultâneo a diferentes endereços. As máquinas SIMD só correm um programa de cada vez, estando todos os processadores dedicados a esse programa. A instrução seguinte (em linguagem FORTRAN): DO 10 I = 1, 50 10 A(I) = B(I) * C(I) seria executada apenas numa instrução se o computador tivesse 50 multiplicadores. Exemplos de máquinas: ILLIAC IV (64 processadores), Connection Machine (64 k processadores).

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I-5

I.1.2.2 - MISD - Paralelismo de pipeline

M D

D P1

D

P2

Pn

UC1

UC2

UCn

I1

I2

In Fig 3

O paralelismo de pipeline é muito usado nas linhas de montagem industriais. As ideias fundamentais são: • Decompor uma operação complexa em N passos de igual duração •

Efectuar cada operação processamento diferente

num

elemento

de

• O tempo de operação mantém-se, mas o número de operações executadas por segundo multiplica-se por N. A dificuldade é manter o pipeline cheio. Praticamente todos os computadores utilizam paralelismo de pipeline, executando em paralelo o fetch / descodificação / execução de instruções. Exemplos de máquinas: Cray, Cyber 205.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I-6

I.1.2.3 - MIMD - Paralelismo funcional UC1 P1

UC2 P2

D1

D2 M

Ucn Pn

Dn

In I2 I1 Fig 4

• Existem vários processadores não iguais a executar operações independentemente.

forçosamente diferentes

• Paralelismo funcional: * Processamento multi-função - o processador inclui vários elementos de processamento especializados mas não autónomos que podem funcionar em paralelo (somador, multiplicador, etc.); * Multiprocessamento os elementos de processamento são processadores completos, capazes de executar programas completos autonomamente. Exemplos de máquinas: iPSC (16-128 Supernode (16 transputers T800). I.2 - MEMÓRIA

processadores),

Em sistemas de multiprocessadores (MIMD) o acesso a memória implica o recurso a uma rede de interligação. ____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I-7

I.2.1 - Memória partilhada Os processadores não possuem memória própria, podendo todos aceder a qualquer endereço de memória. A memória pode ter vários bancos para evitar a contenção. M

M

M

M

Rede de interligação

P

P

P

P Fig 11

I.2.2 - Memória privada Os processadores possuem memória privada, sendo que qualquer informação pode ser partilhada por meio de mensagens entre processadores. Rede de interligação

P

P

P

P

M

M

M

M Fig 12

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I-8

I.3 - Redes de interligação Definem-se as características seguintes: • Atraso - tempo de trânsito para uma mensagem. •

Largura de banda - número máximo de segundo que a rede consegue transmitir.

bytes

por

• Concetividade de um nó - número de ligações que ligam cada nó aos nós adjacentes. • Diâmetro - número máximo de ligações a percorrer por uma mensagem entre dois processadores quaisquer. I.3.1 - Crossbar É a melhor forma de interligar os processadores à memória. A memória é dividida em vários bancos, e é possível vários processadores acederem a bancos diferentes simultaneamente. M

M

M

M

P

P

P

P Fig 13

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I-9

I.3.2 - Hipercubo A topologia mais popular em memória privada é o hipercubo.

multiprocessadores

de

Tem um baixo diâmetro e alta largura de banda.

Fig 14

I.3.3 - Hiperbus Uma das desvantagens do hipercubo é que o número de ligações por nó varia com a dimensão. O hiperbus é uma topologia que se obtém do hipercubo substituindo nós por ligações e ligações por nós. 1 2 3 4

P1

P2

P3

P4

P5 Fig 15

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I - 10

I.4 - ORGANIZAÇÃO DE SISTEMAS I.4.1 - Redes de computadores Existem várias interligação de anel, etc.

arquitecuras computadores:

possíveis para a estrela, multiponto,

No entanto as arquitecturas de rede mais comuns são: • multiponto - Ethernet;

Fig 16

• anel - Token Ring, FDDI.

Fig 17

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I - 11

I.4.2 - Computação distribuída Os sistemas operativos necessidade de:

distribuídos

aparecem

da

• partilhar recursos distribuídos; • garantir uma maior disponibilidade desses recursos em situações de tráfego intenso; • fornecer tolerância a faltas. Para além disso os sitemas operativos distribuídos devem possuir as seguintes características: • transparência - dar ao utilizador a ideia de que todo o conjunto de máquinas é apenas um processador multi-tarefa; • desempenho - uma aplicação deverá correr tão bem num sistema distribuído como num só processador; • escalabilidade - o sistema deverá poder suportar um número cada vez maior de máquinas. Exemplos de alguns sistemas distribuídos: • AFS, NFS - sistemas de ficheiros distribuídos; • Amoeba - micro-kernel (número reduzido de serviços) • ISIS - comunicação inter-grupos.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

I - 12

I.5 - MÁQUINAS MULTI-NÍVEL Seis níveis que estão computadores modernos

Nível 5

presentes

na

maioria

dos

Nível da linguagem orientada ao problema Tradução (compilador)

Nível 4

Nível da linguagem assembly Tradução (assemblador)

Nível 3

Nível 2

Nível 1

Nível 0

Nível da máquina sistema operativo Interpretação parcial (sistema operativo) Nível da máquina convencional Interpretação (micro-programa) Nível da micro-programação Os micro-programas são executados directamente pelo hardware Nível lógico digital Fig 17a

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P-1

A UNIDADE CENTRAL DE PROCESSAMENTO P.1 - ORGANIZAÇÃO DA CPU Unidade Central de Processamento (CPU) = Processador + Unidade de Controle Unidade de Controle

Memória Central

Registos Processador

Operações Aritméticas

Operações Lógicas

Fig 5

• Os registos do processador acessíveis ao programador.

podem

ou

não

ser

• A existência de registos no processador poupa ciclos de acesso à memória. Por outro lado um número elevado de registos torna difícil um manuseamento eficiente. • Exemplos: PDP-11 tem 6 registos de 16 bit I8085 tem 7 registos de 8 bit I8086 tem 8 registos de 16 bit S/370 tem 16 registos de 32 bit + 4 reg. 64 bit

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P-2

Unidade de Controle Síncrona

Relógio

Processador de Instruções 6

1 Contador de Programa

Incrementador

1 Registo de Instrução 6 Processador de Operações 4

Processador de Endereços

3 Descodificador

2

4 Sequenciador 5

Processador

Memória Central (MAR, MDR) Fig 6

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P-3

1 - Endereço da instrução a ser executada está no PC (contador de programa). Endereço vai para memória (MAR - Registo de endereço de memória). A instrução é trazida para IR (registo de instrução) a partir de MDR (registo de dados de memória). 2 - A instrução é dividida em endereço e código de operação (englobando tipo de endereçamento) que são respectivamente mandados para o processador de endereços e de operações. Código de operação e tipo de endereçamento são descodificados. 3 - O processador de endereços calcula o endereço efectivo que será utilizado para: i) aceder a um operando em memória (MDR) ou num registo; ii) aceder à próxima instrução no caso de um salto. 4 - O operando é lido de memória (MDR), caso seja exigido pelo código de operação. 5 - O sequenciador implementa a operação (podendo incluir um armazenamento em memória). 6 - O endereço da próxima instrução fica no PC: i) se a instrução for um salto, um novo endereço vai para o PC; ii) caso contrário, o incrementador incrementa o PC.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P-4

Função da CPU: Executar armazenadas em memória.

sequência

de

instruções

Ciclo de instrução: sequência de instruções envolvidas no processamento de uma instrução. O ciclo de instrução consiste de aquisição e de uma fase de execução.

uma

fase

de

Fase de aquisição: a instrução é lida da memória para IR. Fase de execução: inclui a descodificação da instrução, aquisição dos operandos necessários e execução das operações especificadas no código de operação. O comportamento da CPU durante um ciclo de instrução pode ser definido como uma sequência de microoperações, cada uma das quais envolve uma transferência entre registos. Tempo de ciclo da CPU (tCPU): tempo necessário para a execução da micro-operação mais rápida. tCPU é a unidade de tempo para medir acções na CPU. fCPU = 1 / tCPU é a frequência do relógio. fCPU depende directamente da tecnologia da CPU.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P-5

Interacção da CPU com a Memória Central i) A CPU é normalmente tão rápida quanto a tecnologia permitir, dentro das condicionantes de custo. ii) Como a capacidadede memória é normalmente elevada, esta é constituída com uma tecnologia mais lenta e menos dispendiosa que a da CPU. Tempo de ciclo de memória (tM): tempo mínimo que medeia entre duas operações consecutivas de acesso à memória.

Extensões à organização básica da CPU i) Registos adicionais ii) ALU's com mais funções iii) Existência de cache se tM pretender uma performance elevada

>>

tCPU

e

se

iv) Existência de controlo automático de stack v) Organização de multi-operação (p.ex. pipeline)

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

se

P-6

P.2 - REPRESENTAÇÃO DA INFORMAÇÃO Instruções Informação

Vírgula fixa

Números Vírgula flutuante

Dados

Dados não numéricos

P.2.1 - Dados não numéricos Normalmente são cadeias de caracteres ("strings") com comprimento variável. Os caracteres são usualmente representados pelos códigos ASCII (American Standard Committee on Information Interchange) ou EBCDIC (Extended Binary Coded Decimal Interchange Code). P.2.2 - Dados numéricos Na escolha factores:

de

representação

atender

aos

seguintes

i) tipo de números a serem representados (inteiros, reais, complexos); ii) gama de valores representáveis; iii) precisão do número; iv) custo de hardware para armazenar e processar os números.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P-7

P.2.2.1 - Nomenclatura w - comprimento da palavra de representação quantidade representados distintamente

gama

de

nos

P.2.2.2 - Formatos dos números Para um mesmo w: Vírgula

fixa - gama limitada, hardware simples;

Vírgula

flutuante - gama extensa, hardware complexo.

maior

precisão,

menor

precisão,

P.2.2.2.1 - Vírgula fixa Nos positivos n

b=

∑ b .2 i

i

= bn ...b2b1b0 .b-1b-2 ...b-m

i=-m

O ponto decimal não tem representação máquina, é implícito pelo utilizador.

interna

Nos negativos i) sinal e módulo ii) complemento para 1 iii) complemento para 2

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

na

P-8

Representação de números Característica

Sinal e módulo

Complemento para 1

Complemento para 2

Zero

000....0 100....0

000....0 111....1

000....0

Amplitude

-2N-1+1 a 2N-1-1

-2N-1+1 a 2N-1-1

-2N-1 a 2N-1-1

Adição Subtracção

Não trivial

Usa EAC

Trivial

Multiplicação Divisão

Relativamente simples

Difícil

Difícil

Inversão de sinal

Trivial

Trivial

Necessita adição

P.2.2.2.2 - Vírgula flutuante Também conhecida por notação científica. 3 quantidades estão associadas a esta representação: mantissa M, expoente E, base B. Um nº vírgula flutuante é guardado como um par de dois números vírgula fixa: M, E. M - fracção ou inteiro E - inteiro A precisão é determinada pelo nº de bits de M. A gama é determinada por B e E.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P-9

NORMALIZAÇÃO Diferentes representações em vírgula possíveis para o mesmo número.

flutuante

são

Considere-se B = 2. • Se a mantissa for uma fracção representada por módulo e sinal, diz-se normalizada se o bit para a direita do ponto binário não for zero. P. ex.: (0.1011101). Se a mantissa for uma fracção representada em complemento para 2, diz-se normalizada se o bit de sinal diferir do bit imediatamente à sua direita. P. ex.: (1.01101) • Para mantissas normalizadas: 1/2

≤

|M| < 1

• Mantissas não normalizadas podem normalizar-se deslocando o ponto binário para a esquerda ou direita e incrementando ou decrementando o expoente apropriadamente. REPRESENTAÇÃO DO ZERO k: nº de bits do expoente i) O expoente convém possível (-2(k-1))

ser

o

menor

número

negativo

ii) O expoente convém ser representado só por zeros, por causa dos testes a zero Utiliza-se algumas vezes um expoente deslocado. O expoente é codificado num código excesso 2(k-1), em que 2(k-1) é o deslocamento. Exemplo (K=4) ____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 10

Expoente 1111 1110 1101 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001 0000

Número representado

7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 11

EXEMPLOS DE FORMATOS VÍRGULA FLUTUANTE HP-1000 15 14

0

15

8 7

M S

Precisão simples

0 E S

E

M (23 bit)

Precisão estendida

M S

E S

E

M (39 bit)

M S

Precisão dupla

E

E S

M (55 bit) Fig 7

I 8086/8087 31 30 Real curto

M S

23 22

16

15

0

E

M (23 bit)

Real longo

63

52 48

M S

E

47

32

31

16

15

0

M (52 bit) Fig 8

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 12

IBM S/370 0

1

7 8

Precisão simples

M S

E

Precisão dupla

M S

E

31 M (24 bit)

M (56 bit)

M S

Precisão estendida

E

M (110 bit) Fig 9

PDP-11 0 Precisão simples

1

8 9

M S

15

16

31

E

M (23 bit)

Precisão dupla

M S

E

M (55 bit) Fig 10

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 13

P.2.3 - Formatos de instruções (máquina) • Cada instrução deve especificar de algum modo: 1. Operação a ser executada. 2. Um ou mais operandos da operação. 3. Destino do resultado. 4. Localização da próxima instrução. • i) O código especificado

da

operação

deve

ser

sempre

ii) A localização da próxima instrução só precisa de ser indicada em instruções de salto. iii) Os endereços são normalmente apontadores para memória ou para registos que contêm operandos. Variações principais: endereços imediato, indexado, indirecto e relativo (PC, SP). Exemplos:

EE = E + (IX)

-

indexado

EE = (E)

-

indirecto

iv) Existem instruções de 1, 2 e 3 endereços (0 endereços é um caso particular em máquinas de stack). Poucos endereços - Instruções mais simples, programas mais longos e com maior tempo de execução e unidades de controle mais simples. • Instruções com 3 endereços Instruções

normais: 2 campos para endereços de operando + 1 campo para endereço de resultado

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 14

Instruções

de

salto: 2 campos para endereços de operando + 1 campo para endereço de salto

Exemplo de programa fonte: X := A + B * C; Y := F + G; Programa máquina correspondente MPY ADD ADD Ex. de máquina:

B A F

C T G

T X Y

CDC 6600

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 15

• Instruções com 2 endereços Instruções normais: 2 endereços de operandos Instruções de salto: 1 end. operando + 1 end. salto Existe normalmente um acumulador que recebe o resultado. Alternativamente o resultado pode ir para um dos endereços especificados. Exemplo

Ex. de máquina:

MPY ADD STO ADD STO

B C A Acc Acc X F G Acc Y

IBM S/370

• Instruções com 1 endereços Instruções normais: endereço de operando Instruções de salto: endereço de salto O resultado é deixado no acumulador Exemplo de máquinas: HP 1000, DEC 10

FETCH MPY ADD STO FETCH ADD STO

B C A X F G Y

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 16

• Instruções com 0 endereços Requer uma máquina de "stack" Necessário: i) um stack ii) uma instrução PUSH iii) uma instrução POP iv) operações diádicas usando os 2 registos do topo como operandos e deixando o resultado no topo do stack O compilador transformará as expressões aritméticas para Reverse Polish Notation. No exemplo X := A + B * C; → Y := F + G; (RPN)

X = B C * A + Y = F G +

Código máquina correspondente PUSH C PUSH B MPY PUSH A ADD POP X PUSH G PUSH F ADD POP Y

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 17

P.3 - UNIDADES ARITMÉTICAS E LÓGICAS P.3.1 - Adição, Subtracção e Operações lógicas As operações lógicas são normalmente realizadas bit a bit pelo que os circuitos não apresentam qualquer dificuldade. Exemplo de um circuito AND de 8 bits. x0 y0

z0

x1 y1

z1

x2 y2

z2

x7 y7

z7 Fig 18a

A adição é realizada bit a bit também, mas entrando em conta com o bit de carry. O somador de 1 bit é definido pelas duas equações seguintes:

zi = xi ⊕ yi ⊕ ci+1 ci = xi yi + xici+1 + y ici+1 Os circuitos lógicos e símbolo correspondentes são mostrados abaixo. ____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 18

xi c(i+1)

yi

xi c(i+1)

yi zi

xi c(i+1)

Soma

yi

zi xi c(i+1)

yi ci

+

Carry out

c(i+1) Carry in

xi xi yi

yi

xi c(i+1)

ci

yi c(i+1) Fig 18

A adição pode ser acelerada com "carry look ahead adders".

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 19

P.3.2 - Multiplicação

Circuito multiplicador

Acumulador 7

A

Multiplicador 0

7

Q

Multiplicando 7

0

M

0

Somador paralelo Bus Saída Bus Entrada

CPU

START END CLOCK

Controle

ADD RIGHT-SHIFT

Sinais de controle interno

Contador Fig 19

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 20

i) Multiplicação em módulo e sinal

START

A <- 0 COUNT <- 0 M <- Mcando

Q <- Mcador

S

Q(0) = 0

COUNT <- COUNT + 1

N

A <- A(0:6) + M(0:6)

Right Shift A,Q

COUNT = 7 N

S

Bus Saída <- A

Bus Saída <- Q

STOP

Diag 1

No final da operação A S 7

Q

0

7

0

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 21

ii) Multiplicação em complemento para 2 Pode usar-se o algoritmo de multiplicação em M e S e adaptá-lo para complemento para 2, mas torna-se necessário corrigir o resultado quando o multiplicador é negativo. Utiliza-se normalmente o algoritmo de Booth que trata igualmente nos positivos e nos negativos sem ser necessária a correcção, e além disso sequências de 0's e 1's no multiplicador são saltadas sem se efectuarem adições ou subtracções o que acelera a execução. (Demonstração: HAYES, 183-185) Hardware semelhante ao multiplicador em M e S mas com mais um andar em Q e possibilidade de soma e subtracção. Operação básica: Multiplicador é inspeccionado sequencialmente da direita para a esquerda. Dois bits são inspeccionados de cada vez, se QiQi+1 = 10 (01) o multiplicando é somado (subtraído) ao produto parcial e o resultado é deslocado. Se QiQi+1 = 00 ou 11 só se verifica o deslocamento.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 22

Multiplicação (Algoritmo de Booth)

START

A <- 0 COUNT <- 0 M <- Mcando Q(-1) <- 0

Q(7:0) <- Mcador

A(7) <- A(7) Right Shift A,Q

Q(-1) = 1 Q(0) = 0

N

S

Q(-1) = 0 Q(0) = 1

N

S COUNT <- COUNT + 1

A <- A + M

A <- A - M

COUNT = 7 N S Bus Saída <- A

Bus Saída <- Q(7:1)

STOP Diag 2

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 23

P.3.3 - Divisão

D=QxV+R Objectivo: determinar Q e algumas vezes R. Nº de bits em Q limitado por questão de hardware.

Algoritmos e circuitos semelhantes multiplicação podem ser utilizados.

aos

da

• Na multiplicação efectuam-se adições sucessivas do multiplicando ao produto parcial para obter o produto. • Na divisão o divisor deslocado é subtraído do resto parcial para obter o quociente. Em cada passo i, 2-i.V (divisor deslocado de i bits para a direita) é comparado com o resto parcial Ri. Qi = 1 Ri+1

←

se

2-i.V

≥

Ri ,

Qi = 0

se

2-i.V < Ri

Ri - Qi.2-i.V

Na implementação prefere-se deslocar o resto parcial. Ri+1

←

2.Ri - Qi.V

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 24

Algoritmo de divisão para inteiros positivos

START

Q <- Dividendo COUNT <- 0

M <- Divisor A <- 0

Left Shift A,Q

A <- A - M COUNT <- COUNT + 1

A < 0

S

N Q(0) <- 1

Q(0) <- 0 A <- A + M

COUNT = 7 N S

STOP Diag 3

No final da operação: (A) = resto (Q) = quociente

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 25

Circuito divisor

Acumulador A

7

Quociente 0

7

Q

Divisor 0

7

M

0

Somador paralelo Bus Saída Bus Entrada

A(7)

START END CLOCK

CPU

Controle

Q(0)

Sinais de controle interno

Contador Fig 20

Início:

A,Q - Dividendo M - Divisor

Fim:

Q A

- Quociente - Resto

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 26

P.3.4 - ALU vírgula fixa (típica)

Multiplicador-Quociente

Acumulador 7

AC

0

7

MQ

0

Registo de dados 7

RD

0

Somador paralelo Bus Saída Bus Entrada

CPU

ADD SUB MPY DIV START END CLOCK

Controle

Sinais de controle interno

Contador Fig 21

ADD SUB MPY DIV

: : : :

AC ← AC AC ← AC AC,MQ ← AC,MQ ←

+ RD - RD RD × MQ AC,MQ ÷ RD

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 27

P.3.5 - Operações em vírgula flutuante X = (XM, XE)

⇒

X = XM . BXE

São feitas as seguintes suposições: • XM é uma fracção com NM bits em complemento para 2. • XE é um inteiro com NE bits em código excesso 2 NE-1. • B = 2. • Operandos e resultados são normalizados. Operações Aritméticas Básicas X + Y = ( XM . 2 (XE-YE) + YM ) . 2YE X - Y = ( XM . 2 (XE-YE) - YM ) . 2YE X . Y = ( XM . YM ) . 2(XE+YE) X ÷ Y = (XM ÷ YM) . 2(XE-YE) Adição e subtracção requerem, supondo que XE ≤ YE • Calcular YE - XE (subtracção vírgula fixa) • Deslocar XM de (YE - XE) bits para a direita para formar XM . 2(XE-YE) • Calcular XM . 2(XE-YE) ± YM Multiplicação e divisão requerem: • Multiplicação mantissas.

ou

divisão

vírgula

fixa

das

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 28

• Soma ou subtracção vírgula fixa dos expoentes. Em qualquer das 4 operações é necessário normalizar o resultado. Correcções necessárias por causa do deslocamento do expoente: • Se os expoentes são somados (subtraídos) o expoente vem com um deslocamento duplo e o resultado tem que ser corrigido por subtracção (soma) do deslocamento. Exemplo:

desloc. = 8 ,

NE = 4 ,

XE = 7 ,

YE = -3

XE = 1111 YE = 0101 -----------XE + YE = 10100 Correcção - 1000 -----------01100 • Se na multiplicação um dos factores for zero o resultado não tem necessáriamente um expoente zero. É então necessário um outro passo na operação para colocar o expoente a zero. ALU vírgula flutuante

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 29

Unidade de expoente E1

E2

Somador

Unidade de mantissa AC

MQ

RD

Somador

E

BUS de Dados Fig 22

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 30

P.4 - UNIDADES DE CONTROLE MICROPROGRAMADAS P.4.1 - Introdução Controle hardwired processador de implementado exclusivamente em hardware

operações

Controle microprogramado - processador de operações implementado com base numa memória, normalmente do tipo ROM. Controle hardwired é muito dispendioso e não flexível.

mais

rápido,

mas

Microprogamação - método de desenho do processador de operações em que os sinais de controle e de informação para a sequência de controle estão armazenados numa memória de controle (MC). Microinstrução - uma palavra da MC. Cada microinstrução especifica de algum modo os sinais de controle e a próxima microinstrução a ser executada. Controle microprogramado é mais lento que o hardwired, mas bastante mais flexível e com uma implementação estruturada. Firmware - Software e hardware envolvidos na unidade de controle microprogramada. Microprograma - conjunto de microinstruções interpretam uma instrução máquina.

que

Emulador da linguagem L - conjunto de microprogramas que interpretam o repertório de instruções da linguagem L. P.4.2 - Modelo de WILKES

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 31

Endereço Externo Campo de Endereço

Registo Endereço Matriz Comandos

Matriz Endereços Descodif.

Sinais de controle

Condição externa Fig 23

MEMÓRIA DE CONTROLE = MATRIZ DE COMANDOS + MATRIZ DE ENDEREÇOS

P.4.3 - Comprimento da microinstrução Comprimento da microinstrução depende de: • Grau de paralelismo micrinstrução;

exigido

ao

nível

da

• Modo como a informação de controle é codificada; • Modo como o próximo endereço é especificado (vulgar existir num µPC). Microinstruções horizontais

i) formatos longos ii) implementam um elevado grau de paralelismo iii) pouca codificação no campo de controle

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 32

Microinstruções verticais

i) formatos curtos ii) pequena capacidade de implementar operações paralelas iii) codificação considerável no campo de controle

Definições extremas: microinstrução horizontal não codificação de informação de controle

há

qualquer

microinstrução vertical - especifica só uma microoperação (nenhum paralelismo) Campo de controle

Campo de controle

Descodificador Horizontal

Vertical Fig 24

P.4.4

-

Organização de microprogramada

uma

unidade

de

controle

Formato da microinstrução T

S

C Fig 25

T - Campo de teste S - Endereço de salto C - Campo de controle

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 33

Endereço externo End. salto Condições externas

MPX

Load

µ PC

Contador de microprograma

Increment

Selector de condição

Memória de controle

MC

T

S

C

CMDR

(Control Memory Data Register)

Descodif.

Sinais de controle Fig 26

P.4.5 - Escrita de microprogramas A escrita de microprogramas pode ser comparada à escrita de programas em Assembly, embora seja necessário ter um conhecimento profundo da máquina. Utilizam-se linguagens do tipo MICRO ASSEMBLY. O tradutor será o MICRO ASSEMBLER. P.4.6 - Exemplo de CPU microprogramada

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 34

AC=0 C0(ADD) C1(AND) C2(COMP)

ALU

AC

C12

C3(READ) C4(WRITE)

Memória Central

C5

C6

C8

C11

MDR C7

PC

C9

IR

C10

MAR AC=0

Circuitos de controle

C0 C12 Fig 27

Repertório Mnemónica LOAD X STORE X ADD X AND X JUMP X JUMPZ X COMP RSHIFT

de instruções máquina Descrição AC ← M(X) M(X) ← AC AC ← AC + M(X) AC ← AC ∧ M(X) PC ← X if AC=0 then PC ← X AC ← AC/ Right Shift AC

Micro-operações para interpretação do repertório de instruções ____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 35 START

MAR ← PC

READ M

PC ← PC + 1 IR ← MDR (OP)

N LOAD

S MAR ← MDR(AD)

STORE

S MAR ← MDR(AD)

N

N ADD

N AND

S

S

MAR ← MDR(AD)

N

N

N

JUMP

JUMPZ

COMP

S

S

S

MAR ← MDR(AD)

N AC = 0

READ M

MDR ← AC

READ M

READ M

AC ← MDR

WRITE M

AC ← AC + MDR

AC ← AC ∧ MDR

S PC ← MDR (AD)

PC ← MDR (AD)

AC ← AC/

SHIFT AC

Diag 4

Emulador (linguagem simbólica) FETCH: MAR ← PC READ M PC ← PC +1 , goto IR LOAD:

IR ← MDR (OP)

MAR ← MDR (AD) READ M AC ← MDR , goto FETCH

STORE: MAR ← MDR (AD) MDR ← AC WRITE M , goto FETCH ADD:

MAR ← MDR (AD)

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 36

AND:

JUMP:

READ M AC ← AC + MDR ,

goto FETCH

MAR ← MDR (AD) READ M AC ← AC ∧ MDR ,

goto FETCH

PC ← MDR (AD) , goto FETCH

JUMPZ: if AC 0 then goto FETCH PC ← MDR (AD) , goto FETCH COMP:

AC ← AC/ ,

goto FETCH

RSHIFT: Right-Shift (AC) , Sinais de controle C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12

goto FETCH Operação controlada AC ← AC + MDR AC ← AC ∧ MDR AC ← AC/ MDR ← M(MAR) [READ M] M(MDR) ← MDR [WRITE M] MDR ← AC AC ← MDR MAR ← MDR (AD) PC ← MDR (AD) PC ← PC + 1 MAR ← PC IR ← MDR (OP) Right-Shift AC

P.4.7 - O processador HP 21 MX Formatos das µinstruções (HP 21 MX)

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 37

0

4 OP CODE

1. Common

0 OP CODE

2. Immediate

0 3. Conditional jump

OP CODE

0 4. Unconditional jump

9

ALU Funct

14

Source reg

6 4 Modi Immediate operand fier 4

9 10

Cond Select

C S

4

Dest reg

14

23 Special

19 Dest reg

23 Special

19

9 bit relative addr

7

OP CODE

19

23 Special

19 12 bit absolute address

23

Jump modif Fig 29

Formato das instruções em µAssembly tipo common

campo 1 label

campo 2 op code

campo 3 special

immediate

label

imm

special

conditional jump unconditional jump

label

jmp

cnd x

label

jmp ou jsb ou rtn

jump modifier

campo 4 alu function modifiers condition select

campo 5 dest. register dest. register condition sense

unused

unused

campo 6 source reg. operand

campo 7 comment

branch address branch address

comment

comment

comment

Estrutura do HP 21 MX

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

P - 38 T-BUS (16 bit) Descodificadores e lógica de controle PC

(P)

ALU fixed point

X

Sinais de controle

CMDR

Y S12 Memória

A

B Memória de controle

Central L

S2 (M) MAR

MDR (T)

S1

CMAR

SAVE

S 15

16

16 IR

S-BUS (16 bit) 8

COUNT I / O Fig 28

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-1

A FAMÍLIA 8086 X.1 - INTRODUÇÃO A família de microprocessadores 8086 inclui os CPU's i8086 e i8088. Algumas características: O 8088 comunica externamente através de um canal de 8 bits.

com

a

memória

e

I/O

O 8086 comunica com a memória e I/0 por um canal de 16 bits. Ambos podem endereçar linhas de endereço).

até

1

Mbyte

de

memória

(20

Ambos possuem um pipeline de instruções interno que faz a pré-aquisição de instruções (prefetch) durante os ciclos livres do BUS, o que aumenta muito o desempenho. Ambos possuem canais internos de dados de 16 bits. 4

8086

16

12 Endereço Dados/Endereço

Endereço

8088

Controle

8

Dados/Endereço Controle Fig 30

X.2 - A ARQUITECTURA DOS PROCESSADORES

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-2

Unidade de interface com o BUS (BIU)

Unidade de execução (EU) Registos Gerais

Registos de segmento Ap Instr (IP)

Geração de endereços e controle do BUS

BUS Multiplexado

Operandos Fila de instruções

ALU

Flags Fig 31

Os endereços manipulados pela EU são de 16 bits. A BIU realiza uma relocação de endereços que permite o acesso a um espaço de memória de 1 Mbyte. A BIU executa sistema:

todas

as

operações

com

o

BUS

do

• Troca de dados entre a EU e a memória do sistema e dispositivos de I/O. • Enquanto a EU está ocupada a executar instruções, a BIU lê na memória central as próximas instruções a realizar (prefetch). X.2.1 - Registos gerais O 8086 tem um conjunto de 8 registos gerais de 16 bits organizados da seguinte forma: ____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-3

15

8 7 AX AH

0 AL

Acumulador

BL

Base

CL

Contador

BX Grupo de dados

BH CX CH DX DH 15

Grupo de apontadores e índices

Dados

DL 0 SP

Apontador de Stack

BP

Apontador de base

SI

Índice de origem

DI

Índice de destino Fig 32

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-4

Algumas instruções implícita. Registo AX AL AH BX CX CL DX SP SI DI

usam

os

registos

de

forma

Operações Multiplicação, divisão, I/O (Word) Multiplicação, divisão, I/O (Byte) Multiplicação, divisão (Byte) Tradução Loops, operações com strings Rotação e deslocamento de variáveis Multiplicação, divisão, (Word); I/O indirecto Operações de stack Operações com strings Operações com strings

X.2.2 - Registos de segmento e apontador de instrução O espaço de memória do 8086 está dividido segmentos lógicos de até 64 kbyte cada um.

em

O CPU tem acesso a 4 segmentos em simultâneo. Os seus endereços de base estão contidos nos registos de segmento. 15

0 CS

Segmento de código

DS

Segmento de dados

SS

Segmento de Stack

ES

Segmento extra Fig 33

O apontador de instrução (IP) é um registo de 16 bits que

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-5

• em execução normal tem o offset relativo a CS da próxima instrução a ser fetched pela BIU; • quando é guardado na stack tem o valor da próxima instrução a ser executada. X.2.3 - Flags O 8086 tem 3 flags de controle que podem ser alteradas pelos programas para alterar as operações do processador, e 6 flags de estado que reflectem certas propriedades do resultados das operações aritméticas ou lógicas. Flags de controle

TF

DF

IF

Flags de estado

OF

SF

ZF

AF

PF

CF

Carry Paridade Auxiliar Zero Sinal Overflow Interrupt Enable Direcção Trap Fig 34

• carry - carry ou borrow no bit mais significativo (MSB) de um resultado (8 ou 16 bits) • paridade - paridade par quando activa

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-6

• auxiliar - carry ou borrow entre nibbles (usada por aritmética decimal) • zero - o resultado da operação é 0 • sinal - o MSB é 1 (número negativo) • overflow - perda de um bit significativo •

interrupt enable - permite que o CPU reconheça interrupções externas (mascaráveis)

• direcção - quando activa provoca o auto-decremento nas intruções sobre strings, de contrário provoca o auto-incremento • trap - põe o processador no modo single-step para debugging

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-7

X.3 - MEMÓRIA X.3.1 - Organização O espaço de memória do 8086 conjuntos de bytes (8 bits).

está

organizado

em

• Instruções e dados podem ser guardados em quaisquer endereços sem ter em atenção alinhamento algum. O código fica densamente arrumado, poupando memória. No entanto, variáveis de 16 bits com endereços ímpares (não alinhadas) não aproveitam a capacidade de transferência de 16 bits em simultâneo do 8086. As instruções não precisam de estar alinhadas. • Variáveis de 16 bits (word) são guardadas em memória com o byte menos significativo na posição de memória mais baixa. Apontadores (doubleword) são compostos por 2 words. A word de endereço mais baixo contém um offset. A word de endereço mais elevado contém o endereço base do segmento.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-8

X.3.2 - Segmentação O espaço de memória de 1 Mbyte do 8086 é visto pelos programas como um grupo de segmentos de até 64 kbytes definidos por cada aplicação. Os segmentos bytes.

têm

endereços

base

múltiplos

de

16

Os segmentos podem ser adjacentes, disjuntos, parcialmente ou totalmente sobrepostos. Um endereço físico pode estar contido num ou mais segmentos.

FFFFFH A B C Dados:

DS:

B

Código: CS:

E

Stack:

SS:

H

Extra:

ES:

J

D E F G

H I

J K 0H Fig 35

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X-9

X.3.3 - Geração de endereços físicos Cada posição de memória tem apenas um endereço físico, mas pode ter vários endereços lógicos. Um endereço físico pode variar entre 0H e FFFFFH. Um endereço lógico é dado por 2 valores: base do segmento e offset. Deslocar 4 bits à esquerda

1

2

3

4

15 1

2

3

4

0

0

19

0

0

0

2

15 0

0

2

2

Endereço lógico

Offset

2 0

2

15 1

Base do segmento

0 3

6

Endereço físico

2

19

0

Para a memória Fig 36

Origens dos endereços lógicos Tipo de referência a memória Aquisição de instrução (fetch) Operação em stack Variável (excepto seguintes) String de origem String de destino BP como registo de base

Base de segmento por omissão CS SS DS DS ES SS

Base de segmento alternativo Nenhum Nenhum CS,ES,SS CS,ES,SS Nenhum CS,DS,ES

Offset IP SP Endereço efectivo SI DI Endereço efectivo

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 10

X.3.4 - Implementação da Stack (pilha) A stack no 8086 encontra-se em memória e é referenciada pelos registos SS (stack segment) e SP (stack pointer). Um sistema pode ter um número ilimitado de stacks, e uma stack pode ter até 64 kbytes de capacidade. Apenas se pode endereçar uma stack de cada vez. As operações na stack são sempre sobre 16 bits. Um valor é carregado (PUSHed) em stack decrementando o SP 2 unidades e escrevendo o valor na stack. Um valor é retirado (POPed) da stack lendo-o do topo da stack e incrementando o SP 2 unidades. PUSH AX AX 1 2 3 4

Fim da stack

TOS

1062 1060 105E 105C 105A 1058 1056 1054 1052 1050

0 2 4 6 8 A 0 4 8 C

0 2 4 6 8 A 1 5 9 D

1 3 5 7 9 B 2 6 A E

1 3 5 7 9 B 3 7 B F

POP AX POP BX

TOS Fora da stack

1062 1060 105E 105C 105A 1058 1056 1054 1052 1050

0 2 4 6 8 A 1 4 8 C

0 2 4 6 8 A 2 5 9 D

1 3 5 7 9 B 3 6 A E

1 3 5 7 9 B 4 7 B F

TOS

AX 1 2

3 4

BX 1 2

3 4

1062 1060 105E 105C 105A 1058 1056 1054 1052 1050

0 2 4 6 8 A 1 4 8 C

0 2 4 6 8 A 2 5 9 D

1 3 5 7 9 B 3 6 A E

1 3 5 7 9 B 4 7 B F

1 0

5 0 SS

1 0

5 0 SS

1 0

5 0 SS

0 0

0 8 SP

0 0

0 6 SP

0 0

0 A SP Fig 37

Operação em stack para a sequência de código PUSH AX POP AX POP BX X.4 - INSTRUÇÕES X.4.1 - Instruções de transferência de dados ____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 11

MOV destino, origem PUSH origem POP destino XCHG destino, origem XLAT tabela IN acc, porto OUT porto, acc LEA destino, origem LDS destino, origem LES destino, origem LAHF SAHF PUSHF POPF

Âmbito Geral Move byte ou word Carrega word na stack Retira word da stack Troca byte ou word Traduz byte Entrada / Saída Lê byte ou word Escreve byte ou word Endereço Carrega endereço efectivo Carrega apontador usando DS Carrega apontador usando ES Transferência de flags Coloca as flags em AH Coloca AH nas flags Carrega as flags na stack Retira flags da stack

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 12

X.4.2 - Instruções aritméticas

ADD destino, origem ADC destino, origem INC destino AAA DAA SUB destino, origem SBB destino, origem DEC destino NEG destino CMP destino, origem AAS DAS MUL origem IMUL origem AAM DIV origem IDIV origem AAD CBW CWD

Adição Adiciona byte ou word Adiciona byte ou word com carry Incrementa byte ou word 1 unidade Ajusta ASCII para adição Ajusta decimal para adição Subtracção Subtrai byte ou word Subtrai byte ou word com borrow Decrementa byte ou word 1 unidade Nega byte ou word Compara byte ou word Ajusta ASCII para subtração Ajusta decimal para subtacção Multiplicação Multiplica byte ou word sem sinal Multiplicação inteira de byte ou word Ajuste ASCII para multiplicação Divisão Divide byte ou word sem sinal Divisão inteira de byte ou word Ajuste ASCII para divisão Converte byte em word Converte word em doubleword

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 13

X.4.3 - Instruções de manipulação de bits

NOT destino AND destino, origem OR destino, origem XOR destino, origem TEST destino, origem SHL / SAL destino, count SHR destino, count SAR destino, count

ROL destino, count ROR destino, count RCL destino, count RCR destino, count

Lógicas Complementa byte ou word Produto lógico de byte ou word Soma lógica de byte ou word Ou exclusivo de byte ou word Teste (AND) de byte ou word Deslocamentos Deslocamento lógico / aritmético de byte ou word à esquerda Deslocamento lógico de byte ou word à direita Deslocamento aritmético de byte ou word à direita Rotações Roda byte ou word à esquerda Roda byte ou word à direita Roda byte ou word com carry à esquerda Roda byte ou word com carry à direita

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 14

X.4.4 - Instruções sobre strings

REP REPE / REPZ REPNE / REPNZ MOVS destino, origem MOVSB / MOVSW CMPS destino, origem SCAS destino LODS origem STOS destino

Repete Repete enquanto for igual / zero Repete enquanto não for igual / não zero Move string de bytes ou words Move string de bytes ou words Compara string de bytes ou words Pesquisa string de bytes ou words Lê string de bytes ou words Escreve string de bytes ou words

Registos e flags utilizados SI DI CX AL / AX

DF ZF

Índice (offset) da string origem Índice (offset) da string destino Contador de repetições Valor para pesquisa Destino para LODS Origem para STOS 0 = auto-incrementa SI, DI 1 = auto-decrementa SI, DI Termina pesquisa ou comparação

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 15

Fluxo das operações com strings Inicializa SI, DI, CX e DF

Prefixo REPEAT

Ausente

Presente

CX = 0

S

N

Decrementa CX 1 unidade

Opera string usando SI / DI

Ajusta SI / DI de delta

CMPS ou SCAS

N

Presente

S

String

DF

Byte Byte Word Word

0 1 0 1

delta 1 -1 2 -2

Prefixo

z

REPE REPZ REPNE REPNZ

1 1 0 0

ZF = z

S

N

Prefixo REPEAT

Ausente

Próxima instrução

Diag 5

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 16

X.4.5 - Instruções de transferência de controle Transferências incondicionais CALL nome-de-rotina Chama procedimento RET valor-a-retirar (op) Volta de um procedimento JMP endereço Salta Transferências condicionais JA / JNBE rótulo Salta se superior / não inferior nem igual JAE / JNB rótulo Salta se superior ou igual / não inferior JB / JNAE rótulo Salta se inferior / não superior nem igual JBE / JNA rótulo Salta se inferior ou igual / não superior JC rótulo Salta se carry JE / JZ rótulo Salta se igual / zero JG / JNLE rótulo Salta se superior / não inferior nem igual JGE / JNL rótulo Salta se superior ou igual / não inferior JL / JNGE rótulo Salta se inferior / não superior nem igual JLE / JNG rótulo Salta se inferior ou igual / não superior JNC rótulo Salta se não carry JNE / JNZ rótulo Salta se não for igual / não zero JNO rótulo Salta se não overflow JNP / JPO rótulo Salta se não paridade / paridade ímpar JNS rótulo Salta se não tiver sinal JO rótulo Salta se overflow JP / JPE rótulo Salta se paridade / paridade par JS rótulo Salta se tiver sinal Controle de iteração LOOP rótulo Ciclo LOOPE / LOOPZ rótulo Ciclo se igual / zero LOOPNE / LOOPNZ rótulo Ciclo se não igual / não zero JCXZ rótulo Salta se CX = 0 Interrupções INT tipo Interrupção INTO Interrupção se overflow IRET Volta de interrupção

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 17

Mnemónica JA / JNBE JAE / JNB JB / JNAE JBE / JNA JC JE / JZ JG / JNLE JGE / JNL JL / JNGE JLE / JNG JNC JNE / JNZ JNO JNP / JPO JNS JO JP / JPE JS

Condições testadas (CF ou ZF) = 0 CF = 0 CF = 1 (CF ou ZF) = 1 CF = 1 ZF = 1 ((SF xor OF) ou ZF) = 0 (SF xor OF) = 0 (SF xor OF) = 1 ((SF xor OF) ou ZF) = 1 CF = 0 ZF = 0 OF = 0 PF = 0 SF = 0 OF = 1 PF = 1 SF = 1

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 18

X.4.6 - Instruções de controle do processador

STC CLC CMC STD CLD STI CLI HLT WAIT ESC LOCK NOP

Operações com flags Activa flag de carry Desactiva flag de carry Complementa flag de carry Activa flag de direcção Desactiva flag de direcção Activa flag de interrupt enable Desctiva flag de interrupt enable Sincronização externa Pára até interrupção ou reset Espera até pino TEST/ estar activo Escape para processador externo Prende o bus para a próxima instrução Sem efeito Não efectua nenhuma operação

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 19

X.5 - MODOS DE ENDEREÇAMENTO Cálculo dos endereços de memória Índice simples

Codificado na instrução

Explícito na instrução

Índice duplo BX ou BP

BX ou BP ou SI ou DI

SI ou DI

EU

Endereço efectivo

deslocamento CS

0 ou

Assumido por omissão

SS

0 ou

DS

0

BIU

ou ES

0

Ender. físico Fig 38

O endereço efectivo é calculado pela EU. É um número de 16 bits que representa a distância do operando ao início do segmento onde reside.

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 20

X.5.1 - Operandos em registo e imediato As instruções com operandos apenas em registo são as mais compactas e rápidas. São executadas inteiramente na CPU. Exemplo:

ADD AX, BX

Os operandos imediatos são constantes contidas na instrução, sendo por isso de acesso rápido. Servem apenas como origem, nunca como destino. Exemplo:

ADD AL, 5

X.5.2 - Endereçamento directo É o modo de endereçamento mais simples. É usado para endereçar variáveis simples (escalares). OP CODE

R/M MOD

deslocamento

End. efectivo Fig 39

Exemplo:

ADD CX, alfa ADD alfa, 6

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 21

X.5.3 - Endereçamento indirecto Uma instrução pode operar em diferentes posições de memória se o registo de base ou índice for actualizado. Instruções aritméticas e LEA podem ser usadas para o efeito.

OP CODE

R/M MOD

BX ou BP ou

End. efectivo

SI ou DI Fig 40

Exemplo:

ADD BL, [BX] ADD [SI], 12

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 22

X.5.4 - Endereçamento com registo de base O endereço efectivo é a soma do deslocamento com o conteúdo do registo BX ou BP. É usado para endereçar estruturas. OP CODE

R/M MOD

deslocamento

BX ou BP

End. efectivo Fig 41

Acesso a uma estrutura usando endereçamento com base Endereços altos

deslocamento

deslocamento

(Data_de_inscrição)

(Data_de_inscrição)

Propina

Atraso

Data_de_inscrição

Registo base

Curso

Turma

Idade

Estado

Registo base

Número_de_aluno

End. efectivo

End. efectivo

Propina

Atraso

Data_de_inscrição Curso

Turma

Idade

Estado

Número_de_aluno

Endereços baixos Fig 41a

Exemplo:

ADD [vector].alfa, AH

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 23

X.5.5 - Endereçamento indexado O endereço efectivo é a soma do deslocamento com o conteúdo de SI ou DI. É usado para o endereçamento de vectores. OP CODE

R/M MOD

deslocamento

SI ou DI

End. efectivo Fig 42

Acesso a um vector usando endereçamento indexado Endereços altos

deslocamento

deslocamento

Array (11) Array (10) Registo de índice

Array (9) Array (8)

20

Registo de índice 6

Array (7) End. efectivo

Array (6)

End. efectivo

Array (5) Array (4) Array (3) Array (2) Array (1) Array (0)

1 word Endereços baixos Fig 42a

Exemplo:

ADD CX, alfa[SI] ADD alfa[DI+2], 10

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 24

X.5.6 - Endereçamento indexado e com registo de base O endereço efectivo é a soma do registo de base com um registo de índice e um deslocamento. OP CODE

R/M MOD

deslocamento

BX ou BP

SI ou DI

End. efectivo Fig 43

Exemplo:

ADD [BX].alfa[SI], AL ADD SI, [BP+4][DI]

X.5.7 - Endereçamento de strings Os registos de índice são usados implicitamente. Em operações repetidas a CPU ajusta SI e automaticamente de modo a obter bytes ou words.

DI

OP CODE

SI

End. efectivo

(origem)

DI

End. efectivo

(destino) Fig 44

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 25

X.5.8 - Endereçamento de portos de I/O No endereçamento directo o operando de 8 bits imediato. OP CODE

número

do

porto

é

um

Dado

End. do porto Fig 45

Exemplo:

IN AL, 30

No endereçamento indirecto o número do porto é lido de DX e utiliza 16 bits. OP CODE

DX

End. do porto Fig 46

Exemplo: OUT DX, AX

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 26

X.6 - PROGRAMAÇÃO EM ASSEMBLY 86 X.6.1 - Definição de dados Constantes Podem ser números hexadecimais.

binários,

decimais,

octais

ou

Todos os números devem ser representados em 16 bits incluindo um bit de sinal. Os números negativos são representados em complemento para 2. Exemplos: letra_A

EQU

'A'

;caracter

hexa_A

EQU

41H

;equivalente em hex.

hexa_196

EQU

0C4H

;hexadecimal

octal_8

EQU

10O

;octal

tudo_uns

EQU

11111111B

;binário

menos_5

EQU

-5

;decimal

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 27

Variáveis Podem ser do tipo byte , word ou doubleword. As directivas DB, DW e DD servem para reservar o respectivo espaço em memória.

Exemplos:

dados_1

SEGMENT

alfa beta gama delta epsilon

DB DW DD DB DW

dados_1

ENDS

dados_2

SEGMENT AT 55H

;especifica endereço de base

iota kapa lambda mu

DB DW DD DB

;contém 48 45 4C 4C 4F H ;contém 42 41 H ;contém 0000 5500 H ;contém (100 x) 00H

dados_2

ENDS

? ? ? ? 5

'HELLO' 'AB' dados_1 100 DUP (0)

;não inicializada ;não inicializada ;não inicializada ;não inicializada ;contém 05H

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 28

O assembly 86 guarda três atributos de cada variável e fornece dois operadores que podem ser usados em programação.

Variável alfa beta gama delta epsilon iota kapa lambda mu

Atributos Offset 0 1 3 7 8 0 5 7 11

Segmento dados_1 dados_1 dados_1 dados_1 dados_1 dados_2 dados_2 dados_2 dados_2

Tipo 1 2 4 1 2 1 2 4 1

Operadores LENGTH 1 1 1 1 1 5 1 1 100

SIZE 1 2 4 1 2 5 2 4 100

Estruturas Uma estrutura é uma entidade que atributos a um conjunto de campos.

dá

um

nome

Exemplo: empregado

STRUC

num_cont dept ano_contr

DB DB DW

empregado

ENDS

9 1 1

DUP(?) DUP(?) DUP(?)

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

e

X - 29

X.6.2 - Directivas Um programa em assembly 86 compreende uma série de segmentos: segmento de código, segmento de dados, segmento de stack. As directivas SEGMENT e ENDS iniciam e terminam o segmento. A directiva ASSUME diz ao assemblador quais os endereços que serão colocados nos registos de segmento durante a execução do programa. Exemplo: dados dados pilha

SEGMENT ;definição dos dados ENDS

pilha

SEGMENT DW 100 DUP(?) topo_da_pilha LABEL ENDS

codigo

SEGMENT

ASSUME

CS: codigo DS: dados ES: dados SS: pilha

inicio:

MOV MOV MOV MOV MOV MOV

WORD

AX, dados DS, AX ES, AX AX, pilha SS, AX SP, OFFSET topo_da_pilha

; programa principal codigo

ENDS END

inicio

X.6.3 - Procedimentos ____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 30

Um procedimento em assembly 86 é invocado com instrução CALL. O procedimento termina com instrução RET que transfere o controle para instrução seguinte ao CALL.

a a a

Os parâmetros para o procedimento podem ser passados por registo ou por stack. Exemplo: savebp

MACRO PUSH MOV

BP BP, SP

ENDM deccount num

deccount

; definição de uma macro ; guarda o valor de bp ; fim da definição de macro

PROC NEAR EQU WORD PTR [BP+4] savebp PUSH num CALL _lercount ADD SP, 2 DEC AX PUSH AX PUSH num CALL _esccount ADD SP,4 POP BP RET ENDP

; definição de um procedimento

; repõe o valor de bp ; fim da definição de ; procedimento

; Programa principal ... PUSH CALL ADD

indice deccount SP,2

...

X.6.4 - Strings Exemplo de cópia (deslocada de 10 bytes) de 20 bytes da string linha_1 para a string linha_2. ____________________________________________________________________________________________________________ Arquitectura de Computadores AP

X - 31

REP

LEA SI, linha_1 LEA DI, linha_2 + 10 MOV CX, 20 CLD MOVS linha_2, linha_1

;inicializa ;registos de índice ;contador de repetições ;auto-incrementa

Exemplo de comparação alfabética de 2 nomes. MOV MOV MOV CLD REPE CMPS JB nome_1_menor: nome_2_menor:

SI, OFFSET nome_1 DI, OFFSET nome_2 CX, SIZE nome_2

;alternativo ao LEA ;contador ;auto-incrementa ;enquanto for igual

nome_2, nome_1 nome_2_menor ;não é relevante para ;o exemplo

Exemplo de procura do último ponto ('.') numa string. MOV DI, OFFSET frase + & LENGTH frase ;começa pelo fim MOV CX, SIZE frase ;contador STD ;auto-decrementa MOV AL, '.' ;argumento de procura REPNE SCAS frase JCXZ nao_ha_ponto ha_ponto: ;não é relevante para nao_ha_ponto: ;o exemplo

____________________________________________________________________________________________________________ Arquitectura de Computadores AP

M-1

MEMÓRIA M.1 - HIERARQUIA DE MEMÓRIAS NUM COMPUTADOR DIGITAL Unidade de controle

ROM

MC

Registos

CPU

Processador

CACHE (RAM bipolar) Ta ~ 20 ns

Memória Central (RAM MOS) Ta ~ 80-100 ns

Memória Secundária (Tecnologia Electromecânica) Ta ~ ms

Reg

ALU

Cache

CAM

RAM 1

RAM n

Discos Fig 47

Quando se caminha no sentido da memória secundária encontramos memórias com maior capacidade, maior tempo de acesso e mais baixo custo/bit.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M-2

M.2 - TECNOLOGIA M.2.1 - Características das principais memórias Modos de acesso i) Acesso aleatório Tempo de acesso é o mesmo para todas as palavras. Modo típico de acesso em memória central. Ex.: Memória semicondutora (MOS, bipolar) ii) Acesso sequencial Tempo de acesso depende da localização em memória da palavra à qual se pretende aceder. Típico de memória secundária. Ex.: discos e banda magnética. iii) Acesso associativo Acesso feito só a palavras que tenham um dado conteúdo parcial. Típicamente usado em tabelas de cache ou na memória central em aplicações especiais. Tecnologias Tecnologia Semicondutor a bipolar Semicondutor a MOS Discos magnéticos Bandas magnéticas

Custo/bit relativo

Ta (s)

Modo de acesso

Permanência

Meio físico

10

10-8

Aleatório

Volátil

Electrónico

1

10-7

Aleatório

Volátil

Electrónico

10-2

10-2

Série (Série-Aleatório)

Não-volátil

Magnético

10-3

10-1

Série

Não-volátil

Magnético

M.2.2 - Memórias de acesso aleatório

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M-3

Descodificador

Driver de endereços

UNIDADE DE MEMÓRIA Células de

de endereços

memória Sinais de controle interno

MAR

BUS de endereços

Controle

BUS de controle

Driver de escrita

Driver de leitura

MDR1

MDR2

BUS de dados Fig 48

MAR - Memory Address Register MDR - Memory Data Register UCM - Unidade de Controle de Memória • MDR1 e MDR2 formam normalmente um único registo MDR. • Drivers, descodificador e UCM formam os circuitos de acesso da unidade de memória.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M-4

Organização das células de memória Organização a 1 dimensão C1 BUS de endereços

DESCO DIFI CADOR

Cn Fig 49

• cada célula está ligada a uma linha do endereço descodificado • capacidade de N bits ⇒ descodificador com N saídas e n drivers de endereço Organização a 2 dimensões

DESCO DIFI CADOR X

BUS de endereços

C00

C01

C02

C03

C10

C11

C12

C13

C20

C21

C22

C23

C30

C31

C32

C33

DESCODIFICADOR Y Fig 50

• campo de endereços dividido em 2 componentes X e Y, cada um com ax e ay bits respectivamente ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M-5

• as células estão dispostas num array rectangular com Nx ≤ 2ax linhas e Ny ≤ 2ay colunas. O número total de células é N=Nx.Ny. •

Uma

célula é seleccionada por coincidência sinais nas suas linhas de endereço X e Y.

de

• A organização 2-D requer menor número de circuitos de acesso que a 1-D. Ex: Nx=Ny= N ⇒ 2 N drivers e 2 descodificadores com N saídas.

Implementação Uma célula de implementada com:

memória

semicondutora

pode

ser

• um flip-flop MOS ou bipolar (estática); • um transistor e um condensador (dinâmica). As RAM's dinâmicas são mais baratas e têm alta densidade de integração. Requerem circuitos especiais para refrescamento das células.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M-6

Desenho de um array de memória Um problema comum a resolver é ter CI's (circuitos integrados) com capacidade de m × n bits e precisar de uma memória m'× n', sendo m'≥ m e n'≥ n. Símbolo para um circuito de 4 × 2 bits de memória Linhas de controle

AE WE

Linhas de endereço

Z0

A0 M 4x2

Saída de dados

Z1

A1

Entrada de dados

X0 X1

Fig 51

Array de memória de 16 × 4 bits WE

A0 A1

M 4x2

M 4x2

M 4x2

M 4x2

M 4x2

M 4x2

M 4x2

M 4x2

A2 Descod.

A3 Enable

AN X1 X0 X2 X3

Z0 Z1 Z2 Z3 Fig 52

M.2.3 - Memórias de acesso sequencial ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M-7

• Disco magnético é uma sequencial mais usada.

das

memórias

• Outras tecnologias: tambor magnética, disquetes, etc.

de

acesso

magnético,

banda

O disco é coberto com um material magnetizável. Existem móveis.

sistemas

com

cabeças

fixas

e

com

cabeças

O disco gira por debaixo das cabeças de leitura/escrita por acção de um motor eléctrico, definindo-se pistas na superfície do disco. Geralmente ambos os lados do disco são usados para guardar informação. • Cabeças fixas - para aceder a uma dada palavra a lógica de controle do disco tem que esperar que seja atingido o ângulo de rotação correcto do disco. • Cabeças móveis - para aceder a uma palavra, o mesmo que para cabeças fixas e adicionalmente é necessário posicionar a cabeça na pista correcta. Cilindro - conjunto de pistas acessíveis por todas as cabeças numa dada posição. Os discos com cabeças móveis são geralmente mais lentos do que os com cabeças fixas, embora sejam os mais utilizados. Características físicas • Bits estão armazenados em pistas concêntricas na superfície e em densidades de 1000 a vários milhares de bits por polegada. • Densidades de pista entre 50 a várias centenas de pistas por polegada. ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M-8

Exemplo 1 Considere-se um "disk pack" com cabeças móveis de 18 polegadas (in) de diâmetro e 20 superfícies (s) de armazenamento. Cada superfície tem uma faixa de 5 in de informação gravada com a densidade de 2000 bits/in (b/i) na pista mais interior e 100 pistas/in (t/i). Capacidade = nº de pistas . b/i . circunferência nº de pistas = s . t/i . 5 = 20.100.5 = 104 Capacidade ≈ 104 . 2 . 103 . 25 = 5.108 bits Exemplo 2 Considere-se o mesmo sistema de discos, supondo que se tem um motor a rodar a 2400 rpm.

Tempo de rotação =

3 1 = 60 × 10 ms / min = 25 ms 2400 rpm vel. motor

3 bits por pista 50 10 bit = 2 × 10 6 bit / s × = "Head rate" = tempo de rotação 25 ms

Disco com cabeças móveis

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M-9

Cabeça de escrita/leitura

Pré-amplificadores PA PA

Lógica de selecção de cabeças

PA Um cilindro

Controlador de disco

MOTOR

Motor de posicionamento de cilindro

Lógica de selecção de cilindro Fig 53

Acesso a uma palavra no disco (cabeças móveis)

• A cabeça deve ser colocada na pista correcta. É a chamada operação de busca (seek). Todas as cabeças se movimentam solidariamente. • É necessário aceder à palavra na pista. A identificação do endereço é feita conjuntamente por secções de informação especialmente formatadas e por informação existente na pista quanto à posição angular (circunferência dividida em sectores). Tempo de acesso máximo e tempo de acesso médio em discos, são normalmente indicados pelos fabricantes. O Ta máx é o tempo de busca mais longo mais o tempo de uma rotação. O Ta med é determinado de diferentes modos de fabricante para fabricante. M.3 - MEMÓRIA CENTRAL M.3.1 - Generalidades ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 10

CPU ou canal endereços

controle

dados

UCM

MAR

MDR

Desc. End.

RAM

Fig 54

Tempo de ciclo de memória - período mínimo que tem que mediar entre dois acessos consecutivos a memória. A Unidade de Controle de Memória (UCM) é um conjunto de circuitos lógicos (variável de máquina para máquina) que aceita endereços do exterior e lê ou armazena informação na memória. Funções principais da UCM

• Interface entre a memória e o resto da máquina • Fiscalizar a integridade da informação • Gestão de memória • Protecção de memória M.3.2 - Protecções no acesso a memória central

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 11

Endereço

Teste Registos Delimitadores Acesso a uma região de memória

N

Endereço rejeitado

S

Teste Chave, Fechadura Acesso a um bloco na região

N

S

TEST and SET

N

Estado de espera ou nova tentativa

S

Leitura

Escrita Leitura

N

Teste "tag bits"

S

Teste "tag bits"

N

Acção adequada

Escrita

Acesso a uma palavra Palavra lida

Palavra escrita Diag 6

i) Teste dos registos delimitadores ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 12

Restrigem o acesso a certas zonas fixas de memória para um programa. O hardware está endereços na CPU.

localizado

no

processador

de

Endereço gerado pelo programa

Somador

Registo Base

Comparador

Registo Delimitador

Interrupção ao Sist. Oper.

Endereço efectivo válido

End. Base

End. Limite

Fig 55

ii) Teste de chave e fechadura (lock and key) Protecção a nível delimitadores.

mais

baixo

que

a

dos

registos

Protege blocos dentro de uma região de memória. Exemplos

• Acesso negado (tabelas de sistema)

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 13

• Acesso só de leitura (a um programa de outro utilizador) • Acesso leitura/escrita Blocos de memória são protegidos por uma fechadura (combinação de bits associada ao bloco). Acesso é permitido se o utilizador tiver a chave respectiva assignada pelo sistema operativo. Exemplo do IBM 370 Cada bloco de 2 Kbyte tem associada uma fechadura de 4 bits (storage key) e 1 bit de protecção (read/write ou write protected). A cada utilizador é assignada uma chave (protection key) de 4 bits pelo sistema operativo quando o seu programa está a correr. Permite até 16 utilizadores simultâneos. Chave : Fechadura Bit de protecção Acções permitidas Iguais 0 Leitura/Escrita Iguais 1 Leitura/Escrita Diferentes 0 Só leitura Diferentes 1 Não há acesso Uma chave 0000 permite aceder a qualquer fechadura. É utilizada pelo sistema operativo. iii) Teste de "TEST and SET" Nalgumas circunstâncias desejamos que vários utilizadores tenham acesso aos mesmos blocos de memória mas só um de cada vez. Alguns computadores têm uma instrução do tipo "TEST and SET" (IBM 370, UNIVAC 1108).

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 14

Uma área de memória está protegida por um bit de controle. Se o bit de controle=0 quando TEST and SET é executado, o bit é passado a 1 e o programa acede a essa área. Se o bit de controle=1, é negado o acesso à área. Após completar o acesso, reset do bit de controle.

o

programa

deve

fazer

o

iv) "Tag bits" É um conjunto de bits associados a uma palavra de memória e contendo informação sobre essa palavra. As tags protegem palavras e não blocos. Exemplos:

• bits de paridade; • distinção entre palavras de programa e dados. v) Detecção e correcção de erros Para detectar um erro basta acrescentar um bit de paridade à palavra. Aumentando o número de bits de paridade teremos possibilidades de detectar mais erros e de corrigi-los. Nas máquinas actuais é normal existir controle de erros a nível de periféricos, memória central e memória secundária. Exemplo de código corrector de 1 erro (código Hamming) Suponhamos palavras de 4 bits: d4 d3 d2 d1 São necessários 3 bits de paridade: p3 p2 p1

• p1 controla as posições 1, 3, 5, 7 • p2 controla as posições 2, 3, 6, 7 ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

de

M - 15

• p3 controla as posições 4, 5, 6, 7 Controlando a paridade nestes três grupos de posições, com um circuito combinatório, obtém-se a quantidade c3 c2 c1 que indica a posição do erro, ou se for igual a zero, indica não haver erro. Se enviar a palavra p1p2p3d1d2d3d4=1101001 e receber 1101011, detecto um erro em p2 e p3. Isto dá-me a indicação de um erro no bit 6 da palavra. Para corrigir 1 erro numa palavra com n bits são necessários k bits extra, tal que: 2k ≥ n + k + 1 k ≥ log2(n + k + 1) M.4 - ORGANIZAÇÃO DE MEMÓRIA DE ALTA VELOCIDADE Se o tempo de ciclo de memória for satisfatório pode-se usar a organização tradicional de memória. Se o processador for muito rápido e pretendermos atingir uma maior velocidade de acesso, e admitindo que não se usa uma tecnologia mais rápida teremos que usar memórias paralelas ou cache, ou ambas. Em ambas as organizações se tem por aumentar a largura de banda da memória.

objectivo

Ambas envolvem o uso de hardware adicional e necessitam que haja uma certa regularidade no seu endereçamento para que se possa atingir o seu objectivo. M.4.1 - Memórias paralelas Memória central com 2 módulos

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 16

CPU endereços

dados

UCM

MAR0

MDR0

Unidade de controle de memória

MDR1

MAR1

R A M 0

R A M 1

Endereços pares

Endereços ímpares Fig 56

• Sistema de memórias paralelas ou multi-memória É qualquer sistema de memória que contenha um número de unidades de memória endereçáveis separadamente.

• Sistema de memória com endereçamento entrelaçado É um sistema multi-memória com m unidades em que os endereços sucessivos são assignados através das unidades, módulo m. Regra de entrelaçamento - assignar o endereço Ai à unidade Mj se i=j(mod m). m=3

Unidade 0: A0, A3, A6, ... Unidade 1: A1, A4, A7, ... Unidade 2: A2, A5, A8, ...

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 17

m=2p,

Geralmente: os p bits menos significativos do endereço identificam imediatamente a unidade à qual o endereço pertence.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 18

M.4.2 - Memórias paralelas em multiprocessadores e processadores paralelos Multiprocessador com memórias de endereço entrelaçado CPU 0

CPU 1

CPU n-1 n-1

1 porto 0

U C M

Unid. Mem. 0

U C M

Unid. Mem. 1

U C M

Unid. Mem. m-1

n-1 1 porto 0

n-1

1 porto 0

Fig 57

Processador paralelo com memórias múltiplas Unidade de controle

Proc 0

Proc 1

Proc n-1

Rede de interligações

UCM

UCM

UCM

Unid. Mem 0

Unid. Mem 0

Unid. Mem m-1 Fig 58

Como evitar conflitos nos acessos a arrays de dados? ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 19

Por uma disposição adequada dos arrays em memória, conforme o acesso que se pretende. Arrays uni-dimensionais Suponhamos m=4 0 1 2 3 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 -

Unidades de memória

Acedendo só aos elementos ímpares, a largura de banda é reduzida para metade. Sendo m primo, quaisquer n elementos que estejam distanciados entre si de um valor primo com m podem ser acedidos simultaneamente sem conflitos. Exemplo: m=5 a1 a6 a11 a16

a2 a7 a12 a17

a3 a8 a13 a18

a4 a5 a9 a10 a14 a15 a19 a20

Elementos distanciados entre si de 2, 3 ou 4 podem ser acedidos simultaneamente sem conflito. Arrays bidimensionais m unidades de memória Pretende-se aceder a vectores com n elementos m=4, n=4 0

1

2

3

Unidades de memória

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 20

a00 a10 a20 a30

a01 a11 a21 a31

a02 a12 a22 a32

a03 a13 a23 a33

Straight storage

Acesso a linhas e diagonais sem conflitos, mas não a colunas. 0 a00 a13 a22 a31

1 a01 a10 a23 a32

2 a02 a11 a20 a33

3 a03 a12 a21 a30

Unidades de memória Skewed storage

Acesso a linhas e colunas sem conflitos, mas não a diagonais. Não é possível armazenar uma matriz (n×n) em m=n unidades de memória, quando m é par de modo a que se possa aceder arbitrariamente a linhas, colunas e diagonais sem conflitos.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 21

M.4.3 - Memórias cache Cache - é uma memória de pequena capacidade existente entre a memória central e a CPU, com um tempo de acesso mais rápido do que a memória central e que funciona como um buffer entre CPU e memória central. Objectivo: fazer com que o tempo de acesso médio a memória do ponto de vista do processador seja tão próximo quanto possível do tempo de acesso da cache. "Locality tempo os tendem a espaço de M.4.3.1 cache

of reference" - durante um curto espaço de endereços gerados por um programa típico ficar confinados a pequenas regiões do seu endereçamento lógico.

-

Configuração

de

um

sistema

com

memória

UCM

Cache

CPU

Memória Central Fig 59

A UCM através de hardware especial, faz a gestão da cache. Se quando a CPU acede à cache a palavra não existe lá, um bloco completo é transferido da memória central para a cache. Existirá uma tabela que indica quais existentes na cache. Algoritmos mais usuais i) FIFO para troca de blocos ii) LRU iii) Aleatório

os

blocos

A escrita em memória de blocos alterados na cache (dirty blocks) pode ser feita de duas maneiras: ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 22

• "write back" - espera-se até que o bloco volte à memória central e todo o bloco é ali escrito; • "write through" - qualquer escrita numa palavra da cache pela CPU é também efectuada na palavra correspondente de memória central. M.4.3.1.1 - Organização sectorial

TAG

1 sector

Blocos Sectores

bit de validade

tags

Sectores

CACHE

Memória Central

CACHE Fig 60

• Cache e Memória Central estão divididas em sectores ou páginas. • Sectores são divididos em blocos de poucas palavras. • No caso de memórias entrelaçadas é típico a dimensão do bloco estar ligada ao número de módulos, de modo a que todo o bloco possa ser transferido num ciclo de memória, ou num número múltiplo de ciclos de memória. • Existe um bit de validade associado a cada bloco para indicar se o bloco pertence ou não ao sector referenciado. ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 23

• O algoritmo de substituição trabalha sector a sector e dentro do sector os blocos têm posições fixas. Uma tag está associada a cada sector, indicando o sector de Memória Central ao qual pertence. Acesso da CPU à cache Endereço: (si, bj, dk) si - sector Busca associativa de uma tag que indique que o sector existe na cache bj - índice para um bloco no sector Verificar se o bit de validade é válido. dk - índice para uma palavra no bloco

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 24

Falta de bloco - trazer o bloco de MC para cache e colocar o "bit de validade" válido. Falta de sector - depois de o algoritmo de substituição escolher o sector a substituir na cache, trazer da cache o bloco bj (si), modificar a tag do sector e bit de validade só válido no bloco bj, nos outros blocos do sector será inválido. É utilizado "write through", pois não se pode fazer "write back" bloco a bloco (um bloco inválido pode fazer parte de um sector já substituído e cujo endereço se perdeu na cache). M.4.3.1.2 - Organização (Direct Mapping)

de

correspondência

directa

• Não existem sectores. • Cada bloco tem a sua própria tag, e tem um lugar fixo na cache. Numa cache de n blocos, os blocos k, k+n, k+2n, etc. da MC são assignados à mesma posição da cache. • Quando a CPU acede à cache tem que ver se no endereço (si, bj, dk) os si bits são iguais aos da tag. Não há busca associativa, não há bit de validade nem algoritmo de substituição. • Organização simples mas com problemas de eficiência (baixo "hit ratio") se 2 ou mais blocos frequentemente utilizados têm a mesma posição na cache. Exemplo: PDP-11 / 60 com blocos de 1 w A cache tem 1024 w

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 25

Data BUS Address BUS

CPU

A0-A9

TAG AREA Address BUS (24 bits)

DATA AREA

CACHE

A0-A23 Comp

Cache Control

Equal Fig 61

M.4.3.2 - Eficiência no acesso à cache Cache Hit Ratio (∅) - fracção dos endereços da memória central emitidos pela unidade de controle que podem ser satisfeitos quando do acesso à cache (inclui acesso a instruções e dados). Te = Tc.∅ + (1 - ∅).Tm Tc Tm Te 1-∅ −

tempo tempo tempo "Miss

de ciclo de cache de ciclo de memória central de ciclo efectivo da memória Ratio"

Sc - Aumento de velocidade devido à cache Sc = Tm Te Tm 1 1 = = Sc = T φ Tc φ .Tc + (1 − φ ).Tm + (1- φ ) 1- (1- c )φ Tm Tm

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 26

Sc Tm/Tc

2Tm Tm+Tc 1

1/2

1

∅ Fig 62

Exemplo Estamos a projectar uma cache e pretendemos determinar a sua capacidade. Medimos ∅ para um conjunto de programas, supondo caches de 4k e 8Kbytes.

∅4k = 0,93 ∅8k = 0,97

Supondo

Tc =0,12 Tm

1 ≅ 5,5 1- 0,88 × 0,93 1 S8k = ≅ 6,85 c 1- 0,88 × 0,97 Sc4k =

Aumentando a capacidade da cache de 4 Kbyte obteve-se uma melhoria no aumento da velocidade de: S8k - Sc4k c ≅ 0,24 Sc4k Exemplos de cache em máquinas IBM Tm

Tc

Tm/Tc

Capacid. cache(w)

Dimensão bloco(w)

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 27

360/85 360/195 370/165

1,04µs 756ns 2µs

80ns 54ns 80ns

13 14,2 25

2k→4k 4k 1k→2k

8 8 16

M.4.4 - Memórias associativas Acesso associativo - acesso feito pelo conteúdo ou parte do conteúdo e não pelo endereço. Memória

associativa ou CAM - memória com acesso associativo, examinando simultaneamente todas as posições de memória e seleccionando as que satisfazem a condição.

Chave

- campo memória.

escolhido

para

endereçamento

de

Chave, Dado - estrutura de uma palavra numa memória associativa.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 28

Memória associativa (2×2) Endereço vindo do circuito de selecção

S 0

Registo de máscara

IE 0

S

S 1

IE 1

S

WE OD

IE

WE

WE OD

IE W 10

W 00 M

ID

M

ID

OD 0

S Registo de entrada

ID0

IE

ID1

ID

WE

S OD

IE

M

ID

W 01

Registo de saída

WE OD

W 11 M

OD 1 Palavra 0

Palavra 1 M 0

M 1 Sinais de "match"

Fig 63

Estrutura de uma memória associativa Entrada

Reg. Entrada

Reg. Máscara ID

IE Match

Memória Select

Circuito de selecção

OD Reg. Saída

Saída Fig 64

Célula de uma memória associativa (1 bit) ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 29 S

WE OD S - Select WE - Write enable IE - Input enable ID - Input data OD - Output data M - Match M

IE S IE

WE OD

ID

M

ID Fig 65

M.5 - PROCESSAMENTO DE ENDEREÇOS O processador de endereços determina o endereço efectivo. O processamento de endereços feito na CPU está intimamente ligado ao método de gestão de memória feito pelo sistema operativo. M.5.1 - Sistema mono-programado Sistema Operativo

Disponível para o utilizador

Utilizado pelo programa

Fig 66

Vantagens: i) Simplicidade, sistema operativo pode necessitar só de 1Kb, em contraste com ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 30

sistema operativos multiprogramação podem atingir centenas de Kb. ii) Fácil compreensão e utilização.

que

Desvantagens: i) Memória não é completamente utilizada. ii) Programa limitado ao tamanho da memória. Exemplos:

IBM OS/360 Primary Control Program IBM 1130 Disk Monitor System

Loader Relocador - Soma ao campo de endereço uma constante de relocação igual ao endereço de base no qual é carregado a primeira instrução do programa. Os endereços modificáveis são posição do programa em memória.

os

que

dependem

da

O loader relocador pode também fazer a operação de linkagem (linking loader). Este tipo Estática.

de

relocação

é

conhecido

por

Relocação

M.5.2 - Sistemas multi-programados Sistema que pode ter vários processos em estado de execução.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 31

M.5.2.1 - Sistema de partições Situação de memória partilhada, central é dividida em partições.

em

(i)

que

a

memória

(ii)

10K

10K

20K

PROG 5

20K

PROG 5

30K

PROG 4

30K

PROG 4

15K

PROG 3

PROG 1

15K

20K

PROG 2

PROG 3

20K

10K

PROG 1

Saem

10K

20K

SISTEMA

20K

PROG 2

SISTEMA

Memória fragmentada Fig 67

Supondo que em ii) temos um programa para executar maior do que qualquer das áreas livres, podemos escolher uma das opções (considerando só relocação estática):

•

Esperar que outra área de memória contígua fique livre • Carregar o programa em áreas não contíguas • Compactar a memória ← melhor solução A compactação é difícil de executar com relocação estática, pois o espaço de endereçamento dos programas é alterado na relocação. Para compactar a memória, num sistema de gestão baseado em partições, o melhor será usar Relocação Dinâmica. Relocação dinâmica - a relocação do espaço de endereçamento é feita durante a execução do programa e não durante o carregamento.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 32

End. efectivo

Registo de base

Somador

Endereço de memória Fig 68

Hardware CPU.

existente

no

processador

de

endereços

da

O espaço de endereçamento do programa fica independente da localização do programa em memória. Exemplo R.Base

R.Base

S1 S2 A+S1

MPY A

A

A+S2

MPY A

A

Programa movimentado Fig 69

A relocação dinâmica não resolve 3 problemas:

• Fragmentação continua a existir, existam sucessivas compactações

a

não

ser

que

• A compactação pode demorar um tempo substancial a ser executada ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 33

• O espaço de endereçamento lógico está limitado pela dimensão física da memória central Exemplo: DEC PDP-10

e

UNIVAC 1108

M.5.2.2 - Paginação O espaço de endereçamento é dividido em partes iguais com comprimento fixo, normalmente de 1Kb a 4Kb. A cada uma dessas partes chama-se página. Bloco - área de memória central com limites de endereçamento fixos e com a dimensão de uma página. Paginação - método que permite movimentar páginas de disco para blocos de memória e vice-versa, por uma combinação de hardware e software. A paginação evita a fragmentação (excepto fragmentação interna) sem fazer compactação. Problemas

• Existência de fragmentação página parcialmente vazia).

interna

• Todo o programa em memória, a esteja "overlayed". Exemplo: Sistema com memória paginada

não

(última ser

que

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 34

PROG 1 0 1000

Nº de Nº de página bloco

0 1 2

2000

5 6 9

0 1 2

2000

2 4 7

4000 5000 6000

0

8

8000 9000 10000

Programas dos utilizadores

Livre

7000

PROG 3 0

Sistema Operativo

2000 3000

PROG 2 0 1000

0 1000

Tabelas de páginas

11000

Livre Livre

Memória Central Fig 70

Exemplos: XDS Sigma 7, CDC 3300 Em resumo:

• O espaço de endereçamento dividido em páginas.

de

um

processo

é

• A memória é dividida em blocos. As páginas de um processo devem estar todas em memória. Há uma tabela de páginas para cada processo. As tabelas de páginas existem normalmente em memória mas também poderão existir em registos. Existe também uma tabela de blocos, indicando quais os blocos livres. M.5.2.3 - Memória virtual baseada em paginação Nem todas as páginas de um processo precisam de estar em memória. As tabelas de páginas são estendidas com mais 1 bit, revelando se a página está ou não em memória. ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 35

Uma cópia completa do espaço de endereçamento do processo existe em disco. Existirá uma tabela de ficheiros (gestão de informação pelo sistema operativo) por cada processo, que indica para cada página do processo qual o endereço em disco. Não estando a página em memória, é originada uma interrupção ao sistema operativo, que delega a troca de páginas num programa especial de E/S (entradas/saídas). Se não houver blocos livres (tabela de blocos) é feita a troca de páginas segundo um dado algoritmo. Normalmente quando um processo se inicia, primeira página é trazida para memória.

só

a

Memória Virtual - Sistema em que o programador pode referenciar mais posições do que as que estão assignadas ao seu programa em memória central, i. e., pode referenciar posições de memória saecundária.

• A gestão do espaço de memória é feita pelo sistema operativo. O princípio de "locality of reference" favorece a implementação de memória virtual. Endereçamento de memória virtual

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 36

γk

δs

γj

αq

γi

αp

γ1

Memória Virtual v (2 ) v-l página 2

Memória Central p (2 ) p-l página 2

Tabela de páginas

αq

página k

γk

αp

página j

γj

página 1

página i

γi

Memória Secundária v p (2 -2 )

página 1

γ1

δr

δs δr tamanho do bloco = 2

δ1

l Fig 71

Tabela de páginas

Nº de página v-l

page fault

Nº de linha l

endereço virtual do programa

Endereço de memória secundária

Pedido de página

Actualização de tabela de páginas

Troca de página com M. Central

Nº de page frame p-l

Nº de linha l

endereço em memória central Fig 72

Algoritmos para troca de páginas ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 37

• Estratégia de troca óptima • First-in first-out (FIFO) • Least Recently Used (LRU) Parâmetros a considerar em memória virtual

• Custo por bit C=

C1S1 + C 2S2 S1 + S2

Ci - custo por bit Si

- capacidade

• "Hit Ratio"

H =

N1 N1 + N

2

N1 - nº de memória N2 - nº de memória

referências a central referências a secundária

• Tempo de acesso tA = H.tA1 + (1-H).tA2 tA2 = tB + tA1 tA = tA1 + (1-H).tB O primeiro sistema de memória virtual paginada foi o ATLAS (Universidade de Manchester) com 32 blocos de 512 palavras. A memória secundária era um tambor magnético. Exemplos actuais: VS/1, VS/2 (IBM) e VAX/VMS M.5.2.4 - Memória virtual segmentada Segmento conjunto relacionadas logicamente.

de

palavras

contíguas

Uma palavra num segmento é identificada pelo endereço de base do segmento e um endereço relativo a essa base. ____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

M - 38

Segmentação - técnica de gestão de memória que faz a alocação de memória por segmentos. Existirá uma tabela de segmentos semelhante à tabela de páginas, mas que indicará a dimensão de cada segmento, a sua existência ou não em memória central e o respectivo endereço. Comparação com memória virtual paginada Vantagens

• Módulos de programa são trocados e não páginas. •

Facilita partilha processos.

de

segmentos

por

vários

dos

segmentos

complica

Desvantagens

•

Dimensão gestão.

variável

• Necessita compactação.

____________________________________________________________________________________________________________ Arquitectura de Processadores ASP93

a