Jika saya menggunakan kunci, bisakah algoritme saya tetap bebas kunci?

9

Definisi umum bebas kunci adalah bahwa setidaknya satu proses membuat kemajuan. 1

Jika saya memiliki struktur data sederhana seperti antrian, dilindungi oleh kunci, maka satu proses selalu dapat membuat kemajuan, karena satu proses dapat memperoleh kunci, melakukan apa yang diinginkan, dan melepaskannya.

Jadi, apakah itu memenuhi definisi bebas kunci?

1 Lihat misalnya M. Herlihy, V. Luchangco, dan M. Moir. Sinkronisasi bebas halangan: Antrian berujung ganda sebagai contoh. Dalam Distributed Computing, 2003. "Tidak dikunci jika hanya memastikan bahwa beberapa utas selalu membuat kemajuan".

multithreading Joe Pension
sumber
3
Saya selalu mengerti "bebas kunci" untuk menggambarkan struktur data dan serangkaian algoritma yang tidak menggunakan kunci, hanya serangkaian kecil operasi memori atom. Misalnya drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/…
Paul Johnson

Jawaban:

16

Itu bukan definisi untuk bebas kunci.

Jika Anda dapat menjamin kemajuan maka Anda memiliki jalan buntu , dan jika Anda akhirnya menyelesaikan setiap permintaan, maka Anda bebas kelaparan , tetapi tidak bebas kunci.

Saya mempertanyakan apakah contoh sederhana Anda benar-benar memberikan ini. Anda perlu hierarki kunci dan seterusnya untuk benar-benar membuat jaminan kemajuan ketika beberapa kunci terlibat.

Ben Voigt
sumber
1
Saya menggunakan definisi dari M. Herlihy. Metodologi untuk mengimplementasikan objek data yang sangat konkuren. Transaksi pada Bahasa dan Sistem Pemrograman, 1993. "Kondisi bebas-penguncian menjamin bahwa beberapa proses akan selalu membuat kemajuan meskipun secara sewenang-wenang menghentikan kegagalan atau keterlambatan oleh proses lain"
Joe Pension
12
@ Jo: Itu bukan definisi, itu menggambarkan implikasi. Waspadalah dengan logika kesalahan dari invers.
Ben Voigt
2
Bisa juga mengutip M. Herlihy, V. Luchangco, dan M. Moir. Sinkronisasi bebas halangan: Antrian berujung ganda sebagai contoh. Dalam Distributed Computing, 2003. "Tidak dikunci jika hanya memastikan bahwa beberapa utas selalu membuat kemajuan".
Joe Pension
1
ada juga kelaparan gratis yang lebih spesifik daripada kebuntuan gratis (setiap proses dapat berjalan tidak peduli apa proses lain yang dilakukan) perhatikan bahwa loop CaS (berdasarkan primitif atom) tidak
ratchet freak
5
@ Jo: Jika seluruh dunia menyebut properti itu bebas dari kebuntuan , maka saya akan menggunakan istilah itu. Tidak, contoh sederhana Anda tidak bebas dari jalan buntu. Untuk menjamin bahwa ada sesuatu yang bebas dari kebuntuan, Anda tidak hanya perlu sinkronisasi, tetapi juga jaminan bahwa tidak ada utas yang melakukan operasi pemblokiran saat memegang kunci. "melakukan apa yang diinginkannya" sangat kabur dan tampaknya tidak memberikan jaminan ini.
Ben Voigt
11

Saya telah mempelajari The Art of Multiprocessor Programming 1 dan teks mereka kurang jelas, seperti buku yang Anda rujuk. Berikut beberapa kutipan dari TAMPP:

Kutipan 1 (Definisi bebas kunci)

Suatu metode bebas dari penguncian jika menjamin bahwa pemanggilan metode tak terhingga seringkali selesai dalam sejumlah langkah terbatas.

Kutipan 2 (Definisi nonblocking)

doa tertunda dari metode total tidak pernah diperlukan untuk menunggu doa tertunda lain selesai.

Kutipan 3 (klaim bahwa bebas-kunci tidak menghalangi)

Kondisi progres nonblocking bebas-tunggu dan bebas-kunci menjamin bahwa perhitungan secara keseluruhan membuat kemajuan, terlepas dari bagaimana sistem menjadwalkan utas.

Masalahnya adalah bahwa klaim dalam Kutipan 3 tidak jelas mengikuti dari definisi dalam Kutipan 1. Seperti yang telah disebutkan, antrian yang disinkronkan tampaknya memuaskan Kutipan 1: sering kali beberapa metode berhasil mendapatkan kunci dan menyelesaikannya.

Perhatikan secara khusus frasa yang agak kabur dalam Kutipan 3: "terlepas dari bagaimana sistem menjadwalkan utas". Hal ini tidak didahului oleh apapun deskripsi formal dari "sistem benang-penjadwalan", jadi kami yang tersisa untuk merekonstruksi sifat-sifatnya berdasarkan prasangka kita pada apa definisi harus berarti:

  1. sistem selalu menjalankan instruksi dari beberapa utas;
  2. mungkin tidak pernah menjalankan instruksi dari utas tertentu ;
  3. semua utas menggunakan metode yang dipertimbangkan.

