Penjadwalan Sistem Informasi

Algoritma FIFO (First In First Out)

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.

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.

Algoritma Penjadwalan : Shortest Job First (SJF)

Shortest Job First (SJF) Merupakan penjadwalan tidak berprioritas dan Non Preventive. Maksud Non Preveentive disini ialah ketika proses diberi jatah waktu penggunaan prosessor maka processor tidak dapat diambil proses lain, sampai proses tersebut selesai di eksekusi. Penjadwalan ini mengasumsikan waktu jalan proses sampai selesai diketahui sebelumnya. Mekanismenya adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi dan turn around time rendah. Dalam artian waktu yang digunakan saat program (job) mulai masuk ke system sampai proses diselesaikan system, membutuhkan waktu yang singkat. Shortest Job First (SJF) bisa dikatakan algoritma penjadwalan yang optimal dengan rata-rata waktu tunggu yang minimal.
Misalnya terdapat empat proses dengan CPU Burst dalam milidetik.

::Proses dengan CPU Burst dalam milidetik::

Penjadwalan proses dengan algoritma SJF (non-Preventive) dapat dilihat dalam gant chart berikut :

::Gant chart algoritma SJF (non-Preventive)::

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
Contoh lain untuk algoritma Shortest Job First (SJF), misalnya terdapat empat proses (job) yaitu A,B,C,D dengan waktu jalannya masing-masing adalah 8,4,4 dan 4 menit. Apabila proses-proses tersebut dijalankan, maka turn around time untuk A adalah 8 menit, untuk B adalah 12, untuk C adalah 16 dan untuk D adalah 20. Apabila keempat proses tersebut menggunakan penjadwalan shortest job fisrt, maka turn around time untuk B adalah 4, untuk C adalah 8, untuk D adalah 12 dan untuk A adalah 20.
Karena SJF selalu memperhatikan rata-rata waktu respon terkecil, maka sangat baik untuk proses interaktif. Umumnya proses interaktif memiliki pola, yaitu menunggu perintah, menjalankan perintah, menunggu perintah dan menjalankan perintah, begitu seterusnya. Masalah yang muncul saat menggunakan algoritma ini adalah tidak mengetahui ukuran job saat job masuk. Untuk mengetahui ukuran job adalah dengan membuat estimasi atau perkiraan berdasarkan kelakukan sebelumnya. Prosesnya tidak datang bersamaan, sehingga penetapannya harus dinamis.
Permasalahan lain yang muncul dalam algoritma ini adalah bisa saja saat kondisi-kondisi tertentu, suatu job mungkin tidak pernah menyelesaikan eksekusinya. Saya beri contoh, misalnya terdapat proses A dengan elapse time 1 jam tiba pada waktu 0. Namun pada waktu yang bersamaan dan setiap satu menit berikutnya tiba proses singkat dengan elapse time 2 menit. Hasilnya, bisa saja proses A tidak pernah mendapat jatah eksekusi.


Algoritma Round-Robin (RR) 


Eksekusi proses dilakukan berdasarkan alokasi waktu tertentu yang diatur dengan clock interrupt.
Kelebihan :
- Dapat menghindari ketidakadilan layanan terhadap proses kecil seperti yang telah terjadi pada FCFS
- Response time lebih cepat untuk proses yang berukuran kecil
- Dapat mencegah starvation
- Overhead kecil, jika ukuran proses rata-rata lebih kecil dibandingkan quantum / slot
Kekurangan :
- Performa lebih buruk dibandingkan FCFS jika ukuran slot lebih besar daripada ukuran proses terbesar
- Dapat terjadi overhead berlebihan jika ukuran setiap slot terlalu kecil
- Proses I/O bound mendapatkan layanan lebih sedikit
Contoh :
Berikut adalah contoh kasus seperti pada FCFS namun diselesaikan dengan metode Round-Robin dengan quantum = 1

Process	A	B	C	D	E	Mean
Finsih Time	4	18	17	20	15
Arival Time	0	2	4	6	8
TAT	4	16	13	14	7	10.80
Service Time	3	6	4	5	2
NTAT	1.33	2.67	3.25	2.80	3.50	2.71

 

