David Rodríguez - dribea menulis dalam komentar di StackOverflow bahwa "Tidak semua koleksi dapat diimplementasikan tanpa kunci". Saya tidak yakin apakah ini benar, dan saya juga tidak dapat menemukan bukti.
Pernyataan ini tidak terlalu tepat, tetapi izinkan saya mencoba untuk mengulanginya dengan cara yang sedikit lebih formal: Untuk setiap jenis pengumpulan C
, ada jenis pengumpulan bebas kunci C
LF yang menawarkan rangkaian operasi yang sama, dan di mana setiap operasi di C
LF memiliki kompleksitas big-O yang sama dengan operasi terkait C
.
Ngomong-ngomong, saya tidak mengharapkan transformasi.
LOCK
instruksi CPU tetapi scheduler thread, melalui mutex / semaphores / etc.Jawaban:
Karena saya sendiri agak bingung, saya mulai dengan mengklarifikasi beberapa konsep dalam pertanyaan.
Koleksi . Saya tidak melihat alasan untuk menghabiskan waktu dengan keras mendefinisikan apa arti "koleksi" ketika kita bisa bertanya apa yang terjadi pada struktur data secara umum. Struktur data menempati sepotong memori dan memiliki beberapa operasi yang dapat mengakses memori itu dan yang dapat diminta oleh pengguna . Pengguna ini mungkin prosesor yang berbeda atau hanya utas yang berbeda, itu bukan urusan kami. Yang penting adalah mereka dapat melakukan operasi secara paralel.
Bebas kunci . Herlihy dan Boss mengatakan bahwa struktur data bebas kunci ketika pengguna yang mogok tidak mencegah penggunaan lebih lanjut dari struktur data. Sebagai contoh, bayangkan seseorang menuangkan air ke prosesor yang ada di tengah-tengah memasukkan sebuah simpul dalam satu set yang diurutkan. Nah, jika prosesor lain mencoba nanti untuk memasukkan ke dalam set yang diurutkan, mereka harus berhasil. ( Sunting: Menurut definisi ini, itu adalah kasus bahwa jika struktur data menggunakan kunci maka itu tidak bebas kunci, tetapi itu bukan kasus bahwa jika struktur data tidak menggunakan kunci maka itu bebas kunci.)
Dengan definisi ini, saya pikir Herlihy dan Boss pada dasarnya mengatakan bahwa jawabannya adalah mengubah daerah kritis menjadi transaksi.
Tetapi, Anda mungkin bertanya, apakah ini memiliki kompleksitas yang sama? Saya tidak yakin pertanyaannya masuk akal. Pertimbangkan
push(x) { lock(); stack[size++] = x; unlock(); }
. Apakah ini operasi waktu yang konstan? Jika Anda mengabaikan operasi penguncian dan karenanya pengguna lain maka Anda dapat menjawab YA. Jika Anda tidak ingin mengabaikan pengguna lain, maka benar-benar tidak ada cara untuk mengatakan apakah push akan berjalan dalam waktu yang konstan. Jika Anda naik satu tingkat dan melihat bagaimana tumpukan digunakan oleh beberapa algoritma tertentu, maka Anda mungkin dapat mengatakan bahwa push akan selalu membutuhkan waktu yang konstan (diukur sekarang dalam hal apa pun yang terjadi menjadi input dari algoritma paralel Anda). Tapi itu benar-benar properti dari algoritma Anda, jadi tidak masuk akal untuk mengatakan bahwa push adalah operasi waktu yang konstan.Singkatnya, jika Anda mengabaikan seberapa banyak pengguna yang menjalankan operasi menunggu pengguna lain, maka menggunakan transaksi alih-alih wilayah kritis menjawab pertanyaan Anda dengan tegas. Jika Anda tidak mengabaikan waktu tunggu, maka Anda perlu melihat bagaimana struktur data digunakan.
sumber
push
operasi yang disebutkan di atas bukanlah operasi waktu yang konstan. Untuk sejumlah prosesor, dan implementasi umumlock
yang tidak menjamin kelaparan, operasi di atas (dalam kasus terburuk, untuk setiap prosesor tertentu membutuhkan N_proc * O (1), yang secara naif dapat dianggap sebagai O (1) ( jumlah prosesor yang diperhitungkan ke dalam konstanta tersembunyi)Saya pikir "KOLEKSI" berarti "antrian, tumpukan, daftar terkait, pohon, ..."
Dari http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
Melalui desain dan implementasi yang cermat, adalah mungkin untuk membangun struktur data yang aman untuk digunakan secara bersamaan tanpa perlu mengelola kunci atau memblokir utas. Struktur data non-pemblokiran ini dapat meningkatkan kinerja dengan memungkinkan konkurensi tambahan dan dapat meningkatkan ketahanan dengan menghindari beberapa masalah yang disebabkan oleh inversi prioritas dalam pengaturan lokal, atau kegagalan mesin dan tautan dalam sistem terdistribusi.
Pengantar keseluruhan terbaik untuk algoritme non-pemblokiran kami adalah makalah Pemrograman bersamaan tanpa kunci, saat ini sedang dalam pengajuan, yang mencakup desain kami untuk membandingkan dan menukar multi-kata, memori transaksional perangkat lunak berbasis kata, dan memori transaksional perangkat lunak berbasis objek.
Jika "bebas kunci" berarti "jangan gunakan semaphore, mutex, monitor sistem operarting ..." maka saya pikir (tapi saya bukan ahli) bahwa setiap koleksi dapat dibuat bebas kunci menggunakan atom read-write- memodifikasi primitif yang harus didukung oleh perangkat keras.
Dokumentasi lengkap tentang masalah ini dapat ditemukan online:
http://www.google.it/search?q=lock+free+algorithm+filetype%3Apdf
(... dan referensi lebih lanjut di akhir setiap dokumen)
sumber