Bagaimana variabel disimpan dan diambil dari tumpukan program?

Mohon maaf sebelumnya atas kenaifan pertanyaan ini. Saya seorang seniman berusia 50 tahun yang mencoba memahami komputer dengan benar untuk pertama kalinya. Jadi begini.

Saya telah mencoba memahami bagaimana tipe data dan variabel ditangani oleh kompiler (dalam arti yang sangat umum, saya tahu ada banyak hal). Saya kehilangan sesuatu dalam pemahaman saya tentang hubungan antara penyimpanan dalam "tumpukan" dan tipe nilai, dan penyimpanan pada "tumpukan" dan jenis referensi (tanda kutip dimaksudkan untuk menandakan bahwa saya memahami bahwa istilah ini adalah abstraksi dan bukan untuk dianggap terlalu harfiah dalam konteks yang disederhanakan seperti cara saya membingkai pertanyaan ini). Bagaimanapun, ide simplistis saya adalah bahwa tipe-tipe seperti Boolean dan integer menggunakan "stack" karena mereka bisa, karena mereka dikenal sebagai entitas dalam hal ruang penyimpanan, dan cakupannya mudah dikontrol.

Tapi apa yang saya tidak dapatkan adalah bagaimana variabel pada stack kemudian dibaca oleh aplikasi - jika saya menyatakan dan menetapkan xsebagai integer, katakanlah x = 3, dan penyimpanan dicadangkan pada stack dan kemudian nilainya 3disimpan di sana, dan kemudian di fungsi yang sama saya nyatakan dan tetapkan ysebagai, katakanlah 4, dan kemudian mengikuti yang kemudian saya gunakan xdalam ungkapan lain, (katakanlah z = 5 + x) bagaimana program bisa membaca xuntuk mengevaluasi zketika itu di bawahydi tumpukan? Saya jelas kehilangan sesuatu. Apakah itu lokasi pada stack hanya tentang masa hidup / lingkup variabel, dan bahwa seluruh stack sebenarnya dapat diakses oleh program sepanjang waktu? Jika demikian, apakah itu menyiratkan ada beberapa indeks lain yang hanya menyimpan alamat variabel di stack untuk memungkinkan nilai yang akan diambil? Tapi kemudian saya pikir seluruh poin stack adalah bahwa nilai disimpan di tempat yang sama dengan alamat variabel? Dalam pikiranku yang lemah, sepertinya jika ada indeks lain ini, maka kita berbicara tentang sesuatu yang lebih seperti tumpukan? Saya jelas sangat bingung, dan saya hanya berharap ada jawaban sederhana untuk pertanyaan sederhana saya.

Terima kasih sudah membaca sejauh ini.

Menyimpan variabel lokal pada stack adalah detail implementasi - pada dasarnya optimasi. Anda bisa memikirkannya dengan cara ini. Saat memasukkan fungsi, ruang untuk semua variabel lokal dialokasikan di suatu tempat. Anda kemudian dapat mengakses semua variabel, karena Anda tahu lokasi mereka entah bagaimana (ini adalah bagian dari proses alokasi). Saat meninggalkan fungsi, ruang tersebut tidak dapat dialokasikan (dibebaskan).

Tumpukan adalah salah satu cara untuk mengimplementasikan proses ini - Anda dapat menganggapnya sebagai semacam "tumpukan cepat" yang memiliki ukuran terbatas sehingga hanya cocok untuk variabel kecil. Sebagai optimasi tambahan, semua variabel lokal disimpan dalam satu blok. Karena setiap variabel lokal memiliki ukuran yang diketahui, Anda tahu offset dari masing-masing variabel di blok, dan itulah cara Anda mengaksesnya. Ini berbeda dengan variabel yang dialokasikan pada heap, yang alamatnya sendiri disimpan dalam variabel lain.

$k$

