Testing Computer Network

Tes

SINKRONISASI DAN DEADLOCK

Sinkronisai

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. 

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.

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.

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)

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

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.

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.

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.

Deadlock

Deadlock dalam arti sebenarnya adalah kebuntuan. Kebuntuan yang dimaksud dalam sistem operasi adalah kebuntuan proses. Jadi Deadlock ialah suatu kondisi dimana proses tidak berjalan lagi atau tidak ada komunikasi lagi antar proses. Deadlock disebabkan karena proses yang satu menunggu sumber daya yang sedang dipegang oleh proses lain, proses lain itu pun sedang menunggu sumber daya yang dipegang olehnya. Dengan kata lain setiap proses dalam set menunggu untuk sumber yang hanya dapat dikerjakan oleh proses lain dalam set sedang menunggu. Contoh sederhananya ialah pada gambar berikut ini.

Gambar  Deadlock terjadi pada persimpangan jalan

Dalam kasus ini setiap mobil bergerak sesuai nomor yang ditentukan, tetapi tanpa pengaturan yang benar, maka setiap mobil akan bertemu pada satu titik yang permanen (yang dilingkari) atau dapat dikatakan bahwa setiap mobil tidak dapat melanjutkan perjalanan lagi atau dengan kata lain terjadi Deadlock. 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. Sumber daya ini tidak habis dipakai oleh proses mana pun.Tetapi setelah proses berakhir, sumber daya ini dikembalikan untuk dipakai oleh proses lain yang sebelumnya tidak kebagian sumber daya ini. Contohnya prosesor, Channel I/O, disk, semaphore. Contoh peran sumber daya jenis ini pada terjadinya Deadlock ialah misalnya sebuah proses memakai disk A dan B, maka akan terjadi Deadlock jika setiap proses sudah memiliki salah satu disk dan meminta disk yang lain. Masalah ini tidak hanya dirasakan oleh pemrogram tetapi oleh seorang yang merancang sebuah sistem operasi. Cara yang digunakan pada umumnya dengan cara memperhitungkan dahulu sumber daya yang digunakan oleh proses-proses yang akan menggunakan sumber daya tersebut. Deadlock dari sumber yang dapat dipakai berulang-ulang ialah berkaitan dengan jumlah proses yang memakai memori utama. Ada empat kondisi yang dapat menyebabkan terjadinya deadlock. Keempat kondisi tersebut tidak dapat berdiri sendiri, namun saling mendukung.

1. Mutual exclusion. Hanya ada satu proses yang boleh memakai sumber daya, dan proses lain yang ingin memakai sumber daya tersebut harus menunggu hingga sumber daya tadi dilepaskan atau tidak ada proses yang memakai sumber daya tersebut.

2. Hold and wait. Proses yang sedang memakai sumber daya boleh meminta sumber daya lagi maksudnya menunggu hingga benar-benar sumber daya yang diminta tidak dipakai oleh proses lain, hal ini dapat menyebabkan kelaparan sumber daya sebab dapat saja sebuah proses tidak mendapat sumber daya dalam waktu yang lama.

3. No preemption. Sumber daya yang ada pada sebuah proses tidak boleh diambil begitu saja oleh proses lainnya. Untuk mendapatkan sumber daya tersebut, maka harus dilepaskan terlebih dahulu oleh proses yang memegangnya, selain itu seluruh proses menunggu dan mempersilahkan hanya proses yang memiliki sumber daya yang boleh berjalan.

4. Circular wait. Kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses berikutnya.

Sebuah sistem komputer terdiri dari berbagai macam sumber-daya (resources), seperti:

Ø  Fisik (Perangkat, Memori)

Ø  Logika (Lock, Database record)

Ø  Sistem Operasi (PCB Slots)

Ø  Aplikasi (Berkas)

