Masalah-masalah Kongkruensi

1. A. KONGKURENSI

Perkembangan sistem komputer mendatang adalah menuju ke sistem multiprocessing, multiprogramming, terdistribusi1 dan paralel2 yang mengharuskan adanya proses-proses yang berjalan bersama dalam waktu yang bersamaan. Hal demikian merupakan masalah yang perlu perhatian dari perancang sistem operasi.

Kongkurensi merupakan landasan umum perancangan sistem operasi. Proses-proses disebut kongkurensi jika proses-proses (lebih dari satu proses) berada pada saat yang sama. Proses-proses yang mengalami kongkuren dapat berdiri sendiri (independen) atau dapat saling berinteraksi, sehingga membutuhkan sinkronisasi atau koordinasi proses yang baik.

Untuk penanganan kongkuren, bahasa pemograman saat ini telah memiliki mekanisme kongkurensi dimana dalam penerapannya perlu dukungan sistem operasi dimana bahasa berada.

Proses yang kongkuren ini mempunyai beberapa masalah yang harus diselesaikan, yaitu :

• Ø Mutual Exclusion (pengeluaran timbal balik)

Merupakan kondisi dimana terdapat sumber daya yang tidak dapat dipakai bersama pada waktu yang bersamaan (misalnya : printer, disk drive). Kondisi demikian disebut sumber daya kritis, dan bagian program yang menggunakan sumber daya kritis disebut critical region / section. Hanya satu program pada satu saat yang diijinkan masuk ke critical region. Pemrogram tidak dapat bergantung pada sistem operasi untuk memahami dan memaksakan batasan ini, karena maksud program tidak dapat diketahui oleh sistem operasi. Hanya saja, system operasi menyediakan layanan (system call) yang bertujuan untuk mencegah proses lain masuk ke critical section yang sedang digunakan proses tertentu. Pemrograman harus menspesifikasikan bagian-bagian critical section, sehingga sistem operasi akan menjaganya. Pentingnya mutual exclusion adalah jaminan hanya satu proses yang mengakses sumber daya pada suatu interval waktu.

Pemaksaan atau pelanggaran mutual exclusion menimbulkan :

• Deadlock
• Starvation
• Ø Deadlock (buntu)

Deadlock merupakan kondisi terparah karena banyak proses dapat terlibat dan semuanya tidak dapat mengakhiri prosesnya secara benar.

Ilustasi deadlock, misalnya :

• Terdapat dua proses, yaitu P1 dan P2 dan dua sumber daya kritis, yaitu R1 dan R2.
• Proses P1 dan P2 harus mengakses kedua sumber daya tersebut, dengan kondisi ini terjadi : R1 diberikan ke P1, sedangkan R2 diberikan ke P2.

Karena untuk melanjutkan eksekusi memerlukan kedua sumber daya sekaligus maka kedua proses akan saling menunggu sumber daya lain selamanya. Tak ada proses yang dapat melepaskan sumber daya yang telah dipegangnya karena menunggu sumber daya lain yang tak pernah diperolehnya. Kedua proses dalam kondisi deadlock, yang tidak dapat membuat kemajuan apapun dan deadlock merupakan kondisi terparah karena dapat melibatkan banyak proses dan semuanya tidak dapat mengakhiri prosesnya secara benar.

• Ø Starvation (kelaparan)

Starvation adalah keadaan dimana pemberian akses bergantian terus-menerus, dan ada suatu proses yang tidak mendapatkan gilirannya.

Ilustasi deadlock, misalnya :

• Terdapat tiga proses, yaitu P1, P2 dan P3.
• P1, P2 dan P3 memerlukan pengaksesan sumber daya R secara periodic Skenario berikut terjadi :
• P1 sedang diberi sumber daya R sedangkan P2 dan P3 diblocked menunggu sumber daya R.
• Ketika P1 keluar dari critical section, maka P2 dan P3 diijinkan mengakses R.
• Asumsi P3 diberi hak akses, kemudian setelah selesai, hak akses kembali diberikan ke P1 yang saat itu kembali membutuhkan sumber daya R.

Jika pemberian hak akses bergantian terus-menerus antara P1 dan P3, maka P2 tidak pernah memperoleh pengaksesan sumber daya R. Dalam kondisi ini memang tidak terjadi deadlock, hanya saja P2 mengalami starvation (tidak ada kesempatan untuk dilayani).

• Ø Sinkronisasi

Sinkronisasi adalah proses pengaturan jalannya beberapa proses pada saat yang bersamaan. tujuan utama sinkronisasi adalah menghindari terjadinya inkonsitensi data karena pengaksesan oleh beberapa proses yang berbeda (mutual exclusion) serta untuk mengatur urutan jalannya proses-proses sehingga dapat berjalan dengan lancar dan terhindar dari deadlock dan starvation. Sinkronisasi umumnya dilakukan dengan bantuan perangkat sinkronisasi. Penyelesaian terhadap masalah ini sangat penting karena perkembangan teknologi sistem komputer menuju ke sistem multiprocessing, terdistribusi dan paralel yang mengharuskan adanya proses-proses kongkuren.

