- Akses-akses yang dilakukan secara bersama-sama ke data yang sama, dapat menyebabkan data menjadi tidak konsisten.
- Untuk menjaga agar data tetap konsisten, dibutuhkan mekanisme-mekanisme untuk memastikan pemintaan ekseskusi dari proses yang bekerja.
- Race Condition: Situasi dimana beberapa proses mengakses dan memanipulasi data secara bersamaan. Nilai terakhir dari data bergantung dari proses mana yang selesai terakhir.
- Untuk menghindari Race Condition, proses-proses secara bersamaan harus disinkronisasikan.
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.
Pendekatan
seperti ini terdengar cukup sederhana, tetapi hal ini dapat menggiring kita ke
jenis masalah yang sama seperti race condition dengan spooler direktori.
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.
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.
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. Unutk mencegah race condition,
proses-proses yang berjalan besamaan haus 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.
Bayangkan
bahwa spooler direktori memiliki slot dengan jumlah yang sangat besar, diberi
nomor 0, 1, 2, 3, 4,... masing-masing dapat memuat sebuah nama berkas. Juga
bayangkan bahwa ada dua variabel bersama, out, penunjuk berkas berikutnya untuk
dicetak, dan in, menunjuk slot kosong di direktori. Dua vaiabel tersebut dapat
menamgami sebuah two-word berkas untuk semua proses. Dengan segera, slot 0, 1,
2, 3 kosong (berkas telah selesai dicetak), dan slot 4, 5, 6 sedang terisi (berisi
nama dari berkas yang antre untuk dicetak). Lebih atau kurang secara besamaan,
proses A dan B, mereka memutuskan untuk antre untuk sebuah berkas untuk
dicetak.
Gambar. Race Condition. Sumber Bahan Kuliah IKI-20230 oleh Gabungan Kelompok
Kerja 21–28 IKI-20230 Semester Genap 2002/2003
Dalam
Murphy's Law kasus tesebut dapat terjadi. Proses A membaca in dan menyimpan
nilai "7" di sebuah variabel lokal yang disebut next_free_slot.
Sebuah clock interrupt terjadi dan CPU memutuskan bahwa proses A berjalan cukup
lama, sehingga digantika oleh proses B. Proses B juga membaca in, dan juga
mengambil nilai 7, sehingga menyimpan nama berkas di slot nomor 7 dan
memperbaharui nilai in menjadi 8. Maka proses mati dan melakukan hal lain.
Akhirnya
proses A berjalan lagi, dimulai dari tempat di mana proses tersebut mati. Hal
ini terlihat dalam next_free_slot, ditemukan nilai 7 di sana, dan menulis nama
berkas di slot nomor 7, menghapus nama berkas yang bau saja diletakkan oleh
proses B. Kemudian proses A menghitung next_free_slot + 1, yang nilainya 8 dan
memperbaharui nilai in menjadi 8. Direktori spooler sekarang secara internal
konsisten, sehingga printer daemon tidak akan memberitahukan apa pun yang
terjadi, tetapi poses B tidak akan mengambil output apa pun. Situasi seperti
ini, dimana dua atau lebih proses melakukan proses reading atau writing
beberapa shared data dan hasilnya bergantung pada ketepatan berjalan disebut
race condition.
Bagaimana menghindari race conditions? 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
Critical section harus
melakukan ketiga aturan berikut:
Solusi yang diberikan
harus memuaskan permintaaan berikut:
- Mutual
exclution
- Deadlock
free
- Starvation
free
Problem Klasik pada
Sinkronisasi
Ada tiga
hal yang selalu memjadi masalah pada proses sinkronisasi:
- Problem Bounded buffer.
- Problem Reades and Writer.
- Problem Dining Philosophers.
Problem Readers-Writers
Problem lain yang terkenal adalah readers-writer
problem yang memodelkan proses yang mengakses database. Sebagai contoh sebuah
sistem pemesanan sebuah perusahaan penerbangan, dimana banyak proses
berkompetisi berharap untuk membaca (read) dan menulis (write).
Hal ini dapat diterima bahwa banyak proses membaca database pada saat yang
sama, tetapi jika suatu proses sedang menulis database, tidak boleh ada proses
lain yang mengakses database tersebut, termasuk membaca database tersebut.
Dalam solusi ini, pertama-tama pembaca mengakses
database kemudian melakukan DOWN pada semaphore db.. Langkah selanjutnya
readers hanya menaikkkan nilai sebuah counter. Hasil dari pembaca nilai counter
diturunkan dan nilai terakhir dilakukan UP pada semaphore, mengizinkan memblok
writer.
Misalkan selama sebuah reader menggunakan database,
reader lain terus berdatangan. Karena ada dua reader pada saat bersamaan
bukanlah sebuah masalah, maka reader yang kedua diterima, reader yang ketiga
juga dapat diterima jika terus berdatangan reader-reader baru.
Sekarang misalkan writer berdatangan terus menerus.
Writer tidak dapat diterima ke database karena writer hanya bisa mengakses data
ke database secara ekslusif, jadi writer ditangguhkan. Nanti penambahan reader
akan menunjukkan peningkatan. Selama paling tidak ada satu reader yang aktif,
reader berikutnya jika datang akan diterima.
Sebagai konsekuensi dari strategi ini, selama
terdapat suplai reader yang terus-menerus, mereka akan dilayani segera sesuai
kedatanga mereka. Writer akan ditunda sampai tidak ada reader lagi. Jika sebuah
reader baru tiba, katakan, setiap dua detik, dan masing-masing reader
mendapatkan lima detik untuk melakukan tugasnya, writer tudak akan pernah
mendapatkan kesempatan.
Untuk mencegah situasi seperti itu, program dapat
ditulis agak sedikit berbeda: Ketika reader tiba dan writer menunggu, reader
ditunda dibelakang writer yang justru diterima dengan segera. Dengan cara ini,
writer tidak harus menunggu reader yang sedang aktif menyelesaikan
pekerjaannya, tapi tidak perlu menunggu reader lain yang datang berturut-turut
setelah itu.
Problem Dining Philosopers
Pada tahun 1965, Djikstra menyelesaikan sebuah
masalah sinkronisasi yang beliau sebut dengan dining philisophers problem.
Dining philosophers dapat diuraikan sebagai berikut: Lima orang filosuf duduk
mengelilingi sebuah meja bundar. Masing-masing filosof mempunyai sepiring
spageti. Spageti-spageti tersebut sangat licin dan membutuhkan dua garpu untuk
memakannya. Diantara sepiring spageti terdapat satu garpu.
Kehidupan para filosof terdiri dari dua periode,
yaitu makan atau berpikir. Ketika seorang filosof lapar, dia berusaha untuk
mendapatkan garpu kiri dan garpu kanan sekaligus. Jika sukses dalam mengambil
dua garpu, filosof tersebut makan untuk sementara waktu, kemudian meletakkan
kedua garpu dan melanjutkan berpikir.
Pertanyaan kuncinya adalah, dapatkah anda menulis
program untuk masing-masing filosof yang melakukan apa yang harus mereka
lakukan dan tidak pernah mengalami kebuntuan.
Prosedur take-fork menunggu sampai garpu-garpu yang
sesuaididapatkan dan kemudian menggunakannya. Sayangnya dari solusi ini
ternyata salah. Seharusnya lima orang filosof mengambil garpu kirinya secara
bersamaan. Tidak akan mungkin mereka mengambil garpu kanan mereka, dan akan
terjadi deadlock.
Kita dapat memodifikasi program sehingga setelah
mengambil garpu kiri, program memeriksa apakah garpu kanan meungkinkan untuk
diambil. Jika garpu kanan tidak mungkin diambil, filosof tersebut meletakkan
kembali garpu kirinya, menunggu untuk beberapa waktu, kemudia mengulangi proses
yang sama. Usulan tersebut juga salah, walau pun dengan alasan yang berbeda.
Dengan sedikit nasib buruk, semua filosof dapat memulai algoritma secara
bersamaan, mengambil garpu kiri mereka, melihat garpu kanan mereka yang tidak
mungkin untuk diambil, meletakkan kembali garpu kiri mereka, menunggu,
mengambil garpu kiri mereka lagi secara bersamaan, dan begitu seterusnya.
Situasi seperti ini dimana semua program terus berjalan secara tidak terbatas
tetapi tidak ada perubahan/kemajuan yang dihasilkan disebut starvation.
Sekarang anda dapat berpikir "jika filosof
dapat saja menunggu sebuah waktu acak sebagai pengganti waktu yang sama setelah
tidak dapat mengambil garpu kiri dan kanan, kesempatan bahwa segala sesuatau
akan berlanjut dalam kemandegan untuk beberapa jam adalah sangat kecil."
Pemikiran seperti itu adalah benar,tapi beberapa aplikasi mengirimkan sebuah
solusi yang selalu bekerja dan tidak ada kesalahan tidak seperti hsk nomor acak
yang selalu berubah.
Sebelum mulai mengambil garpu, seorang filosof
melakukan DOWN di mutex. Setelah menggantikan garpu dia harus melakukan UP di
mutex. Dari segi teori, solusi ini cukup memadai. Dari segi praktek, solusi ini
tetap memiliki masalah. Hanya ada satu filosof yang dapat makan spageti dalam
berbagai kesempatan. Dengan lima buah garpu, seharusnya kita bisa menyaksikan
dua orang filosof makan spageti pada saat bersamaan.
Solusi yang diberikan diatas benar dan juga
mengizinkan jumlah maksimum kegiatan paralel untuk sebuah jumlah filosf yang
berubah-ubah ini menggunakan sebuah array, state, untuk merekam status seorang
filosof apakah sedang makan (eating), berpikir (think), atau sedang lapar
(hungry) karena sedang berusaha mengambil garpu. Seorang filosof hanya dapat
berstatus makan (eating) jika tidak ada tetangganya yang sedang makan juga.
Tetangga seorang filosof didefinisikan ole LEFT dan RIGHT.
Dengan kata lain, jika i = 2, maka tetangga kirinya
(LEFT) = 1 dan tetangga kanannya (RIGHT) = 3. Program ini menggunakan sebuah
array dari semaphore yang lapar (hungry) dapat ditahan jika garpu kiri atau
kanannya sedang dipakai tetangganya. Catatan bahwa masing-masing proses
menjalankan prosedur filosof sebagai kode utama, tetapi prosedur yang lain
seperti take-forks, dan test adalah prosedur biasa dan bukan proses-proses yang
terpisah
DAFTAR PUSTAKA
Ø Sistem
Operasi, SP Hariningsih, Penerbit
Graha Ilmu 2003.
Ø Silberschatz, A., Gagne, G. dan Galvin, P., "Applied
Operating System Concept", John Wiley and Sons Inc., 2000
Ø Hariyanto, B.,"Sistem Operasi", Bandung:
Informatika, Desember 1997
Ø Tanenbaum, Andrew S., "Modern Operating
Systems", Englewood Cliffs, New Jersey: Prentice-Hall Inc., 1992
Ø Coffman, E.G., Jr., M.J. Elphick dan A. Shoshani,
"System Deadlocks", Computing surveys, Vol.3, No.2, June 1971
Ø WWW.Google.com
0 komentar:
Posting Komentar