Apa yang mencegah kondisi balapan pada kunci?

24

Saya mengerti dasar-dasar apa ras data itu, dan bagaimana kunci / mutex / semaphore membantu mencegahnya. Tetapi apa yang terjadi jika Anda memiliki "kondisi lomba" pada kunci itu sendiri? Sebagai contoh, dua utas yang berbeda, mungkin dalam aplikasi yang sama, tetapi berjalan pada prosesor yang berbeda, cobalah untuk mendapatkan kunci pada saat yang bersamaan .

Lalu apa yang terjadi? Apa yang dilakukan untuk mencegah hal itu? Apakah itu mustahil, atau sekadar tidak mungkin? Atau apakah ini kondisi balapan yang nyata yang menunggu untuk terjadi?

multithreading concurrency locks Gavin Howard
sumber
Pertanyaan ini diajukan sebelumnya pada SO: stackoverflow.com/questions/980521/…
Doc Brown
dan pertanyaan terkait di sini di P.SE: programmers.stackexchange.com/questions/228827/…
ratchet freak
Anda mendapatkan kunci untuk mendapatkan kunci;) (dengan kata lain, jika kunci Anda memiliki kondisi balapan, itu tidak diterapkan dengan benar - kunci cukup banyak didefinisikan sebagai konstruksi yang menerapkan pengecualian bersama)
Tangrs
Anda melewatkan poin penting tentang cara kerja kunci. Mereka dibangun sedemikian rupa sehingga tidak mungkin untuk berlomba di kunci, jika tidak mereka sama sekali tidak berguna.
Zane

Jawaban:

36

Apakah itu mustahil, atau sekadar tidak mungkin?

Mustahil. Ini dapat diimplementasikan dengan cara yang berbeda, misalnya, melalui Compare-and-swap di mana perangkat keras menjamin eksekusi berurutan. Ini bisa menjadi sedikit rumit di hadapan beberapa inti atau bahkan beberapa soket dan memerlukan protokol yang rumit antara inti, tetapi ini semua diurus.

maaartinus
sumber
3
Terima kasih ... Tuhan ... itu ditangani dalam perangkat keras ... (atau setidaknya tingkat yang lebih rendah dari yang kita sentuh.)
corsiKa
2
@ gdhoward Saya tidak percaya ... jawaban ini memakan waktu kurang dari 5 menit dan ini adalah yang tertinggi ketiga dari empat ratusan jawaban saya (terutama SO). Dan mungkin juga yang terpendek.
maaartinus
1
@maaartinus - Pendek dan manis kadang melakukannya.
Bobson
17

Pelajari konsep operasi "Uji dan Set" atom.

Pada dasarnya operasi tidak dapat dibagi - dua hal tidak mungkin dilakukan pada waktu yang bersamaan. Ini akan memeriksa nilai, menetapkannya jika jelas, dan mengembalikan nilai seperti saat pengujian. Dalam operasi kunci, hasilnya akan selalu "mengunci == BENAR" setelah tes dan set, satu-satunya perbedaan adalah apakah disetel atau tidak di awal.

Pada tingkat kode mikro dalam prosesor inti tunggal, ini adalah salah satu instruksi yang tidak dapat dibagi, dan mudah diterapkan. Dengan beberapa prosesor dan banyak inti, ini menjadi lebih sulit, tetapi sebagai programmer kita tidak perlu khawatir tentang hal itu, karena dirancang untuk bekerja oleh orang-orang yang benar-benar pintar yang melakukan silikon. Pada dasarnya mereka melakukan hal yang sama - membuat instruksi atom yang merupakan versi percobaan dan set yang mewah

mattnz
sumber
2
Pada dasarnya, jika perangkat keras secara intrinsik tidak berurutan pada tingkat tertentu, itu akan memiliki mekanisme yang memungkinkannya untuk memutuskan hubungan yang mungkin terjadi.
Bill Michell
@ BillMichell, aku seharusnya memikirkan itu. Sebenarnya saya lakukan; Saya hanya tidak tahu apakah asumsi saya benar.
Gavin Howard
2

Sederhananya kode untuk masuk ke bagian kritis dirancang khusus sehingga kondisi balapan tidak akan melanggar pengecualian bersama.

Sebagian besar atom waktu membandingkan dan mengatur loop digunakan yang dijalankan pada tingkat perangkat keras

while(!CompareAndSet(&lock, false, true));//busy loop won't continue until THIS thread has set the lock to true
//critical section
CompareAndSet(&lock, true, false);

Karena tidak ada solusi perangkat lunak yang dipelajari dengan baik untuk memungkinkan saling pengecualian.

ratchet freak
sumber
1

Tidak mungkin dua (atau lebih) utas mendapatkan kunci pada saat yang sama. Ada beberapa jenis metode sinkronisasi misalnya:

Tunggu aktif - kunci putar

Kodesemu:

1. while ( xchg(lock, 1) == 1); - entry protocole

XCHG adalah contoh operasi atom (ada pada arsitektur x86) yang pertama-tama menetapkan nilai baru untuk variabel "kunci" dan kemudian mengembalikan nilai lama. Atomic berarti tidak dapat diinterupsi - dalam contoh di atas antara menetapkan nilai baru dan mengembalikan nilai lama. Atomic - hasil deterministik tidak peduli apa.

2. Your code
3. lock = 0; - exit protocol

Ketika kunci sama dengan 0 utas lainnya dapat masuk ke bagian kritis - sementara loop berakhir.

Penangguhan utas - misalnya menghitung semafor

Ada dua operasi atom .Wait()dan .Signal()dan kami memiliki variabel integer, sebut saja int currentValue.

Wait():
if (currentValue > 0) currentValue -= 1;
else suspend current thread;

Signal():
If there exists thread suspended by semaphore wake up one of them
Else currentValue += 1;

Sekarang memecahkan masalah bagian kritis sangat mudah:

Kodesemu:

mySemaphore.Wait();
do some operations - critical section
mySemaphore.Signal();

Biasanya API utas pemrograman Anda harus memberi Anda kemampuan untuk menentukan utas bersamaan maksimum di bagian kritis semaphore. Jelas ada lebih banyak jenis sinkronisasi dalam sistem multithreaded (mutex, monitor, binary semaphore, dll) tetapi mereka didasarkan pada ide-ide di atas. Orang bisa berargumen bahwa metode yang menggunakan penangguhan thread harus lebih disukai daripada menunggu aktif (jadi cpu tidak sia-sia) - itu tidak selalu benar. Ketika utas sedang ditangguhkan - operasi mahal yang disebut sakelar konteks terjadi. Namun masuk akal ketika waktu tunggu pendek (jumlah utas ~ jumlah inti).

fex
sumber