Mengapa tumpukan panggilan memiliki ukuran maksimum statis?

Setelah bekerja dengan beberapa bahasa pemrograman, saya selalu bertanya-tanya mengapa tumpukan thread memiliki ukuran maksimum yang telah ditentukan, daripada berkembang secara otomatis seperti yang diperlukan. 

Sebagai perbandingan, struktur tingkat tinggi tertentu yang sangat umum (daftar, peta, dll.) Yang ditemukan di sebagian besar bahasa pemrograman dirancang untuk tumbuh sesuai kebutuhan sementara elemen baru ditambahkan, dibatasi ukurannya hanya oleh memori yang tersedia, atau oleh batas komputasi ( mis. pengalamatan 32 bit).

Saya tidak mengetahui adanya bahasa pemrograman atau lingkungan runtime di mana ukuran stack maksimum tidak dibatasi oleh beberapa opsi default atau compiler. Inilah sebabnya mengapa terlalu banyak rekursi akan menghasilkan sangat cepat dalam kesalahan / pengecualian stack overflow yang ada di mana-mana, bahkan ketika hanya sebagian kecil dari memori yang tersedia untuk suatu proses digunakan untuk stack.

Mengapa demikian bahwa sebagian besar (jika tidak semua) lingkungan runtime menetapkan batas maksimum untuk ukuran tumpukan dapat tumbuh saat runtime?

Dimungkinkan untuk menulis sistem operasi yang tidak memerlukan tumpukan agar berdekatan di ruang alamat. Pada dasarnya Anda perlu sedikit mengotak-atik konvensi pemanggilan, untuk memastikan bahwa:

1. jika tidak ada ruang yang cukup di tingkat stack saat ini untuk fungsi yang Anda panggil, maka Anda membuat batas stack baru dan memindahkan pointer stack untuk menunjuk ke permulaan sebagai bagian dari membuat panggilan.

2. ketika Anda kembali dari panggilan itu, Anda mentransfer kembali ke tingkat tumpukan asli. Kemungkinan besar Anda mempertahankan yang dibuat pada (1) untuk digunakan di lain waktu oleh utas yang sama. Pada prinsipnya Anda bisa melepaskannya, tetapi dengan cara itu terletak kasus yang agak tidak efisien di mana Anda terus melompat-lompat melintasi batas dalam satu lingkaran, dan setiap panggilan membutuhkan alokasi memori.

3. setjmpdan longjmp, atau apa pun yang setara dengan OS Anda untuk transfer kontrol non-lokal, ikut serta dan dapat dengan benar kembali ke tingkat stack lama bila diperlukan.

Saya mengatakan "konvensi panggilan" - untuk lebih spesifik saya pikir itu mungkin lebih baik dilakukan dalam prolog fungsi daripada oleh penelepon, tetapi ingatan saya tentang hal ini kabur.

Alasan mengapa beberapa bahasa menentukan ukuran stack tetap untuk utas, adalah karena mereka ingin bekerja menggunakan stack asli, pada OS yang tidak melakukan ini. Seperti jawaban orang lain katakan, dengan asumsi bahwa setiap tumpukan harus bersebelahan dalam ruang alamat, dan tidak dapat dipindahkan, Anda perlu memesan rentang alamat tertentu untuk digunakan oleh setiap utas. Itu berarti memilih ukuran di depan. Bahkan jika ruang alamat Anda besar dan ukuran yang Anda pilih sangat besar, Anda masih harus memilihnya segera setelah Anda memiliki dua utas.

"Aha," katamu, "OS apa yang seharusnya menggunakan tumpukan yang tidak bersebelahan ini? Aku yakin itu adalah sistem akademik yang tidak berguna yang tidak berguna bagiku!". Nah, itu pertanyaan lain yang untungnya sudah ditanyakan dan dijawab.

Struktur data tersebut biasanya memiliki properti yang belum dimiliki oleh tumpukan OS:

• Daftar tertaut tidak memerlukan ruang alamat yang berdekatan. Sehingga mereka dapat menambahkan sepotong memori dari mana saja mereka inginkan ketika mereka tumbuh.

• Bahkan koleksi yang membutuhkan penyimpanan yang berdekatan, seperti vektor C ++, memiliki keunggulan dibandingkan tumpukan OS: Mereka dapat mendeklarasikan semua pointer / iterator tidak valid setiap kali mereka tumbuh. Di sisi lain tumpukan OS perlu menjaga pointer ke tumpukan valid sampai fungsi yang frame miliknya dikembalikan.

