PERKEMBANGAN IT: MUTUAL EXCLUSION, DEAD LOCK, STARVATION

MUTUAL EXCLUSION, DEAD LOCK, STARVATION

| di 13.38

ARTIKEL SISTEM OPERASI

$Description: D:\bsi\bsi\logo BSI.jpg$

Disusun oleh :

DARRA HANDIATIKA 13120691

Jurusan Teknik Komputer

Akademik Manajemen Informatika Dan Komputer Bina Sarana Informatika

Fatmawati

2014

MUTUAL EXCLUSION

Mutual exclusion adalah jaminan hanya satu proses yang mengakses sumber daya pada satu interval waktu tertentu. Fasilitas atau kemampuan menyediakan dukungan mutual exclusion harus memenuhi kriteria sbb:

· Mutual exclusion harus dijamin, bahwa tidak ada proses lain, kecuali dirinya

sendiri. Di sini terjadi proses tunggal.

· Proses yang berada di noncritical section.dilarang mem-blocked proses-proses

lain yang ingin masuk ctritical section.hal ini bias terjadi start vation.

· Harus dijamin bahwa proses yang Ingin masuk critical section tidak menunggu

selama waktu yang tak terhingga. Ini bias mengakibatkan masalah deadlock dan

antrian proses bertambah panjang.

· Ketika tidak ada proses pada critical section, maka proses yang ingin masuk

critical section harus ijinkan masuk tanpa waktu tunda.

· Tidak ada asumsi mengenai kecepatan relative proses atau jumlah proses yang

ada.

· Proses hanya tinggal pada critical section selama satu waktu yang tidak

terhingga.

MASALAH CRITICAL SECTION

Kunci untuk mencegah masalah ini dan disituasi yang lain yang melibatkan shared memori, shared berkas, dan shared sumber daya yang lain adalah menemukan beberapa jalan untuk mencegah lebh 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 berkas, proses lain dikeluarkan dari pekerjaan yang sama. Kesulitan yang terjadi karena proses 2 mulai menggunakan variabel bersama sebelum proses 1 menyelesaikan tugasnya. Masalah menghindari race conditions dapat juga diformulasikan secara abstrak bagian dari waktu, sebuah proses sedang sibuk melakukan perhitungan internal dan hal lain yang tidak menggiring ke kondisi race conditions.4 kondisi agar 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 di luar critical section yang dapat mengeblok

proses lain.

· Tidak ada proses yang menunggu selamanya untuk masuk critical section.

Critical section adalah sebuah segmen kode dimana sebuah proses yang mana

sumber daya bersama akses. Terdiri dari:

Entry section : kode yang digunakan untuk masuk ke dalam critical section.

Critical section: kode dimana hanya ada satu proses yang dapat dieksekusi pada

satu waktu .

Exit section : akhir dari critical section, mengizinkan proses lain.

Remainder section: kode istirahat setelah masuk ke critical section.

SOLUSI KE MASALAH CRITICAL SECTION

Ada beberapa solusi untuk mengatasi masalah critical section , yaitu:

· Mutual eclution

Jika proses pi sedang mengeksekusi critical section-nya maka tidak ada proses

lain yang dapat mengeksekusi dalam critical section mereka.

· Progress

Jika tidak ada proses yang sedang dieksekusi dalam critical section dan ada

beberapa proses yang ingin masuk ke critical section mereka, maka pemilihan

proses yang akan masuk ke critical section berikutnya tidak bias ditunda.

· Bounded waiting

Suatu keterikatan harus ada pada sejumlah proses yang diijinkan masuk ke

critical section mereka, setelah adanya proses yang meminta masuk critical

section dan sebelum permintaan itu diterima.

a. Asumsikan bahwa tiap proses mengeksekusi pada nonzero speed.

b. Tidak ada asumsi mengenai kecepatan relative dan proses.

Cara-cara memecahkan masalah

· Hanya dua proses, Po dan P1

· Struktur umum dari proses adalah Pi (proses lain Pj).

DEAD LOCK

Deadlock adalah suatu kondisi dimana dua proses atau lebih tidak dapat meneruskan eksekusinya oleh pemroses. Pada umumnya deadlock terjadi karena proses mengalami startvation , yaitu suatu job yang sedang dieksekusi dan eksekusi job tersebut tidak ada hentinya, tidak diketahui kapan berhentinya proses tersebut atau bahkan job yang antri bias dikatakan mempunyai statuss mati, padahal proses-proses lain sedang menunggu sumber daya proses.kondisi deadlock merupakan kondisi terparah karena banyak proses dapaat terlibat dan semuanya tidak dapat mengakhiri prosesnya secara benar.

Metode Mengendalikan Deadlock

1. Menggunakan suatu protocol untuk menyakinkan bahwa sistem tidak akan pernah

mengalami deadlock

2. Mengijinkan sistem mengalami deadlock, namun kemudian harus segera dapat memperbaikinya.

