For the OS practical assignment we decided to implement a simulation of the MMU, in python programming language. In this post, I will show the code, an explanation of it, and screen captures of the results.
Page Table
As we already know, the page table is used to do memory translations from logic to physical addresses which are understandable to the drivers.
To begin, the script has as parameters first, the size of the address range, namely, the number of bits the computer has to assign addresses. The second is the size of the main memory, and the third the frame size.
The script starts verifying the parameters, to check if they meet certain conditions. Then some of these values are passed as attributes of the class PageTable and calculates the number of bits belonging to the logical address to get an idea of how many rows the page table will need.
Now to generate the page table, we use a "for" to add to a matrix the rows of the Page Table. To tell how many rows it must add, it uses the value from the logical addresses and raises the 2 to the power of that number. Maps the frames of the main memory, and when it ends, maps it again in the spare addresses, with this we achieve that any accessed logical address will have an assigned physical address.
def __init__(self, tamDireccionVirtual, memoriaP, tamFrame):
if (memoriaP%2 != 0) or \ # El tamaño de la memoria principal debe ser un multiplo de 2
(tamFrame%2 != 0) or \ # El tamaño de las frame debe ser un multiplo de 2
( memoriaP%tamFrame != 0) or \ # El tamaño de la memoria principal debe ser un multiplo de el tamaño de la frama
( pow(2,tamDireccionVirtual) < tamFrame) or \ # El tamaño del frame debe poder contenerse en el rango de direcciones
( tamDireccionVirtual%4 != 0): El rango de direcciones debe ser multiplo de 4
print 'Error'
return
self.tDVirtual = tamDireccionVirtual; # bits
self.ram = memoriaP # bytes
self.tFrame = tamFrame # bytes
self.numeroMaximoFrames = 300
#[Direccion fisica, bit de presencia, bit de persistencia, dirty bit, lectura, escritura, modificacion]
self.pageTable = []
# Calcular el numero de direcciones logicas que se pueden tener
self.numDireccioneslogicas = self.tDVirtual - math.log(self.tFrame,2)
# Generar la page table
print 'Numero de registo logico direccion fisica'
contadorDirFis = 0 # Este contador es utilizado para asignar las primeras direcciones a la memoria principal en la tabla
for i in range(0, (int( pow( 2,self.numDireccioneslogicas)) - 1) ):
if i < self.ram/tamFrame :
self.pageTable.append([contadorDirFis, 1,0,0,0,0,0])
else:
self.pageTable.append([contadorDirFis, 0,0,0,0,0,0])
if( contadorDirFis < (self.ram-self.tFrame) ):
contadorDirFis = contadorDirFis + self.tFrame
else :
contadorDirFis = 0
print "%s %s"%(i,self.pageTable[i])
print 'Page table creada.'
The result is the following:
The Page Table is in charge of translating addresses, so to achieve this, the method obtenerDireccionFisica receives a String parameter with a hexadecimal logical address of a certain size. The method splits the address and gets from it the address of the page in the table and the displacement in memory inside of it, and converts it into an integer.To finish, the method searches for the page in the table, and verifies that this page is found on the main memory, otherwise it raises a "Page Fault".
def obtenerDireccionFisica(self, direccionLogica ):
direccionFisica = direccionLogica[0 : int(self.numDireccioneslogicas/4)] # Parte la direccion logica y obtiene la direccion del frame en la tabla
# Parte la direccion logica y obtiene la direccion de desplazamiento de la frame
desplazamiento = direccionLogica[int(self.numDireccioneslogicas/4) : int(self.tDVirtual /4)]
if self.pageTable[int(direccionFisica, 16)][1] == 1: "Verifica que se encuentre en la memoria principal
return self.pageTable[int(direccionFisica, 16)][0] + int(desplazamiento, 16) # Convierte las direcciones a hexagesimal y obtiene la direccion
else:
return "Page fault"
The result is the following:
The TLB works as a cache memory to translate quicker the last used addresses, this memory is pretty quick, and all the rows are accessed simultaneously, which makes it more useful, the problem is, this memory is very small, so it works together with the Page Table to translate addresses.
The TLB receives as parameters the Page Table and the quantity of rows the TLB cache has, then it builds it using the first rows of the Page Table.
def __init__(self, PageTable, filas):
self.pt = PageTable
self.filas=filas
self.table=[] #[ direccion de pagina, PID, sin usar, direccion fisica, N, D, V, G, vejes]
for i in range(0,self.filas):
self.table.append([i, 0, 0, self.pt.pageTable[i][0],0,0,0,0, 0])
print " {} {}".format(i, self.table[i])
print 'TLB creada'
Result:
To get the physical address, first the TLB splits the logical address in the page address and the displacement, then with a "for" cycle, searches if this address is in the TLB, if it is not there, it searches in the Page Table.
It is important to note, the page table must know which pages bring out, and which bring in the Page Table. For this every row has an "age" number which increments every time a page is brought to the TLB, so when it is necessary to take out a page, the TLB uses this number as an index to decide which one bring out, taking out one of the oldest pages.
def obtenerDireccionFisica(self, direccionLogica ):
direccionDePagina = int( direccionLogica[0 : int(self.pt.numDireccioneslogicas/4)] , 16)
desplazamiento = int( direccionLogica[int(self.pt.numDireccioneslogicas/4) : int(self.pt.tDVirtual /4)] , 16)
vejes = 0
for i in range(0,self.filas):
if vejes < self.table[i][8] :
vejes = self.table[i][8]
for i in range(0,self.filas):
if( self.table[i][0] == direccionDePagina):
print 'Direccion encontrada en la tlb'
for e in range(0,self.filas):
self.table[e][8] = self.table[e][8] + 1
return self.table[i][3] + desplazamiento
print 'Direccion no encontrada en la tlb, buscando en la page table y actualizando la tlb ...'
resultado = self.pt.obtenerDireccionFisica( direccionDePagina, desplazamiento)
if resultado != "Page fault" :
for i in range(0,self.filas):
if vejes == self.table[i][8] :
for e in range(0,self.filas):
self.table[e][8] = self.table[e][8] + 1
self.table[i] = [direccionDePagina, 0, 0, self.pt.pageTable[direccionDePagina][0],0,0,0,0, 0]
self.pt.pageTable[direccionDePagina][1] = 1
break
return resultado
else:
print "Se ha generado un {} moviendo datos y actualizando la tlb...".format(resultado)
for i in range(0,self.filas):
if vejes == self.table[i][8] :
for e in range(0,self.filas):
self.table[e][8] = self.table[e][8] + 1
self.table[i] = [direccionDePagina, 0, 0, self.pt.pageTable[direccionDePagina][0],0,0,0,0, 0]
self.pt.pageTable[direccionDePagina][1] = 1
break
return self.pt.pageTable[direccionDePagina][0] + desplazamiento
Resultado:
Replacement policies:
In the past posts, we explained a script about page replacement, for this assignment we joined that script with the Page Table and TLB scripts in order to test them together.
FIFO
The change wasn't that important to note. We just changed some functions and modified some files in order to replace pages using the FIFO algorithm.
def FIFO(self):
page_fault = 0
memory = []
i = 0
for i in range(len(self.access)):
self.tlb.obtenerDireccionFisica_(i, random.randint(0,math.pow(2,12)) )
if len(memory) < self.mem_size:
if self.access[i] not in memory:
page_fault = page_fault + 1
self.pageTable.pageTable[ self.access[i] ][1] = 1
memory.append(self.access[i])
print "Page %s brought to memory.\t Memory: %s"%(self.access[i], memory)
else:
print "Page %s accessed in memory.\t Memory: %s"%(self.access[i], memory)
elif len(memory) == self.mem_size:
if self.access[i] not in memory:
prev = memory.pop(0)
self.pageTable.pageTable[prev][1] = 0
memory.append(self.access[i])
page_fault = page_fault + 1
print "Page %s ejected, page %s in.\t Memory: %s"%(prev, self.access[i], memory)
else:
print "Page %s page has been accesed.\t Memory: %s"%(self.access[i], memory)
print "Page Faults FIFO: %s"%page_fault
#self.pageTable.imprimirTabla(15)
#self.tlb.imprimirTabla()
return page_fault
And the results of the simulation:
Page table creada. TLB creada Memory size: 40 KB. Frame size: 4 KB. Address space: 20 bits. Number of frames: 10 Number of acceses: 10 TLB number of rows: 8 Direccion encontrada en la tlb Page 8 brought to memory. Memory: [8] Direccion encontrada en la tlb Page 7 brought to memory. Memory: [8, 7] Direccion encontrada en la tlb Page 0 brought to memory. Memory: [8, 7, 0] Direccion encontrada en la tlb Page 5 brought to memory. Memory: [8, 7, 0, 5] Direccion encontrada en la tlb Page 2 brought to memory. Memory: [8, 7, 0, 5, 2] Direccion encontrada en la tlb Page 4 brought to memory. Memory: [8, 7, 0, 5, 2, 4] Direccion encontrada en la tlb Page 8 accessed in memory. Memory: [8, 7, 0, 5, 2, 4] Direccion encontrada en la tlb Page 7 accessed in memory. Memory: [8, 7, 0, 5, 2, 4] Direccion no encontrada en la tlb, buscando en la page table y actualizando la tlb ... Page 0 accessed in memory. Memory: [8, 7, 0, 5, 2, 4] Direccion no encontrada en la tlb, buscando en la page table y actualizando la tlb ... Se ha generado un Page fault moviendo datos y actualizando la tlb... Page 2 accessed in memory. Memory: [8, 7, 0, 5, 2, 4] Page Faults FIFO: 6 <--- Page Table ---> 0 [0, 1, 0, 0, 0, 0, 0] 1 [4096, 0, 0, 0, 0, 0, 0] 2 [8192, 1, 0, 0, 0, 0, 0] 3 [12288, 0, 0, 0, 0, 0, 0] 4 [16384, 1, 0, 0, 0, 0, 0] 5 [20480, 1, 0, 0, 0, 0, 0] 6 [24576, 0, 0, 0, 0, 0, 0] 7 [28672, 1, 0, 0, 0, 0, 0] 8 [32768, 1, 0, 0, 0, 0, 0] 9 [36864, 1, 0, 0, 0, 0, 0] 10 [0, 0, 0, 0, 0, 0, 0] 11 [4096, 0, 0, 0, 0, 0, 0] 12 [8192, 0, 0, 0, 0, 0, 0] 13 [12288, 0, 0, 0, 0, 0, 0] 14 [16384, 0, 0, 0, 0, 0, 0] <--- TLB ---> 0 [8, 0, 0, 32768, 0, 0, 0, 0, 1] 1 [9, 0, 0, 36864, 0, 0, 0, 0, 0] 2 [2, 0, 0, 8192, 0, 0, 0, 0, 10] 3 [3, 0, 0, 12288, 0, 0, 0, 0, 10] 4 [4, 0, 0, 16384, 0, 0, 0, 0, 10] 5 [5, 0, 0, 20480, 0, 0, 0, 0, 10] 6 [6, 0, 0, 24576, 0, 0, 0, 0, 10] 7 [7, 0, 0, 28672, 0, 0, 0, 0, 10]
LRU
The LRU code is larger so I will show just the part about the replacement, because this is where the calls to the TLB and PageTable are seen:
for i in range(len(self.access)):
if len(queue) < self.mem_size:
if self.access[i] not in queue:
queue.insert(0, self.access[i])
else:
self.pageTable.pageTable[ int(queue.index(self.access[i])) ][1] = 0
queue.pop(queue.index(self.access[i]))
queue.insert(0, self.access[i])
self.pageTable.pageTable[self.access[i]][1] = 1
elif len(queue) == self.mem_size:
if self.access[i] not in queue:
page_fault = page_fault+1
previous_index = memory.index(queue.pop())
self.pageTable.pageTable[previous_index] = 0
queue.insert(0, self.access[i])
self.pageTable.pageTable[self.access[i]][1] = 1
else:
self.pageTable.pageTable[int( queue.index(self.access[i]) )][1] = 0
queue.pop(queue.index(self.access[i]))
queue.insert(0, self.access[i])
self.pageTable.pageTable[self.access[i]][1] = 1
if len(memory) < self.mem_size:
And the results of the simulation:
Page table creada. TLB creada Memory size: 40 KB. Frame size: 4 KB. Address space: 20 bits. Number of frames: 10 Number of acceses: 10 TLB number of rows: 8 Sequence: [4, 6, 2, 4, 4, 8, 8, 8, 5, 3] Page 4 brought to memory. Memory: [4] Queue: [4] Direccion encontrada en la tlb Page 6 brought to memory. Memory: [4, 6] Queue: [6, 4] Direccion encontrada en la tlb Page 2 brought to memory. Memory: [4, 6, 2] Queue: [2, 6, 4] Direccion encontrada en la tlb Page 4 accessed in memory. Memory: [4, 6, 2] Queue: [4, 2, 6] Direccion encontrada en la tlb Page 4 accessed in memory. Memory: [4, 6, 2] Queue: [4, 2, 6] Direccion encontrada en la tlb Page 8 brought to memory. Memory: [4, 6, 2, 8] Queue: [8, 4, 2, 6] Direccion encontrada en la tlb Page 8 accessed in memory. Memory: [4, 6, 2, 8] Queue: [8, 4, 2, 6] Direccion encontrada en la tlb Page 8 accessed in memory. Memory: [4, 6, 2, 8] Queue: [8, 4, 2, 6] Direccion encontrada en la tlb Page 5 brought to memory. Memory: [4, 6, 2, 8, 5] Queue: [5, 8, 4, 2, 6] Direccion no encontrada en la tlb, buscando en la page table y actualizando la tlb ... Page 3 brought to memory. Memory: [4, 6, 2, 8, 5, 3] Queue: [3, 5, 8, 4, 2, 6] Direccion no encontrada en la tlb, buscando en la page table y actualizando la tlb ... Se ha generado un Page fault moviendo datos y actualizando la tlb... Page Faults LRU: 6 <--- Page Table ---> 0 [0, 0, 0, 0, 0, 0, 0] 1 [4096, 0, 0, 0, 0, 0, 0] 2 [8192, 0, 0, 0, 0, 0, 0] 3 [12288, 1, 0, 0, 0, 0, 0] 4 [16384, 1, 0, 0, 0, 0, 0] 5 [20480, 1, 0, 0, 0, 0, 0] 6 [24576, 1, 0, 0, 0, 0, 0] 7 [28672, 0, 0, 0, 0, 0, 0] 8 [32768, 1, 0, 0, 0, 0, 0] 9 [36864, 1, 0, 0, 0, 0, 0] 10 [0, 0, 0, 0, 0, 0, 0] 11 [4096, 0, 0, 0, 0, 0, 0] 12 [8192, 0, 0, 0, 0, 0, 0] 13 [12288, 0, 0, 0, 0, 0, 0] 14 [16384, 0, 0, 0, 0, 0, 0] <--- TLB ---> 0 [8, 0, 0, 32768, 0, 0, 0, 0, 1] 1 [9, 0, 0, 36864, 0, 0, 0, 0, 0] 2 [2, 0, 0, 8192, 0, 0, 0, 0, 10] 3 [3, 0, 0, 12288, 0, 0, 0, 0, 10] 4 [4, 0, 0, 16384, 0, 0, 0, 0, 10] 5 [5, 0, 0, 20480, 0, 0, 0, 0, 10] 6 [6, 0, 0, 24576, 0, 0, 0, 0, 10] 7 [7, 0, 0, 28672, 0, 0, 0, 0, 10]
If you have any doubt or comment, feel free to comment bellow.
Y aquí otros dos puntos por lo de paginación. El punto extra por el inglés ya lo incorporé en la entrada sobre las excepciones.
ResponderEliminar