Diantara sumber-daya tersebut ada yang preemptable dan ada juga yang tidak. Sumber-daya ini akan digunakan oleh proses-proses yang membutuhkannya. Mekanisme hubungan dari proses-proses dan sumber-daya yang dibutuhkan/digunakan dapat di diwakilkan dengan graf. Graf adalah suatu struktur diskrit yang terdiri dari vertex dan sisi, dimana sisi menghubungkan vertexvertex yang ada. Berdasarkan tingkat kompleksitasnya, graf dibagi menjadi dua bagian, yaitu simple graf dan multigraf. Simpel graf tidak mengandung sisi paralel (lebih dari satu sisi yang menghubungkan dua vertex yang sama). Berdasarkan arahnya graf dapat dibagi menjadi dua bagian yaitu graf berarah dan graf tidak berarah. Graf berarah memperhatikan arah sisi yang menghubungkan dua vertex, sedangkan graf tidak berarah tidak memperhatikan arah sisi yang menghubungkan dua vertex. Dalam hal ini akan dibahas mengenai implementasi graf dalam sistem operasi. Salah satunya dalah graf alokasi sumber daya. Graf alokasi sumber daya merupakan graf sederhana dan graf berarah. Graf alokasi sumber daya adalah bentuk visualisasi dalam mendeteksi maupun menyelesaikan masalah deadlock. Graf alokasi sumber daya mempunyai komponen- komponen layaknya graf biasa. Hanya saja dalam graf alokasi sumber daya ini, vertex dibagi menjadi dua jenis yaitu:

1. Proses P= {P0, P1, P2, P3,..., Pi,..., Pm}. Terdiri dari semua proses yang ada di sistem. Untuk

proses, vertexnya digambarkan sebagai lingkaran dengan nama prosesnya.

2. Sumber daya R= {R0, R1, R2, R3,..., Rj,..., Rn}. Terdiri dari semua sumber daya yang ada di

sistem. Untuk sumber daya, vertexnya digambarkan sebagai segi empat dengan instansi yang dapat dialokasikan serta nama sumber dayanya.

Sisi, E={Pi®Rj,…, Rj®Pi} terdiri dari dua jenis, yaitu:

a. Sisi permintaan: Pi®Rj Sisi permintaan menggambarkan adanya suatu proses Pi yang meminta

sumber daya Rj.

b. Sisi alokasi: Rj®Pi. Sisi alokasi menggambarkan adanya suatu sumber daya Rj yang

mengalokasikan salah satu instansi-nya pada proses Pi.

Misalkan suatu graph pengalokasian sumber daya dengan ketentuan sebagai berikut:

Himpunan P,R dan E:

• P={P1, P2, P3}

• R={R1, R2, R3, R4}

• E={P1®R1, P2®R3, R1®P3, R2®P2, R2®P1, R3®P3}

Instansi sumber daya:

ü  R1 memiliki satu instansi

ü  R2 memiliki dua instansi

ü  R3 memiliki satu instansi

ü  R4 memiliki tiga instansi

Status Proses:

ü  Proses P1 mengendalikan sebuah instansi R2 dan menunggu sebuah instansi dari R1.

ü  Proses P2 mengendalikan sebuah instansi dari R1 dan R2, dan menunggu sebuah instansi R3

ü  Proses P3 mengendalikan sebuah instansi dari R3.

Pada gambar graph di atas tidak terdapat adanya cycle, sehingga proses tidak mengalami terjadinya deadlock. Sekarang perhatikan graph berikut yang terdapat cycle dan memungkinkan terjadinya deadlock.

Terdapat dua cycle (circuit) pada graph di atas yaitu:

P1®R1®P2®R3®P3®R2®P1 dan P2®R3®P3®R2®P2

Proses P1, P2 dan P3 terjadi deadlock. Proses P2 menunggu R3, dimana sedang dikendalikan oleh P3. Proses P3 di sisi lain sedang menunggu proses P1 dan P2 melepas sumber daya R2. Kemudian P1 menunggu proses P2 melepas sumber daya R1. Sekarang perhatikan graph berikut yang terdapat cycle P1®R1®P3®R2®P1.

Walaupun terdapat cycle namun pada proses-proses tersebut tidak terjadi deadlock. Proses P4 akan melepas instansi sumber daya R2 yang akan dialokasikan untuk proses P3.

Solusi Penanggulangan Deadlock

Add beberapa cara untuk menanggulangi terjadinya deadlock, diantaranya adalah:

ü  Mengabaikan masalah deadlock.

ü  Mendeteksi dan memperbaiki

ü  Penghindaran yang terus menerus dan pengalokasian yang baik dengan menggunakan protocol untuk memastikan sistem tidak pernah memasuki keadaan deadlock. Yaitu dengan deadlock avoidance sistem untuk mendata informasi tambahan tentang proses mana yang akan meminta dan menggunakan sumber daya.

