6 CPU 스케줄링

7 minute read

6. CPU 스케줄링

CPU(Central processing unit): 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙처리장치

  1. CPU 내에서 수행되는 명령
    • ex. Add 명령 수행속도가 매우 빠름
  2. 메모리 접근을 필요로 하는 명령
    • ex. Load, Store 명령
    • CPU 내에서 수행되는 명령보다는 오래 걸리지만 비교적 짧은 시간에 수행할 수 있는 명령

⇒ 1,2는 사용자 프로그램이 직접 실행할 수 있는 일반명령에 해당

  1. 입출력을 동반하는 명령
    • 운영체제가 대행 (by 시스템 콜)
    • 오랜 시간 소요
    • 모두 특권명령으로 규정되어 있음

사용자 프로그램이 수행되는 과정은 cpu작업과 I/O 작업의 반복으로 구성됨.

  • CPU 버스트 : 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계

  • I/O 버스트 : I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계

  • I/O 바운드 프로세스 : I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
    • 주로 사용자로부터 인터랙션을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램
  • CPU 바운드 프로세스 : I/O 작업을 거의 하지 않아 CPU 버스트가 길게 나타나는 프로세스
    • 프로그램 수행의 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램
  • CPU 스케줄링 시 I/O 바운드 프로세스의 우선순위를 높여주는게 바람직하다
    • 대화형 프로그램 -> CPU 연산이 짧게 여러번 있음 -> CPU를 우선적으로 줘서 자주 빨리 처리하게 해야함

프로그램 별로 상이한 CPU 사용패턴이 존재하기 때문에 CPU 스케줄링이 필요

I/O 바운드 프로세스

1. CPU 스케줄러

준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 cpu를 할당할지 결정하는 운영체제의 코드

  • cpu 스케줄링이 필요한 경우
    1. 실행 상태에 있던 프로세스가 i/o 요청 등에 의해 봉쇄 상태로 바뀌는 경우
    2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
    3. (io → 봉쇄 상태) → 준비 상태
    4. 실행 상태에 있는 프로세스가 종료되는 경우
  • 비선점형
    • cpu를 획득한 프로세스가 스스로 cpu를 반납하기 전까지 cpu를 빼앗기지 않는 방법 (1, 4)
  • 선점형
    • cpu를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법 (2, 3)
    • 타이머 인터럽트 발생

2. 디스패처

CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하고나면 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하다. 이 때, 문맥교환(context switch)이 일어나게 되는데 디스패처(dispatcher)가 이를 수행해준다.

  • 프로세스의 문맥을 그 프로세스의 PCB에 저장 -> 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원 -> 그 프로세스에게 CPU를 넘김

디스패치 지연시간

  • 하나의 프로세스를 정지시키고 다른 프로세스에게 cpu를 전달하기 까지 걸리는 시간
  • 디스패치 지연시간의 대부분은 문맥교환 오버헤드에 해당됨

3. 스케줄링의 성능 평가

1. 시스템 관점

  • CPU 이용률 (CPU utilization)
    • 전체 시간중에서 CPU가 일을 한 시간의 비율 (일을 하지않고 휴면(idle) 상태에 머무르는 것을 줄이는 것이 목표)
  • 처리량 (throughput)
    • 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지 (cpu 버스트를 완료한 프로세스의 개수)
    • 처리량을 높이기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리

2. 사용자 관점

  • 소요시간 (turnaround time)
    • 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간
    • 준비큐에서 기다린 시간 + 실제로 CPU를 사용한 시간
  • 대기시간 (wating time)
    • cpu 버스트 기간 중 프로세스가 준비 큐에서 cpu를 얻기 위해 기다린 시간의 합
    • 한 번의 cpu 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있다.
  • 응답시간 (response time)
    • 프로세스가 준비 큐에 들어온 후 첫 번째 cpu를 획득하기까지 기다린 시간
    • 타이머 인터럽트가 빈번히 발생할수록 각 프로세스가 cpu를 연속적으로 사용할 수 있는 시간이 짧아지므로 처음 cpu를 얻기까지 걸리는 시간은 줄어들게 되어 응답시간이 향상됨
    • 대화형 시스템에 적합한 성능 척도 (사용자 입장에서 가장 중요한 척도)

4. 스케줄링 알고리즘

1. 선입선출 스케줄링 (First Come First Served : FCFS)

  • 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
  • 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않음

콘보이 현상(Convoy effect) : 잠깐만 사용하면 되는 프로세스는 앞의 긴 작업을 계속 기다려야 하기 때문에 평균 대기시간은 물론 I/O 장치들의 이용률까지 동반 하락

