Go mekanisme alokasi

Ketika saya pertama kali mencoba memahami bagaimana alat alokasi memori di Go bekerja, apa yang ingin saya pahami tampak seperti kotak hitam yang misterius. Seperti halnya teknologi lainnya, hal terpenting di sini tersembunyi di balik banyak lapisan abstraksi, yang melaluinya Anda harus melewatinya untuk memahami sesuatu.



Penulis materi, terjemahan yang kami terbitkan, memutuskan untuk sampai ke bagian bawah alokasi memori di Go dan membicarakannya.

Memori fisik dan virtual

Semua cara untuk mengalokasikan memori harus bekerja dengan ruang alamat memori virtual, yang dikendalikan oleh sistem operasi. Mari kita lihat bagaimana memori bekerja, mulai dari level terendah - dengan sel-sel memori.
Berikut ini cara membayangkan sel RAM.


Tata letak sel memori

Jika, dengan cara yang sangat sederhana, bayangkan sel memori dan apa yang mengelilinginya, maka kita mendapatkan yang berikut:

1. Garis alamat (transistor bertindak sebagai saklar) adalah yang memberikan akses ke kapasitor (jalur data).
2. Ketika sinyal muncul di garis alamat (garis merah), jalur data memungkinkan Anda untuk menulis data ke sel memori, yaitu, mengisi kapasitor, yang memungkinkan untuk menyimpan nilai logis yang sesuai dengan 1 di dalamnya.
3. Ketika tidak ada sinyal di garis alamat (jalur hijau), kapasitor terisolasi dan muatannya tidak berubah. Untuk menulis ke sel 0, Anda harus memilih alamatnya dan mengirimkan 0 logis melalui jalur data, yaitu, menghubungkan jalur data dengan minus, sehingga pemakaian kapasitor.
4. Ketika prosesor perlu membaca nilai dari memori, sinyal dikirim sepanjang garis alamat (sakelar ditutup). Jika kapasitor diisi, sinyal melewati jalur data (1 dibaca), jika tidak, sinyal tidak melewati jalur data (0 dibaca).

Skema interaksi memori fisik dan prosesor

Bus data bertanggung jawab untuk mengangkut data antara prosesor dan memori fisik.

Sekarang mari kita bicara tentang garis alamat dan byte yang bisa dialamatkan.


Jalur alamat bus antara prosesor dan memori fisik

1. Setiap byte dalam RAM diberikan pengenal numerik unik (alamat). Perlu dicatat bahwa jumlah byte fisik yang ada dalam memori tidak sama dengan jumlah baris alamat.
2. Setiap baris alamat dapat menentukan nilai 1-bit, jadi ini menunjukkan satu bit di alamat byte tertentu.
3. Sirkuit kami memiliki 32 garis alamat. Akibatnya, setiap byte yang dapat dialamatkan menggunakan nomor 32-bit sebagai alamatnya. [00000000000000000000000000000000] - alamat memori terendah. [1111111111111111111111111111111111] - alamat memori tertinggi.
4. Karena setiap byte memiliki alamat 32-bit, ruang alamat kami terdiri dari 2 ³² byte yang dapat dialamatkan (4 GB).

Akibatnya, ternyata jumlah byte yang dapat dialamatkan bergantung pada jumlah total baris alamat. Misalnya, jika ada 64 baris alamat (prosesor x86-64), Anda dapat mengatasi 2 ⁶⁴ byte (16 exabytes) memori, tetapi sebagian besar arsitektur yang menggunakan pointer 64-bit sebenarnya menggunakan baris alamat 48-bit (AMD64) dan garis alamat 42-bit (Intel), yang, secara teoritis, memungkinkan komputer untuk dilengkapi dengan 256 terabyte memori fisik (Linux memungkinkan, pada arsitektur x86-64, ketika menggunakan halaman alamat level 4, untuk mengalokasikan hingga 128 TB ruang alamat ke proses, Windows memungkinkan Anda untuk mengalokasikan hingga 192 TB).
Karena ukuran RAM fisik terbatas, setiap proses berjalan di "kotak pasir" sendiri - dalam apa yang disebut "ruang alamat virtual", yang disebut memori virtual.

