Doktorant: Wojciech Complak (Wojciech.Complak@cs.poznan.pl)
Ukończone studia: Informatyka, Politechnika Poznańska, maj 1993
Miejsce pracy: Instytut Informatyki Politechniki Poznańskiej

1. Tytuł pracy: Deterministyczne podejście do zarządzania pamięcią notatnikową w systemach silnie uwarunkowanych czasowo
   
2. Otwarcie przewodu doktorskiego: 12.12.1995
   
3. Promotor: Dr hab. inż. Jerzy Nawrocki, prof. PP
   
4. Przyjęcie rozprawy i wyznaczenie recenzentów: styczen 2001
5. Termin obrony: 17.07.2001
6. Recenzenci: Prof. dr hab. inż. Jacek Błażewicz, Politechnika Poznańska
                      Prof. dr hab inż. Adam Janiak, Politechnika Wrocławska

Spis treści

1. WSTĘP
   1.1. Problemy stosowania pamięci notatnikowej w systemach czasu rzeczywistego
   1.2. Cel i zakres pracy
2. METODY SZACOWANIA MAKSYMALNEGO CZASU WYKONANIA
   2.1. Metody empiryczne
   2.2. Metoda symulacyjna
   2.3. Metody analityczne
   2.4. Metoda funkcji atrybutowych
3. MODELE PAMIĘCI NOTATNIKOWEJ
   3.1. Wprowadzenie
   3.2. Koncepcja pamięci notatnikowej
   3.3. Hierarchia i organizacja
   3.4. Mierniki i ocena wydajności pamięci notatnikowej
4. ZARZĄDZANIE ZAWARTOŚCIĄ PAMIĘCI NOTATNIKOWEJ
   4.1. Wprowadzenie
   4.2. Wady statycznej analizy programów
   4.3. Programowe zarządzanie zawartością pamięci notatnikowej
   4.4. Proste ściąganie zawartości
   4.5. Metoda nanizania bloków podstawowych
   4.6. Metoda nanizania bloków pamięci
5. DWUFAZOWE PODEJŚCIE DO SZEREGOWANIA ZADAŃ
   5.1. Wprowadzenie
   5.2. Problem cyklicznego obciążania
   5.3. Problem cyklicznego obciążania dla komputerów z pamięcią notatnikową
   5.4. Algorytm dokładny
   5.5. Algorytm heurystyczny
   5.6. Eksperymentalna ocena heurystyki
6. EKSPANSJA NIEPODZIELNOŚCI ZADAŃ
   6.1. Opis zjawiska
   6.2. Ograniczanie ekspansji niepodzielności zadań
7. PODSUMOWANIE
DODATEK A. Projekt estymatora maksymalnego czasu wykonania
DODATEK B. Analiza rozmiaru kodu i danych typowych procedur
DODATEK C. Ocena wpływu pamięci notatnikowej na wydajność
DODATEK D. Wpływ przerwań na prędkość wykonywania programów
DODATEK E. Wpływ rozmiaru danych na prędkość przetwarzania
DODATEK F. Analiza jądra systemu MINIX	
BIBLIOGRAFIA

1. Wstęp

1.1. Problemy stosowania pamięci notatnikowej w systemach czasu rzeczywistego

System czasu rzeczywistego może być słabo bądź silnie uwarunkowany czasowo. W systemach słabo uwarunkowanych czasowo dopuszczalne jest pewne przekroczenie planowanego terminu zakończenia zadania. Na przykład projektując system obsługi klientów sklepu czy banku można przyjąć, że czas obsługi pojedynczego klienta może być dłuższy niż 30 sekund, o ile nie będzie to dotyczyć więcej niż 10% klientów. Natomiast w systemach silnie uwarunkowanych czasowo jakiekolwiek przekroczenie terminu zakończenia zadania jest niedopuszczalne. Często są to systemy, w których sprawa bezpieczeństwa odgrywa kluczową rolę (ang. mission critical systems). Przykładem może być system automatycznego pilotażu samolotu. Niedopuszczalne jest w tym przypadku przyjęcie założenia projektowego, że automatyczny pilot może spóźnić się ze swoim działaniem, o ile będzie to dotyczyć nie więcej niż 10% lotów – pasażerowie tych lotów byliby narażeni na ogromne niebezpieczeństwo.

Praca dotyczy informatycznych systemów silnie uwarunkowanych czasowo, czyli takich, w których główną rolę odgrywają komputery oraz ich oprogramowanie i obliczenia muszą się zakończyć przed odpowiednimi liniami krytycznymi. Dokładniejsze określenie tej klasy systemów jest zawarte między innymi w normie DIN 44300 [20]. Systemy silnie uwarunkowane czasowo można spotkać praktycznie we wszystkich dziedzinach życia. Przykładem może być system zbierania danych astronomicznych [37], obsługi lotów kosmicznych [11, 18], sterowania radarem [22], tomografii komputerowej [87], nadzorowania pracy wesołego miasteczka [62], zapobiegania blokowaniu kół samochodu w trakcie hamowania (ABS) [47], czy też tak zwane inteligentne budynki [32].

