Konkurensi dan Sinkronisasi Proses

Konkurensi adalah proses-proses (lebih dari satu proses) yang terjadi pada saat bersamaan. Konkurensi merupakan landasan umum perancangan sistem operasi.  Situasi dimana beberapa proses mengakses dan memanipulasi data yang digunakan bersama-sama secara konkuren disebut dengan race condition. Untuk mencegah race condition tersebut, proses yang konkuren harus dilakukan sinkronisasi.

Masing-masing proses mempunyai sebuah kode segmen yang disebut dengan critical section, dimana proses memungkinkan untuk
mengubah variabel umum, mengubah sebuah tabel, menulis file dan lain sebagainya.Masing-masing proses harus meminta ijin untuk memasuki critical section-nya.

• Daerah kode yang mengimplementasikan perintah ini disebut daerah entry.
• Critical section biasanya diikuti oleh daerah exit.
• Kode pengingat terletak di daerah remainder.

Solusi dari permasalahan critical section harus memenuhi 3 syarat :

1.  Mutual Exclusion: Apabila proses Pi menjalankan critical section-nya, maka tidak ada proses lain yang dapat menjalankan critical section.
2. Progress: Apabila tidak ada proses yang menjalankan critical section-nya dan terdapat beberapa proses yang akan memasuki critical section-nya, maka hanya proses-proses itu yang tidak diproses di dalam daerah pengingat (remainder) dapat ikut berpartisipasi di dalam keputusan proses mana yang akan memasuki critical section selanjutnya, dan pemilihan ini tidak dapat ditunda tiba-tiba.
3. Bounded Waiting: Terdapat batasan jumlah waktu yang diijinkan oleh proses lain untuk memasuki critical section setelah sebuah proses membuat permintaan untuk memasuki critical section-nya dan sebelum permintaan dikabulkan.

Asumsi bahwa masing-masing proses dijalankan pada kecepatan bukan nol (nonzero) dan instruksi dasar bahasa mesin (instruksi primitif, misalnya load, store dan test) dijalankan secara otomatis. Tetapi, tidak ada asumsi mengenai kecepatan relatif dari proses ke n.

Algoritma Bakery

• Algoritma yang digunakan untuk pemecahan permasalahan critical section pada n proses.
• Sebelum memasuki critical section, proses menerima nomo.
• Proses yang mempunyai nomor terkecil dapat memasuki critical section.
• Jika proses Pi dan Pj menerima nomor yang sama, jika i < j maka Pi dilayani lebih dahulu. Sebaliknya, jika j < i, maka Pj akan dilayani lebih dahulu.
• Skema pemberian nomor selalu membangkitkan nomor dengan menaikkan nilai urut
• Terdapat notasi <≡ untuk urutan nomor (ticket #, process id #):
  • (a,b) < (c,d) if a < c or if a = c and b < d
  • max (a0,…, an-1) is a number, k, such that k ≥ ai for i – 0, …, n – 1
• Variabel umum yang digunakan adalah :
  • boolean choosing[n];
  • int number[n];

Perangkat keras Sinkronisasi

Perancang perangkat keras menyediakan instruksi-instruksi atomik yang tak dapat diinterupsi. Instruksi ini biasanya dilaksanakan dengan cara mengunci bus sehingga pemroses-pemroses lain tak dapat menggunakan bus.

Beragam instruksi mesin disediakan oleh perancang pemroses guna membantu implementasi mutual exclusion. Diantara instruksi-instruksi itu adalah:

• tsl (test and set lock)
• tas atau ts (test and set), digunakan IBM S/360, keluarga Motorola M68000, dan lain-lain
• cs (compare and set), digunakan IBM 370 series
• exchange (xchg), digunakan intel X86
• dsb

Semaphore

• Pendekatan yang dikemukakan Dijkstra.
• Prinsip: Dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Proses dipaksa berhenti sampai proses
  memperoleh penanda tertentu.
• Alat untuk sinkronisasi yang tidak membutuhkan busy waiting.
• Hanya dapat diakses melalui operasi atomic yang tak dapat diinterupsi sampai kode selesai.
• Terdapat dua operasi sederhana yaitu block untuk menghentikan sementara proses yang menggunakan semaphore dan wakeup(P) untuk melanjutkan eksekusi proses P yang di-blok.
• Pada saat beberapa proses membawa semaphore dan masing-masing proses menunggu semaphore yang sedang dibawa oleh proses lain maka kemungkinan akan terjadi deadlock.
• Apabila suatu proses tidak pernah dihapus dari antrian semaphore setelah suatu semaphore dihentikan sementara, maka terjadi bloking yang tak terbatas. Keadaan ini disebut starvation.
• Dua bentuk semaphore:
  • Counting semaphore: menggunakan nilai integer yang mempunyai jangkauan tak terbatas
  • Binary semaphore: menggunakan nilai integer dengan jangkauan antara 0 dan 1 sehingga implementasinya lebih sederhana.

Masalah-masalah klasik sinkronisasi

• Bounded-Buffer (Producer-Consumer) Problem:
  • Produsen menghasilkan barang dan konsumen yang akan menggunakannya.
  • Ada beberapa batasan yang harus dipenuhi, antara lain :
  • Barang yang dihasilkan oleh produsen terbatas
  • Barang yang dipakai konsumen terbatas
  • Konsumen hanya boleh menggunakan barang yang dimaksud setelah produsen menghasilkan barang dalam jumlah tertentu
  • Produsen hanya boleh memproduksi barang jika konsumen sudah kehabisan barang
• Reader and Writer Problem:
  • Terdapat dua variasi pada masalah ini, yaitu :
  • Seorang reader tidak perlu menuggu reader lain untuk selesai hanya karena ada writer menunggu (reader memiliki prioritas lebih tinggi disbanding dengan writer)
  • Jika ada writer yang sedang menunggu, maka tidak boleh ada reader lain yang bekerja (writer memiliki prioritas yang lebih tinggi)
• Dining-Philosophers Problem

Contoh Sinkronisasi

Implementasi sinkronisasi pada Windows 2000 menggunakan interrupt mask untuk memproteksi akses ke sumber daya global pada sistem uniprosessor sedangkan ada sistem multiprosessor menggunakan spinlock. Selain itu Windows 2000 juga menyediakan dispatcher object yang berfungsi sebagai mutual exclusion dan semaphore. Dispatcher object juga menyediakan event yang berfungsi sebagai variabel kondisi.