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.
Critical section biasanya digunakan saat program multithreading, dimana program tersebut terdiri dari banyak thread, akan mengubah nilai dari variabel. Dalam hal ini critical sectiondiperlukan 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:
Mutual Exclusion.
Jika suatu proses sedang menjalankan critical section-nya, maka proses-proses lain tidak dapat menjalankan critical section mereka. 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 section-nya dan ada proses-proses lain yang ingin masuk ke critical section, maka hanya proses-proses yang yang sedang berada dalam entry section saja yang dapat berkompetisi untuk mengerjakan critical section.
Ada batas waktu tunggu (bounded waiting).
Jika seandainya ada proses yang sedang menjalankan critical section, maka proses lain memiliki waktu tunggu yang ada batasnya untuk menjalankan critical section-nya, sehingga dapat dipastikan bahwa proses tersebut dapat mengakses critical section-nya (tidak mengalami starvation: proses seolah-olah berhenti, menunggu request akses ke critical section diperbolehkan).
Ada dua jenis solusi untuk memecahkan masalah critical section, yaitu :
Solusi Perangkat Lunak. Solusi ini menggunakan algoritma-algoritma untuk mengatasi masalah critical section.
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.
Selanjutnya akan dibahas sebuah algoritma sebagai solusi masalah dari critical section yang memenuhi tiga syarat seperti yang telah disebutkan di atas. Solusi ini 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.
Berikut ini algoritma-algoritma yang digunakan untuk mengatasi masalah critical section :
Algoritma 1
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 Pi diizinkan 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;
}
Algoritma 2
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:
boolean flag[2];
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 Pi akan 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 dicritical section pada saat yang bersamaan, yang akan melanggar syarat mutual exclusion.
Algoritma 3
Dengan menggabungkan algoritma 1 dan algoritma 2, kita akan memperoleh solusi yang tepat untuk masalahcritical 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];
}
Solusi Untuk Proses Jamak: Algoritma Tukang Roti
Algoritma ini didasarkan pada algoritma penjadualan 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, 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
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);
Penjadwalan CPU
Penjadwalan CPU adalah suatu proses pengaturan atau penjadwalan proses-proses yang ada di dalam komputer. Dimana proses-proses tersebut berjalan dalam pola yang disebut Siklus Burst.
Penjadwalan sangat penting dalam menentukan performance sebuah komputer karena mengatur alokasi resource dari CPU untuk menjalankan proses-proses di dalam komputer. Penjadwalan CPU merupakan suatu konsep dasar dari multiprograming, karena dengan adanya penjadwalan dari CPU itu sendiri maka proses-proses tersebut akan mendapatkan alokasi resource dari CPU.
Penjadwalan CPU mungkin akan dijalankan ketika proses dalam keadaan:
1. Berubah dari running ke waiting state.
2. Berubah dari running ke ready state.
3. Berubah dari waiting ke ready state.
4. Dihentikan.
Penjadwalan nomor 1 dan 4 bersifat Non Preemptive sedangkan lainnya Preemptive.
Penjadwalan yang biasa digunakan sistem operasi dewasa ini biasanya bersifat Preemptive. Bahkan beberapa penjadwalan sistem operasi, contohnya Linux 2.6, mempunyai kemampuan Preemptive terhadap system call-nya ( preemptible kernel).
Penjadwalan CPU secara garis besar dibagi menjadi 2, yaitu Penjadwalan Preemptive dan Penjadwalan Non Preemptive.
1. Penjadwalan Pre-emptive.
Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. Penjadwalan ini bisa saja termasuk penjadwalan proses atau I/O.
Dengan kata lain, penjadwalan Preemptive melibatkan mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem untuk menentukan proses mana yang akan dieksekusi selanjutnya.
Penjadwalan Preemptive memungkinkan sistem untuk lebih bisa menjamin bahwa setiap proses mendapat sebuah slice waktu operasi. Dan juga membuat sistem lebih cepat merespon terhadap event dari luar (contohnya seperti ada data yang masuk) yang membutuhkan reaksi cepat dari satu atau beberapa proses.
Lama waktu suatu proses diizinkan untuk dieksekusi dalam penjadwalan Preemptive disebut time slice/quantum.
Penjadwalan berjalan setiap satu satuan time slice untuk memilih proses mana yang akan berjalan selanjutnya. Bila time slice terlalu pendek maka penjadwal akan memakan terlalu banyak waktu proses, tetapi bila time slice terlau lama maka memungkinkan proses untuk tidak dapat merespon terhadap event dari luar secepat yang diharapkan.
Dalam waktu-waktu tertentu, proses dapat dikelompokkan ke dalam dua kategori: proses yang memiliki Burst I/O yang sangat lama disebut I/O Bound, dan proses yang memiliki Burst CPU yang sangat lama disebut CPU Bound. Terkadang juga suatu sistem mengalami kondisi yang disebut busywait, yaitu saat dimana sistem menunggu request input(seperti disk, keyboard, atau jaringan). Saat busywait tersebut, proses tidak melakukan sesuatu yang produktif, tetapi tetap memakan resource dari CPU. Dengan penjadwalan Preemptive, hal tersebut dapat dihindari.
Keuntungan penggunaan penjadwalan pre-emptive:
1. Sistem lebih responsif daripada sistem yang memakai penjadwalan Non Preemptive.
2. Sistem terhindar dari keadaan busywait.
contoh sistem operasi yang menerapkan penjadwalan Preemptive:
Windows 95, Windows XP, Linux, Unix, AmigaOS, MacOS X, dan Windows NT .
2. Penjadwalan Non Pre-emptive
Penjadwalan Non Preemptive ialah salah satu jenis penjadwalan dimana sistem operasi tidak pernah melakukan context switch dari proses yang sedang berjalan ke proses yang lain. Dengan kata lain, proses yang sedang berjalan tidak bisa di- interupt.
Penjadwalan Non Preemptive terjadi ketika proses hanya :
1. Berjalan dari running state sampai waiting state.
2. Dihentikan.
Ini berarti CPU menjaga proses sampai proses itu pindah ke waiting state ataupun dihentikan (proses tidak diganggu). Metode ini digunakan oleh Microsoft Windows 3.1 dan Macintosh. Ini adalah metode yang dapat digunakan untuk platforms hardware tertentu, karena tidak memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk meng interupt pada metode penjadwalan Preemptive).
Dispatcher
Komponen yang lain yang terlibat dalam penjadwalan CPU adalah dispatcher.
Dispatcher adalah modul yang memberikan kontrol CPU kepada proses yang sedang terjadwal.
Fungsinya:
Context switching
Mengganti state dari suatu proses dan mengembalikannya untuk menghindari monopoli CPU time. Context switching dilakukan untuk menangani suatu interrupt(misalnya menunggu waktu I/O). Untuk menyimpan state dari proses-proses yang terjadwal sebuah Process Control Blockharus dibuat untuk mengingat proses-proses yang sedang diatur scheduler. Selain state suatu proses, PCB juga menyimpan process ID, program counter(posisi saat ini pada program), prioritas proses dan data-data tambahan lainnya.
Switching to user mode dari kernel mode.
Lompat dari suatu bagian di progam user untuk mengulang program.
Dispatcher seharusnya dapat dilakukan secepat mungkin. Dispatch Latency adalah waktu yang diperlukan dispatcher untuk menghentikan suatu proses dan memulai proses yang lain.
Sumber :
https://mediekaputra.wordpress.com/2011/03/26/critical-section/
http://www.infomugi.com/2013/07/penjelasan-solusi-critical-section.html
http://operatingsystem12.blogspot.com/2011/04/problema-critical-section-serta.html
No comments:
Post a Comment