Pada sistem seperti itu, metode pemblokiran tidak dapat bebas dari kunci: jika utas yang memegang kunci tidak pernah lagi dijadwalkan untuk dieksekusi, tidak akan ada utas lain yang dapat menyelesaikan permohonan metodenya dalam sejumlah langkah terbatas, namun akan ada beberapa utas yang menjalankan langkah-langkah metode. Untuk sistem yang lebih realistis, yang pada akhirnya menjamin waktu CPU untuk masing-masing utas, definisi tersebut harus secara eksplisit menyertakan properti nonblocking:

Definisi terkoreksi bebas kunci

Metode bebas kunci jika tidak diblokir dan, selain itu, menjamin bahwa pemanggilan metode yang tak terbatas seringkali selesai dalam sejumlah langkah terbatas.

1 Maurice Herlihy, Nir Shavit, Seni Pemrograman Multi-Prosesor, Elsevier 2008, hlm. 58-60

Marko Topolnik
sumber
1
Kata-kata dari kutipan 1 benar-benar aneh. Apa yang mereka maksud dengan "sering kali"? Jelas sesuatu yang berbeda dari "selalu", jadi boleh saja metode ini tidak pernah kembali dalam kasus "beberapa"?
Hulk
Ya, bahasa yang tidak tepat berlimpah. Apa "sering" itu? Saya pikir maksudnya "dalam sejarah eksekusi yang tak terbatas, peristiwa khusus ini terjadi berkali-kali".
Marko Topolnik
5

Terminologi tidak selalu konsisten, tetapi saya pikir yang penting adalah mengajukan pertanyaan berikut tentang algoritma atau sistem yang diusulkan:

  1. Apakah ada urutan peristiwa di mana utas dapat menjadi macet menunggu satu sama lain bahkan jika semua utas diizinkan sepanjang waktu CPU yang dapat mereka gunakan [jika demikian, itu tidak bebas dari kebuntuan]
  2. Jika satu utas diblokir untuk waktu yang lama dan sewenang-wenang, bisakah itu menghentikan utas lainnya atau merusak operasi sistem untuk waktu yang lama secara sewenang-wenang [jika demikian, itu bukan non-pemblokiran].
  3. Apakah ada beberapa kombinasi penjadwalan thread setidaknya yang secara teoritis paling mungkin yang dapat menyebabkan semua thread berulang kali mencoba kembali operasi yang sama sambil membatalkan pekerjaan masing-masing, tanpa ada yang membuat kemajuan [jika demikian, itu tidak bebas dari kunci]
  4. Jika beberapa utas diberikan waktu CPU yang cukup relatif terhadap yang lain, dapatkah mereka memaksa utas yang terakhir untuk terus mencoba kembali operasinya tanpa batas waktu [jika demikian, ini bukan bebas menunggu].

