SECTION 140. 주요 스케줄링 알고리즘

주요 스케줄링 알고리즘

1. FCFS (선입선출, FIFO)
   1. 개념: FCFS는 프로세스를 도착한 순서대로 처리하는 방식의 스케줄링 알고리즘입니다. 먼저 요청된 프로세스가 먼저 CPU를 할당받아 실행됩니다.
   2. 특징:
      • 특징 설명: 간단하고 직관적인 방식으로, 요청된 순서대로 자원을 할당하므로 구현이 쉽습니다.
      • 장점: 공정하게 모든 프로세스를 처리하며, 오버헤드가 적습니다.
      • 단점: 긴 작업이 앞에 있으면 뒤에 있는 짧은 작업들이 오래 기다리게 되는 문제(Convoy Effect)가 발생할 수 있습니다.
   3. 예제: 프로세스 A, B, C가 각각 1초, 3초, 2초의 실행 시간을 필요로 하고, 도착 순서가 A, B, C일 때, A가 먼저 실행되고 그다음 B, 마지막으로 C가 실행됩니다.
   4. 실제 사용 예시: 인쇄 작업 큐에서 가장 먼저 들어온 인쇄 작업을 먼저 처리하는 방식으로 사용됩니다.
2. SJF (단기 작업 우선)
   1. 개념: SJF는 실행 시간이 가장 짧은 프로세스를 우선적으로 실행하는 스케줄링 알고리즘입니다.
   2. 특징:
      • 특징 설명: 평균 대기 시간을 최소화하기 위해 짧은 작업부터 실행하는 방식입니다.
      • 장점: 평균 대기 시간이 가장 짧아 효율적입니다.
      • 단점: 실행 시간을 사전에 정확히 알 수 없는 경우가 많고, 긴 작업이 계속 대기할 가능성(Starvation)이 있습니다.
   3. 예제: 프로세스 A, B, C가 각각 2초, 1초, 3초의 실행 시간을 필요로 할 때, B, A, C 순서로 실행됩니다.
   4. 실제 사용 예시: 배치 처리 시스템에서 작업의 소요 시간이 사전에 알려진 경우에 사용됩니다.
3. HRN (Highest Response Ratio Next)
   1. 개념: HRN은 응답 비율(Response Ratio)이 가장 높은 프로세스를 우선 실행하는 스케줄링 알고리즘입니다.
   2. 특징:
      • 특징 설명: 대기 시간이 길거나 실행 시간이 짧은 프로세스를 우선 처리하여 공정성을 높입니다.
      • 장점: 긴 작업과 짧은 작업의 균형을 맞추며, Starvation을 방지할 수 있습니다.
      • 단점: 응답 비율을 계산하는 추가적인 오버헤드가 발생할 수 있습니다.
   3. 우선순위 계산식: 응답 비율 = (대기 시간 + 서비스 시간) / 서비스 시간
   4. 예제: 프로세스 A, B, C가 각각 대기 시간 3초, 1초, 2초이고, 서비스 시간이 2초, 4초, 1초일 때, 우선순위는 C > A > B입니다.
   5. 실제 사용 예시: 다양한 실행 시간이 존재하는 대기 작업이 많은 시스템에서 사용됩니다.
4. RR (Round Robin, 라운드 로빈)
   1. 개념: RR은 각 프로세스에게 일정한 시간(Time Quantum)을 할당하고, 해당 시간이 지나면 다음 프로세스로 교체하는 방식의 스케줄링 알고리즘입니다.
   2. 특징:
      • 특징 설명: 공정하게 모든 프로세스에게 일정한 시간을 할당하여 실행합니다. 시간 할당량이 클수록 FCFS와 유사해지고, 작을수록 문맥 교환이 많아집니다.
      • 장점: 대화형 시스템에서 공정하게 프로세스를 관리하며, 모든 프로세스가 CPU를 할당받을 수 있습니다.
      • 단점: 시간 할당량이 너무 작으면 문맥 교환이 빈번해져 오버헤드가 커집니다.
   3. 예제: 프로세스 A, B, C가 있으며, 각 프로세스에게 1초씩 할당된 경우, A, B, C 순서로 돌아가며 실행됩니다.
   4. 실제 사용 예시: 시분할 시스템에서 사용됩니다.
