Diberikan sistem komputer tertentu, apakah mungkin untuk memperkirakan waktu menjalankan sebenarnya yang tepat dari sepotong kode Majelis

ini adalah bagian dari kode Majelis

section .text
    global _start       ;must be declared for using gcc
_start:                     ;tell linker entry point
    mov edx, len    ;message length
    mov ecx, msg    ;message to write
    mov ebx, 1      ;file descriptor (stdout)
    mov eax, 4      ;system call number (sys_write)
    int 0x80        ;call kernel
    mov eax, 1      ;system call number (sys_exit)
    int 0x80        ;call kernel

section .data

msg db  'Hello, world!',0xa ;our dear string
len equ $ - msg         ;length of our dear string

Diberikan sistem komputer tertentu, apakah mungkin untuk memprediksi secara tepat waktu berjalan aktual dari sepotong kode Majelis.

Saya hanya bisa mengutip dari manual CPU yang agak primitif, prosesor 68020 dari sekitar tahun 1986: "Menghitung runtime yang tepat dari urutan instruksi sulit, bahkan jika Anda memiliki pengetahuan yang tepat tentang implementasi prosesor". Yang tidak kita miliki. Dan dibandingkan dengan prosesor modern, CPU itu primitif .

Saya tidak dapat memprediksi runtime kode itu, dan Anda juga tidak bisa. Tetapi Anda bahkan tidak bisa mendefinisikan apa "runtime" dari sepotong kode, ketika prosesor memiliki cache yang besar, dan kemampuan out-of-order yang masif. Prosesor modern yang khas dapat memiliki 200 instruksi "dalam penerbangan", yaitu dalam berbagai tahap eksekusi. Jadi waktu dari mencoba membaca byte instruksi pertama, untuk pensiun instruksi terakhir, bisa sangat lama. Tetapi penundaan sebenarnya untuk semua pekerjaan lain yang perlu dilakukan prosesor mungkin (dan biasanya) jauh lebih sedikit.

Tentu saja melakukan dua panggilan ke sistem operasi membuat ini benar-benar tidak dapat diprediksi. Anda tidak tahu apa yang sebenarnya "menulis untuk stdout", sehingga Anda tidak dapat memprediksi waktu.

Dan Anda tidak dapat mengetahui kecepatan jam komputer pada saat Anda menjalankan kode. Mungkin dalam beberapa mode hemat daya, komputer mungkin mengurangi kecepatan clock karena panas, sehingga bahkan jumlah siklus clock yang sama dapat mengambil jumlah waktu yang berbeda.

Semua dalam semua: Benar-benar tidak dapat diprediksi.

Anda tidak dapat melakukan ini secara umum, tetapi dalam beberapa hal, Anda sangat bisa, dan ada beberapa kasus sejarah di mana Anda memang harus melakukannya.

The Atari 2600 (atau Atari Video Computer System) adalah salah satu sistem home video game yang paling awal dan pertama kali dirilis pada tahun 1978. Tidak seperti sistem kemudian jaman, Atari tidak mampu untuk memberikan perangkat frame buffer, yang berarti bahwa CPU telah untuk menjalankan kode di setiap garis pemindaian untuk menentukan apa yang akan dihasilkan - jika kode ini mengambil alih 17,08 mikrodetik untuk dijalankan (interval HBlank), grafik tidak akan ditetapkan dengan benar sebelum garis pemindaian mulai menggambar mereka. Lebih buruk lagi, jika programmer ingin menggambar konten yang lebih kompleks daripada apa yang biasanya diizinkan Atari, mereka harus mengukur waktu yang tepat untuk instruksi dan mengubah register grafik saat balok sedang digambar, dengan rentang 57,29 mikrodetik untuk seluruh garis pindai.

Namun, Atari 2600, seperti banyak sistem lain yang berbasiskan pada 6502, memiliki fitur yang sangat penting yang memungkinkan manajemen waktu yang cermat untuk skenario ini: CPU, RAM, dan sinyal TV semuanya menjalankan jam berdasarkan master yang sama jam. Sinyal TV menjalankan clock 3,98 MHz, membagi waktu di atas menjadi angka integer "jam warna" yang mengatur sinyal TV, dan siklus jam CPU dan RAM adalah tepat tiga jam warna, yang memungkinkan jam CPU menjadi ukuran waktu yang akurat relatif terhadap sinyal TV kemajuan saat ini. (Untuk informasi lebih lanjut tentang ini, lihat Panduan Programmer Stella , ditulis untuk emulator Stella Atari 2600 ).

