Algoritma Peterson: Solusi Klasik untuk Masalah Sinkronisasi dalam Pemrograman

Dalam dunia komputasi, terutama pada sistem multi-threading atau multi-processing, ada tantangan yang disebut race condition. Race condition terjadi ketika dua atau lebih proses atau thread bersaing untuk mengakses sumber daya bersama secara bersamaan, tanpa adanya mekanisme pengaturan yang tepat. Akibatnya, hasil eksekusi bisa tidak dapat diprediksi dan menyebabkan masalah seperti kehilangan data, inkonsistensi, atau bahkan kegagalan program.

Salah satu solusi klasik untuk mengatasi masalah ini adalah Algoritma Peterson, yang ditemukan oleh seorang ilmuwan komputer asal Amerika, Gary Peterson, pada tahun 1981. Algoritma ini menawarkan metode yang elegan dan sederhana untuk mengatasi masalah mutual exclusion (eksklusi mutual) di lingkungan dua proses atau lebih, yang ingin mengakses sumber daya secara bersamaan.

Latar Belakang: Eksklusi Mutual

Eksklusi mutual adalah konsep penting dalam concurrent programming di mana hanya satu proses yang diizinkan mengakses sumber daya kritis pada satu waktu. Proses lain yang ingin mengakses sumber daya tersebut harus menunggu sampai sumber daya bebas. Tanpa eksklusi mutual, beberapa proses bisa mengakses sumber daya kritis bersamaan, yang dapat menyebabkan kondisi tak terduga.

Cara Kerja Algoritma Peterson

Algoritma Peterson bekerja dengan menggunakan dua variabel utama untuk memediasi akses ke critical section (bagian dari kode yang mengakses sumber daya bersama):

1. flag[i]: Sebuah array boolean yang digunakan untuk menunjukkan apakah proses i ingin masuk ke critical section atau tidak.
2. turn: Sebuah variabel yang menentukan giliran proses mana yang diizinkan untuk masuk ke critical section.

Dalam konteks dua proses (katakanlah Proses A dan Proses B), setiap proses secara bergantian mencoba mengakses critical section. Berikut adalah langkah-langkah utama dalam algoritma:

1. Proses A mengatur flag[A] = true, yang menunjukkan bahwa ia ingin memasuki critical section.
2. Proses B juga mengatur flag[B] = true saat ingin masuk ke critical section.
3. Kedua proses kemudian mengatur variabel turn, yang memberi giliran kepada lawan prosesnya untuk mendapatkan akses ke critical section terlebih dahulu.
4. Proses A memeriksa apakah Proses B ingin masuk ke critical section dan apakah giliran diberikan pada Proses B (turn == B). Jika ya, Proses A akan menunggu hingga Proses B selesai. Sebaliknya, jika Proses B sedang menunggu, Proses A akan diizinkan masuk.
5. Setelah Proses A selesai menjalankan critical section, ia mengatur flag[A] = false sehingga Proses B bisa masuk.
6. Proses yang menunggu (dalam hal ini Proses B) akan segera melanjutkan jika giliran telah berganti dan tidak ada konflik dengan Proses A.

Kode Pseudonya:

flag = [False, False]  # Menggunakan 2 proses
turn = 0  # Menginisialisasi giliran

def process_A():
    flag[0] = True
    turn = 1
    while flag[1] and turn == 1:
        pass  # Tunggu sampai Proses B selesai
    # Critical section Proses A
    flag[0] = False  # Keluar dari critical section

def process_B():
    flag[1] = True
    turn = 0
    while flag[0] and turn == 0:
        pass  # Tunggu sampai Proses A selesai
    # Critical section Proses B
    flag[1] = False  # Keluar dari critical section

Keunggulan dan Keterbatasan Algoritma Peterson

Algoritma Peterson memiliki beberapa keunggulan yang membuatnya menjadi solusi efektif untuk masalah sinkronisasi, terutama dalam sistem dua proses:

1. Kesederhanaan: Algoritma ini sangat sederhana dan mudah dipahami, terutama jika dibandingkan dengan algoritma eksklusi mutual yang lebih kompleks seperti Dekker’s Algorithm atau solusi berbasis semaphore.
2. Deadlock-free: Algoritma ini menjamin bahwa tidak ada kondisi deadlock di mana kedua proses saling menunggu tanpa akhir untuk memasuki critical section.
3. Starvation-free: Tidak ada proses yang akan mengalami starvation, artinya semua proses yang ingin mengakses critical section pada akhirnya akan diizinkan masuk.

Namun, algoritma ini juga memiliki beberapa keterbatasan:

1. Tidak Skalabel: Algoritma Peterson dirancang khusus untuk sistem dua proses. Untuk memperluas algoritma ini ke lebih dari dua proses, implementasinya menjadi lebih kompleks dan tidak lagi efisien.
2. Kinerja di Arsitektur Modern: Algoritma ini dirancang untuk arsitektur komputer yang lebih sederhana. Pada sistem modern dengan prosesor multi-core, penggunaan algoritma ini mungkin tidak seefisien karena adanya optimisasi cache dan memory ordering yang berbeda.

Aplikasi dan Relevansi di Masa Kini

Meskipun Algoritma Peterson mungkin tidak selalu menjadi pilihan di sistem multi-core modern karena kompleksitas dan limitasinya dalam arsitektur multi-prosesor, ia tetap menjadi alat pendidikan yang sangat berguna. Algoritma ini mengajarkan prinsip-prinsip dasar eksklusi mutual, sinkronisasi proses, dan masalah race condition dengan cara yang mudah dipahami.

Dalam lingkungan akademik, Algoritma Peterson sering digunakan untuk mengenalkan mahasiswa pada masalah-masalah fundamental dalam concurrent programming. Mempelajari algoritma ini membantu memahami prinsip-prinsip yang digunakan dalam implementasi algoritma sinkronisasi modern seperti mutex, semaphores, atau locks.

Kesimpulan

Algoritma Peterson mungkin telah usang dalam beberapa aspek modernitas pemrograman paralel, namun nilainya sebagai solusi yang sederhana dan elegan untuk masalah eksklusi mutual tidak dapat dipungkiri. Dalam dunia komputasi, masalah sinkronisasi tetap menjadi tantangan yang besar, dan memahami solusi klasik seperti Algoritma Peterson membantu kita mengapresiasi kemajuan yang telah dibuat di bidang ini. Lebih dari sekadar algoritma, ini adalah bagian penting dari sejarah komputasi yang tetap relevan untuk dipelajari dan dipahami oleh para pengembang dan ilmuwan komputer.