Systemy czasu rzeczywistego są z natury rzeczy wieloprocesowe (wyodrębnionym proce­som zewnętrznym odpowiadają procesy w systemie komputerowym) i mogą być realizowane w środowisku jedno- lub wieloprocesorowym.

Niezależnie od środowiska obliczeniowego potrzebne są metody i narzędzia, które pozwo­lą oszacować maksymalny czas wykonania programu (na przykład czas wykonania funkcji ję­zyka C opisującej działanie danego procesu) na wskazanym procesorze i odpowiedzieć na py­tanie, czy przyjęte rozwiązania gwarantują, że wszystkie procesy (zadania) zostaną wykonane na czas, czyli przed upływem terminów zwanych liniami krytycznymi.

Tego typu analizę nazywa się analizą szeregowalności zadań i opiera się ona na teorii sze­regowania zadań [6, 7, 43, 76]. Potrzebę znajomości maksymalnego czasu wykonania progra­mu (wątku) dostrzegli również twórcy specyfikacji Real Time Javy [8]. Jednym z parametrów konstruktora klasy PeriodicParameters jest parametr cost opisujący maksymalną ilość czasu, jaką otrzyma dany obiekt w pojedynczym okresie. Ponadto w Real Time Javie przewidziano metodę isFeasible, która pozwala zbadać na podstawie przedstawionych wcześniej paramet­rów wątków, czy wątki te (zadania) można uszeregować przed liniami krytycznymi.

Oszacowanie maksymalnego czasu wykonania programu lub jego fragmentu nie jest łatwe. Rzadko kiedy program ma charakter liniowy. Najczęściej zawiera instrukcje warunkowe i pętle, które istotnie utrudniają szacowanie maksymalnego czasu wykonania. Sprawa staje się jeszcze trudniejsza, gdy w programie wykorzystywane są dynamiczne struktury danych i rekurencja. Warto też zauważyć, że w ogólnym przypadku problem szacowania maksymalnego czasu wykonania programu jest nierozstrzygalny, gdyż jest on uogólnieniem problemu sto­pu, o którym wiadomo, że jest również nierozstrzygalny (skoro nie można odpowiedzieć na pytanie czy program się zatrzyma, to tym bardziej nie można odpowiedzieć na pytanie kiedy się zatrzyma). W praktyce jednak postać programu wykorzystywana w dowodzie nierozstrzygalności problemu stopu nie występuje i dla bardzo szerokiej klasy programów można oszacować ich maksymalne czasy wykonania.

Metody szacowania maksymalnego czasu wykonania programu można podzielić na empiryczne, symulacyjne i analityczne. W metodach empirycznych i symulacyjnych informacja o czasie wykonywania programu uzyskiwana jest w drodze eksperymentu. Niestety, ze względu na mechanizmy iteracji i rekurencji nie można w ten sposób określić zachowania systemu w najgorszym przypadku.

Odmienne podejście do szacowania maksymalnego czasu wykonania programu prezentują metody analityczne. Głównym źródłem informacji na temat maksymalnego czasu wykonania programu jest tutaj tekst tego programu. Oprócz niego wykorzystuje się również dane katalogowe opisujące czas wykonania poszczególnych instrukcji procesora oraz informacje na temat sposobu przekładu konstrukcji występujących w programie na język procesora.

Bardzo ważnym i trudnym problemem jest uwzględnienie wpływu pamięci notatnikowej na czas wykonania. Pamięć notatnikowa może skrócić czas wykonania nawet ponad 50-krotnie (Dodatek C), więc trudno zgadzać się na zaniedbanie jej wpływu. Prowadzone w tym zakresie prace zakładały niemodyfikowalność analizowanego kodu i osiągnięcie przy tym założeniu błędu szacowania poniżej 50% wydawało się nie do osiągnięcia [44].

Jeszcze większe wyzwanie, w kontekście pamięci notatnikowej, stanowi obsługa przerwań. Istniejące metody analityczne opierają się na tzw. statycznej analizie programów i klasyfikują każdą instrukcję przekładu analizowanego programu według trzech kategorii:

