DEADLOCK PADA SISTEM OPERASI

Deadlock pada Sistem Operasi

Deadlock adalah keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya. Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah. Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses. Deadlock bisa digambarkan sebagai berikut :

·         Kejadian Deadlock selalu tidak lepas dari sumber daya, bahwa hampir seluruhnya merupakan masalah sumber daya yang digunakan bersama-sama. Oleh karena itu, kita juga perlu tahu tentang jenis sumber daya yaitu: sumber daya dapat digunakan lagi berulang-ulang dan sumber daya yang dapat digunakan dan habis dipakai atau dapat dikatakan sumber daya sekali pakai. Sumber daya ini tidak habis dipakai oleh proses mana pun.Tetapi setelah proses berakhir, sumber daya ini dikembalikan untuk dipakai oleh proses lain yang sebelumnya tidak kebagian sumber daya ini.

Contohnya prosesor, Channel I/O, disk, semaphore. Contoh peran sumber daya jenis ini pada terjadinya Deadlock ialah misalnya sebuah proses memakai disk A dan B, maka akan terjadi Deadlock jika setiap proses sudah memiliki salah satu disk dan meminta disk yang lain. Masalah ini tidak hanya dirasakan oleh pemrogram tetapi oleh seorang yang merancang sebuah sistem operasi. Cara yang digunakan pada umumnya dengan cara memperhitungkan dahulu sumber daya yang digunakan oleh
proses-proses yang akan menggunakan sumber daya tersebut. Contoh lain yang menyebabkan Deadlock dari sumber yang dapat dipakai berulang-ulang ialah berkaitan dengan jumlah proses yang memakai memori utama.

Ada empat kondisi yang dapat menyebabkan terjadinya deadlock. Keempat kondisi tersebut tidak dapat berdiri sendiri, namun saling mendukung.

1.      Mutual exclusion. Hanya ada satu proses yang boleh memakai sumber daya, dan proses lain yang ingin memakai sumber daya tersebut harus menunggu hingga sumber daya tadi dilepaskan atau tidak ada proses yang memakai sumber daya tersebut.

2.      Hold and wait. Proses yang sedang memakai sumber daya boleh meminta sumber daya lagi maksudnya menunggu hingga benar-benar sumber daya yang diminta tidak dipakai oleh proses lain, hal ini dapat menyebabkan kelaparan sumber daya sebab dapat saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama.

3.      No preemption. Sumber daya yang ada pada sebuah proses tidak boleh diambil begitu saja oleh proses lainnya. Untuk mendapatkan sumber daya tersebut, maka harus dilepaskan terlebih dahulu oleh proses yang memegangnya, selain itu seluruh proses menunggu dan mempersilahkan hanya proses yang memiliki sumber daya yang boleh berjalan.

4.       Circular wait. Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya.

A.    Strategi mengatasi Deadlock :

Addabeberapa cara untuk menanggulangi terjadinya deadlock, diantaranya adalah:

·         Mengabaikan masalah deadlock.

·         Mendeteksi dan memperbaiki Penghindaran yang terus menerus dan pengalokasian yang baik dengan menggunakan protokol untuk memastikan sistem tidak pernah memasuki keadaan deadlock. Yaitu dengan deadlock
avoidance sistem untuk mendata informasi tambahan tentang proses mana yang akan meminta dan menggunakan sumber daya.

·         Pencegahan yang secara struktur bertentangan dengan empat kondisi terjadinya deadlock dengan deadlock prevention sistem untuk memastikan bahwa salah satu kondisi yang penting tidak dapat menunggu.

B.     Mengabaikan Masalah Deadlock

Untuk memastikan sistem tidak memasuki deadlock, sistem dapat menggunakan pencegahan deadlock atau penghindaran deadlock. Penghindaran deadlock membutuhkan informasi tentang sumber daya yang mana yang akan suatu proses meminta dan berapa lama akan digunakan. Dengan informasi tersebut dapat diputuskan apakah suatu proses harus menunggu atau tidak. Hal ini disebabkan oleh keberadaan sumber daya, apakah ia sedang digunakan oleh proses lain atau tidak. Metode ini lebih dikenal dengan Algoritma Ostrich. Dalam algoritma ini dikatakan bahwa untuk menghadapi Deadlock ialah dengan berpura-pura bahwa tidak ada masalah apa pun. Hal ini seakanakan melakukan suatu hal yang fatal, tetapi sistem operasi Unix menanggulangi Deadlock dengan cara ini dengan tidak mendeteksi Deadlock dan membiarkannya secara otomatis mematikan program sehingga seakan-akan tidak terjadi apa pun. Jadi jika terjadi Deadlock, maka tabel akan penuh, sehingga proses yang menjalankan proses melalui operator harus menunggu pada waktu tertentu dan mencoba lagi.

