Bab 13. Konsep Penjadwalan

13.1. Pendahuluan

Kita mengenal yang namanya multiprograming, yang bertujuan untuk memaksimalkan penggunaan CPU dengan cara mengatur alokasi waktu yang digunakan oleh CPU, sehingga proses berjalan sepanjang waktu dan memperkecil waktu idle. Oleh karena itu perlu adanya penjadwalan proses-proses yang ada pada sistem. Untuk sistem yang hanya mempunyai prosesor tunggal (uniprosesor), hanya ada satu proses yang dapat berjalan setiap waktunya. Jika ada proses lebih dari satu maka proses yang lain harus menunggu sampai CPU bebas dan siap untuk dijadwalkan kembali.

 

13.2. Penjadwalan Antrian

Gambar 13.1. Device Queue

Ketika sebuah proses memasuki sistem, proses itu diletakkan di dalam job queue. Pada antrian ini terdapat seluruh proses yang berada dalam sistem. Sedangkan proses yang berada pada memori utama, siap dan menunggu untuk mengeksekusi disimpan dalam sebuah daftar yang bernama ready queue.

 

Antrian ini biasanya disimpan sebagai linked list. Header dari ready queue berisi pointer untuk PCB pertama dan PCB terakhir pada list. Setiap PCB memiliki pointer field yang menunjuk kepada PCB untuk proses selanjutnya dalam ready queue.

 

Sistem operasi juga memiliki antrian lain. Ketika sebuah proses dialokasikan ke CPU, proses tersebut berjalan sebentar lalu berhenti, di-interupsi, atau menunggu suatu hal tertentu, seperti selesainya suatu permintaan M/K. Dalam permintaan M/K, dapat saja yang diminta itu adalah tape
drive, atau peralatan yang di-share secara bersama-sama, seperti disk. Karena ada banyak proses dalam sistem, disk dapat saja sibuk dengan permintaan M/K dari proses lainnya. Untuk itu proses tersebut mungkin harus menunggu disk tersebut. Daftar dari proses-proses yang menunggu peralatan M/K tertentu disebut dengan device queue. Tiap peralatan memiliki device queue-nya masing-masing (Gambar 14.1, "Siklus Burst").

 

Penjadwalan proses dapat direpresentasikan secara umum dalam bentuk diagram antrian, seperti yang ditunjukkan oleh Gambar 14.2, "Diagram Burst". Setiap kotak segi empat menunjukkan sebuah antrian. Dua tipe antrian menunjukan antrian yang siap dan seperangkat device queues. Lingkaran menunjukkan sumber daya yang melayani antrian, dan tanda panah mengindikasikan alur dari proses-proses yang ada dalam sistem.

Gambar 13.2. Diagram Antrian

Umumnya proses-proses yang ada pada sistem akan ada dalam beberapa tahap antrian yaitu job queue, ready queue, dan device queue.

 

Job queue, menyimpan seluruh proses yang berada pada sistem. Ketika sebuah proses memasuki sebuah sistem, proses tersebut akan diletakkan di dalam job queue.

 

Ready queue merupakan sebuah daftar proses-proses yang berada pada memori utama (main

memori), siap dan menunggu untuk dieksekusi dan dialokasikan ke CPU. Antrian ini biasanya

disimpan sebagai linked-list. Header dari ready queue ini berisi pointer untuk PCB pertama dan

PCB terakhir pada linked-list tersebut. Dan setiap PCB memiliki pointer field yang menunjuk

kepada PCB untuk proses selanjutnya pada ready queue.

Ketika sebuah proses dialokasikan ke CPU, proses tersebut berjalan sebentar lalu berhenti karena ada interrupt atau menunggu permintaan M/K. Dalam permintaan M/K, dapat saja yang diminta itu adalah peralatan yang di share secara bersama-sama seperti disk. Karena ada banyak proses dalam sistem, disk tersebut dapat saja sibuk dengan permintaan M/K dari proses lainnya.

 

Untuk itu proses tersebut mungkin harus menununggu disk tersebut sampai siap untuk memenuhi permintaan M/K tersebut. Daftar dari proses-proses yang menunggu peralatan M/K tertentu disbut dengan device queue. Tiap peralatan mempunyai device queue-nya masing masing.

 

Penjadwalan proses dapat direpresentasikan secara umum dalam bentuk diagram antrian, yang

ditunjukkan oleh Gambar 13.2, "Diagram Antrian". Setiap kotak segi empat menunjukkan sebuah antrian. Dua antrian diantaranya menunjukkan ready queue dan seperangkat device queue. Lingkaran menunjukkan sumber daya yang melayani antrian dan tanda panah mengindikasikan alur dari proses-proses yang ada dalam sistem.

 

Proses-proses yang ada menunggu di dalam ready queue sampai dia dipilih untuk eksekusi, atau

di-dispatched. Begitu proses tersebut dipilih lalu dialokasikan ke CPU dan sedang berjalan, satu dari beberapa kemungkinan di bawah ini dapat terjadi.

1. Proses tersebut mengeluarkan permintaan M/K, lalu ditempatakan dalam sebuah M/K device queue.
   
