Cvičenie 5 - jednoduchá správa pamäte
Pri riešení tohto cvičenia Vám možno pomôžu:

• Prezentácia z prednášky
  
• Dokumentácia Pythonu
• Prednášky z Pythonu a ADŠ
  

Ú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.