CPU Scheduling

KONSEP DASAR

Pada sistem multiprogramming, selalu terjadi beberapa proses yang berjalan dalam suatu waktu. Sedangkan pada uniprogramming hal ini tidak akan terjadi, karena hanya ada satu proses yang berjalan pada saat tertentu. Sistem multiprogramming diperlukan untuk memaksimalkan utilitas CPU.

Pada saat proses dijalankan terjadi siklus eksekusi CPU dan menunggu I/O yang disebut dengan siklus CPU-I/O burst. Eksekusi proses dimulai dengan CPU burst dan dilanjutkan dengan I/O burst, diikuti CPU burst lain, kemudian I/O burst lain dan seterusnya

Pada saat suatu proses dieksekusi, terdapat banyak CPU burst yang pendek dan terdapat sedikit CPU burst yang panjang. Program I/O bound biasanya sangat pendek CPU burst nya, sedangkan program CPU bound kemungkinan CPU burst nya sangat lama. Oleh karena itu sangat penting pemilihan algoritma penjadwalan CPU.

CPU Scheduler

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 4 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-peemptive. Sebaliknya, jika 2 dan 3, maka disebut dengan preemptive. Pada non-preemptive, jika suatu proses sedang menggunakan CPU, maka proses tersebut akan tetap membawa CPU sampai proses tersebut melepaskannya (berhenti atau dalam keadaan waiting). Preemptive scheduling memiliki kelemahan, yaitu biaya yang dibutuhkan sangat tinggi. Antara lain, harus selalu dilakukan perbaikan data. Hal ini terjadi jika suatu proses ditinggalkan dan akan segera dikerjakan proses yang lain.

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:

·         Switching context

·         Switching ke user-mode

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

KRITERIA PENJADWALAN

Algoritma penjadwalan CPU yang berbeda akan memiliki perbedaan properti. 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. Adalah 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 ini 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).

First-Come First-Served Scheduling (FCFS)

Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu. Misalnya terdapat tiga proses yang dapat dengan urutan P1, P2, dan P3 dengan waktu CPU-burst dalam milidetik yang diberikan sebagai berikut :

Gant Chart dengan penjadwalan FCFS adalah sebagai berikut :

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 dating dengan urutan P2, P3, dan P1, hasil penjadwalan CPU dapat dilihat pada gant chart berikut :

Waktu tunggu sekarang untuk P1 adalah 6, P2 adalah 0 dan P3 adalah 3 sehingga ratarata waktu tunggu adalah (6 + 0 + 3)/3 = 3 milidetik. 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.

Shortest Job First Scheduler (SJF)

Pada penjadwalan SJF, proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu. 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).

SJF adalah algoritma penjadwalan yang optimal dengan rata-rata waktu tunggu yang minimal. Misalnya terdapat empat proses dengan panjang CPU burst dalam milidetik.

CPU burst berikutnya biasanya diprediksi sebagai suatu rata-rata eksponensial yang ditentukan dari CPU burst sebelumnya atau “Exponential Average”.

τ _n+1            = panjang CPU burst yang diperkirakan

τ ₀                 = panjang CPU burst sebelumnya

τ _n                 = panjang CPU burst yang ke-n (yang sedang berlangsung)

α             = ukuran pembanding antara τ n+1 dengan τ n (0 sampai 1)

Priority Scheduling

Algoritma SJF adalah suatu kasus khusus dari penjadwalan berprioritas. CPU dialokasikan untuk proses yang memiliki prioritas paling tinggi. 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 pada preemptive, 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.

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 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) 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 n proses pada ready queue dan waktu quantum q, maka setiap proses mendapatkan 1/n dari waktu CPU paling banyak q unit 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

Penjadwalan proses dengan algoritma round robin dapat dilihat pada gant chart berikut :

Waktu tunggu untuk P1 adalah 6, P2 adalah 4, dan P3 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. Semakin besar quantum-timenya maka switching yang terjadi akan semakin sedikit.

Waktu turnaround juga tergantung ukuran waktu quantum. 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.

Multilevel Queue Scheduling

Algoritma ini membagi beberapa antrian yang akan diberi prioritas berdasarkan tingkatan. Tingkatan lebih tinggi menjadi prioritas utama.

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

Multilevel Feedback Queue Scheduling

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 I/O dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.

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.
   

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.

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 I/O, 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.

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.

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 memeriksa load dari tiap-tiap prosesor. Jika terdapat ketidakseimbangan, maka dilakukan perataan dengan memindahkan (pushing) proses dari yang kelebihan muatan ke prosesor yang idle atau yang memiliki muatan lebih sedikit.

