Sistem Operasi (Pertemuan 4)
Penjadwalan CPU
Pada saat suatu proses dieksekusi, terdapat banyak CPU burst yang pendek dan terdapat sedikit CPU burst yang panjang. Program yang I/O bound biasanya sangat pendek CPU burst nya, sedangkan program yang CPU bound kemungkinan CPU burst nya sangat lama.
Keputusan untuk menjadwalkan CPU mengikuti empat keadaan:
- Apabila proses berpindah dari keadaan running ke waiting
- Apabila proses berpindah dari keadaan running ke ready
- Apabila proses berpindah dari keadaan waiting ke ready
- Apabila proses berhenti.
Apabila model penjadwalan yang dipilih menggunakan keadaan 1 dan 4, maka penjadwakan semacam ini disebut non-preemptive (proses akan terus membawa CPU sampai selesai). Sebaliknya, apabila yang digunakan adalah keadaan 2 dan 3, maka disebut dengan preemptive (selalu melakukan perbaikan data ketika meninggalkan pekerjaan dan melakukan pekerjaan lain sehingga memerlukan biaya yang tinggi).
Di dalam penjadwalan CPU, juga terdapat istilah “Dispatcher”. Dispatcher adalah suatu modul yang akan memberikan kontrol pada CPU
terhadap penyeleksian proses yang dilakukan selama short-term scheduling dan berfungsi untuk switching context, switching ke user-mode, dan melompat ke lokasi tertentu pada user program untuk memulai program. Waktu yang diperlukan oleh dispatcher untuk menghentikan suatu proses dan memulai untuk menjalankan proses yang lainnya disebut dispatch latency.
Ada beberapa kriteria yang digunakan untuk melakukan pembandingan algoritma penjadwalan CPU, antara lain:
- CPU utilization: diharapkan agar CPU selalu dalam keadaan sibuk (berkisar antara 40-90%)
- Throughput: banyaknya proses yang selesai dikerjakan dalam satu satuan waktu
- Turnaround time: banyaknya waktu yang diperlukan untuk mengeksekusi proses, dari mulai menunggu untuk meminta tempat di memori utama, menunggu di ready queue, eksekusi oleh CPU, dan mengerjakan I/O.
- Waiting time. Waktu yang diperlukan oleh suatu proses untuk menunggu di ready queue. Waiting time tidak mempengaruhi eksekusi proses dan penggunaan I/O.
- Response time. Waktu yang dibutuhkan oleh suatu proses dari minta dilayani hingga ada respon pertama yang menanggapi permintaan tersebut.
- Fairness. Meyakinkan bahwa tiap-tiap proses akan mendapatkan pembagian waktu penggunaan CPU secara terbuka (fair).
Algoritma Penjadwalan
- First-Come First-Served Scheduling (FCFS): Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu. 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.
- Shortest Job First Scheduler (SJF): Proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu. Merupakan algoritma penjadwalan yang optimal dengan rata-rata waktu tunggu yang minimal. Terdapat dua skema:
- Non preemptive, bila CPU diberikan pada proses, maka tidak bisa ditunda sampai CPU burst selesai
- Preemptive, jika proses baru datang dengan panjang CPU burst lebih pendek dari sisa waktu proses yang saat itu sedang dieksekusi, proses ini ditunda dan diganti dengan proses baru. Skema ini disebut dengan Shortest-Remaining-Time-First (SRTF).
- Priority Scheduling: CPU dialokasikan untuk proses yang memiliki prioritas paling tinggi (nilai integer terkecil biasanya merupakan prioritas terbesar). Jika beberapa proses memiliki prioritas yang sama, maka akan digunakan algoritma FCFS.
- Round-Robin Scheduling: Konsep dasar dari algoritma ini adalah dengan menggunakan time-sharing. Pada dasarnya algoritma ini sama dengan FCFS, hanya saja bersifat preemptive. Setiap proses mendapatkan waktu CPU yang disebut dengan waktu quantum (quantum time) yang biasanya antara 1-100 milidetik.
- Cara kerja: Jika suatu proses memiliki CPU burst lebih kecil dibandingkan dengan waktu quantum, maka proses tersebut akan melepaskan CPU jika telah selesai bekerja, sehingga CPU dapat segera digunakan oleh proses selanjutnya. Sebaliknya, jika suatu proses memiliki CPU burst yang lebih besar dibandingkan dengan waktu quantum, maka proses tersebut akan dihentikan sementara jika sudah mencapai waktu quantum,
dan selanjutnya mengantri kembali pada posisi ekor dari ready queue, CPU kemudian menjalankan proses berikutnya.
- Cara kerja: Jika suatu proses memiliki CPU burst lebih kecil dibandingkan dengan waktu quantum, maka proses tersebut akan melepaskan CPU jika telah selesai bekerja, sehingga CPU dapat segera digunakan oleh proses selanjutnya. Sebaliknya, jika suatu proses memiliki CPU burst yang lebih besar dibandingkan dengan waktu quantum, maka proses tersebut akan dihentikan sementara jika sudah mencapai waktu quantum,
===================================================================
Contoh soal:
Contoh coding FCFS:
#include<stdio.h>int main(){ int bt[10],at[10],wait_Time_Sum=0,turn_Time_Sum=0; int time=0,n,i,smallest,count=0; printf("Enter no of processes : "); scanf("%d",&n); for(i=0;i<n;i++) { printf("Enter arrival time for process P%d : ",i+1); scanf("%d",&at[i]); printf("Enter burst time for process P%d : ",i+1); scanf("%d",&bt[i]); } printf("\n\nProcess\t|Turnaround Time| Waiting Time\n\n"); at[9]=9999; while(count!=n) //End the loop when n process finish { smallest=9; // Checking For index of Process with smallest Arrival Time for(i=0;i<n;i++) { if(at[i]<at[smallest] && bt[i]>0) { smallest=i; } } //Index of Smallest Arrival Time stored in `smallest` time+=bt[smallest]; //Incrementing Current Time wait_Time_Sum+=time-at[smallest]-bt[smallest]; turn_Time_Sum+=time-at[smallest]; printf("P[%d]\t|\t%d\t|\t%d\n",smallest+1,time-at[smallest],time-at[smallest]-bt[smallest]); bt[smallest]=0; //Making burst time of current Process 0 so that it won't run again count++; } printf("\n average waiting time = %f",wait_Time_Sum*1.0/n); printf("\n average turnaround time = %f\n",turn_Time_Sum*1.0/n); return 0;}