ALGORITMA PENJADWALAN CPU

 Penjadwalan CPU adalah proses yang memungkinkan satu proses menggunakan CPU sementara eksekusi proses lain ditunda (dalam keadaan menunggu) karena tidak tersedianya sumber daya seperti I / O dll, sehingga menggunakan CPU sepenuhnya. Tujuan penjadwalan CPU adalah membuat sistem menjadi efisien, cepat dan adil. Kapanpun CPU menjadi idle, sistem operasi harus memilih salah satu proses dalam antrian siap untuk dieksekusi. Proses seleksi dilakukan oleh penjadwal jangka pendek (atau penjadwal CPU). Penjadwal memilih dari antara proses dalam memori ruang yang siap untuk dieksekusi, dan mengalokasikan CPU ke salah satunya. Pada penjadwalan CPU juga dikenal istilah arrival time dan burts time.

• Arrival time : waktu ketika proses berada di memori utama sebelum proses tersebut dimulai.
• Burst time : Waktu yang dibutuhkan untuk menyelesaikan keseluruhan proses.

Untuk melakukan penjadwalan pada CPU dapat dilakukan dengan berbagai algorima yang ada. Seperti FCFS, SJF,RR, Dan sebagainya. Pada tulisan ini akan dibahas sedikit mengenai algoritma FCFS dan SJF

1. First Come First Served (FCFS)

First Come, first Serves(FCFS), juga dikenal sebagai first in, first out(FIFO), adalah algoritme penjadwalan yang paling sederhana. FCFS hanya mengantri proses dalam urutan yang mereka datangi dalam antrian siap. 

Dalam hal ini, proses yang datang lebih dulu akan dieksekusi terlebih dahulu dan proses selanjutnya dimulai hanya setelah sebelumnya sepenuhnya dieksekusi. Contohnya :

menurut tabel di atas, tentukan berapa rata rata waiting time nya

Jawab: 

Menurut aturan algoritma FCFS, job yang pertama kali datang akan proses terlebih dahulu setelah selesai baru akan berpindah pada job yang selanjutnya.

✓ Langkah 1: pada saat cpu dalam keadaaan menganggur(tidak melakukan tugas) datang job P1. Karena pada saat itu cpu masih dalam keadaan menganggur maka waktu kedatangan nya (AT) adalah 0. P1 memiliki BT 8 yang artinya P1 akan diproses hingga waktu ke 8.

✓ Langkah 2 : Pada saat P1 sedang diproses, datang job P2 pada waktu ke 2 (lihat AT P2). Namun karena P2 datang setelah P1, maka P2 akan diproses setelah P1 selesai. Yakni P2 akan diproses pada waktu ke 8 hingga waktu ke 15. Durasi proses P2 tergantung pada BT milik P2 yakni 7

✓ Langkah 3 : pada waktu ke 7, datang job P3 meminta untuk diproses. Namun karena pada saat itu P2 masih dalam pemrosesan, maka P3 akan diproses setelah P2. P3 memiliki BT 10 itu artinya P3 akan diproses pada waktu ke 15 hingga waktu ke 25.

✓ Langkah 4 : Selanjutnya pada waktu ke 11 datang job P4 pada saat P3 masih diproses. Proses eksekusi yang sama juga berlaku untuk P4, yakni P3 dieksekusi terlebih dahulu baru setelah itu P4. P4 memiliki BT 6 yang artinya P4 akan diproses dari waktu ke 25 hingga waktu ke 31.

 

Proses eksekusi dari P1 hingga P4 dapat dilihat dari gambar berikut : 

Menghitung  waktu tunggu 

~Cara menghitung

Waktu proses - waktu datang ( AT)

 > P1 = 0 - 0 = 0

> P2 = 8 - 2 = 6

> P3 = 15 - 7 = 8

> P4 = 25 - 11 = 14 

  TOTAL= 28

Menghitung Rata - Rata Waktu Tunggu

~ Cara menghitung : 

Total waktu tunggu ÷ jumlah job 

28 ÷ 4 = 7 satuan waktu.

2. Shortest Job  First ( SJF) - Non Preemptive

Apabila suatu proses memiliki waktu tunggu paling sedikit dalam pemrosesannya maka proses tersebut yang akan di kerjakan terlebih dahulu.

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. Pada SJF tidak ada penyelaan karena SJF ini bersifat Non Preemtive. Contoh 

Menurut tabel diatas tentukan rata rata waktu tunggunya

Jawab : 

