Algoritma Penjadwalan FCFS: Apa itu, Contoh Program

Oleh: Natanael Brooks Natanael Brooks
Hours Updated

⚡ Ringkasan Cerdas

Penjadwalan First Come First Serve (FIFO) menjalankan proses sesuai urutan tepat saat proses tersebut mencapai antrian siap, menggunakan pendekatan FIFO non-preemptif sederhana yang menjadikannya algoritma penjadwalan CPU termudah untuk diimplementasikan oleh sistem operasi.

  • 🔄 Definisi: FCFS menetapkan CPU ke proses mana pun yang memintanya terlebih dahulu, mengelola antrian siap pakai sebagai struktur masuk pertama, keluar pertama (FIFO).
  • ⚙️ Alam: FCFS bersifat non-preemptif, sehingga proses yang sedang berjalan akan memegang CPU hingga menyelesaikan seluruh waktu eksekusinya.
  • ️ Analogi: Seperti antrean di loket tiket, proses yang tiba lebih dulu akan dilayani terlebih dahulu, dan yang datang kemudian menunggu giliran mereka.
  • 📊 Perhitungan: Waktu tunggu rata-rata ditemukan dengan subtracmenghitung waktu kedatangan setiap proses dari waktu mulainya, kemudian mengambil rata-rata dari semua proses.
  • 🐢 Efek konvoi: Satu proses panjang di bagian depan memaksa pekerjaan yang lebih pendek untuk menunggu, meningkatkan waktu tunggu rata-rata dan menurunkan kinerja.
  • 🤖 Sudut pandang AI: Pembelajaran mesin memprediksi waktu eksekusi untuk meningkatkan penjadwalan, dan Copilot membantu menulis dan menguji kode FCFS dengan cepat.
Baca Selengkapnya

Algoritma Penjadwalan FCFS dalam OperaSistem ting

Apa itu Metode First Come First Serve?

Pertama Datang Pertama Dilayani (FCFS) FCFS adalah algoritma penjadwalan sistem operasi yang secara otomatis mengeksekusi permintaan dan proses yang diantrekan sesuai urutan kedatangannya. Ini adalah algoritma penjadwalan CPU yang paling mudah dan sederhana. Dalam algoritma ini, proses yang meminta CPU terlebih dahulu akan mendapatkan alokasi CPU terlebih dahulu. Hal ini dikelola dengan antrean FIFO. Singkatan FCFS adalah First Come First Serve (Pertama Datang, Pertama Dilayani).

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

Karakteristik Metode FCFS

Berikut adalah karakteristik utama dari metode First Come First Serve (SIA):

  • Ini adalah tidak preemptif algoritma penjadwalan, sehingga suatu proses mempertahankan CPU hingga menyelesaikan waktu eksekusinya.
  • Pekerjaan selalu dilaksanakan berdasarkan siapa yang datang lebih dulu dilayani.
  • Sangat mudah untuk diterapkan dan digunakan.
  • Metode ini memiliki kinerja yang buruk, dan waktu tunggu secara umum cukup lama.

Contoh Penjadwalan FCFS

Contoh nyata dari metode FCFS adalah membeli tiket film di loket. Dalam algoritma penjadwalan ini, seseorang dilayani sesuai urutan antrian. Orang yang tiba pertama di antrian membeli tiket terlebih dahulu, kemudian orang berikutnya. Ini berlanjut hingga orang terakhir di antrian membeli tiket. Dengan menggunakan algoritma ini, proses CPU bekerja dengan cara yang serupa.

Bagaimana FCFS Bekerja? Menghitung Waktu Tunggu Rata-Rata

Untuk memahami bagaimana algoritma menjadwalkan proses, berikut adalah contoh lima proses yang tiba pada waktu yang berbeda. Setiap proses memiliki waktu eksekusi (burst time) yang berbeda.

Proses Waktu meledak Jam kedatangan
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Dengan menggunakan algoritma penjadwalan FCFS, proses ini ditangani sebagai berikut.

Langkah 1) Proses dimulai dengan P4, yang memiliki waktu kedatangan 0.

Contoh penjadwalan FCFS langkah 1

Langkah 2) Pada waktu=1, P3 tiba. P4 masih dijalankan. Oleh karena itu, P3 disimpan dalam antrian.

Contoh penjadwalan FCFS langkah 2

Langkah 3) Pada waktu=2, P1 tiba dan tetap berada dalam antrian.

Contoh penjadwalan FCFS langkah 3

Langkah 4) Pada waktu=3, proses P4 menyelesaikan eksekusinya.

Contoh penjadwalan FCFS langkah 4

ARTIKEL TERKAIT

Langkah 5) Pada waktu=4, P3 yang berada di urutan pertama dalam antrian memulai eksekusi.

Contoh penjadwalan FCFS langkah 5

Langkah 6) Pada waktu=5, P2 tiba dan ditempatkan dalam antrian.

Contoh penjadwalan FCFS langkah 6

