CPU 스케줄링(2) : 스케줄링 알고리즘

이전 포스트에 썼다시피, 크게 선점과 비선점으로 나뉘고, 다중 처리기 스케줄링과 실시간 스케줄링 정도 추가.

 

비선점 스케줄링: 이미 할당된 CPU는 해당 프로세스가 완료될 때까지 다른 프로세스가 강제로 못 뺏음. 일괄처리에서 주로 사용.

• FCFS(First Come First Service) : 준비상태 큐에 도착한 순서에 따라 CPU를 할당하는 기법 (I/O에서의 FIFO랑 같음)
  현재 CPU를 점유하고 있는 프로세스가 CPU버스트를 모두 수행하고 자발적으로 CPU를 반납할 때까지 CPU를 선점하지 않아, CPU 버스트가 긴 프로세스 하나가 CPU 버스트가 짧은 여러 개의 프로세스보다 먼저 레디 큐에 들어가면 평균 대기 시간 길어지는 콘보이 현상(Convoy Effect) 발생. 대신 짧은 애들이 여러 개 들어오면 평균 대기 시간 짧아짐
  장점) 공평성(우선순위없음) 지켜짐. 준비 상태의 프로세스 개수, 크기(시간)를 알면 실행 시간 예측 가능
  문제) 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 됨=> 평균 응답 시간 길어짐

• SJF(Shortest Job First) : 실행시간(CPU 버스트)이 가장 짧은 프로세스에 먼저 CPU를 할당하는 기법.
  선점형으로도 구현 가능(SRTF: CPU버스트 시간이 더 짧은 프로세스한테 할당)
  장점) 평균 대기 시간을 가장 짧게 하는(평균 응답 시간 최소화) 최적 알고리즘. 콘보이 효과 완화
  문제) CPU 버스트가 긴 프로세스는 레디 큐에서 무한정 기다려야 하는 기아 현상 Starvation 발생. 공평성 X. 입출력 버스트가 빈번하게 요구되는 프로세스일 때 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움.

• HRN(Highest Response ratio Next) : 실행 시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로(SJF+Aging) 우선순위 계산 결과 값이 높은 것부터 우선순위가 부여된다. 대기 시간이 길수록 계산 결과가 높다.
  (대기시간 + 서비스 시간 / 서비스 시간)
  장점) 실행시간이 적은 프로세스의 우선순위가 높지만 대기시간이 너무 길어지면 실행시간이 길더라도 CPU 배당 가능 => 평균 응답 시간 단축 가능
  단점) 공평성 세모

• 기한부(DeadLine) : 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법

• 우선순위(Priority) : 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
  priority number를 통해 표시하며 우선순위 값이 작을수록 높은 우선순위를 가지는 것으로 가정한다.
  선점으로도 구현 가능. starvation 현상 막기 위해 aging 기법 사용함.
  우선순위를 동적으로 부여할 경우
  장점) 시스템의 응답속도 증가
  단점) 구현 복잡, 오버헤드 많음. 공평성 문제 ㅇ

에이징Aging 기법: 특정 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우, 한 번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당받도록 하는 기법

SJF나 우선순위 기법에서 발생할 수 있는 무한 연기 상태, 기아 상태를 예방할 수 있다. 

 

 

선점 스케줄링: 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때, 우선순위가 높은 프로세스가 CPU를 강제로 빼앗아 사용할 수 있음 => 처리 시간 예측 어려움
많은 오버해드 발생. 시분할에서 주로 사용. 시간 배당을 위한 인터럽트용 타이머, clock을 필요로 함

• SRT(Shortest Remaining Time) : 현재 실행 중인 프로세스의 남은 시간과 대기 큐에 프로세스의 실행시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법 (비선점 기법인 SJF 알고리즘의 선점 형태로 변경한 기법)
  장점) 평균 대기 시간이 가장 짧은 알고리즘
  문제) 잦은 문맥 교환으로 인한 오버헤드 증가, 기아 현상 더 심각, CPU의 예상 시간을 예측하기 너무 어려워 실제로 잘 안 씀(exponential averaging으로 예측할 수는 있긴 함)
