C++ 를 이용한 FCFS 스케줄링 알고리즘 프로그램

소개

이 랩에서는 C++ 를 사용하여 First Come First Serve (FCFS) 스케줄링 알고리즘을 구현할 것입니다. FCFS 는 CPU 를 요청 순서대로 프로세스에 할당하는 가장 간단한 CPU 스케줄링 알고리즘입니다. 준비 큐에 먼저 도착한 프로세스가 먼저 처리됩니다.

이 알고리즘은 이해하고 구현하기 쉽지만, 평균 대기 시간 측면에서 최적의 성능을 제공하지 못할 수 있습니다. 이 랩을 마치면 FCFS 알고리즘의 작동 방식을 이해하고 프로세스의 대기 시간 및 반환 시간과 같은 중요한 지표를 계산할 수 있게 됩니다.

FCFS 이해 및 프로그램 구조 생성

First Come First Serve (FCFS) 는 준비 큐에 프로세스가 도착하는 순서대로 실행되는 비선점형 (non-preemptive) 스케줄링 알고리즘입니다. 이 단계에서는 프로그램 파일을 생성하고 기본 구조를 설정합니다.

새로운 C++ 파일을 생성해 보겠습니다.

1. WebIDE 인터페이스를 열고 파일 탐색기 패널로 이동합니다.
2. 탐색기 패널에서 마우스 오른쪽 버튼을 클릭하고 "New File"을 선택합니다.
3. 파일 이름을 fcfs.cpp로 지정하고 Enter 키를 누릅니다.

이제 프로그램에 필요한 헤더 파일과 네임스페이스 선언을 추가해 보겠습니다.

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    return 0;
}

이 코드는 다음과 함께 프로그램의 기본 구조를 설정합니다.

• #include <iostream> - 입/출력 연산을 위해
• #include <iomanip> - 출력 테이블 형식 지정을 위해
• using namespace std; - 표준 네임스페이스를 사용하기 위해
• 제목 표시가 있는 main() 함수

모든 것이 올바르게 설정되었는지 확인하기 위해 프로그램을 컴파일하고 실행해 보겠습니다.

g++ fcfs.cpp -o fcfs
./fcfs

다음 출력을 볼 수 있습니다.

FCFS Scheduling Algorithm Implementation
----------------------------------------

이것은 기본 프로그램 구조가 올바르게 작동하고 있음을 확인합니다. 다음 단계에서는 프로세스 세부 정보를 입력하는 기능을 구현합니다.

프로세스 입력 기능 구현

이 단계에서는 스케줄링할 프로세스에 대한 정보를 수집하는 기능을 구현합니다. FCFS 스케줄링의 경우 다음을 알아야 합니다.

1. 프로세스 수
2. 각 프로세스의 버스트 시간 (각 프로세스에 필요한 실행 시간)

fcfs.cpp 파일을 수정하여 이 기능을 포함해 보겠습니다.

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                  // Number of processes
    int burst_time[20];     // Array to store burst time of each process

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Display the entered data
    cout << "\nProcess\tBurst Time" << endl;
    cout << "--------------------" << endl;
    for (int i = 0; i < n; i++) {
        cout << "P" << i + 1 << "\t" << burst_time[i] << endl;
    }

    return 0;
}

추가한 내용을 살펴보겠습니다.

1. 프로세스 수 (n) 와 각 프로세스의 버스트 시간 (burst_time[20]) 을 저장하는 변수.
2. 프로세스 수와 각 프로세스의 버스트 시간을 수집하기 위한 입력 프롬프트.
3. 프로세스 수가 적절한 범위 (1-20) 내에 있고 버스트 시간이 양수인지 확인하기 위한 입력 유효성 검사.
4. 확인을 위해 입력된 데이터를 표시하는 테이블 표시.

업데이트된 프로그램을 컴파일하고 실행해 보겠습니다.

g++ fcfs.cpp -o fcfs
./fcfs

프로그램을 실행하면 프로세스 수와 버스트 시간을 입력하라는 메시지가 표시됩니다. 다음 데이터를 입력해 보십시오.

3
5
9
4

이는 각각 5, 9, 4 시간 단위의 버스트 시간을 가진 3 개의 프로세스를 나타냅니다. 다음과 유사한 출력을 볼 수 있습니다.

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time
--------------------
P1      5
P2      9
P3      4

이는 입력 기능이 올바르게 작동하고 있음을 확인합니다. 다음 단계에서는 각 프로세스의 대기 시간과 반환 시간을 계산합니다.

대기 시간 및 반환 시간 계산

이 단계에서는 각 프로세스에 대해 두 가지 중요한 지표를 계산합니다.

1. 대기 시간 (WT): 프로세스가 CPU 시간을 얻기 전에 준비 큐에서 대기하는 시간입니다.
2. 반환 시간 (TAT): 프로세스 제출부터 완료까지 걸린 총 시간입니다.

FCFS 에서 이것들이 어떻게 계산되는지 이해해 보겠습니다.