Langkah 7) Pada waktu=11, P3 menyelesaikan eksekusinya.

Contoh penjadwalan FCFS langkah 7

Langkah 8) Pada waktu=11, P1 mulai dieksekusi. Ia memiliki waktu eksekusi (burst time) sebesar 6, sehingga eksekusinya selesai pada interval waktu 17.

Contoh penjadwalan FCFS langkah 8

Langkah 9) Pada waktu=17, P5 mulai dieksekusi. Ia memiliki waktu eksekusi beruntun (burst time) sebesar 4, sehingga eksekusinya selesai pada waktu=21.

Contoh penjadwalan FCFS langkah 9

Langkah 10) Pada waktu=21, P2 mulai dieksekusi. Ia memiliki waktu eksekusi (burst time) sebesar 2, sehingga eksekusinya selesai pada interval waktu 23.

Contoh penjadwalan FCFS langkah 10

Langkah 11) Sekarang, mari kita hitung waktu tunggu rata-rata untuk contoh di atas.

Waktu tunggu rata-rata penjadwalan FCFS

Waiting time = Start time - Arrival time

P4 = 0 – 0 = 0

P3 = 3 – 1 = 2

P1 = 11 – 2 = 9

P5 = 17 – 4 = 13

P2 = 21 – 5 = 16

Waktu Tunggu Rata-Rata = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8

Perhitungan waktu tunggu rata-rata penjadwalan FCFS

Keuntungan FCFS

Berikut adalah kelebihan dan manfaat menggunakan algoritma penjadwalan FCFS:

  • Ini adalah bentuk paling sederhana dari sebuah Algoritma penjadwalan CPU.
  • Ini mudah diprogram.
  • Sistemnya sederhana, yaitu siapa cepat dia dapat.

Kekurangan FCFS

Berikut adalah kekurangan dan kelemahan penggunaan algoritma penjadwalan FCFS:

  • Ini adalah algoritma penjadwalan CPU non-preemptif, jadi begitu sebuah proses dialokasikan ke CPU, proses tersebut tidak akan pernah melepaskan CPU sampai selesai dieksekusi.
  • Rata-rata waktu tunggu cukup tinggi.
  • Proses singkat di bagian belakang antrian harus menunggu proses panjang di bagian depan selesai.
  • Ini bukanlah teknik yang ideal untuk sistem berbagi waktu.
  • Karena kesederhanaannya, FCFS tidak terlalu efisien.

Pertanyaan Umum Demo Slot

First Come First Serve (FCFS) adalah algoritma non-preemptif. Begitu suatu proses mendapatkan CPU, proses tersebut akan berjalan hingga durasi eksekusinya selesai, sehingga penjadwal tidak dapat menginterupsinya untuk menjalankan proses yang baru datang atau yang durasi eksekusinya lebih singkat.

Efek konvoi terjadi ketika beberapa proses pendek menunggu di belakang satu proses panjang di bagian depan antrian. Pekerjaan panjang tunggal ini meningkatkan waktu tunggu rata-rata dan menurunkan throughput CPU secara keseluruhan.

Waktu penyelesaian (turnaround time) sama dengan waktu penyelesaian dikurangi waktu kedatangan untuk setiap proses. Ini mengukur total waktu yang dihabiskan suatu proses dalam sistem, dari saat kedatangannya hingga selesai dieksekusi di CPU.

FCFS (First Come First Served/Pesanan Pertama Dilayani Berdasarkan Urutan Kedatangan), Pekerjaan Terpendek Terlebih Dahulu melayani pesanan dengan jumlah terkecil terlebih dahulu untuk mengurangi waktu tunggu, dan Round Robin memberikan setiap proses alokasi waktu tetap untuk pembagian waktu.

Algoritma FCFS murni tidak menyebabkan kelaparan (starvation), karena setiap proses pada akhirnya akan mencapai bagian depan antrian FIFO. Namun, pekerjaan yang panjang masih dapat menunda pekerjaan yang pendek secara signifikan melalui efek konvoi.

FCFS berjalan dalam waktu O(n) ketika proses sudah diurutkan berdasarkan waktu kedatangan, karena setiap proses dijadwalkan sekali. Mengurutkan kedatangan yang belum diurutkan berdasarkan waktu kedatangan terlebih dahulu menambahkan langkah O(n log n).

Model pembelajaran mesin memprediksi waktu puncak proses dan memilih atau menyesuaikan kebijakan penjadwalan untuk mengurangi waktu tunggu rata-rata dan penggunaan energi. Para peneliti menerapkan penjadwal berbasis AI ini di server cloud dan pusat data.

Ya. GitHub Copilot dapat menghasilkan kode FCFS dalam bahasa C. Java, atau Python dengan perhitungan waktu tunggu dan waktu penyelesaian. Selalu verifikasi pengurutan waktu kedatangan, pemecahan kebuntuan, dan rumus rata-rata sebelum mempercayai hasilnya.

Ringkaslah postingan ini dengan: