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

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.

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.

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.)

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).

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.

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.

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.

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.

Zwolnienie pamięci jest na ogół równoznaczne z problemem zatrzymania - jeśli nie możesz statycznie stwierdzić, czy program się zatrzyma (statycznie), nie możesz powiedzieć, czy zwolni pamięć (statycznie).

function foo(int a) {
    void *p = malloc(1);
    ... do something which may, or may not, halt ...
    free(p);
}

https://en.wikipedia.org/wiki/Halting_problem

Powiedział, że Rust jest bardzo miły ... https://doc.rust-lang.org/book/ownership.html