Piotr Gębala

numer albumu: 93983

Informatyka Stosowana

II stopień, stacjonarne

rok: 2013/2014

Modelowanie procesów dyskretnych

Algorytm RMS (Rate Monotonic Scheduling)

Projekt C++

1. Cel projektu.

Celem projektu było zaimplementowanie algorytmu szeregowania procesów cyklicznych RMS w środowisku języka C++. Poza samym algorytmem rozwiązywania zadania, należało przygotować odpowiedni interfejs graficzny, wraz z metodą reprezentacji wyników w postaci wykresu Gantta.

2. Opis algorytmu.

Algorytm RMS jest statycznym algorytmem priorytetowym szeregowania zadań cyklicznych. Jego działanie opiera się na przydzielaniu priorytetów w taki sposób, że najwyższy priorytet zostaje przydzielony do zadania o najkrótszym okresie. Takie zachowanie wynika z tego, że zadania występujące częściej są ważniejsze o tych wykonujących się rzadziej. Priorytety ustalane są na początku działania algorytmu i są niezmienne przez cały czas jego działania.

Zbiór niezależnych zadań cyklicznych może zostać poprawnie uszeregowany na jednym procesorze jeżeli zostanie spełniony warunek konieczny. Współczynnik wykorzystania procesora musi spełniać zależność: n

p

∑ ( i )≤1

i

T

=1

i

gdzie:

pi – czas wykonania zadania

Ti – okres występowania zadania.

Warunek ten wynika z założenia, że łączny stopień wykorzystania czasu pracy procesora przez wszystkie zadania nie może przekroczyć stu procent.

Ponadto warunkiem wystarczającym, który gwarantuje wykonanie n zadań przed upływem ich ograniczenia czasowego jest: n

p

∑ ( i )≤ n(21/ n−1)

i

T

=1

i

gdzie:

n – zbiór szeregowanych zadań.

3. Charakterystyka środowiska implementacyjnego.

Projekt został zaimplementowany w języku C++, w środowisku programu Visual Studio 2012. Ponadto do stworzenia aplikacji oraz rysowania wykresów Gantta użyty został interfejs programistyczny Windows API.

4. Interfejs graficzny.

Okno główne aplikacji składa się z trzech sekcji. W lewym górnym rogu znajdują się przyciski służące do dodawania zadań, uruchomienia procesu szeregowania oraz zakończenia programu. Dodane zadania zostają wyświetlone na liście zadań do szeregowania. W sekcji tej znajduje się również pole informujące o ilości aktualnie dodanych procesów. Kontrolki posiadają pewne ograniczenia. Przycisk odpowiedzialny za szeregowanie jest wyłączony jeżeli nie dodano żadnego zadania. W przypadku gdy nie zostanie podany czas i/lub okres procesu, program wyświetli komunikat ze stosowną informacją. Podobna wiadomość zostanie przekazana również w wypadku, gdy czas wykonania zadania będzie większy od okresu. Po dodaniu procesów do listy i uruchomieniu procesu szeregowania, zostaje sprawdzony warunek konieczny. W przypadku gdy nie zostanie on spełniony, program nie przystąpi do wykonywania algorytmu, a użytkownik zostanie o tym poinformowany przy pomocy stosownego komunikatu.

W prawej górnej części okna znajdują się trzy przyciski służące do uruchomienia programu dla przygotowanych, wprowadzonych już wcześniej danych testowych, które zaprezentują działanie aplikacji.

Ostatnią sekcją znajdującą się w dolnej części okna aplikacji jest obszar rysowania wykresu. Po uruchomieniu procesu szeregowania zostają na nim wyświetlone zadania w postaci wykresu Gantta. Wykres składa się z tylu osi, ile zostało wprowadzonych zadań. Zostało wprowadzone ograniczenie do sześciu elementów w celu poprawnego wyświetlenia całości wyników na ekranie.

Aplikacja uruchomiona dla przykładowych zadań prezentuje się następująco: Ilustracja 1: Okno aplikacji dla przykłądowych danych

5. Implementacja algorytmu szeregowania RMS.

Program składa się z trzech klas: Interfejs (odpowiedzialna za generowanie okna aplikacji), Proces (odpowiedzialna za przechowywanie informacji o pojedynczym procesie), oraz SzeregowanieRMS (odpowiedzialna za wykonania algorytmu szeregowania).

