PENJADWALAN PROSES

1 Deskripsi Penjadwalan Proses

                Penjadwalan merupakan kumpulan dan mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer. Penjadwalan bertugas memutuskan:

•        Proses yang harus berjalan

•       Kapan dan selama berapa lama proses itu berjalan

Sasaran Utama Penjadwalan Proses

Optimasi kinerja menurut kriteria tertentu.

Kriteria untuk mengukur dan optimasi kinerja penjadwalan :

1. Adil (fairness), proses – proses diperlakukan sama yaitu mendapat jatah pemroses yang sama dan tak ada proses yang tak kebagian layanan pemroses sehingga mengalami startvation. Sasaran penjadwalan seharusnya menjamin tiap proses mendapat pelayanan dari pemroses yang adil.
2. Efisiensi, Efisiensi atau utilisasi pemroses dihitung dengan perbandingan (rasio) waktu sibuk pemroses. Sasaran penjadwalan menjaga agar pemroses tetap dalam keadaan sibuk sehingga efisiensi mencapai maksimum.
3. Waktu Tanggap (Response Time)

Waktu tanggap berbeda untuk:

-          Sistem Interaktif

-          Sistem waktu nyata

Waktu tanggap pada sistem interaktif

Waktu tanggap dalam sistem interaktif didefinisikan sebagai waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukkan atau transaksi sampai hasil terakhir muncul di layar (terminal).

Waktu tanggap ini disebut juga terminal rensponse time.

Waktu tanggap pada sistem waktu nyata

Pada sistem waktu nyata (real-time), waktu tanggap didefinisikan sebagai waktu dari saat kejadian (internal atau eksternal) sampai instruksi pertama rutin layanan yang dimaksud dieksekusi, disebut juga event response time.

Sasaran penjadwalan adalah meminimalkan waktu tanggapnya

5. Turn Arround Time

Turn arround time adalah waktu yang dihabiskan dari saat program atau job mulai masuk ke sistem sampai proses diselesaikan sistem.

Waktu yang dimaksud adalah waktu yang dihabiskan di dalam sistem, diekspresikan sebagai penjumlahan waktu eksekusi (waktu pelayanan job) dan waktu menunggu.

Turn arround time = waktu eksekusi + waktu menunggu

Sasaran penjadwalan adalah meminimalkan turn arround time.

6. Throughput

Throughput adalah jumlah kerja yang dapat diselesaikan dalam satu unit waktu. Cara untuk mengekspresikan throughput adalah dengan jumlah job pemakai yang dapat dieksekusi dalam satu unit/interval waktu.

Sasaran penjadwalan adalah memaksimalkan jumlah job yang diproses per satu interval waktu. Lebih tinggi angka throughput, lebih banyak kerja yang dilakukan sistem.

2 TIPE-TIPE PENJADWALAN

Terdapat tiga tipe penjadwalan berada secara bersama-sama pada sistem operasi yang kompleks, yaitu:

1. Penjadwalan jangka pendek (short-term scheduller)
2. Penjadwalan jangka menengah (medium-term scheduller)
3. Penjadwalan jangka panjang (long-term scheduller)

Penjadwalan Jangka Pendek

Penjadwalan ini bertugas menjadwalkan alokasi pemroses diantara proses-proses ready di memori utama.

Sasaran utama penjadwalan ini memaksimumkan kinerja untuk memenuh satu  kumpulan kriteria yang diharapkan. Penjadwalan ini dijalankan setiap terjadi pengalihan proses untuk memilih proses berikutnya  yang harus dijalankan.

Penjadwalan jangka menengah

                Setelah eksekusi selama suatu waktu, proses mungkin ditunda karena membuat permintaan layanan I/O atau memanggil suatu system call.

                Agar ruang memori bermanfaat, maka proses dipindahkan dari memori utama ke memori skunder agar tersedia ruang untuk proses-proses lain

                aktivitas pemindahan proses yang ditunda dari memori utama ke memori sekunder dsb swapping

Penjadwal jangka menengah:

•       Menangani proses-proses swapping

•       Mengendalikan transisi dari suspended-to-ready proses-proses swapping

            Begitu penyebab tertunda hilang maka proses dimasukan kembali ke memori utama dan ready

Penjadwalan jangka panjang

                Penjadwalan jangka panjang bekerja terhadap antrian batch dan memilih batch berikutnya yang harus di eksekusi.

                Batch biasanya adalah proses-proses dengan penggunaan sumber daya yang intensif (yaitu waktu pemroses, memori, perangkat masukan atau keluaran), program-program ini berprioritas rendah, digunakan sebagai pengisi (agar pemroses sibuk) selama periode aktifitas job-job interaktif rendah.

              Sasaran utama penjadwalan jangka panjang adalah memberi keseimbangan job-job campuran.

