SISTEM OPERASI

ALGORITMA SEMAPHORE DALAM SISTEM OPERASI

·         Pengertian Semaphore

Semaphore adalah sebuah struktur data komputer yang digunakan untuk sinkronisasi proses, yaitu untuk memecahkan masalah di mana lebih dari satu proses atauthreaddijalankan secara bersamaan dan harus diatur urutan kerjanya.

·         Karakteristik Semaphore

Ø  Berdasarkan jenisnya, semaphore hanya bisa memiliki nilai 1 atau 0, atau lebih dari sama dengan 0.

Ø  Dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana.

Ø  Proses dipaksa berhenti sampai proses memperoleh penanda tertentu.

Ø  Variabel khusus untuk penandaan ini disebut semaphore.

·         Fungsi Kunci() dan Fungsi Buka()

Operasi standar pada semaphore (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 penjelasan 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).

·         Jenis Semaphore

-          Binary semaphore. Semaphore ini hanya memiliki nilai 1 atau 0. Sering juga disebut sebagai semaphore primitive

-          Counting semaphore. Semaphore ini memiliki nilai 0, 1, serta integer lainnya. Banyak sistem operasi yang tidak secara langsung mengimplementasikan semaphore ini, tetapi dengan memanfaatkan binary semaphore

·         Prinsip Semaphore

-          Dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana

-          Proses dipaksa berhenti sampai proses memperoleh penanda tertentu

-          Variabel khusus untuk penandaan ini disebut semaphore

·         Fungsi Semaphore

Semaphore berfungsi untuk menangani masalah sinkronisasi secara umum, yaitu:

1.      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 semaphore 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 semaphore mutex yang berupa binary semaphore dengan nilai awal 1.

thread 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.

2.      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 semaphore. Semaphore 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 semaphore 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.

3.      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 semaphore.

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 semaphore 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 (semaphore jenis ini disebut dengan semaphore 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 semaphore, yaitu dengan menambahkan waitingqueue pada masing-masing semaphore. 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 semaphore ini menjadi (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 < 0)

{

/*masukkan thread ke dalam waiting queue*/

/*blok thread tersebut*/

}

}

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

·         Kelebihan Semaphore

-          Dapat digunakan untuk membentuk mutex dan mengatur proses secara fleksibel

-          Merupakan tool yang serbaguna (powerful)

·         Kekurangan Semaphore

-          Termasuk Low Level

-          Kesulitan dalam pemeliharaannya, karena tersebar dalam seluruh program.

-          Menghapus wait => dapat terjadi nonmutual exclusion

-          Menghapus signal => dapat terjadi deadlock

-          Error yang terjadi sulit untuk dideteksi

-          Lebih baik menggunakan high level construct

-          Semaphore mungkin tersebar di seluruh program

-          Tidak mudah melihat seluruh efek semaphore (harus menguji semua kemungkinan yang dapat terjadi)

-          Akses terhadap suatu resource baru benar hanya jika semua proses yang mengakses resource tersebut diprogram secara benar

-          Penanganan mutex dan sinkronisasi sepenuhnya menjadi tanggung jawab programmer.