Makalah Sinkronisasi dan Deadlock

Sinkronasi dan Deadlock

KELOMPOK 4 Sistem Operasi

Kelas 2KA07

Angga Trinugraha (10116850)

George Armando (12116997)

Maulidwi Fathan L (14116311)

Petrus C Jordy C (15116764)

Yossi Jubel Agusto (17116812)

BAB 1

PENDAHULUAN

1. Latar Belakang

Pada zaman sekarang ini telah terjadi banyak perkembangan pada berbagai macam bidang teknologi, seperti halnya komputer yang memiliki sebuah atau beberapa buah sistem operasi. Pada dasarnya sistem operasi memiliki peranan yang sangat penting dalam proses-proses yang terjadi di dalam komputer ,baik itu hubungan PC dengan prangkat input/output, PC dengan user. Pada sistem operasi terdapat beberapa masalah yang ditemukan antara lain seperti Mutual Exclusion, Deadlock,StarVation, Sinkronisasi. Mutual Exclusion adalah jaminan hanya satu proses yang mengaksessumber daya pada satu interval tertentu. Proses disebut deadlock jika prose menunggu suatu kejadian yang tak pernah terjadi. Proses dikatakan mengalami starvation jika prosesproses itu menunggu alokasi sumber daya sampai tak berhingga. sementara prosesproses laindapat memperoleh alokasi sumber daya

BAB 2

ISI

A. Sinkronasi dan Deadloack

Suatu sistem operasi modern merupakan suatu sistem yang besar dan kompleks sehingga strukturnya harus dirancang dengan hati-hati dan saksama supaya dapat berfungsi seperti yang diinginkan serta dapat dimodifikasi dengan mudah

Struktur sistem operasi merupakan komponen-komponen sistem operasi yang dihubungkan dan dibentuk di dalam kernel

Ada beberapa struktur sistem operasi dan pernah dicoba, diantaranya sebagai berikut:

1.Masalah Critical Section

Pengertian Critical Section

critical section adalah dengan mendesain sebuah protokol di mana proses-proses dapat menggunakannya secara bersama-sama. Setiap proses harus ‘meminta izin’ untuk memasuki critical section-nya. Bagian dari kode yang mengimplementasikan izin ini disebut entry section. Akhir dari critical section itu disebut exit section. Bagian kode selanjutnya disebut remainder section.

Struktur umum dari proses Pi yang memiliki segmen critical section adalah :

do {

entry section

critical section

exit section

remainder section

} while (1);

Solusi dari masalah critical section harus memenuhi tiga syarat berikut:

1. Mutual Exclusion.

Jika suatu proses sedang menjalankan critical section-nya, maka proses-proses lain tidak dapat menjalankan critical section mereka. Dengan kata lain, tidak ada dua proses yang berada dicritical section pada saat yang bersamaan.

2. Terjadi kemajuan (progress).

Jika tidak ada proses yang sedang menjalankan critical section-nya dan ada proses-proses lain yang ingin masuk ke critical section, maka hanya proses-proses yang yang sedang berada dalamentry section saja yang dapat berkompetisi untuk mengerjakan critical section.

3. Ada batas waktu tunggu (bounded waiting).

Jika seandainya ada proses yang sedang menjalankan critical section, maka proses lain memiliki waktu tunggu yang ada batasnya untuk menjalankan critical section -nya, sehingga dapat dipastikan bahwa proses tersebut dapat mengakses critical section-nya (tidak mengalamistarvation: proses seolah-olah berhenti, menunggu request akses ke critical sectiondiperbolehkan).

Kunci untuk mencegah masalah ini dan di situasi yang lain yang melibatkan shared memori, shared berkas, and shared sumber daya yang lain adalah menemukan beberapa jalan untuk mencegah lebih dari satu proses untuk melakukan proses writing dan reading kepada shared data pada saat yang sama. Dengan kata lain kita memutuhkan 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. Bagaimana pun setiap kali sebuah proses mengakses shared memory atau shared berkas atau melakukan sesuatu yang kitis akan menggiring kepada race conditions. Bagian dari program dimana shaed memory diakses disebut Critical Section atau Critical Region.

Walau pun dapat mencegah race conditions, tapi tidak cukup untuk melakukan kerjasama antar proses secara pararel dengan baik dan efisien dalam menggunakan shared data. Kita butuh 4 kondisi agar menghasilkan solusi yang baik:

·Tidak ada dua proses secara bersamaan masuk ke dalam citical section.

·Tidak ada asumsi mengenai kecepatan atau jumlah cpu.

·Tidak ada proses yang berjalan di luar critical secion yang dapat mengeblok proses lain.

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

2.Karakteristik DEADLOCK

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:

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.
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.
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.
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.

3. Sinkronisasi Hardware

Seperti yang telah kita ketahui bahwa, sinkronisasi haruslah mutual exclusive/harus ada satu atau sekelompok instruksi yang tidak dapat diberhentikan pada waktu eksekusi (sifat mutual exclusive). Jadi, solusi untuk sinkronisasi dengan cara pendekatan hardware lebih menekankan kepada usaha-usaha untuk membuat suatu atau sekelompok instruksi menjadi mutual exclusive.

Pendekatan dari sisi hardware dapat dibagi menjadi dua:

1. Processor Synchronous

2. Memory Synchronous

Mutual exclusive = Jika proses Pi sedang mengeksekusi critical section maka tidak ada proses lain yang dapat mengeksekusi dalam critical section mereka.

4.Semaphores

Semafor adalah sistem sinyal yang digunakan untuk berkomunikasi secara visual. Dalam software, semafor adalah sebuah variabel bertipe integer yang selain saat inisialisasi, hanya dapat diakses melalui dua operasi standar, yaitu increment dan decrement. Semafor digunakan untuk menyelesaikan masalah sinkronisasi secara umum. Berdasarkan jenisnya, semafor hanya bisa memiliki nilai 1 atau 0, atau lebih dari sama dengan 0. Konsep semafor pertama kali diajukan idenya oleh Edsger Dijkstra pada tahun 1967.

Operasi standar pada semafor (dalam bahasa pemrograman C). Nama asli dari operasi tersebut sebenarnya adalah Proberen (test) dan Verhogen (increment). Fungsi wait dipanggil ketika thread akan memasuki critical section-nya atau ketika thread akan memakai resource yang tersedia. Jika sem_value kurang dari sama dengan 0, thread tersebut harus menunggu sampai thread lain memanggil fungsi buka. Fungsi buka dipanggil ketika thread meningggalkan critical section-nya atau ketika melepaskan resource yang telah digunakannya. Tentu saja kedua operasi tersebut harus bersifat atomik karena sem_value dapat diakses oleh beberapa proses (shared resource).

Semafor memiliki dua jenis, yaitu:

Binary semaphore,

Semafor ini hanya memiliki nilai 1 atau 0. Sering juga disebut sebagai semafor primitif

Counting semaphore

Semafor ini memiliki nilai 0, 1, serta integer lainnya. Banyak sistem operasi yang tidak secara langsung mengimplementasikan semafor ini, tetapi dengan memanfaatkan binary semaphore

Fungsi Semaphore

– Mutual exclusion

Sesuai dengan prinsip mutual exclusion, jika suatu thread sedang berada dalam critical section-nya, thread lain harus menunggu thread tersebut keluar dari critical section-nya sebelum dapat memasuki critical section-nya sendiri. Di sinilah semafor digunakan, thread yang akan memasuki critical section-nya akan memanggil fungsi kunci terlebih dahulu. Jika tidak ada thread lain yang sedang berada dalam critical section, thread ini akan memasuki critical section-nya. Jika terdapat thread lain yang sedang berada dalam critical section-nya, thread ini harus menunggu.Setelah thread keluar dari critical section-nya, thread tersebut akan memanggil fungsi buka sehingga sem_value akan naik menjadi lebih dari 0, dan satu (dari beberapa) thread yang sedang menunggu akan mendapatkan giliran untuk memasuki critical section-nya.

– Sebagai contoh, misalnya terdapat dua buah thread yang sedang berjalan bersamaan:

Thread A: thread B: count = count + 1; count = count + 1; Thread A dan B mengakses variabel yang sama, yaitu count sehingga thread A dan B harus berjalan satu-satu. Untuk itu digunakan semafor mutex yang berupa binary semaphore dengan nilai awal 1.

– Resource controller

Contoh: bayangkan sebuah restoran yang setiap malamnya ramai dikunjungi pelanggan. Kapasitas restoran terbatas, tetapi pemilik restoran memiliki kebijakan bahwa semua pengunjung yang datang akan mendapatkan kesempatan untuk makan, dengan konsekuensi yaitu pelanggan harus sabar menunggu gilirannya. Oleh karena itu, dikerahkanlah pegawai restoran untuk menahan tamu di luar jika restoran penuh lalu mempersilahkan tamu masuk jika tempat telah tersedia. Dari analogi di atas, pelanggan adalah thread, kapasitas restoran adalah resource, dan pegawai restoran adalah semafor. Semafor menyimpan banyaknya resource yang tersedia. Saat thread ingin memakai resource ia akan memanggil fungsi kunci. Jika resource masih tersedia, thread bisa langsung menggunakannya, sebaliknya jika semua resource sedang dipakai, thread tersebut harus menunggu. Setelah resource selesai dipakai thread akan memanggil fungsi buka sehingga resource yang bebas bertambah.

– Sinkronisasi antar-proses

Ada kalanya suatu thread memerlukan resource yang dihasilkan oleh thread lainnya. Oleh karena itu dibutuhkan suatu mekanisme untuk mengatur urutan eksekusi thread. Mekanisme ini dilakukan dengan memanfaatkan semafor.

– Sebagai contoh, misalnya terdapat dua buah thread yang sedang berjalan bersamaan:

Thread A: thread B: count = count + 1; count = count * 2; Nilai awal dari variabel count adalah 5, nilai akhir yang diinginkan adalah 12, oleh karena itu thread A harus dieksekusi sebelum thread B. Agar hal ini dapat terjadi dibutuhkan suatu semafor mutex yang merupakan sebuah binary semaphore dengan nilai awal 0.

Thread A: thread B: count = count + 1; kunci(mutex); buka(mutex); count = count * 2; Thread B akan menunggu sampai eksekusi thread A selesai sebelum melanjutkan.

Implementasi Semaphore

– Windows

Fungsi yg dipakai adalah CreateSemaphore biasanya digunakan untuk membatasi jumlah thread yang memakai suatu resource secara bersamaan

– Java

Semafor di Java bersifat transparan oleh

– Programmer

Java™ menyembunyikan Semafor dibalik konsep

5.Masalah Klasik Sinkronisasi

Masalah Klasik Sinkronisasi dapat dibedakan menjadi 3 :

1.Bounded – Buffer Problem

2.Readers and Writers Problem

3.Dining Philosophers Problem

1.Pengertian Bounded –Buffer Problem

Bounded buffer merupakan suatu struktur data yang mampu untuk menyimpan beberapa nilai dan mengeluarkannya kembali ketika diperlukan . Jika dianalogikan bounded buffer ini akan mirip dengan sebuah tumpukan piring. Kita menaruh piring dan menaruh lagi sebuah piring, ketika ingin mengambil piring maka tumpukan yang paling atas yang akan terambil.Jadi piring terakhir yang dimasukan akan pertama kali diambil.

Contoh Kasus Bounded - Buffer

Pada bagian ini akan dicontohkan suatu produser konsumer. produser akan menghasilkan suatu barang dan konsumer akan mengkonsumsi barang yang dihasilkan oleh produser. produser dan konsumer ini akan mengakses bounded buffer yang sama. produser setelah menghasilkan suatu barang dia akan menaruh barang itu di bounded buffer sebaliknya konsumer ketika membutuhkan suatu barang, dia akan mengambilkannya dari bounded buffer.

Solusi Bounded – Buffer Problem

Solusi Shared Memory untuk Bounded – Buffer, mengijinkan (n-1) items di dalam buffer untuk suatu waktu tertentu.

2.Pengertian Readers and Writers Problem

Readers and Writers Problem adalah problem yang memodelkan proses yang mengakses database. Masalah ini timbul ketika ada dua proses atau lebih berbagi data yang sama. Data yang dimaksud disini bisa berbentuk buffer, file atau objek dari suatu program

Solusi Readers and Writers Problem

a.Pembaca di prioritaskan

b.Penulis di prioritaskan

c.Kedua jenis proses mempunyai prioritas yang sama.

Solusi Pembaca di Prioritaskan

Reader tidak akan menunggu reader(s) lain yang sedang membaca, walaupun ada writer yang sedang menunggu. Dengan kata lain, Jika ada reader yang datang ketika reader lain sedang membaca dan sebuah writer sedang menunggu, maka reader yang baru datang tersebut akan langsung mendapat giliran untuk membaca. Writer akan ditunda pengerjaannya.

