Merupakan kondisi dimana terdapat sumber
daya yang tidak dapat dipakai bersama pada waktu yang bersamaan (misalnya :
printer, disk drive). Kondisi demikian disebut sumber daya kritis, dan bagian
program yang menggunakan sumber daya kritis disebut critical region / section.
Hanya satu program pada satu saat yang diijinkan masuk ke critical region.
Pemrogram tidak dapat bergantung pada sistem operasi untuk memahami dan
memaksakan batasan ini, karena maksud program tidak dapat diketahui oleh sistem
operasi. Hanya saja, system operasi menyediakan layanan (system call)
yang bertujuan untuk mencegah proses lain masuk ke critical
section yang sedang digunakan proses tertentu. Pemrograman harus
menspesifikasikan bagian-bagian critical section, sehingga sistem
operasi akan menjaganya. Pentingnya mutual exclusion adalah jaminan hanya satu
proses yang mengakses sumber daya pada suatu interval waktu.
Pemaksaan atau pelanggaran mutual exclusion menimbulkan
:
1. Deadlock
2. Starvation
Critical Section
Segmen kode yang mengakses data yang digunakan
secara bersama-sama itu disebut critical section. Bagaimana menghindari race
conditions? Kunci untuk mencegah masalah ini da situasi yang lain yang
melibatkan shared memory, shared file, and shared sumber daya yang lain dalah
menemukan beberapa jalan untuk mencegah lebih dari satu proses untuk melakukan
proses writing dan reading kepada shared data pada saat yang sama. Dengan kata
lain kita membutuhkan mutual exclusion, sebuah jalan yang menjamin jika sebuah
proses sedang menggunakan shared files, proses lain dikeluarkan dari pekerjaan
yang sama. Kesulitan yang terjadi karena proses 2 menggunakan shared variabel
sebelum proses 1 menyelesaikan tugasnya.
Walaupun dapat mencegah race conditions, tapi tidak cukup
untuk melakukan kerjasama antar proses secara paralel dengan baik dan efisien
dalam menggunakan shared data. Kita butuh 4 kondisi untuk menghasilkan solusi
yang baik :
· Tidak
ada dua proses secara bersamaan masuk kedalam critical section.
· Tidak
ada asumsi mengenai kecepatan atau jumlah cpu.
· Tidak
ada proses yang berjalan diluar critical section yang dapat mengeblok proses
lain.
· Tidak
ada proses yang menunggu selamanya untuk masuk critical section.
Tiga kondisi untuk
menentukan mutual exclusion :
· Tidak
ada dua proses yang pada saat bersamaan berada di critical section.
· Tidak
ada proses yang berjalan diluar critical region yang bisa menghambat proses
lain.
· Tidak
ada proses yang tidak bisa masuk ke critical region.
Solusi
masalah critical section
1. Ide
:
ü Mencakup
pemakaian secara “exclusive” dari shared variable tersebut
ü Menjamin
proses lain dapat menggunakan shared variable tersebut
1. Solusi
“critical section problem” harus memenuhi:
Ø Mutual
Exclusion: Jika proses Pi sedang “eksekusi” pada bagian “critical
section” (dari proses Pi) maka tidak ada proses proses lain dapat “eksekusi”
pada bagian critical section dari proses-proses tersebut.
Ø Progress: Jika
tidak ada proses sedang eksekusi pada critical section-nya dan jika terdapat
lebih dari satu proses lain yang ingin masuk ke critical section, maka
pemilihan siapa yang berhak masuk ke critical section tidak dapat ditunda tanpa
terbatas.
1. Bounded
Waiting: Terdapat batasan berapa lama suatu proses harus menunggu
giliran untuk mengakses “critical section” – jika seandainya proses lain yang
diberikan hak akses ke critical section.
ü Menjamin
proses dapat mengakses ke “critical section” (tidak mengalami starvation:
proses se-olah berhenti menunggu request akses ke critical section
diperbolehkan).
ü Tidak
ada asumsi mengenai kecepatan eksekusi proses proses n tersebut.
1.2 Mencegah Mutual Exclusion
Mutual exclusion benar-benar tak
dapat dihindari. Hal ini dikarenakan tidak ada sumber daya yang dapat
digunakan bersama-sama, jadi sistem harus membawa sumber daya yang tidak
dapat digunakan bersama-sama.
Di Tulis Oleh : Anan Widiyanto - 12300046
1.3 Metode Penyelesaian Masalah Mutual Exclusion.
Ada
beberapa metode penyelesaian masalah mutual exclusion, antara lain :
1. a.
Sinkronisasi.
Algoritma 1
Pada bagian ini akan dibatasi pada
aplikasi ke 2 proses yaitu Pi dan Pj , atau P0dan P1secara umum, jika ada proses Pimaka akan
digunakan proses Pj sebagai proses lainnya, dengan j=1-i. Ada beberapa
algoritma penyelesaian mutual exclusion dengan menggunakan sinkronisasi,
yakni kedua proses akan berbagi suatu variabel
bertipe integer yaitu turn yang diinisialisaikan dengan 0 (atau 1). Jika
turn=0, maka proses P0 diijinkan untuk mengeksekusi critical section.
Struktur P0 terlihat pada gambar dibawah ini :
repeat
while turn ≠0 do
critical section
turn := 1
remainder section
until false
Solusi ini sudah menunjukkan
adanya mutual exclusion, karena pada suatu saat hanya ada satu proses yang
masuk critical section. Namun belum menunjukkan adanya progress
dan bounded waiting. Sebagai contoh:
Jika P0 meninggalkan critical
section, maka nilai turn=1 yang berarti bahwa P1 siap untuk masuk
kecritical section;
Ø P1 selesai
menggunakan critical section dengan cepat maka baik P1 maupun
P0 beradapadaremainder section dengan nilai turn=0.
Ø P0 kembali
menggunakan critical section dengan cepat dan segera masuk
ke remainder sectiondengan nilai turn=1.
Ø P0 hendak kembali
menggunakan critical section namun nilai turn=1.Terlihat bahwa P1
yang berada pada remainder section memblok P0 sehingga tidak dapat
memasuki critical section. Hal ini menentang progress, yaitu proses diblok
oleh proses yang tidak berada di critical section.
Algoritma 2
Masalah pada algoritma-1 tidak memberika
cukup informasi mengenai status proses. Hanya mempertimbangkan yang masuk
critical section. Untuk mengatasi masalah ini variabel “turn” diganti dengan :
var flag : array [0 ..1] of boolean;
Semua elemen array diinisialisasikan
dengan false. Jika flag[0] bernilai true, maka nilai itu akan mengindikasikan
bahwa P0 siap memasuki critical section. Struktur P0 terlihat pada gambar
dibawah ini.
repeat
flag[0]:=true;
while flag[1] do
critical section
flag[0]
remainder section
until false
Pada algoritma ini, proses P0 pertama
kali menetapkan flag[i] = true, nilai ini mengindikasikan bahwa P0 siap memasuki
critical section. Kemudian P0 mengecek untuk menyakinkan P1 tidak akan memasuki
tidak kan memasuki critical section. Jika P1 juga telah memasuki critical
section, maka P0 harus menunggu sampai P1 tidak membutuhkan critical section
lagi (sampai flag[1] =false). Secepatnya P0 memasuki critical section. Pada
exit section, P0 akan mengeset flag[0] menjadi false, hal ini mengijinkan
proses la in (jika sedang menunggu) untuk memasuki critical section.Pada solusi
ini, kondisi mutual exclusion telah dipenuhi. Namun progress belum juga
dipenuhi. Untuk menggambarkan hal tersebut dapat dilihat :
T0
P0 menetapkan flag[0] = true;
T1
P1 menetapkan flag[1] = true;
Sekarang P0 dan P1 bersama-sama ada di
statement while.
Algoritma –3 (Peterson)
Algoritma ketiga ini diperkenalkan oleh
peterson. Pada dasarnya, algoritma ini merupakan kombinasi antara algoritma –1
dan algoritma-2. Proses ini membutuhkan 2 variabel, yaitu :
Var Flag :array [0 .. 1] of
boolean;
Turn : 0 .. 1;
Nilai awal flag[0] = flag = false, dan
nilai turn (0 atau 1). Struktur proses P1 seperti terlihat pada gambar dibawah
ini :
repeat
flag[0]:=true;
turn:=1;
while (flag[1] and turn=1) do
critical section
flag[0]
remainder section
until false
Untuk masuk ke critical section, proses
P0 mengeset flag[0] = true, dan melihat apakah ada proses lain yang mencoba
masuk critical section (turn=1).
Algoritma Bakery
Critical section untuk n proses:
Sebelum masuk ke critical section.
Proses mendapatkan nomor. Yang memiliki nomor paling kecil lebih dahulu
memasuki critical section. Jika proses Pi dan Pj menerima nomor, jika i<j,
maka Pi lebih dahulu masuk \critical section, sebaliknya Pj yang lebih
dahulu masuk critical section. skema penomoran selalu membangkitkan angka yang
meningkat, seperti 1,2,3,4,5,6, …
shared data
var choosing : array[0..n-1] of boolean;
number : array[0..n-1] of integer;
Struktur data diinisialisaikan dengan
false dengan nilai 0. Struktur proses P1 seperti terlihat pada gambar dibawah
ini :
repeat
choosing[i]:=true;
number[i]:=max(number[0], number[1], …,
number[n-1])+1;
choosing[i]:=false;
for j:= 0 to n-1
do begin
while choosing[j] do no_op;
while number[j] ? 0
and (number[j],j) < (number[i],i) do
no_op;
end;
critical section
number[i]:=0;
remainder section
until false
Algoritma Dekker
Algoritma ini diperkenalkan oleh Dekker,
seorang matematikawan dari Belanda. Algoritma ini memiliki ciri-ciri khusus
sebagai berikut:
Tidak memerlukan instruksi-instruksi
perangkat keras khusus.
Proses yang beroperasi di remainder
section tidak dapat mencegah proses lain yang ingin masuk critical section.
Proses yang ingin masuk critical section
akan segera memasuki kawasan tersebut jika dimungkinkan.
bool Fail = false;
int share = 6;
int x = 0;
int y = 0;
bool z = true;
chan q_0_1 = [0] of {bit};
chan q_0_2 = [0] of {bit};
proctype A() {
bool dapat_dishare = true;
do
::atomic{
z ->
x = 10;
};
::atomic{
dapat_dishare ->
q_0_1?0;
share = share+1;
dapat_dishare = false;
q_0_1?1;
};
::atomic{
!dapat_dishare ->
q_0_2?0;
dapat_dishare = true;
q_0_2?1;
};
od;
}
proctype B() {
bool dapat_dishare = false;
do
::atomic{
z ->
y = 11;
};
::atomic{
dapat_dishare ->
q_0_2!0;
share = share-1;
dapat_dishare = false;
q_0_2!1;
};
::atomic{
!dapat_dishare ->
q_0_1!0;
dapat_dishare = true;
q_0_1!1;
};
od;
}
init {
atomic{
run A();
run B();
};
}
1. b.
Semaphore
Model semaphore secara umum untuk
penyelesaian mutual exclusion adalah sebagai berikut :
mtype = { idle, masuk, critical, keluar
};
#define state mtype
bool Fail = false;
bool semaphore = false;
proctype USER_0() {
state user_state = idle;
do
::atomic{
user_state==idle ->
if
::user_state = idle;
::user_state = masuk;
fi;
};
::atomic{
((user_state==masuk)&&(!semaphore))
->
user_state = critical;
semaphore = true;
};
::atomic{
((user_state==masuk)&&(semaphore))
->
user_state = masuk;
};
::atomic{
user_state==critical ->
if
::user_state = critical;
::user_state = keluar;
fi;
};
::atomic{
user_state==keluar ->
user_state = idle;
semaphore = false;
};
od;
}
proctype USER_1() {
state user_state = idle;
do
::atomic{
user_state==idle ->
if
::user_state = idle;
::user_state = masuk;
fi;
};
::atomic{
((user_state==masuk)&&(!semaphore))
->
user_state = critical;
semaphore = true;
};
::atomic{
((user_state==masuk)&&(semaphore))
->
user_state = masuk;
};
::atomic{
user_state==critical ->
if
::user_state = critical;
::user_state = keluar;
fi;
};
::atomic{
user_state==keluar ->
user_state = idle;
semaphore = false;
};
od;
}
init {
atomic{
run USER_0();
run USER_1();
};
}
Di Tulis Oleh : Wahyulianto E. S - 12300037
SUMBER :
1.
Hariyanto, Bambang. Sistem Operasi. Edisi 2. Bandung. Informatika. 1999.
2.
Kusumadewi, Sri. Sistem Operasi. Yogyakarta, J & J Learning, 2000
3.
Tenembaum, Andrew S., “Modern Operating System”, Englewood Cliffs, New Jersey :
Prentice-Hall Inc., 1992.
4.
stalling, William, “Operating System”, 2nd Englewood Cliffs, New Jersey :
Prentice-Hall
Inc., 1995.
( 23-04-2013 )
2.1 DEADLOCK
Deadlock adalah proses
menunggu suatu kejadian tertentu yang tak akan pernah terjadi.
Contoh :
Misalkan terdapat dua buah proses , yaitu P1 dan P2 dan dua buah sumber daya
kritis Yaitu R1 dan R2 . Proses P1 dan P2 harus mengakses kedua
sumber daya tersebut dengan kondisi ini maka akan terjadi R1
akan diberikan kepada P1, dan R2 akan di berikan kepada P2 , karena
didalam melakukan eksekusi kita memerlukan kedua sumber daya tersebut sekaligus
maka kedua proses akan saling menunggu sumber daya lain selamanya,
proses tidak melepaskan sumber daya yang telah dipegangnya karena menunggu
sumber daya lain yang tak pernah diperolehnya. Maka kedua proses dalam kondisi
Deadlock yang tidak dapat membuat kemajuan apapun, dan Deadlock merupakan
kondisi terparah karena dapat melibatkan banyak proses dan semuanya tidak
mengakhiri proses secara benar.
Urutan kejadian pengoperasian
perangkat input/output adalah Sbb:
- Meminta (request) :meminta pelayanan perangkat input/output
- Memakai (user) :memakai perangkat input/output
- Melepaskan (release) :melepaskan pemakaian perangkat input/output
1.Model Deadlock
Model
deadlock dua proses dan dua sumber daya
Misalnya :
a. Dua buah proses
P1 dan P2
b Dua buah sumber
daya R1 dan R2
Dari gambar diatas dapat kita lihat
bahwa P0 meminta sumber daya pada R0, sedangkan
P1 meminta sumber daya pada R1 , kemudian
P0 sambil menggenggam sumber daya R0 meminta
sumber daya R1 sedangkan P1 sambil mengenggam
sumber dayaR1 juga meminta sumber daya pada R0
kejadian inilah yang mengakibatkan Deadlock seperti kita lihat pada gambar
dibawah ini graph deadlock ini digambarkan sebagai graph
melingkar dan terjadinya deadlock ini juga ditandai dengan muncul
nya graph melingkar:
Deadlock dapat juga terjadi dengan
melibatkan lebih dari dua proses dan dua sumber daya.
Syarat-Syarat
terjadinya Deadlock
Coffman.et al. Menyatakan ada
4 syarat terjadinya deadlock
1. Mutual
exclusion
2. Kondisi
genggam dan tunggu
3. Kondisi
non preemption
4. Kondisi
menunggu secara sirkular
Mutual
Exclusion : Tiap sumber daya pada saat itu
diberikan tepat pada satu proses.
Kondisi genggam & tunggu : Proses-proses yang sedang
menggenggam sumber daya menunggu sumber
data yang baru
Kondisi non preemption
: Sumber daya-sumber daya yang sebelumnya diberikan tidak dapat
diambil
paksa dari proses itu, sumber daya harus secara explisit dilepaskan dari
proses yang menggenggamnya.
Kondisi menunggu secara sirkular: harus terdapat
rantai sirkular dari dua proses atau lebih masing-
masing menunggu sumber daya yang digenggam oleh anggota berikutnya
pada rantai tersebut.
Ketiga syarat tersebut sangat
diperlukan bagi terjadinya deadlock,tetapi ketiga kondisi itu belum berarti
terjadinya deadlock, deadlock baru benar-benar terjadi jika dipenuhi syarat
yang keempat,karena syarat keempat ini merupakan keharusan bagi
terjadinya peristiwa deadlock. Bila salah satu kondisi ini saja tidak terpenuhi
maka deadlock tidak terjadi.
2. Metode Mengatasi Deadlock
Tiga metode dalam mengatasi
Deadlock:
a.Metode pencegahan
terjadinya Deadlock (Deadlock Preventation)
Metode ini banyak dipakai, dan
metode ini berhubungan dengan pengkondisian sistem agar menghilangkan kemungkinan
terjadinya deadlock, pencegahan adalah sulusi yang terbaik dipandang dari
sudut tercegahnya deadlock. Dan metode ini sering menghasilkanutilisasi
sumber daya yangburuk.
b.Metode penghindaran
terjadinya Deadlock (Deadlock Avoidence)
Tujuan dari metoda ini adalah
untuk menghindari terjadinya kondisi-kondisi yang memungkinkan terjadinya deadlock, dan
memperoleh utilisasi sumber daya yg baik.
Penghindaran bukan berarti
menghilangkan semua kemungkinan terjadinya deadlock, Secara teoritis deadlock
dimungkinkan.
Sistem operasi memeriksa semua
permintaan sumber daya secara hati-hati, jika sistem operasi mengetahui bahwa
alokasi sumber daya menimbulkan resiko deadlock, maka sistem akan menolak pengaksesan dan
dengan demikian menghindari terjadinya deadlock
c. Metode deteksi dan pemulihan
Deadlock (Deadlock detection and recovery)
Metode deteksi
ini digunakan pada sistem yang mengizinkan terjadinya deadlock, Tujuan dari metode ini
adalah untuk memeriksa apakah telah terjadi deadlock dan menentukan proses serta
sumber daya yang terlibat dalam deadlock secara presisi setelah ditemukan sistem dipulihkan
dari deadlock dengan metode pemulihan. (metode pemulihan dari deadlock adalah
untuk menghilangkan deadlock sistem sehingga dapat beroperasi kembali) Proses yang
terlibat dalam deadlock mungkin akan dapat menyelesaikan eksekusi dan membebaskan sumber
daya dari sumber dayanya.
3.Strategi burung onta
Strategi ini
diasumsikan bahwa deadlock jarang terjadi jika dibandingkan dengan kejadian
komputer crash. Jadi mengapa kita harus bersusah payah mengatasi deadlock
sedangkan sistem lebih sering rusak karena crash, disebut dengan strategi
burung onta karena burung onta akan menyembunyikan kepalanya ketanah apabila
akan terjadi bahaya yang mengancam dirinya. Jadi sebenarnya strategi ini
adalah sama sekali tidak berusaha mengatasi deadlock .
4.Pencegahan Deadlock.
Havendar mengemukakan bahwa jika keempat syarat tersebut
diatas tidak dipenuhi maka tidak akan terjadi deadlock, sehingga Havendar
menyarankan strategi – strategi untuk meniadakan dengan syarat :
A.Setiap proses harus meminta semua
sumber yang diperlukan sekaligus dan tidak berlanjut
sampai semua
diberikan.
B Jika proses telah/sedang
memegang sumber daya tertentu , untuk permintaan berikutnya
Proses harus melepas
sumber daya yang dipegangnya , jika diperlukan proses harus me-
Minta kembali sekaligus
dengan sumber daya yang baru.
C.Buat urutan yang linear
untuk semua sumber daya pada semua proses, jika proses telah di-
alokasikan pada suatu
type sumber daya maka proses berikutnya boleh meminta type sum
ber daya berikutnya.
Metode pencegahan
Deadlock :
a. Meniadakan mutual exclusion : yaitu
mencegah hanya satu proses yang mengakses sumber daya pada suatu
interval waktu tertentu,
b. Meniadakan syarat Hold dan Wait,
cara ini dapat dilakukan dengan : mengalokasikan semua sumber daya atau tidak
sama sekali dan hold and release.
proses untuk mengalokasikan
semua sumber daya atau tidak sama sekali permintaan ini hanya dapat
dilayani bila semua sumber daya tersedia ,jika sumber daya tersedia proses
dialokasikan jika diperlukan dan berjalan sampai selesai. Jika sumber
daya tidak tersedia atau hanya satu sumber daya maka proses harus menunggu
sampai semua sumber daya yg tersedia untuk dialokasikan padanya, yang
menjadi permasalahan adalah sukar untuk mengetahui lebih dulu sumber daya yang
diperlukan suatu proses karena pada awal proses tidak diketahui
berapa sumber daya yg diperlukan, jika proses hanya butuh satu disk diawal
eksekusi (atau lebih buruk lagi tanpa disk) dan menistrahatkan disk-disk
yang lain. Perlunya proses utnuk menerima disk yang diperlukan sebelum eksekusi
dimulai menyebabkan sumber daya komputer menganggur dalam waktu yang
lama, sementara proses yg memerlukan harus menunggu.
Hold and release (genggam dan
lepas)yaitu pada saat terjadi permintaan satu sumber daya
Maka proses harus melepaskan
sumber daya lain yg telah digunakan, jadi hanya satu sum –
ber daya yg
dialokasikan untuk proses. Cara ini tidak mungkin karena ada proses yang di
Syaratkan harus memegang
beberapa sumber daya sekaligus,misalnya menggambar pada
Plotter yang memerlukan
plotter serta disk untuk menyimpan data gambar yang diplot.
c. meniadakan kondisi non preempation
:yaitu mencegah proses lain harus enunggu proses preemption sehingga
tidak ada tunggu menunggu.
Contohnya :
saat proses
A menulis ke printer
tiba-tiba di stop oleh proses B yang juga akan menulis ke printer
yang sama bila
dimungkinkan preemption ini maka kedua proses akan mencetak
seca
ra tidak benar.
d.Meniadakan kondisi menunggu sirkular: Kondisi ini dapat
ditiadakan dengan cara yaitu
proses hanya dibolehkan menggenggam satu sumber
daya pada satu saat , jika perlu sum
ber daya yang kedua maka proses harus
melepaskan sumber daya pertama. (sama dengan
hold & release), cara ini tidak
dimungkinakn karena terdapat proses yang mengharuskan
memegang lebih dari satu sumber daya pada saat yg
sama untuk menyelesaikan prosenya.
Untuk meniadakan kondisi sirkular juga dapat
dilakukan dengan penomoran global semua
Sumber daya, karena proses dapat meminta kapanpun
proses menginginkan,tetapi perminta
an dibuat terurut secara numerik, cara ini tidak
menimbulkan siklus , permasalah yang
timbul tidak ada cara pengurutan nomor sumber daya
yang memuaskan semua pihak.
Di Tulis Oleh : Adi Suwanto - 12300043
5.Penghindaran Deadlock
Gagasan dasar penghindaran deadlock
adalah untuk memberi akses ke permintaan sumber daya yang tidak
menimbulkan deadlock, cara ini biasa digunakan dengan mengalokasikan sumber
daya dan memeriksa dampak pemberian akses ke suatu permintaan
Jika pemberian akses sumber daya tidak mungkin menimbulkan
deadlock maka sumber daya diberikan ke peminta sumber daya, jika timbul
deadlock maka proses yang meminta di suspend sampai waktu
permintaannya aman (tidak timbul deadlock) baru diberikan, kondisi ini biasanya
terjadi setelah satu suimber daya atau lebih yang semula dipegang oleh
proses-yang aktif liannya dilepas.
Untuk penghindaran deadlock diperlukan pengertian
mengenai state selamat (safe state) dan dan state tak selamat (unsafe state),
dinyatakan sebagai state selamat jika state tidak terjadi deadlock dan terdapat
cara untuk memenuhi semua permintaan yang ditunda tanpa menghasilkan deadlock
dengan menjalankan proses secara hati-hati & mengikuti urutan tertentu.
Contohnya :
* State selamat (safe state) dan
state tak selamat (unsafe state)
Safe State adalah cara untuk memenuhi permintaan yang
ditunda tanpa menghasilkan deadlock dengan menjalankan proses secara hati-hati
mengikuti urutan tertentu.
Contoh:
Pada sistem yang memiliki 10 sumber daya se type , proses A
memerlukan sumber daya maksimum 10 , sedangkan pada saat ini ia menggenggam 2
sumber daya, sedangkan proses B memerlukan sumber daya maksimum 3 sedangkan
saat ini menggenggam 1 sumber daya, proses C memerlukan sumber daya maksimum 7
sedangkan saat ini mengenggam 3 sumber daya ,maka masih tersedia sumber daya 4
seperti pada tabel dibawah ini :
Proses
|
Jlh sumber daya yg digenggam
|
Maks sumber daya yang dibutuhkan
|
A
|
2
|
10
|
B
|
1
|
3
|
C
|
3
|
7
|
Tersedia
4
|
||
Gbr 5.1 state selamat
Gambar 5.1 disebut safe state karena
ditemukan barisan pengalokasian yang memungkinkan semua proses selesai. Dengan
penjadwalan secara hati-hati sistem terhindar dari deadlock.
Sistem terhindar dari deadlock
adalah dengan langkah sbb:
1.Alokasikan 4 sumber daya pada
proses C sehingga sumber daya tersedia tinggal 1,nanti
sampai proses C
berakhir sehingga
Proses
|
Jlh Sumber daya yg digenggam
|
Maks sumber daya yang
dibutuhkan
|
A
|
2
|
10
|
B
|
1
|
3
|
C
|
7
|
7
|
Tersedia
0
|
||
Setelah selesai proses pada C maka diperoleh
Proses
|
Jlh sumber daya yg digenggam
|
Maks Sumber daya yang dibutuhkan
|
A
|
2
|
10
|
B
|
1
|
3
|
C
|
0
|
-
|
Tersedia
7
|
||
2.Alokasikan 5 sumber daya
nantikan sampai proses B berakhir
Proses
|
Jlh Sumber daya yg di genggam
|
Maks sumber daya yang dibutuhkan
|
A
|
2
|
10
|
B
|
3
|
3
|
C
|
0
|
-
|
Tersedia
5
|
||
Setelah proses B selesai maka
hasilnya
Proses
|
Jlh Sumber daya yg di genggam
|
Maks sumber daya yang dibutuhkan
|
A
|
2
|
10
|
B
|
0
|
-
|
C
|
0
|
-
|
Tersedia
8
|
||
3.Alokasikan 8 sumber daya
pada proses A nantikan sampai selesai
Proses
|
Jlh Sumber daya yg di genggam
|
Maks sumber daya yang dibutuhkan
|
A
|
10
|
10
|
B
|
-
|
-
|
C
|
-
|
-
|
Tersedia
0
|
||
Setelah proses A selesai maka
hasilnya
Proses
|
Jlh sumber daya yg di genggam
|
Maks sumber daya yang
dibutuhkan
|
A
|
0
|
-
|
B
|
0
|
-
|
C
|
0
|
-
|
Tersedia
|
0
|
Dengan tiga langkah proses dan
penjadwalan yang hati-hati dapat menyelesaikan proses dengan sempurna.
State tak selamat jika tidak
terdapat cara untuk memenuhi semua permintaan yang saat ini ditunda
dan menjalankan proses sesuai urutan. State tak selamat bila
alokasi sumber daya tak terkendali.
Proses
|
Jml sumber daya yg digenggam
|
Maks sumber daya yang
di butuhkan
|
A
|
2
|
10
|
B
|
1
|
3
|
C
|
3
|
7
|
Tersedia
4
|
||
State
berubah menjadi tak selamat :
· Dua permintaan sumber daya oleh
proses A dilayani dan
· Satu permintaan sumber daya
oleh proses B dilayani maka state berubah menjadi
Proses
|
Jlh sumber daya yg digenggam
|
Maks sumber daya dibutuhkan
|
A
|
4
|
10
|
B
|
2
|
3
|
C
|
3
|
7
|
Tersedia
1
|
||
Pada state
ini tidak terdapat baris pengalokasian yang dapat membuat semua proses
selesai ,
Contohnya :
Langkah : 1
Alokasikan satu sumber daya pada proses B sehingga sumber daya tersedia
Hanya 1 dan nantikan proses B selesai.
Proses
|
Jlh sumber daya yg digenggam
|
Maks sumber daya dibutuhkan
|
A
|
4
|
10
|
B
|
3
|
3
|
C
|
3
|
7
|
Tersedia
0
|
||
Setelah selesai
proses B maka menjadi
Proses
|
Jml sumber daya yg di genggam
|
Maks sumber daya dibutuhkan
|
A
|
4
|
10
|
B
|
0
|
-
|
C
|
3
|
7
|
Tersedia
|
3
|
Sekarang tersedia 3 sumber daya
sementara proses A membutuhakn 6 sumber daya dan proses C membutuhkan 4
sumber daya. Keterangan diatas tadi adalah untuk alokasi sumber daya sejenis ,
pengertian state selamat dan tak selamat dapat diperluas untuk sumber
daya tak sejenis. Yang perlu diingat bahwa state tak selamat bukan
berarti telah terjadi deadlock, tetapi state tersebut kemungkinan menuju
deadlock.
Di Tulis Oleh : Yuyud Yanegar - 12300039
* Algoritma bunker olek Dijkstra
Disebut algoritma karena memodelkan bunker disebuah
kota kecil yang berurusan dengan sekumpulan nasabah yang memohon kredit,
pada algoritma ini kondisi mutual exclusion, hold and wait dan non preemption
diizinkan dan proses melakukan klaim penggunaan sumber daya eksklusif
yang diperlukan, proses diizinkan menggenggam sumber daya sambil meminta
dan menunggu sumber daya yang lain. Serta sumber daya itu tidak diizinkan di
preemption proses lain. Proses dapat meminta sumber daya pada suatu waktu,
sistem operasi dapat mengakses dan menolak sumber daya permintaan, jika
ditolak proses masih menggenggam sumber daya yg telah dialokasikan
dan menunggu sampai waktu yg tak terhingga sampai permintaan dipenuhi.
Dan sistem hanya meberikan permintaan yang menghasilkan
state selamat, sedangkan permintaan yang menghasilkan state tak selamat ditolak
sampai permintaan dipenuhi. Karena sistem selalu memelihara agar dalam kondisi
state selamat maka cepat atau lambat dalam waktu yang tak terhingga semua
permintaan dapat dipenuhi dan semua proses berakhir.
* Kelemahan Algoritma Banker
1. Proses jarang mengetahui jumlah
sumber daya maksimum diperlukan di awalnya.
2. Jumlah proses tidak tetap
3. Sumber daya yang tersedia tiba
tiba dapat saja dicopot
4. Proses harus independen yaitu urutan
proses eksekusi tidak dibatasi kebutuhan sinkronisasi antar proses.
5. Algoritma menghendaki memberikan
semua permintaan pada waktu yang tak terhingga
6. Algoritma menghendaki client
mengembalikan sumber daya setelah waktu yang tak terhingga
6. Deteksi dan pemulihan Deadlock
Deteksi adanya dealock
adalah cara untuk menentukan apakah deadlock terjadi serta mengidentifikasi
proses dan sumber daya yang terlibat dalam deadlock. Umumnya algoritma yang
dibutuhkan untuk deteksi adalah menentukan keberadaan menunggu
sirkular (circular wait), penggunaan algoritma ini melibatkan over head
run time karena secara kontinyu dijalankan untuk mendeteksi
menunggu sirkular, sembaranag algoritma pendeteksian siklus graph berarah dapat
digunakan. Perioda yang biasa dilakukan adalah memonitor permintaan dan
pelepasan sumber daya. Setiap terdapat permintaan & pelepasan maka
dilakukan pembaharuan graph dan deteksi adanya siklus. Bila terdapat
siklus berarti terjadi menunggu sirkular dan deadlock terjadi.
Pemulihan dari deadlock yaitu begitu
sistem terdapat deadlock maka deadlock harus diputuskan denagn menghilangkan
salah satu atau lebih persyaratannya.
Pemulihan dari deadlock ditentukan
oleh beberapa faktor :
·
Belum
tentu secepatnya dapat menentukan deadlock
·
Kebanyakan
sistem tidak memilki fasiltas atau fasilitasnya buruk untuk mensuspend
proses,menghilangkan dari sistem dan meresume proses dilain waktu, pada sistem
waktu nyata yang harus berfungsi kontinyu proses tidak dapat di suspend dan
resume.
·
Jika
terdapat kemampuan sistem resume dan suspend yang efektif kemampuan ini dapat
melibatkan sejumlah overhead, berarti memerlukan perhatian operator yang
berkemampuan tinggi,operator ini tidak selalu tersedia.
·
Pemulihan
memerlukan sejumlah kerja yang berarti.
Pada sistem operasi yang hanya tiga state dasar
(running,ready dan blocked) maka tak ada cara lain kecuali menyingkirkan proses
itu, proses akan hilang dari memori dan harus dimuat kembali, sedangkan pada
operasi modern sistem biasanya menerapkan state supended blocked dan suspended
ready diman sumber dayanya dilepas tetapi proses masih di memory dan akan
ditetapkan kembali proses untuk sumber daya begitu terjadi resume.
Pendekatan yang digunakan untuk pemulihan deadlock :
·
Singkirkan
semua proses yang melibatkan deadlock (cara ini sering digunakan)
·
Backup
semua proses yang terlibat deadlock ke suatu check point yang didefinisikan
sebelumnya dan jalankan kembali semua proses itu, cara ini memerlukan mekanisme
rollback dan restart,resikonya deadlock semula dapat terjadi lagi , tetapi
karena tidak tertentu pemrosesan kong kuren ,biasa tidak akan terjadi deadlock
serupa.
·
Secara
berurutan singkirkan proses sampai tidak terjadi deadlock lagi, urutan proses
yang disingkirkan berdasarkan kriteria ongkos minimum, setelah penyingkiran
algoritma deteksi harus dijaalankan untuk melihat apakah masih terjadi
deadlock.
·
Secara
berurutan preemp sumber daya tidak ada deadlock lagi,
Kriteria-kriterianya sebagai
berikut:
· Waktu pemrosesan yang telah
dijalankan paling kecil
· Jumlah baris keluaran yang
diproduksi kecil
· Mempunyai estimasi sisa waktu
eksekusi besar
· Jumlah total sumber daya terkecil
yang telah dialokasikan
· Prioritas terkecil.
7. Strategi Penanggulangan Deadlock
Terpadu
Silberschatz menyarankan satu
pendekatan terpadu yaitu:
· Kelompokkan sumber daya
menjadi kelas sumber daya
· Gunakan strategi pengurutan linear seperti
yg dijelaskan pada pencegahan menunggu sirkular, strategi ini untuk mencegah
deadlock diantara kelas sumber daya yang berbeda.
· Dalam satu kelas sumber daya gunakan
algoritma yang sesuai untuk kelas sumber daya tsb.
Di Tulis Oleh : Jovie Taufan 12300025
SUMBER :
1.Haryanto,Bambang,Ir sistim operasi
Penerbit informatika Bandung 1999
2.Tanenbaum Andrew,S Modern
operating system,prentic hall Inc 1992
ALAMAT :
(23-04-2013) TGL. AKSES
0 komentar:
Posting Komentar