Czy można statycznie przewidzieć, kiedy należy zwolnić pamięć --- tylko z kodu źródłowego?


27

Pamięć (i blokady zasobów) są zwracane do systemu operacyjnego w deterministycznych punktach podczas wykonywania programu. Przepływ sterujący programu sam w sobie wystarczy, aby wiedzieć, gdzie z pewnością dany zasób może zostać zwolniony. Dokładnie tak, jak ludzki programista wie, gdzie pisać, fclose(file)gdy program z nim skończy.

GC rozwiązują ten problem, ustalając go bezpośrednio w czasie wykonywania, gdy wykonywany jest przepływ sterowania. Ale prawdziwym źródłem prawdy o przepływie kontroli jest źródło. Teoretycznie powinno być możliwe określenie, gdzie wstawić free()wywołania przed kompilacją, poprzez analizę źródła (lub AST).

Liczenie referencji jest oczywistym sposobem na zaimplementowanie tego, ale łatwo jest napotkać sytuacje, w których wskaźniki są nadal przywoływane (nadal w zakresie), ale nie są już potrzebne. To po prostu przekształca odpowiedzialność za ręczne zwolnienie wskaźników na odpowiedzialność za ręczne zarządzanie zakresem / referencjami do tych wskaźników.

Wygląda na to, że można napisać program, który potrafi odczytać źródło programu i:

  1. przewidzieć wszystkie permutacje przepływu sterowania programem --- z podobną dokładnością jak oglądanie wykonywania programu na żywo
  2. śledź wszystkie odniesienia do przydzielonych zasobów
  3. dla każdego odniesienia przejrzyj cały kolejny przepływ sterowania, aby znaleźć najwcześniejszy punkt, w którym odniesienie gwarantuje, że nigdy nie zostanie oderwane
  4. w tym momencie wstaw instrukcję dealokacji w tym wierszu kodu źródłowego

Czy jest coś, co już to robi? Nie sądzę, aby inteligentne wskaźniki / RAII w Rust lub C ++ były tym samym.


57
sprawdź problem zatrzymania. To dziadek, dlaczego pytanie „Czy kompilator nie może ustalić, czy program obsługuje X?” zawsze odpowiada „Nie w ogólnym przypadku”.
maniak zapadkowy

18
Pamięć (i blokady zasobów) są zwracane do systemu operacyjnego w deterministycznych punktach podczas wykonywania programu. Nie.
Euforyczny

9
@ratchetfreak Dzięki, nigdy nie zdaje sobie sprawy z takich rzeczy jak ten problem z zatrzymaniem, który sprawia, że ​​żałuję, że nie mam chemii.
zelcon,

15
@ zelcon5, teraz wiesz o chemii i problemie zatrzymania ... :)
David Arno,

7
@Euforia, chyba że ustrukturyzujesz swój program, więc granice wykorzystania zasobu są bardzo wyraźne, jak w przypadku RAII lub try-with-resources
maniak ratchet

Odpowiedzi:


23

Weź ten (wymyślony) przykład:

void* resource1;
void* resource2;

while(true){

    int input = getInputFromUser();

    switch(input){
        case 1: resource1 = malloc(500); break;
        case 2: resource2 = resource1; break;
        case 3: useResource(resource1); useResource(resource2); break;
    }
}

Kiedy należy zadzwonić za darmo? przed malloc i przypisaniem do resource1nie możemy, ponieważ może zostać skopiowane resource2, przed przypisaniem do resource2nie możemy, ponieważ mogliśmy otrzymać 2 od użytkownika dwa razy bez interwencji 1.

Jedynym sposobem, aby się upewnić, jest przetestowanie zasobu 1 i zasobu 2, aby sprawdzić, czy nie są one równe w przypadkach 1 i 2, i zwolnienie starej wartości, jeśli nie były. Zasadniczo jest to liczenie referencji, jeśli wiesz, że istnieją tylko 2 możliwe referencje.


W rzeczywistości to nie jedyny sposób; innym sposobem jest zezwolenie na istnienie tylko jednej kopii. To oczywiście wiąże się z własnymi problemami.
Jack Aidley,

27

RAII nie jest automatycznie tym samym, ale ma ten sam efekt. Zapewnia łatwą odpowiedź na pytanie „skąd wiesz, kiedy nie można już uzyskać do niego dostępu?” przez użycie zasięgu do objęcia obszaru, gdy używany jest określony zasób.

