KONGKURENSI, MUTUAL EXCLUSION DAN SINKRONISASI PADA SISTEM OPERASI

A. KONGKURENSI

1. Pengertian

Kongkurensi timbul akibat berkembangnya dunia IT. Berawal dari tuntutan kebutuhan pengguna komputer yang semakin komplek maka lahir kongkurensi dengan segala keterhubungannya. Pengguna komputer membutuhkan pelayanan dari komputer yang bisa melayani beberapa proses sekaligus dalam waktu yang bersamaan.

Kongkurensi merupakan landasan umum perancangan sistem operasi. Prosesproses disebut kongkurensi jika proses-proses (lebih dari satu proses) berada pada saat yang sama. Saat yang sama ini maksudnya proses-proses tersebut berlangsung pada waktu yang sama dan menggunakan sumber daya yang sama. Kita ambil contoh pada system operasi Windows, jika kita menjalan Microsoft Word bersamaan dengan Winamp maka itu adalah kongkurensi. 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.

2. Masalah-masalah Akibat Kongkurensi

Proses proses yang kongkuren akan menyebabkan beberapa kemungkinan masalah yang muncul. Masalah ini muncul setelah atau ketika proses berlangsung. Adapun kemungkinan-kemungkinan masalah tersebut adalah :

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

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

c. 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 periodik

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 kembalidiberikan 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).

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

3. Prinsip-prinsip Kongkurensi

Kongkurensi merupakan kegiatan yang berhubungan dengan :

Ø Alokasi waktu pemroses untuk proses-proses yang aktif.

Ø Pemakaian bersama dan persaingan untuk mendapatkan sumber daya.

Ø 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:

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

i. Link dapat otomatis dibuat

ii. Sebuah link berhubungan dengan tepat satu proses komunikasi berpasangan

iii. Diantara pasangan itu terdapat tepat satu link

iv. Link tersebut biasanya merupakan link komunikasi dua arah

b. 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:

i. Link hanya terbentuk jika beberapa proses membagi kotak surat mereka

ii. Sebuah link dapat terhubung dengan banyak proses

iii. Setiap pasang proses dapat membagi beberapa link komunikasi

iv. Link yang ada dapat merupakan link terarah ataupun link yang tidak terarah

Ø Sinkronisasi aktivitas banyak proses

4. Kerjasama diantara Proses

Kerjasama diantara proses terbagi kedalam 2 bagian, diantaranya :

a. Kerjasama diantara proses dengan pemakaian bersama

Dalam kasus kerjasama pemakaian sumber daya bersama meliputi proses-proses yang saling berinteraksi tanpa dinyatakan secara eksplisit. Contoh : Banyak proses mengakses variabel atau berkas yang dipakai bersama. Proses-proses dapat menggunakan dan memperbarui data yang dipakai bersama tanpa peduli proses-proses lain. Proses mengetahui bahwa proses-proses lain dapat juga mengakses data yang sama. Proses-proes harus bekerja sama untuk menjamin integritas data yang dipakai bersama tersebut.

Kerjasama diantara proses-proses dalam pemakaian bersama mempunyai masalah:

Ø Mutual exclusion

Ø Deadlock

Ø Starvation

Karena data disimpan pada suatu sumber daya (peralatan, memori), maka terdapat masalah pengendalian mutual exclusion, deadlock dan starvation. Perbedaannya adalah item-item data dapat diakses dengan dua mode, yaitu :

1. Operasi pembacaan dan penulisan harus mutually exclusive (yaitu benar-benar hanya satu proses yang berada di critical section).

2. Operasi penulisan saja yang harus mutually exclusive.

Pada situasi ini, masalah baru muncul yaitu mengenai koherensi data. Critical section digunakan untuk menjamin integritas data.

b. Kerjasama diantara proses dengan komunikasi

Pada kasus persaingan, proses-proses memakai sumber daya tanpa peduli prosesproses lain. Pada kasus kedua, proses-proses memakai bersama nilai dan meski masingmasing proses tidak secara eksplisit peduli proses-proses lain. Tapi proses-proses peduli untuk menjaga integritas data. Ketiak proses-proses bekerja sama dengan komunikasi, beragam proses berpartisipasi dalam suatu usaha dengan menghubungkan semua proses. Komunikasi menyediakan cara untuk sinkronisasi atau koordinasi beragam aktivitas. Komunikasi dicirikan dengan berisi pesan-pesan dengan suatu urutan. Primitif untuk mengirim dan menerima pesan disediakan sebagai bagian bahasa pemrograman atau disediakan kernel sistem operasi. Karena tak ada sesuatu yang dipakai bersama diantara proses-proses itu dalam melewatkan pesan-pesan, tak ada masalah mutual exclusion. Tetapi masalah deadlock dan starvation dapat muncul.