• zawsze trafiona (ang. always hit) – z analizy przekładu wynika, że dana instrukcja przek­ładu będzie zawsze w pamięci notatnikowej (czyli nie trzeba jej ściągać z pamięci opera­cyjnej), a zatem czas jej wykonania jest minimalny. Na przykład, jeżeli w przekładzie mamy instrukcję mov ax,bx, a po niej add ax,3 i do instrukcji add ax,3 nie ma żadnego skoku oraz obydwie instrukcje znajdują się w tej samej linii pamięci notatnikowej, to przyjmuje się, że instrukcja add ax,3 jest zawsze trafiona, gdyż jej ściągnięcie do pamięci notatnikowej nastąpi nie później niż w momencie wykonania instrukcji mov ax,bx (instrukcje i dane są ściągane do pamięci notatnikowej „paczkami” odpowiadającymi rozmiarowi linii pamięci notatnikowej);
• trafiona za wyjątkiem pierwszego razu (ang. first missed then always hit) – są to głównie instrukcje umieszczone w pętli; przy pierwszym wykonaniu pętli następuje ich ściągnięcie do pamięci notatnikowej i później ich czas wykonania jest już bardzo krótki;
• zawsze nietrafiona (ang. always missed) – do tej kategorii należą między innymi te instrukcje, do których jest wiele skoków z różnych miejsc i wskutek tego nie można ich zakwalifikować do żadnej z wcześniejszych kategorii. Ze względów bezpieczeństwa powiększa się czas wykonania takich instrukcji o czas potrzebny na ich ściągnięcie do pamięci notatnikowej.

Uwzględnienie wpływu przerwań w tym podejściu jest bardzo trudne. Pojawienie się przerwania uruchamia podprogram obsługi przerwania, którego instrukcje i dane mogą wy­przeć z pamięci notatnikowej instrukcje i dane analizowanego programu. W efekcie, należało­by wszystkie instrukcje programu zakwalifikować jako „zawsze nietrafiona”, co jest równo­znaczne z zaniedbaniem wpływu pamięci notatnikowej i może wprowadzić błąd oszacowania maksymalnego czasu wykonania rzędu 1 000%. Innym rozwiązaniem jest zablokowanie przerwań, ale w systemach czasu rzeczywistego jest to nie do przyjęcia.

1.2 Cel i zakres pracy

Celem pracy jest zaproponowanie podejścia do zarządzania pamięcią notatnikową w systemach silnie uwarunkowanych czasowo, które tolerowałoby przerwania bez nadmiernego błędu szacowania maksymalnego czasu wykonania programów.

Proponowane podejście ma charakter deterministyczny. Przed uruchomieniem systemu określany jest tzw. zbiór rezydentów pamięci notatnikowej, czyli tych podprogramów i danych, które przez cały czas będą znajdowały się pamięci notatnikowej i nigdy nie będą z niej wypierane. W pracy przedstawiono algorytm wyboru rezydentów pamięci notatnikowej oraz zaproponowano metody ściągania podprogramów i danych do pamięci notatnikowej dla różnych architektur komputerów. Eksperymenty obliczeniowe i prace projektowe dotyczące prototypu estymatora maksymalnego czasu wykonania programów przeprowadzono na trzech komputerach zgodnych z IBM/PC w środowisku MS–DOS, QNX, MINIX i Microsoft Windows (9X/ME i NT/2000).

W rozdziale 2. dokonano przeglądu istniejących metod analizy maksymalnego czasu wykonania programów, przedstawiając zarówno metody empiryczne, jak i analityczne, stanowiące bazę dla deterministycznego podejścia do zarządzania zawartością pamięci notatnikowej. Ogólne zasady działania pamięci notatnikowej oraz wykorzystywane we współczesnych konstrukcjach rozwiązania sprzętowe omówiono w rozdziale 3. Metody zarządzania zawartością pamięci notatnikowej przedstawiono w rozdziale 4. Zaproponowano różne metody ładowania kodu i danych do pamięci notatnikowej. W najprostszym przypadku – zunifikowanej pamięci notatnikowej – można wykorzystać proste ściąganie zawartości. Metoda ta nie pozwala jednak na ładowanie kodu w nowszych konstrukcjach, które mają oddzielne pamięci notatnikowe kodu i danych (architektura harwardzka). W takiej sytuacji można skorzystać z metody nanizania linii pamięci notatnikowej. W rozdziale 5. przedstawiono dwuetapowe podejście do zarządzania zawartością pamięci notatnikowej. W oparciu o model cyklicznego obciążania konstruowane jest najpierw uszeregowanie przy założeniu braku pamięci notatnikowej. Istniejące rozwiązanie jest następnie ulepszane poprzez ładowanie wybranych elementów, zwanych rezydentami, do pamięci notatnikowej. Wykazano NP-zupełność problemu wyboru rezydentów i zaproponowano algorytm dokładny bazujący na koncepcji programowania dynamicznego. Zaproponowano również algorytm heurystyczny i podjęto próbę eksperymentalnej oceny jego jakości. W rozdziale 6. opisano niepożądane zjawisko ekspansji niepodzielności zadań oraz wskazano jak można jemu przeciwdziałać. W zakończeniu pracy przedstawiono wnioski i kierunki dalszych badań.