• RR(Round Robin) : 시분할 시스템을 위해 고안된 방법으로, FCFS 알고리즘을 선점 형태로 변형한 기법.
  CPU 할당 시간 (타임 슬라이스, Quantum)을 부여해서 이 시간 동안만 CPU를 이용하게 한다. 
  대기 큐를 사용하여 먼저 대기한 프로세스가 먼저 CPU를 사용하는데, 한 퀀텀 동안 CPU를 사용한 후에도 모두 처리하지 못하면 해당 프로세스는 CPU를 뺏기고 대기 큐의 가장 뒤로 배치되며, CPU는 다음 프로세스에게 할당된다.
  
  장점) 우선순위가 없기 때문에 매우 공평. 모든 프로세스가 최초 응답 시간을 빠르게 보장 받음=> 콘보이 효과 감소
  (할당 시간이 Q고 대기 중인 프로세스가 N 개라면, 어떤 프로세스도 (N-1)Q 이상의 시간을 기다리지 않아도 된다.)
  단점) 퀀텀이 너무 크면 FCFS와 같아지고, 너무 작으면 문맥 교환 및 오버헤드 자주 발생
  => 타임 슬라이스 크기 중요. 보통 10-100ms로 설정함
  
  
• 다단계 큐(Multi Level Queue) : 큐를 여러 개롤 분할해서 관리하는 스케줄링 기법으로, 프로세스를 특정 그룹으로 분류할 수 있는 경우 그룹에 따라 각기 다른 준비상태 큐를 사용한다.(한 번 우선순위가 매겨져 준비 큐에 들어가면 이 우선순위는 바뀌지 않는다)
  레디 큐를 대화형 작업용 전위 큐(foreground queue)와 계산 작업용 후위 큐(back ground queue)로 분할한다. 전위 큐에서는 응답 시간을 짧게 하기 위해 Round Robin 방법을 사용하고, 후위 큐에서는 응답 시간이 별로 중요하지 않아 FCFS 기법을 사용한다. 
  어느 큐에 먼저 CPU를 할당할 것인지에 따라 고정 우선순위 방식 / 타임 슬라이스 중 하나를 선택해 결정한다.
  • 고정 우선순위 방식 Fixed Priority Scheduling
    큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐가 비어있을 때만 서비스
    전위 큐에 있는 프로세스에게 먼저 CPU 할당, 전위가 비어있을 때만 후위 큐에 CPU 할당
  • 타임 슬라이스 time slice
    기아 현상을 해소하는 방법으로, 각 큐에 CPU 시간을 적절한 비율로 할당한다. (보통 전위에 80, 후위에 20의 비율로 CPU 시간 할당)
• 다단계 피드백 큐(Multi Level Feedback Queue) : 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법
  위의 다단계 큐에 에이징 기법을 더한 방법으로, 우선순위가 낮은 큐에서 오랫동안 기다렸으면, 우선순위가 높은 큐로 승격시키는 방식이다.
• 선점 우선순위 : 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
  문제) 기아 문제, 공평성 문제

 

 

다중 처리기 스케줄링 (Multi Processor Scheduling)

• 다중 처리기 시스템(multi processor system)에서는 cpu가 여러 개 이기 때문에 cpu가 큐에서 프로세스를 꺼내가는 메커니즘이 필요
• cpu를 줄 세우는 방식을 사용하면, 일부 cpu에 작업이 편중되는 현상이 발생할 수 있어서 cpu 별로 부하분산시키는 메커니즘 필요
• 대칭형 다중 처리(symmentric multi processing)와 비대칭형 다중 처리(asymmetric multiprogramming)로 나눌 수 있다.
• 대칭형은 cpu가 각자 알아서 스케줄링 결정하는 방식
• 비대칭형은 하나의 cpu가 다른 모든 cpu의 스케줄링 및 데이터의 접근을 책임지고 나머지는 거기에 따라 움직이는 방식

실시간 스케줄링

• time sharing system에서는 작업의 처리가 빠를수록 좋지만 특정 시간 이내에 처리하지 못했다고 심각한 문제가 발생하지 않음
• hard real time system은 시간이 정확히 지켜져야 하므로 정해진 시간 안에 반드시 작업이 완료되도록 스케줄링되어야 한다. (원자로 제어, 미사일 발사 등등)
• soft real time system은 데드라인이 존재하기는 하지만 데드라인을 지키지 못했다고 해서 위험한 상황이 발생하지는 않는다 (멀티미디어 스트리밍)
• hard real time system에서는 먼저 온 요청을 먼저 처리하기보다는 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadling Fisrt) 스케줄링을 널리 사용