3 STRATEGI  PENJADWALAN

Terdapat 2 strategi penjadwalan, yaitu:

1. Penjadwalan nonpreemptive (run-to-completion)
2. Penjadwalan Preemptive

Penjadwalan nonpreemptive

                Begitu proses diberi jatah waktu pemroses maka pemroses tidak dapat diambil alih oleh proses lain sampai proses itu selesai.

Penjadwalan preemptive

                Saat proses diberi jatah waktu 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.

Penjadwalan preemptive berguna pada sistem dimana proses-proses yang 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 interaktif time-sharing, penjadwalan preemptive penting agar dapat menjamin waktu tanggap yang memadai.

4 Algoritma-algoritma Penjadwalan

•       Terdapat banyak algoritma penjadwalan, baik nonpreemptive maupun preemptive .

•       Algoritma-algoritma yang menerapkan strategi nonpreemptive di antaranya:

•       FIFO (First-in,First out) atau FCFS (First-come,First serve).

•       SJF (Shortest Job First).

•       HRN (Highest-Ratio Next).

•       MFQ(Multiple Feedback Queues).

•       Algoritma-algoritma yang menerapkan strategi preemptive di antaranya:

•       RR (Round-Robin).

•        SRF  (Shortest-Remaining-First).

•        PS  (Priority Schedulling).

•        GS (Guaranteed Schedulling).

Klasifikasi lain selain berdasarkan dapat/tidaknya suatu proses diambil alih secara paksa adalah klasifikasi berdasarkan adanya prioritas di proses-proses, yaitu:

1.  Algoritma penjadwalan tanpa berprioritas.
2.  Algoritma penjadwalan berprioritas,terdiri dari:

•        Algoritma penjadwalan  berprioritas statik.

•        Algoritma penjadwalan berprioritas dinamis.

4.1  Penjadwalan Round-Robin (RR)

Penjadwalan ini merupakan:

•        Penjadwalan preemptive, bukan di-preempt  oleh proses lain tapi oleh penjadwal berdasarkan lama waktu berjalannya proses, disebut preempt-by-time.

•        Penjadwalan tanpa prioritas.

•       Semua proses dianggap penting dan diberi sejumlah waktu pemroses yang disebut kwanta (quantum) atau time-slice dimana proses itu berjalan.

Ketentuan

Ketentuan algoritma round robin adalah sebagi berikut:

1. Jika kwanta habis dan proses belum selesai maka proses menjadi runnable dan pemroses dialihkan ke proses lain
2. Jika kwanta belum habis dan proses menunggu suatu kejadian (selesainya operasi I/O), maka proses menjadi blocked  dan pemroses dialihkan ke proses lain.

3. Jika kwanta belum habis tapi proses telah selesai maka proses diakhiri dan pemroses di alihkan ke proses lain

Algoritma penjadwalan ini dapat diimplementasi sebagai berikut:

•       Mengelola senarai proses ready (runnable) sesuai urutan kedatangan.

•       Ambil proses yang berada di ujung depan antrian menjadi running.

•       Bila kwanta belum habis dan proses selesai maka ambil proses diujung depan antrian proses ready.

•       Jika kwanta habis dan proses belum selesai maka tempatkan proses running ke ekor antrian proses ready dan ambil proses di ujung depan antrian proses ready.

Masalah penjadwalan ini adalah menentukan besar kwanta, yaitu :

•       Kwanta terlalu besar menyebabkan waktu tanggap besar dan turn arround time rendah.

•       Kwanta terlalu kecil mengakibatkan peralihan proses terlalu banyak sehingga menurunkan efisiensi pemroses.

Harus ditetapkan kwanta waktu yang optimal berdasar kebutuhan sistem terutama dari hasil percobaan atau data historis. Besar kwanta waktu beragam bergantung beban sistem. 

Berdasarkan kriteria penilaian penjadwalan :

•       Fairness

    Penjadwalan RR adil bila dipandang dari persamaan pelayanan oleh pemroses.

•       Efisiensi

    Penjadwalan RR cenderung efisien pada sistem interaktif.

•       Waktu tanggap (response time)

    Penjadwalan RR memuaskan untuk sistem interaktif, tidak memadai untuk sistem waktu nyata.

•       Turn arround time

    Penjadwalan RR cukup bagus.

•       Throughput

                Penjadwalan RR cukup bagus.

Penggunaan

