Manajemen memori pintar dengan operasi waktu konstan?

18

Mari kita pertimbangkan segmen memori (yang ukurannya dapat tumbuh atau menyusut, seperti file, bila diperlukan) di mana Anda dapat melakukan dua operasi alokasi memori dasar yang melibatkan blok ukuran tetap:

  • alokasi satu blok
  • membebaskan blok yang sebelumnya dialokasikan yang tidak digunakan lagi.

Selain itu, sebagai persyaratan, sistem manajemen memori tidak diperbolehkan untuk bergerak di sekitar blok yang saat ini dialokasikan: indeks / alamatnya harus tetap tidak berubah.

Algoritme manajemen memori yang paling naif akan menambah penghitung global (dengan nilai awal 0) dan menggunakan nilai barunya sebagai alamat untuk alokasi selanjutnya. Namun ini tidak akan pernah memungkinkan untuk mempersingkat segmen ketika hanya beberapa blok yang dialokasikan tetap.

Pendekatan yang lebih baik: Pertahankan penghitung, tetapi pertahankan daftar blok yang tidak dapat dialokasikan (yang dapat dilakukan dalam waktu konstan) dan gunakan sebagai sumber untuk alokasi baru selama tidak kosong.

Apa selanjutnya? Adakah sesuatu yang pintar yang dapat dilakukan, masih dengan kendala alokasi waktu dan deallokasi yang konstan, yang akan membuat segmen memori sesingkat mungkin?

(Tujuannya mungkin untuk melacak blok yang saat ini tidak dialokasikan dengan alamat terkecil, tetapi tampaknya tidak layak dalam waktu yang konstan ...)

Stéphane Gimenez
sumber
bukankah pengecekan daftar tidak lagi menjadi waktu yang konstan, karena daftar tersebut mungkin bertambah atau menyusut karena beberapa alokasi / disallokasi yang dilakukan sebelumnya?
Sim
@Sim, saya berasumsi itu adalah daftar tertaut dan dengan itu operasinya akan menjadi , karena Anda selalu bekerja hanya dengan kepala. HAI(N)
svick
Saya pikir "pendekatan yang lebih baik" Anda sudah akan menggunakan jumlah memori yang optimal, yaitu tidak akan mengalokasikan memori tambahan jika ada blok gratis. Bagaimana Anda membayangkan pendekatan "pintar" akan memperbaiki itu? Apakah maksud Anda harus mengalokasikan dekat dengan awal sehingga ada kemungkinan lebih baik bahwa Anda dapat mengecilkan segmen setelah deallocations?
svick
@Sim: Maaf, mungkin saya seharusnya menggunakan istilah stack (tapi saya pikir itu bisa membingungkan), 'deallocate' adalah push dan 'alokasikan' adalah pop, atau dalam kasus gagal gagal kembali ke kenaikan tambahan. Keduanya adalah waktu yang konstan.
Stéphane Gimenez
Apakah Anda memiliki batasan waktu nyata, atau apakah Anda baik-baik saja dengan waktu konstan diamortisasi? Jawabannya mungkin sangat berbeda.
Gilles 'SO- stop being evil'

Jawaban:

11

Dengan blok ukuran tetap, apa yang telah Anda gambarkan adalah daftar gratis . Ini adalah teknik yang sangat umum, dengan twist berikut: daftar blok gratis disimpan di blok gratis sendiri. Dalam kode C, akan terlihat seperti ini:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
    void *x;

    if (free_list_head == NULL) {
        x = alloc_ptr;
        alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
    } else {
        x = free_list_head;
        free_list_head = *(void **)free_list_head;
    }
    return x;
}

static void
release(void *x)
{
    *(void **)x = free_list_head;
    free_list_head = x;
}

Ini bekerja dengan baik selama semua blok yang dialokasikan memiliki ukuran yang sama, dan ukuran itu adalah kelipatan dari ukuran pointer, sehingga pelurusan dipertahankan. Alokasi dan deallokasi adalah waktu-konstan (yaitu, sebagai waktu-konstan ketika akses memori dan penambahan-penambahan elementer - dalam komputer modern, akses memori dapat melibatkan kehilangan cache dan bahkan memori virtual, karenanya disk mengakses, sehingga "waktu konstan" bisa sangat besar). Tidak ada memori overhead (tidak ada pointer per-blok tambahan atau hal-hal seperti itu; blok yang dialokasikan berdekatan). Juga, penunjuk alokasi mencapai titik tertentu hanya jika, pada satu waktu, bahwa banyak blok harus dialokasikan: karena alokasi lebih suka menggunakan daftar bebas, penunjuk alokasi ditingkatkan hanya jika ruang di bawah penunjuk saat ini adalah jam penuh. Dalam pengertian itu, teknik.

