SINKRONISASI DAN DEADLOCK

A.  Sinkronisasi

Akses bebarengan untuk berbagi dua bersama dapat mengakibatkan inkosistensi data. Pemeliharaan konsistensi data memerlukan mekanisme untuk memastikan eksekusi dari proses kerjasama. Shared memory merupakan solusi ke masalah bounded-butter yang mengijinkan paling banyak n-1 materi dalam buffer pada waktu yang sama. Suatu solusi, jika semua N buffer digunakan tidaklah sederhana. Dimisalkan kita memdifikasi producer-consumer code dengan menambahkan suatu variable counter, dimulai dari 0 dan masing-masing waktu tambahan dari suatu item baru diberikan kepada buffer. 

1. Race Condition

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. Untuk mencegah race condition, proses-proses yang berjalan besamaan harus di disinkronisasi.

Dalam beberapa sistem operasi, proses-proses yang berjalan bersamaan mungkin untuk membagi beberapa penyimpanan umum, masing-masing dapat melakukan proses baca (read) dan proses tulis (write). Penyimpanan bersama (shared storage) mungkin berada di memori utama atau berupa sebuah berkas bersama, lokasi dari memori bersama tidak merubah kealamian dari komunikasi atau masalah yang muncul. Untuk mengetahui bagaimana komunikasi antar proses bekerja, mari kita simak sebuah contoh sederhana, sebuah print spooler. Ketika sebuah proses ingin mencetak sebuah berkas, proses tersebut memasukkan nama berkas ke dalam sebuah spooler direktori yang khusus. Proses yang lain, printer daemon, secara periodik memeriksa untuk mengetahui jika ada banyak berkas yang akan dicetak, dan jika ada berkas yang sudah dicetak dihilangkan nama berkasnya dari direktori.

2. Masalah Critical Section

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.

Critical Section adalah sebuah segmen kode di mana sebuah proses yang mana sumber daya bersama diakses. Terdiri dari:

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

Critical Section: Kode di mana 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.

3. Solusi ke Masalah Critical-Section

Ada bebrapa Solusi untuk mengatasi masalah Critical Section, yaitu:

·       Mutual exclution

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 ke critical section dan sebelum  permintaan itu diterima.

a.      Asumsikan bahwa tiap proses mengeksekusi pada nonzero speed.

b.      Tidak ada asumsi mengenai kecepatan relative dan n proses.

Cara-cara memecahkan masalah

·       Hanya dua proses, Po dan P1

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

4. Bakery Algorithm

Critical section untuk n proses:

a.       Sebelum memasuki critical Section-nya, proses menerima nomor pemilik nomor terkecil memasuki critical section.

b.      Jika proses Pi dan Pj menerima nomor yang sama, jika i < j, maka Pi dilayani duluan, lainnya Pj dilayani duluan (if i< j, then Pi is served first; else Pj is served first).

c.      Skema penomoran selalu menghasilkan angka –angka yang disebutkan satu per satu, yaitu 1,2,3,3,3,3,4,5….

5. Semaphore

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:

i.      Semaphore dapat diinisialisasi dengan nilai non-negatif.

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

Ø  Operasi Down

Operasi ini menurunkan nilai semaphore, jika nilai semaphore menjadi non-positif maka proses yang mengeksekusinya diblocked. Operasi Down adalah atomic, tak dapat diinterupsi sebelaum diselesaikan.Emnurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblocked sebagai instruksi tunggal. Sejak dimulai, tak ada proses alain yang dapat mengakses semaphore sampai operasi selesai atau diblocked.

Ø  Operasi Up

Operasi Up menakkan nilai semaphore. Jika satu proses atau lebih diblocked pada semaphore itu tak dapat menyelesaikan operasi Down, maka salah satu dipilih oleh system dan menyelesaikan operasi Down-nya. Urutan proses yang dipilih tidak ditentukan oleh Djikstra, dapat dipilih secara acak. Adanya semaphore mempermudah persoalan mutual exclusion. Skema penelesaian mutual exclusion mempunyai bagan sebagai berikut:

Sebelum masuk critical section, proses melakukan Down. Bila berhasil maka proses masuk ke critical section. Bila tidak berhasil maka proses di-blocked atas semaphore itu. Proses yang diblocked akan dapat melanjutkan kembali bila proses yang ada di critical section keluar dan melakukan opersai up sehingga menjadikan proses yang diblocked ready dan melanjutkan sehingga opersi Down-nya berhasil.

6. Problem Klasik pada Sinkronisasi

Ada tiga hal yang selalu memjadi masalah pada proses sinkronisasi:

a.    Problem Bounded buffer.

b.    Problem Reades and Writer.

c.    Problem Dining Philosophers.

7. Monitors

