Adakah Barisan Berbilang Pengeluar/Berbilang Pengguna Sempadan Benar-Benar Tanpa Kunci?

Analisis Algoritma Baris Tanpa Kunci

Soalan: Adakah algoritma baris gilir bersempadan berbilang pengeluar/berbilang pengguna dalam liblfds tanpa kunci?

Definisi Tanpa Kunci:

Algoritma tanpa kunci memastikan bahawa sekurang-kurangnya satu utas boleh membuat kemajuan ke hadapan tanpa mengira sebarang urutan serentak. Ini bermakna ia tidak boleh mempunyai kod di mana urutan bergantung pada satu lagi untuk meneruskan, seperti menunggu bendera ditetapkan semula atau dinyahtetapkan.

Analisis Algoritma:

algoritma menyimpan slot dalam baris gilir menggunakan gelung CAS untuk menambah indeks tulis. Ia kemudian menyalin data pengguna ke dalam slot yang dikhaskan dan mengemas kini nombor urutan. Walau bagaimanapun, tempahan ini bermakna bahawa operasi POP bergantung pada urutan PUSH yang melengkapkan kemas kini nombor jujukan.

Kekurangan Jaminan Kemajuan:

Mengikut takrifan "membuat kemajuan," algoritma tidak memenuhi kriteria bebas kunci. Barisan gilir boleh diperhatikan sebagai penuh atau kosong walaupun operasi PUSH atau POP sedang berjalan, menghalang urutan lain daripada melaksanakan operasi tersebut.

Kemajuan Disekat Separa:

Semasa algoritma mungkin membenarkan operasi POP diteruskan sehingga elemen dalam proses, kemajuan ini terhad. Jika urutan dialihkan konteks semasa kawasan kritikal antara kemas kini indeks tulis dan penulisan nombor urutan, semua urutan pengguna akan melaporkan baris gilir kosong.

Mutex Tersembunyi:

Gabungan indeks tulis dan nombor turutan slot pada asasnya bertindak sebagai mutek per-elemen. Sebaik sahaja benang berjaya menambah indeks tulis, semua urutan berikutnya dihalang daripada menulis ke baris gilir sehingga urutan asal menyelesaikan operasi.

Kelebihan Prestasi:

Walaupun tidak kerana bebas kunci, algoritma menawarkan kelebihan prestasi dari segi daripada:

• Prestasi tanpa lawan: Laluan pantas terdiri daripada satu operasi CompareAndSwap.
• Prestasi dipertandingkan: Pembolehubah indeks tulis dipertikaikan, tetapi tingkah laku adalah munasabah dengan baik- CAS yang dioptimumkan pelaksanaan.

Kesimpulan:

Walaupun algoritma menyediakan beberapa sifat prestasi yang berguna, ia tidak mempunyai sifat ketepatan utama operasi bebas kunci disebabkan oleh sistem tempahan dan pergantungan antara operasi PUSH dan POP.

Atas ialah kandungan terperinci Adakah Barisan Berbilang Pengeluar/Berbilang Pengguna Sempadan Benar-Benar Tanpa Kunci?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!