Cvičenie 5 - jednoduchá správa pamäte
Pri riešení tohto cvičenia Vám možno pomôžu:
Úloha 1:
Dokončite implementáciu jednoduchej správy metódou spájaného zoznamu
v triede PamatSpajanyZoznam.
Pred začatím práce si ale prečítajte kód tak, aby ste rozumeli
každej funkcii (ak nerozumiete, tak sa pýtajte) a
riaďte sa pokynmi uvedenými nižšie.
from abc import ABC, abstractmethod
class Pamat(ABC):
def __init__(self,velkost):
self.pamat =
[0]*velkost # pole pamat je pridelovana pamat, jej prvky sy akoze
bajty pamati
@abstractmethod
def __repr__(self):
pass
@abstractmethod
def getMem(self,dlzka): # vysledkom je
index v poli pamat alebo None ak nie je miesto
pass
@abstractmethod
def freeMem(self,adresa,dlzka): # adresa je
index do pola pamat
pass
def zapis_bajt(self,adresa,obsah): # zapise
bajt do pola pamat
self.pamat[adresa] =
obsah
def
citaj_bajt(self,adresa): #
precita bajt z pola pamat
return
self.pamat[adresa]
class PamatSpajanyZoznam(Pamat):
class Node: # trieda zobrazujuca jeden
prvok spajaneho zoznamu a ten zobrazuje jeden usek pamati
def __init__(self, typ,
zaciatok, dlzka, dalsi):
self.typ = typ # 'volny' alebo 'obsadeny'
self.zaciatok = zaciatok
self.dlzka = dlzka
self.dalsi = dalsi
def __init__(self,velkost):
super().__init__(velkost)
self.zoznam =
self.Node('volny',0,velkost,None) # cela pamat je na zaciatku
jeden volny usek
def __repr__(self): # zobraz informaciu o
usekoch pamati
z = self.zoznam
res = ''
n = 1
while z is not None:
res += str(n) + '. ' + z.typ + ', zaciatok:' + str(z.zaciatok) + '
dlzka:'+ str(z.dlzka) +'\n'
z = z.dalsi
n += 1
return res
def getMem(self,dlzka): # vysledkom je
index v poli pamat alebo None ak nie je miesto
pass
def freeMem(self,adresa,dlzka): # adresa je
index do pola pamat
pass
Doprogramujte funkcie getMem a freeMem tak,
aby pri evidencii voľných a obsadených úsekov používali spájaný
zoznam z objektov Node (viď funkciu __init__ triedy PamatSpajanyZoznam)
a aby pri hľadaní voľného úseku používali metódu First fit.
Podúloha 1a - Getmem
Návod:
- Nájde v zozname voľný úsek dĺžky aspoň dlzka.
- Ak taký neexistuje, tak vráti None.
- Upraví zoznam úsekov tak, aby obsahoval informáciu o
obsadenom úseku dĺžky dlzka a, ak bol voľný úsek väčší
než dlzka, aj o zvyšnom voľnom úseku.
- Vráti nájdenú adresu voľného úseku.
Otestujte funkčnosť Getmem, touto funkciou, ale najprv si ju
prečítajte a povedzte si, čo by mala urobiť a aké výsledky by mala
dať.
def testGetMem():
p = PamatSpajanyZoznam(1000)
useky = [0]*10;
# poziadame o 10 usekov pamati po 100 bajtoch a
vyplnime i-ty usek bajtmi s hodnotou i
for i in range(10):
useky[i] =
p.getMem(100) # poziadame o usek pamati
print('pridelene:',useky[i])
print('zoznam
usekov:\n',p)
for j in
range(100): # vyplnime ho cislom i
p.zapis_bajt(useky[i]+j,i)
# kontrolne vypisy adries a stavu pamati
print('useky:',useky)
print('zoznam usekov:\n',p)
# kontrola obsahu pamati
for i in range(10):
for j in range(100):
bajt = p.citaj_bajt(useky[i]+j)
if bajt != i:
print ('zla hodnota',bajt,'na mieste',i,j)
# test, ci vie zistit kedy je pamat plna
u1 = p.getMem(100)
print('toto ma byt None',u1)
Podúloha 1b - FreeMem
Návod:
- Ak je adresa None, tak vyhlási chybu (exception
AdresaNone - zedefinujte novú výnimku).
- Nájde v zozname úsek, ktorý začína na adrese adresa,
ak taký neexituje, tak vyhlási chybu (exception AdresaZla -
zedefinujte novú výnimku).
- Ak nájdený úsek nie je obsadený, tak vyhlási chybu (exception
AdresaZla).
- Ak nájdený úsek nemá dĺžku dlzka, tak vyhlási chybu
(exception DlzkaZla - zedefinujte novú výnimku).
- Upraví zoznam úsekov tak, aby obsahoval informáciu o voľnom
úseku na adrese adresa.
- Ak je pred alebo za uvoľneným úsekom voľný úsek, tak upraví
zoznam úsekov tak, aby obsahoval len jeden voľný úsek, ktorého
dĺžka je ich súčtom.
Testujte program na vhodnej postupnosti volani getMem a
freeMem.
Môžete začať nasledujúcim testom, ale najprv si ho prečítajte a
povedzte si, čo by mal urobiť a aké výsledky by mal dať.
def testGetMemFreeMem():
p = PamatSpajanyZoznam(1000)
useky = [0]*10;
# poziadame o 10 usekov pamati po 100 bajtoch
for i in range(10):
useky[i] =
p.getMem(100) # poziadame o usek pamati
# kontrolne vypisy adries a stavu pamati
print('useky:',useky)
print('zoznam usekov:\n',p)
# uvolnujeme useky v inom poradi nez sme si ich
pridelovali
for i in [0,2,1,9,8,7,5,6,3,4]:
print('uvolnujem',i)
p.freeMem(useky[i],100)
print(p)
# test ci vie zistit, ze uvolnujeme usek, ktory
neexistuje
p.freeMem(123,100); # toto ma vyvolat exception
Podúloha 1c.
Pridajte do testovacej funckie ďalšie časti tak, aby
otestovali aj iné situácie (napr. nerovnako veľké bloky, freeMem so
správnou adresou ale nesprávnou dĺžkou, ...).
Úloha 2:
Po odladení Úlohy 2 vytvorte novú podtriedu triedy PamatSpajanyZoznam
tak, aby jej funkcia getMem používala Circular first
fit.
Zmeňte aj testovaciu funkciu tak, aby dokázala ukázať rozdiel medzi
First Fit a Circular First Fit.
Úloha 3:
Táto úloha je prémia za max. 2 body.
Termín: 14.12.2020 12:20.
Implementujte jednoduchú správu pamäti metódou bitovej mapy (poľa s
prvkami True a False), ako novú potriedu triedy Pamat.
Hodnotím len unikátne riešenia, nie kópie už skôr zaslaných
programov.
Hodnotím aj čiastočné riešenia, prípadne postupne vylepšené riešenia
na základe vzájomnej e-mailovej komunikácie.