Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік алгоритм
Computer algorithm
Бадди жадыны бөлу техникасы – жады сұранысын мүмкіндігінше жақсы қанағаттандыру үшін жадыны бөліктерге бөлетін жадыны бөлу алгоритмі. Бұл жүйе жадыны екіге бөліп, ең тиімді сәйкестікті табуға тырысады. Дональд Кнуттың сөзіне сүйенсек, бадди жүйесін 1963 жылы Гарри Марковиц ойлап тапқан, ал алғаш рет Кеннет К. Ноултон сипаттаған (1965 жылы жарияланған). Бадди жадыны бөлуді іске асыру салыстырмалы түрде оңай. Ол жад блоктарын бөлуге және біріктіруге шектеулі, бірақ тиімді мүмкіндіктер береді.
The buddy memory allocation technique is a memory allocation algorithm that divides memory into partitions to try to satisfy a memory request as suitably as possible. This system makes use of splitting memory into halves to try to give a best fit. According to Donald Knuth, the buddy system was invented in 1963 by Harry Markowitz, and was first described by Kenneth C. Knowlton (published 1965). The Buddy memory allocation is relatively easy to implement. It supports limited but efficient splitting and coalescing of memory blocks.
Алгоритм
Бадди жүйесінің әр түрлі нысандары бар; әр блок екі кіші блокқа бөлінетін түрлері ең қарапайым және кең таралғандары болып табылады. Бұл жүйедегі әрбір жад блогының дәрежесі болады, онда дәреже 0-ден белгілі бір жоғарғы шекке дейінгі бүтін сан. n дәрежелі блоктың көлемі 2n-ге пропорционал, сондықтан блоктар бір дәреже төмен блоктардан екі есе үлкен болады. Екінің дәрежесіндегі блок көлемдері адрестеуді жеңілдетеді, себебі барлық баддилер екінің дәрежесіндегі жад адресі шекараларында тегістеледі. Үлкен блок бөлінген кезде, ол екі кіші блокқа бөлінеді, және әр кіші блок екіншісі үшін бірегей баддиге айналады. Бөлінген блок тек өзінің бірегей бадди блогымен біріктіріле алады, содан кейін олар бұрын бөлінген үлкен блокты қайта құрайды. Бастапқыда ең кіші блок көлемі анықталады, яғни бөлуге болатын ең кішкентай жад блогы. Егер ешқандай төменгі шек болмаса (мысалы, биттік мөлшерде бөлу мүмкін болса), жадтың қай бөліктері бөлінген және қайсысы бөлінбегенін қадағалау үшін жүйеге көп жад және есептеу ресурстары қажет болар еді. Дегенмен, бөліністердің көлемі ең кішкентай блок көлемінің еселігіне сәйкес келмеген жағдайдағы орташа жадты ысырапты азайту үшін, салыстырмалы түрде төменгі шек қажет болуы мүмкін. Әдетте, төменгі шек бір бөлініске шаққандағы орташа ысырапты азайтуға жеткілікті кішкентай, бірақ артық шығындарды болдырмауға жеткілікті үлкен болады. Ең кішкентай блок көлемі 0 дәрежелі блок көлемі ретінде қабылданады, сондықтан барлық жоғары дәрежелер осы көлемнің екінің дәрежесіндегі еселігі ретінде беріледі. Бағдарламашы содан кейін қалған бос жад кеңістігіне сыятын ең жоғары дәрежені анықтау үшін код жазуы керек немесе оны алу үшін код жазылуы тиіс. Белгілі бір компьютер жүйесіндегі жалпы қолжетімді жад ең кішкентай блок көлемінің екінің дәрежесіндегі еселігі болмауы мүмкін болғандықтан, ең үлкен блок көлемі жүйенің барлық жадын қамтымайды. Мысалы, егер жүйеде 2000 К физикалық жад болса және 0 дәрежелі блок көлемі 4 К болса, онда дәреже шегі 8 болады, себебі 8 дәрежелі блок (256 0 дәрежелі блок, 1024 К) жадқа сыятын ең үлкен блок болып табылады. Осылайша, барлық физикалық жадты бір бөлікке бөлу мүмкін емес; қалған 976 К жад кішкентай блоктарда бөлінуі керек.
There are various forms of the buddy system; those in which each block is subdivided into two smaller blocks are the simplest and most common variety. Every memory block in this system has an order, where the order is an integer ranging from 0 to a specified upper limit. The size of a block of order n is proportional to 2n, so that the blocks are exactly twice the size of blocks that are one order lower. Power of two block sizes make address computation simple, because all buddies are aligned on memory address boundaries that are powers of two. When a larger block is split, it is divided into two smaller blocks, and each smaller block becomes a unique buddy to the other. A split block can only be merged with its unique buddy block, which then reforms the larger block they were split from. Starting off, the size of the smallest possible block is determined, i. e. the smallest memory block that can be allocated. If no lower limit existed at all (e. g., bit sized allocations were possible), there would be a lot of memory and computational overhead for the system to keep track of which parts of the memory are allocated and unallocated. However, a rather low limit may be desirable, so that the average memory waste per allocation (concerning allocations that are, in size, not multiples of the smallest block) is minimized. Typically the lower limit would be small enough to minimize the average wasted space per allocation, but large enough to avoid excessive overhead. The smallest block size is then taken as the size of an order 0 block, so that all higher orders are expressed as power of two multiples of this size. The programmer then has to decide on, or to write code to obtain, the highest possible order that can fit in the remaining available memory space. Since the total available memory in a given computer system may not be a power of two multiple of the minimum block size, the largest block size may not span the entire memory of the system. For instance, if the system had 2000 K of physical memory and the order 0 block size was 4 K, the upper limit on the order would be 8, since an order 8 block (256 order 0 blocks, 1024 K) is the biggest block that will fit in memory. Consequently, it is impossible to allocate the entire physical memory in a single chunk; the remaining 976 K of memory would have to be allocated in smaller blocks.
Орындау және тиімділік
Динамикалық бөлу сияқты басқа қарапайым техникалармен салыстырғанда, бадди жад жүйесінде сыртқы фрагментация аз, және жадты аз қосымшы шығынмен жинақтауға мүмкіндік береді. Жадты босатудың бадди әдісі жылдам, қажетті жинақтаулардың максималды саны O(ең жоғары рет) = O(log2(жалпы жад көлемі))-не тең. Әдетте, бадди жадты бөлу жүйесі пайдаланылған немесе бос бөлінген жад блоктарын көрсету үшін екілік ағаш пайдалану арқылы іске асырылады. Блоктың "баддисінің" адресі – блок адресі мен блок көлемінің биттік эксклюзивті НЕ (XOR) операциясының нәтижесіне тең. Дегенмен, ішкі фрагментация мәселесі де бар – сұралған жад кішкентай блоктан сәл үлкен, бірақ үлкен блоктан әлдеқайда кіші болғандықтан жад ысырапқа кетеді. Бадди жадты бөлу техникасының жұмыс істеу принципіне байланысты, 66 К жад сұраған бағдарламаға 128 К жад бөлінеді, бұл 62 К жадтың ысырап болуына әкеледі. Бұл мәселені табақша бөлу арқылы шешуге болады, оны одан ұсақ түйірлі бөлу үшін ірі бадди бөлушінің үстіне қоюға болады. Бадди бөлу алгоритмінің бір нұсқасын Дональд Кнут "Компьютерлік бағдарламалау өнері" кітабының 1-томында егжей-тегжейлі сипаттаған. Linux ядросы да бадди жүйесін қолданады, сыртқы фрагментацияны азайту үшін қосымша өзгерістермен, сондай-ақ блоктардағы жадты басқару үшін басқа да әртүрлі бөлушілермен бірге. jemalloc – бұл басқалармен қатар бадди техникасын қолданатын қазіргі заманғы жад бөлуші.
In comparison to other simpler techniques such as dynamic allocation, the buddy memory system has little external fragmentation, and allows for compaction of memory with little overhead. The buddy method of freeing memory is fast, with the maximal number of compactions required equal to O(highest order) = O(log2(total memory size)). Typically the buddy memory allocation system is implemented with the use of a binary tree to represent used or unused split memory blocks. The address of a block's "buddy" is equal to the bitwise exclusive OR (XOR) of the block's address and the block's size. However, there still exists the problem of internal fragmentation – memory wasted because the memory requested is a little larger than a small block, but a lot smaller than a large block. Because of the way the buddy memory allocation technique works, a program that requests 66 K of memory would be allocated 128 K, which results in a waste of 62 K of memory. This problem can be solved by slab allocation, which may be layered on top of the more coarse buddy allocator to provide more fine grained allocation. One version of the buddy allocation algorithm was described in detail by Donald Knuth in volume 1 of The Art of Computer Programming. The Linux kernel also uses the buddy system, with further modifications to minimise external fragmentation, along with various other allocators to manage the memory within blocks. jemalloc is a modern memory allocator that employs, among others, the buddy technique.