Algoritma Penjadualan CPU dalam Sistem Operasi

Isi kandungan:

Anonim

Apakah Penjadualan CPU?

Penjadualan CPU adalah proses menentukan proses mana yang akan dimiliki CPU untuk pelaksanaan sementara proses lain ditangguhkan. Tugas utama penjadwalan CPU adalah memastikan bahawa setiap kali CPU tetap tidak berfungsi, OS setidaknya memilih salah satu proses yang tersedia dalam antrian siap untuk pelaksanaan. Proses pemilihan akan dilakukan oleh penjadual CPU. Ia memilih salah satu proses dalam memori yang siap untuk dilaksanakan.

Dalam tutorial penjadualan CPU ini, anda akan belajar:

  • Apakah penjadualan CPU?
  • Jenis Penjadualan CPU
  • Terminologi penjadualan CPU yang penting
  • Kriteria Penjadualan CPU
  • Pemasa Selang
  • Apa itu Penghantar?
  • Jenis Algoritma penjadualan CPU
  • Siapa cepat dia yang dapat
  • Sisa Masa Terpendek
  • Penjadualan Berdasarkan Keutamaan
  • Penjadualan Round-Robin
  • Pekerjaan Terpendek Pertama
  • Penjadualan Antrian Pelbagai Peringkat
  • Tujuan algoritma Penjadualan

Jenis Penjadualan CPU

Berikut adalah dua jenis kaedah Penjadualan:

Penjadualan Awal

Dalam Penjadualan Preemptive, tugas-tugas kebanyakannya diberikan mengikut keutamaannya. Kadang-kadang penting untuk menjalankan tugas dengan keutamaan yang lebih tinggi sebelum tugas dengan keutamaan yang lebih rendah, walaupun tugas dengan prioriti yang lebih rendah masih berjalan. Tugas keutamaan yang lebih rendah ditahan selama beberapa waktu dan disambung semula apabila tugas dengan keutamaan yang lebih tinggi menyelesaikan pelaksanaannya.

Penjadualan Bukan Pencegahan

Dalam kaedah penjadualan jenis ini, CPU telah dialokasikan untuk proses tertentu. Proses yang membuat CPU sibuk akan melepaskan CPU sama ada dengan menukar konteks atau menghentikan. Ini adalah satu-satunya kaedah yang boleh digunakan untuk pelbagai platform perkakasan. Ini kerana ia tidak memerlukan perkakasan khas (misalnya, pemasa) seperti penjadualan awal.

Semasa penjadualan adalah Preemptive atau Non-Preemptive?

Untuk menentukan apakah penjadualan adalah preemptive atau non-preemptive, pertimbangkan empat parameter berikut:

  1. Proses beralih dari keadaan berjalan ke keadaan menunggu.
  2. Proses tertentu beralih dari keadaan berjalan ke keadaan siap.
  3. Proses tertentu beralih dari keadaan menunggu ke keadaan siap.
  4. Proses selesai pelaksanaannya dan ditamatkan.

Hanya syarat 1 dan 4 yang berlaku, penjadualan tersebut disebut bukan preemptive.

Semua penjadualan lain adalah preemptive.

Terminologi penjadualan CPU yang penting

  • Waktu Meletup / Waktu Pelaksanaan: Ini adalah masa yang diperlukan oleh proses untuk menyelesaikan pelaksanaan. Ia juga dipanggil masa berjalan.
  • Waktu Ketibaan: apabila proses memasuki keadaan siap
  • Waktu Selesai: apabila proses selesai dan keluar dari sistem
  • Pelbagai program : Sejumlah program yang dapat hadir dalam memori pada masa yang sama.
  • Pekerjaan: Ini adalah jenis program tanpa interaksi pengguna.
  • Pengguna: Ini adalah sejenis program yang mempunyai interaksi pengguna.
  • Proses: Merupakan rujukan yang digunakan untuk pekerjaan dan pengguna.
  • Kitaran pecah CPU / IO: Mencirikan pelaksanaan proses, yang bergantian antara aktiviti CPU dan I / O. Waktu CPU biasanya lebih pendek daripada masa I / O.

