Apa kunci dan konsep Re-entrant secara umum?

Saya selalu bingung. Akankah seseorang menjelaskan apa arti Reentrant dalam konteks yang berbeda? Dan mengapa Anda ingin menggunakan reentrant vs. non-reentrant?

Katakan pthread (posix) mengunci primitif, apakah mereka masuk kembali atau tidak? Perangkap apa yang harus dihindari saat menggunakannya?

Apakah mutex re-entrant?

Penguncian peserta kembali

Kunci reentrant adalah salah satu proses yang dapat mengklaim kunci beberapa kali tanpa memblokirnya sendiri. Ini berguna dalam situasi di mana tidak mudah untuk melacak apakah Anda sudah mengambil kunci. Jika kunci tidak masuk kembali, Anda dapat mengambil kunci tersebut, lalu memblokirnya saat Anda akan mengambilnya lagi, yang secara efektif akan menghentikan proses Anda sendiri.

Reentrancy secara umum adalah properti kode yang tidak memiliki status pusat yang dapat berubah yang dapat rusak jika kode dipanggil saat dijalankan. Panggilan semacam itu dapat dilakukan oleh utas lain, atau dapat dilakukan secara rekursif oleh jalur eksekusi yang berasal dari dalam kode itu sendiri.

Jika kode bergantung pada status bersama yang dapat diperbarui di tengah pelaksanaannya, kode tersebut tidak masuk kembali, setidaknya tidak jika pembaruan itu dapat merusaknya.

Kasus penggunaan untuk penguncian peserta kembali

Contoh (agak umum dan dibuat-buat) dari aplikasi untuk kunci peserta ulang mungkin adalah:

• Anda memiliki beberapa perhitungan yang melibatkan algoritma yang melintasi grafik (mungkin dengan siklus di dalamnya). Traversal dapat mengunjungi node yang sama lebih dari sekali karena siklus atau karena beberapa jalur ke node yang sama.

• Struktur data tunduk pada akses bersamaan dan dapat diperbarui karena alasan tertentu, mungkin oleh utas lain. Anda harus dapat mengunci node individu untuk menangani potensi kerusakan data karena kondisi balapan. Untuk beberapa alasan (mungkin kinerja) Anda tidak ingin mengunci seluruh struktur data secara global.

• Perhitungan Anda tidak dapat menyimpan informasi lengkap tentang node apa yang Anda kunjungi, atau Anda menggunakan struktur data yang tidak memungkinkan pertanyaan 'apakah saya pernah ke sini sebelumnya' untuk dijawab dengan cepat.
  
  Contoh situasi ini akan menjadi implementasi sederhana dari algoritma Dijkstra dengan antrian prioritas yang diimplementasikan sebagai tumpukan biner atau pencarian luas-pertama menggunakan daftar tertaut sederhana sebagai antrian. Dalam kasus ini, memindai antrian untuk penyisipan yang ada adalah O (N) dan Anda mungkin tidak ingin melakukannya di setiap iterasi.

Dalam situasi ini, melacak kunci apa yang sudah Anda peroleh itu mahal. Dengan asumsi Anda ingin melakukan penguncian pada level node, mekanisme penguncian re-entrant mengurangi kebutuhan untuk mengetahui apakah Anda pernah mengunjungi node sebelumnya. Anda dapat mengunci node secara membabi buta, mungkin membukanya setelah Anda mengeluarkannya dari antrean.

Mutex peserta kembali

Mutex sederhana tidak masuk kembali karena hanya satu utas yang dapat berada di bagian kritis pada waktu tertentu. Jika Anda mengambil mutex dan kemudian mencoba mengambilnya lagi, mutex sederhana tidak memiliki cukup informasi untuk mengetahui siapa yang memegangnya sebelumnya. Untuk melakukan ini secara rekursif, Anda memerlukan mekanisme di mana setiap utas memiliki token sehingga Anda dapat mengetahui siapa yang telah mengambil mutex. Ini membuat mekanisme mutex agak lebih mahal sehingga Anda mungkin tidak ingin melakukannya di semua situasi.

IIRC, API utas POSIX memang menawarkan opsi mutex re-entrant dan non re-entrant.

