Deadlock & Mutual Exclusion

Deadlock

Deadlock adalah suatu kondisi dimana dua proses atau lebih saling menunggu proses untuk melepaskan seumber daya atau resources yang sedang dipakai. Mudahnya, ada proses A yang membutuhkan suatu resources, tetapi resources tersebut sedang dipakai oleh proses lain.

Untuk lebih paham tentang pengertian deadlock dan cara mengatasinya, anda dapat membandingkan dengan situasi berikut: Dalam kehidupan, tentunya anda membutuhkan pekerjaan. Untuk memperoleh pekerjaan, anda harus punya pengalaman. Untuk punya pengalaman, anda harus bekerja.

Pengertian Deadlock dan Cara Mengatasinya

Deadlock terjadi karena sebuah proses membutuhkan resources tertentu, tetapi resources tersebut sedang digunakan oleh process lain. Padahal proses lain tersebut tidak akan melepaskan resources selama proses yang dilakukannya belum selesai.

Deadlock pada lalu lintas

Syarat Terjadinya Deadlock

Ada empat kondisi yang menyebabkan terjadinya deadlock, dimana seluruh kondisi tersebut harus terpenuhi. Kondisi tersebut adalah:

Mutual Exclusion, mutual exclusion terjadi ketika resource yang digunakan adalah resource yang non shareable.
Hold and Wait, terdapat suatu proses yang menahan resource, padahal resource tersebut telah dialokasikan oleh proses yang lain
No Preemption, resource yang telah di alokasikan untuk sebuah proses tidak dapat didahului oleh proses lain.
Circular Wait, beberapa proses membentuk urutan rantai berbentuk sirkular dimana masing-masing proses menunggu proses sebelumnya untuk selesai.

Cara Mencegah Deadlock

Ada tiga metode yang dapat digunakan untuk mencegah deadlock, yaitu:

Ignore Deadlock Membiarkan deadlock terjadi, dan ketika deadlock benar-benar terjadi sistem operasi akan mengabaikannya (kebanyakan OS melakukan hal tersebut).

Memastikan deadlock tidak terjadi dengan cara mencegah salah satu kondisi terjadinya deadlock agar tidak pernah terjadi.

Membiarkan deadock terjadi, tetapi hal ini membutuhkan deteksi terhadap kondisi proses jika terjadi deadlock, selanjutnya sistem operasi harus memperbaiki kondisi tersebut dengan cara memperoleh kembali resource yang menyebabkan deadlock.

                        Ditulis oleh roddy yoto sumaryo

                        12.5.00080

Definisi dari Proses, Thread,Mutual Exclution, Race Condition,Sinkronisasi, Deadlock, Starvation,Monitor, dan Semaphore!

Secara informal; proses adalah program dalam eksekusi. Suatu proses adalah lebih dari kode program, dimana kadang kala dikenal sebagai bagian tulisan. Proses juga termasuk aktivitas yang sedang terjadi, sebagaimana digambarkan oleh nilai pada program counter dan isi dari daftar prosesor/ processor’s register. Suatu proses umumnya juga termasuk process stack, yang berisikan data temporer (seperti parameter metoda, address yang kembali, dan variabel lokal) dan sebuah data section, yang berisikan variabel global.

Thread adalah sebuah alur kontrol dari sebuah proses. Suatu proses yang multithreaded mengandung beberapa perbedaan alur kontrol dengan ruang alamat yang sama. Keuntungan dari multithreaded meliputi peningkatan respon dari user, pembagian sumber daya proses, ekonomis, dan kemampuan untuk mengambil keuntungan dari arsitektur multiprosesor. User level thread adalah thread yang tampak oleh programmer dan tidak diketahui oleh kernel. User level thread secara tipikal dikelola oleh sebuah library thread di ruang user. Kernel level thread didukung dan dikelola oleh kernel sistem operasi. Secara umum, user level thread lebih cepat dalam pembuatan dan pengelolaan dari pada kernel thread. Ada tiga perbedaan tipe dari model yang berhubungan dengan user dan kernel thread.

