SISTEM OPERASI BAB 6-DEADLOCK

Deadlock

1. Apa yang dimaksud dengan sumber daya ? Berikan contohnya!

2. Apa yang dimaksud deadlock ?

3. Sebutkan 4 kondisi yang menyebabkan deadlock?

4. Sebutkan cara mencegah deadlock dari 4 kondisi tersebut pada soal 3?

5. Diketahui snapshot dari suatu sistem :

Allocation Max Available

A B C D A B C D A B C D

P0 0 0 1 2 0 0 1 2 1 5 2 0

P1 1 0 0 0 1 7 5 0

P2 1 3 5 4 2 3 5 6

P3 1 6 3 2 1 6 5 2

P4 0 0 1 4 0 6 5 6

Jawablah pertanyaan berikut :

a. Bagaimana isi matrik Need ?

b. Apakah sistem dalam state selamat ?

c. Jika proses P1 meminta (0,4,2,0) dapatkah permintaan dipenuhi segera ?

JAWAB

1. Sumber daya (resources) adalah sesuatu proses yang digunakan untuk proses-proses untuk menyelesaikan task.Sumber daya yang ada pada sistem terdiri dari tipe resource CPU cycle, ruang memori, perangkat I/O yang disebut dengan tipe sumber daya R1, R2, . . ., Rm.

2. Deadlock adalah proses dimana saling terjadinya penungguan antara proses-proses yang ingin menggunakan resources (sumber daya), proses yang sedang menunggu tidak mau saling mengalah maka akan terjadi deadlock.

3. 4 kondisi yang menyebabkan terjadinya deadlock :

a. Mutual Exclusion : hanya satu proses pada satu waktu yang dapat menggunakan sumberdaya.

b. Genggam dan Tunggu (Hold and Wait) : suatu proses membawa sedikitnya satu sumberdaya menunggu mendapatkan tambahan sumber daya baru yang dibawa oleh proses.

c. Non-Preemption : sebuah sumber daya dapat dibebaskan dengan sukarela oleh proses yangmemegangnya setelah proses menyelesaikan task.

d. Menunggu Secara Sirkuler (Circular Wait) : Terdapat sekumpulan proses {P0, P1, …, P0}yang menunggu sumber daya dimana P0 menunggu sumber daya yang dibawa P1, P1 menunggu sumber daya yang dibawa P2, dan seterusnya, Pn–1 menunggu sumber dayayang dibawa oleh Pn, dan Pn menunggu sumber daya yang dibawa P0.

4. Cara mencegah terjadinya deadlock :

a. Mencegah Mutual Exclusion

Mutual exclusion benar-benar tak dapat dihindari. Hal ini dikarenakan tidak ada sumber dayayang dapat digunakan bersama-sama, jadi sistem harus membawa sumber daya yang tidak dapat digunakan bersama-sama.

b. Mencegah Hold and Wait

Untuk mencegah hold and wait, sistem harus menjamin bila suatu proses meminta sumberdaya, maka proses tersebut tidak sedang memegang sumber daya yang lain. Proses harus meminta dan dialokasikan semua sumber daya yang diperlukan sebelum proses memulai eksekusi atau mengijinkan proses meminta sumber daya hanya jika proses tidak membawasumber daya lain. Model ini mempunyai utilitas sumber daya yang rendah dan kemungkinan terjadi starvation jika proses membutuhkan sumber daya yang popular sehingga terjadi keadaan menunggu yang tidak terbatas karena setidaknya satu dari sumberdaya yang dibutuhkannya dialokasikan untuk proses yang lain.

c. Mencegah Non Preemption

Peniadaan non preemption mencegah proses-proses lain harus menunggu. Seluruh proses menjadi preemption, sehingga tidak ada tunggu menunggu. Cara mencegah kondisi non preemption :

Jika suatu proses yang membawa beberapa sumber daya meminta sumber daya lainyang tidak dapat segera dipenuhi untuk dialokasikan pada proses tersebut, maka semuasumber daya yang sedang dibawa proses tersebut harus dibebaskan.

