Metody realizacji języków programowania/MRJP Ćwiczenia 9

From Studia Informatyczne

Autor: Marcin Kowalczyk (qrczak@mimuw.edu.pl)

Zadanie 1

Rozważmy następujący fragment programu (w Pythonie):

class N:
    def __init__(self, name, children):
        self.name = name
        self.children = children
a = N('a', [])
b = N('b', [a])
c = N('c', [b])
b.children.append(c)
d = N('d', [c])
a = b = c = d = None

Które obiekty spośród obiektów a, b, c, d będą miały zwolnioną pamięć (z punktu widzenia dostępności zajmowanej przez nie wcześniej pamięci dla alokacji innych obiektów tego programu) natychmiast po wykonaniu ostatniej linii, a które w ogóle mają szansę mieć zwolnioną pamięć przed zakończeniem programu, jeśli odśmiecacz użytej implementacji języka działa na zasadzie:

  1. zliczania odwołań?
  2. mark & sweep?
  3. odśmiecania kopiującego?

Zadanie 2

Pewien program alokuje obiekty stałej wielkości w stałym tempie, utrzymując przez cały czas stałą liczbę osiągalnych obiektów. Przyjmujemy idealistyczne założenia, że dostęp do pamięci ma stały koszt niezależnie od ilości używanej pamięci, że niskopoziomowe operacje alokacji i zwalniania pamięci używane przez odśmiecacz mają stały koszt i że pamięci jest dowolnie dużo. Rozważmy dwa algorytmy odśmiecania:

  1. Mark & sweep ze stertą ustalonej wielkości.
  2. Odśmiecanie kopiujące ze stertą ustalonej wielkości.

Jak w obu przypadkach zachowuje się procentowy udział czasu odśmiecania w całkowitym czasie wykonania programu, w miarę jak ustalony rozmiar sterty jest coraz większy:

  1. dąży do 0%?
  2. dąży do jakiejś wielkości między 0% a 100%?
  3. dąży do 100%?

Zadanie 3

Rozmiar wskaźnika na danej architekturze wynosi 32 bity. Konserwatywny odśmiecacz poszukuje wskaźników na początki obiektów w całej zaalokowanej pamięci, rozpatrując tylko wartości umieszczone pod adresami wyrównanymi do wielkości wskaźnika.

Pewien program zaalokował tablicę bajtów wielkości 16 MB, w której umieścił mocno skompresowaną grafikę, oraz jednokierunkową listę długości 16 tysięcy. Tablica bajtów jest osiągalna przez program, natomiast lista przestała być osiągalna. Oszacuj prawdopodobieństwo, że odśmiecacz nie będzie w stanie zwolnić ostatniego elementu listy.