Algoritma Penjadwalan

ALGORITMA

1. FIFO

 Algoritma ini adalah algoritma yang paling sederhana. Prinsip dari algoritma ini adalah seperti prinsip antrian (antrian tak berprioritas), halaman yang masuk lebih dulu maka akan keluar lebih dulu juga. Algoritma ini menggunakan struktur data stack. Apabila tidak ada frame kosong saat terjadi page fault, maka korban yang dipilih adalah frame yang berada di stack paling bawah, yaitu halaman yang berada paling lama berada di memori. Dengan hanya informasi mengenai lama berada di memori, maka algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu berada terus di memori karena selalu digunakan. Page itu karena mengikuti pola antrian berdasar lamanya berada di memori menjadi elemen terdepan, diganti, dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali



.

     Pada awalnya, algoritma ini dianggap cukup mengatasi masalah tentang pergantian halaman, sampai pada tahun 70-an, Belady menemukan keanehan pada algoritma ini yang dikenal kemudian dengan anomali Belady. Anomali Belady adalah keadaan di mana page fault rate meningkat seiring dengan pertambahan jumlah frame , seperti yang bisa dilihat pada contoh di bawah ini.'

Ketika jumlah frame ditambah dari 3 frame menjadi 4 frame, jumlah page fault yang terjadi malah bertambah (dari 14 page fault menjadi 15 page fault ). Hal ini biasanya terjadi pada kasus yang menginginkan halaman yang baru saja di-swap-out sebelumnya. Oleh karena itu, dicarilah algoritma lain yang mampu lebih baik dalam penanganan pergantian halaman seperti algoritma optimal.
Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).
Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya memindahkan page tidak diacu Page ditambah bit R mencatat apakah page diacu atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu.
Variasi dari FIFO antara lain:

    Algoritma penggantian page kesempatan kedua (second chance page replacement algorithm)
    Algoritma penggantian clock page (clock page replacement algorithm)

Algoritma Penggantian Page Kesempatan Kedua
Mekanisme algoritma

    Saat terjadi page fault, algoritma memilih page elemen terdepan diganti bila bit R bernilai 0.
    Bila bit R bernilai 1, maka bit page terdepan senarai direset menjadi 0 dan diletakkan ke ujung belakang senarai. Mekanisme ini kembali diterapkan ke elemen berikutnya.

Algoritma Penggantian Clock Page
Algoritma penggantian page kesempatan kedua merupakan algoritma yang memadai tapi tidak efisien karena memindahkan page-page di senarainya. Algoritma penggantian clock page merupakan perbaikan algoritma pertama.
Mekanisme algoritma

    Pada algoritma ini, semua page merupakan senarai melingkar membentuk pola jam. Terdapat penunjuk (pointer) ke page tertua.

Ketika terjadi page fault, page yang ditunjuk diperiksa.

    Jika bit R bernilai 0, maka page diganti. Page baru ditempatkan di tempat page diganti, dan penunjuk dimajukan satu posisi ke page berikutnya.
    Jika bit R bernilai 1, maka bit R direset menjadi 0, dan penunjuk dimajukan satu posisi. Seterusnya sampai menemui page dengan bit R bernilai 0.

Kedua algoritma adalah sama, hanya berbeda dalam implementasi, yaitu:

    Algoritma penggantian page kesempatan kedua menggunakan senarai lurus tidak sirkular.
    Algoritma penggantian clock page menggunakan senarai sirkular.

2 SJF (Shortest Job First)

Pada algoritma 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 menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.

Tabel 14.1. Contoh Shortest Job First

Process	Arrival Time	Burst Time
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

Contoh: Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time 4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4 dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF.
Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms.

Gambar 14.3. Shortest Job First (Non-Preemptive)

Average waiting time rata-rata untuk ketiga prses tersebut adalah sebesar (9+1+0+2)/4=3 ms.
Ada beberapa kekurangan dari algoritma ini yaitu:

1. Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya.
2. Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.
   
   
   
   

   Algoritma Penjadwalan

Algortima – algoritma yang menerapkan strategi preemptive :

• RR ( Round-Robin ).

• SRF ( Shortest-Remaining-First ).

• PS ( Priority Schedulling ).
• GS ( Guaranteed Schedulling ).

1. 
   Penjadwalan Round Robin (RR)
   Penjadwalan preemptive , bukan di- preempt oleh proses lain tapi terutama oleh penjadwal berdasarkan waktu berjalannya proses, disebut preempt-by-time. Penjadwalan tanpa prioritas.
   Penjadwalan FIFO ( First In First Out )
   Penjadwalan non-preemptive (run to completion). Penjadwalan tidak berprioritas.
   Penjadwalan Berprioritas (PS)
   Ide penjadwalan adalah tipa proses diberi prioritas dan proses berprioritas tertinggi running (mendapat jatah waktu pemroses). Prioritas dapat diberikan secara :
   
2. Prioritas statis ( static priorities ).

• Prioritas dinamis (dynamic priorities ) .

• Prioritas Statis

• Prioritas statis berarti prioritas tak berubah.

• Prioritas Dinamis

Penjadwalan dengan Banyak Antrian (MFQ) : Penjadwalan preemptive (by time ). Penjadwalan berprioritas dinamis.
Penjadwalan Sisa Waktu Terpendek, Duluan ( SRF ) Penjadwalan ini merupakan : Penjadwalan preemptive  dan Penjadwalan berprioritas dinamis
Penjadwalan Rasio Tanggapan Tertinggi, Duluan (HRN) Penjadwalan ini merupakan : Penjadwalan non-preemptive Penjadwalan berprioritas dinamis.
Penjadwalan Terjamin ( GS ) Penjadwalan ini merupakan : Penjadwalan preemptive menjadwalan berprioritas dinamis.
Penjadwalan  Earliest Deadline First (EDP) : Variasi yang diterpakan pada Sistem Waktu Nyata Karena sistem waktu nyata sering mempunyai deadline absolut, maka penjadwalan dapat berdasarkan deadline. Proses yang dijalankan yang mempunyai deadline terdekat. Proses yang lebih dalam bahaya kehilangan deadline dijalankan lebih dulu. Proses yang harus berakhir 10 detik lagi mendapat prioritas di atas proses yang harus berakhir 10 menit lagi.