Alamat byte di ruang alamat virtual tidak cocok dengan alamat yang digunakan prosesor untuk mengakses memori fisik. Akibatnya, kita membutuhkan sistem yang memungkinkan kita untuk mengubah alamat virtual ke alamat fisik. Lihatlah seperti apa alamat memori virtual itu.


Representasi Ruang Alamat Virtual

Akibatnya, ketika prosesor menjalankan instruksi yang merujuk ke alamat memori, langkah pertama adalah menerjemahkan alamat logis ke alamat linier. Konversi ini dilakukan oleh unit manajemen memori.


Representasi yang disederhanakan dari hubungan antara memori virtual dan fisik

Karena alamat logis terlalu besar untuk nyaman digunakan dengan mereka secara terpisah (ini tergantung pada berbagai faktor), memori diatur ke dalam struktur yang disebut halaman. Dalam hal ini, ruang alamat virtual dibagi menjadi area kecil, halaman, yang dalam kebanyakan OS berukuran 4 KB, meskipun biasanya ukuran ini dapat diubah. Ini adalah unit terkecil manajemen memori dalam memori virtual. Memori virtual tidak menyimpan apa pun, ia hanya mengatur korespondensi antara ruang alamat program dan memori fisik.

Proses hanya melihat alamat memori virtual. Apa yang terjadi jika suatu program membutuhkan lebih banyak memori dinamis (juga disebut memori tumpukan, atau "tumpukan")? Berikut adalah contoh kode assembler sederhana di mana tambahan memori yang dialokasikan secara dinamis diminta dari sistem:

_start:        mov $12, %rax #    brk        mov $0, %rdi # 0 -  ,            syscall b0:        mov %rax, %rsi #  rsi    ,           mov %rax, %rdi #     ...        add $4, %rdi # ..  4 ,           mov $12, %rax #    brk        syscall 

Berikut ini cara merepresentasikannya dalam bentuk diagram.


Tambah memori yang dialokasikan secara dinamis

Program meminta memori tambahan menggunakan panggilan sistem brk (sbrk / mmap dan sebagainya). Kernel memperbarui informasi tentang memori virtual, tetapi halaman baru belum disajikan dalam memori fisik, dan di sini ada perbedaan antara memori virtual dan fisik.

Pengalokasi memori

Setelah kita, secara umum, membahas bekerja dengan ruang alamat virtual, berbicara tentang bagaimana cara meminta memori dinamis tambahan (memori pada heap), akan lebih mudah bagi kita untuk berbicara tentang cara mengalokasikan memori.

Jika tumpukan memiliki cukup memori untuk memenuhi permintaan kode kami, maka pengalokasi memori dapat menjalankan permintaan ini tanpa mengakses kernel. Kalau tidak, ia harus menambah ukuran tumpukan menggunakan panggilan sistem (menggunakan brk, misalnya), sambil meminta blok memori yang besar. Dalam kasus malloc, "besar" berarti ukuran yang dijelaskan oleh parameter MMAP_THRESHOLD , yang, secara default, adalah 128 Kb.

Namun, pengalokasi memori memiliki lebih banyak tanggung jawab daripada hanya mengalokasikan memori. Salah satu tanggung jawabnya yang paling penting adalah untuk mengurangi fragmentasi memori internal dan eksternal, dan untuk mengalokasikan blok memori secepat mungkin. Misalkan program kami secara berurutan mengeksekusi permintaan untuk mengalokasikan blok memori yang berkelanjutan menggunakan fungsi form malloc(size) , setelah itu memori ini dibebaskan menggunakan fungsi form free(pointer) .


Demonstrasi fragmentasi eksternal

Dalam diagram sebelumnya, pada langkah p4, kami tidak memiliki cukup blok memori yang ditempatkan secara berurutan untuk memenuhi permintaan alokasi enam blok seperti itu, walaupun jumlah total memori bebas memungkinkan ini. Situasi ini menyebabkan fragmentasi memori.