Kriteria Penjadualan CPU

Algoritma penjadualan CPU cuba memaksimumkan dan meminimumkan perkara berikut:

Maksimumkan:

Penggunaan CPU: Penggunaan CPU adalah tugas utama di mana sistem operasi perlu memastikan bahawa CPU tetap sibuk. Ia boleh berkisar antara 0 hingga 100 peratus. Namun, untuk RTOS, dapat berkisar antara 40 persen untuk tingkat rendah dan 90 persen untuk sistem tingkat tinggi.

Throughput: Jumlah proses yang menyelesaikan pelaksanaannya setiap unit masa diketahui Throughput. Jadi, ketika CPU sibuk menjalankan prosesnya, pada waktu itu, pekerjaan sedang dilakukan, dan kerja yang diselesaikan per unit waktu disebut Throughput.

Minimumkan:

Waktu menunggu: Waktu menunggu adalah jumlah yang perlu ditunggu proses tertentu dalam barisan siap.

Masa respons: Ini adalah jumlah masa di mana permintaan dihantar sehingga respons pertama dihasilkan.

Waktu Putaran: Waktu putaran adalah jumlah masa untuk melaksanakan proses tertentu. Ini adalah perhitungan jumlah masa yang dihabiskan menunggu untuk masuk ke memori, menunggu dalam barisan dan, dijalankan pada CPU. Tempoh antara waktu penyerahan proses hingga waktu penyelesaian adalah waktu pemulihan.

Pemasa Selang

Gangguan pemasa adalah kaedah yang berkait rapat dengan pencegahan. Apabila proses tertentu mendapat peruntukan CPU, pemasa dapat ditetapkan ke selang waktu yang ditentukan. Kedua-dua gangguan pemasa dan preemption memaksa proses mengembalikan CPU sebelum burst CPU selesai.

Sebilangan besar sistem operasi berbilang program menggunakan beberapa bentuk pemasa untuk mengelakkan proses mengikat sistem selama-lamanya.

Apa itu Penghantar?

Ia adalah modul yang menyediakan kawalan CPU untuk prosesnya. Dispatcher harus cepat sehingga dapat berjalan di setiap suis konteks. Latency pengiriman adalah jumlah masa yang diperlukan oleh penjadual CPU untuk menghentikan satu proses dan memulakan proses yang lain.

Fungsi yang dilakukan oleh Dispatcher:

  • Pertukaran Konteks
  • Beralih ke mod pengguna
  • Berpindah ke lokasi yang betul dalam program yang baru dimuat.

Jenis Algoritma penjadualan CPU

Terdapat terutamanya enam jenis algoritma penjadualan proses

  1. Servis First Come First (FCFS)
  2. Penjadualan Terpendek-Pekerjaan-Pertama (SJF)
  3. Sisa Masa Terpendek
  4. Penjadualan Keutamaan
  5. Penjadualan Robin Bulat
  6. Penjadualan Antrian Bertingkat
Algoritma Penjadualan

Siapa cepat dia yang dapat

First Come First Serve adalah bentuk penuh FCFS. Ini adalah algoritma penjadualan CPU yang paling mudah dan sederhana. Dalam jenis algoritma ini, proses yang meminta CPU mendapat peruntukan CPU terlebih dahulu. Kaedah penjadualan ini dapat dikendalikan dengan barisan FIFO.

Ketika proses memasuki barisan siap, PCBnya (Proses Kawalan Blok) dihubungkan dengan ekor barisan. Jadi, apabila CPU menjadi bebas, ia harus ditugaskan untuk proses pada awal barisan.

Ciri-ciri kaedah FCFS:

  • Ia menawarkan algoritma penjadualan bukan preemptive dan pre-emptive.
  • Pekerjaan selalu dilaksanakan berdasarkan 'first-come, first-melayani'
  • Ia mudah dilaksanakan dan digunakan.
  • Walau bagaimanapun, kaedah ini berprestasi rendah, dan masa menunggu umum agak tinggi.

Sisa Masa Terpendek

Bentuk penuh SRT adalah baki masa terpendek. Ia juga dikenali sebagai penjadualan preemptive SJF. Dalam kaedah ini, proses akan dialokasikan untuk tugas, yang hampir selesai. Kaedah ini menghalang proses keadaan siap yang lebih baru daripada menahan proses yang lebih lama.

Ciri-ciri kaedah penjadualan SRT:

  • Kaedah ini kebanyakannya diterapkan dalam lingkungan batch di mana pekerjaan pendek diperlukan untuk diberi keutamaan.
  • Ini bukan kaedah yang ideal untuk menerapkannya dalam sistem bersama di mana masa CPU yang diperlukan tidak diketahui.
  • Kaitkan dengan setiap proses sebagai panjang CPU seterusnya. Sehingga sistem operasi menggunakan panjang ini, yang membantu menjadualkan proses dengan waktu sesingkat mungkin.

Penjadualan Berdasarkan Keutamaan

Penjadualan keutamaan adalah kaedah proses penjadualan berdasarkan keutamaan. Dalam kaedah ini, penjadual memilih tugas yang akan dikerjakan sesuai keutamaan.

Penjadualan keutamaan juga membantu OS untuk melibatkan penugasan keutamaan. Proses dengan keutamaan yang lebih tinggi harus dilakukan terlebih dahulu, sedangkan pekerjaan dengan keutamaan yang sama dilakukan berdasarkan round-robin atau FCFS. Keutamaan dapat diputuskan berdasarkan keperluan memori, keperluan masa, dll.

Penjadualan Round-Robin

Round robin adalah algoritma penjadualan tertua dan termudah. Nama algoritma ini berasal dari prinsip round-robin, di mana setiap orang mendapat bahagian yang sama dari sesuatu pada gilirannya. Ia kebanyakannya digunakan untuk penjadualan algoritma dalam multitasking. Kaedah algoritma ini membantu pelaksanaan proses kebuluran secara percuma.

Ciri Penjadualan Round-Robin

  • Round robin adalah model hibrid yang didorong oleh jam
  • Potongan waktu harus minimum, yang ditugaskan untuk tugas tertentu untuk diproses. Walau bagaimanapun, ia mungkin berbeza untuk proses yang berbeza.
  • Ini adalah sistem masa nyata yang bertindak balas terhadap peristiwa tersebut dalam had waktu tertentu.

Pekerjaan Terpendek Pertama

SJF adalah bentuk penuh (pekerjaan terpendek pertama) adalah algoritma penjadualan di mana proses dengan masa pelaksanaan terpendek harus dipilih untuk pelaksanaan berikutnya. Kaedah penjadualan ini boleh bersifat preemptive atau non-preemptive. Ini secara signifikan mengurangkan purata masa menunggu proses lain yang menunggu pelaksanaan.

Ciri Penjadualan SJF

  • Ia dikaitkan dengan setiap pekerjaan sebagai satu unit masa untuk diselesaikan.
  • Dalam kaedah ini, apabila CPU tersedia, proses atau pekerjaan berikutnya dengan waktu penyelesaian terpendek akan dilaksanakan terlebih dahulu.
  • Ia Dilaksanakan dengan dasar bukan preemptive.
  • Kaedah algoritma ini berguna untuk pemprosesan jenis kumpulan, di mana menunggu pekerjaan selesai tidak penting.
  • Ini meningkatkan output pekerjaan dengan menawarkan pekerjaan yang lebih pendek, yang harus dilaksanakan terlebih dahulu, yang kebanyakannya mempunyai waktu perputaran yang lebih pendek.

