Mateusz Macięga
nr abumu 94017
Earliest Deadline First
Projekt z przedmiotu Modelowanie
Procesów Dyskretnych
Język: C++
Cel projektu
Celem projektu było zaimplementowanie programu wykonującego
szeregowanie zadań w systemach czasu rzeczywistego zgodnie z algorytmem
EDF.
Poza zaimplementowaniem algorytmu należało przedstawić graficznie
otrzymane uszeregowanie za pomocą wykresu Gantta.
Algorytm EDF
Algorytm EDF jest dynamicznym algorytmem szeregowania używanym w
systemach czasu rzeczywistego, który ustawia procesy w kolejce priorytetowej.
Oznacza to, że priorytety przydzielane są dynamicznie w zależności od czasu
wymaganego do zakończenia obliczeń. Zadanie, które musi się najszybciej
wykonać otrzymuje najwyższy priorytet. W algorytmie tym dopuszcza się
możliwość wywłaszczania bieżącego zadania, jeśli zadanie o wyższym
priorytecie staje się gotowe.
Jest to algorytm optymalny spośród wszystkich algorytmów z dynamicznym
przydziałem priorytetów. Optymalność tego algorytmu polega na tym, że jeśli
EDF nie jest w stanie uszeregować zbioru zadań to żaden inny algorytm z
dynamicznym przydziałem również nie będzie umieć, natomiast jeśli
jakikolwiek inny algorytm uszereguje zbiór zadań to EDF również.
Zbiór zadań jest możliwy do uszeregowania przez algorytm EDF wtedy i tylko
wtedy gdy stopień wykorzystania procesora dla tego zbioru wynosi <= 1.
gdzie C to czas działania i-tego zadania, natomiast T okres i-tego zadania.
i i
Wykorzystana technologia i środowisko
Aplikacja została stworzona w języku C++. Wykorzystano środowisko
programistyczne Visual Studio Ultimate 2012. Do stworzenia interfejsu
graficznego wykorzystano bibliotekę MFC (Microsoft Foundation Classes).
Biblioteka MFC została napisana w C++ i jest obiektową oraz uproszczoną
wersją Microsoft Windows API.
Interfejs graficzny
Interfejs graficzny programu składa się z dwóch głównym części. W
górnej części okna znajduje się kontrolka gdzie rysowany jest wykres Gantta
otrzymanego uszeregowania. Natomiast w dolnej części znajduje się lista
zadań do uszeregowania oraz trzy przyciski, z czego dwa służą do zarządzania
zadaniami do uszeregowania, a za pomocą trzeciego uruchamiamy proces
szeregowania zbioru zadań i rysowania wykresu Gantta.
Po dokonaniu aktualizacji listy zadań do uszeregowania wyliczana jest wartość
U będąca testem uszeregowania. Jeśli obliczona wartość U przekroczy jeden
oznacza, to że algorytm EDF nie jest w stanie uszeregować zbioru zadań.
Przycisk odpowiedzialny za rozpoczęcie procesu szeregowania zostanie
zablokowany. Wartość U wyświetlana jest w dolnej części interfejsu
graficznego.
Ilustracja 1: Interfejs graficzny po uruchomieniu aplikacji
Ilustracja 2: Interfejs graficzny dla przykładowego zbioru zadań
Ilustracja 3: Interfejs graficzny dla przykładowego zbioru nie do uszeregowania
Ilustracja 4: Okno dialogowe
dodania nowego zadania
Implementacja szeregowania algorytmem EDF
Za uszeregowanie odpowiedzialna jest klasa  ZarzadcaProcesami .
Algorytm szeregowania wygląda następująco. Przed szeregowaniem oraz po
zakończeniu bieżącego zadania wybierane jest zadanie, które musi się
najszybciej wykonać. Wartość wyliczana jest ze wzoru  czasTerminuWykonania
 czasDziałaniaZadania .
