Baixe o app para aproveitar ainda mais
Prévia do material em texto
Professores: Ivanildo Melo e Rosangela Melo ivanildo.melo@paulista.ifpe.edu.br rosangela.melo@paulista.ifpe.edu.br Arquitetura de Computadores Aula 11 – Memória Principal e Secundária: Características, Organização, Arquitetura, Hierarquia e Memória Cache. [Quinta Parte] Sobre este Material 2 O material dessa aula segue o conteúdo literal e em alguns pontos adaptado das seguintes fontes: • MONTEIRO, Mario A. Introdução a Organização de Computadores. 5ª ed. Rio de Janeiro: LTC, 2007. • BARBOSA, Luiz Sérgio de O. Arquitetura e Organização de Computadores. (Apostila) PROINOVALAB- Amazonas. Universidade do Estado do Amazonas (UEA) • TANENBAUM, Andrew S. Organização Estruturada de Computadores. 5ª ed. São Paulo: Pearson Prentice Hall, 2010. • STALLINGS, William. Arquitetura e Organização de Computadores. 8ª ed. São Paulo: Pearson Prentice Hall, 2010. • Tiago Bandeira Marchesan – Memória – Disponível em:<http://coral.ufsm.br/tiago/introcomp/Aula%203%20- %20Memoria.pdf>. • TI Network. Organização de computadores - Aula 9 – Memória – Disponível em: <https://youtu.be/D39L13a7yPg>. • OLIVEIRA, Helder - Mapeamento Associativo e Associativo por Conjunto - Memória Cache Memória Cache - Cont. 3 Nos Mapeamentos Associativos e Associativo por Conjunto quando a memória cache encontra-se completamente ocupada ou cheia, é preciso definir critérios para definir qual o bloco da memória cache será substituído, • Algoritmos de Substituição de Blocos Existentes na Memória Cache 0 1 2 3 Memória Cache - Cont. 4 1. Não aplicado ao mapeamento direto devido ao mapeamento ser fixo alocar o bloco na MP em uma posição fixa na memória cache por meio do uso da função de mapeamento. 2. Cada bloco é mapeado previamente e caso necessite se carregado na memória cache ele ocupará uma posição pré-determinada. • Algoritmos de Substituição de Blocos Existentes na Memória Cache Memória Cache - Cont. 5 • FIFO – First In First Out • LFU – Last Frequently Used • LRU – Least Recently Used • Substituição Aleatória • Algoritmos de Substituição de Blocos Existentes na Memória Cache Memória Cache - Cont. 6 • FIFO – First In First Out • LFU – Least Frequently Used • LRU – Least Recently Used • Substituição Aleatória • Algoritmos de Substituição de Blocos Existentes na Memória Cache Memória Cache - Cont. 7 Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? • Algoritmos de Substituição de Blocos Existentes na Memória Cache FIFO – First In First Out 1. Utiliza o conceito de fila. 2. O primeiro bloco carregado é o primeiro a sair no critério de substituição. 0 1 2 3 Memória Cache - Cont. 8 Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? • Algoritmos de Substituição de Blocos Existentes na Memória Cache FIFO – First In First Out 1. Utiliza o conceito de fila. 2. O primeiro bloco carregado é o primeiro a sair no critério de substituição. 3. Para o exemplo o Bloco “0” seria o candidato a ser substituído, uma vez que ele foi o primeiro a ser carregado. 0 1 2 3 Memória Cache - Cont. 9 Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? • Algoritmos de Substituição de Blocos Existentes na Memória Cache FIFO – First In First Out 1. Utiliza o conceito de fila. 2. O primeiro bloco carregado é o primeiro a sair no critério de substituição. 3. Para o exemplo o Bloco “0” seria o candidato a ser substituído, uma vez que ele foi o primeiro a ser carregado. 4. O Bloco 6 é carregado na memória cache. 0 1 2 3 Memória Cache - Cont. 10 Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? • Algoritmos de Substituição de Blocos Existentes na Memória Cache FIFO – First In First Out 1. Utiliza o conceito de fila. 2. O primeiro bloco carregado é o primeiro a sair no critério de substituição. 3. Para o exemplo o Bloco “0” seria o candidato a ser substituído, uma vez que ele foi o primeiro a ser carregado. 4. O Bloco 6 é carregado na memória cache. 5. Nesse momento a posição 1 da memoria cache passa a ser posição ˜mais antiga˜ 6. O algoritmo FIFO pode ser implementado por meio de um registrador (via hardware) 0 1 2 3 Memória Cache - Cont. 11 Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? • Algoritmos de Substituição de Blocos Existentes na Memória Cache FIFO – First In First Out Considerações importantes: 1. O fato de uma determinada posição ter sido ocupada primeiro não implica dizer que ela não seja relevante ao processo. 2. Uma desvantagem ao utilizar o FIFO está relacionada ao uso de variáveis globais de um determinado programa. 3. Variáveis globais são trechos de códigos frequentemente utilizadas, logo substituir essas posições torna o uso da FIFO como uma estratégia frágil nesse contexto. 0 1 2 3 Memória Cache - Cont. 12 • FIFO – First In First Out • LFU – Least Frequently Used • LRU – Least Recently Used • Substituição Aleatória • Algoritmos de Substituição de Blocos Existentes na Memória Cache Memória Cache - Cont. 13 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used 1. Utiliza um contador para “contar” o uso da posição da memória cache. 0 1 2 3 Contador Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? Memória Cache - Cont. 14 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used 1. Utiliza um contador para “contar” o uso da posição da memória cache. 0 1 2 3 200 Contador Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? Memória Cache - Cont. 15 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used 1. Utiliza um contador para “contar” o uso da posição da memória cache. 0 1 2 3 200 100 Contador Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? Memória Cache - Cont. 16 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used 1. Utiliza um contador para “contar” o uso da posição da memória cache. 0 1 2 3 200 100 10 Contador Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? Memória Cache - Cont. 17 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used 1. Utiliza um contador para “contar” o uso da posição da memória cache. 0 1 2 3 200 100 10 50 Contador Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? Memória Cache - Cont. 18 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used 1. Utiliza um contador para “contar” o uso da posição da memória cache. 2. O bloco a ser substituído é o menos frequentemente utilizado. 0 1 2 3 200 100 10 50 Contador Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? Memória Cache - Cont. 19 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used 1. Utiliza um contador para “contar” o uso da posição da memória cache. 2. O bloco a ser substituído é o menos frequentemente utilizado. 3. O bloco menos utilizado, no exemplo, é o Bloco “2” é o candidato a ser substituído quando o algoritmo LFU é utilizado, visto que ele foi o “menos utilizado”. 0 1 2 3 200 100 10 50 Contador Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? Memória Cache - Cont. 20 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used 1. Utiliza um contador para “contar” o uso da posição da memória cache. 2. O bloco a ser substituído é o menos frequentemente utilizado. 3. O bloco menos utilizado, no exemplo, é o Bloco “2” é o candidato a ser substituídoquando o algoritmo LFU é utilizado, visto que ele foi o “menos utilizado”. 4. O Bloco 6 é carregado na memória cache. 0 1 2 3 200 100 10 50 Contador Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? Memória Cache - Cont. 21 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used Considerações importantes: 1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para implementação, uma vez que elimina a desvantagem presente na FIFO. 0 1 2 3 200 100 10 50 Contador Memória Cache - Cont. 22 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used Considerações importantes: 1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para implementação, uma vez que elimina a desvantagem presente na FIFO. 2. Entretanto, a desvantagem presente na LFU concentra-se na não garantia de que a posição mais frequentemente utilizada não necessariamente tenha sido efetivamente usada. 0 1 2 3 200 100 10 50 Contador Memória Cache - Cont. 23 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used Considerações importantes: 1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para implementação, uma vez que elimina a desvantagem presente na FIFO. 2. Entretanto, a desvantagem presente na LFU concentra-se na não garantia de que a posição mais frequentemente utilizada não necessariamente tenha sido efetivamente usada. 3. Por exemplo, para o exemplo apresentado o Bloco “0” possui uma contagem de 200 acessos. Entretanto, se considerarmos que esses 200 acessos fosse um vetor de 200 posições inicializado apenas?. 0 1 2 3 200 100 10 50 Contador Memória Cache - Cont. 24 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used Considerações importantes: 1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para implementação, uma vez que elimina a desvantagem presente na FIFO. 2. Entretanto, a desvantagem presente na LFU concentra-se na não garantia de que a posição mais frequentemente utilizada não necessariamente tenha sido efetivamente usada. 3. Por exemplo, para o exemplo apresentado o Bloco “0” possui uma contagem de 200 acessos. Entretanto, se considerarmos que esses 200 acessos fosse um vetor de 200 posições inicializado apenas?. 4. Isso significaria que o contador para esse tipo de situação não se mostra uma estratégia interessante, uma vez que dependendo da ação realizada, ela não garantira em efetivo a substituição do menos frequentemente utilizado. Em outras palavras, um bloco seria mantido usando a LFU apenas pela ação de inicialização que se repete e não pelo seu uso. 0 1 2 3 200 100 10 50 Contador Memória Cache - Cont. 25 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LFU – Least Frequently Used Considerações importantes: 1. Quando comparada a FIFO, a LFU mostra-se melhor estratégia para implementação, uma vez que elimina a desvantagem presente na FIFO. 2. Entretanto, a desvantagem presente na LFU concentra-se na não garantia de que a posição mais frequentemente utilizada não necessariamente tenha sido efetivamente usada. 3. Por exemplo, para o exemplo apresentado o Bloco “0” possui uma contagem de 200 acessos. Entretanto, se considerarmos que esses 200 acessos fosse um vetor de 200 posições inicializado apenas?. 4. Isso significaria que o contador para esse tipo de situação não se mostra uma estratégia interessante, uma vez que dependendo da ação realizada, ela não garantira em efetivo a substituição do menos frequentemente utilizado. Em outras palavras, um bloco seria mantido usando a LFU apenas pela ação de inicialização que se repete e não pelo seu uso. 5. Por outro lado, nesse mesmo exemplo o bloco substituído (Bloco “2”) poderia ter trechos de códigos referentes a variáveis globais. Logo, sua substituição não seria adequada, visto que o seu uso se tornaria mais frequente do que a inicialização de um vetor conforme descrito no item 3 e 4. 0 1 2 3 200 100 10 50 Contador Memória Cache - Cont. 26 • FIFO – First In First Out • LFU – Least Frequently Used • LRU – Least Recently Used • Substituição Aleatória • Algoritmos de Substituição de Blocos Existentes na Memória Cache Memória Cache - Cont. 27 • Algoritmos de Substituição de Blocos Existentes na Memória Cache 0 1 2 3 LRU – Least Recently Used 1. Remove o bloco menos recentemente utilizado. Memória Cache - Cont. 28 • Algoritmos de Substituição de Blocos Existentes na Memória Cache 0 1 2 3 LRU – Least Recently Used 1. Remove o bloco menos recentemente utilizado. 2. Se considerarmos os blocos carregados na imagem, o bloco menos recentemente usado seria o Bloco “4” da MP, representado em verde carregado no endereço “0” da memória cache, Memória Cache - Cont. 29 • Algoritmos de Substituição de Blocos Existentes na Memória Cache 0 1 2 3 LRU – Least Recently Used 1. Remove o bloco menos recentemente utilizado. 2. Se considerarmos os blocos carregados na imagem, o bloco menos recentemente usado seria o Bloco “4” da MP, representado em verde carregado no endereço “0” da memória cache, 3. Se o Bloco “0” for acessado, ele passa da condição de menos recentemente utilizado e o Bloco “1” da memória cache representado pela cor laranja passaria ser o bloco menos recentemente utilizado, carregado no endereço “1” da memória cache. Memória Cache - Cont. 30 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used 1. Remove o bloco menos recentemente utilizado. 2. Se considerarmos os blocos carregados na imagem, o bloco menos recentemente usado seria o Bloco “4” da MP, representado em verde carregado no endereço “0” da memória cache, 3. Se o Bloco “0” for acessado, ele passa da condição de menos recentemente utilizado e o Bloco “1” da memória cache representado pela cor laranja passaria ser o bloco menos recentemente utilizado, carregado no endereço “1” da memória cache. 4. Desse modo, o endereço “0” da memória cache passaria a ser o endereço mais recentemente utilizado, ou seja, seria o último a ser substituído na LRU. 0 1 2 3 Memória Cache - Cont. 31 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used Como isso se operacionaliza? 1. Este algoritmo utiliza o conceito de “idade” para indicar se o bloco carregado na linha da cache foi acessado recentemente ou não. 2. Para cada linha de endereço da memoria cache relaciona um “bit de idade” representado no exemplo por 4 bits. 0 1 2 3 0 0 0 0 Bits de Idade Memória Cache - Cont. 32 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used Como isso se operacionaliza? 1. Este algoritmo utiliza o conceito de “idade” para indicar se o bloco carregado na linha da cache foi acessado recentemente ou não. 2. Para cada linha de endereço da memoria cache relaciona um “bit de idade” representado no exemplo por 4 bits. 0 1 2 3 0 0 0 0 0 0 0 1 Bits de Idade Memória Cache - Cont. 33 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used Como isso se operacionaliza? 1. Este algoritmo utiliza o conceito de “idade” para indicar se o bloco carregado na linha da cache foi acessado recentemente ou não. 2. Para cada linha de endereço da memoria cache relaciona um “bit de idade” representado no exemplo por 4 bits. 0 1 2 3 0 0 0 0 0 0 0 1 0 0 1 0 Bits de Idade Memória Cache - Cont. 34 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used Como isso se operacionaliza? 1. Este algoritmo utiliza o conceito de “idade” para indicar se o bloco carregado na linha da cache foi acessado recentemente ou não. 2. Para cada linha de endereço da memoria cache relaciona um“bit de idade” representado no exemplo por 4 bits. 0 1 2 3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 Bits de Idade Memória Cache - Cont. 35 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used Como isso se operacionaliza? 1. Este algoritmo utiliza o conceito de “idade” para indicar se o bloco carregado na linha da cache foi acessado recentemente ou não. 2. Para cada linha de endereço da memoria cache relaciona um “bit de idade” representado no exemplo por 4 bits. 3. Cada “bit de idade” indicará se o bloco carregado na linha de endereço da cache foi acessado recentemente ou não. 0 1 2 3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 Bits de Idade Memória Cache - Cont. 36 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used Como isso se operacionaliza? 1. Este algoritmo utiliza o conceito de “idade” para indicar se o bloco carregado na linha da cache foi acessado recentemente ou não. 2. Para cada linha de endereço da memoria cache relaciona um “bit de idade” representado no exemplo por 4 bits. 3. Cada “bit de idade” indicará se o bloco carregado na linha de endereço da cache foi acessado recentemente ou não. 4. Para o exemplo apresentado, a memória cache está vazia e, após esse processo exemplificado, foi completamente ocupada. 0 1 2 3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 Bits de Idade Memória Cache - Cont. 37 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used 1. O algoritmo busca no “bit idade” o valor do bit que indique o bloco menos recentemente utilizado. 0 1 2 3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 Bits de Idade Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? ? Memória Cache - Cont. 38 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used 1. O algoritmo busca no “bit idade” o valor do bit que indique o bloco menos recentemente utilizado. 2. Para o exemplo, o Bloco carregado na memória cache menos recentemente utilizado é o Bloco “4” que está na linha de endereço “0” da memória cache que possui o bit de idade correspondente a ”0000(2)”. Ele torna-se o candidato a ser substituído. 0 1 2 3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 Bits de Idade Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? ? Memória Cache - Cont. 39 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used 1. O algoritmo busca no “bit idade” o valor do bit que indique o bloco menos recentemente utilizado. 2. Para o exemplo, o Bloco carregado na memória cache menos recentemente utilizado é o Bloco “4” que está na linha de endereço “0” da memória cache que possui o bit de idade correspondente a ”0000(2)”. Ele torna-se o candidato a ser substituído. 3. O Bloco 6 é carregado na memória cache. 0 1 2 3 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 Bits de Idade Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? ? Memória Cache - Cont. 40 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used 1. O algoritmo busca no “bit idade” o valor do bit que indique o bloco menos recentemente utilizado. 2. Para o exemplo, o Bloco carregado na memória cache menos recentemente utilizado é o Bloco “4” que está na linha de endereço “0” da memória cache que possui o bit de idade correspondente a ”0000(2)”. Ele torna-se o candidato a ser substituído. 3. O Bloco 6 é carregado na memória cache. 4. O bit de idade é atualizado para ”0100(2)”. Observe que o bit de idade possui um contador que incrementa a medida em que existe um acesso a posição da memória cache. 0 1 2 3 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 Bits de Idade Como carregar o Bloco 6 da Memória Principal se a memória cache encontra-se cheia? ? Memória Cache - Cont. 41 • Algoritmos de Substituição de Blocos Existentes na Memória Cache LRU – Least Recently Used Considerações Importantes: 1. Diferentemente da LFU que usa um contador a LRU concentra-se no endereço menos recentemente usado para a substituição. 2. O uso da LRU mostra-se mais efetivo do que o LFU e a FIFO por preservar a informação mais recentemente carregada. 3. A LRU promove um número de Cache Hit maior que a LRU e FIFO tendo em vista que utiliza o princípio da localidade temporal. Memória Cache - Cont. 42 • FIFO – First In First Out • LFU – Least Frequently Used • LRU – Least Recently Used • Substituição Aleatória • Algoritmos de Substituição de Blocos Existentes na Memória Cache Memória Cache - Cont. 43 • Algoritmos de Substituição de Blocos Existentes na Memória Cache Substituição Aleatória • Quando um bloco da memória principal precisar vir ou ser carregado para a memoria cache. A linha de endereço selecionada na memória cache será escolhida de maneira aleatória. • Dessa forma, o bloco a ser carregado poderia entrar em qualquer das linhas de endereço da memória cache. • No livro do William Stalings, página 120, contém a seguinte informação sobre Substituição Aleatória: “Estudos de simulação têm mostrado que a substituição aleatória oferece um desempenho apenas ligeiramente inferior a um algoritmo baseado no uso (SMITH, 1982).” Professores: Ivanildo Melo e Rosangela Melo ivanildo.melo@paulista.ifpe.edu.br rosangela.melo@paulista.ifpe.edu.br Arquitetura de Computadores Aula 11 – Memória Principal e Secundária: Características, Organização, Arquitetura, Hierarquia e Memória Cache. [Quinta Parte]
Compartilhar