5. SRT (Shortest Remaining Time)
   1. 개념: SRT는 남은 실행 시간이 가장 짧은 프로세스를 우선 실행하는 선점형 스케줄링 알고리즘입니다.
   2. 특징:
      • 특징 설명: 현재 실행 중인 프로세스보다 짧은 남은 실행 시간을 가진 프로세스가 도착하면 CPU를 선점합니다.
      • 장점: 평균 대기 시간을 최소화할 수 있습니다.
      • 단점: 긴 작업이 계속 대기하는 Starvation이 발생할 수 있으며, 문맥 교환이 빈번해 오버헤드가 증가합니다.
   3. 예시: 프로세스 A, B, C가 각각 남은 실행 시간이 3초, 2초, 1초일 때, C가 먼저 실행되고 그다음 B, A 순서로 실행됩니다.
   4. 실제 사용 예시: 실시간 시스템에서 사용됩니다.

 

기출 따라잡기

문제 1. HRN 비선점형 스케줄링의 우선순위를 구하는 계산식을 쓰시오.

• 답: (대기 시간 + 서비스 시간) / 서비스 시간
• 해설: HRN 방식에서는 응답 비율을 계산하여 대기 시간이 길거나 서비스 시간이 짧은 프로세스를 우선적으로 처리합니다. 계산식은 응답 비율 = (대기 시간 + 서비스 시간) / 서비스 시간입니다.

문제 2. SJF(Shortest Job First) 스케줄링에서 다음과 같은 프로세스가 차례로 큐에 도착하였을 때, 평균 반환 시간과 평균 대기 시간을 계산하시오.프로세스 번호실행 시간

P1	7
P2	8
P3	3
P4	4

• 답:
  • 평균 반환 시간: 14.5초
  • 평균 대기 시간: 10.25초
• 해설: SJF 방식에서는 실행 시간이 가장 짧은 프로세스부터 처리하므로, P3 -> P4 -> P1 -> P2 순서로 실행됩니다. 각 프로세스의 반환 시간과 대기 시간을 계산하여 평균을 구하면 반환 시간은 14.5초, 대기 시간은 10.25초가 됩니다.

문제 3. 다음이 설명하고 있는 비선점 스케줄링 알고리즘의 명칭을 쓰시오.

• 실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스 시간을 이용하는 기법이다.
• 대기 시간이 길어질수록 우선순위가 높아지며, 시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선순위를 부여하여 밀린 작업 상황을 방지한다.
• 답: HRN (Highest Response Ratio Next)
• 해설: HRN 스케줄링 알고리즘은 SJF의 단점을 보완하고, 대기 시간이 길어질수록 높은 우선순위를 부여하여 공정하게 프로세스를 관리하는 방식입니다.

문제 4. HRN 방식으로 스케줄링 할 경우, 입력된 작업이 다음과 같을 때 처리되는 작업 순서를 나열하시오.

작업	대기 시간	서비스(실행) 시간
A	5	20
B	40	20
C	15	45
D	20	2

• 답: B, D, A, C
• 해설: HRN 방식에서는 응답 비율을 계산하여 우선순위를 정합니다. 각 작업의 응답 비율을 계산한 결과, B, D, A, C 순서로 처리됩니다.

문제 5. 스케줄링에 대한 다음 설명에서 괄호 (1)~(3)에 들어갈 알맞은 용어를 쓰시오.

• (1) 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법이다. 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘이지만, 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 무한 대기 상태가 발생할 수 있다.
• (2) 시분할 시스템을 위해 고안된 방식으로, 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 시간 할당량 동안 준비상태 큐의 후미로 배치된다. 할당된 시간이 차는 경우 문맥 교환 및 준비상태로 전환된다. 시간 할당량이 작을 경우 문맥 교환이 많아져 오버헤드가 커질 수 있다.
• (3) 각 프로세스의 대기 시간을 고려하여 특정 프로세스에 대한 서비스 요청이 너무 오래 지연되지 않도록 우선순위를 조정하는 기법으로, 시분할 시스템에서 실행 시간을 추적하여 높아진 우선순위가 오버헤드를 증가시킨다.
• 답:
  1. SJF (Shortest Job First)
  2. RR (Round Robin)
  3. HRN (Highest Response Ratio Next)
• 해설: (1)은 짧은 작업을 우선 처리하는 SJF 알고리즘을 설명하고 있으며, (2)는 시분할 시스템을 위해 설계된 라운드 로빈 기법을 나타냅니다. (3)은 대기 시간을 고려하여 우선순위를 조정하는 HRN 기법을 설명하고 있습니다.