Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
| Ця стаття не містить . (травень 2018) |
Купа (англ. heap) в інформатиці та програмуванні — назва структури даних, за допомогою якої реалізовано динамічно розподілювану пам'ять програми.
Розмір купи — розмір пам'яті, виділеної операційною системою (ОС) для зберігання купи (під купу).
Принцип роботи
При запуску процесу ОС виділяє пам'ять для розміщення купи. Надалі пам'ять для купи (під купу) може виділятися динамічно.
Програма користувача, використовуючи функції, подібні malloc()може отримувати покажчики на області пам'яті, що належать купі. Програми використовують купу для розміщення динамічно створюваних структур даних. Програма може звільнити пам'ять з допомогою функцій, подібних free().
Пам'ять купи можна розділити на зайняту (виділену програмі за допомогою функцій, подібних malloc()) і вільну (зайняту або вже звільнену з допомогою функцій, подібних free()).
Для зберігання даних про те, яка ділянка купи є зайнятою, а яка — вільною, зазвичай використовується додаткова область пам'яті.
Перед початком роботи програми виконується ініціалізація купи, в ході якої пам'ять, виділена під купу, позначається як вільна.
Функція, подібна malloc() виконує приблизно такі дії:
- переглядає список зайнятих/вільних областей пам'яті, розміщених в купі, в пошуках вільної області відповідного розміру;
- у разі нестачі вільної пам'яті може запитати додаткову пам'ять у ОС;
- додає знайдену область в список зайнятих областей (або позначає область як зайняту);
- повертає покажчик на початок області пам'яті;
- якщо з тих чи інших причин виділити пам'ять не вдалося, повідомляє про помилку (наприклад,
malloc()повертаєNULL).
Функція, подібна free()виконує приблизно такі дії:
- переглядає список зайнятих/вільних областей пам'яті, розміщених в купі, в пошуках зазначеної області;
- видаляє зі списку зайнятих областей пам'яті знайдену область
- додає знайдену область в список вільних областей (або позначає область як вільну).
Програма може бути впевнена в тому, що між викликами функцій, подібних malloc() і free()область пам'яті, позначена як зайнята, не буде виділена повторно. Після виклику функції, подібної free()область пам'яті буде звільнена і надалі може використовуватися повторно або може бути віддана ОС. Використання вказівника на звільнену область пам'яті буде приводити до збоїв або непередбачуваної роботи програми.
Алгоритми і продуктивність
Купа являє собою безперервну область пам'яті, поділену на зайняті і вільні області (блоки) різного розміру.
Інформація про вільні і зайняті області купи може зберігатися в списках різних форматів. Від обраного формату списку безпосередньо залежить продуктивність функцій, подібних malloc() і free(), так як більшу частину часу ці функції витрачають на пошук за списком відповідних областей.
Для збільшення розміру купи функція, подібна malloc()використовує системний виклик (викликає функцію ОС). При цьому відбувається перемикання контексту з в простір ядра ОС і назад. Пошук за списком зайнятих/вільних областей купи виконується швидше, ніж перемикання контекстів, тому вигідніше один раз використовувати системний виклик для виділення великої області пам'яті під купу, а надалі виділяти програмі області меншого розміру з наявної великої області з веденням списку зайнятих/вільних областей.
Кількість елементів, що входять в список зайнятих/вільних областей купи, може бути зменшено шляхом злиття елементів, що містять інформацію про наступні одну за іншою областях. Це дозволить зменшити час обходу списку.
Кожен елемент списку може зберігати адресу області пам'яті, її розмір, інформацію про наступну (для пошуку в прямому напрямку) і/або попередньої (для пошуку в зворотному напрямку) області.
Приклад реалізації
Створення декількох списків для зберігання інформації про областях однакових або близьких розмірів. Вибір списку в залежності від розміру області.
Дивись також
- Функції стандартної бібліотеки мови C
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno traven 2018 Kupa angl heap v informatici ta programuvanni nazva strukturi danih za dopomogoyu yakoyi realizovano dinamichno rozpodilyuvanu pam yat programi Rozmir kupi rozmir pam yati vidilenoyi operacijnoyu sistemoyu OS dlya zberigannya kupi pid kupu Princip robotiPri zapusku procesu OS vidilyaye pam yat dlya rozmishennya kupi Nadali pam yat dlya kupi pid kupu mozhe vidilyatisya dinamichno Programa koristuvacha vikoristovuyuchi funkciyi podibni span class n malloc span span class p span mozhe otrimuvati pokazhchiki na oblasti pam yati sho nalezhat kupi Programi vikoristovuyut kupu dlya rozmishennya dinamichno stvoryuvanih struktur danih Programa mozhe zvilniti pam yat z dopomogoyu funkcij podibnih span class n free span span class p span Pam yat kupi mozhna rozdiliti na zajnyatu vidilenu programi za dopomogoyu funkcij podibnih span class n malloc span span class p span i vilnu zajnyatu abo vzhe zvilnenu z dopomogoyu funkcij podibnih span class n free span span class p span Dlya zberigannya danih pro te yaka dilyanka kupi ye zajnyatoyu a yaka vilnoyu zazvichaj vikoristovuyetsya dodatkova oblast pam yati Pered pochatkom roboti programi vikonuyetsya inicializaciya kupi v hodi yakoyi pam yat vidilena pid kupu poznachayetsya yak vilna Funkciya podibna span class n malloc span span class p span vikonuye priblizno taki diyi pereglyadaye spisok zajnyatih vilnih oblastej pam yati rozmishenih v kupi v poshukah vilnoyi oblasti vidpovidnogo rozmiru u razi nestachi vilnoyi pam yati mozhe zapitati dodatkovu pam yat u OS dodaye znajdenu oblast v spisok zajnyatih oblastej abo poznachaye oblast yak zajnyatu povertaye pokazhchik na pochatok oblasti pam yati yaksho z tih chi inshih prichin vidiliti pam yat ne vdalosya povidomlyaye pro pomilku napriklad span class n malloc span span class p span povertaye span class nb NULL span Funkciya podibna span class n free span span class p span vikonuye priblizno taki diyi pereglyadaye spisok zajnyatih vilnih oblastej pam yati rozmishenih v kupi v poshukah zaznachenoyi oblasti vidalyaye zi spisku zajnyatih oblastej pam yati znajdenu oblast dodaye znajdenu oblast v spisok vilnih oblastej abo poznachaye oblast yak vilnu Programa mozhe buti vpevnena v tomu sho mizh viklikami funkcij podibnih span class n malloc span span class p span i span class n free span span class p span oblast pam yati poznachena yak zajnyata ne bude vidilena povtorno Pislya vikliku funkciyi podibnoyi span class n free span span class p span oblast pam yati bude zvilnena i nadali mozhe vikoristovuvatisya povtorno abo mozhe buti viddana OS Vikoristannya vkazivnika na zvilnenu oblast pam yati bude privoditi do zboyiv abo neperedbachuvanoyi roboti programi Algoritmi i produktivnistKupa yavlyaye soboyu bezperervnu oblast pam yati podilenu na zajnyati i vilni oblasti bloki riznogo rozmiru Informaciya pro vilni i zajnyati oblasti kupi mozhe zberigatisya v spiskah riznih formativ Vid obranogo formatu spisku bezposeredno zalezhit produktivnist funkcij podibnih span class n malloc span span class p span i span class n free span span class p span tak yak bilshu chastinu chasu ci funkciyi vitrachayut na poshuk za spiskom vidpovidnih oblastej Dlya zbilshennya rozmiru kupi funkciya podibna span class n malloc span span class p span vikoristovuye sistemnij viklik viklikaye funkciyu OS Pri comu vidbuvayetsya peremikannya kontekstu z v prostir yadra OS i nazad Poshuk za spiskom zajnyatih vilnih oblastej kupi vikonuyetsya shvidshe nizh peremikannya kontekstiv tomu vigidnishe odin raz vikoristovuvati sistemnij viklik dlya vidilennya velikoyi oblasti pam yati pid kupu a nadali vidilyati programi oblasti menshogo rozmiru z nayavnoyi velikoyi oblasti z vedennyam spisku zajnyatih vilnih oblastej Kilkist elementiv sho vhodyat v spisok zajnyatih vilnih oblastej kupi mozhe buti zmensheno shlyahom zlittya elementiv sho mistyat informaciyu pro nastupni odnu za inshoyu oblastyah Ce dozvolit zmenshiti chas obhodu spisku Kozhen element spisku mozhe zberigati adresu oblasti pam yati yiyi rozmir informaciyu pro nastupnu dlya poshuku v pryamomu napryamku i abo poperednoyi dlya poshuku v zvorotnomu napryamku oblasti Priklad realizaciyiStvorennya dekilkoh spiskiv dlya zberigannya informaciyi pro oblastyah odnakovih abo blizkih rozmiriv Vibir spisku v zalezhnosti vid rozmiru oblasti Divis takozhDinamichna pam yat NULL Funkciyi standartnoyi biblioteki movi C malloc