Algoritma Penjadwalan CPU dalam Sistem Operasi

Daftar Isi:

Anonim

Apa itu Penjadwalan CPU?

Penjadwalan CPU adalah proses menentukan proses mana yang akan memiliki CPU untuk dieksekusi sementara proses lain ditunda. Tugas utama penjadwalan CPU adalah memastikan bahwa setiap kali CPU tetap menganggur, OS setidaknya memilih salah satu proses yang tersedia dalam antrian siap untuk dieksekusi. Proses seleksi akan dilakukan oleh penjadwal CPU. Ini memilih salah satu proses dalam memori yang siap untuk dieksekusi.

Dalam tutorial penjadwalan CPU ini, Anda akan belajar:

  • Apa itu penjadwalan CPU?
  • Jenis Penjadwalan CPU
  • Terminologi Penjadwalan CPU yang Penting
  • Kriteria Penjadwalan CPU
  • Timer Interval
  • Apa itu Dispatcher?
  • Jenis Algoritma Penjadwalan CPU
  • Siapa cepat dia dapat
  • Sisa Waktu Tersingkat
  • Penjadwalan Berbasis Prioritas
  • Penjadwalan Round-Robin
  • Pekerjaan Terpendek Pertama
  • Penjadwalan Antrian Beberapa Tingkat
  • Tujuan dari algoritma Penjadwalan

Jenis Penjadwalan CPU

Berikut dua jenis metode Penjadwalan:

Penjadwalan Preemptive

Dalam Penjadwalan Terlebih Dahulu, sebagian besar tugas ditetapkan dengan prioritasnya. Terkadang penting untuk menjalankan tugas dengan prioritas lebih tinggi sebelum tugas dengan prioritas lebih rendah lainnya, meskipun tugas dengan prioritas lebih rendah masih berjalan. Tugas dengan prioritas lebih rendah akan bertahan selama beberapa waktu dan dilanjutkan saat tugas dengan prioritas lebih tinggi menyelesaikan eksekusinya.

Penjadwalan Non-Preemptive

Dalam metode penjadwalan jenis ini, CPU telah dialokasikan untuk proses tertentu. Proses yang membuat CPU sibuk akan melepaskan CPU baik dengan mengganti konteks atau mengakhiri. Ini adalah satu-satunya metode yang dapat digunakan untuk berbagai platform perangkat keras. Itu karena tidak memerlukan perangkat keras khusus (misalnya, pengatur waktu) seperti penjadwalan preemptive.

Kapan penjadwalan bersifat Preemptive atau Non-Preemptive?

Untuk menentukan apakah penjadwalan bersifat preemptive atau non-preemptive, pertimbangkan empat parameter berikut:

  1. Sebuah proses beralih dari menjalankan ke status menunggu.
  2. Proses tertentu beralih dari status berjalan ke status siap.
  3. Proses tertentu beralih dari status menunggu ke status siap.
  4. Proses menyelesaikan eksekusinya dan dihentikan.

Hanya kondisi 1 dan 4 yang berlaku, penjadwalan disebut non-preemptive.

Semua penjadwalan lainnya bersifat preemptive.

Terminologi Penjadwalan CPU yang Penting

  • Burst Time / Execution Time: Ini adalah waktu yang dibutuhkan oleh proses untuk menyelesaikan eksekusi. Ini juga disebut waktu berjalan.
  • Arrival Time: ketika suatu proses masuk dalam keadaan siap
  • Waktu Selesai: saat proses selesai dan keluar dari sistem
  • Multiprogramming: Sejumlah program yang dapat hadir dalam memori pada saat yang bersamaan.
  • Pekerjaan: Ini adalah jenis program tanpa interaksi pengguna apa pun.
  • Pengguna: Ini adalah jenis program yang memiliki interaksi pengguna.
  • Proses: Ini adalah referensi yang digunakan untuk pekerjaan dan pengguna.
  • Siklus burst CPU / IO: Mencirikan eksekusi proses, yang berganti-ganti antara aktivitas CPU dan I / O. Waktu CPU biasanya lebih pendek daripada waktu I / O.

Kriteria Penjadwalan CPU

Algoritme penjadwalan CPU mencoba memaksimalkan dan meminimalkan hal berikut:

Maksimalkan:

Pemanfaatan CPU: Pemanfaatan CPU adalah tugas utama di mana sistem operasi perlu memastikan bahwa CPU tetap sesibuk mungkin. Ini dapat berkisar dari 0 hingga 100 persen. Namun, untuk RTOS dapat berkisar dari 40 persen untuk level rendah dan 90 persen untuk sistem level tinggi.

Throughput: Jumlah proses yang menyelesaikan eksekusinya per satuan waktu dikenal Throughput. Jadi, ketika CPU sibuk menjalankan proses, pada saat itu, pekerjaan sedang dilakukan, dan pekerjaan yang diselesaikan per satuan waktu disebut Throughput.

Memperkecil:

Waktu tunggu: Waktu tunggu adalah jumlah yang proses khusus perlu menunggu dalam antrian siap.

