Bagaimana menyebabkan kernel memadatkan memori yang terfragmentasi

Saya sedang berlari Fedora 26.

Ini untuk tugas yang sangat aneh yang diberikan oleh profesor algoritma saya. Tugas mengatakan:

Memori fragmentasi dalam C:
Desain, laksanakan, dan jalankan C-program yang melakukan hal berikut: Ini mengalokasikan memori untuk urutan 3mukuran array 800.000 elemen masing-masing; kemudian secara eksplisit mendelokasi semua array genap dan mengalokasikan urutan marray berukuran 900.000 elemen masing-masing. Ukur jumlah waktu yang dibutuhkan program Anda untuk alokasi urutan pertama dan untuk urutan kedua. Pilih muntuk menguras hampir semua memori utama yang tersedia untuk program Anda. "

Tujuan keseluruhan dari ini adalah untuk memecah memori kemudian meminta sedikit lebih banyak daripada apa yang tersedia sebagai potongan yang berdekatan, memaksa sistem operasi untuk memadatkan atau mendefrag memori.

Di kelas saya bertanya bagaimana kita harus melakukan ini karena memori divisualisasikan dan tidak benar-benar berdekatan, yang dia jawab: "Yah, Anda harus mematikan [memori virtual]." Beberapa siswa lain bertanya di kelas bagaimana kita harus tahu kapan kita telah mencapai "pengumpulan sampah" ini, dan dia berkata bahwa: "Waktu untuk alokasi kedua harus lebih besar daripada yang pertama karena waktu yang diambil oleh pengumpulan sampah"

Setelah mencari-cari sedikit, hal terdekat yang dapat saya temukan untuk menonaktifkan memori virtual adalah dengan menonaktifkan swap memori swapoff -a. Saya menonaktifkan lingkungan desktop saya dan mengkompilasi dan menjalankan program saya dari terminal asli (untuk menghindari kemungkinan gangguan dari proses lain, terutama yang berat seperti Lingkungan Desktop). Saya melakukan ini dan menjalankan program saya dengan peningkatan msampai saya mencapai titik di mana waktu untuk alokasi kedua lebih besar dari yang pertama.

Saya menjalankan program dengan peningkatan mdan akhirnya menemukan titik di mana waktu untuk alokasi kedua lebih dari waktu untuk alokasi pertama. Namun dalam perjalanan saya mencapai titik di mana proses itu dibunuh sebelum alokasi kedua. Saya memeriksa dmesgdan melihat bahwa itu dibunuh oleh oom-killer. Saya menemukan dan membaca beberapa artikel tentang oom-killer dan menemukan bahwa Anda dapat menonaktifkan alokasi memori oleh kernel.

Saya melakukan ini dan menjalankan program saya lagi, hanya saja kali ini saya tidak dapat menemukan msehingga waktu yang kedua lebih tinggi dari yang pertama. Akhirnya dengan m yang lebih besar dan lebih besar (meskipun jauh lebih kecil dari ketika keseluruhan alokasi diaktifkan) malloc akan gagal dan program saya akan berakhir.

Saya punya tiga pertanyaan, yang pertama tidak terlalu penting:

1. Apakah pengumpulan sampah adalah istilah yang benar untuk ini? Profesor saya sangat bersikeras mengatakan bahwa ini adalah pengumpulan sampah, tetapi saya berada di bawah asumsi bahwa pengumpulan sampah adalah sesuatu yang dilakukan oleh bahasa pemrograman dan bahwa ini akan dianggap lebih defragmenting.

2. Apakah pemadatan seperti yang diinginkannya mungkin pada sistem linux?

3. Mengapa saya bisa mencapai titik di mana waktu untuk alokasi kedua lebih tinggi daripada yang pertama ketika saya menonaktifkan swap tetapi masih memiliki keseluruhan memori yang diaktifkan? Apakah pemadatan benar-benar terjadi? Jika demikian mengapa saya tidak dapat mencapai titik di mana pemadatan terjadi setelah saya menonaktifkan keseluruhan memori?

Kudos atas riset Anda sejauh ini, ini memang serangkaian pertanyaan yang menarik.

Ada aspek penting untuk dipertimbangkan di sini secara umum: alokasi memori sebagian tanggung jawab sistem operasi, dan sebagian tanggung jawab setiap proses yang berjalan (mengabaikan sistem lama tanpa perlindungan memori dan ruang alamat virtual). Sistem operasi menangani penyediaan setiap proses dengan ruang alamatnya sendiri, dan mengalokasikan memori fisik untuk proses bila perlu. Setiap proses menangani mengukir ruang alamatnya (sampai batas tertentu) dan memastikan itu digunakan dengan tepat. Perhatikan bahwa tanggung jawab suatu proses akan sebagian besar tidak terlihat oleh programmer, karena lingkungan runtime menangani sebagian besar hal.

Sekarang, untuk menjawab pertanyaan Anda ...

1. Dalam pikiran saya pengumpulan sampah adalah satu langkah dihapus dari apa yang Anda lakukan di sini. Saya membayangkan Anda menulis dalam bahasa C, menggunakan malloc()dan free(). Pengumpulan sampah , di mana didukung oleh bahasa pemrograman dan lingkungan runtime, mengurus bagian yang terakhir: ia mengidentifikasi blok memori yang sebelumnya dialokasikan tetapi tidak lagi digunakan (dan, yang penting, tidak pernah lagi dapat digunakan), dan mengembalikannya ke pengalokasi. Pertanyaan terkait di JdeBP ‘s komentar menyediakan beberapa latar belakang, tapi saya merasa sebagian besar menarik karena menunjukkan bahwa orang yang berbeda memiliki pendapat yang sangat berbeda pada pengumpulan sampah, dan bahkan apa yang merupakan pengumpulan sampah.

   Dalam konteks yang kami minati, saya akan menggunakan "pemadatan memori" untuk membicarakan proses yang sedang dibahas.

2. Dari perspektif pemrograman userspace, apa yang diminta oleh dosen Anda tidak mungkin, di C, di Linux, karena satu alasan sederhana: apa yang kami pedulikan di sini bukanlah fragmentasi memori fisik, melainkan fragmentasi ruang. Ketika Anda mengalokasikan banyak blok 800.000 byte Anda, Anda akan berakhir dengan pointer sebanyak untuk setiap blok. Di Linux, pada titik ini, sistem operasi itu sendiri belum banyak berbuat, dan Anda tidak perlu memiliki memori fisik yang mendukung setiap alokasi (sebagai tambahan, dengan alokasi yang lebih kecil sistem operasi tidak akan terlibat sama sekali, hanya Anda Pengalokasi C library, tetapi alokasi di sini cukup besar yang akan digunakan oleh C librarymmap, yang ditangani oleh kernel). Saat Anda membebaskan blok bernomor ganjil, Anda mendapatkan kembali blok ruang alamat itu, tetapi Anda tidak bisa mengubah pointer yang Anda miliki ke blok lain. Jika Anda mencetak pointer saat Anda pergi, Anda akan melihat perbedaan di antara mereka tidak lebih dari permintaan alokasi (802.816 byte pada sistem saya); tidak ada ruang antara dua pointer untuk blok 900.000 byte. Karena program Anda memiliki pointer aktual untuk setiap blok, daripada beberapa nilai yang lebih abstrak (dalam konteks lain, pegangan), lingkungan runtime tidak dapat melakukan apa-apa tentang hal itu, sehingga tidak dapat memadatkan memorinya untuk menyatukan blok bebas.

   Jika Anda menggunakan bahasa pemrograman di mana pointer bukan konsep yang terlihat oleh programmer, maka pemadatan memori dimungkinkan, di Linux. Kemungkinan lain adalah menggunakan API alokasi memori di mana nilai yang dikembalikan bukan pointer; lihat misalnya fungsi alokasi heap berbasis pegangan di Windows (di mana pointer hanya valid ketika pegangan dikunci).

3. Latihan profesor Anda secara efektif mengukur kinerja mmap, yang mencakup algoritme berjalan bebas blok. Anda pertama-tama mengalokasikan blok 3 × m , kemudian membebaskan setengah dari mereka, dan kemudian mulai mengalokasikan blok m lagi; membebaskan semua blok tersebut membuang banyak blok-blok gratis pada pengalokasi kernel, yang perlu dilacak (dan waktu yang dihabiskan oleh freepanggilan menunjukkan bahwa tidak ada optimasi yang dilakukan saat ini). Jika Anda melacak waktu alokasi masing-masing blok individu, Anda akan melihat bahwa alokasi 900k pertama membutuhkan banyak, banyaklebih lama dari yang lain (tiga urutan besarnya pada sistem saya), yang kedua jauh lebih cepat tetapi masih membutuhkan lebih banyak (dua urutan besarnya), dan alokasi ketiga kembali ke tingkat kinerja yang khas. Jadi ada sesuatu yang terjadi, tetapi pointer yang dikembalikan menunjukkan bahwa itu bukan pemadatan memori, setidaknya tidak dialokasikan pemadatan blok (yang, seperti yang dijelaskan di atas, tidak mungkin) - mungkin waktu berhubungan dengan waktu memproses struktur data yang digunakan kernel untuk melacak ruang alamat yang tersedia dalam proses (saya memeriksa ini dan akan memperbarui nanti). Alokasi panjang ini dapat tumbuh untuk mengerdilkan urutan alokasi keseluruhan yang Anda ukur, yaitu ketika alokasi 900k berakhir dengan keseluruhan keseluruhan lebih lama daripada alokasi 800k.

   Alasan overcommit mengubah perilaku yang Anda lihat adalah bahwa itu mengubah latihan dari memanipulasi ruang alamat, untuk benar-benar mengalokasikan memori, dan dengan demikian mengurangi ukuran taman bermain Anda. Ketika Anda bisa overcommit, kernel hanya dibatasi oleh ruang alamat proses Anda, sehingga Anda dapat mengalokasikan blok yang jauh lebih banyak dan memberi tekanan lebih besar pada pengalokasi. Ketika Anda menonaktifkan overcommit, kernel dibatasi oleh memori yang tersedia, yang mengurangi nilai yang Anda miliki untuk mturun ke tingkat di mana pengalokasi tidak cukup tertekan untuk alokasi waktu meledak.