Ada dua struktur data yang diketahui oleh setiap programmer dan yang dianggap sebagai aksioma yang bahkan tidak ada yang mencoba menganalisis apakah mereka diperlukan, apakah ada manfaat dari mereka dan apakah kerusakan ini tidak melebihi mereka.
Antrian
Pertama-tama, kita akan membahas antrian. Apa arti dari antrian? Antrian adalah buffer. Dan kapan kita membutuhkan buffer? Ketika kita tidak punya waktu untuk memproses acara yang masuk dengan kecepatan kedatangan mereka.
Sehubungan dengan hal tersebut di atas, satu pertanyaan muncul: mengapa? Jawabannya adalah kita berharap sesuatu akan terjadi dan tiba-tiba sistem akan memungkinkan kita untuk memproses peristiwa.
Pertama, mari kita bahas paragraf pertama. Apa yang harus terjadi pada sistem, yang tiba - tiba berhenti mengerem dan mulai mencerna data lebih cepat? Kemungkinan besar, beberapa proses intensif sumber daya hanya akan berakhir dan membebaskan sumber daya. Tetapi bagaimana jika ini tidak terjadi? Apa yang harus dilakukan dengan data? Diketahui bahwa: kita baru meresetnya, atau keseluruhan sistem hanya hang karena kekurangan sumber daya.
Bebek, ada dua pertanyaan:
- Dan mengapa Anda tidak dapat langsung mengirimkan data jika kami tahu bahwa kami tidak memiliki sumber daya untuk memprosesnya? Itu sebabnya tidak mungkin membuat antrian dari satu elemen?
- Atau pertanyaan sebaliknya. Mengapa kita memiliki ilusi dan tidak menyediakan sistem dengan jumlah sumber daya yang diperlukan untuk memproses data pada tingkat penerimaan?
Jawaban atas pertanyaan-pertanyaan ini, pada kenyataannya, jelas. Kami sama sekali tidak tahu bagaimana merancang perangkat lunak dan sistem perangkat keras. Karena jika kita tahu cara mendesainnya, maka kita akan tahu berapa banyak data input yang kita miliki, tingkat penerimaan mereka, berapa banyak yang kita butuhkan untuk memprosesnya, dan dengan demikian, kita dapat menghitung kebutuhan nyata akan sumber daya. Tetapi keadaan terkini dari alat dan metodologi pengembangan TIK, dengan pengecualian bagian dari sistem teknologi (dan tidak semuanya), tidak memungkinkan kita untuk membuat perhitungan objektif kebutuhan sumber daya.
Dan kami menutup kekurangan ini dengan segala macam penyangga, khususnya, dalam bentuk antrian. Sebagai hasilnya, kami memiliki bom yang diletakkan di fondasi bangunan bahkan pada tingkat lubang fondasi, karena kruk ini berfungsi sebagai sumber dari berbagai penghinaan dan sulit untuk memahami masalah dengan keandalan, keamanan dan hanya kualitas pekerjaan.
Tapi, mari kita lanjutkan, di depan kita adalah struktur "favorit" saya yang paling - tumpukan!
Tumpukan
Itu sudah pasti, seperti yang pernah dikatakan Hoar tentang Null, bahwa ini adalah kesalahan satu miliar dolar, sehingga hal yang sama dapat dikatakan tentang tumpukan itu.
Ini adalah salah satu struktur paling bermasalah yang digunakan dalam TIK dan penghindaran maksimumnya dalam praktik menciptakan perangkat keras dan lunak, hingga pemberantasan total, sangat diinginkan.
Jadi apa sebenarnya masalah tumpukan? Ya, persis sama dengan antrian. Tumpukan pada dasarnya mustahil untuk diatur. Segera setelah ada seseorang yang secara akurat memprediksi berapa banyak memori yang dibutuhkan oleh program arbitrer mana pun, saya secara pribadi meminta maaf dan menulis sebuah artikel besar bahwa saya salah dan meminta pengampunan.
Tetapi sesuatu mengatakan kepada saya bahwa ini tidak mungkin terjadi di masa mendatang.
Mari kita menganalisis mengapa kita perlu tumpukan? Ya, persis sama, untuk mana antrian. Ini adalah buffer. Artinya, ini adalah tongkat penyangga untuk pikiran malas yang tidak ingin merancang perangkat lunak dan sistem perangkat keras dengan benar.
Jadi pelajarannya adalah ini: rekursi harus dihindari di mana ada solusi berulang yang jelas. Namun, ini tidak berarti bahwa rekursi harus dibuang dengan cara apa pun. Ada banyak contoh bagus menggunakan rekursi, yang akan kami tunjukkan di bagian dan bab selanjutnya. Fakta bahwa ada implementasi prosedur rekursif pada mesin yang hampir non-rekursif membuktikan bahwa untuk tujuan praktis, setiap program rekursif dapat diubah menjadi program yang murni iteratif. Namun, ini membutuhkan kerja eksplisit dengan tumpukan rekursi, dan tindakan ini sering mengaburkan esensi program sehingga sulit dipahami. Kesimpulan: algoritma yang bersifat rekursif dan tidak berulang, perlu dirumuskan sebagai prosedur rekursif.
Nicklaus Wirth. Algoritma dan struktur data
Setuju dengan master tentang opsi konversi, saya tidak setuju dengan pendekatan lembutnya untuk menggunakan stack.
Saya mengedepankan teorema: algoritma stack dapat dikonversi ke loop, dan mereka yang tidak dapat dikonversi buruk.
Praktik memanggil subprogram dengan melewati parameter melalui stack harus dihentikan, dan rekursi yang tidak berkembang ke loop dan praktik yang banyak digunakan lainnya juga harus pergi ke sana.
Kami dapat mengganti tumpukan untuk kasus-kasus berikut:
- Rekursi, diimplementasikan dalam bentuk memperluas algoritma stack ke dalam satu loop dengan blok data yang diubah selama eksekusi dari loop.
- Jika Anda perlu mentransfer parameter, maka Anda akan mengatur sistem firmware dengan pengiriman pesan. Dan tentang pengiriman pesan, kita masuk ke baris yang dijelaskan di bagian pertama artikel. Jika Anda benar-benar ingin tumpukan, maka jelas Anda tidak harus mendorong puluhan dan ratusan kilobyte objek di sana, tetapi Anda perlu mengalokasikan memori untuk ini secara normal, di heap.
Pada saat yang sama, di tingkat atas, programmer dapat menggunakan struktur data apa pun, dan terserah kompiler untuk mengubahnya sehingga tidak termasuk penggunaan stack.
Tentu saja, beberapa peluang mungkin akan hilang, tetapi ini, jika dipertimbangkan secara rinci, bukan fakta.
Blockout
Pada 1995, dengan teman sekelas saya, saya merumuskan prinsip-prinsip membangun sistem operasi yang mengecualikan kedua paradigma ini.
Prinsip-prinsipnya adalah sebagai berikut:
- Perangkat lunak - jaringan proses yang berinteraksi.
- Interaksi proses dilakukan melalui pertukaran pesan.
- Jaringan proses berinteraksi diatur sebagai berikut: sumber pesan utama dalam jaringan semacam itu hanya peristiwa dari dunia luar yang dipasok oleh peralatan, konsumen akhir pesan hanyalah perangkat yang melakukan tindakan di dunia luar. Artinya, jaringan dimulai di dunia nyata dan berakhir di dalamnya.
- Proses tidak dapat memiliki prioritas. Prioritas hanya dapat memiliki jaringan proses.
- Jaringan tidak pernah buffer pesan. Kompleks perangkat keras-perangkat lunak harus diatur sedemikian rupa untuk mengelola untuk memproses pesan dengan kecepatan penerimaan mereka dari dunia luar.
- Kompleks perangkat keras adalah jaringan node komputasi yang terhubung oleh saluran komunikasi.
- Setiap node memiliki "biaya", tergantung pada kekuatan pemrosesan, ukuran memori, faktor beban dan berat, dengan mempertimbangkan biaya pembuatan dan pemeliharaannya.
- Setiap saluran komunikasi memiliki "biaya", tergantung pada bandwidth, kemacetan dan koefisien bobotnya, dengan mempertimbangkan biaya pembuatan dan pemeliharaannya.
- Sistem operasi menyediakan peluncuran proses dalam menanggapi pesan yang masuk dan perutean pesan.
- Sistem operasi memastikan distribusi proses dan pesan antar node komputasi, mengoptimalkan fungsi f (cpu, mem) pada topologi jaringan, dengan mempertimbangkan biaya pengiriman kode proses dan pesan ke node.
- Mengingat konstruksi sistem, Anda selalu dapat secara akurat menghitung jumlah memori yang diperlukan untuk proses tersebut. Jumlah waktu penghitungan yang dibutuhkan dapat dihitung secara akurat berdasarkan analisis algoritma.
Prosesor BIND
Sebagai bagian dari karir mengajarnya, bersama siswa, ia pernah berpartisipasi dalam kontes emulator CPU IEEE. Prosesor stackless tujuan umum arsitektur Harvard dikembangkan menggunakan sistem perintah yang mirip dengan ARM sebelumnya. Juga, gagasan transporter yang dilupakan dimasukkan ke dalam CPU dan prosesor dilengkapi dengan 16 saluran menerima-transmisi 8-bit.
Karenanya, tidak ada operasi panggilan / pengembalian dalam prosesor. Hanya transisi kondisional / tanpa syarat yang dimungkinkan. Karena hampir tidak ada yang menulis di assembler sekarang, semua pertanyaan tentang membuat program dalam kode mesin seharusnya ditugaskan ke kompiler.
Tujuan utama dari prosesor ini adalah untuk secara mulus mendukung prinsip-prinsip Blockout OS di tingkat perangkat keras dengan menciptakan jaringan prosesor di simpul komputasi lokal yang dihubungkan oleh saluran komunikasi yang prosesnya sudah akan didistribusikan.
Kesimpulan
Teks menunjukkan kelemahan fatal dari antrian dan menumpuk struktur data. Prinsip-prinsip merancang perangkat lunak dan sistem perangkat keras yang memungkinkan untuk mengecualikan struktur ini dari praktik aplikasi diberikan.
Teks ini, lebih tepatnya, kompilasi pemikiran yang telah terjadi sepanjang karir di bidang IT, sehingga, untuk mereduksi semuanya menjadi satu tempat.