Lingkungan operasi ini, di samping itu, berarti bahwa setiap instruksi CPU memiliki jumlah siklus yang pasti akan diperlukan dalam setiap kasus, dan banyak 6502 pengembang menerbitkan informasi ini dalam tabel referensi. Misalnya, pertimbangkan entri ini untuk CMPinstruksi (Bandingkan Memori dengan akumulator), yang diambil dari tabel ini :

CMP  Compare Memory with Accumulator

     A - M                            N Z C I D V
                                    + + + - - -

     addressing    assembler    opc  bytes  cycles
     --------------------------------------------
     immediate     CMP #oper     C9    2     2
     zeropage      CMP oper      C5    2     3
     zeropage,X    CMP oper,X    D5    2     4
     absolute      CMP oper      CD    3     4
     absolute,X    CMP oper,X    DD    3     4*
     absolute,Y    CMP oper,Y    D9    3     4*
     (indirect,X)  CMP (oper,X)  C1    2     6
     (indirect),Y  CMP (oper),Y  D1    2     5*

*  add 1 to cycles if page boundary is crossed

Dengan menggunakan semua informasi ini, Atari 2600 (dan 6502 pengembang lainnya) dapat menentukan dengan tepat berapa lama kode mereka untuk dieksekusi, dan membangun rutinitas yang melakukan apa yang mereka butuhkan dan masih mematuhi persyaratan waktu sinyal TV Atari. Dan karena pengaturan waktu ini sangat tepat (terutama untuk instruksi yang membuang-buang waktu seperti NOP), mereka bahkan dapat menggunakannya untuk memodifikasi gambar saat gambar tersebut diambil.

Tentu saja, Atari's 6502 adalah kasus yang sangat spesifik, dan semua ini hanya mungkin karena sistem memiliki semua hal berikut:

• Master clock yang menjalankan semuanya, termasuk RAM. Sistem modern memiliki jam independen untuk CPU dan RAM, dengan jam RAM sering lebih lambat dan keduanya tidak selalu sinkron.
• Tanpa caching dalam bentuk apa pun - 6502 selalu mengakses DRAM secara langsung. Sistem modern memiliki cache SRAM yang membuatnya lebih sulit untuk memprediksi keadaan - sementara mungkin masih mungkin untuk memprediksi perilaku sistem dengan cache, itu jelas lebih sulit.
• Tidak ada program lain yang berjalan secara bersamaan - program pada kartrid memiliki kendali penuh atas sistem. Sistem modern menjalankan banyak program sekaligus menggunakan algoritma penjadwalan non-deterministik.
• Kecepatan clock cukup lambat sehingga sinyal dapat melintasi sistem dalam waktu. Pada sistem modern dengan kecepatan clock 4 GHz (misalnya), dibutuhkan foton siklus cahaya 6,67 untuk menempuh panjang motherboard setengah meter - Anda tidak akan pernah bisa mengharapkan prosesor modern untuk berinteraksi dengan sesuatu yang lain di papan tulis hanya dalam satu siklus, karena dibutuhkan lebih dari satu siklus untuk sinyal di papan untuk mencapai perangkat.
• Kecepatan clock yang terdefinisi dengan baik yang jarang berubah (1,19 MHz untuk Atari) - kecepatan CPU dari sistem modern berubah setiap saat, sementara Atari tidak dapat melakukan ini tanpa juga memengaruhi sinyal TV.
• Timing siklus yang dipublikasikan - x86 tidak menentukan berapa lama waktu yang diperlukan untuk instruksinya.

Semua hal ini datang bersama-sama untuk menciptakan suatu sistem di mana dimungkinkan untuk membuat set instruksi yang membutuhkan waktu yang tepat - dan untuk aplikasi ini, itulah yang diminta. Sebagian besar sistem tidak memiliki tingkat ketelitian ini hanya karena tidak diperlukan untuk itu - perhitungan bisa dilakukan ketika mereka selesai, atau jika jumlah waktu yang tepat dibutuhkan, jam independen dapat ditanyakan. Tetapi jika kebutuhannya benar (seperti pada beberapa sistem tertanam), masih dapat muncul, dan Anda akan dapat secara akurat menentukan berapa lama kode Anda diperlukan untuk berjalan di lingkungan ini.

Dan saya juga harus menambahkan penafian besar-besaran bahwa semua ini hanya berlaku untuk membangun satu set instruksi perakitan yang akan memakan waktu yang tepat. Jika yang ingin Anda lakukan adalah mengambil bagian perakitan yang sewenang-wenang, bahkan di lingkungan ini, dan bertanya "Berapa lama waktu yang diperlukan untuk mengeksekusi?", Anda pasti tidak bisa melakukan itu - itu adalah Masalah Pemutusan , yang telah terbukti tidak dapat diselesaikan.

