Contoh Dynamic Memory Allocation Dengan Doubly-linked List, First-fit & Auto Left-Right Join [Part 1]

Virtual memory dapat dialokasikan untuk menyediakan wilayah memori dalam bentuk blok berukuran tetap, membuat kemungkinan fragmentasi semakin kecil. Sayangnya, banyak program cenderung mengalokasikan kebutuhan memori untuk program mereka dalam jumlah banyak, namun dengan ukuran yang relatif jauh lebih kecil dari ukuran blok page virtual memori. Oleh karena itu, diperlukan mekanisme alokasi yang dapat memenuhi kebutuhan tersebut, agar sistem dapat menjaga efisiensi penggunaan memori.

Jika masih bingung dengan latar beakang tulisan ini, coba sedikit mengingat kapan terakhir kali anda membuat program mengalokasikan memori, Biasanya, kita menggunakan malloc() dan free() di lingkungan pemrograman C. Selain itu, di sistem operasi Windows juga tersedia fungsi API yang serupa dengan kedua API library C tersebut, yaitu HeapAlloc() dan HeapFree(). Fungsi semacam itulah yang akan kita coba implementasikan di sini.

Memori perlu memiliki sistematika alokasi, sehingga apabila suatu program sedang menggunakan wilayah memori untuk menangani tugas tertentu, wilayah tersebut akan lebih aman dari campur tangan pekerjaan dari task lain. Meski demikian, masih ada kemungkinan thread lain dapat menggunakan memori yang sudah diklaim sebelumnya, baik itu sengaja atau tidak sengaja. Oleh karena itu perlu juga adanya mekanisme untuk selalu memeriksa kemungkinan buruk tersebut. Tanpa alokasi memori, masing-masing thread dapat menggunakan memori dengan bebas. Masalahnya mulai timbul ketika sudah mulai banyak memori yang digunakan. Celah fragmentasi akan sulit dilacak.

Mekanisme alokasi memori biasanya dilakukan dengan implementasi linked list. Cara sederhana bisa dilakukan dengan membuat linked-list yang menghubungkan setiap potongan (chunk) daerah memory, mulai awal hingga akhir. Sistem yang lebih profesional bahkan membuat 2 macam linked-list untuk memisahkan daerah memori yang sudah dialokasi dan daerah yang bebas. Hal ini membuat proses alokasi semakin cepat.

Sebuah header berada di bagian awal dari setiap chunk, menyediakan informasi instan mengenai kondisi dan properti chunk, seperti ukuran, status chunk dan beberapa hal spesifik lain terkait alokasi memori. Di dalamnyalah linked list akan disematkan.

Meski keberadaan linked list membantu, ada sedikit masalah yang perlu diatasi saat proses pembebasan memori. Meski pembebasan memori bisa dilakukan dengan cukup mengubah variabel state pada header, linked list masih masih terpasang untuk menghubungkan blok bebas(free blocks) yang harusnya tiada lagi. Lihat ilustrasinya seperti berikut.

1. Kita bayangkan awal layout chunk memori seperti berikut, dimana blok merah

adalah area teralokasi.

2. Program membebaskan beberapa blok memori, sehingga bisa dialokasikan kembali.

3. Program meminta alokasi memori ke sistem; Alokator mencari daerah bebas yang pas dengan ukuran permintaan. Ternyata pencarian gagal, karena tiap header menunjukkan blok dalam ukuran kecil. Padahal, seharusnya beberapa wilayah yang baru saja dibebaskan cukup untuk menampung request yang sedang diminta.

Oleh karena itu, saat proses pembebasan memori, alokator juga bertanggung jawab mengatasi fragmentasi internal semacam ini dengan mengusahakan penggabungan blok (joining). Jika alokator mampu menangani pembebasan memori dengan baik, maka kenampakannya akan seperti berikut.

***

Masalah belum sampai disitu. Jika hanya dengan singly-linked list, alokator hanya dapat melihat dan memeriksa posisi blok di sebelah arah kanan saja. Ini menyebabkan penggabngan blok kurang maksimal. Contoh kasusnya adalah seperti ilustrasi berikut.

1. Layout awal.

2. Program meminta pembebasan sebuah blok memori. Untungnya saat ini, alokator belum memerlukan penggabungan chunk memori.

3. Program meminta pembebasan memori kembali. Sepertinya alokator harus melakukan penggabungan sekarang. Dia menemukan sebah blok bebas disebelahnya.