PENJADWALAN CPU: Juni 2012

A. 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 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). 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 read

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.

B. Kriteria Penjadwalan

· CPU utilization: tingkat penggunaan CPU

· Throughput: jumlah proses yang diselesaikan per satuan waktu

· Turnaround time: waktu tunggu sejak sebuah proses di-submit hingga

· selesai eksekusi

· Waiting time: total waktu sebuah proses berada dalam ready queue

· Response time: waktu tunggu sejak sebuah proses di-submit sampai

· respon pertama diperoleh

Memaksimalkan:

· CPU utilization

· throughput

Meminimalkan:

· turnaround time

· waiting time

· response time

Kelebihan dari proses FCFS adalah:

· Merupakan metode scheduling paling sederhana

· Overhead kecil

· Dapat mencegah starvation

Kekurangan :

· Proses yang pendek dapat dirugikan, bila urutan eksekusinya setelah proses yang panjang

C. 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.

D. Flowchart

Penjelasan:

Bedasarkan flowchart di atas proses 1 (p1) tiba atau arrive pertama, proses 2 (p2 ) tiba kedua dan proses 3 tiba ketiga, karena menggunakan algorima FCFS (first come first served ) atau algoritma yang memprioritaskan sistem arrive atau kedatangan suatu proses. Dalam flowchart di atas p1 tiba terlebih dahulu dibandingkan p2 dan p3, kemudian disusul oleh p2 kemudian p3. Maka p1 akan di eksekusi lebih awal di banding kedua proses lainnya. Dalam alur pemrogramannya p1 berada pada memory utama / RAM kemudian p1 di alihkan pada status ready yang artinya siap untuk di eksekusi. Semua proses baik p1, p2, dan p3 telah berada pada memory utama/RAM sebelum proses tersebut di eksekusi. Kemudian p1 di eksekusi bedasarkan burst time atau lamanya eksekusi proses, apabila proses tersebut selesai kemudian p1 berada pada status finish, namun apabila ada masalah interupt maka p1 di pindahkan ke status blocked dan status waiting, begitupun eksekusi proses p2 dan p3 selanjutnya.

E. Source code Program C++

#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(".::TUGAS KELOMPOK SISTEM OPERASI::.\n\n");

printf("\t.:: 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("======================================================================");

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("=========================================================================");

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

}

F. Hasil Output

Hasil output Penjadwalan CPU FCFS dengan bahasa pemrograman C++.

G. 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.

H. 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.

PENJADWALAN CPU

Jumat, 08 Juni 2012

Penjadwalan atau Scheduling CPU FCFS Program di C++