[OS] 6. CPU 스케줄링

CPU 스케줄링

• 스케줄링은 다중 프로그래밍을 가능하게 하는 운영체제의 동작 기법이다.
• 운영체제는 프로세스들에게 CPU 등의 자원 배정을 적절히 함으로써 시스템의 성능을 개선할 수 있다.
• CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다.
• 스케줄링의 목적
  • 공정성 : 모든 프로세스에 공정하게 할당한다.
  • 처리율(량)증가 : 단위 시간당 프로세스를 처리하는 비율(양)을 증가시킨다.
  • CPU 이용률 증가 : 프로세스 실행 과정에서 주기억장치를 액세스한다든지, 입출력 명령 실행 등의 원인에 의해 발생할 수 있는 CPU 의 낭비 시간을 줄이고, CPU 가 순수하게 프로세스를 실행하는데 사용되는 시간 비율을 증가시킨다.
  • 우선순위 제도 : 우선순위가 높은 프로세스를 먼저 실행한다.
  • 오버헤드 최소화 : 오버헤드를 최소화한다.
  • 응답시간 최소화 : 작업을 지시하고 반응하기 시작하는 시간을 최소화한다.
  • 반환시간 최소화 : 프로세스를 제출한 시간부터 실행이 완료될 때까지 걸리는 시간을 최소화한다.
  • 대기시간 최소화 : 프로세스가 준비상태 큐에서 대기하는 시간을 최소화한다.
  • 균형있는 자원의 사용 : 메모리, 입출력장치 등의 자원을 균형있게 사용한다.
  • 무한 연기 회피 : 자원을 사용하기 위해 무한정 연기되는 상태를 회피한다.

선점형 스케줄링

• 하나의 프로세스가 CPU 를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU 를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.

  출처 : https://velog.velcdn.com

• 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.
• 주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용된다.
• 많은 오버헤드(문맥 교환 오버헤드)를 초래한다.
• 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록이 필요하다.
• 선점 스케줄링의 종류에는 라운드로빈, SRT, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등의 알고리즘이 있다.
• 용어
  • 처리량 : 단위 시간당 작업을 마친 프로세스의 수
  • 반환 시간 : 대기 시간 + 실행 시간
  • 평균 대기시간 : 모든 프로세스의 대기 시간의 합 / 프로세스 수
• RR (Round Robin Scheduling, RR)
  • 시분할 시스템을 위해 설계된 선점형 스케줄링
  • 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU 를 할당하는 방식의 알고리즘
  • 한 프로세스가 할당받은 타임 슬라이스동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.
  • 선점형 알고리즘 중 가장 대표적이고 단순한 방식으로, 프로세스들이 작업을 완료할 때 까지 계속 순환하면서 실행된다.
  • 라운드 로빈 알고리즘이 효과적으로 작동하려면, 문맥 교환에 따른 추가시간을 고려하여 타임 슬라이스를 적절하게 설정해야한다.
  • 타임 슬라이스의 크기는 프로세스의 반응 시간 및 시스템 전체의 성능에 영향을 미친다.
    • 타임 슬라이스가 큰 경우
      • 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보인다.
      • 실행하는 프로그램이 끊겨보이고 반응 속도가 매우 느리다.
    • 타임 슬라이스가 작은 경우
      • 문맥교환이 너무 자주 일어나 문맥교환에 걸리는 시간이 실제 작업 시간보다 커지며, 문맥 교환에 시간을 낭비하여 실제 작업을 못하는 문제가 발생한다.
      • 시스템의 성능이 떨어진다.
    • 유닉스 운영체제에서는 타임 슬라이스가 10~200 밀리초 사이로 조정한다.
• SRT (Shortest Remaining Time Scheduling)
  • 최단 잔여시간을 우선으로 하는 스케줄링
  • 진행 중인 프로세스가 있어도 최단 잔여시간인 프로세스를 위해 sleep 시키고 짧은 프로세스를 먼저 할당한다.
  • SJF 스케줄링과 라운드로빈 스케줄링을 혼합한 방식이다. 즉 SJF 스케줄링의 선점형 버전이다.
  • 기본적으로 라운드로빈 스케줄링을 사용하지만, CPU 를 할당받을 프로세스를 선택할 때 남아있는 작업시간이 가장 적은 프로세스를 선택한다.
  • 단점
    • 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야하므로 오버헤드가 발생한다.
    • 운영체제가 프로세스의 종료 시간을 예측하기 어렵다.
    • 기아 현상 : CPU 제어권을 얻기 위해 준비 큐에 줄 서 있는 상황에서 특정 프로세스는 CPU 를 얻지 못하고 무한정 기다리는 상태
