SILAKAN MENONTON TV ONLINE DI BAWAH SENDIRI JAL..

Senin, 15 November 2010

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 deadlock pada lalu lintas di jembatan


      Pada contoh di atas, digambarkan ilustrasi dari kejadian deadlock pada dunia nyata, yaitu pada lalu lintas di jembatan. 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. Kondisi tersebut bila terjadi dalam waktu yang lama dapat menyebabkan terjadinya starvation.

Contoh kasus deadlock pada lalu lintas di persimpangan



        Gambar di atas adalah contoh lain terjadinya deadlock pada dunia nyata. Pada gambar jelas terlihat bahwa lalu lintas terhenti dan terjadi antrian pada empat arah datangnya mobil. Tidak ada mobil yang bisa melanjutkan perjalanan dan hanya menunggu saja. Permasalahan ini dapat dipecahkan dengan cara salah satu dari antrian tersebut mundur dan memberikan kesempatan antrian lain untuk berjalan terlebih dahulu. Kasus seperti ini sangat potensial untuk terjadinya starvation. Berikut ini diberikan contoh situasi deadlock yang dideskripsikan dengan pseudocode.


STARVATION
       Pada bagian pendahuluan, telah sama-sama kita ketahui mengenai pengertian dari deadlock. Di contoh lalu lintas jembatan, terlihat bahwa kejadian deadlock yang berlangsung secara terus-menerus dan tiada akhir dapat menyebabkan terjadinya starvation. Akan tetapi, deadlock bukanlah satu-satunya penyebab terjadinya starvation. Lalu lintas yang didominasi oleh kendaraan-kendaraan dari satu arah pun dapat menyebabkan terjadinya starvation. Akibat yang terjadi adalah kendaraan dari arah lain menjadi terus menunggu giliran untuk berjalan hingga akhirnya mengalami starvation.
Starvation adalah keadaan dimana satu atau beberapa proses 'kelaparan' karena terus dan terus menunggu kebutuhan sumber dayanya dipenuhi. Namun, karena sumber daya tersebut tidak tersedia atau dialokasikan untuk proses lain, akhirnya proses yang membutuhkan tidak bisa memilikinya. Kondisi seperti ini merupakan akibat dari keadaan menunggu yang berkepanjangan.

MODEL SISTEM
      Keadaan dimana suatu proses yang meminta sumber daya pasti terjadi dalam suatu sistem. Untuk itu dibutuhkan cara pemodelan terhadapnya. Terdapat tipe sumber daya R 1, R 2, ..., R m. Contohnya adalah space pada memori dan juga komponen-komponen M/K. Setiap tipe sumber daya R i tersebut memiliki W i instances. Misalnya sebuah sumber daya M/K memiliki dua buah instances yang bisa diakses oleh proses.
Sebuah proses dalam melakukan penggunaan terhadap suatu sumber daya melalui langkah-langkah sebagai berikut:
•    Request . Pada langkah ini, pertama kali proses mengajukan diri untuk bisa mendapatkan
     sumber daya. Proses dapat meminta satu atau lebih sumber daya yang tersedia ataupun yang
     sedang dimiliki oleh proses yang lain.
•    Use . Selanjutnya, setelah proses mendapatkan sumber daya yang dibutuhkannya, proses
     akan melakukan eksekusi. Sumber daya digunakan oleh proses sampai proses selesai
     melakukan eksekusi dan tidak membutuhkan lagi sumber daya tersebut.
•    Release . Setelah memanfaatkan sumber daya untuk melakukan eksekusi, proses pun akan
     melepaskan sumber daya yang dimilikinya. Sumber daya tersebut dibutuhkan oleh proses lain
     yang mungkin sedang menunggu untuk menggunakan.

KARAKTERISTIK
         Setelah pada bagian sebelumnya kita telah mengetahui mengenai pengertian dari deadlock dan bagaimana memodelkannya, sekarang kita akan membahas secara mendalam mengenai karakteristik dari terjadinya deadlock. Karakteristik-karakteristik ini harus dipenuhi keempatnya untuk terjadi deadlock. Namun, perlu diperhatikan bahwa hubungan kausatif antara empat karakteristik ini dengan terjadinya deadlock adalah implikasi. Deadlock mungkin terjadi apabila keempat karakteristik terpenuhi. Empat kondisi tersebut adalah:
1.  Mutual Exclusion . Kondisi yang pertama adalah mutual exclusion yaitu proses memiliki
     hak milik pribadi terhadap sumber daya yang sedang digunakannya. Jadi, hanya ada satu
     proses yang menggunakan suatu sumber daya. Proses lain yang juga ingin menggunakannya
     harus menunggu hingga sumber daya tersebut dilepaskan oleh proses yang telah selesai 
     menggunakannya. Suatu proses hanya dapat menggunakan secara langsung sumber daya
     yang tersedia secara bebas.
