Implementacija algoritama: LRU, FIFO , Optimalni i Random

[ itf @ 27.11.2006. 08:41 ] @

Nije ovo ništa teško kao što ti misliš. Ovi algoritmi koje si nabrojao se koriste u operacijskom sustavu prilikom straničenja (paging-a) i svaki od njih ima svoju karakterističnu brzinu izvođenja. Mogu se na netu naći barem u pseudo kodu pa ti zato neću sve pisati.

Ono što ću ti objasniti jest FIFO metoda. Može se realizirati poljem, listom ili u datoteci. Mislim da će ti biti puno korisnija ova metoda sa listom pošto vjerujem da je riječ o paging-u... a za ostalo se sam malo potrudi :-)

Kada se red (FIFO struktura) realizira listom nije potrebno paziti na cirkularnost jer ne može doći do preljeva i nedostatka mjesta u redu. Jedina greška koja može nastati jest da nema dosta memorije za kreiranje novog elementa. Npr. da imaš strukturu...

Code:
struct zapis {
int element;
struct zapis *sljed;
};
typedef struct zapis lista;

Dodavanje elementa se vrši na ulazu u red.

Code:
int dodaj(lista **ulaz, lista **izlaz, int element) {
    lista *ubaci;
    if((ubaci = (lista*)malloc(sizeof(lista)))!=NULL) {
        ubaci->element = element;
        ubaci->sljed = NULL;
        if(*izlaz == NULL) *izlaz = ubaci;
            else (*ulaz)->sljed = ubaci;
        *ulaz = ubaci;
        return 1;
    }
    return 0;
}

Pokazivač ulaz sada pokazuje na zadnji element u listi, koji je prethodno pokazivačima spojen sa ostalim elementima u redu. Zadnji element u redu ima također svoj pokazivač na novi element u listi. Taj pokazivač se postavlja na vrijednost NULL.

Code:
int skini(lista **ulaz, lista **izlaz, int *element) {
    lista *temp;
    if(*izlaz) {
        *element = (*izlaz)->element;
        temp = *izlaz;
        *izlaz = (*izlaz)->sljed;
        free(temp);
        if(*izlaz == NULL) *ulaz = NULL;
        return 1;
  }
    return 0;
}

Operacija skidanja elemenata iz reda realiziranog listom je puno jednostavnija. Potrebno je pokazivač izlaz preusmjeriti na sljedeći element u redu, a onaj element koji se skida se sprema u varijablu čija je adresa predana kao argument funkciji (ako ti taj element treba u pozivajućem programu). Konačno, oslobađa se memorija koja je bila potrebna za dodavanje tog elementa redu i funkcija vraća 1. Funkcija će vratiti nulu samo u slučaju ako je izlaz NULL pokazivač.