Akhirnya, izinkan saya menyebutkan bahwa dalam praktiknya, beberapa variabel lokal disimpan dalam register. Ini karena akses ke register lebih cepat daripada akses ke stack. Ini adalah cara lain untuk mengimplementasikan ruang untuk variabel lokal. Sekali lagi, kita tahu persis di mana variabel disimpan (kali ini bukan melalui offset, tetapi melalui nama register), dan jenis penyimpanan ini hanya sesuai untuk data kecil.

Memiliki ydi tumpukan tidak secara fisik mencegah xdiakses, yang, seperti yang Anda tunjukkan, membuat tumpukan komputer berbeda dari tumpukan lainnya.

Ketika sebuah program dikompilasi, posisi variabel dalam stack juga telah ditentukan sebelumnya (dalam konteks fungsi). Dalam contoh Anda, jika tumpukan berisi xdengan y"di atas" itu, maka program tahu di muka bahwa xakan 1 item di bawah bagian atas tumpukan sementara di dalam fungsi. Karena perangkat keras komputer dapat secara eksplisit meminta 1 item di bawah bagian atas tumpukan, komputer bisa mendapatkannya xwalaupun yjuga ada.

Apakah itu lokasi pada stack hanya tentang masa hidup / lingkup variabel, dan bahwa seluruh stack sebenarnya dapat diakses oleh program sepanjang waktu?

Iya. Ketika Anda keluar dari suatu fungsi, penunjuk tumpukan bergerak kembali ke posisi sebelumnya, secara efektif menghapus xdan y, tetapi secara teknis mereka akan tetap ada sampai memori digunakan untuk sesuatu yang lain. Selain itu, jika fungsi Anda memanggil fungsi lain, xdan yakan tetap ada dan dapat diakses dengan sengaja masuk terlalu jauh di tumpukan.

Untuk memberikan contoh konkret tentang bagaimana kompiler mengelola tumpukan dan bagaimana nilai-nilai pada tumpukan diakses, kita dapat melihat penggambaran visual, ditambah kode yang dihasilkan oleh GCCdalam lingkungan Linux dengan i386 sebagai arsitektur target.

1. Tumpuk frame

