Penjadwalan Proses

Penjadwalan Proses

Penjadwalan merupakan kumpulan kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem computer. Penjadwalan bertugas memilih proses, menentukan kapan serta berapa lama proses tersebut boleh menggunakan prosesor.

Tujuan Penjadwalan Proses

1. Adil (fairness)
Proses-proses diperlakukan sama yaitu mendapat jatah waktu layanan pemroses yang sama dan tidak ada proses yang tidak kebagian layanan pemroses sehingga mengalami startvation.
Startvation adalah kondisi bahwa proses tidak pernah berjalan karena tidak dijadwalkan untuk berjalan. Sasaran penjadwalan seharusnya menjamin setiap proses mendapat pelayanan dari pemroses secara adil.

2. Efisiensi
Efisiensi atau utilisasi pemroses dihitung dengan perbandingan (rasio) waktu sibuk pemroses dengan total waktu operasi sistem komputer secara keseluruhan.
Sasaran penjadwalan adalah menjaga agar pemroses tetap dalam keadaan sibuk sehingga efisiensi sistem komputer mencapai nilai maksimum. Keadaan sibuk berarti pemroses tidak menganggur. Layanan pemroses termasuk waktu yang dihabiskan untuk mengeksekusi program pemakai dan layanan sistem operasi secara efektif, bukan untuk melakukan penjadwalan itu sendiri.

3. Waktu Tanggap (response time)
Waktu tanggap berbeda untuk :

• ·         Sistem interaktif

Waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukkan oleh program atau transaksi sampai hasil pertama muncul di jperangkat masukan keluaran seperti layar (terminal).Waktu tanggap untuk sistem interaktif biasa disebut terminal responce time.

• ·         Sistem waktu nyata (real time)

Pada sistem waktu nyata, waktu tanggap didefinisikan sebagai waktu dari saat kemunculan suatu kejadian (internal/eksternal) sampai instruksi pertama rutin layanan terhadap kejadian dieksekusi. Waktu untuk sistem waktu nyata biasa disebut event response time.
Sasaran penjadwalan adalah meminimalkan waktu tanggap sehingga menghasilkan sistem yang responsif.

4. Turn arround Time
Waktu yang dihabiskan dari saat proses atau job mulai masuk ke sistem sampai proses itu diselesaikan sistem.Waktu yang dimaksud adalah waktu yang dihabiskan proses berada di sistem, diekspresikan sebagai penjumlahan waktu eksekusi (waktu layanan proses/job).

5. Troughput
Troughput adalah jumlah kerja yang dapat diselsesaikan selama satu selang/ unit waktu. Cara untuk mengekspresikan throughput adalah dengan jumlah proses/job pemakai yang dapat dieksekusi dalam satu unit/ interval waktu tertentu.
Sasaran penjadwalan adalah memaksimalkan jumlah job/ proses yang dilayani per satu interval waktu. Lebih tinggi angka througput maka lebih banya kerja yang dilakukan sistem.
Kriteria tersebut saling bergantung dan dapat saling bertentangan sehingga tidak dimungkinkan optimasi semua kriteria secara simultan.

Tipe-Tipe Penjadwalan
Dapat terdapat 3 tipe penjadwal berada secara bersama-sama pada sistem operasi yang kompleks, yaitu :

1. Penjadwal jangka pendek (short-term scheduller).

Penjadwalan jangka pendek bertugas menjadwalkan alokasi pemroses di antara proses-proses Ready yang berada di memori utama. sasaran utama penjadwal jangka pendek adalah memaksimumkan kinerja sistem untuk memenuhi satu kumpulan kriteria yang diharapkan. Penjadwal ini dijalankan setiap terjadi pengalihan proses untuk memilih proses berikutnya yang harus dijalankan.

2. Penjadwal jangka menengah (medium-term scheduller).

Setelah eksekusi selama suatu waktu, proses mungkin ditunda karena permintaan layanan masukan/keluaran atau memanggil suatu system call. Proses-proses yang tertunda tidak dapat membuat suatu kemajuan untuk menuju selesai sampai ondisi yang menyebabkannya hilang. Agar ruang memori dapat bermanfaat maka proses dipindah dari memori utama ke memori sekunder sehingga tersedia ruang yang lebih besar untuk proses yang lain. Kapasitas memori utama terbatas untuk sejumlah proses yang aktif. Aktivitas pemindahan proses yang tertunda dari memori utama ke memori sekunder disebut swapping. Penjadwal jangka menengah bertugas menangani proses swapping . Proses yang mempunyai kepentingan kecil saat itu adalah proses yang tertunda. Tetapi begitu kondii yang membuat proses tertunda hilang dan proses dimasukkan kembali ke memori utama dan Ready. Penjadwal jangka menengah mengendalikan transisi dari suspended ke ready (dari state suspend ke Ready dari proses yang mengalami swapping).

3. Penjadwal jangka panjang (long-term scheduller).

Penjadwal jangka panjang bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi sistem. Batch biasanya berupa proses-proses dengan penggunaan sumber daya yang intensif (yaitu waktu pemroses, memori, perangkat masukan/keluaran), program ini mempunyai prioritas yang rendah, dan biasa digunakan sebagai pengisi (agar pemroses sibu) selama periode aktivitas proses-proses interaktif rendah. Sasaran utama penjadwal jangka panjang adalah memberi keseimbangan proses-proses campuran. Tipe-tipe penjadwal dapat dikaitkan dengan state proses.