Bagaimana cara mengurangi fragmentasi memori? Jawaban untuk pertanyaan ini tergantung pada algoritma alokasi memori tertentu, di mana pangkalan perpustakaan digunakan untuk bekerja dengan memori.

Sekarang kita akan melihat alat alokasi memori TCMalloc, yang menjadi dasar mekanisme alokasi memori Go.

TCMalloc

TCMalloc didasarkan pada gagasan membagi memori menjadi beberapa tingkatan untuk mengurangi fragmentasi memori. Di dalam TCMalloc, manajemen memori dibagi menjadi dua bagian: bekerja dengan memori utas dan bekerja dengan heap.

▍ Utas memori

Setiap halaman memori dibagi menjadi urutan fragmen ukuran tertentu, dipilih sesuai dengan kelas ukuran. Ini mengurangi fragmentasi. Akibatnya, setiap utas memiliki cache untuk objek kecil, yang memungkinkan alokasi memori yang sangat efisien untuk objek yang lebih kecil dari atau sama dengan 32 KB.


Tembolok cache

▍Bunch

Tumpukan terkelola TCMalloc adalah kumpulan halaman yang kumpulan halaman berurutannya dapat direpresentasikan sebagai rentang halaman (rentang). Ketika Anda perlu mengalokasikan memori untuk objek yang lebih besar dari 32 KB, heap digunakan untuk mengalokasikan memori.


Tumpukan dan bekerja dengan halaman

Ketika tidak ada cukup ruang untuk menempatkan benda-benda kecil dalam memori, mereka beralih ke tumpukan memori. Jika tumpukan tidak memiliki cukup memori bebas, memori tambahan diminta dari sistem operasi.

Hasilnya, model kerja dengan memori yang disajikan mendukung kumpulan memori ruang pengguna, penggunaannya secara signifikan meningkatkan efisiensi pengalokasian dan membebaskan memori.

Perlu dicatat bahwa alat alokasi memori Go awalnya didasarkan pada TCMalloc, tetapi sedikit berbeda dari itu.

Buka pengalokasi memori

Kita tahu bahwa Go runtime berencana untuk menjalankan goroutine pada prosesor logis. Demikian pula, versi TCMalloc yang digunakan oleh Go membagi halaman memori menjadi blok-blok yang ukurannya sesuai dengan kelas ukuran tertentu yang ada.

Jika Anda tidak terbiasa dengan penjadwal Go , Anda dapat membacanya di sini .


Pergi kelas ukuran

Karena ukuran halaman minimum di Go adalah 8192 byte (8 Kb), jika halaman tersebut dibagi menjadi blok 1 KB, maka kita akan mendapatkan 8 blok seperti itu.


Ukuran halaman 8 KB dibagi menjadi blok yang sesuai dengan ukuran kelas 1 KB

Urutan halaman serupa di Go dikendalikan menggunakan struktur yang disebut mspan.

Trtruktur mspan

Struktur mspan adalah daftar tertaut ganda, objek yang berisi alamat awal halaman, informasi tentang ukuran halaman dan jumlah halaman yang termasuk di dalamnya.


Struktur mspan

▍ struktur mcache

Seperti TCMalloc, Go memberikan setiap cache prosesor logis dengan thread lokal, yang dikenal sebagai mcache. Akibatnya, jika goroutine membutuhkan memori, ia bisa mendapatkannya langsung dari mcache. Untuk melakukan ini, Anda tidak perlu melakukan kunci, karena pada waktu tertentu hanya satu goroutin dijalankan pada satu prosesor logis.

Struktur mcache berisi, dalam bentuk cache, struktur mspan dari berbagai kelas ukuran.


Interaksi antara prosesor logis, mcache dan mspan di Go

Karena setiap prosesor logis memiliki mcache sendiri, tidak perlu kunci ketika mengalokasikan memori dari mcache.

Setiap kelas ukuran dapat diwakili oleh salah satu objek berikut:

• Objek pindai adalah objek yang berisi pointer.
• Objek noscan adalah objek di mana tidak ada pointer.

Salah satu kekuatan dari pendekatan ini adalah ketika pengumpulan sampah dilakukan, objek noscan tidak perlu dielakkan, karena mereka tidak mengandung objek yang dialokasikan memori.