•       cocok untuk sitem interactive-time sharing dimana kebanyakan waktu program adalah untuk menunggu keyboard, sehingga dapat dijalankan proses-proses lain.

4.2 PenjadwalanFIFO(first-in,first-out)

Penjadwalan ini merupakan:

•       Penjadwalan non-preemptive (run-to-completion).

•       Penjadwalan tidak berprioritas.

Ketentuan

Penjadwalan FIFO adalah penjadwalan paling sederhana, yaitu :  

•       Proses-proses diberi jatah waktu pemroses berdasarkan waktu kedatangan.

•       Begitu proses mendapat jatah waktu pemroses, proses dijalankan sampai selesai.

Penjadwalan ini dikatakan adil dalam arti resmi (dalam semantiks / arti antrian, yaitu proses yang datang duluan, dilayani duluan juga), tapi dinyatakan tak adil karena job-job yang perlu waktu lama membuat job-job pendek menunggu. Job-job tak penting dapat membuat job-job penting menunggu.

FIFO jarang digunakan secara mandiri tapi dikombinasikan dengan skema lain, misalnya:

•       Keputusan berdasarkan prioritas proses. Untuk proses-proses berprioritas sama diputuskan berdasarkan FIFO.

Berdasarkan kriteria penilaian penjadwalan.

•       Fairness

Penjadwalan FIFO adil bila dipandang dari semantik antrian.

•       Efisiensi

Penjadwalan FIFO sangat efisiensi.

•       Waktu tanggap(response time)

Penjadwalan FIFO sangat jelek, tidak cocok untuk sistem interaktif apalagi waktu nyata.

•       Turn arround time

                Penjadwalan FIFO jelek.

•       Throughput

                Penjadwalan FIFO jelek.

Penggunaan

•       cocok untuk sistem batch yang sangat jarang interaksi dengan pemakai. Contoh aplikasi aplikasi analisis numerik, pembuatan tabel.

•       Penjadwalan ini sama sekali tak berguna untuk sistem interaktif karena tidak memberi waktu tanggap yang bagus.

4.3 Penjadwalan Berprioritas (ps)

•       Ide penjadwalan adalah tiap proses diberi prioritas dan proses berprioritas  tertinggi running (mendapat jatah waktu pemroses).

•       Prioritas dapat diberikan secara:

•       Prioritas statis (static priorities).

•       Prioritas dinamis (dynamic priorities).

Prioritas statis

                prioritas statis berarti  prioritas tak berubah.

Keunggulan

•       Mudah diimplementasikan.

•       Mempunyai overhead relatif kecil.

Kelemahan

•       Penjadwalan tak tanggap perubahan lingkungan yang mungkin menghendaki  penyesuaian prioritas.

Prioritas Dinamis

                Prioritas dinamis merupakan mekanisme menanggapi perubahan lingkungan sistem 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 I/O  menghabiskan kebanyakan waktu menunggu selesainya operasi I/O.

                Proses-proses ini diberi prioritas sangat tinggi sehingga  begitu proses memerlukan pemroses segara diberikan, proses akan segera memulai permintaan I/O berikutnya sehingga menyebabkan proses blocked menunggu selesainya operasi I/O.

                Dengan demikian pemroses dapat dipergunakan proses-proses lain. Proses-proses I/O bound berjalan paralel bersama proses-proses lain yang benar-benar memerlukan pemroses, sementara proses-proses I/O bound itu menunggu selesainya operasi DMA.

                Proses-proses yang sangat banyak operasi masukan/keluaran kalau harus menunggu lama untuk memakai pemroses (karena prioritas rendah) hanya akan membebani memori karena harus disimpan  tanpa perlu  proses-proses itu di memori karena tidak selesai-selesai menunggu operasi masukan dan menunggu jatuh pemroses.

               

4.4 Penjadwalan dengan banyak antrian (MFQ)

Penjadwalan ini merupakan:

•       Penjadwalan preemptive (by-time)

•       Penjadwalan berprioritas dinamis