·         Model many to one: memetakan beberapa user level thread hanya ke satu buah kernel thread.

·         Model one to one: memetakan setiap user thread ke dalam satu kernel thread. Berakhir.

·         Model many to many: mengizinkan pengembang untuk membuat user thread sebanyak mungkin, konkurensi tidak dapat tercapai karena hanya satu thread yang dapat dijadualkan oleh kernel dalam satu waktu.

Mutual Exclusion adalah Suatu kondisi dimana setiap sumber daya diberikan tepat pada satu proses pada suatu waktu (kondisi-kondisi untuk solusi). Tiga kondisi untuk menentukan mutual Exclusion diantaranya :

1.      Tidak ada dua proses yang pada saat bersamaan berada di critical region.

2.      Tidak ada proses yang berjalan diluar critical region yang bisa menghambat proses lain

3.      Tidak ada proses yang tidak bisa masuk ke critical region

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.

Sinkronisasi adalah Komunikasi antara proses yang membutuhkan place by calls untuk mengirim dan menerima data primitive. Terdapat rancangan yang berbeda-beda dalam implementasi setiap primitive. Pengiriman pesan mungkin dapat diblok (blocking) atau tidak dapat dibloking (nonblocking) – juga dikenal dengan nama sinkron atau asinkron.

Deadlock ialah suatu kondisi permanen dimana proses tidak berjalan lagi ataupun tidak ada komunikasi lagi antar proses. Deadlock disebabkan karena proses yang satu menunggu sumber daya yang sedang dipegang oleh proses lain yang sedang menunggu sumber daya yang dipegang oleh proses tersebut. Atau dengan kata lain setiap proses dalam set menunggu untuk sumber yang hanya bisa dikerjakan oleh proses lain dalam set yang sedang menunggu.

Starvation adalah suatu proses meninggalkan critical section dan lebih dari satu proses menunggu (waiting).Beberapa proses dapat ditolak aksenya dalam waktu tak terbatas.

Monitor adalah kumpulan prosedur, variabel dan struktur data di satu modul atau paket khusus. Proses dapat memanggil prosedur-prosedur kapan pun diinginkan. Tapi proses tak dapat mengakses struktur data internal dalam monitor secara langsung. Hanya lewat prosedur-prosedur yang dideklarasikan minitor untuk mengakses struktur internal.

Semaphore adalah pendekatan yang diajukan oleh Djikstra, dengan prinsip bahwa dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Seperti proses dapat dipaksa berhenti pada suatu saat, sampai proses mendapatkan penanda tertentu itu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan struktur penanda yang cocok untuk kebutuhan itu. Variabel khusus untuk penanda ini disebut semaphore.Semaphore mempunyai dua sifat, yaitu:

1.      Semaphore dapat diinisialisasi dengan nilai non-negatif.

2.      Terdapat dua operasi terhadap semaphore, yaitu Down dan Up. Usulan asli yang disampaikan Djikstra adalah operasi P dan V.

Di tulis oleh aditya anwar Ibrahim

12.5.00109

Mutual Exclusion

            1. Pengertian Mutual Exclusion

Mutual Exclution merupakan kondisi dimana terdapat sumber daya yang tidak dapat dipakai bersama pada waktu yang bersamaan (misalnya : printer, disk drive) maka terdapat jaminan hanya satu proses yang mengakses sumber daya pada satu interval tertentu. 

2. Critical Section

Beberapa proses memiliki suatu segmen kode dimana jika segmen itu dieksekusi, maka proses-proses itu dapat saling mengubah variabel, mengupdate suatu tabel, menulis ke suatu file, dan lain sebagainya, dan hal ini dapat membawa proses tersebut ke dalam bahaya race condition. Segmen kode yang seperti inilah yang disebut Critical Section. Sedangkan race

