W zasadzie to racja. Przerobiłem na szybko, oto efekt.
#include "stdafx.h"
#include <iostream>
using namespace std;
/**
* TEORIA:
*
* Procesy w systemie zgłaszają zapotrzebowanie na dostęp do danej strony.
* Strona może być w pamięci, która ma określony rozmiar (określoną ilość ramek) lub może być zrzucona na dysk.
*
* Więc następuje zgłoszenie zapotrzebowania na jakąś stronę
* Jeśli ta strona jest w pamięci, to wszystko jest ok.
* Jeśli ta strona jest zrzucona na dysk (nie ma jej w pamięci), ale pamięć nie jest w pełni wykorzystana (np ma ilość ramek=5 a ilość stron w pamięci=3), to:
* -> Ładuje się potrzebną strone w wolne miejsce pamięci.
* -> Występuje błąd odwołania do strony (bo nie było jej w pamięci, gdy była potrzebna).
* Jesli ta strona jest akurat zrzucona na dysk, a pamięć jest pełna, to trzeba jej zrobić miejsce w pamięci.
* W tym celu trzeba wyrzucić z pamięci którąś ze stron w niej już obecnych.
* Którą? Na to są te algorytmy. Strona wybrana do wyrzucenia z pamięci nazywa się stroną-ofiarą.
*
*
*/
class Program
{
/**
* odwolania - lista odwolań do stron
* pamięc - ramki (w ktorych mogą być strony)
* random - javowska klasa do losowania liczb
* Integer to obiekt a nie liczba jak int. Dzięki temu można go trzymać w ArrayLiście i używać jak każdego obiektu, ale nie można na przykład wykonywać na nim działań arytmetycznych
* Integer to nadal sama liczba. Nie jakiś obiekt z polem int, wiec nie trzeba żadnych getterów/setterów.
*/
/*private ArrayList<Integer> odwolania;
private Integer pamiec[];
private Random random = new Random();*/
Program(){}
/**
* metodą tworząca struktury danych potrzebne w programie.
* parametr n - ilość ramek czyli wielkość pamięci.
* całą pamięć od razu wypełniam stronami nr -1. Umownie jest to pusta ramka. W przypadku pozostawienia ramki faktycznie pustej przeszkadzałby ulubiony nullPointerException
*/
}
void inicjalizuj(int n)
{
odwolania = new ArrayList<Integer>();
pamiec = new Integer[n];
for(int i=0; i<n; i++)
{
pamiec[i] = -1;
}
}
/**
* metoda losująca ciąg odwołań do stron
* n - ilość ramek
* m - ilość stron
* k - ilość odwołań do stron
*
* np dla n=3; m=10; k=1000
* program utworzy pamięć o wielkości 3 ramek i wylosuje ciąg 1000 odwołań do stron, które będą miały nr od 1 do 10
*/
// public void losujOdwolania(int n, int m, int k)
// {
// inicjalizuj(n);
// int tmp = -1;
// odwolania.add(random.nextInt(m) + 1);// /** ręczne dodanie pierwszego zgłoszenia w ciągu */
// for(int i=1; i<k; i++)
// {
/**
* zasada lokalności odwołań. Jeśli nastąpiło odwołanie do strony x, to istenieje duża szansa, że następne odwołanie będzie do tej samej strony
* tutaj wynosi ona 40%
* metoda nextInt(x) zwraca losowego inta z przedziału [0;x) - przedział otwarty prawostronnie.
*/
// tmp = random.nextInt(101);
// tmp = tmp<40 ? odwolania.get(odwolania.size()-1) : random.nextInt(m) + 1;
// odwolania.add(tmp);
// }
// }
/**
* IDEA:
*
* losuje się jakaś liczna z podanego zakresu.
* kolne kilka (maksymalnie tyle, ile wynosi ZASIEG) bedzie sie różniło od tej wylosowanej o co najwyżej tyle, ile wynosi PARAMETR
* przykład:
* PARAMETR=5, ZASIEG=10
* Wylosowało się odwołanie do strony nr 15. Kolejne 0 do 10 odwołań bedzie tylko do stron o numerach od 10 (15-5) do 20 (15+5).
*
* PARAMETR musi być sensownie dobrany do ilości stron podanych w trakcie obsługi programu
* powidzmy, że PARAMETR = 4, a ilość stron damy 10. Pierwsze odwołanie będzie powiedzmy do strony nr 5. Kolejne ileś odwołań wylosuje się z przedziału 1-9.
* prawie całkowicie pokrywa sie to z całym zakresem losowania od 1-10.
* PARAMETR powinien stanowić jakieś 5-10% wartości ilość stron, którą zamierzasz podać w programie
*
* To ustawienie testowałem dla ilości stron = 50.
*/
void losujOdwolania(int n, int m, int k)
{
inicjalizuj(n);
final int MAX_ZASIEG = 7; /** minimum 1 (wtedy wyłączasz zasadę lokalności)*/
final int PARAMETR = 3;
for(int i=0; i<k; i++)
{
int zasieg = random.nextInt(MAX_ZASIEG)+1; /** za każdym razem losuje się, ile kolejnych stron podopadnie pod zasadę lokalności */
/**
* komentarz do poniższej linijki kodu:
* na przykład m(ilość stron w programie)=50; PARAMETR=10. tmp losuje się wtedy z zakresu 11 do 40. Bo PARAMETR będzie się losował spośród liczb -10 do 10
* To da razem po dodaniu do siebie strony z zakresu 1-50, tak jak podał użytkownik w programie (dodawanie odbywa się kilka linije nieżej, oznaczyłem ją gwiazdkami).
*/
int tmp = random.nextInt(m-2*PARAMETR)+PARAMETR+1;
for (int j=0; (j<zasieg) && (i<k); j++, i++) /**taki dziwny for. Zwaliłem z neta */
{
/**
* funkcja random losuje liczby z zakresu 0 do x. Ja potrzebuję -x do x. Losuję więc liczbę od 0 do 100.
* jak wylosuje się mniej niż 50, to ustawiam znak na -1
* jak wiecej niz 50 lub rowne 50, to ustawiam znak na 1
* Potem wylosowaną liczbę z zakresu 0 do x mnożę razy znak i mam w sumie losowanie od -x do x.
*/
int znak = random.nextInt(101);
znak = znak<50 ? -1 : 1;
odwolania.add((int)(tmp+znak*random.nextInt(PARAMETR+1))); /*******************/
}
}
}
/**
* nie ma nigdzie konstruktora kopiującego, a program będzie zmieniał dane w pamięci.
* Przed testowaniem kazdego kolejnego algorytmu, trzeba będzie ponownie ustawiać ramki pamięci na puste (umownie jak wcześniej).
*/
void czyscPamiec()
{
for(int i=0; i<pamiec.length; i++)
{
pamiec[i] = -1;
}
}
/**
* Metoda sprawdzająca, czy w ktorejś z ramek jest strona o podanym numerze
*/
bool czyJestWPamieci(int odwolanie)
{
int i = 0;
while(i<pamiec.length && !pamiec[i].equals(odwolanie))
{
i++;
}
return i==pamiec.length ? false : true;
}
/**
* Zwraca numer ramki, w której jest strona o podanym numerze
* UWAGA:
* metodę o tej samej nazwie ma każda ArrayLista. Nie należy ich mylić.
*/
int indexOf(int wart)
{
for(int i=0; i<pamiec.length; i++)
{
if(wart==pamiec[i])
{
return i;
}
}
return -1;
}
/**
* zasada działania: http://www.mimuw.edu.pl/~kubica/sop/wyklad8/wyklad.html
*/
int fcfs()
{
int iloscBledowStrony = 0;
int id = 0; /** zmienna trzymająca numer ramki, w której trzeba zastąpić stronę */
czyscPamiec();
pamiec[0] = odwolania.get(0); /** ręczne wstawienie do pierwszej ramki pamięci strony, do której było pierwsze odwołanie */
iloscBledowStrony = id =1; /** nie było jej w pamięci, więc wystąpił pierwszy błąd */
for(int i=1; i<odwolania.size(); i++) /** po kolei dla kazdego kolejnego odwołania do strony rób: */
{
if(!czyJestWPamieci(odwolania.get(i))) /** jeśli nie ma potrzebnej strony w paięci, to: */
{
pamiec[id]=odwolania.get(i); /** wstaw tą strone do pamięci na miejsce id */
id = id==pamiec.length-1 ? 0 : id+1; /**zwiększy id od o 1 albo ustaw na 0 jeśli wskazuje ono już na ostatnią ramkę pamięci (tak tutaj działa FCFS, info w linku) */
iloscBledowStrony++; /** potrzebnej ramki nie było w pamięci, wiec kolejny błąd */
}
}
return iloscBledowStrony;
}
/**
* zasada działania: http://www.mimuw.edu.pl/~kubica/sop/wyklad8/wyklad.html
*/
int opt()
{
int iloscBledowStrony = 0;
int id = 0; /** zmienna trzymająca numer ramki, w której trzeba zastąpić stronę. */
int i = 0;
czyscPamiec();
/**
* pętla wypełniająca poczatkowo pustą pamięć.
* nie trzeba używać żadnych algorytmów, póki są wolne ramki w pamięci.
* Po prostu zapełniamy kolejną wolną.
* Pamiętamy, że odwołanie do strony, której nie ma to zawsze błąd strony, nawet jak pamięć nie jest w pełni zapełniona.
*/
for(i=0; i<odwolania.size() && pamiec[pamiec.length-1]==-1; i++) /** póki ostatnia ramka pamięci ma stronę równą -1, to zgodnie z umową jest pusta i można nadal pamięć zapełniać bez żadnych algorytmów. */
{
if(!czyJestWPamieci(odwolania.get(i))) /** jeśli strony, do której nastąpiło odwołanie nie ma w pamięci, to: */
{
pamiec[id]=odwolania.get(i); /** wstawiamy tą strone w pierwsza wolną ramkę, */
id++; /** zapełniliśmy pozycję id, kolejna potencjalna pozycja do zepłnienia to id+1. */
iloscBledowStrony++; /** nie było potrzbnej strony, czli błąd. */
}
}
/**
* pętla z algorytmem optymalnym, gdy pamięć jest już pełna
*/
for(i=i+1; i<odwolania.size(); i++) /** i+1, bo kontynuacja poprzedniej pętli. Bierzemy kolejne odwołanie do jakiejś strony. */
{
if(!czyJestWPamieci(odwolania.get(i)))
{
id = 0;
/**
* zmienna czasNieuzywania przechowuje infrmacje o tym, za ile będzie ponowne zapotrzebowanie na stronę, która akurat jest w którejś z ramek
* nasz zgłoszenia są w ciągu, np 1 5 6 (7) (1) 2 1 4 4 5 7 8 9 (po lewej zgłoszenie najbliższe, po prawej -ostatnie)
* w jednej ramce jest strona 7, a w drugiej strona 1 (te w nawiasach). Dłużej nie będzie potrzebna strona 7, więc opróżniamy ramkę ze stroną nr 7.
*/
int czasNieuzywania = 0;
for(int j=0; j<pamiec.length; j++)
{
int tmp = 0;
/**
* zmienna tmp zlicza właśnie, ile nie będzie potrzeba stron, które są w ramkach.
* w pętli najpierw sprawdza to dla strony z ramki pierwszej, drugiej, ..., ostatniej.
* id trzyma numer ramki, która trzyma stroną, która najdłużej nie będzie potrzebna.
* strona z ramki nr id to strona-ofiara
*/
for(int k=i; k<odwolania.size() && !odwolania.get(k).equals(pamiec[j]); k++)
{
tmp++;
}
id = tmp>czasNieuzywania ? j : id;
czasNieuzywania = tmp>czasNieuzywania ? tmp : czasNieuzywania;
}
/**
* wstawiamy nową, aktualnie potrzebną stronę w zwolnione miejsce i doliczamy kolejny błąd strony
*/
pamiec[id]=odwolania.get(i);
iloscBledowStrony++;
}
}
return iloscBledowStrony;
}
/**
* zasada działania: http://www.mimuw.edu.pl/~kubica/sop/wyklad8/wyklad.html
*/
/**
* niemal identycznie jak powyżej.
* tam szukaliśmy strony, która nadłużej nie będzie potrzebna (czyli szukanie w ciągu zgłoszeń na prawo od aktualnego).
* tutaj szukamy strony, która najdłużej nie była potrzebna (czyli suzkanie w ciągu zgłoszeń na lewo od aktualnego).
*/
int lru()
{
int iloscBledowStrony = 0;
int id = 0;
int i = 0;
czyscPamiec();
for(i=0; i<odwolania.size() && pamiec[pamiec.length-1]==-1; i++)
{
if(!czyJestWPamieci(odwolania.get(i)))
{
pamiec[id]=odwolania.get(i);
id++;
iloscBledowStrony++;
}
}
for(i=i+1; i<odwolania.size(); i++)
{
if(!czyJestWPamieci(odwolania.get(i)))
{
id = 0;
int czasNieuzywania = 0;
for(int j=0; j<pamiec.length; j++)
{
int tmp = 0;
/**
* jedyna różnica. Pętla idzie "w lewo".
*/
for(int k=i; k>-1 && !odwolania.get(k).equals(pamiec[j]); k--)
{
tmp++;
}
id = tmp>czasNieuzywania ? j : id;
czasNieuzywania = tmp>czasNieuzywania ? tmp : czasNieuzywania;
}
pamiec[id]=odwolania.get(i);
iloscBledowStrony++;
}
}
return iloscBledowStrony;
}
/**
* zasada działania: http://th-www.if.uj.edu.pl/~placzek/dydaktyka/SO/wyklady/wyklad07k.pdf (strona 18)
* Wybrałem alg. bitów odniesienia (ten pierwszy).
* ArrayLista pamiecHelp trzyma te same wartosci, co tablica pamiec, ale w innej kolejności. W kolejności FIFO, w której się poszukuje strony-ofiary
* ArrayLista tablicaBitowOdniesienia trzyma bit odniesienia dla stron z pamiecHelp. Pozycja x w tablicaBitowOdniesienia i pozycja x w pamiecHelp dotyczą tej samej strony
* tablicaBitowOdniesienia jest na Integery, bo Byte ani boolean nie działały. :P Oczywiście to głupie rezerwnować Inta na liczby z zakresu 0-1.
*/
int lruAproks()
{
int iloscBledowStrony = 0;
int id = 0;
int i = 0;
int tmp = 0;
ArrayList<Integer> tablicaBitowOdniesienia = new ArrayList<Integer>();
ArrayList<Integer> pamiecHelp = new ArrayList<Integer>();
czyscPamiec();
/**
* znowu zapełnianie pustych raek pamięci
*/
for(i=0; i<odwolania.size() && pamiec[pamiec.length-1]==-1; i++)
{
if(!czyJestWPamieci(odwolania.get(i)))
{
pamiec[id] = odwolania.get(i);
pamiecHelp.add(pamiec[id]); /** wstawiamy także do pamiecHelp */
id++;
iloscBledowStrony++;
tablicaBitowOdniesienia.add(0); /** bit odniesienia dla nowej strony w pamięci. Na początku jest równy 0. */
}
else
{
/**
* jeśli nastąpiło odwołanie do strony, która już jest w pamięci, to trzeba tej stronie zmienić bit na 1.
*/
tmp = pamiecHelp.indexOf(odwolania.get(i)); /** pozycja tej strony w pamiecHelp */
tablicaBitowOdniesienia.set(tmp, 0); /** jak już znamy pozycję tej strony, to zmieniamy jej bit na 1. */
}
}
/**
* gdy pamięć jest już pełna, to używaj alg. Lru aproksymowany.
*/
for(i=i+1; i<odwolania.size(); i++) /** i+1, bo kontynuacja poprzedniej pętli. Bierzemy kolejne odwołanie do jakiejś strony. */
{
tmp = id = 0;
if(!czyJestWPamieci(odwolania.get(i))) /** jeżeli potrzebnej strony nie ma w pamięci, to: */
{
for(int j=0; j<pamiecHelp.size(); j++) /** przeszukuj po kolei pamiecHelp (ktora jest pamięcią ułożoną do przeglądania FIFO. */
{
if(tablicaBitowOdniesienia.get(j)==0)
{
tmp = j; /** jak znajdziesz strona z bitem równym 0, to zapamietaj jej pozycje pod tmp. */
break; /** Moga być też inne strony z bitem równym 0. Nas interesuje tylko ta pierwsza napotkana. */
}
else
{
tablicaBitowOdniesienia.set(j, 0); /** Jeśli spotkany bit był równy 1 to ustaw na 0 - daj drugą szansę do wywalenia. */
}
/**
* zmieniłem to, bo algorytm rozjejżdżał się ze zwykłym LRU dla ciągów, w których dobrze zadziałała zasada lokalności.
* np dla takich: 5 6 5 5 7 14 14 15 13 14 10 11 11 12
*/
}
id = indexOf(pamiecHelp.get(tmp)); /** szuka w tablicy pamiec tej strony, co wybrał przy przeszukiwaniu FIFO pamiecHelp. Pod id zapisuje jej pozycje */
pamiecHelp.remove(tmp); /** wywala z pamiecHelp znalezona strone, bo będzie ona też wyrzucona z pamiec. */
tablicaBitowOdniesienia.remove(tmp); /** wywala tez bit odniesienia tej strony. */
pamiecHelp.add(odwolania.get(i)); /** dodaj do pamiecHelp obecnie potrzebną stronę. Doda ją na koniec, by zachować kolejnośc do przeglądania FIFO. */
tablicaBitowOdniesienia.add(0); /** to samo z bitem odniesienia. Na początku równy zero. Jego pozycja w tablicaBitowOdniesienia odpowiada pozycji strony (której on dotyczy) w pamiecHelp. */
pamiec[id]=odwolania.get(i); /** wstawienie tej strony do tablicy Pamiec. */
iloscBledowStrony++; /** jak zwykle -błąd, */
/**
* jak widzisz, trzeba samemu kontrolować, by pozycje bitów odniesienia w tablicaBitowOdniesienia były takie same jak
* pozycje odpowiadających im stron w pamiecHelp.
* na początku trochę zagmatwane, ale można zczaić, o co biega.
*/
}
/**
* jeśli strona, do której było odwołanie jest akurat w pamięci, to trzeba tej stronie bit ustawić na 1.
*/
else
{
tmp = pamiecHelp.indexOf(odwolania.get(i)); /** pozycja tej strony w pamiecHelp */
tablicaBitowOdniesienia.set(tmp, 0); /** jak już znamy pozycję tej strony, to zmieniamy jej bit na 1. */
}
}
return iloscBledowStrony;
}
/**
* zasada działania: http://www.mimuw.edu.pl/~kubica/sop/wyklad8/wyklad.html
*/
int rnd()
{
int iloscBledowStrony = 0;
int id = 0;
int i = 0;
Random random = new Random();
czyscPamiec();
/**
* znowu zapełnianie wolnych ramek pamięci na początku.
*/
for(i=0; i<odwolania.size() && pamiec[pamiec.length-1]==-1; i++)
{
if(!czyJestWPamieci(odwolania.get(i)))
{
pamiec[id]=odwolania.get(i);
id++;
iloscBledowStrony++;
}
}
/**
* jak nie ma juz wolnych ramek, to alg. random przy kolejnych odwołaniach do stron.
*/
for(i=i+1; i<odwolania.size(); i++)
{
/**
* jeśli nie ma potrzebnej ramki w pamięci, to trzeba usunąć jedną z tych, co w niej akurat są.
* ktorą ramkę opróżnić? Byle którą. :) Wybierz losowo.
*/
if(!czyJestWPamieci(odwolania.get(i)))
{
id = random.nextInt(pamiec.length);
pamiec[id]=odwolania.get(i);
iloscBledowStrony++;
}
}
return iloscBledowStrony;
}
/**
* do testowania tych przykładów ze stron www
*/
void test(int n)
{
inicjalizuj(n);
odwolania.add(1);
odwolania.add(2);
odwolania.add(3);
odwolania.add(4);
odwolania.add(1);
odwolania.add(2);
odwolania.add(5);
odwolania.add(1);
odwolania.add(2);
odwolania.add(3);
odwolania.add(4);
odwolania.add(5);
}
/**
* menu jak zawsze
*/
void menu()
{
cout<<"1 - Wylosować nowy ciąg odwołań)";
cout<<"2 - Wyświetlić ciąg odwołań";
cout<<"3 - Obliczyć ilość błędów stron dla różnych algorytmów";
cout<<"0 - Zakończ";
}
int _tmain(int argc, _TCHAR* argv[])
{
int flaga = -1;
do
{
cout<<"Co chcesz zrobic?";
menu();
while(token.nextToken()!=token.TT_NUMBER);
flaga = (int)token.nval;
switch(flaga)
{
case 1:
{
cout<<"Podaj ilość odwołań:";
while(token.nextToken()!=token.TT_NUMBER);
int iloscOdwolan = (int)token.nval;
cout<<"Podaj ilość ramek:";
while(token.nextToken()!=token.TT_NUMBER);
int iloscRamek = (int)token.nval;
cout<<"Podaj ilość Stron";
while(token.nextToken()!=token.TT_NUMBER);
int iloscStron = (int)token.nval;
losujOdwolania(iloscRamek, iloscStron, iloscOdwolan);
cout<<"zakończono skukcesem. Uwzględniono zasadę lokalności odwołań.";
break;
}
case 2:
{
if(odwolania.isEmpty())
{
cout<<"najpierw wylosuj ciąg odwołań";
break;
}
int tmp = 0;
while(tmp<odwolania.size())
{
for(int i=0; i<20 && tmp<odwolania.size(); i++)
{
if(odwolania.get(tmp)<10) cout<<"0" + odwolania.get(tmp) + " ";
else cout<<odwolania.get(tmp) + " ";
tmp++;
}
}
break;
}
case 3:
{
cout<<"alg. OPT: " + opt();
cout<<"alg. FCFS: " + fcfs();
cout<<"alg. LRU: " + lru();
cout<<"alg. LRU Aproksymowany: " + lruAproks();
cout<<"alg. RND: " + rnd();
break;
}
/**
* ukryta opcja w menu. ^^ Do testowania tych przykładów z www.
*/
case 4:
{
test(4); /** 4 -ilość ramek */
cout<<"test alg. OPT: " + opt();
cout<<"test alg. FCFS: " + fcfs();
cout<<"test alg. LRU: " + lru();
break;
}
}
}
while(flaga!=0);
return 0;
}