CPU Scheduling

Tujuan

1. Untuk memperkenalkan CPU Scheduling yang merupakan dasar dari multi-program Operasi Sistem.
2. Untuk menggambarkan bentuk-bentuk algoritma CPU scheduling.
3. Untuk membicarakan algoritma CPU Scheduling yang cocok dipakai dalam sistem tertentu.

5.1 Konsep Dasar

Di sistem prosesor tunggal, hanya satu proses yang dapat berjalan dalam satu waktu, dan yang lainnya harus menunggu sampai CPU bebas dan dapat dijadwal ulang. Tujuan darimultiprogramming adalah untuk memaksimalkan penggunaan CPU dengan cara mengatur alokasi waktu yang digunakan oleh CPU, sehingga proses berjalan sepanjang waktu dan memperkecil waktu idle. Akibatnya sistem operasi dapat membuat komputer lebih produktif. Oleh karena itu perlu adanya penjadwalan proses-proses yang ada pada sistem.

5.1.1 Siklus Burst CPU – I/O

Keberhasilan penjadwalan CPU tergantung pada beberapa properti prosesor. Pengeksekusian dari proses tersebut terdiri dari siklus CPU ekskusi dan I/O Wait. Proses hanya akan bolak balik diantara dua state ini. Pengeksekusian proses dimulai dari burst CPU setelah itu diikuti burst I/O, lalu diikuti burst CPU lagi, kemudian burst I/O lagi, begitu seterusnya. Burst CPU akan berakhir dengan permintaan dari sistem untuk mengakiri pengeksekusian (Gambar 5.1).

Durasi burst CPU menjadi dapat diukur secara ekstensif. Walaupun dari proses ke proses dan dari komputer ke komputer berubah-ubah. Dan cenderung mirip dengan kurva frekuensi seperti pada Gambar 5.2. Kurva itu secara umum mempunyai karakteristik sebagai eksponen atau hyper-eksponen, dengan sebagian besar dari burst CPU yang singkat dan sebagian kecil dari burst CPU yang lama. Secara khas sebuah program I/O-bound punya banyak burst CPU singkat sedangkan program CPU-bound mungkin hanya punya sedikit burst CPU lama.

Gambar 5.1 Rangkaian bolak balik dari burst CPU dan I/O.

Gambar 5.2 Histogram dari durasi burst CPU.

5.1.2 CPU Scheduler

Sewaktu-waktu CPU menjadi idle, operasi sistem harus memilih satu dari proses yang siapqueue untuk di eksekusi. Proses seleksi dilaksanakan oleh short-term scheduler (atau CPUScheduler). Scheduler memilih proses dari banyak proses di memory untuk diberikan ke CPU untuk diproses.

5.1.3 Penjadwalan Preemptive

Penjadwalan CPU mungkin akan dijalankan ketika proses dalam keadaan:

1. Berubah dari running ke waiting state.
2. Berubah dari running ke ready state.
3. Berubah dari ready ke waiting state.
4. Dihentikan.

Penjadwalan nomor 1 dan 4 bersifat nonpreemptive, artinya sistem opersi tidak pernah melakukan context switch dari proses yang sedang berjalan ke proses yang lain.

Sedangkan yang lainnya bersifat preemptive yang mana sistem operasi bisa memberhentikan sementara proses yang sedang berjalan dan memberikan ruang kepada proses yang prioritasnya lebih tinggi.

5.1.4 Dispatcher

Dispatcher adalah modul yang memberikan kontrol CPU kepada proses yang sedang terjadwal. Fungsinya adalah:

1. Switching context.
2.  Switching to user mode.
3. Lompat dari suatu bagian di progam user untuk mengulang program.

Gambar 5.3 Dispatch Latency

Dispatcher seharusnya dapat dilakukan secepat mungkin. Dispatch Latency adalah waktu yang diperlukan dispatcher untuk menghentikan suatu proses dan memulai proses yang lain.

5.2 Kriteria Penjadwalan

Suatu algoritma penjadwalan CPU yang berbeda dapat mempunyai nilai yang berbeda untuk sistem yang berbeda. Banyak kriteria yang bisa dipakai untuk menilai algoritma penjadwalan CPU.

Kriteria yang digunakan dalam menilai adalah:

