Departamento de Ciências e Tecnologias da Informação
Arquitectura de Computadores II
Textos de apoio
– Hierarquia da Memória –
Versão 0.02a – Maio de 2010 – Tomás Brandão.
ISCTE-IUL - DCTI
2
Índice
1.
INTRODUÇÃO.................................................................................................................................5
2.
MEMÓRIAS CACHE ......................................................................................................................7
2.1.
PRINCÍPIOS DE FUNCIONAMENTO ...............................................................................................7
2.2.
CARÁCTER LOCAL DAS REFERÊNCIAS.........................................................................................8
2.3.
ESTRUTURA DE UMA CACHE .......................................................................................................8
2.3.1. Cache directa........................................................................................................................8
2.3.2. Cache completamente associativa ......................................................................................13
2.3.3. Cache associativa de N vias ...............................................................................................13
2.4.
POLÍTICAS DE ESCRITA .............................................................................................................15
2.5.
REDUÇÃO DA TAXA DE FALTAS ................................................................................................16
2.5.1. Aumento da dimensão do bloco ..........................................................................................16
2.5.2. Aumento do grau de associatividade (número de vias) ......................................................17
2.5.3. Utilização de uma “cache vítima” .....................................................................................17
2.5.4. Técnicas de compilação......................................................................................................18
3.
MEMÓRIA VIRTUAL ..................................................................................................................19
3.1.
PAGINAÇÃO..............................................................................................................................19
3.1.1. Paginação simples..............................................................................................................19
3.1.2. Tabelas de páginas .............................................................................................................21
3.1.3. Page fault............................................................................................................................22
3.1.4. Algoritmos de substituição de páginas ...............................................................................23
3.1.5. Paginação multi-nível.........................................................................................................24
3.1.6. TLB (Translation Lookaside Buffer)...................................................................................26
4.
BIBLIOGRAFIA ............................................................................................................................29
5.
LISTA DE REVISÕES...................................................................................................................30
ISCTE-IUL - DCTI
3
ISCTE-IUL - DCTI
4
1. Introdução
Ideally one would desire an indefinitely large memory capacity such that any particular word
would be immediately available.
We are forced to recognize the possibility of constructing a hierarchy of memories, each of
which has greater capacity than the preceding but is less quickly accessible.
Burks, Goldstine & von Newmann (1946)
Quando um processador executa um programa, vai lendo as instruções da memória (fetch) e
também vai lendo e escrevendo dados em memória. Sendo assim, a rapidez com que é feito o
acesso à memória é um importante factor no desempenho de um computador.
De forma a facultar um rápido acesso aos elementos guardados em memória, nos actuais
sistemas é habitual ser estabelecida uma hierarquia de memória semelhante à esquematizada na
Figura 1.
Chip do processador
CPU
Registos
Cache
Memória
Principal
Memória
Secundária
(RAM)
(Disco)
Figura 1 – Hierarquia da memória.
Nesta hierarquia, os registos do processador são os elementos de memória mais rápidos que
podem ser encontrados no sistema de memória. Por outro lado são também os elementos com
menor capacidade de armazenamento, tipicamente com capacidade para guardar uma única
palavra.
Subindo na hierarquia, o bloco que se segue é a memória cache. A memória cache consiste
numa memória rápida, mas com uma capacidade reduzida relativamente à memória principal
(tipicamente é 100 a 1000 vezes mais pequena, usando números redondos). O objectivo da
utilização de memória cache é o processador aceder mais depressa às instruções e aos dados de
ISCTE-IUL - DCTI
5
que necessita. Caso encontre o que necessita na cache, escusa de aceder à memória principal. As
memórias cache estão normalmente incluídas no próprio circuito integrado do processador.
A memória secundária, o disco rígido, serve para guardar grandes quantidades de informação.
No contexto de um sistema hierárquico de memória assume um papel importante quando o
sistema utiliza memória virtual. Nesse caso o disco poderá ser utilizado para armazenar
programas (ou partes de programas) e dados, que dadas as suas dimensões não “caberiam” na
memória principal.
Em suma, num sistema hierárquico de memória, os elementos mais próximos do processador
são os mais rápidos, mas também os com menor capacidade e custo mais elevado. Para um
sistema hierárquico cumprir os objectivos para os quais foi projectado, a maioria dos acessos à
memória devem ser feitos aos elementos que se encontram mais próximos do processador, i.e.,
acede-se muitas vezes à cache, ocasionalmente acede-se à RAM e raramente se acede ao disco.
ISCTE-IUL - DCTI
6
2. Memórias cache
2.1. Princípios de funcionamento
Tal como já foi referido, uma memória cache é uma memória de dimensões reduzidas, mas de
rápido acesso e que tipicamente se encontra incluída no mesmo circuito integrado que o
processador.
A memória cache guarda cópias de blocos da memória principal, i.e., cópias de palavras
guardadas em endereços consecutivos da memória RAM. Quando o processador necessita de
aceder à memória (para ir buscar uma instrução ou para ir buscar dados) verifica primeiro se a
palavra pretendida se encontra na memória cache. Se encontrar o que pretende, apenas acede à
cache e portanto perde pouco tempo até obter a palavra pretendida – diz-se que teve sucesso ou
que ocorreu um cache hit.
Por outro lado, quando o processador não encontra na cache os dados pretendidos, diz-se que o
bloco está em falta ou que ocorreu um cache miss. Nesse caso terá que ser acedida a memória
principal para o bloco ser copiado para a cache, e portanto perde-se mais tempo. Copia-se o
bloco de dados no qual se encontra a palavra pretendida, na esperança de que futuros acessos a
palavras incluídas nesse bloco resultem em sucesso. Deste modo consegue-se uma maior
eficiência.
Exemplo:
Admita que um sistema utiliza uma cache com um tempo de acesso de 1ns e que 90% dos
acessos resultam em sucesso (hit rate = 90%). Sabe-se também que o tempo necessário para
aceder à memória RAM (ou copiar um bloco de dados da mesma) requer 15 ns.
Qual será, em média, o tempo de acesso à memória? Ou seja, qual será o tempo que o
processador perde até aceder aos dados pretendidos?
Resposta:
Pelo enunciado do problema, pode-se concluir que 90% dos acessos à memória resultam em hits
na cache, pelo que em 90% das vezes o tempo de acesso é igual ao tempo de acesso à cache.
Nos restantes 10% dos acessos, o processador verifica em primeiro lugar a cache, mas os dados
pretendidos não se encontram lá – ocorrem misses e nesses casos o processador terá que em
seguida aceder à memória principal.
Sendo assim tem-se:
Tacesso = 0.9 × 1 ns + 0.1 × (1 ns + 15 ns) = 0.9 + 1.6 = 2.5 ns
Pelo resultado pode concluir-se que presença da memória cache faz com que o desempenho
aumente consideravelmente. Se a cache não existisse, todos os acessos demorariam 15 ns.
ISCTE-IUL - DCTI
7
Para cache anterior, e a título de exemplo, pode-se também calcular a percentagem de sucesso
(h) a partir da qual compensa utilizar a cache. Poder-se-ia escrever a seguinte inequação:
h × 1ns + (1 – h) × (1ns + 15ns) < 15 ns
⇔ h + 16 – 16 h < 15
⇔ -15 h < - 1
⇔ h > 1/15
⇔ h > 0.067
Ou seja, para uma taxa de sucesso maior do que 6.7% já compensaria utilizar esta cache.
A taxa de sucesso das caches é normalmente elevada, pois estas são projectadas de forma a tirar
partido do carácter local das referências.
2.2. Carácter local das referências
A designação carácter local das referências significa que um programa em execução tende a
referenciar (ou aceder) posições de memória que se encontram localizadas próximas umas das
outras. Essa localização pode ser vista num contexto espacial e num contexto temporal:
•
Espacial – quando uma determinada posição de memória é acedida, é provável que num
futuro próximo sejam acedidas posições de memória vizinhas. Como exemplos temos o
acesso aos elementos de uma matriz (as matrizes são colocadas em posições de memória
consecutivas), a execução de uma sequência de instruções, sem saltos pelo meio (também
estão colocadas em posições consecutivas da memória), etc.
•
Temporal – é provável que um programa aceda às mesmas posições de memória várias
vezes ao longo da sua execução. Como exemplos de situações deste género, tem-se uma
variável que é utilizada muitas vezes, uma sequência de instruções dentro de um ciclo com
muitas iterações, etc.
As memórias cache, ao guardarem blocos de memória copiados da RAM acabam por tirar
partido destas duas características – a temporal, porque guardam valores, e portanto estes podem
ser acedidos no futuro, e espacial, porque as caches guardam blocos de dados que contêm os
valores guardados em posições de memória consecutivas.
2.3. Estrutura de uma cache
A estrutura da cache varia consoante o tipo de cache em questão: cache directa, cache
completamente associativa e cache associativa de N vias.
2.3.1.
Cache directa
A cache directa é provavelmente a cache cuja organização é a mais simples. A cache directa
pode ser vista como uma tabela, composta por várias linhas, e em que cada entrada numa linha é
composta por três campos principais:
ISCTE-IUL - DCTI
8
•
bloco de dados – com capacidade para guardar uma cópia de um bloco de dados da
memória;
•
tag ou etiqueta – que serve para identificar o bloco que se encontra guardado na cache;
•
bit de validade – que indica se essa entrada da cache contém dados válidos ou não.
Na Figura 2 encontra-se esquematizada a organização de uma cache directa
Bit de
validade
Bloco de dados
Tag
Linhas
0
1
2
3
4
...
...
Figura 2 – Organização interna de uma cache directa.
Uma questão importante numa cache directa é o modo como é feito o acesso à cache. Para
ilustrar este conceito, vamos considerar uma memória principal com uma dimensão pequena –
256 Bytes, endereçáveis individualmente – e uma cache directa, também pequena, com 8 linhas
e com 4 Bytes por bloco, ilustrada na Figura 3. Se as dimensões fossem maiores, o
funcionamento seria idêntico.
Cache
8 linhas
0
1
2
3
4
5
6
7
4 Bytes / bloco
Figura 3 – Estrutura da cache utilizada neste exemplo.
A memória possui 256 Bytes, o que quer dizer que os endereços são de 8 bits. Como se encontra
organizada em blocos de 4 Bytes, possui um total de 64 blocos (de 0 a 63).
Como a cache possui 8 linhas, faz sentido utilizar 3 bits para indexar as linhas (23 = 8) e como
os blocos são de 4 bytes (4 palavras) faz sentido utilizar 2 bits para indexar cada bloco (22 = 4).
ISCTE-IUL - DCTI
9
Deste modo, quando se pretende aceder à cache, divide-se cada endereço em três partes: um
índice de palavra dentro de cada bloco, um índice de linha e uma etiqueta.
Como os endereços são de 8 bits, pode-se então dividir cada endereço da seguinte forma:
8 bits
Etiqueta
Linha
Palavra
3 bits
3 bits
2 bits
Repare que os bits da etiqueta são os que “sobram” depois de definidos quantos bits são
necessários para indexar as linhas e quantos são necessários para indexar as palavras dentro de
cada bloco. Para acesso à cache, a estruturação que é feita aos endereços é utilizada da forma
indicada na Figura 4.
Estruturação de um endereço
Etiqueta
Índice de linha
Índice de palavra
Indexa as palavras
pertencentes ao bloco
Indexa as linhas
0
1
2
3
4
5
...
Figura 4 – Estruturação de um endereço para acesso a uma cache directa.
Na Figura 5 pretende-se ilustrar o modo como os vários blocos em memória são “mapeados”
para a cache directa do exemplo anterior. Com base na figura pode-se ver, por exemplo, que o
bloco 0, composto pelos endereços 0000 0000 a 0000 0011, irá ocupar a linha 0, o bloco 1 irá
ocupar a linha 1, e assim sucessivamente. Repare que o bloco 8 também será mapeado para
linha 0 (tal como o bloco 0) e o bloco 9 será mapeado para linha 1 (tal como o bloco 1). A
etiqueta serve precisamente para distinguir os blocos que são mapeados para as mesmas linhas
da cache.
Repare que tanto o bloco 0 como o 1 têm etiqueta ‘000’ ao passo que os blocos 8 e 9 têm
etiqueta ‘001’.
ISCTE-IUL - DCTI
10
RAM
0000 0000
0000 0001
0000 0010
0000 0011
0000 0100
0000 0101
0000 0110
0000 0111
...
Bloco 0
Bloco 1
Cache
...
0010 0000
0010 0001
0010 0010
0010 0011
0010 0100
0010 0101
0010 0110
0010 0111
...
1111 1100
1111 1101
1111 1110
1111 1111
...
Bloco 8
Bloco 9
...
0
1
2
3
4
5
6
7
...
Bloco 63
Figura 5 – Mapeamento de blocos de memória para uma cache directa.
De uma forma geral, se a cache directa tiver N linhas, as linhas da cache para as quais cada
bloco de memória é mapeado repetem-se de N em N blocos.
A sequência de acções que é feita quando se acede a uma cache é a seguinte:
•
Consultar a linha indicada no endereço;
•
Nessa linha, verificar o bit de validade – se está a ‘0’ então ocorre uma falta (miss);
•
Verificar a etiqueta – se a etiqueta do bloco guardado em cache for igual à especificada no
endereço, então há sucesso (hit), caso contrário ocorre uma falta (miss);
No caso de haver uma falta, procede-se a uma transferência do bloco em falta para a cache; Em
caso de sucesso e lêem-se os dados da cache poupando-se o acesso à RAM.
ISCTE-IUL - DCTI
11
Exemplo:
Na cache do exemplo anterior, o seu conteúdo em determinada altura da execução de um
programa, poderia ser o seguinte:
Cache
0
1
2
3
4
5
6
7
•
1
0
1
1
0
1
0
1
000
xxx
000
010
xxx
111
xxx
001
M[00] a M[03]
xxx
M[08] a M[0B]
M[4C] a M[4F]
xxx
M[F4] a M[F7]
xxx
M[3C] a M[3F]
Nestas condições, o que será que acontece caso se aceda ao endereço 0x0A ?
Observando a cache, temos imediatamente a resposta a esta pergunta – ocorre um hit porque o
conteúdo do endereço 0x0A já se encontra na cache. Mas como é que o processador sabe que
ocorre um hit ?
Em primeiro lugar, são obtidos os diversos campos que compõem o endereço (de acordo com a
estruturação que já foi vista anteriormente). Assim, tem-se:
0x0A = 0000 1010 – Etiqueta 000; Linha 010 (2); Palavra 10 (2)
Seria acedida a linha 2, que está válida e cuja etiqueta é igual à do endereço a aceder – daria um
hit, pois os dados pretendidos encontram-se na cache.
•
Então e no caso de se aceder ao endereço 0x05 ?
0x05 = 0000 0101 – Etiqueta 000; Linha 001 (1); Palavra 01 (1)
Neste caso seria acedida a linha 1, que está inválida – daria um miss, pois os dados não se
encontram em cache. De seguida o bloco ao qual pertence o endereço 0x05 (M[04] até M[07])
seria carregado para a linha 1. O bit de validade seria modificado para o valor ‘1’.
•
E no caso de se aceder ao endereço 0x40 ?
0x40 = 0100 0000 – Etiqueta 010; Linha 000 (0); Palavra 00 (0)
Neste caso seria acedida a linha 0, que é válida, mas como a etiqueta do endereço a aceder é
diferente da guardada em cache, ocorreria um miss. Depois da ocorrência deste miss, o bloco ao
qual pertence o endereço 0x40 (M[40] até M[43]) seria copiado para linha 0, substituindo o
bloco que lá se encontra.
ISCTE-IUL - DCTI
12
2.3.2.
Cache completamente associativa
Numa cache completamente associativa não existe o conceito de linha. A cache completamente
associativa pode ser vista como uma cache em que um bloco copiado da memória principal
poderá ocupar qualquer entrada da cache – não existem posições pré-definidas como foi visto
com a cache directa.
A cache associativa tem no entanto uma complexidade adicional no que respeita à verificação
das etiquetas: como um bloco pode ocupar qualquer posição da cache, terão que ser verificadas
as etiquetas de todas as entradas válidas guardadas na cache... Esta verificação pode ser feita em
paralelo, à custa de mais material (muitos comparadores lógicos e portas OR a unir as suas
saídas).
A vantagem deste tipo de caches em relação às directas é o facto se poderem aproveitar todas as
entradas da cache, já que não existe nenhum mapeamento de blocos pré-definido.
Mas como acontece em qualquer cache, as caches associativas são susceptíveis de ficarem
“cheias”, isto é, com todas as suas entradas ocupadas. O que fazer então no caso da cache estar
cheia e ser acedido um bloco de memória que não se encontra na cache? Nesta situação, um dos
blocos que estão na cache terá que ser substituído pelo bloco em falta. Mas como a cache é
completamente associativa, o novo bloco poderá ocupar qualquer uma das entradas da cache,
pelo que o bloco a substituir poderá ser escolhido com algum critério. Qual deverá então ser o
bloco a ser substituído? É aqui que entra em acção o algoritmo de substituição de blocos.
Um bom algoritmo de substituição de blocos seria um algoritmo que descartasse um bloco que
tão cedo não fosse necessário, ou que nunca mais viesse a ser acedido. Mas como os
computadores não conseguem prever o futuro (pelo menos por enquanto...) podem ser seguidas
as seguintes abordagens:
•
Descartar o bloco que não é acedido à mais tempo (algoritmo LRU – least recently used)
•
Ou descartar o bloco que foi acedido menos vezes (algoritmo NFU – not frequently used)
Basicamente estes algoritmos analisam, de uma forma simplista, o comportamento do acesso
aos blocos no passado e extrapolam esse comportamento para o futuro. Muitas vezes resulta. No
entanto, como estes algoritmos obrigam a que seja guardada informação adicional (de controlo)
na cache, podem-se tornar pouco atractivos em caches de maiores dimensões. Nesses casos, a
escolha do bloco a substituir é feita de forma aleatória, uma estratégia com bons resultados em
caches grandes, e que não traz um custo adicional tão pesado.
2.3.3.
Cache associativa de N vias
Uma cache associativa de N vias é uma solução de compromisso entre uma cache directa e uma
cache completamente associativa. A cache associativa de N vias é constituída por um conjunto
de linhas, que são compostas por N entradas cada uma. A ideia consiste em mapear os blocos
ISCTE-IUL - DCTI
13
para uma dada linha, mas dentro dessa linha existe a liberdade de escolher para qual das N vias
se vai transferir o bloco de dados.
Na Figura 6 apresenta-se uma esquematização de uma cache associativa de 4 vias. Neste
esquema, por cada conjunto existem 4 vias. Um bloco que estivesse mapeado para o conjunto 0,
por exemplo, poderia ocupar uma das 4 entradas desse conjunto
Via 0
Via 1
Via 2
Via 3
...
...
...
...
0
1
2
3
4
...
Figura 6 – Estrutura de uma cache associativa de 4 vias.
A estruturação de endereços para uma cache deste género é semelhante ao que é feito na cache
directa, mas neste caso há que ter em conta que se podem encontrar N blocos em cada linha.
Exemplo:
Suponha que uma cache associativa de 8 vias tem uma capacidade útil de 256KBytes. Sabe-se
também que a dimensão de cada bloco é de 64 Bytes e que os endereços são de 24 bits. Como
será que são estruturados os endereços para aceder a esta cache ?
Para determinar o modo como é feita a estruturação dos endereços temos que determinar
quantos bits são utilizados para indexar as linha e quantos bits são utilizados para indexar cada
bloco.
Como o enunciado especifica que cada bloco é composto por 64 bytes, e assumindo que cada
palavra consiste num byte, então cada bloco contém 64 palavras. Como 64 = 26, conclui-se que
são utilizados 6 bits para indexar as palavras dentro de cada bloco.
Para determinar quantos bits são necessários para indexar as linhas, há que determinar quantas
linhas existem nesta cache. Como a cache é de 8 vias, quer dizer que cada linha tem capacidade
para guardar 8 blocos. Como cada bloco são 64 bytes, então cada linha tem capacidade para 8 ×
64 = 512 bytes. Como a cache tem uma capacidade de 256 KBytes, então terá 256K / 512 = 512
linhas. Como 512 = 29, então serão necessários 9 bits para indexar as linhas.
Como os endereços são de 24 bits, o número de bits das etiquetas será 24 – 9 – 6 = 9 bits.
Chega-se portanto à seguinte estruturação de endereços:
24 bits
ISCTE-IUL - DCTI
Etiqueta
Linha
Palavra
9 bits
9 bits
6 bits
14
2.4. Políticas de escrita
Até este ponto do texto tem-se falado da interacção processador-cache quando se pretende ler o
conteúdo de uma posição de memória. Mas o que acontece no caso de uma escrita? Será que se
escreve na cache? Ou na memória principal? Ou em ambos os lados?
Esta secção debruça-se sobre as várias hipóteses de procedimentos em caso de escrita – estas
possíveis acções designam-se por políticas de escrita.
Em primeiro lugar há que separar as políticas de escrita utilizadas em caso de sucesso (hit) ou
em caso de falta (miss).
Quando se pretende escrever uma palavra pertencente a um bloco que se encontra em cache,
tem-se um sucesso. As políticas de escrita em caso de sucesso dividem-se em dois grupos:
•
Write-back – a palavra é escrita apenas na cache; o bloco onde se encontra a palavra que foi
modificada só será escrito na memória principal quando for substituído, i.e. quando “sair”
da cache.
•
Write-through – a palavra é escrita em ambos os lados: na cache e na memória principal.
A política write-back tem a vantagem de ser mais rápida na maioria das situações, pois ao se
escrever apenas na cache, evitam-se provavelmente muitas escritas na memória principal. No
entanto, um aspecto que poderá ser problemático é o facto do conteúdo da memória principal
poder estar desactualizado. Esta situação poderá causar problemas no caso da memória principal
ser partilhada por diversos dispositivos (e.g. vários CPUs) ou no caso de existirem
transferências de dados entre a memória e um periférico.
A política write-through é à partida mais lenta, já que se acede sempre à RAM em caso de
escrita, mas tem a vantagem de ter a memória sempre actualizada com os mesmos valores que
se encontram em cache. Para aumentar a eficiência desta política, muitas vezes é utilizado um
buffer auxiliar que guarda as palavras a escrever na RAM – o objectivo desta técnica (designada
por write buffer) é fazer com que o processador não tenha que ficar à espera da escrita dos
valores na memória principal. O CPU escreve no buffer, e quando houver oportunidade (o BUS
estiver livre), transfere-se o conteúdo do buffer para a memória.
No caso de ocorrer uma falta (miss) durante uma escrita, pode-se seguir uma das seguintes
políticas:
•
Write allocate (escrita com colocação) – copia-se o bloco em falta para cache, seguindo-se
depois uma das políticas em caso de hit.
•
No write allocate (escrita sem colocação) – escreve-se apenas na memória principal, sem se
copiar o bloco em falta para a cache.
Na estratégia write allocate copia-se o bloco em falta para a cache, na esperança de que esse
bloco venha depois a ser utilizado em futuros acessos. A estratégia no write allocate assume um
maior cepticismo quanto a futuras utilizações do bloco em falta, sendo mais rápida na medida
ISCTE-IUL - DCTI
15
em que não necessita de copiar um bloco de dados da memória, mas sim escrever apenas uma
palavra, o que em princípio será mais rápido.
Para estabelecer uma política completa, combina-se uma das estratégias em caso de hit com
uma das estratégias em caso de miss. As combinações mais habituais são:
•
Write-back em conjunto com write allocate – como à partida se escreve apenas na cache,
valerá a pena copiar para lá blocos que estejam em falta.
•
Write through em conjunto com no write allocate – já que em caso de hit se escreve sempre
na memória RAM, não valerá a pena copiar o bloco em falta para cache.
Apesar destas serem as combinações mais comuns, é possível utilizar as restantes combinações.
2.5. Redução da taxa de faltas
O desempenho de uma cache está tipicamente associado a dois factores: o tempo de acesso à
cache (e comparação das etiquetas) e a taxa de sucesso. Nesta secção são discutidas algumas
estratégias que visam aumentar a taxa de sucesso.
Antes de começar, há no entanto que distinguir as causas de um cache miss:
Cold-start – o miss ocorre por o bit de validade estar a ‘0’. A situação típica é o início da
execução de um programa. Como todas as entradas da cache estão inicialmente “vazias” por
ainda não terem havido acessos, o primeiro acesso a um novo bloco de dados ou instruções irá
inevitavelmente dar um cache miss.
Colisão – apesar do bit de validade estar a ‘1’, a etiqueta do endereço a aceder não coincide com
a etiqueta do bloco guardado na cache, originando um miss. Ou seja, o bloco de dados que se
encontra na cache não é o bloco onde se encontra o endereço a aceder. Esta situação ocorre
essencialmente devido a duas causas: devido à capacidade da cache ser pequena relativamente à
da memória principal e porque blocos de memória distintos podem ser mapeados para as
mesmas linhas da cache.
2.5.1.
Aumento da dimensão do bloco
Intuitivamente poderá parecer vantajoso aumentar a dimensão dos blocos da cache, já que assim
se consegue tirar maior partido do carácter espacial das referências, diminuindo o número de
cold-start misses.
Mas assumido que a capacidade da cache se mantém, o aumento da dimensão do bloco só será
possível se houver uma diminuição do número de linhas, no caso de uma cache directa, e/ou do
número de vias, no caso de uma cache associativa. Essa diminuição do número de entradas na
cache poderá fazer com que aumente o número de colisões.
Em suma, mantendo a capacidade da cache e aumentando a dimensão dos blocos faz com que
diminuam as faltas devido a cold-start mas ao mesmo tempo podem aumentar as colisões.
ISCTE-IUL - DCTI
16
Por outro lado, com blocos maiores, o tempo de transferência de blocos entre a memória
principal e a cache (e vice-versa) também poderá aumentar, aumentando portanto a penalização
em caso de miss.
È portanto necessário ter algum cuidado com esta estratégia, pois só deverá ser vantajosa até
uma determinada dimensão de bloco.
2.5.2.
Aumento do grau de associatividade (número de vias)
Uma estratégia cujo objectivo é uma diminuição do número de colisões consiste em aumentar o
grau de associatividade da cache, ou seja, aumentar o seu número de vias. Ao ser aumentado o
número de vias, está-se a aumentar o número de hipóteses de localizações dentro da cache para
as quais um bloco poderá ser copiado.
Por outro lado, ao ser aumentado o grau de associatividade, poder-se-á estar a aumentar o tempo
de verificação das etiquetas (pois terão que ser verificadas todas as etiquetas dentro de um
conjunto), o que poderá causar um impacto negativo no tempo de acesso à cache.
Na tabela encontra-se sintetizada uma estatística referente à percentagem de faltas de várias
caches, com a mesma dimensão de bloco (16 bytes), mas em que se varia a dimensão total e o
número de vias.
Dimensão da cache
2 vias
4 vias
8 vias
16 KB
5.18 %
4.67 %
4.39 %
64KB
1.88 %
1.54 %
1.39 %
256KB
1.15 %
1.13 %
1.12 %
Tabela 1 – Percentagem de faltas (misses) em função do grau de associatividade de uma cache.1
Com base na tabela pode-se observar que à medida que aumenta o grau de associatividade da
cache, o número de faltas diminui, mas que essa diminuição tem cada vez menor significado à
medida que aumenta a dimensão da cache.
Pode-se portanto concluir que aumentar o grau de associatividade compensa desde que se
garanta que o atraso adicional no acesso à cache não prejudica o desempenho do sistema. Na
prática tende-se a projectar caches pequenas com um grau de associatividade elevado e caches
maiores com grau de associatividade mais baixa.
2.5.3.
Utilização de uma “cache vítima”
Uma “cache vítima” é uma cache de dimensões muito reduzidas, completamente associativa,
com capacidade para guardar 4 a 8 blocos. Como guarda pouca informação também é muito
rápida.
O objectivo da cache vítima é guardar alguns blocos que foram substituídos na cache principal.
Deste modo, sempre que ocorre uma falta na cache principal, verifica-se se o bloco pretendido
1
Tabela retirada do livro Computer architecture: a quantitative approach – 2nd edition.
ISCTE-IUL - DCTI
17
se encontra na vítima. No caso de se encontrar na vítima, troca-se esse bloco com o bloco a
substituir na cache principal, passando o bloco a substituir para a vítima e o bloco a aceder para
a cache principal.
No fundo está-se a dar uma segunda chance aos blocos que foram substituídos na cache
principal: em vez de serem descartados por completo na altura da substituição, poderão ainda
ser “repescados” na cache vítima.
A utilização desta técnica acaba por reduzir, ainda que de forma indirecta, os misses devido a
colisões. A única desvantagem é um ligeiro aumento do tempo de penalização no caso de
ocorrer um miss tanto na cache principal como na vítima.
2.5.4.
Técnicas de compilação
Uma outra hipótese de redução do número de faltas na cache pode ser feita através de software,
durante a compilação dos programas. Se o compilador foi projectado para ter em conta
características da cache de um determinado processador, poderão feitas optimizações que tiram
partido dessas características.
Entre o tipo de optimizações mais comuns, destacam-se os seguintes:
•
separação de matrizes (blocking);
•
fusão / separação de ciclos;
•
trocas de índices dentro de ciclos.
Estas técnicas têm em vista reduzir o número de colisões, adaptando as matrizes às dimensões
dos blocos utilizados, de forma a maximizar os acessos a um determinado bloco, antes deste ser
descartado da cache (evitando-se que seja carregado múltiplas vezes).
O detalhe destes métodos sai fora do âmbito da disciplina.
ISCTE-IUL - DCTI
18
3. Memória virtual
3.1. Paginação
3.1.1.
Paginação simples
Uma das formas mais comuns de implementação de memória virtual é a paginação. A ideia
consiste em dividir o espaço virtual em blocos de dimensão fixa designados por páginas. Do
mesmo modo, a memória física encontra-se dividida em blocos com capacidade para conter uma
página, designados por molduras ou page frames.
Cada página do espaço de endereçamento virtual poderá estar colocada numa moldura (na
RAM), num ou mais blocos do disco, ou poderá nem sequer existir fisicamente por o programa
em questão não necessitar de muita memória. Na Figura 7 pretendem-se ilustrar estes conceitos.
Espaço virtual
RAM
Página 0
Moldura 0
Página 1
Moldura 1
Página 2
Moldura 2
Página 3
Moldura 3
Página 4
Disco
Página 5
Página 6
Página 7
Figura 7 – Exemplo de mapeamento de páginas virtuais para localizações físicas.
Observando a Figura 7 podemos concluir, por exemplo, que a página 0 está carregada na
moldura 1 da RAM, a página 1 está no disco, a página 2 está na moldura 2 da RAM, etc. Mais à
frente será discutida a forma como se consegue saber em que localizações físicas (quer na RAM
quer no disco) se encontram cada uma das páginas.
Resta observar como poderá ser obtido um endereço real a partir do virtual quando é utilizada
paginação. Num esquema simples de paginação, o endereço virtual é estruturado segundo duas
partes distintas:
•
Número de página – uma sequência de bits que identifica a página.
•
Deslocamento (offset) – uma sequência de bits que indexa a posição a aceder dentro de
uma página.
Ou seja, na forma mais simples de paginação, um endereço virtual é composto por dois campos
distintos – o número de página e o deslocamento, tal como pode ser observado na Figura 8.
ISCTE-IUL - DCTI
19
Endereço virtual
Nº de página
Deslocamento
Figura 8 – Estrutura de um endereço virtual utilizado pela paginação.
Para ficar com uma ideia mais clara do que é o deslocamento, considere o exemplo ilustrado na
figura adjacente:
Deslocamento = 3
O deslocamento é semelhante ao índice de palavra
utilizado para indexar os blocos na cache.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Página 0
Espaço virtual
Página 1
Repare na posição de memória que se encontra
sombreada (endereço 11). Neste exemplo está-se a
partir do princípio que cada página contém 8
posições diferentes. O endereço 11 corresponde ao
endereço de início da página 1, somado de 3
posições (11 = 8 + 3). O deslocamento é portanto o
número de posições que são contadas a partir do
início da página.
...
...
Vamos agora supor que o sistema utiliza endereços
virtuais de 8 bits – isto quer dizer que o espaço de
endereçamento virtual seria composto por 28 = 256 palavras. Como seria a estruturação dos
endereços virtuais?
Repare que cada página tem 8 palavras, pelo que seriam necessários 3 bits para o deslocamento
(o deslocamento seria portanto um valor entre 0 e 7) e os restantes bits especificariam o número
de página.
Para o exemplo da posição 11 teríamos:
11(10) = 0000 1011 (2)
O deslocamento é dado pelos 3 bits menos significativos, ou seja, é ‘011’ = 3;
O número de página seria dado pelos 5 bits mais significativos – ‘00001’ = 1.
Quando se utiliza paginação, é relativamente fácil a conversão de endereço virtual para real,
desde que se saiba qual o número da moldura em que se encontra determinada página.
Considere a Figura 9, que representa as páginas do espaço virtual que se encontram carregadas
em molduras, na memória RAM. Na figura encontram-se indicados os endereços de início de
cada página, assim como os endereços de início de cada moldura (representados em
hexadecimal). Repare também que o deslocamento dentro de cada página será agora dado por
12 bits (3 dígitos em hexadecimal).
ISCTE-IUL - DCTI
20
Espaço virtual
RAM
0x0000
0x0000
0x1000
0x1000
0x2000
0x2000
0x3000
0x3000
0x4000
0x5000
0x6000
0x7000
Figura 9 – Exemplo de algumas páginas carregadas em RAM.
Qual será então, por exemplo, o endereço real que corresponde ao endereço virtual 0x5f80 ?
Basta observar que a página onde se encontra o endereço 0x5f80 é a página 5, que se encontra
carregada na moldura 3. O endereço real correspondente será dado pelo endereço de início da
moldura 3, somado ao deslocamento. Será portanto o endereço real 0x3f80.
Outra forma de obter o endereço real é concatenar o número da moldura ao deslocamento, isto é
a moldura 0x3 concatenada com o deslocamento 0xf80 resulta em 0x3f80.
De forma a que o hardware consiga traduzir os endereços virtuais em reais, é necessária
existência de uma estrutura de dados que faça a correspondência entre o número de página e a
localização física da mesma. Essa estrutura de dados designa-se por tabela de páginas.
3.1.2.
Tabelas de páginas
Uma tabela de páginas é composta por um número de entradas igual ao número de páginas
existentes no espaço virtual, em que cada entrada da tabela guarda informação referente à
página correspondente. Faz por isso sentido que seja indexada pelo número de página. Em cada
uma das entradas de uma tabela de paginação podemos encontrar um descritor de página. O
descritor de página contém, entre outras informações, um campo que indica o número da
moldura em que se encontra localizada a página em questão (caso esteja carregada na RAM).
Com base numa consulta à tabela de paginação consegue-se traduzir o endereço virtual em real,
tal como se ilustra na Figura 10.
ISCTE-IUL - DCTI
21
Endereço virtual
Nº Página
Deslocamento
Tabela de páginas
0
Descritor da página 0
1
Descritor da página 1
2
Descritor da página 2
3
Descritor da página 3
N-1
Descritor da página N-1
Nº Moldura
Deslocamento
Endereço real
Figura 10 – Tabela de páginas.
A informação e a dimensão dos descritores de páginas variam de sistema para sistema, mas de
uma forma geral, possuem a seguinte informação:
•
Bit de presença – indica se a página se encontra carregada na RAM (nesse caso estará a
‘1’) ou se a página se encontra no disco (nesse caso estará a ‘0’)
•
Bits de protecção – bits de protecção do acesso à página. Por exemplo, nas páginas que
contém as instruções de um programa pode-se limitar o acesso apenas para leitura, de modo
a evitar que possam ser escritos dados nas posições de memória ocupadas pelo programa.
•
Bits de controlo – são normalmente utilizados pelo algoritmo de substituição de páginas,
para decidir qual ou quais as páginas candidatas a serem transferidas para o disco, no caso
de ser necessário espaço na RAM para carregar novas páginas.
•
Número de moldura – o índice da moldura em que se pode encontrar a página a que se
refere o descritor. No caso da página se encontrar em disco, em vez da moldura este campo
poderia conter o bloco do disco no qual se encontraria a página.
A informação que se encontra na tabela de paginação é normalmente controlada por software,
nomeadamente pelo sistema operativo. O hardware limita-se a fornecer o número da página, o
deslocamento e um endereço base da tabela de paginação, pois a tabela de paginação é mantida
na memória RAM.
3.1.3.
Page fault
Durante a execução de um programa com uma dimensão grande, ou se estiverem vários
programas a correr num sistema, poderão existir situações em que uma página necessária não se
encontre na memória RAM, estando localizada no disco. O que será que acontece quando o
processador tanta aceder a uma página que não se encontra na RAM ?
ISCTE-IUL - DCTI
22
Uma primeira hipótese seria aceder à página directamente do disco, mas tal poderia conduzir a
uma grande degradação do desempenho, pois como facilmente se deduz, um acesso ao disco
demora muito mais tempo que um acesso à memória RAM....
Outra hipótese mais eficiente seria carregar a página em falta do disco para RAM e só depois
aceder. Este é o método seguido em todas as arquitecturas que utilizam memória virtual. Para
“informar” o processador que a página pretendida não se encontra na RAM existe um
mecanismo chamado page fault ou página em falta..
Uma page fault ocorre quando se consulta a tabela de páginas e se verifica que o bit de presença
se encontra a ‘0’. Isso significa que a página a aceder não se encontra carregada na RAM.
Ao receber uma page fault, inicia-se um procedimento de procura de uma moldura na RAM que
se encontre disponível para receber a página em falta. Se todas as molduras estiverem ocupadas
é necessário correr um algoritmo de substituição de páginas, que escolhe uma página para
descartar da memória RAM, transferindo-a para o disco, libertando desta forma uma moldura.
Depois de escolhida uma moldura, dá-se início à transferência da página em falta, do disco para
a RAM. Durante o tempo em que é feita essa transferência, o processador pode dedicar-se a uma
outra tarefa.
É necessário ainda actualizar a tabela de páginas, mais concretamente actualizar o descritor da
página que veio do disco e, no caso de ser necessária uma substituição, actualizar também o
descritor da página que foi substituída.
3.1.4.
Algoritmos de substituição de páginas
Tal como foi referido na secção anterior, podem ocorrer situações em que todas as molduras da
RAM estão ocupadas por páginas, sendo necessário substituir uma delas por uma página que
estava no disco, mas que entretanto se tentou aceder.
Nessa altura entra em acção o algoritmo de substituição de páginas. O algoritmo de substituição
de páginas é geralmente da responsabilidade do sistema operativo, o que significa que é corrido
por software.
Apesar de existirem diversos algoritmos de substituição de páginas, todos eles tentam substituir
uma página com uma baixa probabilidade de vir a ser necessária a curto prazo. Como não se
consegue prever se uma página vai ter utilizações futuras, o algoritmo de substituição analisa o
comportamento das páginas, mas no passado. Um algoritmo de substituição de páginas é muito
parecido com um algoritmo de substituição de blocos numa cache associativa (que já foi visto
mais atrás).
Entre os algoritmos de substituição de páginas “clássicos” temos:
•
LRU (Least recently used) – escolhe para substituição a página que não é acedida à mais
tempo;
•
NFU (Not frequently used) – escolhe para substituição a página que foi acedida menos
vezes;
ISCTE-IUL - DCTI
23
•
FIFO (First in, first out) – escolhe para substituição a página que está carregada à mais
tempo na RAM;
•
etc.
Na disciplina de Sistemas Operativos estes (e outros) algoritmos serão estudados com maior
detalhe.
3.1.5.
Paginação multi-nível
Quando o espaço de endereçamento virtual é muito grande, é natural que exista também um
número muito elevado de páginas. Um número muito elevado de páginas significa que a tabela
de páginas tem muitas entradas e portanto poderá ocupar uma quantidade de memória RAM
considerável.
Exemplo:
Suponha que são utilizados 32 bits para os endereços virtuais de um dado sistema em que cada
palavra é um byte. Admitindo que cada página tem uma dimensão de 4KBytes, quantas páginas
existirão ?
A dimensão do espaço virtual é de 232 = 4GBytes. Logo o número de páginas é dado por
4Gbytes / 4Kbytes = 1 Mpáginas.
Se existem 1 Mpáginas, então a tabela de paginação terá 1 M entradas. Como em cada entrada
se tem um descritor com, suponhamos, 8 bytes, uma tabela de paginação ocuparia qualquer
coisa como 8MBytes...
No caso de um programa precisar de poucas páginas, esta situação poderia conduzir a uma
utilização muito pouco eficiente da memória disponível – poder-se-ia mesmo correr o risco de
ser necessária mais memória para guardar as tabelas de paginação do que o exigido pelos
próprios programas.
De forma a evitar este problema, existem esquemas de paginação multi-nível. Num esquema de
paginação multi-nível, em vez de existir uma única tabela de páginas existem várias tabelas de
páginas, mais pequenas, que são mantidas em memória à medida das necessidades do programa
em execução.
Uma esquematização desta ideia pode ser observada na Figura 11, onde se representa um
esquema de paginação a 2 níveis. Estrutura-se o endereço virtual em mais campos, mais
especificamente, subdivide-se o campo do número de página de forma a serem utilizados
índices mais curtos para indexar tabelas. Quanto às tabelas em si, estas podem ser organizadas
em níveis, em que uma tabela de nível anterior contém nas suas entradas os endereços de início
das tabelas do nível seguinte.
ISCTE-IUL - DCTI
24
Endereço virtual
10 bits
10 bits
12 bits
TP1
TP2
Deslocamento
Tabela de 1º nível
(Directoria)
Tabelas de 2º nível
(Tabelas de páginas)
0
1
2
0
1
2
1023
1023
0
1
2
1023
Nº de moldura
Deslocamento
Endereço real
0
1
2
1023
Figura 11 – Exemplo de paginação a 2 níveis.
Na figura, o endereço virtual encontra-se dividido em 3 partes: uma parte que indexa a tabela de
1º nível ou directoria (TP1), uma parte que indexa as tabelas de 2º nível (TP2) e o
deslocamento. Repare que a concatenação dos dois índices (TP1 e TP2) corresponde ao número
de página.
Para converter um endereço virtual em real procede-se do seguinte modo:
•
Com o 1º índice (TP1) acede-se à directoria, e obtêm-se uma referência para uma das
tabelas de 2º nível;
•
Referenciada a tabela de 2º nível, acede-se a esta com base no 2º índice (TP2);
•
A tabela de 2º nível irá conter o descritor de página, construindo-se o endereço real a partir
da moldura obtida nesse descritor.
Suponha agora que um determinado programa só necessita apenas de 2048 páginas. No
esquema da figura pode-se concluir que cada tabela de 2º nível tem 1024 entradas, ou seja,
contém informação respeitante 1024 páginas. Para satisfazer as necessidades do programa serão
apenas necessárias duas tabelas de 2º nível. Como essas tabelas têm que ser referenciadas, a
directoria também será necessária. Tem-se um total de 3 tabelas com 1024 entradas cada uma.
Admitindo novamente que em cada entrada estão 8 bytes, o espaço total para guardar as tabelas
seria dado por 3 × 8bytes × 1024 entradas = 24Kbytes. Comparando este valor com o obtido
ISCTE-IUL - DCTI
25
anteriormente para paginação simples (8MBytes) pode-se concluir que esta solução é vantajosa
sob o ponto de vista de utilização de recursos, especialmente quando se pretende correr
programas que usem pouca memória.
A paginação multi-nível apresenta contudo uma desvantagem: o tempo de conversão de um
endereço virtual em real é maior à medida que aumenta o número de níveis. Basta pensar que
com paginação multi-nível são feito múltiplos acessos à memória (1 por cada nível) para ir
consultando as tabelas. De forma a minorar os atrasos é normalmente utilizada uma pequena
cache especial chamada TLB (Translation lookaside buffer).
3.1.6.
TLB (Translation Lookaside Buffer)
Uma TLB consiste numa cache completamente associativa de dimensões reduzidas2
(tipicamente com 64 a 256 entradas). Esta cache é especial na medida em que não guarda dados
respeitantes ao programa, mas sim dados auxiliares à tradução de endereços virtuais em
endereços reais.
Na realidade os dados que são guardados na TLB são descritores de páginas. Sendo assim, antes
de se consultarem as tabelas de páginas, consulta-se primeiro a TLB e verifica-se se o descritor
da página pretendida se encontra lá guardado. No caso desta verificação ter sucesso, conseguese imediatamente traduzir o endereço virtual para real, dispensando-se deste modo a consulta às
tabelas de páginas e consequentes acessos à memória. No caso do descritor da página pretendida
não se encontrar na TLB, segue-se a via “normal” de tradução, acedendo-se à memória para
consultar a(s) tabela(s).
Uma TLB segue normalmente a estrutura ilustrada na Figura 12.
Etiquetas
(Nos de página)
Blocos de dados
(Descritores)
1
24
Descritor da página 24
1
56
Descritor da página 56
0
xxx
xxx
1
3
Descritor da página 3
0
xxx
xxx
0
xxx
xxx
Bit de validade
Figura 12 – Estrutura e exemplo de conteúdo de uma TLB.
Repare que o número de página é utilizado como etiqueta. Para determinar se o descritor da
página pretendida se encontra na TLB, utilizam-se os mesmos circuitos que numa cache
associativa regular, comparando-se o número da página que se pretende aceder com as etiquetas
válidas na cache.
2
Por exemplo, a maioria dos modelos do processador Intel P4 incluem duas TLBs de 64 entradas cada
uma (uma TLB é utilizada para páginas referentes a instruções, a I-TLB, e outra para páginas referentes a
dados, a D-TLB).
ISCTE-IUL - DCTI
26
Deste modo, para determinar se o descritor de uma determinada página está ou não presente na
TLB, compara-se o número da página que se pretende aceder (extraído directamente do
endereço virtual) com todas as etiquetas presentes na TLB. Estas comparações são todas feitas
em paralelo.
Para ilustrar a vantagem em utilizar uma TLB, considere o seguinte exemplo:
Suponha que o acesso à TLB requer 1 ns e que em 80% dos casos os acessos resultam em
sucesso. Admita também que uma consulta à memória requer 10 ns. Qual será o tempo médio
de conversão de um endereço virtual em real, admitindo que é utilizada:
a) paginação simples
Neste caso, em 80% dos casos o tempo será de 1 ns e nos restantes casos será dado por
um acesso em falta à TLB seguido de um acesso à RAM para consultar a tabela de
paginação. Ou seja:
Tconversão = 0.8 × 1ns + 0.2 × (1ns + 10ns) = 0.8 + 2.2 = 3ns
Quanto ao ganho resultante do uso da TLB, pode-se calcular o rácio entre o tempo que
seria necessário quando não se utiliza a TLB e o tempo resultante com a utilização da
TLB. Tem-se:
Ganho =
10ns
= 3.33
3ns
b) Paginação com 2 níveis
Neste caso, quando o descritor se encontra em falta na TLB serão necessários dois
acessos à RAM – um para consultar a directoria e outro para consultar a tabela de 2º
nível. Tem-se então
Tconversão = 0.8 × 1ns + 0.2 × (1ns + 10ns + 10ns) = 0.8 + 4.2 = 5ns
Ganho =
20ns
=4
5ns
c) Paginação com 3 níveis
Semelhante ao caso anterior, mas desta vez são necessários 3 acessos à RAM para
converter o endereço virtual em físico, quando o descritor não é encontrado na TLB:
Tconversão = 0.8 × 1ns + 0.2 × (1ns + 10ns + 10ns + 10ns) = 0.8 + 6.2 = 7ns
Ganho =
30ns
= 4.29
7ns
Pode-se observar que, para todos estes casos, o facto de utilizar uma TLB com as características
referidas tem um impacto positivo no desempenho do sistema. Esse impacto é tanto maior
ISCTE-IUL - DCTI
27
quanto o número de níveis utilizados na paginação (o que faz sentido, já que se usarem vários
níveis, são mais acessos à memória que a TLB evita em caso de sucesso).
Note também que tudo se pode complicar se existirem memórias cache à mistura…
Nesse caso, o melhor caso para acesso a um determinado endereço (por exemplo para leitura),
seria o correspondente a:
•
a página ter um descritor na TLB (hit na TLB)
•
os dados a aceder estarem em cache (hit na cache – acesso aos dados)
O pior caso seria dado por:
•
a página não tem descritor na TLB; (miss na TLB)
•
o bloco de memória em que se encontra a entrada da tabela de páginas não estar em
cache; (miss na cache – consulta da tabela).
•
o bloco de dados a aceder não se encontra em cache (miss na cache – acesso aos dados).
ISCTE-IUL - DCTI
28
4. Bibliografia
1. Arquitectura de computadores: dos sistemas digitais aos microprocessadores – 2ª
edição, Guilherme Arroz, José Monteiro e Arlindo Oliveira, 2009
2. Computer organization and design: the hardware/software interface – 4th edition,
David Patterson & John Hennessy, Morgan Kaufmann, 2008.
3. Logic and computer design fundamentals – 4th edition, Morris Mano & Charles Kime,
Prentice-Hall, 2007.
4. Computer architecture: a quantitative approach, 3rd edition, John Hennessy, David
Patterson, Morgan Kaufmann, 2003.
5. Computer organization, 5th edition, Carl Zamacher, Zvonko Vranesic, Safwat Zaky,
McGraw Hill, 2002.
6. Structured computer organization, 4th edition, Andrew Tanenbaum, Prentice-Hall
International, 1999.
ISCTE-IUL - DCTI
29
5. Lista de revisões
Versão
Autor
Data
0.01
Tomás Brandão
Jun / 2005
0.02
0.02a
Tomás Brandão
João Pedro Oliveira
Mai / 2009
Mai / 2010
ISCTE-IUL - DCTI
Comentários
Versão draft inicial;
Publicação antecipada para as avaliações 2004/05.
Correcção de gralhas; Reformulação de texto.
Correcção de gralhas.
30