C প্রোগ্রামিং-এ FCFS শিডিউলিং (FCFS Scheduling)

আমাদের n সংখ্যক প্রসেস দেওয়া আছে অর্থাৎ P1, P2, P3, ......., Pn এবং তাদের সংশ্লিষ্ট বার্স্ট টাইম (burst times)। টাস্ক হলো FCFS CPU শিডিউলিং অ্যালগরিদম ব্যবহার করে অয়েরেজ ওয়েটিং টাইম (average waiting time) এবং অয়েরেজ টার্নআরাউন্ড টাইম (average turnaround time) বের করা।

ওয়েটিং টাইম (Waiting Time) এবং টার্নআরাউন্ড টাইম (Turnaround Time) কী?

• টার্নআরাউন্ড টাইম (Turnaround Time) হল একটি প্রসেস সাবমিশন (submission) এবং এর কমপ্লিশন (completion) এর মাঝপথের টাইম ইন্টারভাল।
  Turnaround Time = completion of a process − submission of a process

• ওয়েটিং টাইম (Waiting Time) হল টার্নআরাউন্ড টাইম এবং বার্স্ট টাইম (burst time)-এর পার্থক্য।
  Waiting Time = turnaround time − burst time

FCFS শিডিউলিং (FCFS Scheduling) কী?

First Come, First Served (FCFS) যাকে First In, First Out (FIFO)-ও বলা হয়, এটি একটি CPU শিডিউলিং অ্যালগরিদম যেখানে CPU প্রসেসগুলোকে রেডি কিউ (ready queue)-তে যেন কতৃক কিউড (queued) আছে সেটি অনুযায়ী অ্যালোকেট করা হয়।

FCFS নন-প্রিপ্টিভ (non-preemptive) শিডিউলিং ফলো করে অর্থাৎ একবার CPU একটি প্রসেসকে অ্যালোকেট করলে এটি CPU ছাড়ে না যতক্ষণ না প্রসেসটি টার্মিনেট (terminate) হয় বা কোনো I/O ইন্টারাপ্ট (interrupt) এর কারণে हाल্ট (halt) হয়।

উদাহরণ (Example)

ধরুন, চারটি প্রসেস আসছে P2, P3, P1 ক্রমে তাদের এক্সিকিউশন টাইমের সাথে টেবিলে দেখানো অনুযায়ী। আর তাদের অ্যারাইভাল টাইম (arrival time) ০ ধরা হয়েছে।

প্রসেস P1, P2 এবং P3-এর সিস্টেমে ওয়েটিং টাইম দেখানো গ্যান্ট চার্ট (Gantt chart):

উপরের চিত্র অনুযায়ী,

• প্রসেস P2-এর ওয়েটিং টাইম ০
• প্রসেস P3-এর ওয়েটিং টাইম ৩
• প্রসেস P1-এর ওয়েটিং টাইম ৬

অয়েরেজ টাইম = (০ + ৩ + ৬) / ৩ = ৩ msec.

যেহেতু অ্যারাইভাল টাইম ০ ধরা হয়েছে, তাই টার্নআরাউন্ড টাইম এবং কমপ্লিশন টাইম একই হবে।

উদাহরণ ইনপুট/আউটপুট

Input:  processes = P1, P2, P3      Burst time = 5, 8, 12
Output:
Processes  Burst  Waiting  Turn around
1          5      0        5
2          8      5        13
3          12     13       25
Average Waiting time = 6.000000
Average turn around time = 14.333333

আলগরিদম (Algorithm)

Start
Step 1 → In function int waitingtime(int proc[], int n, int burst_time[], int wait_time[])
    Set wait_time[0] = 0
    Loop For i = 1 and i < n and i++
        Set wait_time[i] = burst_time[i-1] + wait_time[i-1]
    End For

Step 2 → In function int turnaroundtime(int proc[], int n, int burst_time[], int wait_time[], int tat[])
    Loop For i = 0 and i < n and i++
        Set tat[i] = burst_time[i] + wait_time[i]
    End For

Step 3 → In function int avgtime(int proc[], int n, int burst_time[])
    Declare and initialize wait_time[n], tat[n], total_wt = 0, total_tat = 0
    Call waitingtime(proc, n, burst_time, wait_time)
    Call turnaroundtime(proc, n, burst_time, wait_time, tat)
    Loop For i=0 and i

উদাহরণ (C প্রোগ্রাম)
#include <stdio.h>

// Function to find the waiting time for all processes
int waitingtime(int proc[], int n, int burst_time[], int wait_time[]) {
    wait_time[0] = 0;
    for (int i = 1; i < n; i++)
        wait_time[i] = burst_time[i-1] + wait_time[i-1];
    return 0;
}

// Function to calculate turn around time
int turnaroundtime(int proc[], int n, int burst_time[], int wait_time[], int tat[]) {
    int i;
    for (i = 0; i < n; i++)
        tat[i] = burst_time[i] + wait_time[i];
    return 0;
}

// Function to calculate average time
int avgtime(int proc[], int n, int burst_time[]) {
    int wait_time[n], tat[n], total_wt = 0, total_tat = 0;
    int i;
    waitingtime(proc, n, burst_time, wait_time);
    turnaroundtime(proc, n, burst_time, wait_time, tat);
    printf("Processes  Burst  Waiting  Turn around\n");
    for (i = 0; i < n; i++) {
        total_wt = total_wt + wait_time[i];
        total_tat = total_tat + tat[i];
        printf(" %d\t  %d\t\t %d \t%d\n", i+1, burst_time[i], wait_time[i], tat[i]);
    }
    printf("Average waiting time = %f\n", (float)total_wt / (float)n);
    printf("Average turn around time = %f\n", (float)total_tat / (float)n);
    return 0;
}

// main function
int main() {
    int proc[] = {1, 2, 3};
    int n = sizeof proc / sizeof proc[0];
    int burst_time[] = {5, 8, 12};
    avgtime(proc, n, burst_time);
    return 0;
}


আউটপুট (Output)
Processes  Burst  Waiting  Turn around
 1         5      0        5
 2         8      5        13
 3         12     13       25
Average waiting time = 6.000000
Average turn around time = 14.333333


ব্যাখ্যা: FCFS সিম্পল কিন্তু কনভয় ইফেক্ট (convoy effect) ক্যারি করে: বড় প্রসেস প্রথমে আসলে ছোট প্রসেসগুলো অনেক देर অপেক্ষা করে। অয়েরেজ ওয়েটিং টাইম অন্যান্য অ্যালগরিদমের চেয়ে বেশি হয়। অ্যারাইভাল টাইম বিবেচনা না করলে সহজ, কিন্তু রিয়েল সিস্টেমে অ্যারাইভাল টাইম কনসিডার করতে হয়।