Penjadwalan CPU Algorithms in OperaSistem

Oleh: Natanael Brooks Natanael Brooks
Hours Updated

⚡ Ringkasan Cerdas

Penjadwalan CPU menentukan proses mana yang siap dijalankan sistem operasi selanjutnya, menjagaping Prosesor sibuk dan meningkatkan kinerja melalui algoritma seperti First Come First Serve, Shortest Job First, Priority, dan Round Robin.

  • 🔄 Definisi: Penjadwalan CPU memilih proses dari antrian siap (ready queue) setiap kali CPU dalam keadaan menganggur.
  • ️ jenis: Penjadwalan preemptif dapat menginterupsi tugas yang sedang berjalan, sedangkan penjadwalan non-preemptif menunggu hingga tugas tersebut melepaskan CPU.
  • 📊 Kriteria: Algoritma yang baik memaksimalkan pemanfaatan CPU dan throughput sekaligus meminimalkan waktu tunggu, respons, dan penyelesaian.
  • 🧮 Algorithms: FCFS, SJF, Shortest Remaining Time, Priority, Round Robin, dan Multilevel Queue masing-masing cocok untuk beban kerja yang berbeda.
  • 🚦 pengirim: Dispatcher melakukan peralihan konteks yang menyerahkan kendali CPU ke proses yang dipilih.
  • 🤖 Sudut Pandang AI: Pembelajaran mesin menyempurnakan keputusan penjadwalan, dan Copilot membantu dalam pengkodean dan pengujian algoritma penjadwal.
Baca Selengkapnya

Penjadwalan CPU Algorithms in OperaSistem

Apa itu Penjadwalan CPU?

Penjadwalan CPU Penjadwalan CPU adalah proses menentukan proses mana yang akan memiliki CPU untuk dieksekusi sementara proses lain sedang menunggu. Tugas utama penjadwalan CPU adalah memastikan bahwa setiap kali CPU tetap menganggur, sistem operasi memilih setidaknya satu dari proses yang tersedia dalam antrian siap untuk dieksekusi. Proses pemilihan dilakukan oleh penjadwal CPU, yang memilih salah satu proses dalam memori yang siap untuk dieksekusi.

Jenis Penjadwalan CPU

Berikut adalah dua jenis metode penjadwalan:

Jenis Penjadwalan CPU

Penjadwalan Preemptive

Dalam penjadwalan preemptif, tugas-tugas sebagian besar ditetapkan berdasarkan prioritasnya. Terkadang penting untuk menjalankan tugas dengan prioritas lebih tinggi sebelum tugas dengan prioritas lebih rendah, meskipun tugas dengan prioritas lebih rendah tersebut masih berjalan. Tugas dengan prioritas lebih rendah akan berhenti untuk beberapa waktu dan melanjutkan eksekusinya ketika tugas dengan prioritas lebih tinggi selesai.

Penjadwalan Non-Preemptive

Dalam metode penjadwalan jenis ini, CPU dialokasikan ke proses tertentu. Proses yang membuat CPU sibuk akan melepaskan CPU baik dengan beralih konteks atau mengakhiri prosesnya. Ini adalah satu-satunya metode yang dapat digunakan di berbagai platform perangkat keras, karena tidak memerlukan perangkat keras khusus (misalnya, timer) seperti penjadwalan preemptif.

Kapan Penjadwalan Bersifat Preemptif atau Non-Preemptif?

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

  1. Suatu proses beralih dari keadaan berjalan ke keadaan menunggu.
  2. Suatu proses tertentu beralih dari status berjalan ke status siap.
  3. Suatu proses tertentu beralih dari status menunggu ke status siap.
  4. Suatu proses menyelesaikan eksekusinya dan berakhir.

Jika hanya kondisi 1 dan 4 yang berlaku, penjadwalan disebut non-preemptif. Semua situasi penjadwalan lainnya bersifat preemptif.

Terminologi Penting Penjadwalan CPU

  • Waktu Burst/Waktu Eksekusi: Waktu yang dibutuhkan suatu proses untuk menyelesaikan eksekusinya. Ini juga disebut waktu berjalan.
  • Jam kedatangan: Waktu ketika suatu proses memasuki keadaan siap.
  • Waktu Selesai: Waktu ketika suatu proses selesai dan keluar dari sistem.
  • Multiprogram: Sejumlah program yang dapat berada di memori secara bersamaan.
  • Pekerjaan: Suatu jenis program tanpa interaksi pengguna sama sekali.
  • Pengguna: Suatu jenis program yang memiliki interaksi pengguna.
  • Proses: Referensi yang digunakan baik untuk pekerjaan maupun pengguna.
  • Siklus ledakan CPU/IO: Menggambarkan eksekusi proses, yang bergantian antara aktivitas CPU dan I/O. Waktu CPU biasanya lebih singkat daripada waktu I/O.

Kriteria Penjadwalan CPU

Algoritma penjadwalan CPU mencoba memaksimalkan dan meminimalkan hal berikut:

Kriteria Penjadwalan CPU

Maksimalkan

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

Throughput: Jumlah proses yang menyelesaikan eksekusinya per satuan waktu dikenal sebagai throughput. Jadi, ketika CPU sibuk mengeksekusi suatu proses, pekerjaan sedang dilakukan, dan pekerjaan yang diselesaikan per satuan waktu disebut throughput.

Memperkecil

Waktu menunggu: Waktu tunggu adalah lamanya waktu yang harus ditunggu oleh suatu proses tertentu dalam antrian siap.

Waktu merespon: Ini adalah jangka waktu dari saat permintaan diajukan hingga respons pertama diberikan.

Waktu penyelesaian: Waktu penyelesaian (turnaround time) adalah jumlah waktu yang dibutuhkan untuk mengeksekusi suatu proses tertentu. Ini adalah total waktu yang dihabiskan untuk menunggu masuk ke memori, menunggu dalam antrian, dan mengeksekusi di CPU. Periode antara waktu pengajuan proses dan waktu penyelesaian adalah waktu penyelesaian.

Timer Interval

Interupsi pengatur waktu merupakan salah satu metode yang berkaitan erat dengan preemption. Ketika suatu proses tertentu mendapat alokasi CPU, pengatur waktu dapat diatur ke interval tertentu. Interupsi pengatur waktu dan preemption memaksa suatu proses untuk mengembalikan CPU sebelum ledakan CPU-nya selesai.

Sebagian besar sistem operasi multi-program menggunakan semacam pengatur waktu untuk mencegah suatu proses membebani sistem selamanya.

Apa itu pengirim?

Dispatcher adalah modul yang menyediakan kendali CPU kepada proses. Dispatcher harus cepat, sehingga dapat berjalan pada setiap peralihan konteks. Latensi dispatch adalah jumlah waktu yang dibutuhkan oleh penjadwal CPU untuk menghentikan satu proses dan memulai proses lain.

Fungsi yang dilakukan oleh petugas pengiriman:

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

Jenis Penjadwalan CPU Algorithms

Terutama ada enam jenis algoritma penjadwalan proses:

  1. Pertama Datang Pertama Dilayani (FCFS)
  2. Penjadwalan Pekerjaan Terpendek-Pertama (SJF).
  3. Waktu Tersisa Terpendek
  4. Penjadwalan Prioritas
  5. Penjadwalan Round Robin
  6. Penjadwalan Antrian Bertingkat

Penjadwalan Algorithms

Penjadwalan Algorithms

Siapa cepat dia dapat

FCFS adalah singkatan dari Siapa cepat dia dapatIni adalah algoritma penjadwalan CPU yang paling mudah dan sederhana. Dalam jenis algoritma ini, proses yang meminta CPU akan mendapatkan alokasi CPU terlebih dahulu. Metode penjadwalan ini dapat dikelola dengan antrian FIFO (First-In, First-Out).

Saat suatu proses memasuki antrian siap, PCB (Process Control Block) proses tersebut dihubungkan dengan ujung antrian. Jadi, ketika CPU menjadi bebas, CPU tersebut harus dialokasikan ke proses yang berada di awal antrian.

Karakteristik Metode FCFS

  • Ini adalah algoritma penjadwalan non-preemptif.
  • Pekerjaan selalu dilaksanakan berdasarkan siapa yang datang lebih dulu dilayani.
  • Sangat mudah untuk diterapkan dan digunakan.
  • Namun, kinerja metode ini buruk, dan waktu tunggu secara umum cukup lama.

ARTIKEL TERKAIT

Waktu Tersisa Terpendek

Singkatan SRT adalah Shortest Remaining Time (Waktu Tersisa Terpendek). Metode ini juga dikenal sebagai penjadwalan preemptif SJF. Dalam metode ini, proses akan dialokasikan ke tugas yang paling dekat dengan penyelesaiannya. Metode ini mencegah proses dengan status siap yang lebih baru menghambat penyelesaian proses yang lebih lama.

Karakteristik Metode Penjadwalan SRT

  • Metode ini sebagian besar diterapkan dalam lingkungan pemrosesan batch di mana pekerjaan singkat perlu diprioritaskan.
  • Ini bukanlah metode yang ideal untuk diimplementasikan dalam sistem bersama di mana waktu CPU yang dibutuhkan tidak diketahui.
  • Setiap proses dikaitkan dengan durasi burst CPU berikutnya, sehingga sistem operasi menggunakan durasi ini untuk menjadwalkan proses dengan waktu sesingkat mungkin.

Penjadwalan Berbasis Prioritas

Penjadwalan Prioritas adalah metode penjadwalan proses berdasarkan prioritas. Dalam metode ini, penjadwal memilih tugas-tugas yang akan dikerjakan sesuai dengan prioritasnya.

Penjadwalan prioritas juga membantu sistem operasi dalam menetapkan prioritas. Proses dengan prioritas lebih tinggi dijalankan terlebih dahulu, sedangkan pekerjaan dengan prioritas yang sama dijalankan secara bergilir (round-robin) atau FCFS (First Come First Serve). Prioritas dapat ditentukan berdasarkan kebutuhan memori, kebutuhan waktu, dan faktor lainnya.

Penjadwalan Round-Robin

Usul adalah salah satu algoritma penjadwalan tertua dan paling sederhana. Nama algoritma ini berasal dari prinsip round-robin, di mana setiap orang mendapatkan bagian yang sama secara bergantian. Algoritma ini sebagian besar digunakan untuk penjadwalan dalam sistem multitasking. Metode ini membantu mencapai eksekusi proses tanpa kelaparan (starvation).

Karakteristik Penjadwalan Round-Robin

  • Round robin adalah model hibrida yang digerakkan oleh waktu.
  • Alokasi waktu yang ditetapkan untuk pemrosesan tugas tertentu harus seminimal mungkin. Namun, alokasi waktu tersebut dapat bervariasi untuk proses yang berbeda.
  • Sistem ini berper behaves seperti sistem berbagi waktu yang merespons setiap proses dalam batas waktu tertentu.

Pekerjaan Terpendek Terlebih Dahulu

SJF (Shortest Job First) adalah algoritma penjadwalan di mana proses dengan waktu eksekusi terpendek dipilih untuk dieksekusi selanjutnya. Metode penjadwalan ini dapat bersifat preemptif atau non-preemptif. Metode ini secara signifikan mengurangi waktu tunggu rata-rata untuk proses lain yang menunggu eksekusi.

Karakteristik Penjadwalan SJF

  • Setiap pekerjaan dikaitkan dengan satuan waktu untuk penyelesaiannya.
  • Dalam metode ini, ketika CPU tersedia, proses atau pekerjaan berikutnya dengan waktu penyelesaian terpendek akan dieksekusi terlebih dahulu.
  • Hal ini diimplementasikan dengan kebijakan non-preemptif.
  • Algoritma ini berguna untuk pemrosesan tipe batch, di mana menunggu hingga pekerjaan selesai bukanlah hal yang kritis.
  • Hal ini meningkatkan hasil kerja dengan mengeksekusi pekerjaan yang lebih pendek terlebih dahulu, yang sebagian besar memiliki waktu penyelesaian yang lebih singkat.

Penjadwalan Antrian Bertingkat

Algoritma ini memisahkan antrian siap (ready queue) menjadi beberapa antrian terpisah. Dalam metode ini, proses ditugaskan ke antrian berdasarkan properti spesifik dari proses tersebut, seperti prioritas proses, ukuran memori, dan sebagainya.

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

Karakteristik Penjadwalan Antrian Bertingkat

  • Beberapa antrian harus dipelihara untuk proses-proses dengan karakteristik yang sama.
  • Setiap antrian mungkin memiliki algoritma penjadwalan tersendiri.
  • Prioritas diberikan kepada setiap antrian.

Tujuan dari Algoritma Penjadwalan

Berikut alasan penggunaan algoritma penjadwalan:

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

Pertanyaan Umum Demo Slot

Tidak ada satu algoritma terbaik pun. Shortest Job First memberikan waktu tunggu rata-rata terendah dan terbukti optimal, tetapi membutuhkan waktu pemrosesan yang diketahui dan dapat menyebabkan pekerjaan yang memakan waktu lama menjadi tidak dapat diproses. Round Robin lebih adil untuk sistem berbagi waktu.

Kelaparan terjadi ketika suatu proses menunggu tanpa batas waktu karena pekerjaan dengan prioritas lebih tinggi atau lebih pendek terus mendapatkan CPU terlebih dahulu. Hal ini umum terjadi pada penjadwalan Prioritas dan Pekerjaan Terpendek Pertama (Priority and Shortest Job First), di mana proses yang panjang atau berprioritas rendah mungkin tidak pernah dijalankan.

Aging adalah teknik yang secara bertahap meningkatkan prioritas proses yang telah menunggu lama. Hal ini mencegah kelaparan (starvation) dalam penjadwalan berbasis prioritas, karena bahkan proses dengan prioritas rendah pada akhirnya akan mencapai prioritas yang cukup tinggi untuk dijalankan.

Pengalihan konteks menyimpan status proses saat ini dan memuat status proses lain dari PCB-nya, sehingga eksekusi dapat dilanjutkan nanti. Ini murni merupakan overhead penjadwalan yang ditangani oleh dispatcher pada setiap peralihan antar proses.

Penjadwal jangka panjang (pekerjaan) mengontrol berapa banyak proses yang masuk ke antrian siap dan menetapkan tingkat multiprogramming. Penjadwal jangka pendek (CPU) memilih proses siap mana yang akan dijalankan selanjutnya dan berjalan jauh lebih sering.

Linux menggunakan penjadwal EEVDF, yang menggantikan Completely Fair Scheduler (CFS) pada kernel 6.6. Windows menggunakan penjadwal berbasis prioritas preemptif dengan pembagian waktu round-robin di dalam setiap tingkat prioritas.

Model pembelajaran mesin memprediksi waktu puncak proses dan menyesuaikan atau memilih kebijakan penjadwalan untuk mengurangi waktu tunggu dan penggunaan energi. Penjadwal berbasis AI ini dipelajari untuk pusat data, server cloud, dan sistem waktu nyata.

Ya. GitHub Copilot dapat menghasilkan kode FCFS, SJF, Prioritas, dan Round Robin beserta bagan Gantt dan perhitungan waktu tunggu. Selalu verifikasi kasus-kasus khusus, aturan pemecahan kebuntuan, dan rumus waktu rata-rata sebelum mengandalkan hasilnya.

Ringkaslah postingan ini dengan: