Kamis, 28 Mei 2009

Dead lock

Karakteristik Deadlock

Situasi deadlock dapat terjadi bila terdapat 4 kondisi yang berjalan serentak pada sistem.
Mutual Exclusion
Sebuah resource hanya dapat digunakan oleh sebuah proses pada suatu waktu tertentu. (resource yang non-shareable.)
Hold and Wait
terdapat proses yang sedang menunggu dan memegang resource.

Karakteristik Deadlock (cont.)

Non-preemption
Resource tidak dapat digunakan sebelum proses yang menggunakan telah selesai menggunakan dan kemudian melepaskannya.
Circular wait
Proses-proses berada dalam lingkaran. Terjadi saling menunggu resource yang sedang digunakan oleh proses berikutnya dalam lingkaran tersebut.

Pengendalian Deadlock
Mengabaikan, menganggap bahwa deadlock
tidak akan pernah terjadi.
Membiarkan terjadinya deadlock, lalu kemudian segera diperbaiki/recover.
Menggunakan protokol untuk meyakinkan bahwa sistem tidak akan pernahdeadlock.

Ostrich Algorithm

Algoritmapaling sederhana.
Mengabaikanterjadinyakondisideadlock.
Jadiapayang haruskitalakukanjikaterjadideadlock menurutOstrich algorithm?
Cukup di restart!

Mendeteksi dan memperbaiki

Mendeteksi apabiladalamsebuahproses
terjadi kondisiyang mengarahkecircular wait.
Apabila deadlock terjadi tentukan proses mana saja yang terlibat.
Setelah deadlock terdeteksi, biarkan proses yang mengalami deadlock selesai menggunakan resource, agar resource bisa digunakan. Atau stop semua proses yang terlibat deadlock.

Penggunaan Protokol

Deadlock Prevention
Menggunakan method supaya tidak terjadi salah
satu kondisi yang menyebabkan deadlock.
Deadlock Avoidance
Menghindari situasi yang dapat mengarah kepada terjadinya deadlock, sistem harus diberikan
informasi tambahan yang menyatakan resource
mana yang diminta proses, dan digunakan selama proses berjalan.

Deadlock prevention

Salah satu faktor-faktor penyebab deadlock
harus dapat dicegah.
Mutual Exclusion
Sifat alamiah sebuah resource (tidak bisa dicegah).Namun, ada beberapa resource yang dapat
di-spool.
Hold and Wait
Harus dipastikan bahwa ketika sebuah proses
merequest resource, proses itu tidak sedang memegang resource lain.

Deadlock prevention (cont.)

Non preemption
Mencegah supaya tidak ada proses dalam keadaan menunggu-mendapat-resource yang sedang digunakan oleh proses lain. (seluruh proses menjadi preemption).
Circular waiting
Mengatur agar setiap proses hanya dapat menggunakan sebuah sumber daya pada suatu waktu.
Melakukan penomoran resource.

Deadlock avoidance

Menyeleksi request resource dari proses-proses, apabila request itu ‘berbahaya’ maka requestnya akan ditunda dahulu hingga keadaan sudah aman.
Membutuhkan informasi tambahan mengenai aliran resource yang diminta.
Algoritma yang digunakan Algoritma Banker.

Deadlock detection

Jika tidak terdapat deadlock prevention atau avoidance dalam suatu sistem diperlukan suatu mekanisme untuk mengetahui terjadinya deadlock.
Menggunakan algoritmauntukmendeteksiadanyadeadlock.
Memeriksa penggunaan resource oleh proses-proses


Save vsUnsafe state

Ketika terjadi resource request, sistem harus memastikan proses berada dalam safe state
Safe state sistem dapat mengalokasikan resource untuk tiap-tiap proses dan mencegah terjadinya deadlock
Unsafe state sistem tidak dapat mengatur alokasi resource untuk tiap proses

Safe vs Unsafe state (cont.)

Jika sistem berada dalam kondisi safe state, berarti tidak terjadi deadlock.
Jika dalam kondisi unsafe state, kemungkinan bisa terjadi deadlock.


Banker’s algorithm

Setiap prosesharusmengklaimberapajumlahmaksimumresource yang akandigunakan.
Jikaresource tidaktersediamakapermintaanditunda.
Setiap prosesyang telahselesaiharusmengembalikanresource yang dipakai.

BANKER'S ALGORITHM

PROSES ALOKASI MAKS TERSEDIA
P1 2 5 2
P2 4 8
P3 2 3
P1 2 5 4
P2 4 8
P3 - -
P1 - - 6
P2 4 8
P3 - -

Kelemahan Banker’s algorithm

Proses kebanyakan belum mengetahui jumlah maksimum resource yang dibutuhkan.
Jumlah proses tidak tetap.
Beberapa resource dapat diambil dari sistem sewaktu-waktu.
Algoritma membuat sistem untuk memenuhi permintaan hingga waktu yang tidak terbatas.

Deadlock Recovery

Pemulihandeadlock dapatdilakukanmelalui:
Hapussemuaprosesyang terlibatdalamdeadlock.
Rollback danrestart proses.
Secarabertahaphapusproses-prosesyang terlibatdeadlock hinggatidakadadeadlock lagi.
Secaraberurutan, preempt resource-
resource sampaitidakadadeadlock.

Summary