Penjadwalanini untuk mencegah banyaknya swapping dengan proses-proses yang sangat banyak menggunakan pemeroses (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam suatu waktu.

Penjadwalan ini menghendaki kelas-kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalan selama satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya berjalan empat kwanta, dan seterusnya. Kententuan yang berlaku adalah sebagai berikut:

•       Jalankan proses kelas tertinggi.

•       Jika proses menggunakan seluruh kwanta yang di alokasikan maka diturunkan kelas prioritas-nya.

•       Proses yang masuk untuk pertama kali ke sistem langsung diberi kelas tertinggi.

Mekanisme ini dapat mencegah proses yang perlu berjalan lama swapping bekali-kali dan mencegah proses-proses interaktif yang singkat harus menunggu lama

Penggunaan 

Sistem dengan banyak proses lambat, memerlukan waktu lama dan juga terdapat banyak proses singkat.

4.5 Penjadwalan terpendek(SJF)

Penjadwalan ini merupakan:

Penjadwalan non-preemptive(run-to-completion).

Penjadwalan tak berprioritas

Penjadwalan ini mengansumsikan waktu jalan proses (sampai selesai) diketahui sebelumnya. Mekanisme penjadwalan adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai. Penjadwalan mempunyai evisien tinggi dan turn arround time rendah.

contoh

Terdapat empat proses A, B, C, D dengan waktu jalan selama 8, 7, 6, 5 kwanta.

•       Gambar 5-3(a) menunjukan penjadwalan cara I, dengan proses-proses dijadwalkan berurutan sebagai A, B, C, D

•       Gambar 5-3(b) menunjukan bila proses-proses dijadwalkan secara SJF yaitu berurutan D,C,B,A

 •       Kedua cara menghasilkan turn arround time ditunjukan pada gambar 5-3(c). Cara I turn around time rata-rata adalah 17,5 kwanta sedang cara II adalah 15 kwanta

Gambar Perbandingan Turn-Arround dengan SJF

Walaupun mempunyai turn arround yang bagus, SJF mempunyai masalah yaitu:

•        tidak dapat mengetahui ukuran job saat job masuk

•       Proses yang tidak datang bersamaan, sehingga penetapannya harus dinamis

•       SJF amat jarang digunakan, merupakan kajian teoritis untuk pembanding turn arround time

4.6 Penjadwalan Sisa Waktu Terpendek, (SRF)

•       Penjadwalan ini merupakan

                - penjadwalan preemptive

                - penjadwalan berprioritas dinamis

•       Penjadwalan ini melengkapi SJF. SJF merupakan penjadwalan nonpremptive sedangkan SRF adalah preemptive untuk timesharing.

•       Pada SRT proses dengan sisa waktu jalan diestimasi terendah dijalankan, termasuk proses-proses yang baru tiba

•       Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai

•       Pada SRT proses yang sedang berjalan (running) dapat diambil alih proses baru dengan sisa waktu jalan yang diestimasi lebih rendah

Kelemahan

•       SRT mempunyai overhead lebih besar dibanding SJF

•       SRT harus menyimpan waktu layanan yang telah dihabiskan oleh job dan kadang-kadang harus menangani peralihan

•       Tibanya proses-proses kecil akan segera dijalankan

•       Job-job lebih lama berarti dengan lama dan variasi waktu tunggu lebih lama dibandingkan pada SJF

•       SRT memberi waktu tunggu minimum tetapi karena overhead peralihan maka pada situasi tertentu SFJ bisa memberi kinerja lebih baik dibanding SRT

4.7 Penjadwalan Rasio Tanggapan Tertinggi(HRN)

•       Penjadwalan ini untuk mengkoreksi kelemahan SJF.

•       Penjadwalan ini merupakan

                - penjadwalan non-preemptive (denganprioritas proses tidak hanya merupakan fungsi waktu layanan tapi juga jumlah waktu tunggu proses)

- penjadwalan berprioritas dinamis

•       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

•       Disebut HRN (High Respon Next) karena (waktu tunggu + waktu layanan) adalah waktu tanggap, berarti waktu tanggap tertinggi yang harus dilayani

4.8 Penjadwalan Terjamin(GS)

•       Penjadwalan ini memberikan janji yang realistis (memberi daya pemroses yang sama) untuk membuat dan menyesuaikan performance adalah jika ada N pemakai, sehingga setiap proses (pemakai) akan mendapatkan 1/N dari daya pemroses CPU.

•       Untuk mewujudkannya, sistem harus selalu menyimpan informasi tentang jumlah waktu CPU untuk semua proses sejak login dan juga berapa lama pemakai sedang login.

•       Kemudian jumlah waktu CPU, yaitu waktu mulai login dibagi dengan n,sehingga lebih mudah menghitung rasio waktu CPU. 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 diperuntukkan proses itu.

•       Rasio 0,5 berarti sebuah proses hanya punya 0,5 dari apa yang waktu CPU miliki dan rasio 2,0 berarti sebuah proses hanya punya 2,0 dari apa yang waktu CPU miliki.

•       Algoritma akan menjalankan proses dengan rasio paling rendah hingga naik ketingkat lebih tinggi diatas pesaing terdekatnya. Ide sederhana ini dapat diimplementasikan ke sistem real-time dan memiliki penjadwalan berprioritas dinamis.