Penjadwalan CPU



Pengenalan Penjadwalan CPU

Penjadwalan CPU (CPU Scheduling) adalah basis dari sistem operasi multiprograming. Dengan men-switch CPU kepada proses-proses, sistem operasi dapat membuat computer lebih produktif. Pada materi ini akan dibahas dasar konsep penjadwalan dan diperkenalkan beberapa algoritma penjadwalan CPU.



[Top]


Konsep Dasar

Tujuan dari multiprograming adalah agar beberapa proses dapat berjalan sedemikian rupa sehingga penggunaan CPU menjadi maksimal (CPU utilization maksimal). Ketika CPU mengganggur, sistem operasi harus memilih satu dari proses dalam ready queue untuk dieksekusi. Pemilihan tersebut dilakukan oleh penjadwal CPU (CPU Scheduler). Penjadwal tersebut akan memilih di antara proses di memori yang siap untuk dieksekusi dan kemudian akan memberikan jatah CPU kepada salah satu proses tersebut.

Keputusan dalam penjadwalan CPU berlangsung saat state proses :

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

Untuk nomor 1 dan 4, skema penjadwalannya dikatakan non-preemptive. Sedangkan untuk nomor 2 dan 3, skema penjadwalannya dikatakan preemptive. Preemptive maksudnya dapat diganti oleh proses lain. Non-preemptive maksudnya tidak dapat diganti oleh proses lain (proses yang sedang berjalan harus dijalankan sampai selesai dulu).



[Top]


Kriteria Penjadwalan

Kriteria yang digunakan untuk membandingkan algoritma-algoritma penjadwalan adalah sebagai berikut:

  • CPU utilization
    Sebaiknya CPU bekerja sesibuk mungkin.
  • Throughput
    Throughput adalah banyaknya proses yang selesai dieksekusi per satuan waktu. Semakin banyak throughput, semakin baik.
  • Turnaround time
    Turnaround time adalah waktu yang dibutuhkan untuk mengeksekusi suatu proses.     Semakin kecil turnaround time, semakin baik.
  • Waiting time
    Waiting time adalah waktu yang dibutuhkan suatu proses selama menunggu di ready queue.     Semakin kecil waiting time, semakin baik.
  • Response time
    Response time adalah waktu yang dibutuhkan sejak suatu proses datang me-request sampai proses itu menerima response pertama. Semakin kecil response time, semakin baik.
Kriteria yang optimal adalah :
  1. CPU utilization maksimal
  2. Throughput maksimal
  3. Turnaround time minimal
  4. Waiting time minimal
  5. Response time minimal


[Top]


Algoritma Penjadwalan

Terdapat banyak algoritma untuk penjadwalan CPU. Tapi dalam materi ini hanya akan dibahas beberapa algoritma. Berikut ini adalah algoritma-algoritma tersebut :

  • First-Come, First-Served Scheduling (FCFS)
    (lihat simulasi FCFS)

    FCFS memilih proses berdasarkan urutan waktu me-request CPU. Proses yang me-request CPU lebih dahulu akan mendapatkan jatah CPU lebih dahulu. Skema FIFO (First In First Out) adalah non-preemptive.
    Algoritma ini memungkinkan terjadinya convoy effect : proses yang waktu eksekusinya sebentar (CPU burst time-nya kecil) menunggu terlalu lama karena didahului oleh proses yang waktu eksekusinya lama     (CPU burst time-nya besar). FCFS tidak cocok untuk sistem time-sharing.
  • Shortest-Job-First Scheduling (SJF)

    SJF memilih proses berdasarkan besar next CPU burst proses.     Proses yang next CPU burst-nya kecil akan mendapatkan jatah CPU lebih dahulu.
    SJF menghasilkan solusi optimal untuk : minimum average waiting time.
    Dua skema dalam SJF:
    Nonpreemptive (lihat simulasi SJF Nonpremptive)- sekali jatah CPU diberikan pada suatu proses, maka proses lain tidak dapat mengambil alih jatah CPU sampai proses yang sedang memakai jatah CPU itu melepaskan jatah CPU dengan sukarela.
    Preemptive (lihat simulasi SJF Preemptive)- jika terdapat proses baru dengan next CPU burst yang lebih kecil daripada sisa waktu CPU burst proses yang running (sedang memakai jatah CPU) saat ini, maka dilakukan preempt terhadap proses yang sedang running tersebut. Algoritma ini disebut juga Shortest-Remaining-Time-First (SRTF).
  • Prioritas Scheduling

    Pada algoritma ini setiap proses diberi prioritas. Jatah CPU diberikan pada proses dengan prioritas tertinggi.
    Dua skema dalam algoritma ini :
    Preemptive : proses dapat diinterupsi jika terdapat proses dengan prioritas lebih tinggi.
    Nonpreemptive : proses tidak dapat diinterupsi.
    SFF merupakan prioritas scheduling dimana yang menjadi prioritas adalah next CPU burst proses.
    Algoritma ini memungkinkan terjadinya starvation : proses dengan prioritas rendah bisa jadi tidak pernah dieksekusi.


  • Round-Robin Scheduling (RR)
    (lihat simulasi RR)

    Setiap proses mendapat jatah waktu CPU (time slice/quantum) tertentu misalkan 10 atau 100 milidetik.
    Setelah waktu tersebut maka proses akan di-preempt dan dipindahkan ke ready queue.
    Jika terdapat n proses di ready queue dan waktu quantum q (milidetik), maka:
    Maka setiap proses akan mendapatkan 1/n dari waktu CPU.
    Proses tidak akan menunggu lebih lama dari: (n-1)q satuan waktu.


[Top]