Penulis | herongwei
Editor | Tu Min
Kata pengantar
1. Apa itu ruang Pengguna dan ruang Kernel?
2. Berapakah area tumpukan?
3. Apa yang dimaksud dengan area heap?
4. Bagaimana algoritma malloc diimplementasikan?
5. Berapa banyak metode alokasi ruang heap yang ada di sistem Linux?
6. Apa tata letak ruang alamat proses di Linux?
Apakah Anda memiliki jawaban atas pertanyaan di atas? Jika tidak, datang dan jelajahi dengan saya.
Ruang pengguna dan ruang Kernel
Aplikasi modern berjalan dalam ruang memori Dalam sistem 32-bit, ruang memori ini memiliki kemampuan pengalamatan 4GB (2 pangkat 32).
Meskipun konfigurasi ruang memori sebagian besar komputer semakin tinggi, pada kenyataannya, memori masih memiliki posisi berbeda dalam rentang alamat yang berbeda. Sebagai contoh, sebagian besar sistem operasi akan mentransfer sebagian dari ruang memori 4GB ke kernel untuk digunakan, dan aplikasi tidak dapat Akses langsung ke bagian memori ini, bagian dari alamat memori ini disebut ruang kernel.
Secara default, Windows mengalokasikan 2GB ruang alamat tinggi ke kernel (1GB juga dapat dikonfigurasi).
Linux mengalokasikan 1GB ruang alamat tinggi ke kernel secara default.
Sisa ruang memori 2GB atau 3GB yang digunakan oleh pengguna disebut ruang pengguna.
Mengapa membedakan antara ruang kernel dan ruang pengguna?
Secara kasar ada tiga faktor:
Poin pertama: data sistem operasi disimpan di ruang sistem, dan data proses pengguna disimpan di ruang pengguna;
Poin kedua: penyimpanan terpisah, sehingga data sistem dan data pengguna tidak saling mengganggu, memastikan stabilitas sistem, dan manajemen sangat nyaman;
Poin ketiga: Ini juga poin penting Memisahkan data pengguna dari data sistem dapat mengontrol akses ke dua bagian data. Dengan cara ini, dapat dipastikan bahwa program pengguna tidak dapat dengan mudah mengoperasikan data sistem operasi, sehingga mencegah program pengguna dari kesalahan pengoperasian atau kerusakan berbahaya pada sistem.
Gambar berikut menjelaskan perbedaan antara User space dan Kernel space dengan lebih jelas.
Poin pertama: data sistem operasi disimpan di ruang sistem, dan data proses pengguna disimpan di ruang pengguna;
Sederhananya, ruang Kernel adalah ruang operasi dari kernel Linux, dan ruang Pengguna adalah ruang operasi program pengguna. Demi keamanan, mereka diisolasi, bahkan jika program pengguna lumpuh, kernel tidak terpengaruh.
Ruang kernel dapat menjalankan perintah sewenang-wenang dan memanggil semua sumber daya sistem;
Secara relatif, ruang Pengguna melakukan operasi yang relatif sederhana. Operasi yang dilakukan tidak mempengaruhi pelaksanaan program lain, dan tidak dapat secara langsung memanggil sumber daya sistem. Antarmuka sistem (juga dikenal sebagai panggilan sistem) harus digunakan untuk mengeluarkan instruksi ke kernel.
Berikut suplemen untuk mengetahui komentar netizen @ :
Faktanya, di ruang pengguna, hampir semua sumber daya kernel dapat diakses di ruang pengguna (harus memiliki izin yang sesuai), bahkan otak kernel sistem operasi (penjadwal).
Tata letak ruang alamat proses Linux
Di ruang pengguna, ada juga banyak rentang alamat yang berstatus privileged. Secara umum, ruang memori yang digunakan oleh aplikasi memiliki area "default" berikut.
Area tumpukan: Tumpukan digunakan untuk mempertahankan konteks panggilan fungsi. Jika Anda meninggalkan tumpukan, panggilan fungsi tidak dapat diterapkan. Tumpukan biasanya dialokasikan di alamat tertinggi dalam ruang pengguna, biasanya berukuran beberapa megabyte.
Area tumpukan: Heap digunakan untuk menampung area memori yang dialokasikan secara dinamis oleh aplikasi.Ketika program menggunakan malloc atau new untuk mengalokasikan memori, memori akan berasal dari heap.
Heap biasanya ada di bawah tumpukan (arah alamat rendah), dan dalam beberapa kasus, heap mungkin tidak memiliki area penyimpanan tetap dan terpadu. Heap umumnya jauh lebih besar daripada tumpukan, dan dapat memiliki kapasitas puluhan hingga ratusan megabyte.
Gambar file yang dapat dijalankan: Gambar dari file yang dapat dieksekusi dalam memori disimpan, dan memori dari file yang dapat dieksekusi dibaca atau dipetakan di sini oleh loader saat memuat.
Area reservasi: Area yang dicadangkan bukanlah area memori tunggal, tetapi istilah umum untuk area memori yang dilindungi dan dilarang untuk diakses: Misalnya, di sebagian besar sistem operasi, alamat yang sangat kecil biasanya tidak diizinkan untuk diakses. Misalnya, bahasa C akan Penetapan petunjuk yang tidak valid ke 0 juga menjadi pertimbangan.
Area pemetaan perpustakaan tautan dinamis: Area ini digunakan untuk memetakan pustaka tautan dinamis yang dimuat. Di Linux, jika file yang dapat dieksekusi bergantung pada pustaka bersama lainnya, sistem akan mengalokasikan ruang yang sesuai untuk alamat mulai dari 0x40000000, dan memuat pustaka bersama ke ruang ini.
Sisanya terdiri dari bagian-bagian berikut:
(1) Segmen kode
(2) Inisialisasi segmen data (data segment)
(3) Segmen data yang tidak diinisialisasi (segmen BSS)
Gambar di bawah ini adalah tata letak memori tipikal dalam proses di Linux
Panah pada gambar menunjukkan arah pertumbuhan beberapa ukuran variabel. Di sini, Anda dapat melihat dengan jelas:
Tumpukan tumbuh dari alamat tinggi ke alamat rendah.
Heap berkembang dari alamat rendah ke alamat tinggi.
Jika ukuran tumpukan atau heap yang ada tidak mencukupi, ukurannya akan diperluas sesuai dengan arah pertumbuhan pada gambar hingga ruang yang dicadangkan habis.
Sebelum berbicara tentang heap dan stack, mari kita lihat segmen kode, segmen data yang diinisialisasi, dan segmen data yang tidak diinisialisasi.
Cuplikan kode
Instruksi yang dapat dieksekusi disimpan dalam segmen kode. Untuk memastikan bahwa instruksi tersebut tidak akan ditimpa karena stack overflow, instruksi tersebut ditempatkan di bawah segmen stack (seperti yang dapat dilihat pada gambar di atas).
Secara umum, segmen kode dibagikan, sehingga instruksi yang berulang kali dieksekusi beberapa kali hanya perlu memiliki satu salinan di memori, seperti kompiler C, editor teks, dll.
Segmen kode umumnya hanya-baca, sehingga instruksi tidak dapat diubah sesuka hati selama eksekusi program, yang juga untuk perlindungan isolasi.
Inisialisasi segmen data
Segmen data inisialisasi terkadang disebut segmen data. Segmen data adalah bagian dari ruang alamat virtual suatu program, termasuk variabel global dan variabel statis, variabel ini telah diinisialisasi selama pemrograman. Segmen data dapat dimodifikasi, jika tidak variabel tidak dapat diubah saat program berjalan, yang berbeda dari segmen kode.
Segmen data dapat dibagi lagi menjadi area read-only yang diinisialisasi dan area baca-tulis yang diinisialisasi. Ini konsisten dengan beberapa variabel khusus dalam pemrograman. Misalnya, variabel global int global n = 1 ditempatkan di area inisialisasi baca-tulis, karena global dapat dimodifikasi. Dan const int m = 2 akan ditempatkan di area read-only. Jelas, m tidak dapat dimodifikasi.
Tumpukan
Stack (stack) adalah salah satu konsep terpenting dalam program komputer modern. Hampir setiap program menggunakan stack. Tanpa stack, tidak akan ada fungsi, tidak ada variabel lokal, dan tidak ada bahasa komputer yang dapat kita lihat saat ini.
Sebelum menjelaskan mengapa tumpukan sangat penting, mari kita pahami dulu definisi tumpukan tradisional:
Dalam ilmu komputer klasik, tumpukan didefinisikan sebagai wadah khusus. Pengguna dapat mendorong data ke dalam tumpukan (push, push), atau data pop yang telah didorong ke dalam tumpukan (pop, pop).
Tetapi penampung tumpukan harus mematuhi aturan: Data yang dimasukkan ke dalam stack adalah first in last out (First In Last Out, FIFO) yang kurang lebih seperti tumpukan buku: buku yang ditumpuk lebih dulu ada di paling bawah: jadi harus dikeluarkan terakhir.
Dalam sistem komputer, tumpukan adalah area memori dinamis dengan atribut di atas. Program dapat mendorong data ke dalam tumpukan atau mengeluarkan data dari atas tumpukan. Operasi dorong membuat tumpukan bertambah, dan operasi sembulan membuat tumpukan berkurang .
Dalam sistem operasi klasik, tumpukan selalu tumbuh ke bawah.
Di bawah i386, bagian atas tumpukan terletak oleh sebuah register bernama esp. Operasi mendorong tumpukan mengurangi alamat bagian atas tumpukan, dan operasi popping meningkatkan alamat bagian atas tumpukan.
Di sini alamat bagian bawah tumpukan adalah 0xbffff, dan register esp menunjukkan bagian atas tumpukan, dan alamatnya adalah 0xbifff4.
Mendorong data pada stack akan menyebabkan esp berkurang, dan data popping akan menyebabkan esp meningkat.
Tumpukan memainkan peran penting dalam operasi program. Yang terpenting, tumpukan menyimpan informasi pemeliharaan yang diperlukan untuk panggilan fungsi. Ini sering disebut bingkai tumpukan atau catatan aktivasi. Bingkai tumpukan umumnya mencakup aspek-aspek berikut:
1. Alamat pengirim dan parameter fungsi.
2. Variabel sementara: termasuk variabel fungsi lokal non-statis dan variabel sementara lainnya yang secara otomatis dibuat oleh kompilator.
3. Konteks yang disimpan: termasuk register yang harus tetap tidak berubah sebelum dan sesudah pemanggilan fungsi.
tumpukan
Dibandingkan dengan tumpukan, memori heap menghadapi pola perilaku yang sedikit lebih rumit: kapan saja, program dapat membuat permintaan, baik menerapkan bagian memori, atau melepaskan bagian memori yang telah diterapkan, dan ukuran aplikasi berkisar dari beberapa byte hingga Beberapa gigabyte dimungkinkan.
Kami tidak dapat mengasumsikan berapa banyak ruang heap yang akan diterapkan program pada suatu waktu. Oleh karena itu, peran heap disorot saat ini. Demikian pula, dibandingkan dengan tumpukan, pengelolaan heap lebih rumit.
Tumpukan saja tidak cukup untuk pemrograman berorientasi proses, karena data pada tumpukan akan dirilis saat fungsi kembali, sehingga data tidak dapat diteruskan ke luar fungsi. Variabel global tidak dapat dibuat secara dinamis. Variabel tersebut hanya dapat ditentukan pada waktu kompilasi. Ada banyak kasus yang kurang ekspresif. Dalam kasus ini, Heap adalah satu-satunya pilihan.
Heap adalah ruang memori besar yang sering menempati sebagian besar ruang virtual. Di ruang ini, program dapat meminta memori berkelanjutan dan menggunakannya secara bebas. Memori ini akan tetap valid hingga program menyerah secara sukarela. , Berikut adalah contoh penerapan paling sederhana untuk ruang heap:
int utama { char * p = (char *) malloc (233); gratis (p); kembali 0; }Dalam kode, setelah menerapkan malloc untuk 233 byte ruang pada baris 3, program dapat dengan bebas menggunakan 233 byte ini sampai program melepaskannya dengan fungsi bebas.
Jadi bagaimana malloc diimplementasikan?
Salah satu caranya adalah dengan menyerahkan manajemen memori proses ke kernel sistem operasi Karena kernel mengelola ruang alamat proses, jika kernel menyediakan panggilan sistem, program dapat menggunakan panggilan sistem ini untuk menerapkan memori. ?
Tentu saja, ini adalah pendekatan yang secara teoritis dapat dilakukan, tetapi pada kenyataannya, kinerja melakukannya relatif buruk, karena setiap kali program meminta atau melepaskan ruang heap, panggilan sistem diperlukan.
Kita tahu bahwa overhead kinerja panggilan sistem sangat besar. Ketika program beroperasi pada heap secara sering, akibatnya akan sangat mempengaruhi kinerja program.
Pendekatan yang lebih baik adalah: Program ini berlaku untuk sistem operasi untuk jumlah ruang heap yang sesuai, dan kemudian program mengelola ruang ini dengan sendirinya. Secara khusus, pengelolaan alokasi ruang heap sering kali merupakan operasi program Perpustakaan.
Pustaka runtime setara dengan "grosir" ruang heap yang lebih besar ke sistem operasi, dan kemudian "eceran" untuk program.
Ketika semuanya "terjual habis" atau program memiliki banyak kebutuhan memori, maka "beli" sistem operasi tersebut sesuai dengan kebutuhan sebenarnya.
Tentu saja, saat pustaka runtime meretail ruang heap ke program, ia harus mengelola ruang heap grosirnya, dan tidak dapat menjual alamat yang sama dua kali, yang menyebabkan konflik alamat.
Manajemen heap proses Linux
Seperti yang dapat dilihat dari bagian pertama, dalam ruang alamat proses, kecuali untuk file yang dapat dieksekusi, perpustakaan bersama, dan tumpukan, ruang yang tidak terisi dapat digunakan sebagai ruang heap.
Di sistem Linux, tersedia dua metode alokasi ruang heap:
panggilan sistem brk dan panggilan sistem mmap.
Kedua metode ini mengalokasikan memori virtual, bukan memori fisik. Saat mengakses ruang alamat virtual yang dialokasikan untuk pertama kalinya, terjadi interupsi kesalahan halaman, dan sistem operasi bertanggung jawab untuk mengalokasikan memori fisik, dan kemudian menetapkan hubungan pemetaan antara memori virtual dan memori fisik.
Di library C standar, fungsi malloc / free disediakan untuk mengalokasikan dan melepaskan memori. Lapisan bawah dari kedua fungsi ini diimplementasikan oleh panggilan sistem seperti brk, mmap, dan munmap.
panggilan sistem brk
Pernyataan formulir bahasa C: int brk {void * end_data_segment;}
Peran brk sebenarnya untuk mengatur alamat akhir dari segmen data proses, yaitu dapat memperluas atau mengecilkan segmen data (segmen data dan BBS di Linux digabungkan bersama dan secara kolektif disebut sebagai segmen data).
Jika kita memindahkan alamat akhir dari segmen data ke alamat yang lebih tinggi, maka bagian ruang yang diperbesar dapat kita gunakan. Ini adalah praktik yang paling umum untuk mengambil ruang ini dan menggunakannya sebagai ruang heap.
panggilan sistem mmap
Ini sangat mirip dengan VirtualAlloc di sistem Windows. Fungsinya untuk menerapkan ruang alamat virtual dari sistem operasi. Ruang alamat virtual ini (antara heap dan stack, disebut area pemetaan file) dapat dipetakan ke sebuah file.
Fungsi malloc dari glibc menangani permintaan ruang pengguna seperti ini: Untuk permintaan yang lebih kecil dari 128KB, ia akan mengalokasikan ruang di ruang heap yang ada sesuai dengan algoritma alokasi heap dan kembali; untuk permintaan yang lebih besar dari 128KB , Ini akan menggunakan fungsi mmap untuk mengalokasikan ruang anonim untuknya, dan kemudian mengalokasikan ruang untuk pengguna di ruang anonim ini.
Pernyataannya adalah sebagai berikut:
void * mmap { batal * mulai; size_t length; int prot; bendera int; int fd; off_t offset; }Dua parameter pertama mmap digunakan untuk menentukan alamat awal dan panjang ruang yang akan diterapkan. Jika alamat awal disetel ke 0, sistem Linux akan secara otomatis memilih alamat awal yang sesuai.
Parameter prot / flags: digunakan untuk mengatur hak akses ruang yang diminta (dapat dibaca, ditulis, dieksekusi) dan jenis pemetaan (pemetaan file, ruang anonim, dll.).
Dua parameter terakhir digunakan untuk deskriptor file dan offset file yang ditentukan selama pemetaan file.
Setelah memahami manajemen heap sistem Linux, kita dapat memikirkan pertanyaan ini:
Berapa jumlah ruang maksimum yang dapat diajukan malloc pada satu waktu?
Untuk menjawab pertanyaan ini, saya harus kembali dan mempelajari gambar 1 sebelumnya. Kita dapat melihat bahwa dalam kasus pustaka bersama, ada dua ruang tersisa untuk heap.
Yang pertama adalah dari ujung segmen BSS hingga 0x40.000.000, yaitu sekitar 1GB kurang dari ruang;
Tempat kedua adalah ruang dari pustaka bersama ke tumpukan, yang kurang dari 2GB. Ukuran kedua bagian ruang ini bergantung pada ukuran dan jumlah tumpukan dan perpustakaan bersama.
Oleh karena itu, dapat diperkirakan bahwa ruang aplikasi maksimum untuk malloc kurang dari 2GB. (Linux kernel versi 2.4).
Tentu saja, ada banyak faktor lain yang mempengaruhi ukuran maksimal malloc, seperti batasan sumber daya sistem (ulimit), jumlah memori fisik dan ruang swap, dll.
Jika mmap berlaku untuk ruang anonim, sistem akan mencadangkan alamatnya di memori atau ruang swap, tetapi ukuran ruang yang diminta tidak boleh melebihi jumlah memori bebas + ruang swap kosong.
Algoritme alokasi heap
1. Metode daftar tertaut gratis (yaitu, panggil malloc untuk mengalokasikan)
Ini untuk menghubungkan blok gratis di heap dalam daftar tertaut. Saat pengguna meminta sepotong ruang, seluruh daftar dapat dilintasi hingga blok dengan ukuran yang sesuai ditemukan dan dipecah; ketika pengguna melepaskan ruang, itu digabung menjadi Daftar gratis.
Daftar tertaut gratis adalah struktur di mana terdapat header di awal (atau akhir) dari setiap ruang kosong di heap. Alamat blok bebas sebelumnya (sebelumnya) dan berikutnya (berikutnya) dicatat dalam struktur header. Dengan kata lain, semua blok gratis membentuk daftar tertaut. seperti yang ditunjukkan gambar.
Rencana implementasi khusus:
-
Inti dari fungsi malloc adalah ia memiliki apa yang disebut daftar tertaut gratis yang menghubungkan blok memori yang tersedia ke dalam daftar panjang.
-
Saat fungsi malloc dipanggil, ia mencari blok memori yang cukup besar untuk memenuhi permintaan pengguna di sepanjang tabel koneksi. Kemudian, bagi blok memori menjadi dua (ukuran satu blok sama dengan ukuran yang diminta oleh pengguna, dan ukuran blok lainnya adalah byte yang tersisa). Selanjutnya, teruskan area penyimpanan memori yang dialokasikan untuk pengguna ke pengguna, dan kembalikan sisanya (jika ada) ke tabel koneksi.
-
Saat memanggil fungsi gratis, ini menghubungkan blok memori yang dilepaskan oleh pengguna ke daftar tertaut gratis.
-
Pada akhirnya, rantai bebas akan dipotong menjadi banyak fragmen memori kecil. Jika pengguna mengajukan permohonan untuk fragmen memori besar saat ini, mungkin tidak ada fragmen yang dapat memenuhi persyaratan pengguna pada daftar tertaut gratis. Oleh karena itu, fungsi malloc meminta penundaan, dan mulai memeriksa setiap segmen memori pada daftar tertaut gratis, mengatur memorinya, dan menggabungkan blok kecil bebas yang berdekatan menjadi blok memori yang lebih besar.
2. Metode bitmap
Mengingat kekurangan dari daftar idle, metode alokasi lain lebih kuat. Metode ini disebut Bitmap, dan ide intinya adalah membagi seluruh heap menjadi sejumlah besar blok, yang masing-masing memiliki ukuran yang sama.
Ketika seorang pengguna meminta memori, sejumlah bilangan bulat blok selalu dialokasikan ke pengguna. Blok pertama disebut kepala dari area yang dialokasikan, dan sisanya disebut badan dari area yang dialokasikan, dan kita bisa Array integer digunakan untuk mencatat penggunaan blok, karena setiap blok hanya memiliki tiga status: head / body / idle, hanya dua bit yang dibutuhkan untuk merepresentasikan sebuah blok, jadi ini disebut bitmap.
3. Kumpulan objek
Metode lain adalah kumpulan objek, yang juga membagi ruang heap menjadi blok-blok dengan ukuran yang sama. Ia menganggap bahwa ruang yang dialokasikan setiap waktu dalam beberapa kasus adalah sama, sehingga secara langsung mengembalikan ukuran blok setiap kali. Metode pengelolaannya dapat diubah Daftar tertaut juga bisa berupa bitmap. Karena tidak perlu mencari ukuran memori yang sesuai setiap kali mengembalikan, ini sangat efisien.
Faktanya, dalam banyak aplikasi praktis, algoritme alokasi heap sering kali terdiri dari beberapa algoritme.
Misalnya, untuk glibc, ia menggunakan metode yang mirip dengan kumpulan objek untuk aplikasi ruang kurang dari 64 byte.
Untuk aplikasi ruang yang lebih besar dari 512 byte, digunakan algoritma adaptasi terbaik;
Untuk yang lebih besar dari 64 byte tetapi lebih kecil dari 512 byte, itu akan mengadopsi strategi kompromi terbaik dalam metode di atas sesuai dengan situasinya;
Untuk aplikasi yang lebih besar dari 128KB, ini akan menggunakan mekanisme mmap untuk langsung mengajukan ruang dari sistem operasi.
Bahan referensi:
-
"Pengembangan Diri Programmer"
-
- Platform Seluler Baidu Menutup Saluran Android; Apple Akan Mendorong iPhone SE 2; Microsoft Open Sources Scalar | Berita Utama Geek
- Pembelajaran mesin mendominasi daftar gaji tinggi, dan blockchain sudah mati? Interpretasi status insinyur perangkat lunak pada tahun 2020
- Hitung tiga "kejahatan" Python! Mengapa orang yang memiliki kemampuan pemrograman 10 kali lebih baik dari saya memujinya?
- Kementerian Pendidikan mengumumkan daftar usulan 200 Pengawas Sekolah Nasional ke-11 dan 300 Pengawas Pendidikan Khusus
- mengucapkan selamat! 7 Alumni Universitas Peking memenangkan Penghargaan Penelitian Sloan "Nobel Vane"