SEMAPHORE

2.1  PENGERTIAN SEMAPHORE

Semaphore adalah mekanisme efektif yang digunakan baik pada system uniprosesor  maupun sistem multiprosesor. Semaphore pada dasarnya adalah counter yang  diasosiasikan dengan struktur data. Semaphore diperiksa oleh semua kernel thread sebelum kernel thread tersebut mencoba untuk mengakses struktur data. Setiap semaphore dapat dipandang sebagai objek yang terdiri atas Variable integer List proses yang sedang menunggu (waiting) Dua metode atomik: down() atau up(). Metode down() mengurangi nilai dari semaphore. Jika nilai yang baru kurang dari 0, metode ini menambahkan proses yang sedang berjalan ke list semaphore dan mem-block proses tersebut. Metode up() menambah nilai dari semaphore dan jika nilai barunya sama dengan atau lebih dari 0, mengaktivasi kembali proses dalam semaphore list.

Tiap stuktur data yang diproteksi memiliki semaphorenya masing-masing yang diinisiasi dari 1. Ketika sebuah kernel control path akan mengakses struktrur data tersebut, control path mengeksekusi metode down() pada semaphore bersangkutan. Jika nilai baru semaphore tidak negatif, akses ke data dapat dilakukan. Sebaliknya jika nilai baru negatif, proses yang mengeksekusi kernel control path ditambahkan ke dalam list semaphore dan di-block. Ketika proses lain mengeksekusi metode up() pada semaphore tersebut, salah satu dari proses dalam list diperbolehkan untuk dilanjutkan.

Semaphore adalah salah satu cara menangani critical section. Semaphore S merupakan variabel bertipe integer yang diakses dengan 2 standar operasi atomic, yaitu wait dan  signal. Operasi-operasi ini diwakili dengan P (wait) dan V(signal), sebagai berikut:

Wait(S) : while S 0 do no)op; S:=S – 1;

Signal : S:=S + 1;

            Misalkan ada 2 proses yang sedang berjalan secara konkure, yaitu P1 denga pernyataan S1 dan P2 dengan pernyataan S2. andaikan kita mengharapkan S2 baru akan dijalankan hanya setelah S1 selesai. Hal ini dapat dilakukan dengan menggunakan bantuan semaphore synch (dengan nilai awal = 0) yang akan dishare oleh kedua proses. Untuk Proses P1 : S1 ; Signal(synch); Untuk proses P2: Wait(synch); S2; Karena nilai awal untuk synch adalah nol, maka P2 akan mengeksekusi S2 hanya setelah P1 mengerjakan signal(synch) setelah S1.

Salah satu kerugian dari penggunaan semaphore diatas adalah adanya busy waiting. Apabila suatu proses menempati critical, dan ada proses lain ingin masuk critical section, maka kan terjadi iterasi secara terus-menerus pada entry-section. Hal ini akan menimbulkan masalah pada sistem yang menggunakan konsep multiprogramming.

Untuk menghindari busy waiting, dilakukan modifikasi pada operasi wait dan signal. Jika suatu proses sedang mengeksekusi operasi wait, maka nilai semaphore menjadi tidak positif. Pada saat ini proses akan memblok dirinya sendiri (blok) dan ditempatkan pada waiting queue. Proses yang sedang diblok akan menunggu hingga semaphore S direstart, yaitu pada saat beberapa proses yang lain mengeksekusi operasi signal. Suatu proses akan direstart dengan operasi wakeup, yang akan mengubah proses dari keadaan waiting ke ready.

Beberapa Prinsip Semaphore :

1.      Dua proses dapat saling berkaitan atau menentukan proses yang lain dengan memanfaatkan signal-sinal

2.      Sebuah proses akan dihentikan oleh proses yang lain, ketika mendapatkan signal tertentu. Suatu proses akan menunggu diproses setelah nilai integer menjadi 0. selanjutnya sinyal akan dilakukan increamen dengan penambahan 1

3.      Semaphore merupakan variable bertipe integer yang diakses oleh 2 operasi atomik standar, yaitu wait dan signal.