Po dodaniu zadań następuje proces ustalania priorytetów. Zadania sortowane są według ich okresów, następnie nadawane są priorytety (im mniejsza wartość okresu tym większy priorytet.

/** Metoda ustalająca priorytety procesów. Najwyższy priorytet otrzymuje proces o najmniejszym okresie. */

void ustawPiorytety() {

int maxPriorytet = liczbaProcesow;

Proces tmp;

for(int i=0; i<liczbaProcesow; i++) {

for(int j=i; j<liczbaProcesow-1; j++) {

if(tablicaProcesow[j].getOkres()>tablicaProcesow[j+1].getOkres()){

tmp = tablicaProcesow[j];

tablicaProcesow[j] = tablicaProcesow[j+1];

tablicaProcesow[j+1] = tmp;

}

}

}

for(int i=0; i<liczbaProcesow; i++) {

tablicaProcesow[i].setPriorytet(maxPriorytet--);

}

}

Po ustaleniu priorytetów następuje proces szeregowania. Dla każdego zadania sprawdzane jest czy dany okres został już wykorzystany przez jakąś pracę. Jeżeli okres jest niewykorzystany, a w puli procesów znajduje się zadanie oczekujące to może ono zostać przydzielone. W przeciwnym wypadku czas oczekiwania na przydział zostaje zwiększony. Jeżeli czas oczekiwania na przydział jest większy od 0, zadanie czeka na swoją kolej. Jeżeli czas oczekiwania osiągnie wartość 0, proces może zostać przydzielony. Ustalany jest stan PROCES_PRACUJE, a dany okres zostaje oznaczony jako wykorzystany. W

przypadku kiedy w kolejce znajduje się proces o wyższym priorytecie, aktualnie przydzielony proces otrzymuje stan PROCES_USPIONY. Po uszeregowaniu procesów ich stan zostaje zapisany w tablicy historii, która jest dalej przekazywana w celu prezentacji wyniku na ekranie.

/** Metoda główna programu, odpowiedzialna za wykonanie uszeregowania RMS. */

void symulacjaRMS() {

stworzHistorie();

int l;

for (int i = 0; i < koniecPracy; i++) {

bool ustawionoPrace = false;

for(int k=0; k<liczbaProcesow; k++) {

l = tablicaProcesow[k].getOkres();

//sprawdzenie czy dany okres został już wykorzystany przez jakąś pracę if((int)i%l==0){

tablicaProcesow[k].setOkresWykorzystany(false);

tablicaProcesow[k].setNrOkresu();

}

//sprawdzenie czy okres jest niewykorzystany oraz czy jakiś proces oczekuje na obsłużenie

//jeżeli oba warunki są prawdziwe, flaga zostaje ustawiona na true, a proces może zostać przydzielony

if(tablicaProcesow[k].getOkresWykorzystany() == false) if(tablicaProcesow[k].getPracaWykonana() == 0)

tablicaProcesow[k].setflaga(true);

else

tablicaProcesow[k].setflaga(false);

//w przypadku gdy wartość flagi jest nieprawdziwa, zwiększamy czas oczekiwania na przydział procesora

if(tablicaProcesow[k].getflaga() == 0)

tablicaProcesow[k].zwiekszCzekanie();

//jeżeli proces ma ustawiony czas oczekiwania, to czeka na swoją kolej w przeciwnym wypadku przydzielamy mu pracę

if(tablicaProcesow[k].getCzasCzekania() > 0) {

tablicaProcesow[k].czekaj();

} else {

//jeżeli procesor nie wykonuje pracy, przydzielamy mu zadanie if(ustawionoPrace == false){

tablicaProcesow[k].dodajPrace();

ustawionoPrace = true;

//ustalamy też, że dany okres został już wykorzystany if(tablicaProcesow[k].getStan() != 0) {

tablicaProcesow[k].setOkresWykorzystany(true);

}

} else {

//w przeciwnym wypadku jeżeli inny proces o wyższym priorytecie chce pracować, aktualny proces jest usypiany

if (tablicaProcesow[k].getStan() == PROCES_PRACUJE ||

tablicaProcesow[k].getStan() == PROCES_USPIONY) {

tablicaProcesow[k].uspijPrace();

} else {

tablicaProcesow[k].czekaj();

}

}

}

}

//zapisanie stany uszeregowania

zapiszStan();

}

}

Sprawdzanie warunku koniecznego uszeregowania znajduje się w klasie Interfejs, już na etapie pobierania procesów z okna aplikacji.

//sprawdzenie warunku koniecznego uszeregowania RMS

for(int i = 0; i<lp; i++){

suma+=(double)listaCzasow[i]/listaOkresow[i];

}

if(suma<=1){

(…)

}

Klasa Proces przechowuje informacje i pojedynczym procesie takie jak: identyfikator, stan, okres, czy czas pracy. Ponadto można w niej znaleźć metody służące do zmiany stanu procesu.

Klasa Interfejs posiada metody odpowiedzialne za pobranie danych z okna aplikacji, przekazanie ich do obiektu klasy szeregującej, a następnie pobranie wyniku i wyświetlenie go w postaci wykresu Gantta na ekranie.

Podsumowanie

Aplikacja realizuje wyznaczony cel, tj. pozwala na dodawanie procesów oraz ich późniejsze szeregowanie przy pomocy algorytmu RMS, oraz wyświetlenie wyników w postaci wykresów Gantta.

Sam algorytm służy do szeregowanie zadań cyklicznych w czasie rzeczywistym, a wśród algorytmów statycznych, priorytetowych charakteryzuje się tym, że wyznacza uszeregowanie optymalne (jeżeli nie są utrzymane ograniczenia czasowe to żaden inny algorytm z tej klasy ich nie dotrzymuje).