Penjadwalan CPU dengan FCFS


1.      Penjadwalan CPU dengan FCFS
1.1  Dasar Teori
Penjadwalan CPU adalah permasalahan menentukan proses mana pada ready queue yang dialokasikan ke CPU. Pada saat CPU menganggur, maka sistem operasi harus menyeleksi prosesproses 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). Keputusan untuk menjadwalkan CPU mengikuti empat keadaan dibawah ini :
1. Apabila proses berpindah dari keadaan running ke waiting;
2. Apabila proses berpindah dari keadaan running ke ready;
3. Apabila proses berpindah dari keadaan waiting ke ready;
4. Apabila proses berhenti.
Setiap algoritma diukur “turnaround time” dan “waiting time” untuk membandingkan performansi dengan algoritma lain. Dan untuk mengukur turnaround time dan waiting time, digunakan “Gant Chart”. CPU time (Burst Time) membutuhkan semua proses diasumsikan diketahui. Arrival time untuk setiap proses pada ready queue diasumsikan diketahui.
1.2  Algoritma
First-Come First-Served Scheduling (FCFS) adalah Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu. Pada skema ini, proses yang meminta CPU pertama kali akan dialokasikan ke CPU pertama kali.  Misalnya terdapat tiga proses yang dapat dengan urutan P1, P2, dan P3 dengan waktu CPU-burst dalam milidetik yang diberikan sebagai berikut :
Proses              Burst Time
P1                           24
P2                           3
P3                           3
Gant Chart dengan penjadwalan  FCFS sebagai berikut :
P1           P2           P3
                               
0              24               27                    30
Waktu tunggu untuk P1 adalah 0, P2 adalah 24 dan P3 adalah 27 sehingga rata-rata
waktu tunggu adalah (0 + 24 + 27)/3 = 17 milidetik. Sedangkan apabila proses datang dengan urutan P2, P3, dan P1, hasil penjadwalan CPU dapat dilihat pada gant chart berikut :
P2           P3           P1
                               
0               3                 6                    30
Waktu tunggu sekarang untuk P1 adalah 6, P2 adalah 0 dan P3 adalah 3 sehingga rata-rata waktu tunggu adalah (6 + 0 + 3)/3 = 3 milidetik. Rata-rata waktu tunggu kasus ini jauh lebih baik dibandingkan dengan kasus sebelumnya. Pada penjadwalan CPU dimungkinkan terjadi Convoy effect apabila proses yang pendek berada pada proses yang panjang.
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.
1.3  Listing/source code  Program C++ yang sudah benar
#include<stdio.h>#include<string.h>main()
{
int n, ar[100], b[100], i, j, tmp, wt[100], ta[100], time[100];
int totWT=0, totTA=0;
float AvWT, AvTA;
char name[20][20], tmpName[20];
printf(“\t.:: Program Penjadwalan CPU FCFS ::.\n”);
puts(“”);
printf(“Banyak Proses\t= “); scanf(“%d”, &n);
puts(“”);
// Masukkan data yang diproses
for(i=0; i<n; i++){
fflush(stdin);
printf(“Nama Proses\t= “); gets(name[i]);
printf(“Arrival time\t= “); scanf(“%d”, &ar[i]);
printf(“Burst time\t= “); scanf(“%d”, &b[i]);
puts(“”);
}
// SORTING Data
for(i=0; i<n; i++){
for(j=i+1; j<n; j++)
if(ar[i]>ar[j]){
//tukar nama
strcpy(tmpName, name[i]);
strcpy(name[i], name[j]);
strcpy(name[j], tmpName);
//tukar arrival time
tmp=ar[i];
ar[i]=ar[j];
ar[j]=tmp;
//tukar burst
tmp=b[i];
b[i]=b[j];
b[j]=tmp;
}
}
time[0]=ar[0];
puts(“\n\t.:: Process Table ::.”);
puts(“==========================================”);
printf(“| no | proses\t | time arrival\t | burst |\n”);
puts(“——————————————”);
for (i=0; i<n; i++){
printf(“| %2d | %s\t |  \t%d\t | %d\t |\n”, i+1, name[i], ar[i], b[i]);
time[i+1]=time[i]+b[i]; //menghitung time pada ganchart
wt[i]=time[i]-ar[i];
ta[i]=time[i+1]-ar[i];
totWT+=wt[i];
totTA+=ta[i];
}
puts(“==========================================”);
printf(“\tTotal waiting time\t= %d \n”, totWT);
printf(“\tTurn arround time\t= %d \n”, totTA);
puts(“\n\t.:: Time Process Table ::.”);
puts(“==================================================”);
printf(“| no | proses\t | waiting time\t | turn arround\t |\n”);
puts(“————————————————–”);
for(i=0; i<n; i++){
printf(“| %2d | %s\t |  \t%d\t | \t%d\t |\n”, i+1, name[i], wt[i], ta[i]);
}
puts(“==================================================”);
//untuk Gant Chart
puts(“\n”);
puts(“\t.:: Gant-Chart ::.\n”);
for(i=0; i<n; i++){
printf(” %s\t “, name[i]);
}
puts(“”);
for(i=0; i<n; i++){
printf(“|=========”);
}
printf(“|\n”);
for(i=0; i<=n; i++){
printf(” %d\t “, time[i]);
} printf(“//diperoleh dari penjumlahan Burst”);
puts(“\n”);
AvWT=(float)totWT/n; //average waiting time
AvTA=(float)totTA/n; //average turn arround time
printf(“\tAverage Waiting Time : %f\n”, AvWT);
printf(“\tAverage Turn Arround TIme : %f\n”, AvTA);
}
1.4  Hasil Output


Penjadwalan CPU FCFS dengan bahasa pemrograman C++
1.2  Analisa
Pertama masukkan banyak proses kemudia inputan ini di looping sebanyak inputan tadi, didalam proses looping terdapat inputan yaitu nama proses, arrival dan burst yang menggunakan array.
             Untuk mengetahui nilai dari waiting time maka nilai dari arrival time dikurangi dengan nilai burst yang sudah dijumlah kan, seperti pada Gant Chart nya.
             Untuk mencari nilai rata-rata waktu tunggu maka nilai waiting time dijumlahkan semua kemudian di bagi dengan jumlah waiting time tersebut.
             Untuk mencari rata-rata time around maka nilai dari burst dijumlahkan kemudian di bagi dengan jumlah burst tadi.
1.3  Kesimpulan
Program ini merupakan program penjadwalan cpu dengan FCFS maksud nya proses yang pertama kali memintah jatah waktu maka akan di kerjakan terlebih dahulu baru proses berikutnya, dengan menggunakan penjadwalan cpu fcfs ini terdapat kekurangan nya yaitu :
             Waktu tunggu rata-rata cukup lama
             Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU
             Di penjadwalan cpu fcfs ini menerapkan konsep non-preemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh proses yang lain.

AJAR HERDITAMA                            1010 511 095 (Kelas B)
DWI PRASETYO ISWORO               1010 511 120 (Kelas B)
MUHAMMAD RIDWAN                   1010 511 103 (Kelas C)
MUHAMMAD FAJAR KAMALI       1010 511 126 (Kelas C)
TAUFAN FIRMANSYAH                  1010 511 102 (Kelas C)