• 첫 번째 프로세스 (P1) 의 경우 대기 시간은 항상 0 입니다 (즉시 시작).
• 후속 프로세스의 경우 대기 시간은 이전 모든 프로세스의 버스트 시간의 합입니다.
• 각 프로세스의 반환 시간은 버스트 시간과 대기 시간의 합입니다.

이제 fcfs.cpp 파일을 수정하여 이러한 계산을 추가해 보겠습니다.

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    return 0;
}

추가한 내용을 이해해 보겠습니다.

1. 두 개의 새로운 배열: 각 프로세스의 대기 시간과 반환 시간을 저장하기 위한 waiting_time[20] 및 turnaround_time[20].
2. 총 대기 시간과 총 반환 시간을 추적하기 위한 변수.
3. 대기 시간 계산:
   • 첫 번째 프로세스의 대기 시간은 0 입니다.
   • 각 후속 프로세스의 경우 대기 시간은 이전 모든 프로세스의 버스트 시간의 합입니다.
4. 반환 시간 계산:
   • 각 프로세스의 경우 반환 시간 = 버스트 시간 + 대기 시간.
5. 결과를 표시하기 위한 형식화된 테이블.

업데이트된 프로그램을 컴파일하고 실행해 보겠습니다.

g++ fcfs.cpp -o fcfs
./fcfs

이전과 동일한 데이터를 입력해 보십시오.

3
5
9
4

다음과 유사한 출력을 볼 수 있습니다.

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

결과를 분석해 보겠습니다.

• P1: 대기 시간 = 0, 반환 시간 = 5 (버스트 시간)
• P2: 대기 시간 = 5 (P1 의 버스트 시간), 반환 시간 = 14 (5 + 9)
• P3: 대기 시간 = 14 (P1 + P2 의 버스트 시간), 반환 시간 = 18 (14 + 4)

이는 대기 시간 및 반환 시간 계산이 올바르게 작동하고 있음을 확인합니다. 다음 단계에서는 평균 시간을 계산하고 최종 결과를 표시합니다.

평균 시간 계산 및 최종 결과 표시

이 마지막 단계에서는 모든 프로세스에 대한 평균 대기 시간과 평균 반환 시간을 계산합니다. 이러한 평균은 스케줄링 알고리즘의 효율성을 평가하는 데 중요한 지표입니다.

fcfs.cpp 파일을 수정하여 이러한 계산을 추가하고 프로그램을 완성해 보겠습니다.

#include <iostream>
#include <iomanip> // For formatted output

using namespace std;

int main() {
    cout << "FCFS Scheduling Algorithm Implementation" << endl;
    cout << "----------------------------------------" << endl;

    // Variables declaration
    int n;                      // Number of processes
    int burst_time[20];         // Array to store burst time of each process
    int waiting_time[20];       // Array to store waiting time of each process
    int turnaround_time[20];    // Array to store turnaround time of each process
    int total_waiting_time = 0;
    int total_turnaround_time = 0;
    float avg_waiting_time = 0.0;
    float avg_turnaround_time = 0.0;

    // Get the number of processes from the user
    cout << "\nEnter the number of processes (maximum 20): ";
    cin >> n;

    // Input validation
    if (n <= 0 || n > 20) {
        cout << "Invalid number of processes. Please enter a value between 1 and 20." << endl;
        return 1;
    }

    // Get burst time for each process
    cout << "\nEnter the Burst Time for each process:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Process P" << i + 1 << ": ";
        cin >> burst_time[i];

        // Input validation for burst time
        if (burst_time[i] <= 0) {
            cout << "Burst time must be a positive integer. Please restart the program." << endl;
            return 1;
        }
    }

    // Calculate waiting time for each process
    waiting_time[0] = 0;    // First process has 0 waiting time

    for (int i = 1; i < n; i++) {
        waiting_time[i] = 0;
        // Add burst times of all previous processes
        for (int j = 0; j < i; j++) {
            waiting_time[i] += burst_time[j];
        }
    }

    // Calculate turnaround time for each process and total times
    cout << "\nProcess\tBurst Time\tWaiting Time\tTurnaround Time" << endl;
    cout << "----------------------------------------------------" << endl;

    for (int i = 0; i < n; i++) {
        turnaround_time[i] = burst_time[i] + waiting_time[i];
        total_waiting_time += waiting_time[i];
        total_turnaround_time += turnaround_time[i];

        cout << "P" << i + 1 << "\t" << burst_time[i] << "\t\t"
             << waiting_time[i] << "\t\t" << turnaround_time[i] << endl;
    }

    // Calculate average waiting time and average turnaround time
    avg_waiting_time = (float)total_waiting_time / n;
    avg_turnaround_time = (float)total_turnaround_time / n;

    // Display the results with two decimal places
    cout << fixed << setprecision(2);
    cout << "\nAverage Waiting Time: " << avg_waiting_time << " time units" << endl;
    cout << "Average Turnaround Time: " << avg_turnaround_time << " time units" << endl;

    // Visual representation of the FCFS schedule (Gantt chart in text)
    cout << "\nGantt Chart:" << endl;
    cout << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }
    cout << endl << "|";

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "P" << i + 1;
        for (int j = 0; j < burst_time[i] - 1; j++) {
            cout << " ";
        }
        cout << "|";
    }

    cout << endl << " ";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < burst_time[i]; j++) {
            cout << "--";
        }
    }

    cout << endl;
    cout << "0";
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        current_time += burst_time[i];
        for (int j = 0; j < burst_time[i] * 2 - 1; j++) {
            cout << " ";
        }
        if (current_time < 10) cout << " ";
        cout << current_time;
    }
    cout << endl;

    return 0;
}

추가한 내용을 이해해 보겠습니다.

1. 평균 시간을 저장하기 위한 두 개의 새로운 변수: avg_waiting_time 및 avg_turnaround_time.
2. 평균 시간 계산:
   • 평균 대기 시간 = 총 대기 시간 / 프로세스 수
   • 평균 반환 시간 = 총 반환 시간 / 프로세스 수
3. 소수점 두 자리까지 평균 시간을 표시하기 위한 형식화된 출력.
4. FCFS 스케줄을 시각화하기 위한 간단한 텍스트 기반 Gantt 차트:
   • 각 프로세스는 ID (P1, P2 등) 로 표시됩니다.
   • 각 프로세스 블록의 너비는 버스트 시간에 비례합니다.
   • 시간 마커가 하단에 표시됩니다.

최종 프로그램을 컴파일하고 실행해 보겠습니다.

g++ fcfs.cpp -o fcfs
./fcfs

이전과 동일한 데이터를 입력해 보십시오.

3
5
9
4

다음과 유사한 출력을 볼 수 있습니다.

FCFS Scheduling Algorithm Implementation
----------------------------------------

Enter the number of processes (maximum 20): 3

Enter the Burst Time for each process:
Process P1: 5
Process P2: 9
Process P3: 4

Process Burst Time      Waiting Time    Turnaround Time
----------------------------------------------------
P1      5               0               5
P2      9               5               14
P3      4               14              18

Average Waiting Time: 6.33 time units
Average Turnaround Time: 12.33 time units

Gantt Chart:
 --------------------
|   P1    |    P2    |  P3  |
 --------------------
0         5         14     18

결과를 살펴보겠습니다.

• 평균 대기 시간: (0 + 5 + 14) / 3 = 6.33 시간 단위
• 평균 반환 시간: (5 + 14 + 18) / 3 = 12.33 시간 단위

Gantt 차트는 프로세스가 시간에 따라 어떻게 스케줄링되는지 시각적으로 나타냅니다.

• P1 은 시간 0 에서 5 까지 실행됩니다.
• P2 는 시간 5 에서 14 까지 실행됩니다.
• P3 는 시간 14 에서 18 까지 실행됩니다.

이것으로 FCFS 스케줄링 알고리즘의 구현이 완료되었습니다. 다양한 수의 프로세스와 버스트 시간을 실험하여 평균 대기 시간과 반환 시간에 미치는 영향을 확인할 수 있습니다.

요약

이 랩에서는 C++ 를 사용하여 First Come First Serve (FCFS) CPU 스케줄링 알고리즘을 성공적으로 구현했습니다. 다음은 여러분이 배운 주요 개념과 기술입니다.

1. FCFS 알고리즘 기본: 프로세스가 도착하는 순서대로 스케줄링되는 방식을 이해합니다.

2. 성능 지표 계산:

   • 대기 시간 (Waiting Time): 프로세스가 실행을 시작하기 전에 대기하는 시간
   • 반환 시간 (Turnaround Time): 제출부터 완료까지의 총 시간
   • 평균 대기 시간 및 평균 반환 시간: 스케줄링 알고리즘의 주요 성능 지표

3. C++ 프로그래밍 개념:

   • 프로세스 정보를 저장하기 위한 배열
   • 반복 계산을 위한 루프
   • 유효성 검사를 포함한 입/출력 연산
   • 더 나은 데이터 표현을 위한 형식화된 출력

4. 시각화 기술: 스케줄링 타임라인을 시각화하기 위한 텍스트 기반 Gantt 차트 생성

FCFS 알고리즘은 이해하고 구현하기 쉽지만 항상 최적의 성능을 제공하지는 않을 수 있습니다. 짧은 프로세스가 긴 프로세스 뒤에서 대기하게 되어 평균 대기 시간을 증가시키는 "호송 효과 (convoy effect)"를 초래할 수 있습니다.

이 구현은 Shortest Job First (SJF), 우선순위 스케줄링 (Priority Scheduling), Round Robin (RR) 과 같이 프로세스 스케줄링의 다양한 측면을 최적화하는 보다 복잡한 스케줄링 알고리즘을 이해하기 위한 기초 역할을 합니다.