Solusi Penulis di Prioritaskan

Di mana suatu writer sedang dijalankan oleh sistem, maka tidak boleh ada reader yang memulai untuk membaca data.

Solusi Kedua Jenis Punya Prioritas Sama

Tidak ada prioritas khusus yang diberikan kepada kedua jenis proses.

3.Sejarah Dining Philosophers Prolem

Masalah ini pertama ini pertama kali ditulis dan diselesaikan oleh Djikstra pada tahun 1965.Masalah ini memodelkan masalah enkapsulasi dari ketergantungan mesin dan masalah portabilitas. Dalam masalah Dining Philosophers, diketahui sejumlah (N) filusuf yang hanya memiliki tiga status, berpikir, lapar, dan makan. Semua filusuf berada di sebuah meja makan bundar yang ditata sehingga di depan setiap filusuf ada sebuah piring berisi mie dan di antara dua piring yang bersebelahan terdapat sebuah sumpit.

Solusi Dining Philosophers Problem

Solusi Dining – Philosophers Problem ada dua, yakni :

a.Solusi Waiter

Solusi Waiter : solusi sederhana ini dilakukan dengan mengadakan seorang waiter yang senantiasa mengawasi penggunaan sumpit di meja makan. Ketika empat buah (dua pasang) sumpit sedang dipakai,orang berikutnya yang ingin memakai sumpit harus meminta izin kepada sang waiter, yang hanya dapat diberi ketika salah satu sumpit telah selesai terpakai.

b.Solusi Hierarki Resource

Solusi Hirarki Resource: resources (sumpit) di meja makan telah diberi susunan hirarki. Setiap permintaan orang terhadap sebuah sumpit harus dilakukan pada susunan tertentu, dan dikembalikan pada susunan sebaliknya. Dalam hal ini, setiap orang dapat mengambil sumpit dimanapun diatas meja. Misalkan setiap sumpit diberi nomor sebagai tingkat hirarki dari 1 sampai 5, seseorang hanya dapat mengambil sumpit dengan nomor yang paling rendah, kemudian mengambil sumpit yang setingkat lebih tinggi. Ketika ia hendak mengembalikannya, orang itu harus meletakkan sumpit dengan nomor yang lebih tinggi terlebih dahulu, lalu yang rendah.

6.Deadlock

6.1 MODEL SISTEM

Pada sistem terdapat beberapa sumber daya (resource) yang digunakan untuk proses-proses untuk menyelesaikan task. Sumber daya yang pada sistem terdiri dari tipe resource CPU cycle, ruang memori, perangkat I/O yang disebut dengan tipe sumber daya R1, R2, . . ., Rm. Setiap tipe sumber daya Ri mempunyai beberapa anggota Wi. Setiap proses yang menggunakan sumber daya menjalankan urutan operasi sebagai berikut :

• meminta (request) : meminta sumber daya

• memakai (use) : memakai sumber daya

• melepaskan (release) : melepaskan sumber daya

6.2 KARAKTERISTIK DEADLOCK

6.2.1 Kondisi yang Diperlukan Deadlock terjadi bila terdapat empat kondisi berikut ini secara simultan. a. Mutual Exclusion : hanya satu proses pada satu waktu yang dapat menggunakan sumber daya. b. Genggam dan Tunggu (Hold and Wait) : suatu proses membawa sedikitnya satu sumber daya menunggu mendapatkan tambahan sumber daya baru yang dibawa oleh proses

6.2.2 Resource Allocation Graph Deadlock dapat digambarkan lebih presisi dengan menggunakan graph berarah yang disebut resource allocation graph.

6.3 METODE MENANGANI DEADLOCK

Terdapat tiga metode untuk menangani permasalahan deadlock yaitu : • Menggunakan protocol untuk menjamin bahwa sistem tidak pernah memasuki status deadlock • Mengijinkan sistem memasuki status deadlock dan kemudian memperbaikinya. • Mengabaikan permasalahan dan seakan-akan deadlock tidak pernah terjadi pada sistem. Model ini yang banyak digunakan pada sistem operasi termasuk UNIX.

6.4 MENCEGAH DEADLOCK