Sebagian besar pentingnya algoritme bebas-kunci bukan berarti lebih cepat daripada algoritme bebas-kunci, melainkan fakta bahwa algoritme tersebut tidak rentan terhadap sekarat jika ada thread yang terhalang [perhatikan bahwa jaminan semacam itu hanya membutuhkan bahwa algoritme menjadi non-pemblokiran, tetapi semua algoritma bebas-kunci adalah]. Algoritme bebas kunci dimungkinkan untuk menggunakan kunci, tetapi hanya jika upaya akuisisi kunci menyertakan batas waktu bersama dengan algoritme untuk memastikan bahwa selalu ada kemungkinan bagi seseorang untuk membuat kemajuan (misalnya, suatu algoritma dapat menggunakan CompareExchangeloop sebagai yang utama metode arbitrase, tetapi gunakan kunci untuk menengahi akses ketika pertikaian tampaknya tinggi, jika kunci tampaknya ditahan terlalu lama, utas lainnya dapat memutuskan untuk meninggalkan upaya untuk menggunakan kunci itu dan alih-alih membuat yang baru.CompareExchange, jika pelanggan meninggalkan kunci tidak akan membahayakan konsistensi sistem, meskipun itu mungkin berarti bahwa kode yang telah menahan kunci lama tidak akan menyelesaikan pekerjaan sampai kunci itu meninggalkan kunci lama dan mengantre untuk kunci yang baru.

supercat
sumber
Ini berbeda dari terminologi standar: 2. Anda merujuk pada makna standar non-blocking, sedangkan 3. merujuk pada kebebasan mengunci.
Marko Topolnik
Saya telah melihat penggunaan terminologi yang tidak konsisten, dan saya tidak tahu standar "resmi". Yang paling penting adalah bahwa ada jaminan yang berbeda yang dapat ditawarkan oleh suatu algoritma, dan penting untuk menggunakan algoritma yang menawarkan jaminan yang cukup untuk memenuhi persyaratan aplikasi. Banyak makalah hanya mencakup beberapa jaminan di atas, tetapi ada beberapa kasus di mana masing-masing mungkin dapat memenuhi persyaratan aplikasi lebih mudah daripada jaminan lain yang akan memenuhi persyaratan.
supercat
Saya pikir ada konsensus bahwa terminologi yang disajikan dalam The Art of Multiprocessor Programming adalah "standar".
Marko Topolnik
@MarkoTopolnik: Saya akan mengedit posting agar sesuai dengan itu. Apakah Anda suka versi baru?
supercat
Keren, sangat bagus.
Marko Topolnik
4

Anda harus melihat "definisi" yang Anda kutip dalam konteks :

Cara tradisional untuk menerapkan struktur data bersama adalah dengan menggunakan saling pengecualian (kunci) untuk memastikan bahwa operasi bersamaan tidak saling mengganggu. Mengunci memiliki sejumlah kelemahan sehubungan dengan rekayasa perangkat lunak, toleransi kesalahan, dan skalabilitas (lihat [8]). Sebagai tanggapan, para peneliti telah menyelidiki berbagai teknik sinkronisasi alternatif yang tidak menggunakan saling pengecualian . Teknik sinkronisasi bebas menunggu jika memastikan bahwa setiap utas akan terus membuat kemajuan dalam menghadapi penundaan sewenang-wenang (atau bahkan kegagalan) utas lainnya. Ini bebas kunci jika hanya memastikan bahwa utas selalu membuat kemajuan.

Anda menggunakan kunci untuk pengecualian bersama, jadi itu bukan teknik bebas kunci yang mereka bicarakan.

vartec
sumber
2

Jika saya menggunakan kunci, bisakah algoritme saya tetap bebas kunci?

Bisa jadi, tapi itu tergantung algoritma.

Jika saya memiliki struktur data sederhana seperti antrian, dilindungi oleh kunci, maka satu proses selalu dapat membuat kemajuan, karena satu proses dapat memperoleh kunci, melakukan apa yang diinginkan, dan melepaskannya.

Jadi, apakah itu memenuhi definisi bebas kunci?

Catatan per se .

Jika langkah "lakukan apa yang diinginkan" tidak melibatkan memperoleh kunci lain, dan dijamin akan selesai dalam waktu yang terbatas, maka bagian khusus dari algoritma Anda ini akan bebas dari kebuntuan.

Namun, jika prasyarat tersebut tidak terpenuhi, setidaknya ada potensi kebuntuan ...

Stephen C
sumber
Setelah beberapa studi teks dalam The Art of Multiprocessor Programming, saya sampai pada kesimpulan bahwa mutexes benar-benar membatalkan definisi bebas kunci, ketika definisi tersebut dieja dengan benar. Saya telah menambahkan jawaban ke halaman ini untuk memperjelas ini.
Marko Topolnik
1

Contoh yang Anda berikan tidak bebas kunci karena alasan berikut.

Mendukung satu utas mendapatkan kunci, dan penjadwal OS menangguhkan utas untuk periode tunggal tanpa batas, maka semua utas tidak dapat membuat kemajuan karena tidak ada yang dapat memperoleh kunci yang diperoleh oleh utas yang ditangguhkan.

Secara umum, algoritma yang menggunakan kunci tidak bebas kunci.

Perhatikan bahwa jalan buntu dan bebas kunci adalah dua konsep yang berbeda. jalan buntu berarti tidak ada kemungkinan kebuntuan, tetapi mungkin ada livelock yang dapat mencegah keseluruhan sistem dari membuat kemajuan. Kunci-kebebasan lebih kuat dari itu karena itu berarti beberapa utas dalam sistem selalu membuat kemajuan dengan sejumlah langkah terbatas.

Chaoran
sumber
Lihatlah definisi yang lebih hati-hati di Wikipedia: "Suatu algoritma bebas kunci jika memuaskan bahwa ketika utas program dijalankan cukup lama, setidaknya salah satu utas membuat kemajuan." Ini tidak termasuk kasus penghentian utas. Kemajuan dalam penghentian juga dicakup oleh kebebasan yang menghalangi , bukan mengunci kebebasan .
Marko Topolnik
@MarkoTopolnik Komentar Anda sama sekali tidak masuk akal. Kunci-kebebasan mencakup obstruksi-kebebasan. Apa pun yang bebas kunci harus bebas hambatan. Dan definisi yang Anda berikan tidak mengecualikan utas penghentian.
Chaoran
Harap berhati-hati untuk membedakan "masuk akal" dari "benar". Komentar saya salah, seperti yang bisa dilihat dari jawaban saya selanjutnya. Tetapi definisi Wikipedia juga salah atau setidaknya ambigu.
Marko Topolnik
@MarkoTopolnik Karena Anda mengakui bahwa komentar Anda tidak benar, Anda harus menghapusnya untuk menghindari membingungkan pembaca lain. Wikipedia sering salah atau ambigu. Anda harus menemukan definisi halus seperti "kunci-kebebasan" dalam makalah akademis seperti cs.rochester.edu/~scott/papers/2006_PPoPP_synch_queues.pdf (definisi bebas-penguncian ada di bagian 2.1)
Chaoran
Ya, termasuk properti nonblocking sebagai bagian dari definisi kebebasan kunci adalah salah satu cara untuk melakukannya. Itu dinyatakan dalam revisi sebelumnya atas jawaban saya.
Marko Topolnik