Seperti yang Anda ketahui, stack adalah lokasi di ruang alamat dari proses yang berjalan yang digunakan oleh fungsi , atau prosedur , dalam arti bahwa ruang dialokasikan pada stack untuk variabel yang dideklarasikan secara lokal, serta argumen yang dikirimkan ke fungsi ( ruang untuk variabel yang dideklarasikan di luar fungsi apa pun (yaitu variabel global) dialokasikan di wilayah yang berbeda dalam memori virtual). Ruang yang dialokasikan untuk semua data fungsi dirujuk ke bingkai tumpukan . Berikut ini adalah gambaran visual dari beberapa frame stack (dari Computer Systems: A Programmer's Perspective ):

2. Manajemen bingkai tumpukan dan lokasi variabel

Agar nilai yang ditulis ke tumpukan dalam bingkai tumpukan tertentu untuk dikelola oleh kompiler dan dibaca oleh program, harus ada beberapa metode untuk menghitung posisi nilai-nilai ini dan mengambil alamat memori mereka. Register dalam CPU disebut sebagai stack pointer dan bantuan pointer dasar dengan ini.

Pointer basis, ebpberdasarkan konvensi, berisi alamat memori bagian bawah, atau bagian bawah, dari tumpukan. Posisi semua nilai dalam bingkai tumpukan dapat dihitung menggunakan alamat pada penunjuk dasar sebagai referensi. Ini digambarkan dalam gambar di atas: %ebp + 4adalah alamat memori yang disimpan dalam pointer dasar plus 4, misalnya.

3. Kode yang dihasilkan kompiler

Tapi yang tidak saya dapatkan adalah bagaimana variabel pada stack kemudian dibaca oleh aplikasi - jika saya mendeklarasikan dan menetapkan x sebagai integer, katakanlah x = 3, dan penyimpanan dicadangkan pada stack dan kemudian nilainya 3 disimpan di sana, dan kemudian dalam fungsi yang sama saya menyatakan dan menetapkan y sebagai, katakanlah 4, dan kemudian setelah itu saya kemudian menggunakan x dalam ekspresi lain, (katakanlah z = 5 + x) bagaimana program dapat membaca x untuk mengevaluasi z saat mengevaluasi di bawah y di tumpukan?

Mari kita gunakan contoh program sederhana yang ditulis dalam C untuk melihat bagaimana ini bekerja:

int main(void)
{
        int x = 3;
        int y = 4;
        int z = 5 + x;

        return 0;
}

Mari kita periksa teks rakitan yang diproduksi oleh GCC untuk teks sumber C ini (saya membersihkannya sedikit demi kejelasan):

main:
    pushl   %ebp              # save previous frame's base address on stack
    movl    %esp, %ebp        # use current address of stack pointer as new frame base address
    subl    $16, %esp         # allocate 16 bytes of space on stack for function data
    movl    $3, -12(%ebp)     # variable x at address %ebp - 12
    movl    $4, -8(%ebp)      # variable y at address %ebp - 8
    movl    -12(%ebp), %eax   # write x to register %eax
    addl    $5, %eax          # x + 5 = 9
    movl    %eax, -4(%ebp)    # write 9 to address %ebp - 4 - this is z
    movl    $0, %eax
    leave

Apa yang kami amati adalah bahwa variabel x, y dan z terletak di alamat %ebp - 12, %ebp -8dan %ebp - 4, masing-masing. Dengan kata lain, lokasi variabel dalam bingkai tumpukan main()dihitung menggunakan alamat memori yang disimpan dalam register CPU %ebp.

4. Data dalam memori di luar penunjuk tumpukan berada di luar ruang lingkup

Saya jelas kehilangan sesuatu. Apakah itu lokasi pada stack hanya tentang masa hidup / lingkup variabel, dan bahwa seluruh stack sebenarnya dapat diakses oleh program sepanjang waktu? Jika demikian, apakah itu menyiratkan ada beberapa indeks lain yang hanya menyimpan alamat variabel di stack untuk memungkinkan nilai yang akan diambil? Tapi kemudian saya pikir seluruh poin stack adalah bahwa nilai disimpan di tempat yang sama dengan alamat variabel?

Tumpukan adalah wilayah dalam memori virtual, yang penggunaannya dikelola oleh kompiler. Compiler menghasilkan kode sedemikian rupa sehingga nilai-nilai di luar penunjuk tumpukan (nilai-nilai di atas tumpukan) tidak pernah direferensikan. Ketika suatu fungsi dipanggil, posisi penunjuk tumpukan berubah untuk menciptakan ruang pada tumpukan yang dianggap tidak "di luar batas", jadi bisa dikatakan.

Saat fungsi dipanggil dan kembali, penunjuk tumpukan dikurangi dan bertambah. Data yang ditulis ke tumpukan tidak hilang setelah di luar ruang lingkup, tetapi kompiler tidak menghasilkan instruksi yang merujuk data ini karena tidak ada cara bagi kompiler untuk menghitung alamat data ini menggunakan %ebpatau %esp.

5. Ringkasan

Kode yang dapat dieksekusi langsung oleh CPU dihasilkan oleh kompiler. Kompiler mengelola tumpukan, susunan bingkai untuk fungsi dan register CPU. Salah satu strategi yang digunakan oleh GCC untuk melacak lokasi variabel dalam bingkai tumpukan dalam kode yang dimaksudkan untuk dieksekusi pada arsitektur i386 adalah dengan menggunakan alamat memori dalam penunjuk basis bingkai tumpukan %ebp,, sebagai referensi dan menulis nilai variabel ke lokasi dalam bingkai tumpukan di offset ke alamat di %ebp.

Ada dua register khusus: ESP (penunjuk tumpukan) dan EBP (penunjuk dasar). Ketika prosedur dipanggil dua operasi pertama biasanya

push        ebp  
mov         ebp,esp 

Operasi pertama menyimpan nilai EBP pada stack, dan operasi kedua memuat nilai pointer stack ke dalam pointer basis (untuk mengakses variabel lokal). Jadi, EBP menunjuk ke lokasi yang sama dengan ESP.

Assembler menerjemahkan nama variabel menjadi offset EBP. Misalnya, jika Anda memiliki dua variabel lokal x,y, dan Anda memiliki sesuatu seperti

  x = 1;
  y = 2;
  return x + y;

maka itu dapat diterjemahkan menjadi sesuatu seperti

   push        ebp  
   mov         ebp,esp
   mov  DWORD PTR [ ebp + 6],  1   ;x = 1
   mov  DWORD PTR [ ebp + 14], 2   ;y = 2
   mov  eax, [ ebp + 6 ]
   add  [ ebp + 14 ], eax          ; x + y 
   mov  eax, [ ebp + 14 ] 
   ...  

Nilai offset 6 dan 14 dihitung pada waktu kompilasi.

Ini kira-kira cara kerjanya. Lihat buku kompiler untuk detailnya.

Anda bingung karena variabel lokal yang disimpan dalam stack tidak diakses dengan aturan akses stack: First In Last Out, atau hanya FILO .

Masalahnya adalah bahwa aturan FILO berlaku untuk urutan panggilan fungsi dan bingkai stack , daripada variabel lokal.

Apa itu bingkai tumpukan?

Ketika Anda memasukkan suatu fungsi, itu diberikan sejumlah memori pada stack, yang disebut stack frame. Variabel lokal dari fungsi disimpan dalam bingkai tumpukan. Anda dapat membayangkan bahwa ukuran bingkai tumpukan bervariasi dari satu fungsi ke fungsi lain karena setiap fungsi memiliki jumlah dan ukuran variabel lokal yang berbeda.

Bagaimana variabel lokal disimpan dalam bingkai tumpukan tidak ada hubungannya dengan FILO. (Bahkan urutan penampilan variabel lokal Anda dalam kode sumber Anda tidak memastikan bahwa variabel lokal akan disimpan dalam urutan itu.) Ketika Anda menyimpulkan dengan benar dalam pertanyaan Anda, "ada beberapa indeks lain yang hanya menyimpan alamat variabel-variabel tersebut. di tumpukan untuk memungkinkan nilai yang akan diambil ". Alamat variabel lokal biasanya dihitung dengan alamat basis , seperti alamat batas frame stack, dan nilai offset khusus untuk setiap variabel lokal.

Jadi kapan perilaku FILO ini muncul?

Sekarang, apa yang terjadi jika Anda memanggil fungsi lain? Fungsi callee harus memiliki bingkai tumpukan sendiri, dan bingkai tumpukan inilah yang didorong dalam tumpukan . Yaitu, bingkai tumpukan fungsi callee ditempatkan di atas bingkai tumpukan fungsi pemanggil. Dan jika fungsi callee ini memanggil fungsi lain, maka frame stack-nya akan didorong, sekali lagi, di atas stack.

Apa yang terjadi jika suatu fungsi kembali? Ketika fungsi callee kembali ke fungsi pemanggil, stack frame fungsi callee ini adalah muncul keluar dari tumpukan, membebaskan ruang untuk penggunaan masa depan.

Jadi dari pertanyaan Anda:

Apakah itu lokasi pada stack hanya tentang masa hidup / lingkup variabel, dan bahwa seluruh stack sebenarnya dapat diakses oleh program sepanjang waktu?

Anda cukup benar di sini karena nilai variabel lokal pada bingkai tumpukan tidak benar-benar dihapus ketika fungsi kembali. Nilai hanya tetap di sana, meskipun lokasi memori di mana ia disimpan bukan milik bingkai tumpukan fungsi apa pun. Nilai dihapus ketika beberapa fungsi lain memperoleh bingkai tumpukan yang mencakup lokasi dan menulis lebih dari beberapa nilai lainnya ke lokasi memori itu.

Lalu apa yang membedakan tumpukan dari tumpukan?

Stack dan heap sama dalam arti bahwa keduanya adalah nama yang merujuk pada ruang pada memori. Karena kami dapat mengakses lokasi mana saja di memori dengan alamatnya, Anda dapat mengakses lokasi mana pun di tumpukan atau tumpukan.

Perbedaannya datang dari janji yang dibuat oleh sistem komputer tentang bagaimana ia akan menggunakannya. Seperti yang Anda katakan, tumpukan adalah untuk tipe referensi. Karena nilai dalam tumpukan tidak ada hubungannya dengan bingkai tumpukan tertentu, ruang lingkup nilai tidak terikat ke fungsi apa pun. Variabel lokal, bagaimanapun, dicakup dalam suatu fungsi, dan meskipun Anda dapat mengakses nilai variabel lokal apa pun yang terletak di luar kerangka tumpukan fungsi saat ini, sistem akan mencoba memastikan bahwa perilaku semacam ini tidak terjadi, dengan menggunakan tumpukan frame. Ini memberi kita semacam ilusi bahwa variabel lokal dibatasi untuk fungsi tertentu.

Ada banyak cara untuk mengimplementasikan variabel lokal dengan sistem runtime bahasa. Menggunakan tumpukan adalah solusi efisien yang umum, digunakan dalam banyak kasus praktis.

Secara intuitif, stack pointer spdisimpan di sekitar saat runtime (dalam alamat tetap, atau dalam register - itu benar-benar penting). Asumsikan bahwa setiap "push" menambah penunjuk tumpukan.

Pada waktu kompilasi, kompiler menentukan alamat masing-masing variabel sebagai sp - Kmana Kkonstanta yang hanya bergantung pada ruang lingkup variabel (karenanya dapat dihitung pada waktu kompilasi).

Perhatikan bahwa kita menggunakan kata "tumpukan" di sini dalam arti longgar. Tumpukan ini tidak hanya diakses melalui operasi push / pop / top, tetapi juga diakses menggunakan sp - K.

Sebagai contoh, pertimbangkan kodesemu ini:

procedure f(int x, int y) {
  print(x,y);    // (1)
  if (...) {
    int z=x+y; // (2)
    print(x,y,z);  // (3)
  }
  print(x,y); // (4)
  return;
}

Ketika prosedur dipanggil, argumen x,ydapat dikirimkan pada stack. Untuk kesederhanaan, anggap konvensi adalah penelepon mendorong xpertama, lalu y.

Kemudian, kompiler pada titik (1) dapat ditemukan xdi sp - 2dan ydi sp - 1.

Pada titik (2), variabel baru dimasukkan dalam ruang lingkup. Kompiler menghasilkan kode yang menjumlahkan x+y, yaitu apa yang ditunjukkan oleh sp - 2dan sp - 1, dan mendorong hasil dari jumlah pada tumpukan.

Pada titik (3), zdicetak. Compiler tahu itu adalah variabel terakhir dalam lingkup, jadi itu ditunjukkan oleh sp - 1. Ini tidak lagi y, karena spdiubah. Namun, untuk mencetak ykompiler tahu bahwa ia dapat menemukannya, dalam lingkup ini, di sp - 2. Demikian pula, xsekarang ditemukan di sp - 3.

Pada titik (4), kita keluar dari cakupan. zmuncul, dan ysekali lagi ditemukan di alamat sp - 1, dan xdi sp - 2.

Ketika kami kembali, salah satu fatau pemanggil muncul x,ydari tumpukan.

Jadi, menghitung Kuntuk kompiler adalah soal menghitung berapa banyak variabel dalam lingkup, secara kasar. Di dunia nyata, ini sebenarnya lebih kompleks karena tidak semua variabel memiliki ukuran yang sama, sehingga perhitungannya Ksedikit lebih kompleks. Terkadang, stack juga berisi alamat pengirim untuk f, jadi Kharus "lewati" itu juga. Tapi ini teknis.

Perhatikan bahwa, dalam beberapa bahasa pemrograman, berbagai hal dapat menjadi lebih kompleks jika fitur yang lebih kompleks harus ditangani. Misalnya prosedur bersarang memerlukan analisis yang sangat hati-hati, karena Ksekarang harus "melewatkan" banyak alamat pengirim, terutama jika prosedur bertumpuk bersifat rekursif. Fungsi closures / lambdas / anonim juga membutuhkan perhatian untuk menangani variabel "yang ditangkap". Namun, contoh di atas harus menggambarkan ide dasar.

Ide termudah adalah memikirkan variabel sebagai memperbaiki nama untuk alamat dalam memori. Memang, beberapa assembler menampilkan kode mesin seperti itu ("simpan nilai 5 di alamat i", di mana iada nama variabel).

Beberapa alamat ini "absolut", seperti variabel global, beberapa "relatif", seperti variabel lokal. Variabel (yaitu alamat) dalam fungsi relatif ke beberapa tempat pada "tumpukan" yang berbeda untuk setiap pemanggilan fungsi; dengan cara itu nama yang sama dapat merujuk ke objek aktual yang berbeda, dan panggilan melingkar ke fungsi yang sama adalah doa independen yang bekerja pada memori independen.

Item data yang dapat disimpan di tumpukan diletakkan di tumpukan - Ya! Ini adalah ruang premium. Juga, Setelah kami mendorong xke tumpukan dan kemudian mendorong yke tumpukan, idealnya kita tidak dapat mengakses xsampai yada. Kita perlu pop yuntuk mengakses x. Anda mendapatkannya dengan benar.

Tumpukan bukan dari variabel, tetapi dari frames

Di mana Anda salah, adalah tentang tumpukan itu sendiri. Di tumpukan itu bukan item data yang didorong langsung. Sebaliknya, pada stack sesuatu yang disebut stack-framedidorong. Tumpukan-bingkai ini berisi item data. Meskipun Anda tidak dapat mengakses frame jauh di dalam stack, Anda dapat mengakses frame atas dan semua item data yang terkandung di dalamnya.

Katakanlah kita memiliki item data kita dibundel dalam dua frame stack frame-xdan frame-y. Kami mendorong mereka satu demi satu. Sekarang selama frame-yberada di atas frame-x, Anda tidak dapat secara ideal mengakses item data apa pun di dalamnya frame-x. Hanya frame-yterlihat. TETAPI yang frame-yterlihat, Anda dapat mengakses semua data-item yang dibundel di dalamnya. Seluruh frame terlihat memperlihatkan semua item data yang terkandung di dalamnya.

Akhir dari jawaban. Lebih banyak (kata-kata kasar) pada bingkai ini

Selama kompilasi, daftar semua fungsi dalam program dibuat. Kemudian untuk setiap fungsi dibuat daftar item data yang dapat ditumpuk . Kemudian untuk setiap fungsi stack-frame-templatedibuat. Template ini adalah struktur data yang berisi semua variabel yang dipilih, ruang untuk input data fungsi, data output dll. Sekarang selama runtime, setiap kali suatu fungsi dipanggil, salinannya templatediletakkan di stack - bersama dengan semua input dan variabel perantara . Ketika fungsi ini memanggil beberapa fungsi lain, maka salinan dari yang fungsi ini stack-framedisimpan di stack. Sekarang selama itu fungsi berjalan, ini fungsi ini item data yang diawetkan. Setelah itu fungsi berakhir, tumpukan-frame-nya muncul keluar. Sekarangini tumpukan-frame aktif dan fungsi ini dapat mengakses semua variabel nya.

Perhatikan bahwa struktur dan komposisi bingkai tumpukan bervariasi dari bahasa pemrograman ke bahasa pemrograman. Bahkan dalam suatu bahasa mungkin ada perbedaan yang halus dalam implementasi yang berbeda.

Terima kasih telah mempertimbangkan CS. Saya seorang programmer sekarang hari mengambil pelajaran piano :)