Panduan: Menggunakan gabungan untuk Mencegah Kebuntuan

  • Artikel

Topik ini menggunakan masalah filsuf makan untuk menggambarkan cara menggunakan kelas konkurensi::join untuk mencegah kebuntuan dalam aplikasi Anda. Dalam aplikasi perangkat lunak, kebuntuan terjadi ketika dua atau beberapa proses masing-masing menyimpan sumber daya dan saling menunggu proses lain untuk merilis beberapa sumber daya lain.

Masalah filsuf makan adalah contoh spesifik dari serangkaian masalah umum yang dapat terjadi ketika sekumpulan sumber daya dibagikan di antara beberapa proses bersamaan.

Prasyarat

Baca topik berikut sebelum Anda memulai panduan ini:

Bagian

Panduan ini berisi bagian berikut:

Masalah Filsuf Makan

Masalah filsuf makan menggambarkan bagaimana kebuntuan terjadi dalam aplikasi. Dalam masalah ini, lima filsuf duduk di meja bundar. Setiap filsuf bergantian antara berpikir dan makan. Setiap filsuf harus berbagi sumpit dengan tetangga di sebelah kiri dan sumpit lain dengan tetangga di sebelah kanan. Ilustrasi berikut menunjukkan tata letak ini.

The Dining Philosophers Problem.

Untuk makan, seorang filsuf harus memegang dua sumpit. Jika setiap filsuf hanya memegang satu sumpit dan sedang menunggu satu lagi, maka tidak ada filsuf yang bisa makan dan semua kelaparan.

[Atas]

Implementasi Naïve

Contoh berikut menunjukkan implementasi naif dari masalah filsuf makan. Kelas philosopher , yang berasal dari konkurensi::agent, memungkinkan setiap filsuf untuk bertindak secara independen. Contohnya menggunakan array bersama konkurensi::critical_section objek untuk memberi setiap philosopher objek akses eksklusif ke sepasang sumpit.

Untuk menghubungkan implementasi dengan ilustrasi, philosopher kelas mewakili satu filsuf. Variabel int mewakili setiap sumpit. Objek critical_section berfungsi sebagai pemegang tempat sumpit beristirahat. Metode ini run mensimulasikan kehidupan filsuf. Metode ini think mensimulasikan tindakan berpikir dan metode mensimulasikan eat tindakan makan.

Objek philosopher mengunci kedua critical_section objek untuk mensimulasikan penghapusan sumpit dari pemegang sebelum memanggil eat metode . Setelah panggilan ke eat, philosopher objek mengembalikan sumpit ke pemegang dengan mengatur critical_section objek kembali ke status tidak terkunci.

Metode ini pickup_chopsticks menggambarkan di mana kebuntuan dapat terjadi. Jika setiap philosopher objek mendapatkan akses ke salah satu kunci, maka tidak ada philosopher objek yang dapat dilanjutkan karena kunci lainnya dikontrol oleh objek lain philosopher .

Contoh

// philosophers-deadlock.cpp
// compile with: /EHsc
#include <agents.h>
#include <string>
#include <array>
#include <iostream>
#include <algorithm>
#include <random>

using namespace concurrency;
using namespace std;

// Defines a single chopstick.
typedef int chopstick;

// The total number of philosophers.
const int philosopher_count = 5;

// The number of times each philosopher should eat.
const int eat_count = 50;

// A shared array of critical sections. Each critical section 
// guards access to a single chopstick.
critical_section locks[philosopher_count];

// Implements the logic for a single dining philosopher.
class philosopher : public agent 
{
public:
   explicit philosopher(chopstick& left, chopstick& right, const wstring& name)
      : _left(left)
      , _right(right)
      , _name(name)
      , _random_generator(42)
   {
      send(_times_eaten, 0);
   }

   // Retrieves the number of times the philosopher has eaten.
   int times_eaten()
   {
      return receive(_times_eaten);
   }

