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:
running ke waiting time
running ke ready state
waiting ke ready state
terminatesProses 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.
1. Penjadwalan Preemptive
Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. Penjadwalan ini bisa saja termasuk penjadwalan proses atau I/O. Penjadwalan Preemptive memungkinkan sistem untuk lebih bisa menjamin bahwa setiap proses mendapat sebuah slice waktu operasi. Dan juga membuat sistem lebih cepat merespon terhadap event dari luar (contohnya seperti ada data yang masuk) yang membutuhkan reaksi cepat dari satu atau beberapa proses. Membuat penjadwalan yang Preemptive mempunyai keuntungan yaitu sistem lebih responsif daripada sistem yang memakai penjadwalan Non Preemptive.
Dalam waktu-waktu tertentu, proses dapat dikelompokkan ke dalam dua kategori: proses yang memiliki Burst M/K yang sangat lama disebut I/O Bound, dan proses yang memiliki Burst CPU yang sangat lama disebut CPU Bound. Terkadang juga suatu sistem mengalami kondisi yang disebut busywait, yaitu saat dimana sistem menunggu request input(seperti disk, keyboard, atau jaringan). Saat busywait tersebut, proses tidak melakukan sesuatu yang produktif, tetapi tetap memakan resource dari CPU. Dengan penjadwalan Preemptive, hal tersebut dapat dihindari.
Dengan kata lain, penjadwalan Preemptive melibatkan mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem untuk menentukan proses mana yang akan dieksekusi selanjutnya.
Lama waktu suatu proses diizinkan untuk dieksekusi dalam penjadwalan Preemptive disebut time slice/quantum. Penjadwalan berjalan setiap satu satuan time slice untuk memilih proses mana yang akan berjalan selanjutnya. Bila time slice terlalu pendek maka penjadwal akan memakan terlalu banyak waktu proses, tetapi bila time slice terlau lama maka memungkinkan proses untuk tidak dapat merespon terhadap event dari luar secepat yang diharapkan.
2. Penjadwalan Non Preemptive
Penjadwalan Non Preemptive ialah salah satu jenis penjadwalan dimana sistem operasi 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.
Penjadwalan Non Preemptive terjadi ketika proses hanya:
1. Berjalan dari running state sampai waiting state.
2. Dihentikan.
Ini berarti CPU menjaga proses sampai proses itu pindah ke waiting state ataupun dihentikan (proses tidak diganggu). Metode ini digunakan oleh Microsoft Windows 3.1 dan Macintosh. Ini adalah metode yang dapat digunakan untuk platforms hardware tertentu, karena tidak memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk meng interupt pada metode penjadwalan Preemptive).
Algoritma Penjadwalan CPU
Penjadwalan CPU terkait dengan bagaimana proses dikelola . Banyak algoritma yang digunakan untuk penjadwalan proses. Beberapa algoritma yang digunakan antara lain :
1. First-Come First- Serve (FCFS)
Merupakan algoritma yang paling sederhana dalam penjadwalan proses. Proses yang melakukan request terhadap CPU akan diproses oleh CPU. Implementasinya dengan menggunakan algoritma First In First Out – FIFO. FCFS bersifat non-preemptive yaitu proses yang dikerjakan oleh CPU tidak dapat diinterupsi oleh proses yang lainnya.
Sebagai contoh :
Proses Burst
P1 10
P2 1
P3 2
P4 1
P5 5
Gant Chart :
Proses diasumsikan datang bersamaan dan masuk dalam antrian penggunaan CPU. Proses akan dikerjakan berdasarkan nomor urutan proses, sedangkan yang lainnya menunggu sampai proses diatasnya selesai dikerjakan.
Dari Gant Chart dapat diperoleh waktu tunggu proses dari CPU yang dapat diambil waktu rata-ratanya.
Waiting Time P1 = 0, Waiting Time P2 = 10, Waiting Time P3 = 11, Waiting Time P4 = 13, Waiting Time P5 = 14.
Avarage Waiting Time (AWT) = (WT P1 + WT P2 + WT P3 + WT P4 + WT P5)/5
Avarage Waiting Time (AWT) = (0 + 10 + 11 + 13 + 14)/5 = 9.6 ms
FCFS dapat juga bekerja dengan adanya prioritas terhadap proses, prioritas dengan nilai terkecil akan diberi status sebagai prioritas tinggi dan akan dikerjakan terlebih dahulu.
Proses Burst Prioritas
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Gant Chart :
Avarage Waiting Time (AWT) = (0 + 1 + 6 + 16 + 18)/4 = 8.2 ms
Masalah utama pada FCFS adalah adanya antrian dari proses yang menjadi panjang karena waiting time yang rata-rata panjang. Proses-proses yang telah berada dalam posisi ready akan tetapi CPU belum dapat memprosesnya. Hal ini yang disebut dengan starvation.
2. Shortest Job First (SJF)
Pendekatan SJF berbeda dengan FCFS, algoritma SJF tergantung dengan panjang proses yang ada pada queue. Ketika CPU akan melakukan proses, CPU akan memilik proses dengan CPU burst paling kecil. SJF dapat bekerja dengan mode preemptive maupun non-preemptive.
Non-preemptive
Proses Burst
P1 6
P2 8
P3 7
P4 3
Gant chat :Waiting Time P1 = 3
Waiting Time P2 = 16
Waiting Time P3 = 9
Waiting Time P4 = 0
Avarage Waiting Time = (3 + 16 + 9 + 0)/4 = 7 ms
b. Preemptive
SJF dengan waktu kedatangan (arrival time) berbeda.
Proses Arrival Burst
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Proses akan di-preemptive jika ada proses masuk, dah penjadwalan dilakukan ulang dengan membandingkan proses yang masuk dengna proses yang sedang dijalankan. Sebaga contoh pada tabel ketika P1 dijalankan dengna membutuhkan 8 ms, akan tetapi datang burst dari proses P2 dengan burst time 4 ms pada deti ke-1. Proses akan berhenti pada detik 1 kemudian membandingkan proses P1 dengan P2. Karena P2 < P1 maka proses P1 akan dikembalikan ke ready queue dengan P1 = 7 dan memproses P2. Demikian seterusnya.
Gant chart :
Waiting Time P1 = 0 + (10-1) = 9
Waiting Time P2 = 1-1 = 0
Waiting Time P3 = 17-2 = 15
Waiting Time P4 = 5-3 = 2
Average Waiting Time = (9 + 0 + 15 + 2 )/4 = 6.5 ms
3. Round Robin (RR)
Round Robin hampir mirip dengan FCFS akan tetapi terdapat proses perpindahan antar proses dimana satu proses melakukan interupsi terhadap proses yang lainnya atau disebut juga dengan preemptive. Proses preemptive dengan menggunakan time quantum atau time slice.
Sebagai contoh :
Proses Burst
P1 24
P2 3
P3 3
Dengan time slice sebesar 4 ms, penjadwalan yang terjadi adalah sebagai berikut:
P1 mendapatkan kesempatan pada 4 ms (time slice) pertama, karena P1 > time slice maka P1 hanya akan diproses selama time slice, sisa P1 sebesar P1 – time slice akan di preemptive-kan. Selanjutnya penjadwalan akan beralih ke P2, karena P2 < time slice maka P2 diproses hingga selesai, setelah itu penjadwalan beralih ke P3 dan seterusnya.
Waiting Time P1 = 0 + (10 – 4) = 6
Waiting Time P2 = 4
Waiting Time P3 = 7
Average Waiting Time = (6 + 4 + 7 )/3 = 5.66 ms
Pada algoritma RR, tidak ada proses yang dikerjakan dalam satu waktu lebih dari time slice yang disediakan. Jika terdapat n proses pada queue dengan time slice sebesar q, maka setiap proses akan mendapatkan waktu 1/n dengan masing-masing proses sebesar q .Setiap proses akan menunggu setidaknya sebanyak (n-1)x q untuk proses selanjutnya. Sebagai contoh terdapat 5 proses dengan time slice sebesar 20 ms maka masing-masing proses akan mendapatkan waktu sebanyak 20 ms setiap 100 ms.
Performance dari RR tergantung pada ukuran time slice. Jika time slice terlalu besar maka RR akan sama atau mendekati performance FCFS. Akan tetapi jika time slice kecil maka muncul problem context switch yang terlalu banyak, yaitu proses perpindahan dari satu proses ke proses lain yang akan menimbulkan permasalahan. Hal ini terjadi karena perbedaan kecepatan processor dan memori, dengan terjadinya perpindahan yang terlalu sering proses pembacaan CPU ke memori dan sebaliknya akan membebani sistem.
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.
ALGORITMA PENJADWALAN
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
Penjadwalan Jangka Pendek (Short Term Scheduller)
Bertugas menjadwalkan alokasi pemroses di antara proses-proses ready di memori utama. Penjadwalan dijalankan setiap terjadi pengalihan proses untuk memilih proses berikutnya yang harus dijalankan.
Penjadwalan Jangka Menengah (Medium Term Scheduller)
Proses dipindah dari memori utama ke memori sekunder agar tersedia ruang untuk proses-proses lain. Kapasitas memori utama terbatas untuk sejumlah proses aktif. Aktivitas pemindahan proses yang tertunda dari memori utama ke memori sekunder disebut swapping
Penjadwalan Jangka Panjang (Long Term Scheduller)
Penjadwal ini bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi. Batch biasanya adalah proses-proses dengan penggunaan sumber daya yang intensif (yaitu waktu
pemroses, memori, masukan/keluaran), program-program ini berprioritas rendah, digunakan sebagai pengisi (agar pemroses sibuk) selama periode aktivitas job-job interaktif rendah.
Contoh penjadwalan CPU:
Ketika sebuah proses beralih dari keadaan running ke keadaan waiting .
Ketika sebuah proses beralih dari keadaan runningke status ready.
Ketika sebuah proses beralih dari waiting untuk ready.
Ketika proses berakhir .
Posts
