CPU 스케줄링

• CPU 버스트가 균일하지 않은 다양한 프로그램이 공존하므로 효율적인 CPU 스케줄링 기법이 필요하다.
  • 사용자 프로그램이 수행되는 과정은 CPU 작업과 I/O 작업의 반복으로 구성된다.
  • 각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지는 않다.
  • 대부분의 프로세스가 짧은 CPU 버스트를 가지며 극히 일부분만 긴 CPU 버스트를 가진다.
  • I/O 바운드 프로세스의 CPU 할당 우선순위를 높여주어서 전체적인 효율을 높이는 게 중요하다.
  • CPU burst
    • 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 단계
    • Add, Load, Store 명령 등
  • I/O burst
    • I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
    • 입출력 명령
  • I/O bound process
    • I/O 버스트가 빈번해 CPU 버스트가 매우 짧게 나타나는 프로세스
  • CPU bound process
    • I/O 를 거의 하지 않아 CPU 버스트가 매우 길게 나타나는 프로세스
• CPU 스케줄러
  • CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드다.
  • 프로세스가 명령을 수행 중 타이머 인터럽트가 발생하면 CPU 스케줄러가 호출되고 CPU 스케줄러는 준비 큐에서 CPU를 기다리는 프로세스 중 하나를 선택해 CPU를 할당한다.
  • 스케줄링 방식(스케줄러가 프로세스를 제어할 수 있느냐 없느냐)
    • 선점형
      • 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법
        • 실행상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비상태로 바뀌는 경우
        • I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 준비 상태로 바뀌고 완료된 프로세스가 인터럽트 당한 프로세스보다 우선순위가 높은 경우
      • 장점
        • 실행 중인 프로세스가 I/O 등의 이벤트 발생 등으로 인해 중단될 경우에 강제로 빼앗아 다른 프로세스에게 CPU를 할당할 수 있기 때문에 CPU 자원을 효율적으로 활용할 수 있다.
      • 단점
        • 실행 중인 프로세스가 중간에 강제로 중지되어야 하므로, 이에 대한 오버헤드가 발생할 수 있다.
        • 실행 중인 프로세스가 다른 프로세스에 의해 계속 중지되면, 해당 프로세스의 실행 시간이 길어지며, 이는 일부 프로세스의 실행이 늦어질 가능성을 높일 수 있다.
    • 비선점형
      • CPU 비선점형 스케줄러란, 현재 CPU를 점유하고 있는 프로세스가 I/O 등의 이벤트 발생 등으로 실행 중지될 경우, 이 프로세스가 다시 실행 가능한 상태가 되기 전까지 다른 프로세스가 CPU를 점유하지 않고 대기하는 스케줄링 방식을 의미한다.
      • 즉, CPU가 점유되고 있는 프로세스가 실행 중지되어도 다른 프로세스가 그 자리를 대기하는 것이 아니라, 해당 프로세스가 다시 실행 가능한 상태가 되기를 기다리는 것이다.
      • 프로세스가 자발적으로 blocked 되거나 실행이 끝난 경우에만 다른 프로세스가 CPU 점유 가능
        • 실행 상태에 있던 프로세스가 I/O 요청에 의해 봉쇄 상태로 바뀌는 경우
        • CPU에서 실행 상태에 있는 프로세스가 종료되는 경우
      • 장점
        • 실행 중인 프로세스가 실행을 잠시 멈추더라도 CPU 자원을 계속 활용할 수 있다.
        • 만약 CPU가 실행 중인 프로세스가 I/O 등의 이벤트 발생으로 인해 잠시 멈추는 경우, 다른 프로세스가 그 동안 CPU 자원을 활용하여 실행되므로, 전체적인 시스템 성능을 높일 수 있다. 
      • 단점
        • 실행 중인 프로세스가 종료되기를 기다리는 경우에는 다른 프로세스가 CPU를 사용할 수 없다.
        • 실행 중인 프로세스가 짧은 시간 동안 실행되는 경우에는 효과적이지만, 실행 시간이 긴 프로세스의 경우 다른 프로세스가 오랜 시간 동안 CPU를 사용하지 못할 수 있다.