B. MUTUAL EXCLUSION

1. Pengertian

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

2. Critical Section

Beberapa proses memiliki suatu segmen kode dimana jika segmen itu dieksekusi, maka proses-proses itu dapat saling mengubah variabel, mengupdate suatu tabel, menulis ke suatu file, dan lain sebagainya, dan hal ini dapat membawa proses tersebut ke dalam bahaya race condition. Segmen kode yang seperti inilah yang disebut Critical Section. Sedangkan race condition sendiri adalah kondisi dimana ada beberapa proses yang memanipulasi suatu data secara kongkuren, sehingga data tersebut tidak sinkron lagi. Nilai akhirnya akan tergantung pada proses mana yang terakhir dieksekusi. Maka dibutuhkan sinkronisasi.

3. Sumber Daya

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

a. Sumber daya fisik

Contoh dari sumber daya fisik diantaranya keyboard, bar-code reader, mouse, joystick, lightpen, track-ball, touchscreen, pointing devices, floppy disk drive, hard-disk, tape drive, optical disk, CD ROM drive, CRT, LCD, printer, modem, ethernet card, PCMCIA, RAM, cache memory, register, kamera, sound card, radio, digitizer, scanner, plotter, dan sebagainya.

b. Sumber daya abstrak

Terdiri dari :

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

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

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

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

Sebaliknya jika waktu proses tidak berhingga atau tidak jelas maka tidak jelas pula kapan critical section kosong, maka proses yang diluar akan selamanya menunggu dan akan terjadi deadlock.

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

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

6. Ketika Tidak Ada Proses Di Critical Section Maka Proses Yang Ingin Masuk Ke Critical Section Harus Diijinkan Tanpa Waktu Tunda

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

7. Metode-metode dan Algoritma untuk Menjamin Mutual Exclusion

a. Disabling interrupt / mematikan interupsi

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

b. Lock variables

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

c. Strict alternation

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

Contohnya :

While (true)

{

while (turn != 0) /*wait*/;

critical_section ( );

turn = 1;

noncritical_section ( );

}

while (true)

{

while (turn != 1) /*wait*/;

critical_section ( );

turn = 0;

noncritical_section ( );

}

d. Peterson’s Solution

Proses tidak akan diteruskan sampai while terpenuhi, bila interested[other] = TRUE, maka proses akan menunggu sampai FALSE.

Kelemahannya : jika proses memanggil enter_region-nya secara hampir bersamaan, yang disimpan di turn adalah data yang ditulis terakhir.

Contohnya :

# include “prototype.h”

# define FALSE 0

# define TRUE 1

# define N 2 /*banyaknya proses*/

int turn;

int interested [N]; /*nilai awal di-set = 0 (false)*/

void enter_region(int process) /*proses = 1 atau 0*/

{

int other; /*jumlah proses lainnya*/

other = 1 – process; /*proses lainnya*/

interested[process] = TRUE; /*menunjukkan tertarik*/

turn = process; /*set flag*/

while (turn==process && interested[other] == TRUE)

}

void leave_region(int process) /*proses yang selesai*/

{

interested[process] = FALSE; /*meninggalkan critical region*/

}

e. Test and Set Lock Instruction / Instruksi TSL

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

Contoh :

Enter_region :

Tsl reg,flag | copy flag ke reg dan set flag = 1

Cmp reg,#0 | apakah flag = 0

Jnz enter_region |jika <> 0 loop lagi

Ret |return ke caller, masuk critical region

Leave_region :

Mov flag, #0 |simpan 0 ke flag

Ret |return ke caller

Proses harus memanggil ini pada saat yang tepat.

C. SINKRONISASI

1. Pengertian

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.

2. Prinsip Kerja Call Sleep Dan Call Wake Up Pada Kasus Produser Dan Consumer

Dua proses berbagi sebuah 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 satu produsen dan satu 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 satu 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 dairi 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, produsen akan terus menambahkan barang dan menaikkan nilai 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, penjadual 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.

3. Kemungkinan Sinkronisasi Gagal

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.

Inti permasalahannya disini adalah pesan untuk membangkitkan sebuah proses tidak tersampaikan. Jika pesan/ sinyal ini tersampaikan dengan baik, segalanya akan berjalan lancar.

Kesimpulan :

Mekanismenya : proses akan di blok / tidur (sleep) apabila tidak bisa memasuki critical_section-nya dan akan dibangunkan (wake up) / ready apabila resource yang diperlukan telah tersedia.