Proses Penjadwalan CPU

Penjadwalan CPU merupakan 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. Terdapat 4 skema dalam penjadwalan CPU, yaitu:

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

Pada skema 1 dan 2 dapat dikatakan preemptive, yang artinya dapat diganti oleh proses lain atau bahasa lainnya bisa di interrupt. Skema 3 dan 4 dikatakan non-preemtive yang artinya tidak dapat diganti oleh proses lain harus dijalankan sampai selesai dengan kata lain tidak bisa 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 dengan I/O Bound.

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:

1. proses yang memiliki Burst M/K yang sangat lama disebut I/O Bound.
2. 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.

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

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:

1. 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%.
2. Throughput. Adalah banyaknya proses yang selesai dikerjakan dalam satu satuan waktu.
3. 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.
4. Waiting time. Waktu yang diperlukan oleh suatu proses untuk menunggu di ready queue. Waiting time ini tidak mempengaruhi eksekusi proses dan penggunaan I/O.
5. Response time. Waktu yang dibutuhkan oleh suatu proses dari minta dilayani hingga ada respon pertama yang menanggapi permintaan tersebut.
6. Fairness. Meyakinkan bahwa tiap-tiap proses akan mendapatkan pembagian waktu penggunaan CPU secara terbuka (fair).

Algoritma Penjadwalan

Penjadwalan CPU menyangkut penentuan proses-proses yang ada dalam ready queue yang akan dialokasikan pada CPU. Terdapat beberapa algoritma penjadwalan CPU, yaitu :

1. First-Come First-Served Scheduling (FCFS)
2. Shortest Job First Scheduler (SJF)
3. Priority Scheduling
4. Round-Robin Scheduling

First-Come First-Served Scheduling (FCFS)

Pertama datang pertama dilayani. Tidak peduli apakah burst timenya panjang atau pendek. Algoritma FCFS merupakan penjadwalan non-preemptive, sebuah proses yang sedang dikerjakan harus diselesaikan terlebih dulu barulah proses lainnya dapat dilayani.

Kekurangan FCFS :

• Waiting Time rata-ratanya cukup lama.
• Terjadinya Convoy Effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi CPU.

Misalnya proses-proses yang akan dikerjakan oleh CPU adalah sebagai berikut :

ST = Waktu mulai proses yang dilayani CPU

CT = Waktu selesai proses yang dieksekusi CPU ( ST + BT )

WT = Waktu tunggu dalam antrian ( ST — AT)

TAT= Waktu yang dihabiskan proses selama dalam sistem pemrosesan (CT-AT)

Average Waiting Time adalah :

( 0 + 6 + 9 ) = 15 / 3 = 5 ms

Turn Arround Time adalah :

( 8 + 11 + 12 ) = 10, 33 ms

Shortest Job First Scheduler (SJF)

Salah satu jenis algoritma penjadwalan salah satunya adalah algoritma penjadwalan Shortest Job First. Pada algortima 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 pendek, sehingga dapat dikatakan bahwa algortima ini adalah algoritma yang optimal.

Algoritma ini dapat berupa preemptive dan non-preemptive. Jika preemptive, jika ada proses datang dengan burst time yang lebih kecil daripada yang sedang dieksekusi, maka proses tersebut akan menggantikan proses yang sedang dieksekusi. Pada non-preemptive, proses yang sedang berlangsung tidak dapat digantikan dan harus menunggu sampai burst selesai

Langkah-langkah Menghitung Algoritma Shortest Job First

Waiting Time : waktu pada saat job menunggu untuk dieksekusi

Turn Around Time : waktu yang diperlukan job sejak tiba sampai selesai dikerjakan oleh CPU

Average Waiting Time : rata-rata waktu proses menunggu

• Membuat Gantt Chart

Kelebihan dan Kekurangan

Kelebihan :

• Memberikan minimum waiting time untuk kumpulan proses yang mengantri.
• Penjadwalan SJF mempunyaI efiesiensi tinggi dan turn around time rendah.

Kekurangan :

• Tidak bisa memprediksi burst time proses yang akan dieksekusi selanjutnya.
• Proses yang mempunyai burst time lebih banyak akan mempunyai waiting time yang lebih besar karena yang dieksekusi terlebih dahulu adalah yang mempunyai burst time lebih sedikit.

Algoritma Preemptive

Penjadualan preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. 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.

Table Solusi :

Algoritma 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 diinterupt. 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.

Priority Scheduling

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

Prioritas tersebut dapat ditentukan melalui beberapa karakteristik antara lain:

• Time limit
• Memory requirement
• Akses file
• Perbandingan antara I/O Burst dengan CPU Burst
• Tingkat kepentingan proses
• Priority Scheduling preemptive

Pada Priority Scheduling 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.

• Priority Scheduling non-preemptive

Sebaliknya pada Priority Scheduling non-preemptive saat ada proses baru yang memiliki prioritas lebih tinggi datang dari pada proses yang sedang berjalan, maka proses baru yang memiliki prioritas yang lebih tinggi tidak akan menganggu proses yang sedang berjalan tetapi hanya akan dimasukan kedalam qeue.

Round-Robin Scheduling

Round Robin merupakan penjadwalan proses dimana algoritma ini menggilir proses yang ada di antrian. Proses akan mendapatkan jatah sebesar time quantum. Jika time quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke proses berikutnya. Pada penjadwalan proses ini, tidak ada proses yang diprioritaskan, semua proses mendapatkan pembagian waktu yang sama dari CPU. Time sharing merupakan konsep dasar dari algoritma ini. Pada dasarnya algoritma ini sama dengan FCFS, hanya saja bersifat preemptive.

Kelebihan :

1. Algoritma yang paling simpel.
2. Memiliki overhead yang kecil, jika ukuran proses lebih kecil dibanding slot waktunya
3. Mencegah terjadinya kondisi deadlock atau starvision

Kekurangan :

1. Waktu tunggu sangat lama untuk proses besar
2. Sering terjadi convoy effect
3. Jika slot waktunya terlalu kecil , maka sebagian proses tidak bisa diselesaikan oleh satu slot waktu saja.

Ketentuan Penjadwalan Round-Robin

1. Jika Quantum habis dan proses belum selesai maka proses running itu menjadi ready dan pemrosesan dialihkan ke proses lain,
2. Jika Quantum belum habis dan proses menunggu suatu kejadian (misal menunggu selesainya suatu operasi I/O), maka proses running itu menjadi blocked dan proses dialihkan ke proses lain.
3. Dan jika Quantum belum habis tapi proses telah selesai maka proses running itu diakhiri dan pemprosesan dialihkan ke proses lain.

Misalnya proses-proses yang akan dikerjakan oleh CPU adalah sebagai berikut :

Average Waiting Time adalah :

( 7 + 5 + 0 ) / 3 = 4 ms

Turn Arround Time adalah :

( 14 + 10 + 2 ) / 3 = 8,66 ms