• 디스패처(dispatcher)
  • CPU를 새롭게 할당받은 선택된 프로세스가 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드를 디스패처라고 부른다.
  • 디스패처는 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.
  • 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패치 지연시간이라고 하며, 디스패치 지연시간의 대부분은 문맥교환 오버헤드에 해당한다.
  • 새로운 프로세스의 문맥을 복원시킨 후에는 시스템의 상태를 사용자모드로 전환해 사용자 프로그램에게 CPU의 제어권을 넘긴다.
  • 사용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소를 찾아서 명령을 실행한다.
• 스케줄링의 성능 평가
  • 시스템 관점 지표
    • CPU 이용률
      • 전체 시간 중 CPU가 일을 한 시간의 비율. 휴먼 상태의 시간의 비율을 최대한 줄여야 좋다.
    • 처리량
      • 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇개를 끝마쳤는지를 나타낸다.
      • 여러 프로세스가 CPU를 기다리고 있는 상황에서 주어진 시간에 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.
  • 사용자 관점 지표
    • 소요시간
      • 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간
      • 준비큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합을 의미한다.
    • 대기시간
      • CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다란 시간의 합을 뜻한다.
    • 응답시간
      • 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간을 뜻한다.
        타이머 인터럽트가 빈번하게 발생할수록 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 짧아지므로 처음 CPU를 얻기까지 걸리는 시간은 줄어들게 되어 응답시간이 향상된다.