Prinsip-prinsip Kongkurensi

Kongkurensi merupakan kegiatan yang berhubungan dengan :

1. Alokasi waktu pemroses untuk proses-proses yang aktif.
2. Pemakaian bersama dan persaingan untuk mendapatkan sumber daya.
3. Komunikasi antar proses.

Sistem berbagi memori

Sistem berbagi memori atau yang disebut juga sebagai Shared Memory System merupakan salah satu cara komunikasi antar proses dengan cara mengalokasikan suatu alamat memori untuk dipakai berkomunikasi antar proses. Alamat dan besar alokasi memori yang digunakan biasanya ditentukan oleh pembuat program. Pada metode ini, sistem akan mengatur proses mana yang akan memakai memori pada waktu tertentu sehingga pekerjaan dapat dilakukan secara efektif.

Sistem berkirim pesan

Sistem berkirim pesan adalah proses komunikasi antar bagian sistem untuk membagi variabel yang dibutuhkan. Proses ini menyediakan dua operasi yaitu mengirim pesan dan menerima pesan. Ketika dua bagian sistem ingin berkomunikasi satu sama lain, yang harus dilakukan pertama kali adalah membuat sebuah link komunikasi antara keduanya. Setelah itu, kedua bagian itu dapat saling bertukar pesan melalui link komunikasi tersebut. Sistem berkirim pesan sangat penting dalam sistem operasi. Karena dapat diimplementasikan dalam banyak hal seperti pembagian memori, pembagian bus, dan melaksanakan proses yang membutuhkan pengerjaan bersama antara beberapa bagian sistem operasi.

Terdapat dua macam cara berkomunikasi, yaitu:

1. Komunikasi langsung. Dalam komunikasi langsung, setiap proses yang ingin berkirim pesan harus mengetahui secara jelas dengan siapa mereka berkirim pesan. Hal ini dapat mencegah pesan salah terkirim ke proses yang lain.

Karakteristiknya antara lain:

• Link dapat otomatis dibuat
• Sebuah link berhubungan dengan tepat satu proses komunikasi berpasangan
• Diantara pasangan itu terdapat tepat satu link
• Link tersebut biasanya merupakan link komunikasi dua arah

1. Komunikasi tidak langsung. Berbeda dengan komunikasi langsung, jenis komunikasi ini menggunakan sejenis kotak surat atau port yang mempunyai ID unik untuk menerima pesan. Proses dapat berhubungan satu sama lain jika mereka membagi port mereka. Karakteristik komunikasi ini antara lain:

• Link hanya terbentuk jika beberapa proses membagi kotak surat mereka
• Sebuah link dapat terhubung dengan banyak proses
• Setiap pasang proses dapat membagi beberapa link komunikasi
• Link yang ada dapat merupakan link terarah ataupun link yang tidak terarah

1. Sinkronisasi aktivitas banyak proses

1. B. MUTUAL EXCLUSION

Merupakan kondisi dimana terdapat sumber daya yang tidak dapat dipakai bersama pada waktu yang bersamaan (misalnya : printer, disk drive). Kondisi demikian disebut sumber daya kritis, dan bagian program yang menggunakan sumber daya kritis disebut critical region / section. Hanya satu program pada satu saat yang diijinkan masuk ke critical region. Pemrogram tidak dapat bergantung pada sistem operasi untuk memahami dan memaksakan batasan ini, karena maksud program tidak dapat diketahui oleh sistem operasi. Hanya saja, system operasi menyediakan layanan (system call) yang bertujuan untuk mencegah proses lain masuk ke critical section yang sedang digunakan proses tertentu. Pemrograman harus menspesifikasikan bagian-bagian critical section, sehingga sistem operasi akan menjaganya. Pentingnya mutual exclusion adalah jaminan hanya satu proses yang mengakses sumber daya pada suatu interval waktu.

Pemaksaan atau pelanggaran mutual exclusion menimbulkan :

• Deadlock
• Starvation

Critical Section

Segmen kode yang mengakses data yang digunakan secara bersama-sama itu disebut critical section. Bagaimana menghindari race conditions? Kunci untuk mencegah masalah ini da situasi yang lain yang melibatkan shared memory, shared file, and shared sumber daya yang lain dalah 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 membutuhkan mutual exclusion, sebuah jalan yang menjamin jika sebuah proses sefang menggunakan shared files, proses lain dikeluarkan dari pekerjaan yang sama. Kesulitan yang terjadi karena proses 2 menggunakan shared variabel sebelum proses 1 menyelesaikan tugasnya.

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

