Penjadwalan

Sistem Operasi

Penjadwalan Proses • Adil (fairness) Adalah proses-proses yang diperlakukan sama, yaitu

mendapat jatah waktu pemroses yang sama dan tak ada proses yang tak kebagian layanan pemroses sehingga mengalami kekurangan waktu.

• Efisiensi (eficiency)• Waktu tanggap (response time) , Waktu tanggap berbeda untuk :

– Sistem interaktif Didefinisikan sebagai waktu yang dihabiskan dari saat karakter terakhir dari . perintah dimasukkan atau transaksi sampai hasil pertama muncul di layar. Waktu tanggap ini disebut terminal response time.

– Sistem waktu nyata Didefinisikan sebagai waktu dari saat kejadian (internal atau eksternal) sampai instruksi pertama rutin layanan yang dimaksud dieksekusi, disebut event response time.

• Turn around time Adalah waktu yang dihabiskan dari saat program atau job mulai masuk ke sistem sampai proses diselesaikan sistem.

• 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

Algoritma Penjadwalan

• Nonpre-emptive, menggunakan konsep : – FIFO (First In First Out) atau FCFS (First Come First

Serve)– SJF (Shortest Job First)– HRN (Highest Ratio Next)– MFQ (Multiple Feedback Queues)– Pre-emptive, menggunakan konsep :

• RR (Round Robin)• SRF (Shortest Remaining First)• PS (Priority Schedulling)• GS (Guaranteed Schedulling)

Penjadwalan Real-Time• Penjadwalan real-time dapat diartikan dengan penjadwalan yang benar-

benar valid, yang ditentukan oleh hasil logika dan waktu hasil diperoleh.• Terdapat dua jenis penjadwalan berdasarkan tugasnya yaitu

penjadwalan dengan hard real time, dan penjadwalan dengan soft real time. Dalam hard real time, tugas yang dikerjakan harus selesai tepat waktu namun pada soft real time, tugas yang dikerjakan harus selesai namun tidak ada batasan waktunya.

• Sebelumnya, ciri-ciri dari penjadwalan real-time diantaranya:- Determinism = Suatu proses memiliki batasan untuk dikerjakan- Responsiveness = Respon suatu proses untuk dikerjakan- User Control = Kontrol dari user terhadap proses yang dieksekusi- Realiability = Penjadwalan ini dapat diandalkan dalam penangan masalah pada sistem operasi- Fail-Soft Operation = Penyelesaian masalah yang ada pada sistem operasi.

Algoritma Penjadawalan

- Static Table-Driven ApproachesPada pilihan ini, analisis statis digunakan untuk mencari tugas-tugas mana saja yang ikut dalam antrian dan deadline mana yang paling dekat, maka itulah yang dijalankan lebih dahulu.- Static Priority-Driven Preemptive ApproachesTugas-tugas diprioritaskan berdasarkan batasan waktu mereka. Pada saat dijalankan jika ada tugas dengan prioritas lebih tinggi, tugas yang sedang dijalankan dapat dihentikan.- Dynamic Planning-Based ApproachesTugas-tugas sudah direncakan untuk dijalankan, namun jika ada tugas baru datang dan memungkinkan untuk dijalankan, maka akan diterima untuk dijalankan.

Algoritma Penjadawalan- Dynamic Best Effort ApproachesPilihan ini mempunyai perintah untuk menjalankan semua tugas yang datang, namun jika deadline tidak terpenuhi, maka dibatalkan.Dan ada yang mengelompokkan penjadwalan real-time ini dengan algoritma lain, yaitu:- Clock DrivenClock driven ini biasa digunakan pada hard real-time sistem. Pelaksanaannya menggunakan timer interrupt dan scheduler dapat melakukan pekerjaannya setelah interupsi terjadi.- Weighted Round RobinWeighted Round Robin ini digunakan untuk penjadwalan real-time traffic berkecepatan tinggi. Contohnya yaitu pada algoritma penjadwalan jaringan.- Priority DrivenPriority driven ini mengutamakan priotas untuk penyelesaian suatu proses yang dieksekusi. Biasanya digunakan untuk dinamis real-time sistem.