Być może warto rozważyć podobny problem: „skąd mam wiedzieć, że w moim programie nie wystąpi błąd typu?”. Rozwiązaniem tego problemu nie jest przewidywanie wszystkich ścieżek wykonania w programie, ale użycie systemu adnotacji i wnioskowania typu, aby udowodnić, że nie może być takiego błędu. Rust jest próbą rozszerzenia tej właściwości dowodu na przydział pamięci.

Możliwe jest pisanie dowodów na zachowanie programu bez konieczności rozwiązywania problemu zatrzymania, ale tylko wtedy, gdy używasz pewnego rodzaju adnotacji, aby ograniczyć program. Zobacz także dowody bezpieczeństwa (sel4 itp.)


Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
maple_shaft

13

Tak, istnieje na wolności. ML Kit to kompilator jakości produkcyjnej, który ma opisaną strategię (mniej więcej) jako jedną z dostępnych opcji zarządzania pamięcią. Pozwala także na użycie konwencjonalnego GC lub hybrydyzację z liczeniem referencji (możesz użyć profilera sterty, aby zobaczyć, która strategia rzeczywiście przyniesie najlepsze wyniki dla twojego programu).

Retrospektywa na temat zarządzania pamięcią opartą na regionie jest artykułem oryginalnych autorów zestawu ML Kit, który opisuje jego sukcesy i porażki. Ostateczny wniosek jest taki, że strategia jest praktyczna, gdy pisze się z pomocą profilera sterty.

(Jest to dobra ilustracja tego, dlaczego zwykle nie powinieneś szukać problemu zatrzymania w poszukiwaniu odpowiedzi na praktyczne pytania inżynierskie: nie chcemy ani nie musimy rozwiązywać ogólnego przypadku najbardziej realistycznych programów).


5
Myślę, że jest to doskonały przykład prawidłowego zastosowania problemu zatrzymania. Problem zatrzymania mówi nam, że problem jest nierozwiązywalny w ogólnym przypadku, więc szukasz ograniczonych scenariuszy, w których problem można rozwiązać.
Taemyr

Zauważ, że problem staje się o wiele bardziej rozwiązywalny, gdy mówimy o czystych lub prawie czystych funkcjonalnych, niepowodujących efektów ubocznych językach, takich jak Standard ML i Haskell
cat

10

przewidzieć wszystkie permutacje przepływu sterującego programu

Na tym polega problem. Ilość permutacji jest tak ogromna (w praktyce jest nieskończona) dla każdego nietrywialnego programu, że potrzebny czas i pamięć uczynią to całkowicie niepraktycznym.


Słuszna uwaga. Myślę, że procesory kwantowe są jedyną nadzieją, jeśli w ogóle
istnieje

4
@ zelcon5 Haha, no. Obliczenia kwantowe pogarszają , a nie poprawiają. Dodaje dodatkowe („ukryte”) zmienne do programu i znacznie więcej niepewności. Najbardziej praktyczny kod QC, jaki widziałem, opiera się na „kwantie do szybkich obliczeń, klasycznym dla potwierdzenia”. Sam ledwo zarysowałem powierzchnię obliczeń kwantowych, ale wydaje mi się, że komputery kwantowe mogą nie być bardzo przydatne bez klasycznych komputerów do ich tworzenia kopii zapasowych i sprawdzania ich wyników.
Luaan,

8

Problem zatrzymania pokazuje, że nie jest to możliwe we wszystkich przypadkach. Jest to jednak nadal możliwe w bardzo wielu przypadkach, a właściwie jest to wykonywane przez prawie wszystkie kompilatory dla prawdopodobnie większości zmiennych. W ten sposób kompilator może powiedzieć, że bezpiecznie jest po prostu przypisać zmienną do stosu lub nawet rejestru, zamiast do długoterminowego przechowywania na stosie.

Jeśli masz czyste funkcje lub naprawdę dobrą semantykę własności, możesz jeszcze bardziej rozszerzyć tę analizę statyczną, chociaż jest to zbyt kosztowne, ponieważ więcej gałęzi zajmuje Twój kod.


Kompilator uważa, że może zwolnić pamięć; ale może tak nie być. Pomyśl o typowym błędzie początkującego, aby zwrócić wskaźnik lub odwołanie do zmiennej lokalnej. Trywialne przypadki są wychwytywane przez kompilator, prawda; te mniej trywialne nie są.
Peter - przywróć Monikę

Ten błąd popełniają programiści w językach, w których programiści muszą ręcznie zarządzać alokacją pamięci @Peter. Gdy kompilator zarządza przydziałem pamięci, tego rodzaju błędy się nie zdarzają.
Karl Bielefeldt,