condition sendiri adalah kondisi dimana ada beberapa proses yang memanipulasi suatu data secara kongkuren, sehingga data tersebut tidak sinkron lagi. Nilai akhirnya akan tergantung pada proses mana yang terakhir dieksekusi. Maka dibutuhkan sinkronisasi.

3. Sumber Daya

Yang dimaksud dengan sumber daya pada sistem komputer adalah semua komponen yang memberikan fungsi (manfaat) atau dengan pengertian lain adalah semua yang terdapat atau terhubung ke sistem komputer yang dapat untuk memindahkan, menyimpan, dan memproses data, serta untuk mengendalikan fungsi-fungsi tersebut. Sumber daya pada sistem komputer,

antara lain :

a. Sumber daya fisik

Contoh dari sumber daya fisik diantaranya keyboard, bar-code reader, mouse, joystick, lightpen, track-ball, touchscreen, pointing devices, floppy disk drive, hard-disk, tape drive, optical disk, CD ROM drive, CRT, LCD, printer, modem, ethernet card, PCMCIA, RAM, cache

memory, register, kamera, sound card, radio, digitizer, scanner, plotter, dan sebagainya.

b. Sumber daya abstrak

Terdiri dari :

Ø Data, misalnya :Semaphore untuk pengendalian sinkronisasi prosesproses, PCB (Process Control Block) untuk mencatat dan mengendalikan proses, tabel segmen, tabel page, i-node, FAT, file dan sebagainya.

Ø Program yang berupa kumpulan instruksi yang dapat dijalankan oleh system komputer, yang dapat berupa utilitas dan program aplikasi pengolahan data tertentu.

4. Proses yang berada di critical section harus menunggu dalam waktu yang berhingga dan proses yang berada didalam critical section pun harus dalam jangka waktu yang berhingga pula

Jelas sekali hal ini harus terjadi pada manajemen proses disebuah operating system, karena hal ini untuk menghindari deadlock. Deadlock sendiri merupakan kondisi terparah karena banyak proses dapat terlibat dan semuanya tidak dapat mengakhiri prosesnya secara benar. Hal ini dapat terjadi jika waktu tunggu proses diluar critical section tidak jelas maka proses tersebut akan masuk kapan saja kedalam critical section, entah itu kosong atau masih ada proses didalam critical section. Jika dalam critical sectionnya masih ada proses maka kasus tersebut telah melanggar mutual exclusion. Sebaliknya jika waktu proses tidak berhingga atau tidak jelas maka tidak jelas pula kapan critical section kosong, maka proses yang diluar akan selamanya menunggu dan akan terjadi deadlock.

5. Proses-Proses (Masuk) Ke Daerah Critical Section Tidak Boleh Saling

Memblok

Jika proses-proses saling memblok ketika akan masuk ke critical section maka akan terjadi pula deadlock. Ini salah satu penyebab lain deadlock. Karena jika proses-proses saling memblok maka selamanya proses-proses tersebut tidak akan masuk ke critical section, oleh karena itu akan terjadi deadlock atau buntu dan proses-proses yang telah berjalan tidak akan selesai dengan sempurna.

6. Ketika Tidak Ada Proses Di Critical Section Maka Proses Yang Ingin

Masuk Ke Critical Section Harus Diijinkan Tanpa Waktu Tunda

Fungsi seperti itu mutlak harus ada dalam system operasi. Hal ini berfungsi untuk mencegah adanya deadlock. Ketika critical section kosong maka proses selanjutnya harus masuk dan menyelesaikan prosesnya sampai selesai. Jika tidak berarti tidak ada kejelasan waktu tunggu atau tidak ada kejelasanan waktu proses dan hal ini akan menyebabkan deadlock.

7. Metode-metode dan Algoritma untuk Menjamin Mutual Exclusion

a. Disabling interrupt / mematikan interupsi

