1 of 32

Reference Counting

2 of 32

Garbage Collection

Автоматично събиране на динамично заделена памет.

​

3 of 32

Някои основни понятия

  • GC граф - ориентиран граф
  • Връх / клетка / обект
  • Корен (root)
  • Достижимост на връх в графа
  • Боклук (garbage) - недостижим обект, чиято паметта не е освободена

4 of 32

Основни алгоритми за garbage collection

  • Reference counting
  • Копиращ алгоритъм
  • Mark and sweep

5 of 32

Reference Counting (Collins, 1960)

“A method for overlapping and erasure of lists”, George E. Collins, 1960

6 of 32

Копиращ алгоритъм (C.J. Cheney, 1970)

  • Stop and copy, Copying collection

​

7 of 32

Копиращ алгоритъм (C.J. Cheney, 1970)

  • Stop and copy, Copying collection

​

8 of 32

Копиращ алгоритъм (C.J. Cheney, 1970)

  • Stop and copy, Copying collection

​

9 of 32

Mark and Sweep (Steele 1975 and Dijkstra 1978)

10 of 32

Mark and Sweep (Steele 1975 and Dijkstra 1978)

​

11 of 32

Предимства при използването на Reference Counting

  • Лесна имплементация
  • Директно освобождаване на неизползвана вече памет
  • Локалност на връзките
  • В общия случай не предполага продължително спиране на програмата за събирането на неизползвана вече памет*

12 of 32

Предимства при използването на Reference Counting

  • Лесна имплементация
  • Директно освобождаване на неизползвана вече памет
  • Локалност на връзките
  • В общия случай не предполага продължително спиране на програмата за събирането на неизползвана вече памет*

13 of 32

Недостатъци на Reference Counting

  • Допълнително памет за броене на връзките
  • Неумение да се справя с цикли

14 of 32

Циклични връзки

15 of 32

Циклични връзки

16 of 32

Циклични връзки

  • “Reference counting does not reclaim cycles”, J. H. McBeth, 1963
  • Coherent Labs, към края на 2021 😄

17 of 32

Външни и вътрешни за цикъла връзки

“Reference counting can manage the circular environments of mutual recursion”, Friedman and Wise, 1978

​

18 of 32

Външни и вътрешни за цикъла връзки

“Reference counting can manage the circular environments of mutual recursion”, Friedman and Wise, 1978

​

19 of 32

Външни и вътрешни за цикъла връзки

“Reference counting can manage the circular environments of mutual recursion”, Friedman and Wise, 1978

​

20 of 32

Външни и вътрешни за цикъла връзки

“Managing Reentrant Structures Using Reference Counts” Daniel G. Bobrow, 1980

21 of 32

Външни и вътрешни за цикъла връзки

“Managing Reentrant Structures Using Reference Counts” Daniel G. Bobrow, 1980

22 of 32

Външни и вътрешни за цикъла връзки

“Managing Reentrant Structures Using Reference Counts” Daniel G. Bobrow, 1980

23 of 32

Външни и вътрешни за цикъла връзки

“Managing Reentrant Structures Using Reference Counts” Daniel G. Bobrow, 1980

24 of 32

Алгоритми с използване на слаби връзки (weak pointers)

Инварианти за коректност:

  1. Всеки жив обект трябва да е достижим от някой от корените с път съставен от силни връзки (strong pointers)
  2. Силните връзки не образуват цикли

25 of 32

Алгоритми с използване на слаби връзки (weak pointers)

  • “Cyclic Reference Counting for Combinator Machines” Brownbridge, 1985
  • “Implementation and analysis of two reference counting algorithms” Salkild, 1987
  • “A cyclic reference counting algorithm and its proof” Pepels et al., 1988

26 of 32

Алгоритми с използване на слаби връзки (weak pointers)

  • “Cyclic Reference Counting for Combinator Machines” Brownbridge, 1985
  • “Implementation and analysis of two reference counting algorithms” Salkild, 1987
  • “A cyclic reference counting algorithm and its proof” Pepels et al., 1988

27 of 32

Алгоритми с използване на слаби връзки (weak pointers)

  • “Cyclic Reference Counting for Combinator Machines” Brownbridge, 1985
  • “Implementation and analysis of two reference counting algorithms” Salkild, 1987
  • “A cyclic reference counting algorithm and its proof” Pepels et al., 1988

28 of 32

Алгоритми с използване на слаби връзки (weak pointers)

  • Риск да съберат памет докато още се използва
  • Цена на допълнителни итерации на графа
  • Допълнително памет освен тази, която използваме за RC

29 of 32

Частичен Mark & Sweep

  • Алгоритъм на Кристофър
  • Пълен mark and sweep

​

30 of 32

Частичен Mark & Sweep

  • Алгоритъм на Линс
  • Локален mark and sweep

31 of 32

Още ресурси ако темата ви е интересна

​

​

​

32 of 32

Q&A