Cóż, napisałeś bardzo ogólne stwierdzenie, w tym zwrot „prawie wszystkie kompilatory”, które muszą zawierać kompilatory C.
Peter - przywróć Monikę

2
Kompilatory C używają go do określania, jakie zmienne tymczasowe można przypisać do rejestrów.
Karl Bielefeldt,

4

Jeśli jeden programista lub zespół pisze cały program, uzasadnione jest zidentyfikowanie punktów projektowych, w których należy zwolnić pamięć (i inne zasoby). Tak więc, statyczna analiza projektu może być wystarczająca w bardziej ograniczonych kontekstach.

Jeśli jednak weźmiesz pod uwagę biblioteki DLL, interfejsy API, frameworki (i wrzucisz także wątki) innych firm, może to być bardzo trudne (nie, niemożliwe we wszystkich przypadkach), aby programiści używający oprogramowania poprawnie uzasadnili, która jednostka jest właścicielem jakiej pamięci i kiedy jest to ostatnie użycie. Nasi zwykli podejrzani o języki w niewystarczającym stopniu dokumentują przeniesienie własności pamięci obiektów i tablic, płytkich i głębokich. Jeśli programista nie może tego uzasadnić (statycznie lub dynamicznie!), Kompilator najprawdopodobniej nie może tego zrobić. Ponownie wynika to z faktu, że przeniesienia własności pamięci nie są przechwytywane w wywołaniach metod lub interfejsach itp., Więc nie można statystycznie przewidzieć, kiedy i gdzie w kodzie zwolnić pamięć.

Ponieważ jest to tak poważny problem, wiele współczesnych języków wybiera zbieranie śmieci, które automatycznie odzyskuje pamięć jakiś czas po ostatnim odwołaniu na żywo. GC ma znaczny koszt wydajności (szczególnie dla aplikacji w czasie rzeczywistym), jednak nie jest to uniwersalne lekarstwo na wszystko. Co więcej, nadal możesz mieć wycieki pamięci za pomocą GC (np. Kolekcja, która rośnie tylko). Mimo to jest to dobre rozwiązanie dla większości ćwiczeń programistycznych.

Istnieje kilka alternatyw (niektóre pojawiają się).

Język Rust prowadzi ekstremalnie RAII. Zapewnia konstrukcje językowe, które bardziej szczegółowo definiują przeniesienie własności w metodach klas i interfejsów, np. Obiekty są przenoszone na kontra pożyczane między dzwoniącym a odbiorcą lub w obiektach o dłuższym okresie życia. Zapewnia wysoki poziom bezpieczeństwa czasu kompilacji w kierunku zarządzania pamięcią. Jednak nie jest to trywialny język do wychwycenia i nie jest też pozbawiony problemów (np. Nie sądzę, aby projekt był w pełni stabilny, pewne rzeczy wciąż są eksperymentowane, a tym samym zmieniane).

Swift i Objective-C idą jeszcze inną drogą, którą jest w większości automatyczne liczenie referencji. Zliczanie referencji powoduje problemy z cyklami i istnieją poważne wyzwania dla programistów, na przykład szczególnie przy zamknięciach.


3
Jasne, GC ma koszty, ale ma również zalety w zakresie wydajności. Na przykład w .NET alokacja ze sterty jest prawie bezpłatna, ponieważ wykorzystuje wzorzec „alokacji stosu” - wystarczy zwiększyć wskaźnik i to wszystko. Widziałem aplikacje, które działają szybciej przepisywane wokół .NET GC niż korzystały z ręcznego przydzielania pamięci, to naprawdę nie jest jasne. Podobnie, liczenie referencji jest w rzeczywistości dość drogie (tylko w innych miejscach niż GC) i coś, czego nie chcesz płacić, jeśli możesz tego uniknąć. Jeśli chcesz wydajności w czasie rzeczywistym, statyczny przydział jest często jedynym sposobem.
Luaan,

2

Jeśli program nie zależy od nieznanych danych wejściowych, to tak, powinno być to możliwe (z zastrzeżeniem, że może to być złożone zadanie i może potrwać długo; ale byłoby to prawdą również dla programu). Takie programy byłyby całkowicie rozwiązywalne w czasie kompilacji; w kategoriach C ++ mogą (prawie) całkowicie składać się z constexprs. Prostym przykładem byłoby obliczenie pierwszych 100 cyfr liczby pi lub posortowanie znanego słownika.


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.