ü  Pencegahan yang secara struktur bertentangan dengan empat kondisi terjadinya deadlock dengan deadlock prevention sistem untuk memastikan bahwa salah satu kondisi yang penting tidak dapat menunggu.

Mengabaikan Masalah Deadlock

Untuk memastikan sistem tidak memasuki deadlock, sistem dapat menggunakan pencegahan deadlock atau penghindaran deadlock. Penghindaran deadlock membutuhkan informasi tentang sumber daya yang mana yang akan suatu proses meminta dan berapa lama akan digunakan. Dengan informasi tersebut dapat diputuskan apakah suatu proses harus menunggu atau tidak. Hal ini disebabkan oleh keberadaan sumber daya, apakah ia sedang digunakan oleh proses lain atau tidak. Metode ini lebih dikenal dengan Algoritma Ostrich. Dalam algoritma ini dikatakan bahwa untuk menghadapi Deadlock ialah dengan berpura-pura bahwa tidak ada masalah apa pun. Hal ini seakanakan melakukan suatu hal yang fatal, tetapi sistem operasi Unix menanggulangi Deadlock dengan cara ini dengan tidak mendeteksi Deadlock dan membiarkannya secara otomatis mematikan program sehingga seakan-akan tidak terjadi apa pun. Jadi jika terjadi Deadlock, maka tabel akan penuh, sehingga proses yang menjalankan proses melalui operator harus menunggu pada waktu tertentu dan mencoba lagi.

Mendeteksi dan Memperbaiki

Caranya ialah dengan cara mendeteksi jika terjadi deadlock pada suatu proses maka dideteksi system mana yang terlibat di dalamnya. Setelah diketahui sistem mana saja yang terlibat maka diadakan proses untuk memperbaiki dan menjadikan sistem berjalan kembali. Jika sebuah sistem tidak memastikan deadlock akan terjadi, dan juga tidak didukung dengan pendeteksian deadlock serta pencegahannya, maka kita akan sampai pada kondisi deadlock yang dapat berpengaruh terhadap performance sistem karena sumber daya tidak dapat digunakan oleh proses sehingga proses-proses yang lain juga terganggu. Akhirnya sistem akan berhenti dan harus direstart.

Hal-hal yang terjadi dalam mendeteksi adanya Deadlock adalah:

ü  Permintaan sumber daya dikabulkan selama memungkinkan.

ü  Sistem operasi memeriksa adakah kondisi circular wait secara periodik.

ü  Pemeriksaan adanya deadlock dapat dilakukan setiap ada sumber daya yang hendak digunakan oleh sebuah proses.

ü  Memeriksa dengan algoritma tertentu.

Ada beberapa jalan untuk kembali dari Deadlock, yaitu:

ü  Lewat Preemption

Dengan cara untuk sementara waktu menjauhkan sumber daya dari pemakainya, dan memberikannya pada proses yang lain. Ide untuk memberi pada proses lain tanpa diketahui oleh pemilik dari sumber daya tersebut tergantung dari sifat sumber daya itu sendiri. Perbaikan dengan cara ini sangat sulit atau dapat dikatakan tidak mungkin. Cara ini dapat dilakukan dengan memilih korban yang akan dikorbankan atau diambil sumber dayanya untuk sementara, tentu saja harus dengan perhitungan yang cukup agar waktu yang dikorbankan seminimal mungkin. Setelah kita melakukan preemption dilakukan pengkondisian proses tersebut dalam kondisi aman. Setelah itu proses dilakukan lagi dalam kondisi aman tersebut.

ü  Lewat Melacak Kembali

Setelah melakukan beberapa langkah preemption, maka proses utama yang diambil sumber dayanya akan berhenti dan tidak dapat melanjutkan kegiatannya, oleh karena itu dibutuhkan langkah untuk kembali pada keadaan aman dimana proses masih berjalan dan memulai proses lagi dari situ. Tetapi untuk beberapa keadaan sangat sulit menentukan kondisi aman tersebut, oleh karena itu umumnya dilakukan cara mematikan program tersebut lalu memulai kembali proses. Meski pun sebenarnya lebih efektif jika hanya mundur beberapa langkah saja sampai deadlock tidak terjadi lagi. Untuk beberapa sistem mencoba dengan cara mengadakan pengecekan beberapa kali secara periodik dan menandai tempat terakhir kali menulis ke disk, sehingga saat terjadi deadlock dapat mulai dari tempat terakhir penandaannya berada.

