1. Pengertian Critical Section
Critical Section adalah bagian dari suatu proses
yang akan melakukan akses dan manipulasi data. Ketika sebuah proses sedang dijalankan dalam critical
section nya, tidak ada proses lain yang boleh dijalankan dalam critical section
tersebut, karena akan menyebabkan keadaan mutually exclusive. Mutually exclusive yakni keadaan terjadinya akses
resources yang sama di saat yang bersamaan, mutually exclusive memerlukan
kondisi tertentu agar dapat terpenuhi.
2. Kegunaan dari Critical Section
Critical section biasanya digunakan saat program multithreading,
dimana program tersebut terdiri dari banyak thread, akan mengubah nilai dari
variabel. Dalam hal ini critical section diperlukan untuk melindungi variabel
dari concurrent access (pengaksesan program di saat yang bersamaan) yang dapat
membuat nilai dari variabel tersebut menjadi tidak konsisten.
Seperti yang telah kita ketahui bahwa proses dapat
bekerja sendiri (independent process) dan juga dapat bekerja bersama
proses-proses yang lain (cooperating process). Pada umumnya ketika proses
saling bekerjasama (cooperating process) maka proses-proses tersebut akan
saling berbagi data. Pada saat proses-proses berbagi data, ada kemungkinan
bahwa data yang dibagi secara bersama itu akan menjadi tidak konsisten
dikarenakan adanya kemungkinan proses-proses tersebut melakukan
akses secara bersamaan yang menyebabkan data tersebut berubah, hal ini dikenal
dengan istilah Race Condition.
Oleh karena itu, dibutuhkan solusi yang tepat untuk
menghindari munculnya Race Condition. Solusi tersebut harus memenuhi ketiga
syarat berikut:
a. Mutual Exclusion
Mutual Exclusion merupakan
sebuah jalan yang menjamin jika sebuah proses sedang menggunakan variabel atau
berkas yang digunakan bersama-sama, proses lain akan dikeluarkan dari pekerjaan
yang sama.
Misal proses Pi sedang menjalankan critical section (dari proses
Pi), maka tidak ada proses-proses lain yang dapat menjalankan critical section
dari proses-proses tersebut. Dengan kata lain, tidak ada dua proses yang berada
di critical section pada saat yang bersamaan.
do {
entry section
critical section
exit section
remainder section
} while (1);
Setiap proses harus meminta izin untuk memasuki critical section-nya. Bagian
dari kode yang mengimplementasikan izin ini disebut entry section. Akhir dari
critical section itu disebut exit section. Bagian kode selanjutnya disebut remainder
section. Dari kode di atas, dapat kita lihat bahwa untuk bisa memasuki critical
section sebuah proses harus melalui entry section.
Gambar 18.3. ilustrasi
proses Pi
b. Progress
Terjadi kemajuan (progress), Jika tidak ada
proses yang sedang menjalankan critical section-nya dan jika terdapat lebih
dari satu proses lain yang ingin masuk ke critical section, maka hanya proses-proses
yang tidak sedang menjalankan remainder section-nya yang dapat berpartisipasi
dalam memutuskan siapa yang berikutnya yang akan masuk ke critical section, dan
pemilihan siapa yang berhak masuk ke critical section ini tidak dapat ditunda
secara tak terbatas (sehingga tidak terjadi deadlock).
c. Bounded Waiting
Ada batas waktu tunggu (bounded waiting), Jika
seandainya ada proses yang sedang menjalankan critical section, maka terdapat
batasan waktu berapa lama suatu proses lain harus menunggu giliran untuk
mengakses critical section. Dengan adanya batas waktu tunggu akan menjamin
proses dapat mengakses ke critical section (tidak mengalami starvation: proses
seolah-olah berhenti, menunggu request akses ke critical section
diperbolehkan).
Ada dua jenis solusi untuk memecahkan masalah critical section, yaitu.
1. Solusi Perangkat Lunak. Solusi ini menggunakan
algoritma-algoritma untuk mengatasi masalah critical section.
2. Solusi Perangkat Keras. Solusi ini tergantung pada
beberapa instruksi mesin tertentu, misalnya dengan me-non-aktifkan interupsi,
mengunci suatu variabel tertentu atau menggunakan instruksi level mesin seperti
tes dan set.
Berikut ini algoritma-algoritma yang digunakan untuk
mengatasi masalah critical section:
- Algoritma I
Algoritma I memberikan giliran kepada setiap proses
untuk memproses critical section-nya secara bergantian. Asumsi yang digunakan disini setiap proses secara
bergantian memasuki critical section-nya.
Statement while(turn != 4) akan memeriksa apakah
pada saat itu proses 4 mendapatkan turn, jika tidak maka proses 4 akan busy
waiting(lihat kembali bahwa perintah while diakhiri dengan “;”). Jika ternyata
pada saat itu merupakan giliran proses 4 maka proses 4 akan mengerjakan
critical section-nya. Sampai sini jelas terlihat bahwa mutex terpenuhi! Proses
yang tidak mendapatkan turn tidak akan dapat mengerjakan critical section-nya
dan turn hanya akan diberikan pada satu proses saja.
Setelah proses 4 selesai mengerjakan critical
section maka turn diberikan pada proses lainnya (turn= j, j merupakan proses
selanjutnya yang dapat mengerjakan critical section). Setelah turn-nya
diberikan kepada proses lain, proses 4 akan mengerjakan remainder section.
Disini jelas terlihat bahwa syarat bounded waiting jelas terpenuhi.
Ingat asumsi yang digunakan dalam algoritma ini adalah setiap proses secar
bergantian memasuki critical section-nya, jika pada saat itu proses 4 ternyata
belum mau mengerjakan critical section-nya maka proses ke-j tidak akan
mendapatkan kesempatan untuk mengerjakan critical section walau saat itu
sebenarnya proses ke-j akan memasuki critical section. Artinya syarat progress
tidak terpenuhi pada algoritma ini.
- Algoritma II
Masalah yang terjadi pada algoritma 1 ialah ketika
di entry section terdapat sebuah proses yang ingin masuk ke critical section,
sementara di critical section sendiri tidak ada proses yang sedang berjalan,
tetapi proses yang ada di entry section tadi tidak bisa masuk ke critical
section. Hal ini terjadi karena giliran untuk memasuki critical section adalah
giliran proses yg lain sementara proses tersebut masih berada di remainder
section. Untuk mengatasi masalah ini maka dapat diatasi dengan merubah variabel
trun pada algoritma pertama dengan array
Boolean flag [2];
Elemen array diinisialisasi false. Jika flag[i]
true, nilai tersebut menandakan bahwa Pi ready untuk memasuki critical section.
Pada algoritma ini. hal pertama yang dilakukan ialah mengeset proses Pi dengan
nilai True, ini menandakan bahwa Pi ready untuk masuk ke critical section.
kemudian, Pi memeriksa apakah Pj tidak ready untuk memasukui critical section. Jika
Pj ready, maka Pi menunggu sampai Pj keluar dari critical section (flag[j]
bernilai false). Ketika keluar dari critcal section, Pi harus merubah nilai flag[i]
menjadi false agar prores lain dapat memasuki critical section.
Contoh:
Pada algoritma ini, kriteria Mutual-exclusion
terpenuhi, tetapi tidak memenuhi kriteria
progress. Ilustrasinya seperti di bawah ini.
T0 : Po set flag [0] = true
T1 : Po set flag [1] = true
Dari ilustrasi diatas terlihat bahwa algoritma ini
memungkinkan terjadinya nilai true untuk kedua proses, akibatnya tidak ada
proses yang akan berhasil memasuki critical section.
Jadi untuk algoritma 2 masih terdapat kelemahan,
seperti yang terjadi di atas.
- Algoritma III
Idenya berasal dari algoritma 1 dan 2. Algoritma 3
mengatasi kelemahan pada algoritma 1 dan 2 sehingga progres yang diperlukan
untuk mengatasi critical section terpenuhi.
Algoritma III ditemukan oleh G.L. Petterson pada
tahun 1981 dan dikenal juga sebagai Algoritma Petterson. Petterson menemukan
cara yang sederhana untuk mengatur proses agar memenuhi mutual exclusion.
Algoritma ini adalah solusi untuk memecahkan masalah critical section pada dua
proses. Ide dari algoritma ini adalah menggabungkan variabel yang di- sharing
pada Algoritma I dan Algoritma II, yaitu variabel turn dan variabel flag.
Sama
seperti pada Algoritma I dan II, variabel turn menunjukkan giliran proses mana
yang diperbolehkan memasuki critical section dan variabel flag menunjukkan
apakah suatu proses membutuhkan akses ke critical section atau tidak.
Awalnya flag untuk kedua proses diinisialisai
bernilai false, yang artinya kedua proses tersebut tidak membutuhkan akses ke critical
section. Kemudian jika suatu proses ingin memasuki critical section, ia akan
mengubah flag-nya menjadi true (memberikan tanda bahwa ia butuh critical
section) lalu proses tersebut memberikan turn kepada lawannya. Jika lawannya
tidak menginginkan critical section (flag-nya false), maka proses tersebut
dapat menggunakan critical section, dan setelah selesai menggunakan critical
section ia akan mengubah flag-nya menjadi false.
Tetapi apabila proses lawannya
juga menginginkan critical section maka proses lawan-lah yang dapat memasuki critical
section, dan proses tersebut harus menunggu sampai proses lawan menyelesaikan critical
section dan mengubah flag-nya menjadi false.
Misalkan ketika P0 membutuhkan critical section,
maka P0 akan mengubah flag[0] = true, lalu P0 mengubah turn= 1. Jika P1
mempunyai flag[1] = false, (berapapun nilai turn) maka P0 yang dapat mengakses critical
section. Namun apabila P1 juga membutuhkan critical section, karena flag[1] = true
dan turn= 1, maka P1 yang dapat memasuki critical section dan P0 harus menunggu
sampai P1 menyelesaikan critical section dan mengubah flag[1] = false, setelah
itu barulah P0 dapat mengakses critical section.
Bagaimana bila kedua proses membutuhkan critical
section secara bersamaan? Proses mana yang dapat mengakses critical section terlebih
dahulu? Apabila kedua proses (P0 dan P1) datang bersamaan, kedua proses akan
menset masing-masing flag menjadi true (flag[0] = true dan flag[1] = true),
dalam kondisi ini P0 dapat mengubah turn = 1 dan P1 juga dapat mengubah turn =
0. Proses yang dapat mengakses critical section terlebih dahulu adalah proses
yang terlebih dahulu mengubah turn menjadi turn lawannya. Misalkan P0 terlebih
dahulu mengubah turn= 1, lalu P1 akan mengubah turn= 0, karena turn yang
terakhir adalah 0 maka P0-lah yang dapat mengakses critical section terlebih
dahulu dan P1 harus menunggu.
Algoritma III memenuhi ketiga syarat yang
dibutuhkan. Syarat progress dan bounded waiting yang tidak dipenuhi pada
Algoritma I dan II dapat dipenuhi oleh algoritma ini karena ketika ada proses
yang ingin mengakses critical section dan tidak ada yang menggunakan critical
section maka dapat dipastikan ada proses yang bisa menggunakan critical section,
dan proses tidak perlu menunggu selamanya untuk dapat masuk ke critical section.
- Algoritma Tukang Roti
Algoritma ini didasarkan pada algoritma penjadwalan
yang biasanya digunakan oleh tukang roti, dimana urutan pelayanan ditentukan
dalam situasi yang sangat sibuk. Algoritma ini dapat digunakan untuk memecahkan
masalah critical section untuk n buah proses, yang diilustrasikan dengan n buah
pelanggan. Ketika memasuki toko, setiap pelanggan menerima sebuah nomor.
Sayangnya, algoritma tukang roti ini
tidak dapat menjamin bahwa dua proses (dua pelanggan) tidak akan menerima nomor
yang sama. Dalam kasus di mana dua proses menerima nomor yang sama, maka proses
dengan nomor ID terkecil yang akan dilayani dahulu. Jadi, jika Pi dan Pj
menerima nomor yang sama dan i < j, maka Pi dilayani dahulu. Karena setiap
nama proses adalah unik dan berurut, maka algoritma ini dapat digunakan untuk
memecahkan masalah critical section untuk n buah proses.
Struktur data umum algoritma ini adalah:
boolean choosing[n];
int number [n];
Awalnya, struktur data ini diinisialisasi masing-masing ke false dan 0, dan menggunakan notasi berikut:
– (a, b) < (c, d) jika a < c atau jika a= c
dan b < d
– max(a0, …, an-1) adalah sebuah bilangan k,
sedemikian sehingga k >= ai untuk setiap i= 0, , n – 1
Dengan demikian, diketahui bahwa Algoritma I dan II terbukti tidak dapat memecahkan masalah critical section untuk dua proses karena tidak memenuhi syarat progress dan bounded waiting. Algoritma yang dapat menyelesaikan masalah critical section pada dua proses adalah Algoritma III. Sedangkan untuk masalah critical section pada n-buah proses dapat diselesaikan dengan menggunakan Algoritma Tukang Roti.
4. Komponen Critical Section
- Entry Section : kode yang digunakan untuk masuk ke dalam critical section.
- Critical Section : kode dimana hanya satu proses yang dapat dieksekusi dalam satu waktu.
- Exit Section : Akhir dari critical section, mengijinkan proses lainnya.
- Remainder Section : kode istirahat setelah masuk ke critical section.
Sumber :
https://mediekaputra.wordpress.com/2011/03/26/critical-section/
ftp://ftp.gunadarma.ac.id/linux/docs/v06/Kuliah/SistemOperasi/BUKU/SistemOperasi-4.X-1/ch18s04.html
https://asripujiastuti.files.wordpress.com/2012/07/modul-7_proses_sinkronisasi.ppt