Deadlock berpotensi terjadi pada sistem dengan multiproses akibat penggunaan resource bersama yang mengakibatkan konflik.
Ada beberapa cara untuk menghandle deadlock ini, namun tidak ada solusi umum mengenai deadlock.
Masing-masing teknik mempunyai kelemahan.

Sabtu, 02 Mei 2009

Round Robin

A. Round Robin (RR)

Merupakan :

· Penjadwalan yang paling tua, sederhana, adil, banyak digunakan

algoritmanya dan mudah diimplementasikan.

· Penjadwalan ini bukan dipreempt oleh proses lain tetapi oleh penjadwal

berdasarkan lama waktu berjalannya proses (preempt by time).

· Penjadwalan tanpa prioritas.

· Berasumsi bahwa semua proses memiliki kepentingan yang sama,

sehingga tidak ada prioritas tertentu.

Semua proses dianggap penting sehingga diberi sejumlah waktu oleh

pemroses yang disebut kwanta (quantum) atau time slice dimana proses itu

berjalan.Jika proses masih running sampai akhir quantum, maka CPU akan

mempreempt proses itu dan memberikannya ke proses lain.

Penjadwal membutuhkannya dengan memelihara daftar proses dari

runnable. Ketika quantum habis untuk satu proses tertentu, maka proses

tersebut akan diletakkan diakhir daftar (list), seperti nampak dalam gambar

berikut ini :

(a) (b)

Proses Proses Proses

saat berikutnya saat

ini ini

V V V

+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+

+---+

: B :--: F :--: D :--: G :--: A : : B :--: F :--: D :--: G :-

-: A :

+---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+

+---+

Gambar 3.(a) : Daftar proses runnable.

3.(b) : Daftar proses runnable sesudah proses b habis

quantumnya.

Algoritma yang digunakan :

1. Jika kwanta habis dan proses belum selesai, maka proses menjadi

runnable dan pemroses dialihkan ke proses lain.

2. Jika kwanta belum habis dan proses menunggu suatu kejadian

(selesainya operasi I/O), maka proses menjadi blocked dan pemroses

dialihkan ke proses lain.

3. Jika kwanta belum habis tetapi proses telah selesai, maka proses diakhiri

dan pemroses dialihkan ke proses lain.

Diimplementasikan dengan :

1. Mengelola senarai proses ready (runnable) sesuai urutan kedatangan.

2. Ambil proses yang berada di ujung depan antrian menjadi running.

3. Bila kwanta belum habis dan proses selesai, maka ambil proses di ujung

depan antrian proses ready.

4. Jika kwanta habis dan proses belum selesai, maka tempatkan proses

running ke ekor antrian proses ready dan ambil proses di ujung depan

antrian proses ready.

Masalah yang timbul adalah menentukan besar kwanta, yaitu :

_ Kwanta terlalu besar menyebabkan waktu tanggap besar dan turn arround

time rendah.

_ Kwanta terlalu kecil menyebabkan peralihan proses terlalu banyak

sehingga menurunkan efisiensi proses.

Switching dari satu proses ke proses lain membutuhkan kepastian waktu

yang digunakan untuk administrasi, menyimpan, memanggil nilai-nilai

register, pemetaan memori, memperbaiki tabel proses dan senarai dan

sebagainya. Mungkin proses switch ini atau konteks switch membutuhkan

waktu 5 msec disamping waktu pemroses yang dibutuhkan untuk menjalankan

proses tertentu.

Dengan permasalahan tersebut tentunya harus ditetapkan kwanta waktu

yang optimal berdasarkan kebutuhan sistem dari hasil percobaan atau data

historis. Besar kwanta waktu beragam bergantung beban sistem. Apabila nilai

quantum terlalu singkat akan menyebabkan terlalu banyak switch antar proses

dan efisiensi CPU akan buruk, sebaliknya bila nilai quantum terlalu lama akan

menyebabkan respon CPU akan lambat sehingga proses yang singkat akan

menunggu lama. Sebuah quantum sebesar 100 msec merupakan nilai yang

dapat diterima.

Penilaian penjadwalan ini berdasarkan kriteria optimasi :

_ Adil, adil bila dipandang dari persamaan pelayanan oleh pemroses.

_ Efisiensi, cenderung efisien pada sistem interaktif.

_ Waktu tanggap, memuaskan untuk sistem interaktif, tidak memadai untuk

sistem waktu nyata.

_ Turn around time cukup baik.

_ Throughtput cukup baik.

Penjadwalan ini :

a. Baik untuk sistem interactive-time sharing dimana kebanyakan waktu

dipergunakan menunggu kejadian eksternal. Contoh : text editor,

kebanyakan waktu program adalah untuk menunggu keyboard, sehingga

dapat dijalankan proses-proses lain.

b. Tidak cocok untuk sistem waktu nyata apalagi hard-real-time

applications.

Artikel Round Robin

Round Robin
Algoritma ini menggilir proses yang ada di antrian. Proses akan mendapat jatah sebesar time quantum. Jika time quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke proses berikutnya. Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU yaitu (1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.
Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja dengan algoritma first come first served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang.
Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai dalam 1 quantum. Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma first come first served. Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.
Gambar 14.4. Urutan Kejadian Algoritma Round Robin

Gambar 14.5. Penggunaan Waktu Quantum