Konsep Dasar Penjadwalan CPU
Penjadwalan proses didasarkan pada sistem operasi yang menggunakan prinsip multiprogramming. Dengan cara mengalihkan kerja CPU untuk beberapa proses, maka CPU akan semakin produktif.
Pada multiprogramming, selalu akan terjadi beberapa proses berjalan dalam suatu waktu. Sedangkan pada uniprogramming hal ini tidak akan terjadi, karena hanya ada satu proses yang berjalan pada saat tertentu.
Konsep dasar dari multiprogramming ini adalah: suatu proses akan menggunakan CPU sampai proses tersebut dalam status wait (misalnya meminta I/O) atau selesai. Pada saat wait , maka CPU akan nganggur (idle). Untuk mengatasi hal ini, maka CPU dialihkan ke proses lain pada saat suatu proses sedang dalam wait, demikian seterusnya.
Tabel proses kerja prosesor
Dalam menggambarkan sebuah penjadwalan dapat dilakukan dengan menyusun kerja proses seperti Gambar di atas, atau ada kalanya diperlukan barisan saat proses untuk dapat menyusun tabel kerja proses. Selanjutnya, dari kedua cara ini, dapat dihitung waktu sia-sia (T-t), rerata lama tanggap Tt, nilai rasio tanggap Rt, dan rasio penalti Rp.
Penjadwalan prosesor dapat dibagi menjadi beberapa kategori setelah proses sudah berada dalam antrian yaitu prioritas dan preempsi. Dalam keadaan tanpa prioritas atau preempsi, maka penjadwalan adalah melalui antrian. Dengan demikian dapat disusun ketegori penjadwalan berdasarkan prioritas dan preempsi itu kedalam Gambar berikut:
Gambar Kategori kerja prosesor
Kesemuanya ada empat kategori meliputi (I) tanpa prioritas dan tanpa preempsi melalui antrian biasa, (II) dengan prioritas dan tanpa preempsi, (III) tanpa prioritas dan dengan preempsi, dan (IV) dengan prioritas dan dengan preempsi. Selanjutnya kategori penjadwalan ini dapat kita uraikan dalam berbagai algoritma penjadwalan.
Algoritma Penjadwalan
Proses memerlukan prosesor. Proses memerlukan penjadwalan pemakaian prosesor. Berdasarkan berbagai ketentuan pada penjadwalan proses serentak, dapat disusun teknik penjadwalan prosesor. Dapat dipandang semua proses serentak itu sebagai satu kumpulan proses yang memerlukan prosesor.
Di sini, dianggap semua proses sebagai satu kumpulan proses serentak. Proses ini akan diolah oleh prosesor baik dalam bentuk antrian maupun dalam bentuk prioritas atau preempsi. Beberapa algoritma penjadwalan yang umum akan dibahas pada bagian ini. Untuk memudahkan mengamati setiap algoritma akan digunakan dua buah contoh (kedua Gambar berikut) antrian tetap yang akan kita gunakan untuk diterapkan pada berbagai algoritma penjadwalan yang akan kita bahas.
Gambar Kasus I – antrian lima proses dengan saat tiba = 0
Gambar Kasus II – antrian lima proses saat tiba berbeda
Algotima Penjadwalan First Come First Served
Algoritma First Come First Served (FCFS) disebut juga sebagai teknik Pertama Tiba Pertama Dilayani (PTPD). FCFS merupakan penjadwalan tanpa prioritas dan tanpa preempsi (lihat posting penjadwalan cpu). Karena itu, proses ini serentak tersusun dalam antrian murni.
Pada FCFS, proses yang tiba lebih dahulu akan dilayani lebih dahulu. Kalau proses itu tiba pada waktu yang sama, maka pelayanan dilakukan berdasarkan urutan mereka pada antrian. Tidak menjadi soal apakah waktu proses mereka singkat atau lama. Untuk dapat dilayani oleh prosesor, proses di antrian belakang harus menunggu sampai semua proses di depannya rampung dilaksanakan.
Kita dapat langsung memasukkan proses ini ke dalam tabel proses pada kerja prosesor. Pada contoh kasus I, proses B hanya dapat dilaksanakan setelah proses A rampung dilaksanakan. Proses C hanya dapat dilaksanakan setelah proses B rampung dilaksanakan. Demikian seterusnya sehingga didapatkan nilai seperti pada tabel Gambar berikut.
Gambar Ujuk kerja prosesor dengan algoritma FCFS untuk kasus I
Tampak di sini bahwa rerata lama tanggap adalah 19,4 satuan waktu. Nilai ini cukup besar dibandingkan dengan lama proses dari masing-masing proses itu. Berikut ilustrasi untuk contoh kasus kedua .
Gambar Ujuk kerja prosesor dengan algoritma FCFS untuk kasus II
Pada Gambar Contoh kasus di bagian atas postingan ini, proses belum terurut sesuai waktu tibanya, oleh karena itu setelah diurut berdasarkan waktu tibanya, maka antrian menjadi A, B, D, E, dan C. Tampak di sini bahwa rerata lama tanggap adalah 17,8 satuan waktu. Nilai ini masih cukup besar dibandingkan dengan lama proses dari masing-masing proses tetapi masih lebih kecil dari rerata lama tanggap untuk kasus I. Perbedaan dengan contoh pertama terletak pada perhitungan lama tanggap. Kalau pada contoh pertama, lama tanggap sama dengan saat rampung, maka di sini mereka tidak sama karena saat tiba proses tidaklah sama.
Kedua contoh ini menunjukkan bahwa lama tanggap sangat dipengaruhi oleh lama proses pada proses yang terletak di bagian depan antrian. Jika lama proses pada proses di bagian depan antrian itu besar, maka proses dengan lama proses yang singkat di bagian belakang antrian, tetap harus lama menunggu, sebelum mereka dapat dilayani oleh prosesor. Itu sebabnya penjadwalan FCFS ini kurang menguntungkan bagi keseluruhan pelayanan.
Salah satu cara untuk mengatasi hal itu adalah melalui prioritas. Proses dengan lama proses yang singkat memperoleh prioritas untuk didahulukan ke prosesor. Makin singkat masa prosesnya, makin cepat proses itu dilayani oleh prosesor. Penjadwalan ini dikenal sebagai Proses Terpendek Dipertamakan (PTD)
Algoritma Penjadwalan Shortest Job First
Gambar Kasus I – antrian lima proses dengan saat tiba = 0
Gambar Kasus II – antrian lima proses saat tiba berbeda
Disebut juga sebagai teknik Proses Terpendek Dipertamakan (PTD). SJF merupakan penjadwalan dengan prioritas tanpa preempsi. Dasar prioritas adalah pendeknya proses. Makin pendek proses makin tinggi prioritasnya.
Pada algoritma ini di ditempuh dua langkah. Langkah pertama: menentukan urutan prioritas berdasarkan pendeknya proses yang dilayani. Langkah kedua: menentukan pada saat tertentu, proses mana yang perlu dilayani oleh prosesor.
Sekalipun urutan prioritas proses sudah ditentukan pada langkah pertama, namun masih ada masalah yang dapat menghambat pelaksanaan proses menurut urutan itu. masalah itu adalah masalah saat tiba dari setiap proses. Kalau pada saat prosesor siap menerima proses, serta proses terpendek sudah tiba, maka proses terpendek itulah yang dikerjakan oleh prosesor sesuai dengan pengaturan pada langkah pertama. Tetapi kalau pada saat prosesor sudah siap menerima proses. Sedangkan proses yang memperoleh giliran pada saat itu belum juga tiba, maka kita perlu mempunyai ketentuan tentang proses mana yang akan dikerjakan oleh prosesor.
Ketentuan itu adalah: pada saat prosesor siap menerima proses sedangkan proses terpendek yang memperoleh giliran pada saat itu belum juga tiba, maka lihat semua proses yang sudah tiba pada saat itu. Proses yang sudah rampung diabaikan. Dari proses yang sudah tiba tapi belum diproses itu dipilih proses terpendek, dan proses terpendek itulah yang pada saat itu dikerjakan oleh prosesor.
Kalau dalam penentuan urutan proses ini, ditemukan dua atau lebih proses yang memiliki prioritas sama, maka pelayanan dilakukan berdasarkan urutan antrian diantara proses berprioritas sama itu.
Lihat contoh kasus I pada bagian atas postingan ini yang menunjukkan sekumpulan proses A, B, C, D, dan E yang mempunyai saat tiba yang sama yaitu 0. Namun lama proses mereka berbeda. Berdasarkan lama proses yang berbeda ini, pada langkah pertama, kita menyusun prioritas berdasarkan pendeknya proses, maka urutan proses berubah menjadi C, D, A, E, dan B. Karena semua proses sudah tiba, maka langkah kedua tidak mengalami kesulitan. Seperti tampak pada Gambar dibawah ini urutan antriannya berubah sehingga sesuai dengan urutan prioritas.
Tampak disini bahwa algoritma SJF menyebabkan rerata lama tanggap semua proses itu menjadi 14,6 satuan waktu. Rerata ini menjadi lebih singkat jika dibandingkan dengan rerata lama tanggap untuk penjadwalan FCFS.
Gambar Ujuk kerja prosesor dengan algoritma SJF untuk kasus I
Selanjutnya lihat contoh II untuk sekumpulan proses dengan saat tiba tidak sama seperti pada Gambar paling atas posting ini (kasus II) mula-mula kita menyusun urutan proses itu berdasarkan prioritas.
Dalam pelaksanaannya, kita mulai dari saat = 0. Pada saat = 0 ini, proses terpendek C belum tiba. Bahkan proses satu-satunya yang sudah tiba adalah proses A. Karena itu pada saat = 0, proses A yang dikerjakan. Untuk lebih jelasnya perhatikan barisan saat dibawah. Proses A selesai ketika saat = 7. Ketika itu proses yang telah tiba adalah proses B, D, dan E, dan yang terpendek dari keduanya adalah D, sehingga proses berikutnya adalah D. Ketika D selesai saat = 11, dan proses yang telah tiba dalam ready queue adalah B, C dan E. Dan yang terpendek dari ketiganya adalah C, maka C dikerjakan dahulu. Ketika C telah selesai diproses oleh CPU, saat = 13 berarti sisa proses yang menunggu adalah B dan E, dan yang terpendek dari keduanya adalah E, maka E didahulukan, setelah selesai barulah B diproses. Inilah perbedaan yang terjadi jika algoritma SJF diterapkan pada beberapa proses yang memiliki waktu tiba tidak sama.
Dengan demikian didapatkan bahwa A diproses mulai saat = 0 hingga 7, D mulai saat = 7 hingga 11, C mulai saat = 11 hingga 13, E mulai saat = 13 hingga 21, dan B mulai saat = 21 hingga 31.
Gambar Ujuk kerja prosesor dengan algoritma SJF untuk kasus II
Gambar Barisan Saat Algoritma Shortest Job First
Tidak ada komentar:
Posting Komentar