Struktur data pohon konkuren bebas-waktu-update yang konstan?

20

Saya telah membaca sedikit literatur belakangan ini, dan telah menemukan beberapa struktur data yang agak menarik.

Saya telah meneliti berbagai metode untuk menurunkan waktu pembaruan menjadi waktu pembaruan terburuk [1-7].O(1)

Baru-baru ini saya mulai mencari struktur data bebas kunci, untuk mendukung akses bersamaan yang efisien.

Apakah ada teknik update-waktu terburuk yang pernah digunakan dalam penerapan struktur data bebas-kunci?O(1)

Saya bertanya karena; bagi saya, mereka tampak seperti perpanjangan praktis yang jelas dari "peningkatan teoritis" ini.

  1. Tarjan, Robert Endre. "Memperbarui Pohon Pencarian yang Seimbang dalam O (1) Rotasi." Pemrosesan Informasi Huruf 16, no. 5 (1983): 253 - 257.

  2. Driscoll, JR, N Sarnak, DD Sleator, dan RE Tarjan. "Membuat Struktur Data Persisten." Dalam Prosiding Simposium ACM Tahunan Kedelapan Belas tentang Teori Komputasi, 109-121. STOC '86. New York, NY, AS: ACM, 1986.

  3. Levcopoulos, C., dan Mark H. Overmars. “Pohon Pencarian Seimbang dengan O (1) Waktu Pembaruan Kasus Terburuk.” Acta Inf. 26, tidak. 3 (November 1988): 269–277.

  4. Fleischer, Rudolf. Pohon Pencarian Seimbang Sederhana Dengan O (1) Waktu Pembaruan Terburuk

  5. Dietz, Paul F, dan Rajeev Raman. "Pohon Pembaruan Waktu Pencarian Jari yang Konstan." Informasi Memproses Huruf 52, no. 3 (1994): 147 - 154.

  6. Lagogiannis, George, Christos Makris, Yannis Panagis, Spyros Sioutas, dan Kostas Tsichlas. “Pohon Pencarian Seimbang Dinamis Baru dengan Waktu Pembaruan Konstan Terburuk.” J. Autom. Lang. Sisir. 8, tidak. 4 (Juli 2003): 607–632.

  7. Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, dan Kostas Tsichlas. "Pohon Pencarian Jari Optimal di Mesin Pointer." J. Comput. Syst. Sci. 67, tidak. 2 (September 2003): 381-418.

reference-request data-structures time-complexity concurrency search-trees DI
sumber
2
Harap pertimbangkan untuk menambahkan tautan ke makalah sebagai rasa hormat kepada orang-orang yang ingin menyelidiki masalah Anda.
Raphael
3
Oke, ditambahkan tautan ke artikel masing-masing.
AT
1
Saya sarankan pengajuan ulang di cstheory.SE (dengan tautan kembali ke sini) jika Anda tidak segera mendapatkan tanggapan yang bermanfaat.
JeffE
1
Terima kasih untuk sarannya. Saya telah memposting ulang: Struktur data pohon konkuren bebas waktu pembaruan yang konstan?
AT
Saya menggunakan pustaka struktur data bebas kunci Praktis sebelumnya. Mereka memiliki beberapa dukungan struktur data pohon bebas-kunci. Mungkin memiliki apa yang Anda cari.
Reza

Jawaban:

4

tidak membantu dalam dan dari dirinya sendiri. Dalam struktur data bebas-kunci, perlu ada instance atom tunggal ketika struktur data Anda tampaknya berubah. Semuainvarian representasiharus berlaku segera sebelum dan segera setelah instan atom itu.O(1)

Ini berarti bahwa jika Anda melakukan modifikasi pada struktur data karakteristik penting adalah bahwa Anda dapat melakukan semua mod pada struktur data pribadi dan kemudian menukar modifikasi dalam instruksi atom tunggal.

