Critical Section
7:56:00 AM
KertasputiH
, Posted in
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 enggiring 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:
I. Tidak ada dua proses secara bersamaan masuk ke dalam citical section.
II. Tidak ada asumsi mengenai kecepatan atau jumlah cpu.
III. Tidak ada proses yang berjalan di luar critical secion yang dapat mengeblok proses lain.
IV. 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
· eadlock free
· Starvation free
Pendekatan yang mungkin untuk solusi proses sinkronisasi
i. Solusi Piranti lunak (Software solution)
· Tanpa Sinkronisasi.
· Dengan Sinkronisasi.
· Low-level primitives: semaphore
· High-level primitives: monitors
ii. Solusi Piranti Keras (Hardware solution)
Mutual Exclusion
Mutual Exclusion: Kondisi-kondisi untuk solusi
Tiga kondisi untuk menentukan mutual Exclusion
1. Tidak ada dua proses yang pada saat bersamaan berada di critical region.
2. Tidak ada proses yang berjalan diluar critical region yang bisa menghambat proses lain
3. Tidak ada proses yang tidak bisa masuk ke critical region
Solusi
Cara-cara memecahkan masalah
• Hanya dua proses, Po dan P1
• Struktur umum dari proses adalah Pi (proses lain Pj)
do {
critical section
remainder section
} while(1);
Algoritma 1
Disini kita akan mencoba membuat sebuah rangkaian solusi-solusi dari permasalahan yang makin meningkat kerumitannya.
Pada semua contoh, i adalah proses yang sedang berjalan, j adalah proses yang lain. Pada contoh ini code.
i. Shared variables
• int turn
Initially turn=0
• turn = i, Pi can enter its critical section
ii. Process Pi
do {
while(turn!=1);
critical section
turn=j;
remainder section
} while(1);
iii. Memenuhi mutual exclusion, tapi bukan progress.
Algoritma 2
FLAG untuk setiap proses yang memberi STATE
Setiap proses memantau suatu flag yang mengindikasikan ia ingin memasuki critical section. Dia memeriksa flag poses lain dan tidak akan memasuki critical section bila ada proses lain yang sedang masuk.
i. Shared variables
• boolean flag[2];
initially flag [0] = flag [1] = false
• flag [i] = true , Pi ready to enter its critical section
ii. Process Pi
do {
flag[i]:=true;
while(turn!=1);
critical section
turn=j;
remainder section
} while(1);
iii. Memenuhi mutual exclusion, tapi tidak memenuhi progess.
Algoritma 3
FLAG untuk meminta izin masuk:
· Setiap proses mengeset sebuah flag untuk meminta izin masuk. Lalu setiap proses mentoggle bit untuk mengizinkan yang lain untuk yang pertama
· Kode ini dijalankan untuk setiap proses i
Shared variables
F boolean flag[2];
initially flag[0] = flag[1] = false
F flag[i] = true;
Pi ready to enter its critical section
· Gabungan shared variables dari algorima 1 dan 2
· Process Pi
do {
flag[i]:=true;
turn = j;
while(flag[j] and turn = j);
critical section
flag[i] = false;
remainder section
} while(1);
· Memenuhi ketiga persyaratan, memecahkan persoalan critical section untuk kedua proses
Algoritma Bakery
Critical Section untuk n buah proses:
Sebelum memasukkan proses ke critical section, proses menerima sebuah nomor. Pemegang nomor terkecil masuk ke critical section. Jika ada dua proses atau lebih menerima nomor sama, maka proses dengan indeks terkecil yang dilayani terlebih dahulu untuk masuk ke critical section. Skema penomoran selalu naik secara berurut contoh: 1, 2, 3, 3, 3, 3, 4, 5,...
boolean choosing [n];
long long long int number [n];
/* 64 bit maybe okay for about 600 years */
Array structure elements are initiallized to false and 0 respectively
while (true) {
choosing[i] = true;
number[i] = max(number[0], ... [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))) {}
}
number[i] = 0
}
Solves the critical-section problem
for n process
0 Response to "Critical Section"
Posting Komentar