Apakah ada pemulung yang memperhitungkan paging akun?

12

Koleksi sampah harus mengunjungi semua benda yang hidup, sehingga dapat menemukan memori yang dapat direklamasi. (Memiliki banyak generasi hanya menunda ini sedikit)

Semua hal yang sama, jelas lebih baik untuk pertama mengunjungi objek yang sudah di-paging ke RAM, sebelum paging blok lain dan karena itu paging keluar beberapa objek.

Kemungkinan lain adalah bahwa ketika OS ingin mengambil halaman ram dari proses, GC pertama kali ditanya apakah ia memiliki halaman yang dapat diberikan tanpa perlu paging out. GC mungkin sebagian besar dilakukan dengan memindahkan objek dari sebuah halaman, jadi dapat menghapus halaman itu dalam batas waktu yang dimiliki OS untuk membutuhkan sebuah halaman.

Namun, saya tidak dapat mengingat pengumpul sampah yang terintegrasi dengan sistem paging OS yang menggerakkan urutan GC bekerja.

memory-management paging garbage-collection Ian Ringrose
sumber
Tidak persis paging tetapi rubi edisi perusahaan gc ditulis ulang untuk mengurangi efek gc pada salinan di halaman tulis dengan memindahkan meta-data objek ke halaman yang terpisah.
user1937198
Agak terkait pertanyaan tentang implementasi malloc / gratis: Akankah implementasi malloc mengembalikan memori bebas-ed kembali ke sistem? , khususnya jawaban ini . Juga: Apakah membebaskan () memetakan memori suatu proses?
Paul A. Clayton
Secara mengejutkan, afaik / afaict, hampir semua (?) literatur gc tampaknya tidak menganalisis paging OS kecuali secara abstrak. ide: sistem alokasi memori yang melacak pointer antara objek dalam struktur yang terpisah dari objek itu sendiri mungkin lebih ramah lokal / paging karena hanya pointer itu sendiri yang dilintasi (selama gc) dalam ruang yang dipadatkan dengan ketat, bukan semua objek dari berbagai ukuran yang mungkin tersebar di memori (dan beberapa jarang diakses & begitu halaman). mungkin ada beberapa overhead sederhana tetapi mungkin berhasil penghematan secara keseluruhan tergantung pada implementasi.
vzn
Flash drive perlu menggunakan bentuk menyalin pengumpulan sampah yang memperhitungkan pengaturan memori menjadi blok, meskipun saya tidak tahu seberapa baik hal-hal seperti itu dibahas dalam literatur akademik. Masalah yang harus dipecahkan sangat berbeda (flash drive memerlukan GC karena ruang hanya dapat didaur ulang dalam blok yang sangat besar, jadi jika blok memiliki beberapa halaman langsung dan banyak halaman mati, data langsung harus disalin di tempat lain sebelum halaman dapat didaur ulang) tetapi prinsip-prinsip konsolidasi data dapat membantu.
supercat
1
Pola yang saya gunakan dalam kasus-kasus di mana item data relatif kecil terhadap ukuran memori-chunk saya adalah memiliki setiap item data terdiri dari header berukuran tetap yang dialokasikan dari depan ke belakang, dan data berukuran variabel yang akan dialokasikan kembali ke depan. Sebuah tabel menyimpan alamat chunk logis yang dipetakan ke alamat fisik dan jumlah ruang kosong di setiap chunk; setelah setiap pemindaian juga akan mengidentifikasi berapa banyak ruang yang mati. Referensi disimpan dalam flash, dan setiap referensi memiliki bentuk "Item # 3 dari chunk logis # 7". Siklus GC akan menyalin semua data langsung dari satu chunk ke yang baru, dan ...
supercat

Jawaban:

8

Seingat saya, copy collector seharusnya ramah paging, karena penelusuran dengan menyalin cenderung meningkatkan lokalitas referensi pointer. Ini memiliki efek positif pada program (mutator) yang akan menyebabkan lebih sedikit kesalahan halaman saat mengikuti tautan, dan juga akan meningkatkan siklus pengumpulan berikutnya karena pelacakan juga akan menyebabkan lebih sedikit kesalahan halaman. Agenda penelusuran (petunjuk mana yang harus diproses terlebih dahulu) dapat berdampak pada efektivitas untuk meningkatkan lokalitas data. Ini dapat ditingkatkan dengan mengukur statistik pada jumlah akses ke berbagai petunjuk dalam berbagai jenis sel.

