Semafor (pemrograman)

Semafor adalah sebuah struktur data komputer yang digunakan untuk sinkronisasi proses, yaitu untuk memecahkan masalah di mana lebih dari satu proses atau thread dijalankan secara bersamaan dan harus diatur urutan kerjanya. Semafor dicetuskan oleh Edsger Dijkstra dan pertama digunakan dalam sistem operasi THE.

Nilai semafor diinisialisasi dengan jumlah resource yang dikendalikannya. Dalam kasus khusus di mana ada satu shared resource, semafornya disebut "semafor biner". Semafor adalah solusi klasik dari dining philosophers problem, walaupun tidak mencegah deadlock.

Penjelasan

Semafor hanya dapat diakses dengan menggunakan operasi berikut:

P(Semaphore s)
{
  wait until s > 0, then s:= s-1;
  /* must be atomic once s > 0 is detected */
}

V(Semaphore s)
{
  s:= s+1;   /* must be atomic */
}

Init(Semaphore s, Integer v)
{
  s:= v;
}

Perhatikan bahwa menginkrementasi variabel s tidak boleh diinterupsi, dan operasi P tidak boleh diinterupsi bila s ditemukan sebagai nonzero. Hal ini dapat dilakukan dengan perintah seperti test-and-set (bila instruction set arsitektur komputer mendukungnya), atau (dalam sistem prosesor mikro) mengabaikan interrupt untuk mencegah proses lain menjadi aktif.

Nama-nama P dan V berasal dari bahasa Belanda. V artinya verhoog, atau "inkrementasi". Beberapa penjelasan telah diusulkan untuk P, termasuk passeer "pass", probeer "coba", dan pakken "ambil"), tapi Dijkstra sebenarnya menulis bahwa ia memaksudkan P sebagai lakuran rekaannya sendiri prolaag, singkatan dari probeer te verlagen, atau "coba untuk dekrementasi". Hal ini berasal dari kenyataan bahwa dalam bahasa Belanda, kata untuk dekrementasi dan inkrementasi sama-sama diawali huruf V, dan bila kata tersebut dituliskan secara lengkap dapat membingungkan pembaca yang tidak dapat berbahasa Belanda.

Nilai semafor adalah jumlah resource yang bebas. Bila hanya ada satu resource, sebuah semafor biner dengan nilai 0 atau 1 digunakan. Operasi P busy-wait sampai sebuah resource tersedia, kemudian mengklaimnya. V adalah kebalikannya; ia membuat sebuah resource tersedia kembali setelah proses selesai menggunakannya. Init hanya digunakan di awal untuk menginisialisasi nilai semafor. Operasi P dan V harus atomic, artinya operasi ini tidak boleh diselingi oleh proses lain dalam semafor yang sama.

Dalam bahasa pemrograman ALGOL 68, dalam kernel Linux, dan dalam beberapa buku bahasa Inggris, operasi P dan V disebut masing-masing down dan up. Dalam teknik perangkat lunak, mereka biasanya disebut wait dan signal, atau take dan release, atau pend dan post.

Untuk menghindari busy-waiting, sebuah semafor dapat memiliki sebuah queue atau antrian proses (biasanya FIFO atau pertama-masuk-pertama-keluar). Bila sebuah proses melakukan P pada sebuah semafor yang memiliki nilai 0, proses ini ditambahkan ke antrian. Ketika proses lain menginkrementasi nilai semafor dengan V, dan ada proses dalam antrian, salah satunya diambil dari antrian dan mulai dijalankan.

Semafor masih digunakan dalam bahasa pemrograman yang tidak mendukung bentuk sinkronisasi lain. Kecenderungan perkembangan bahasa pemrograman saat ini bergerak ke arah sinkronisasi yang lebih terstruktur, misalnya dengan monitor dan channel. Selain ketidakmampuannya mencegah deadlock, semafor tidak melindungi pemrogram dari kesalahan mengambil semafor yang sudah dipegang proses lain, dan lupa melepaskan semafor yang sudah diambil. Dengan kata lain, pemrograman semafor termasuk rumit dan error-prone.

Contoh

Karena semafor dapat memiliki variabel penghitung, ia dapat digunakan ketika beberapa threads ingin mencapai suatu tujuan secara bekerja sama. Misalnya:

Ada thread A yang ingin informasi dari 2 basis data sebelum ia dapat maju. Akses ke kedua basis data tersebut dikendalikan oleh dua thread B dan C. Keduanya memiliki message-processing loop; semua yang ingin menggunakannya menulis pesan dalam antrian pesan. Thread A menginisialisasi semafor S dengan init(S,-1). A kemudian menulis permohonan data, termasuk pointer ke semafor S, kepada baik B maupun C. Kemudian A memanggil P(S), yang memblokir. Kedua thread lain mengambil informasi; setelah mereka selesai, mereka memanggil V(S) dalam semafor. Hanya setelah keduanya selesai mengambil data, thread A dapat maju. Semafor seperti ini disebut "counting semaphore".

Selain counting semaphore, terdapat juga "blocking semaphore", yaitu semafor yang diinisialisasi dengan nilai 0. Artinya setiap thread yang melakukan P(S) akan diblokir sampai thread lain memanggil V(S). Jenis ini sangat berguna ketika urutan eksekusi thread harus diperhatikan.

Bentuk semafor paling sederhana adalah "semafor biner", digunakan untuk mengendalikan akses kepada satu resource, atau disebut juga mutual exclusion. Sebuah semafor biner selalu diinisialisasi dengan nilai 1. Ketika resource sedang digunakan, thread yang menggunakan memanggil P(S) untuk mengurangi nilai ini menjadi 0, dan setelah selesai menginkrementasi kembali nilainya menjadi 1 untuk menandakan resource yang sekarang bebas.

Pranala luar

semaphore.h programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1
A simple in-process semaphore using C#
J2SE class