Solusi sinkronisasi ini dikemukakan oleh Hoare pada tahun 1974. 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.

Properti-properti monitor adalah sebagai berikut:

a.    Variabel-variabel data lokal, hanya dapat diakses oleh prosedur-prosedur dala monitor dan tidak oleh prosedur di luar monitor.

b.    Hanya satu proses yang dapat aktif di monitor pada satu saat. Kompilator harus mengimplementasi ini(mutual exclusion).

c.    Terdapat cara agar proses yang tidak dapat berlangsung di-blocked. Menambahkan variabel-variabel kondisi, dengan dua operasi, yaitu Wait dan Signal.

d.   Wait: Ketika prosedur monitor tidak dapat berkanjut (misal producer menemui buffer penuh) menyebabkan proses pemanggil diblocked dan mengizinkan proses lain masuk monitor.

e.    Signal: Proses membangunkan partner-nya yang sedang diblocked dengan signal pada variabel kondisi yang sedang ditunggu partnernya.

f.     Versi Hoare: Setelah signal, membangunkan proses baru agar berjalan dan menunda proses lain.

g.    Versi Brinch Hansen: Setelah melakukan signal, proses segera keluar dari monitor.

Dengan memaksakan disiplin hanya satu proses pada satu saat yang berjalan pada monitor, monitor menyediakan fasilitas mutual exclusion. Variabel-variabel data dalam monitor hanya dapat diakses oleh satu proses pada satu saat. Struktur data bersama dapat dilindungi dengan menempatkannya dalam monitor. Jika data pada monitor merepresentasikan sumber daya, maka monitor menyediakan fasilitas mutual exclusion dalam mengakses sumber daya itu.

B.  Deadlock

Deadlock yang mungkin dapat terjadi pada suatu proses disebabkan proses itu menunggu suatu kejadian tertentu yang tidak akan pernah terjadi. Dua atau lebih proses dikatakan berada dalam kondisi deadlock, bila setiap proses yang ada menunggu suatu kejadian yang hanya dapat dilakukan oleh proses lain dalam himpunan tersebut. Terdapat kaitan antara overhead dari mekanisme koreksi dan manfaat dari koreksi deadlock itu sendiri. Pada beberapa kasus, overhead atau ongkos yang harus dibayar untuk membuat sistem bebas deadlock menjadi hal yang terlalu mahal dibandingkan jika mengabaikannya. Sementara pada kasus lain, seperti pada real-time process control, mengizinkan deadlock akan membuat sistem menjadi kacau dan membuat sistem tersebut tidak berguna.

Contoh berikut ini terjadi pada sebuah persimpangan jalan. Beberapa hal yang dapat membuat deadlock pada suatu persimpangan, yaitu:

·       Terdapat satu jalur pada jalan.

·       Mobil digambarkan sebagai proses yang sedang menuju sumber daya.

·       Untuk mengatasinya beberapa mobil harus preempt (mundur).

·       Sangat memungkinkan untuk terjadinya starvation (kondisi proses tak akan mendapatkan sumber daya).

1.  Peranan Deadlock

Menurut Coffman 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 berada pada suatu proses tidak dapat diambil secara paksa dari proses tersebut,sampai proses itu melepaskannya.

g.      Circular Wait

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

2.   Resources-Allocation Graph

Sebuah cara visual (matematika) untuk menentukan apakah ada deadlock, atau kemungkinan terjadinya.

G = (V, E) Graf berisi node and edge. Node V terdiri dari proses-proses = {P1, P2, P3, ...} dan jenis resource. {R1, R2, ...} Edge E adalah (Pi, Rj) atau (Ri, Pj)

Sebuah panah dari process ke resource menandakan proses meminta resource. Sebuah panah dari resource ke process menunjukkan sebuah instance dari resource telah dtempatkan ke proses. Process adalah lingkaran, resource adalah kotak; titik-titik merepresentasikan jumlah instance dari resource Dalam tipe. Meminta poin-poin ke kotak, perintah datang dari titik.

Jika graf tidak berisi lingkaran, maka tidak ada proses yang deadlock. Jika membentuk lingkaran, maka:

a.       jika tipe resource memiliki banyak instance, maka deadlock DAPAT ada.

b.      jika setiap tipe resource mempunyai satu instance, maka deadlock telah terjadi.

3.  Strategi menghadapi Deadlock

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

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

4.  Strategi Ostrich

