Architektura Komputerów/Wykład 3: Synteza modelu programowego
|
|
Na wstępie zidentyfikujemy wymagania, jakie stawia język wysokiego poziomu przez modelem logicznym procesora i komputera. Pokazane zostanie odwzorowanie obiektów występujących w programie w obiekty obecne w pamięci podczas wykonania programu. Następnie zbudujemy model programowy prostego procesora, nadający się do implementacji podstawowych mechanizmów języka wysokiego poziomu. Na końcu zostanie pokazane przejście od modelu przykładowego procesora do rzeczywistego modelu programowego procesorów rodziny x86. |
|
Głównym celem projektantów pierwszych komputerów było uzyskanie urządzenia, które byłoby w stanie działać bezawaryjnie wystarczająco długo, aby wykonać potrzebne obliczenia. Czasy międzyawaryjne pierwszych komputerów nie przekraczały kilkudziesięciu minut, a ich struktura logiczna była podporządkowana uwarunkowaniom implementacyjnym. Wkrótce po upowszechnieniu komputerów ustabilizowały się metody ich programowania. Obecnie powszechnie używa się języków wysokiego poziomu - proceduralnych i obiektowych. Współczesne komputery są budowane z myślą o programowaniu ich w takich właśnie językach, a ich struktura logiczna jest zaprojektowana tak, aby mogły one łatwo i wydajnie wykonywać prograqmy powstałe przez translację zapisu algorytmów w językach wysokiego poziomu. Pomimo odrębnych paradygmatów programowania, języki obiektowe od strony implementacji nie różnią się znacząco od języków proceduralnych. Możny przyjąć, że komputer, który daje się efektywnie programować w języku C będzie podobnie skutecznie wykonywał programy napisane w innych podobnych językach proceduralnych i obiektowych, takich jak np. Pascal, C++ czy Java. |
|
Przykładowy program w języku C zawiera podstawowe obiekty i mechanizmy występujące w typowych programach. Główna procedura programu wywołuje inne procedury, przekazując do nich argumenty i odbierając wartości. W programie występują dane o różnym zasięku i czasie życia: zmienne zewnętrzne x, y i p; zmienne lokalne i argumenty procedur ora zmienna wskazywana przez zmienną wskaźnikową p. |
|
Wykonanie programu napisanego w języku wysokiego poziomu wymaga umieszczenia w pamięci komputera wszystkich występujących w programie obiektów oraz realizacji mechanizmów związanych z wywoływaniem procedur. Poszczególne rodzaje obiektów – instrukcje i dane – będą odwzorowane w odrębne sekcje, czyli klasy pamięci. Wywoływanie procedur wymaga zrealizowania mechanizmów przekazywania argumentów, przekazywania i zwracania sterowania oraz zwracania wartości funkcji. |
|
Podczas wykonania programu w pamięci znajdą się obiekty czterech podstawowych rodzajów, odwzorowane w różne klasy pamięci. Klasa kodu będzie zawierała instrukcje tworzące program. Klasa danych statycznych zawiera dane zadeklarowane na poziomie zewnętrznym. Klasa danych automatycznych zawiera argumenty wywołania i zmienne lokalne procedur. Klasa danych kontrolowanych zawiera dane dynamiczne jawnie tworzone i usuwane przez programistę. |
|
Kodu programu w postaci ciągów instrukcji jest odwzorowany w sekcję kodu, występującą często pod nazwą TEXT. Sekcja ta nie zmienia swoich rozmiarów ani zawartości przez cały czas wykonywania programu. Jest ona tworzona przed rozpoczęciem wykonywania programu, a niszczona po jego zakończeniu. Z punktu widzenia wykonywanego programu „żyje” ona ciągle, a więc jest statyczna. Oprócz samych instrukcji sekcja może zawierać stałe niezbędne do działania programu, w tym m.in. adresy ciągów instrukcji odpowiedzialnych za poszczególne ścieżki instrukcji złożonych typu switch oraz stałe (literały) występujące w programie, które nie mogą być zapisane bezpośrednio jako argumenty natychmiastowe. |
|
Sekcja danych statycznych zawiera dane deklarowane w języku C na poziomie zewnętrznym oraz dane deklarowane lokalnie wewnątrz procedur ze słowem kluczowym static. Sekcja danych statycznych, podobnie jak sekcja kodu, ma stały rozmiar i istnieje przez cały czas wykonania programu. W sekcji tej mogą jednak występować obiekty o różnych dozwolonych rodzajach dostępu i odmiennych sposobach inicjowania. Wygodnie jest podzielić sekcję danych statycznych na trzy „podsekcje” o różnych atrybutach. |
|
Sekcja danych dynamicznych automatycznych służy do przechowywania argumentów procedur i ich zmiennych lokalnych. Są one powoływane do życia w miarę zagłębiania wywołań procedur i usuwane podczas kończenia wykonania procedur. Kolejność usuwania jest zawsze odwrotna do kolejności tworzenia. Dane te tworzą strukturę danych zwaną stosem. |
|
Dane dynamiczne kotrolowane są alokowane i dealokowane jawnie przez programistę, a ich czas życia nie ma bezpośredniego związku z zagłębianiem procedur. Przed rozpoczęciem dealokacji obszar tych danych zachowuje się podobnie do stosu, jednak kolejność dealokacji może być dowolna, a nowe obiekty mogą być alokowane w miejscu zwolnionym przez poprzednie. Dane dynamiczne kontrolowane tworzą strukturę danych zwaną stertą. |
|
Cztery obszary/klasy obiektów – kod, dane statyczne, stos i sterta – muszą być podczas wykonania programu odwzorowane w przestrzeni adresowej procesora. Na ogół przyjmuje się, że sterta rośnie w kierunku rosnących adresów, a stos – w kierunku adresów malejących. Kolejność rozmieszczenia sekcji w przestrzeni adresowej oraz wartości ich adresów początkowych zależy od decyzji projektanta systemu operacyjnego. Adresy bliskie zera pozostają wolne, a dostęp do nich nie jest dozwolony. Dzięki temu próby odwołań przy użyciu niezainicjowanych zmiennych wskaźnikowych lub wskaźników o wartości NULL (zwykle równej 0) są wychwytywane i sygnalizowane jako błędy wykonania. Poszczególne sekcje ne muszą sąsiadować ze sobą w przestrzeni adresowej. Przestrzeń adresowa – to tylko zbiór adresów,a adresy nie muszą być odwzorowane w fizyczne lokacje pamięci, stąd puste obszary przestrzeni adresowej pomiędzy sekcjami nie zajmują pamięci komputera. |
|
Z cech maszyny von Neumanna wynika pośrednio obecność w procesorze rejestru, służącego do wskazywania kolejnych wykonywanych instrukcji. Ponieważ zawartość tego rejestru jest inkrementowana po pobraniu każdej instrukcji, rejestr ten nosi nazwę licznika instrukcji. Podczas wykonywania instrukcji rejestr PC wskazuje następną instrukcję po aktualnie wykonywanej. Taka wartość PC jest określana jako nextPC (PC następnej instrukcji). Podczas wykonywania instrukcji skoku do rejestru licznika instrukcji jest ładowana nowa wartość. |
|
Procesor przystosowany do wykonywania programu napisanego w języku wysokiego poziomu musi umożliwiać łatwą implementację przekazywania sterowania pomiędzy procedurami. W tym celu potrzebne są dwie instrukcje – skoku ze śladem i powrotu według śladu. Instrukcja skoku ze śladem wykonuje skok po uprzednim zapamiętaniu wartości rejestru PC. Podczas wykonywania instrukcji skoku ze śladem PC wskazuje następną instrukcję po instrukcji skoku, i taka właśnie wartość PC podlega zapamiętaniu. Instrukcja skoku ze śladem służy do przekazania sterowania do procedury (wywołania procedury). Instrukcja powrotu według śladu jest instrukcją skoku, której adres docelowy jest uprzednio zapamiętany m adresem śladu wywołania, czyli adresem wskazującym następną instrukcję po ostatnio wykonanej instrukcji skoku ze śladem. |
|
Z opisu mechanizmów wywołania i powrotu z procedur wynika, że stos oprócz argumentów i zmiennych lokalnych procedur powinien przechowywać również ślady powrotów i ewentualnie inne informacje wymagające przechowania podczas wywoływania procedur. |
|
Pierwszy model procesora zawiera minimum mechanizmów niezbędnych do wykonania zaprezentowanego wcześniej programu w języku C. Modelowy procesor jest wyposażony w rejestr licznika instrukcji oraz rejestr przechowujący wynik obliczeń, służący jednocześnie jako rejestr argumentu źródłowego. Rejestr taki jest nazywany akumulatorem. Model procesora obsługuje stos i realizuje podstawowe operacje na stosie, jednak implementacja stosu pozostaje nieokreślona. Procesor wykonuje dostępy do danych wyspecyfikowanych przez podanie nazw lub wartości. Oczywiście ten aspekt modelu jest wysoce nierealistyczny i ma charakter tymczasowy. |
|
Tabela zawiera opis instrukcji pierwszego modelu procesora. Procesor wykonuje pięć instrukcji dotyczących stosu. PUSH umieszcza wartość na stosie. Instrukcja skoku ze śladem przekazuje sterowanie do procedury po uprzednim zapamiętaniu śladu na stosie. Instrukcja powrotu według śladu odtwarza ślad ze stosu jednocześnie usuwając go. Instrukcja alokacji danej CREATE przypomina instrukcję PUSH, lecz nie nadaje danej na wierzchołku stosu żadnej wartości. Instrukcja DESTROY usuwa daną z wierzchołka stosu. |
|
W typowej konwencji wołania używanej w języku C argumenty wywoływanej procedury są wkładane na stos w kolejności od ostatniego do pierwszego. Dzięki temu tuż przed wywołaniem na wierzchołku stosu jest położony pierwszy argument,a głębiej na stosie znajdują się kolejne argumenty wywołania. |
|
Wywołanie procedury jest realizowane przez pierwsze trzy instrukcje. Rysunek pokazuje zawartość stosu bezpośrednio po wykonaniu instrukcji skoku ze śladem. |
|
|
Pierwsza instrukcja procedura należy do prologu procedury i służy przygotowaniu środowiska jej działania – w tym przypadku alokacji jednej zmiennej lokalnej. Rysunek przedstawia zawartość stosu po zakończeniu prologu. Kolejne cztery instrukcje stanowią ciało procedury. Ostatnia z nich przygotowuje wartość zwracaną przez procedurę. Ostatnie dwie instrukcje stanowią epilog procedury. Służą one do dealokacji zmiennej lokalnej i powrotu do procedury wywołującej. |
|
|
Stos jest najczęściej implementowany w pamięci komputera. W tym celu do procesora wprowadza się rejestr wskaźnika stosu, który zawiera adres wierzchołka stosu. Najczęściej implementowany rodzaj stosu nazywa się stosem pełnym schodzącym. Przy takiej implementacji SP zawiera adres danej ostatnio umieszczonej na stosie, a stos rośnie w kierunku malejących adresów. |
|
Druga wersja modelu procesora stanowi urealnioną odmianę modelu pierwszego. Stos został zaimplementowany w pamięci, co wymagało umieszczenia w procesorze rejestru SP. Posługując się rejestrem SP zdefiniowano jawnie operacje wykonywane przez instrukcje odnoszące się do stosu. Model wciąż korzysta z dostępu do danych przez nazwy. Ten element zostanie dookreślony w trzecim modelu. |
|
Tablica przedstawia definicję instrukcji modelu, w tym symboliczny opis działania instrukcji operujących na stosie. Ponieważ model II różni się od modelu I tylko jawną definicją instrukcji, translacja programu dla modelu II jest identyczna, jak dla modelu I. |
|
Każda procedura do swojego wykonania potrzebuje tylko niewielkiego fragmentu stosu, złożonego z argumentów wywołania, śladu powrotu i zmiennych lokalnych. Fragment stosu używany przez procedurę nazywa się ramką stosu procedury. Część ramki, która jest obecna na stosie w chwili przekazania sterowania do procedury, nazywa się rekordem aktywacji. |
|
W każdej chwili podczas wykonania procedury można wyznaczyć odległość pomiędzy wierzchołkiem stosu i każdym obiektem ramki stosu. Dostęp do obiektów ramki stosu może być realizowany poprzez adresy, stanowiące sumę wskaźnika stosu i stałej, określającej odległość obiektu od wierzchołka stosu. Adresy takie mogą zastąpić nazwy, którymi posługuje się dotychczas wprowadzony model procesora. Adresowanie obiektów poprzez podania ich przemieszczenia względem SP nie jest jednak w ogólnym przypadku wygodne, gdyż podczas wykonywania procedur wywołujących inne procedury wartość SP może się zmieniać. Tym samym zmieniałyby się przemieszczenia liczone względem SP. Adresowani względem SP nie nastręcza problemów w procedurach nie wywołujących innych procedur, czyli tzw. liściach. |
|
Do adresowania ramki stosu można posłużyć się rejestrem wskaźnika ramki. Zawartość wskaźnika ramki, w przeciwieństwie do zawartości wskaźnika stosu, nie zmienia się podczas wykonania ciała procedury. Wskaźnik ramki wskazuje ramkę bieżącej procedury. Oznacza to, że każda procedura ustanawia własną wartość wskaźnika ramki. Każda procedura spodziewa się również, że jej wartość wskaźnika ramki nie zostanie zmieniona. Oznacza to, że procedura musi przed powrotem odtworzyć wskaźnik ramki procedura wołającej. |
|
|
Po wprowadzeniu wskaźnika ramki możemy wskazać odwzorowanie modelu procesora w rzeczywisty model programowy procesorów rodziny x86, używanych w komputerach PC. Procesory x86 posiadają 8 rejestrów uniwersalnych ( w tym główny akumulator EAX, wskaźnik stosu ESP i wskaźnik ramki EBP) oraz rejestr licznika instrukcji oznaczony symbolem EIP. Większość instrukcji występuje w postaci dwuargumentowej, a w zapisie symbolicznym instrukcji jako pierwszy podaje się argument docelowy, a następnie argumenty źródłowe. W instrukcjach arytmetycznych i logicznych argument docelowy jest jednocześnie pierwszym argumentem źródłowym. Procesory x86 umożliwiają adresowanie pamięci sumą zawartości rejestru i stałej (przemieszczenia). Taki tryb adresowania jest wygodny do adresowania obiektów w ramce stosu. Możliwe jest adresowanie zarówno względem wskaźnika stosu, jak i względem wskaźnika ramki. |
|
Tabela zawiera zestawienie instrukcji modelu II i ich odpowiedników w x86. instrukcje LOAD i STOR są zastąpione pojedynczą, dwuargumentową instrukcją przesłania MOV. Operacje CREATE i DESTROY są realizowane jako odjęcie i dodanie stałej określającej rozmiar obiektów do wskaźnika stosu. |
|
Składnia zapisu przykładowego programu jest zgodna z asemblerami rodziny NASM. Sekwencja wywołania dla x86 jest taka sama, jak w dotychczasowych modelach. Alokacja i dealokacj zmiennej r w procedurze wywoływanej polega na wykonaniu prostej operacji na wskaźniku stosu. Podczas wykonania ciała procedury wskaźnik stosu wskazuje zmienną r. Dostępy do obiektów lokalnych są realizowane przy użyciu adresowania względem wskaźnika stosu. Po powrocie z procedury następuje usunięcie argumentów. Polega ono na przesunięciu wskaźnika stosu o rozmiar argumentów – w tym przypadku o 8 (dwa argumenty po 32 bity). Wartość funkcji zostaje zapamiętana w zmiennej statycznej x. Zapis [x] oznacza komórkę pamięci o adresie x. Adres zmiennej jest stałą. która może zostać zapisana symbolicznie. |
|
W wersji korzystającej ze wskaźnika ramki w prologu procedura następuje zapamiętanie wskaźnika ramki procedury wołającej i ustanowienie własnej wartości wskaźnika ramki. Ostatnia instrukcja prologu służy do alokacji zmiennej lokalnej. Można zauważyć, że każda procedura będzie miała niemal identyczny prolog, zawierający trzy instrukcje. Jedyna różnica pomiędzy różnymi procedurami polega na odmiennych rozmiarach alokowanych zmiennych lokalnych. Rysunek przedstawia ramkę stosu procedury podczas wykonywania ciała procedury. pomiędzy śladem powrotu i zmiennymi lokalnymi znajduje się zapamiętany wskaźnik ramki procedury wołającej. Na rysunku zaznaczono adresy poszczególnych obiektów ramki stosu liczone względem rejestru wskaźnika ramki (EBP). Epilog każdej procedury jest identyczny i zawiera trzy instrukcje. Począwszy od modelu 80186 dwie instrukcje (MOV ESP, EBP; POP EBP) mogą być zastąpione pojedynczą, bezargumentową instrukcją LEAVE. |
|
Ponieważ odwołania do pamięci są wolne, we współczesnych procesorach często stosuje się inne implementacje stosu, nie wymagające ciągłych odwołań do pamięci. Jedna lub kilka ramek stosu może zostać umieszczonych w rejestrach procesora. Ponieważ możliwość taka dotyczy tylko obiektów skalarnych określonych typów, w praktyce takie rozwiązanie powoduje istotne komplikacje w przekazywaniu argumentów i alokacji zmiennych lokalnych. Problemem tym zajmuje się jednak kompilator, a programista nie musi być świadomy stopnia komplikacji programu wynikowego. |