Penjadualan Antrian Pelbagai Peringkat

Algoritma ini memisahkan giliran siap menjadi pelbagai barisan berasingan. Dalam kaedah ini, proses ditugaskan ke barisan berdasarkan sifat tertentu proses, seperti keutamaan proses, ukuran memori, dll.

Namun, ini bukan algoritma penjadualan OS yang bebas kerana perlu menggunakan jenis algoritma lain untuk menjadualkan tugas.

Ciri Penjadualan Antrian Pelbagai Tahap:

  • Beberapa barisan harus dikekalkan untuk proses dengan beberapa ciri.
  • Setiap barisan mungkin mempunyai algoritma penjadualan tersendiri.
  • Keutamaan diberikan untuk setiap barisan.

Tujuan algoritma Penjadualan

Berikut adalah sebab untuk menggunakan algoritma penjadualan:

  • CPU menggunakan penjadualan untuk meningkatkan kecekapannya.
  • Ini membantu anda memperuntukkan sumber di antara proses yang bersaing.
  • Penggunaan CPU maksimum dapat diperoleh dengan multi-pengaturcaraan.
  • Proses yang akan dijalankan berada dalam barisan siap.

Ringkasan:

  • Penjadualan CPU adalah proses menentukan proses mana yang akan dimiliki CPU untuk pelaksanaan sementara proses lain ditangguhkan.
  • Dalam Penjadualan Preemptive, tugas-tugas kebanyakannya diberikan mengikut keutamaannya.
  • Dalam kaedah penjadualan Non-preemptive, CPU telah dialokasikan untuk proses tertentu.
  • Waktu pecah adalah masa yang diperlukan untuk proses menyelesaikan pelaksanaan. Ia juga dipanggil masa berjalan.
  • Penggunaan CPU adalah tugas utama di mana sistem operasi perlu memastikan bahawa CPU tetap sibuk
  • Jumlah proses yang menyelesaikan pelaksanaannya per unit masa diketahui Throughput.
  • Waktu menunggu adalah jumlah yang perlu ditunggu proses tertentu dalam barisan siap.
  • Ini adalah jumlah masa di mana permintaan itu diserahkan sehingga respons pertama dihasilkan.
  • Waktu pemulihan adalah jumlah masa untuk melaksanakan proses tertentu.
  • Gangguan pemasa adalah kaedah yang berkait rapat dengan pencegahan,
  • Penghantar adalah modul yang menyediakan kawalan CPU untuk prosesnya.
  • Enam jenis algoritma penjadualan proses adalah:
  • Servis First Come First (FCFS), 2) Penjadualan Kerja Terpendek-Pertama (SJF) 3) Waktu Sisa Terpendek 4) Penjadualan Keutamaan 5) Penjadualan Robin Bulat 6) Penjadualan Antrian Tahap Bertingkat
  • Dalam kaedah First Come First Serve, proses yang meminta CPU mendapat peruntukan CPU terlebih dahulu.
  • Dalam Sisa Waktu Terpendek, proses akan dialokasikan untuk tugas, yang hampir selesai.
  • Dalam, Priority Penjadwalan penjadual memilih tugas yang akan dikerjakan sesuai prioriti.
  • Dalam, penjadualan Round robin ini berfungsi pada asasnya, di mana setiap orang mendapat bahagian yang sama dari sesuatu pada gilirannya
  • Dalam pekerjaan terpendek pertama, masa pelaksanaan terpendek harus dipilih untuk pelaksanaan berikutnya
  • Dalam penjadualan bertingkat, kaedah memisahkan giliran siap menjadi pelbagai barisan berasingan. Dalam kaedah ini, proses ditugaskan ke barisan berdasarkan sifat tertentu
  • CPU menggunakan penjadualan untuk meningkatkan kecekapannya.