Analisis Perbandingan Algoritme Marking Sweeping dan Copying Collect pada Proses Garbage Collection (Comparison Analysis of Marking Sweeping and Copying Collect Methods in Garbage Collection Process).

Abstract

Memori merupakan salah satu komponen sistem komputer yang sangat penting karena menyimpan data dan semua instruksi selama program sedang berjalan (running). Pengatur Memori (Memory Mana-ger) didalam Sistem Operasi mengatur pengalokasian data kedalam memori. Pada waktu running, Peng-atur Memori (PM) mengalokasikan data kedalam bagian memori yang disebut dengan heap dengan cara dinamik, yaitu dengan mempergunakan sebagian teknik penempatan: first fit atau best fit. Pengalokasian dengan teknik-teknik tersebut akan menyebabkan sebagian memori menjadi sampah (garbage). Adanya sampah ini karena semua blok bebas dalam memori tidak cukup untuk menyimpan data yang dialokasikan oleh PM. Proses Garbage Collection (GC) menggeser memori aktif ke alamat yang lebih rendah dan menyusun. semua blok bebas sampah diatas menjadi sebuah blok bebas, sedemikian rupa sehingga blok aktif menempati posisi yang berurutan kemudian diikuti sebuah blok bebas. Blok bebas tersebut berukuran lebih besar dan diharapkan dapat meyimpan data yang sebelumnya gagal teralokasi. Dengan demikian, pesan kesalahan karena kekurangan memori (out of memori) kemungkinan besar dapat ditunda. Selama proses GC sedang berjalan, PM belum dapat melayani antrian permintaan lokasi sampai tersedia sebuah blok bebas yang cukup. Waktu menunggu sampai selesainya proses GC itu disebut dengan waktu tunggu (pause time). Waktu eksekusi GC yang terlalu lama menyebabkan program berjalan lebih lambat. Proses GC memiliki dua algoritme yaitu Marking Sweeping (MS) dan Copying Collect (CC). Algoritme MS menelusuri blok aktif untuk menghasilkan sebuah blok bebas. Sedangkan pada Algoritme CC, PM membagi area heap menjadi dua bagian sama besar yang disebut dengan working area (tempat dimana PM melakukan transaksi lokasi) dan dormant area (tempat yang selalu dibiarkan bebas oleh PM). Algoritme ini menyalin blok aktif dari working area kedalam dormant area, kemudian menggunakan dormant area ini sebagai working area. Sisa dari working area sekarang merupakan sebuah blok bebas yang terbentuk sedangkan working area sebelumnya sekarang menjadi dormant area. Dari hasil analisis perbandingan kompleksitas dan waktu eksekusi kedua algoritme diatas dapat disimpulkan bahwa proses GC yang menggunakan Algoritme CC lebih cepat daripada Algoritme MS. Perbandingan waktu eksekusi ini dapat dilihat pada bagian lampiran. Walaupun Algoritme CC lebih cepat tetapi area kerja dari PM hanya menggunakan setengah dari heap memori. Proses GC dilaksanakan pada saat semua blok bebas didalam heap tidak cukup untuk menyimpan data program. Selain itu, proses ini dapat juga dilakukan pada saat processor komputer sedang menganggur (idle). Proses GC tidak pernah dilaksanakan jika ketersediaan ruangan bebas masih cukup. Jika A,NeN dimana A merupakan jumlah sel aktif dan N adalah jumlah sel didalam heap, maka kompleksitas Algoritme MS ialah CMS CLA+CN sedangkan Algoritme CC adalah: Ccc