Dengan cara mematikan interupsi yang masuk pada saat proses sedang berada pada critical section-nya. Cara ini kadang cukup berguna untuk kernel tetapi tidak untuk user. Dan cara inipun tidak terlalu baik untuk CPU yang jumlahnya lebih dari satu, dimana disable interrupt hanya mengenai CPU yang sedang menjalankan proses itu dan tidak berpengaruh terhadap CPU lain

b. Lock variable

Setiap proses yang akan mengakses ke critical section-nya harus meng-cek lock variable. Jika 0 berarti proses dapat memasuki critical section-nya dan jika 1 maka proses harus menunggu sampai lock variable = 0. Kelemahannya adalah 2 proses masih dapat memasuki critical section-nya pada saat yang bersamaan. Sewaktu satu proses meng-cek lock variable = 0, pada saat akan men-set 1 ada interupsi untuk melaksanakan proses lain yang juga ingin memasuki critical sectionnya, maka akan terjadi race condition.

c. Strict alternation

Dengan mengamati variable turn untuk menentukan siapa yang akan memasuki critical section-nya bukanlah ide yang baik jika proses lebih lambat dari yang lain.

d. Peterson’s Solution

Proses tidak akan diteruskan sampai while terpenuhi, bila interested[other] = TRUE, maka proses akan menunggu sampai FALSE. Kelemahannya : jika proses memanggil enter_region-nya secara hampir bersamaan, yang disimpan di turn adalah data yang ditulis terakhir.

e. Test and Set Lock Instruction / Instruksi TSL

Dengan bantuan hardware, menentukan siapa yang berhak memasuki critical_region (section).

Ditulis oleh agung surjadi

12.5.00007

                                         MUTUAL EXCLUSION

Penjelasan tema Mutual Exclusion

Pada     system   computer   terdapat   sumber   daya   yang   tidak   dapat   dipakai   bersama   pada   saat   yang  bersamaan seperti pada penggunaan printer, Sumber daya seperti hanya dapat menjalankan satu proses pada suatu saat, sumber daya ini disebut sumber daya kritis. Program yang menggunakan sumber daya kritis disebut sedang memasuki critical region / section .

Sistem operasi memberikan fasilitas untuk pemrogram dapat memberikan indikasi keberadaan critical region. Sistem operasi menyediakan layanan ( berupa system call ) untuk mencagah suatu proses masuk kedalam critical region akan tetapi di dalam critical region terdapat proses lain yang sedang berjalan. Mutual exclusion merupakan solusi bagi masalah pada critical region / section, mutual exclusion adalah  persoalan untu menjamin hanya satu proses saja yang berjalan dalam suatu critical region / section. Ilustrasi aplikasi tabungan Seluruh sistem yang melibatkan banyak proses mengakses satu sumber daya bersama selalu menimbulkan persoalan mutual-exclusion.

Contohnya adalah sebagai berikut.

•    Pada   aplikasi   tabungan,  misalnya  rekening  A  berisi  Rp  1.000.000,-  yang  terdaftar  di 

         kantor cabang bandung.

 •   Kemudian   pada   suatu   saat   program   aplikasi   kantor   cabang   di   Jakarta   melayani 

         penyetoran Rp 3.000.000,- ke rekening A. lalu program aplikasi membaca saldo akhir 

         rekening A 

Persoalan di atas dapat tidak terjamin mutual-exclusion jika:

     1.  Program aplikasi bandung menulis ke rekening A secara cepat sehingga di hasilkan saldo 

         Rp 6.000.000. Setelah itu, program aplikasi kantor cabang Jakarta menimpa hasil itu 

         dengan saldo Rp 4.000.000,- . Dalam kasus ini saldo akhir yang diperoleh adalah Rp 

         4.000.000,- bukan Rp 10.000.000,- (yang seharusnya).

2.   Program   aplikasi   Jakarta   dilakukan   menulis   ke   rekening   A   secara   cepat  sehingga 

dihasilkan   saldo   Rp   4.000.000,-.   Setelah   itu   program   aplikasi   di   kantor   bandung menimpa hasil itu dengan saldo Rp 6.000.000,-. Hasil yang lebih baik dibanding skenario pertama tetapi masih di bawah yang seharusnya yaitu Rp 10.000.000,-.

