Apa sebenarnya fungsi reentrant?

Sebagian besar dari para kali , definisi reentrance yang dikutip dari Wikipedia :

Suatu program komputer atau rutin digambarkan sebagai reentrant jika ia dapat dipanggil kembali dengan aman sebelum pemanggilannya yang sebelumnya selesai (mis. Ia dapat dijalankan dengan aman secara bersamaan). Untuk menjadi reentrant, program komputer atau rutin:

1. Tidak boleh menyimpan data statis atau global yang tidak konstan.
2. Tidak boleh mengembalikan alamat ke data tidak konstan statis (atau global).
3. Harus bekerja hanya pada data yang disediakan oleh pemanggil.
4. Jangan mengandalkan kunci untuk sumber daya tunggal.
5. Tidak boleh memodifikasi kodenya sendiri (kecuali mengeksekusi di penyimpanan utasnya sendiri)
6. Tidak boleh memanggil program atau rutinitas komputer yang tidak merujuk kembali.

Bagaimana didefinisikan dengan aman ?

Jika suatu program dapat dieksekusi dengan aman secara bersamaan , apakah itu selalu berarti bahwa itu reentrant?

Apa sebenarnya benang merah antara enam poin yang disebutkan yang harus saya ingat ketika memeriksa kode saya untuk kemampuan reentrant?

Juga,

1. Apakah semua fungsi rekursif reentrant?
2. Apakah semua fungsi thread-safe reentrant?
3. Apakah semua fungsi rekursif dan thread-safe reentrant?

Saat menulis pertanyaan ini, satu hal muncul di benak saya: Apakah istilah seperti reentrance dan thread safety absolut sama sekali yaitu apakah mereka telah menetapkan definisi konkret? Sebab, jika tidak, pertanyaan ini tidak terlalu berarti.

1. Bagaimana cara didefinisikan dengan aman ?

Secara semantik. Dalam hal ini, ini bukan istilah yang sulit didefinisikan. Itu hanya berarti "Anda bisa melakukan itu, tanpa risiko".

2. Jika suatu program dapat dijalankan dengan aman secara bersamaan, apakah itu selalu berarti bahwa itu reentrant?

Tidak.

Sebagai contoh, mari kita memiliki fungsi C ++ yang mengambil kunci, dan panggilan balik sebagai parameter:

#include <mutex>

typedef void (*callback)();
std::mutex m;

void foo(callback f)
{
    m.lock();
    // use the resource protected by the mutex

    if (f) {
        f();
    }

    // use the resource protected by the mutex
    m.unlock();
}

Fungsi lain mungkin perlu mengunci mutex yang sama:

void bar()
{
    foo(nullptr);
}

Pada pandangan pertama, semuanya tampak baik-baik saja ... Tapi tunggu:

int main()
{
    foo(bar);
    return 0;
}

Jika kunci pada mutex tidak rekursif, maka inilah yang akan terjadi, di utas utama:

1. mainakan menelepon foo.
2. foo akan mendapatkan kunci.
3. fooakan memanggil bar, yang akan memanggil foo.
4. yang ke-2 foo akan mencoba mendapatkan kunci, gagal dan menunggu sampai dilepaskan.
5. Jalan buntu.
6. Ups ...

Oke, saya curang, menggunakan panggilan balik. Tetapi mudah untuk membayangkan potongan kode yang lebih kompleks yang memiliki efek serupa.

3. Apa sebenarnya benang merah antara enam poin yang disebutkan yang harus saya ingat ketika memeriksa kode saya untuk kemampuan reentrant?

Anda dapat mencium masalah jika fungsi Anda memiliki / memberikan akses ke sumber daya persisten yang dapat dimodifikasi, atau memiliki / memberikan akses ke fungsi yang berbau .

( Oke, 99% kode kita harus berbau, lalu ... Lihat bagian terakhir untuk mengatasinya ... )

Jadi, mempelajari kode Anda, salah satu poin itu harus mengingatkan Anda:

1. Fungsi memiliki status (mis. Mengakses variabel global, atau bahkan variabel anggota kelas)
2. Fungsi ini dapat dipanggil oleh banyak utas, atau dapat muncul dua kali dalam tumpukan saat proses sedang dijalankan (yaitu fungsi tersebut dapat memanggil dirinya sendiri, langsung atau tidak langsung). Berfungsi menerima panggilan balik karena parameter sangat berbau .