Bahasa pemrograman atau runtime dapat memilih untuk mengimplementasikan tumpukan mereka sendiri yang tidak bersebelahan atau bergerak untuk menghindari keterbatasan tumpukan OS. Golang menggunakan tumpukan khusus untuk mendukung jumlah rutinitas yang sangat tinggi, yang awalnya diimplementasikan sebagai memori yang tidak bersebelahan dan sekarang melalui tumpukan bergerak berkat pelacakan pointer (lihat komentar hobb). Python tanpa tumpukan, Lua dan Erlang mungkin juga menggunakan tumpukan kustom, tapi saya tidak mengkonfirmasi itu.

Pada sistem 64-bit Anda dapat mengkonfigurasi tumpukan yang relatif besar dengan biaya yang relatif rendah, karena ruang alamat banyak dan memori fisik hanya dialokasikan ketika Anda benar-benar menggunakannya.

Dalam prakteknya, sulit (dan kadang-kadang tidak mungkin) untuk menumbuhkan tumpukan. Untuk memahami mengapa diperlukan beberapa pemahaman tentang memori virtual.

Dalam Ye Olde Days aplikasi single-threaded dan memori yang berdekatan, tiga adalah tiga komponen ruang alamat proses: kode, heap, dan stack. Bagaimana ketiganya diletakkan tergantung pada OS, tetapi umumnya kodenya lebih dulu, mulai dari dasar memori, tumpukan berikutnya dan tumbuh ke atas, dan tumpukan mulai di atas memori dan tumbuh ke bawah. Ada juga beberapa memori yang disediakan untuk sistem operasi, tetapi kita dapat mengabaikannya. Program pada masa itu memiliki stack overflow yang lebih dramatis: stack akan menabrak tumpukan, dan tergantung pada yang diperbarui terlebih dahulu Anda akan bekerja dengan data yang buruk atau kembali dari subrutin ke bagian memori yang sewenang-wenang.

Manajemen memori mengubah model ini agak: dari perspektif program Anda masih memiliki tiga komponen dari peta memori proses, dan mereka umumnya diatur dengan cara yang sama, tetapi sekarang masing-masing komponen dikelola sebagai segmen independen dan MMU akan memberi sinyal kepada OS jika program mencoba mengakses memori di luar segmen. Setelah Anda memiliki memori virtual, tidak ada kebutuhan atau keinginan untuk memberikan akses program ke seluruh ruang alamatnya. Jadi ruas-ruas itu diberi batas tetap.

Jadi mengapa tidak diinginkan untuk memberikan akses program ke ruang alamat lengkapnya? Karena memori itu merupakan "biaya komit" terhadap swap; kapan saja setiap atau semua memori untuk satu program mungkin harus ditulis untuk ditukar untuk memberikan ruang bagi memori program lain. Jika setiap program berpotensi mengkonsumsi 2GB swap, maka Anda harus menyediakan swap yang cukup untuk semua program Anda atau mengambil kesempatan bahwa dua program akan membutuhkan lebih banyak daripada yang bisa mereka dapatkan.

Pada titik ini, dengan asumsi ruang alamat virtual yang cukup, Anda dapat memperluas segmen ini jika diperlukan, dan segmen data (heap) sebenarnya tumbuh dari waktu ke waktu: Anda mulai dengan segmen data kecil, dan ketika pengalokasi memori meminta lebih banyak ruang saat itu dibutuhkan. Pada titik ini, dengan satu tumpukan, secara fisik dimungkinkan untuk memperluas segmen tumpukan: OS dapat menjebak upaya untuk mendorong sesuatu di luar segmen dan menambah lebih banyak memori. Tapi ini juga tidak diinginkan.

Masukkan multi-threading. Dalam hal ini, setiap utas memiliki segmen tumpukan independen, yang lagi-lagi berukuran tetap. Tapi sekarang segmen diletakkan satu demi satu di ruang alamat virtual, jadi tidak ada cara untuk memperluas satu segmen tanpa memindahkan yang lain - yang tidak bisa Anda lakukan karena program ini berpotensi memiliki pointer ke memori yang tinggal di stack. Anda juga dapat meninggalkan beberapa ruang di antara segmen, tetapi ruang itu akan terbuang dalam hampir semua kasus. Pendekatan yang lebih baik adalah dengan membebani pengembang aplikasi: jika Anda benar-benar membutuhkan tumpukan dalam, Anda bisa menentukannya saat membuat utas.

Hari ini, dengan ruang alamat virtual 64-bit, kita dapat membuat tumpukan efektif tak terbatas untuk jumlah utas yang tak terbatas secara efektif. Tetapi sekali lagi, itu tidak terlalu diinginkan: dalam hampir semua kasus, stack overlow mengindikasikan bug dengan kode Anda. Memberikan Anda tumpukan 1 GB hanya menentang penemuan bug itu.

