Contoh kasus fungsi transfer uang yang dijelaskan pada bagian sebelum- nya hanyalah salah satu contoh kasus konkurensi yang membutuhkan mekanisme sinkronisasi. Pada kasus transfer uang, digunakan bentuk sinkronisasi yang disebut dengan mutual exclusive (mutex) yang me mastikan hanya satu proses yang diijinkan masuk ke critical section pada setiap saat.
Mutex merupakan salah satu bentuk khusus dari semaphor dan dikenal dengan istilah binary semaphore yang merupakan mekanisme sin kronisasi yang lebih umum. Jika mutex hanya mengijinkan satu (n=1)
proses memasuki critical section-nya maka semaphore mengijinkan sejumlah proses (n>1) untuk memasuki critical section secara bersamaan. Selain semaphore dan mutex, masih terdapat mekanisme lain seperti monitor. Mekanisme monitor jauh lebih kompleks dan tidak akan dibahas dalam buku ini.
Di bawah ini akan dibahas sejumlah masalah klasik konkurensi yang membutuhkan mekanisme sinkronisasi: Bounded Buffer (Produser- Consumer), Dining Philosopher, Readers and Writers, serta Sleeping Barber. Masalah-masalah konkurensi di atas lebih kompleks dibanding- kan dengan kasus transfer uang dan membutuhkan teknik sinkronisasi yang lebih kompleks dan berbeda satu sama lainnya.
4.5.1 MASALAH BOUNDED-BUFFER (PRODUCER-CONSUMERS)
Pada kasus Bounded-Buffer, diasumsikan terdapat suatu buffer yang memiliki kapasitas terbatas sejumlah n. Produser mengisi buffer, sedangkan Consumer memindahkan atau menghapus isi buffer. Masalah timbul pada produser jika buffer sudah penuh sehingga tidak dapat diisi lebih lanjut. Sementara bagi consumer, masalah muncul jika buffer menjadi kosong sehingga tidak ada item yang dapat dipindahkan lebih lanjut. Selain itu saat salah satu pihak melakukan operasinya maka pihak lainnya tidak boleh melakukan operasinya. Atau dengan kata lain operasi produser dan operasi consumer haruslah mutual exclusive (mutex).
Salah satu bentuk solusi terhadap masalah konkurensi ini adalah menggunakan 3 semaphore yaitu full, empty, dan mutex. Konstruksi sinkronisasi menggunakan semaphore ini dapat dilihat pada Gambar 4.15. Nilai full menandakan jumlah slot buffer yang terisi, nilai empty menunjukkan sisa slot buffer yang masih kosong atau masih dapat diisi, sedangkan mutex menandakan boleh tidaknya suatu proses, baik producer maupun consumer, mengakses buffer.
Nilai awal full adalah 0, yang artinya buffer masih kosong, dan nilai awal empty adalah N, yaitu kapasitas slot buffer, dan nilai awal mutex adalah 1. Instruksi wait(semaphore) akan menurunkan nilai semaphore. Namun jika nilai semaphore sudah 0 maka proses bersangkutan akan beralih status menjadi blocked dan menunggu sampai terjadi eksekusi instruksi signal(semaphore) oleh proses lain. Instruksi signal(semaphore) sebaliknya akan menaikkan nilai semaphore dan membangunkan proses blocked yang sedang menunggu semaphore bersangkutan.
Untuk proses produser, setelah item diproduksi maka perintah wair (empty) dilakukan untuk memastikan masih terdapat slot kosong pada buffer. Kalau slot sedang kosong, maka proses produser akan beralih status menjadi blocked sampai tersedia slot kosong pada buffer. Jika terdapat slot kosong pada buffer maka instruksi wait(empty) akan menyebabkan nilai empty berkurang satu dan menandakan jumlah slot kosong pada buffer berkurang satu. Selanjutnya proses produser melakukan instruksi wait(mutex) untuk memastikan tidak ada proses lain. yaitu consumer, yang sedang mengakses buffer.
Jika dua kondisi di atas terpenuhi maka produser akan melakukan critical section-nya, yaitu memasukkan item yang diproduksi ke dalam buffer. Setelah itu, produser akan membebaskan mutex dengan instruksi signal(mutex) sehingga proses lain mendapat giliran untuk mengakses buffer. Proses produser selanjutnya melakukan instruksi signal(full) yang akan menaikkan satu nilai full dan menandakan slot buffer yang terisi bertambah satu.
Pada sisi proses consumer, langkah pertama wait(full) berfungsi memasti- kan terdapat slot terisi atau item yang dapat dikonsumsi. Nilai full-0 menandakan tidak item dalam buffer, sehingga proses consumer akan beralih status menjadi blocked dan menunggu sampai buffer terisi item baru. Jika buffer memiliki item maka instruksi selanjutnya yaitu wait(mutex) memastikan tidak ada proses lain yang sedang mengakses buffer.
Jika kedua kondisi di atas terpenuhi maka proses akan mengonsumsi item pada buffer. Setelah itu, proses akan membebaskan kembali mutex dengan perintah signal(mutex) dan menaikkan nilai jumlah slot buffer yang kosong dengan instruksi signal(empty).
Data yang dipakal bersama
type rem
var buffer =
full, empty, mutex: semaphore, fut = 0; empty n. mutex -1.
Proses Produser
repeat
membuat item
warmutex
menyisipkan itam ke buffer
signal mutex)
signal ful
until falso
Proses Consumer
repeat
wait(full) wait(mutex) ambil dan hapus satu item dari buffer signal(mutex) signal(empty);
until false,
Gambar 4.15 Solusi sinkronsiasi untuk masalah producer consumer
Selain menggunakan semaphore, masalah producer dan consumer dapat juga diselesaikan dengan menggunakan monitor dan message passing Kontruksi sinkronisasi dengan menggunakan monitor dan message passing dapat dilihat pada Tanembaum, A.S. (2001).
Manajemen Proses
117
4.5.2 MASALAH READERS AND WRITERS
Sebuah data, baik berupa berkas maupun rekaman di basis data, terkadang digunakan bersama oleh sejumlah proses secara bersamaan. Beberapa proses mungkin melakukan operasi baca (read), sedangkan yang lain melakukan operasi tulis (write) baik berupa penyisipan data baru ataupun modifikasi terhadap data lama. Umumnya jika semua proses yang berjalan bersamaan adalah operasi baca, tidak ada masalah yang muncul. Namun ika terdapat satu saja proses yang melakukan operasi tulis maka masalah dapat muncul. Kasus konkurensi ini disebut dengan masalah readers and writers.
Untuk mencegah hal tersebut maka proses write harus mendapatkan hak akses eksklusif terhadap data yang digunakan bersama. Artinya sebelum proses write melakukan critical section-nya, harus dipastikan seluruh proses read sudah selesai dan ketika proses write sedang mengeksekusi critical sectiomya, tidak ada proses read yang diijinkan untuk beroperasi. Solusi sinkronsisasi untuk masalah readers and writers ini ditunjukkan pada Gambar 4.16.
Dalam solusi ini digunakan dua semaphore, lebih tepatnya adalah mutex, yaitu reader Mutex dan dataMutex. Selain itu, terdapat counter readcount untuk mencatat proses reader yang aktif. Variabel reader Mutex diguna- kan untuk mensinkronisasikan pembaharuan nilai readcount, sedangkan data Mutex digunakan untuk mensinkronisasi akses ke data oleh proses reader pertama dan proses writer.
Perhatikan, jika proses reader terjadi lebih dahulu dibanding proses writer maka akses ke data akan mulai terkunci oleh instruksi wait dari proses reader yang pertama, dan hanya akan dibebaskan oleh instruksi signal dari proses reader yang terakhir yang selesai. Ini berarti jika ada proses reader yang masih aktif maka reader yang masuk berikutnya dapat langsung membaca, bahkan jika ada proses writer yang sedang menunggu. Proses writer hanya dapat melanjutkan eksekusinya jika seluruh proses reader sudah selesai. Disisi lain, jika proses writer terjadi lebih dahulu dibanding proses reader maka seluruh proses reader yang terjadi sesu dahnya harus menunggu sampai proses writer menyelesaikan eksekusi- nya.
118
Sistem Operasi
Data yang dipakai bersama
VirenderMutax data Mutex: Semaphore
readcounts antige
reador Muter 1 dateMutext, readcount=0,
Proses Writer
wait data fotent
operasi wrze
aignal (dala Mit Proses Reader waill readork readcount
Toreadcount=1 then hata Mutex);
operasiroad
waitt readerMutex
readcount readcount-1, if readcount = 0 then signal data Mutex); signal reader Mutex)
Gambar 4.16 Solusi sinkronisasi masalah readers and writers
Solusi sinkronisasi yang dijelaskan memiliki kelemahan. Jika proses reader terjadi terus menerus secara konstan maka dapat terjadi proses writer yang sedang menunggu tidak akan pernah mendapat giliran sama sekali. Kondisi ini ini disebut dengan kondisi starvation bagi proses writer. Salah satu solusi yang dianjurkan adalah, jika terdapat proses writer yang sedang menunggu maka proses reader yang mencoba masuk harus menunggu dan tidak boleh mendahului proses writer yang terlebih dahulu menunggu. Konsekuensinya adalah berkurangnya tingkat konkurensi yang dapat dicapai dan mengurangi unjuk kerja sistem.
Manajemen Proses
119
4.5.3 MASALAH DINING PHILOSOPHER
Masalah konkurensi klasik ini pertama dikemukakan oleh Dijkstra pada tahun 1965. Kondisi ini dilukiskan pada Gambar 4.17. Misalnya ada 5 filsuf yang menghabiskan waktunya untuk berpikir dan makan. Mereka duduk bersama mengelilingi satu meja makan dengan lima buah piring yang masing-masing dibatasi dengan sumpit. Di tengah terdapat satu bakul nasi. Ketika sedang berpikir filsuf akan diam saja. Namun ketika sedang lapar maka ia dapat mengambil kedua sumpit di sampingnya. Mungkin ia hanya mengambil satu sumpit. Tetapi tentu saja ia tidak akan mengambil sumpit yang sudah dipegang oleh yang lain. Ketika lapar berat, ia akan mengambil kedua sumpit dan tidak akan melepaskan selama makan. Baru setelah selesai makan, ia akan melepaskan sumpit dan mulai berpikir kembali.
Gambar 4.17 Masalah Dining-philosopher
Dining-philosopher merupakan masalah klasik konkurensi dan secara sederhana menunjukkan masalah yang muncul ketika terjadi peng- alokasian beberapa sumber daya, resource, untuk beberapa proses yang dapat berakibat deadlock ataupun starvation. Untuk masalah deadlock akan dibahas secara khusus pada bagian terakhir dari bab ini.
120
Sistem Operasi
Salah satu penyelesaian sederhana untuk masalah dining-philosopher adalah dengan menggunakan satu sempahore atau tepatnya mutex pada setiap sumpit. Setiap sumpit atau mutex dan juga filsuf akan diindeks dari O sampai 4. Filsuf (1) yang ingin makan akan mencoba mengeksekusi instruksi wait terhadap mutex sumpit kiri, yaitu chopstick[i] dan mutex sumpit kanannya, yaitu chopstick[i+1]. Jika sudah selesai makan, proses filsuf akan melakukan instruksi signal untuk membebaskan kedua sumpit tersebut, yaitu signal(chopstick[i]) dan signal(chopstick[i+1]). Secara lengkap, langkah sinkronisasi dapat dideskripsi pada Gambar 4.18.
Philosopher
repeat
wail(chopstick mod 5)
agra (chopstick):
Signal chopstick mod 51);
think
until falso:
Gambar 4.18 Solusi sinkronisasi pada masalah dining philosopher
Meskipun cara ini menjamin tidak akan ada dua filsuf yang berdekatan makan secara bersamaan, tetapi cara ini masih memungkinkan terjadinya deadlock. Misalnya kelima filsuf lapar secara bersamaan dan bersamaan pula berhasil mengambil sumpit di sisi kirinya maka ketika akan mengambil sumpit di sisi kanannya akan terjadi deadlock. Beberapa perbaikan yang dapat dilakukan untuk mengatasi deadlock dan menghindarkan timbulnya salah satu filsuf mati kelaparan adalah:
Manajemen Proses
121
1. Membolehkan maksimal 4 filsuf yang secara bersamaan duduk di meja makan.
2. Membolehkan filsuf untuk mengambil sumpit jika kedua buah sumpit tersedia, yaitu menjadi instruksi wait(chopstick[i]) dan wait(chopstick [i+1]) sebagai critical section yang harus disinkronisasi dengan suatu mutex baru.
3. Menggunakan penyelesaian asimetris. Filsuf ganjil mengambil sumpit di kirinya baru kemudian sumpit yang kanan. Sementara filsuf genap dengan cara sebaliknya, yaitu mengambil sumpit kanan dahulu baru kemudian mengambil sumpit kiri.
4.5.4 MASALAH SLEEPING BARBER
Masalah konkurensi klasik lainnya dianalogikan kondisinya seperti di tempat potong rambut, yang hanya memiliki satu kursi potong dan memiliki sejumlah n kursi tunggu. Jika tidak ada pelanggan maka tukang potong rambut (barber) akan tidur di kursi potong. Jika ada pelangan yang masuk maka si tukang potong harus dibangunkan. Jika pelanggan lainnya datang, pelanggan tersebut akan melihat apakah ada kursi tunggu yang tersedia dan menunggu disana. Jika ternyata tidak ada kursi tunggu yang kosong, pelanggan tersebut meninggalkan tempat tersebut.
Masalahnya adalah bagaimana mengatur agar tidak terjadi race condition untuk proses tukang potong dan proses pelanggan. Kondisi seperti ini umumnya terjadi pada kasus antrian, seperti hel pada esk yang dapat melayani sejumlah m panggilan lewat sejumlah n komputer secara simultan, di mana sering terjadi m > n. Salah satu solusinya adalah menggunakan 3 buah semaphore.
1. customers untuk menghitung jumlah pelanggan yang menunggu, tidak termasuk pelanggan yang sedang dipotong rambutnya,
2. barbers, untuk menghitung jumlah tukang potong yang tersedia atau yang sedang tidur, dimana dalam kasus ini hanya ada satu tukang potong sehingga cukup menggunakan mutex atau binary semaphore.
3. waitingmutex, untuk mensinkronisasi pengubahan terhadap nilai variabel waiting, yang digunakan untuk mencatat jumlah pelangan
122
Sistem Operasi
yang sedang menunggu. Perhatikan, sekalipun semaphore customers secara implisit memiliki nilai yang menunjukkan jumlah pelanggan yang sedang menunggu, pengubahan nilainya hanya dapat dilakukan lewat operasi wait dan signal. Untuk kebutuhan program, diperlukan variabel lain, yaitu waiting untuk mencatat jumlah pelanggan yang menunggu.
Secara lengkap, langkah-langkah sinkronisasi pada proses barber maupun customer ditunjukkan oleh Gambar 4.19.
Data yang dipakai bersama
var kursi Tunggu
waiting mteger customera, barbers, waitingmulex, semaphore customers, burturs 0; waitingimutex=1; waiting:=0:
Prosos Barber wall(customers): midur jika tidak ada pelanggan watt waitinginkite ki, akses te antrian tunggu waiting waiting-1: Miurangi jumlah antian signal barbersy laekarang berber siap melayani signal(warningmutex); //lepaskan akses intran operasi pemotongan rambut
Proses Customers
aignal(waltingmutex), Ankses antrian waiting skaira Tunggul fika ada kurst kosong wailing waiting +1: //tambah antrian signal(customers), nambah jumlah anthan signal(writingmutex); Repas akses antrian wait(barbers); //menunggu tukang potong dilayani potong rambut
else
signal waitingmulex)}
Gambar 4.19 Solusi sinkronisasi pada masalah sleeping barber
Tidak ada komentar:
Posting Komentar