Saya sebelumnya menanyakan pertanyaan ini di Programmers.SE , tanpa hasil.
Saya mencari sumber belajar tertulis tentang bagaimana merancang struktur data bersamaan. Saya lebih tertarik pada proses desain (misalnya, mengidentifikasi invarian yang tepat) daripada produk akhir (daftar kode lengkap).
Sebagai contoh konkret: Saya benar-benar menikmati buku Chris Okasaki “Struktur Data Murni Fungsional”, karena ini lebih dari sekadar referensi - buku ini memandu pembaca melalui desain struktur data dan algoritma. Seringkali, buku ini memotivasi desain yang rumit atau tidak jelas dengan terlebih dahulu memberikan versi yang lebih naif, dan baru kemudian memperbaikinya sampai kompleksitas waktu yang diinginkan (baik yang terburuk maupun yang diamortisasi) tercapai. Ini adalah hal yang saya cari.
Begitu:
Apa teknik atau heuristik yang ada untuk merancang struktur data bersamaan?
Apakah ada buku, makalah, posting blog, tutorial, dll. Yang menjelaskan teknik dan heuristik ini?
Jawabannya tidak sesederhana pemrograman fungsional. Dalam pemrograman fungsional di sini kita memiliki konsep umum tentang apa yang pemrograman fungsional dan spesifikasi struktur data itu sendiri tidak berubah oleh fakta bahwa mereka fungsional. Namun tidak demikian halnya dengan concurrency:
Ada banyak model komputasi terdistribusi / paralel / bersamaan.
Tidak ada transformasi umum yang diberikan spesifikasi struktur data berurutan memberikan yang spesifikasi versi bersamaan nya. Ada berbagai kondisi (umumnya dikategorikan di bawah keamanan dan liveness kondisi) yang bisa kita butuhkan dari versi bersamaan dari struktur data, ada berbagai hasil baru (misalnya operasi berhenti, operasi batal, crash, dll). Jadi bisa ada banyak spesifikasi berbeda untuk versi bersamaan dari struktur data sekuensial.
Beberapa pertanyaan tentang referensi tentang komputasi terdistribusi:
Lihat juga Mengapa kita belum mampu mengembangkan teori kompleksitas komputasi terdistribusi?
sumber
Aturan pertama struktur data konkuren adalah: Anda tidak ingin konkurensi.
Dalam kasus ideal, komputasi terdistribusi / paralel / konkuren berarti Anda memiliki sejumlah proses sekuensial yang sepenuhnya independen. Setiap proses memiliki data dan sumber dayanya sendiri, dan prosesnya bahkan tidak mengetahui proses lainnya.
Dalam kasus terburuk, Anda memiliki sistem memori bersama dengan beberapa utas yang menanyakan dan memperbarui struktur data yang sama secara bersamaan. Mungkin ada yang salah, jika Anda serius mempertimbangkan ini.
Tentu saja, ketika kita berbicara tentang struktur data bersamaan, beberapa derajat konkurensi tidak dapat dihindari. Kami masih ingin menguranginya. Semakin lama suatu proses dapat bekerja secara berurutan tanpa menyentuh mutex, melakukan operasi atom, atau menyampaikan pesan, semakin besar kemungkinan semuanya bekerja dengan benar dan kinerjanya dapat diterima.
Struktur data statis dengan pembaruan batch memerlukan lebih sedikit sinkronisasi daripada struktur data dinamis. Anda harus mencoba membuat struktur data konkuren Anda statis, atau setidaknya sedekat mungkin dengan statis. Jika algoritme Anda membutuhkan kueri interleaving dengan pembaruan, coba ubah algoritme sebelum beralih ke struktur dinamis bersama.
Prinsip desain yang sama juga berlaku untuk memperbarui struktur data statis. Semakin mandiri Anda dapat membuat proses memperbarui struktur, semakin baik semuanya berfungsi.
sumber