Jeśli jakieś nowe zadanie stanie się gotowe to aktualnie wykonywane zadanie
zostanie wywłaszczone wtedy i tylko wtedy gdy różnica terminu wykonania
nowego zadania i czasu działania jest mniejsza od różnicy terminu wykonania
aktualnie pracującego zadania i pozostałego czasu działania do wykonania.
/* metoda odpowiedzialna za uszeregowanie procesów zgodnie z algorytmem EDF */
void ZarzadcaProcesami::szeregujEDF() {
//inicjujemy obiekt historii
stworzHistorie();
//co każdą jednostke czasu wykonujemy operacje
for(int i = 0; i < MAKS_CZAS; i++) {
try {
//szukamy proces z najbliższym zakończeniem
Proces procesAktualny = procesZPierwszymZakonczeniem(i);
Proces* pProcesAktualny = NULL;
//przelatujemy wszystkie procesy do uporządkowania
for( int i = 0; i < listaProcesow.size(); i++ )
{
if (listaProcesow[i].dajID() == procesAktualny.dajID()) {
pProcesAktualny = &listaProcesow[i];
listaProcesow[i].wykonajPrace();//proces z najbliższym
zakończeniem pracuje
} else {
if (listaProcesow[i].dajStan() != Proces::PROCES_SKONCZONY) {
listaProcesow[i].czekaj(); //pozostałe procesy
oczekują na swoją kolej
}
}
}
//zapisujemy bieżący stan do historii
zapiszStanDoHistorii();
//sprawdzamy czy aktualnie pracujący proces zakończył już wszystkie zadania
if (pProcesAktualny != NULL) {
pProcesAktualny->sprawdzCzySkonczylPrace();
}
} catch (int error) {
//żaden proces nie pracuje
//zapisujemy bieżący stan do historii
zapiszStanDoHistorii();
}
}
//porządkujemy otrzymaną historię
uporzadkujHistorie();
}
Tabela 1: Uszeregowanie zbioru zadań algorytmem EDF
/* metoda zwracająca proces z najbliższym zakończeniem. Zwrócony proces będzie pracował. */
Proces ZarzadcaProcesami::procesZPierwszymZakonczeniem(int aktualnyCzas) {
//aktualizujemy wszystkie procesy, którym rozpoczął się nowy okres
std::vector procesyZNowymiOkresami = aktualizacjaNowychOkresow(aktualnyCzas);
//szukamy procesu pracującego
Proces* procesPracujacy = czyJakisProcesPracuje();
int minCzasOczekiwania;
if (procesPracujacy != NULL) {
//mamy proces aktualnie pracujący będziemy sprawdzać czy którykolwiek proces z
nowym okresem ma bliższy czas wykonania
if (procesyZNowymiOkresami.size() != 0) {
Proces* procesMin = NULL;
minCzasOczekiwania = std::numeric_limits::max();
for (int i = 0; i < procesyZNowymiOkresami.size(); i++) {
int tymczasCzasOczekiwania = procesyZNowymiOkresami[i].dajOkres() -
procesyZNowymiOkresami[i].dajCzasWykonania();
if (tymczasCzasOczekiwania < minCzasOczekiwania) {
minCzasOczekiwania = tymczasCzasOczekiwania;
procesMin = &procesyZNowymiOkresami[i];
}
}
int aktPracCzasOczekiwania = (procesPracujacy->dajOkres()
- (procesPracujacy->dajDlugoscCzekania() + procesPracujacy-
>dajWykonanaPraca()))
- (procesPracujacy->dajCzasWykonania() - procesPracujacy-
>dajWykonanaPraca());
if (minCzasOczekiwania < aktPracCzasOczekiwania) {
procesPracujacy->uspijPrace();
return *procesMin;
}
}
return *procesPracujacy;
} else {
//szukamy proces wśród uśpionych i do wykonania z najbliższym czasem zakończenia
minCzasOczekiwania = std::numeric_limits::max();
int minIndeks = -1;
for( int i = 0; i < listaProcesow.size(); i++ )
{
if (listaProcesow[i].dajStan() == Proces::PROCES_DO_WYKONANIA ||
listaProcesow[i].dajStan() == Proces::PROCES_USPIONY) {
int tymczasCzasOczekiwania = (listaProcesow[i].dajOkres()
- (listaProcesow[i].dajDlugoscCzekania() +
listaProcesow[i].dajWykonanaPraca()))
- (listaProcesow[i].dajCzasWykonania() -
listaProcesow[i].dajWykonanaPraca());
if (tymczasCzasOczekiwania < minCzasOczekiwania) {
minCzasOczekiwania = tymczasCzasOczekiwania;
minIndeks = i;
}
}
}
if(minIndeks != -1) {
return listaProcesow[minIndeks];
} else {
throw -1;
}
}
}
Tabela 2: Metoda odpowiedzialna za znalezienie zadania z najkrótszym terminem wykonania
Obok klasy szeregującej zbiór zadań stworzona została klasa przechowująca
pojedyncze zadanie. Każdy obiekt tej klasy przechowuje czas działania oraz
okres zadania.
Podsumowanie
Stworzona aplikacja szereguje zdefiniowany zbiór zadań zgodnie z
algorytmem EDF oraz przedstawia wykres Gantta dla uszeregowania.
Algorytm EDF jest optymalnym algorytmem szeregowania zadań cyklicznych w
systemach czasu rzeczywistego.
Bibliografia
1. Earliest deadline first scheduling -
http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling
2. Szeregowanie w systemach czasu rzeczywistego -
http://jedrzej.ulasiewicz.staff.iiar.pwr.wroc.pl/SystemyCzasuRzeczywisteg
o/wyklad/SzeregowanieRTS-5.pdf