2.  Hold and Wait . Kondisi yang kedua adalah hold and wait yaitu beberapa proses saling
     menunggu sambil menahan sumber daya yang dimilikinya. Suatu proses yang memiliki
     minimal  satu buah  sumber daya melakukan request lagi terhadap sumber daya. Akan
     tetapi, sumber daya yang dimintanya sedang dimiliki oleh proses yang lain. Pada saat yang
     sama,  kemungkinan adanya proses lain yang juga mengalami hal serupa dengan proses
     pertama cukup besar terjadi.Akibatnya, proses-proses tersebut hanya bisa saling menunggu
     sampai sumber daya yang dimintanya dilepaskan. Sambil menunggu, sumber daya yang telah
     dimilikinya pun tidak akan dilepas. Semua proses itu pada akhirnya saling menunggu dan
     menahan sumber daya miliknya.
3.  No Preemption . Kondisi yang selanjutnya adalah no preemption yaitu sebuah sumber daya
     hanya dapat dilepaskan oleh proses yang memilikinya secara sukarela setelah ia selesai
     menggunakannya. Proses yang menginginkan sumber daya tersebut harus menunggu sampai
     sumber daya tersedia, tanpa bisa merebutnya dari proses yang memilikinya.
4.  Circular Wait . Kondisi yang terakhir adalah circular wait yaitu kondisi membentuk siklus yang
     berisi proses-proses yang saling membutuhkan. Proses pertama membutuhkan sumber daya
     yang dimiliki proses kedua, proses kedua membutuhkan sumber daya milik proses ketiga, dan
     seterusnya sampai proses ke n-1 yang membutuhkan sumber daya milik proses ke n. Terakhir,
     proses ke n membutuhkan sumber daya milik proses yang pertama. Yang terjadi adalah
     proses-proses tersebut akan selamanya menunggu. Circular wait oleh penulis diistilahkan
     sebagai 'Lingkaran Setan' tanpa ujung.

PENANGANAN
Secara umum terdapat 4 cara untuk menangani keadaan deadlock, yaitu:
1.  Pengabaian. Maksud dari pengabaian di sini adalah sistem mengabaikan terjadinya deadlock
     dan pura-pura tidak tahu kalau deadlock terjadi. Dalam penanganan dengan cara ini dikenal
     istilah ostrich algorithm. Pelaksanaan algoritma ini adalah sistem tidak mendeteksi adanya
     deadlock dan secara otomatis mematikan proses atau program yang mengalami deadlock.
     Kebanyakan sistem operasi yang ada mengadaptasi cara ini untuk menangani keadaan
     deadlock. Cara penanganan dengan mengabaikan deadlock banyak dipilih karena kasus
     deadlock tersebut jarang terjadi dan relatif rumit dan kompleks untuk diselesaikan. Sehingga
     biasanya hanya diabaikan oleh sistem untuk kemudian diselesaikan masalahnya oleh user
     dengan cara melakukan terminasi dengan Ctrl+Alt+Del atau melakukan restart terhadap
     komputer.
2.  Pencegahan. Penanganan ini dengan cara mencegah terjadinya salah satu karakteristik
     deadlock. Penanganan ini dilaksanakan pada saat deadlock belum terjadi pada sistem. Intinya
     memastikan agar sistem tidak akan pernah berada pada kondisi deadlock. Akan dibahas
     secara lebih mendalam pada bagian selanjutnya.
3.  Penghindaran. Menghindari keadaan deadlock. Bagian yang perlu diperhatikan oleh pembaca
     adalah bahwa antara pencegahan dan penghindaran adalah dua hal yang berbeda. Pencegahan
     lebih kepada mencegah salah satu dari empat karakteristik deadlock terjadi, sehingga deadlock
     pun tidak terjadi. Sedangkan penghindaran adalah memprediksi apakah tindakan yang diambil
     sistem, dalam kaitannya dengan permintaan proses akan sumber daya, dapat mengakibatkan
     terjadi deadlock. Akan dibahas secara lebih mendalam pada bagian selanjutnya.
4.  Pendeteksian dan Pemulihan. Pada sistem yang sedang berada pada kondisi deadlock,
     tindakan yang harus diambil adalah tindakan yang bersifat represif. Tindakan tersebut adalah
     dengan mendeteksi adanya deadlock, kemudian memulihkan kembali sistem. Proses
     pendeteksian akan menghasilkan informasi apakah sistem sedang deadlock atau tidak serta
     proses mana yang mengalami deadlock. Akan dibahas secara lebih mendalam pada bagian
     selanjutnya.

PENCEGAHAN
Pencegahan deadlock dapat dilakukan dengan cara mencegah salah satu dari empat karakteristik terjadinya deadlock. Berikut ini akan dibahas satu per satu cara pencegahan terhadap empat karakteristik tersebut.
1.  Mutual Exclusion . Kondisi mutual exclusion pada sumber daya adalah sesuatu yang
     wajar terjadi, yaitu pada sumber daya yang tidak dapat dibagi (non-sharable). Sedangkan
     pada sumber daya yang bisa dibagi tidak ada istilah mutual exclusive. Jadi, pencegahan
     kondisi yang pertama ini sulit karena memang sifat dasar dari sumber daya yang tidak dapat
     dibagi.
2.  Hold and Wait . Untuk kondisi yang kedua, sistem perlu memastikan bahwa setiap kali proses
     meminta sumber daya, ia tidak sedang memiliki sumber daya lain. Atau bisa dengan proses
     meminta dan mendapatkan sumber daya yang dimilikinya sebelum melakukan eksekusi,
     sehingga  tidak perlu menunggu.
3.  No Preemption . Pencegahan kondisi ini dengan cara membolehkan terjadinya preemption.
     Maksudnya bila ada proses yang sedang memiliki sumber daya dan ingin mendapatkan
     sumber daya tambahan, namun tidak bisa langsung dialokasikan, maka akan preempted.
     Sumber daya yang dimiliki proses tadi akan diberikan pada proses lain yang membutuhkan dan
     sedang menunggu. Proses akan mengulang kembali eksekusinya setelah mendapatkan semua
     sumber daya yang dibutuhkannya, termasuk sumber daya yang dimintanya terakhir.
4.  Circular Wait . Kondisi 'lingkaran setan' ini dapat 'diputus' dengan jalan menentukan total
     kebutuhan terhadap semua tipe sumber daya yang ada. Selain itu, digunakan pula
     mekanisme enumerasi terhadap tipe-tipe sumber daya yang ada. Setiap proses yang akan
     meminta sumber daya harus meminta sumber daya dengan urutan yang menaik. Misalkan
     sumber daya printer memiliki nomor 1 sedangkan CD-ROM memiliki nomor 3. Proses boleh 
     melakukan permintaan terhadap printer dan kemudian CD-ROM, namun tidak boleh sebaliknya.

PENGHINDARAN
Penghindaran terhadap deadlock adalah cara penanganan yang selanjutnya. Inti dari penghindaran adalah jangan sembarangan membolehkan proses untuk memulai atau meminta lagi. Maksudnya adalah, jangan pernah memulai suatu proses apabila nantinya akan menuju ke keadaan deadlock. Kedua, jangan memberikan kesempatan pada proses untuk meminta sumber daya tambahan jika penambahan tersebut akan membawa sistem pada keadaan deadlock. Tidak mungkin akan terjadi deadlock apabila sebelum terjadi sudah kita hindari.
Langkah lain untuk menghindari adalah dengan cara tiap proses memberitahu jumlah kebutuhan maksimum untuk setiap tipe sumber daya yang ada. Selanjutnya terdapat deadlock-avoidance algorithm yang secara rutin memeriksa state dari sistem untuk memastikan tidak adanya kondisi circular wait serta sistem berada pada kondisi safe state. Safe state adalah suatu kondisi dimana semua proses mendapatkan sumber daya yang dimintanya dengan sumber daya yang tersedia. Apabila tidak bisa langsung, ia harus menunggu selama waktu tertentu, kemudian mendapatkan sumber daya yang diinginkan, melakukan eksekusi, dan terakhir melepas kembali sumber daya tersebut. Terdapat dua jenis algoritma penghindaran yaitu resource-allocation graph untuk single instances resources serta banker's algorithm untuk multiple instances resources.
Algoritma penghindaran yang pertama yaitu resource-allocation graph akan dijelaskan secara mendalam pada bab selanjutnya yaitu Diagram Graf. Untuk algoritma yang kedua yaitu banker's algorithm akan dibahas pada bab ini dan dilengkapi oleh pembahasan di bab selanjutnya.
Dalam banker's algorithm, terdapat beberapa struktur data yang digunakan, yaitu:
•    Available . Jumlah sumber daya yang tersedia.
•    Max . Jumlah sumber daya maksimum yang diminta oleh tiap proses.
•    Allocation . Jumlah sumber daya yang sedang dimiliki oleh tiap proses.
•    Need . Sisa sumber daya yang masih dibutuhkan oleh proses, didapat dari max- allocation.
Kemudian terdapat safety algorithm untuk menentukan apakah sistem berada pada safe state atau tidak.