2. 최단작업 우선 스케줄링 (Shortest Job First : SJF)

  • CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  • 평균 대기시간을 가장 짧게 하는 최적 알고리즘
  • 비선점형 방식 : 일단 CPU를 획득하면 자진반납할 때까지 빼앗지 않음
  • 선점형 방식 (Shortest Remaining Time First : SRTF) : 할당받아도 더 짧은 프로세스가 도착할 경우 빼앗아 더 짧은 프로세스에게 부여, 일반적인 시분할 환경에서 평균 대기시간을 가장 많이 줄일 수 있는 방식
  • 프로세스의 CPU 버스트 시간을 미리 알 수 없으므로 과거의 CPU 버스트 시간을 통해 CPU 버스트 시간을 예측한 뒤 예측치가 가장 짧은 프로세스에게 CPU 할당

기아 현상(starvation) : CPU 버스트가 긴 프로세스는 준비 큐에서 무한정 기다려야 하는 문제

3. 우선순위 스케줄링 (priority scheduling)

  • 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  • 우선순위는 우선순위 값을 통해 표시, 작을수록 높은 우선순위
  • 우선순위를 결정하는 지표로 CPU 버스트 시간을 사용하면 SJF 알고리즘과 동일한 의미
    • 비선점형 방식 : 일단 CPU를 획득하면 자진반납할 때까지 빼앗지 않음
    • 선점형 방식 : 할당받아도 우선순위가 더 높은 프로세스가 도착하면 CPU를 빼앗아 더 높은 프로세스에게 부여
  • 시스템과 관련된 중요한 작업을 수행하는 프로세스의 우선순위를 높게 부여하면 이러한 프로세스가 cpu를 빨리 할당받을 수 있게 할 수 도있음

기아 현상(starvation) : 우선순위가 낮은 프로세스는 CPU를 얻지 못한 채 계속 기다려야 함

⇒ 노화(aging) 기법 : 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 CPU를 할당받을 수 있게 해주는 방법

4. 라운드 로빈 스케줄링

  • 시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식

  • 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정 시간으로 제한하고 이 시간이 지나면 CPU를 빼앗음

  • 최대 할당 시간 (time quantum) : 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간
    • 할당시간 ⬆️ : FCFS와 같은 결과, CPU 버스트 시간이 매우 긴 프로세스가 모든 작업을 수행할 만큼 할당시간을 길게 설정하는 경우
    • 할당시간 ⬇️ : CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥교환 오버헤드 발생
    • 프로세스 n개, 할당시간 q인 경우, 모든 프로세스는 (n-1)q 시간 내에 적어도 한 번 CPU를 할당받을 수 있음
  • 대화형 프로세스의 빠른 응답시간을 보장할 수 있음

  • CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있고, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 함 ⇒ 공정한 스케줄링 방식

  • 일반적으로 SJF 방식보다 평균 대기시간을 길지만, 응답시간은 더 짧음
  • 할당시간이 만료되면 타이머 인터럽트를 발생해 CPU 회수, CPU 버스트 시간이 할당시간보다 짧으면 사용완료 후 스스로 반납

FCFS vs SJF vs 라운드로빈

FCFS (선입선출)

  • 프로세스를 하나씩 끝내는 방식이므로, 평균 대기시간이나 평균 소요시간 측면에서 좋은 결과를 얻을 수 있지만 프로세스 간 대기시간이나 소요시간의 편차가 매우 크며, 평균 응답시간이 지나치게 길어지는 문제가 있음

SJF (최단 작업 우선)

  • 평균 대기시간 측면에서 가장 우수하지만 cpu버스트 시간이 짧은 프로세스에게만 유리하고 긴 프로세스들은 전체 시스템의 성능을 향상시키기 위해 희생해야 한다.

라운드 로빈

  • CPU를 조금씩 같이 쓰고 거의 동시에 끝나게 되어 대기시간이나 처리시간의 편차는 크지 않지만, 평균 대기시간과 평균 소요시간이 길어 비효율적
  • 동일한 CPU 버스트 시간을 가지는 프로세스들에 라운드 로빈 스케줄링을 적용하면 평균 대기시간과 평균 소요시간은 FCFS의 거의 두 배, 하지만 평균 응답시간은 더 짧음

