Penjadwalan CPU adalah Memilih dari proses-proses yang berada di memori (ready to execute) dan memberikan jatah CPU ke salah satu proses tersebut. Penjadwalan CPU mungkin akan dijalankan ketika proses:
- Berubah dari running ke waiting state.
- Berubah dari running ke ready state.
- Berubah dari waiting ke ready.
- Terminates.
Penjadwalan 1 dan 4 adalah non preemptive, maksudnya adalah setiap proses secara berkala memberikan CPU ke OS. Contoh: Penjadualan untuk switch dari running ke wait atau terminate. Selain itu bersifat preemptive yaitu OS dapat mengambil (secara interrupt) CPU dari satu proses setiap saat. Contoh: Penjadualan proses dari running ke ready.
Kriteria Penjadwalan
Algoritma penjadwalan CPU yang berbeda akan memiliki perbedaan properti. Sehingga untuk memilih algoritma ini harus dipertimbangkan dulu properti-properti algoritma tersebut. Ada beberapa kriteria yang digunakan untuk melakukan pembandingan algoritma penjadwalan CPU, antara lain:
- CPU utilization : Diharapkan agar CPU selalu dalam keadaan sibuk. Utilitas CPU dinyatakan dalam bentuk prosen yaitu 0-100%. Namun dalam kenyataannya hanya berkisar antara 40-90%.
- Throughput : Banyaknya proses yang selesai dikerjakan dalam satu satuan waktu (maksimalkan jumlah proses yang selesaidijalankan (per 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. minimalkan waktu selesai eksekusi suatu proses (sejak di submit sampai selesai).
- Waiting time : Waktu yang diperlukan oleh suatu proses untuk menunggu diready queue. Waiting time ini tidak mempengaruhi eksekusi proses dan penggunaan I/O.(Meminimalkan waktu tunggu proses (jumlah waktu yang dihabiskan menunggu di ready queue)).
- Response time : Waktu yang dibutuhkan oleh suatu proses dari minta dilayani hingga ada respon pertama yang menanggapi permintaan tersebut.(Meminimalkan waktu response darisistimterhadap user (interaktif, time-sharing system), sehingga interaksi dapat berlangsung dengan cepat).
- Fairness : Meyakinkan bahwa tiap-tiap proses akan mendapatkan pembagian waktu penggunaan CPU secara terbuka (fair).
Dispatcher
Dispatcher adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penyeleksian proses yang dilakukan selama short-term scheduling. Fungsi-fungsi yang terkandung di dalam-nya meliputi:
1. Switching context;
2. Switching ke user-mode;
3. 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. Karena dispatcher digunakan setiap berpindah proses,dispatcher harus secepat mungkin.
Penjadwalan CPU menyangkut penentuan proses-proses yang ada dalam ready queue yang akan dialokasikan pada CPU. Terdapat beberapa algoritma penjadwalan CPU seperti dijelaskan pada sub bab di bawah ini.
ü First Come-First Served
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. Rata-rata waktu tunggu(Average Waiting Time=AWT) cukup tinggi. Misalnya terdapat tiga proses yang dapat dengan urutan P1, P2, danP3 dengan waktu CPU-burst dalam milidetik yang diberikan sebagai berikut :
Process Burst Time
P1 24
P2 3
P3 3
Gant Chart dengan penjadwalan FCFS adalah sebagai berikut :
Waktu tunggu untuk P1 adalah 0, P2 adalah 24 danP3 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 :
Waktu tunggu sekarang untuk P1 adalah 6, P2adalah 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 terjadiConvoy 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.
ü Shortest Job
Pada penjadwalan SJF, proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu. Terdapat dua skema :
1. Non preemptive, bila CPU diberikan pada proses, maka tidak bisa ditunda sampai CPU burst selesai.
2. 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).
SJF adalah algoritma penjadwalan yang optimal dengan rata-rata waktu tunggu
yang minimal. Misalnya terdapat empat proses dengan panjang CPU burst dalam
milidetik.
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
Penjadwalan proses dengan algoritma SJF (non-preemptive) dapat dilihat pada gant chart berikut :
Waktu tunggu untuk P1 adalah 0, P2 adalah 26, P3adalah 3 dan P4 adalah 7 sehingga rata-rata waktu tunggu adalah (0 + 6 + 3 + 7)/4 = 4 milidetik. Sedangkan Penjadwalan proses dengan algoritma SRTF (preemptive) dapat dilihat pada gant chart berikut :
Waktu tunggu untuk P1 adalah 9, P2 adalah 1, P3adalah 0 dan P4 adalah 4 sehingga rata-rata waktu tunggu adalah (9 + 1 + 0 + 4)/4 = 3 milidetik.
Meskipun algoritma ini optimal, namun pada kenyataannya sulit untuk diimplementasikan karena sulit untuk mengetahui panjang CPU burst berikutnya. Namun nilai ini dapat diprediksi. CPU burst berikutnya biasanya diprediksi sebagai suatu rata-rata eksponensial yang ditentukan dariCPU burst sebelumnya atau “Exponential Average”.
dengan:
τ n+1 = panjang CPU burst yang diperkirakan
τ 0 = panjang CPU burst sebelumnya
τ n = panjang CPU burst yang ke-n (yang sedang berlangsung)
α = ukuran pembanding antara τ n+1 dengan τ n (0 sampai 1)
Grafik hasil prediksi CPU burst dapat dilihat pada Gambar dibawah:
Prediksi panjang CPU burst berikutnya
Sebagai contoh, jika α = 0,5, dan
CPU burst (τ n ) = 6 4 6 4 13 13 13 . . .
τ n = 10 8 6 6 5 9 11 12 . . .
Pada awalnya τ 0 = 6 dan τ n = 10, sehingga :
τ 2 = 0,5 * 6 + (1 - 0,5) * 10 = 8
Nilai yang dapat digunakan untuk mencari τ 3
τ 3 = 0,5 * 4 + (1 - 0,5) * 8 = 6
ü Priority
Algoritma SJF adalah suatu kasus khusus dari penjadwalan berprioritas. Tiaptiap proses dilengkapi dengan nomor prioritas (integer). 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. Penjadwalan berprioritas terdiri dari dua skema yaitu non preemptive dan preemptive. Jika ada proses P1 yang datang pada saat P0 sedang berjalan, maka akan dilihat prioritas P1. Seandainya prioritas P1 lebih besar dibanding dengan prioritas P0, maka pada non-preemptive, algoritma tetap akan menyelesaikan P0 sampai habis CPU burst-nya, dan meletakkan P1 pada posisi head queue. Sedangkan padapreemptive, P0 akan dihentikan dulu, dan CPU ganti dialokasikan untuk P1. Misalnya terdapat lima proses P1, P2, P3, P4 dan P5 yang datang secara berurutan dengan CPU burst dalam milidetik.
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
Penjadwalan proses dengan algoritma priority dapat dilihat pada gant chart berikut:
Waktu tunggu untuk P1 adalah 6, P2 adalah 0, P3 adalah 16,P4 adalah 18 dan P5 adalah 1 sehingga rata-rata waktu tunggu adalah (6 + 0 +16 + 18 + 1)/5 = 8.2 milidetik.
ü Round Robin
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) untuk membatasi waktu proses, biasanya 1-100 milidetik. Setelah waktu habis, proses ditunda dan ditambahkan pada ready queue. 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. Jika terdapat nproses pada ready queue dan waktu quantum q, maka setiap proses mendapatkan 1/n dari waktu CPU paling banyak qunit waktu pada sekali penjadwalan CPU. Tidak ada proses yang menunggu lebih dari (n-1)q unit waktu. Performansi algoritma round robin dapat dijelaskan sebagai berikut, jika q besar, maka yang digunakan adalah algoritma FIFO, tetapi jika q kecil maka sering terjadi context switch.
Misalkan ada 3 proses: P1, P2, dan P3 yang meminta pelayanan CPU dengan quantum-time sebesar 4 milidetik.
Process BurstTime
P1 24
P2 3
P3 3
Penjadwalan proses dengan algoritma round robin dapat dilihat pada gant chart berikut :
Waktu tunggu untuk P1 adalah 6, P2 adalah 4, danP3 adalah 7 sehingga rata-rata waktu tunggu adalah (6 + 4 + 7)/3 = 5.66 milidetik.Algoritma Round-Robin ini di satu sisi memiliki keuntungan, yaitu adanya keseragaman waktu. Namun di sisi lain, algoritma ini akan terlalu sering melakukan switching seperti yang terlihat pada Gambar dibawah. Semakin besar quantum-timenya maka switching yang terjadi akan semakin sedikit.
Menunjukkan waktu kuantum yang lebih kecil meningkatkan
context switch
Waktu turnaround juga tergantung ukuran waktu quantum. Seperti pada Gambar dibawah , rata-rata waktu turnaround tidak meningkat bila waktu quantum dinaikkan. Secara umum, rata-rata waktu turnaround dapat ditingkatkan jika banyak proses menyelesaikan CPU burst berikutnya sebagai satu waktu quantum. Sebagai contoh, terdapat tiga proses masing-masing 10 unit waktu dan waktu quantum 1 unit waktu, rata-rata waktu turnaround adalah 29. Jika waktu quantum 10, sebaliknya, rata-rata waktu turnaround turun menjadi 20.
Menunjukkan waktu turnaround berbeda pada waktu quantum
yang berbeda
· Multiprocessor
Tidak ada komentar:
Posting Komentar