PENDETEKSIAN
Pada dasarnya kejadian deadlock sangatlah jarang terjadi. Apabila kondisi tersebut terjadi, masing-masing sistem operasi mempunyai mekanisme penanganan yang berbeda. Ada sistem operasi yang ketika terdapat kondisi deadlock dapat langsung mendeteksinya. Namun, ada pula sistem operasi yang bahkan tidak menyadari kalau dirinya sedang mengalami deadlock. Untuk sistem operasi yang dapat mendeteksi deadlock, digunakan algoritma pendeteksi. Secara lebih mendalam, pendeteksian kondisi deadlock adalah cara penanganan deadlock yang dilaksanakan apabila sistem telah berada pada kondisi deadlock. Sistem akan mendeteksi proses mana saja yang terlibat dalam kondisi deadlock. Setelah diketahui proses mana saja yang mengalami kondisi deadlock, maka diadakan mekanisme untuk memulihkan sistem dan menjadikan sistem berjalan kembali dengan normal.
Mekanisme pendeteksian adalah dengan menggunakan detection algorithm yang akan memberitahu sistem mengenai proses mana saja yang terkena deadlock. Setelah diketahui proses mana saja yang terlibat dalam deadlock, selanjutnya adalah dengan menjalankan mekanisme pemulihan sistem yang akan dibahas pada bagian selanjutnya. Berikut ini adalah algoritma pendeteksian deadlock.

PEMULIHAN
Pemulihan kondisi sistem terkait dengan pendeteksian terhadap deadlock. Apabila menurut algoritma pendeteksian deadlock sistem berada pada keadaan deadlock, maka harus segera dilakukan mekanisme pemulihan sistem. Berbahaya apabila sistem tidak segera dipulihkan dari deadlock, karena sistem dapat mengalami penurunan performance dan akhirnya terhenti.
Cara-cara yang ditempuh untuk memulihkan sistem dari deadlock adalah sebagai berikut:
1.  Terminasi proses. Pemulihan sistem dapat dilakukan dengan cara melalukan terminasi
     terhadap semua proses yang terlibat dalam deadlock. Dapat pula dilakukan terminasi terhadap
     proses yang terlibat dalam deadlock secara satu per satu sampai 'lingkaran setan' atau circular
     wait hilang. Seperti diketahui bahwa circular wait adalah salah satu karakteristik terjadinya
     deadlock dan merupakan kesatuan dengan tiga karakteristik yang lain. Untuk itu, dengan
     menghilangkan kondisi circular wait dapat memulihkan sistem dari deadlock.Dalam melakukan
     terminasi terhadap proses yang deadlock, terdapat beberapa faktor yang menentukan proses
     mana yang akan diterminasi. Faktor pertama adalah prioritas dari proses-proses yang terlibat
     deadlock.Faktor kedua adalah berapa lama waktu yang dibutuhkan untuk eksekusi dan waktu
     proses menunggu sumber daya. Faktor ketiga adalah berapa banyak sumber daya yang telah
     dihabiskan dan yang masih dibutuhkan. Terakhir, faktor utilitas dari proses pun menjadi
     pertimbangan sistem untuk melakukan terminasi pada suatu proses.
2.  Rollback and Restart . Dalam memulihkan keadaan sistem yang deadlock, dapat dilakukan
     dengan cara sistem melakukan preempt terhadap sebuah proses dan kembali ke state yang
     aman. Pada keadaan safe state tersebut, proses masih berjalan dengan normal, sehingga
     sistem dapat memulai proses dari posisi aman tersebut. Untuk menentukan pada saat apa
     proses akan rollback, tentunya ada faktor yang menentukan. Diusahakan untuk
     meminimalisasi kerugian yang timbul akibat memilih suatu proses menjadi korban. Harus pula
     dihindari keadaan dimana proses yang sama selalu menjadi korban, sehingga proses tersebut
     tidak akan pernah sukses menjalankan eksekusi.



PUSTAKA

Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005 . Operating Systems Concepts. Seventh Edition. John Wiley & Sons.
[Tanenbaum1997] Andrew S Tanenbaum dan Albert S Woodhull. 1997 . Operating Systems Design and Implementation . Second Edition. Prentice-Hall.
[WEBRpi2004] Computer Science RPI. 2004 . Deadlock http://www.cs.rpi.edu/academics/courses/fall04/os/c10/index.html.
[WEBWiki2006a] Wikipedia. 2006 . Deadlock http://en.wikipedia.org/wiki/Deadlock.
[WEBWiki2006b] Wikipedia. 2006 . Banker's Algorithm http://en.wikipedia.org/wiki/Banker%27s_algorithm.

Tidak ada komentar:

MIVO.TV