C.    Mendeteksi dan Memperbaiki

Caranya ialah dengan cara mendeteksi jika terjadi deadlock pada suatu proses maka dideteksi sistem mana yang terlibat di dalamnya. Setelah diketahui sistem mana saja yang terlibat maka diadakan proses untuk memperbaiki dan menjadikan sistem berjalan kembali. Jika sebuah sistem tidak memastikan deadlock akan terjadi, dan juga tidak didukung dengan  pendeteksian deadlock serta pencegahannya, maka kita akan sampai pada kondisi deadlock yang dapat berpengaruh terhadap performance sistem karena sumber daya tidak dapat digunakan oleh proses sehingga proses-proses yang lain juga terganggu. Akhirnya sistem akan berhenti dan harus direstart.
Hal-hal yang terjadi dalam mendeteksi adanya Deadlock adalah:

·         Permintaan sumber daya dikabulkan selama memungkinkan.

·         Sistem operasi memeriksa adakah kondisi circular wait secara periodik.

·         Pemeriksaan adanya deadlock dapat dilakukan setiap ada sumber daya yang

·         hendak digunakan oleh sebuah proses.

·         Memeriksa dengan algoritma tertentu.

Ada beberapa jalan untuk kembali dari Deadlock, yaitu:

·         Lewat Preemption

Dengan cara untuk sementara waktu menjauhkan sumber daya dari pemakainya, dan memberikannya pada proses yang lain. Ide untuk memberi pada proses lain tanpa diketahui oleh pemilik dari sumber daya tersebut tergantung dari sifat sumber daya itu sendiri. Perbaikan dengan cara ini sangat sulit atau dapat dikatakan tidak mungkin. Cara ini dapat dilakukan dengan memilih korban yang

Akan dikorbankan atau diambil sumber dayanya untuk sementara, tentu saja harus dengan perhitungan yang cukup agar waktu yang dikorbankan seminimal mungkin. Setelah kita melakukan preemption dilakukan pengkondisian proses tersebut dalam kondisi aman. Setelah itu proses dilakukan lagi dalam
kondisi aman tersebut.

·         Lewat Melacak Kembali

Setelah melakukan beberapa langkah preemption, maka proses utama yang diambil sumber dayanya akan berhenti dan tidak dapat melanjutkan kegiatannya, oleh karena itu dibutuhkan langkah untuk kembali pada keadaan aman dimana proses masih berjalan dan memulai proses lagi dari situ. Tetapi untuk beberapa keadaan sangat sulit menentukan kondisi aman tersebut, oleh karena itu umumnya dilakukan cara mematikan program tersebut lalu memulai kembali proses. Meski pun sebenarnya lebih efektif jika hanya mundur beberapa langkah saja sampai deadlock tidak terjadi lagi. Untuk beberapa sistem mencoba dengan cara mengadakan pengecekan beberapa kali secara periodik dan menandai tempat terakhir kali menulis ke disk, sehingga saat terjadi deadlock dapat mulai dari tempat terakhir penandaannya berada.

·         Lewat mematikan proses yang menyebabkan Deadlock

Cara yang paling umum ialah mematikan semua proses yang mengalami deadlock. Cara ini paling umum dilakukan dan dilakukan oleh hampir semua sistem operasi. Namun, untuk beberapa sistem, kita juga dapat mematikan beberapa proses saja dalam siklus deadlock untuk menghindari deadlock dan mempersilahkan proses lainnya kembali berjalan. Atau dipilih salah satu korban untuk melepaskan sumber dayanya, dengan cara ini maka masalah pemilihan korban menjadi lebih selektif, sebab telah diperhitungkan beberapa kemungkinan jika si proses harus melepaskan sumber dayanya. Kriteria pemilihan korban ialah:

Ø  Yang paling jarang memakai prosesor

Ø  Yang paling sedikit hasil programnya

Ø  Yang paling banyak memakai sumber daya sampai saat ini

Ø  Yang alokasi sumber daya totalnya tersedkit

Ø  Yang memiliki prioritas terkecil

·         Menghindari Deadlock

Pada sistem kebanyakan permintaan terhadap sumber daya dilakukan sebanyak sekali saja. Sistem sudah harus dapat mengenali bahwa sumber daya itu aman atau tidak (tidak terkena deadlock), setelah itu baru dialokasikan. Ada dua cara yaitu:

Ø  Jangan memulai proses apa pun jika proses tersebut akan membawanya pada kondisi deadlock, sehingga tidak mungkin terjadi deadlock karena pada saat akan menuju deadlock, proses sudah dicegah.