4.      Terdapat dua operasi terhadap semaphore yaitu Down dan Up.

Nama aslinya : P dan V

2. 2   MACAM-MACAM SEMAPHORE

Ada 2 macam semafor yang cukup umum, yaitu: 

1. Binary semaphore 

2. Counting semaphore

Binary semaphore adalah semafor yang bernilai hanya 1 dan 0. Sedangkan Counting semaphore adalah semafor yang dapat bernilai 1 dan 0 dan nilai integer yang lainnya. Banyak sistem operasi yang hanya mengimplementasi binary semaphore sebagai primitif, sedangkan counting semaphore dibuat dengan memakai primitif ini. Untuk lebih rinci mengenai cara pembuatan counting semaphore dapat dilihat pada bagian berikutnya. 

Perlu diketahui di sini bahwa, ada beberapa jenis dari counting semaphore. Salah satu jenisnya adalah semafor yang tidak mencapai nilai negatif (seperti yang dicontohkan pada bagian sebelumnya). Jenis yang lain adalah semaphore yang dapat mencapai nilai negatif.

Solusi Pembuatan Counting Semaphore dari Binary Semaphore.

Pembuatan counting semaphore banyak dilakukan para programmer untuk memenuhi alat sinkronisasi yang sesuai dengannya. Seperti yang telah dibahas di atas, bahwa counting semaphore ada beberapa macam. Pada bagian ini, akan dibahas counting semaphore yang memperbolehkan harga negatif. 

Listing program di bawah ini diambil dari buku Silberschatz. 

00 binary-semaphore S1,S2; 01 int C;

Subrutin waitC dapat dilihat di bawah ini: 02 wait (S1);03 C--; 04 if ( C < 0 ) { 05 signal (S1); 06 wait (S2); 07 } 08 signal (S1); subrutin signalC dapat dilihat di bawah ini: 09 wait (S1); 10 C++; 11 if (C <= 0) 12 signal (S2); 13 else 14 signal (S1); Kita memerlukan dua binary semaphore pada kasus ini, maka pada baris 00 didefinisikan dua binary semaphore. Baris 01 mendefinisikan nilai dari semafor tersebut. Perlu diketahui di sini bahwa waitC adalah wait untuk counting semaphore, sedangkan wait adalah untuk binary semaphore. Jika diperhatikan pada subrutin waitC dan signalC di awal dan akhir diberikan pasangan wait dan signal dari binary semaphore. Fungsi dari binary semaphore yang ini adalah untuk menjamin critical section (instruksi wait dan signal dari semafor bersifat atomic, maka begitu pula untuk waitC dan signalC, jadi kegunaan lain semafor adalah untuk membuat suatu subrutin bersifat atomic). Binary semaphore S2 sendiri digunakan sebagai tempat menunggu giliran proses-proses. Proses-proses tersebut menunggu dengan cara spinlock atau non-spinlock tergantung dari implementasi binary semaphore yang ada.

Perhatikan baris 03 dan 04. Baris ini berbeda dengan apa yang sudah dijabarkan pada bagian sebelumnya. Karena baris ini maka memungkinkan nilai semafor untuk menjadi negatif. Lalu apa artinya bagi kita? Ternyata nilai negatif mengandung informasi tambahan yang cukup berarti bagi kita yaitu bila nilai semafor negatif, maka absolut dari nilai tersebut menunjukkan banyaknya proses yang sedang menunggu atau wait. Jadi arti baris 11 menyatakan bahwa bila ada proses yang menunggu maka bangunkan mereka semua untuk berkompetisi. Mengapa pada baris 05 dilakukan signal untuk S1? Alasannya karena seperti yang telah kita ketahui bahwa semaphore menjamin ketiga sifat dari critical section. Tetapi adalah tidak relevan bila pada saat waktu menunggu, waitC masih mempertahankan mutual exclusivenya. Bila hal ini terjadi, proses lain tidak akan dapat masuk, sedangkan proses yang berada di dalam menunggu proses yang lain untuk signal. Dengan kata lain deadlock terjadi. Jadi, baris 05 perlu dilakukan untuk menghilangkan sifat mutual exclusive pada saat suatu proses menunggu. Pada baris 12 hanya menyatakan signal untuk S2 saja. Hal ini bukanlah merupakan suatu masalah, karena jika signal S2 dipanggil, maka pasti ada proses yang menunggu akan masuk dan meneruskan ke instruksi 07 kemudian ke instruksi 08 di mana proses ini akan memanggil signal S1 yang akan mewakili kebutuhan di baris 12.