Tumpukan yang memiliki ukuran maksimal tetap tidak ada di mana-mana.

Sulit juga untuk mendapatkan yang benar: kedalaman tumpukan mengikuti Distribusi Power Law, yang berarti bahwa sekecil apa pun Anda membuat ukuran tumpukan, masih akan ada sebagian kecil fungsi yang signifikan dengan tumpukan yang lebih kecil (jadi, Anda membuang-buang ruang), dan tidak peduli seberapa besar Anda membuatnya, masih akan ada fungsi dengan tumpukan yang lebih besar (jadi Anda memaksa stack overflow error untuk fungsi yang tidak memiliki kesalahan). Dengan kata lain: berapa pun ukuran yang Anda pilih, ukurannya akan selalu terlalu kecil dan terlalu besar pada saat bersamaan.

Anda dapat memperbaiki masalah pertama dengan membiarkan tumpukan mulai dari yang kecil dan tumbuh secara dinamis, tetapi kemudian Anda masih memiliki masalah yang kedua. Dan jika Anda membiarkan tumpukan untuk tumbuh secara dinamis, lalu mengapa menempatkan batas yang sewenang-wenang di atasnya?

Ada sistem di mana tumpukan dapat tumbuh secara dinamis dan tidak memiliki ukuran maksimum: Erlang, Go, Smalltalk, dan Skema, misalnya. Ada banyak cara untuk mengimplementasikan sesuatu seperti itu:

• tumpukan bergerak: ketika tumpukan berdekatan tidak dapat tumbuh lagi karena ada sesuatu yang lain di jalan, pindahkan ke lokasi lain dalam memori, dengan lebih banyak ruang kosong
• tumpukan terpisah: alih-alih mengalokasikan seluruh tumpukan dalam satu ruang memori yang berdekatan, alokasikan di banyak ruang memori
• tumpukan yang dialokasikan heap: alih-alih memiliki area memori yang terpisah untuk tumpukan dan tumpukan, hanya mengalokasikan tumpukan pada tumpukan; seperti yang Anda perhatikan sendiri, struktur data yang dialokasikan tumpukan cenderung tidak memiliki masalah tumbuh dan menyusut sesuai kebutuhan
• tidak menggunakan tumpukan sama sekali: itu juga merupakan pilihan, misalnya alih-alih melacak status fungsi dalam tumpukan, mintalah fungsi meneruskan kelanjutan ke callee

Segera setelah Anda memiliki konstruksi aliran kontrol non-lokal yang kuat, ide tumpukan tunggal bersebelahan keluar jendela: pengecualian dan kelanjutan yang dapat dilanjutkan, misalnya, akan "memotong" tumpukan, sehingga Anda benar-benar berakhir dengan jaringan tumpukan (misalnya diimplementasikan dengan tumpukan spaghetti). Juga, sistem dengan tumpukan modifikasi kelas satu, seperti Smalltalk cukup banyak membutuhkan tumpukan spaghetti atau yang serupa.

OS harus memberikan blok yang berdekatan ketika tumpukan diminta. Satu-satunya cara untuk melakukannya adalah jika ukuran maksimum ditentukan.

Sebagai contoh, katakanlah memori tampak seperti ini selama permintaan (Xs mewakili yang digunakan, Os tidak digunakan):

XOOOXOOXOOOOOX

Jika permintaan ukuran tumpukan 6, jawaban OS akan menjawab tidak, bahkan jika lebih dari 6 tersedia. Jika permintaan tumpukan ukuran 3, jawaban OS akan menjadi salah satu area dari 3 slot kosong (Os) berturut-turut.

Juga, orang dapat melihat kesulitan untuk memungkinkan pertumbuhan ketika slot yang berdekatan berikutnya ditempati.

Objek lain yang disebutkan (Daftar, dll.) Tidak masuk tumpukan, mereka berakhir di tumpukan di area yang tidak bersebelahan atau terfragmentasi, jadi ketika mereka tumbuh mereka hanya mengambil ruang, mereka tidak memerlukan berdekatan karena mereka dikelola secara berbeda.

Sebagian besar sistem menetapkan nilai yang wajar untuk ukuran tumpukan, Anda dapat menimpanya ketika thread dibangun jika ukuran yang lebih besar diperlukan.

Di linux, ini murni batas sumber daya yang ada untuk membunuh proses pelarian sebelum mereka mengkonsumsi sumber daya dalam jumlah yang berbahaya. Di sistem debian saya, kode berikut

