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) :

P1

P3

P2

P4

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.

 

Kode VIDEO