Aturan dalam SJF non Preemptive adalah jika suatu proses yang datang memiliki arrival time (AT) yang sama maka proses yang memiliki burst time (BT) terkecil akan dilayani lebih dulu

✓ Langkah 1 : pad waktu ke 0 atau saat CPU masih dalam keadaan menganggur datang P1 dengan BT 12 masuk ke antrian . Begitupun dengan P2, P3, P4 dan P5.

✓ Langkah 2 : Proses P1 hingga waktu ke 12. Karena P1 memiliki BT 12.

✓ Langkah 3 : Pada waktu ke 12, semua sisa proses akan masuk  ke antrian  yakni P2, P3, P4, dan P5. Lalu proses antrian yang memiliki nilai BT terkecil. P5 memiliki  nilai BT terkecil yakni 1, sehingga akan langsung diproses hingga waktu ke 13.

✓ Langkah 4 : Pada waktu ke 13, proses job yang memiliki BT terkecil, yakni P4 dengan BT 2. P4 akan diproses hingga waktu ke 15.

✓ Langkah 5 : Pada waktu ke 15, sisa job (P2 dan P3) akan masuk ke antrian. Lalu proses job yang memiliki BT terkecil yakni P3 dengan BT 5. Proses P3 hingga waktu ke 20.

✓ Langkah 6 : Pada waktu ke 20, P2 akan masuk ke antrian dan langsung diproses hingga waktu ke 28.

Menghitung waktu tunggu 

> P1 = 0

> P2 = 20-2 = 18

> P3 = 15-3 = 12

> P4 = 13-5 = 8

> P5 = 12-9 = 3

 TOTAL= 41

Menghitung rata rata waktu tunggu

41÷5 = 8.5 satuan waktu.

3. Shortest Job First (SJF) - 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 SJFsering disebut juga Shortest-Remaining- Time-First scheduling(SRF). Contoh : 

Dari tabel diatas tentukan rata rata waktu tunggunya.

Jawab : 

✓ Langkah 1 : Pada waktu ke 0 , P1 masuk dan langsung diproses. 

✓ Langkah 2 : Pada saat waktu ke 2, P2 masuk dengan BT 8. P2 sebagai interupsi akan langsung diproses dan sisa proses dari P1 akan dimasukkan pada antrian. Sisa proses dari P1 adalah 10.

✓ Langkah 3 : Pada waktu ke 3 , datang P3 dengan BT 3 Dan akan langsung diproses. Sisa proses dari P2 dan P1 akan disimpan di antrian. Pada waktu ini, P2 masih menyisakan 7 proses.

✓ Langkah 4 : Pada waktu ke 5, datang P4 dengan BT 2 Dan akan langsung dieksekusi. Karna P4 hanya memiliki BT 2, maka akan langsung diproses hingga waktu ke 7.

✓ Langkah 5 : Pada waktu ke 7 P2, P1,dan P3 masuk ke antrian. Karena dalam antrian P3 memiliki BT terkecil yakni 3, maka P3 akan diproses terlebih dahulu.

✓ Langkah 6 : Pada saat ke 9 masuk P5 dengan BT 1 dan sisa dari proses sebelumnya juga akan masuk ke antrian. Pada waktu ini sisa proses dari P3 adalah 1. Karena P3 dan P5 memiliki BT yang sama yakni 1, maka proses job yang pertama kali masuk yaitu P3. P3 akan diproses hingga waktu ke 10.

✓ Langkah 7 : saat waktu ke 10 P5, P2, dan P1 masuk ke antrian. Dari ketiga antrian yang ada, P5 memiliki BT terkecil yaitu 1, akan diproses terlebih dahulu. P5 akan di proses hingga waktu ke 11. 

✓ Langkah 8 : Pada waktu ke 11, P2 dan P1 masuk ke antrian. Diantara P2 dan P3 yang memiliki nilai BT terkecil adalah P2 sehingga P2 akan diproses terlebih dahulu. P2 akan diproses hingga waktu ke 18.

✓ Langkah 9 : Pada saat ke 18, P1 masuk ke antrian dan akan langsung diproses. P1 akan diproses hingga waktu ke 28. 

Menghitung waktu tunggu

> P1 = 18-2 = 16

> P2 = 11-3 = 8

> P3 = 7-5 = 2

> P4 = 5-5 = 0

> P5 = 10-9 = 1

TOTAL = 27

Menghitung Rata Rata Waktu Tunggu

 27÷5 = 5.4 satuan waktu