Menurunpenunjuk alokasi setelah rilis dapat menjadi lebih kompleks, karena blok gratis hanya dapat diidentifikasi secara andal dengan mengikuti daftar gratis, yang melewati mereka dalam urutan yang tidak terduga. Jika mengurangi ukuran segmen besar bila mungkin penting bagi Anda, Anda dapat menggunakan teknik alternatif, dengan overhead yang lebih banyak: di antara dua blok yang dialokasikan, Anda meletakkan "lubang". Lubang-lubang tersebut dihubungkan bersama dengan daftar yang terhubung ganda, dalam urutan memori. Anda memerlukan format data untuk lubang sehingga Anda dapat menemukan alamat mulai lubang dengan mengetahui di mana ujungnya, dan juga ukuran lubang jika Anda tahu di mana lubang dimulai di memori. Kemudian, ketika Anda melepaskan blok, Anda membuat lubang yang Anda gabungkan dengan lubang berikutnya dan sebelumnya, membangun kembali (masih dalam waktu yang konstan) daftar semua lubang yang dipesan. Overhead kemudian sekitar dua kata berukuran pointer per blok yang dialokasikan; tetapi, pada harga itu, Anda dapat dengan andal mendeteksi terjadinya "lubang terakhir", yaitu kesempatan untuk mengurangi ukuran segmen besar.

Ada banyak variasi yang memungkinkan. Makalah pengantar yang baik adalah Dynamic Storage Allocation: A Survey and Critical Review oleh Wilson et al.

Thomas Pornin
sumber
4
Bagaimana Anda menemukan lubang terdekat dengan situs deallokasi dalam waktu yang konstan?
Raphael
1
Dalam metode kedua yang saya jelaskan, sebuah lubang adalah sebuah header (sepasang pointer, untuk daftar lubang) bersama dengan ruang untuk nol, satu atau lebih blok data. Di antara dua blok yang dialokasikan, selalu ada lubang, meskipun itu adalah lubang mikro yang hanya terdiri dari header lubang. Jadi mencari lubang terdekat itu mudah: mereka tepat sebelum dan tepat setelah slot. Tentu saja, lubang mikro tidak dijadikan bagian dari daftar gratis (daftar lubang yang memenuhi syarat untuk dialokasikan). Cara lain untuk melihatnya adalah Anda menambahkan header ke setiap blok dan setiap lubang (non-mikro) (alokasi di bawah 16-bit Ms-Dos bekerja seperti itu).
Thomas Pornin
4

Jawaban ini adalah tentang teknik manajemen memori generik. Saya melewatkan pertanyaan tentang kasus di mana semua blok memiliki ukuran yang sama (dan disejajarkan).


Strategi dasar yang harus Anda ketahui adalah kecocokan pertama, kecocokan berikutnya, kecocokan terbaik, dan sistem pertemanan . Saya menulis ringkasan singkat sekali untuk kursus yang saya ajarkan, saya harap ini bisa dibaca. Saya menunjuk ke sana untuk survei yang cukup lengkap .

Dalam praktiknya Anda akan melihat berbagai modifikasi dari strategi dasar ini. Tapi tidak ada yang benar-benar konstan! Saya tidak berpikir itu mungkin dalam kasus terburuk, saat menggunakan jumlah memori yang terbatas.

rgrig
sumber
Menarik, saya harus membaca ini secara terperinci. Namun, tampaknya sistem ini secara khusus menangani alokasi ukuran yang tidak konstan, yang bukan masalah yang saya hadapi.
Stéphane Gimenez
Baik. Maaf, saya membaca pertanyaan Anda terlalu cepat.
rgrig
HAI(lgn)
s / blok gratis terkecil / blok gratis di alamat terkecil /
rgrig
2

Anda mungkin ingin melihat analisis diamortisasi dan khususnya array dinamis. Bahkan jika operasi tidak benar-benar dilakukan dalam waktu yang konstan di setiap langkah, dalam jangka panjang kelihatannya seperti itu terjadi.

gallais
sumber
2
Dan bagaimana tepatnya array dinamis membantu mengalokasikan memori?
svick
Anda akan (de) mengalokasikan potongan sel yang berdekatan menggunakan jenis algoritma yang sama? Seluruh file Anda akan menjadi daftar tautan potongan yang lebih besar dan lebih besar.
gallais