Metode ini berkaitan dengan pengkondisian sistem agar menghilangkan kemungkinan terjadinya deadlock. Pencegahan merupakan solusi yang bersih dipandang dari sudut tercegahnya deadlock. Metode ini sering menghasilkan utilisasi sumber daya yang buruk. Pencegahan deadlock merupakan metode yang banyak dipakai. Untuk mencegah deadlock dilakukan dengan meniadakan salah satu dari syarat perlu sebagai berikut : • Mencegah Mutual Exclusion Mutual exclusion benar-benar tak dapat dihindari. Hal ini dikarenakan tidak ada sumber daya yang dapat digunakan bersama-sama, jadi sistem harus membawa sumber daya yang tidak dapat digunakan bersama-sama.

• Mencegah Hold and Wait Untuk mencegah hold and wait, sistem harus menjamin bila suatu proses meminta sumber daya, 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 membawa sumber 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 sumber daya yang dibutuhkannya dialokasikan untuk proses yang lain.

• 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 : o Jika suatu proses yang membawa beberapa sumber daya meminta sumber daya lain yang tidak dapat segera dipenuhi untuk dialokasikan pada proses tersebut, maka semua sumber daya yang sedang dibawa proses tersebut harus dibebaskan. o Proses yang sedang dalam keadaan menunggu, sumber daya yang dibawanya ditunda dan ditambahkan pada daftar sumber daya. o Proses akan di restart hanya jika dapat memperoleh sumber daya yang lama dan sumber daya baru yang diminta.

• 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.

6.5 MENGHINDARI DEADLOCK

Metode alternatif untuk menghindari deadlock adalah digunakan informasi tambahan tentang bagaimana sumber daya diminta. Misalnya pada sistem dengan satu tape drive dan satu printer, proses P pertama meminta tape drive dan kemudian printer sebelum melepaskan kedua sumber daya tersebut. Sebaliknya proses Q pertama meminta printer kemudian tape drive. Dengan mengetahui urutan permintaan dan

pelepasan sumber daya untuk setiap proses, dapat diputuskan bahwa untuk setiap permintaan apakah proses harus menunggu atau tidak. Setiap permintaan ke sistem harus dipertimbangkan apakah sumber daya tersedia, sumber daya sedang dialokasikan untuk proses dan permintaan kemudian serta pelepasan oleh proses untuk menentukan apakah permintaan dapat dipenuhi atau harus menunggu untuk menghindari deadlock. Model yang sederhana dan sangat penting dibutuhkan adalah setiap proses menentukan jumlah maksimum sumber daya dari setiap tipe yang mungkin diperlukan. Algoritma deadlock avoidance secara dinamis memeriksa status sumber daya yang dialokasikan untuk menjamin tidak pernah terjadi kondisi menunggu sirkular. Status alokasi sumber daya ditentukan oleh jumlah sumber daya yang tersedia dan yang dialokasikan dan maksimum permintaan oleh proses-proses.

6.6 MENDETEKSI DEADLOCK

Jika sistem tidak menyediakan algoritma mencegah deadlock dan menghindari deadlock, maka terjadi deadlock. Pada lingkungan ini sistem harus menyediakan : • Algoritma yang menguji state sistem untuk menentukan apakah deadlock telah terjadi. • Algoritma untuk memperbaiki dari deadlock.

6.6.1 Satu Anggota untuk Setiap Tipe Sumber Daya Jika semua sumber daya hanya mempunyai satu anggota, kita dapat menentukan algoritma mendeteksi deadlock menggunakan bentuk resource allocation graph yang disebut wait-for graph.

Garis dari Pi → Pj pada wait-for graph menandakan bahwa proses Pi menunggu Pj melepaskan sumber daya yang dibutuhkan Pi. Garis Pi → Pj terdapat pada wait-for graph jika dan anya jika resource allocation graph berisi dua garis Pi → Rq dan Rq → Pj untuk beberapa sumber daya Rq seperti Gambar 6-7. Secara periodik sistem menggunakan algoritma yang mencari siklus pada graph. Algoritma untuk mendeteksi siklus pada graph membutuhkan operasi n2 dimana n adalah jumlah titik pada graph.