Waktu tanggapan: Ini adalah jumlah waktu di mana permintaan diajukan hingga tanggapan pertama dibuat.

Waktu Perputaran: Waktu penyelesaian adalah jumlah waktu untuk menjalankan proses tertentu. Ini adalah perhitungan total waktu yang dihabiskan untuk menunggu masuk ke memori, menunggu dalam antrian dan, mengeksekusi di CPU. Jangka waktu antara waktu pengajuan proses hingga waktu penyelesaian adalah waktu penyelesaian.

Timer Interval

Interupsi timer adalah metode yang terkait erat dengan preemption. Ketika proses tertentu mendapatkan alokasi CPU, pengatur waktu dapat diatur ke interval tertentu. Interupsi timer dan preemption memaksa proses untuk mengembalikan CPU sebelum burst CPU selesai.

Sebagian besar sistem operasi multi-program menggunakan beberapa bentuk pengatur waktu untuk mencegah proses mengikat sistem selamanya.

Apa itu Dispatcher?

Ini adalah modul yang menyediakan kontrol CPU untuk proses tersebut. Dispatcher harus cepat sehingga dapat berjalan di setiap sakelar konteks. Pengiriman latensi adalah jumlah waktu yang dibutuhkan oleh penjadwal CPU untuk menghentikan satu proses dan memulai proses lainnya.

Fungsi yang dilakukan oleh Dispatcher:

  • Pengalihan Konteks
  • Beralih ke mode pengguna
  • Pindah ke lokasi yang benar di program yang baru dimuat.

Jenis Algoritma Penjadwalan CPU

Ada enam jenis algoritma penjadwalan proses

  1. First Come First Serve (FCFS)
  2. Penjadwalan Shortest-Job-First (SJF)
  3. Sisa Waktu Tersingkat
  4. Penjadwalan Prioritas
  5. Penjadwalan Round Robin
  6. Penjadwalan Antrian Bertingkat
Algoritma Penjadwalan

Siapa cepat dia dapat

First Come First Serve adalah bentuk lengkap FCFS. Ini adalah algoritma penjadwalan CPU termudah dan paling sederhana. Dalam jenis algoritme ini, proses yang meminta CPU mendapatkan alokasi CPU terlebih dahulu. Metode penjadwalan ini dapat diatur dengan antrian FIFO.

Saat proses memasuki antrian siap, PCB-nya (Blok Kontrol Proses) dihubungkan dengan ekor antrian. Jadi, saat CPU menjadi bebas, itu harus ditugaskan ke proses di awal antrian.

Karakteristik metode FCFS:

  • Ini menawarkan algoritma penjadwalan non-preemptive dan pre-emptive.
  • Pekerjaan selalu dijalankan atas dasar siapa cepat dia dapat
  • Mudah diimplementasikan dan digunakan.
  • Namun, metode ini memiliki kinerja yang buruk, dan waktu tunggu umumnya cukup tinggi.

Sisa Waktu Tersingkat

Bentuk lengkap SRT adalah sisa waktu terpendek. Ini juga dikenal sebagai penjadwalan preemptive SJF. Dalam metode ini, proses akan dialokasikan ke tugas yang paling dekat dengan penyelesaiannya. Metode ini mencegah proses status siap yang lebih baru menahan penyelesaian proses yang lebih lama.

Karakteristik metode penjadwalan SRT:

  • Metode ini sebagian besar diterapkan di lingkungan batch di mana pekerjaan singkat harus diberikan preferensi.
  • Ini bukan metode yang ideal untuk menerapkannya dalam sistem bersama di mana waktu CPU yang diperlukan tidak diketahui.
  • Mengasosiasikan dengan setiap proses sebagai panjang ledakan CPU berikutnya. Sehingga sistem operasi menggunakan panjang ini, yang membantu menjadwalkan proses dengan waktu sesingkat mungkin.

Penjadwalan Berbasis Prioritas

Penjadwalan prioritas adalah metode proses penjadwalan berdasarkan prioritas. Dalam metode ini, penjadwal memilih tugas untuk bekerja sesuai prioritas.

Penjadwalan prioritas juga membantu OS untuk melibatkan penetapan prioritas. Proses dengan prioritas lebih tinggi harus dilakukan terlebih dahulu, sedangkan pekerjaan dengan prioritas yang sama dilakukan secara round-robin atau FCFS. Prioritas dapat ditentukan berdasarkan kebutuhan memori, persyaratan waktu, dll.

Penjadwalan Round-Robin

Round robin adalah algoritma penjadwalan tertua dan paling sederhana. Nama algoritma ini berasal dari prinsip round-robin, di mana setiap orang mendapat bagian yang sama dari sesuatu secara bergantian. Ini sebagian besar digunakan untuk menjadwalkan algoritma dalam multitasking. Metode algoritma ini membantu eksekusi proses tanpa kelaparan.

Karakteristik Penjadwalan Round-Robin

  • Round robin adalah model hybrid yang digerakkan oleh jam
  • Bagian waktu harus minimum, yang ditetapkan untuk tugas tertentu yang akan diproses. Namun, ini mungkin berbeda untuk proses yang berbeda.
  • Ini adalah sistem waktu nyata yang menanggapi acara dalam batas waktu tertentu.

