Chương trình C cho thuật toán lập lịch FCFS (First Come First Served)

Cho n tiến trình P1, P2, P3... với burst time. Tìm average waiting time và average turnaround time bằng FCFS.

Waiting Time & Turnaround Time

• Turnaround Time: thời gian từ nộp đến hoàn thành. = Completion - Submission.
• Waiting Time: Turnaround Time - Burst Time.

FCFS Scheduling

First Come First Served (FCFS) = First In First Out (FIFO). CPU cấp cho tiến trình theo thứ tự trong ready queue. Non-preemptive: một khi cấp CPU, tiến trình giữ CPU đến khi kết thúc hoặc bị ngắt I/O.

Ví dụ

4 tiến trình đến theo thứ tự P2, P3, P1 (arrival time = 0):

Waiting: P2=0, P3=3, P1=6. Average = (0+3+6)/3 = 3 ms. Với arrival time = 0, turnaround = completion time.

Ví dụ khác

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

Thuật toán

waitingtime(proc, n, bt, wt):
  wt[0] = 0
  for i = 1 đến n-1: wt[i] = bt[i-1] + wt[i-1]

turnaroundtime(proc, n, bt, wt, tat):
  for i = 0 đến n-1: tat[i] = bt[i] + wt[i]

avgtime(proc, n, bt):
  wt[n], tat[n], total_wt=0, total_tat=0
  waitingtime(...); turnaroundtime(...)
  for i = 0 đến n-1:
    total_wt += wt[i]; total_tat += tat[i]
    in process, bt, wt, tat
  in Avg waiting = total_wt/n
  in Avg turnaround = total_tat/n

Ví dụ mã nguồn

#include <stdio.h>

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;
}

int turnaroundtime(int proc[], int n, int burst_time[], int wait_time[], int tat[]) {
    for (int i = 0; i < n; i++)
        tat[i] = burst_time[i] + wait_time[i];
    return 0;
}

int avgtime(int proc[], int n, int burst_time[]) {
    int wait_time[n], tat[n], total_wt = 0, total_tat = 0;
    waitingtime(proc, n, burst_time, wait_time);
    turnaroundtime(proc, n, burst_time, wait_time, tat);

    printf("Processes  Burst  Waiting  Turnaround\n");
    for (int i = 0; i < n; i++) {
        total_wt += wait_time[i];
        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 / n);
    printf("Average turn around time = %f\n", (float)total_tat / n);
    return 0;
}

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;
}

Kết quả đầu ra

Processes  Burst  Waiting  Turnaround
1          5      0        5
2          8      5        13
3          12     13       25
Average Waiting time = 6.000000
Average turn around time = 14.333333