6.6.2 Beberapa Anggota untuk Setiap Tipe Sumber Daya Untuk Tipe sumber daya yang mempunyai beberapa anggota digunakan algoritma yang sejenis dengan algoritma Banker dengan struktur daya seperti di bawah ini : • Available : vector panjang m menandakan jumlah sumber daya yang tersedia untuk setiap tipe sumber daya. • Allocation : matrik n x m yang mendefinisikan jumlah sumber daya untuk setiap tipe sumber daya yang sedang dialokasikan untuk setiap proses. • Request : matrik n x m yang mendefinisikan permintaan setiap proses. Jika Request [I, j] = k, maka proses Pi meminta k anggota tipe sumber daya Rj.

Gambar

6.6.3 Penggunaan Algoritma Deteksi Untuk menjawab kapan dan berapa sering menggunakan algoritma deteksi, hal ini tergantung pada : • Seberapa sering terjadi deadlock. • Berapa proses yang perlu dilakukan roll back. Jika algoritma deteksi digunakan, terdapat beberapa siklus pada graph, hal ini tidak dapat mengetahui berapa proses yang deadlock yang menyebabkan deadlock.

6.7 PERBAIKAN DARI DEADLOCK

Terdapat dua pilihan untuk membebaskan deadlock. Satu solusi sederhana adalah dengan menghentikan satu atau beberapa proses untuk membebaskan kondisi menunggu sirkular. Pilihan kedua adalah menunda beberapa sumber daya dari satu atau lebih proses yang deadlock.

6.7.1 Terminasi Proses Untuk memperbaiki deadlock dengan terminasi proses, dapat diguankan salah satu dari dua metode di bawah ini : • Menghentikan (abort) semua proses yang deadlock • Menghentikan satu proses setiap waktu sampai siklus deadlock hilang.

Untuk menentukan urutan proses yang harus dihentikan ada beberapa faktor yang harus diperhatikan : • Prioritas proses. • Berapa lama proses dijalankan dan berapa lama lagi selesai. • Sumber daya yang digunakan proses. • Sumber daya proses yang diperlukan untuk menyelesaikan task. • Berapa proses yang perlu diterminasi. • Apakah proses interaktif atau batch.

6.7.2 Menunda Sumber Daya Untuk menghilangkan deadlock dengan menunda sumber daya, sumber daya dari proses harus ditunda dan memberikan sumber daya tersebut ke proses lain sampai siklus deadlock hilang. Jika penundaan dibutuhkan untuk menghilangkan deadlock, terdapat tiga hal yang perlu diperhatikan : • Pilihlah korban (sumber daya) yang mempunyai biaya minimal. • Lakukan rollback yaitu memulai kembali (restart) proses pada state yang aman. • Harus dijamin starvation tidak akan terjadi karena kemungkinan beberapa proses selalu terpilih sebagai korban termasuk jumlah rollback sebagai faktor biaya.

6.8 METODE KOMBINASI MENANGANI DEADLOCK

Untuk menangani deadlock dilakukan kombinasi dari tiga algoritma dasar yaitu mencegah deadlock, menghindari deadlock dan mendeteksi deadlock. Kombinasi ketiga algoritma ini memungkinkan penggunaan yang optimal untuk setiap sumber daya pada sistem.

BAB 3

Penutup

KESIMPULAN

Sebenarnya mutual Exclusion sendiri merupakan salahsatu bagian dari pembahasan Deadlock, tepatnya Mutual Exclusion adalah salah satu dari empat kriteria penyebab terjadinya Deadlock. Selain Mutual Exclusion ada juga Hold and Wait, No Preemption, dan Circular Wait dan suatu kondisi di katakan Deadlock adalah apabila ke-empat karakteristik itu terpenuhi. Langsung saja ke pembahasan awal mengenai Deadlock

refrensi

http://wahyupramartha.blogspot.co.id/2012/11/sinkronisasi-dan-deadlock.html

ftp://ftp.gunadarma.ac.id/linux/docs/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-1/ch23s04.html

https://www.academia.edu/8785351/Sinkronisasi_Proses_Sistem_Operasi_Komputer

http://arna.lecturer.pens.ac.id/Diktat_SO/6.Deadlock.pdf

https://guruinformatika.blogspot.co.id/2015/05/makalah-deadlock-sistem-operasi.html

Categories:

One Response so far.

Steven says:

6 Mei 2019 pukul 01.55

Silakan Kunjungi Artikel Bola :

Prediksi Chelsea vs Eintracht Frankfurt 10 Mei 2019
Prediksi Valencia vs Arsenal 10 Mei 2019

Dan dapat Hubungi Kontak Kami +62-8122-222-995

Creation Information