다음은 반효경 교수님의 ‘운영체제와 정보기술의 원리’ CH6. CPU 스케줄링를 읽고 정리한 내용입니다 🙌



🌩 INTRO

  • CPU는 PC가 가리키는 명령어를 하나씩 수행하기 때문에 효율적으로 관리해야한다.
  • 기계어 명령은 다음 3가지로 나뉜다.
    1. CPU 내에서 수행되는 명령
      1. ADD 명령
      2. 수행 속도 빠르며 일반명령
      3. CPU 버스트
    2. 메모리 접근을 필요로 하는 명령
      1. LOAD 명령
      2. 메모리에 있는 데이터를 CPU로 읽는 명령
      3. CPU 명령보다는 오래 걸리지만 비교적 빠르며 일반명령
      4. CPU 버스트
    3. 입출력을 동반하는 명령
      1. 입출력 작업이필요한 경우이며 오랜 시간이 소요
      2. 특권명령으로 운영체제를 통해 서비스를 대행해야한다.
      3. I/O 버스트
    • CPU 수행은 위 명령어의 조합과 반복으로 이루어진다.
  • 각 프로그램마다 위 명령어들의 비율이 다르며 CPU 연산이 많이 이루어지는 것을 CPU 바운드 프로세스, I/O 연산이 많이 일어나는 것을 I/O 바운트 프로세스라고 한다.
    • I/O 바운드 프로세스는 사용자 인터렉션이 많은 대화형 프로그램이 해당된다.
  • 프로그램마다 CPU 사용패턴이 다르므로 버스트가 균일하지 않다. 때문에 효율적인 CPU 스캐줄링이 필요하다.
  • 컴퓨터에서 수행되는 대부분의 프로세스는 다수의 짧은 CPU 버스트와 소수의 긴 CPU 버스트로 구성이 된다.
    • CPU 버스트가 짧은 프로세스들은 대화형 작업으로 사용자와 인터렉션을 하며 입력을 받아서 연산을 수행하는 것이다.
    • 이런 작업은 빠른 응답을 위해 CPU의 빠른 서비스를 필요로 한다.
  • CPU 스캐줄링 시 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스캐줄링이 필요하다.
    • I/O 바운드 프로세스의 우선순위를 높이는 것이 필요하다.
  • I/O 바운드 프로세스에게 우선권을 주면 I/O 장치의 효율성을 높이며 CPU 연산을 하는 동안 I/O 장치가 휴먼 상태인 것도 방지할 수 있다.

🌩 1. CPU 스캐줄러

  • 운영체제의 코드로 준비 상태에 있는 프로세스들 중 어느 프로세스에게 CPU를 할당할지 결정한다.
  • 대표적으로 타이머 인터럽트가 발생하면 CPU 스캐줄러가 호출되며 준비 큐에 있는 프로세스 중 하나를 선택해서 CPU를 할당한다.
  • 다음과 같은 경우에도 호출된다.
    1. 실행상태 프로세스는 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우 - 비선점형
    2. 실행상태 프로세스가 타이머 인터럽트로 준비 상태로 바뀌는 경우 - 선점형
    3. 봉쇄상태 프로세스가 I/O 작업이 완료되어 인터럽트가 발생하고 준비상태로 바뀌는 경우 - 선점형
    4. CPU의 실행상태에 있던 프로세스가 종료되는 경우 - 비선점형
  • 스캐줄링 방식 2가지가 있다.
    • 비선점형 (nonpreemptive) 방식
      • CPU를 차지한 프로세스가 스스로 반납하기 전에 CPU를 뺏기지 않는 방법이다.
    • 선점형 (preemptive) 방식
      • 프로세스에게서 CPU를 강제로 빼앗을 수 있는 방식이다.
  • CPU 빼앗는 방법
    • 할당시간 time quantum을 부여하여 타이머 인터럽트를 발생시켜서 빼앗는다.

