PENJADWALAN PROSES (THREAD)
Penjadwalan proses merupakan basis sistem operasi multiprograming. Dengan mengalih-alihkan pemroses diantara proses-proses yang ada, sistem operasi membuat sistem komputer menjadi lebih produktif dan efisien. Sasaran multiprograming adalah mempunyai proses yang berjalan (dieksekusi) di setiap waktu untukmemaksimumkan utilisasi pemroses. Untuk sistem komputer dengan pemroses tunggal (disebut uniprocessor atau singleprocessor) maka tidak pernah lebih dari satu proses yang berjalan (running). Jika terdapat beberapa proses di sistem, satu proses berjalan sedangkan sisahnya menunggu sampai penroses bebas dan proses itu dijadwalkan untuk dijalankan.
Gagasan multiprograming adalah sederhana. Satu proses dieksekuasi sampai proses itu menunggu sesuatu, biasanya pelaksanaan operasi I/O. Pada multiprograming, beberapa proses disimpan dimemori pada satu waktu. Ketika satu proses harus menunggu, sistem operasi mengambil pemroses darinya dan memberikan pemroses ke proses lain. Pola ini dilakukan secara terus-menerus. Setiap kali satu proses harus menunggu, proses lain mengambil alih penggunaan pemroses.
Deskripsi Penjadwalan Proses
Penjadwalan merupakan kumpulan kebijaksanaan dan mekanisme di sistemoperasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer. Penjadwalan bertugas memutuskan hal-hal berikut:
• Proses yang harus berjalan.
• Kapan dan berapa lama proses berjalan.
Sasaran utam penjadwalan proses adalah optimasi kinerja sistem komputer menurut kriteria tertentu.
Kriteria untuk mengukur dan optimasi kinerja penjadwalan:
• Adil (fairness)
• Efisiensi
• Waktu tanggap (response time)
• Turn arroound time
• Throughput
Adil (fairness)
Adil adalah proses-proses diperlakukan sama yaitu mendapat jatah waktu layanan pemroses yang sama dan tidak ada proses yang tidak mendapatkan layanan pemroses sehingga mengalami startvation. Startvation adalah kondisi bahwa proses tidak pernah berjalan karena dijadwalkan untuk berjalan. Sasaran penjadwalan seharusnya menjamin setiap proses mendapat pelayanan dari pemroses secara adil.
Efisiensi
Efisiensi adalah utilasi pemroses yang dihitung dengan perbandingan (rasio) waktu sibuk pemroses dengan total waktu operasi sistem komputer secarakeseluruhan. Sasaran penjadwalan adalah menjaga agar pemroses tetap dalam keadaan sibuk sehingga efesiensi 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.
Waktu Tanggap (Response Time)
Waktu tanggap berbeda untuk
• Sistem interaktif
• Sistem waktu nyata
Waktu tanggap pada sistem interaktif
Waktu tanggap pada sistem interaktif didefinisikan sebagai waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukan oleh program atau transaksi sampai hasil pertam muncul di perangkat masukan keluaran seperti layar (terminal).
Waktu tanggap pada sistem waktu nyata
pada sistem waktu nyata (real-time), waktu tanggap didefinisikan sebagai waktu dari saat kemunculan suatu kejadian(internal atau eksternal) sampai instruksi pertam rutin layanan terhadap kejadian dieksekusi. Waktu untuk sistem nyata biasa disebut even response time.
Sasaran penjadwalan adalah meminimalkan waktu tanggap sehingga menghasilkan sistem yang responsif.
Turn Arround Time
Turn arround time adalah waktu yang dihabiskan dari saat proses atau job dimulai masuk kesistem sampai proses itu diselesaikan sistem. Waktu yang dimaksud adalah waktu yang dihabiskan proses berada di sistem, diekspresikan sebagai penjumlahan waktu eksekusi(waktu pelayanan proses/job) dan waktu menunggu dari proses itu, yaitu:
Turn arround time = waktu eksekusi + waktu menunggu
Sasaran penjadwalan adalah meminimalkan turn arround time
Throughput
Throughput adalah jumlah kerja yang dapat diselesaikan 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 interfal waktu. Lenih tinggi angka throughput maka lebih banyak kerja yang dilakukan sistem.
Kriteria-kriteria tersebut saling bergantuk dan dapat saling bertentangan sehingga tidak mungkin optimasi semua kriteria secara simultan.
Contoh
Untuk memberi tanggap waktu kecil umumnya memerlukan penjadwalan yang sering beralih-alih diantara proses –proses yang ada.cara ini meningkatkan overhead sistem sehingga menurunkan efisiensi.
Kebijaksanaan perancangan penjadwalan melibatkan kompromi diantara kebutuhan-kebutuhan yang saling bertentangan. Kompromi ini bergantung pada sifat dan penggunaan sistem komputer.
Tipe-Tipe Penjadwalan
Dapat terdapat tiga tipe penjadwal berada secara bersama-sama pada sistem operasi yang kompleks, yaitu:
1. Penjadwal jangka pendek (short-term scheduller)
2. Penjdawal jangka menengah (medium-term scheduller)
3. Penjadwal jangka panjang (long-term scheduller)
Penjadwal jangka menengah
Penjadwal jangka panjang Penjadwal jangka pendek
Program-program interaktif
Penjadwalan Jangka Pendek
Penjdawalan jengka pendek bertugas menjadwalkan alokasi pemroses diantara proses-proses Ready yang berada di memory utama. Sasaran utama penjadwalan jangka pendek adalah memaksimumkan kinerja sistem untuk memenuhi satu kumpulan kriteria yang diharapkan. Penjadwalan ini dijadwalkan 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 masukan /keluaran atau memanggil suatu sistem call. Proses-proses yang ditunda tidak dapat membuat kamajuan untuk menuju selesai sampai kondisi-kondisi yang menyebabkannya tertunda hilang. Agar ruang memory dapat bermanfaat maka proses dipindah dari memori utama ke memori sekunder sehingga tersedia ruang yang lebih besar untuk proses-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.
Penjadwalan jangka menengah bertugas menanganiproses-proses swapping. Proses-proses yang mempunyai kepentingan kecil saat itu adalah proses yang tertunda. Tetapi, begitu kondisi yang membuat proses tertunda hilang dan proses dimasukan kembali ke memori utama dan Ready. Penjadwal jangka menengah mengendalaikan trasisi dari Suspended ke Ready (dari state Suspend ke Ready) dari proses-proses yang mengalami swapping.
Penjadwal Jangka Panjang
Penjadwal jangka panjang bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi sistem. Batch biasanya berupa proses-proses dengan pengguanaan sumber daya yang intensif (yaitu waktu pemroses, memori, perangkat masukan/keluaran), program-program ini mempunyai prioritas yang rendah, dan biasa digunakan sebagai pengisi (agar pemroses sibuk) selama periode aktivitas proses-proses interaktif rendah. Sasaran utama penjadwal jangka panjang adalah memberi keseimbangan proses-proses campuran. Tipe-tipe penjadwalan dapat dikaitkan dengan state-state proses.
Strategi Penjadwalan
Terdapat dua strategi penjadwal, yaitu
1. Penjadwalan preemptiv (run-to-completion)
2. Penjadwalan preemptive
1. Penjadwalan Nonpreemptive
Begitu proses diberi jatah layanan pemroses maka pemroses dapat diambil alih proses lain sampai proses itu selesai. Non-preemtive juga disebut run-to-completion karena proses yang telah dijadwalkan akan dijalankan sampai selesainya atau proses tersebut meminta layanan masukan/keluaran.
2. Penjadwalan Preemptive
Saat proses diberi jatah layanan pemroses maka pemroses dapat diambil alih oleh proses lain yang mempunyai prioritas yang lebih tinggi berdasarkan kriteria sistem itu. Pada penjadwalan preemptive, proses dapat disela oleh proses lain sebelum selesainya dan harus dilanjutkan menunggu jatah waktu layanan pemroses tiba kembalai pada proses itu. Proses yang disela berubah menjadi state Ready.
Penjadwalan preemptive berguna pada sistem yakni proses-proses yangperlu mendapat perhatian/tanggapan pemroses secara cepat. Misalanya:
• Pada sistem-sistem waktu nyata, kehilangan interupsi (yaitu interupsi tidak segera dilayani) dapat berakibat fatal.
• Pada sistem-sistem interaktif timesharing, penjadwalan preemptive penting agar dapat menjamin waktu tanggap yang memadai.
Penjadwalan preemptive adalah bagus tapi tidak tanpa ongkos. Peralihan proses (yaitu layanan pemroses dari satu proses beralih ke proses lain) memerlukan overhead (karena banyak tabel yang dikelola). Agar penjadwalan preemptive menjadi fektif, 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-algoritma Penjadwalan Proses
Terdapat banyak algoritma penjadwalan nonpreemptive maupun penjadwalan preemptive. Algoritma-algoritma yang menerapkan srategi nonpreemptive diantaranya:
• FIFO (First-in, First-out) atau FCFS (First-come, First-serve).
• SJF (Shortest job First).
• Jika kwanta habis dan proses belum selesai maka tempatkan proses Running ke ekor antrian proses Ready dan sistem mngambil proses di ujung depan antrian proses Ready.
Masalah penjadwalan ini adalah dalam hal menentukan besar kwanta, yaitu:
• Kwanta terlalu besar menyebabkan waktu tanggap besar dan turun arround time rendah.
• Kwanta terlalu kecil mengakibatkan peralihan proses terlalu banyak sehingga menurunkan efesiensi pemroses.
Harus ditetapkan besar kwanta waktu yang optimal berdasarkan kebutuhan sistem terutama dari hasil percobaan atau data historis dari sistem. Besar kwanta waktu beragam yang bergantung beban sistem. Bedasarkan kriteria penilaian penjadwalan:
• Fairness Penjdawalan 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 menandai untuk sistem waktu nyata.
• Turn Arround time Penjadwalan RR cukup bagus.
• Throughput Penjadwalan Rrcukup bagus.
Penggunaan
• Cocok untuk sistem interaktif-timesharing dalamhal ini sebagian besar waktu dipergunakan untuk menunggu kejadian eksternal. Contoh text-editor kebanyakan waktu program adalah untuk menunggu kejadian dari keyboard sehingga pemroses dapat digunakan untuk mengeksekusi proses-proses lain.
• Tidak cocok untuk sistem waktu nyata apalagi hard-real-time application.
Penjadwalan FIFO
Penjadwalan FIFO ini merupakan
1. Penjadwalan non-preemptive (run-to-completion)
2. Penjadwalan tidak berprioritas
Algoritma-algoritma yang menerapkan strategi preemptive diantaranya:
• RR (Round-Robin)
• MFQ (Multipiee feedback Queues)
• SRF (Shortest-Remaining-First)
• HRN (Highest-Ratio Next)
• PS (Priority-Shcedulling)
• GS (Guaranteed Shcedulling)
Klafikasi lain selain berdasarkan dapat/tidaknya suatu proses diambil alih secara paksa adalah klafikasi berdasarkan adanya prioritas diproses-proses, yaitu:
1. Algoritma penjadwalan tanpa berprioritas.
2. Algoritma penjadwalan berprioritas,terdiri dari
• Algoritma penjadwalan berprioritas statis
• Algoritma penjadwalan berprioritas dinamis.
Penjadwalan Round-robin (RR)
Penjadwalan Round-robin merupakan penjadwalan preemptive, namun proses tidak di-preempt secara langsung oleh proses lain namunoleh penjadwal berdasarkan lama waktu berjalannya suatu proses maka penjadwala ini disebut preempt-by time. Atau juga penjadwal tanpa berprioritas.
Semua proses dianggap penting dan diberi sejumlah waktu pemroses yang disebut kwanta (quantum) atau time-slice tempatproses itu berjalan. Proses berjalan selama 1 kwanta, kemudian penjadwal akan mengalihkan kepada proses berikutnya, juga untuk berjalan sati kwanta, begitu seterusnya sampai kembali pada proses pertama, dan barulang.
Penjdwalan Berprioritas (PS)
Gagasan penjadwalan adalah masing-masing diberi proses dan proses berprioritas tertinggi menjadi running (yaitu mendapat jatah waktu pemroses). Prioritas dapat diberikan berupa prioritas statis (Ststic priorities) ataupun prioritas dinamis (dynamic priorities)
Algoritma sederhana yang memberi layanan bagus adalah dengan menge-set proses dengan prioritas berdasarkan rumus nilai 1/f bahwa f adalah rasio kwanta terakhir yang digunakan proses. Kebijaksanaan yang diterapkan adalah jaminan proses-proses mendapat layanan yang adil dari pemroses dalam arti dalam jumlah pemroses yang sama untuk masing-masing pemroses dalam satu waktu.
Penjadwalan yang Terpendek yang LebihDahulu
Penjadwalan SJF ini merupakan
• Penjadwalan non-preemptive.
• Penjadwaln dapat dikatakan sebagai prioritas. Di SJF, prioritas dialokasikan ke proses dengan proses dan pemroses dialokasikan ke proses dengan prioritas tertinggi. Proses-proses dengan prioritas yang sama akan dijadwalkan secara FCFS (FIFO).
Penjadwalaninimengasumsikan waktu jalan proses (sampai selesai) atau waktu lamanya peoses diketahui sebelumnya. Mekanisme penjadwalan SJF adalah lebih dulu menjadwalkan proses dengan waktu jalan terpendek sampai selesai Setelah proses itu selesai, maka proses dengan waktu jalan terpendek berikutnya dijadwalkan. Demikian seterusnya.
Keunggulan
Penjadwalan SJF mempunyai efisien tinggi dan turn arround time rendah.
Penggunaan
Amat jarang digunaka, merupakan kajian teorities untuk pembanding dalam perbandingan turn-arroun-time.
Penjdawlan dengan banyak antrian (MFQ)
Penjadwalan MFQ ini merupakan
• Penjadwalan preemptive
• Penjadwalan berprioritas
Sasaran penjadwalan MFQ ini adalah untuk mencegah banyaknya aktivitas swapping. Cara yang dilakuakn adalah dengan
1) Proses-proses yang sangat banyak mengguanakan pemroses (karena menyelesaikan tugasnya memakan waktu yang lama) diberi jatah waktu ( jumlah kwanta) lebih banyak dalam satu waktu.
2) 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 selama tiga kwanta, dan seterusnya.
Ketentuan yang berlaku adalah sebagai berikut:
• Jalankan proses-proses yang berada pada kelas beprioritas tertinggi.
• Jika proses telah menggunakan seluruh kwanta yang dialokasikan maka proses itu diturunkan kelas prioritasnya.
• Proses yang masuk pertama kali ke sistem langsung diberikan kelas tertinggi.
Evaluasi algoritma
Bagaimana memilih algoritma penjadwalan untuk sistem tertentu? Masing-nasing algoritma mempunyai parameter-parameter tersendiri. Pemilihan algoritma penjadwalan merupakan hal yang sulit. Persoalan utama adalah mendefinisikan kriteria untuk pemilihan algoritma.
Kriteria-kriteria yang sering digunakan adalah fairness (keadilan), efisiensi,waktu tanggap, turn arround time, throughput. Begitu kriteria pemilihan telah didefinisikan, kita dapat mengevaluasi beragam algoritma. Terdapat sejumlah metode eavaluasi untuk melakukan metode ini
Read more...