• Pull migration, kondisi ini terjadi saat prosesor yang idle menarik (pulling) proses yang sedang menunggu dari prosesor yang sibuk.

  

Operating System Examples

 

Solaris

Solaris menggunakan penjadwalan berdasarkan prioritas dimana yang mempunyai prioritas yang lebih tinggi dijalankan terlebih dahulu.

Terbagi dalam 4 kelas penjadwalan yang berbeda:

•    Real time (RT).  Thread di kelas RT memiliki prioritas yang tetap dengan waktu kuantum yang tetap juga. Thread ini memiliki prioritas yang tinggi berkisar antara 100-159. Hal inilah yang membuat proses waktu nyata memiliki response time yang cepat. Proses waktu nyata akan dijalankan sebelum proses-proses dari kelas yang lain dijalankan sehingga dapat menghentikan proses di system class. Pada umumnya, hanya sedikit proses yang merupakan real time class.

•    System (SYS). Solaris menggunakan system class untuk menjalankan kernel proses, seperti penjadwalan dan paging daemon. Threads di kelas ini adalah "bound" threads, berarti bahwa mereka akan dijalankan sampai mereka di blok atau prosesnya sudah selesai. Prioritas untuk SYS threads berkisar 60-99. Sekali dibangun, prioritas dari sistem proses tidak dapat dirubah. System class dialokasikan untuk kernel use( user proses berjalan di kernel mode bukan di system class).

•    Time Sharing (TS).  Time sharing class merupakan default class untuk proses dan kernel thread yang bersesuaian. Time slices masing-masing proses dibagi berdasarkan prioritasnya. Dalam hal ini, prioritas berbanding terbalik dengan time slices-nya. Untuk proses yang prioritasnya tinggi mempunyai time-slices yang pendek, dan sebaliknya proses dengan prioritas yang rendah mempunyai time slices yang lebih panjang. Besar prioritasnya berada antara 0-59. Proses yang interaktif berada di prioritas yang tinggi sedangkan proses CPU-bound mempunyai prioritas yang rendah. Aturan penjadwalan seperti ini memberikan response time yang baik untuk proses yang interaktif, dan troughput yang baik untuk proses CPU-bound.

•    Interactive (IA). Kelas Interaktif menggunakan aturan yang sama dengan aturan dengan kelas kelas time sharing, tetapi kelas ini memberikan prioritas yang tinggi untuk aplikasi jendela ( windowing application) sehingga menghasilkan performance yang lebih baik. Seperti TS, range IA berkisar 0-59.

Keterangan:

                                Priority: prioritas berdasarkan kelas untuk time sharing dan interactive class. Nomor yang lebih tinggi menunjukkan prioritas yang lebih tinggi.

                                Time quantum: waktu kuantum untuk setiap prioritas. Dapat diketahui bahwa fungsi waktu kuantum berbanding terbalik dengan prioritasnya.

                                Time quantum expired: Prioritas terbaru untuk thread yang telah habis time slices-nya tanpa diblok. Dapat dilihat dari tabel bahwa thread yang CPU-bound tetap mempunyai prioritas yang rendah.

                                Return from sleep: Prioritas thread yang kembali dari sleeping(misalnya menunggu dari M/K). Seperti yang terlihat dari tabel ketika M/K berada di waiting thread, prioritasnya berada antara 50-59, hal ini menyebabkan response time yang baik untuk proses yang interaktif.

                                Fixed Priority (FX).  Thread di kelas fixed priority memiliki range prioritas (0-59) yang sama seperti di time-sharing class; tetapi, prioritas mereka tidak akan berubah.

                                Fair Share Scheduler (FSS). Thread yang diatur oleh FSS dijadwalkan berdasar pembagian sumber daya dari CPU yang tersedia dan dialokasikan untuk himpunan proses-proses (yang dikenal sebagai project). FS juga berkisar 0-59. FSS and FX baru mulai diimplementasikan di Solaris 9.

Windows XP scheduling