Algoritma Penjadwalan Multiple Feedback Queue (MFQ) 

 

Ide dasar dari algoritma ini berdasarkan pada sistem prioritas proses. Prinsipnya, jika setiap proses dapat dikelompokkan berdasarkan prioritasnya, maka akan didapati queue seperti pada gambar berikut:

Dari gambar tersebut terlihat bahwa akan terjadi pengelompokan proses-proses berdasarkan prioritasnya. Kemudian muncul ide untuk menganggap kelompok-kelompok tersbut sebagai sebuah antrian-antrian kecil yang merupakan bagian dari antrian keseluruhan proses, yang sering disebut dengan algoritma multilevel queue.
Dalam hal ini, dapat dilihat bahwa seolah-olah algoritma dengan prioritas yang dasar adalah algoritma multilevel queue dimana setiap queue akan berjalan dengan algoritma FCFS yang memiliki banyak kelemahan. Oleh karena itu, dalam prakteknya, algoritma multilevel queue memungkinkan adanya penerapan algoritma internal dalam masing-masing sub-antriannya yang bisa memiliki algoritma internal yang berbeda untuk meningkatkan kinerjanya.
Berawal dari priority scheduling, algoritma ini pun memiliki kelemahan yang sama dengan priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dengan prioritas rendah bisa saja tidak mendapat jatah CPU. Untuk mengatasi hal tersebut, salah satu caranya adalah dengan memodifikasi algoritma ini dengan adanya jatah waktu maksimal untuk tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan dan digantikan oleh antrian dibawahnya, dan tentu saja batas waktu untuk tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian.

MFQ (Multiple Feedback Queue)
Algoritma ini mirip sekali dengan algoritma multilevel queue. Perbedaannya ialah algoritma ini mengizinkan proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke antrian yang lebih rendah. Hal ini menguntungkan proses interaksi karena proses ini hanya memakai waktu CPU yang sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan tingkatannya. Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil, dengan begitu CPU akan terutilisasi penuh dan M/K dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga semakin besar.

Algoritma ini didefinisikan melalui beberapa parameter, antara lain:
1. Jumlah antrian.
2. Algoritma penjadwalan tiap antrian.
3. Kapan menaikkan proses ke antrian yang lebih tinggi.
4. Kapan menurunkan proses ke antrian yang lebih rendah.
5. Antrian mana yang akan dimasuki proses yang membutuhkan.

Dengan pendefinisian seperti tadi membuat algoritma ini sering dipakai, karena algoritma ini mudah dikonfigurasi ulang supaya cocok dengan sistem. Tapi untuk mengatahui mana penjadwal terbaik, kita harus mengetahui nilai parameter tersebut.
Multilevel feedback queue adalah salah satu algoritma yang berdasar pada algoritma multilevel queue. Perbedaan mendasar yang membedakan multilevel feedback queue dengan multilevel queue biasa adalah terletak pada adanya kemungkinan suatu proses berpindah dari satu antrian ke antrian lainnya, entah dengan prioritas yang lebih rendah ataupun lebih tinggi, misalnya pada contoh berikut.
1. Semua proses yang baru datang akan diletakkan pada queue 0 ( quantum= 8 ms).
2. Jika suatu proses tidak dapat diselesaikan dalam 8 ms, maka proses tersebut akan dihentikan dan dipindahkan ke queue 1 ( quantum= 16 ms).
3. Queue 1 hanya akan dikerjakan jika tidak ada lagi proses di queue 0, dan jika suatu proses di queue 1 tidak selesai dalam 16 ms, maka proses tersebut akan dipindahkan ke queue 2.
4. Queue 2 akan dikerjakan bila queue 0 dan 1 kosong, dan akan berjalan dengan algoritma FCFS.

Disini terlihat bahwa ada kemungkinan terjadinya perpindahan proses antar queue, dalam hal ini ditentukan oleh time quantum, namun dalam prakteknya penerapan algoritma multilevel feedback queue akan diterapkan dengan mendefinisikan terlebih dahulu parameter-parameternya, yaitu:
1. Jumlah antrian.
2. Algoritma internal tiap queue.
3. Aturan sebuah proses naik ke antrian yang lebih tinggi.
4. Aturan sebuah proses turun ke antrian yang lebih rendah.
5. Antrian yang akan dimasuki tiap proses yang baru datang.