Pendekatan yang paling sederhana adalah dengan menggunakan strategi burung unta: masukkan kepala dalam pasir dan seolah-olah tidak pernah ada masalah sama sekali. Beragam pendapat muncul berkaitan dengan strategi ini. Menurut para ahli Matematika, cara ini sama sekali tidak dapat diterima dan semua keadaan deadlock harus ditangani. Sementara menurut para ahli Teknik, jika komputer lebih sering mengalami kerusakkan disebabkan oleh kegagalan hardware, error pada kompilator atau bugs pada sistem operasi. Maka ongkos yang dibayar untuk melakukan penanganan deadlock sangatlah besar dan lebih baik mengabaikan keadaan deadlock tersebut. Metode ini diterapkan pada sistem operasi UNIX dan MINIX.

5.  Mencegah Deadlock

Metode ini merupakan metode yang paling sering digunakan. Metode Pencegahan dianggap sebagai solusi yang bersih dipandang dari sudut tercegahnya deadlock. Tetapi pencgahan akan mengakibatkan kinerja utilisasi sumber daya yang buruk.

Metode pencegahan menggunakan pendekatan dengan cara meniadakan empat syarat yang dapat menyebabkan deadlock terjadi pada saat eksekusi Coffman (1971).

Syarat pertama yang akan dapat ditiadakan adalah Mutual Exclusion, jika tidak ada sumber daya yang secara khusus diperuntukkan bagi suatu proses maka tidak akan pernah terjadi deadlock. Namun jika membiarkan ada dua atau lebih proses mengakses sebuah sumber daya yang sama akan menyebabkan chaos. Langkah yang digunakan adalah dengan spooling sumber daya, yaitu dengan mengantrikan job-job pada antrian dan akan dilayani satu-satu.

Beberapa masalah yang mungkin terjadi adalah:

i.      Tidak semua dapat di-spool, tabel proses sendiri tidak mungkin untuk di-spool

ii.    Kompetisi pada ruang disk untuk spooling sendiri dapat mengarah pada deadlock

Hal inilah yang menyebabkan mengapa syarat pertama tidak dapat ditiadakan, jadi mutual exclusion benar-benar tidak dapat dihilangkan.

Cara kedua dengan meniadakan kondisi hold and wait terlihat lebih menjanjikan. Jika suatu proses yang sedang menggunakan sumber daya dapat dicegah agar tidak dapat menunggu sumber daya yang lain, maka deadlock dapat dicegah. Langkah yang digunakan adalah dengan membuat proses agar meminta sumber daya yang mereka butuhkan pada awal proses sehingga dapat dialokasikan sumber daya yang dibutuhkan. Namun jika terdapat sumber daya yang sedang terpakai maka proses tersebut tidak dapat memulai prosesnya.

Masalah yang mungkin terjadi:

i.      Sulitnya mengetahui berapa sumber daya yang dibutuhkan pada awal proses

ii.    Tidak optimalnya pengunaan sumber daya jika ada sumber daya yang digunakan hanya beberapa waktu dan tidak digunakan tapi tetap dimiliki oleh suatu proses yang telah memintanya dari awal.

Meniadakan syarat ketiga non preemptive ternyata tidak lebih menjanjikan dari meniadakan syarat kedua, karena dengan meniadakan syarat ketiga maka suatu proses dapat dihentikan ditengah jalan. Hal ini tidak dimungkinkan karena hasil dari suatu proses yang dihentikan menjadi tidak baik.

Cara terakhir adalah dengan meniadakan syarat keempat circular wait. Terdapat dua pendekatan, yaitu:

i.      Mengatur agar setiap proses hanya dapat menggunakan sebuah sumber daya pada suatu waktu, jika menginginkan sumber daya lain maka sumber daya yang dimiliki harus dilepas.

ii.    Membuat penomoran pada proses-proses yang mengakses sumber daya. Suatu proses dimungkinkan untuk dapat meminta sumber daya kapan pun, tetapi permintaannya harus dibuat terurut.

Masalah yang mungkin terjadi dengan mengatur bahwa setiap proses hanya dapat memiliki satu proses adalah bahwa tidak semua proses hanya membutuhkan satu sumber daya, untuk suatu proses yang kompleks dibutuhkan banyak sumber daya pada saat yang bersamaan. Sedangkan dengan penomoran masalah yang dihadapi adalah tidak terdapatnya suatu penomoran yang dapat memuaskan semua pihak.

Secara ringkas pendekatan yang digunakan pada metode pencegahan deadlock dan masalah-masalah yang menghambatnya, terangkum dalam tabel dibawah ini.

Tabel 3-1. Tabel Deadlock

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

6.  Menghindari Deadlock

Pendekatan metode ini adalah dengan hanya memberi 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 diberikan. Kondisi ini terjadi ketika setelah sumber daya yang sebelumnya dipegang oleh proses lain telah dilepaskan.

Kondisi aman yang dimaksudkan selanjutnya disebut sebagai safe-state, sedangkan keadaan yang tidak memungkinkan untuk diberikan sumber daya yang diminta disebut unsafe-state.

7. Kondisi Aman (Safe state)