• 우선순위 스케줄링
  • 우선순위를 반영한 스케줄링 알고리즘
    • 프로세스는 중요도에 따라서 우선순위를 갖는다.
  • 우선순위는 비선점형 방식과 선점형 방식에 모두 적용할 수 있다.
    • SJF 스케줄링(비선점형): 작업시간이 짧은 프로세스에 높은 우선순위 부여
    • HRN 스케줄링(비선점형): 작업시간이 짧거나 대기 시간이 긴 프로세스에 높은 우선순위 부여
    • SRT 스케줄링(선점형): 남은시간이 짧은 프로세스에 높은 우선순위 부여
  • 단점
    • 공평성 위배, 아사 현상 유발
      • 우선순위가 높은 프로세스에 먼저 CPU 를 할당
      • 아사 현상 : 작업 시간이 길다는 이유로 해당 프로세스가 계속 뒤로 밀려 공평성이 떨어지는 현상
    • 프로세스의 우선순위를 매번 바꿔야 하기 때문에 오버헤드가 발생하여 시스템의 효율성이 떨어진다.
• MLQ (MultiLevel Queue Scheduling)
  • 우선순위 마다 준비 큐 형성
  • 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다.
    • 라운드로빈 방식으로 운영되는 큐는 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되는 것만으로도 우선순위가 결정된다.
    • 우선순위는 고정형 우선순위를 사용한다.
  • 우선순위에 따라 다양한 스케줄링이 가능하다.
    • 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있다.
    • 우선순위에 따라 타임슬라이스를 조절하여 작업 효율을 올릴 수 있다.
      • e.g. 전면 프로세스는 반응속도를 높이기 위해 타임슬라이스를 작게 설정하고, 후면 프로세스는 사용자와 상호작용이 없으므로 FCFS 방식으로 처리한다.
  • 우선순위가 높은 상위 큐 프로세스의 작업이 끝날때까지 하위 큐 프로세스의 작업을 할 수 없다.
  • 우선순위가 낮은 프로세스는 오랫동안 CPU 할당을 기다리는 기아 현상이 발생할 수도 있다.
    • 이점을 개선한 알고리즘이 다단계 피드백 큐 스케줄링(MLFQ)이다.
  • 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어짐
• MLFQ (MultiLevel Feedback Queue)
  • 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링(MLQ)의 문제점을 보완한 방식
  • CPU 를 사용한 프로세스의 우선순위가 낮아진다.
    • CPU 를 사용한 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.
    • 다단계 큐 스케줄링에서는, 우선순위에는 변화가 없다.
    • 다단계 큐 스케줄링에서 발생하는 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화한다.
  • 우선순위에 따라 타임슬라이스의 크기가 다르다.
    • 우선순위가 낮은 프로세스의 경우, 어렵게 얻은 CPU를 오랫동안 사용할 수 있도록 타임슬라이스를 크게 설정한다.
  • 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식으로, 변동 우선순위 알고리즘의 전형적인 알고리즘이다.
  • 유닉스 운영체제에서 타임슬라이스(프로세스에 배당된 작업 시간)를 10~200밀리초 사이에서 조정할 수 있도록 한 이유는 다단계 피드백 큐 스케줄링을 사용하기 때문이다.

비선점형 스케줄링

• 이미 할당된 CPU 를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.

  출처 : https://velog.velcdn.com

• 프로세스가 CPU 를 할당받으면 해당 프로세스가 완료될 때까지 CPU 를 사용한다.
• 프로세스 응답 시간의 예측이 용이하며, 일괄 처리 방식에 적합하다.
• CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.
• 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생할 수 있다.
• 비선점 스케줄링의 종류에는 FCFS, SJF, 우선순위, HRN, 기한부 등의 알고리즘이 있다.
• FCFS(First Come First Served)
  • 준비 큐에 도착한 순서대로 CPU 를 할당받는 비선점형 알고리즘
  • 선입선출(FIFO) 스케줄링으로, 프로세스에 큐가 도착한 순서대로 실행되며 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다.
  • 큐가 하나라서 모든 프로세스는 우선순위가 동일하다.
  • 단점
    • 단순하고 공평하지만, 처리기간이 긴 프로세스가 CPU 를 차지하면 다른 프로세스는 기다려야 해서 세스템의 효율성이 떨어진다. (콘보이 효과, Convoy effect)
    • 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU 가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다.
• SJF(Shorteset Job First)
  • 준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU 를 할당하는 비선점형 알고리즘
  • 최단 작업 우선 스케줄링
  • FCFS 스케줄링의 콘보이 효과를 완화하여 평균 대기 시간이 줄기 때문에 시스템의 효율성을 높인다.
  • 단점
    • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
      • 현대의 프로세스는 사용자와의 상호작용이 빈번하게 발생하기 때문이다.
    • 공평성 위배
      • 작업시간이 긴 특정 프로세스의 작업이 계속 연기된다.
      • 기아 현상(Starvation)
      • 무한 봉쇄(Infinite Blocking)
• HRN(Highest Response ratio Next)
  • SJF 스케줄링에서 발생할 수 있는 아사현상을 해결하기 위해 만들어진 비선점형 알고리즘
  • 최고 응답률 우선 스케줄링
  • 우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용시간
  • 실행 시간이 짧은 프로세스의 우선순위를 높게 설정하면서도(=SJF 스케줄링), 대기 시간을 고려하여 아사 현상을 완화한다.
  • 단점
    • 공평성 위배

프로세스 우선순위