Contoh:
Terdapat tiga antrian; Q1=10 ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam 40 ms tidak selesai, maka dipindahkan lagi ke Q3. Berdasarkan hal-hal di atas maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan kebutuhan sistem. Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.

 

 

Penjadualan CPU

Shortest Remaining Time First

ALGORITMA PENJADWALAN

Penjadwalan berkaitan dengan permasalahan memutuskan proses mana yang akan dilaksanakan dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Algoritma penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan dieksekusi oleh CPU. Bagian berikut ini akan memberikan ilustrasi beberapa algoritma penjadwalan.

Rujukan

[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005 . Operating Systems Concepts. Seventh Edition. John Wiley & Sons.

[Scheduling] Moonbase. 1991 . Scheduling– http://moonbase.wwc.edu/~aabyan/352/Scheduling.html. Diakses 20 Februari 2007.



Algoritma Higest Ratio Next (HRN)


Higest Ratio Next (HRN) Merupakan penjadwalan untuk mengoreksi kelemahan SJF yang berprioritas dinamis. HRN Adalah strategi penjadwalan dengan prioritas proses tidak hanya merupakan fungsi waktu layanan,tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, maka proses berjalan sampai selesai. Prioritas dinamis HRN dihitung berdasarkan rumus berikut : Prioritas = (waktu tunggu + waktu layanan ) / waktu layanan. Karena waktu layanan muncul sebagai pembagi, maka job lebih pendek berprioritas lebih baik, karena waktu tunggu sebagai pembilang, maka proses yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus. Mengapa algoritma ini disebut HRN karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayani.


Algoritma PS (Priority Schedulling)


tentang PS (Priority schedulling)
Setiap proses diberi prioritas dan proses yang berprioritas tertinggi mendapat jatah waktu lebih dulu (running). Diasumsikan bahwa masing-masing proses memiliki prioritas tertentu, sehingga akan dilaksanakan berdasar prioritas yang dimilikinya. Ilustrasi yang dapat memperjelas prioritas tersebut adalah dalam komputer militer, dimana proses dari jendral berprioritas 100, proses dari kolonel 90, mayor berprioritas 80, kapten berprioritas 70, letnan berprioritas 60 dan seterusnya. Dalam UNIX perintah untuk mengubah prioritas menggunakan perintah nice. Pemberian prioritas diberikan secara:
1)      Statis (Static Priorities) berarti prioritas tidak berubah.
Keunggulan :
• Mudah diimplementasikan.
• Mempunyai overhead relatif kecil.
Kelemahan :
• Tidak tanggap terhadap perubahan lingkungan yang mungkin menghendaki penyesuaian prioritas.
2)      Dinamis (Dynamic Priorities) merupakan mekanisme untuk menanggapi perubahan lingkungan system beroperasi. Prioritas awal yang diberikan ke proses mungkin hanya berumur pendek setelah disesuaikan ke nilai yang lebih tepat sesuai lingkungan.
Kelemahan :
Implementasi mekanisme prioritas dinamis lebih kompleks dan mempunyai overhead lebih besar. Overhead ini diimbangi dengan peningkatan daya tanggap sistem.
Contoh penjadwalan berprioritas :
Proses-proses yang sangat banyak operasi masukan/keluaran menghabiskan kebanyakan waktu menunggu selesainya operasinya masukan/keluaran. Proses-proses ini diberi prioritas sangat tinggi sehingga begitu proses Memerlukan pemroses segera diberikan, proses akan segera memulai permintaan masukan/keluaran berikutnya sehingga menyebabkan proses blocked menunggu selesainya operasi masukan/keluaran. Dengan demikian pemroses dapat dipergunakan proses-proses lain. Proses-proses I/O berjalan paralel bersama proses-proses lain yang benar-benar memerlukan pemroses, sementara proses-proses I/O itu menunggu selesainya operasi DMA.
Proses-proses yang sangat banyak operasi I/O-nya, kalau harus menunggu lama untuk memakai pemroses (karena prioritas rendah) hanya akan membebani memori, karena harus disimpan tanpa perlu proses-proses itu dimemori karena tidak selesai-selesai menunggu operasi masukan dan menunggu jatah pemroses.




  GS (Guaranteed Schedulling)

 