Kriteria Penyelesaian Mutual-Exclusion

Kemampuan menjamin mutual-exclusion harus memenuhi kriteria-kriteria berikut:

     1.  Mutual-exclusion harus dijamin.

     2.  Hanya satu proses pada satu saat yang diizinkan masuk critical section yang sama pada 

         saat telah ada proses yang masuk critical section itu.

     3.  Proses yang berada di noncritical section, dilarang mem-block proses-proses lain yang 

         ingin masuk critical section.

     4.  Harus dijamin proses yang ingin masuk critical section tidak menunggu selama waktu 

         yang tak berhingga atau tidak boleh terjadi deadlock maupun startvation.

     5.  Ketika tidak ada proses di critical section, maka proses yang ingin masuk critical section 

         harus diizinkan segera masuk tanpa ada waktu tunda.

     6.  Tidak ada asumsi mengenai kecepatan relatif proses atau jumlah proses yang ada.

kriteria   pada   nomor   satu   merupakan   kriteria   pokok   yang   harus   dipenuhi.   Metode   yang  melanggar kriteria nomor satu sama sekali tidak dapat di gunakan. Pelanggaran kriteria-kriteria  lain berarti metode masih bisa digunakan  pada situasi-situasi tertentu tapi harus dilakukan  secara hati-hati.

Algoritma dan flowchart

Berikut ini adalah pemecahan masalah critical region menggunakan mutual exclusion :

Algoritma 1

Shared Variables / Crtitical Region: CR

For processes i=0 to N

do

{          //Process Non Critical Regions

          //End of Non Critical Regions

          Request_CR (i);

          //if Request Granted then Enter CR else wait

          Exit_CR (i);

}while(1);

Algoritma 2

Shared Variables / Critical Region: CR

CT : Current Time of the System

DUR : Duration of use of Critical Region

CTfirst : First Previously Requested Process Current Time

DURprev : All Previously Requested Process Duration of use of Critical Region

For processes i=0 to N

Flowchart :

                                           START

 

                                           Process

                             Enter Process ID, Current Time 

                            of Request, and Duration of USE 

                                in Critical Region’s Queue

                                           Queue 

                                           Empt

                   Enter CR

                                            CT =

                                      CT     + DUR       

                                         first      prev

                                                                                  Wait

                                                Remove Current using 

                       Send Message to Current 

                              Using Processprocess from the Queue 

      Update DURprev             Repl               and Set CR Free                                                                                                                      END

Do

{

          //Process Non Critical Regions

          //End of Non Critical Regions

          Request_CR (i, CT, DUR);

          If(Queue of CR is Empty)

                     Enter Critical Region

          Else

          {

                     If(CT = CT     + DUR      )

                                first       prev 

                    {

                               Send Message to Currently Accessing Process

                               If(reply = true)

                                   Update DURprev with new Time

                               Else

                                   Remove current process entry from the queue

                    }

                    Wait for Critical Region to be free until DUR

                    }

                     Exit

          }while (1);

Ditulis oleh adik joko supriyanto

12.5.00108

Contoh Kasus yang diselesaikan

Masalah printer Daemon Daemon   printer   adalah   proses   penjadwalan   &   pengendalian   pencetakan   berkas2   di   printer 

sehingga seolah2 printer dapat digunakan secara simultan oleh proses-proses. Daemon printer  

mempunyai   ruang  disk  (disebut   direktori  spooler)   untuk   menyimpan   berkas-berkas   yang   akan 

dicetak. Direktori spooler membagi disk menjadi sejumlah slot. Slot-slot diisi berkas yang akan 

dicetak. Terdapat variable in menunjuk slot bebas di ruang disk yang kan dipakai menyimpan berkas 

yang ingin dijadwalkan untuk dicetak.