Apa yang masuk ke mcache? Objek yang ukurannya tidak melebihi 32 KB langsung ke mcache menggunakan mspan dari kelas ukuran yang sesuai.

Apa yang terjadi jika mcache tidak memiliki sel bebas? Kemudian mereka mendapatkan mspan baru dari kelas ukuran yang diinginkan dari daftar objek mspan yang disebut mcentral.

Structure Struktur pusat

Struktur mcentral mengumpulkan semua rentang halaman dari kelas ukuran tertentu. Setiap objek mcentral berisi dua daftar objek mspan.

1. Daftar objek mspan di mana tidak ada objek gratis, atau orang-orang mspan yang ada di mcache.
2. Daftar objek mspan yang memiliki objek gratis.

Struktur Mcentral

Setiap struktur mcentral ada di dalam struktur mheap.

He Struktur tumpukan

Struktur mheap diwakili oleh objek yang menangani manajemen heap di Go. Hanya ada satu objek global yang memiliki ruang alamat virtual.


Struktur tumpukan

Seperti yang dapat Anda lihat dari diagram di atas, struktur mheap berisi larik struktur mcentral. Array ini mengandung struktur mcentral untuk semua kelas ukuran.

 central [numSpanClasses]struct { mcentral mcentral   pad     [sys.CacheLineSize unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte } 

Karena kami memiliki struktur mcentral untuk setiap kelas ukuran, ketika mcache meminta struktur mspan dari mcentral, sebuah kunci diterapkan pada tingkat mcentral individu, sebagai akibatnya, permintaan dari mcache lain yang meminta struktur mspan dari ukuran lain dapat dilayani pada waktu yang bersamaan.

Alignment (pad) memastikan bahwa struktur mcentral dipisahkan satu sama lain dengan jumlah byte yang sesuai dengan nilai CacheLineSize . Akibatnya, setiap mcentral.lock memiliki garis cache sendiri, yang menghindari masalah yang terkait dengan berbagi memori palsu.

Apa yang terjadi jika daftar mcentral kosong? Kemudian mcentral menerima urutan halaman dari mheap untuk mengalokasikan fragmen memori dari kelas ukuran yang diperlukan.

• free[_MaxMHeapList]mSpanList adalah array spanList. Struktur mspan di setiap spanList terdiri dari 1 ~ 127 (_MaxMHeapList - 1) halaman. Misalnya, gratis [3] adalah daftar tertaut dari struktur mspan yang berisi 3 halaman. Kata "bebas" dalam hal ini menunjukkan bahwa kita berbicara tentang daftar kosong di mana memori tidak dialokasikan. Daftar dapat, sebagai lawan kosong, daftar di mana memori dialokasikan (sibuk).
• freelarge mSpanList adalah daftar struktur mspan gratis. Jumlah halaman per elemen (yaitu, mspan) lebih dari 127. Untuk mendukung daftar ini, struktur data mtreap digunakan. Daftar struktur mspan yang sibuk disebut busylarge.

Objek yang lebih besar dari 32 Kb dianggap objek besar, memori untuk mereka dialokasikan langsung dari mheap. Permintaan untuk mengalokasikan memori untuk objek tersebut dilakukan menggunakan kunci, sebagai akibatnya, pada titik waktu tertentu, permintaan serupa dapat diproses dari hanya satu prosesor logis.

Proses mengalokasikan memori untuk objek

• Jika ukuran objek melebihi 32 Kb, itu dianggap besar, memori untuk itu dialokasikan langsung dari mheap.
• Jika ukuran objek kurang dari 16 Kb, mekanisme mcache yang disebut pengalokasi kecil digunakan.
• Jika ukuran objek berada dalam kisaran 16-32 Kb, ternyata kelas ukuran mana (sizeClass) yang akan digunakan, maka blok yang sesuai dialokasikan di mcache.
• Jika tidak ada blok yang tersedia di sizeClass yang sesuai dengan mcache, mcentral dipanggil.
• Jika mcentral tidak memiliki blok gratis, maka mereka memanggil mheap dan mencari mspan yang paling cocok. Jika ukuran memori yang dibutuhkan oleh aplikasi ternyata lebih besar daripada yang mungkin untuk dialokasikan, ukuran memori yang diminta akan diproses sehingga akan mungkin untuk mengembalikan halaman sebanyak yang dibutuhkan oleh program, setelah membentuk struktur mspan baru.
• Jika memori virtual aplikasi masih tidak cukup, sistem operasi diakses untuk set halaman baru (minimal 1 MB memori diminta).

Bahkan, pada level sistem operasi, Go meminta alokasi memori yang lebih besar yang disebut arena. Alokasi serentak fragmen memori yang besar memungkinkan Anda menemukan kompromi antara jumlah memori yang dialokasikan untuk aplikasi dan akses yang mahal ke sistem operasi dalam hal kinerja.

Memori yang diminta pada heap dialokasikan dari arena. Pertimbangkan mekanisme ini.

Memori virtual pergi

Lihatlah penggunaan memori dengan program sederhana yang ditulis dalam Go:

 func main() {   for {} } 

Informasi Proses Program

Ruang alamat virtual bahkan dari program yang sederhana ini adalah sekitar 100 MB, sedangkan indeks RSS hanya 696 Kb. Pertama, mari kita cari tahu alasan perbedaan ini.


Memetakan dan menampar informasi

Di sini Anda dapat melihat area memori, yang ukurannya kira-kira sama dengan 2 MB, 64 MB, 32 MB. Memori seperti apa ini?

RArena

Ternyata memori virtual di Go terdiri dari seperangkat arena. Ukuran memori awal yang dimaksudkan untuk tumpukan sesuai dengan satu arena, yaitu - 64 MB (ini relevan untuk Go 1.11.5).


Ukuran arena saat ini dalam berbagai sistem

Akibatnya, memori yang dibutuhkan untuk kebutuhan program saat ini dialokasikan dalam porsi kecil. Proses ini dimulai dengan satu arena 64 MB.

Indikator numerik yang kita bicarakan di sini tidak boleh diambil untuk beberapa nilai absolut dan tidak berubah. Mereka bisa berubah. Sebelumnya, misalnya, Go mencadangkan ruang virtual terus-menerus di muka, pada sistem 64-bit ukuran arena adalah 512 GB (Sangat menarik untuk memikirkan apa yang terjadi jika permintaan memori aktual begitu besar sehingga permintaan yang sesuai akan ditolak oleh mmap?).

Faktanya, kami menyebut banyak arena sebagai satu kesatuan. Di Go, arena dianggap sebagai fragmen memori, dibagi menjadi blok berukuran 8192 byte (8 Kb).


Satu arena 64 MB

Go memiliki beberapa rasa blok - span dan bitmap. Memori untuk mereka dialokasikan di luar heap, mereka menyimpan arena metadata. Mereka terutama digunakan dalam pengumpulan sampah.
Berikut adalah garis besar umum tentang bagaimana mekanisme alokasi memori bekerja di Go.


Garis besar umum mekanisme alokasi memori di Go

Ringkasan

Secara umum, dapat dicatat bahwa dalam materi ini kami menggambarkan subsistem untuk bekerja dengan memori Go dalam istilah yang sangat umum. Ide utama subsistem memori di Go adalah mengalokasikan memori menggunakan berbagai struktur dan cache dari berbagai tingkatan. Ini memperhitungkan ukuran objek yang dialokasikan memori.

Representasi satu blok alamat memori kontinu yang diterima dari sistem operasi dalam bentuk struktur multi-level meningkatkan efisiensi mekanisme alokasi memori karena fakta bahwa pendekatan ini menghindari pemblokiran. Alokasi sumber daya, dengan mempertimbangkan ukuran objek yang perlu disimpan dalam memori, mengurangi fragmentasi, dan, setelah membebaskan memori, memungkinkan Anda untuk mempercepat pengumpulan sampah.

Pembaca yang budiman! Pernahkah Anda mengalami masalah yang disebabkan oleh tidak berfungsinya memori dalam program yang ditulis dalam Go?