라운드로빈 스케줄링 구현 - laundeulobin seukejulling guhyeon

#include 
int all_zero(int *arr, int size)
{
   int i = 0;
   for(i = 0; i < size; i++)
   {
      if(arr[i] != 0)
         return 0;
   }
   return 1;
}
void print_arr(int *arr, int size, int num, int real_count, int when) //0 : before, 1 : after
{
   int i;
   if(when == 0)
      printf("%d 번째, %d index 할당 전 상태 : ", real_count, num);
   else
      printf("%d 번째, %d index 할당 후 상태 : ", real_count, num);

   for(i = 0; i < size; i++)
      printf("%d ", arr[i]);
   printf("\n");

   if(when == 1)
      printf("\n");
}
void main()
{
   int arr[10] = {2, 1, 8, 4, 5, 3, 6, 7, 9, 4};
   int i = 0, size = sizeof(arr)/4, real_count = 1;

   while(1)
   {
      if( all_zero(arr,size) == 1 )
         break;

      while(arr[i%size] == 0)
      {
         i++;
      }
      print_arr(arr, size, i%size, real_count, 0);

      if( arr[i%size] != 0 )
         arr[i%size]--;

      print_arr(arr, size, i%size, real_count, 1);
      i++;
      real_count++;
   
   }
}

OS에서 핵심적인 부분 중 하나인 Scheduling입니다.

상당히 중요한 부분인 만큼 긴 내용이 되겠군요..ㅜ

먼저 대표적인 스케줄링 기법으로 라운드로빈 방식이 있습니다.

- 라운드 로빈 스케줄링(Round Robin Scheduling, RR)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum/Slice)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘입니다.

(==) 같은말로, 컴퓨터 운영에서, 컴퓨터 자원을 사용할 수 있는 기회를 프로그램 프로세스들에게 공정하게 부여하기 위한 한 방법으로서, 각 프로세스에 일정시간을 할당하고, 할당된 시간이 지나면 그 프로세스는 잠시 보류한 뒤 다른 프로세스에게 기회를 주고, 또 그 다음 프로세스에게 하는 식으로, 돌아가며 기회를 부여하는 운영방식이라 풀어 말할 수 있겠습니다.

보통 시간 단위는 10 ms ~ 100 ms 정도로, 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 되고, 문맥 전환의 오버헤드가 큰 반면에 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리합니다.

그렇다면 이 스케줄링이란 무엇일까요?

1) 스케줄링(Scheduling) 이란?

- 일반적인 스케줄링이란 처리할 일들의 진행순서를 정하는 일입니다. 

1) 프로세스 스케줄링이란 CPU를 사용하려고 하는 프로세스들 사이의 우선 순위를 관리하는 일을 말하고, 

2) 디스크 스케줄링은 디스크를 사용하려고 하는 프로세서들 사이의 우선 순위를 관리하는 일들을 말합니다. 

스케줄링은 처리율과 CPU 이용률을 증가시키고, 오버헤드/응답시간/반환시간/대기시간을 최소화시키기 위한 기법입니다. 즉, CPU가 쉬지않고 계속 열심히 일할 수 있도록 효율적인 계획을 잡아 주는 것이 스케줄링입니다.

2) 스케줄링 방식 -> 비선점스케줄링과 선점스케줄링

- 스케줄링의 적용 시점에 따라 비선점형과 선점형의 2가지로 구분할 수 있습니다.

1) 비선점형 스케줄링은 프로세스가 (실행->대기), (실행->종료) 로의 상태전이가 있을 때 적용되며,

2) 선점형 스케줄링은 (실행->대기), (실행->준비), (대기->준비), (수행->종료) 모든 상태변화에서 적용됩니다.

 (앞선 Process State Trasition Diagram, 선점형/비선점형 글을 참고로 보시면 됩니다.)

- 비선점 스케줄링 은 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법입니다. 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드도 적습니다. 일괄처리 시스템에 적합하고, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점도 있습니다.

- 선점 스케줄링 은 하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법입니다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있으며, 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있습니다.

(이 또한, 앞선 선점형 OS와 비선점형OS 글에서 다루었던 부분입니다.)

그렇다면, 이 스케줄링 알고리즘들에는 어떤것들이 있는지 아래에서 살펴보겠습니다.

3) 비선점형 스케줄링 알고리즘 : FIFO, SJF, HRN

-FIFO(First In First Out): 가장 간단한 방식으로 선입선출의 방식입니다. 먼저 들어오면 먼저 나가는 방식으로, 아무리 중요한 작업이 있다 하더라고 그 작업 보다 먼저 들어온 작업이 끝나기 전까지는 절대 먼저 실행될 수 없는 비효율적인 방식이라고 말할 수 있습니다. FIFO라고도 하고 FCFS(First Come First Served Scheuling)이라고도 합니다. 관련은 없지만 선입선출이라는 면에서 자료구조의 Queue를 한번 떠올려보게되네요.ㅎㅎ

-SJF(Shortest Remaining Time First Scheduling): 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식입니다. 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 연기 상태에 빠질 수 있다는 단점이 있습니다.

-HRN(Highest Response-ratio Next) : 실행시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 대기 시간과 서비스 시간을 이용하는 방식입니다. '우선순위 = (대기시간+서비스시간)/서비스시간'의 공식을 이용하여 우선순위를 계산하여 우선순위가 높은 것부터 실행하는 방식입니다. 

이렇게 프로세스가 자원을 기다리고 있는 시간에 비례하여 우선순위를 부여함으로서 무한 연기의 문제를 방지하는 것을 ‘에이징(Aging)기법’이라고 합니다.

4) 선점형 스케줄링 알고리즘 : SRT, RR, MQ

-SRT(Shortest Remaining Time): 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법입니다. SJF처럼 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식으로, 단지 차이점은 ‘선점형’으로 바뀌어 중요한 프로세스가 있으면 점유시간이 길어도 먼저 실행 시킬수 있는 권한이 생겼다는 것입니다.

- RR(Round Robin): 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU를 할당하는 방식입니다. 보통 시간 단위는 10ms ~ 100ms 정도이고 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 됩니다. 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하고, 할당되는 시간이 클 경우 비선점 FIFO기법과 같아지게 됩니다.

(위에서 설명한 부분입니다..^^)

- 다단계 큐(MQ, Multi-level Queue): 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 분비 상태 큐를 사용하는 기법입니다. 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없습니다. 하위 준비 상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비 상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당해야 합니다.

사진에 보이는 것처럼 Level 1, 2, 3으로 큐가 불리 되어 있습니다. 레벨 1의 큐가 모두 완료 되어야만 레벨 2의 큐로 넘어갈 수 있고 레벨2의 큐가 모두 완료되어야 그다음으로 넘어 갈수 있는 방식입니다.