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);