5. 멀티레벨 큐

  • 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법, 즉 프로세스들이 한줄이 아닌 여러줄로 기다리는 것
  • 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 분리
    • 빠른 응답을 필요로 하는 대화형 작업과 그렇지 않은 작업을 분리
  • 하나뿐인 CPU를 어느 줄에 먼저 스케줄링할 것인가 + 프로세스가 도착했을 때 어느 줄에 세울 것인가
  1. 전위큐 (foreground queue) : 대화형 작업
    • 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용
  2. 후위큐 (background queue) : 계산 위주의 작업
    • 응답시간이 큰 의미를 가지지 않기 때문에 FCFS 사용해 문맥교환의 오버헤드 줄임
  • 큐 자체의 스케줄링 (어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링)
    1. 고정 우선순위 방식(fixed priority scheduling) : 큐에 고정 우선순위를 부여해 우선순위가 높은 큐 먼저 서비스 (전위 큐가 우선적)
    2. 타임 슬라이스 방식(time sclice) : 각 큐에 CPU 시간을 적절한 비율로 할당 (80:20), 큐에 대한 기아 현상을 해소할 수 있는 방식

6. 멀티레벨 피드백 큐

  • 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동가능하다는 점이 추가됨
  • 프로세스들의 다양한 성격을 반영해 구현가능, 에이징(aging)을 이와 같은 방식으로 구현가능
  • 멀티레벨 피드백 큐를 정의하는 파라미터들
    • 큐의 수
    • 각 큐의 스케줄링 알고리즘
    • 프로세스를 상위큐로 승격시키는 기준
    • 프로세스를 하위큐로 강등시키는 기준
    • 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준

과정

멀티레벨 피드백 큐

  • CPU 버스트가 긴 프로세스들은 처음 8만큼 CPU를 사용하고도 작업이 완료되지 않으면 > 16인 하위큐로 내려가서 줄서고 본인 차례가 되어 16만큼을 추가로 사용하고도 작업이 완료되지 않으면 > CPU를 오래 사용하는 계산 위주의 프로세스로 간주되어 최하위 큐로 이동해 FCFS 스케줄링을 적용

    ⇒ 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하고 작업시간이 긴 프로세스에 대해서는 문맥교환 오버헤드를 줄임

7. 다중처리기 스케줄링

  • CPU가 여러 개인 시스템
  • 프로세스를 준비큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내어가도록 함
  • 특정 CPU에서만 수행되어야 하는 프로세스가 있는 경우 복잡 ⇒ 한 줄이 아니라 각 CPU 별로 줄 세우기

  • 여러 줄로 줄 세우기 하는 경우 CPU 작업이 편중될 수 있어 load balancing(부하균형) 필요

  • 대칭형 다중처리 (symmetric multi-processing) : 각 CPU가 알아서 스케줄링 결정
  • 비대칭형 다중처리 (asymmetric multiprogramming) : 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지는 거기에 따라 움직임

8. 실시간 스케줄링

  • 실시간 시스템 (real-time system)에서는 각 작업마다 주어진 데드라인이 있음
  • 경성 실시간 시스템 (hard real-time system)
    • 데드라인을 반드시 지켜야 함 (미사일 발사, 원자로 제어 등)
    • 정해진 시간 안에 반드시 작업이 완료되도록 스케줄링
  • 연성 실시간 시스템 (soft real-time system)
    • 데드라인이 존재하기는 하지만, 지키지 못했다고 위험한 상황이 발생하지는 않음 (멀티미디어 스트리밍)
  • 실시간 환경에서의 스케줄링은 빠른 서비스도 중요하지만 데드라인 지키기가 더 중요함
  • EDF (Earlist Deadline First) 스케줄링 : 데드라인이 얼마 남지 않은 요청 먼저 처리

5. 스케줄링 알고리즘 평가

  1. 큐잉 모델 (queueing model)
    • 주로 이론가들이 수행하는 방식
    • 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 주면 CPU의 처리량, 프로세스의 평균 대기시간 등을 구함
  2. 시뮬레이션 (simulation)
    • 실제 시스템이 아니라 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떤 결과 나오는지 확인하는 방법
    • 실제 시스템에서 추출한 입력값을 트레이스(trace) 함
    • 트레이스 : 몇 초에 어떤 프로세스가 도착하고 각각 cpu 버스트 시간을 얼마나 하는지에 대한 정보를 시간 순서대로 적어놓는다.
  3. 구현 및 실측 (implementation & measurement)
    • 이론가와 정반대인 구현가들이 수행하는 방식
    • 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜보고 실행시간 측정하여 알고리즘 성능평가

Leave a comment

You may also enjoy