Ø  Jangan memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika penambahan ini akan membawa kita pada suatu keadaan deadlock. Jadi diadakan dua kali penjagaan, yaitu saat pengalokasian awal, dijaga agar tidak deadlock dan ditambah dengan penjagaan kedua saat suatu proses meminta sumber daya, dijaga agar jangan sampai terjadi deadlock. Pada sistem deadlock avoidance (penghindaran) dilakukan dengan cara memastikan bahwa program memiliki maksimum permintaan. Dengan kata lain cara sistem ini memastikan terlebih dahulu bahwa sistem akan selalu dalam kondisi aman. Baik mengadakan permintaan awal atau pun saat meminta permintaan sumber daya

tambahan, sistem harus selalu berada dalam kondisi aman.

Sumber : http://nugan88.wordpress.com/2011/10/03/deadlock-pada-sistem-operasi/

Tgl akses : 24 april 2013 11:04

MUTUAL EXCLUSION

MUTUAL EXCLUSION

A.        Definisi

Beberapa proses terkadang membutuhkan sumber daya yang sama pada saat bersamaan. Sumber daya seperti ini disebut sumber daya kritis. Bagian program yang menggunakan sumber daya kritis disebut memasuki critical region/section. Hanya satu program pada saat yang diijinkan masuk critical region. Kondisi yang tidak dapat diprediksi hasilnya, bergantung pada proses-proses berjalan yang sedang bersaing disebut Kondisi Pacu (Race Condition). Kondisi pacu harus dihilangkan agar hasil-hasil proses dapat diprediksi dan tidak bergantung pada jalanya proses-proses tersebut. Sistem operasi hanya menyediakan layanan (berupa system call) untuk mencegah proses masuk critical section yang sedang dimasuki proses lain. Pemrogram harus menspesifikasikan bagian-bagian critical region sehingga sistem operasi akan menjaganya dengan suatu mekanisme untuk mencegah proses lain masuk critical region yang sedang dipakai proses lain. inilah yang dimaksud dengan mutual exclusion. Mutual Exclusion adalah suatu cara yang menjamin jika ada sebuah proses yang menggunakan variabel atau berkas yang sama (digunakan juga oleh proses lain), maka proses lain akan dikeluarkan dari pekerjaanyangsama.

KriteriapenyelesaianMutualExclusion : Mutual Exclusionharus dijamin. Hanya satu proses pada satu saat yang diizinkan masuk Critical Section/Region. Proses yang berada di noncritical section, dilarang memblok proses-proses yang ingin masuk critical section. Harus dijamin proses yang ingin masuk critical section tidak menunggu lama hingga waktu tak terhingga, agar tidak terjadi deadlock atau starvation. Ketika ada proses di critical section maka proses yang ingin masuk critical section harus diijinkan segera masuk tanpa waktu tunda tidak ada asumsi mengenai kecepatan relative proses atau jumlah proses yang ada.

B.         Metode-metode Penjamin Mutual Exclusion

1.        Metode Naif

Sebenarnya metode ini tidak menyelesaikan mutual exclusion, karena masih terdapat scenario proses yang membuat situasi kacau. Metode ini sering disebut metode variable lock sederhana. Ketika proses hendak masuk critical section, proses lebih dulu memeriksa variable lock dengan ketentuan :

Jika variable lock bernilai 0, proses mengeset variable lock menjadi 1 dan segera masuk critical section. Jika variable lock bernilai 1, proses menunggu sampai nilai variabel lock menjadi 0.

2.        Metode untuk situasi tertentu

Metode ini sering disebut metode bergantian secara ketat yang mengasumsikan proses-proses yang hendak masuk critical section secara bergantian terus menerus. Proses memeriksa terus menerus sehingga kondisi siap untuk diproses. Kondisi ini tidak dapat ditentukan lamanya waktu sehingga menyia-nyiakan waktu pemroses. Suatu saat kondisi akan crash ketika ada proses yang harus segera masuk sementara ada proses lain yang masih berjalan.

3.        Metode Busy Waiting

a.       Metode Penyelesaian Dekker

Algoritma Dekker mempunyai property-property berikut : Tidak memerlukan instruksi-instruksi perangkat keras khusus. Proses yang beroperasi di luar critical section tidak dapat mencegah proses lain memasuki critical section. Proses yang ingin masuk critical section akan segera masuk bila dimungkinkan.

b.      Metode Penyelesaian Peterson