🌩 2. 디스패처

  • 다음 프로세스에게 CPU를 이양하는 작업을 수행하는 운영체제의 코드를 dispatcher라고 부른다.
    • 현재 프로세스의 문맥을 해당 프로세스의 PCB에 저장하고
    • 새로운 프로세스의 문맥을 PCB로부터 CPU에 복원한다.
    • 시스템의 상태를 사용자 모드로 전환하고 사용자 프로그램에게 CPU 제어권을 넘긴다.
  • 위 과정이 걸리는 시간은 디스패처 지연시간 dispatch latency라고 하며 문맥교환 오버헤드에 해당한다.

🌩 3. 스캐줄링의 성능 평가

  • 2가지 지표
    • 시스템 관점 지표
      • CPU 이용률 및 처리량
    • 사용자 관점 지표
      • 소요시간, 대기시간, 응답시간 등 기다린 시간
  • CPU utilization
    • 전체 시간 중 CPU가 일을 한 시간 비율이며 이용률은 시스템 전체 성능과 밀접하게 관련있다.
    • CPU의 휴면 idle 상태를 최대한 줄이는 것이 중요하다.
  • 처리량 throughput
    • 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇개를 끝냈는지를 나타낸다.
      • CPU 버스트를 완료한 프로세스 수
    • 처리량을 높이기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.
  • 소요시간 turnaround time
    • 프로세스가 CPU를 요청한 시점부터 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간
    • 준비큐에서 기다린 시간 + CPU 사용한 시간
    • 각 소요시간은 프로그램의 시작 및 종료 시간보다 CPU 버스트 단위로 별도로 측정한다.
  • 대기시간 waiting time
    • CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
    • 시분할 시스템에서는 한번의 CPU 버스트 중 준비큐에서 기다린 시간이 많을 수 있으며 이것의 합이다
  • 응답시간 response time
    • 프로세스가 준비 큐에 들어온 이후 첫번째 CPU 획득까지 걸린 시간
    • 타이머 인터럽트 주기가 짧을 경우 프로세스가 빨리 돌아가서 응답시간이 줄어드므로 향상된다.
    • 대화형 시스템에 적합한 성능 척도이며 사용자 입장에서 가장 중요한 척도이다.

🌩 4. 스캐줄링 알고리즘

선입선출 스케줄링 FCFS

  • 프로세스가 준비 큐에 도착한 시간 순대로 CPU를 할당하는 방식
  • 해당 프로세스가 자발적으로 CPU를 반납할 때까지 CPU를 빼앗기지 않는다.
  • 때로 비효율적인 결과를 초래한다.
    • CPU 버스트가 긴 프로세스가 짧은 프로세스 여러 개 보다 먼저 도착하면 CPU를 잠깐 사용하고 I/O 작업을 할 수 있는 프로세스가 앞의 긴 프로세스 하나 때문에 오래 기다려야 한다.
    • I/O 장치 이용률도 떨어진다.
  • 먼저 도착한 프로세스의 버스트 길이에 따라 평균 대기시간이 크게 달라진다.
  • convoy effect 콘보이 현상 - CPU 버스트가 짧은 프로세스가 버스트가 긴 프로세스부터 나중에 도착해 오랜 시간을 기다려야 하는 현상

최단작업 우선 스캐줄링 SJF (Shortest Job First)

  • CPU 버스트가 가장 짧은 프로세스에게 가장먼저 CPU를 할당하는 방식으로 프로세스의 준비 큐에서 기다리는 전체적인 시간이 줄어든다.
  • 대기시간을 가장 짧게 하는 최적 알고리즘이다.
  • 비선점형 방식과 선점형 방식
    • 비선점형은 CPU를 획득하면 해당 프로세스가 CPU를 자진 반납하기 전까지 CPU 할당
    • 선점형은 CPU에서 버스트가 가장 짧은 프로세스에게 할당하더라도 중간에 더 짧은 버스트 프로세스가 도착하면 CPU를 빼앗아 더 짧은 프로세스에게 우선 부여하는 방식
      • 현재 진행 중이던 프로세스의 남은 버스트 시간보다 더 짧은 경우이다.
      • SRTF Shortest Remaining Time First 라고도 부른다.
  • 일반적으로 프로세스가 한꺼번에 도착하지 않으므로 선점형 방식이 평균 대기시간을 가장 많이 줄일 수 있는 방법이다.
  • 하지만 프로세스의 CPU 버스트 시간을 미리 알 수 없다.
    • 따라서 CPU 시간을 예측하여 스캐줄링한다.
    • 이전 CPU 버스트 시간의 예측값과 실제값의 반영정도를 매개변수로 한 공식을 사용한다.
    • 과거의 CPU 버스트 시간들을 통해 미래 CPU 버스트 시간을 예측하는 것인데 최근 것일수록 가중치를 눂여서 반영하는 형식이다.
  • 평균 대기시간을 최소화 하기는 하지만 평균 CPU 버스트 시간이 긴 프로세스는 준비큐에서 무한정 기다려야하는 문제가 발생한다.
    • 기아 현상 starvation이라고 한다.

