Menulis manajer memori Anda sendiri yang baik

Selamat siang, pembaca. Anda mungkin sudah membaca artikel saya sebelumnya, dan Anda tahu bahwa saya sedang menulis OS saya sendiri. Hari ini kita akan berbicara, dan mempertimbangkan algoritma sederhana dan cukup cepat untuk mengelola memori - manajer memori adalah bagian penting dari OS, karena bekerja dengan cepat, dapat diandalkan, dan tidak limbah dengan memori adalah kunci untuk OS yang baik.
Saya sedang mencari ide-ide sederhana dan memadai untuk manajer di Runet dan di situs berbahasa Inggris - saya masih tidak dapat menemukan artikel bagus tentang pengalokasi yang memadai, bukan O (N). Nah, hari ini kita akan mempertimbangkan ide yang lebih baik untuk manajer memori, saya meletakkan kelanjutannya di bawah cat.

Teori

Dari wiki: Manajer memori - bagian dari program komputer (baik aplikasi dan sistem operasi) yang memproses permintaan untuk alokasi dan pelepasan RAM atau (untuk beberapa arsitektur komputer) permintaan untuk memasukkan area memori yang diberikan dalam ruang alamat prosesor.

Saya sarankan juga sebelum melanjutkan membaca artikel ini .

Pengalokasi Watermak

Yah, mungkin yang paling sederhana dari semua pengalokasi adalah Watermark Allocator. Esensinya kira-kira sebagai berikut: seluruh memori dibagi menjadi blok, blok memiliki header yang berisi ukuran ini dan blok sebelumnya, status blok (sibuk / gratis), mengetahui alamat blok, kita bisa mendapatkan alamat blok berikutnya dan sebelumnya untuk O (1).

Alokasi memori

Untuk mengalokasikan memori, kita hanya perlu menjalankan blok, dan mencari blok yang ukurannya lebih besar atau sama dengan ukuran memori yang diperlukan untuk alokasi. Seperti yang sudah Anda pahami, perilaku asimptotik O (N) buruk.

Pelepasan memori

Untuk membebaskan memori, cukup bagi kita untuk mengatur status blok sebagai "bebas" - O (1) - super!

Tetapi, seperti yang Anda pahami, lubang dapat mulai terbentuk di mana 2 atau lebih blok bebas didefragmentasi, ketika dirilis, blok tetangga dapat dilihat, dan jika satu atau dua gratis, gabungkan menjadi satu.

Alokator Logaritma

Kami tahu bahwa kami hanya perlu mencari di antara blok gratis. Menjalankan hanya dengan gratis meningkatkan kecepatan rata-rata dua kali, tetapi masih berupa garis. Nah, mengapa kita harus menjalankan semua blok, mencari ukuran, jika kita dapat mengatur pohon dari blok gratis! Awalnya, kami hanya memiliki satu blok gratis, dan kemudian kami menambahkan blok gratis ke pohon pencarian biner, kuncinya adalah ukuran blok. Jadi, untuk mengalokasikan memori, cukup bagi kita untuk menemukan blok di pohon yang ukurannya lebih besar atau sama dengan apa yang kita butuhkan. Kami diam-diam melakukan ini untuk O (log N), hanya turun pohon. Selanjutnya, kami memotong blok menjadi dua, atau sepenuhnya memberikannya kepada orang yang meminta memori. Selanjutnya, kami menghapus blok dari pohon untuk O (1). Dan, jika perlu, masukkan sisa blok kembali ke belakang O (log N). Untuk rilis, kita hanya perlu memasukkan kembali blok, dan jangan lupa tentang fragmentasi.

Adalah logis bahwa Anda tidak perlu menggunakan pohon sederhana, Anda perlu menggunakan pohon self-balancing, Merah-Hitam atau AVL. Anda dapat menyimpan pohon blok dalam array statis, atau Anda bisa mencari cara melakukannya secara berbeda.

Sebenarnya kodenya:

char * malloc(size_t size) { if (!size) { return 0; } char * addr = 0; int i; for (i = 0; i < allocationAvlTree.size; ) { int r; node_t *n; n = &allocationAvlTree.nodes[i]; /* couldn't find it */ if (!n->key) { return NULL; } r = allocationAvlTree.cmp(n->key, size); if (r <= 0) { //We're lucky today. //Get memory block header alloc_t * block = (size_t)n->val - sizeof(alloc_t); //Set to used block->status = 1; //Set size block->size = size; alloc_t * next = (size_t)n->val + size; next->prev_size = size; next->status = 0; next->size = n->key - size - 16; avltree_remove(&allocationAvlTree, n->key, n->val); if (n->key - size - 16) avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t)); memset((size_t)block + sizeof(alloc_t), 0, block->size); block->signature = 0xDEADBEEF; unlockTaskSwitch(); return (size_t)block + sizeof(alloc_t); } else if (r > 0) i = __child_r(i); else assert(0); } return 0; } void free(void * mem) { if (!mem) return; //Get current alloc alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t)); if (alloc->signature != 0xDEADBEEF) return; alloc->status = 0; alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size); if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size) { //Merge blocks if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) { left->size += sizeof(alloc_t) + alloc->size; alloc = left; } else assert(0); } alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size; if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF) { if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t))) alloc->size += sizeof(alloc_t) + right->size; else assert(0); } avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t)); } 

Semoga berhasil dan peretasan etis! Setiap kritik objektif diterima, tujuan artikel ini bukan untuk mengatakan bahwa itu adalah semacam pengalokasi, tetapi hanya untuk berbicara tentang pengalokasi yang akan lebih baik daripada implementasi bodoh dari pengalokasi sederhana.