Beberapa waktu lalu, tautan ke artikel "filsuf makan modern" tersebar di berbagai sumber seperti Reddit dan HackerNews. Artikel ini menarik, menunjukkan beberapa solusi untuk tugas terkenal ini, diimplementasikan dalam C ++ modern menggunakan pendekatan berbasis tugas. Jika seseorang belum membaca artikel ini, maka masuk akal untuk menghabiskan waktu dan membacanya.
Namun, saya tidak bisa mengatakan bahwa solusi yang disajikan dalam artikel itu tampak sederhana dan dapat dipahami bagi saya. Ini mungkin karena penggunaan tugas. Terlalu banyak dari mereka yang dibuat dan dikirim melalui berbagai dispatcher / serialis. Jadi tidak selalu jelas di mana, kapan, dan tugas apa yang dilakukan.
Selain itu, pendekatan berbasis tugas bukan satu-satunya yang mungkin untuk memecahkan masalah seperti itu. Mengapa tidak melihat bagaimana tugas "filsuf makan" diselesaikan melalui model Aktor dan CSP?
Oleh karena itu, saya mencoba mencari dan menerapkan beberapa solusi untuk masalah ini menggunakan Aktor dan CSP. Kode untuk solusi ini dapat ditemukan di repositori di GitHub . Dan di bawah pemotong, penjelasan dan penjelasan, jadi siapa pun yang tertarik, selamat datang di bawah dipotong.
Beberapa kata umum
Saya tidak memiliki tujuan mengulangi keputusan yang ditunjukkan dalam artikel "filsuf makan modern" , terutama karena saya pada dasarnya tidak menyukai satu hal penting: pada kenyataannya, filsuf tidak melakukan apa pun pada keputusan itu. Dia hanya mengatakan "Aku ingin makan", dan kemudian seseorang memberinya garpu secara ajaib, atau dia berkata "sekarang tidak akan berhasil."
Jelas mengapa penulis memilih perilaku seperti itu: ia memungkinkan penggunaan implementasi yang sama dari "filsuf" dalam hubungannya dengan implementasi yang berbeda dari "protokol". Namun, menurut saya pribadi bahwa itu lebih menarik ketika "filsuf" mencoba untuk mengambil satu plug pertama, lalu yang lain. Dan ketika "filsuf" terpaksa menangani upaya gagal untuk menangkap garpu.
Justru ini realisasi tugas "filsuf makan" yang saya coba buat. Pada saat yang sama, beberapa solusi menggunakan pendekatan yang sama seperti pada artikel yang disebutkan (misalnya, diimplementasikan oleh protokol ForkLevelPhilosopherProtocol dan WaiterFair).
Saya membuat keputusan berdasarkan SObjectizer , yang sepertinya tidak mengejutkan mereka yang telah membaca artikel saya sebelumnya. Jika seseorang belum pernah mendengar tentang SObjectizer, secara singkat: ini adalah salah satu dari sedikit "kerangka aktor" OpenSource untuk C ++ ( CAF dan QP / C ++ juga dapat disebutkan antara lain). Saya berharap contoh di atas dengan komentar saya akan cukup jelas bahkan untuk mereka yang tidak terbiasa dengan SObjectizer. Jika tidak, saya akan dengan senang hati menjawab pertanyaan di komentar.
Solusi Aktor
Kami akan memulai diskusi tentang solusi yang diimplementasikan dengan yang didasarkan pada Aktor. Pertama, pertimbangkan implementasi solusi Edsger Dijkstra, kemudian beralih ke beberapa solusi lain dan lihat bagaimana perilaku masing-masing solusi tersebut berbeda.
Keputusan Dijkstra
Edsger Dijkstra, dia tidak hanya merumuskan tugas "filum makan" (formulasi menggunakan "garpu" dan "spageti" disuarakan oleh Tony Hoar), dia juga mengusulkan solusi yang sangat sederhana dan indah. Yaitu: para filsuf seharusnya hanya mengambil garpu untuk menambah jumlah garpu, dan jika filsuf berhasil mengambil garpu pertama, maka ia tidak akan melepaskannya sampai ia menerima garpu kedua.
Misalnya, jika seorang filsuf perlu menggunakan garpu dengan angka 5 dan 6, maka seorang filsuf pertama-tama harus mengambil garpu nomor 5. Hanya kemudian ia dapat mengambil garpu nomor 6. Dengan demikian, jika garpu dengan angka yang lebih rendah berada di sebelah kiri para filsuf, maka filsuf harus pertama ambil garpu kiri dan baru setelah itu dia bisa mengambil garpu kanan.
Filsuf terakhir dalam daftar, yang harus berurusan dengan percabangan pada angka (N-1) dan 0, melakukan yang sebaliknya: ia pertama kali mengambil percabangan kanan dengan angka 0, dan kemudian percabangan kiri dengan angka (N-1).
Untuk menerapkan pendekatan ini, dua jenis aktor akan diperlukan: satu untuk garpu dan satu untuk filsuf. Jika filsuf ingin makan, ia mengirim pesan ke aktor garpu yang sesuai untuk menangkap garpu, dan aktor garpu merespons dengan pesan tanggapan.
Kode untuk menerapkan pendekatan ini dapat dilihat di sini .
Pesan
Sebelum berbicara tentang aktor, Anda perlu melihat pesan yang akan dipertukarkan oleh aktor:
struct take_t { const so_5::mbox_t m_who; std::size_t m_philosopher_index; }; struct taken_t : public so_5::signal_t {}; struct put_t : public so_5::signal_t {};
Ketika aktor-filsuf ingin mengambil steker, ia mengirim pesan take_t ke aktor garpu dan aktor garpu merespons dengan pesan taken_t . Ketika aktor filsuf selesai makan dan ingin meletakkan garpu kembali di atas meja, ia mengirim pesan put_t ke put_t .
Dalam pesan take_t , bidang take_t menunjukkan kotak surat (alias mbox) dari aktor filsuf. Pesan respons taken_t harus dikirim ke taken_t ini. Kolom kedua dari take_t tidak digunakan dalam contoh ini, kita akan membutuhkannya ketika kita sampai pada implementasi dari wait_with_queue dan waiter_with_timestamps.
Garpu aktor
Sekarang kita bisa melihat apa itu aktor garpu. Ini kodenya:
class fork_t final : public so_5::agent_t { public : fork_t( context_t ctx ) : so_5::agent_t{ std::move(ctx) } {} void so_define_agent() override {
Setiap aktor di SObjectizer harus diturunkan dari base class agent_t . Apa yang kita lihat di sini untuk tipe fork_t .
Metode so_define_agent() ditimpa di kelas so_define_agent() . Ini adalah metode khusus, ini secara otomatis dipanggil oleh SObjectizer ketika mendaftarkan agen baru. Dalam metode so_define_agent() , so_define_agent() "dikonfigurasikan" untuk bekerja di SObjectizer: status awal berubah, pesan yang diperlukan dilanggan.
Setiap aktor di SObjectizer adalah mesin status dengan status (meskipun aktor hanya menggunakan satu status default). Aktor fork_t memiliki dua status: gratis dan diambil . Ketika seorang aktor dalam keadaan bebas , colokan dapat "ditangkap" oleh filsuf. Dan setelah menangkap "fork", aktor fork_t harus masuk ke status yang diambil . Di dalam kelas fork_t state diwakili oleh instance st_free dan st_taken tipe state_t khusus.
Negara memungkinkan Anda memproses pesan masuk dengan cara berbeda. Misalnya, dalam keadaan bebas , agen merespons hanya untuk take_t dan reaksi ini sangat sederhana: keadaan aktor berubah dan respon yang taken_t :
st_free .event( [this]( mhood_t<take_t> cmd ) { this >>= st_taken; so_5::send< taken_t >( cmd->m_who ); } );
Sementara semua pesan lainnya, termasuk put_t dalam status bebas , diabaikan saja.
Dalam status yang diambil , aktor memproses dua pesan, dan bahkan pesan take_t ia memproses secara berbeda:
st_taken .event( [this]( mhood_t<take_t> cmd ) { m_queue.push( cmd->m_who ); } ) .event( [this]( mhood_t<put_t> ) { if( m_queue.empty() ) this >>= st_free; else { const auto who = m_queue.front(); m_queue.pop(); so_5::send< taken_t >( who ); } } );
Handler untuk put_t paling menarik di put_t : jika antrian para filsuf yang menunggu kosong, maka kita dapat kembali ke yang gratis , tetapi jika tidak kosong, yang pertama dari mereka perlu dikirim dengan taken_t .
Aktor filsuf
Kode aktor-filsuf jauh lebih banyak, jadi saya tidak akan memberikannya di sini sepenuhnya. Kami hanya akan membahas fragmen yang paling signifikan.
Seorang aktor-filsuf memiliki lebih banyak keadaan:
state_t st_thinking{ this, "thinking.normal" }; state_t st_wait_left{ this, "wait_left" }; state_t st_wait_right{ this, "wait_right" }; state_t st_eating{ this, "eating" }; state_t st_done{ this, "done" };
Aktor memulai karyanya dalam keadaan berpikir , kemudian beralih ke wait_left , lalu ke wait_right , lalu ke makan . Dari makan, seorang aktor dapat kembali berpikir atau dapat melakukan jika filsuf telah makan semua yang seharusnya.
Diagram keadaan untuk aktor-filsuf dapat direpresentasikan sebagai berikut:
Logika perilaku aktor dijelaskan dalam penerapan metode so_define_agent() :
void so_define_agent() override {
Mungkin satu-satunya hal yang harus ditekankan adalah pendekatan untuk meniru proses "berpikir" dan "makan". Tidak ada this_thread::sleep_for dalam kode aktor atau cara lain untuk memblokir utas yang saat ini aktif. Sebaliknya, pesan yang tertunda digunakan. Misalnya, ketika seorang aktor memasuki kondisi makan , ia mengirim pesan stop_eating_t tertunda ke dirinya sendiri. Pesan ini diberikan ke timer SObjectizer dan timer mengirimkan pesan ke aktor ketika saatnya tiba.
Menggunakan pesan tertunda memungkinkan Anda untuk menjalankan semua aktor dalam konteks utas tunggal. Secara kasar, satu utas membaca pesan dari beberapa antrian dan menarik penangan pesan berikutnya dari aktor penerima yang sesuai. Lebih lanjut tentang konteks kerja untuk para aktor akan dibahas di bawah ini.
Hasil
Hasil implementasi ini mungkin terlihat sebagai berikut (fragmen kecil):
Socrates: tttttttttttLRRRRRRRRRRRRRREEEEEEEttttttttLRRRRRRRRRRRRRREEEEEEEEEEEEE Plato: ttttttttttEEEEEEEEEEEEEEEEttttttttttRRRRRREEEEEEEEEEEEEEttttttttttLLL Aristotle: ttttEEEEEtttttttttttLLLLLLRRRREEEEEEEEEEEEttttttttttttLLEEEEEEEEEEEEE Descartes: tttttLLLLRRRRRRRREEEEEEEEEEEEEtttLLLLLLLLLRRRRREEEEEEttttttttttLLLLLL Spinoza: ttttEEEEEEEEEEEEEttttttttttLLLRRRREEEEEEEEEEEEEttttttttttRRRREEEEEEtt Kant: ttttttttttLLLLLLLRREEEEEEEEEEEEEEEttttttttttLLLEEEEEEEEEEEEEEtttttttt Schopenhauer: ttttttEEEEEEEEEEEEEttttttLLLLLLLLLEEEEEEEEEttttttttLLLLLLLLLLRRRRRRRR Nietzsche: tttttttttLLLLLLLLLLEEEEEEEEEEEEEttttttttLLLEEEEEEEEEttttttttRRRRRRRRE Wittgenstein: ttttEEEEEEEEEEtttttLLLLLLLLLLLLLEEEEEEEEEttttttttttttRRRREEEEEEEEEEEt Heidegger: tttttttttttLLLEEEEEEEEEEEEEEtttttttLLLLLLREEEEEEEEEEEEEEEtttLLLLLLLLR Sartre: tttEEEEEEEEEttttLLLLLLLLLLLLRRRRREEEEEEEEEtttttttLLLLLLLLRRRRRRRRRRRR
Baca ini sebagai berikut:
t menyatakan bahwa filsuf itu "berpikir";L berarti bahwa filsuf mengharapkan untuk menangkap garpu kiri (dalam keadaan wait_left );R berarti bahwa filsuf mengharapkan untuk menangkap garpu yang tepat (dalam status wait_right )E berarti bahwa filsuf "makan."
Kita dapat melihat bahwa Socrates dapat mengambil garpu di sebelah kiri hanya setelah Sartre memberikannya. Setelah itu Socrates akan menunggu sampai Plato melepaskan garpu yang tepat. Hanya setelah ini Socrates akan dapat makan.
Keputusan sederhana tanpa arbiter (pelayan)
Jika kita menganalisis hasil keputusan Dijkstra, kita akan melihat bahwa para filsuf menghabiskan banyak waktu menunggu penangkapan garpu. Apa yang tidak baik, karena waktu ini juga dapat digunakan untuk refleksi. Bukan tanpa alasan bahwa ada pendapat bahwa jika Anda berpikir dengan perut kosong, Anda bisa mendapatkan hasil yang jauh lebih menarik dan tak terduga;)
Mari kita lihat solusi paling sederhana di mana filsuf mengembalikan garpu yang ditangkap pertama jika dia tidak bisa menangkap yang kedua (dalam artikel "filsuf makan modern" yang disebutkan di atas, solusi ini diterapkan oleh ForkLevelPhilosopherProtocol).
Kode sumber untuk implementasi ini dapat dilihat di sini , dan kode untuk aktor filsuf terkait di sini .
Pesan
Solusi ini menggunakan sekumpulan pesan yang hampir sama:
struct take_t { const so_5::mbox_t m_who; std::size_t m_philosopher_index; }; struct busy_t : public so_5::signal_t {}; struct taken_t : public so_5::signal_t {}; struct put_t : public so_5::signal_t {};
Satu-satunya perbedaan adalah kehadiran sinyal busy_t . Garpu aktor-mengirimkan sinyal ini sebagai tanggapan terhadap filsuf-aktor jika garpu sudah ditangkap oleh filsuf lain.
Garpu aktor
Aktor fork dalam solusi ini bahkan lebih sederhana daripada solusi Dijkstra:
class fork_t final : public so_5::agent_t { public : fork_t( context_t ctx ) : so_5::agent_t( ctx ) { this >>= st_free; st_free.event( [this]( mhood_t<take_t> cmd ) { this >>= st_taken; so_5::send< taken_t >( cmd->m_who ); } ); st_taken.event( []( mhood_t<take_t> cmd ) { so_5::send< busy_t >( cmd->m_who ); } ) .just_switch_to< put_t >( st_free ); } private : const state_t st_free{ this }; const state_t st_taken{ this }; };
Di sini kita bahkan tidak perlu menjaga garis para filsuf yang menunggu.
Aktor filsuf
Filsuf-aktor dalam implementasi ini mirip dengan solusi Dijkstra, tetapi di sini filsuf-aktor harus memproses busy_t , sehingga diagram negara terlihat seperti ini:
Demikian pula, seluruh logika aktor-filsuf didefinisikan dalam so_define_agent() :
void so_define_agent() override { st_thinking .event< stop_thinking_t >( [=] { this >>= st_wait_left; so_5::send< take_t >( m_left_fork, so_direct_mbox(), m_index ); } ); st_wait_left .event< taken_t >( [=] { this >>= st_wait_right; so_5::send< take_t >( m_right_fork, so_direct_mbox(), m_index ); } ) .event< busy_t >( [=] { think( st_hungry_thinking ); } ); st_wait_right .event< taken_t >( [=] { this >>= st_eating; } ) .event< busy_t >( [=] { so_5::send< put_t >( m_left_fork ); think( st_hungry_thinking ); } ); st_eating .on_enter( [=] { so_5::send_delayed< stop_eating_t >( *this, eat_pause() ); } ) .event< stop_eating_t >( [=] { so_5::send< put_t >( m_right_fork ); so_5::send< put_t >( m_left_fork ); ++m_meals_eaten; if( m_meals_count == m_meals_eaten ) this >>= st_done; else think( st_normal_thinking ); } ); st_done .on_enter( [=] { completion_watcher_t::done( so_environment(), m_index ); } ); }
Secara umum, ini hampir kode yang sama seperti dalam solusi Dijkstra, kecuali untuk beberapa penangan untuk busy_t .
Hasil
Hasil pekerjaan terlihat berbeda:
Socrates: tttttttttL..R.....EEEEEEEEEEEEttttttttttR...LL..EEEEEEEttEEEEEE Plato: ttttEEEEEEEEEEEttttttL.....L..EEEEEEEEEEEEEEEttttttttttL....L.... Aristotle: ttttttttttttL..LR.EEEEEEtttttttttttL..L....L....R.....EEEEEEEEE Descartes: ttttttttttEEEEEEEEttttttttttttEEEEEEEEttttEEEEEEEEEEEttttttL..L.. Spinoza: ttttttttttL.....L...EEEEEEtttttttttL.L......L....L..L...R...R...E Kant: tttttttEEEEEEEttttttttL.L.....EEEEEEEEttttttttR...R..R..EEEEEtttt Schopenhauer: tttR..R..L.....EEEEEEEttttttR.....L...EEEEEEEEEEEEEEEEttttttttttt Nietzsche: tttEEEEEEEEEEtttttttttEEEEEEEEEEEEEEEttttL....L...L..L....EEEEEEE Wittgenstein: tttttL.L..L.....RR....L.....L....L...EEEEEEEEEEEEEEEtttttttttL. Heidegger: ttttR..R......EEEEEEEEEEEEEttttttttttR..L...L...L..L...EEEEtttttt Sartre: tttEEEEEEEtttttttL..L...L....R.EEEEEEEtttttEEEEtttttttR.....R..R.
Di sini kita melihat simbol baru, yang berarti bahwa aktor-filsuf dalam "pikiran lapar".
Bahkan dalam fragmen pendek ini, orang dapat melihat bahwa ada periode waktu yang lama di mana filsuf tidak dapat makan. Ini karena solusi ini dilindungi dari masalah kebuntuan, tetapi tidak memiliki perlindungan terhadap kelaparan.
Keputusan dengan pelayan dan antrian
Solusi paling sederhana yang ditunjukkan di atas tanpa arbiter tidak melindungi terhadap kelaparan. Artikel "filsuf makan modern" yang disebutkan di atas berisi solusi untuk masalah puasa dalam bentuk protokol WaiterFair. Intinya adalah bahwa ada seorang wasit (pelayan), yang menjadi tujuan para filsuf ketika mereka ingin makan. Dan pelayan memiliki antrian aplikasi dari para filsuf. Dan sang filsuf mendapat garpu hanya jika kedua garunya gratis sekarang, dan tidak ada tetangga dari filsuf yang menoleh ke pelayan di antrian.
Mari kita lihat bagaimana solusi yang sama ini terlihat pada para aktor.
Kode sumber untuk implementasi ini dapat ditemukan di sini .
Trick
Cara termudah adalah dengan memperkenalkan satu set pesan baru di mana para filsuf dapat berkomunikasi dengan pelayan. Tapi saya ingin menyimpan tidak hanya set pesan yang sudah ada (mis. take_t , taken_t , busy_t , put_t ). Saya juga ingin aktor-filsuf yang sama untuk digunakan seperti dalam solusi sebelumnya. Oleh karena itu, saya harus menyelesaikan masalah yang rumit: bagaimana membuat aktor-filsuf berkomunikasi dengan satu-satunya aktor-pelayan, tetapi pada saat yang sama berpikir bahwa ia berinteraksi langsung dengan garpu aktor (yang sudah hilang).
Masalah ini diselesaikan dengan menggunakan trik sederhana: seorang aktor-pelayan menciptakan seperangkat mbox-s, tautan yang diberikan kepada aktor-filsuf sebagai tautan ke mbox-s dari aktor-aktor garpu. Pada saat yang sama, aktor-pelayan berlangganan pesan dari semua mboxes ini (yang mudah diimplementasikan dalam SObjectizer, karena SObjectizer adalah implementasi tidak hanya / karena banyak Model Aktor, tetapi juga Pub / Sub didukung di luar kotak) .
Dalam kode, tampilannya seperti ini:
class waiter_t final : public so_5::agent_t { public : waiter_t( context_t ctx, std::size_t forks_count ) : so_5::agent_t{ std::move(ctx) } , m_fork_states( forks_count, fork_state_t::free ) {
Yaitu Pertama, buat vektor mbox-s untuk "garpu" yang tidak ada, kemudian berlangganan masing-masing. Ya, kami berlangganan untuk mengetahui plug mana yang terkait dengan permintaan tersebut.
Penangan asli untuk permintaan masuk on_take_fork() adalah metode on_take_fork() :
void on_take_fork( mhood_t<take_t> cmd, std::size_t fork_index ) {
Ngomong-ngomong, di sinilah kami membutuhkan bidang kedua dari pesan take_t .
Jadi, di on_take_fork() kami memiliki permintaan asli dan indeks garpu yang terkait dengan permintaan tersebut. Karena itu, kita dapat menentukan apakah filsuf meminta garpu kiri atau garpu kanan. Dan, karenanya, kita dapat memprosesnya secara berbeda (dan kita harus memprosesnya secara berbeda).
Karena filsuf selalu pertama-tama meminta garpu kiri, maka kita perlu melakukan semua pemeriksaan yang diperlukan pada saat ini. Dan kita dapat menemukan diri kita dalam salah satu situasi berikut:
- Kedua garpu gratis dan dapat diberikan kepada filsuf yang mengirim permintaan. Dalam hal ini, kami
taken_t filsuf, dan menandai garpu kanan sebagai cadangan sehingga tidak ada orang lain yang dapat mengambilnya. - Garpu tidak dapat diberikan kepada filsuf. Tidak peduli mengapa Mungkin beberapa dari mereka sedang sibuk sekarang. Atau sejalan adalah salah satu tetangga filsuf. Bagaimanapun, kami menempatkan filsuf yang mengirim permintaan dalam antrian, setelah itu kami
busy_t kepadanya.
Berkat logika kerja ini, filsuf yang menerima taken_t untuk garpu kiri dapat dengan aman mengirim permintaan take_t untuk garpu kanan. Permintaan ini akan segera dipenuhi, karena garpu sudah disediakan untuk filsuf ini.
Hasil
Jika Anda menjalankan solusi yang dihasilkan, Anda dapat melihat sesuatu seperti:
Socrates: tttttttttttL....EEEEEEEEEEEEEEttttttttttL...L...EEEEEEEEEEEEEtttttL. Plato: tttttttttttL....L..L..L...L...EEEEEEEEEEEEEtttttL.....L....L.....EEE Aristotle: tttttttttL.....EEEEEEEEEttttttttttL.....L.....EEEEEEEEEEEtttL....LL Descartes: ttEEEEEEEEEEtttttttL.L..EEEEEEEEEEEEtttL..L....L....L.....EEEEEEEEEE Spinoza: tttttttttL.....EEEEEEEEEttttttttttL.....L.....EEEEEEEEEEEtttL....LL Kant: ttEEEEEEEEEEEEEtttttttL...L.....L.....EEEEEttttL....L...L..L...EEEEE Schopenhauer: ttttL...L.....L.EEEEEEEEEEEEEEEEEtttttttttttL..L...L..EEEEEEEttttttt Nietzsche: tttttttttttL....L..L..L...L...L.....L....EEEEEEEEEEEEttL.....L...L.. Wittgenstein: tttttttttL....L...L....L....L...EEEEEEEttttL......L.....L.....EEEEEE Heidegger: ttttttL..L...L.....EEEEEEEEEEEEtttttL...L..L.....EEEEEEEEEEEttttttL. Sartre: ttEEEEEEEEEEEEEttttttttL.....L...EEEEEEEEEEEEttttttttttttL.....EEEEE
Anda dapat memperhatikan kurangnya karakter R Ini karena kegagalan atau harapan tidak dapat terjadi pada permintaan garpu yang tepat.
Keputusan lain menggunakan arbiter (pelayan)
Dalam beberapa kasus, solusi waiter_with_queue sebelumnya dapat menampilkan hasil yang mirip dengan yang ini:
Socrates: tttttEEEEEEEEEEEEEEtttL.....LL...L....EEEEEEEEEttttttttttL....L.....EE Plato: tttttL..L..L....LL...EEEEEEEEEEEEEEEttttttttttttL.....EEEEEEEEEttttttt Aristotle: tttttttttttL..L...L.....L.....L....L.....EEEEEEEEEEEEtttttttttttL....L.. Descartes: ttttttttttEEEEEEEEEEttttttL.....L....L..L.....L.....L..L...L..EEEEEEEEtt Spinoza: tttttttttttL..L...L.....L.....L....L.....L..L..L....EEEEEEEEEEtttttttttt Kant: tttttttttL....L....L...L...L....L..L...EEEEEEEEEEEttttttttttL...L......E Schopenhauer: ttttttL....L..L...L...LL...L...EEEEEtttttL....L...L.....EEEEEEEEEttttt Nietzsche: tttttL..L..L....EEEEEEEEEEEEEttttttttttttEEEEEEEEEEEEEEEttttttttttttL... Wittgenstein: tttEEEEEEEEEEEEtttL....L....L..EEEEEEEEEtttttL..L..L....EEEEEEEEEEEEEEEE Heidegger: tttttttttL...L..EEEEEEEEttttL..L.....L...EEEEEEEEEtttL.L..L...L....L...L Sartre: ttttttttttL..L....L...L.EEEEEEEEEEEtttttL...L..L....EEEEEEEEEEtttttttttt
Anda dapat melihat keberadaan periode waktu yang cukup lama ketika para filsuf tidak dapat makan walaupun ada garpu gratis. Misalnya, garpu kiri dan kanan untuk Kant gratis untuk waktu yang lama, tetapi Kant tidak dapat mengambilnya, karena tetangganya sudah mengantri. Yang sedang menunggu tetangga mereka. Siapa yang menunggu tetangga mereka, dll.
Oleh karena itu, implementasi dari wait_with_queue yang dibahas di atas melindungi terhadap kelaparan dalam arti bahwa cepat atau lambat filsuf akan makan. Ini dijamin untuknya. Tetapi periode puasa bisa sangat lama. Dan pemanfaatan sumber daya mungkin tidak optimal.
Untuk mengatasi masalah ini, saya menerapkan solusi lain, waiter_with_timestamp (kodenya dapat ditemukan di sini ). Alih-alih mengantri, mereka memprioritaskan permintaan dari para filsuf dengan mempertimbangkan waktu puasa mereka. Semakin lama filsuf kelaparan, semakin prioritas permintaannya.
Kami tidak akan mempertimbangkan kode untuk solusi ini, karena pada umumnya hal utama di dalamnya adalah trik yang sama dengan seperangkat mbox untuk "garpu" yang tidak ada, yang sudah kita bahas dalam percakapan tentang penerapan waiter_with_queue.
Beberapa detail implementasi yang ingin saya perhatikan
Ada beberapa detail dalam implementasi berdasarkan Aktor yang ingin saya perhatikan, karena detail ini menunjukkan fitur menarik dari SObjectizer.
Konteks kerja untuk para aktor
Dalam implementasi yang dipertimbangkan, semua aktor utama ( fork_t , philosopher_t , waiter_t ) bekerja pada konteks satu utas kerja umum. Yang tidak berarti sama sekali bahwa dalam SObjectizer semua aktor bekerja hanya pada satu utas tunggal. Dalam SObjectizer Anda dapat mengikat aktor ke konteks yang berbeda, yang dapat dilihat, misalnya, dalam kode fungsi run_simulation() dalam solusi no_waiter_simple.
Run_simulation kode dari no_waiter_simple void run_simulation( so_5::environment_t & env, const names_holder_t & names ) { env.introduce_coop( [&]( so_5::coop_t & coop ) { coop.make_agent_with_binder< trace_maker_t >( so_5::disp::one_thread::create_private_disp( env )->binder(), names, random_pause_generator_t::trace_step() ); coop.make_agent_with_binder< completion_watcher_t >( so_5::disp::one_thread::create_private_disp( env )->binder(), names ); const auto count = names.size(); std::vector< so_5::agent_t * > forks( count, nullptr ); for( std::size_t i{}; i != count; ++i ) forks[ i ] = coop.make_agent< fork_t >(); for( std::size_t i{}; i != count; ++i ) coop.make_agent< philosopher_t >( i, forks[ i ]->so_direct_mbox(), forks[ (i + 1) % count ]->so_direct_mbox(), default_meals_count ); }); }
Dalam fungsi ini, aktor tambahan dari tipe trace_maker_t dan completion_watcher_t . Mereka akan bekerja pada konteks pekerjaan individu. Untuk melakukan ini, dua instance dari dispatcher dari tipe one_thread dan para aktor terikat pada instance dari dispatcher ini. Yang berarti bahwa para aktor ini akan berfungsi sebagai objek aktif : masing-masing akan memiliki utas kerjanya sendiri.
SObjectizer menyediakan satu set beberapa dispatcher berbeda yang dapat digunakan langsung di luar kotak. Dalam hal ini, pengembang dapat membuat dalam aplikasinya sebanyak contoh operator yang dibutuhkan pengembang.
, , . , fork_t , philosopher_t .
run_simulation no_waiter_simple_tp void run_simulation( so_5::environment_t & env, const names_holder_t & names ) { env.introduce_coop( [&]( so_5::coop_t & coop ) { coop.make_agent_with_binder< trace_maker_t >( so_5::disp::one_thread::create_private_disp( env )->binder(), names, random_pause_generator_t::trace_step() ); coop.make_agent_with_binder< completion_watcher_t >( so_5::disp::one_thread::create_private_disp( env )->binder(), names ); const auto count = names.size();
fork_t philosopher_t .
Modern dining philosophers , , :
void doEat() { eventLog_.startActivity(ActivityType::eat); wait(randBetween(10, 50)); eventLog_.endActivity(ActivityType::eat);
SObjectizer . , , . Karena apa?
, SObjectizer- : . agent_state_listener_t . , SObjectizer .
greedy_philosopher_t philosopher_t :
philosopher_t(...) ... { so_add_destroyable_listener( state_watcher_t::make( so_environment(), index ) ); }
state_watcher_t — .
state_watcher_t class state_watcher_t final : public so_5::agent_state_listener_t { const so_5::mbox_t m_mbox; const std::size_t m_index; state_watcher_t( so_5::mbox_t mbox, std::size_t index ); public : static auto make( so_5::environment_t & env, std::size_t index ) { return so_5::agent_state_listener_unique_ptr_t{ new state_watcher_t{ trace_maker_t::make_mbox(env), index } }; } void changed( so_5::agent_t &, const so_5::state_t & state ) override; };
state_watcher_t SObjectizer changed() . state_watcher_t::changed -.
state_watcher_t::changed void state_watcher_t::changed( so_5::agent_t &, const so_5::state_t & state ) { const auto detect_label = []( const std::string & name ) {...}; const char state_label = detect_label( state.query_name() ); if( '?' == state_label ) return; so_5::send< trace::state_changed_t >( m_mbox, m_index, state_label ); }
CSP
, . (no_waiter_dijkstra, no_waiter_simple, waiter_with_timestamps) std::thread SObjectizer- mchain- (, , CSP- ). , , CSP- ( take_t , taken_t , busy_t , put_t ).
CSP- "" . , std::thread .
.
: + take_t put_t . fork_process :
void fork_process( so_5::mchain_t fork_ch ) {
fork_process : , - .
fork_process — "" , . receive() :
so_5::receive( so_5::from( fork_ch ), [&]( so_5::mhood_t<take_t> cmd ) {...}, [&]( so_5::mhood_t<put_t> ) {...} );
SObjectizer- receive() . . . , . , .
-. fork_t . , , .
philosopher_process . , .
philosopher_process oid philosopher_process( trace_maker_t & tracer, so_5::mchain_t control_ch, std::size_t philosopher_index, so_5::mbox_t left_fork, so_5::mbox_t right_fork, int meals_count ) { int meals_eaten{ 0 }; random_pause_generator_t pause_generator;
:
void philosopher_process( trace_maker_t & tracer, so_5::mchain_t control_ch, std::size_t philosopher_index, so_5::mbox_t left_fork, so_5::mbox_t right_fork, int meals_count )
.
SObjectizer- , , Actor-. :
tracer.thinking_started( philosopher_index, thinking_type_t::normal );
tracer , .
control_ch , philosopher_done_t , , . .
left_fork right_fork . take_t put_t . , mbox_t mchain_t ?
! , . , mchain — - mbox-, mchain- mbox_t .
, :
int meals_eaten{ 0 }; random_pause_generator_t pause_generator; auto self_ch = so_5::create_mchain( control_ch->environment() );
— self_ch . , .
. Yaitu , .
, , this_thread::sleep_for .
, :
so_5::send< take_t >( left_fork, self_ch->as_mbox(), philosopher_index );
take_t . mbox_t , self_ch mchain_t . as_mbox() .
receive() :
so_5::receive( so_5::from( self_ch ).handle_n( 1u ), [&]( so_5::mhood_t<taken_t> ) {...} );
taken_t . . , .
- , philosopher_process . receive() :
so_5::receive( so_5::from( self_ch ).handle_n( 1u ), [&]( so_5::mhood_t<taken_t> ) { ... so_5::receive( so_5::from( self_ch ).handle_n( 1u ), [&]( so_5::mhood_t<taken_t> ) {...} ); ... } );
- .
run_simulation() , . CSP- run_simulation() . , , ( ).
run_simulation void run_simulation( so_5::environment_t & env, const names_holder_t & names ) noexcept { const auto table_size = names.size(); const auto join_all = []( std::vector<std::thread> & threads ) { for( auto & t : threads ) t.join(); }; trace_maker_t tracer{ env, names, random_pause_generator_t::trace_step() };
, run_simulation() - . .
. :
std::vector< so_5::mchain_t > fork_chains; std::vector< std::thread > fork_threads( table_size ); for( std::size_t i{}; i != table_size; ++i ) { fork_chains.emplace_back( so_5::create_mchain(env) ); fork_threads[ i ] = std::thread{ fork_process, fork_chains.back() }; }
, , . . , join .
, .. join :
std::vector< std::thread > philosopher_threads( table_size ); for( std::size_t i{}; i != table_size - 1u; ++i ) { philosopher_threads[ i ] = philosopher_maker( i, i, i+1u ); } philosopher_threads[ table_size - 1u ] = philosopher_maker( table_size - 1u, table_size - 1u, 0u );
. :
so_5::receive( so_5::from( control_ch ).handle_n( table_size ), [&names]( so_5::mhood_t<philosopher_done_t> cmd ) { fmt::print( "{}: done\n", names[ cmd->m_philosopher_index ] ); } );
receive() table_size philosopher_done_t .
philosopher_done_t .
join :
join_all( philosopher_threads );
join . join , .. . receive() . join :
for( auto & ch : fork_chains ) so_5::close_drop_content( ch ); join_all( fork_threads );
.
noexcept
, run_simulation , noexcept . , exception-safety . — .
run_simulation ?
, . - exception-safety , . - , :
try { for( std::size_t i{}; i != table_size; ++i ) { fork_chains.emplace_back( so_5::create_mchain(env) ); fork_threads[ i ] = std::thread{ fork_process, fork_chains.back() }; } } catch( ... ) { for( std::size_t i{}; i != fork_chains.size(); ++i ) { so_5::close_drop_content( fork_chains[ i ] ); if( fork_threads[ i ].joinable() ) fork_threads[ i ].join(); } throw; }
, . Karena , . - :
struct fork_threads_stuff_t { std::vector< so_5::mchain_t > m_fork_chains; std::vector< std::thread > m_fork_threads; fork_threads_stuff_t( std::size_t table_size ) : m_fork_threads( table_size ) {} ~fork_threads_stuff_t() { for( std::size_t i{}; i != m_fork_chains.size(); ++i ) { so_5::close_drop_content( m_fork_chains[ i ] ); if( m_fork_threads[ i ].joinable() ) m_fork_threads[ i ].join(); } } void run() { for( std::size_t i{}; i != m_fork_threads.size(); ++i ) { m_fork_chains.emplace_back( so_5::create_mchain(env) ); m_fork_threads[ i ] = std::thread{ fork_process, m_fork_chains.back() }; } } } fork_threads_stuff{ table_size };
, (, Boost- ScopeExit-, GSL- finally() ).
. .
, exception-safety run_simulation() , run_simulation() , . , -. exception-safety run_simulation() noexcept , std::terminate . , .
, , , , . , join , join . .
()
, CSP- , .
.
fork_process , :
void fork_process( so_5::mchain_t fork_ch ) {
, fork_process , ( , ).
philosopher_process , , .
philosopher_process void philosopher_process( trace_maker_t & tracer, so_5::mchain_t control_ch, std::size_t philosopher_index, so_5::mbox_t left_fork, so_5::mbox_t right_fork, int meals_count ) { int meals_eaten{ 0 };
- philosopher_process philosopher_process . .
-, thinking_type . , , , "" .
-, busy_t . receive() :
so_5::receive( so_5::from( self_ch ).handle_n( 1u ), []( so_5::mhood_t<busy_t> ) { }, [&]( so_5::mhood_t<taken_t> ) { ... so_5::receive( so_5::from( self_ch ).handle_n( 1u ), []( so_5::mhood_t<busy_t> ) { }, [&]( so_5::mhood_t<taken_t> ) {...} );
, busy_t , , receive() , receive() . busy_t . , .. receive() busy_t . receive() busy_t .
CSP- , . (): waiter_with_queue, , waiter_with_timestamps. : mbox- , mbox- , mbox- .
CSP- , philosopher_process no_waiter_simple. mchain- , ?
, .
mchain- . , mchain-.
SObjectizer- select() , , , :
so_5::select( so_5::from_all(), case_(ch1, one_handler_1, one_handler_2, one_handler_3, ...), case_(ch2, two_handler_1, two_handler_2, two_handler_3, ...), ...);
select() , -. " " . CSP- .
.
, , take_t put_t . - . take_t put_t , :
struct extended_take_t final : public so_5::message_t { const so_5::mbox_t m_who; const std::size_t m_philosopher_index; const std::size_t m_fork_index; extended_take_t( so_5::mbox_t who, std::size_t philosopher_index, std::size_t fork_index ) : m_who{ std::move(who) } , m_philosopher_index{ philosopher_index } , m_fork_index{ fork_index } {} }; struct extended_put_t final : public so_5::message_t { const std::size_t m_fork_index; extended_put_t( std::size_t fork_index ) : m_fork_index{ fork_index } {} };
, so_5::message_t , ( ). , SObjectizer- .
, . take_t put_t , extended_take_t extended_put_t , .
mbox. :)
mbox- class wrapping_mbox_t final : public so_5::extra::mboxes::proxy::simple_t { using base_type_t = so_5::extra::mboxes::proxy::simple_t;
mbox-: so_5_extra , . so_5::abstract_message_box_t .
, wrapping_mbox_t . , . wrapping_mbox, mchain . waiter_process , , :
void waiter_process( so_5::mchain_t waiter_ch, details::waiter_logic_t & logic ) {
, , . waiter_with_timestamps .
: " philosopher_process mbox-?" , waiter_with_timestamps mbox, mchain.
, mchain. , .. so_5_extra mchain- ( ). mbox- mchain-.
Kesimpulan
, , , CSP . , . , , . , - .
, SObjectizer-. , "" SObjectizer — 5.6, 5.5. , ( ). - , SO-5.6 ( ).
, !
PS. "" , . C++14.