Kamis, 14 Mei 2015
Download disini
Source code penjadwalan CPU dengan sjf (shortest job first)
1. Penjadwalan CPU
Penjadwalan CPU adalah pemilihan proses dari antrian ready untuk dapat dieksekusi. Penjadwalan CPU merupakan konsep dari multiprogramming, dimana CPU digunakan secara bergantian untuk proses yang berbeda. Suatu proses terdiri dari dua siklus yaitu Burst I/O dan Burst CPU yang dilakukan bergantian hingga proses selesai. Penjadwalan CPU mungkin dijalankan ketika proses:
1. running ke waiting time
2. running ke ready state
3. waiting ke ready state
4. terminates
1. Penjadwalan CPU
Penjadwalan CPU adalah pemilihan proses dari antrian ready untuk dapat dieksekusi. Penjadwalan CPU merupakan konsep dari multiprogramming, dimana CPU digunakan secara bergantian untuk proses yang berbeda. Suatu proses terdiri dari dua siklus yaitu Burst I/O dan Burst CPU yang dilakukan bergantian hingga proses selesai. Penjadwalan CPU mungkin dijalankan ketika proses:
1. running ke waiting time
2. running ke ready state
3. waiting ke ready state
4. terminates
Proses
1 dan 4 adalah proses Non Preemptive, dimana proses tersebut tidak bisa
di- interrupt, sedangkan 2 dan 3 adalah proses Preemptive, dimana
proses boleh di interrupt.
Pada saat CPU menganggur, maka sistem operasi harus menyeleksi proses-proses yang ada di memori utama (ready queue) untuk dieksekusi dan mengalokasikan CPU untuk salah satu dari proses tersebut. Seleksi semacam ini disebut dengan shortterm scheduler (CPU scheduler).
Komponen yang lain dalam penjadwalan CPU adalah dispatcher, Dispatcher adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penyeleksian proses yang dilakukan selama short-term scheduling . Waktu yang diperlukan oleh dispatcher untuk menghentikan suatu proses dan memulai proses yang lain disebut dengan dispatch latency.
Jika dalam suatu proses Burst CPU jauh lebih besar daripada Burst I/O maka disebut CPU Bound. Demikian juga sebaliknya disebut dengn I/O Bound.
Pada saat CPU menganggur, maka sistem operasi harus menyeleksi proses-proses yang ada di memori utama (ready queue) untuk dieksekusi dan mengalokasikan CPU untuk salah satu dari proses tersebut. Seleksi semacam ini disebut dengan shortterm scheduler (CPU scheduler).
Komponen yang lain dalam penjadwalan CPU adalah dispatcher, Dispatcher adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penyeleksian proses yang dilakukan selama short-term scheduling . Waktu yang diperlukan oleh dispatcher untuk menghentikan suatu proses dan memulai proses yang lain disebut dengan dispatch latency.
Jika dalam suatu proses Burst CPU jauh lebih besar daripada Burst I/O maka disebut CPU Bound. Demikian juga sebaliknya disebut dengn I/O Bound.
2. Penjadwalan CPU dengan sjf (shortest job first)
Dalam Sistem Operasi dikenal istilah multiprograming, yang bertujuan untuk memaksimalkan penggunaan CPU dengan cara mengatur alokasi waktu yang digunakan oleh CPU,sehingga proses berjalan sepanjang waktu dan memperkecil waktu idle. Oleh karena itu perlu adanyapenjadwalan proses-proses yang ada pada sistem. Untuk sistem yang hanya mempunyai prosesortunggal (uniprosesor), hanya ada satu proses yang dapat berjalan setiap waktunya. Jika ada proseslebih dari satu maka proses yang lain harus menunggu sampai CPU bebas dan siap untuk dijadwalkankembali
Penjadwalan berkaitan dengan permasalahan memutuskan proses mana yang akandilaksanakan dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan mengantridi ready queue. Algoritma penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan dieksekusi oleh CPU. Bagian berikut ini akan memberikan ilustrasialgoritma penjadwalan Shortest Job First.
3. 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.
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 :
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.