Penjadwalan GS ini adalah:
a) Penjadwalan preemptive
b) Penjadwalan berprioritas dinamis
Penjadwalan ini berupaya memberi masing-masing pemakai daya pemroses tang sama.. Jika terdapat N pemakai maka tiap pemakai diupayakan mendapat 1/N daya pemroses. Sistem merekam banyak waktu pemroses yang telah digunakan proses sejak login dan jumlah waktu pemroses yang digunakan seluruh proses. Karena jumlah waktu pemroses tiap pemakai dapat diketahui maka dapat dihitung rasio antara waktu pemroses yang sesungguhnya harus diperoleh yaitu 1/N. Waktu pemroses seluruhnya dan waktu pemroses yang telah diperuntukan prose situ. Penjadwalan akan menjalankan proses dengan rasio terendah sampai rasio proses diatas pesaing terdekatnya. Variasi yang ditetapkan pada Sistem Waktu Nyata Karena sistem waktu nyata sering mempunyai deadline absolut maka penjadwalan dapat berdasarkan deadline terdekat. Proses yang lebih dalam bahaya kehilangan deadline dijalankan lebih dahulu. Proses yang berakhir 10 detik lagi mendapat prioritas lebih tinggi dibanding yang berakhir 10 menit lagi.
Strategi penjadualan berprioritas merupakan strategi penjadualan nonpreemtive, sehingga dalam hal ini apabila pemroses melakukan eksekusi proses yang berkaitan dengan operasi pada beberapa peripheral I/O secara bersamaan maka pemroses tidak dapat diambil alih oleh proses lain sampai proses itu selesai. Dalam artian, eksekusi proses dilakukan secara bergantian pada beberapa I/O tersebut dan tidak dapat dilakukan secara bersamaan.
Sedangkan untuk strategi penjadualan terjamin (GS) merupakan salah satu contoh algoritma strategi penjadualan preemptive, sehingga apabila pemroses melakukan eksekusi proses yang berkaitan dengan operasi pada beberapa peripheral I/O secara bersamaan maka pemroses dapat diambil alih proses lain, sehingga proses disela sebelum selesai dan harus dilanjutkan menunggu jatah waktu pemroses tiba kembali pada proses itu. Dalam artian, apabila proses menginginkan suatu eksekusi diselesaikan maka proses dapat disela tanpa harus menunggu proses lain yang sedang berjalan selesai.




Logaritma Gs
1.1 Perbedaan strategi penjadualan berprioritas dan penjadualan terjamin.
Dari kedua strategi penjadualan ini terdapat beberapa perbedaan ketika penjadualan tersebut bekerja pada peripheral I/O. Perbedaan tersebut antara lain:
a. Penjadualan berprioritas
Untuk penjadualan berprioritas merupakan salah satu contoh algoritma strategi penjadualan nonpreemtive. Dalam penjadualan ini proses yang telah diberi jatah layanan pemroses maka pemroses tidak dapat diambil alih oleh proses lain sampai proses itu selesai. Beberapa contoh algoritma yang menggunakan strategi penjadualan nonpreemtive yaitu: FIFO (Fist in,Fist Out) atau FCFS (Fist Come,Fist Serve) dan SJF (Shortest Job First).

b. Penjadualan terjamin
Untuk penjadualan berprioritas merupakan salah satu contoh algoritma strategi penjadualan preemtive. Dalam penjadualan ini, proses diberi jatah waktu oleh pemroses, maka pemroses dapat diambil alih proses lain, sehingga proses disela sebelum selesai dan harus dilanjutkan menunggu jatah waktu pemroses tiba kembali pada proses itu. Contoh algoritma yang menggunakan strategi penjadualan ini yaitu: RR (Round-Robin), MFQ (Multiple-Feedback -Queues), SRF (Shortes-Remaining-First), HRN (Highest-Ratio Next), PS (Priority Schedulling), GS (Guaranteed Schedulling).