CPU 스케줄링 개요

• CPU 스케줄링(CPU scheduling)
  • 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
  • 컴퓨터 성능과도 직결되는 중요한 문제임

프로세스 우선순위

• 입출력 집중 프로세스(I/O bound process)
  • 입출력 작업이 많은 프로세스
  • 비디오 재생이나 디스크 백업 작업 등을 담당함
  • 입출력장치를 기다리는 작업을 입출력 버스트(I/O burst)라고 함
• CPU 집중 프로세스(CPU bound process)
  • CPU 작업이 많은 프로세스
  • 복잡한 수학 연산, 컴파일, 그래픽 처리 작업 등을 담당함
  • CPU를 이용하는 작업을 CPU 버스트(CPU burst)라고 함

우선순위 효율

일반적으로 프로세스는 실행 상태와 대기 상태를 반복하며 실행되는데, 입출력 집중 프로세스는 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 된다. 반대로 CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무르게 된다.

때문에 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고, 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적이다. 입출력장치가 입출력 작업을 완료하기 전까지는 입출력 집중 프로세스는 어차피 대기 상태가 될 예정이기 때문에 입출력 집중 프로세스를 얼른 먼저 처리해 버리면 다른 프로세스가 CPU를 사용할 수 있기 때문이다.

위와 같은 이유로 입출력 집중 프로세스와 CPU 집중 프로세스 중 입출력 집중 프로세스에 높은 우선순위를 부여하는 것이 효율적이다.

이렇게 모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다, 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적이다.

스케줄링 큐

• 스케줄링 큐(scheduling queue)
  • CPU, 메모리, 입출력장치 등의 자원을 사용하고 싶은 프로세스들을 줄 세운 것
  • 원래 큐는 선입선출(FIFO)지만 스케줄링에서의 큐는 반드시 선입선출일 필요가 없음
• 준비 큐(ready queue)
  • CPU를 이용하고 싶은 프로세스들을 관리
  • 운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그 중 우선순위가 높은 프로세스들을 먼저 실행함
• 대기 큐(waiting queue)
  • 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들을 관리
  • 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 관리
  • 입출력이 완료되어 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고, 이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거하고 준비 큐로 이동시킴

선점형과 비선점형 스케줄링

• 선점형 스케줄링(preemptive scheduling)
  • 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
  • 하나의 프로세스가 자원 사용을 독점할 수 없음
  • 장점 : 특정 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 분배할 수 있음
  • 단점 : 문맥 교환 과정에서 오버헤드가 발생할 수 있음
• 비선점형 스케줄링(non0preemptive scheduling)
  • 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식
  • 하나의 프로세스가 자원 사용을 독점할 수 있음
  • 다른 프로스세들은 CPU를 사용 중인 프로세스의 사용이 끝날 때까지 기다려야 함
  • 장점 : 문맥 교환에서 발생하는 오버헤드는 선점형 스케줄링보다 적음
  • 단점 : 모든 프로세스가 골고루 자원을 사용할 수 없음

현재 대부분의 운영체제는 선점형 스케줄링 방식을 사용하고 있다.

비선점형 스케줄링 방식은 작업이 중단되면 안 되거나 간단하고 예측 가능한 환경 등에서 쓰인다. 실시간 시스템, 배치 처리 시스템, 임베디드 시스템, 멀티코어 환경에서의 작업 분배 등이 있다.

CPU 스케줄링 알고리즘

스케줄링 알고리즘의 종류

선입 선처리 스케줄링

• FCFS 스케줄링(First Come First Served Scheduling)
• 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
• 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있음
• 호위 효과(convoy effect) : CPU를 오래 사용하는 프로세스가 먼저 도착하면, 다른 프로세스는 수행 시간이 굉장히 짧더라도 먼저 도착한 프로세스가 CPU를 사용하는 동안 기다려야 하는 현상

최단 작업 우선 스케줄링

• SJF 스케줄링(Shortest Job First Scheduling)
• 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식
• 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수도 있음 (선점형 최단 작업 우선 스케줄링)
• 호위 효과를 방지할 수 있음

라운드 로빈 스케줄링

• 라운드 로빈 스케줄링(round robin scheduling)
• 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식
• 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
• 타임 슬라이스 크기가 매우 중요함
  • 지나치게 클 때 : 사실상 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 생길 여지가 있음
  • 지나치게 작을 때 : 문맥 교환에 발생하는 비용이 커짐

최소 잔여 시간 우선 스케줄링

• SRT 스케줄링(Shortest Remainging Time Scheduling)
• 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식
• 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택됨

우선순위 스케줄링

• 우선순위 스케줄링(priority scheduling)
• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
• 기아(starvation) 현상 : 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기되는 현상
• 에이징(aging) : 기아 현상을 방지하기 위한 기법. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케줄링

• 다단계 큐 스케줄링(multilevel queue scheduling)
• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
• 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어 있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리
• 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해짐
• 큐마다 다른 스케줄링 알고리즘을 사용할 수 있음
• 프로세스들이 큐 사이를 이동할 수 없음 -> 우선순위가 낮은 프로세스는 계속 연기될 여지가 있음 (기아현상)

다단계 피드백 큐 스케줄링

• 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)
• 프로세스들이 큐 사이를 이동할 수 있음
  • 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 점차 우선순위가 높은 큐로 이동시키는 에이징 기법을 적용하여 기아 현상을 예방할 수 있음
• 동작방식
  • 새로 준비 상태가 된 프로세스가 있다면 우선순위가 가장 높은 우선순위 큐에 삽입되고 일정 시간(타임 슬라이스) 동안 실행됨
  • 만약 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선수위 큐에 삽입되어 실행됨
    
    => CPU를 비교적 오래 사용해야 하는 CPU 집중 프로세스들은 자연스레 우선순위가 낮아지고, CPU를 비교적 적게 사용하는 입출력 집중 프로세스들은 자연스레 우선순위가 높은 큐에서 실행이 끝남
• 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져 있음