Minggu, 21 Agustus 2016
Konsep Dan Algoritma Penjadwalan (SOJ)
ALGORITMA PENJADWALAN PROCESSOR
Penjadwalan
berkaitan dengan permasalahan memutuskan proses mana yang akan dilaksanakan
dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan
mengantri di ready
queue.
Algoritma
penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan
dieksekusi oleh CPU.
Algoritma
ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU.
Dengan menggunakan algoritma ini setiap proses yang berada pada status ready
dimasukkan kedalam FIFO queue atau antrian dengan prinsip first in
first out, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih
dahulu yang akan dieksekusi.
Contoh: Ada
tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki
burst time 24 ms, P2 memiliki burst time 3 ms, dan P3 memiliki burst time 3 ms.
Hitunglah waiting time rata-rata dan turnaround time( burst
time + waiting time) dari ketiga proses tersebut dengan menggunakan
algoritma FCFS. Waiting time untuk P1 adalah 0 ms (P1 tidak perlu
menunggu), sedangkan untuk P2 adalah sebesar 24 ms (menunggu P1 selesai), dan
untuk P3 sebesar 27 ms (menunggu P1 dan P2 selesai).
Urutan kedatangan adalah P1, P2 ,
P3; gantt chart untuk urutan ini adalah:
Waiting time rata-ratanya adalah sebesar(0+24+27)/3 = 17ms. Turnaround
time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 27 ms (dihitung
dari awal kedatangan P2 hingga selesai dieksekusi), untuk P3 sebesar 30 ms. Turnaround
time rata-rata untuk ketiga proses tersebut adalah (24+27+30)/3 = 27 ms.
Kelemahan dari algoritma ini:
1.
Waiting
time rata-ratanya cukup lama.
2.
Terjadinya convoy effect,
yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang
dieksekusi oleh CPU. Algoritma ini juga menerapkan konsep non-preemptive, yaitu
setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh
proses yang lain.
Misalkan proses dibalik sehingga
urutan kedatangan adalah P3, P2, P1. Waiting time adalah P1=6; P2=3;
P3=0. Average waiting time: (6+3+0)/3=3.
SJF (Shortest Job First)
Pada algoritma ini setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.
Burst
time:asumsi berapa lama sebuah proses membutuhkan CPU diantara proses menunggunya
I/O. Hal ini tidak dapat diprediksi secara tepat sebelum dimulainya sebuah
proses. Artinya jumlah waktu yang dibutuhkan sebuah proses dalam menggunakan
CPU dalam sebuah satuan waktu. (Sebuah proses dapat menggunakan CPU selama
beberapa kali selama task yang diberikan belum
diselesaikan.
Process
|
Arrival Time
|
Burst Time
|
P1
|
0.0
|
7
|
P2
|
2.0
|
4
|
P3
|
4.0
|
1
|
P4
|
5.0
|
4
|
Contoh: Ada 4 buah proses yang
datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst
time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time
4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4
dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting
time rata-rata dan turnaround time dari keempat proses tersebut
dengan mengunakan algoritma SJF.
Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0
+6+3+7)/4=4 ms.
Average waiting time rata-rata untuk
ketiga prses tersebut adalah sebesar (9+1+0+2)/4=3 ms.
Ada beberapa kekurangan dari algoritma ini yaitu:
1.
Susahnya untuk memprediksi burst time proses yang akan
dieksekusi selanjutnya.
2.
Proses yang mempunyai burst time yang besar
akan memiliki waiting time yang besar pula karena yang dieksekusi
terlebih dahulu adalah proses dengan burst time yang lebih kecil.
Algoritma ini dapat dibagi menjadi dua bagian yaitu
:
1.
Preemptive . Jika ada proses yang sedang
dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang
lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang
sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready
queue tersebut. Preemptive SJF sering disebut juga
Shortest-Remaining- Time-First scheduling.
2.
Non-preemptive . CPU tidak memperbolehkan
proses yang ada di ready queue untuk menggeser proses yang sedang
dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time
yang lebih kecil.
Priority Scheduling
Priority
Scheduling merupakan algoritma penjadwalan
yang mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses
memiliki prioritasnya masing-masing.
Prioritas suatu proses dapat
ditentukan melalui beberapa karakteristik antara lain:
1.
Time limit.
2.
Memory
requirement.
3.
Akses file.
4.
Perbandingan antara burst M/K
dengan CPU burst.
5.
Tingkat kepentingan proses.
Priority scheduling juga dapat dijalankan secara preemptive maupun non-preemptive.
Pada preemptive, jika ada suatu proses yang baru datang memiliki
prioritas yang lebih tinggi daripada proses yang sedang dijalankan, maka proses
yang sedang berjalan tersebut dihentikan, lalu CPU dialihkan untuk proses yang
baru datang tersebut. Sementara itu, pada non-preemptive, proses yang
baru datang tidak dapat menganggu proses yang sedang berjalan, tetapi hanya
diletakkan di depan queue.
Kelemahan pada priority scheduling
adalah dapat terjadinya indefinite blocking( starvation). Suatu
proses dengan prioritas yang rendah memiliki kemungkinan untuk tidak dieksekusi
jika terdapat proses lain yang memiliki prioritas lebih tinggi darinya.
Solusi dari permasalahan ini adalah aging,
yaitu meningkatkan prioritas dari setiap proses yang menunggu dalam queue
secara bertahap.
Contoh: Setiap 10 menit, prioritas
dari masing-masing proses yang menunggu dalam queue dinaikkan satu
tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21
jam 20 menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang
tertinggi (semakin kecil angka menunjukkan bahwa prioritasnya semakin tinggi).
Round Robin
Algoritma ini menggilir proses yang
ada di antrian. Proses akan mendapat jatah sebesar time quantum. Jika time
quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke
proses berikutnya. Tentu proses ini cukup adil karena tak ada proses yang
diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU yaitu
(1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.
Algoritma ini sepenuhnya bergantung
besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja
dengan algoritma first come first served. Jika terlalu kecil, akan
semakin banyak peralihan proses sehingga banyak waktu terbuang.
Permasalahan utama pada Round
Robin adalah menentukan besarnya time quantum. Jika time quantum
yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai
dalam 1 quantum. Hal ini tidak baik karena akan terjadi banyak switch,
padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain
(disebut dengan context switches time). Sebaliknya, jika time quantum terlalu
besar, algoritma Round Robin akan berjalan seperti algoritma first
come first served. Time quantum yang ideal adalah jika 80% dari
total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.
|
|
Multilevel Queue
Ide dasar dari algoritma ini
berdasarkan pada sistem prioritas proses. Prinsipnya, jika setiap proses dapat
dikelompokkan berdasarkan prioritasnya, maka akan didapati queue
seperti pada gambar berikut:
Dari gambar tersebut terlihat bahwa akan terjadi
pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul ide untuk
menganggap kelompok-kelompok tersbut sebagai sebuah antrian-antrian kecil yang
merupakan bagian dari antrian keseluruhan proses, yang sering disebut dengan algoritma
multilevel queue.
Dalam hal ini, dapat dilihat bahwa seolah-olah
algoritma dengan prioritas yang dasar adalah algoritma multilevel queue
dimana setiap queue akan berjalan dengan algoritma FCFS yang memiliki
banyak kelemahan. Oleh karena itu, dalam prakteknya, algoritma multilevel
queue memungkinkan adanya penerapan algoritma internal dalam masing-masing
sub-antriannya yang bisa memiliki algoritma internal yang berbeda untuk
meningkatkan kinerjanya.
Berawal dari priority scheduling,
algoritma ini pun memiliki kelemahan yang sama dengan priority scheduling,
yaitu sangat mungkin bahwa suatu proses pada queue dengan prioritas rendah bisa
saja tidak mendapat jatah CPU. Untuk mengatasi hal tersebut, salah satu caranya
adalah dengan memodifikasi algoritma ini dengan adanya jatah waktu maksimal
untuk tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu,
maka prosesnya akan dihentikan dan digantikan oleh antrian dibawahnya, dan
tentu saja batas waktu untuk tiap antrian bisa saja sangat berbeda tergantung
pada prioritas masing-masing antrian.
Multilevel Feedback Queue
Algoritma ini mirip sekali
dengan algoritma multilevel queue. Perbedaannya ialah algoritma ini
mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu
lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Hal ini
menguntungkan proses interaksi karena proses ini hanya memakai waktu CPU yang
sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini
akan dinaikkan tingkatannya. Biasanya prioritas tertinggi diberikan kepada
proses dengan CPU burst terkecil, dengan begitu CPU akan terutilisasi
penuh dan M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst
proses juga semakin besar.
Gambar 14.7. Multilevel Feedback Queue
Algoritma ini didefinisikan melalui
beberapa parameter, antara lain:
a.
Jumlah antrian.
b.
Algoritma penjadwalan tiap antrian.
c.
Kapan menaikkan proses ke antrian
yang lebih tinggi.
d.
Kapan menurunkan proses ke antrian
yang lebih rendah.
e.
Antrian mana yang akan dimasuki
proses yang membutuhkan.
Dengan pendefinisian seperti tadi
membuat algoritma ini sering dipakai, karena algoritma ini mudah dikonfigurasi
ulang supaya cocok dengan sistem. Tapi untuk mengatahui mana penjadwal terbaik,
kita harus mengetahui nilai parameter tersebut.
Multilevel feedback queue adalah salah satu algoritma yang berdasar pada algoritma multilevel
queue. Perbedaan mendasar yang membedakan multilevel feedback queue
dengan multilevel queue biasa adalah terletak pada adanya kemungkinan
suatu proses berpindah dari satu antrian ke antrian lainnya, entah dengan
prioritas yang lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut.
1.
Semua proses yang baru datang akan
diletakkan pada queue 0 ( quantum= 8 ms).
2.
Jika suatu proses tidak dapat
diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan
ke queue 1 ( quantum= 16 ms).
3.
Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue
0, dan jika suatu proses di queue 1 tidak selesai dalam 16 ms, maka
proses tersebut akan dipindahkan ke queue 2.
4.
Queue 2 akan dikerjakan bila queue 0 dan 1 kosong, dan akan
berjalan dengan algoritma FCFS.
Disini terlihat bahwa ada
kemungkinan terjadinya perpindahan proses antar queue, dalam hal ini
ditentukan oleh time quantum, namun dalam prakteknya penerapan algoritma
multilevel feedback queue akan diterapkan dengan mendefinisikan terlebih
dahulu parameter-parameternya, yaitu:
1.
Jumlah antrian.
2.
Algoritma internal tiap queue.
3.
Aturan sebuah proses naik ke antrian
yang lebih tinggi.
4.
Aturan sebuah proses turun ke
antrian yang lebih rendah.
5.
Antrian yang akan dimasuki tiap
proses yang baru datang.
Contoh: Terdapat tiga antrian; Q1=10
ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika
dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam
40 ms tidak selesai, maka dipindahkan lagi ke Q3. Berdasarkan hal-hal di atas
maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai
dengan kebutuhan sistem. Pada zaman sekarang ini algoritma multilevel
feedback queue adalah salah satu yang paling banyak digunakan.
STRATEGI
DASAR PENJADWALAN
Strategi
penjadwalan proses secara umum dibedakan menjadi dua kelompok besar, yaitu
penjadwalan non-preemptive dan preemptive.
1.
Non-preemptive
(run-to-completion)
Pada
strategi ini, begitu proses telah berjalan maka sistem operasi maupun proses
lain tidak dapat mengmabil alih eksekusi prosesor. Pengalihan hanya dapat
terjadi jika proses yang running sudah selesai, baik secara normal maupun
abnormal. Strategi ini membahayakan sistem dan proses lain, sebab jika proses
yang sedang berjalan mengalami kegagalan, crash ataupun looping tak berhingga
maka sistem operasi menjadi tidak berfungsi dan proses lain tidak mendapatkan
kesempatan untuk dieksekusi. Strategi penjadwalan non-preemptive umumnya
digunakan pada sistem batch atau sekuensial.
2.
Preemptive
Pada
strategi ini, sistem operasi dan proses lain dapat mengambil alih eksekusi
prosesor tanpa harus menunggu proses yang sedang running menyelesaikan
tugasnya. Penjadwalan preemptive merupakan fitur yang penting, terutama pada
sistem dimana proses-proses memerlukan tanggapan prosesor secara cepat. Sebagai
contoh adalah sistem real-time, dimana jika terjadi interupsi dan tidak segera
dilayani maka dapat berakibat fatal. Contoh lain adalah sistem interaktif
time-sharing, dimana pengguna sistem mengharapkan tanggapan yang cepat dari
sistem. Secara umum, sistem konkuren seperti sistem operasi yang multitasking
lebih menghendaki sistem penjadwalan preemptive.
Penjadwalan Preemptive
1.
Berubah dari running ke waiting state.
2.
Berubah dari running ke ready state.
3.
Berubah dari waiting ke ready state.
4.
Dihentikan.
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 M/K. 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. Membuat penjadwalan yang Preemptive mempunyai keuntungan yaitu sistem lebih responsif
daripada sistem yang memakai penjadwalan Non Preemptive.
Dalam waktu-waktu tertentu, proses dapat dikelompokkan
ke dalam dua kategori: proses yang memiliki Burst M/K yang sangat lama
disebut I/O Bound, dan proses yang memiliki Burst CPU yang sangat lama disebutCPU 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.
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 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). Windows
95, Windows XP, Linux, Unix, AmigaOS, MacOS X, dan Windows NT adalah beberapa contoh sistem operasi yang menerapkan
penjadwalan Preemptive.
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.
Penjadwalan Non Preemptive
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 menginterupt pada metode
penjadwalan Preemptive).
Dispatcher
Komponen
penjadwalan proses lainnya adalah dispatcher. Dispatcher adalah suatu rutin
sistem operasi yang berfungsi untuk melakukan pengalihan eksekusi dari proses
yang running ke proses yang terseleksi oleh short-term scheduler. Rutin ini
memindahkan isi register prosesor, konteks prosesor, ke PCB proses yang
dihentikan, kemudian mengubah statusnya menjadi ready, kemudian menginisiasi
isi register prosesor menggunakan konteks prosesor yang tersimpan dalam PCB proses
terpilih. Durasi waktu yang diperlukan untuk melakukan pengalihan (switching)
disebut dengan dispatch latency.
ALGORITMA PENJADWALAN PROCESSOR
Penjadwalan
berkaitan dengan permasalahan memutuskan proses mana yang akan dilaksanakan
dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan
mengantri di ready
queue.
Algoritma
penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan
dieksekusi oleh CPU.
Algoritma
ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU.
Dengan menggunakan algoritma ini setiap proses yang berada pada status ready
dimasukkan kedalam FIFO queue atau antrian dengan prinsip first in
first out, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih
dahulu yang akan dieksekusi.
Contoh: Ada
tiga buah proses yang datang secara bersamaan yaitu pada 0 ms, P1 memiliki
burst time 24 ms, P2 memiliki burst time 3 ms, dan P3 memiliki burst time 3 ms.
Hitunglah waiting time rata-rata dan turnaround time( burst
time + waiting time) dari ketiga proses tersebut dengan menggunakan
algoritma FCFS. Waiting time untuk P1 adalah 0 ms (P1 tidak perlu
menunggu), sedangkan untuk P2 adalah sebesar 24 ms (menunggu P1 selesai), dan
untuk P3 sebesar 27 ms (menunggu P1 dan P2 selesai).
Urutan kedatangan adalah P1, P2 ,
P3; gantt chart untuk urutan ini adalah:
Waiting time rata-ratanya adalah sebesar(0+24+27)/3 = 17ms. Turnaround
time untuk P1 sebesar 24 ms, sedangkan untuk P2 sebesar 27 ms (dihitung
dari awal kedatangan P2 hingga selesai dieksekusi), untuk P3 sebesar 30 ms. Turnaround
time rata-rata untuk ketiga proses tersebut adalah (24+27+30)/3 = 27 ms.
Kelemahan dari algoritma ini:
1.
Waiting
time rata-ratanya cukup lama.
2.
Terjadinya convoy effect,
yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang
dieksekusi oleh CPU. Algoritma ini juga menerapkan konsep non-preemptive, yaitu
setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh
proses yang lain.
Misalkan proses dibalik sehingga
urutan kedatangan adalah P3, P2, P1. Waiting time adalah P1=6; P2=3;
P3=0. Average waiting time: (6+3+0)/3=3.
SJF (Shortest Job First)
Pada algoritma ini setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.
Burst
time:asumsi berapa lama sebuah proses membutuhkan CPU diantara proses menunggunya
I/O. Hal ini tidak dapat diprediksi secara tepat sebelum dimulainya sebuah
proses. Artinya jumlah waktu yang dibutuhkan sebuah proses dalam menggunakan
CPU dalam sebuah satuan waktu. (Sebuah proses dapat menggunakan CPU selama
beberapa kali selama task yang diberikan belum
diselesaikan.
Process
|
Arrival Time
|
Burst Time
|
P1
|
0.0
|
7
|
P2
|
2.0
|
4
|
P3
|
4.0
|
1
|
P4
|
5.0
|
4
|
Contoh: Ada 4 buah proses yang
datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst
time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time
4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4
dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting
time rata-rata dan turnaround time dari keempat proses tersebut
dengan mengunakan algoritma SJF.
Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0
+6+3+7)/4=4 ms.
Average waiting time rata-rata untuk
ketiga prses tersebut adalah sebesar (9+1+0+2)/4=3 ms.
Ada beberapa kekurangan dari algoritma ini yaitu:
1.
Susahnya untuk memprediksi burst time proses yang akan
dieksekusi selanjutnya.
2.
Proses yang mempunyai burst time yang besar
akan memiliki waiting time yang besar pula karena yang dieksekusi
terlebih dahulu adalah proses dengan burst time yang lebih kecil.
Algoritma ini dapat dibagi menjadi dua bagian yaitu
:
1.
Preemptive . Jika ada proses yang sedang
dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang
lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang
sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready
queue tersebut. Preemptive SJF sering disebut juga
Shortest-Remaining- Time-First scheduling.
2.
Non-preemptive . CPU tidak memperbolehkan
proses yang ada di ready queue untuk menggeser proses yang sedang
dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time
yang lebih kecil.
Priority Scheduling
Priority
Scheduling merupakan algoritma penjadwalan
yang mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses
memiliki prioritasnya masing-masing.
Prioritas suatu proses dapat
ditentukan melalui beberapa karakteristik antara lain:
1.
Time limit.
2.
Memory
requirement.
3.
Akses file.
4.
Perbandingan antara burst M/K
dengan CPU burst.
5.
Tingkat kepentingan proses.
Priority scheduling juga dapat dijalankan secara preemptive maupun non-preemptive.
Pada preemptive, jika ada suatu proses yang baru datang memiliki
prioritas yang lebih tinggi daripada proses yang sedang dijalankan, maka proses
yang sedang berjalan tersebut dihentikan, lalu CPU dialihkan untuk proses yang
baru datang tersebut. Sementara itu, pada non-preemptive, proses yang
baru datang tidak dapat menganggu proses yang sedang berjalan, tetapi hanya
diletakkan di depan queue.
Kelemahan pada priority scheduling
adalah dapat terjadinya indefinite blocking( starvation). Suatu
proses dengan prioritas yang rendah memiliki kemungkinan untuk tidak dieksekusi
jika terdapat proses lain yang memiliki prioritas lebih tinggi darinya.
Solusi dari permasalahan ini adalah aging,
yaitu meningkatkan prioritas dari setiap proses yang menunggu dalam queue
secara bertahap.
Contoh: Setiap 10 menit, prioritas
dari masing-masing proses yang menunggu dalam queue dinaikkan satu
tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21
jam 20 menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang
tertinggi (semakin kecil angka menunjukkan bahwa prioritasnya semakin tinggi).
Round Robin
Algoritma ini menggilir proses yang
ada di antrian. Proses akan mendapat jatah sebesar time quantum. Jika time
quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke
proses berikutnya. Tentu proses ini cukup adil karena tak ada proses yang
diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU yaitu
(1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.
Algoritma ini sepenuhnya bergantung
besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja
dengan algoritma first come first served. Jika terlalu kecil, akan
semakin banyak peralihan proses sehingga banyak waktu terbuang.
Permasalahan utama pada Round
Robin adalah menentukan besarnya time quantum. Jika time quantum
yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai
dalam 1 quantum. Hal ini tidak baik karena akan terjadi banyak switch,
padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain
(disebut dengan context switches time). Sebaliknya, jika time quantum terlalu
besar, algoritma Round Robin akan berjalan seperti algoritma first
come first served. Time quantum yang ideal adalah jika 80% dari
total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.
|
|
Multilevel Queue
Ide dasar dari algoritma ini
berdasarkan pada sistem prioritas proses. Prinsipnya, jika setiap proses dapat
dikelompokkan berdasarkan prioritasnya, maka akan didapati queue
seperti pada gambar berikut:
Dari gambar tersebut terlihat bahwa akan terjadi
pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul ide untuk
menganggap kelompok-kelompok tersbut sebagai sebuah antrian-antrian kecil yang
merupakan bagian dari antrian keseluruhan proses, yang sering disebut dengan algoritma
multilevel queue.
Dalam hal ini, dapat dilihat bahwa seolah-olah
algoritma dengan prioritas yang dasar adalah algoritma multilevel queue
dimana setiap queue akan berjalan dengan algoritma FCFS yang memiliki
banyak kelemahan. Oleh karena itu, dalam prakteknya, algoritma multilevel
queue memungkinkan adanya penerapan algoritma internal dalam masing-masing
sub-antriannya yang bisa memiliki algoritma internal yang berbeda untuk
meningkatkan kinerjanya.
Berawal dari priority scheduling,
algoritma ini pun memiliki kelemahan yang sama dengan priority scheduling,
yaitu sangat mungkin bahwa suatu proses pada queue dengan prioritas rendah bisa
saja tidak mendapat jatah CPU. Untuk mengatasi hal tersebut, salah satu caranya
adalah dengan memodifikasi algoritma ini dengan adanya jatah waktu maksimal
untuk tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu,
maka prosesnya akan dihentikan dan digantikan oleh antrian dibawahnya, dan
tentu saja batas waktu untuk tiap antrian bisa saja sangat berbeda tergantung
pada prioritas masing-masing antrian.
Multilevel Feedback Queue
Algoritma ini mirip sekali
dengan algoritma multilevel queue. Perbedaannya ialah algoritma ini
mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu
lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Hal ini
menguntungkan proses interaksi karena proses ini hanya memakai waktu CPU yang
sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini
akan dinaikkan tingkatannya. Biasanya prioritas tertinggi diberikan kepada
proses dengan CPU burst terkecil, dengan begitu CPU akan terutilisasi
penuh dan M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst
proses juga semakin besar.
Gambar 14.7. Multilevel Feedback Queue
Algoritma ini didefinisikan melalui
beberapa parameter, antara lain:
a.
Jumlah antrian.
b.
Algoritma penjadwalan tiap antrian.
c.
Kapan menaikkan proses ke antrian
yang lebih tinggi.
d.
Kapan menurunkan proses ke antrian
yang lebih rendah.
e.
Antrian mana yang akan dimasuki
proses yang membutuhkan.
Dengan pendefinisian seperti tadi
membuat algoritma ini sering dipakai, karena algoritma ini mudah dikonfigurasi
ulang supaya cocok dengan sistem. Tapi untuk mengatahui mana penjadwal terbaik,
kita harus mengetahui nilai parameter tersebut.
Multilevel feedback queue adalah salah satu algoritma yang berdasar pada algoritma multilevel
queue. Perbedaan mendasar yang membedakan multilevel feedback queue
dengan multilevel queue biasa adalah terletak pada adanya kemungkinan
suatu proses berpindah dari satu antrian ke antrian lainnya, entah dengan
prioritas yang lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut.
1.
Semua proses yang baru datang akan
diletakkan pada queue 0 ( quantum= 8 ms).
2.
Jika suatu proses tidak dapat
diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan
ke queue 1 ( quantum= 16 ms).
3.
Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue
0, dan jika suatu proses di queue 1 tidak selesai dalam 16 ms, maka
proses tersebut akan dipindahkan ke queue 2.
4.
Queue 2 akan dikerjakan bila queue 0 dan 1 kosong, dan akan
berjalan dengan algoritma FCFS.
Disini terlihat bahwa ada
kemungkinan terjadinya perpindahan proses antar queue, dalam hal ini
ditentukan oleh time quantum, namun dalam prakteknya penerapan algoritma
multilevel feedback queue akan diterapkan dengan mendefinisikan terlebih
dahulu parameter-parameternya, yaitu:
1.
Jumlah antrian.
2.
Algoritma internal tiap queue.
3.
Aturan sebuah proses naik ke antrian
yang lebih tinggi.
4.
Aturan sebuah proses turun ke
antrian yang lebih rendah.
5.
Antrian yang akan dimasuki tiap
proses yang baru datang.
Contoh: Terdapat tiga antrian; Q1=10
ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika
dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam
40 ms tidak selesai, maka dipindahkan lagi ke Q3. Berdasarkan hal-hal di atas
maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai
dengan kebutuhan sistem. Pada zaman sekarang ini algoritma multilevel
feedback queue adalah salah satu yang paling banyak digunakan.
STRATEGI
DASAR PENJADWALAN
Strategi
penjadwalan proses secara umum dibedakan menjadi dua kelompok besar, yaitu
penjadwalan non-preemptive dan preemptive.
1.
Non-preemptive
(run-to-completion)
Pada
strategi ini, begitu proses telah berjalan maka sistem operasi maupun proses
lain tidak dapat mengmabil alih eksekusi prosesor. Pengalihan hanya dapat
terjadi jika proses yang running sudah selesai, baik secara normal maupun
abnormal. Strategi ini membahayakan sistem dan proses lain, sebab jika proses
yang sedang berjalan mengalami kegagalan, crash ataupun looping tak berhingga
maka sistem operasi menjadi tidak berfungsi dan proses lain tidak mendapatkan
kesempatan untuk dieksekusi. Strategi penjadwalan non-preemptive umumnya
digunakan pada sistem batch atau sekuensial.
2.
Preemptive
Pada
strategi ini, sistem operasi dan proses lain dapat mengambil alih eksekusi
prosesor tanpa harus menunggu proses yang sedang running menyelesaikan
tugasnya. Penjadwalan preemptive merupakan fitur yang penting, terutama pada
sistem dimana proses-proses memerlukan tanggapan prosesor secara cepat. Sebagai
contoh adalah sistem real-time, dimana jika terjadi interupsi dan tidak segera
dilayani maka dapat berakibat fatal. Contoh lain adalah sistem interaktif
time-sharing, dimana pengguna sistem mengharapkan tanggapan yang cepat dari
sistem. Secara umum, sistem konkuren seperti sistem operasi yang multitasking
lebih menghendaki sistem penjadwalan preemptive.
Penjadwalan Preemptive
1.
Berubah dari running ke waiting state.
2.
Berubah dari running ke ready state.
3.
Berubah dari waiting ke ready state.
4.
Dihentikan.
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 M/K. 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. Membuat penjadwalan yang Preemptive mempunyai keuntungan yaitu sistem lebih responsif
daripada sistem yang memakai penjadwalan Non Preemptive.
Dalam waktu-waktu tertentu, proses dapat dikelompokkan
ke dalam dua kategori: proses yang memiliki Burst M/K yang sangat lama
disebut I/O Bound, dan proses yang memiliki Burst CPU yang sangat lama disebutCPU 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.
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 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). Windows
95, Windows XP, Linux, Unix, AmigaOS, MacOS X, dan Windows NT adalah beberapa contoh sistem operasi yang menerapkan
penjadwalan Preemptive.
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.
Penjadwalan Non Preemptive
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 menginterupt pada metode
penjadwalan Preemptive).
Dispatcher
Komponen
penjadwalan proses lainnya adalah dispatcher. Dispatcher adalah suatu rutin
sistem operasi yang berfungsi untuk melakukan pengalihan eksekusi dari proses
yang running ke proses yang terseleksi oleh short-term scheduler. Rutin ini
memindahkan isi register prosesor, konteks prosesor, ke PCB proses yang
dihentikan, kemudian mengubah statusnya menjadi ready, kemudian menginisiasi
isi register prosesor menggunakan konteks prosesor yang tersimpan dalam PCB proses
terpilih. Durasi waktu yang diperlukan untuk melakukan pengalihan (switching)
disebut dengan dispatch latency.
Langganan:
Postingan (Atom)