Strategi Penjadwalan Terdapat 2 strategi penjadwalan, yaitu :

• ·         Penjadwalan nonpreemptive (run-to-completion). Begitu proses diberi jatah layanan pemroses aka pemroses tidak dapat diambil alih oleh proses lain sampai proses itu selesai. Non-preemptive juga disebut run-to-completion karena proses yang telah dijadwalkan akan dijalankan sampai selesainya atau proses tersebut meminta layanan masukan/keluaran.
• ·         Penjadwalan preemptive. Saat proses diberi jatah layanan pemroses maka pemroses dapat diambil alih proses lain yang mempunyai prioritas lebih tinggi berdasarkan kriteria sistem itu. Pada penjadwalan preemptive, proses dapat disela oleh proses lain sebelumnya selesainya dan harus dilanjutkan menunggu jatah waktu layanan pemroses tiba kembali pada proses itu. Proses yang disela berubah menjadi state Ready.

·         Penjadwalan preemptive berguna pada sistem yakni proses-proses yang perlu mendapat perhatian/ tanggapan pemroses secara cepat. Misalnya :

• Pada sistem-sistem waktu nyata, kehilangan interupsi (yaitu interupsi tidak segera dilayani) dapat berakibat fatal
• Pada sistem-sistem interatif timesharing, penjadwalan preemptive penting agar dapat menjamin waktu tanggap yang memadai.

Peralihan proses (yaitu layanan pemroses dari satu proses beralih ke proses lain) memerlukan overhead (karena banya tabel yang dikelola). Agar penjadwalan preemptive menjadi efektif, banyak proses harus berada di memori utama sehingga proses-proses tersebut dapat segera Running begitu diperlukan. Menyimpan banyak proses yang tidak Running di memori utama merupakan suatu overhead tersendiri.

Algoritma Penjadwalan Proses

Setiap algoritma diukur “turnaround time” dan “waiting time” untuk membandingkan performansi dengan algoritma lain. Dan untuk mengukur turnaround time dan waiting time, digunakan “Gant Chart” . CPU time (Burst Time) membutuhkan semua proses diasumsikan diketahui. Arrival time untuk setiap proses pada ready queue diasumsikan diketahui.

·         Algoritma Penjadwalan First Come, First Served (FCFS)

Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu. Dan rata-rata waktu tunggu (Average waiting time) cukup tinggi. Algoritma penjadwalan FCFS merupakan salah satu strategi penjadwalan non-Preemptive karena sekali CPU dialokasikan pada suatu proses, maka proses tersebut akan tetap memakai CPU sampai proses tersebut melepaskannhya, yaitu jika proses berhenti atau meminta I/O. Kelemahan dari Algoritma penjadwalan ini adalah adanya convoy effect. skema proses yang meminta CPU mendapat prioritas. Implementasi dari FCFS mudah diatasi dengan FIFO queue. Contoh :

urutan kedatangan adalah P1, P2, P3 Gant Chart ini adalah :

Waiting time for P1 = 0; P2 = 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 misal proses dibalik sehingga urutan kedatangan adalah P2, P3, P1. Gant Chartnya adalah :

• ·         Algoritma Shortest Job First Scheduler

Algoritma ini digunakan ketika CPU bebas proses yang mempunyai waktu terpendek untuk menyelesaikannya mendapat prioritas. Seandainya dua proses atau lebih mempunyai waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah tersebut. Prinsip algoritma penjadwalan ini adalah, proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu. Oleh karena itu, algoritma ini optimal jika digunakan, tetapi sulit untuk diimplementasikan karena sulit mengetahui CPU burst selanjutnya. Ada dua skema dalam SJFS ini yaitu:

1.       Non premptive— ketika CPU memberikan kepada proses itu tidak bisa ditunda hingga selesai.

2.       premptive— bila sebuah proses datang dengan waktu proses lebih rendah dibandingkan dengan waktu proses yang sedang dieksekusi oleh CPU maka proses yang waktunya lebih rendah mendapatkan prioritas. Skema ini disebut juga Short – Remaining Time First (SRTF). Contoh :

Average waiting time = (0 + 6 + 3 + 7)/4 = 4

• ·         Algoritma Penjadwalan Priority Schedulling (jadwal prioritas)

Penjadualan SJF (Shortest Job First) adalah kasus khusus untuk algoritma penjadual 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 penjadual prioritas adalah sebagai berikut:

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

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

3.   SJF adalah contoh penjadual prioritas dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya. Permasalahan yang muncul dalam penjadualan prioritas adalah indefinite blocking atau starvation.

4.  Kadang-kadang untuk kasus dengan prioritas rendah mungkin tidak pernah dieksekusi. Solusi untuk algoritma penjadual prioritas adalah aging.

5.  Prioritas akan naik jika proses makin lama menunggu waktu jatah CPU. Contoh Priority:

·         Algoritma Penjadwalan Round Robin.

Algoritma Round Robin (RR) dirancang untuk sistem time sharing. Algoritma ini mirip dengan penjadual 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 penjadual 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 :