Penjadwalan
CPU menyangkut penentuan proses-proses yang ada dalam ready queue yang akan
dialokasikan kepada CPU. Terdapat beberapa algoritma penjadwalan CPU seperti di bawah ini :
1. First Come First Server (FCFS)
Pertama
datang, pertama dilayani (First In, First Out atau FIFO) tidak peduli apakah
burst time nya panjang atau pendek, sebuah proses yang sedang dikerjakan
diselesaikan terlebih dulu barulah proses berikutnya dilayani.
Penjadwalan
FCFS merupakan penjadwalan:
·
Penjadwalan
non-prevebtive (run-to-completion)
·
Penjadwalan
tidak berprioritas
Ketentuan
dari penjadwalan FCFS adalah:
·
Proses-proses
diberi jatah waktu pemroses, diurut dengan waktu kedatangannya.
·
Begitu
proses mendapat jatah waktu pemproses, proses dijalankan sampai proses tersebut
selesai, walaupun ada proses lain yang datang, proses tersebut berada dalam
antrian sistem atau disebut dengan ready queue.
Pada
dasarnya algoritma penjadwalan ini cukup adil dalam hal bahasa, karena proses
yang datang lebih dulu dikerjakan terlebih dahulu. Dari segi konsep sistem
operasi, penjadwalan model ini tidak adil karena proses-proses yang membutuhkan
waktu yang lama membuat proses-proses yang memiliki waktu proses yang lebih
pendek menunggu sampai proses yang lama tersebut selesai, sedangkan
proses-proses yang tidak penting membuat proses penting menunggu.
Penjadwalan
FCFS cocok digunakan untuk sistem batch yang sangat jarang melakukan interaksi
dengan user secara langsung, tapi tidak cocok digunakan untuk sistem interaktif
karena tidak memberi waktu tanggap yang bagus, begitu juga dengan waktu sistem
nyata.
Contoh
dari penjadwalan FCFS adalah:
Misalnya
proses-proses yang akan dikerjakan oleh CPU adalah sebagai berikut:
Pada
saat posisi P1 masuk pada waktu 0, maka P1 dijalankan sebanyak 12, dan P2 masuk
pada saat 2, P3 pada saat 3, P4 pada saat 5, dan P5 pada waktu 9. Pada posisi
12 P1 selesai dikerjakan, dan P2 akan dieksekusi karena P2 lebih dulu berasa di
dalam Ready Queue (RQ) karena pada contoh diatas menggunakan algoritma FCFS
(First Come Firs Server) dan begitulah seterusnya sampai semua proses selesai
dikerjakan. Setelah semua proses selesai dikerjakan maka dihitung waktu tunggu
setiap proses, maka akan ditemukan jumlah waktu tunggu rata-rata dari setiap
proses, seperti contoh di bawah ini:
Jadi
waktu tunggu setiap proses adalah:
Rata-rata
waktu tunggu untuk setiap proses adalah: Avg 65/5 = 13 satuan waktu.
Jika
urutan proses pada contoh diatas dibalikkan misal : P5, P4, P3, P2 , P1 dengan
waktu menganggur CPU (idle time) antar awaktu 1 dan 2 sehingga panjangnya waktu
yang dibutuhkan untuk menyelesaikan lima proses tersebut menjadi 29 atau
bertambah satu dari waktu yang dibutuhkan sebelumnya.
Algoritma
FCFS termasuk non-preemptive, karena sekali CPU dialokasikan pada suatu proses,
maka proses tersebut tetap akan memakai CPU sampai proses tersebut
melepaskannya, yaitu jika proses tersebut berhenti atau meminta I/O.
Penggunaan
algoritma FCFS yang lebih kompleks dengan menambahkan aktivitas input dan
output sebagai berikut:
2. Algoritma Penjadwalan Proses Shortest Job First (SJF)
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 haltersebut maka waiting time
rata-ratanya juga menjadi pendek, sehingga dapat dikatakan
bahwaalgoritma ini adalah algoritma yang optimal.
Contoh 1 :
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 arrivaltime 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
denganmengunakan algoritma SJF.
Gambar Shortest Job First (Non-Preemptive) :
0 7 8 12 16
Average waiting time rata-rata untuk ketiga porses tersebut adalah sebesar (9+1+0+2)/4=3 ms.
Contoh 2 :
Nama Proses
|
Waktu Tiba
|
Lama Eksekusi
|
A
|
0
|
10
|
B
|
0
|
5
|
C
|
0
|
7
|
D
|
0
|
1
|
E
|
0
|
3
|
Nama Proses
|
Waktu Tiba
|
Lama Eksekusi
|
Mulai Eksekusi
|
Selesai Eksekusi
|
Waktu Tunggu
|
TA
|
D
|
0
|
1
|
0
|
1
|
0
|
1
|
E
|
0
|
3
|
1
|
4
|
1
|
4
|
B
|
0
|
5
|
4
|
9
|
4
|
9
|
C
|
0
|
7
|
9
|
16
|
9
|
16
|
A
|
0
|
10
|
16
|
26
|
16
|
26
|
|
∑TA
|
56
|
Rata-Rata
|
56/5 = 11.2
|
Tampak
di sini bahwa SJF ini menyebabkan rata-rata lama tanggap semua proses
itu menjadi 11.2satuan waktu. Rata-rata ini akan lebih singkat jika
dibandingkan dengan rata-rata lama tanggap untuk penjadwalan FIFO.
Algoritma ini dapat dibagi menjadi dua bagian yaitu :
1. Preemptive
Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk
memberhentikan sementara proses yang sedang berjalan untuk memberi ruang
kepada prosesyang prioritasnya lebih tinggi.
Jika ada proses
yang sedang dieksekusi oleh CPU dan terdapat proses di ready queuedengan
burst time yang lebih kecil daripada proses yang sedang dieksekusi
tersebut, makaproses yang sedang dieksekusi oleh CPU akan digantikan
oleh proses yang berada di readyqueue tersebut.
Preemptive SJF sering disebut juga Shortest-Remaining- Time-Firstscheduling.2.
2. Non-preemptive
Penjadwalan
Non Preemptive ialah salah satu jenis penjadwalan dimana sistemoperasi
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 .CPU tidak memperbolehkan proses yang ada di ready
queue untuk menggeser prosesyang sedang dieksekusi oleh CPU meskipun
proses yang baru tersebut mempunyai burst time yang lebih kecil.
Program Penjadwalan Proses Menggunakan Shortest Job First Dengan C++
Berikut
ini adalah source code program penghitungan waiting time, turn around
time dan response time sistem penjadwalan proses menggunakan Shortest
Job First dengan C++.
Ini listing programnya :
#include
#include
void main()
{
int i,j,n,brust_time[10],start_time[10],end_time[10],wait_time[10],temp,tot;
float avg;
printf("Enter the No. of jobs:\n\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\n \n Enter %d process burst time:\n",i);
scanf("%d",&brust_time[i]);
}
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(brust_time[i]>brust_time[j])
{
temp=brust_time[i];
brust_time[i]=brust_time[j];
brust_time[j]=temp;
}
}
if(i==1)
{
start_time[1]=0;
end_time[1]=brust_time[1];
wait_time[1]=0;
}
else
{
start_time[i]=end_time[i-1];
end_time[i]=start_time[i]+brust_time[i];
wait_time[i]=start_time[i];
}
}
printf("\n\n BURST TIME \t STARTING TIME \t END TIME \t WAIT TIME\n");
printf("\n ********************************************************\n");
for(i=1;i<=n;i++)
{
printf("\n %5d %15d %15d %15d",brust_time[i],start_time[i],end_time[i],wait_time[i]);
}
printf("\n ********************************************************\n");
for(i=1,tot=0;i<=n;i++)
tot+=wait_time[i];
avg=(float)tot/n;
printf("\n\n\n AVERAGE WAITING TIME=%f",avg);
for(i=1,tot=0;i<=n;i++)
tot+=end_time[i];
avg=(float)tot/n;
printf("\n\n AVERAGE TURNAROUND TIME=%f",avg);
for(i=1,tot=0;i<=n;i++)
tot+=start_time[i];
avg=(float)tot/n;
printf("\n\n AVERAGE RESPONSE TIME=%f\n\n",avg);
getch();
}
Output :
4. Analisa
Berdasarkan program di atas dapat di simpulkan bahwa semua proses
telah masuk pada ready queque namun dalam algoritma SJF (shortest job
first) maka suatu proses akan di eksekusi berdasarkan burst time atau
lamanya eksekusi, dan kemudian proses yang time burst nya paling kecil
akan di utamakan di bandingkan dengan proses yang time burst nya besar.
5. Kesimpulan
Pada program penjadwalan sjf 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
haltersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga
dapat dikatakan bahwaalgoritma ini adalah algoritma yang optimal.
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.
3.
Priority
Scheduling.
- Tiap proses diberi skala prioritas, proses
yang mendapatkan prioritas tertinggi mendapat jatah waktu pemroses
- Prioritas dapat diberikan secara :
*
Prioritas
statis (static priorities)
*
Prioritas
dinamis (dynamic priorities)
- Jika beberapa proses memiliki prioritas
yang sama akan digunakan algoritma FCFS, prioritas meliputi :
* Waktu
* Memori yang dibutuhkan
* Banyaknya file yang dibuka
* Perbandingan antara rata-rata I/O Burst
dengan rata-rata CPU Burst
- Algoritma Priority Scheduling dapat
bersifat Preemptive atau Non Preemptive. Jika ada proses P1 yang datang pada saat P0 sedang
berjalan à akan dilihat prioritas P1, Jika prioritas
P1>P0, maka :
* Pada Non Preemptive, Algoritma tetap
akan menyelesaikan P0 sampai habis CPU burstnya dan meletakkan P1 pada posisi
head queue.
* Pada Preemptive, P0 akan dihentikan
dulu dan CPU ganti dialokasikan untuk P1.
Contoh Priority Scheduling
Keunggulan priority scheduling biasanya
memenuhi kebijaksanaan yang ingin mencapai maksimasi suatu kriteria diterapkan.
Algoritma Round Robin
Round robin merupakan salah satu algoritma penjadwalan yang paling
sederhana untuk proses dalam sistem operasi. Seperti umumnya istilah ini
digunakan, irisan waktu ditugaskan untuk setiap proses pada porsi yang
sama dan dalam urutan melingkar, menjalankan semua proses tanpa
prioritas (dikenal juga sebagai eksekutif siklik). Penjadwalan
round-robin itu sederhana, mudah diterapkan, dan bebas starvation.
Penjadwalan round-robin juga dapat diterapkan untuk masalah penjadwalan
lainnya, seperti penjadwalan paket data dalam jaringan komputer.
Algoritma round robin dirancang untuk sistem time sharing. Algoritma
ini mirip dengan penjadwalan FCFS (First Come First Served), namun
preemption ditambahkan untuk switch (peralihan proses) antara proses.
Antrian ready diperlakukan atau dianggap sebagai antrian sirkular. CPU
menglilingi antrian ready dan mengalokasikan masing-masing proses untuk
interval waktu tertentu sampai satu time slice /quantum.
Algoritma ini berjalan dengan menggilir proses yang ada pada antrian.
Setiap Proses akan mendapat jatah sebesar time quantum. Jika time
quantum-nya habis atau proses sudah selesai, CPU akan dialihkan ke
proses yang selanjutnya. 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.
Ketentuan
Ketentuan algoritma round robin adalah sebagai berikut:
1. Jika quantum dan proses belum selesai maka proses menjadi runnable dan pemroses dialihkan ke proses lain.
2. Jika quantum belum habis dan proses menunggu suatu kejadian
(selesainya operasi I/O), maka proses menjadi blocked dan pemroses
dialihkan ke proses lain.
3. Jika quantum belum habis tapi proses telah selesai, maka proses diakhiri dan pemroses dialihkan ke proses lain.
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. Algoritma penjadwalan ini dapat
diimplementasi sebagai berikut: – Mengelola senarai proses read
(runnable) sesuai urutan kedatangan. – Ambil proses yang berada di ujung
depan antrian menjadi running. – Bila quantum belum habis dan proses
selesai maka ambil proses di ujung depan antrian proses ready. – Jika
quantum habis dan proses belum selesai maka tempatkan proses running ke
ekor antrian proses ready dan ambil proses di ujung depan antrian proses
ready.
Bentuk Algoritma
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.
Urutan event dalam algoritma round robin
Penggunaan Waktu Quantum
Berikut adalah algoritma penjadwalan Round Robin secara Keseluruhan :
- Setiap proses mendapat jatah waktu CPU (time slice/quantum) tertentu Time slice/quantum umumnya ntara 10 – 100 milidetik.
1. Setelah time slice/quantum maka proses akan di-preempt dan dipindahkan ke antrian ready.
2. Proses ini adil dan sangat sederhana.
- Jika terdapat n proses di “antrian ready ” dan waktu quantum q (milidetik), maka:
1. Maka setiap proses akan mendapatkan 1/n dari waktu CPU.
2. Proses tidak akan menunggu lebih lama dari: (n-1)q time units.
