Ноу Інти, лекція, управління пам’яттю

Прибирання сміття

Найбільш загальною і повністю задовільною технікою є лише автоматичне прибирання сміття або просто збірка сміття.

Механізм складання сміття

Збирач сміття (garbage collector) - це функція виконавчої системи (runtime system) мови програмування. Складальник сміття виконує виявлення і утилізацію недосяжних об'єктів, не потребуючи в управлінні додатком, хоча додаток може мати в своєму розпорядженні різні засоби контролю роботи збирача.

Детальний розгляд усіх проблем збірки сміття вимагає окремої книги. (В кінці лекції наведено бібліографію з цієї проблеми.) Розглянемо загальні принципи і виникають проблеми, концентруючи увагу на властивостях, важливих для розробників програм.

Вимоги до збирачеві сміття

Збирач сміття, безсумнівно, повинен бути коректним, задовольняючи двом вимогам:

Властивості збирача сміття

Якісність. кожен збирається об'єкт повинен бути недосяжним.

Повнота. кожен недосяжний об'єкт повинен бути зібраний.

Якісність - абсолютна вимога: краще не збирати сміття, ніж викидати потрібний об'єкт. Потрібна повна впевненість в тому, що управління пам'яттю можна сліпо довіряти. Фактично треба забути про нього майже назавжди, будучи впевненим, що хтось якось прибирає безлад у вашій програмі, також як хтось якось прибирає сміття у вашому офісі, коли вас немає, але не прибирає при цьому ваші книги, комп'ютер і сімейні фотографії зі столу.

Повнота бажана - без неї все одно можна зіткнутися з проблемою, яку збирач сміття повинен вирішити: пам'ять витрачається на непотрібні об'єкти. Але тут можна не вимагати бездоганності: збирач може бути корисним, якщо він збирає основну частину сміття, іноді пропускаючи один або два об'єкти.

Це зауваження вимагає деталізації. На практиці будь-складальник промислового масштабу повинен володіти повнотою. Повнота на практиці також необхідна, як якісність, але менш жорстка, якщо перефразувати її визначення: "кожен недосяжний об'єкт повинен бути, в кінці кінців, зібраний". Припустимо, що ми можемо зробити процес складання більш ефективним, завдяки алгоритму, який збирає кожен недосяжний об'єкт, але може запізнитися зі зверненням до деяких з них: така схема буде прийнятною для більшості додатків. У цьому ідея обговорюваного далі алгоритму "збірки сміття поколінь", який з метою ефективності частіше сканує області пам'яті, що містять з більшою ймовірністю недосяжні об'єкти, і рідше звертає увагу на інші ділянки пам'яті.

При такому компромісному підході для збирача сміття необхідно буде ввести не тільки бінарні критерії повноти і якісність, а й критерій, званий своєчасність (timeliness). Його значенням є інтервал часу від моменту, коли об'єкт стає недосяжним, до моменту його утилізації, причому важливо як середнє значення часу, так і верхня його межа.

Визначення якісність висвічує труднощі, пов'язані зі складанням сміття для деяких мов програмування, і відповідні ролі мови і його реалізації. Чому, наприклад, прибирання сміття зазвичай застосовується для С ++? Зазвичай наводяться причини пов'язані з культурою: в світі З кожен розробник повинен сам піклуватися про своїх "іграшках" (за словами Стефенсона); він просто не довіряє якомусь автоматичного механізму управляти його справами. Але, якби це було справжньою причиною, а не апостеріорного виправданням, середовища С ++ могли б, як мінімум, запропонувати збірку сміття як підключається можливість, але більшість реалізацій цього не роблять.

Дійсна проблема лежить в структурі мови, а не в технології компіляції або культурних традиціях. Мова С ++, слідуючи С, слабо типізований; він надає можливість перетворення типу, завдяки якій на об'єкт одного типу можна посилатися як на сутність іншого типу. конструкція:

Для вирішення цієї проблеми пропонувалися різні методи. Широкого застосування вони не отримали з-за накладаються обмежень. Мова Java може розглядатися як мову сімейства C ++, в якому запроваджено суттєві обмеження на систему типів, аж до видалення множинного спадкоємства і універсалізації, щоб зробити, нарешті, можливої ​​збірку сміття в світі програм, заснованих на С.

При ретельно спроектованій системі типів, звичайно, можна поєднувати міць множинного спадкоємства і універсалізації з безпекою типів і підтримкою ефективної збірки сміття.

Основа збірки сміття

Розглянемо роботу збирача сміття.

Як і у випадку з підрахунком посилань, об'єкти включають додаткове поле, яке використовується тут для позначки. Але необхідна для цього поля пам'ять незначна, - досить одного біта для кожного об'єкта. Як буде видно при вивченні динамічного зв'язування, реалізація ГО-можливостей вимагає, щоб об'єкт мав додаткову внутрішню інформацію (наприклад, тип). Ця інформація зазвичай займає одне або два слова в кожному об'єкті. Біт позначки може бути частиною службового слова, і не буде займати додаткову пам'ять.

Збірка за принципом "все-або-нічого"

Коли потрібно приводити в дію збирач сміття?

Класичні збирачі сміття активізуються на вимогу і працюють до завершення. Іншими словами, збирач сміття не працює, поки залишається пам'ять для роботи програми. Як тільки її не вистачає, додаток запускає повний цикл збірки сміття - фаза позначки і слідом фаза чистки.

