내블로그
링크추가

내인생의 환희블로그를
링크에 추가하시겠습니까?

취소

Have you got stucked in the development while aiming to implement a modern and very efficient alorithm? Here's a start up point before getting to implement them.

Simple Memory Allocation Algorithms

Memory allocation is a process that assigns chunks of memory upon request of the various processes running on a machine. Today, there are several well known efficient algorithms used on high-end operating systems but their mathematical models are quite difficult to comprehend from the first time by most amateur operating system developers. That’s why most of the simple operating systems available on the amateur websites use less efficient memory allocation algorithms but highly comprehensible and very educative.

This article focuses on three simple algorithms you may want to experiment on your osdev projects.

The Simplest Algorithm

The complexity of an algorithm is given by the number of steps, their iteration and their timing. Since we are talking about the simplest one, it will have the fastest memory release function: it will do nothing!

The allocator will just store the address of the next free available memory block and allocate requested chunks continuously. A brief implementation follows:

#define MAX_MEMORY 1024 * 1024 * MEMORY_SIZE_IN_MEGABYTES

int peak;

void *malloc(size_t size) {
    void *current;
if( MAX_MEMORY ? peak < size ) return null;
    current = (void *)peak;
    peak += size;
    return current;
}

void free(void *ptr) {
    return;
}
Extremely inefficient, but stable, no different block will overlap to cause memory sharing violations. Since the memory will be consumed after a certain number of allocations, we must implement a mechanism to re-enter the released blocks back in a list of available locations.

The “First Fit” Algorithm

The first fit algorithm basically extends the previous one by implementing a list of free blocks. When the allocator will receive a request of X bytes, it will lookup the list for an available block to fit X bytes. Since aiming to find a perfect match my yield negative results we will allocate memory for the X bytes in the first block equal or greater than X.

Of course, this will lead to an undesired effect: memory fragmentation. Larger block will be split into smaller ones to fit the requested amounts of memory and we may end up with the impossibility of serving a process requesting Y bytes although the sum of all free, but small, blocks is way greater than Y.

A brief C-like implementation follows.

#define MAX_MEMORY 1024 * 1024 * MEMORY_SIZE_IN_MEGABYTES
// using a fixed size array isn’t the best idea,
// the best implementation would be to manage the data with a chained list
#define LIST_ITEMS 100

typedef struct {
    size_t size;
    size_t first_byte_ptr;
} list_item;

list_item list[LIST_ITEMS];
list_item allocted[LIST_ITEMS];

int j = 0;

void *malloc(size_t size) {
    int i;
    void *current;

    if( j < LIST_ITEMS ) return null; // no slots

    for( i = 0 ; i < LIST_ITEMS ; i++ )
        if( list[i].size >= size ) break;

    if( i == LIST_ITEMS ) return null; // no suitable block found

    current = (void *)list[i].first_byte_ptr;
    list[i].first_byte_ptr += size;
    list[i].size -= size;

    allocated[j].first_byte_ptr = current;
    allocated[j].size = size;
    j++;

    return current;
}

void free(void *ptr) {
    int i;

    for( i = 0 ; i < LIST_ITEMS ; i++ )
        if( allocated[i].first_byte_ptr == ptr ) break;
    
    for( k = 0 ; k < LIST_ITEMS ; k++ )
        if( list[k].size == 0 ) break;

    list[k].size = allocated[i].size;
    list[k].first_byte_ptr = allocated[k].first_byte_ptr;

    allocated[i].first_byte_ptr = 0;
    allocated[i].size = 0;

    return;
}

There is enough room for optimization for the above code, especially for the management of the two lists. Chained links are optimal and sorting them when the CPU is idle is a good idea, especially if followed by testing if any blocks are adjacent in order to be merged.

The “Buddy” Algorithm

The buddy algorithm is an optimized version of the “first fit” allocator. It will only allocate blocks of certain sizes, maintaining lists for each series of blocks of a specific size. The permitted sizes are often powers of two, aiming to match blocks of basic types which have sizes of powers of two and because splitting a lager block in two will result a pair of permitted blocks of inferior permitted size. Some implementations use other series of sizes, such as the Fibonacci sequence.

The main advantage compared to “first fit” is speed. We know exactly where to lookup for free blocks, and if we don’t find one we go straight to the next list, of larger blocks. But as its ancestor, it suffers from memory fragmentation.

Let’s suppose a process requests a block of 7 bytes. The allocator will automatically lookup the list of 8 bytes blocks and assign one. There will be a one byte loss in the allocated block. But what if the process then requests a block of 9 bytes? It will look up the 16 bytes block list and return one block. The loss will consist in 7 unused bytes.

That may not sound very tragic, but multiply the amounts with 1K or 1MB to get the figures quite closed to the reality. The lost memory space is common known as slack space. Fragmentation can be reduced by making the block sizes closer together.



ⓒ Daum

검색