Metody realizacji języków programowania/MRJP Ćwiczenia 9: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
(Nie pokazano 3 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 1: Linia 1:
autor: Marcin Kowalczyk (qrczak@mimuw.edu.pl)
+
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 Pythona działa na zasadzie:
+
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 &amp; sweep?
 
# mark &amp; sweep?
 
# odśmiecania kopiującego?
 
# 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 &amp; 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.

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:

  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.