우선순위 스케줄링 priority scheduling

  • 준비 큐에서 기다리는 프로세스 중 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당한다.
  • 우선순위 값을 할당하며 숫자가 적은 것이 우선순위가 높은것으로 판단한다.
  • 우선순위값의 정의는 여러가지이다.
    • CPU 버스트 시간을 그 값으로 정하면 SJF 알고리즘과 동일하다.
  • 선점형과 비선점형이 있다.
    • 선점형은 수행중인 프로세스 보다 높은 우선순위 프로세스가 들어오면 선점하여 CPU를 할당한다.
  • 기아 현상이 발생할 수 있다.
    • 우선순위가 높은 프로세스가 계속 들어올 경우 CPU를 계속 할당받지 못하는 프로세스가 있을 수 있다.
    • 노화 aging 기법을 사용한다.
      • 기다리는 시간이 길어지면 우선순위를 조금씩 높여서 CPU를 할당받을 수 있게 한다.

라운드 로빈 스캐줄링 round robin scheduling

  • 시분할 시스템의 성질을 가장 잘 이용한 스캐줄링 방식이다.
  • 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 제한되며 시간이 경과하면 CPU를 회수해 다른 프로세스에게 할당한다.
  • 할당 시간 time quantum - CPU를 연속적으로 사용할 수 있는 최대시간
    • 할당시간이 너무 길면 FCFS와 동일해진다.
    • 할당시간이 너무 짧으면 문맥교환의 오버헤드가 커진다.
    • 일반적으로 수십밀리초 정도의 규모로 설정한다.
  • n 개의 프로세스에 q만큼의 할당시간이라고 하면 모든 프로세스는 적어도 (n-1)q 시간 이내에 적어도 한번 CPU를 할당받을 수 있다.
    • 대화형 프로세스에 빠른 응답시간을 보장한다.
  • n 개의 프로세스에 q만큼의 할당시간이라고 하면 모든 프로세스는 적어도 (n-1)q 시간 이내에 적어도 한번 CPU를 할당받을 수 있다.
    • 대화형 프로세스에 빠른 응답시간을 보장한다.
  • CPU 버스트가 긴 프로세스는 대기 시간이 비례해서 길어지고 적게 쓰는 프로세스는 대기시간도 짧아진다.
  • SJF 보다 평균 대기 시간은 길지만 응답시간은 더 짧다.
  • 할당시간이 만료되면 타이머 인터럽트로 CPU를 회수한다. 만일 CPU 버스트 시간이 할당 시간보다 짧으면 자진 반납한다.
    • 짧은 프로세스는 빨리 CPU를 얻으며 긴 프로세스도 불이익 당하지 않아서 매우 공정하다.
  • 소요시간과 대기시간이 CPU 버스트의 길이와 비례하여 공정하다.
  • FCFS와 비교했을 때 FCFS는 하나씩 프로세스를 끝마쳐 가므로 해당 프로세스의 소요시간 및 대기 시간이 짧아지지만 라운드 로빈 스케줄링은 CPU를 조금씩 같이 쓰고 거의 동시에 끝나게 되어 소요시간 및 대기시간이 가장 긴 프로세스에 어느정도 맞춰진다.
    • 동일한 CPU 버스트 시간을 가진 프로세스들이 도착할 경우 평균 소요시간 및 대기시간이 길어지지만 여전히 평균 응답시간은 더 짧다.
  • 하지만 주로 프로세스의 CPU 버스트 시간이 균일하지 않으므로 라운드 로빈 스캐줄링 기법이 타당한다.

