Konkurensi dan Model Memori
Model konkurensi dan memori mendefinisikan bagaimana program konkuren disusun dan bagaimana thread-thread yang berinteraksi mengamati memori bersama, yang mendasari perangkat lunak paralel yang benar.
Definition
Model konkurensi menjelaskan bagaimana komputasi yang dieksekusi secara independen disusun dan berkomunikasi, sementara model memori menentukan nilai mana yang dapat diamati oleh pembacaan ketika thread konkuren mengakses memori bersama, mendefinisikan kontrak antara pemrogram, bahasa, dan perangkat keras.
Scope
Area ini mencakup bahasa dan teori konkurensi: kalkulus proses dan model konkurensi untuk komunikasi dan sinkronisasi, model konsistensi memori yang menentukan urutan operasi memori yang diizinkan, mekanisme sinkronisasi dan kebebasan dari data-race, serta sistem tipe untuk konkurensi seperti tipe sesi. Ini membahas bagaimana bahasa memberikan makna pada program yang dieksekusi secara bersamaan dan berbagi status.
Sub-topics
Core questions
- Bagaimana proses konkuren yang berkomunikasi dapat dimodelkan dan dianalisis?
- Urutan operasi memori apa yang dapat diamati oleh suatu program?
- Bagaimana kebebasan dari data-race dijamin atau ditentukan?
- Bagaimana tipe dapat mendisiplinkan komunikasi dan mencegah kesalahan konkurensi?
Key theories
- Kalkulus proses
- CSP dari Hoare dan CCS serta pi-calculus dari Milner menyediakan teori aljabar tentang proses konkuren yang berkomunikasi, dengan operator untuk komposisi dan sinkronisasi serta gagasan kesetaraan perilaku seperti bisimulasi.
- Konsistensi sekuensial
- Lamport mendefinisikan konsistensi sekuensial sebagai persyaratan bahwa eksekusi multiprosesor muncul sebagai beberapa interleave operasi setiap prosesor dalam urutan program, yang merupakan dasar perbandingan model memori yang lebih lemah.
- Model konsistensi memori
- Adve dan Gharachorloo mensistematisasi spektrum model konsistensi memori bersama, menjelaskan bagaimana urutan yang lebih longgar memungkinkan kinerja sambil mempersulit penalaran tentang program konkuren.
Clinical relevance
Model memori kini menjadi bagian dari spesifikasi bahasa utama (misalnya di C++ dan Java) karena perangkat keras multicore membuat urutan yang lebih longgar dapat diamati; memahaminya dengan benar sangat penting untuk perangkat lunak konkuren yang benar dan portabel. Kalkulus proses dan tipe sesi menginformasikan desain bahasa dan protokol berbasis pesan.
History
Teori konkurensi berkembang dari Petri nets dan karya Hoare (CSP) serta Milner (CCS) pada tahun 1970-an, kemudian pi-calculus untuk proses bergerak. Lamport mendefinisikan konsistensi sekuensial pada tahun 1979; seiring dengan proliferasi perangkat keras yang lebih longgar, model memori diformalkan untuk bahasa seperti Java dan C++ pada tahun 2000-an, dan semantik memori lemah menjadi area penelitian yang aktif.
Debates
- Konsistensi memori yang kuat versus yang longgar
- Para perancang menukar kesederhanaan intuitif model yang kuat seperti konsistensi sekuensial dengan kinerja model yang longgar yang memungkinkan pengurutan ulang, yang mempersulit penalaran dan memerlukan semantik tingkat bahasa yang cermat.
Key figures
- C. A. R. Hoare
- Robin Milner
- Leslie Lamport
- Sarita Adve
Related topics
Seminal works
- hoare1978
- milner1989
- lamport1979
- adve1996
Frequently asked questions
- Apa itu model memori?
- Model memori adalah kontrak formal yang menentukan nilai mana yang dapat dikembalikan oleh pembacaan ketika beberapa thread mengakses memori bersama, mendefinisikan pengurutan ulang apa yang dapat dilakukan oleh kompiler dan perangkat keras serta apa yang dapat diandalkan oleh pemrogram.
- Apa itu konsistensi sekuensial?
- Konsistensi sekuensial mensyaratkan bahwa eksekusi konkuren berperilaku sebagai satu interleave operasi thread yang menghormati urutan program setiap thread, menjadikannya model memori yang paling intuitif (tetapi sering kali dilonggarkan).