Sinkronisasi dan Kebebasan dari Data-Race

Mekanisme sinkronisasi mengoordinasikan utas konkuren sehingga data bersama diakses dengan aman, dan kebebasan dari data-race adalah properti yang membuat program konkuren dapat diprediksi.

Definition

Sinkronisasi adalah koordinasi aktivitas konkuren untuk memberlakukan pengurutan atau pengecualian bersama pada sumber daya bersama, dan kebebasan dari data-race adalah properti bahwa tidak ada dua utas yang mengakses lokasi memori yang sama secara konkuren dengan setidaknya satu penulisan tanpa sinkronisasi yang mengintervensi.

Scope

Topik ini mencakup mekanisme dan properti yang membuat akses konkuren ke status bersama menjadi benar: pengecualian bersama (mutual exclusion), kunci (locks), semafor dan monitor, variabel kondisi, algoritma bebas kunci (lock-free) dan bebas tunggu (wait-free), memori transaksional, relasi happens-before, dan deteksi data race. Ini membahas kebuntuan (deadlock), atomisitas, dan disiplin yang diperlukan untuk menjaga program bebas dari data-race.

Core questions

• Bagaimana pengecualian bersama dicapai dan apa bahayanya (deadlock, kelaparan)?
• Apa yang membedakan sinkronisasi berbasis kunci dari sinkronisasi bebas kunci?
• Bagaimana relasi happens-before mendefinisikan data race?
• Bagaimana data race dapat dideteksi secara otomatis?

Key theories

Pengecualian bersama

Solusi Dijkstra untuk masalah kontrol konkuren menetapkan pengecualian bersama sebagai persyaratan sinkronisasi fundamental, menjamin bahwa bagian kritis tidak dieksekusi secara bersamaan.

Memori transaksional

Herlihy dan Moss mengusulkan memori transaksional, di mana kelompok operasi memori dieksekusi secara atomik, menawarkan alternatif yang dapat disusun untuk penguncian berbutir halus untuk membangun struktur data konkuren.

Happens-before dan deteksi race dinamis

Berdasarkan relasi happens-before Lamport, detektor Eraser menunjukkan cara menemukan data race secara dinamis dengan memeriksa disiplin penguncian, mencontohkan deteksi race otomatis.

Clinical relevance

Sinkronisasi yang benar sangat penting untuk perangkat lunak konkuren dan paralel yang andal; data race menyebabkan beberapa bug yang paling sulit dipahami dalam praktiknya. Detektor race, memori transaksional, dan pola sinkronisasi yang disiplin adalah alat utama untuk membangun sistem multithread yang dapat diandalkan.

History

Solusi pengecualian bersama Dijkstra pada tahun 1965 dan semafornya kemudian menjadi dasar sinkronisasi, diikuti oleh monitor Hoare dan Brinch Hansen. Relasi happens-before Lamport pada tahun 1978 mendasari definisi race modern; Herlihy dan Moss memperkenalkan memori transaksional pada tahun 1993, dan detektor race dinamis seperti Eraser (1997) dan alat happens-before selanjutnya menjadi standar untuk debugging konkurensi.

Debates

Pendekatan kunci versus bebas kunci dan transaksional

Para perancang memperdebatkan sinkronisasi berbasis kunci tradisional, yang sederhana tetapi rentan terhadap kebuntuan dan komposisi yang buruk, dibandingkan dengan algoritma bebas kunci dan memori transaksional, yang meningkatkan komposisi dan jaminan kemajuan dengan biaya kompleksitas atau overhead.

Key figures

• Edsger Dijkstra
• Leslie Lamport
• Maurice Herlihy
• C. A. R. Hoare
• Stefan Savage

Seminal works

• dijkstra1965
• herlihy1993
• savage1997
• lamport1978

Frequently asked questions

Apa itu data race?

Data race terjadi ketika dua utas mengakses lokasi memori yang sama secara konkuren, setidaknya satu akses adalah penulisan, dan akses tersebut tidak diurutkan oleh sinkronisasi, yang mengarah pada perilaku yang tidak terdefinisi atau tidak dapat diprediksi di sebagian besar model memori.

Apa perbedaan antara sinkronisasi berbasis kunci dan bebas kunci?

Sinkronisasi berbasis kunci menggunakan pengecualian bersama sehingga hanya satu utas yang memasuki bagian kritis pada satu waktu, sementara sinkronisasi bebas kunci menggunakan operasi atomik untuk menjamin bahwa beberapa utas selalu membuat kemajuan tanpa memegang kunci, menghindari kebuntuan.