Algoritma Bakery: Pendekatan Elegan untuk Mengatasi Sinkronisasi di Sistem Multiprosesor

Dalam dunia concurrent programming, sinkronisasi antar proses yang berjalan secara bersamaan merupakan tantangan besar. Seperti pada kehidupan nyata di sebuah toko roti, pelanggan harus menunggu giliran untuk dilayani, dan giliran ini harus diatur agar tidak ada pelanggan yang dilayani dua kali atau melangkahi giliran. Algoritma Bakery adalah metafora sempurna yang digunakan untuk mengatasi masalah ini di dunia komputasi.

Algoritma Bakery (atau Bakery Algorithm) dikembangkan oleh Leslie Lamport pada tahun 1974. Algoritma ini dirancang untuk memecahkan masalah mutual exclusion dalam sistem multiprosesor, yaitu bagaimana memastikan bahwa beberapa proses tidak mengakses critical section secara bersamaan. Inspirasi dari algoritma ini adalah cara toko roti melayani pelanggan dengan menggunakan nomor antrean.

Latar Belakang: Masalah Sinkronisasi dan Eksklusi Mutual

Di lingkungan multi-threading atau multi-prosesor, proses-proses yang berjalan bersamaan sering kali perlu berbagi sumber daya bersama, seperti memori atau file. Tanpa adanya mekanisme yang memastikan hanya satu proses yang bisa mengakses sumber daya pada suatu waktu, hal ini dapat mengakibatkan race conditions, deadlock, atau inkonsistensi data.

Untuk mencegah masalah ini, dibutuhkan konsep mutual exclusion (eksklusi mutual), yaitu memastikan bahwa hanya satu proses yang dapat masuk ke critical section (bagian dari kode di mana akses ke sumber daya bersama dilakukan) pada satu waktu. Algoritma Bakery memberikan solusi praktis untuk memastikan eksklusi mutual ini pada sistem dengan banyak proses.

Cara Kerja Algoritma Bakery

Secara konseptual, Algoritma Bakery bekerja mirip dengan cara toko roti melayani pelanggan. Setiap proses yang ingin memasuki critical section akan mengambil “nomor antrean”, dan proses dengan nomor terkecil akan diberi kesempatan masuk lebih dulu. Setelah selesai, proses akan keluar dan nomor antrean akan dilanjutkan ke proses berikutnya.

Komponen Utama dalam Algoritma Bakery:

  1. choosing[i]: Sebuah array boolean yang menunjukkan apakah proses i sedang memilih nomor antreannya.
  2. number[i]: Sebuah array yang menyimpan nomor antrean proses i. Semakin kecil nomor, semakin cepat proses tersebut dapat mengakses critical section.
  3. N: Jumlah proses yang ada dalam sistem.

Langkah-Langkah Algoritma Bakery:

  1. Ketika sebuah proses ingin masuk ke critical section, ia akan:
    • Mengatur choosing[i] = true, yang berarti proses i sedang memilih nomor antreannya.
    • Mengatur nilai number[i] ke angka yang lebih besar dari nomor antrean proses lainnya. Biasanya ini dilakukan dengan mencari nomor antrean tertinggi di antara proses lain, lalu menambahkannya satu.
    • Mengatur choosing[i] = false, setelah proses i telah memilih nomornya.
  2. Setelah proses i telah memilih nomornya, ia harus menunggu sampai:
    • Semua proses lain yang sedang memilih nomor selesai (choosing[j] == false untuk semua j).
    • Tidak ada proses j yang memiliki nomor antrean yang lebih kecil dari number[i], atau jika nomor antreannya sama, proses dengan indeks lebih kecil akan diizinkan masuk lebih dulu.
  3. Proses i kemudian masuk ke critical section.
  4. Setelah selesai, proses i akan mengatur number[i] = 0 untuk menunjukkan bahwa ia tidak lagi bersaing untuk masuk ke critical section.

Kode Pseudo untuk Algoritma Bakery:

choosing = [False] * N  # Menyimpan apakah setiap proses sedang memilih nomor
number = [0] * N        # Menyimpan nomor antrean setiap proses

def enter_critical_section(i):
    choosing[i] = True
    number[i] = max(number) + 1  # Ambil nomor antrean terbesar dan tambahkan 1
    choosing[i] = False
    
    for j in range(N):
        while choosing[j]:  # Tunggu sampai proses j selesai memilih nomor
            pass
        while number[j] != 0 and (number[j] < number[i] or (number[j] == number[i] and j < i)):
            pass  # Tunggu jika proses j punya nomor lebih kecil atau sama dan indeks lebih kecil

def leave_critical_section(i):
    number[i] = 0  # Keluarkan proses dari antrean setelah selesai di critical section

Keunggulan Algoritma Bakery

  1. Sederhana dan Mudah Dipahami: Algoritma Bakery memiliki mekanisme yang intuitif, di mana setiap proses hanya perlu memilih nomor antrean, mirip seperti bagaimana pelanggan mengambil nomor untuk dilayani di toko roti.
  2. Starvation-Free: Algoritma ini menjamin bahwa setiap proses yang ingin mengakses critical section pada akhirnya akan mendapatkan giliran. Tidak ada proses yang akan dibiarkan menunggu selamanya (starvation).
  3. Deadlock-Free: Algoritma Bakery juga mencegah terjadinya deadlock, di mana beberapa proses saling menunggu untuk mengakses critical section.
  4. Cocok untuk Sistem Multiprosesor: Algoritma ini dapat diterapkan pada sistem dengan banyak proses yang berjalan secara paralel, bukan hanya terbatas pada dua proses seperti Algoritma Peterson.

Keterbatasan Algoritma Bakery

  1. Skalabilitas yang Terbatas: Walaupun Algoritma Bakery dapat bekerja untuk lebih dari dua proses, ia kurang efisien pada sistem dengan jumlah proses yang sangat besar. Semakin banyak proses yang bersaing untuk memasuki critical section, semakin banyak pengecekan yang perlu dilakukan oleh setiap proses.
  2. Overhead: Proses pengecekan nomor antrean setiap proses bisa menimbulkan overhead yang cukup besar, terutama jika banyak proses sedang bersaing untuk mengakses critical section.
  3. Assumptions Tentang Komunikasi: Algoritma Bakery mengasumsikan bahwa semua proses memiliki akses yang sama terhadap memori bersama dan dapat melihat nomor antrean proses lain secara konsisten, yang tidak selalu realistis pada arsitektur modern dengan banyak core dan prosesor.

Aplikasi dan Relevansi Algoritma Bakery

Di lingkungan komputasi modern, Algoritma Bakery mungkin tidak lagi digunakan secara langsung karena optimisasi di prosesor modern yang menggunakan mekanisme sinkronisasi yang lebih efisien seperti mutexes atau locks yang disediakan oleh perangkat keras. Namun, konsep dari Algoritma Bakery tetap menjadi bagian penting dalam pendidikan pemrograman konkuren.

Algoritma ini mengajarkan pentingnya pengelolaan giliran dan koordinasi antar proses yang adil dalam lingkungan multi-threaded atau multiprosesor. Banyak prinsip yang diperkenalkan dalam Algoritma Bakery juga diterapkan dalam desain algoritma sinkronisasi modern, terutama dalam hal menghindari deadlock dan starvation.

Kesimpulan

Algoritma Bakery adalah solusi elegan dan intuitif untuk masalah eksklusi mutual di lingkungan multiprosesor. Dengan menggunakan pendekatan nomor antrean yang mirip dengan sistem pelayanan di toko roti, algoritma ini memastikan setiap proses dapat masuk ke critical section secara adil dan teratur. Meskipun mungkin tidak ideal untuk sistem komputasi modern yang lebih kompleks, Algoritma Bakery tetap merupakan alat pendidikan yang kuat dan berharga dalam memahami dasar-dasar sinkronisasi proses.

Loading