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
Progress
Bounded Waiting
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.
Berikut ini algoritma-algoritma
yang digunakan untuk mengatasi masalah critical section:
1. 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 printah 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.
2. 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.
3. 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] = truedan 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 waitingyang 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 sectionmaka dapat dipastikan ada proses yang bisa menggunakan critical section, dan proses tidak
perlu menunggu selamanya untuk dapat masuk ke critical section.
4. 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.
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:
Berubah dari running ke waiting state.
Berubah dari running ke ready state.
Berubah dari waiting ke ready state.
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:
a.
sistem lebih responsif daripada sistem yang memakai penjadwalan Non Preemptive.
b.
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.
REFERENCE :
Tidak ada komentar:
Posting Komentar