2. 3  FUNGSI SEMAPHORE

a.         Menyelesaikan Masalah Critical Section. Critical section adalah suatu bagian yang berisi sejumlah variabel yang akan dishare (dipengaruhi dan mempengaruhi ) proses yang lain. Secara umum, penyelesaian critical section harus memenuhi 3 syarat :

1. Mutual exclusion.

Jika suatu proses sedang mengerjakan critical section, maka tidak boleh ada proses lain yang masuk (mengerjakan) critical section tersebut.

2. Progress.

Jika tidak ada suatu proses yang megerjakan critical section, dan ada beberapa proses yag akan masuk ke critical section, maka hanya proses-proses yang sedang berada pada entry-section saja yang boleh berkompetisi untuk mengerjakan critical section.

3. Bounded waiting.

Besarnya waktu tunggu dari suatu proses yang akan memasuki critical section sejak proses itu meminta ijin untuk mengerjakan critical section, hingga permintaan itu dipenuhi. Untuk setiap proses yang akan masuk critical section harus meminta ijin terlebih dahulu, dan proses yang mendapat izinlah yang akan masuk ke critical section. Gambar dibawah ini menunjukkan struktur untuk proses Pi. Entry-section adalah daerah tempat proses menunggu untuk memasuki critical section. Sedangkan Exit-section adalah daerah dimana suatu proses baru saja keluar dari critical section.

b.         Semafor Menyelesaikan Masalah Sinkronisasi antar Proses Kadangkala kita ingin membuat suatu proses untuk menunggu proses yang lain untuk menjalankan suatu perintah. Isu yang ada di sini adalah bagaimana caranya suatu proses mengetahui bahwa proses yang lain telah menyelesaikan instruksi tertentu. Oleh karena itu digunakanlah semafor karena semafor adalah solusi yang cukup baik dan mudah untuk mengatasi hal tersebut. Nilai semaphore diset menjadi 0 Proses 1 Proses 2 56 print "satu" 17 wait(semaphoreVar) 57 signal(semaphoreVar) 18 print "dua" siapapun yang berjalan lebih cepat, maka keluarannya pasti "satu" kemudian diikuti oleh "dua". Hal ini disebabkan karena jika proses 2 berjalan terlebih dahulu, maka proses tersebut akan menunggu (nilai semafor = 0) sampai proses 1 memanggil signal. Sebaliknya jika proses 1 berjalan terlebih dahulu, maka proses tersebut akan memanggil signal untuk memberikan jalan terlebih dahulu kepada proses 2.

2. 4  IMPLEMENTASI SEMAPHORE

1.         Windows

Fungsi yg dipakai adalah CreateSemaphore. Biasanya digunakan untuk membatasi jumlah thread yang memakai suatu resource secara bersamaan

2.         Java

Semafor di Java™ bersifat transparan oleh programmer

3.         Java™  menyembunyikan Semafor dibalik konsep monitor

4.          Reserved Word yang dipakai Java™ adalah synchronized

2. 5  KELEMAHAN SEMAPHORE

1.         Termasuk Low Level

2.         Kesulitan dalam pemeliharaannya, karena tersebar dalam seluruh program.

3.         Menghapus wait => dapat terjadi nonmutual exclusion.

4.          Menghapus signal => dapat terjadi deadlock

5.         Error yang terjadi sulit untuk dideteksi

6.         Lebih baik menggunakan high level construct