처음으로 | 찾기 | 아카이브 | 글 올리기 | 링크 | 자료실 | 통계 | 연락처 | 자유게시판
이지도움 특집
TI DaVinci
Analog Blackfin
캐쉬의 모든것
메모리 할당 알고리즘
CPU 파이프라이닝




사용자 등록

현재 접속중인 등록 사용자는 0명, 익명 사용자는 1명 입니다.
전체 등록 사용자: 751명

마지막 답장
·libcurl + fuse 조합으로 되는게 많네. (1)
·Linux Ftrace에 관해 (3)
·Android MTP ( Media Transfer Protocol ) (1)
·Lighttpd에 인증을 digest 사용시 IE 오동작 문제? (1)
·Dtrace에 관해 (1)

·OpenSSL and multi-threads (0)
·ARM 환경에서 OpenCL 사용 (0)
·IoT용 WIFI 모듈 비교 ( MCU ) 클래스 (0)
·Glances - 리눅스 여러 가지 항목을 한 화면에서 모니터링 (0)
·plugin 방식의 로그 분석기 (0)

뜨거운 감자
·나는 인터렉티브한 환경에서 역어셈블 한다. (12)
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)
·ASP.NET의 데이터 그리드와 사용자 컨트롤 (7)
·DHTML Editing Control (7)

가장 많이 읽은 글
·[Cache] 2-way Set-Associative 방식이란 무엇일까? (2)
·멀티쓰레드(Pthread) 프로그래밍
·Sorting Algorithm Animation (2)
·GNU REGEX (정규표현식) 프로그래밍 강좌 (7)
·SoCRobotWar 2005 - 신입생 기초 교육자료 (7)

Beginner's Guide Allocation
글쓴이: EzDoum 글쓴날: 2002년 04월 12일 오후 11:28

Memory allocation is the process of assigning blocks of memory on request. Typically the allocator receives memory from the operating system in a small number of large blocks that it must divide up to satisfy the requests for smaller blocks. It must also make any returned blocks available for reuse. There are many common ways to perform this, with different strengths and weaknesses. A few are described briefly here:

First fit
Buddy system
These techniques can often be used in combination.

First fit
In the first fit algorithm, the allocator keeps a list of free blocks (known as the free list) and, on receiving a request for memory, scans along the list for the first block that is large enough to satisfy the request. If the chosen block is significantly larger than that requested, then it is usually split, and the remainder added to the list as another free block.

The first fit algorithm performs reasonably well, as it ensures that allocations are quick. When recycling free blocks, there is a choice as to where to add the blocks to the free list -- effectively in what order the free list is kept:

Memory location (address)
This is not fast for allocation or recycling, but supports efficient merging of adjacent free blocks (known as coalescence). According to Dynamic Storage Allocation: A Survey and Critical Review, this ordering reduces fragmentation. It can also improve locality of reference.

Increasing size
This is equivalent to the best fit algorithm, in that the free block with the "tightest fit" is always chosen. The fit is usually sufficiently tight that the remainder of the block is unusably small.

Decreasing size
This is equivalent to the worst fit algorithm. The first block on the free list will always be large enough, if a large enough block is available. This approach encourages external fragmentation, but allocation is very fast.

Increasing time since last use
This is very fast at adding new free blocks, because they are added to the beginning of the list. It encourages good locality of reference (where blocks used together are not spread throughout memory), but can lead to bad external fragmentation.

A variation of first fit, known as next fit, continues each search for a suitable block where the previous one left off, by using a roving pointer into the free block chain. This is not usually combined with increasing or decreasing size ordering because it would eliminate their advantages.

Buddy system
In a buddy system, the allocator will only allocate blocks of certain sizes, and has many free lists, one for each permitted size. The permitted sizes are usually either powers of two, or form a Fibonacci sequence (see below for example), such that any block except the smallest can be divided into two smaller blocks of permitted sizes.

When the allocator receives a request for memory, it rounds the requested size up to a permitted size, and returns the first block from that size's free list. If the free list for that size is empty, the allocator splits a block from a larger size and returns one of the pieces, adding the other to the appropriate free list.

When blocks are recycled, there may be some attempt to merge adjacent blocks into ones of a larger permitted size (coalescence). To make this easier, the free lists may be stored in order of address. The main advantage of the buddy system is that coalescence is cheap because the "buddy" of any free block can be calculated from its address.

A binary buddy heap before allocation

A binary buddy heap after allocating a 8 kB block

A binary buddy heap after allocating a 10 kB block; note the 6 kB wasted because of rounding up

For example, an allocator in a binary buddy system might have sizes of 16, 32, 64,... 64 kB. It might start off with a single block of 64 kB. If the application requests a block of 8 kB, the allocator would check its 8 kB free list and find no free blocks of that size. It would then split the 64 kB block into two block of 32 kB, split one of them into two blocks of 16 kB, and split one of them into two blocks of 8 kB. The allocator would then return one of the 8 kB blocks to the application and keep the remaining three blocks of 8 kB, 16 kB, and 32 kB on the appropriate free lists. If the application then requested a block of 10 kB, the allocator would round this request up to 16 kB, and return the 16 kB block from its free list, wasting 6 kB in the process.

A Fibonacci buddy system might use block sizes 16, 32, 48, 80, 128, 208,... bytes, such that each size is the sum of the two preceding sizes. When splitting a block from one free list, the two parts get added to the two preceding free lists.

A buddy system can work very well or very badly, depending on how the chosen sizes interact with typical requests for memory and what the pattern of returned blocks is. The rounding typically leads to a significant amount of wasted memory, which is called internal fragmentation. This can be reduced by making the permitted block sizes closer together.

For more information, see buddy system in the Glossary.

There are many examples of application programs that include additional memory management code called a suballocator. A suballocator obtains large blocks of memory from the system memory manager and allocates the memory to the application in smaller pieces. Suballocators are usually written for one of the following reasons:

To avoid general inefficiency in the system memory manager;
To take advantage of special knowledge of the application's memory requirements that cannot be expressed to the system memory manager;
To provide memory management services that the system memory manager does not supply.
In general, suballocators are less efficient than having a single memory manager that is well-written and has a flexible interface. It is also harder to avoid memory management bugs if the memory manager is composed of several layers, and if each application has its own variation of suballocator.

Many applications have one or two sizes of block that form the vast majority of their allocations. One of the most common uses of a suballocator is to supply the application with objects of one size. This greatly reduces the problem of external fragmentation. Such a suballocator can have a very simple allocation policy.

There are dangers involved in making use of special knowledge of the application's memory requirements. If those requirements change, then the performance of the suballocator is likely to be much worse than that of a general allocator. It is often better to have a memory manager that can respond dynamically to changing requirements.

  • 첨부 파일: buddy_heap.gif buddy_heap.gif (7 KiB(7,091 Bytes))

    [Image Size 513 x 411]

  • 관련 링크
  • [분류: 리눅스 커널 인쇄용 페이지 본문 email로 보내기 ]

    <  리눅스 커널 공부하기 | 엽기 msn 닉네임..  >
    Beginner's Guide Allocation | 답장: 1개 | 본문에 답장
    정렬 :  
    icon_eek.gif EzDoum 2002년 04월 13일 오전 10:37 [ 이글에 답장 | 본문에 답장 | 책갈피 ]
    a skeleton C file of the buddy system

    #include <stdio.h>
    #include <stdlib.h>

    /* Stored at the beginning of each block in a buddy system. Forward
    * and backward links are used only within free blocks. */
    struct Block {
    struct Block *f; /* forward link to next free block */
    struct Block *b; /* backward link to previous free block */
    char k; /* size of block is 1<<|k|; k>0 iff free */

    /* Represents one buddy system. */
    struct Arena {
    char *mem; /* memory pool */
    unsigned int m; /* of size 1<<m */
    struct Block **freelists; /* array of doubly linked free block lists */

    /* Initializes a buddy system. Sets up an Arena structure, including
    * the allocation of its memory pool of size 1<<m. Returns a pointer
    * to the Arena structure or NULL if could not allocate any of the
    * structures. */
    struct Arena *
    bs_init(int m)
    /* Check for sane parameter */
    /* Allocate Arena structure a */
    /* Allocate memory pool of a and align it (use memalign(1<<m,1<<m)) */
    /* Allocate array of pointers to doubly linked lists */
    /* Set up free lists */
    /* Set up block structure at the beginning of the only free block */
    return a;

    /* Allocates a block of size >=s from Arena a. Returns pointer to
    * beginning of block or NULL if no more memory is available in Arena
    * a. */
    void *
    bs_alloc(struct Arena *a, int s)
    /* Check for validity of parameters */
    /* Adjust s since we need to allocate extra space for Block structure */
    /* Let k=ceil(log2(s)) */
    /* Find smallest k<=j<=m such that there is a free block b of size
    * 1<<j. Return NULL if there are no free blocks */
    /* Remove block b of size 1<<j from list a->freelists[j] */
    /* As long as block b is too big, we split it and add a new
    * initialized smaller block to the next free list. We adjust b's
    * k. */
    while(j>k) {
    /* ... */
    /* Block b is of the right size, so we mark b as taken and return a
    * pointer to beginning of free space, i.e. right after the Block
    * structure. */

    /* Free a memory region starting at p in Arena a. Returns silently on
    * error. */
    bs_free(struct Arena *a, void *p)
    /* Check for sane parameters */
    /* Let b be the pointer to the Block structure belonging to p */
    /* Mark b as free */
    while (b->k<a->m) {
    /* Let c be the address of b's candidate buddy */
    /* If c is not free or of different size, then break */
    /* Now c is free and of same size as b, so we coalesce them. We
    * remove c from its free list and let b point to the new big
    * block. Also increase b->k. */
    /* Put b on free list b->k */

    /* Check arena a for simple faults by scanning the arena and checking
    * that each free block appears in the appropriate free list. For
    * every inconsistency encountered print an error message but don't
    * return till checked whole memory pool. */
    bs_check(struct Arena *a)
    /* Check if a is NULL */
    /* Check if a->mem is NULL */
    /* Check if a->freelists is NULL */
    /* Let b point to the beginning of memory pool */
    /* As long as b < end of memory pool within arena, check if block b
    * is free. If so, see that b is in the appropriate doubly linked
    * free list b->k. It should be. Also, the b->k should be <= m.
    * If b is not free, skip it. Once checking of b is done, increase
    * b by 2^k and loop back. */


    Beginner's Guide Allocation | 답장: 1개 | 본문에 답장
    정렬 :  

    답장 쓰기
    글을 올리시려면 로그인 (사용자 등록) 하셔야 합니다.


    ·공지 (6)
    ·인터넷 (87)
    ·하드웨어 (260)
    ·C/C++ (65)
    ·어셈블리 (7)
    ·리눅스 (136)
    ·리눅스 커널 (67)
    ·윈도우즈 (25)
    ·데이터베이스 (20)
    ·보안 (16)
    ·.NET (25)
    ·그래픽 (13)
    ·책소개 (42)
    ·호기심 천국 (80)
    ·잡담 (111)
    ·사랑 (3)

    전체 본문수: 963
    전체 답장수: 525

    분류 : 리눅스 커널
    가장 많이 읽은 글
    ·리눅스 커널 공부하기 (2)
    뜨거운 감자
    ·SunWorld Online (4)

    이지도움 어때요?
    이게 뭐야. 다시 안올란다. --;
    아이 좋아라~ +_+;
    먼가는 있는거 같은데 뭐하는 곳이지?
    기타 (자유게시판에 글로 남겨 주세요)
    [ 결과 | 투표 ]

    랜덤 링크

     Home ^ BACK TO TOP ^ EzDoum - 도움이 필요하세요~??
     Powered by KorWeblog 1.5.8 Copyleft © 2001 EzDoum, 관리자: EzDoum