Algoritma Pre-emptive (A. Round Robin (RR))

• Penjadwalan yang paling tua, sederhana, adil,banyak digunakan algoritmanya dan mudah diimplementasikan.

• Penjadwalan ini bukan dipreempt oleh proses lain tetapi oleh penjadwal berdasarkan lama waktu berjalannya proses (preempt by time).

• Penjadwalan tanpa prioritas.• Berasumsi bahwa semua proses memiliki

kepentingan yang sama, sehingga tidak ada prioritas tertentu.

Algoritma yang digunakan :

• Jika kwanta habis dan proses belum selesai, maka proses menjadi runnable dan pemroses dialihkan ke proses lain.

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

• Jika kwanta belum habis tetapi proses telah selesai, maka proses diakhiri dan pemroses dialihkan ke proses lain.

Diimplementasikan dengan :• Mengelola senarai proses ready (runnable) sesuai

urutan kedatangan.• proses yang berada di ujung depan antrian

menjadi running.• Bila kwanta belum habis dan proses selesai, maka

ambil proses di ujung 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 yang timbul• Kwanta terlalu besar menyebabkan waktu tanggap besar

dan turn arround time rendah.• Kwanta terlalu kecil menyebabkan peralihan proses terlalu

banyak sehingga menurunkan efisiensi proses.Penjadwalan ini :–Baik untuk sistem interactive-time sharing dimana kebanyakan waktu dipergunakan menunggu kejadian eksternal.

• Contoh : text editor, kebanyakan waktu program adalah untuk menunggu keyboard, sehingga dapat dijalankan proses-proses lain.–Tidak cocok untuk sistem waktu nyata apalagi hard-real-time applications.

B. Priority Schedulling (PS)• Adalah tiap proses diberi prioritas dan proses yang

berprioritas tertinggi mendapat jatah waktu lebih dulu (running). Berasumsi bahwa masing-masing proses memiliki prioritas tertentu, sehingga akan dilaksanakan berdasar prioritas yang dimilikinya. Ilustrasi yang dapat memperjelas prioritas tersebut adalah dalam komputer militer, dimana proses dari jendral berprioritas 100, proses dari kolonel 90, mayor berprioritas 80, kapten berprioritas 70, letnan berprioritas 60 dan seterusnya. Dalam UNIX perintah untuk mengubah prioritas menggunakan perintah nice.

• Pemberian prioritas diberikan secara :– Statis (static priorities)– Dinamis (dynamic priorities)

Statis (static priorities)

• Berarti prioritas tidak berubah.• Keunggulan :–Mudah diimplementasikan.–Mempunyai overhead relatif kecil.

• Kelemahan :–Tidak tanggap terhadap perubahan lingkungan yang mungkin menghendaki penyesuaian prioritas.

Dinamis (dynamic priorities)• Merupakan mekanisme untuk 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 in diimbangi dengan peningkatan daya tanggap sistem.

• Dalam algoritma berprioritas dinamis dituntun oleh keputusan untuk memenuhi kebijaksanaan tertentu yang menjadi tujuan. Layanan yang bagus adalah menset prioritas dengan nilai 1/f, dimana f adalah ration kwanta terakhir yang digunakan proses.

• Contoh : – Proses yang menggunakan 2 msec kwanta 100 ms, maka prioritasnya 50. – Proses yang berjalan selama 50 ms sebelum blocked berprioritas 2. – Proses yang menggunakan seluruh kwanta berprioritas 1.

C. Multiple Feedback Queues (MFQ)

• Penjadwalan berprioritas dinamis.– Penjadwalan ini untuk mencegah (mengurangi)

banyaknya swapping dengan proses-proses yang sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam satu waktu. Penjadwalan ini juga 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.