Kunci re-entrant memungkinkan Anda menulis metode Myang mengunci sumber daya Adan kemudian memanggil Msecara rekursif atau dari kode yang sudah menahan kunci A.

Dengan kunci non-peserta ulang, Anda akan memerlukan 2 versi M, satu yang mengunci dan yang tidak, dan logika tambahan untuk memanggil yang benar.

Kunci masuk kembali dijelaskan dengan sangat baik dalam tutorial ini .

Contoh dalam tutorial ini jauh lebih tidak dibuat-buat daripada jawaban tentang melintasi grafik. Kunci masuk kembali berguna dalam kasus yang sangat sederhana.

Apa dan mengapa mutex rekursif bukanlah hal yang rumit seperti yang dijelaskan dalam jawaban yang diterima.

Saya ingin menuliskan pemahaman saya setelah menggali di internet.

Pertama, Anda harus menyadari bahwa ketika berbicara tentang mutex , konsep multi utas pasti terlibat juga. (mutex digunakan untuk sinkronisasi. Saya tidak perlu mutex jika saya hanya memiliki 1 utas di program saya)

Kedua, Anda harus mengetahui perbedaan antara mutex normal dan mutex rekursif .

Dikutip dari APUE :

(Mutex rekursif adalah a) Jenis mutex yang memungkinkan utas yang sama menguncinya beberapa kali tanpa membukanya terlebih dahulu.

Perbedaan utamanya adalah bahwa dalam utas yang sama , mengunci kembali kunci rekursif tidak menyebabkan kebuntuan, tidak juga memblokir utas.

Apakah ini berarti bahwa gembok berulang tidak pernah menyebabkan kebuntuan?
Tidak, itu masih dapat menyebabkan kebuntuan seperti mutex biasa jika Anda telah menguncinya di satu utas tanpa membukanya, dan mencoba menguncinya di utas lain.

Mari kita lihat beberapa kode sebagai bukti.

1. mutex normal dengan kebuntuan

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lock;


void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

keluaran:

thread1
thread1 hey hey
thread2

contoh kebuntuan umum, tidak masalah.

2. mutex rekursif dengan kebuntuan

Hapus saja baris ini
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
dan komentari baris lainnya.

keluaran:

thread1
thread1 hey hey
thread2

Ya, mutex rekursif juga bisa menyebabkan kebuntuan.

3. mutex normal, kunci kembali di utas yang sama

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t lock;


void func3(){
    printf("func3\n");
    pthread_mutex_lock(&lock);
    printf("func3 hey hey\n");
}

void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    func3();
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    sleep(2); 
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

keluaran:

thread1
func3
thread2

Jalan buntu thread t1, masuk func3.
(Saya gunakan sleep(2)untuk mempermudah melihat bahwa kebuntuan pertama-tama disebabkan oleh penguncian kembali func3)

4. mutex rekursif, kunci kembali di utas yang sama

Sekali lagi, hapus komentar pada baris mutex rekursif dan komentari baris lainnya.

keluaran:

thread1
func3
func3 hey hey
thread1 hey hey
thread2

Jalan buntu thread t2, masuk func2. Lihat? func3selesai dan keluar, penguncian ulang tidak menghalangi utas atau menyebabkan kebuntuan.

Jadi, pertanyaan terakhir, mengapa kita membutuhkannya?

Untuk fungsi rekursif (disebut dalam program multi-utas dan Anda ingin melindungi beberapa sumber daya / data).

Misalnya Anda memiliki program multi utas, dan memanggil fungsi rekursif di utas A. Anda memiliki beberapa data yang ingin dilindungi dalam fungsi rekursif itu, jadi Anda menggunakan mekanisme mutex. Eksekusi fungsi itu berurutan di utas A, jadi Anda pasti akan mengunci kembali mutex dalam rekursi. Gunakan mutex normal menyebabkan kebuntuan. Dan mutex resursif diciptakan untuk mengatasi ini.

Lihat contoh dari jawaban yang diterima Kapan menggunakan mutex rekursif? .

Wikipedia menjelaskan mutex rekursif dengan sangat baik. Layak untuk dibaca. Wikipedia: Reentrant_mutex