Perhatikan bahwa non-reentrancy adalah viral: Suatu fungsi yang dapat memanggil fungsi non-reentrant tidak dapat dianggap reentrant.

Perhatikan juga, bahwa metode C ++ berbau karena mereka memiliki aksesthis , jadi Anda harus mempelajari kode untuk memastikan mereka tidak memiliki interaksi lucu.

4.1. Apakah semua fungsi rekursif reentrant?

Tidak.

Dalam kasus multithreaded, fungsi rekursif mengakses sumber daya bersama dapat dipanggil oleh banyak utas pada saat yang sama, menghasilkan data yang buruk / rusak.

Dalam kasus singlethreaded, fungsi rekursif dapat menggunakan fungsi non-reentrant (seperti yang terkenal strtok), atau menggunakan data global tanpa menangani fakta data sudah digunakan. Jadi fungsi Anda bersifat rekursif karena ia memanggil dirinya secara langsung atau tidak langsung, tetapi masih bisa bersifat rekursif-tidak aman .

4.2. Apakah semua fungsi thread-safe reentrant?

Dalam contoh di atas, saya menunjukkan bagaimana fungsi threadsafe ternyata tidak reentrant. OK, saya curang karena parameter panggilan balik. Tetapi kemudian, ada beberapa cara untuk mem-deadlock sebuah utas dengan membuatnya memperoleh dua kali kunci non-rekursif.

4.3. Apakah semua fungsi rekursif dan thread-safe reentrant?

Saya akan mengatakan "ya" jika dengan "rekursif" yang Anda maksud adalah "rekursif-aman".

Jika Anda dapat menjamin bahwa suatu fungsi dapat dipanggil secara bersamaan oleh beberapa utas, dan dapat memanggil dirinya sendiri, secara langsung atau tidak langsung, tanpa masalah, maka itu adalah reentrant.

Masalahnya adalah mengevaluasi jaminan ini ... ^ _ ^

5. Apakah istilah seperti reentrance dan keselamatan ulir benar-benar mutlak, yaitu apakah mereka telah menetapkan definisi konkret?

Saya percaya mereka melakukannya, tetapi kemudian, mengevaluasi suatu fungsi adalah thread-safe atau reentrant bisa sulit. Inilah sebabnya saya menggunakan istilah bau di atas: Anda dapat menemukan suatu fungsi bukan reentrant, tetapi bisa jadi sulit untuk memastikan sepotong kode kompleks reentrant

6. Contoh

Katakanlah Anda memiliki objek, dengan satu metode yang perlu menggunakan sumber daya:

struct MyStruct
{
    P * p;

    void foo()
    {
        if (this->p == nullptr)
        {
            this->p = new P();
        }

        // lots of code, some using this->p

        if (this->p != nullptr)
        {
            delete this->p;
            this->p = nullptr;
        }
    }
};

Masalah pertama adalah bahwa jika entah bagaimana fungsi ini disebut secara rekursif (yaitu fungsi ini memanggil dirinya sendiri, secara langsung atau tidak langsung), kode tersebut mungkin akan macet, karena this->p akan dihapus pada akhir panggilan terakhir, dan masih mungkin digunakan sebelum akhir panggilan pertama.

Dengan demikian, kode ini tidak aman secara rekursif .

Kami dapat menggunakan penghitung referensi untuk memperbaikinya:

struct MyStruct
{
    size_t c;
    P * p;

    void foo()
    {
        if (c == 0)
        {
            this->p = new P();
        }

        ++c;
        // lots of code, some using this->p
        --c;

        if (c == 0)
        {
            delete this->p;
            this->p = nullptr;
        }
    }
};

Dengan cara ini, kodenya menjadi aman secara rekursif ... Tetapi itu masih belum reentrant karena masalah multithreading: Kita harus yakin modifikasi cdan pakan dilakukan secara atomis, menggunakan mutasi rekursif (tidak semua mutex bersifat rekursif):

#include <mutex>

struct MyStruct
{
    std::recursive_mutex m;
    size_t c;
    P * p;

    void foo()
    {
        m.lock();

        if (c == 0)
        {
            this->p = new P();
        }

        ++c;
        m.unlock();
        // lots of code, some using this->p
        m.lock();
        --c;

        if (c == 0)
        {
            delete this->p;
            this->p = nullptr;
        }

        m.unlock();
    }
};