C. Multiple Feedback Queues (MFQ)

• Ketentuan yang berlaku adalah sebagai berikut :– Jalankan proses pada kelas tertinggi.– Jika proses menggunakan seluruh kwanta yang

dialokasikan, maka diturunkan kelas prioritasnya.– Proses yang masuk untuk pertama kali ke sistem

langsung diberi kelas tertinggi.• Mekanisme ini mencegah proses yang perlu

berjalan lama swapping berkali-kali dan mencegah proses-proses interaktif yang singkat harus menunggu lama.

D. Shortest Remaining First (SRF)• Penjadwalan berprioritas dinamis.• Adalah preemptive untuk timesharing.• Melengkapi SJF.• Pada SRF, proses dengan sisa waktu jalan

diestimasi terendah dijalankan, termasuk proses-proses yang baru tiba.– Pada SJF, begitu proses dieksekusi, proses dijalankan

sampai selesai.– Pada SRF, proses yang sedang berjalan (running)

dapat diambil alih proses baru dengan sisa waktu jalan yang diestimasi lebih rendah.

• Kelemahan :– Mempunyai overhead lebih besar dibanding SJF. SRF perlu

penyimpanan waktu layanan yang telah dihabiskan 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 dibanding pada SJF.• SRF perlu menyimpan waktu layanan yang telah

dihabiskan , menambah overhead. Secara teoritis, SRF memberi waktu tunggu minimum tetapi karena overhead peralihan, maka pada situasi tertentu SFJ bisa memberi kinerja lebih baik dibanding SRF.