   // Retrieves the name of the philosopher.
   wstring name() const
   {
      return _name;
   }

protected:
   // Performs the main logic of the dining philosopher algorithm.
   void run()
   {
      // Repeat the thinks/eat cycle a set number of times.
      for (int n = 0; n < eat_count; ++n)
      {
         think();
         
         pickup_chopsticks(); 
         eat();
         send(_times_eaten, n+1);
         putdown_chopsticks();
      }

      done();
   }

   // Gains access to the chopsticks.
   void pickup_chopsticks()
   {
      // Deadlock occurs here if each philosopher gains access to one
      // of the chopsticks and mutually waits for another to release
      // the other chopstick.
      locks[_left].lock();
      locks[_right].lock();
   }

   // Releases the chopsticks for others.
   void putdown_chopsticks()
   {
      locks[_right].unlock();
      locks[_left].unlock();
   }

   // Simulates thinking for a brief period of time.
   void think()
   {
      random_wait(100);
   }

   // Simulates eating for a brief period of time.
   void eat()
   { 
      random_wait(100);
   }

private:
   // Yields the current context for a random period of time.
   void random_wait(unsigned int max)
   {
      concurrency::wait(_random_generator()%max);
   }

private:
   // Index of the left chopstick in the chopstick array.
   chopstick& _left;
   // Index of the right chopstick in the chopstick array.
   chopstick& _right;

   // The name of the philosopher.
   wstring _name;
   // Stores the number of times the philosopher has eaten.
   overwrite_buffer<int> _times_eaten;

   // A random number generator.
   mt19937 _random_generator;
};

int wmain()
{
   // Create an array of index values for the chopsticks.
   array<chopstick, philosopher_count> chopsticks = {0, 1, 2, 3, 4};

   // Create an array of philosophers. Each pair of neighboring 
   // philosophers shares one of the chopsticks.
   array<philosopher, philosopher_count> philosophers = {
      philosopher(chopsticks[0], chopsticks[1], L"aristotle"),
      philosopher(chopsticks[1], chopsticks[2], L"descartes"),
      philosopher(chopsticks[2], chopsticks[3], L"hobbes"),
      philosopher(chopsticks[3], chopsticks[4], L"socrates"),
      philosopher(chopsticks[4], chopsticks[0], L"plato"),
   };
   
   // Begin the simulation.
   for_each (begin(philosophers), end(philosophers), [](philosopher& p) {
      p.start();
   });

   // Wait for each philosopher to finish and print his name and the number
   // of times he has eaten.
   for_each (begin(philosophers), end(philosophers), [](philosopher& p) {
      agent::wait(&p);
      wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
   });
}

Mengompilasi Kode

Salin kode contoh dan tempelkan dalam proyek Visual Studio, atau tempelkan dalam file yang diberi nama philosophers-deadlock.cpp lalu jalankan perintah berikut di jendela Prompt Perintah Visual Studio.

cl.exe /EHsc philosophers-deadlock.cpp

[Atas]

Menggunakan gabungan untuk Mencegah Kebuntuan

Bagian ini menunjukkan cara menggunakan buffer pesan dan fungsi pengiriman pesan untuk menghilangkan kemungkinan kebuntuan.

Untuk menghubungkan contoh ini dengan yang lebih lama, philosopher kelas mengganti setiap critical_section objek dengan menggunakan objek konkurensi::unbounded_buffer dan join objek. Objek berfungsi join sebagai arbiter yang menyediakan sumpit untuk filsuf.

Contoh ini menggunakan unbounded_buffer kelas karena ketika target menerima pesan dari unbounded_buffer objek, pesan dihapus dari antrean pesan. Ini memungkinkan unbounded_buffer objek yang menyimpan pesan untuk menunjukkan bahwa sumpit tersedia. Objek unbounded_buffer yang tidak menyimpan pesan menunjukkan bahwa sumpit sedang digunakan.

Contoh ini menggunakan objek yang tidak serakah join karena gabungan yang tidak serakah memberi setiap philosopher objek akses ke kedua sumpit hanya ketika kedua unbounded_buffer objek berisi pesan. Gabungan serakah tidak akan mencegah kebuntuan karena gabungan serakah menerima pesan segera setelah tersedia. Kebuntuan dapat terjadi jika semua objek serakah join menerima salah satu pesan tetapi menunggu selamanya agar yang lain tersedia.