Sekarang, jika Anda mempertimbangkan kolektor pelacak secara umum, Anda biasanya harus memelihara struktur yang melacak pointer yang belum dilacak. Dimungkinkan untuk mengatur struktur ini sehingga semua pointer yang menunggu yang menunjuk pada halaman yang sama akan disimpan bersama (meskipun itu mungkin membutuhkan lebih banyak ruang, dalam beberapa kasus, tergantung pada teknik yang tersedia untuk menyimpan daftar pointer tersebut). Kebijakan yang memungkinkan adalah selalu melacak terlebih dahulu set pointer menunggu terbesar yang menunjuk ke halaman yang sama, ketika tidak ada pointer menunggu yang tersisa ke halaman dalam memori.

Mengenai pertanyaan di paragraf ketiga, yang ditambahkan setelah saya menjawab, koleksi salinan lagi merupakan jawaban. OS dapat mengurangi jumlah halaman fisik yang dialokasikan pada waktu pengumpulan, karena halaman sepenuhnya dibebaskan. Dengan tanda dan penyapu kolektor, acara satu halaman penuh bebas mungkin jauh lebih jarang, sehingga tidak layak menjadi machanism tertentu untuk dipertimbangkan.

Gagasan semacam ini alami, dan mungkin dijelaskan dalam beberapa makalah. Tapi saya tidak mengingatnya begitu saja. Saya pikir makalah awal tentang Lisp GC berisi beberapa ide ini (seperti: apakah mobil atau cdr harus diikuti terlebih dahulu?).

Kabar baiknya dalam peran koleksi-salinan ini adalah juga paging ramah untuk menyalin koleksi karena menambah ruang penyimpanan yang tersedia. Ingat bahwa kolektor salinan pada prinsipnya membutuhkan ruang dua kali lebih banyak dari yang digunakan untuk penyimpanan data aktual. Sekarang, efek paging tergantung juga pada ruang alamat mesin, dan memori fisik yang tersedia. Di komputer lama, memori fisik jauh lebih sedikit daripada ruang alamat yang tersedia, sehingga paging benar-benar bonus ruang, memungkinkan kebijakan seperti menyalin GC. Bahkan ketika ruang fisik sebesar ruang alamat, orang mungkin ingin membagikannya, sehingga proses menggunakan GC akan memiliki lebih sedikit ruang alamat tanpa paging (lihat paging). Kata-kata ini agak digantikan oleh penggunaan kolektor generasi. Mereka umumnya menggunakan koleksi salinan untuk generasi muda justru karena kualitas-kualitas ini, dan karena generasi muda kebanyakan berumur pendek.

Kemudian Anda memiliki semua interaksi GC generasi dengan sistem cache, yang telah dibahas dalam pertanyaan sebelumnya: Apakah pengumpul sampah generasi pada dasarnya ramah terhadap cache?

Untuk informasi lebih lanjut tentang masalah ini, saya akan mencari di web dengan, misalnya, pengumpulan dan penempatan sampah kata kunci .