#include <sys/resource.h>
#include <stdio.h>

int main() {
    struct rlimit limits;
    getrlimit(RLIMIT_STACK, &limits);
    printf("   soft limit = 0x%016lx\n", limits.rlim_cur);
    printf("   hard limit = 0x%016lx\n", limits.rlim_max);
    printf("RLIM_INFINITY = 0x%016lx\n", RLIM_INFINITY);
}

menghasilkan output

   soft limit = 0x0000000000800000
   hard limit = 0xffffffffffffffff
RLIM_INFINITY = 0xffffffffffffffff

Perhatikan, bahwa batas keras diatur ke RLIM_INFINITY: Proses diizinkan untuk menaikkan batas lunaknya ke jumlah berapapun . Namun, selama programmer tidak memiliki alasan untuk percaya bahwa program tersebut benar-benar membutuhkan jumlah memori stack yang tidak biasa, proses tersebut akan terbunuh ketika melebihi ukuran tumpukan delapan mebibytes.

Karena batas ini, proses pelarian (rekursi tak terbatas yang tidak disengaja) terbunuh lama sebelum mulai mengkonsumsi begitu banyak memori sehingga sistem dipaksa untuk mulai bertukar. Ini dapat membuat perbedaan antara proses macet dan server macet. Namun, itu tidak membatasi program dengan kebutuhan sah untuk tumpukan besar, mereka hanya perlu mengatur batas lunak ke beberapa nilai yang sesuai.

Secara teknis, tumpukan memang tumbuh secara dinamis: Ketika batas lunak diatur ke delapan mebibit, itu tidak berarti bahwa jumlah memori ini sebenarnya telah dipetakan. Ini akan menjadi pemborosan karena sebagian besar program tidak pernah mendekati batas lunak masing-masing. Sebaliknya, kernel akan mendeteksi akses di bawah tumpukan, dan hanya memetakan di halaman memori sesuai kebutuhan. Dengan demikian, satu-satunya batasan nyata pada ukuran stack adalah memori yang tersedia pada sistem 64 bit (fragmentasi ruang alamat agak teoretis dengan ukuran ruang alamat 16 zebibyte).

The maksimum ukuran stack adalah statis karena itu adalah definisi "maksimal" . Segala jenis maksimum pada apa pun adalah angka tetap, disepakati yang membatasi. Jika berperilaku sebagai target bergerak spontan, itu tidak maksimal.

Tumpukan pada sistem operasi virtual-memory sebenarnya tumbuh secara dinamis, hingga maksimum .

Omong-omong, itu tidak harus statis. Sebaliknya, itu dapat dikonfigurasi, berdasarkan per proses atau per-thread, bahkan.

Jika pertanyaannya adalah "mengapa adalah ada ukuran maksimum stack" (salah satu artifisial dipaksakan, biasanya jauh lebih sedikit daripada memori yang tersedia)?

Salah satu alasannya adalah sebagian besar algoritma tidak memerlukan ruang stack yang besar. Tumpukan besar adalah indikasi kemungkinan rekursi melarikan diri . Ada baiknya untuk menghentikan rekursi yang melarikan diri sebelum mengalokasikan semua memori yang tersedia. Masalah yang tampak seperti rekursi runaway adalah penggunaan tumpukan yang merosot, mungkin dipicu oleh kasus uji yang tidak terduga. Sebagai contoh, misalkan pengurai untuk biner, operator infiks bekerja dengan mengulang pada operan yang tepat: parse operan pertama, memindai operator, parsing sisa ekspresi. Ini berarti bahwa kedalaman tumpukan sebanding dengan panjang dari ekspresi: a op b op c op d .... Kasing uji bentuk ini akan membutuhkan tumpukan besar. Membatalkan program ketika mencapai batas stack yang masuk akal akan menangkap ini.

Alasan lain untuk ukuran tumpukan maksimum tetap adalah bahwa ruang virtual untuk tumpukan itu dapat dipesan melalui pemetaan khusus, dan karenanya dijamin. Dijamin berarti bahwa ruang tersebut tidak akan diberikan kepada alokasi lain yang kemudian ditumpuk oleh tumpukan sebelum mencapai batasnya. Diperlukan parameter ukuran tumpukan maksimum untuk meminta pemetaan ini.

Utas membutuhkan ukuran tumpukan maksimum untuk alasan yang serupa dengan ini. Tumpukan mereka dibuat secara dinamis dan tidak dapat dipindahkan jika bertabrakan dengan sesuatu; ruang virtual harus dipesan di muka, dan ukuran diperlukan untuk alokasi itu.