2. Proses tersebut dapat membuat sub-proses baru dan menunggu untuk di-terminasi.
   
3. Proses tersebut dikeluarkan (di-remove) secara paksa dari CPU, sebagai hasil dari suatu interrupt dan diletakkan kembali ke dalam ready queue.
   
   
    

Pada dua kemungkinan pertama (1 dan 2) proses berganti status dari waiting state menjadi ready state, lalu diletakkan kembali ke dalam ready queue. Siklus ini akan terus terjadi pada proses sampai dia di-terminasi, yaitu dimana proses tersebut dikeluarkan dari seluruh antrian yang ada dan memiliki PCB-nya sendiri dan seluruh sumber daya yang dia gunakan dialokasikan kembali.

13.3. Penjadwal

Gambar 13.3. Medium-term Scheduler

Terdapat dua jenis scheduler pada CPU yang umum dipakai, yaitu:

1. Long-Term Scheduler atau Job Scheduler yang bertugas memilih proses dari tempat ini dan mengisinya ke dalam memori.
   
2. Short-Term Scheduler atau CPU scheduler yang bertugas memilih proses yang sudah siap untuk melakukan eksekusi,dan dialokasikan di CPU untuk proses tersebut.
   

 

Perbedaan signifikan pada kedua scheduler ini adalah frekuensi dari eksekusinya. Short-Term

Scheduler harus sering memilih proses baru untuk CPU dan eksekusinya paling sedikit 1 kali dalam 100 milidetik. Jadi,sudah seharusnya scheduler ini berjalan cepat. Sedangkan pada Long-Term Scheduler melakukan eksekusi lebih sedikit dengan selang waktu pada kisaran menit untuk tiap eksekusinya.

 

Long-Term Scheduler mengatur degree of multiprogramming, yaitu jumlah proses dalam memori. Jadi jika degree of multi programming stabil, maka rata-rata jumlah proses baru sama dengan jumlah proses yang telah selesai. Oleh karena itu,long-term scheduler dipanggil bila sudah ada proses yang selesai atau telah meninggalkan sistem sehingga eksekusinya jauh lebih jarang dibandingkan short-term scheduler.

 

Secara umum, proses pada Long-Term Scheduler dapat dibagi menjadi dua, yaitu:

1. M/K Bound yaitu proses yang lebih banyak mengerjakan permintaan M/K dibandinkan komputasi.
   
2. CPU Bound yaitu proses yang lebih banyak mengerjakan komputasi dibandingkan permintaan M/K.
   
   
    

13.4. Context Switch

Mengganti CPU ke proses lain memerlukan penyimpanan keadaan dari proses lama dan mengambil keadaan dari proses yang baru. Hal ini dikenal dengan sebutan context switch. Context switch sebuah proses direpresentasikan dalam PCB dari suatu proses; termasuk nilai dari CPU register, status proses (dapat dilihat pada Gambar 14.1, "Siklus Burst") dan informasi manajemen memori.

Gambar 13.4. Context Switch

Ketika context switch terjadi, kernel menyimpan data dari proses lama ke dalam PCB nya dan

mengambil data dari proses baru yang telah terjadwal untuk berjalan. Waktu context switch adalah murni overhead, karena sistem melakukan pekerjaan yang tidak begitu berarti selama melakukan pengalihan. Kecepatannya bervariasi dari mesin ke mesin, bergantung pada kecepatan memori, jumlah register yang harus di-copy, dan ada tidaknya instruksi khusus (seperti instruksi tunggal untuk mengisi atau menyimpan seluruh register). Tingkat kecepatan umumnya berkisar antara 1 sampai 1000 mikro detik.

 

13.5. Rangkuman

Sebuah proses, ketika sedang tidak dieksekusi, ditempatkan pada antrian yang sama. Disini ada duakelas besar dari antrian dalam sebuah sistem operasi: permintaan antrian M/K dan ready queue.Ready queue memuat semua proses yang siap untuk dieksekusi dan yang sedang menunggu untukdijalankan pada CPU. PCB dapat digunakan untuk mencatat sebuah ready queue. PenjadwalanLong-term adalah pilihan dari proses-proses untuk diberi izin menjalankan CPU. Normalnya,penjadwalan long-term memiliki pengaruh yang sangat besar bagi penempatan sumber daya, terutama manajemen memori. Penjadwalan short-term adalah pilihan dari satu proses dari ready

 

Sebuah proses, ketika sedang tidak dieksekusi, ditempatkan pada antrian yang sama. Disini ada dua kelas besar dari antrian dalam sebuah sistem operasi: permintaan antrian M/K dan ready queue. Ready queue memuat semua proses yang siap untuk dieksekusi dan yang sedang menunggu untuk dijalankan pada CPU. PCB dapat digunakan untuk mencatat sebuah ready queue. Penjadwalan Long-term adalah pilihan dari proses-proses untuk diberi izin menjalankan CPU. Normalnya, penjadwalan long-term memiliki pengaruh yang sangat besar bagi penempatan sumber daya, terutama manajemen memori. Penjadwalan short-term adalah pilihan dari satu proses dari ready queue.

 

 

[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005. Operating Systems

Concepts. Seventh Edition. John Wiley & Sons.