• 스케줄링 알고리즘
  • 선입선출(First-Come First-Served, FCFS) 스케줄링
    • 프로세스가 준비큐에 도착한 시간 순서대로 CPU를 할당하는 방식
    • 먼저 요청한 프로세스에게 CPU를 먼저 할당하고 자발적으로 CPU를 반납할 때까지 빼앗지 않는다.
    • CPU 버스트가 긴 프로세스가 먼저 요청할 경우, CPU를 잠깐만 사용하면 준비 큐를 떠나 I/O 작업을 수행할 수 있는 다수의 프로세스들이 기다리는 비효율이 발생할 수 있다.
    • 이러한 비효율적인 현상은 콘보이(conboy) 현상이라고 부른다.
  • 최단작업(Shortest-Job First, SJF) 우선 스케줄링
    • CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
    • 평균 대기시간이 가장 짧게 하는 최적 알고리즘
    • 비선점형 방식으로 구현
      • CPU를 획득하면 그 프로세스가 자진 반납하기 전까지 CPU를 빼앗지 않는 방식
    • 선점형 방식으로 구현
      • 준비큐에서 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당했다 하더라도, CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식
      • 실행 중인 프로세스의 남은 CPU 버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗는다.(Shortest Remaining Time First, SRTF)
      • 보통 CPU작업을 필요로 하는 프로세스가 동시에 준비 큐에 도착하지 않는다. 그래서 프로세스들이 준비 큐에 도착하는 시간이 불규칙한 환경에서는 선점형 방식이 프로세스들의 평균 대기시간을 최소화하는 최적의 알고리즘이 된다.
      • 프로세스의 CPU 버스트 시간은 과거의 CPU 버스트 시간을 통한 예측치로 비교한다.
      • CPU 버스트가 짧은 프로세스가 계속 도착할 경우 긴 CPU 버스트 시간을 갖는 프로세스는 영원히 CPU를 할당받을 수 없을 수도 있게 된다. 이러한 현상을 기아(starvation) 현상이라고 부른다.
  • 우선순위(priority) 스케줄링
    • 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
    • 최단작업 우선 스케줄링처럼 기아 현상이 발생할 수 있다.
    • 기아 현상을 해결하기 위해 노화(aging) 기법을 사용할 수 있다.
    • 기다리는 시간이 길어질수록 우선순위를 조금씩 높여서 너무 오래 기다리지 않게 한다.
  • 라운드 로빈(Round Robin) 스케줄링
    • 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 제한 시간이 경과하면 타이머 인터럽트로 CPU를 회수하고 준비큐에 대기하는 다른 프로세스에게 CPU를 할당하는 방식
    • 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 할당 시간이라고 부른다.
    • 할당시간이 너무 길면 라운드 로빈 스케줄링은 FCFS와 같은 결과를 나타낸다.
    • 할당시간이 너무 짧으면 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커진다.
    • 일반적으로 할당시간은 수십 밀리초 정도의 규모로 설정한다. 이는 사람이 느리지 않다고 체감할 정도의 시간 안에 한 번씩은 CPU를 할당받을 수 있게 한 것이다.
    • 라운드 로빈 스케줄링은 일반적으로 SJF 방식보다 평균 대기시간은 길지만 응답시간은 더 짧다.
  • 멀티 레벨 큐
    • 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법
    • 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두어서 관리한다.
    • 빠른 응답을 필요로 하는 대화형 작업을 담기 위한 전위 큐
      • 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용한다.
    • 계산 위주의 작업을 담기 위한 후위 큐
      • 응답시간은 큰 의미가 없으므로 문맥 교환 오버헤드를 줄이기 휘해 FCFS 스케줄링을 사용
    • 여러 개의 준비 큐 자체에 적용할 스케줄링 기법
      • 고정 우선순위 방식
        • 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어있을 때에만 서비스한다.
      • 타임 슬라이스 방식
        • 큐에 대한 기아 현상을 해소할 수 있는 방식으로 각 큐에 CPU 시간을 적절한 비율로 할당한다.
  • 멀티 레벨 피드백 큐
    • CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
    • 우선순위가 낮은 큐에서 오래 기다린 프로세스를 우선순위가 높은 큐로 이동시켜 기아현상을 해결할 수도 있다.
  • 다중처리기 스케줄링
    • CPU가 여러 개인 시스템을 다중처리기 시스템이라고 부른다.
    • 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내어 가도록 할 수 있다.
    • 은행창구에서 번호표를 뽑은 고객을 호출하는 방식과 유사하다.
    • 또는 각 CPU 별로 여러 줄로 준비 큐를 관리할 수도 있다. 이때 각 CPU별 부하가 적절히 분산되도록 하는 부하 균형 메커니즘을 필요로 한다. (load balancing)
  • 실시간 스케줄링
    • 실시간 시스템에서는 각 작업마다 주어진 데드라인이 있어서 정해진 데드라인 안에 반드시 작업을 처리해야 한다.
    • 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 사용한다.
    • hard real-time system: 미사일 발사, 원자로 제어같이 반드시 정해진 시간을 지켜야 한다.
    • soft real-time system: 멀티미디어 스트리밍 시스템. 데드라인을 못 지켜도 위험한 상황이 발생하지는 않음
  • 스케줄링 알고리즘의 평가 방식
    • 큐잉 모델
      • 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 주어서 수학적 계산을 통해 각종 성능지표인 CPU 처리량, 프로세스의 평균 대기시간 등을 구한다.
    • 시뮬레이션
      • 가상의 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 결과를 확인하는 방법
      • 입력값은 가상으로 사용할 수 있고 실제 시스템에서 추출한 입력값인 트레이스(trace)를 사용할 수도 있다.
      • 트레이스는 몇 초에 어떤 프로세스가 도착하고, 각각 CPU 버스트 시간을 얼마로 하는지에 대한 정보를 시간 순서대로 적어놓은 파일을 의미한다.
    • 구현 및 실측
      • 실제로 커널의 스케줄링을 수행하는 코드를 직접 수정하여 실행시간을 측정한 후 비교하고 알고리즘의 성능을 평가한다.