E. Guaranteed Scheduloing (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.

Algoritma Non Pre-emptive• A. First In First Out (FIFO)

– Penjadwalan tidak berprioritas.• FIFO adalah penjadwalan paling sederhana, yaitu :

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

– Pada saat proses mendapat jatah waktu pemroses, proses dijalankan sampai selesai.

• Penjadwalan ini :– Baik untuk sistem batch yang sangat jarang berinteraksi dengan

pemakai.• Contoh : aplikasi analisis numerik, maupun pembuatan tabel.

– Sangat tidak baik (tidak berguna) untuk sistem interaktif, karena tidak memberi waktu tanggap yang baik.

– Tidak dapat digunakan untuk sistem waktu nyata (real-time applications).

Algoritma Non Pre-emptive• B. Shortest Job First (SJF)

– Penjadwalan ini mengasumsikan waktu jalan proses sampai selesai diketahui sebelumnya. Mekanismenya adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi dan turn around time rendah dan penjadwalannya tak berprioritas.

• Masalah yang muncul adalah :– Tidak mengetahui ukuran job saat job masuk. Untuk

mengetahui ukuran job adalah dengan membuat estimasi berdasarkan kelakukan sebelumnya.

– Proses yang tidak datang bersamaan, sehingga penetapannya harus dinamis.

• Penjadwalan ini jarang digunakan, karena merupakan kajian teoritis untuk pembandingan turn around time.

Algoritma Non Pre-emptive• C. Highest Ratio Next (HRN)

– Penjadwalan berprioritas dinamis.– Penjadwalan untuk mengoreksi kelemahan SJF.– Adalah strategi penjadwalan dengan prioritas proses tidak hanya

merupakan fungsi waktu layanan tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, proses berjalan sampai selesai.

• Prioritas dinamis HRN dihitung berdasarkan rumus :– 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, karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayani.

Interupsi• Kerja prosesor pada suatu proses terhenti oleh

pensaklaran konteks (perubahan kegiatan prosesor dari proses ke proses yang terjadi diantara proses sistem / proses aplikasi).

• 2 cara interupsi pada processor :– Interupsi langsung Berasal dari luar prosesor

(peripheral / alat mengirim sinyal kepada prosesor untuk meminta pelayanan)

– Interupsi Tanya / Polling, Berasal dari prosesor (prosesor secara bergiliran mengecek apakah ada peripheral yang memerlukan pelayanan atau tidak)

Interupsi• Interupsi dapat di-enable dan disable tergantung pada levelnya.• Pembangkit interupsi dapat berasal dari :

– Program, di dalam program telah dirancang pada bagian tertentu akan terjadi pensaklaran konteks, yang menimbulkan interupsi, contohnya pada saat penggunaan alat / prosesor secara bergantian.

– Prosesor, prosesor sendiri dapat membangkitkan interupsi, yang biasa mengolah logika dan aritmatika. Jika melampoi ukuran tampung register di dalam prosesor, maka terjadi kekeliruan yang akan menginterupsi kerjanya sendiri dan menyerahkan kendali prosesor pada sistem operasi. Misalnya pembagian dengan bilangan nol.

– Satuan kendali, tugas untuk melaksanakan interupsi terletak pada satuan kendali, sehingga satuan kendali dapat membangkitkan interupsi. Misalnya kekeliruan instruksi

– Kunci waktu / clock, menggunakan interupsi berkala. Misalnya pada program looping yang tak terhingga, diinterupsi pada setiap selang waktu 60 detik.

– Peripheral I/O, I/O jika akan bekerja memberitahukan pada prosesor dengan interupsi prosesor dan juga ketika pekerjaan selesai atau pada saat terjadi kekeliruan paritas.

– Memori, karena terjadi kekeliruan, misalnya ketika prosesor ingin mencapai alamat memori yang terletak di luar bentangan alamat memori yang ada.

• Sumber daya lain, misal dibangkitkan oleh operator sistem komputer yang mengerti cara interupsi.– Interupsi vector : Berisi alamat prosedur service interupsi– Penerimaan interupsi dan interupsi berganda : ada kalanya interupsi ditolak oleh prosesor atau

interupsi yang datang tidak hanya satu sehingga diperlukan prioritas.

• 1. Penata interupsi / interrupt handler• Jika terjadi interupsi, maka kendali prosesor diserahkan ke

bagian penata interupsi pada sistem operasi, maka penata interupsi inilah yang melaksanakan interupsi.

1. Instruksi yang sedang diolah oleh prosesor dibiarkan sampai selesai program.

2. Penata interupsi merekam semua informasi proses ke dalam blok kendali proses.

3. Penata interupsi mengidentifikasi jenis dan asal interupsi.4. Penata interupsi mengambil tindakan sesuai dengan yang dimaksud

interupsi.5. Penata interupsi mempersiapkan segala sesuatu untuk pelanjutan

proses yang diinterupsi.6. Penata keliru / error handler

•Pemulihan, komputer telah dilengkapi dengan sandi penemuan dan pemulihan kekeliruan, contohnya telah dilengkapi dengan sandi Hamming sehingga ketika menemukan kekeliruan sandi akan mengoreksi kekeliruan itu, proses pulih ke bentuk semula sebelum terjadi kekeliruan.•Pengulangan, mengatur agar proses yang membangkitkan interupsi keliru dikerjakan ulang, jika kekeliruan dapat diatasi maka proses akan berlangsung seperti biasa, jika tidak teratasi maka interupsi akan menempuh tindak lanjut keluar dari proses.•Keluar dari proses, penata keliru menyiapkan tampilan berita keliru dari monitor, setelah itu prosesor keluar dari proses, ini adalah tindakan terakhir jika tidak dapat menolong proses yang keliru tersebut.

Langkah-langkah terjadi interupsi :

• Hardware memuatkan (load) program counter baru dari vector interrupsi

• Prosedur bahasa rakitan menyimpan isi register• Prosedur bahasa rakitan men-set stack yang baru• Prosedur C menandai proses servis siap (ready)• Scheduler / penjadwalan menentukan proses

mana yang akan jalan berikutnya• Prosedur C kembali ke modus bahasa rakitan• Prosedur bahasa rakitan memulai proses yang

sedang dilaksanakan.