Ця техніка може бути названа "все-або-нічого". Перевага її в тому, що вона не викликає перевантаження поки досить пам'яті. Коли програма виходить за межі досяжних ресурсів, в покарання викликається збирач сміття.

Для пакетних додатків така схема ще може бути прийнятна. Але і тут при високому коефіцієнті відносини віртуальної пам'яті до реальної перевантаження може стати причиною серйозної втрати продуктивності, якщо система створює велике число об'єктів, лише мала частина з яких є в кожен момент досяжними.

Прибирання сміття за принципом "все-або-нічого" не працюватиме для інтерактивних систем або систем реального часу. Уявімо систему виявлення ракетного нападу, яка має 50-мілісекунди інтервал для реагування на запуск ракети. Припустимо, програма прекрасно працювала, поки система не вийшла за межі пам'яті, але, на жаль ця подія відбулася в момент запуску ракети, коли замість системи почав свою роботу неспішний збирач сміття.

У таких випадках проблема полягає не в глобальному ефекті тимчасових втрат, пов'язаних зі складанням сміття: певна втрата продуктивності може бути цілком допустимою для розробників і користувачів, як плата за надійність і зручність, що надається автоматичної складанням сміття. Але тимчасові втрати повинні бути рівномірно розподілені. Неприйнятні непередбачувані сплески активності збирача сміття. Краще черепаха, ніж заєць, час від часу без попередження засипає на півгодини. Підрахунок посилань, якби не його фатальний порок, задовольняв би гаслу: "краще їхати повільно, але з постійною швидкістю, ніж швидко, але з несподіваними і непередбачуваними зупинками".

Звичайно, тимчасові втрати повинні бути не тільки постійними, а й невеликими. Якщо додаток без збирача сміття - заєць, ніхто не погодиться замінити його черепахою. Хороший збирач сміття повинен забезпечувати затримку, що не перевищує 5-15%. Хоча деякі скажуть, що і це неприйнятно, я знаю зовсім небагато додатків, яким потрібні менші витрати. Необхідно враховувати також, що у відсутності збирача сміття потрібно ручна утилізація, також не обходиться без витрат. Незважаючи на всі негативні наслідки, прибирання сміття необхідна.

В ході обговорення виявлені дві додаткові проблеми ефективності роботи збирача сміття: продуктивність глобальна (overall performance) і в стартстопном режимі (incrementality).

Високий рівень (Advanced) підхід до складання сміття

Хороший складальник повинен забезпечувати хорошу продуктивність, працюючи як постійно, так і в стартстопном режимі, стаючи прийнятним для інтерактивних додатків і навіть для систем реального часу.

Звідси перша вимога - необхідно дати можливість розробникам керувати запуском і вимиканням циклів роботи збирача. Зокрема, бібліотеки повинні надавати процедури:

Виклик першої припиняє циклічну роботу по збірці сміття до особливого розпорядження; другий - включає складальник, відновлюючи нормальний стан роботи; третій - змушує складальник негайно виконати повний цикл роботи. Нехай деяка система містить критичний за часом виконання розділ, в якому не повинно бути ніяких непередбачуваних тимчасових затримок. В цьому випадку розробник може викликати collection_off на початку цього розділу і collection_on в його кінці; в будь-якій точці, де додаток працює вхолосту (наприклад, під час введення або виведення), можна запустити collect_now.

Практична реалізація збірки сміття поколінь має багато варіацій. Зокрема, зазвичай ділять об'єкти не тільки на молоді і старі, але на більше число поколінь з різними стратегіями збірки сміття різних поколінь.

Алгоритми паралельної збірки сміття

Для отримання повного рішення проблеми роботи в стартстопном режимі вкрай привабливо виділити збирачеві сміття окремий потік виконання, звичайно, за умови підтримки багатозадачності операційною системою. Цей прийом відомий, як прибирання сміття "на льоту" (on-the fly) або паралельна.

Під час складання сміття на льоту виконання ГО-системи використовує два окремих потоку (часто відповідають двом окремим процесам операційної системи): додаток і збирач. Тільки додаток виділяє пам'ять об'єктів за допомогою інструкцій створення; тільки збирач звільняє пам'ять за допомогою reclaim операцій.

Складальник буде працювати безперервно, повторюючи фазу позначки і слідом фазу чистки для виявлення і видалення недосяжних об'єктів.

Окремі потоки не обов'язково повинні бути окремими процесами. Вони можуть бути, щоб уникнути додаткових витрат на переключення між процесами або навіть потоками, плоскими співпрограмами. (Детальніше співпрограми будуть розглянуті в лекції 12 курсу "Основи об'єктно-орієнтованого проектування", що розглядає "паралелізм")

Навіть за цих умов прибирання сміття на льоту на практиці має незадовільну повну продуктивність. Це сумно, оскільки сам метод досить хороший, особливо за умови використання алгоритму Дейкстри (див. Бібліографічне посилання).

Ця ідея вимагає зміни домінуючої апаратної архітектури і, ймовірно, навряд чи знайде швидке застосування. Я сподіваюся, що відповіддю на іноді задається питання -

"Який тип апаратного забезпечення найбільш придатний для об'єктної технології?" -

першим пунктом у списку побажань буде наявність окремого процесора для збору сміття.