ü  Lewat mematikan proses yang menyebabkan Deadlock

Cara yang paling umum ialah mematikan semua proses yang mengalami deadlock. Cara ini paling umum dilakukan dan dilakukan oleh hampir semua sistem operasi. Namun, untuk beberapa sistem, kita juga dapat mematikan beberapa proses saja dalam siklus deadlock untuk menghindari deadlock dan mempersilahkan proses lainnya kembali berjalan. Atau dipilih salah satu korban untuk melepaskan sumber dayanya, dengan cara ini maka masalah pemilihan korban menjadi lebih selektif, sebab telah diperhitungkan beberapa kemungkinan jika si proses harus melepaskan sumber dayanya.

Kriteria pemilihan korban ialah:

ü  Yang paling jarang memakai prosesor

ü  Yang paling sedikit hasil programnya

ü  Yang paling banyak memakai sumber daya sampai saat ini

ü  Yang alokasi sumber daya totalnya tersedkit

ü  Yang memiliki prioritas terkecil

Menghindari Deadlock

Pada sistem kebanyakan permintaan terhadap sumber daya dilakukan sebanyak sekali saja. Sistem sudah harus dapat mengenali bahwa sumber daya itu aman atau tidak (tidak terkena deadlock), setelah itu baru dialokasikan. Ada dua cara yaitu:

ü  Jangan memulai proses apa pun jika proses tersebut akan membawanya pada kondisi deadlock, sehingga tidak mungkin terjadi deadlock karena pada saat akan menuju deadlock, proses sudah dicegah.

ü  Jangan memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika penambahan ini akan membawa kita pada suatu keadaan deadlock. Jadi diadakan dua kali penjagaan, yaitu saat pengalokasian awal, dijaga agar tidak deadlock dan ditambah dengan penjagaan kedua saat suatu proses meminta sumber daya, dijaga agar jangan sampai terjadi deadlock. Pada sistem deadlock avoidance (penghindaran) dilakukan dengan cara memastikan bahwa program memiliki maksimum permintaan. Dengan kata lain cara sistem ini memastikan terlebih dahulu bahwa sistem akan selalu dalam kondisi aman. Baik mengadakan permintaan awal atau pun saat meminta permintaan sumber daya tambahan, sistem harus selalu berada dalam kondisi aman.

Status Aman

Status ini terjadi jika sistem dapat mengalokasikan sumber daya bagi tiap proses dalam keadaan tertentu dan masih dapat terjadi deadlock. Status aman bukanlah status deadlock, jadi status deadlock merupakan status tidak aman, tetapi tidak selamanya status tidak aman mengakibatkan status deadlock melainkan ada kemungkinan dapat terjadi.

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:

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

ü  Jumlah proses yang tidak tetap dan berubah-ubah.

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

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

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

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. 

Terminasi Proses

Metode ini akan menghapus proses-proses yang terlibat pada kondisi deadlock dengan mengacu pada beberapa syarat. Beberapa syarat yang termasuk dalam metode ini adalah, sebagai berikut:

• Menghapus semua proses yang terlibat dalam kondisi deadlock (solusi ini terlalu mahal).
• Menghapus satu persatu proses yang terlibat, sampai kondisi deadlock dapat diatasi (memakan banyak waktu).
• Menghapus proses berdasarkan prioritas, waktu eksekusi, waktu untuk selesai, dan kedalaman dari rollback.

Resources Preemption

Metode ini lebih menekankan kepada bagaimana menghambat suatu proses dan sumber daya, agar tidak terjebak pada unsafe condition.

Beberapa langkahnya, yaitu:

• Pilih salah satu - proses dan sumber daya yang akan di-preempt.
• Rollback ke safe state yang sebelumnya telah terjadi.
• Mencegah suatu proses agar tidak terjebak pada starvation karena metode ini.

MULTITASKING, KONKURENSI DAN THREAD

MULTITASKING, KONKURENSI, DAN THREAD

