PENJADWALAN CPU

Anggota Kelompok dari pembuatan blog ini :

1. Ade Arman                       ( NRP 210.511.136 )
2. Roby yanri Dinata             ( NRP 210.511.158 )
3. Muhammad Farhan           ( NRP 210.511.167 )
4. Wahyu Hikmah fadilah       ( NRP 210.511.177)




Aslmkm wr.wb.

Alhamdulillah kita bisa berbagi ilmu mengenai penjadwalan CPU melalui blog ini.
mungkin masih banyak kekurangan yang belum terpenuhi didalam blog ini,kami pun menerima saran dari teman-teman maupun bapak dosen pembimbing mata kuliah Sistem Operasi untuk membei saran terhadap blog ini,agar blog ini dapat bermanfaat bagi kita semua.

kurang lebihnya silahkan mulai membaca postingan didalam blog ini mudah-mudahan bermanfaat.
 Terima kasih

1.1 KONSEP DASAR

Pada  sistem  multiprogramming,  selalu  akan  terjadi  beberapa  proses  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 seperti pada Gambar 1-1.

                                                          Gambar 1.1: siklus CPU I/O Burst

Gambar 1-2 :Histogram waktu CPU burst

Pada saat suatu proses dieksekusi, terdapat banyak CPU burst yang pendek dan terdapat sedikit CPU burst yang panjang.   Program yang I/O bound biasanya sangat pendek CPU burst nya, sedangkan program yang CPU bound kemungkinan CPU burst nya sangat  lama.   Hal ini dapat digambarkan  dengan grafik yang eksponensial  atau hiper eksponensial seperti pada Gambar 1-2.  Oleh karena itu sangat penting pemilihan algoritma penjadwalan CPU.

1.1.1 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 short- term scheduler (CPU scheduler).  Keputusan untuk menjadwalkan CPU mengikuti empat keadaan dibawah ini :

1.   Apabila proses berpindah dari keadaan running ke waiting;

2.   Apabila proses berpindah dari keadaan running ke ready;

3.   Apabila proses berpindah dari keadaan waiting ke ready;

4.   Apabila proses berhenti.

Apabila model penjadwalan yang dipilih menggunakan keadaan 1 dan 4, maka penjadwakan semacam ini disebut non-peemptive. Sebaliknya, apabila yang digunakan adalah keadaan 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.

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

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

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

1.3.1   First-Come First-Served Scheduling (FCFS)

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.

Misalnya terdapat tiga proses yang dapat dengan urutan P1, P2, dan P3  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 :

P1	P2	P3

0                                                            24              27              30

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

Waktu tunggu sekarang untuk P1  adalah 6, P2  adalah 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  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.

1.3.2    Shortest Job First Scheduler (SJF)

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)  

Waktu tunggu untuk P1  adalah 0, P2  adalah 26, P3  adalah 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) 

Waktu tunggu untuk P1  adalah 9, P2  adalah 1, P3  adalah 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   dari   CPU   burst   sebelumnya   atau

“Exponential Average”.

 τ n +1 = α t0 + (1 − α )τ n

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 1-3.

                                          Gambar 1-3 : 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

1.3.3    Priority Scheduling

Algoritma SJF adalah suatu kasus khusus dari penjadwalan berprioritas. Tiap- tiap 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.   

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

Process            Burst Time

P1                             24

P2                               3

P3                               3

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

P1

P2

P3

P1

P1

P1

P1

P1

0                4          7          10             14            18               22               26          30

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 seperti yang terlihat pada Gambar 1-4. Semakin besar quantum-timenya maka

switching yang terjadi akan semakin sedikit.

                           Gambar 1-4 : Menunjukkan waktu kuantum yang lebih kecil meningkatkan context switch

Waktu  turnaround  juga  tergantung  ukuran  waktu  quantum. Seperti  pada Gambar 1-5, 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.