• Tidak ada dua proses secara bersamaan masuk kedalam critical section.
• Tidak ada asumsi mengenai kecepatan atau jumlah cpu.
• Tidak ada proses yang berjalan diluar critical section yang dapat mengeblok proses lain.
• Tidak ada proses yang menunggu selamanya untuk masuk critical section.

Tiga kondisi untuk menentukan mutual exclusion  :

• Tidak ada dua proses yang pada saat bersamaan berada di critical section.
• Tidak ada proses yang berjalan diluar critical region yang bisa menghambat proses lain.
• Tidak ada proses yang tidak bisa masuk ke critical region.

Solusi masalah critical section

1. Ide :

• Mencakup pemakaian secara “exclusive” dari shared variable tersebut
• Menjamin proses lain dapat menggunakan shared variable tersebut

1. Solusi “critical section problem” harus memenuhi:

• Mutual Exclusion: Jika proses Pi sedang “eksekusi” pada bagian “critical section” (dari proses Pi) maka tidak ada proses proses lain dapat “eksekusi” pada bagian critical section dari proses-proses tersebut.
• Progress: Jika tidak ada proses sedang eksekusi pada critical section-nya dan jika terdapat lebih dari satu proses lain yang ingin masuk ke critical section, maka pemilihan siapa yang berhak masuk ke critical section tidak dapat ditunda tanpa terbatas.

1. Bounded Waiting: Terdapat batasan berapa lama  suatu proses harus menunggu giliran untuk mengakses “critical section” – jika seandainya proses lain yang diberikan hak akses ke critical section.

• Menjamin proses dapat mengakses ke “critical section” (tidak mengalami starvation: proses se-olah berhenti menunggu request akses ke critical section diperbolehkan).
• Tidak ada asumsi mengenai kecepatan eksekusi  proses proses n tersebut.

1. C. SINKRONISASI

Sinkronisasi:

1. Koordinasi akses ke shared data, misalkan hanya satu proses yang dapat menggunakah shared var.
2. Contoh operasi terhadap var. “counter” harus dijamin di-eksekusi dalam satu kesatuan (atomik) :

• counter := counter + 1;
• counter := counter - 1;

1. Sinkronisasi merupakan “issue” penting dalam rancangan/implementasi OS (shared resources, data, dan multitasking).

Kasus Produser – Consumer

Dua proses berbagi sebuah kebiasaan, buffer dengan ukuran yang tetap. Salah satunya produser, meletakkan informasi ke buffer yang lainnya. Konsumen mengambil informasi dari buffer. (ini juga dapat digeneralisasi untuk masalah yang memiliki m buah produsen dan n buah konsumen, tetapi kita hanya akan memfokuskan kasus dengan 1 produsen dan 1 konsumen karena diasumsikan dapat menyederhanakan solusi).

Masalah akan timbul ketika produsen ingin menaruh barang yang baru tetapi buffer sudah penuh. Solusi untuk produsen adalah istirahat (sleep) dan akan dibangunkan ketika konsumen telah mengambil 1 atau lebih barang dari buffer. Biasanya jika konsumen ingin mengambil barang dari buffer dan melihat bahwa buffer sedang kosong, maka konsumen istirahat (sleep) sampai produsen meletakkan barang pada buffer dan membangunkan (wake-up) consumer.

Untuk mengetahui jumlah barang di buffer kita membutuhkan sebuah variabel kita namakan count. Jika jumlah maksimum dari barang yang dapat ditampung buffer adalah n, kode produser pertama kali akan mencoba untuk mengetahui apakah nilai count sama dengan nilai n. Jika itu terjadi maka produsen akan istirahat (sleep), tetapi jika nilai count tidak sama dengan n, maka produsen akan terus menambahkan barang dan menaikkan count.

Sekarang mari kita kembali ke permasalahan race condition. Ini dapat terjadi karena akses ke count tidak dipaksakan. Situasi seperti itu mungkin dapat terjadi. Buffer sedang kosong dan konsumen baru saja membaca count untuk melihat apakah count bernilai 0. Pada saat itu, penjadwal memutuskan untuk mengentikan proses konsumen sementara dan menjalakan produsen. Produsen memasukkan barang ke buffer, menaikkan nilai count, dan memberitahukan bahwa count sekarang bernilai 1. Pemikiran bahwa count baru saja bernilai 0 sehingga konsumen harus istirahat ( sleep ). Produsen memanggil fungsi wake up untuk membangkitkan konsumen.

Sayangnya, konsumen secara logika belum istirahat. Jadi sinyal untuk membangkitkan konsumen, tidak dapat ditangkap oleh konsumen. Ketika konsumen bekerja berikutnya, konsumen akan memeriksa nilai count yang dibaca sebelumnya, dan mendapatkan nilai 0, kemudian konsumen istirahat ( sleep ) lagi. Cepat atau lambat produsen akan mengisi buffer dan juga pergi istirahat ( sleep ). Keduanya akan istirahat selamanya.