A. Kriteria Penjadwal
Algoritma penjadwal CPU yang berbeda mempunyai property yang berbeda. Dalam memilih algoritma yang digunakan untuk situasi tertentu, kita harus memikirkan properti yang berbeda untuk algoritma yang berbeda. Banyak kriteria yang dianjurkan utnuk membandingkan penjadwal CPU algoritma. Kritria yang biasanya digunakan dalam memilih adalah:
1. CPU utilization: kita ingin menjaga CPU sesibuk mungkin. CPU utilization akan mempunyai range dari 0 ke 100 persen. Di sistem yang sebenarnya seharusnya ia mempunyai range dari 40 persen samapi 90 persen.
2. Throughput: jika CPU sibuk mengeksekusi proses, jika begitu kerja telah dilaksanakan. Salah satu ukuran kerja adalah banyak proses yang diselesaikan per unit waktu, disebut througput. Untuk proses yang lama mungkin 1 proses per jam; untuk proses yang sebentar mungkin 10 proses perdetik.
3. Turnaround time: dari sudur pandang proses tertentu, kriteria yang penting adalah berapa lama untuk mengeksekusi proses tersebut. Interval dari waktu yang diizinkan dengan waktu yang dibutuhkan untuk menyelesaikan sebuah prose disebut turn-around time. Trun around time adalah jumlah periode untuk menunggu untuk bisa ke memori, menunggu di ready queue, eksekusi di CPU, dan melakukan I/O.
4. Waiting time: algoritma penjadwal CPU tidak mempengaruhi waktu untuk melaksanakan proses tersebut atau I/O; itu hanya mempengaruhi jumlah waktu yang dibutuhkan proses di antrian ready. Waiting time adalah jumlah periode menghabiskan di antrian ready.
5. Response time: di sistem yang interaktif, turnaround time mungkin bukan waktu yang terbaik untuk kriteria. Sering sebuah proses bisa memproduksi output diawal, dan bisa meneruskan hasil yang baru sementara hasil yang sebelumnya telah diberikan ke user. Ukuran yang lain adalah waktu dari pengiriamn permintaan sampai respon yang pertama di berikan. Ini disebut response time, yaitu waktu untuk memulai memberikan respon, tetapi bukan waktu yang dipakai output untu respon tersebut. Biasanya yang dilakukan adalah memaksimalkan CPU utilization dan throughput, dan minimalkan turnaround time, waiting time, dan response time dalam kasus tertentu kita mengambil rata-rata.
B. Dispatcher
Komponen yang lain yang terlibat dalam penjadwalan CPU adalah dispatcher. Dispatcher adalah modul yang memberikan kontrol CPU kepada proses yang sedang terjadwal. Fungsinya adalah:
1. Context switching . Mengganti state dari suatu proses dan mengembalikannya untuk menghindari monopoli CPU time. Context switching dilakukan untuk menangani suatu interrupt(misalnya menunggu waktu M/K). Untuk menyimpan state dari proses-proses yang terjadwal sebuah Process Control Block harus dibuat untuk mengingat proses-proses yang sedang diatur scheduler. Selain state suatu proses, PCB juga menyimpan process ID, program counter(posisi saat ini pada program), prioritas proses dan data-data tambahan lainnya.
2. Switching to user mode dari kernel mode.
3. Lompat dari suatu bagian di progam user untuk mengulang program.
Gambar 13.2. Dispatch Latency
Dispatcher seharusnya dapat dilakukan secepat mungkin. Dispatch Latency adalah waktu yang diperlukan dispatcher untuk menghentikan suatu proses dan memulai proses yang lain.
A. Algoritma Penjadwalan
First Come, First Served
Penjadwal CPU berurusan dengan permasalahan memutuskan proses mana yang akan dillaksanakan, oleh karena itu banyak bermacam algoritma penjadwal, di seksi ini kita akan mendiskripsikan beberapa algoritma. Ini merupakan algoritma yang paling sederhana, dengan skema proses yang meminta CPU mendapat prioritas. Implementasi dari FCFS mudah diatasi dengan FIFO queue.
Contoh:
Gambar 2-27. Kedatangan Proses
misal urutan kedatangan adalah P1, P2, P3 Gantt Chart untuk ini adalah:
Gambar 2-28. Gannt Chart Kedatangan Proses I
Gambar 2-29. Gannt Chart Kedatangan Proses II
misal proses dibalik sehingga urutan kedatangan adalah P3, P2, P1.
Gantt chartnya adalah: 53
Gambar 2-30. Gannt Chart Kedatangan Proses III
Gambar 2-31. Gannt Chart Kedatangan Proses IV
Dari dua contoh diatas bahwa kasus kedua lebih baik dari kasus pertama, karena pengaruh kedatangan disamping itu FCFS mempunyai kelemahan yaitu convoy effect dimana seandainya ada sebuah proses yang kecil tetapi dia mengantri dengan proses yang membutuhkan waktu yang lama mengakibatkan proses tersebut akan lama dieksekusi. Penjadwal FCFS algoritma adalah nonpremptive. Ketika CPU telah dialokasikan untuk sebuah proses, proses tetap menahan CPU sampai selssai. FCFS algortima jelas merupakan masalah bagi system time-sharing, dimana sangat penting untuk user mendapatkan pembagian CPU pada regular interval. Itu akan menjadi bencana untuk megizinkan satu proses pada CPU untuk waktu yang tidak terbatas.
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.
Priority Schedulling (jadwal prioritas)
Penjadwalan SJF (Shortest Job First) adalah kasus khusus untuk algoritma penjadwal Prioritas. Prioritas dapat diasosiasikan masing-masing proses dan CPU dialokasikan untuk proses dengan prioritas tertinggi. Untuk proritas yang sama dilakukan dengan FCFS.
Ada pun algoritma penjadwal prioritas adalah sebagai berikut:
• Setiap proses akan mempunyai prioritas (bilangan integer). Beberapa sistem menggunakan integer dengan urutan kecil untuk proses dengan prioritas rendah, dan sistem lain juga bisa menggunakan integer urutan kecil untuk proses dengan prioritas tinggi. Tetapi dalam teks ini diasumsikan bahwa integer kecil merupakan prioritas tertinggi.
• CPU diberikan ke proses dengan prioritas tertinggi (integer kecil adalah prioritas tertinggi).
• Dalam algoritma ini ada dua skema yaitu:
1. Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan CPU.
2. Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain time-slice habis.
• SJF adalah contoh penjadwal prioritas dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya. Permasalahan yang muncul dalam penjadwalan prioritas adalah indefinite blocking atau starvation.
• Kadang-kadang untuk kasus dengan prioritas rendah mungkin tidak pernah dieksekusi. Solusi untuk algoritma penjadwal prioritas adalah aging.
• Prioritas akan naik jika proses makin lama menunggu waktu jatah CPU.
Contoh Priority:
Round Robin.
Algoritma Round Robin (RR) dirancang untuk sistem time sharing. Algoritma ini mirip dengan penjadwal FCFS, namun preemption ditambahkan untuk switch antara proses. Antrian ready diperlakukan atau dianggap sebagai antrian sirkular. CPU mengelilingi antrian ready dan mengalokasikan masing-masing proses untuk interval waktu tertentu sampai satu time slice/ quantum.
Berikut algoritma untuk penjadwal Round Robin:
• Setiap proses mendapat jatah waktu CPU (time slice/ quantum) tertentu Time slice/quantum umumnya antara 10 – 100 milidetik.
- Setelah time slice/ quantum maka proses akan di-preempt dan dipindahkan ke antrian ready.
- Proses ini adil dan sangat sederhana.
• Jika terdapat n proses di “antrian ready” 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 time units.
• Kinerja dari algoritma ini tergantung dari ukuran time quantum.
- Time Quantum dengan ukuran yang besar maka akan sama dengan FCFS.
- Time Quantum dengan ukuran yang kecil maka time quantum harus diubah ukurannya lebih besar dengan respek pada alih konteks sebaliknya akan memerlukan ongkos yang besar. Contoh :
- Tipikal: lebih lama waktu rata-rata turnaround dibandingkan SJF, tapi mempunyai response terhadap user lebih cepat.
Tidak ada komentar:
Posting Komentar