Algoritma Semaphore

Semaphore adalah pendekatan yang dikemukakan Dijkstra. Prinsip semaphore

adalah sebagai berikut : Dua proses atau lebih dapat bekerja sama dengan

menggunakan penanda-penanda sederhana. Proses dipaksa berhenti sampai proses

memperoleh penanda tertentu. Sembarang kebutuhan koordinasi kompleks dapat

dipenuhi dengan strukstur penanda yang sesuai kebutuhannya. Variabel khusus untuk

penandaan ini disebut semaphore.

Semaphore adalah alat untuk sinkronisasi yang tidak membutuhkan busy

waiting. Semaphore S berupa variable integer. Semaphore hanya dapat diakses melalui

operasi atomic yang tak dapat diinterupsi sampai kode selesai. Operasi dari semaphore

S adalah wait dan signal berikut :

wait (S):

while S≤ 0 do no-op;

S--;

signal (S):

S++;

Adanya semaphore mempermudah penyelesaian persoalan critical section pada

n proses. Penyelesaian critical section menggunakan semaphore menggunakan variabel

umum berikut :

semaphore mutex;

Variabel semaphore mutex diinisialisasi mutex = 1. Sedangkan struktur program

untuk proses Pi adalah :

do {

wait(mutex);

critical section

signal(mutex);

remainder section

} while (1);

Implementasi semaphore harus dapat menjamin mutual exclusion variabel

semaphore, yaitu hanya mengijinkan satu proses pada satu saat yang boleh

memanipulasi semaphore. Implementasi sebuah semaphore menggunakan struktur data

record sebagai berikut :

typedef struct {

int value;

struct process *L;

} semaphore;

Pada semaphore terdapat dua operasi sederhana yaitu block untuk menghentikan

sementara proses yang menggunakan semaphore dan wakeup(P) untuk melanjutkan

eksekusi proses P yang di-blok. Operasi wait dan signal dari semaphore didefinisikan

sebagai :

wait(S):

S.value--;

if (S.value < 0) {

tambahkan proses ke S.L;

block;

}

signal(S):

S.value++;

if (S.value <= 0) {

hapus proses P dari S.L;

wakeup(P);

}

Sebagai alat sinkronisasi yang umum, semaphore dieksekusi oleh suatu proses

setelah proses lain. Misalnya semaphore B pada proses Pj hanya dieksekusi setelah

semaphore A dieksekusi pada proses Pi. Pada saat menggunakan semaphore, flag

diinisialisasi 0. Kode yang diakses proses Pi dan Pj dapat dilihat berikut ini :

Pi                                            Pj

A                                  wait(flag)

signal(flag)                  B

Semaphore merupakan salah satu sumber daya sistem. Misalnya dua proses P1

dan P2, dua sumber daya kritis R1 dan R2, proses P1 dan P2 harus mengakses kedua

sumber daya. Kondisi berikut dapat terjadi : R1 diberikan ke P1, sedang R2 diberikan ke

P2. Apabila dua proses untuk melanjutkan eksekusi memerlukan kedua sumber daya

sekaligus maka kedua proses akan saling menunggu sumber daya lain selamanya. Tak

ada proses yang dapat melepaskan sumber daya yang telah dipegangnya karena

menunggu sumber daya lain yang tak pernah diperolehnya. Kedua proses dalam kondisi

deadlock, tidak dapat membuat kemajuan apapun.

Pada saat beberapa proses membawa semaphore dan masing-masing proses

menunggu semaphore yang sedang dibawa oleh proses lain maka kemungkinan akan

terjadi deadlock. Misalnya terdapat dua semaphore S dan Q yang diinisialisasi 1.

P0                                           P1

wait(S);                        wait(Q);

wait(Q);                       wait(S);

signal(S);                     signal(Q);

signal(Q);                    signal(S);

Proses P0 dan P1 masing-masing menjalankan operasi wait(S) dan wait(Q). Kemudian

proses P0 dan P1 menjalankan operasi wait(Q) dan wait(S) maka sistem akan deadlock

sampai salah satu proses menjalankan operasi signal.

Apabila suatu proses tidak pernah dihapus dari antrian semaphore setelah suatu

semaphore dihentikan sementara, maka terjadi bloking yang tak terbatas. Keadaan ini

disebut starvation.

Keadaan starvation digambarkan sebagai berikut. Misalnya terdapat tiga proses

P1, P2 dan P3 yang memerlukan pengaksesan sumber daya R secara periodik. Skenario

yang bisa terjadi :

·         P1 sedang diberi sumber daya R, P2 dan P3 blocked menunggu sumber daya R.

·         Ketika P1 keluar dari critical section, P2 dan P3 diijinkan mengakses R.

·         Asumsi P3 diberi hak akses. Kemudian setelah selesai, hak akses kembali diberikan

ke P1 yang saat itu kembali membutuhkan sumber daya R.

Jika pemberian hak akses bergantian terus-menerus antara P1 dan P3, maka P2

tidak pernah memperoleh pengaksesan sumber daya R, meski tidak ada deadlock. Pada

situasi ini, P2 mengalami yang disebut Starvation.

Terdapat dua bentuk semaphore yaitu counting semaphore dan binary

semaphore. Counting semaphore menggunakan nilai integer yang mempunyai

jangkauan tak terbatas seperti pada struktur yang telah dijelanskan diatas. Binary

semaphore menggunakan nilai integer dengan jangkauan antara 0 dan 1 sehingga

implementasinya lebih sederhana. Counting semaphore S diatas dapat

diimplementasikan dengan binary semaphore. Struktur data yang digunakan adalah :

binary-semaphore S1, S2;

int C:

Struktur data diatas diinisialisasi dengan

S1 = 1

S2 = 0

C = initial value of semaphore S

Implementasi operasi wait dan signal pada binary semaphore S adalah sebagai berikut :

Operasi wait :

wait(S1);

C--;

if (C < 0) {

signal(S1);

wait(S2);

}

signal(S1);

Operasi signal :

wait(S1);

C ++;

if (C <= 0)

signal(S2);

else

signal(S1);