Membandingkan algoritma Peterson dan Dekker

Saya mencoba memahami algoritma oleh Peterson dan Dekker yang sangat mirip dan menampilkan banyak simetri.

Saya mencoba merumuskan algoritma dalam bahasa informal seperti berikut:

Peterson's: "I want to enter."                 flag[0]=true;
            "You can enter next."              turn=1;
            "If you want to enter and          while(flag[1]==true&&turn==1){
            it's your turn I'll wait."         }
            Else: Enter CS!                    // CS
            "I don't want to enter any more."  flag[0]=false;

Dekker's:   "I want to enter."                 flag[0]=true;
            "If you want to enter              while(flag[1]==true){
             and if it's your turn               if(turn!=0){
             I don't want to enter any more."      flag[0]=false;
            "If it's your turn                     while(turn!=0){
             I'll wait."                           }
            "I want to enter."                     flag[0]=true;
                                                 }
                                               }
            Enter CS!                          // CS
            "You can enter next."              turn=1;
            "I don't want to enter any more."  flag[0]=false;

Perbedaannya tampaknya menjadi titik di mana "You can enter next."terjadi dan fakta yang "if it's your turn I don't want to enter any more."terjadi di Dekker.

Dalam algoritma Peterson, dua proses tampaknya dominan. Sebuah proses tampaknya memaksa masuk ke bagian kritis kecuali giliran orang lain.

Sebaliknya, dalam algoritma Dekker, kedua proses tersebut tampaknya tunduk dan sopan. Jika kedua proses ingin memasuki bagian kritis, dan giliran yang lain, proses memutuskan untuk tidak lagi ingin masuk. (Apakah ini diperlukan untuk kebebasan-kelaparan? Mengapa?)

Bagaimana tepatnya perbedaan algoritma ini? Saya membayangkan bahwa ketika kedua proses mencoba memasuki bagian kritis, di Peterson, proses mengatakan "Saya masuk", sedangkan di Dekker proses mengatakan "Anda boleh masuk". Adakah yang bisa menjernihkan perilaku proses di setiap algoritma? Apakah cara saya mengatakannya secara informal benar?

Deskripsi informal Anda tentang algoritma sangat bagus.

Saya pikir dalam kedua kasus penulis sedang mencoba untuk menemukan solusi paling sederhana yang dapat mereka pikirkan yang menjamin pengucilan bersama dan kebebasan menemui jalan buntu. Tidak ada algoritma yang bebas kelaparan atau adil.[ed: seperti yang ditunjukkan dalam komentar, algoritme Peterson bebas kelaparan dan adil]. Solusi Dekker adalah algoritma eksklusi mutual yang pertama menggunakan hanya memuat dan menyimpan instruksi. Itu diperkenalkan di Dijkstra, Edsger W .; "Bekerja sama proses sekuensial", dalam F. Genuys, ed., Bahasa Pemrograman: NATO Advanced Study Institute , hal. 43-112, Academic Press, 1968 . Jika Anda membaca makalah yang Anda lihat Dijkstra bekerja melalui sejumlah upaya, mengenali masalahnya dengan masing-masing, dan kemudian menambahkan sedikit lebih banyak untuk versi berikutnya. Bagian dari inefisiensi algoritmanya berasal dari fakta bahwa ia mulai dengan algoritma belokan dan kemudian mencoba memodifikasinya untuk memungkinkan proses untuk maju dalam urutan apa pun. (Bukan hanya 0,1,0,1, ...)

Algoritma Peterson diterbitkan pada tahun 1981, setelah lebih dari satu dekade pengalaman dan melihat ke belakang tentang algoritma Dekker. Peterson menginginkan algoritma yang jauh lebih sederhana daripada Dekker sehingga bukti kebenarannya jauh lebih mudah. Anda dapat melihat bahwa dia merasa frustrasi dengan komunitas dari judul makalahnya. Peterson, GL; "Mitos tentang masalah pengecualian bersama," Inf. Proc Lett. , 12 (3): 115-116, 1981. Sangat cepat dibaca dan ditulis dengan sangat baik. (Dan pernyataan sinis tentang metode formal sangat berharga.) Makalah Peterson juga membahas proses yang digunakannya untuk membangun solusinya dari upaya yang lebih sederhana. (Karena solusinya lebih sederhana, diperlukan lebih sedikit langkah menengah.) Perhatikan bahwa perbedaan utama (apa yang Anda sebut "dominasi" daripada "ketundukan") adalah karena Peterson memulai dengan yang baru (bukan dari algoritme belokan yang Dijkstra mulai dengan ) lingkaran tunggunya lebih sederhana dan lebih efisien. Dia menyadari bahwa dia bisa lolos dengan tes loop sederhana sementara Dijkstra harus mundur dan mencoba lagi setiap kali.

Saya merasa saya juga harus menyebutkan kertas algoritma Bakery klasik Lamport : Lamport, Leslie; "Solusi Baru Masalah Pemrograman Serentak Dijkstra", Comm ACM 17 (8): 453-455, 1974 . Algoritma Bakery bisa dibilang lebih sederhana daripada algoritma Dekker (dan tentu saja lebih sederhana dalam kasus lebih dari 2 prosesor), dan secara khusus dirancang untuk menjadi toleran terhadap kesalahan. Saya secara khusus menyebutkannya karena dua alasan. Pertama, karena memberikan sedikit sejarah tentang definisi masalah pengecualian bersama dan upaya untuk menyelesaikannya hingga 1974. Kedua karena algoritma Bakery menunjukkan bahwa tidak diperlukan atomisitas perangkat keras untuk menyelesaikan masalah pengecualian bersama.