3. Mengabaikan semua masalah dan menganggap deadlock tidak akan pernah terjadi lagi di dalam sistem.

Strategi untuk menghadapi deadlock dapat dibagi menjadi tiga pendekatan, yaitu:

a. Mengakibatkan adanya deadlock.

b. Memastikan bahwa deadlock tidak akan pernah ada, baik dengan metode pencegahan, dengan mencegah empat kondisi deadlock agar tidak akan pernah terjadi. Metode menghindari deadlock yaitu mengizinkan empat kondisi deadlock , tetapi menghentikan setiap proses yang kemungkinan mencapai deadlock.

c. Membiarkan deadlock untuk terjadi, pendekatan ini membutuhkan dua metode yang

saling mendukung yaitu:

- Pendeteksian deadlock, untuk mengidentifikasi ketika deadlock terjadi.

- Pemulihan deadlock, mengembalikan kembali sumber daya yang dibutuhkan

pada proses yang memintanya.

Pencegahan deadlock

1. Meniadakan Mutual exclusion.

Harus tetap menjaga resource-resource yang bersifat non-shareable. Yaitu, proses menahan sebuah resource, proses lain yang meminta resource tersebut harus menunggu sampai proses melepaskannya,. Jika terjadi pada perangkat I/O dan berkas , maka sulit untuk menghindari mutual exclusion pada sumber daya non shareable.

2. Meniadakan Syarat Hold & Wait

Apabila suatu proses minta ijin untuk mengakses suatu resource, maka proses tersebut tidak boleh membawa resource yang lainnya. Sebelum proses meminta resource, maka harus melepas semua resource yang dibawa.

3. Meniadakan Non Preemption

Jika siatu proses minta ijin mengakses resource, sementara resource tersebut tidak dapat dipenuhi secepatnya, maka proses tersebut harus membebaskan semua resourcenya terlebih dahulu.

4. Meniadakan Circular Wait

Memberi nomor pada setiap resource yang ada, dan setiap resource hanya boleh mengakses resource secara berurutan.

Mendeteksi Deadlock dan Memulihkan Deadlock

Metode deteksi digunakan pada sistem yang mengijinkan terjadinya deadlock. Tujuan metode ini adalah memeriksa apakah telah terjadi deadlock dan menentukan proses-proses dan sumber daya-sumber daya yang terlibat deadlock secara presisi. Begitu telah dapat ditentukan sistem dipulihkan dari deadlock dengan metode pemulihan. Metode pemulihan dari deadlock berupaya untuk menghilangkan deadlock dari sistem sehingga sistem beroperasi kembali, bebas dari deadlock. Proses-proses yang terlibat deadlock mungkin dapat menyelesaikan eksekusi dan membebaskan sumber daya-sumber dayanya.

Peranan Deadlock

Menurut Coffinan dalam bukunya “Operating System” menyebutkan empat syarat bagi terjadinya deadlock, yaitu :

a. Mutual Exclusion

b. Suatu kondisi dimana setiap sumber daya diberikan tepat pada satu proses pada suatu waktu

c. Hold and Wait

d. Kondisi yang menyatakan proses-proses yang sedang memakai suatu sumber daya dapat meminta sumber daya yang lain

e. Non-pre-emptive

f. Kondisi dimana suatu sumber daya yang sedang memakai suatu proses tidak dapat diambil secara paksa dari proses tersebut sampai prose situ melepaskannya

g. Circular Wait

h. Kondisi yang menyatakan bahwa adanya rantai saling meminta sumber daya yang dimiliki oleh suatu proses oleh proses lainnya.

Metode pencegahan deadlock dan masalah-masalah yang menghambatnya, terangkum dalam table dibawah ini :

Syarat	Langkah	Kelemahan
Mutual Exclusion	Spooling sumber daya	Dapat menyebabkan chaos
Hold and Wait	Meminta sumber daya diawal	Sulit memperkirakan diawal dan tidak optimal
No Pre-emptive	Mengambil sumber daya ditengah proses	Hasil proses tidak akan baik
Circular wait	Penomoran permintaan sumber daya	Tidak ada penomoran yang memuaskan semua pihak

Menghindari Deadlock

Pendekatan metode ini adalah dengan hanya member kesempatan ke permintaan sumber daya yang tidak mungkin akan menyebabkan deadlock. Metode ini memeriksa dampak pemberian akses pada suatu proses. Jika pemberian akses tidak mungkin menuju kepada deadlock, maka sumber daya akan diberikan pada proses yang meminta. Jika tidak aman, proses yang meminta akan di-suspend sampai suatu waktu permintaannya aman untuk diberika.

STARVATION

Starvision adalah kondisi yang biasa terjadi setelah deadlock. Proses yang kekurangan resource (karena terjadi deadlock) tidak akan pernah mendapatkan resource yang dibutuhkan sehingg mengalami starvation (kelaparan). Ilustrasi dengan deadlock seperti gambar dibawah ini:

Description: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8xW5KBhdfJ8I1mT_G8Dvlz4fn1Kyhsg1oW3w9AhP1M9uSvwQ1WRFk5Mgzr1h19A5t8w2B6a2y2aqbNIBsTuODa0WcTjJMFAL1aW0Gu-ZXK_SjZPCUNv7BtfMS4mt90NiFQYv0lWNMqsU/s320/star1.png

Dalam kasus diatas, antrian di sebelah kiri menunggu antrian kanan untuk mengosongkan jembatan (resource), begitu juga dengan antrian kanan. Akhirnya tidak terjadi kemajuan dalam kerja dua antrian tersebut.Misal ada proses A mempunyai resource X, proses B mempunyai resource Y. Kemudian kedua proses ini dijalankan bersama, proses A memerlukan resource Y dan proses B memerlukan resource X,tetapikedua proses tidak akan memberikan resource yang dimiliki sebelum proses dirinya sendiri selesai dilakukan. Sehingga akan terjadi tunggu-menunggu.

Algoritma Starvation

Starvation dapat terjadi pada proses penjadwalan yang menggunakan prinsip “proses yang paling cepat diselesaikan didahulukan”, seperti pada Shortest Job First (SJF) dan Penjadwalan Prioritas.

Logikanya, jika kita mempunyai banyak kebutuhan, kita akan memilahnya mana yang didahulukan berdasarkan sesuatu. Setelah kita selesai menyusunnya, ternyata ada kebutuhan lain yang datang (misalkan kebutuhan A) dan ternyata kebutuhan itu mengalahkan salah satu kebutuhan kita. Sebelum kebutuhan A terpenuhi, datang lagi kebutuhan lain yang mengalahkan kebuthan awal. Jika hal ini terjadi secara terus menerus, maka ada kebuthan awal kita yang tidak terpenuhi (starvation).

Contoh nyatanya, pada kehidupan mahasiswa. Seorang mahasiswa telah memiliki 3 tugas dan ingin juga menonton film baru. Mahasiswa tersebut mendahulukan menyelesaikan tugas dibandingkan menonton. Sebelum ketiga tugas tersebut selesai, dosen lain memberinya tugas baru. Keesokan harinya ada tugas dari asisten untuk praktikum berikutnya. Ketika tugas satu belum selesai, sudah ada tugas lain dari dosen atau asisten. Hal ini terus berulang, sehingga keinginan mahasiswa tersebut untuk menonton film baru bisa tidak terlaksana atau tidak terpenuhi.
Mengatasi Starvision

Description: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjx8sQxCMH39i-Fa0eVHbem3ndGgg0ggTSWd_eFLoyGXWibyzdyxXmOEqTZm7XQ0JcLxG4i64SZJOvTPbLsW1x18L8byA9PuV1nL0cSVIlNMrCbjDeNWqnKGJprL1Ta2nrzyeymGDuCRzg/s400/star3.png

Ada beberapa cara untuk mengatasi Starvation, salah satunya dengan Aging. Pada flowchart di atas, proses awal yang ada diberi urutan ( N ) pemrosesan dengan rumus N = ( P+T ) / P. N maksimum akan mulai dikerjakan dan proses yang lain dinaikkan tingkat urutan prosesnya agar nanti jika ada proses lain yang masuk, proses terdahulu mendapatkan bagian resource dan dapat dikerjakan. Jika ada beberapa proses yang memiliki N maksimum, maka diantara proses tersebut dilihat dari waktu yang dibutuhkan untuk menyelesaikannya. Jika masih sama juga, maka dilihat waktu kedatangannya.

Description: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhFbm8R96yvcUFPWo6Fox_Pyw1dvp3Ttlz38YymNKtXPTyvLxX7eh8mqMntMfSnPdcezR9wP_HrOKy-DY1R2jgS0XHgefReK5ifeRSLjqtBKeGiHPXr8eKYcD96jltrmkbvrSLbZSR-wNY/s400/star4.png

Selain itu, Starvation juga dapat diatasi dengan pemrosesan dengan cara Round Robin. Pada Round Robin, proses yang masuk akan dimasukkan ke dalam antrian menurut kedatangan proses tersebut. Dalam penyelesainnya, suatu proses tidak akan langsung selesai jika waktu yang dibutuhkan melebihi waktu kuantum yang diberikan. Waktu kuantum adalah waktu yang diberikan untuk menyelesaikan suatu proses. Ketika sutu proses telah mencapai batas waktu kuantum, sisa dari proses tersebut dikembalikan ke antrian paling belakang dan resource dipindahkan ke proses selanjutnya. Dengan cara ini, semua proses yang mengantri, akan mendapatkan resource secara bergantian ( tidak ada proses yang memonopoli resource ) sehingga semua proses dapat diselesaikan.