Critical
Section
Critical
section adalah bagian dari program
yang mengakses sumber daya bersama. Hanya ketika sebuah proses berada di Bagian
Kritisnya dapat berada dalam posisi untuk mengganggu proses lain. Kita dapat
menghindari kondisi balapan dengan memastikan bahwa tidak ada dua proses
memasuki Bagian Kritis mereka pada saat yang bersamaan. Secara sederhana bagian kritis
adalah sekelompok instruksi / pernyataan atau wilayah kode yang perlu
dieksekusi secara atom, seperti mengakses sumber daya (file, input atau output
port, data global, dll).
Dalam pemrograman konkuren,
jika satu thread mencoba untuk mengubah nilai data bersama pada saat yang sama
ketika thread lain mencoba untuk membaca nilai (mis., Data balas antar utas),
hasilnya tidak dapat diprediksi.
Akses ke variabel bersama tersebut (memori
bersama, file bersama, port bersama, dll ...) untuk disinkronkan. Beberapa bahasa pemrograman
telah dibangun untuk mendukung sinkronisasi.
Sangat penting untuk memahami pentingnya
kondisi balapan saat menulis pemograman mode kernel (driver perangkat, utas
kernel, dll.). karena programmer dapat secara langsung
mengakses dan memodifikasi struktur data kernel.
Solusi sederhana untuk bagian kritis dapat
dipikirkan seperti yang ditunjukkan di bawah ini,
acquirLock ();
Bagian Proses Kritis
releaseLock ();
Sebuah utas harus mendapatkan kunci sebelum
mengeksekusi bagian kritis. Kunci dapat diperoleh hanya dengan satu utas. Ada berbagai cara untuk
mengimplementasikan kunci dalam kode pseudo di atas. Mari kita bahas di artikel
mendatang.
Solusi
dari masalah critical section harus memenuhi tiga syarat berikut:
Mutual
Exclusion.
Jika
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.
Terjadi
kemajuan (progress).
Jika
tidak ada proses yang sedang menjalankan critical
sectionnya dan jika terdapat lebih dari satu proses lain yang ingin masuk
ke critical section, maka hanya proses-proses yang tidak
sedang menjalankan remainder
sectionnya yang dapat berpartisipasi dalam memutuskan siapa yang berikutnya
yang akan masuk ke critical
section, dan pemilihan siapa
yang berhak masuk ke critical
sectionini tidak dapat ditunda secara tak terbatas (sehingga tidak terjadi deadlock).
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).
Kita mengasumsikan
bahwa setiap proses berjalan pada kecepatan yang bukan nol. Akan tetapi, tidak
ada asumsi lain mengenai kecepatan relatif proses-proses tersebut ataupun
jumlah CPU yang ada.
Ada dua jenis solusi
masalah critical section, yaitu:
Solusi
perangkat lunak
Dengan
menggunakan algoritma-alogoritma yang nilai kebenarannya tidak tergantung pada
asumsi-asumsi lain, selain bahwa setiap proses berjalan pada kecepatan yang
bukan nol.
Solusi
perangkat keras
Tergantung
pada beberapa instruksi mesin tertentu, misalnya dengan me-non-aktifkan
interupsi atau dengan mengunci suatu variabel tertentu
Untuk
selanjutnya akan dibahas algoritma-algoritma untuk solusi masalah critical section yang memenuhi tiga syarat seperti yang
telah disebutkan di atas. Solusi-solusi tersebut tidak tergantung pada asumsi
mengenai instruksi-instruksi perangkat keras atau jumlah prosesor yang dapat
didukung oleh perangkat keras. Namun, kita mengasumsikan bahwa insruksi bahasa
mesin yang dasar (instruksi-instruksi primitif seperti load, store, dan test)
dieksekusi secara atomik. Artinya, jika dua instruksi tersebut dieksekusi
secara konkuren, hasilnya ekuivalen dengan eksekusi instruksi tersebut secara
sekuensial dalam urutan tertentu. Jadi, jika load dan store dieksekusi
secara konkuren, load akan
mendapatkan salah satu dari nilai yang lama atau nilai yang baru, tetapi tidak
kombinasi dari keduanya.
Pada
bagian ini, kita membatasi pembahasan algoritma-algoritma untuk solusi critical section untuk dua proses saja. Proses-proses itu
adalah P0 dan P1.
Untuk memudahkan, ketika kita membahas Pi, kita
menggunakan Pj untuk
menyebut proses lainnya, sehingga j == 1-i.
Untuk mengilustrasikan
proses-proses yang akan masuk ke critical
section, kita
mengimplementasikan thread dengan menggunakan class Worker
dan abstract
class MutualExclusion. Class TestAlgoritma
akan digunakan untuk menjalankan ketiga algoritma tersebut.
/**
* Thread pekerja yang digunakan untuk
mengsimulasikan masalah
* critical section.
* Disadur dari buku Silberschatz dkk,
* Applied Operating Systems Concepts,
2000.
*/
public class Pekerja extends Thread
{
public Pekerja (String n, int i,
MutualExclusion s) {
nama = n;
id = i;
shared = s;
}
public void run() {
while (true) {
shared.masukCriticalSection(id);
System.out.println("Pekerja
" + nama +
" masuk critical
section");
MutualExclusion.criticalSection();
System.out.println("Pekerja
" + nama +
" keluar critical
section");
shared.keluarCriticalSection(id);
MutualExclusion.nonCriticalSection();
}
}
private String nama;
private int id;
private MutualExclusion shared;
}
|
/**
* Mengsimulasi critical dan non-critical
sections dengan
* sleeping untuk sejumlah waktu antara 0
dan 3 detik (random).
* Disadur dari buku Silberschatz dkk,
* Applied Operating Systems Concepts,
2000.
*/
public abstract class MutualExclusion
{
public static void criticalSection() {
try {
Thread.sleep( (int)
(Math.random() * 3000) );
}
catch (InterruptedException e) { }
}
public static void nonCriticalSection()
{
try {
Thread.sleep( (int)
(Math.random() * 3000) );
}
catch (InterruptedException e) { }
}
public abstract void
masukCriticalSection(int t);
public abstract void
keluarCriticalSection(int t);
public static final int TURN_0 = 0;
public static final int TURN_1 = 1;
}
|
/**
* Program untuk test solusi, akan create sebuah object untuk
* Algoritma_1, Algoritma_2, or
Algoritma_3.
* Disadur dari buku Silberschatz dkk,
* Applied Operating Systems Concepts,
2000.
*/
public class TestAlgoritma
{
public static void main(String args[])
{
//sesuai algoritma yang mau ditest
MutualExclusion alg = new
Algoritma_1();
Pekerja pertama = new
Pekerja("Runner 0", 0, alg);
Pekerja kedua = new
Pekerja("Runner 1", 1, alg);
pertama.start();
kedua.start();
}
}
|
Pada
algoritma 1, variabel yang digunakan bersama (shared variabel) adalah sebuah variabel
integer turn, yang
diinisialisasi awal nilai 0 (atau 1 di proses yang kedua). Jika turn == i, maka
proses Pidiizinkan
untuk mengeksekusi critical
sectionnya. Algoritma ini menjamin bahwa hanya ada satu proses pada suatu
saat yang berada di critical
section. Namun, algoritma ini
tidak memenuhi syarat terjadinya kemajuan, karena algoritma ini membutuhkan
pergiliran proses di dalam menjalankan critical
section. Misalnya, jika turn == 0 dan P1 ingin
masuk ke critical section, P1 tidak
dapat masuk, meskipun P0 sedang
berada di remainder section. Hal ini dikarenakan P0 belum
masuk ke critical section. dan oleh karenanya P0 belum
mengubah nilai turn (menjadi turn == 1.)
/**
* Program ini sesuai dengan solusi
critical section dengan
* menggunakan algoritma 1.
* Disadur dari buku Silberschatz dkk,
* Applied Operating Systems Concepts,
2000.
*/
public class Algoritma_1 extends
MutualExclusion
{
public Algoritma_1() {
turn = TURN_0;
}
public void masukCriticalSection(int t)
{
while (turn != t)
Thread.yield();
}
public void keluarCriticalSection(int
t) {
turn = 1 - t;
}
private volatile int turn;
}
|
Kelemahan
algoritma 1 adalah bahwa algoritma 1 tidak menyediakan informasi yang cukup
mengenai keadaan state setiap proses, ia hanya mengingat proses mana yang
diperbolehkan untuk memasuki critical
section. Untuk memecahkan
masalah ini, variabel turn diganti
dengan sebuah array, yaitu:
Setiap elemen dari
array tersebut diinisialisasi awal ke false. Jika flag[i] bernilai true, maka
ini mengindikasikan bahwa Pi siap
untuk masuk ke critical
section.
Setiap proses memantau
suatu flag yang mengindikasikan ia ingin memasuki critical section. Dia memeriksa flag proses lain dan
tidak akan memasuki critical
section bila ada proses lain
yang sedang masuk.
/**
* Program ini sesuai dengan solusi
critical section dengan
* menggunakan algoritma 2.
* Disadur dari buku Silberschatz dkk,
* Applied Operating Systems Concepts,
2000.
*/
public class Algoritma_2 extends
MutualExclusion
{
public Algoritma_2() {
flag[0] = false;
flag[1] = false;
}
public void masukCriticalSection(int t)
{
int other;
other = 1 - t;
flag[t] = true;
while (flag[other] == true)
Thread.yield();
}
public void keluarCriticalSection(int
t) {
flag[t] = false;
}
private volatile boolean[] flag = new
boolean[2];
}
|
Di
algoritma 2 ini, proses Pi pertama-tama
mengubah nilai (set) flag[i] menjadi true, menandakan
bahwa Pi mau
masuk ke critical section. Kemudian Pi mengecek
apakah proses Pj juga
mau masuk kecritical section. Jika
proses Pj mau
masuk, maka proses Pi akan
menunggu sampai proses Pj mengubah
statenya bahwa ia tidak mau lagi masuk ke critical
section (flag[j] ==
false). Pada saat itu, maka Piakan
masuk ke critical section. Ketika keluar dari critical section, Pi akan
mengset nilai flag[i] menjadi false, memperbolehkan
proses lain (jika ada proses lain yang menunggu) untuk masuk ke critical section.
Solusi dengan algoritma
2 ini memenuhi syarat mutual
exclusion, tetapi tidak
memenuhi syarat terjadinya kemajuan. Untuk mengilustrasikan masalah ini,
perhatikan urutan eksekusi berikut:
T0: P0 sets flag[0] true
T1: P1 sets flag[1] true
|
Sekarang P0 dan P1 akan
loop selama-lamanya di dalam statement while masing-masing.
Perhatikan bahwa
mengubah urutan instuksi untuk mengset flag[i] dan
mengecek nilai flag[j] tidak
akan memecahkan masalah ini. Kita malah akan berada di situasi di mana ada
kemungkinan untuk kedua proses berada di critical
section pada saat yang
bersamaan, yang akan melanggar syarat mutual
exclusion.
Dengan
menggabungkan algoritma 1 dan algoritma 2, kita akan memperoleh solusi yang
tepat untuk masalah critical
section, di mana solusi itu
akan memenuhi tiga syarat seperti yang telah disebutkan di atas. Setiap proses
menggunakan dua variabel:
boolean flag[2];
int turn;
|
Awalnya flag[0] = flag[1] = false, dan
nilai turn tergantung
dari proses yang boleh masuk (0 atau 1).
Untuk masuk ke critical section, proses Pi pertama-tama
mengset flag[i] menjadi true, dan
kemudian mengset nilai turn menjadi j, sehingga
memperbolehkan proses lain yang ingin masuk ke critical section untuk dapat masuk ke critical section. Jika kedua
proses mencoba untuk masuk ke critical
section pada saat yang
bersamaan, turn akan
diset ke nilai i dan j pada
saat yang hampir bersamaan. Yang terakhir mengubah nilai turn akan
mempersilakan proses yang lainnya untuk masuk ke critical section.
/**
* Program ini sesuai dengan solusi
critical section dengan
* menggunakan algoritma 3.
* Disadur dari buku Silberschatz dkk,
* Applied Operating Systems Concepts, 2000.
*/
public class Algoritma_3 extends
MutualExclusion
{
public Algoritma_3() {
flag[0] = false;
flag[1] = false;
turn = TURN_0;
}
public void masukCriticalSection(int t)
{
int other;
other = 1 - t;
flag[t] = true;
turn = other;
while ( (flag[other] == true)
&& (turn == other) )
Thread.yield();
}
public void keluarCriticalSection(int
t) {
flag[t] = false;
}
private volatile int turn;
private volatile boolean[] flag = new
boolean[2];
}
|
Diperkenalkan
pertama kali oleh Leslie Lamport, merupakan algoritma yang didasarkan pada
algoritma penjadwalan yang biasanya digunakan oleh tukang roti, di mana 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, tukang roti 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
do {
choosing[i] = true;
number[i] = max(number[0], number
[1], ..., number [n+1])+1;
choosing[i] = false;
for (j=0; j < n; j++) {
while (choosing[j]);
while ((number[j]!=0) &&
((number[j],j) < number[i],i)));
}
<foreignphrase>critical
section</foreignphrase>
number[i] = 0;
<foreignphrase>remainder
section</foreignphrase>
} while (1);
|
Sumber :