Windows XP menggunakan algoritma, prioritas penjadwalan quantum-based yang berbasis reemptive priority scheduling. Terdapat 6 kemungkinan state dari sebuah thread, yaitu ready, standby, running, waiting, transition dan terminated. Ready state yaitu thread yang siap untuk dieksekusi. Thread yang berada pada ready state dengan prioritas tertinggi akan berpindah menjadi standby state. Ketika thread dieksekusi, thread tersebut berada pada running state. State waiting dimasuki thread ketika thread menunggu untuk dijadwalkan ulang. Ketika thread akan dieksekusi tetapi sumber daya yang diperlukan belum tersedia, maka thread tersebut akan berpindah pada state transition. Terminated state dimasuki thread ketika thread selesai dieksekusi.

Linux Scheduling

Dua masalah dengan penjadwal UNIX tradisional adalah bahwa hal itu tidak memberikan dukungan yang cukup untuk sistem SMP dan bahwa hal itu tidak cocok pada sistem. Dengan Versi 2,5, scheduler itu dirombak, dan kernel sekarang menyediakan algoritma penjadwalan yang berjalan dalam waktu konstan-dikenal sebagai O (1)-terlepas dari jumlah tugas pada sistem. The scheduler baru juga memberikan peningkatandukungan untuk SMP, termasuk afinitas prosesor dan load balancing, serta memberikan keadilan dan dukungan untuk tugas-tugas interaktif.

The scheduler Linux adalah, preemptive prioritas berbasis algoritma dengan dua rentang prioritas yang terpisah: berbagai real-time 0-99 dan nilai yang bagus antara 100 sampai 140. Kedua rentang peta ke dalam skema prioritas global dimana nilai-nilai numerik yang lebih rendah menunjukkan prioritas yang lebih tinggi.

Tidak seperti penjadwal untuk sistem lain, termasuk Solaris dan Windows XP, Linux memberikan prioritas lebih tinggi lagi tugas kuanta waktu dan lebih rendah-prioritas tugas quanta waktu yang lebih singkat. Hubungan antara prioritas dan waktu-slice panjang ditunjukkan pada

Sebuah tugas runnable dianggap memenuhi syarat untuk eksekusi pada CPU asalkan memiliki waktu tersisa dalam irisan waktu.

Ketika tugas telah habis irisan waktu, itu dianggap kadaluarsa dan tidak memenuhi syarat untuk eksekusi lagi sampai semua tugas-tugas lain juga telah habis quanta waktu mereka.

Kernel menyimpan daftar semua tugas runnable dalam struktur data runqueue. Karena dukungan untuk SMP, setiap prosesor mempertahankan runqueue sendiri dan jadwal dirinya sendiri secara mandiri. Runqueue masing-masing berisi dua array prioritas: aktif dan kadaluarsa. Array aktif berisi semua tugas dengan waktu yang tersisa di iris waktu mereka, dan array berakhir berisi semua tugas kedaluwarsa. Masing-masing array prioritas berisi daftar tugas diindeks sesuai dengan prioritas The scheduler memilih tugas dengan prioritas tertinggi dari array aktif untuk eksekusi pada CPU. Pada mesin multiprosesor, ini berarti bahwa setiap prosesor adalah penjadwalan tertinggi-prioritas tugas dari struktur runqueue sendiri. Ketika semua tugas telah kehabisan waktu mereka irisan (yaitu, array aktif kosong), dua array prioritas dipertukarkan, array berakhir menjadi array aktif, dan sebaliknya.

Linux mengimplementasikan real-time penjadwalan seperti yang didefinisikan oleh POSIX.1b. Real-time tugas ditugaskan prioritas statis. Semua tugas-tugas lain memiliki prioritas dinamis yang didasarkan pada nilai-nilai mereka bagus plus atau minus nilai 5.

Interaktivitas dari tugas menentukan apakah nilai 5 akan ditambahkan atau dikurangi dari nilai yang bagus. Interaktivitas Sebuah tugas yang ditentukan oleh berapa lama telah tidur sambil menunggu I / O. Tugas yang lebih interaktif biasanya memiliki waktu tidur lebih lama dan karena itu lebih mungkin untuk memiliki penyesuaian lebih dekat ke -5, sebagai scheduler tugas interaktif. Hasil dari penyesuaian tersebut akan menjadi prioritas yang lebih tinggi untuk tugas-tugas. Sebaliknya, tugas dengan waktu tidur pendek sering lebih CPU-terikat dan dengan demikian akan memiliki prioritas mereka diturunkan.

Prioritas dinamis Sebuah tugas ini dihitung ulang ketika tugas yang telah habis waktu kuantum dan akan dipindahkan ke array expired. Dengan demikian, ketika dua array dipertukarkan, semua tugas dalam array aktif baru telah ditetapkan prioritas baru dan irisan waktu yang sesuai.