• CPU Utilization. Menjaga CPU selalu dalam keadaan sesibuk mungkin.
• Throughput. Adalah jumlah kerja yang diselesaikan per satuan waktu.
• Turnaround Time. Adalah sejumlah waktu yang dihabiskan untuk menyelesaikan sebuah proses. Waktu yang dimaksud adalah jumlah dari waktu menunggu dan waktu eksekusi.
• Waiting Time. Adalah jumlah waktu yang dibutuhkan proses di ready queue. Waiting time ini tidak mempengaruhi eksekusi proses dan penggunaan I/O.
• Response Time. Waktu yang di butuhkan oleh suatu proses dari minta dilayani hingga ada respon pertama yang menanggapi permintaan tersebut. Tetapi bukan waktu yang dipakai output untuk respon tersebut.
• Fairness. Suatu algoritma harus memperhatikan pengawasan nilai prioritas dari suatu proses (menghindari terjadinya starvation CPU time). Jadi tiap-tiap proses akan mendapatkan pembagian waktu yang sama.
• Efisiensi. Penghitungan prioritas dan sebagainya menentukan apakah suatu algoritma efisien atau tidak.

Algoritma penjadwalan yang baik adalah memaksimalkan CPU utilization dan throughput, dan meminimalkan turnaround time, waiting time, dan response time.

5.3 Algoritma Penjadwalan

Algoritma diperlukan untuk mengatur giliran proses-proses yang ada di ready queue yang mengantri untuk dialokasikan ke CPU.

5.3.1 First Come First Served (FCFS) Scheduling

FCFS merupakan algoritma penjadwalan yang paling sederhana yang digunakan dalam CPU. Dengan menggunakan algoritma ini setiap proses yang berada pada status readydimasukkan kedalam FIFO queue atau antrian dengan prinsip first in first out, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi.

Kelemahan dari algoritma ini:

1. Waiting time rata-ratanya cukup lama.
2. Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU. Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh proses yang lain.

5.3.2 Shortest Job First (SJF) Scheduling

Pada algoritma ini setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek.

Ada beberapa kekurangan dari algoritma ini yaitu:

1. Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya.
2. Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula SJF (Shortest Job First) karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.

Algoritma ini dapat dibagi menjadi dua bagian yaitu :

1. Preemptive . Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready queue tersebut. Preemptive SJF sering disebut juga Shortest-Remaining- Time-First scheduling.
2. Non-preemptive . CPU tidak memperbolehkan proses yang ada di ready queue untuk menggeser proses yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil.

5.3.3 Priority Scheduling

Priority Scheduling merupakan algoritma penjadwalan yang mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing.

Prioritas suatu proses dapat ditentukan melalui beberapa karakteristik antara lain:

1. Time limit.
2. Memory requirement.
3. Akses file.
4. Perbandingan antara I/O burst dengan CPU burst.
5. Tingkat kepentingan proses.

Ada dua skema:

1. Preemptive. Jika ada suatu proses yang baru datang memiliki prioritas yang lebih tinggi daripada proses yang sedang dijalankan, maka proses yang sedang berjalan tersebut dihentikan, lalu CPU dialihkan untuk proses yang baru datang tersebut.
2. Nonpreemtive. Proses yang baru datang tidak dapat menganggu proses yang sedang berjalan, tetapi hanya diletakkan di depan queue.

Kelemahan pada priority scheduling adalah dapat terjadinya indefinite blocking (starvation). Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yang menunggu dalam queue secara bertahap.

5.3.4 Round Robin Scheduling

Algoritma ini menggilir proses yang ada di antrian. Setiap proses mendapat jatah sebesartime quantum. Jika time quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke proses berikutnya.