Dan tentu saja, ini semua menganggap lots of codeitu sendiri reentrant, termasuk penggunaan p.

Dan kode di atas bahkan tidak aman dari pengecualian , tetapi ini adalah cerita lain ... ^ _ ^

7. Hai 99% dari kode kami tidak reentrant!

Ini cukup benar untuk kode spageti. Tetapi jika Anda mempartisi kode Anda dengan benar, Anda akan menghindari masalah reentrancy.

7.1. Pastikan semua fungsi tidak memiliki status

Mereka hanya harus menggunakan parameter, variabel lokal mereka sendiri, fungsi lain tanpa status, dan mengembalikan salinan data jika mereka kembali sama sekali.

7.2. Pastikan objek Anda "recursive-safe"

Metode objek memiliki akses this, sehingga ia berbagi keadaan dengan semua metode dengan instance objek yang sama.

Jadi, pastikan objek dapat digunakan pada satu titik di stack (yaitu memanggil metode A), dan kemudian, di titik lain (yaitu memanggil metode B), tanpa merusak keseluruhan objek. Rancang objek Anda untuk memastikan bahwa saat keluar dari suatu metode, objek tersebut stabil dan benar (tidak ada pointer yang menggantung, tidak ada variabel anggota yang bertentangan, dll.).

7.3. Pastikan semua objek Anda dienkapsulasi dengan benar

Tidak ada orang lain yang memiliki akses ke data internal mereka:

    // bad
    int & MyObject::getCounter()
    {
        return this->counter;
    }

    // good
    int MyObject::getCounter()
    {
        return this->counter;
    }

    // good, too
    void MyObject::getCounter(int & p_counter)
    {
        p_counter = this->counter;
    }

Bahkan mengembalikan referensi const bisa berbahaya jika pengguna mengambil alamat data, karena beberapa bagian lain dari kode dapat memodifikasinya tanpa kode yang menahan referensi const diberitahu.

7.4. Pastikan pengguna tahu objek Anda tidak aman

Dengan demikian, pengguna bertanggung jawab untuk menggunakan mutex untuk menggunakan objek yang dibagikan di antara utas.

Objek dari STL dirancang untuk tidak aman-thread (karena masalah kinerja), dan dengan demikian, jika pengguna ingin berbagi std::string antara dua utas, pengguna harus melindungi aksesnya dengan primitif concurrency;

7.5. Pastikan kode aman thread Anda adalah rekursif-aman

Ini berarti menggunakan mutex rekursif jika Anda yakin sumber daya yang sama dapat digunakan dua kali oleh utas yang sama.

"Safely" didefinisikan persis seperti akal sehat yang menentukan - itu berarti "melakukan hal itu dengan benar tanpa mengganggu hal-hal lain". Enam poin yang Anda sebutkan dengan jelas menyatakan persyaratan untuk mencapainya.

Jawaban untuk 3 pertanyaan Anda adalah 3 × "tidak".

Apakah semua fungsi rekursif reentrant?

TIDAK!

Dua doa simultan dari fungsi rekursif dapat dengan mudah mengacaukan satu sama lain, jika mereka mengakses data global / statis yang sama, misalnya.

Apakah semua fungsi thread-safe reentrant?

TIDAK!

Sebuah fungsi adalah thread-safe jika tidak berfungsi jika dipanggil bersamaan. Tetapi ini bisa dicapai misalnya dengan menggunakan mutex untuk memblokir pelaksanaan doa kedua sampai yang pertama selesai, jadi hanya satu doa yang bekerja pada satu waktu. Reentrancy berarti mengeksekusi secara bersamaan tanpa mengganggu doa lainnya .

Apakah semua fungsi rekursif dan thread-safe reentrant?

TIDAK!

Lihat di atas.

Utas umum:

Apakah perilaku didefinisikan dengan baik jika rutin dipanggil saat itu terputus?

Jika Anda memiliki fungsi seperti ini:

int add( int a , int b ) {
  return a + b;
}

Maka itu tidak tergantung pada keadaan eksternal. Perilaku ini didefinisikan dengan baik.

Jika Anda memiliki fungsi seperti ini:

int add_to_global( int a ) {
  return gValue += a;
}

Hasilnya tidak didefinisikan dengan baik pada banyak utas. Informasi bisa hilang jika waktunya salah.