Suatu keadaan dapat dinyatakan sebagai safe state jika tidak terjadi deadlock dan terdapat cara untuk memenuhi semua permintaan sumber daya yang ditunda tanpa menghasilkan deadlock. Dengan cara mengikuti urutan tertentu.

8. Kondisi Tak Aman (Unsafe state)

Suatu state dinyatakan sebagai state tak selamat (unsafe state) jika tidak terdapat cara untuk memenuhi semua permintaaan yang saat ini ditunda dengan menjalankan proses-proses dengan suatu urutan.

9. Algoritma Bankir

Algoritma penjadualan ini diungkapkan oleh Dijkstra (1965) lebih dikenal dengan nama Algoritma Bankir. Model ini menggunakan suatu kota kecil sebagai percontohan dengan suatu bank sebagai sistem operasi, pinjaman sebagai sumber daya dan peminjam sebagai proses yang membutuhkan sumber daya. Deadlock akan terjadi apabila terdapat seorang peminjam yang belum mengembalikan uangnya dan ingin meminjam kembali, padahal uang yang belum dikembalikan tadi dibutuhkan oleh peminjam lain yang juga belum mengembalikan uang pinjamannya.

Beberapa kelemahan algoritma Bankir Tanenbaum (1992), Stallings (1995) dan Deitel (1990) adalah sebagai berikut:

i.      Sulit untuk mengetahui seluruh sumber daya yang dibutuhkan proses pada awal eksekusi.

ii.    Jumlah proses yang tidak tetap dan berubah-ubah.

iii.  Sumber daya yang tadinya tersedia dapat saja menjadi tidak tersedia kembali.

iv.  Proses-proses yang dieksekusi haruslah tidak dibatasi oleh kebutuhan sinkronisasi antar proses.

v.    Algoritma ini menghendaki memberikan semua permintaan selama waktu yang berhingga.

10. Mendeteksi Deadlock dan Memulihkan Deadlock

Metode ini mengunakan pendekatan dengan teknik untuk menentukan apakah deadlock sedang terjadi serta proses-proses dan sumber daya yang terlibat dalam deadlock tersebut. Setelah kondisi deadlock dapat dideteksi, maka langkah pemulihan dari kondisi deadlock dapat segera dilakukan. Langkah pemulihan tersebut adalah dengan memperoleh sumber daya yang diperlukan oleh proses-proses yang membutuhkannya. Beberapa cara digunakan untuk mendapatkan sumber daya yang diperlukan, yaitu dengan terminasi proses dan pre-emption (mundur) suatu proses. Metode ini banyak digunakan pada komputer mainframe berukuran besar.

C. Kesimpulan

Untuk mengatasi problem critical section dapat digunakan berbagai solusi software. Namun masalah yang akan timbul dengan solusi software adalah solusi software tidak mampu menangani masalah yang lebih berat dari critical section. Tetapi Semaphores mampu menanganinya, terlebih jika hardware yang digunakan mendukung maka akan memudahkan dalam menghadapi problem sinkronisasi. Berbagai contoh klasik problem sinkronisasi berguna untuk mengecek setiap skema baru sinkronisasi. Monitor termasuk ke dalam level tertinggi mekanisme sinkronisasi yang berguna untuk mengkoordinir aktivitas dari banyak thread ketika mengakses data melalui pernyataan yang telah disinkronisasi. Kondisi deadlock akan dapat terjadi jika terdapat dua atau lebih proses yang akan mengakses sumber daya yang sedang dipakai oleh proses yang lainnya. Pendekatan untuk mengatasi deadlock dipakai tiga buah pendekatan, yaitu:

·       Memastikan bahwa tidak pernah dicapai kondisi deadlock

·       Membiarkan deadlock untuk terjadi dan memulihkannya

·       Mengabaikan apa pun deadlock yang terjadi

Dari ketiga pendekatan diatas, dapat diturunkan menjadi empat buah metode untuk mengatasi deadlock, yaitu:

·       Pencegahan deadlock

·       Menghindari deadlock

·       Mendeteksi deadlock

·       Pemulihan deadlock

Namun pada sebagian besar Sistem Operasi dewasa ini mereka lebih condong menggunakan pendekatan untuk mengabaikan semua deadlock yang terjadi. Silberschatz (1994) merumuskan sebuah strategi penanggulangan deadlock terpadu yang dapat disesuaikan dengan kondisi dan situasi yang berbeda, strateginya sendiri berbunyi:

1.      Kelompokkan sumber daya kedalam kelas yang berbeda

2.     Gunakan strategi pengurutan linear untuk mencegah kondisi circular waityang nantinya.

3.    Gunakan algoritma yang paling cocok untuk suatu kelas sumber daya yang berbeda satu dengan yang lain.