Untuk informasi selengkapnya tentang gabungan serakah dan tidak serakah, dan perbedaan antara berbagai jenis buffer pesan, lihat Blok Pesan Asinkron.

Untuk mencegah kebuntuan dalam contoh ini

  1. Hapus kode berikut dari contoh.
// A shared array of critical sections. Each critical section 
// guards access to a single chopstick.
critical_section locks[philosopher_count];
  1. Ubah jenis _left anggota data dan _right kelas menjadi philosopherunbounded_buffer.
// Message buffer for the left chopstick.
unbounded_buffer<chopstick>& _left;
// Message buffer for the right chopstick.
unbounded_buffer<chopstick>& _right;
  1. philosopher Ubah konstruktor untuk mengambil unbounded_buffer objek sebagai parameternya.
explicit philosopher(unbounded_buffer<chopstick>& left, 
   unbounded_buffer<chopstick>& right, const wstring& name)
   : _left(left)
   , _right(right)
   , _name(name)
   , _random_generator(42)
{
   send(_times_eaten, 0);
}
  1. pickup_chopsticks Ubah metode untuk menggunakan objek yang tidak serakah join untuk menerima pesan dari buffer pesan untuk kedua sumpit.
// Gains access to the chopsticks.
vector<int> pickup_chopsticks()
{
   // Create a non-greedy join object and link it to the left and right 
   // chopstick.
   join<chopstick, non_greedy> j(2);
   _left.link_target(&j);
   _right.link_target(&j);

   // Receive from the join object. This resolves the deadlock situation
   // because a non-greedy join removes the messages only when a message
   // is available from each of its sources.
   return receive(&j);
}
  1. putdown_chopsticks Ubah metode untuk melepaskan akses ke sumpit dengan mengirim pesan ke buffer pesan untuk kedua sumpit.
// Releases the chopsticks for others.
void putdown_chopsticks(int left, int right)
{
   // Add the values of the messages back to the message queue.
   asend(&_left, left);
   asend(&_right, right);
}
  1. run Ubah metode untuk menyimpan hasil pickup_chopsticks metode dan untuk meneruskan hasil tersebut ke putdown_chopsticks metode .
// Performs the main logic of the dining philosopher algorithm.
void run()
{
   // Repeat the thinks/eat cycle a set number of times.
   for (int n = 0; n < eat_count; ++n)
   {
      think();
      
      vector<int> v = pickup_chopsticks(); 
      
      eat();
               
      send(_times_eaten, n+1);

      putdown_chopsticks(v[0], v[1]);
   }

   done();
}
  1. Ubah deklarasi chopsticks variabel dalam wmain fungsi menjadi array unbounded_buffer objek yang masing-masing menyimpan satu pesan.
// Create an array of message buffers to hold the chopsticks.
array<unbounded_buffer<chopstick>, philosopher_count> chopsticks;

// Send a value to each message buffer in the array.
// The value of the message is not important. A buffer that contains
// any message indicates that the chopstick is available.
for_each (begin(chopsticks), end(chopsticks), 
   [](unbounded_buffer<chopstick>& c) {
      send(c, 1);
});

Deskripsi

Berikut ini menunjukkan contoh lengkap yang menggunakan objek yang tidak serakah join untuk menghilangkan risiko kebuntuan.

Contoh

// philosophers-join.cpp
// compile with: /EHsc
#include <agents.h>
#include <string>
#include <array>
#include <iostream>
#include <algorithm>
#include <random>

using namespace concurrency;
using namespace std;

// Defines a single chopstick.
typedef int chopstick;

// The total number of philosophers.
const int philosopher_count = 5;

// The number of times each philosopher should eat.
const int eat_count = 50;

// Implements the logic for a single dining philosopher.
class philosopher : public agent 
{
public:
   explicit philosopher(unbounded_buffer<chopstick>& left, 
      unbounded_buffer<chopstick>& right, const wstring& name)
      : _left(left)
      , _right(right)
      , _name(name)
      , _random_generator(42)
   {
      send(_times_eaten, 0);
   }