Bentuk paling sederhana dari fungsi reentrant adalah sesuatu yang beroperasi secara eksklusif pada argumen yang diteruskan dan nilai konstan. Hal lain membutuhkan penanganan khusus atau, sering kali, bukan reentrant. Dan tentu saja argumen tidak boleh merujuk global yang bisa berubah.

Sekarang saya harus menguraikan komentar saya sebelumnya. @ balasan otak salah. Dalam kode contoh tidak ada yang melihat bahwa mutex yang seharusnya menjadi parameter tidak benar-benar diteruskan?

Saya membantah kesimpulannya, saya tegaskan: agar suatu fungsi aman di hadapan konkurensi, ia harus masuk kembali. Oleh karena itu concurrent-safe (biasanya ditulis thread-safe) menyiratkan masuk kembali.

Baik thread safe maupun re-entrant tidak memiliki sesuatu untuk dikatakan tentang argumen: kita berbicara tentang eksekusi fungsi secara bersamaan, yang masih bisa tidak aman jika parameter yang tidak tepat digunakan.

Misalnya, memcpy () aman-utas dan masuk kembali (biasanya). Jelas itu tidak akan berfungsi seperti yang diharapkan jika dipanggil dengan pointer ke target yang sama dari dua utas yang berbeda. Itulah inti dari definisi SGI, menempatkan tanggung jawab pada klien untuk memastikan akses ke struktur data yang sama disinkronkan oleh klien.

Penting untuk dipahami bahwa secara umum tidak masuk akal untuk menjalankan operasi yang aman dengan menyertakan parameter. Jika Anda sudah melakukan pemrograman basis data apa pun, Anda akan mengerti. Konsep apa yang "atomik" dan mungkin dilindungi oleh mutex atau teknik lain tentu saja konsep pengguna: memproses transaksi pada database dapat memerlukan beberapa modifikasi yang tidak terputus. Siapa yang bisa mengatakan yang mana yang harus disinkronkan tetapi programmer klien?

Intinya adalah bahwa "korupsi" tidak harus mengacaukan memori di komputer Anda dengan tulisan yang tidak di-serialisasi: korupsi masih dapat terjadi bahkan jika semua operasi individu bersambung. Itu mengikuti bahwa ketika Anda bertanya apakah suatu fungsi thread-safe, atau masuk kembali, pertanyaan itu berarti untuk semua argumen yang dipisahkan dengan tepat: menggunakan argumen yang digabungkan bukan merupakan contoh tandingan.

Ada banyak sistem pemrograman di luar sana: Ocaml adalah satu, dan saya pikir Python juga, yang memiliki banyak kode non-reentrant di dalamnya, tetapi yang menggunakan kunci global untuk interleave akses benang. Sistem-sistem ini tidak masuk kembali dan tidak aman atau berbarengan, mereka beroperasi dengan aman hanya karena mereka mencegah konkurensi secara global.

Contoh yang bagus adalah malloc. Itu tidak masuk kembali dan tidak aman. Ini karena ia harus mengakses sumber daya global (heap). Menggunakan kunci tidak membuatnya aman: sudah pasti tidak masuk kembali. Jika antarmuka ke malloc telah dirancang dengan benar, maka dimungkinkan untuk membuatnya kembali masuk dan aman-utas:

malloc(heap*, size_t);

Sekarang ini bisa aman karena mentransfer tanggung jawab untuk membuat serialisasi akses bersama ke satu tumpukan ke klien. Khususnya tidak diperlukan pekerjaan jika ada objek tumpukan yang terpisah. Jika tumpukan umum digunakan, klien harus membuat serialisasi akses. Menggunakan kunci di dalam fungsi tidak cukup: cukup pertimbangkan malloc mengunci heap * dan kemudian sinyal datang dan memanggil malloc pada pointer yang sama: deadlock: sinyal tidak dapat dilanjutkan, dan klien tidak bisa karena itu terputus.

Secara umum, kunci tidak membuat hal-hal menjadi aman. Mereka benar-benar menghancurkan keselamatan dengan secara tidak tepat mencoba mengelola sumber daya yang dimiliki oleh klien. Penguncian harus dilakukan oleh pembuat objek, itulah satu-satunya kode yang tahu berapa banyak objek yang dibuat dan bagaimana mereka akan digunakan.