Akhirnya, favorit saya adalah Lamport, Leslie; "Algoritma Pengecualian Saling Cepat," ACM Trans. Comp. Sys. , 5 (1): 1-11, 1987. Dalam makalah ini Lamport mencoba untuk mengoptimalkan solusi untuk masalah saling pengecualian dalam kasus (umum) bahwa ada sedikit pertengkaran untuk bagian kritis. Sekali lagi, ini menjamin pengucilan satu sama lain dan kebuntuan kebebasan, tetapi tidak adil. Ini (saya percaya) adalah algoritma saling pengecualian pertama yang hanya menggunakan pembacaan dan penulisan normal yang dapat menyinkronkan prosesor N dalam waktu O (1) ketika tidak ada pertentangan. (Ketika ada pertikaian, itu jatuh kembali pada tes O (N).) Dia memberikan demonstrasi informal bahwa yang terbaik yang dapat Anda lakukan dalam kasus bebas pertengkaran adalah tujuh akses memori. (Dekker dan Peterson keduanya melakukannya dengan 4, tetapi mereka hanya dapat menangani 2 prosesor, ketika Anda memperluas algoritme mereka ke N, mereka harus menambahkan akses O (N) tambahan.)

Secara keseluruhan: Saya akan mengatakan algoritma Dekker itu sendiri menarik terutama dari perspektif sejarah. Makalah Dijkstra menjelaskan pentingnya masalah pengecualian bersama, dan menunjukkan bahwa itu bisa diselesaikan. Tetapi dengan solusi bertahun-tahun dari belakang yang lebih sederhana (dan lebih efisien) daripada Dekker telah ditemukan.

Dalam makalah berikut ini kami memberikan model formal untuk algoritma Peterson dan Dekker (dan beberapa lainnya) dan kami menggunakan pemeriksa model untuk membuktikan sifat mereka. Silakan, cari hasil kami pada tabel di bawah ini (kolom "Deadlock" dan "Divergent" merujuk ke model kami, "ME" = TRUE berarti algoritma itu benar, "Overtaking" = TRUE berarti itu adil).

R. Meolic, T. Kapus, Z. Brezočnik. ACTLW - Logika Pohon Perhitungan Berbasis Aksi Dengan Kecuali Operator. Ilmu Informasi, 178 (6), hlm. 1542-1557, 2008.

https://doi.org/10.1016/j.ins.2007.10.023

Algoritma Peterson memiliki tekanan yang lebih ketat saat memasuki bagian kritis, dimana algoritma dekker relatif lebih lunak dan kurang agresif. Untuk membuatnya lebih jelas, mari kita lihat contoh tentang budaya Iran. Sebelum masuk ke contoh ini, ada baiknya untuk mengetahui bahwa orang Iran memiliki perilaku lembut yang nyata satu sama lain saat memasuki suatu tempat! Tebak dua orang Iran akan memasuki sebuah rumah, dan rumah itu hanya memiliki satu pintu untuk masuk.

Sekarang bayangkan dua pria dari budaya lain ( Zombian Culture ) yang sebenarnya tidak terlalu mereka pedulikan satu sama lain saat memasuki suatu tempat ( Ini masalah rasa hormat untuk bertanya kepada seseorang apakah dia ingin masuk atau tidak ).

Untuk mengklarifikasi informasi tentang masalah kita dapat mengatakan bahwa:

• Dua Iran = Dua proses menggunakan algoritma Dekker
• Two Zombians = Dua proses menggunakan algoritma Peterson

Jadi mari kita cari tahu apa yang dilakukan di setiap algoritma ( budaya ). Komentar berikut adalah untuk orang Iran pertama yang akan memasuki rumah saat menggunakan algoritma Dekker :

p0:
   wants_to_enter[0] ← true // Goes through the house entrance
   while wants_to_enter[1] { // If the other man wants to enter too
      if turn ≠ 0 { // Then see if it is your turn or not
         wants_to_enter[0] ← false // If it is not your turn don't go furthur
         while turn ≠ 0 { // and wait until it is your turn
           // busy wait
         }
         wants_to_enter[0] ← true // when it is your turn go through the door
      }
   }

   // critical section
   ...
   turn ← 1
   wants_to_enter[0] ← false // Set the turn for the other man
   // remainder section

Kami juga memiliki dua Zombian yang akan memasuki rumah menggunakan algoritma Peterson . Yang ini berjalan sebagai berikut:

P0:     
  flag[0] = true; // Goes through the house entrance
  turn = 1; // Set the turn for himself
  while (flag[1] && turn == 1) // Wait until the other one is going in
  {
   // busy wait
  }
   // critical section
      ...
   // end of critical section
  flag[0] = false; // Done going inside

Sangat penting untuk menyebutkan bahwa keduanya tidak masuk ke dalam sementara yang lain melakukannya ( Pengeksklusifan Bersama ) tetapi, orang Iran jauh lebih lembut.