Post

6장 CPU 스케줄링

Study, OS
운영체제와 정보기술의 원리
Posted

서론


시분할 시스템에서의 CPU관리는 매우 효율적으로 관리되어야 하는 자원이다.

프로그램 실행에서 사용되는 명령에는 크게 3가지가 있다.

CPU내에서 수행되는 명령은 대표적으로 Add 명령이 있으며, CPU내에서 수행되므로 수행속도가 빠르다.

메모리 접근을 필요로 하는 명령은 대표적오르 Load, Store 명령이 있으며, Add보다는 느리나 비교적 빠른 시간에 수행할 수 있는 명령에 해당된다.

위 두 명령은 사용자 프로그램이 직접 실행할 수 있는 일반명령이다.

입출력을 동반하는 명령은 느리고, 특권명령에 해당한다.


그래서 프로그램은 두 단계가 반복되면서 실행되는데, CPU를 가지고 수행되는 빠른 단계와 I/O 요청으로 커널의 입출력 작업을 진행하는 느린 단계이다.

전자를 CPU 버스트, 후자를 I/O 버스트라 부르는데 각 프로그램마다 두 버스트의 비율이 균일하지 않다.

CPU 버스트가 비교적 긴 프로그램은 CPU 바운드 프로세스라 하고, I/O 버스트가 빈번해 CPU 버스트가 짧은 프로그램은 I/O 바운드 프로세스라고 한다.


CPU 스케줄링은 이러한 CPU 사용시간이 상이한 여러 프로그램들이 있기 때문에 필요하다.

대부분 프로그램은 짧은 CPU 버스트를 가지는데, 이런 프로세스들은 대부분 대화형 작업 즉, 사용자의 입력을 받아 CPU 작업 후 그 결과를 다시 출력하는 작업을 수행한다.

따라서 CPU 스케줄링을 할 때 짧은 프로세스에게 우선적으로 할당해주는 스케줄링이 필요하다.

다른 말로 I/O 바운드 프로세스의 우선순위를 높여주는 것이다.





CPU 스케줄러


CPU 스케줄러는 준비상태에 있는 프로세스들 중 어느 프로세스에게 CPU를 할당할지를 결정하는 운영체제의 코드이다.

CPU 스케줄링이 필요한 경우는 다음과 같다.


  • 실행 상태에 있는 프로세스가 I/O 요청에 의해 봉쇄 상태로 바뀌는 경우

  • 실행 상태의 프로세스가 타이머 인터럽트로 인해 준비 상태로 바뀌는 경우

  • 봉쇄 상태에 있던 프로세스의 I/O 연산이 완료되어 준비 상태로 바뀌는 경우

  • 실행 중이던 프로세스가 작업이 완료되어 종료되는 경우


CPU 스케줄링 방식으로 비선점형(nonpreemptive)와 선점형(preemptive) 방식이 있다.

비선점형은 사용 중이던 프로세스가 스스로 반납하기 전까지 CPU를 빼앗기지 않는 방법이다.

선점형은 타이머 인터럽트 등을 통해 CPU를 빼앗아가는 방법이다.

1번과 4번이 비선점형, 2번과 3번이 선점형 방식이라 볼 수 있다.





디스패치


디스패치는 5장에서 배웠듯이 준비상태에 있는 프로세스들 중 CPU를 할당해주는 작업이다.

할당받은 프로세스가 작업을 수행할 수 있도록 환경설정하는 운영체제의 코드를 디스패처(dispatcher)라고 부른다.

디스패처는 현재 수행 중이던 프로세스의 문맥을 PCB에 저장, 새로운 프로세스의 문맥을 PCB에서 가져오고 사용자모드로 전환해 그 프로세스에게 CPU 권한을 넘긴다.

디스패처가 이러한 작업을 수행하는 시간을 디스패치 지연시간(dispatch latency)라고 하며, 지연시간의 대부분은 문맥교환 오버헤드에 해당된다.





스케줄링의 성능 평가


스케줄링 기법을 평가하기 위해 여러 지표가 사용되는데, 시스템 관점과 사용자 관점에서 나눌 수 있다.


  • 시스템 관점
    • CPU 이용률(CPU utilization)
      • 전체 시간 중에서 CPU가 일을 한 시간의 비율
    • 처리량(throughput)
      • 주어진 시간 동안 준비 큐에서 대기중인 프로세스들 중 몇 개의 프로세스를 처리했는지
      • CPU 버스트가 짧은 프로세스에게 우선적으로 할당하는 것이 유리하다.


  • 사용자 관점
    • 소요시간(turnaround time)
      • 준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간
      • 프로그램이 시작하고부터 종료하기까지의 시간이 아니다.
    • 대기시간(waiting time)
      • 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
      • 타이머로 인해 여러번 할당받게 되므로 이번 CPU 버스트가 끝나기까지 준비 큐에서 기다린 시간의 합을 뜻한다
    • 응답시간(response time)
      • 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 할당받기까지 걸린 시간
      • 여러 번 음식을 받는다고 할 때, 첫 번째 음식이 나오기까지 걸린 시간이라 생각하면 된다.





스케줄링 알고리즘


  • FCFS(First Come First Serve)
    • 단점은 CPU 버스트 시간이 긴 프로세스가 먼저 오면 오래 기다리게 되는 콘보이 현상(Convoy effect)이 발생한다.


  • 최단작업 우선(Shortest-Job First, SJF) 스케줄링

    • CPU 버스트가 가장 짧은 프로세스에게 먼저 할당

    • 비선점형, 선점형 방식이 있으며 대략적인 뜻인 위에서 설명한 것과 같다.
      • 선점형에서는 현재 CPU가 할당된 프로세스보다 더 짧은 버스트 시간을 가진 프로세스가 도착하면 CPU를 뺏어서 더 짧은 프로세스에게 전달한다.
      • 이러한 선점형 방식을 SRTF(Shortest Remaining Time First)라고 한다.
    • 현실적으로 어려운 부분은 프로세스의 CPU 버스트 시간을 미리 알 수 없다는 점으로, 예측을 통해 할당하게 된다.
      • 예측은 과거의 CPU 버스트 시간을 통해 이루어지는데, 오래된 과거일수록 영향력이 적어지도록 반영하는 방식이다.
    • 단점은 항상 좋은 방식이라 할 수 없는데 왜냐하면, CPU 버스트가 긴 프로세스는 무한정 기다리는 문제(기아 현상, starvation)가 발생할 수 있다.


  • 우선순위(priority) 스케줄링

    • 비선점형과 선점형 방식으로 구분하고 맥락은 같다.

    • 문제점은 기아 현상이 발생할 수 있다.

    • 해결방법으로 노화(aging) 기법을 사용하는데, 노화 기법은 기다리는 시간이 길어지면 우선순위를 높이는 방법이다.


  • 라운드로빈(round robin) 스케줄링

    • 타이머 스케줄링이라 생각하면 된다 즉, 시분할 시스템 성질을 가장 잘 활용한 스케줄링이다.

    • 프로세스 문맥 오버헤드가 있으므로 적절한 시간을 설정하는 것이 중요하다.


그 외에 준비 큐를 여러 개 두는 멀티레벨 큐, 더 나아가 멀티레벨 피드백 큐가 있고 다중 CPU 시스템에서는 다중처리기 스케줄링이 있다.

실시간 시스템에 대해서는 실시간 스케줄링이 있다.





스케줄링 알고리즘 평가


성능을 평가하는 방법으로 큐잉모델, 시뮬레이션, 구현 및 실측 방식이 있다.





Study, OS
운영체제와 정보기술의 원리
This post is licensed under CC BY 4.0 by the author.