Sebelum masuk critical section, proses memanggil enter_critical_section, namun sebelumnya proses memeriksa sampai kondisi aman. Terjadi busy waiting, setelah selesai proses menandai pekerjaan dan mengijinkan proses lain masuk. Keadaan awal tidak ada proses di critical section. Proses 0 akan masuk critical section. Proses menandai elemen arraynya dan mengeset turn ke 0. Proses memeriksa kondisi, dan prosedur enter_critical_section dilaksanakan. Jika kemudian, proses 1 akan masuk, proses akan menunggu sampai interest(0) menjadi FALSE. Kondisi ini hanya terjadi jika proses 0 mengeset elemen itu dan keluar dari critical section.

c.       Metode Pematian Interupsi

Proses mematikan interupsi ke pemroses dan segera masuk ke critical section. Proses kembali mengaktifkan interupsi segera setelah meninggalkan critical section. Metode ini mengakibatkan. Pemroses tidak dapat beralih ke proses lain karena interupsi clock dimatikan sehingga penjadual pun tidak dieksekusi. Karena penjadual tidak beroperasi maka tidak terjadi alih proses. Proses dapat memakai memori bersama tanpa takutü terinvensi proses lain karena memang tidak ada proses lain yang dieksekusi saat itu.

Kelemahan utama :

Bila proses yang mematikan interupsi mengalami gangguan maka proses tidak akan pernah menghidupkan interupsi kembali. Kejadian ini mengakibatkan kematian seluruh system. Jika terdapat dua pemroses atau lebih, mematikan interupsi hanya berpengaruh pada pemrosesan yang sedang mengeksekusi intruksi itu. Proses lain masih dapat memasuki critical section.

d.      Metode Test and Set Lock (TSL)

Metode ini membaca isi memori ke register dan kemudian menyimpan nilai bukan 0  ke alamat memori. Pemroses yang mengeksekusi instruksi tsl mengunci bus memori, mencegah pemroses lain mengkases memori.

e.       Metode Exchange (XCHG)

Metode ini menggunakan instruksi exchange (xchg). Instruksi xchg menukarkan dua isi memori.

f.       Metode Instruksi Mesin

Keunggulan :

·         Sederhana dan mudah diverifikasi

·          Dapat diterapkan ke sembarang jumlah proses

·          Dapat digunakan untuk mendukung banyak critical region

Kelemahan :

·         Merupakan metode dengan busy waiting, sangat tidak efisien.

·          Adanya busy waiting memungkinkan terjadi deadlock dan starvation.

 

4.        Metode Penyelesaian Level Tinggi (Metode Semapore)

Dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Proses berhenti sampai proses memperoleh penanda tertentu. Variabel khusus untuk penandaan ini disebut semaphore. Semaphore mempunyai dua property :

a.       Semaphore dapat diinisialisasi dengan nilai bukan negative.

b.      Ada dua operasi terhadap semaphore yaitu Operasi Up dan Operasi Down.

·         Operasi Down

Operasi ini menurunkan nilai semaphore. Jika nilai semaphore menjadi bukan positif maka proses yang mengeksekusinya diblok. Operasi Down adalah atomic (atomic action), tidak dapat diinterupsi sebelum selesai. Menurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblok sebagai instruksi tunggal. Tidak ada proses lain yang dapat diakses sampai proses selesai.

·         Operasi Up

Operasi ini menaikkan nilai semaphore. Jika satu proses atau lebih telah diblok pada suatu semaphore tidak dapat menyelesaikan operasi down maka salah satu dipilih oleh system dan dibolehkan menyelesaikan operasi downnya. Operasi Up menaikan nilai semaphore, memindahkan dari antrian dan menempatkan satu proses ke senarai ready tidak dapat diinterupsi.

Sebelum masuk critical section, proses melakukan down. Bila berhasil maka proses masuk critical section. Bila tidak berhasil maka proses diblok pada semaphore. Proses yang diblok dapat melanjutkan jika proses yang berada di critical section keluar dan melakukan operasi up dan menjadikan proses yang diblok menjadi ready dan berlanjut hingga operasi downnya berhasil.

C.        Implementasi Semaphore

1.      Pematian Interupsi

Sistem operasi mematikan interupsi selagi memeriksa semaphore, memperbarui, dan menjadikan proses diblok. Karena semua aksi hanya memerlukan beberapa instruksi, pematian interupsi tidak merugikan.

2.      Instruksi tsl

Pada banyak pemroses, tiap semaphore dilindungi variable lock dan instruksi tsl agar menjamin hanya satu pemroses yang saat itu memanipulasi semaphore.

Sumber : http://godaizone.blogspot.com/2010/12/mutual-exclusion.html

diambil dari: Modul 04/Sistem Operasi – Yuli Haryanto, S.Kom./Tatap Muka 9

Diposkan oleh blog pikun

Tgl akses : 24 April 2013 11:04