Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Implementacija algoritama: LRU, FIFO , Optimalni i Random

[es] :: C/C++ programiranje :: Implementacija algoritama: LRU, FIFO , Optimalni i Random

[ Pregleda: 3158 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Zeroo
Zeroo Aps
bih

Član broj: 122871
Poruke: 36
*.dlp455.bih.net.ba.



Profil

icon Implementacija algoritama: LRU, FIFO , Optimalni i Random26.11.2006. u 23:07 - pre 182 meseci
E evo nesto dosta tesko...radi se algoritmima zamjene blokova u kes memoriji.Svaki od ovih algoritama radi drugacije.

Prije svega treba znati kako rade ti algoritmi i onda pokusati implementaciju u C++.
Ako neko ima kakvu ideju....sve se prihvata...tnx :-)

 
Odgovor na temu

itf
Zagreb

Član broj: 59794
Poruke: 993
161.53.55.*



+9 Profil

icon Re: Implementacija algoritama: LRU, FIFO , Optimalni i Random27.11.2006. u 08:41 - pre 182 meseci
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č.
 
Odgovor na temu

[es] :: C/C++ programiranje :: Implementacija algoritama: LRU, FIFO , Optimalni i Random

[ Pregleda: 3158 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.