• 우선순위가 높다는 것은 더 빨리 자주 실행된다는 의미다.

  우선순위 높음	우선순위 낮음
  커널 프로세스	일반 프로세스
  전면 프로세스	후면 프로세스
  대화형 프로세스	일괄 처리 프로세스
  입출력 집중 프로세스	CPU 집중 프로세스

• CPU 집중 프로세스 : 수학 연산과 같이 CPU 를 많이 사용하는 프로세스
• 입출력 집중 프로세스 : 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스
• 전면 프로세스: GUI 를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스
  • 현재 입력과 출력을 사용하는 프로세스
  • 상호작용 프로세스라고도 한다.
• 후면 프로세스: 사용자와 상호작용이 없는 프로세스
  • 일괄 작업 프로세스라고도 한다.
  • e.g. 압축프로그램
• CPU 버스트(CPU burst): CPU 를 할당받아 실행하는 작업
• 입출력 버스트(I/O burst): CPU 를 할당받아 실행하는 입출력 작업
• 특징
  1. 일반 프로세스의 우선순위는 사용자가 조절할 수 있다.
     • 관리자(Administrator)만 우선순위를 높일 수 있고 일반 계정은 우선순위를 낮추는 것만 가능하다.
  2. 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템의 효율이 높향상된다.
     • 입출력 집중 프로세스가 실행 상태로 가면 입출력 요구에 의해 대기상태로 옮겨지기 때문에 다른 프로세스가 CPU 를 사용할 수 있다.
     • 사이클 훔치기(Cycle stealing): 입출력 집중 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우 발생할 수 있다.
     • CPU 집중 프로세스가 먼저 실행 상태로 들어가면 자신의 타임 슬라이스를 다 사용할 때까지 다른 프로세스가 실행되지 못한다.
• 예시
  • 워드 프로세서와 비디오 플레이어 중에서 비디오 플레이어의 우선순위가 높다.
  • 워드 프로세서의 경우, 사람이 타이핑하는 속도가 CPU 의 연산보다 느려서 천천히 실행되어도 문자 입력 처리가 가능하다.
  • 비디오 플레이어는 실시간으로 데이터를 읽어와 영상과 소리를 출력해야하기 때문에 자주 실행되지 않으면 화면이 끊긴다.
  • 전면 프로세스와 후면 프로세스 관점 (워드 프로세서 vs. 압축 프로그램)
    • 워드 프로세서는 사용자로부터 키보드로 입력을 받아야하기 때문에 전면 프로세스로 실행된다.
    • 압축 프로그램은 압축이 끝날 때까지 사용자의 입력이 필요없기 때문에 후면 프로세스로 실행된다.

다중 큐

• 준비 상태의 다중 큐
  • 프로세스의 중요도는 프로제스 제어 블록에 표시된다.
  • CPU 스케줄러는 모든 프로세스 제어블록을 뒤져서 가장 높은 우선순위의 프로세스에 CPU 를 할당한다.
  • 그러나 매번 프로세스의 제어 블록을 검색하는 것은 번거로운 일이다.
  • 이를 위해 준비상태의 프로세스를 우선순위에 따라서 여러 개의 큐로 관리한다.
  • 준비상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다.
  • 한번에 하나의 프로세스를 꺼내어 CPU 를 할당한다.
  • 프로세스의 우선순위를 배정하는 방식
    1. 고정 우선순위 방식: 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날때까지 바뀌지 않는 방식
       • 구현하기 쉽지만 작업 효율이 떨어진다.
    2. 변동 우선순위 방식: 프로세스 생성 시 부여받은 우선순위가 작업 중간에 변하는 방식
       • 구현하기 어렵지만 작업 효율이 올라간다.
    3. 반전 우선순위 방식: 프로세스의 낮은 우선순위를 높은 우선순위로 바꾸는 것으로, 시스템의 효율성을 향상시킬 수 있다.
       • 우선순위가 낮은 P1이 중요한 자원을 사용하고 있어 이 자원을 사용하는 다른 프로세스는 작업을 기다려야 한다.
       • 이 때 프로세스 P1의 우선순위를 높이면 다른 프로세스보다 CPU 를 더 자주 할당받게 되어 작업을 빨리 끝낼수 있으며, 이 자원을 기다리던 다른 프로세스의 작업도 원만하게 끝낼 수 있다.
• 대기 상태의 다중 큐
  • 시스템 내에는 다양한 종류의 입출력장치가 있기 때문에 대기 상태의 프로세스를 한 곳에 모아놓으면 관리하기가 불편하다.
  • 예를 들어 하드디스크에서 작업이 끝났다고 인터럽트가 발생한 경우, 해당 프로세스를 찾기 위해 대기 상태의 모든 프로세스를 검색하는 것은 번거로운 일이다.
  • 대기 상태는 입출력이 완료되기를 기다리는 프로세스가 모여있는 곳이다.
  • 같은 장치의 입출력을 기다리는 프로세스의 프로세스 제어 블록은 동일한 입출력 큐에서 관리한다.
    • 하드디스크의 입출력을 기다리는 프로세스 제어 블록은 모두 HDD 큐에 삽입된다.
  • 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮긴다. (인터럽트 벡터)

맨 위로 이동 ↑