Semua proses mendapat jatah waktu yang sama dari CPU yaitu (1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.

Jika q terlalu besar maka akan sama dengan algoritma FCFS. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang.

Gambar 5.4 Urutan kejadian algoritma round robin

5.3.5 Multilevel Queue Scheduling

Algoritma ini membagi beberapa antrian yang akan diberi prioritas berdasarkan tingkatan. Tingkatan lebih tinggi menjadi prioritas utama Seperti yang terlihat pada gambar 5.5.

Gambar 5.5 Multi level queue

Ready queue dibagi menjadi queue yang terpisah yaitu foreground (interaktif) danbackground (batch). Setiap queue mempunyai algoritmanya masing - masing. Foreground queue memakai algoritma penjadwalan round robin sedangkan background queue memakai algoritma penjadwalan FCFS.

5.3.6 Multilevel Feedback-Queue Scheduling

Algoritma ini mirip sekali dengan algoritma multilevel queue. Perbedaannya ialah algoritma ini mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Hal ini menguntungkan proses interaksi karena proses ini hanya memakai waktu CPU yang sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan tingkatannya. Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil, dengan begitu CPU akan terutilisasi penuh dan M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.

Gambar 5.6 Multilevel feedback queue

Multilevel feedback queue akan diterapkan dengan mendefinisikan terlebih dahulu parameter-parameternya, yaitu:

1. Jumlah antrian.
2. Algoritma internal tiap queue.
3. Aturan sebuah proses naik ke antrian yang lebih tinggi.
4. Aturan sebuah proses turun ke antrian yang lebih rendah.
5. Antrian yang akan dimasuki tiap proses yang baru datang.

5.4 Multiple-Processor Scheduling

Pada prosesor jamak, penjadwalannya jauh lebih kompleks daripada prosesor tunggal karena pada prosesor jamak memungkinkan adanya load sharing antar prosesor yang menyebabkan penjadwalan menjadi lebih kompleks namun kemampuan sistem tersebut menjadi lebih baik.

5.4.1 Approaches to Multiple-Processor Scheduling

Pendekatan pertama untuk penjadwalan prosesor jamak adalah penjadwalan asymmetric multiprocessing atau bisa disebut juga sebagai penjadwalan master/slave. Dimana pada metode ini hanya satu prosesor(master) yang menangani semua keputusan penjadwalan, pemrosesan M/K, dan aktivitas sistem lainnya dan prosesor lainnya (slave) hanya mengeksekusi proses. Metode ini sederhana karena hanya satu prosesor yang mengakses struktur data sistem dan juga mengurangi data sharing.

Penjadwalan SMP (Symmetric multiprocessing) adalah pendekatan kedua untuk penjadwalan prosesor jamak. Dimana setiap prosesor menjadwalkan dirinya sendiri (self scheduling). Semua proses mungkin berada pada ready queue yang biasa, atau mungkin setiap prosesor memiliki ready queue tersendiri. Bagaimanapun juga, penjadwalan terlaksana dengan menjadwalkan setiap prosesor untuk memeriksa antrian ready dan memilih suatu proses untuk dieksekusi.

5.4.2 Processor Affinity

Afinitas prosesor (processor affinity) adalah pencegahan migrasi proses antar prosesor sehingga menjaga proses tersebut tetap berjalan di prosesor yang sama.

Ada dua jenis afinitas prosesor, yakni:

• Soft affinity yang memungkinkan proses berpindah dari satu prosesor ke prosesor yang lain, dan
• Hard affinity yang menjamin bahwa suatu proses akan berjalan pada prosesor yang sama dan tidak berpindah. Contoh sistem yang menyediakan system calls yang mendukung hard affinity adalah Linux.

5.4.3 Load Balancing

Load balancing adalah usaha untuk menjaga workload terdistribusi sama rata untuk semua prosesor dalam sistem SMP. Load balancing hanya perlu untuk dilakukan pada sistem dimana setiap prosesor memiliki antrian tersendiri(private queue) untuk proses-proses yang akan dipilih untuk dieksekusi.

Ada dua jenis load balancing, yakni:

• Push migration, pada kondisi ini ada suatu task spesifik yang secara berkala memeriksaload dari tiap-tiap prosesor. Jika terdapat ketidakseimbangan, maka dilakukan perataan dengan memindahkan (pushing) proses dari yang kelebihan muatan ke prosesor yang idleatau yang memiliki muatan lebih sedikit.
• Pull migration, kondisi ini terjadi saat prosesor yang idle menarik (pulling) proses yang sedang menunggu dari prosesor yang sibuk.

5.4.4 Symmetric Multithreading

SMT (Symetric Multithreading) adalah strategi alternatif untuk menjalankan beberapa threadsecara bersamaan. SMT juga biasa disebut teknologi hyperthreading dalam prosesor intel.