"Common thread" (pun intended !?) di antara poin-poin yang tercantum adalah bahwa fungsi tersebut tidak boleh melakukan apa pun yang akan mempengaruhi perilaku setiap panggilan rekursif atau bersamaan ke fungsi yang sama.

Jadi misalnya data statis adalah masalah karena dimiliki oleh semua utas; jika satu panggilan memodifikasi variabel statis, semua utas menggunakan data yang dimodifikasi sehingga memengaruhi perilaku mereka. Kode modifikasi diri (walaupun jarang ditemui, dan dalam beberapa kasus dicegah) akan menjadi masalah, karena meskipun ada beberapa utas, hanya ada satu salinan kode; kode juga merupakan data statis yang penting.

Pada dasarnya untuk masuk kembali, setiap utas harus dapat menggunakan fungsi seolah-olah hanya itu pengguna, dan bukan itu masalahnya jika satu utas dapat mempengaruhi perilaku yang lain dalam cara yang tidak deterministik. Terutama ini melibatkan setiap utas yang memiliki data terpisah atau konstan yang berfungsi.

Semua yang dikatakan, poin (1) belum tentu benar; misalnya, Anda mungkin sah dan dengan desain menggunakan variabel statis untuk mempertahankan jumlah rekursi untuk menjaga dari rekursi yang berlebihan atau untuk membuat profil suatu algoritma.

Fungsi thread-safe tidak perlu reentrant; itu dapat mencapai keselamatan ulir dengan secara khusus mencegah reentrancy dengan kunci, dan poin (6) mengatakan bahwa fungsi seperti itu tidak reentrant. Mengenai poin (6), suatu fungsi yang memanggil fungsi thread-safe yang mengunci tidak aman untuk digunakan dalam rekursi (itu akan mati-kunci), dan karena itu tidak dikatakan reentrant, meskipun mungkin tetap aman untuk konkurensi, dan masih akan kembali masuk dalam arti bahwa banyak thread dapat memiliki program-counter mereka dalam fungsi seperti itu secara bersamaan (hanya saja tidak dengan wilayah terkunci). Mungkin ini membantu membedakan keamanan thread dari reentarncy (atau mungkin menambah kebingungan Anda!).

Jawaban pertanyaan "Juga" Anda adalah "Tidak", "Tidak" dan "Tidak". Hanya karena suatu fungsi bersifat rekursif dan / atau aman, itu tidak membuatnya kembali masuk.

Setiap jenis fungsi ini dapat gagal pada semua poin yang Anda kutip. (Meskipun saya tidak 100% yakin dengan poin 5).

Istilah "Thread-safe" dan "re-entrant" hanya bermakna dan tepat apa yang definisi mereka katakan. "Aman" dalam konteks ini hanya berarti apa definisi yang Anda kutip di bawahnya.

"Aman" di sini tentu saja tidak berarti aman dalam arti yang lebih luas bahwa memanggil fungsi yang diberikan dalam konteks yang diberikan tidak akan sepenuhnya menyiram aplikasi Anda. Secara keseluruhan, suatu fungsi dapat dipercaya menghasilkan efek yang diinginkan dalam aplikasi multi-threaded Anda tetapi tidak memenuhi syarat sebagai re-entrant atau thread-safe sesuai dengan definisi. Secara berlawanan, Anda dapat memanggil fungsi masuk kembali dengan cara yang akan menghasilkan berbagai efek yang tidak diinginkan, tak terduga, dan / atau tak terduga dalam aplikasi multi-utas Anda.

Fungsi rekursif dapat berupa apa saja dan Re-pendaftar memiliki definisi yang lebih kuat daripada utas-aman sehingga jawaban untuk pertanyaan bernomor Anda semuanya tidak.

Membaca definisi pendaftar ulang, orang mungkin meringkasnya sebagai fungsi yang tidak akan mengubah apa pun di luar apa yang Anda sebut untuk diubah. Tetapi Anda tidak harus hanya mengandalkan ringkasan.

Pemrograman multi-utas hanya sangat sulit dalam kasus umum. Mengetahui bagian mana dari kode ulang seseorang hanya merupakan bagian dari tantangan ini. Keamanan utas bukan aditif. Daripada mencoba menyatukan kembali fungsi-fungsi pendaftar, lebih baik menggunakan pola desain yang aman untuk keseluruhan dan gunakan pola ini untuk memandu penggunaan setiap thread dan sumber daya bersama dalam program Anda.