-
Notifications
You must be signed in to change notification settings - Fork 0
/
LRU_aproximado.py
127 lines (95 loc) · 4.6 KB
/
LRU_aproximado.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# Importa os dois arquivos separados que são necessários para o programa
import leitura as L
import funcoes as F
import time
# Chama a função que determina qual arquivo será lido
texto = L.define_leitura()
inicio_leitura = time.time()
# Cria o diretório local para o arquivo que será lido
arquivo = open("traces/" + texto, "r")
dados = []
# Transforma os arquivo de hexadecimal para binário
dados = L.Hex_Bin(dados, arquivo)
arquivo.close()
fim_leitura = time.time()
# Apenas da um clear no terminal para ficar mais organizado
F.clear_terminal()
# O usuário determinará a quantidade de frames que serão utilizados
qtd_frames = int(input("Digite a quantidade de frames disponíveis: "))
F.clear_terminal()
# Como não podemos ter frames igual a zero ou abaixo, o programa para a sua execução
if qtd_frames <= 0:
print("Quantidade de frames não pode ser 0 ou menor!")
exit()
# Chama a função para criar a lista de paginação
paginador = F.B2D_pagina(dados)
set_aux = set()
stack = list()
bitRef = list()
acertos = 0
falhas = 0
"""
Este trecho de código implementa o algoritmo de paginação LRU aproximado. A ideia do algoritmo é manter uma lista de frames (páginas de memória) na memória principal e
substituir uma página quando a lista estiver cheia e uma nova página precisar ser carregada. O LRU (Least Recently Used) significa que a página que foi acessada há mais
tempo deve ser substituída.
No código, a lista set_aux mantém as páginas que estão atualmente na memória, a lista stack mantém a ordem em que as páginas foram acessadas, e a lista bitRef mantém um
bit de referência para cada página, indicando se a página foi referenciada desde a última vez que a lista foi percorrida.
O algoritmo percorre a lista de páginas a serem acessadas paginador e verifica se a página já está na memória. Se sim, atualiza a lista stack para colocar a página mais
recentemente acessada no final, atualiza o bit de referência para True e incrementa o contador de acertos. Se a página não está na memória, adiciona à lista set_aux,
adiciona à lista stack e à lista bitRef com um novo bit de referência False, e incrementa o contador de falhas.
Quando a lista set_aux estiver cheia e uma nova página precisar ser carregada, o algoritmo percorre a lista bitRef procurando por uma página que não tenha sido referenciada
desde a última vez que a lista foi percorrida (ou seja, com o bit de referência False). Se encontrar uma, substitui a página correspondente na lista set_aux e na lista stack
com a nova página e atualiza o bit de referência para False. Se não encontrar, substitui a página no início da lista stack (a menos recentemente acessada) e atualiza as listas
correspondentes.
"""
inicio_paginador = time.time()
for i in paginador:
if len(set_aux) < qtd_frames:
if i in set_aux:
indice = stack.index(i)
if bitRef[indice] == False:
bitRef[indice] = True
else:
stack.remove(i)
del bitRef[indice]
stack.append(i)
bitRef.append(False)
acertos = acertos + 1
else:
stack.append(i)
bitRef.append(False)
set_aux.add(i)
falhas = falhas + 1
else:
if i in set_aux:
indice = stack.index(i)
if bitRef[indice] == False:
bitRef[indice] = True
else:
stack.remove(i)
del bitRef[indice]
stack.append(i)
bitRef.append(False)
acertos = acertos + 1
else:
while bitRef[0] == True:
recente = stack[0]
stack.remove(recente)
del bitRef[0]
stack.append(recente)
bitRef.append(False)
recente = stack[0]
del stack[0]
set_aux.remove(recente)
del bitRef[0]
falhas = falhas + 1
set_aux.add(i)
stack.append(i)
bitRef.append(False)
fim_paginador = time.time()
print("Arquivo lido: " + str(texto))
print("Quantidade de frames: " + str(qtd_frames))
print("Tempo de execução da leitura do arquivo: " + str(round(fim_leitura - inicio_leitura, 2)) + " segundos")
print("Tempo de execução do paginador: " + str(round(fim_paginador - inicio_paginador, 2)) + " segundos")
print("Acertos: " + str(acertos))
print("Falhas: " + str(falhas))