CPU 스케줄링

1. 프로세스 우선순위와 스케줄링 큐

• 스케줄링
  • 모든 프로세스(및 스레드)는 실행되기 위해 자원을 필요로 한다. 운영체제가 공정하고 합리적으로 자원을 배분하는 방법
    ==> CPU 스케줄링 (자원 > CPU)
  • 프로세스마다 우선순위가 다르므로 정해진 시간동안 돌아가면서 CPU를 사용하는 것이 가장 좋은 것은 아니다.
  • $ps -el
    • PRI, NI가 낮을수록 높은 우선순위
  • $top
    •  PR, NI가 낮을수록 높은 우선순위
• 우선순위의 차이를 보이는 대표적인 프로세스 유형
  • I/O bound process, CPU bound process
• CPU 스케줄링 알고리즘
  • 프로세스 우선순위를 토대로 CPU 할당 받는 방법
• 스케줄링 큐
  • 자원은 한정되어 있고 실행 중인 프로세스는 여러 개
  • 프로세스들의 요구사항을 일목요연하게 관리하는 방법
• 대표적인 스케줄링 큐
  • 준비 큐(ready queue): CPU 이용을 기다리는 프로세스들의 큐
  • 대기 큐(run queue): 대기 상태 프로세스들의 큐 (입출력 요청)

• 한 프로세스 실행 도중 다른 급한 프로세스가 실행되어야 한다면
  1. 선점형 스케줄링: 현재 실행 중인 프로세스의 자원을 빼앗아 해당 프로세스에게 할당
     • 프로세스에 자원을 고루 할당 가능
     • 문맥 교환 과정의 오버헤드
  2. 비선점형 스케줄링: 현재 실행 중인 프로세스 실행이 끝날 때까지 해당 프로세스 대기
     • 고르지 않은 자원 분배
     • 문맥 교환 과정에서의 오버헤드 적

2. CPU 스케줄링 알고리즘

1. 선입 선처리 스케줄링(FIFO 스케줄링)
   • CPU를 먼저 요청한 프로세스부터 CPU 할당
   • 준비 큐에 삽입된 순서대로 실행되는 비선점형 스케줄링
   • 부작용: 호위 효과 (convoy effect) - 실행 시간이 긴 프로세스로 인해 짧은 실행 시간을 갖고 있는 프로세스가 후에  진행되는 효과
2. 최단 작업 우선 스케줄링(SJF 스케줄링)
   • 준비 큐 프로세스 중 CPU 이용 시간이 짧은 프로세스부터 실행
   • 호위 효과 방지
3. 라운드 로빈 스케줄링(Round Robin 스케줄링)
   • 선입 선처리 스케줄링 + 타임 슬라이스
   • 준비 큐에 삽입된 순서로 실행하되, 타임 슬라이스만큼 실행
   • 선점형 스케줄링
4. 최소 잔여 시간 우선 스케줄링(SRT 스케줄링)
   • 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
   • 작업 시간 짧은 프로세스부터 처리하되, 타임 슬라이스만큼 돌아간다.
5. 우선순위 스케줄링
   • 프로세스마다 우선순위 부여, 우선순위 높은 순으로 스케줄링
   • 최단 작업 우선 스케줄링 - 작업 시간 짧은 순으로 우선순위 부여
   • 최소 잔여 시간 스케줄링 - 남은 시간 짤은 순으로 우선순위 부여
   • 아사(starvation) 현상
     • 모든 우선순위 스케줄링 알고리즘의 근본적인 문제
     • 우선순위 낮은 프로세스의 실행이 계속 연기되는 현상
     • 우선순위 높은 프로세스 실행하느라 우선순위 낮은 프로세스 실행을 못한다.
     • 해결책: aging
     • 대기 시간이 길어지면 점차 우선순위를 높이는 방식
6. 다단계 큐 스케줄링
   • 우선 순위별로 준비 큐를 여러 개 사용하는 스케줄링
   • 프로세스 유형 별로 큐 구분 가능
     e. g.) CPU 바운드, I/O 바운드, 백그라운드, 포그라운드, 실시간 프로세스 ...
   • 큐 별로 다른 스케줄링 알고리즘 적용 가능
     e. g.) 선입 선처리 큐, 라운드 로빈 큐, ...
   • 큐 별로 다른 타임 슬라이스 적용 가능
   • 기본적으로 프로세스는 큐 간의 이동 불가능, 따라서 아사 현상 발생한다.
7. 다단계 피드백 큐 스케줄링
   • 다단계 큐 스케줄링의 아사 현상을 극복하기 위한 방법
   • 프로세스가 큐 간의 이동이 가능하다.
   • 높은 우선순위 큐에 삽입, 실행이 끝나지 않을 경우 낮은 우선순위 큐에 삽입
   • 에이징 적용
   • CPU bound, I/O bound 프로세스 구분 가능

3. 리눅스 스케줄링

• 리눅스 스케줄링 정책
  • 실시간 정책 스케줄링 (우선순위 높음)
    • SCHED_FIFO
    • SCHED_RR
  • 일반 정책 스케줄링 (우선순위 낮음)
    • SCHED_OTHER/SCHED_NORMAL
    • SCHED_BATCH
    • SCEH_IDLE
• CFS (Completely Fair Scheduler)
  - 비실시간 프로세스를 대상으로 하는 스케줄링 방식 (linux kernel 2.6.23~)
  • vruntime (virtual runtime)
    • 프로세스가 그 동안 실행한 시간을 정규화한 정보
    • vruntime이 작은 프로세스를 다음 실행할 프로세스로 삼음
    • vruntime 별 테스크를 고르는 과정에서 RB tree 사용
  • 타임 슬라이스
    • nice 값에 비례해 가중치 할당, 가중치를 바탕으로 타임 슬라이스 할당
  • nice 명령어
    - 사용자 영역에서 설정한 프로세스 우선순위
    • 사용자 영역에서의 값은 20 ~ 19
    • 커널 영역에서의 값은 0 ~ 139
      ==> 실시간 스케줄링되는 프로세스 0 ~ 99
      ==> CFS 프로세스: 100 ~ 139
    • 새 프로세스를 실행할 때 해당 프로세스의 우선순위 부여
      기본적으로 설정된 nice 값은 0
      • $ nice -n [우선순위][program]
      • $ nice -n 19 uptime
  • renice 명령어
    • 이미 실행 중인 프로세스의 우선순위 부여
      • $ renice [우선순위][PID]
      • $ renice +5 1234