EDIT 1: Dalam versi sebelumnya dari jawaban ini, saya menyatakan bahwa Atari 2600 tidak memiliki cara untuk memberitahu prosesor di mana ia berada di sinyal TV, yang memaksanya untuk menjaga seluruh program dihitung dan disinkronkan dari awal. Seperti yang saya tunjukkan dalam komentar, ini berlaku untuk beberapa sistem seperti ZX Spectrum, tetapi tidak berlaku untuk Atari 2600, karena berisi register perangkat keras yang menghentikan CPU hingga interval pengosongan horizontal berikutnya terjadi, serta sebuah fungsi untuk memulai interval pengosongan vertikal sesuka hati. Oleh karena itu, masalah penghitungan siklus terbatas pada setiap garis pemindaian, dan hanya menjadi tepat jika pengembang ingin mengubah konten saat garis pemindaian sedang dibuat.

Ada dua aspek yang berperan di sini

Seperti yang ditunjukkan @ gnasher729, jika kita mengetahui instruksi yang tepat untuk dieksekusi, masih sulit untuk memperkirakan runtime yang tepat karena hal-hal seperti caching, prediksi cabang, penskalaan, dll.

Namun, situasinya bahkan lebih buruk. Diberikan potongan perakitan, tidak mungkin untuk mengetahui instruksi mana yang akan berjalan, atau bahkan untuk mengetahui berapa banyak instruksi yang akan berjalan. Ini karena teorema Rice: jika kita dapat menentukannya dengan tepat, maka kita dapat menggunakan informasi itu untuk menyelesaikan Masalah Pemutusan, yang tidak mungkin.

Kode assembly dapat berisi lompatan dan cabang, yang cukup untuk membuat jejak penuh dari program yang mungkin tak terbatas. Telah ada pekerjaan pada perkiraan konservatif dari waktu eksekusi, yang memberikan batas atas pada eksekusi, melalui hal-hal seperti semantik biaya atau sistem tipe beranotasi. Saya tidak terbiasa dengan apa pun untuk perakitan khusus tetapi saya tidak akan terkejut jika sesuatu seperti itu ada.

Apakah pilihan "sistem komputer" akan menyertakan mikrokontroler? Beberapa mikrokontroler memiliki waktu eksekusi yang sangat dapat diprediksi, misalnya seri PIC 8 bit memiliki empat siklus clock per instruksi kecuali instruksi tersebut bercabang ke alamat yang berbeda, dibaca dari flash atau merupakan instruksi dua kata khusus.

Interupsi dengan obyektif akan mengganggu timimg semacam ini, tetapi dimungkinkan untuk melakukan banyak hal tanpa penangan interupsi dalam konfigurasi "bare metal".

Menggunakan perakitan dan gaya pengkodean khusus dimungkinkan untuk menulis kode yang akan selalu mengambil waktu yang sama untuk dieksekusi. Itu tidak begitu umum sekarang bahwa sebagian besar varian PIC memiliki banyak timer, tetapi itu mungkin.

Kembali di era komputer 8-bit, beberapa game melakukan sesuatu seperti itu. Pemrogram akan menggunakan jumlah waktu yang tepat yang diperlukan untuk menjalankan instruksi, berdasarkan pada jumlah waktu yang mereka ambil dan kecepatan clock CPU yang diketahui, untuk menyinkronkan dengan waktu yang tepat dari perangkat keras video dan audio. Pada masa itu, tampilannya adalah monitor tabung sinar katoda yang akan berputar di setiap baris layar dengan kecepatan tetap dan mengecat deretan piksel dengan menyalakan dan mematikan sinar katoda untuk mengaktifkan atau menonaktifkan fosfor. Karena pemrogram perlu memberi tahu perangkat keras video apa yang harus ditampilkan tepat sebelum balok mencapai bagian layar itu, dan menyesuaikan kode dengan sisa waktu yang tersisa, mereka menyebutnya "memacu sinar."

Ini benar-benar tidak akan berfungsi pada komputer modern apa pun, atau untuk kode seperti contoh Anda.

Kenapa tidak? Berikut adalah beberapa hal yang akan mengacaukan waktu yang sederhana dan dapat diprediksi:

