Semaphore adalah konsep pemrograman yang sering digunakan untuk menyelesaikan masalah multi-threading. Pertanyaan saya kepada komunitas:
Apa itu semaphore dan bagaimana Anda menggunakannya?
multithreading
concurrency
semaphore
bmurphy1976
sumber
sumber
Jawaban:
Pikirkan semaphores sebagai penjaga di klub malam. Ada sejumlah orang yang berdedikasi yang diperbolehkan di klub sekaligus. Jika klub penuh tidak ada yang diizinkan untuk masuk, tetapi begitu satu orang meninggalkan orang lain mungkin masuk.
Ini hanyalah cara untuk membatasi jumlah konsumen untuk sumber daya tertentu. Misalnya, untuk membatasi jumlah panggilan simultan ke database dalam suatu aplikasi.
Ini adalah contoh yang sangat pedagogis dalam C # :-)
sumber
Artikel Mutex dan Semaphores Demystified oleh Michael Barr adalah pengantar singkat yang bagus tentang apa yang membuat mutex dan semaphores berbeda, dan kapan mereka harus dan tidak boleh digunakan. Saya telah mengutip beberapa paragraf utama di sini.
Poin kuncinya adalah bahwa mutex harus digunakan untuk melindungi sumber daya bersama, sementara semaphores harus digunakan untuk pensinyalan. Anda seharusnya tidak menggunakan semaphore untuk melindungi sumber daya bersama, atau mutex untuk pensinyalan. Ada masalah, misalnya, dengan analogi bouncer dalam hal menggunakan semaphore untuk melindungi sumber daya bersama - Anda dapat menggunakannya dengan cara itu, tetapi mungkin menyebabkan sulit untuk mendiagnosis bug.
...
Pada titik ini analogi yang menarik dibuat dengan menggunakan ide kunci kamar mandi sebagai melindungi sumber daya bersama - kamar mandi. Jika toko memiliki kamar mandi tunggal, maka satu kunci akan cukup untuk melindungi sumber daya itu dan mencegah banyak orang menggunakannya secara bersamaan.
Jika ada beberapa kamar mandi, seseorang mungkin tergoda untuk menguncinya sama dan membuat beberapa kunci - ini mirip dengan semaphore yang salah digunakan. Setelah Anda memiliki kunci, Anda sebenarnya tidak tahu kamar mandi mana yang tersedia, dan jika Anda melewati jalan ini, Anda mungkin akan berakhir dengan menggunakan mutex untuk memberikan informasi itu dan pastikan Anda tidak mengambil kamar mandi yang sudah ditempati. .
Semafor adalah alat yang salah untuk melindungi beberapa sumber daya yang pada dasarnya sama, tetapi ini adalah berapa banyak orang yang memikirkannya dan menggunakannya. Analogi bouncer jelas berbeda - tidak ada beberapa jenis sumber daya yang sama, melainkan ada satu sumber daya yang dapat menerima beberapa pengguna secara bersamaan. Saya kira semafor dapat digunakan dalam situasi seperti itu, tetapi jarang ada situasi dunia nyata di mana analogi itu benar-benar terjadi - lebih sering bahwa ada beberapa jenis yang sama, tetapi masih sumber daya individu, seperti kamar mandi, yang tidak dapat digunakan cara ini.
...
...
Di sini poin penting dibuat bahwa mutex mengganggu sistem operasi waktu nyata dengan cara yang buruk, menyebabkan inversi prioritas di mana tugas yang kurang penting dapat dilaksanakan sebelum tugas yang lebih penting karena pembagian sumber daya. Singkatnya, ini terjadi ketika tugas dengan prioritas lebih rendah menggunakan mutex untuk mengambil sumber daya, A, lalu mencoba untuk mengambil B, tetapi dihentikan sementara karena B tidak tersedia. Sementara menunggu, tugas prioritas yang lebih tinggi datang dan membutuhkan A, tetapi sudah diikat, dan oleh proses yang bahkan tidak berjalan karena sedang menunggu B. Ada banyak cara untuk menyelesaikan ini, tetapi paling sering diperbaiki dengan mengubah mutex dan task manager. Mutex jauh lebih kompleks dalam kasus ini daripada semaphore biner,
...
Mutex: berbagi sumber daya
Semaphore: pensinyalan
Jangan gunakan satu untuk yang lain tanpa pertimbangan efek samping.
sumber
Mutex: akses anggota eksklusif ke sumber daya
Semaphore: akses n-anggota ke sumber daya
Artinya, mutex dapat digunakan untuk menyinkronkan akses ke penghitung, file, basis data, dll.
Seorang sempahore dapat melakukan hal yang sama tetapi mendukung sejumlah penelepon simultan. Sebagai contoh, saya dapat membungkus panggilan basis data saya dalam semaphore (3) sehingga aplikasi multithreaded saya akan mencapai basis data dengan paling banyak 3 koneksi simultan. Semua upaya akan diblokir hingga salah satu dari tiga slot terbuka. Mereka membuat hal-hal seperti melakukan pelambatan naif dengan sangat, sangat mudah.
sumber
Pertimbangkan, taksi yang dapat menampung total 3 ( belakang ) +2 ( depan ) orang termasuk pengemudi. Jadi,
semaphore
hanya memungkinkan 5 orang di dalam mobil pada suatu waktu. Danmutex
memungkinkan hanya 1 orang di satu kursi mobil.Oleh karena itu,
Mutex
adalah untuk memungkinkan akses eksklusif untuk sumber daya ( seperti benang OS ) sementaraSemaphore
adalah untuk memungkinkan akses bagi n jumlah sumber daya pada suatu waktu.sumber
@Craig:
Ini tidak terbatas hanya pada satu utas. Semafor dapat dikonfigurasikan untuk memungkinkan sejumlah utas tetap mengakses sumber daya.
sumber
Semaphore juga dapat digunakan sebagai ... semaphore. Misalnya jika Anda memiliki beberapa proses yang meminta data ke antrian, dan hanya satu tugas yang mengkonsumsi data dari antrian. Jika Anda tidak ingin tugas memakan Anda terus-menerus polling antrian untuk data yang tersedia, Anda dapat menggunakan semaphore.
Di sini semaphore tidak digunakan sebagai mekanisme pengecualian, tetapi sebagai mekanisme pensinyalan. Tugas memakan menunggu di semaphore. Tugas memproduksi memposting di semaphore.
Dengan cara ini, tugas yang memakan waktu dijalankan kapan dan hanya ketika ada data yang harus di-dequeued
sumber
Ada dua konsep penting untuk membangun program bersamaan - sinkronisasi dan saling pengecualian. Kita akan melihat bagaimana kedua jenis penguncian ini (semaphore lebih umum merupakan semacam mekanisme penguncian) membantu kami mencapai sinkronisasi dan saling pengecualian.
Semaphore adalah konstruk pemrograman yang membantu kita mencapai konkurensi, dengan mengimplementasikan sinkronisasi dan pengecualian bersama. Semafor terdiri dari dua jenis, Biner dan Menghitung.
Semafor memiliki dua bagian: penghitung, dan daftar tugas yang menunggu untuk mengakses sumber daya tertentu. Semafor melakukan dua operasi: tunggu (P) [ini seperti mendapatkan kunci], dan lepaskan (V) [mirip dengan melepaskan kunci] - ini adalah hanya dua operasi yang dapat dilakukan seseorang pada semafor. Dalam semaphore biner, penghitung secara logis berjalan antara 0 dan 1. Anda dapat menganggapnya mirip dengan kunci dengan dua nilai: buka / tutup. Semaphore penghitungan memiliki beberapa nilai untuk penghitungan.
Yang penting untuk dipahami adalah bahwa penghitung semaphore melacak jumlah tugas yang tidak harus diblokir, yaitu, mereka dapat membuat kemajuan. Tugas memblokir, dan menambahkan diri mereka ke daftar semaphore hanya ketika penghitung adalah nol. Oleh karena itu, tugas ditambahkan ke daftar di rutin P () jika tidak dapat berlanjut, dan "dibebaskan" menggunakan rutin V ().
Sekarang, cukup jelas untuk melihat bagaimana semaphore biner dapat digunakan untuk menyelesaikan sinkronisasi dan saling pengecualian - mereka pada dasarnya terkunci.
ex. Sinkronisasi:
Dalam contoh di atas, B2 hanya dapat mengeksekusi setelah B1 telah menyelesaikan eksekusi. Katakanlah utas A dijalankan terlebih dahulu - sampai ke sem.P (), dan menunggu, karena penghitungnya 0 (tertutup). Thread B datang, menyelesaikan B1, dan kemudian membebaskan thread A - yang kemudian menyelesaikan B2. Jadi kami mencapai sinkronisasi.
Sekarang mari kita lihat saling pengecualian dengan semaphore biner:
Pengecualian satu sama lain juga cukup sederhana - m1 dan m2 tidak dapat memasuki bagian kritis pada saat yang sama. Jadi setiap utas menggunakan semafor yang sama untuk memberikan pengecualian bersama untuk dua bagian kritisnya. Sekarang, mungkinkah memiliki konkurensi yang lebih besar? Tergantung pada bagian kritis. (Pikirkan tentang bagaimana lagi orang dapat menggunakan semaphores untuk mencapai pengecualian bersama .. petunjuk: apakah saya hanya perlu menggunakan satu semaphore?)
Menghitung semaphore: Semaphore dengan lebih dari satu nilai. Mari kita lihat apa artinya ini - kunci dengan lebih dari satu nilai ?? Jadi buka, tutup, dan ... hmm. Apa gunanya multi-stage-lock dalam pengecualian atau sinkronisasi timbal balik?
Mari kita ambil yang lebih mudah dari keduanya:
Sinkronisasi menggunakan semaphore penghitungan: Katakanlah Anda memiliki 3 tugas - # 1 dan 2 yang ingin Anda jalankan setelah 3. Bagaimana Anda mendesain sinkronisasi Anda?
Jadi jika semaphore Anda dimulai dengan ditutup, Anda memastikan bahwa blok t1 dan t2, ditambahkan ke daftar semaphore. Kemudian datanglah semua t3 penting, menyelesaikan bisnisnya dan membebaskan t1 dan t2. Dalam urutan apa mereka dibebaskan? Bergantung pada implementasi daftar semaphore. Bisa jadi FIFO, bisa berdasarkan beberapa prioritas tertentu, dll. (Catatan: pikirkan tentang bagaimana Anda akan mengatur P dan V Anda; jika Anda ingin t1 dan t2 dieksekusi dalam urutan tertentu, dan jika Anda tidak mengetahui implementasi semaphore)
(Cari tahu: Apa yang terjadi jika jumlah V lebih besar dari jumlah P?)
Pengecualian Saling Menggunakan penghitungan semaphores: Saya ingin Anda membuat pseudocode Anda sendiri untuk ini (membuat Anda memahami hal-hal lebih baik!) - tetapi konsep dasarnya adalah ini: semaphore penghitungan counter = N memungkinkan N tugas untuk memasuki bagian kritis dengan bebas . Apa artinya ini adalah Anda memiliki tugas N (atau utas, jika Anda suka) memasuki bagian kritis, tetapi tugas N + 1 diblokir (masuk dalam daftar tugas yang diblokir favorit kami), dan hanya dibiarkan masuk ketika seseorang sedang berada di semaphore setidaknya sekali. Jadi penghitung semafor, alih-alih berayun antara 0 dan 1, sekarang beralih antara 0 dan N, memungkinkan tugas N untuk bebas masuk dan keluar, menghalangi siapa pun!
Nah, mengapa Anda perlu hal bodoh seperti itu? Bukankah inti dari saling pengecualian untuk tidak membiarkan lebih dari satu orang mengakses sumber daya ?? (Petunjuk ... Anda tidak selalu hanya memiliki satu drive di komputer Anda, bukan ...)
Pikirkan : Apakah saling pengecualian dicapai dengan memiliki semaphore penghitungan saja? Bagaimana jika Anda memiliki 10 instance sumber daya, dan 10 utas masuk (melalui semaphore penghitungan) dan mencoba menggunakan instance pertama?
sumber
Semaphore adalah objek yang berisi bilangan asli (yaitu bilangan bulat lebih besar atau sama dengan nol) di mana dua operasi modifikasi didefinisikan. Satu operasi,,
V
menambahkan 1 ke alam. Operasi lainnyaP
,, mengurangi bilangan asli dengan 1. Kedua aktivitas bersifat atomik (yaitu tidak ada operasi lain yang dapat dijalankan bersamaan dengan aV
atau aP
).Karena bilangan asli 0 tidak dapat diturunkan, memanggil
P
semafor yang berisi 0 akan memblokir pelaksanaan proses pemanggilan (/ utas) hingga beberapa saat ketika bilangan tersebut tidak lagi 0 danP
dapat berhasil (dan secara atom) dieksekusi.Seperti disebutkan dalam jawaban lain, semaphore dapat digunakan untuk membatasi akses ke sumber daya tertentu ke jumlah maksimum (tetapi variabel) proses.
sumber
Saya telah menciptakan visualisasi yang seharusnya membantu memahami ide tersebut. Semaphore mengontrol akses ke sumber daya bersama di lingkungan multithreading.
Keluaran
Kode sampel dari artikel
sumber
Bendera perangkat keras atau perangkat lunak. Dalam sistem multi-tasking, semaphore adalah sebagai variabel dengan nilai yang menunjukkan status sumber daya yang sama. Proses yang membutuhkan sumber daya memeriksa semaphore untuk menentukan status sumber daya dan kemudian memutuskan bagaimana untuk melanjutkan.
sumber
Semaphores bertindak seperti pembatas utas.
Contoh: Jika Anda memiliki kumpulan 100 utas dan Anda ingin melakukan beberapa operasi DB. Jika 100 utas mengakses DB pada waktu tertentu, maka mungkin ada masalah penguncian dalam DB sehingga kita dapat menggunakan semaphore yang hanya memperbolehkan utas terbatas pada satu waktu. Contoh di bawah hanya mengizinkan satu utas pada satu waktu. Ketika sebuah thread memanggil
acquire()
metode, maka ia akan mendapatkan akses dan setelah memanggilrelease()
metode, itu akan melepaskan akses sehingga utas berikutnya akan mendapatkan akses.sumber
Jadi bayangkan semua orang mencoba pergi ke kamar mandi dan hanya ada sejumlah kunci ke kamar mandi. Sekarang jika tidak ada kunci yang tersisa, orang itu perlu menunggu. Jadi pikirkan semaphore sebagai mewakili set kunci yang tersedia untuk kamar mandi (sumber daya sistem) yang prosesnya berbeda (pengunjung kamar mandi) dapat meminta akses.
Sekarang bayangkan dua proses mencoba pergi ke kamar mandi secara bersamaan. Itu bukan situasi yang baik dan semafor digunakan untuk mencegah hal ini. Sayangnya, semaphore adalah mekanisme dan proses sukarela (pengunjung kamar mandi kami) dapat mengabaikannya (yaitu bahkan jika ada kunci, seseorang masih bisa hanya menendang pintu terbuka).
Ada juga perbedaan antara biner / mutex & penghitungan semaphores.
Lihatlah catatan kuliah di http://www.cs.columbia.edu/~jae/4118/lect/L05-ipc.html .
sumber
Ini adalah pertanyaan lama tapi salah satu kegunaan semaphore yang paling menarik adalah kunci baca / tulis dan belum disebutkan secara eksplisit.
Kunci r / w bekerja dengan cara sederhana: gunakan satu izin untuk pembaca dan semua izin untuk penulis. Memang, implementasi sepele dari ar / w lock tetapi membutuhkan modifikasi metadata saat dibaca (sebenarnya dua kali) yang dapat menjadi leher botol, masih jauh lebih baik daripada mutex atau kunci.
Kelemahan lain adalah bahwa penulis dapat memulai dengan mudah juga kecuali jika semafor itu adil atau penulis mendapatkan izin dalam beberapa permintaan, dalam kasus seperti itu mereka membutuhkan hubungan eksplisit antara mereka sendiri.
Baca lebih lanjut :
sumber
Semaphore adalah cara untuk mengunci sumber daya sehingga dijamin bahwa sementara sepotong kode dieksekusi, hanya potongan kode ini yang memiliki akses ke sumber daya itu. Ini menjaga dua utas agar tidak secara bersamaan mengakses sumber daya, yang dapat menyebabkan masalah.
sumber