Sistem operasi

SISTEM OPERASI

MUTUAL EXCLUSION

Mutual exclusion adalah suatu cara yang menjamin jika ada sebuah proses yang  menggunakan  variable atau berkas yang sama  (digunakan juga oleh proses lain ) maka proses lain akan dikeluarkan dari pekerjaan yang sama. Jadi , mutual exclusive terjadi ketika hanya ada satu  proses yang boleh memakai sumber daya tersebut harus menunggu  hingga sumber daya tadi dilepaskan atau tidak ada proses yang memakai sumber daya tersebut. Pentingnya  mutual exclusion dapat dilihat pada ilustrasi berikut:

DEMON PRINTER

Demon printer adalah proses penjadwalan dan pengendalian pencetakan berkas-berkas di printer sehingga seolah-olah 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 akan dipakai menyimpan berkas yang ingin dijadwalkan untuk dicetak. Jika terdapat kondisi dimana dua proses atau lebih sedang membaca atau menulis data bersama (yaitu variable in) dengan 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 yaitu dengan cara mencegah lebih dari satu proses membaca atau menulis data bersama pada saat bersamaan.(Bambang Harianto, Sistem Operasi)

Bagian program yang sedang mengakses memori atau sumber daya yang dipakai bersama disebut critical section / region. Kesuksesan proses-proses kongkuren memerlukan pendefinisian critical section dan memaksakan mutual exclusion diantara proses-proses kongkuren yang sedang berjalan. Critical Region adalah bagian dari kode yang selalu dieksekusi di bawah kondisi mutual eksklusif. Critical Region menyerahkan penanganan kondisi mutual eksklusif tersebut dari tangan programmer (seperti yang terjadi dalam semafor) ke tangan  kompiler. Hal ini membantu mengurangi error yang terjadi karena kesalahan programmer dalam mengimplementasi semafor.

Kriteria Penyelesaian Mutual-Exclusion

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

1. Mutual-exclusion harus dijamin.

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

saat telah ada proses yang masuk critical section itu.

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

ingin masuk critical section.

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

yang tak berhingga atau tidak boleh terjadi deadlock maupun startvation.

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

harus diizinkan segera masuk tanpa ada waktu tunda.

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

METODE-METODE PENJAMIN MUTUAL EXCLUSION

1.                  Metode Naif

Disebut naïf karena tidak menyelesaikan masalah mutual exclusion. Metode-metode ini dipelajari untuk memperoleh gambaran lebih jelas mengenai mekanisme penjaminan mutual exclusion. Yang masuk metode naïf adalah:

Metode Variabel Lock Sederhana

Metode ini meniru mekanisme penguncian pintu dengan kunci pintu diganti variable lock. Variabel lock bernilai 0 berarti pintu tidak terkunci, berniali 1 berarti pintu terkunci. Metode ini gagal karena analogi ini tidak sepenuhnya sama, yaitu pengambilan kunci ( di computer berarti membaca variable lock) tidaklah sama, dengan di dunia fisik dimana pengambilan kunci berarti benar-benar pemakai-pemakai lain tidak dapat mengambilnya lagi, sementara pembacaan variable lock masih memungkinkan pemakai-pemakai lain membacanya.

-                      Mekanisme yang diusulkan :

Ketika proses hendak masuk critical section, proses lebih dulu memeriksa variable lock denagn ketentuan sebagai berikut:

-            Jika variable lock bernilai 0, proses menset variable lock menjadi 1 dan kemudian masuk critical section

-            Jika variable lock bernilai 1, proses menunggu sampai nilai variable lock menjadi 0 ( situasi ini berarti terdapat proses lain pada critical section)

2.                 Metode untuk Situasi Tertentu

Metode Bergantian secara Ketat

Metode ini mengasumsikan dapat menggilir masuk critical section secara bergantian terus-menerus. Variabel Turn (Giliran) mencatat (nomor)  proses yang sedang masuk critical section. Variabel turn diinisialisasi 0. Skenario yang terjadi adalah: Proses 0, memeriksa variable turn, berniali 0 dan segera memasuki critical section. Proses 1, menemukan variable turn berniali 0, melakukan loop memeriksa variable turn terus-menerus, memeriksa apakah turn telah berniali 1. kondisi ini disebut busy waiting, kalau hal ini terjadi lama maka cara ini harus dihindari karena banyak menyiakan waktu pemroses.

3.                  Metode Menggunakan Busy Waiting

-                      Metode Penyelesaian Dekker

Algoritma Dekker mempunyai properti-properti berikut :

> Tidak memerlukan instruksi-instruksi perangkat keras khusus

> Proses yang beroperasi di luar critical section tidak dapat mencegah proses lain masuk critical section itu.

> Proses yang ingin masuk critical section akan segera masuk bila dimungkinkan

Program sulit diikuti dan pembuktian kebenarannya memerlukan kecerdasan.

-                      Metode Penyelesaian Peterson

-                      Metode Pematian Interupsi

Proses mematikan interupsi ke pemroses dan segera memasuki critical section. Proses kembali mengaktifkan interupsi segera setelah meninggalkan critical section. Cara pematian interupsi mengakibatkan: Pemroses tidak dapat beralih ke proses lain, karena interupsi clock dimatikan sehingga penjadwal pun tidak dieksekusi. Karena penjadwal tidak beroperasi maka tidak terdapat alih proses, proses dapat memakai memori bersama tanpa takut intervensi proses lain karena memang tidak ada proses lain yang dieksekusi pada saat itu.

Kelemahan Utama:

-                  Bila proses yang mematikan interupsi mengalami gangguan (yaitu crash), maka proses tak akan pernah menghidupkan interupsi kembali. Kejadian ini menagkibatkan mematikam seluruh sistem.

-                  Jika terdapat dua pemroses atau lebih, mematikan interupsi hanya berpengaruh pada pemroses yang mengeksekusi instruksi tersebut. Pematian interupsi tidak mempengaruhi pemroses-pemroses lain, pemroses lain masih bebas memasuki critical section yang sedang dimasuki pemroses lain di pemroses lain. Teknik ini tidak dpat diterapkan pada system multiprocessors.

-         Metode dengan Instruksi Teks and Set Lock

Instruksi ini membaca isi memori ke register dan kemudian menyimpan nilai non-zero ke alamat memori itu. Operasi membaca isi memori dan menyimpan ke memori adalah atomic dijamin tak dapat diinterupsi. Tak ada pemroses lain yang dapat mengakses memori itu sampai instruksi berakhir. Pemroses yang mengeksekusi instruksi TSL mengunci bus memori, mencegah pemroses lain mengakses memori itu.

-         Metode dengan Instruksi Exchange (XCHG)

Instruksi ini disediakan mesin. Intel yang menyediakan. Instruksi ini saling menukarkan antra dua isi memori yang dilakukan secara atomic, tidak dapat disela. Instruksi dapat digunakan untuk implementasi mutual exclusion.

-         Karakteristik Pendekatan dengan Instruksi Mesin

Keunggulan:

Ø      Sederhana dan mudah diverifikasi

Ø      Dapat diterapkan ke sembarang jumlah proses baik di pemroses tunggal maupun bayak pemroses yang memakai memori bersama

Ø      Dapat digunakan untuk mendukung banyak critical region, tiap critical region didefinisikan dengan suatu variable

Kelemahan:

Ø      Merupakan metode dengan busy waiting, sangat tidak efisien. Selagi proses menunggu memasuki critical region, proses berlanjut mengkonsumsi waktu pemroses

Ø      Adanya busy waiting memungkinkan terjadinya deadlock dan starvation.

-         Dampak Adanya Busy Waiting

Metode dengan busy waiting mempunyai keterbatasan yaitu tidak dapat diterapkan pada system dengan penjadwalan berprioritas. Pada system dengan penjadwalan berprioritas, metode dengan busy waiting dapat menimbulkan deadlock. Aturan penjadwalan berprioritas selalu menjadwalkan proses-proses berprioritas lebih tinggi di antrian proses ready.

4.                  METODE SEMAPHORE

Prinsip semaphore yaitu dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Proses dipaksa berhenti sampai proses memperoleh penanda tertentu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan struktur penanda yang sesuai kebutuhannya. Variabel khusus untuk penandaan ini disebut semaphore. Terdapat dua operasi terhadap semaphore:

-                      Operasi Down

Operasi ini menurunkan nilai semaphore. Jika nilai semaphore menjadi nonpositif maka proses yang mengeksekusi di blocked.Operasi down adalah atomic (atomic action), tak dapat diinterupsi sebelum selesai. Menurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblocked sebagai instruksi tunggal. Sejak dimulai, tak ada proses lain yang dpat mengakses semaphore sampai operasi selessai atau di blocked.

-                      Operasi Up

Operasi menaikkan nilai semaphore. Jika satuproses atau lebih telah di blocked pada sustau semaphore tak dapat menyelesaikan operasi down, maka salah satu dipilih oleh system dan dibolehkan menyelesaikan operasi down-nya. Urutan proses yang dipilih tidak ditentukan, dapat dipili secara acak, FIFO, dan sebagainya sesuai keperluan dan kepentingan system.(Bambang Harianto, Sistem Operasi)

Deadlock pada Sistem Operasi

 Deadlock adalah keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya. Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah. Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses. Deadlock bisa digambarkan sebagai berikut :

Kejadian Deadlock selalu tidak lepas dari sumber daya, bahwa hampir seluruhnya merupakan masalah sumber daya yang digunakan bersama-sama. Oleh karena itu, kita juga perlu tahu tentang jenis sumber daya, yaitu: sumber daya dapat digunakan lagi berulang-ulang dan sumber daya yang dapat digunakan dan habis dipakai atau dapat dikatakan sumber daya sekali pakai.
(http://nugan88.wordpress.com/2011/10/03/deadlock-pada-sistem-operasi/ 25 April 2013. 21.56 WIB)

                    I.                        Model Deadlock

Urutan kejadian pengoprasian perangkat masukan/pengeluaran adalah :

·                  Meminta (request)          :meminta pelayanan perangkat masukan/keluaran

·                    Memakai (use)             : memakai perangkat masukan/keluaran

·                  Melepaskan (release)     : melepaskan pemakaian perangkat masukan/pengeluaran

Deadlock tidak hanya terjadi pada dua proses dan dua sumber daya,deadlock dapat terjadi dengan melibatkan lebih dari dua proses dan dua sumber daya. (Bambang Harianto, Sistem Operasi)

Penyebab terjadinya deadlock adalah :
A. Mutual Exclusion

 Yaitu suatu keadaan dimana hanya ada satu proses saja yang boleh memakai resource, proses yang lain harus menunggu sampai proses tadi benar-benar selesai. contoh mutual exclusion adalah “buffering” ketika kita menonton video.
B. Hold and Wait

Yaitu keadaan dimana suatu proses ‘kelaparan’ sumberdaya. Suatu proses menunggu suatu sumberdaya dalam waktu yang lama hingga sumberdaya tersebut tidak terpakai oleh proses lainnya.
C. No Pre-emption

Yaitu keadaan dimana suatu sumberdaya tidak boleh diambil(dipakai) begitu saja/secara paksa oleh proses yang lainnya sehingga suatu proses harus menunggu hingga proses yang sedang memakai sumberdaya benar-benar telah selesai.
D. circular wait

 Yaitu suatu keadaan dimana proses yang lain membutuhkan sumberdaya yang sedang dipakai oleh suatu proses sehingga timbul antrian melingkar (waiting chain) seperti halnya rantai.
Keempat penyebab timbulnya deadlock hampir sama yaitu penggunaan sumber daya dan waktu tunggu oleh suatu proses atau lebih.

(http://2010219ifunsika.wordpress.com/2012/12/26/deadlock-pada-sistem-operasi/ 25 April 2013. 22.03 WIB)

Penanganan Deadlock
Secara umum terdapat 4 cara untuk menangani keadaan deadlock, yaitu:
1. Pengabaian

 Maksud dari pengabaian di sini adalah sistem mengabaikan terjadinya deadlock dan pura-pura tidak tahu kalau deadlock terjadi. Dalam penanganan dengan cara ini dikenal istilah ostrich algorithm. Pelaksanaan algoritma ini adalah sistem tidak mendeteksi adanya deadlock dan secara otomatis mematikan proses atau program yang mengalami deadlock. Kebanyakan sistem operasi yang ada mengadaptasi cara ini untuk menangani keadaan deadlock. Cara penanganan dengan mengabaikan deadlock banyak dipilih karena kasus deadlock tersebut jarang terjadi dan relatif rumit dan kompleks untuk diselesaikan.

2. Pencegahan

 Penanganan ini dengan cara mencegah terjadinya salah satu karakteristik deadlock. Penanganan ini dilaksanakan pada saat deadlock belum terjadi pada sistem. Intinya memastikan agar sistem tidak akan pernah berada pada kondisi deadlock. Akan dibahas secara lebih mendalam pada bagian selanjutnya.

3. Penghindaran

 Menghindari keadaan deadlock. Bagian yang perlu diperhatikan oleh pembaca adalah bahwa antara pencegahan dan penghindaran adalah dua hal yang berbeda. Pencegahan lebih kepada mencegah salah satu dari empat karakteristik deadlock terjadi, sehingga deadlock pun tidak terjadi. Sedangkan penghindaran adalah memprediksi apakah tindakan yang diambil sistem, dalam kaitannya dengan permintaan proses akan sumber daya, dapat mengakibatkan terjadi deadlock. Akan dibahas secara lebih mendalam pada bagian selanjutnya.

4. Pendeteksian dan Pemulihan

Pada sistem yang sedang berada pada kondisi deadlock, tindakan yang harus diambil adalah tindakan yang bersifat represif. Tindakan tersebut adalah dengan mendeteksi adanya deadlock, kemudian memulihkan kembali sistem. Proses pendeteksian akan menghasilkan informasi apakah sistem sedang deadlock atau tidak serta proses mana yang mengalami deadlock. Akan dibahas secara lebih mendalam pada bagian selanjutnya. 
(http://blog.ugm.ac.id/2010/05/08/deadlock-dan-penanganannya/ 25 April 2013. 22.04 WIB)

                 II.                        Strategi Butrung Onta

Strategi ini disebut strategi onta karena kabar yang telah tyersebar, bahwa burung onta akan menyembunyikan kepalanya ke tanah bila mengetahui adanya bahaya yang mengancam. Bila solusi yang dilakukan justru sebenarnya tak memperdulikan adanya masalah.strategi ini sebenarnya berarti aadalah sama sekali tidak berusaha mengatasi deadlock atau tak ada metode sama sekali untuk mengatasi masaalah deadlock.

               III.                        Pencegahan Deadlock

Havender menyarankan strategi – strategi berikut untuk meniadakan syarat – syarat tersebut, yaitu :

·                   Tiap proses harus meminta semua sumber daya yang diperlukan sekaligus dan tidak berlanjut sampai semuanya diberikan.

·                   Jika proses telah sedang memegang sumber daya tertentu, untuk permintaan berikutnya proses harus melepas dahulu sumber daya yang dipegangnya.

·                   Beri pengurutan linear trerhadap tipe-tipe sumber daya pada semua proses, yaitu jika proses telah dialokasikan ssuatu tipe sumber daya.

              IV.                        Penghindaran Deadlock

Strategi ini biasanya diimplementasikan dengan pengalokasi sumber daya memeriksa dampak – dampak pemberian akses ke suatu permintaan.

·                    Jika pemberian akses akses sumber daya tidak mungkin menuju deadlock, sumber daya diberikan ke peminta.

·                    Jika tidak aman (memungkinkan timbulnya deadlock),proses yang meminta di-suspend sampai suatu waktu permintaannya aman diberikan.kondisi ini biasanya terjadi setelah satu sumber daya atau lebih yang semula di pegang oleh proses-proses aktif lain dilepas.

                 V.                        Deteksi pemulihan deadlock

·                    Deteksi adanya deadlock

Deteksi deadlock adalah tekhnik untuk menentukan apakah, deadlock terjadi serta mengidentifikasi proses – proses dan sumber daya yg terlobat deadlock. Umumnya algoritma -  algoritma deteksi yang digunakan adalah menentukan keberadaan menunggu sirkulasi ( circular wait ). Pengguna algoritma deteksi deadlock melibatkan over-head run time karena secara periodic dijalankan untuk menunggu sirkulasi.

·                    Pemulihan dari deadlock

Pemulihan dari deadlock dirumitkan oleh factor-faktor berikut :

                  Belum tentu dapat melakukan adanya deadlock secepatnya.

                  Kebanyakan system tidak memiliki fasilitas atau tidak memiliki fasilitas yang buruk untuk men-suspend proses,menghilangkan dari system dan me-resume proses dilain waktu. Pada system waktu nyata yang harus berfungsi terus-menerus, proses-proses tidak dapat di suspend dan di-resume.

                  Bahkan jika terdapat kemampuan suspend dan resume yangefektif. Kemampuan ini melibatkan sejumlah over head  berarti dan memerlukan perhatian operator yang berkemampuan tinggi. Operator semacam ini tidak selalu  tersedia.

                  Pemulihan memerlukan sejumlah kerja yang bararti.

Teknik pemulihan yang biasa digunakan adalah menghilangkan proses-proses dalam system dan pengklaiman kembali (reclaim) sumber daya yang dipegang prose itu. Istilah “ pemulihan “ sebenarnya kurang berarti disini karena yang terjadi sesungguhnya adalah penyingkiran beberapa proses “untuk member manfaat”proses-proses lain. Pendekatan berikut dapat dilakukan untuk pemulihan deadlock. Pendekatan – pendekatan dituliskan terurut kecanggihan penyelesaiannya :

1.                     Abaikan semua proses yang terlibat deadlock.

2.                     Backup semua proses yang terlibat deadlock ke suatu checkpoint yang didefisinikan sebelumnya dan jalankan kembali semua prose situ.

3.                     Secara berurutan abaikan proses sampai tidak ada deadiock lagi. Setelah masing-masing penyingkiran,algoritma deteksi harus dijalankan untuk melihat apakah masih terdapat deadlock.

4.                     Secara berurutan preempt sumber daya sampai tidak ada deadlock lagi. Sebagaimana item 3. Proses yang kehilangan sumber daya karena preemption harus dikembalikan (rool-back) ke titik sebelum mmemperolah sumbert daya.

Untuk item 3 dan 4,criteria pemilihan proses yang akan disingkirkan (kill) atau di-suspend adalah dengan kriteria, sbb :

·                    Waktu pemrosesan yang telah dijalankan paling kecil.

·                    Jumlah baris kluaran yang di produksi paling kecil.

·                    Mempunyai estimasi sisa waktu eksekusi terbesar.

·                    Jumlah total sumber daya terkecil yang telah dialokasikan.

·                    Prioritas terkecil.

              VI.                        Strategi penanggulangan deadlock terpadu

Masing-masing tekhnik memilik keunggulan dan kelemahan, maka daripada berusaha merancang fasilitas system operasi dengan satu strategi penangfgulan deadlock maka lebih efisien menggunakan startegi-strategi berbeda untuk situasi berbeda. Silberschatz menyarankan satu pendekatan terpadu,yaitu:

ü                Kelompokkan sumber daya-sumber daya menjadi sejumlah kelas sumber daya.

ü                Gunakan strategi pengurutan linear seperti yang di definisikan pada pencegahan menunggu sirkular. Strategi ini digunakan untuk mencegah deadlock diantara kelas-kelas sumber daya berbeda.

ü                Dalam satu kelas sumber daya, gunakan algoritma yang paling cocok untuk kelas sumber daya itu.(Bambang Harianto, Ssitem Operasi)