Pencegahan Deadlock pada Alokasi Resource dalam
Sistem Operasi Menggunakan Algoritma Greedy
Timotius
T. Safei (13509017)
Program
Studi Teknik Informatika
Sekolah
Teknik Elektro dan Informatika
Institut
Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia
Analisis masalah
Sistem
operasi menangani berbagai fungsi, salah satunya pengalokasian sumber daya.
Pada pengalokasian sumber daya dalam sistem operasi sangat mungkin terjadi
masalah. Salah satu masalah tersebut adalah deadlock. Karena itu
diperlukan cara-cara khusus untuk menanganinya. Selain penangan, dapat juga
dilakukan pencegahan. Oleh karena itu dalam makalah ini akan dibahas mengenai
pencegahan deadlock menggunakan algoritma greedy.
Bagian yang akan dibahas pada makalah ini
adalah bagian pembagian sumber daya. Sumber daya perlu diatur karena sumber
daya tersebut terbatas, sedangkan proses yang membutuhkannya lebih banyak.
Tentu saja hal tersebut menimbulkna masalah.
Secara khusus, masalah yang akan dibahasa
adalah mengenai deadlock. Masalah deadlock muncul ketika sumber
daya tertentu diperlukan oleh 2 proses atau lebih dalam periode yang sama. Penyelesaian
masalah tersebut dapat dibagi menjadi dua bagian, yaitu perbaikan dan
pencegahan. Perbaikan dilakukan apabila deadlock sudah terjadi. Metode
ini memiliki beberapa contoh seperti algoritma ostrich, roll back, dan killing
proses. Selain itu, permasalahan deadlock bisa dihindarkan dengan cara
dicegah. Kita bisa membuat mekanisme sedemikian hingga kejadian deadlock tidak
akan terjadi.
Perancangan
sistem
Dalam mengalokasikan sumber daya,
perlu diperhatikan jumlah sumber daya yang akan diberikan. Selain itu perlu
diperhatikan juga proses yang mana yang harus diberikan sumber daya. Apabila
sumber daya diberikan ke sembarang proses dalam keadaan tertentu maka akan
terjadi deadlock.
Pada makalah ini, permasalah yang
akan diangkat adalah bagaimana mengalokasikan sumber daya agar tidak terjadi deadlock.
Hal ini termasuk dalam prevention. Kita mencegah agar deadlock tidak
akan muncul. Dalam masalah ini, asumsi yang digunakan adalah:
a. Sumberdaya bersifat
non-preamptable
b. Proses dan sumber daya dianggap
homogen
Pemasalah yang ada bukanlah
permasalahan secara menyeluruh, tetapi merupakan model dari permasalahan yang
ada.
Sebagai
contoh berikut adalah tabel alokasi sumber daya
Tabel I
|
Alokasi
|
Kebutuhan
|
Proses
1
|
3
|
5
|
Proses
2
|
2
|
4
|
Sisa sumber daya: 1.
Keadaan di atas belum merupakan deadlock,
tetapi merupakan keadaan unsafe. Dapat dilihat bahwa dalam pengalokasian
selanjutnya, akan terjdai deadlock. Tujuan dari penggunaan algoritma
greedy adalah mencegah keadaan tersebut terjadi sehingga dapat menghindarai deadlock.
Berikut ini contoh kedua
Tabel II
|
Alokasi
|
Kebutuhan
|
Proses
1
|
2
|
5
|
Proses
2
|
2
|
4
|
Sisa sumber daya: 2.
Keadaan
pada contoh kedua sistem dalam keadaan safe karena dengan pengalokasian yang
tepat, maka semua proses pasti dapat diselesaikan. Akan tetapi jika kita salah
mengalokasikan sumber daya yang ada maka dapat terjadi deadlock. Apabila
kita mengalokasikan sisa sumber daya tersebut pada proses 1 maka akna terjadi
keadaan seperti pada contoh satu dan jika dilanjutkan lagi akan terjadi deadlock.
Dapat
dilihat dari contoh bahwa perlu cara yang tepat untuk menangani pembagian
sumber daya agar tidak terjadi deadlock. Bahkan walaupun dalam keadaan
safe sekalipun.
Implementasi
Pada pencegahan masalah ini algoritma
greedy digunakan untuk mencari solusi bagaimana cara alokasi yang tidak akan
mengakibatkan permasalahan di atas. Apabila kita lihat lebih jauh, kita dapat
menemukan elemen greedy dari permasalahan tersebut.
Himpunan kandidat dari permasalahn di
atas adalah semua kemungkinan alokasi sumber daya kepada setiap proses.
Himpunan kandidat dari contoh pertama pada permasalahn adalah sumber daya
dialokasikan ke proses 1 atau ke proses 2.
Himpunan solusinya adalah bentuk
alokasi yang diambil setelah mengeksekusi fungsi seleksi terhadap himpunan
kandidat yang ada.
Fungsi seleksi yang akan digunakan
adalah fungsi yang mencari proses yang membutuhkan alokasi sumber daya paling
sedikit. Dengan begitu, kita dapat menyelesaikan proses sebanyak-banyaknya
dengan sumber daya yang ada. Dengan demikian diharapkan proses yang harus
menunggu sumber daya berjumlah minimal.
Fungsi kelayakan yang akan digunakan
adalah melihat apakah dengan alokasi yang dilakukan akan ada proses baru yang
dapat terselesaikan. Fungsi akan melihat apabila kandidat yang dipilih
dijalankan, apakah akan ada proses yang selesai. Apabila tidak ada proses yang
selesai maka alokasi akan ditunda. Hal ini digunakan untuk mencegah deadlock
karena kekurangan sumber daya.
Fungsi
obyektif dari algoritma ini untuk menyelesaikan proses sebanyak-banyaknya.
Dengan begitu, diharapkan semua proses dapat selesai tanpa terjadi deadlock.
Pengujian
Algoritma greedy yang dibuat
digunakan dari awal alokasi sumber daya, yaitu saat semua alokasi pada proses
bernilai 0. Agar semua proses pasti dapat terselesaikan, maka jumlah sumber
daya minimal yang dimiliki harus lebih besar sama dengan kebutuhan terbesar
dari salah satu proses. Dalam
penerapannya, algoritma ini mungkin saja mendapat proses baru yang harus
dijalankan. Hal ini tidak menjadi masalah karena proses baru tersebut dapat
langsung dimasukkan ke dalam himpunan kandidat.
Pengeksekusian algoritma greedu ini
dilakukan setiap kali ada perubahan sumber daya yang tersedia. Jadi setiap ada
penambahan atau pengurangan sumber daya, alokasi akan coba dilakukan
menggunakan algoritma greedy. Selain itu, algoritma akan dijalankan apabila ada
proses baru yang masuk. Jadi setiap ada penambahan proses maka akan dicoba
pengalokasian sumber daya. Tentu saja pengalokasian dilakukan dengan algoritma
greedy yang sudah dibuat. Sebagai bahan
analisis berikut ini diberikan contoh tabel alokasi
Tabel III
|
Alokasi
|
Kebutuhan
|
P1
|
0
|
5
|
P2
|
0
|
10
|
P3
|
0
|
6
|
Jumlah sumber daya yang tersedia 10.
Total
sumber daya : 10.
Dari tabel III algoritma greedy yang
akan mencoba mengalokasikan sumber daya yang ada ke salah satu proses. Sesuai
dengan fungsi seleksi yang ada, maka kandidat yang akan diajukan adalah P1.
Setelah
itu, fungsi kelayakan akan mengecek apakah kandidat yang ada sudah layak.
Apabila alokasi dilakukan maka P1 dapat diselesaikan, berarti kandidat tersebut
akan dijalankan dan dimasukkan ke dalam fungsi solusi.
Tabel IV
|
Alokasi
|
Kebutuhan
|
P1
|
5
|
5
|
P2
|
0
|
10
|
P3
|
0
|
6
|
Jumlah sumber daya yang tersedia 5.
Total sumber daya : 10.
Dilihat dari tabel IV, setelah
alokasi, maka algoritma dijalankan kembali. Fungsi seleksi akan menghasilkan
kandidat P3. Akan tetapi P3 tidak memenuhi fungsi kelayakan, karena meskipun
diberikan semua sumber daya yang ada, P3 tetap tidak dapat diselesaikan. Oleh
karena itu P3 tidak akan dimasukkan ke dalam himpunan solusi.
Setelah P1 selesai maka pengalokasian
akan dijalankan kembali. P3 menjadi kandidat untuk dialokasikan. Karena dengan
pengalokasian P3 dapat diselesaikan maka P3 akan dimasukkan ke dalam himpunan
solusi dan alokasi akan dijalankan. Setelah itu, algoritma akan dijalankan lagi
karena terjadi perubahan jumlah sumber daya yang tersedia. Akan tetapi karena
P2 tidak memenuhi fungsi kelayakan maka tidak akan dimasukkan ke dalam himpunan
solusi dan alokasi tidak akan dilakukan.
Apabila
ada proses baru yang masuk, maka proses tersebut aka dimasukkan ke dalam
himpunan kandidat seperti yang dapat terlihat dalam tabel V
Tabel V
|
Alokasi
|
Kebutuhan
|
P2
|
0
|
10
|
P3
|
6
|
6
|
P4
|
0
|
2
|
Jumlah sumber daya yang tersedia 4.
Total sumber daya : 10.
Karena ada proses baru yang masuk
maka pengalokasian akan dicoba sekali lagi. Fungsi seleksi akan memilih P4
karena membutuhkan alokasi paling sedikit, yaitu 2 dan karena P4 memenuhi
fungsi kelayakan maka akan dialokasikan 2 sumber daya kepada P4 dan yang
tersisa adalah 2 sumber daya. Algoritma greedy akan dijalankan kembali, tetapi
karena tidak ada kandidat yang layak maka tidak akan dilakukan
pengalokasian. Pemilihan fungsi
kelayakan dikarenakan jika alokasi tetap dilakukan meski tidak menyelesaikan
proses, maka sangat mungkin terjadi masalah jika ada proses baru yang masuk.
Misalkan pada lanjutan contoh sebelumnya, sisaalokasi akan dimasukkan ke P2
meskipun tidak menyelesaikan proses, tetapi merupakan proses dengan kebutuhan
sumber daya paling sedikit.
Masalah
yang timbul adalah terbuangnya sumber daya dan waktu. Misalkan setelah
pengalokasian, masuk 1 proses baru. Agar lebih jelas dapat dilihat pada tabel
VI.
Tabel VI
|
Alokasi
|
Kebutuhan
|
P2
|
2
|
10
|
P3
|
6
|
6
|
P4
P5
|
2
0
|
2
4
|
Jumlah sumber daya yang tersedia 0.
Total sumber daya : 10.
Apabila setelah ini P4 selesai, maka
P5 tetap harus menunggu P3 selesai baru dapat diselesaikan. Hal ini mengurangi
efisiensi waktu. Oleh karena itu isi dari fungsi kelayakan adalah setiap
pengalokasian harus ada proses baru yang dapat diselesaikan. Akan tetapi penggunaan algoritma greedy ini
bukan berarti tanpa masalah. Sebagai contoh lihat tabel berikut
Tabel VII
|
Alokasi
|
Kebutuhan
|
P2
|
0
|
10
|
P3
|
6
|
6
|
P5
P6
P7
|
4
0
0
|
4
3
5
|
Jumlah sumber daya yang tersedia 0.
Total sumber daya : 10.
Pada tabel VII masuk 2 proses baru
yang membutuhkan alokasi lebih rendah dari P2. Apabila P3 dan P5 selesai maka
algoritma greedy akan mengalokasikan sumber daya kepada P6 dan P7. Kemudian ada
proses baru yang masuk. Agar lebih jelas akan digambarkan pada tabel VIII.
Tabel VIII
|
Alokasi
|
Kebutuhan
|
P2
|
0
|
10
|
P6
P7
P8
|
3
5
0
|
3
5
9
|
Jumlah sumber daya yang tersedia 2.
Total sumber daya : 10.
Dapat dilihat dari tabel VIII, P2
memiliki kebutuhan alokasi maksimal. Oleh karena itu, apabila ada proses yang
belum diselesaikan dan memiliki kebutuhan lebih kecil P2 tidak akan terproses
sampai semua proses selesai. Jadi apabila masih ada proses yang sedang
dikerjakan atau ada proses baru terus menerus maka P2 akan membutuhkan waktu
yang sangat lama untuk diselesaikan.
Peristiwa
ini disebut starving. Starving adalah peristiwa di mana proses yang memiliki
prioritas kecil, dalam hal ini memiliki kebutuhan alokasi paling besar, tidak
akan terselesaikan karena tidak mendapatkan sumber daya yang dibutuhkan.
Peristiwa ini harus ditangani lagi dengan cara khusus. Oleh karena itu,
algoritma greedy memberikan hasil optimum dalam persoalan ini. Akan tetapi
sangat mungkin menimbulkan masalah lain yang harus dihindari juga.
Simpulan
Dalam menjalankan fungsinya,
sistemoperasi memiliki beberapa masalah yang dapat muncul. Salah satu masalah
dalam pengalokasian sumber daya adalah deadlock. Deadlock dapat
dihindari dengan mengaplikasikan algoritma greedy dalam mengalokasikan sumber
daya. Algoritma greey dapat menghindarkan deadlock sepenuhnya selama
sumber daya yang ada memang mencukupi. Akan tetapi algoritma ini juga masih
memiliki kekurangan. Algoritma ini menghilangkan deadlock, Makalah
IF3051 Strategi Algoritma – Sem. I Tahun 2011/2012
tetapi
memungkinkan terjadinya starving. Jadi algoritma ini dapat digunakan tetapi
masih membutuhkan beberapa perbaikan dan penyesuaian.