Kunci-kebebasan biasanya paling mudah ketika struktur data Anda tidak dapat diubah ( berfungsi murni ). Anda cukup menyimpan pointer global ke versi saat ini dari struktur data. Pembaca tidak perlu mengunci apa pun. Modifikasi pada struktur data dilakukan dengan menukar penunjuk global ke satu struktur data yang tidak dapat diubah lainnya.

Misalnya: jika Anda memiliki pohon seimbang pohon murni fungsional Anda:

  1. Rekam pointer global saat ini ke akar pohon.
  2. Buat pohon baru yang menyisipkan atau menghapus simpul. (Ini adalah logaritmik dalam waktu dan ruang dalam jumlah node saat ini di pohon, dan melibatkan pembuatan node baru dari titik modifikasi hingga ke root, dan hanya menunjukkan segala sesuatu yang baru di bagian lama dari versi sebelumnya dari struktur data. )
  3. Bandingkan dan tukarkan secara global pointer global ke root. (Perhatikan bahwa ini mungkin gagal jika modifikasi lain telah terjadi antara waktu Anda merekam pointer root lama dan sekarang. Jika ini terjadi, Anda kembali ke langkah 1 dan coba lagi. Ini disebut "kontrol konkurensi optimis.")

Perhatikan bahwa bagian terpenting adalah apa yang saya katakan di atas tentang perlunya mempertahankan invarian perwakilan. Biasanya tidak cukup untuk memiliki algoritma yang secara atomis membuat perubahan di tengah pohon. Mengapa? Misalnya: Anda mungkin memiliki utas pembaca yang sedang dalam proses melakukan preorder traversal dari pohon. Jika Anda memodifikasi sebuah simpul yang merupakan leluhur dari simpul yang sedang mereka baca maka Anda akan membatalkan prasyarat yang menurut mereka telah ditegakkan. Pembaca harus dapat bekerja dengan struktur data persis seperti sebelum Anda membuat perubahan, atau persis seperti yang akan terjadi setelah Anda membuat perubahan. Bukan sesuatu di antaranya.

O(log(N))O(N)

Logika Pengembaraan
sumber
Saya pikir teknik menunggu aktif, misalnya dengan membandingkan-dan-swap, biasanya disebut "bebas kunci" sehingga ada beberapa jalan keluar, bahkan dalam pengaturan yang bisa berubah.
Raphael
Saya tidak terbiasa dengan istilah menunggu aktif (dan Google tidak membantu). (Jika Anda berbicara tentang karya Kogan dan Petrank, itu menunjukkan cara mengubah algoritme bebas-kunci menjadi bebas-menunggu.) Saya menambahkan suntingan tentang bagaimana Anda dapat menangani ketidakmampuan untuk kebebasan kunci pada umumnya.
Pengembaraan Logika
Yang dimaksud dengan "menunggu aktif" adalah sesuatu seperti di while ( !P ) { noOp(); } doWork();mana noOpmungkin berada sleepatau serupa.
Raphael
Di bagian Edit , Anda menyebutkan teknik untuk membuat struktur data yang dapat diubah menjadi bebas kunci. Seperti yang ditunjukkan, kami menyalin seluruh struktur data, membuat mod ke salinan, dan kemudian menggunakan CAS primitive. Namun, bagaimana cara membuat Copylangkah atom? Tampaknya menjadi masalah sulit lainnya atomic snapshot.
hengxin
@ Hengxin: pikirkan primitif CAS sebagai operator "publikasikan". Sebelum struktur data diterbitkan, hanya utas yang melakukan modifikasi yang memiliki akses ke sana. Setelah struktur data diterbitkan, itu tidak berubah. Langkah penyalinan tidak perlu bersifat atomik karena satu-satunya hal yang dapat disalin oleh thread adalah versi yang diterbitkan, yang tidak dapat diubah. Jika dua utas secara bersamaan mencoba untuk bermutasi, keduanya menyalin struktur data yang tidak berubah yang sama, memodifikasi salinan lokal mereka, dan kemudian salah satu operasi CAS berhasil dan yang lainnya gagal. Yang gagal perlu menyalin dan memperbarui.
Pengembaraan Logika