Pekerjaan Terpendek Pertama

SJF adalah bentuk lengkap (Shortest job first) adalah algoritma penjadwalan dimana proses dengan waktu eksekusi terpendek harus dipilih untuk eksekusi selanjutnya. Metode penjadwalan ini dapat bersifat preemptive atau non-preemptive. Ini secara signifikan mengurangi waktu tunggu rata-rata untuk proses lain yang menunggu eksekusi.

Karakteristik Penjadwalan SJF

  • Ini terkait dengan setiap pekerjaan sebagai unit waktu untuk diselesaikan.
  • Dalam metode ini, ketika CPU tersedia, proses atau pekerjaan berikutnya dengan waktu penyelesaian terpendek akan dijalankan terlebih dahulu.
  • Ini Diimplementasikan dengan kebijakan non-preemptive.
  • Metode algoritme ini berguna untuk pemrosesan tipe batch, di mana menunggu pekerjaan selesai tidak penting.
  • Ini meningkatkan hasil pekerjaan dengan menawarkan pekerjaan yang lebih pendek, yang harus dijalankan terlebih dahulu, yang sebagian besar memiliki waktu penyelesaian yang lebih pendek.

Penjadwalan Antrian Beberapa Tingkat

Algoritme ini memisahkan antrean siap menjadi berbagai antrean terpisah. Dalam metode ini, proses ditugaskan ke antrian berdasarkan properti tertentu dari proses tersebut, seperti prioritas proses, ukuran memori, dll.

Namun, ini bukan algoritma OS penjadwalan independen karena perlu menggunakan jenis algoritma lain untuk menjadwalkan pekerjaan.

Karakteristik Penjadwalan Antrian Bertingkat:

  • Beberapa antrian harus dipertahankan untuk proses dengan beberapa karakteristik.
  • Setiap antrian mungkin memiliki algoritme penjadwalan terpisah.
  • Prioritas diberikan untuk setiap antrian.

Tujuan dari algoritma Penjadwalan

Berikut alasan penggunaan algoritme penjadwalan:

  • CPU menggunakan penjadwalan untuk meningkatkan efisiensinya.
  • Ini membantu Anda mengalokasikan sumber daya di antara proses yang bersaing.
  • Pemanfaatan CPU secara maksimal dapat diperoleh dengan multi-pemrograman.
  • Proses yang akan dieksekusi berada dalam antrian siap.

Ringkasan:

  • Penjadwalan CPU adalah proses menentukan proses mana yang akan memiliki CPU untuk dieksekusi sementara proses lain ditunda.
  • Dalam Penjadwalan Terlebih Dahulu, sebagian besar tugas ditetapkan dengan prioritasnya.
  • Dalam metode penjadwalan Non-preemptive, CPU telah dialokasikan ke proses tertentu.
  • Waktu burst adalah waktu yang diperlukan untuk proses menyelesaikan eksekusi. Ini juga disebut waktu berjalan.
  • Pemanfaatan CPU adalah tugas utama di mana sistem operasi perlu memastikan bahwa CPU tetap sesibuk mungkin
  • Jumlah proses yang menyelesaikan eksekusinya per satuan waktu dikenal Throughput.
  • Waktu tunggu adalah jumlah yang proses khusus perlu menunggu dalam antrian siap.
  • Ini adalah jumlah waktu di mana permintaan dikirim hingga tanggapan pertama dibuat.
  • Waktu penyelesaian adalah jumlah waktu untuk menjalankan proses tertentu.
  • Interupsi timer adalah metode yang berkaitan erat dengan preemption,
  • Dispatcher adalah modul yang menyediakan kontrol CPU untuk proses tersebut.
  • Enam jenis algoritma penjadwalan proses adalah:
  • First Come First Serve (FCFS), 2) Penjadwalan Shortest-Job-First (SJF) 3) Sisa Waktu Tersingkat 4) Penjadwalan Prioritas 5) Penjadwalan Round Robin 6) Penjadwalan Antrian Multilevel
  • Dalam metode First Come First Serve, proses yang meminta CPU mendapatkan alokasi CPU terlebih dahulu.
  • Dalam waktu Tersingkat, proses akan dialokasikan ke tugas, yang paling dekat dengan penyelesaiannya.
  • Di, Penjadwalan Prioritas, penjadwal memilih tugas untuk bekerja sesuai prioritas.
  • Dalam, penjadwalan Round robin ini bekerja berdasarkan prinsip, di mana setiap orang mendapat bagian yang sama dari sesuatu secara bergantian
  • Dalam pekerjaan terpendek dulu, waktu eksekusi terpendek harus dipilih untuk eksekusi berikutnya
  • Dalam penjadwalan bertingkat, metode memisahkan antrian siap menjadi berbagai antrian terpisah. Dalam metode ini, proses ditugaskan ke antrian berdasarkan properti tertentu
  • CPU menggunakan penjadwalan untuk meningkatkan efisiensinya.