Simulirati dinamičko upravljanje radnim spremnikom. Zauzeti dio spremnika koji će predstavljati neki radni spremnik. Ostvariti funkcije:
void *dodijeli(unsigned velicina); void oslobodi(void *kazaljka);
Simulirati dinamičko dodjeljivanje spremnika uz pomoć funkcija dodijeli i oslobodi koje će pronaći mjesto u radnom spremniku za program zadane veličine, te osloboditi dio spremnika na koji pokazuje kazaljka kada program završava.
Za upravljanje potrebna je odgovarajuća struktura podataka. Obzirom na sličnost rada dinamičkog upravljanja spremnikom sa radom funkcija malloc i free može se koristiti i slična struktura podataka.
Definirati tip podataka ZAGLAVLJE
koji sadrži duljinu bloka (u oktetima, uključujući zaglavlje), kazaljku na slijedeći
blok u listi i oznaku da li je blok slobodan.
Zaglavlje se nalazi na početku svakog bloka i služi za povezivanje u listu
blokova. Ostvariti listu slobodnih blokova i po potrebi listu zauzetih blokova!
Popis svih blokova za ispis u programu može se načiniti izravno krećući se od početka spremnika i uzimajući u obzir veličine
blokova.
Funkcija dodijeli vraća kazaljku na zaglavlje, iako bi se prilikom učitavanja programa u radni spremnik trebalo preskočiti zaglavlje. Npr. ako je zaglavlje veličine 12 okteta, a dodijeli je vratio adresu 2060, tada se program može učitati u spremnik s početnom adresom 2060+12 = 2072.
Radi bržeg pretraživanja slobodne blokove treba čuvati u listi sortiranoj po veličini, tako da se odabir "najbolji odgovarajući" može obaviti vrlo brzo.
Ukoliko je tražena veličina manja od duljine bloka koji se dodjeljuje, treba slobodni blok podijeliti na dva dijela i ostatak ostaviti u listi slobodnih blokova. Najmanji blok koji ostaje na taj način mora biti dovoljan za zaglavlje i slobodan prostor duljine jedne jedinice mjere. U suprotnom slučaju se blok ne dijeli nego se dodjeljuje u cijelosti.
Procedura oslobodi treba provjeriti jesu li susjedni blokovi slobodni i, ako jesu, povezati ih u jedan slobodni blok.
Primjer stanja jednog trivijalnog spremničkog sustava koji ima 100 okteta spremnika, veličina zaglavlja 3 okteta (po oktet za veličinu, adresu idućeg slobodnog bloka te oznaku zauzetosti) prikazano je na idućoj slici. Sustav je u stanju kada je prvi blok slobodan, drugi zauzet i treći slobodan.
------------------------------------------------------------------------------------------------------------------ |23|69|0|xxxxxxxxxxxxxxxxxxxx|43|0|1|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|34|0|0|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| ------------------------------------------------------------------------------------------------------------------
Objašnjenje: prvi blok je veličine 23 okteta (20 za program + 3 za zaglavlje), idući slobodni blok nalazi se na adresi 69, blok je slobodan (0); drugi blok je veličine 43 (40+3), obzirom da je zauzet oznaka idućeg slobodnog nema smisla (0), blok je zauzet (1); treći blok veličine je 34 okteta, zadnji je u listi slobodnih blokova (0), blok je slobodan (0). Sa "x" su označeni dijelovi gdje se mogu smjestiti programi.
Program treba omogućiti interaktivno ispitivanje ispravnost rada procedura dodijeli i oslobodi (zahtjeve unositi sa tipkovnice, pri svakoj promjeni ispisati sve zauzete i slobodne blokove).
Prijedlog struktura podataka i nekih makroa - izvorni tekst programa.
# ./a.out RS: broj blokova = 1, slobodni = 1, zauzeti = 0 1: pocetak = 0, velicina = 10000, oznaka = s Unesi zahtjev (d-dodijeli, o-oslobodi): d Unesi velicinu programa (u oktetima): 500 Dodijeljen blok na adresi 0 RS: broj blokova = 2, slobodni = 1, zauzeti = 1 1: pocetak = 0, velicina = 512, oznaka = z 2: pocetak = 512, velicina = 9488, oznaka = s Unesi zahtjev (d-dodijeli, o-oslobodi): d Unesi velicinu programa (u oktetima): 700 Dodijeljen blok na adresi 512 RS: broj blokova = 3, slobodni = 1, zauzeti = 2 1: pocetak = 0, velicina = 512, oznaka = z 2: pocetak = 512, velicina = 712, oznaka = z 3: pocetak = 1244, velicina = 8756, oznaka = s Unesi zahtjev (d-dodijeli, o-oslobodi): o Unesi pocetnu adresu programa: 0 RS: broj blokova = 3, slobodni = 2, zauzeti = 1 1: pocetak = 0, velicina = 512, oznaka = s 2: pocetak = 512, velicina = 712, oznaka = z 3: pocetak = 1244, velicina = 8756, oznaka = s Unesi zahtjev (d-dodijeli, o-oslobodi): d Unesi velicinu programa (u oktetima): 300 Dodijeljen blok na adresi 0 RS: broj blokova = 4, slobodni = 2, zauzeti = 2 1: pocetak = 0, velicina = 312, oznaka = z 2: pocetak = 312, velicina = 200, oznaka = s 3: pocetak = 512, velicina = 712, oznaka = z 4: pocetak = 1244, velicina = 8756, oznaka = s Unesi zahtjev (d-dodijeli, o-oslobodi): o Unesi pocetnu adresu programa: 512 RS: broj blokova = 2, slobodni = 1, zauzeti = 1 1: pocetak = 0, velicina = 312, oznaka = z 2: pocetak = 312, velicina = 9688, oznaka = s