Kecepatan CPU dan pengambilan memori keduanya merupakan hambatan pada waktu eksekusi. Buang-buang uang untuk menjalankan CPU lebih cepat daripada yang bisa diambil instruksi untuk dijalankan, atau untuk menginstal memori yang dapat memberikan byte lebih cepat daripada CPU dapat menerimanya. Karena itu, komputer lama menjalankan keduanya dari jam yang sama. CPU modern berjalan jauh lebih cepat daripada memori utama. Mereka mengelolanya dengan memiliki instruksi dan cache data. CPU masih akan berhenti jika perlu menunggu byte yang tidak ada dalam cache. Instruksi yang sama karena itu akan berjalan lebih cepat jika sudah ada dalam cache daripada jika tidak.

Selain itu, CPU modern memiliki jaringan pipa yang panjang. Mereka menjaga throughput tinggi mereka dengan meminta bagian lain dari chip melakukan pekerjaan pendahuluan pada beberapa instruksi berikutnya dalam pipa. Ini akan gagal jika CPU tidak tahu apa instruksi selanjutnya, yang dapat terjadi jika ada cabang. Oleh karena itu, CPU mencoba memprediksi lompatan bersyarat. (Anda tidak memiliki potongan kode ini, tetapi mungkin ada lompatan kondisional yang salah diprediksi yang menyumbat pipa. Selain itu, alasan yang bagus untuk menghubungkan jawaban legendaris itu.) Demikian pula, sistem yang memanggil int 80untuk menjebak ke mode kernel sebenarnya menggunakan fitur CPU yang rumit, sebuah gerbang interupsi, yang menyebabkan penundaan tak terduga.

Jika OS Anda menggunakan multitasking preemptive, utas yang menjalankan kode ini bisa kehilangan kutu waktu setiap saat.

Balap balok juga hanya bekerja karena program ini berjalan pada logam telanjang dan menggedor langsung pada perangkat keras. Di sini, Anda menelepon int 80untuk melakukan panggilan sistem. Itu melewati kendali ke sistem operasi, yang tidak memberi Anda jaminan waktu. Anda kemudian mengatakan itu I / O pada aliran sewenang-wenang, yang mungkin telah dialihkan ke perangkat apa pun. Terlalu abstrak bagi Anda untuk mengatakan berapa banyak waktu yang diperlukan I / O, tetapi pasti akan mendominasi waktu yang dihabiskan untuk melaksanakan instruksi.

Jika Anda ingin pengaturan waktu yang tepat pada sistem modern, Anda perlu memperkenalkan loop penundaan. Anda harus membuat iterasi yang lebih cepat berjalan pada kecepatan yang paling lambat, sebaliknya tidak mungkin terjadi. Salah satu alasan orang melakukannya di dunia nyata adalah untuk mencegah bocornya informasi kriptografis kepada penyerang yang dapat menentukan waktu permintaan yang lebih lama dari yang lain.

Ini agak tangensial tetapi pesawat ulang-alik memiliki 4 komputer yang redundan yang bergantung pada sinkronisasi yang akurat, yaitu waktu run-time-nya benar-benar cocok.

Upaya peluncuran pertama dari pesawat ulang-alik dibatalkan ketika komputer Backup Flight Software (BFS) menolak untuk melakukan sinkronisasi dengan empat komputer Sistem Perangkat Lunak Penerbangan Primer (PASS). Detail dalam "The Bug Heard Round the World" di sini . Baca menarik tentang bagaimana perangkat lunak dikembangkan untuk mencocokkan siklus untuk siklus dan mungkin memberi Anda latar belakang yang menarik.

Saya pikir kita sedang mencampur dua masalah berbeda di sini. (Dan ya, saya tahu ini telah dikatakan oleh orang lain, tapi saya harap saya bisa mengungkapkannya dengan lebih jelas.)

Pertama kita perlu beralih dari kode sumber ke urutan instruksi yang benar-benar dieksekusi (yang membutuhkan pengetahuan tentang data input serta kode - berapa kali Anda berputar-putar? Cabang mana yang diambil setelah tes? ). Karena masalah penghentian, urutan instruksi mungkin tidak terbatas (non-terminasi) dan Anda tidak dapat selalu menentukan itu secara statis, bahkan dengan pengetahuan tentang data input.

Setelah menetapkan urutan instruksi yang akan dieksekusi, Anda kemudian ingin menentukan waktu eksekusi. Itu tentu dapat diperkirakan dengan beberapa pengetahuan tentang arsitektur sistem. Tetapi masalahnya adalah bahwa pada banyak mesin modern, waktu eksekusi sangat bergantung pada caching pengambilan memori, yang berarti tergantung pada input data seperti pada instruksi yang dieksekusi. Ini juga tergantung pada tebakan yang benar dari tujuan cabang bersyarat, yang lagi-lagi tergantung data. Jadi itu hanya akan menjadi perkiraan, itu tidak akan tepat.