CPU 스케줄링의 기본

※ 전남대학교 박태준 교수님의 운영체제 강의를 듣고, 정리한 내용입니다.

CPU 스케줄링이 실행되는 4가지 상황

1. 쓰레드가 시스템 호출 끝에 I/O 를 요청하여 블록될 때

   1. 쓰레드를 블록 상태로 만들고 스케줄링
   2. CPU 의 활용률 향상 목적

   

2. 쓰레드가 자발적으로 CPU 를 반환할 때

   1. yield() 시스템 호출 등을 통해 쓰레드가 자발적으로 CPU 반환
   2. 커널은 현재 쓰레드를 준비 리스트에 넣고, 새로운 쓰레드 선택
   3. CPU 의 자발적 양보

3. 쓰레드의 타임 슬라이스가 소진되어 타이머 인터럽트 발생

   1. 균등한 CPU 분배 목적

4. 더 높은 순위의 쓰레드가 요청한 입출력 작업 완료, 인터럽트 발생

   1. 현재 쓰레드 강제 중단 → 준비 리스트에 삽입
   2. 높은 순위의 쓰레드를 깨워 스케줄링
   3. 우선순위를 지키기 위한 목적

Scheduler and Dispatcher

스케줄링과 디스패쳐 관련 코드는 굉장히 중요해서 커널 내 코드 형태로 존재하고, 모두 실행 시간이 짧도록 작성되어 있습니다.

왜냐하면 시간이 오래 걸리면 결국 처리하는데만 시간이 오래걸려 제대로 된 작업을 수행하지 못하기 때문입니다.

( 즉 최적화가 잘되어있어야 함!! )

Scheduling Process

• 쓰레드 A 실행중 타임아웃
• 우선순위에 의한 교체 ( 인터럽트, 시스템 호출 처리 )
• CPU 스케줄링 ( 교체할 쓰레드 선텍 )
• Dispatcher 진행
  • CPU 레지스터들 ( 원래 진행하던 작업 ) 을 TCB-A 에 저장
  • TCB-B 에 저장된 레지스터들 ( 앞으로 진행할 작업 ) 을 CPU 에 복귀
• 쓰레드 B 실행

선점과 비선점

실행중인 쓰레드를 강제로 중단할 것인지, 그렇지 않을 것인지 CPU 스케줄링 타입을 결정하는 것이 선점과 비선점 입니다.

• 비선점 스케줄링 ( non-preemptive scheduling )
  • 현재 실행중인 쓰레드를 강제로 중단시키지 않음
  • 쓰레드가 CPU 를 할당받아 실행을 시작하면, 실행이 완료되거나 CPU 를 더 이상 사용할 수 없는 상황이 올 때 까지 쓰레드를 강제 중단시키지 않고 스케줄링도 하지 않는 방식
  • 스케줄링 시점
    • CPU 를 더 이상 사용할 수 없게 된 경우 : I/O 로 인한 블록 상태, sleep 등
    • 자발적으로 CPU 를 양보할 때
    • 실행 중 종료할 때
• 선점 스케줄링 ( preemptive scheduling )
  • 현재 실행중인 쓰레드를 강제 중단시키고 다른 쓰레드 선택, CPU 할당
  • 스케줄링 시점
    • 타임슬라이스가 소진되어 타이머 인터럽트가 발생될 때 ( CPU 를 사용할 수 있는 시간을 다 쓴 경우 )
    • 인터럽트나 시스템 호출 종료 시점에서, 더 높은 순위의 쓰레드가 준비 상태일 때
• 오늘 날은 주로 선점 스케줄링 사용

우선순위

일반적으로 우선순위가 높은 프로세스가 CPU 를 먼저, 더 오래 차지하게 됩니다.

프로세스의 우선순위를 배정하는 방식

우선순위 실행 도중 바뀔 수 있는지, 안바뀌는지에 따라 정적 스케줄링 / 동적 스케줄링으로 나뉘어집니다.

• 정적 스케줄링 ( Static Scheduling )
  • 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때 까지 바뀌지 않는 형식
  • 프로세스가 작업하는 동안 우선순위가 변하지 않기 때문에
    • 구현하기 쉬움
    • 시스템의 변화에 대응하기 어려워 작업 효율이 떨어짐
• 동적 스케줄랑 ( Dynamic Scheduling )
  • 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식
  • 프로세스가 작업하는 동안 우선순위가 변하기 때문에
    • 구현하기엔 어려움
    • 시스템의 변화에 대응할 수 있어 시스템의 효율성을 높일 수 있음

Starvation And Aging

쓰레드가 스케줄링 과정에서 선택받지 못한 채 오랫동안 준비 리스트에 있는 상황을 기아 현상이라고 부릅니다.

이 기아 현상을 해결하기 위한 방법을 에이징이라고 부릅니다.

• 기아 ( starvation )

  • 쓰레드가 스케줄링에서 선택되지 못한 채 오랫동안 준비 리스트에 있는 상황
  • 예시
    • 우선순위를 기반으로 하는 시스템에서, 더 높은 순위의 쓰레드가 계속 시스템에 들어오는 경우 ( 계속해서 순위가 뒤로 밀림 → 기아현상 발생 )
    • 짧은 쓰레드를 우선 실행시키는 시스템에서, 자신보다 짧은 쓰레드가 계속 도착하는 경우 ( 계속해서 순위가 뒤로 밀림 → 기아현상 발생 )
  • 스케줄링 알고리즘 설계시 기아 현상이 발생하지 않도록 설계하는 것이 바람직한 설계방법!

• 에이징 ( aging )

  • 기아 현상의 해결책
  • 쓰레드가 준비 리스트에 머무르는 시간에 비례하여 스케줄링 순위를 높이는 방법
  • 오래 기다릴 수는 있지만, 언젠가는 가장 높은 순위에 도달하는 것을 보장해줌

  결국 스케줄링은, 어떤 작업을 어떤 순서로 넣을 것 인지 정하는 방법이라고 볼 수 있습니다.