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.

Dalam kehidupan nyata, semafor adalah sistem sinyal yang digunakan untuk berkomunikasi secara visual. Dalam software, semafor adalah sebuah variabel bertipe integer yang selain saat inisialisasi, hanya dapat diakses melalui dua operasi standar, yaitu increment dan decrement. Semafor digunakan untuk menyelesaikan masalah sinkronisasi secara umum. Berdasarkan jenisnya, semafor hanya bisa memiliki nilai 1 atau 0, atau lebih dari sama dengan 0.

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

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 kata portmanteau 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

Operasi standar pada semafor (dalam bahasa pemrograman C):

void kunci(int sem_value) {
while(sem_value <= 0); sem_value--; } void buka(int sem_value) { sem_value++; }

Nama asli dari operasi tersebut sebenarnya adalah Proberen (test) dan Verhogen (increment). Namun, sebutan untuk 2 method ini sangat beragam, antara lain sering dikenal dengan nama : release dan acquire, P dan V, serta kunci dan buka. Dalam buku ini akan digunakan istilah buka dan kunci. Fungsi wait dipanggil ketika thread akan memasuki critical section-nya atau ketika thread akan memakai resource yang tersedia. Jika sem_value kurang dari sama dengan 0, thread tersebut harus menunggu sampai thread lain memanggil fungsi buka. Fungsi buka dipanggil ketika thread meningggalkan critical section-nya atau ketika melepaskan resource yang telah digunakannya. Tentu saja kedua operasi tersebut harus bersifat atomik karena sem_value dapat diakses oleh beberapa proses (shared resource).

Semafor memiliki dua jenis, yaitu:

1. Binary semaphore . Semafor ini hanya memiliki nilai 1 atau 0. Sering juga disebut sebagai semafor primitif
2. Counting semaphore . Semafor ini memiliki nilai 0, 1, serta integer lainnya. Banyak sistem operasi yang tidak secara langsung mengimplementasikan semafor ini, tetapi dengan memanfaatkan binary semaphore

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.

Fungsi Semafor

Seperti telah disebutkan sebelumnya, semafor berfungsi untuk menangani masalah sinkronisasi secara umum, yaitu:

• Mutual Exclusion . Sesuai dengan prinsip mutual exclusion, jika suatu thread sedang berada dalam critical section-nya, thread lain harus menunggu thread tersebut keluar dari critical section-nya sebelum dapat memasuki critical section-nya sendiri. Di sinilah semafor digunakan, thread yang akan memasuki critical section-nya akan memanggil fungsi kunci terlebih dahulu. Jika tidak ada thread lain yang sedang berada dalam critical section, thread ini akan memasuki critical section-nya. Jika terdapat thread lain yang sedang berada dalam critical section-nya, thread ini harus menunggu.Setelah thread keluar dari critical section-nya, thread tersebut akan memanggil fungsi buka sehingga sem_value akan naik menjadi lebih dari 0, dan satu (dari beberapa) thread yang sedang menunggu akan mendapatkan giliran untuk memasuki critical section-nya.

Sebagai contoh, misalnya terdapat dua buah thread yang sedang berjalan bersamaan:

thread A: thread B:
count = count + 1; count = count + 1;

Thread A dan B mengakses variabel yang sama, yaitu count sehingga thread A dan B harus berjalan satu-satu. Untuk itu digunakan semafor mutex yang berupa binary semaphore dengan nilai awal 1.

hread A: thread B:
kunci(mutex); kunci(mutex);
count = count + 1; count = count + 1;
buka(mutex); buka(mutex);

Thread manapun yang mengeksekusi kunci terlebih dahulu akan jalan terus, sedangkan thread yang tiba belakangan akan menunggu sampai thread yang sudah berjalan terlebih dahulu mengeksekusi buka, setelah itu kedua thread berjalan lagi dengan normal.

• Resource Controller . Bayangkan sebuah restoran yang setiap malamnya ramai dikunjungi pelanggan. Kapasitas restoran terbatas, tetapi pemilik restoran memiliki kebijakan bahwa semua pengunjung yang datang akan mendapatkan kesempatan untuk makan, dengan konsekuensi yaitu pelanggan harus sabar menunggu gilirannya. Oleh karena itu, dikerahkanlah pegawai restoran untuk menahan tamu di luar jika restoran penuh lalu mempersilahkan tamu masuk jika tempat telah tersedia.Dari analogi di atas, pelanggan adalah thread, kapasitas restoran adalah resource, dan pegawai restoran adalah semafor. Semafor menyimpan banyaknya resource yang tersedia. Saat thread ingin memakai resource ia akan memanggil fungsi kunci. Jika resource masih tersedia, thread bisa langsung menggunakannya, sebaliknya jika semua resource sedang dipakai, thread tersebut harus menunggu. Setelah resource selesai dipakai thread akan memanggil fungsi buka sehingga resource yang bebas bertambah