1.   MULTITASKING

            Multitasking adalah sebuah metode dimana banyak pekerjaan (proses) diolah dengan menggunakan sumber daya CPU yang sama dalam waktu yang hampir bersamaan. Dalam kasus sebuah computer dengan prosesor tunggal, hanya satu in instruksi yang dapat bekerja dalam satu waktu, berarti bahwa CPU tersebut secara aktif mengolah instruksi untuk satu pekerjaan tersebut.

            Multitasking memecahkan masalah ini dengan menjadwalkan pekerjaan mana yang dapat berjalan dalam satu waktu, dan kapan pekerjaan yang lain menunggu untuk diolah dapat dikerjakan. Kondisi mengalokasikan CPU dari pekerjaan satu ke pekerjaan yang lain disebut context switch. Ketika context switch terjadi dengan sangat cepat, kondisi ini cukup memberikan ilusi pengolahan-paralel. Bahkan dalam  komputer yang memiliki lebih dari satu CPU (multi-processor) multitasking memperbolehkan lebih banyak pekerjaan dijalankan dibanding dengan jumlah CPU yang tersedia.

Sistem operasi komputer dapat juga mengadopsi berbagai macam strategi penjadwalan, yang secara garis besar dapat dikategorikan sebagai berikut:

·         Dalam system multi-program, pekerjaan yang sedang diolah terus berjalan hingga membutuhkan suatu operasi yang memerlukan interaksi dari luar. Siatem multi-program didesain untuk memaksimalkan penggunaan CPU.

·         Dalam system time-sharing, pekerjaan yang sedang diolah diharuskan melepaskan kerja CPU, baik secara sukarela atau dari interaksi luar, seperti interupsi-perangkat-keras. Sistem time-sharing didesain untuk memperbolehkan beberapa program seolah diproses secara bersamaan.

·         Dalam system real-time, beberapa program ang sedang menunggu dijamin untuk mendapatkan pengolahan dari CPU ketika interaksi luar terjadi. Sistem real-time didesain untuk melakukan control mekanik seperti robot-robot industry, yang memerlukan ketepatan pemrosesan.

Saat ini, penggunaan time-sharing jarang digunakan, dan digantikan dengan multitasking.

Contoh sistem operasi jenis ini antara lain adalah linux. Linux adalah sistem operasi yang multitasking dan multiuser seperti kebanyakan SO yang ada pada saat ini. Multitasking pada linux artinya linux bisa atau mampu menjalankan beberapa proses dalam waktu yang bersamaan.

Seperti contoh pada saat kita menjalan kan aplikasi web browser kita juga bisa menjalankan aplikasi kompresi file. Sedangkan multiuser pada linux adalah user bisa login ke dalam sistem secara bersamaan, dengan artinya user bisa menggunakan satu sistem secara bersamaan dalam satu waktu. Multitasking dan multiuser pada sistem operasi merupakan satu keharusan dalam masa ini.

Banyak proses dijalankan hampir bersamaan, masing-masing proses mendapat bagian memori dan kendali tersendiri. Program yang dijalankan bersifat :

1.   Tidak bergantung (Independent) proses terpisah satu dari lainnya & tidak berpengaruh.

2.   Satu program pada satu saat (one program at any instant), pada satu waktu hanya satu proses yang dilayani pemroses, menggunakan interleave bukan overlap diantara program-program.

Keuntungasn system ini adalah:

·         Suatu perintah dapat dilaksanakan secara tuntas sampai berakhir dengan prioritas tertinggi.

·         Mampu memproses lebih dari satu perintah dalam waktu yang bersamaan.hal ini dapat terjadi karena kemampuan membagi sumber daya yang tersedia. Jika suatu perintah datang membutuhkan sumber daya media simpan menyelesaikan perintah/pekerjaan yang telah ditentukan, apabila datang perintah lain yang membutuhkan sumber daya memori misalnnya, perintah tersebut dapat langsung dikerjakan tanpa menunggu perintah sebelumnya selesai dierjakan.

Kelemahan dari sistem ini adalah jika terdapat banyak perintah, maka akan terjadi antian perintah yang cukup panjang. Pengguna harus menunggu perintah selesai dilaksanakan untuk memasukkan perintah selanjutnya.

Manfaat metode ini akan terasa ketika banyak terdapat perintah yang menggunakan sumber daya yang berbeda, sehingga rangkaina perintah dapat diselesaikan dengan lebih cepat.

2.   KONKURENSI

            Konkurensi adalah proses-proses (lebih dari satu proses) yang terjadi pada saat bersamaan. Konkurensi merupakan landasan umum perancangan sistem operasi. Proses-proses disebut konkuren jika proses-proses berada pada saat yang sama. Pada proses-proses konkuren yang berinteraksi mempunyai beberapa masalah yang harus diselesaikan:

a.       Mutual Exclusion

b.      Sinkronisasi

c.       Deadlock

d.      Startvation

A.  Prinsip-Prinsip Konkurensi

Konkurensi meliputi hal-hal sebagai berikut :
•    Alokasi waktu pemroses untuk proses-proses.
•    Pemakaian bersama dan persaingan untuk mendapatkan sumber daya.
•    Komunikasi antarproses.
•    Sinkronisasi aktivitas banyak proses.

Konkurensi dapat muncul pada konteks berbeda, antara lain:

a.    Banyak aplikasi (multiple application).

Multiprogramming memungkinkan banyak proses sekaligus dijalankan. Proses-proses dapat berasal dari aplikasi-aplikasi berbeda. Pada sistem multiprogramming bisa terdapat banyak aplikasi sekaligus yang dijalankan di sistem komputer.

b.    Aplikasi terstruktur.

Perluasan prinsip perancangan modular dan pemrograman terstruktur adalah suatu aplikasi dapat secara efektif diimplementasikan sebagai sekumpulan proses. Dengan sekumpulan proses, maka tiap proses menyediakan satu layanan spesifik tertentu.

c.     Struktur sistem operasi.

Keunggulan strukturisasi dapat juga diterapkan ke pemrograman sistem. Beberapa sistem operasi aktual yang dipasarkan dan yang sedang dalam riset telah diimplementasikan sebagai sekumpulan proses. Sistem operasi bermodelkan client/server menggunakan pendekatan ini.

d.   Untuk Strukturisasi Satu Proses.

Saat ini untuk peningkatan kinerja maka satu proses dapat memiliki banyak thread yang independen. Thread-thread tersebut harus dapat bekerjasama untuk mencapai tujuan proses.

B.  Interaksi Antar Proses

Pada sistem dengan banyak proses (kongkuren), terdapat 2 katagori interaksi, yaitu:

a.    Proses-proses Saling Tidak Peduli (Independen).
Proses-proses ini tidak dimaksudkan untuk bekerja untukmencapai tujuan tertentu. Pada multiprogramming dengan proses-proses independen, dapat berupa batch atau sesi interaktif, atau campuran keduanya.

b.     Proses-proses Saling Mempedulikan Secara Tidak Langsung.
Proses-proses tidak perlu saling mempedulikan identitas proses-proses lain, tapi sama-sama mengakses objek tertentu, seperti buffer masukan/keluaran. Proses-proses itu perlu bekerja sama (cooperation) dalam memakai bersama objek tertentu.

C.  Kesulitan- Kesulitan yang Ditimbulkan Konkurensi

Masalah yang dihadapi proses-proses kongkurensi pada multiprogramming dan multiprocessing serupa, yaitu: kecepatan eksekusi proses-proses di sistem tidak dapat diprediksi. Beberapa kemungkinan yang terjadi tidak dapat diprediksi seperti:

a.    Kecepatan proses pada sistem tergantung pada beberapa hal, antara lain:

·  Aktivitas proses-proses lain.

·  Cara sistem operasi menangani interupsi

·  Kebijaksanaan penjadwalan yang dilakukan oleh sistem operasi.

b.    Beberapa kesulitan yang dapat muncul, di antaranya adalah:

·  Pemakaian bersama sumber daya global.
Jika dua proses menggunakan variabel global yang sama, serta keduanya membaca dan menulis variabel itu maka urutan terjadinya pembacaan dan penulisan terhadap variabel itu menjadi kritis.

·  Pengelolaan alokasi sumber daya agar optimal
Jika proses A meminta suatu kanal masukan/keluaran tertentu dan dapat terjadi kemudian proses A di suspend sebelum menggunakan kanal itu. Jika sistem operasi mengunci kanal tersebut dan orang lain tidak dapat menggunakannya, maka akan terjadi inefisiensi.

·  Pencarian kesalahan pemrograman.
Pencarian kesalahan pada pemrograman kongkuren lebih sulit dibanding pencarian kesalahan pada program-program sekuen.

c.    Proses-proses konkuren mengharuskan beberapa hal yang harus ditangani, antara lain:

·  Sistem operasi harus mengetahui proses-proses yang aktif.

·  Sistem operasi harus mengalokasikan dan mendealokasikan beragam sumber daya untuk tiap proses aktif. Sumber daya yang harus dikelola, antara lain:

                             i.     Waktu pemroses

                           ii.     Memori

                         iii.     Berkas-berkas

                         iv.     Perangkat I/O

·  Sistem operasi harus memproteksi data dan sumber daya fisik masing-masing proses dari gangguan proses-proses lain.

·  Hasil-hasil proses harus independen terhadap kecepatan relatif proses-proses lain dimana eksekusi dilakukan.

D.  Pokok Penyelesaian Masalah Konkurensi

Pada dasarnya penyelesaian masalah kongkurensi terbagi menjadi 2, yaitu:

1.    Mengasumsikan adanya memori yang digunakan bersama.

2.    Tidak mengasumsikan adanya memori yang digunakan bersama.

Adanya memori bersama lebih memudahkan penyelesaian masalah kongkurensi. Metode memori bersama dapat dipakai untuk singleprocessor ataupun multiprocessor yang mempunyai memori bersama. Penyelesaian ini tidak dapat digunakan untuk multiprocessor tanpa memori bersama atau untuk sistem tersebar.

3.   THREAD

Thread adalah unit dasar dari penggunaan CPU, yang terdiri dari thread ID, program counter, set register, dan stack. Thread juga sering disebut Lightweight process. Thread berbagi code section, data section, dan sumber daya sistem operasi dengan thread lain yang termasuk dalam proses yang sama.

Keuntungan dari thread adalah :

·         Responsiveness : Melakukan multithreading pada aplikasi yang interaktif dapat membuat program terus berjalan meskipun bagian dari program tersebut diblok atau sedang menjalankan operasi yang panjang, karena itu dapat meningkatkan respon kepada user.

·         Resource sharing : sebuah aplikasi dapat mempunyai beberapa thread yang berbeda dalam sebuah alamat memori yang sama karena Thread berbagi memori dan sumber daya dari proses yang memilikinya.

·         Economy: karena mahal untuk mengalokasikan memori dan sumber daya untuk pembuatan proses. Alternatifnya adalah dengan penggunaan thread sebab thread berbagi sumber daya dari proses yang memilikinya oleh sebab itu akan lebih ekonomis untuk membuat sebuah thread.

·         Utilization of multiproccesor architectures: keuntungan dari multithreading dapat meningkat secara drastis dalam arsitektur multiprosesor, dimana setiap thread dapat berjalan secara pararel pada prosesor yang berbeda.

User threads didukung diatas kernel dan diimplementasikan oleh thread library pada level user. Library mendukung pembuatan thread, penjadwalan, dan manajemen tanpa dukungan dari kernel. Karena kernel tidak menyadari adanya user-level threads maka pembuatan semua thread dan penjadwalan dilakukan di dalam user space tanpa intervensi dari kernel. Kernel threads didukung secara langsung dari sistem operasi. Pembuatan thread, penjadwalan, dan manajemen dilakukan oleh sistem operasi, secara umum kernel threads lebih lambat untuk dibuat dan diatur dibanding user thread.

Fasilitas thread adalah mekanisme yang berguna yang diadopsi pada beberapa OS baru untuk mendukung resource sharing dan akses konkuren. Penggunaan thread sepadan dengan penggunaan system call “fork” dihasilkan dengan program counter baru, atau thread control dan mengeksekusinya dalam ruang alamat yang sama. Thread bekerjasama dengan thread yang lain dalam penggunaan bagian kode, bagian data, resource; seperti open file dan sinyal secara kolektif yang sering disebut task.

Dengan menggunakan fasilitas thread, CPU dapat secara ekstensif membagi di antara peer thread tanpa menggunakan manajemen memori. Meskipun context switch pada thread masih memerlukan register set switch, tetapi pembuatan thread lebih murah dibandingkan dengan context switch di antara proses heavy-weight.

Beberapa sistem mengimplementasikan “user-level threads” pada user-level library daripada melalui system call :

·         Sehingga switching thread tidak perlu memanggil OS dan menyebabkan interrupt ke kernel

·         Switching antara user-level thread dapat dilakukan secara independent dari OS (dapat dilakukan lebih cepat)