C Academy · Ders

Boş Listeler ve Yeniden Kullanım

Blokları izleyip yeniden kullanın.

Boş Listeler ve Yeniden Kullanım, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, C Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. C Academy kursu toplamda 4 dersten oluşur.

Bump Allocator'ın Ötesi

Tek tek blokları serbest bırakıp yeniden kullanmak için kayıt tutmamız gerekir. Serbest liste, allocator'ın yeni bellek almadan önce aradığı kullanılabilir bloklardan oluşan bağlı bir listedir.

Her blok, allocator'ın boyutunu bulabilmesi ve zincirdeki sonraki bloğa bağlanabilmesi için bir başlık taşır.

Bağlantılı Blok Başlığı

Başlığı bir next işaretçisi ve bir free bayrağıyla genişletiyoruz. Bunlar birlikte havuzumuzu üzerinde gezinilebilen bir blok listesine dönüştürür.

Yük, bellekte başlığın hemen ardından gelir.

typedef struct block {
    size_t size;          /* payload bytes */
    int free;             /* 1 if reusable */
    struct block *next;   /* next block in pool */
} block_t;

Tek Bir Büyük Serbest Bloğu Başlatma

Başlangıçta havuzun tamamı tek bir dev serbest bloktur. Ayırmalar gerçekleşirken bloğu böleriz; serbest bırakmalar gerçekleşirken blokları yeniden kullanılabilir olarak işaretleriz.

Listenin başı, tüm alanı kaplayan bu ilk bloktur.

static unsigned char pool[4096];
static block_t *head;

void heap_init(void) {
    head = (block_t *)pool;
    head->size = sizeof(pool) - sizeof(block_t);
    head->free = 1;
    head->next = NULL;
}

İlk Uygun Bloğu Arama

En basit yeniden kullanım stratejisi first-fit'tir: listede ilerleyin ve yeterince büyük olan ilk serbest bloğu döndürün. Bu yöntem hızlıdır ve küçük blokları listenin başına yakın tutma eğilimindedir.

Alternatifler best-fit (yeterli olan en küçük blok) ve worst-fit'tir; bunlar hızı parçalanma davranışıyla değiş tokuş eder.

block_t *first_fit(size_t size) {
    for (block_t *b = head; b; b = b->next)
        if (b->free && b->size >= size)
            return b;
    return NULL;
}

Serbest Bir Bloktan Ayırma

Uygun bir blok bulduğumuzda onu kullanılıyor olarak işaretler ve başlığının hemen sonrasındaki işaretçiyi döndürürüz. Şimdilik bloğun tamamını teslim ediyoruz; bölme işlemi bir sonraki derste ele alınacak.

Döndürülen işaretçi block + 1 olur ve başlık çağırandan gizlenir.

void *my_alloc(size_t size) {
    block_t *b = first_fit(size);
    if (!b) return NULL;
    b->free = 0;
    return (void *)(b + 1);
}

Bir Bloğu Serbest Bırakma

Serbest bırakmak için kullanıcı işaretçisinden başlığına geri gidip free bayrağını tersine çevirin. Böylece blok, sonraki aramada yeniden kullanılmaya uygun hale gelir.

Yükten başlığı geri almak, daha önce gördüğümüz tek adımlı işaretçi hilesinin aynısıdır.

void my_free(void *p) {
    if (!p) return;
    block_t *b = (block_t *)p - 1;
    b->free = 1;
}

Bitişik Serbest Blokları Birleştirme

Tek başına serbest bırakma, havuzu küçük serbest bloklarla doldurur. Birleştirme, serbest bırakılmış bir bloğu sonraki blok da serbestse onunla birleştirerek daha büyük bitişik bölgeleri yeniden oluşturur.

Bu işlem dış parçalanmayla mücadele eder; böylece gelecekteki büyük istekler karşılanabilir.

void coalesce(block_t *b) {
    if (b->next && b->next->free) {
        b->size += sizeof(block_t) + b->next->size;
        b->next = b->next->next;
    }
}