a.  Contoh Algoritma Program: 

   Program Give_File_to_spooler;

   Var

     in : Integer;

     berkasA, berkasB: File;

   ProcedureStore (Berkas: File, next_slot: Integer);

   {Untukmenyimpanberkaspadaslot kenext_slot}

   Procedure ProsesA;

   Var

     next_free_slot: Integer;

   Begin

     next_free_slot:=in;

     store(BerkasA, next_free_slot);

     in:=next_free_slot+1;

   End; 

   ProcedureProsesB;

  Var

    next_free_slot:Integer;

   Begin

    next_free_slot:=in;

    store(BerkasB, next_free_slot);

    in:=next_free_slot+1;

   End;   Begin

     in:=0;

          Repeat

            Parbegin

                    ProsesA;

                    ProsesB;

            Parend

          Forever

   End.

b.  Skenario yang Membuat Kacau

    Misal proses A dan B ingin mencetak berkas, variable  in  bernilai 9. Scenario berikut dapat 

    terjadi :

    Proses A                                          Proses B

     {in=9}

    Next_free_slot←in

    {in=9}

    {Penjadwal  menjadwalkan B  berjalan}

                                                     {in=9}

                                                      Next_free_slot←in

                                                     Store berkas B to slot[next_free_slot]

                                                     {berkas  B disimpan dislot ke-9}

                                                     in ←next_free_slot+ 1

                                                     {in=10}

                                                     {Penjadwal menjadwalan A  berjalan}

    {in=9}     Store berkas A to slot[next_free_slot]

     {berkas     A     disimpan     dislot-9,     menimpa 

     berkasB}

     in ←next_free_slot+ 1

     {in=10}

     {berkasA menimpa berkasB, sehingga B tak pernah mendapat cetakannya}

c.   Penjelasan

 Proses   A   membaca   variable  in  bernilai   9.   Belum   sempat   A   menyelesaikan   proses, 

 penjadwal menjadwalkan proses B berjalan. Proses B yang juga ingin mencetak,  membaca 

 variable  in  ,   variable   in   masih   berniali   9.   Proses   B   dapat   menyelesaikan   proses.Proses   B menyimpan berkas B dislot ke-9. Proses A dijadwalkan kembali dan juga menyimpan berkas A dislot ke 9. BerkasB ditima berkas A, B tak akan pernah memperoleh cetakan. Pada  contoh terdapat kondisi  dimana dua  proses atau lebih sedang  membaca atau 

 menulis data bersama (yaitu variable in ) denga hasil akhir bergantung jalannya proses-proses. 

 Hasil akhir tidak dapat diprediksi. Kondisi ini disebut kondisi pacu (race condition ). Kondisi pacu harus dihilangkan agar hasil proses dapat diprediksi dan tidak bergantung jalannya proses-

 proses itu.Kunci penghilangan  kondisi  pacu adalah  harus  dapat dicegah  lebih dari satu proses 

 membaca atau menulis data bersama pada saat bersaman. Mutual exclusion adalah menjamin 

 hanya   satu   proses   yang   yang   sedang   menggunakan   variable   atau   berkas   pada   suatu   saat.Proses-proses   lain   dilarang   mengerjakan   hal   yang   sama.   Bagian   program   yang   sedang mengakses memori atau sumber daya yang dipakai bersama disebut critical section/region.Untuk   mengatasi   kondisi   pacu   harus   dijamin   tidak   boleh   dua   proses   atau   lebih  memasuki  critical section  yang sama secara bersamaan. Kesuksesan proses-proses konkuren  memerlukan pendefinisian critical section dan memaksakan mutual exclusion di antara proses-proses  kongkuren yang  sedang  berjalan. Pemaksaan  mutual  exclusion  merupakan landasan pemrosesn kongkuren.

                                                                                                     

Ketua : Adik joko supriyanto

Anggota

1. Aditya anwar Ibrahim

2. Aditya prasaja

3. Agung surjadi

4 .Rorddy yoto sumaryo