Proses yang sedang dalam keadaan menunggu, sumber daya yang dibawanya ditunda dan ditambahkan pada daftar sumber daya.

Proses akan di restart hanya jika dapat memperoleh sumber daya yang lama dan sumberdaya baru yang diminta.

d. Mencegah Kondisi Menunggu Sirkular

Sistem mempunyai total permintaan global untuk semua tipe sumber daya. Proses dapat meminta proses kapanpun menginginkan, tapi permintaan harus dibuat terurut secara numerik. Setiap proses yang membutuhkan sumber daya dan memintanya maka nomor urut akan dinaikkan. Cara ini tidak akan menimbulkan siklus. Masalah yang timbul adalah tidak ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.

5. a. Isi matrik Need didefinisikan dengan Max – Allocation :

Need

A B C

P0 7 4 3

P1 1 2 2

P2 6 0 0

P3 0 1 1

P4 4 3 1

Sistem dalam keadaan state selamat dengan urutan <> yang memenuhi kriteria algoritma safety.

Misalnya proses P1 meminta tambahan anggota tipe sumber daya A dan dua anggota tipesumber daya C sehingga Request1 = (1, 0, 2). Untuk menentukan apakah permintaan dapat segera dipenuhi, pertama harus diperiksa apakah Request1 ≤ Available ((1, 0, 2) ≤ (3, 3, 2)) ternyata benar. Maka akan diperoleh state baru berikut :

Allocation Need Available

A B C A B C A B C

P0 0 1 0 7 4 3 2 3 0

P1 3 0 2 0 2 0

P2 3 0 1 6 0 0

P3 2 1 1 0 1 1

P4 0 0 2 4 3 1

Kemudian harus ditentukan apakah sistem berada dalam state selamat. Setelah mengeksekusi algoritma safety ternyata urutan memenuhi criteria safety. Setelah sistem berada pada state doatas, permintaan (3, 3, 0) oleh P4 tidak dapat dipenuhi karena sumber daya tidak tersedia. Permintaan (0, 2, 0) oleh P1 juga tidak dapat dipenuhi karena meskipun sumber daya tersedia, state hasil tak selamat.

b. Sistem dalam state tidak selamat

c. Dapat

JAWABAN SO BAB 5

1.  Yg d maksd dgn race c0nditi0n.

Jawab: Race Condition adalah situasi di mana beberapa proses mengakses dan memanipulasi data bersama pada saat besamaan. Nilai akhir dari data bersama tersebut tergantung pada proses yang terakhir selesai. Unutk mencegah race condition, proses-proses yang berjalan besamaan haus di disinkronisasi.

2.  Yg dimaksud Critical secti0n, untk mnyelesaikn masalah critical secti0n ada 3 hal yg hrus dipenuhi, sbut dan jelaskn

Jawab:

Critical secti0n adalah Suatu system terdiri dari n proses dimana semuanya berkompetisi menggunakan

data yang digunakan bersama-sama, Masing-masing proses mempunyai sebuah kode

segmen.

3 hal yg harus d penuhi adalah

1. Mutual Exclusion. Apabila proses Pi menjalankan critical section-nya, maka tidak

ada proses lain yang dapat menjalankan critical section.

2. Progress. Apabila tidak ada proses yang menjalankan critical section-nya dan

terdapat beberapa proses yang akan memasuki critical section-nya, maka hanya

proses-proses itu yang tidak diproses di dalam daerah pengingat (remainder) dapat

ikut berpartisipasi di dalam keputusan proses mana yang akan memasuki critical

section selanjutnya, dan pemilihan ini tidak dapat ditunda tiba-tiba.

3. Bounded Waiting. Terdapat batasan jumlah waktu yang diijinkan oleh proses lain

untuk memasuki critical section setelah sebuah proses membuat permintaan untuk

memasuki critical section-nya dan sebelum permintaan dikabulkan.