babou
sumber
Saya ragu dengan gagasan pengumpul salinan yang sebenarnya lebih "lokal" daripada penelusuran. copy collector tampaknya secara konseptual sangat mirip dalam dinamika akses memori (mungkin hampir tidak bisa dibedakan) dengan menelusuri "ruang lama". pikir ini perlu referensi. yang mengatakan ada beberapa kemungkinan mekanisme penyalinan meningkatkan kedekatan di ruang baru. ruang baru dimulai berdampingan sempurna, tetapi kemudian "lokalitas" ini menurun atau menurun seiring waktu.
vzn
Nah, Anda menemukan sebagian besar jawabannya. Jadi jangan ragu. Itu ada dalam referensi dasar tentang topik tersebut. Lokalitas dari fakta bahwa penyimpanan dipadatkan, dan dari penyalinan yang menggantikan setiap sel data yang dekat secara logis sesuai dengan struktur penunjuk (yang dapat berevolusi dengan penugasan kembali penunjuk).
babou
Saya masih skeptis / ragu-ragu. tampaknya secara intuitif ruang lama akan memiliki lokalitas yang buruk dan / atau kedekatan ketika siklus copy / gc dimulai. lokalitas terkait dengan membaca (dari ruang lama) dan menulis (ke ruang baru). untuk menganalisisnya, perilaku gestalt / emergent harus dipelajari. mungkin banyak dari ini hanya dapat secara efektif / akurat / realistis dipelajari secara empiris & tidak banyak secara teoritis.
vzn
Saya mengatakan itu dalam literatur, seperti banyak hal lainnya. Tapi saya tidak punya waktu untuk mencarinya dan saya pikir jawaban saya panjang dan penuh dengan informasi., Anda dapat google: mengumpulkan pengumpulan sampah daerah, dan ada referensi ke pertanyaan sebelumnya. Maaf karena singkat, ada kereta untuk menangkap.
babou
Maaf ... bingung pertanyaan ini dengan yang lain ... yang memiliki lebih banyak.
babou
8

Emery Berger, Matthew Hertz & Yi Feng melakukan beberapa hal dalam hal ini.

Pengumpulan sampah menawarkan banyak keuntungan rekayasa perangkat lunak, tetapi berinteraksi buruk dengan manajer memori virtual. Pengumpul sampah yang ada membutuhkan lebih banyak halaman daripada set kerja aplikasi dan halaman sentuh tanpa memperhatikan yang mana dalam memori, terutama selama pengumpulan sampah penuh. Paging yang dihasilkan dapat menyebabkan throughput menurun dan jeda waktu melonjak hingga detik atau bahkan menit.

Saya menghadirkan pengumpul sampah yang menghindari paging. Kolektor bookmark ini bekerja sama dengan manajer memori virtual untuk memandu keputusan pengusirannya.

Ini adalah video ceramah Emery tentang itu, dan dia menulis makalah Koleksi Sampah Tanpa Paging

Untuk beberapa alasan sepertinya tidak banyak yang bekerja nanti, atau penggunaan "dunia nyata". Pada akhir makalah ini tertulis "Kami sedang mengembangkan varian bersamaan dari algoritma pengumpulan bookmark" , tapi saya tidak bisa melacaknya.

CRAMM: Dukungan Memori Virtual untuk Aplikasi yang Dikumpulkan Sampah berusaha mengubah OS untuk membuat GC membuat paging lebih sedikit.

Menggunakan Halaman Residensi untuk Menyeimbangkan Pengorbanan dalam Melacak Pengumpulan Sampah

Kami memperkenalkan ekstensi sebagian besar koleksi salinan yang menggunakan residensi halaman untuk menentukan kapan harus memindahkan objek. Kolektor kami mempromosikan halaman dengan tempat tinggal yang tinggi, menghindari pekerjaan yang tidak perlu dan ruang yang terbuang. Ia memprediksi residensi setiap halaman, tetapi ketika prediksinya terbukti tidak akurat, kolektor kami mendapatkan kembali ruang kosong dengan menggunakannya untuk memenuhi permintaan alokasi. Menggunakan residensi memungkinkan kolektor kami untuk secara dinamis menyeimbangkan tradeoffs dari koleksi penyalinan dan non-penyalinan. Teknik kami membutuhkan lebih sedikit ruang daripada kolektor penyalinan murni dan mendukung penyematan objek tanpa mengorbankan kemampuan untuk memindahkan objek. Tidak seperti hibrid lain, kolektor kami tidak bergantung pada konfigurasi khusus aplikasi dan dapat dengan cepat menanggapi perubahan perilaku aplikasi. Pengukuran kami menunjukkan bahwa hibrida kami berkinerja baik di berbagai kondisi; itu lebih suka menyalin koleksi ketika ada banyak ruang tumpukan tetapi jatuh kembali pada koleksi non-menyalin ketika ruang menjadi terbatas.

Ian Ringrose
sumber