   // Retrieves the number of times the philosopher has eaten.
   int times_eaten()
   {
      return receive(_times_eaten);
   }

   // Retrieves the name of the philosopher.
   wstring name() const
   {
      return _name;
   }

protected:
   // Performs the main logic of the dining philosopher algorithm.
   void run()
   {
      // Repeat the thinks/eat cycle a set number of times.
      for (int n = 0; n < eat_count; ++n)
      {
         think();
         
         vector<int> v = pickup_chopsticks(); 
         
         eat();
                  
         send(_times_eaten, n+1);

         putdown_chopsticks(v[0], v[1]);
      }

      done();
   }

   // Gains access to the chopsticks.
   vector<int> pickup_chopsticks()
   {
      // Create a non-greedy join object and link it to the left and right 
      // chopstick.
      join<chopstick, non_greedy> j(2);
      _left.link_target(&j);
      _right.link_target(&j);

      // Receive from the join object. This resolves the deadlock situation
      // because a non-greedy join removes the messages only when a message
      // is available from each of its sources.
      return receive(&j);
   }

   // Releases the chopsticks for others.
   void putdown_chopsticks(int left, int right)
   {
      // Add the values of the messages back to the message queue.
      asend(&_left, left);
      asend(&_right, right);
   }

   // Simulates thinking for a brief period of time.
   void think()
   {
      random_wait(100);
   }

   // Simulates eating for a brief period of time.
   void eat()
   {      
      random_wait(100);      
   }

private:
   // Yields the current context for a random period of time.
   void random_wait(unsigned int max)
   {
      concurrency::wait(_random_generator()%max);
   }

private:
   // Message buffer for the left chopstick.
   unbounded_buffer<chopstick>& _left;
   // Message buffer for the right chopstick.
   unbounded_buffer<chopstick>& _right;

   // The name of the philosopher.
   wstring _name;
   // Stores the number of times the philosopher has eaten.
   overwrite_buffer<int> _times_eaten;

   // A random number generator.
   mt19937 _random_generator;
};

int wmain()
{
   // Create an array of message buffers to hold the chopsticks.
   array<unbounded_buffer<chopstick>, philosopher_count> chopsticks;
   
   // Send a value to each message buffer in the array.
   // The value of the message is not important. A buffer that contains
   // any message indicates that the chopstick is available.
   for_each (begin(chopsticks), end(chopsticks), 
      [](unbounded_buffer<chopstick>& c) {
         send(c, 1);
   });
   
   // Create an array of philosophers. Each pair of neighboring 
   // philosophers shares one of the chopsticks.
   array<philosopher, philosopher_count> philosophers = {
      philosopher(chopsticks[0], chopsticks[1], L"aristotle"),
      philosopher(chopsticks[1], chopsticks[2], L"descartes"),
      philosopher(chopsticks[2], chopsticks[3], L"hobbes"),
      philosopher(chopsticks[3], chopsticks[4], L"socrates"),
      philosopher(chopsticks[4], chopsticks[0], L"plato"),
   };
   
   // Begin the simulation.
   for_each (begin(philosophers), end(philosophers), [](philosopher& p) {
      p.start();
   });

   // Wait for each philosopher to finish and print his name and the number
   // of times he has eaten.
   for_each (begin(philosophers), end(philosophers), [](philosopher& p) {
      agent::wait(&p);
      wcout << p.name() << L" ate " << p.times_eaten() << L" times." << endl;
   });
}

Contoh ini menghasilkan output berikut.

aristotle ate 50 times.
descartes ate 50 times.
hobbes ate 50 times.
socrates ate 50 times.
plato ate 50 times.

Mengompilasi Kode

Salin kode contoh dan tempelkan dalam proyek Visual Studio, atau tempelkan dalam file yang diberi nama philosophers-join.cpp lalu jalankan perintah berikut di jendela Prompt Perintah Visual Studio.

cl.exe /EHsc philosophers-join.cpp

[Atas]

Baca juga

Panduan Runtime Konkurensi
Pustaka Agen Asinkron
Agen Asinkron
Blok Pesan Asinkron
Fungsi Passing Pesan
Struktur Data Sinkronisasi