3.  Bagaimana algoritma bakery untuk sinkronisasi banyakk pr0ses (n proses)

Jawab:

Pada algoritma bakery terdapat notasi <≡ untuk urutan nomor (ticket #, process id #)

sebagai berikut :

• (a,b) < (c,d) if a < c or if a = c and b < d

• max (a0,…, an-1) is a number, k, such that k ≥ ai for i - 0,

…, n – 1

Variabel umum yang digunakan adalah :

boolean choosing[n];

int number[n];

Struktur data diatas diinisialisasi false dan 0. Struktur dari proses Pi adalah :

do {

choosing[i] = true;

number[i] = max(number[0], number[1], …, number [n – 1])+1;

choosing[i] = false;

for (j = 0; j < n; j++) {

while (choosing[j]) ;

while ((number[j] != 0) && (number[j],j < number[i],i)) ;

}

critical section

number[i] = 0;

remainder section

} while (1);

4.  Apa yg dimaksud semaph0re dan sebutkan operasi pada semaphore.

Jawab:

Semaphore adalah sebuah struktur data komputer yang digunakan untuk sinkronisasi proses, yaitu untuk memecahkan masalah di mana lebih dari satu proses atau thread dijalankan secara bersamaan dan harus diatur urutan kerjanya.

Oprasi pd semaphore adalah

 Operasi Down (P)

• operasi ini menurunkan nilai semaphore
• jika nilai semaphore menjadi non positif maka proses yang mengeksekusinya diblocked

Operasi Up (V)

• Operasi ini menaikkan nilai semaphore
• jika satu proses atau lebih telah di blocked pada suatu semaphore tak dapat menyelesaikan operasi Down, maka salah satu dipilih oleh sistem dan dibolehkan menyelesaikan operasi Down-nya
• urutan proses yang dipilih tidak ditentukan oleh Dijkstra dapat dipilih secara acak, FIFO dll sesuai kepentingan
• operasi UP menaikkan nilai semaphore, memindahkan dari antrian dan menempatkan proses ke antrian.

5.  Bagaimana struktur semaph0re yg digunakan untuk menylesaikan

a. B0unded buffer pr0blem.

B. Reader and writer pr0blem

c. Dining phil0s0pher pr0blem

Jawab:

a. B0unded buffer pr0blem.

Untuk penyelesaian permasalahan bounded buffer menggunakan semaphore

menggunakan variabel umum berikut :

semaphore full, empty, mutex;

Inisialisasi untuk variable diatas, full = 0, empty = n, mutex = 1. Struktur

program untuk produsen adalah

do {

…

menghasilkan item pada nextp

…

wait(empty);

wait(mutex);

…

menambah nextp ke buffer

…

signal(mutex);

signal(full);

} while (1);

Sedangkan struktur program untuk konsumen adalah

do {

wait(full)

wait(mutex);

…

mengambil item dari buffer ke nextc

…

signal(mutex);

signal(empty);

…

menggunakan item pada nextc

…

} while (1);

B. Reader and writer pr0blem

Variabel umum yang digunakan

adalah

semaphore mutex, wrt;

Inisialisasi variable diatas adalah mutex = 1, wrt = 1, readcount = 0.

Struktur proses writer adalah

wait(wrt);

…

menulis

…

signal(wrt);

Sedangkan struktur proses reader adalah

wait(mutex);

readcount++;

if (readcount == 1)

wait(rt);

signal(mutex);

…

membaca

…

wait(mutex);

readcount--;

if (readcount == 0)

signal(wrt);

signal(mutex):

c. Dining phil0s0pher pr0blem

Struktur data yang digunakan untuk penyelesaian permasalahan ini dengan semaphore

adalah

semaphore chopstick[5];

Dimana semua nilai array dinisialisasi 1. Struktur program untuk filosof ke i adalah

do {

wait(chopstick[i])

wait(chopstick[(i+1) % 5])

…

makan

…

signal(chopstick[i]);

signal(chopstick[(i+1) % 5]);

…

berfikir

…

} while (1);