Penjelasan Semaphore
Semaphore adalah salah satu cara menangani critical section, yang dikemukakan
oleh Dijkstra. Prinsip semaphore sebagai berikut:
Dua proses atau lebih dapat bekerja sama dengan menggunakan
penandapenanda sederhana. Proses dipaksa berhenti sampai proses
memperoleh penanda tertentu. Sembarang kebutuhan koordinasi kompleks
dapat dipenuhi dengan penanda yang sesuai kebutuhannya. Variabel khusus
untuk penandan ini disebut semaphore. Semaphore mempunyai dua property, yaitu :
1. Semaphore dapat diinisialisasi dengan nilai nonnegative.
2. Terdapat dua operasi terhadap semaphore yaitu Down dan Up. Nama asli yang disampaikan Dijkstra adalah operasi P dan V.
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:=S+1;
Misalkan ada 2 proses yang sedang berjalan secara konkuren, yaitu P1
dengan 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 di-share oleh kedua proses.
Untuk Proses P 1 :
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 section, dan ada proses lain
yang ingin masuk critical section, maka akan 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 (block ) 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.
Untuk mengimplmentasikan hal ini, semaphore dirancang dalam bentuk record :
type semaphore= Record
value : integer;
L: list of process;
end;
Var s: semaphore
Operasi-operasi pda semaphore;
wait(S) S.value :=S.value-1;
if S.value < 0 then
Begin
Tambahkan proses ini ke S.L.
block;
end;
Algoritma Semaphore Dijkstra
Model untuk algoritma Dijkstra semaphore dengan menggunakan rendevous
adalah sebagai berikut :
#define p 0
#define v 1
chan sema = [0] of { bit };
proctype dijkstra()
{ byte count = 1;
do
:: (count == 1) -> sema!p; count = 0
:: (count == 0) -> sema? v; count = 1
od
}
proctype user()
{ do
:: sema? p;
/* critical section */
sema!v;
/* non-critical section */
od
}
init
{ run dijkstra(); run user();
run user(); run user()
}
Algoritma Semaphore Dijkstra
Model untuk algoritma Dekker adalah sebagai berikut :
Bit x, y; /* signal masuk/keluar dari section */
byte mutex; /* # proses yang masuk critical section. */
byte turn,A_TURN,B_TURN; /* giliran siapa? */
active proctype A() {
x = 1;
turn = B_TURN;
(y == 0 || turn == A_TURN);
mutex++;
mutex–;
x = 0;
}
active proctype B() {
y = 1;
turn = A_TURN;
(x == 0 || turn == B_TURN);
mutex++;
mutex–;
y = 0;
}
active proctype monitor() {
assert(mutex != 2);
}
Algoritma Semaphore Peterson
Model untuk algoritma 3 (Peterson) adalah sebagai berikut :
#define true 1
#define false 0
bool flag[2];
bool turn;
proctype user(bool i)
{ flag[i] = true;
turn = i;
(flag[1-i] == false || turn == 1-i);
crit: skip; /* critical section */
flag[i] = false
}
init { atomic { run user(0); run user(1) } }
Penjelasan lebih Lanjut
1. Konsep Dasar Semaphore
Semaphore termasuk pendekatan yang diajukan oleh Djikstra, dengan
prinsip bahwa dua proses atau lebih dapat bekerja sama dengan
menggunakan penanda-penanda sederhana. Seperti proses dapat dipaksa
berhenti pada suatu saat, sampai proses mendapatkan penanda tertentu
itu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan
struktur penanda yang cocok untuk kebutuhan itu. Variabel khusus untuk
penanda ini disebut semaphore.Semaphore mempunyai dua sifat, yaitu:
Semaphore dapat diinisialisasi dengan nilai non-negatif.
Terdapat dua operasi terhadap semaphore, yaitu Down dan Up. Usulan asli yang disampaikan Djikstra adalah operasi P dan V.
Semaphore adalah salah satu teknik sinyal sederhana, dan merupakan
konsep penting dalam OS desain, dimana sebuah nilai integer digunakan
untuk pensinyalan antara proses. Hanya tiga operasi yang mungkin
dilakukan pada semaphore, yang semuanya atom: inisialisasi, penurunan,
dan penaikan. Operasi pengurangan dapat mengakibatkan terhalangnya
proses, dan kenaikan dari pengoperasian yang sedang berlangsung dapat
mengakibatkan terblokirnya suatu proses. Hal ini juga dikenal sebagai
sebuah perhitungan semaphore atau semaphore umum.
Semaphore adalah bendera digunakan untuk memeriksa apakah sumber daya
saat ini sedang digunakan oleh thread atau proses. Misalnya, jika suatu
proses ingin menggunakan printer, terlebih dahulu perlu memastikan
printer tersedia dengan memeriksa untuk melihat apakah semaphore telah
ditetapkan. jika sudah diatur, maka perlu menunggu untuk proses yang
saat ini telah selesai. Namun, jika printer bebas, proses ini akan
menetapkan semaphore dan mulai menggunakan printer, memblokir akses ke
semua proses lainnya sampai selesai.
Semaphore adalah teknik klasik untuk melindungi bagian penting dari
kode dari yang secara simultan dieksekusi oleh lebih dari satu thread.
Semaphore adalah generalisasi dari monitor. Sebuah monitor memungkinkan
hanya satu thread untuk mengunci objek sekaligus. Semaphore A N
memungkinkan proses. Proses meraih semaphore-eksklusif untuk menggunakan
semi disebut menenggak semaphore karena mereka diimplementasikan dengan
integer Countdown yang decrements untuk setiap kunci dan kenaikan untuk
masing-masing membuka. Jika semaphore adalah sepenuhnya terisi, thread
baru ingin menggunakannya akan menunggu sampai thread beberapa rilis
kunci dengan upping semaphore itu. Untuk semaphore untuk bekerja, cek
untuk penuh, dan penurunan harus dilakukan semua dalam satu instruksi
yang tidak pernah terputus atom. Instruksi monitor JVM menyediakan
dukungan hardware yang diperlukan untuk mensimulasikan semaphores.
Semaphore s, lain kontribusi penting oleh EW Dijkstra, dapat dilihat
sebagai ekstensi untuk mutex kunci. Semaphore adalah suatu obyek dengan
dua metode Tunggu dan Sinyal, sebuah integer swasta counter dan antrian
swasta (benang). Semantik dari semaphore adalah sangat sederhana.
Misalkan S adalah semaphore yang swasta counter telah diinisialisasi ke
integer non-negatif.
Ketika Tunggu dijalankan oleh thread, kita memiliki dua kemungkinan:
Penghitung S adalah positif
Dalam hal ini, konter ini mengalami penurunan sebesar 1 dan benang kembali pelaksanaannya.
Penghitung S adalah nol
Dalam hal ini, benang ditangguhkan dan dimasukkan ke dalam antrian pribadi S.
Ketika Sinyal dijalankan oleh thread, kami juga memiliki dua kemungkinan:
Antrian S tidak memiliki benang menunggu
Penghitung S ditingkatkan oleh satu dan benang kembali pelaksanaannya.
Antrian S telah menunggu threads
Dalam hal ini, konter S harus nol (lihat pembahasan Tunggu di atas).
Salah satu benang menunggu akan diizinkan untuk meninggalkan antrian dan
melanjutkan pelaksanaannya. Benang yang mengeksekusi Sinyal juga terus.
Operasi Tunggu atau Signal adalah atom. Ini berarti sekali kegiatan
Tunggu mulai (yaitu, pengujian dan penurunan nilai counter dan
memasukkan benang ke dalam antrian), mereka akan terus sampai akhir
tanpa gangguan apapun. Lebih tepatnya, meskipun ada banyak langkah untuk
melaksanakan Tunggu dan Signal, langkah-langkah ini dianggap sebagai
instruksi non-interruptible tunggal. Demikian pula, hal yang sama
berlaku untuk Sinyal. Apalagi, jika lebih dari satu benang mencoba
mengeksekusi Tunggu (atau sinyal), hanya satu dari mereka akan berhasil.
Kita tidak boleh membuat asumsi tentang mana thread akan berhasil.
Tunggu karena dapat menyebabkan thread untuk memblokir (yaitu, ketika
counter nol), ia memiliki efek yang sama dari operasi kunci dari sebuah
kunci mutex. Demikian pula, sebuah sinyal dapat melepaskan benang
tunggu, dan mirip dengan membuka operasi. Bahkan, semaphores dapat
digunakan sebagai kunci mutex. Pertimbangkan S semaphore dengan nilai
awal 1. Kemudian, Tunggu dan Signal sesuai untuk mengunci dan membuka:
Mari kita periksa bagaimana sepasang Tunggu dan Signal dapat menjamin
pengecualian bersama. Perlu diingat bahwa nilai awal counter dari S
adalah 1. Misalkan sejumlah benang mencoba untuk eksekusi Tunggu. Karena
hanya ada satu thread berhasil dapat mengeksekusi Tunggu, thread ini,
katakanlah A, menyebabkan counter berkurang sebesar 1, dan memasuki
bagian yang kritis. Karena nilai awal counter adalah 1, sekali thread A
memasuki critical section, konter menjadi 0, dan, sebagai hasilnya,
semua usaha berikutnya dalam melaksanakan Tunggu akan diblokir. Oleh
karena itu, membenarkan klaim kita bahwa Tunggu mirip untuk mengunci.
Ketika Sebuah thread keluar dari critical section, Sinyal dijalankan.
Jika ada menunggu benang, salah satu dari mereka akan dirilis, dan
thread ini dirilis memasuki critical section. Perhatikan bahwa counter
masih nol (karena, dalam hal ini, Sinyal tidak meningkatkan dan Tunggu
tidak mengurangi counter), yang berarti semua thread berikutnya yang
mencoba mengeksekusi Tunggu diblokir. Di sisi lain, jika tidak ada
benang menunggu, pelaksanaan Sinyal menyebabkan nilai dari counter akan
meningkat dengan 1, sehingga nilai saat ini 1. Dalam hal ini, thread
berikutnya yang mengeksekusi Tunggu bisa masuk ke bagian kritis. Oleh
karena itu, Sinyal mirip untuk membuka. Singkatnya, kita belajar bahwa
pengaturan counter untuk 1 awalnya akan menjamin bahwa paling banyak
satu thread bisa di bagian kritis, jika semua benang yang melibatkan
mengikuti Tunggu sama – urutan Sinyal.
Jika Anda berhati-hati, Anda akan melihat bahwa nilai counter adalah 1
atau 0, dan tidak pernah memiliki nilai lain. Oleh karena itu, disebut
sebagai semaphore biner. Jika kita mengganti counter dengan variabel
Boolean dan menafsirkan 1 dan 0 sebagai benar (yaitu, kunci terbuka) dan
false (yaitu, kunci tertutup), masing-masing, maka semaphore biner
menjadi kunci mutex! Karena itu, Anda dapat menggunakan kunci mutex atau
semaphore biner bergantian.
Namun, keindahan menggunakan semaphores adalah bahwa nilai awal tidak
harus 1. Bisa jadi ada nilai non-negatif. Kemudian kita akan membahas
teknik-teknik lain semaphores menggunakan.
Kemajuan besar pertama dalam menangani masalah proses konkuren datang
pada tahun 1965 dengan risalah Dijkstra [DIJK65]. Dijkstra prihatin
dengan desain dari OS sebagai kumpulan proses sekuensial dan bekerja
sama dengan pembangunan mekanisme yang efisien dan dapat diandalkan
untuk mendukung kerja sama. Mekanisme ini hanya bias mudah digunakan
oleh proses pengguna jika prosesor dan OS membuat mekanisme yang
tersedia.
[DOWN07] menunjukkan tiga konsekuensi menarik dari definisi semaphore:
• Secara umum, tidak ada cara untuk mengetahui sebelum proses decrement semaphore sebuah akan terblokir atau tidak.
• Setelah proses increment semaphore dan proses lain akan berjalan,
kedua proses terus berjalan bersamaan. Tidak ada cara untuk mengetahui
proses, jika salah satu, akan segera melanjutkan pada sistem prosesor
tunggal.
• Saat sinyal Anda semaphore, Anda tidak perlu tahu apakah proses
yang lain sedang menunggu, sehingga jumlah proses yang diblokir mungkin
nol atau satu.
Konsep Dasar Monitor
Monitor termasuk kumpulan prosedur, variabel dan struktur data di
satu modul atau paket khusus. Proses dapat memanggil prosedur-prosedur
kapan pun diinginkan. Tapi proses tak dapat mengakses struktur data
internal dalam monitor secara langsung. Hanya lewat prosedur-prosedur
yang dideklarasikan minitor untuk mengakses struktur internal.
Java menggunakan monitor ke benang koordinasi untuk memastikan mereka
tidak tersandung saling mengakses data yang sama. Dengan monitor, Anda
mengunci obyek, bagian-bagian penting dari kode atau Anda mengunci
seluruh metode dengan menyatakan mereka disinkronisasi. Monitor memiliki
dukungan hardware test dan mengatur di belakang mereka untuk memastikan
cek thread untuk melihat apakah monitor sudah dikunci dan jika tidak,
menyita mengunci semua dalam satu operasi atom non-interruptible. Tanpa
atomicity, thread mungkin periksa apakah monitor tidak terkunci, dan
memiliki beberapa thread lain ambil monitor sebelum mendapat kesempatan
untuk menguncinya. Puritan akan menunjukkan bahwa monitor sebenarnya
bukan kunci, melainkan kunci adalah cara yang digunakan untuk melindungi
bagian penting dari kode.
Monitor Sebuah bahasa pemrograman membangun yang merangkum variabel,
prosedur akses dan inisialisasi kode dalam suatu variabel tipe data
abstrak. Monitor hanya dapat diakses melalui prosedur akses dan hanya
satu proses yang dapat secara aktif mengakses monitor dalam satu waktu.
Prosedur-prosedur pengaksesan adalah bagian penting. Dimana monitor
mungkin memiliki antrian proses-proses yang sedang menunggu untuk
mengaksesnya.
Anda mungkin mendapatkan pengalaman dari belajar semua contoh
semaphore bahwa sinyal dan menunggu panggilan masih dapat tersebar di
mana-mana dalam program anda dengan cara yang tidak terlalu terstruktur
dengan baik. Jika Anda benar-benar mendapatkan seperti perasaan, konsep
monitor datang untuk menyelamatkan. Konsep monitor berasal dari 1974
kertas CAR Hoare’s.
Sebuah monitor memiliki empat komponen seperti yang ditunjukkan di
bawah ini: inisialisasi, data pribadi, prosedur memonitor, dan antrian
masuk monitor. Komponen inisialisasi berisi kode yang digunakan tepat
satu kali ketika monitor dibuat, Bagian data pribadi berisi semua data
pribadi, termasuk prosedur swasta, yang hanya dapat digunakan dalam
monitor. Dengan demikian, barang-barang pribadi tidak terlihat dari luar
monitor. Prosedur monitor prosedur yang dapat dipanggil dari luar
monitor. Antrian entri memantau berisi semua thread yang disebut
prosedur monitor tapi belum diberikan izin. Kita akan kembali ke ini
segera.
Oleh karena itu, monitor terlihat seperti kelas dengan inisialisasi,
data pribadi dan prosedur monitor sesuai dengan konstruktor, data
pribadi dan metode kelas tersebut. Satu-satunya perbedaan utama adalah
bahwa kelas tidak memiliki antrian masuk.
Monitor yang seharusnya digunakan dalam lingkungan multithreaded atau
multiproses di mana beberapa thread / proses dapat menghubungi prosedur
monitor pada saat yang sama meminta layanan. Dengan demikian, monitor
menjamin bahwa setiap saat paling banyak satu thread bisa mengeksekusi
dalam monitor! Apa artinya ini? Ketika thread panggilan prosedur
monitor, kita dapat melihat prosedur monitor disebut sebagai
perpanjangan ke thread panggilan. Jika prosedur monitor disebut dalam
eksekusi, kita akan mengatakan thread memanggil di monitor melaksanakan
prosedur monitor disebut.
Sekarang, jika dua thread di monitor (yaitu, mereka adalah
melaksanakan dua, mungkin, monitor prosedur yang sama), beberapa data
pribadi dapat dimodifikasi oleh kedua benang pada saat yang sama
menyebabkan kondisi ras terjadi. Oleh karena itu, untuk menjamin
keutuhan data pribadi, monitor saling memberlakukan pengecualian
implisit. Lebih tepatnya, jika thread panggilan prosedur monitor, thread
ini akan diblokir jika ada thread lain eksekusi pada monitor. Mereka
benang yang tidak diberikan izin masuk akan antri masuk ke antrian
monitor luar monitor. Ketika monitor menjadi kosong (yaitu, tidak ada
thread mengeksekusi di dalamnya), salah satu benang dalam antrian entri
akan dirilis dan diberikan izin untuk menjalankan prosedur monitor
disebut. Meskipun kita mengatakan “antrian masuk,” Anda tidak harus
melihat secara harfiah. Lebih tepatnya, ketika thread harus dilepaskan
dari antrian masuk, Anda tidak perlu menganggap kebijakan apapun yang
thread yang akan dirilis.
Secara ringkas, monitor memastikan saling eksklusi otomatis sehingga
tidak ada lebih dari satu thread bisa mengeksekusi dalam memonitor
setiap saat. Ini adalah kemampuan yang sangat usably dan berguna.
Monitor sebagai Mini-OS
Konsep monitor sangat mirip dengan sebuah sistem operasi. Satu dapat
mempertimbangkan inisialisasi sebagaimana data yang diinisialisasi
ketika sistem boot up, data pribadi dan kode sebagai struktur data
internal dan fungsi dari sebuah sistem operasi, dan prosedur monitor
sebagai panggilan sistem. Program-program, tentu saja, benang yang
membuat permintaan layanan. Oleh karena itu, monitor bisa dianggap
sebagai mini-OS dengan layanan terbatas.
2. Persamaan dan perbedaannya:
Sejak menunggu operasi sinyal pada semaphores dan pada monitor
kondisi variabel yang sama, untuk membantu Anda membedakan perbedaan
mereka dan menggunakannya dengan benar, berikut ini adalah perbandingan
singkat.Semaphore Monitor – Kondisi Variabel
Dapat digunakan di mana saja dalam program, tetapi seharusnya tidak
digunakan dalam monitor Hanya dapat digunakan pada monitor
Wait() tidak selalu memblokir pemanggil (yaitu, ketika counter
semaphore lebih besar dari nol). Wait() selalu blok
pemanggil.
Signal() baik melepaskan thread yang diblokir, jika ada satu, atau
meningkatkan semaphore counter. Signal() baik melepaskan thread yang
diblokir, jika ada satu, atau sinyal hilang seolah-olah itu tidak
pernah terjadi.
Jika Signal () melepaskan thread yang diblokir, pemanggil dan thread
dirilis & keduanya melanjutkan. Jika Signal () melepaskan thread
yang diblokir, pemanggil hasil monitor (tipe Hoare) atau terus (Mesa
Type). Hanya satu dari pemanggil atau threadyang dirilis dapat
melanjutkan, tapi tidak keduanya.
Perbedaan:
operasi semaphore tersebar pada seluruh section program
pada monitor, sinkronosasi dikendalikan oleh prosedur tertentu, dimana shared data hanya bisa diakses melalui prosedur tersebut
dalam penggunaan semaphore mungkin timbul kesalahan yang sulit terdeteksi (misal: deadlock), yang dicegah oleh monitor
Di samping itu, sinyal operasi menunggu kondisi variabel monitor
mirip dengan P dan operasi V pada perhitungan semaphores. Sebuah
pernyataan tunggu dapat memblokir proses itu eksekusi, sedangkan
pernyataan sinyal dapat menyebabkan proses lain menjadi diblokir. Namun,
ada beberapa perbedaan di antara mereka. Ketika sebuah proses
mengeksekusi operasi P, tidak selalu menghalangi proses tersebut karena
semaphore penghitungan mungkin lebih besar dari nol. Sebaliknya, ketika
sebuah pernyataan menunggu dieksekusi, selalu blok proses. Saat tugas
yang mengeksekusi operasi V pada semaphore, itu baik unblocks suatu
tugas menunggu yang semaphore atau increment yang semaphore counter jika
tidak ada tugas untuk membuka. Di sisi lain, jika suatu proses
mengeksekusi pernyataan sinyal ketika tidak ada proses lain untuk
membuka blokir, tidak ada efek pada variabel kondisi.
Perbedaan lain antara semaphores dan monitor adalah bahwa pengguna
terbangun oleh operasi V dapat melanjutkan eksekusi tanpa penundaan.
Sebaliknya, pengguna terbangun oleh operasi sinyal restart hanya ketika
monitor terkunci.
Selain itu, solusi monitor terstruktur lebih banyak dari yang satu
dengan semaphores karena data dan prosedur yang dikemas dalam satu modul
tunggal dan bahwa pengecualian saling disediakan secara otomatis oleh
pelaksanaannya.
3. Pengertian Deadlock dan Starvation beserta contohnya:
a) Deadlock
Deadlock secara bahasa berarti buntu atau kebuntuan. Dalam definisi
lebih lengkap, deadlock berarti suatu keadaan dimana sistem seperti
terhenti dikarenakan setiap proses memiliki sumber daya yang tidak bisa
dibagi dan menunggu untuk mendapatkan sumber daya yang sedang dimiliki
oleh proses lain. Keadaan seperti ini hanya dapat terjadi pada akses
terhadap sumber daya yang tidak bisa dibagi atau non-sharable.
Contoh:
kasus ilustrasi dari kejadian deadlock pada dunia nyata, yaitu pada
lalu lintas dijembatan. Dapat dilihat bahwa kedua mobil yang berada di
tengah-tengah jembatan tidak dapat maju dan hanya
menunggu. Penyelesaian dari masalah tersebut adalah salah satu dari
mobil tersebut mundur, sehingga mobil yang lain dapat maju. Mobil pada
kasus ini adalah proses, sedangkan jembatan adalah sumber daya. Kedua
mobil berebut untuk menggunakan sumber daya, namun karena sumber daya
tersebut hanya dapat digunakan oleh satu proses saja, maka terjadilah
deadlock.
Ilustrasinya:
ü Dua Proses, P1 dan P2
ü Dua Resource kritis R1 dan R2
ü Proses P1 dan P2 harus mengakses kedua sumber daya.
Kondisi berikut dapat terjadi : R1 diberikan ke P1, sedang R2 di berikan ke P2.
Karena untuk melanjutkan ekssekusi memerlukan sumber daya sekaligus
maka kedua proses akan saling menunggu sumber daya yang lainnya,
selamanya. Tidak ada proses yang dapat melepaskan sumber daya yang telah
dipegangnya karena menunnggu sumber daya lain yang tidak pernah
diperolehnya. Keduanya tidak membuat proses kemajuan apapaun, kedua
proses tersebut dalam kondisi deadlock.
Kondisi deadlock merupakan kondisi terparah karena banyak proses
dapat terlibat dan semua yang terlibat tidak dapat mengakhiri prosesnya
secara benar. Beragam mekanisme diusulkan untuk mengatasi kondisi
deadlock.
b) Starvation
Ilustrasinya :
ü Terdapat tiga proses P1, P1, dan P3
ü P1, P2, dan P3 memerlukan pengaksesan sumber daya R secara periodik
Terjadi Skenario berikut:
ü P1 sedang di beri sumber daya R, P2, dan P3 Blocked menunggu sumber daya R.
ü Ketika P1 keluar daricritical section, P2 dan P3 diijinkan mengakse 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. meskipun
tidak ada deadlock, pada sutuasi ini P2 mengalami starvation.
Untuk pemahaman lebih jelas, berikut detail dari penjelasannya:
Deadlock adalah situasi di mana dua atau lebih proses yang tidak
dapat dilanjutkan karena masing-masing sedang menunggu satu yang lain
untuk melakukan sesuatu.
Deadlock mengacu situasi di mana satu set dari dua atau lebih proses
yang menunggu untuk anggota lain dimana diset untuk menyelesaikan
operasi untuk memprosesnya, tapi tidak ada anggota yang mampu memproses.
Deadlock adalah fenomena yang sulit untuk mengantisipasi, dan tidak ada
solusi umum yang mudah untuk mengatasi masalah ini. Ada tiga pendekatan
utama untuk berurusan dengan deadlock: pencegahan, penghindaran, dan
deteksi.
Dalam Hal ini, dimungkinkan untuk dua atau lebih program yang akan
menutup telepon menunggu satu sama lain. Sebagai contoh, dua program
mungkin masing-masing memerlukan dua perangkat I / O untuk melakukan
beberapa operasi (misalnya, disk untuk menyalin tape). Salah satu
program telah
merebut kendali dari salah satu perangkat dan program lain yang
memiliki kontrol dari perangkat lain. Setiap menunggu program lain untuk
melepaskan sumber daya yang diinginkan. Deadlock tersebut mungkin
tergantung pada waktu kesempatan alokasi sumber daya dan pelepasannya.
Prinsip-Prinsip Deadlock
Deadlock dapat didefinisikan sebagai memblokir permanen dari
serangkaian proses yang baik bersaing untuk sumber daya sistem atau
berkomunikasi satu sama lain. Satu set proses adalah jalan buntu ketika
setiap proses dalam set diblokir menunggu suatu peristiwa (biasanya
membebaskan beberapa sumber daya yang diminta) yang hanya dapat dipicu
oleh lain diblokir proses dalam set. Deadlock adalah permanen karena
tidak ada peristiwa yang pernah dipicu. Tidak seperti masalah lain dalam
proses manajemen bersamaan, ada ada solusi efisien dalam kasus umum.
Semua kebuntuan melibatkan konflik akan kebutuhan sumber daya oleh
dua atau lebih proses. Sebuah contoh umum adalah kebuntuan lalu lintas.
Gambar 6.1a menunjukkan situasi di mana empat mobil telah tiba di sebuah
simpang empat arah berhenti di kurang lebih sama waktu. Keempat kuadran
dari persimpangan adalah sumber daya di mana kendali dibutuhkan. Secara
khusus, jika semua empat mobil ingin pergi langsung melalui
persimpangan itu, kebutuhan sumber daya adalah sebagai berikut:
• Mobil 1, bepergian ke utara, membutuhkan kuadran a dan b.
• Mobil 2, membutuhkan kuadran b dan c.
• Mobil 3, membutuhkan kuadran c dan d.
• Mobil 4, membutuhkan kuadran d dan a.
Aturan khas jalan di Amerika Serikat adalah bahwa mobil di halte
empat arah harus menunda untuk mobil segera haknya. Aturan ini bekerja
jika hanya ada dua atau tiga mobil di persimpangan. Misalnya, jika hanya
utara dan arah barat mobil tiba di persimpangan, mobil utara akan
menunggu dan mobil ke arah barat diterima. Namun, jika semua empat mobil
tiba pada waktu yang sama, masing-masing akan menahan diri dari
memasuki persimpangan, ini menyebabkan kebuntuan potensial. Kebuntuan
ini hanya potensial, tidak aktual, karena sumber daya yang diperlukan
tersedia untuk salah satu mobil untuk melanjutkan. Jika salah satu mobil
akhirnya melanjutkan, maka yang lain juga dapat melanjutkannya.
Namun, jika semua empat mobil mengabaikan aturan dan lanjutkan
(hati-hati) ke perempatan pada saat yang sama, maka setiap mobil merebut
satu sumber daya (satu kuadran) tetapi tidak dapat dilanjutkan karena
kedua sumber daya yang diperlukan telah disita oleh mobil lain. Ini
merupakan kebuntuan yang sebenarnya.
Mari kita lihat gambaran dari kebuntuan yang melibatkan proses-proses dan komputer
sumber daya. Gambar 6.2 (berdasarkan satu di [BACO03]), yang kami
sebut sebagai diagram kemajuan bersama, menggambarkan kemajuan dua
proses yang bersaing untuk dua sumber. Setiap proses membutuhkan
penggunaan eksklusif dari kedua sumber daya untuk sebuah tertentu jangka
waktu tertentu. Dua proses, P dan Q, mempunyai bentuk umum berikut:
Process P Process Q
• • • • • •
Get A Get B
• • • • • •
Get B Get A
• • • • • •
Release A Release B
• • • • • •
Release B Release A
• • • • • •
Sebagai contoh sederhana, Deadlock terjadi jika dua proses memerlukan
dua sumber daya yang sama untuk melanjutkan dan masing-masing memiliki
satu kepemilikan. Kecuali beberapa tindakan yang diambil, setiap proses
akan menunggu tanpa batas waktu untuk sumber daya yang hilang tersebut.
Starvation adalah situasi di mana proses runnable yang terlupakan
tanpa batas oleh penjadwal; meskipun mampu melanjutkan, tetapi tidak
pernah dipilih.
Starvation mengacu pada situasi di mana suatu proses siap untuk
mengeksekusi tetapi terus ditolak akses ke prosesor untuk mendahulukan
proses lainnya. Dalam sebagian besar, starvation ditangani sebagai isu
penjadwalan.
Contoh, perhatikan dua proses, P1 dan P2, dan dua sumber daya, R1 dan
R2. Misalkan bahwa setiap proses membutuhkan akses ke kedua sumber daya
untuk melakukan sebagian fungsinya. Maka mungkin untuk memiliki situasi
berikut ini:
OS menugaskan R1 untuk P2, dan R2 untuk P1. Setiap proses sedang
menunggu salah satu dari dua sumber daya. Tidak akan melepaskan sumber
daya yang sudah memiliki sampai telah mengakuisisi sumber daya lainnya
dan melakukan fungsi yang membutuhkan baik sumber daya. Kedua proses ini
menemui deadlock (jalan buntu).
Sebuah masalah pengendalian akhir ini adalah starvation. Misalkan
tiga proses (P1, P2, P3) masing-masing membutuhkan akses berkala kepada
sumber daya R. Pertimbangkan situasi di mana P1 adalah memiliki sumber
daya, dan kedua P2 dan P3 yang tertunda, menunggu sumber daya itu.
Ketika keluar dari critical section P1, baik P2 atau P3 harus diberi
akses ke R. Asumsikan bahwa OS memberikan akses ke P3 dan bahwa P1 lagi
membutuhkan akses sebelum P3 menyelesaikan critical section-nya. Jika OS
memberikan akses ke P3 P1 setelah selesai, dan kemudian bergantian
memberikan akses ke P1 dan P3, maka P2 dapat tanpa batas waktu menolak
akses ke sumber daya, meskipun tidak ada situasi deadlock.
sumber : http://blog.ub.ac.id/zarkazi/2011/03/26/semaphore-dan-monitor-algoritmanya-deker-peterson-dijkstra/
