Metody realizacji języków programowania/MRJP Ćwiczenia 9: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| (Nie pokazano 2 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
| Linia 1: | Linia 1: | ||
Autor: Marcin Kowalczyk (qrczak@mimuw.edu.pl) | |||
==Zadanie 1== | ==Zadanie 1== | ||
Rozważmy następujący fragment programu w Pythonie: | Rozważmy następujący fragment programu (w Pythonie): | ||
class N: | '''class''' N: | ||
def __init__(self, name, children): | '''def''' __init__(self, name, children): | ||
self.name = name | self.name = name | ||
self.children = children | self.children = children | ||
| Linia 16: | Linia 16: | ||
a = b = c = d = None | a = b = c = d = None | ||
Które obiekty spośród obiektów <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code> 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 | Które obiekty spośród obiektów <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code> 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: | ||
# zliczania odwołań? | # zliczania odwołań? | ||
# mark & sweep? | # mark & sweep? | ||
Aktualna wersja na dzień 23:39, 1 paź 2006
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:
- zliczania odwołań?
- mark & sweep?
- 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:
- Mark & sweep ze stertą ustalonej wielkości.
- 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:
- dąży do 0%?
- dąży do jakiejś wielkości między 0% a 100%?
- 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.