Contohnya dapat kita lihat pada kasus berikut: Terdapat tiga buah thread yang berjalan bersamaan. Resource yang tersedia hanya cukup untuk dua buah thread.

thread A: thread B: thread C:
//critical section //critical section //critical section

Tentu saja harus diatur agar pada suatu saat hanya ada dua buah thread yang berada pada critical section-nya. Hal ini dilakukan dengan menggunakan semafor multiplex yaitu sebuah counting semaphore dengan nilai awal sama dengan jumlah resource yang tersedia yaitu dua.

thread A: thread B: thread C:
kunci(multiplex); kunci(multiplex); kunci(multiplex);
//critical section //critical section //critical section
buka(multiplex); buka(multiplex); buka(multiplex);

Jika dua buah thread sedang berada dalam critical section, thread berikutnya yang akan memasuki critical section harus menunggu kedua thread tersebut selesai untuk dapat memasuki critical section-nya.

• Sinkronisasi Antar-Proses. Ada kalanya suatu thread memerlukan resource yang dihasilkan oleh thread lainnya. Oleh karena itu dibutuhkan suatu mekanisme untuk mengatur urutan eksekusi thread. Mekanisme ini dilakukan dengan memanfaatkan semafor.

Sebagai contoh, misalnya terdapat dua buah thread yang sedang berjalan bersamaan:

thread A: thread B:
count = count + 1; count = count * 2;

Nilai awal dari variabel count adalah 5, nilai akhir yang diinginkan adalah 12, oleh karena itu thread A harus dieksekusi sebelum thread B. Agar hal ini dapat terjadi dibutuhkan suatu semafor mutex yang merupakan sebuah binary semaphore dengan nilai awal 0.

thread A: thread B:

count = count + 1; kunci(mutex);

buka(mutex); count = count * 2;

Thread B akan menunggu sampai eksekusi thread A selesai sebelum melanjutkan.

Jika kita cermati fungsi kunci, thread akan terus berada dalam waiting loop sampai sem_value naik lebih dari 0. Padahal, di dalam loop tersebut thread tidak melakukan tugas apa-apa. Inilah yang disebut dengan busy waiting (semafor jenis ini disebut dengan semafor spinlock). Hal ini tentu saja akan berakibat buruk terhadap kinerja CPU, karena loop tersebut membutuhkan CPU cycle, sementara loop tersebut tidak menghasilkan apa-apa, jadi sama saja dengan menyia-nyiakan CPU cycle.

Untuk mengatasi hal ini, dibuatlah modifikasi dari semafor, yaitu dengan menambahkan waiting queue pada masing-masing semafor. Tujuannya adalah agar thread yang harus menunggu dipindahkan ke waiting queue dan kegiatannya dihentikan sementara.

Ketika thread keluar dari critical section-nya, thread tersebut akan memanggil fungsi buka yang akan mengeluarkan satu (dari beberapa) thread yang berada dalam waiting queue lalu membangunkannya untuk kemudian memasuki critical section-nya.

Struktur semafor ini menjadi (masih dalam bahasa C):

void buka(int sem_value)
{
sem_value++;
if(sem_value <= 0)

{ /*keluarkan satu thread dari waiting queue*/ /*aktifkan thread tersebut*/ } } void kunci(int sem_value) { sem_value--; if(sem_value <>

Berbeda dengan semafor yang biasa, pada semafor yang telah dimodifikasi ini sem_value bisa menjadi negatif. Jika kita renungkan maknanya, ternyata ketika semafor bernilai negatif, nilai tersebut melambangkan banyaknya thread yang berada pada waiting queue semafor tersebut

Keuntungan menggunakan semafor:

1. dari segi programming, penanganan masalah sinkronisasi dengan semafor umumnya rapi dan teratur, sehingga mudah untuk dibuktikan kebenarannya
2. semafor diimplementasikan dalam hard code sehingga penggunaannya bersifat portabel.

Artikel Terkait: