Programarea calculatoarelor 2 - Laborator 12

• dimensiunile blocurilor sunt puteri ale lui 2. (Dacă doriţi, puteţi însă implementa un sistem buddy de ordin >= 1, de ex. Fibonacci).
• fiecare bloc conţine un câmp pentru lungime, şi un bit care indică dacă blocul e alocat sau liber
• în plus, blocurile libere conţin câmpuri pentru predecesor şi succesor, păstrându-se câte o listă dublu înlănţuită pentru fiecare dimensiune.
• blocurile au o dimensiune minimă suficientă pentru a conţine câmpurile descrise mai sus
• iniţial, întreg tabloul e un unic bloc liber.

Testaţi programul alternând la întâmplare alocări de dimensiuni aleatoare cu dealocări, de asemenea aleatoare, dintre blocurile alocate deja.

Observaţii:

• Pentru a economisi spaţiu, în loc de lungimea blocului se poate reţine numărul de ordine din secvenţa de lungimi posibile. De exemplu, pentru lungimi 8, 16, 32, ... reţinem 0, 1, 2, etc. La fel, pentru legăturile predecesor şi succesor se poate ţine cont de faptul că adresele blocurilor sunt multipli ale dimensiunii minime. În acest fel, 8 octeţi sunt suficienţi pentru un spaţiu de adrese de 32 de biţi: 5 biţi pentru <= 32 de lungimi posibile, un bit pentru ocupare, şi 2 * (32-3) biti pentru legăturile înainte şi înapoi). Dintre acesţia, doar un octet (cu dimensiunea şi bitul de ocupare) e spaţiul suplimentar folosit într-un bloc ocupat.
• Pentru compactare la eliberarea blocurilor, se poate determina simplu care e blocul "pereche" care trebuie testat: dacă blocul eliberat are dimensiunea 2^i, şi adresa lui (în cadrul tabloului) e un multiplu par de 2^i, perechea sa e vecinul următor de dimensiune 2^i; daca adresa e multiplu impar de 2^i, perechea sa e vecinul anterior.