Çalıştırılabilir Serbest Liste Gösterimi

Bu eksiksiz program bir havuzu başlatır, iki blok ayırır, ilk bloğu serbest bırakır ve ardından daha küçük bir istek için onu yeniden kullanır; böylece serbest listenin çalıştığını kanıtlar.

#include <stdio.h>
#include <stddef.h>

typedef struct block { size_t size; int free; struct block *next; } block_t;
static unsigned char pool[1024];
static block_t *head;

void heap_init(void){ head=(block_t*)pool; head->size=sizeof(pool)-sizeof(block_t); head->free=1; head->next=NULL; }
block_t *first_fit(size_t s){ for(block_t *b=head;b;b=b->next) if(b->free&&b->size>=s) return b; return NULL; }
void *my_alloc(size_t s){ block_t *b=first_fit(s); if(!b) return NULL; b->free=0; return (void*)(b+1); }
void my_free(void *p){ if(!p) return; ((block_t*)p-1)->free=1; }

int main(void){
    heap_init();
    int *a = my_alloc(sizeof(int));
    *a = 7;
    printf("a=%d free=%d\n", *a, head->free);
    my_free(a);
    printf("after free: free=%d\n", head->free);
    return 0;
}

Aramanın Bedeli

Tek bağlı bir serbest liste, ayırma işleminin blok sayısına göre O(n) olduğu anlamına gelir. Çok sayıda ayırma yapıldığında bu işlem yavaşlar.

Gerçek allocator'lar, aramayı O(1)'e yaklaştırmak için boyuta göre sınıflandırılmış serbest listeler (kutular) veya ağaçlar kullanır. Yeniden kullanım ilkesi aynı kalır.

/* Segregated lists: one bucket per size class */
static block_t *bins[NUM_SIZE_CLASSES];
/* lookup goes straight to the right bucket */

Çift Serbest Bırakma ve Bozulma

Bir bloğu iki kez serbest olarak işaretlemek veya bir bloğun boyutunun ötesine yazmak, komşu başlıkları bozar. Sonraki arama da bozuk bir next işaretçisini izleyerek çöker.

C'deki bellek hatalarının bu kadar tehlikeli olmasının nedeni budur: allocator'ın kendi üst verileri verilerinizin hemen yanında bulunur.

Yeniden Kullanımı Bir Araya Getirme

Çalışan bir serbest liste allocator'ı başlatma, uygunluk stratejisi, ayırma, serbest bırakma ve birleştirme işlemlerine ihtiyaç duyar. Bunlarla bellek sonsuza kadar büyümek yerine havuz içinde dolaşır.

Geriye kalan iyileştirme, aşırı büyük blokları bölmek ve hizalamaya uymaktır; bunlar son dersin konusudur.

Hızlı Kontrol

Bir serbest listenin kötü biçimde parçalanmasını neyin önlediğini düşünün.

Özet

Serbest liste, blokları başlıklar aracılığıyla birbirine bağlayarak tek tek ayırmaların serbest bırakılıp yeniden kullanılmasını sağlar. İlk uygun blok araması bir blok bulur, serbest bırakma bir bayrağı tersine çevirir ve birleştirme, parçalanmayla mücadele etmek için komşuları birleştirir.

Doğrusal arama O(n)'dir; üretim allocator'ları hız için boyutlara göre kutulara ayırır. Sırada bölme ve hizalama var.

Sıkça Sorulan Sorular

“Boş Listeler ve Yeniden Kullanım” dersi ücretsiz mi?

Evet — “Boş Listeler ve Yeniden Kullanım” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve C Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. C Academy kursu toplamda 4 dersten oluşur.

“Boş Listeler ve Yeniden Kullanım” dersinde ne öğreneceğim?

Blokları izleyip yeniden kullanın. C Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

C Academy öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te C Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.

“Boş Listeler ve Yeniden Kullanım” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu C Academy dersinde kod yazıp çalıştırabilir miyim?

Evet. Her C Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

← C Academy Sayfasına Dön