Stos wywołań
W informatyce stos wywołań (dosłownie przetłumaczony z angielskiego jako „stos wywołań”) to obszar pamięci programu, zorganizowany w formie stosu , w którym przechowywane są informacje o aktywnych w danym momencie podprogramach ( aktywne podprogramy to te, które zostały wywołane, ale których wykonanie nie zostało zakończone). Może być tłumaczony jako stos wywołań funkcji (lub wywołań funkcji ) lub stos wywołań metod (lub wywołań metod ) w zależności od typu zastosowanego podprogramu.
Ten typ stosu jest również często określany jako stos wykonania , stos sterowania , stos funkcji lub stos czasu wykonywania , lub, gdy nie ma możliwości pomyłki, po prostu stos .
Zbiór informacji specyficznych dla podprogramu w stosie wywołań nazywany jest ramką .
Operacja
Powodem, dla którego musisz zastosować stos wywołań, jest śledzenie, gdzie każdy aktywny podprogram powinien zwracać kontrolę po zakończeniu wykonywania. Jeśli, na przykład, podprogram DrawSquare (rysowanie kwadratu) wywołuje podprogram DrawLine (rysowanie linii) z czterech różnych punktów, kod DrawLine musi być w stanie wiedzieć, gdzie ma powrócić po wykonaniu. To zadanie jest zwykle wykonywane przez kod dla każdego wywołania w DrawSquare, wstawiając adres instrukcji po określonym „adresie zwrotnym” w stosie wywołań.
Ponieważ stos wywołań jest zorganizowany jako stos, funkcja wywołująca umieszcza adres powrotu na szczycie stosu, a wywoływana podprocedura, po zakończeniu, usuwa adres powrotu ze stosu i przekazuje kontrolę na ten adres. Jeśli wywołany podprogram wywołuje inny podprogram, adres powrotu zostanie umieszczony nad stosem wywołań i tak dalej, informacje są układane i usuwane zgodnie z oczekiwaniami programu . Jeśli wykorzystana zostanie cała przestrzeń dostępna dla stosu wywołań, wystąpi błąd o nazwie przepełnienie stosu . Dodanie podprogramu do stosu wywołań nazywa się nawijaniem ; usunięcie go nazywa się rozwijaniem.
Zwykle istnieje tylko jeden stos wywołań powiązany z uruchomionym programem (a dokładniej z każdym zadaniem lub wątkiem procesu), jednak można utworzyć dodatkowe stosy do obsługi sygnałów lub do kooperacyjnej wielozadaniowości . Ponieważ w tym ważnym kontekście jest tylko jeden, po prostu odnosimy się do stosu (domyślnie „zadania”).
W językach programowania wysokiego poziomu specyfikacje stosu wywołań są ukryte przed programistą . Ten ostatni ma dostęp tylko do listy funkcji, a nie do pamięci zajmowanej przez stos, ani do przyjętej struktury wewnętrznej. Z drugiej strony wiele języków asemblerowych wymaga od programistów zaangażowania w zarządzanie stosem. Szczegóły stosu w języku programowania zależą również od dostępnego kompilatora, systemu operacyjnego i instrukcji.
Cel stosu wywołań
Podstawowym celem stosu wywołań jest:
- przechowywać adresy zwrotne - Kiedy wywoływany jest podprogram, adres instrukcji powrotu musi być gdzieś przechowywany. Używanie stosu do przechowywania adresów zwrotnych ma dużą przewagę nad alternatywami. Jednym z nich jest to, że każde zadanie ma swój własny stos, a zatem podprogramy mogą być „ponowne” i dlatego mogą być aktywne jednocześnie dla różnych zadań wykonujących różne rzeczy. Kolejną zaletą jest to, że rekursja jest obsługiwana automatycznie. Gdy funkcja wywołuje się rekursywnie, adres powrotu musi być zarejestrowany dla każdej aktywacji funkcji, aby można go było użyć do powrotu z każdej aktywacji funkcji. Ta funkcja jest automatyczna ze stosem.
Stos wywołań może mieć dodatkowe cele, w zależności od języka, systemu operacyjnego i środowiska maszyny. Między nimi:
- przechowuj dane lokalne - Podprogram często potrzebuje miejsca w pamięci do zapisu wartości zmiennych lokalnych, zmiennych używanych tylko w aktywnym podprogramie i które nie mogą przechowywać wartości po powrocie (do funkcji wywołującej). Często wygodnie jest przydzielić miejsce do tego celu, aby po prostu przenieść się na górę stosu na tyle, aby mieć miejsce. Jest to bardzo szybkie w porównaniu np. z alokacją sterty . Każda inna aktywacja podprogramu ma osobną przestrzeń stosu dla danych lokalnych.
- przekazywanie parametrów — podprogramy często wymagają podania wartości parametrów przez kod, który je wywołuje, i często zdarza się, że miejsce na te parametry znajduje się w stosie wywołań. Generalnie, jeśli jest tylko kilka małych parametrów, rejestry procesora mogą być używane do przekazywania wartości, ale jeśli jest więcej parametrów do zarządzania w ten sposób, wymagana jest przestrzeń pamięci. Stos wywołań najlepiej sprawdza się jako miejsce dla tych parametrów, zwłaszcza że każde wywołanie podprogramu, które będzie miało różne wartości parametrów, będzie miało osobne miejsce w stosie wywołań dla tych wartości.
- stos ewaluacyjny — argumenty operacji arytmetycznych i logicznych są często wprowadzane do rejestru i tam używane. Jednak w niektórych sytuacjach operandy mogą być ułożone w stos na dowolnej głębokości, co oznacza, że należy użyć czegoś więcej niż rejestr. Stos tych operandów, podobnie jak w przypadku komputerów typu RPN, nazywany jest stosem oceny i może zajmować miejsce na stosie wywołań.
- wskaźnik bieżącej instancji — niektóre języki zorientowane obiektowo (takie jak C++ ) przechowują ten wskaźnik jako argument do funkcji w stosie wywołań podczas wywoływania metody. Ten wskaźnik wskazuje wystąpienie obiektu, z którym jest skojarzona wywołana metoda. Jest to zasadnicza część kontekstu wykonania języków obiektowych, ponieważ zapewnia dostęp do danych posiadanych przez bieżący obiekt. Ten wskaźnik jest połączony z warstwami używanymi w warstwowym programowaniu obiektowym (typy struktur stosu) stosu wywołań w czasie wykonywania.
- Subroutine Container Environment - Niektóre języki programowania (takie jak Pascal i Ada ) obsługują zagnieżdżone podprogramy , umożliwiając wewnętrznej procedurze dostęp do kontekstu jej procedury kontenera, to znaczy do parametrów i zmiennych lokalnych w środowisku procedury zewnętrznej. Takie języki na ogół pozwalają procedurom na wykonywanie wywołań rekurencyjnych (sam wywołania funkcji), co skutkuje wieloma stosami wywołań dla rutynowych wywołań procedur wewnętrznych, z których każde wskazuje na to samo środowisko co procedura zewnętrzna. Ten typ ramki wywołania jest również znany jako wyświetlacz .