멀티레벨 큐 multi-level queue

  • 큐를 여러개 분할해 관리하는 스캐줄링 기법이다.
  • 어떤 줄의 프로세스에 CPU를 할당하며 프로세스를 어떤 줄에 세워야할지 고려해야한다.
  • 성격이 다른 프로세스들을 별도로 관리하고 각각의 성격에 맞는 스케줄링을 큐마다 적용한다.
    • 예를 들어 대화형 작업과 그렇지 않은 작업을 따로 두어 대화형 작업에 우선적으로 CPU를 할당한다.
  • 일반적으로 전위큐 (foreground queue)와 후위큐(background queue)로 분할하여 운영한다.
    • 전위큐는 응답시간을 짧게하기 위한 라운드 로빈 스캐줄링
    • 후위큐는 계산 위주 작업으로 응답시간이 중요하지 않은 FCFS 스캐줄링 기법으로 문맥교환 오버헤드를 줄인다.
  • 큐 자체에 대한 스캐줄링도 필요하다.
    • 가장 쉬운 방법은 고정 우선순위 방식 fixed priority scheduling 이다.
      • 우선순위가 높은 큐를 먼저 서비스하고 해당 큐가 비면 우선순위가 낮은 큐를 서비스한다.
    • 타임 슬라이스 time slice 방식
      • 큐의 기아 현상을 해소하기위해 각 큐에 CPU 시간을 적절한 비율로 할당한다.

멀티레벨 피드백 큐 multilevel feedback queue

  • 멀티레벨큐와 비슷하나 프로세스가 하나의 큐에서 다른 큐로 이동할 수 있다.
    • 예를 들어 노화 기법을 사용하여 우선순위가 낮은 큐에서 높은 큐로 이동할 수 있다.
  • 큐의 수, 각 큐의 스캐줄링 알고리즘, 프로세스를 상위 큐로 승격시키는 기준, 프로세스를 강등시키는 기준, 프로세스가 도착할 대 큐를 결정하는 기준 등을 고려해야한다.
  • 일반적인 멀티레벨 피드백 큐는
    • 3개의 큐로 구성되며 우선순위 순으로 라운드로빈 (할당시간 5) → 라운드로빈 (할당시간 10) → FCFS 이다.
    • 대화형 서비스는 빨리 작업을 완료할 수 있다.
    • 모든 프로세스들은 처음에 상위 큐에 있다가 할당시간만큼 서비스 되고 나서 버스트 기간이 남으면 하위 큐로 강등된다.
    • 큐는 최상위 큐가 비었을 때 하위 큐가 서비스 받는다.

다중처리기 스케줄링 multi-processor system

  • 각 CPU 별로 줄을 세워야하므로 더 복잡하다.
  • 일부 CPU에 작업이 편중될 수도 있는데 이것을 방지하기 위해 적절히 분산되도록 부하균형(load balancing) 매커니즘이 필요하다.
  • 대칭형 다중처리
    • CPU가 각자 알아서 스케줄링을 결정한다.
  • 비대칭형 다중처리
    • 하나의 CPU가 다른 CPU 스캐줄링 및 데이터 접근을 책임진다.

실시간 스케줄링

  • 각 작업마다 데드라인이 있어서 반드시 처리해야하는 real-time system에서 사용된다.
  • 경성 실시간 시스템 hard real-time system과 연성 실시간 시스템 soft real-time system 으로 나뉜다.
    • 전자는 미사일 원자로 제어 등 반드시 정확해야하는 시스템
    • 후자는 위험하지는 않은 멀티미디어 스트리밍 시스템
  • 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF earliest dedline first 스캐줄링을 사용한다.

🌩 5. 스캐줄링 알고리즘의 평가

  • 큐잉 모델
    • 확률분포 등 수학적으로 구해서 평가한다.
  • 구현 및 실측
    • 실제로 수행하여 커널을 컴파일하여 실행시간 측정하여 평가한다.
  • 시물레이션
    • 가상 CPU 스캐줄링 프로그램을 작성하여 결과를 확인한다.