11-1 CPU 스케줄링 개요

CPU 스케줄링(CPU scheduling): 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것

프로세스 우선 순위

프로세스의 CPU 사용을 우선순위에 맞추어 처리

입출력 집중 프로세스(I/O bound process)

  • **입출력 작업(입출력 버스트, I/O burst)**이 많은 프로세스
  • 실행 상태보다는 입출력을 위한 대기 상태에 많이 머무름

CPU 집중 프로세스(CPU bound process)

  • **CPU 작업(CPU 버스트, CPU burst)**이 많은 프로세스
  • 대기 상태보다는 실행 상태에 더 많이 머무름

입출력 집중 프로세스 먼저, CPU 집중 프로세스를 그 다음

  • 어차피 입출력 집중 프로세스는 입출력 작업 완료 전까지 대기 상태임
  • 대기동안 CPU 집중 프로세스가 CPU를 독점적으로 사용

우선순위(priority)

  • 프로세스의 중요도에 맞게 프로세스마다 운영체제가 부여한 중요도
  • 각 프로세스의 PCB에 적힘

스케줄링 큐

운영체제가 모든 프로세스의 우선순위를 검사하는 것은 비효율적

스케줄링 큐(scheduling queue)

  • 프로세스들이 서는 줄
  • FIFO 일 필요는 없음
  • 준비 큐(ready queue)
    • CPU를 이용하고 싶은 프로세스들이 서는 줄
    • 준비 상태의 프로세스는 준비 큐 마지막에 삽입
    • 운영체제는 준비 큐에서 하나씩 꺼내어 실행
  • 대기 큐(wating queue)
    • 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄
    • 하드 디스크 대기 큐, 프린터 대기 큐, …
    • 대기 상태의 프로세스는 대기 큐 마지막에 삽입
    • 입출력이 완료된 프로세스는 준비 상태로 변경한 뒤 대기 큐에서 삭제되고 준비 큐로 이동
  • 우선순위에 따라 순서가 바뀔 수 있음

선점형과 비선점형 스케줄링

다른 프로세스가 현재 CPU를 사용중인 프로세스 대신 CPU 사용을 요구할 때의 차이

선점형 스케줄링(preemptive scheduling)

  • 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있음
  • 독점을 막고 모든 프로세스가 골고루 자원을 분배
  • 문맥 교환 과정에서 오버헤드 발생

비선점형 스케줄링(non-preemptive scheduling)

  • 자원을 사용하는 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없음
  • 따라서 기다려야함
  • 문맥 교환 과정이 선점형 스케줄링보다 적음
  • 모든 프로세스가 골고루 자원을 사용할 수 없음

11-2 CPU 스케줄링 알고리즘

스케줄링 알고리즘의 종류

선입 선처리 스케줄링(First Come First Served Scheduling)

  • 준비 큐에 들어온 순서대로 처리
  • 호위 효과(convoy effect): 처리 기간이 짧은 프로세스가 실제 처리 기간보다 훨씬 더 긴 시간을 기다려야 함
  • 비선점형 스케줄링 알고리즘

최단 작업 우선 스케줄링(Shortest Job First Scheduling)

  • CPU 이용 시간의 길이가 짧은 프로세스부터 실행
  • 비선점형 스케줄링 알고리즘

라운드 로빈 스케줄링(round robin scheduling)

  • 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
    • 너무 크면 FCFS와 동일해져 호위 효과 발생
    • 너무 작으면 문맥 교환 비용이 커짐
  • 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용
  • CPU 이용 후 프로세스가 완료되지 않으면 준비 큐의 맨 뒤로 삽입

최소 잔여 시간 우선 스케줄링(Shortest Remaining Time)

  • SJFS + 라운드 로빈 스케줄링을 합친 방식
  • 타임 슬라이스만큼 CPU를 사용하되, 다음 사용 프로세스는 남아있는 작업 시간이 가장 적은 프로세스로 선택

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

  • 프로세스들에 우선순위를 부여하고 우선순위 순서대로 처리
    • 우선순위가 같으면 FCFS로 처리
  • 기아(starvation) 현상: 우선순위가 낮은 프로세스가 계속해서 연기되는 것
  • 에이징(aging): 오랫동안 대기한 프로세스의 우선순위를 높여 기아 현상을 방지

다단계 큐 스케줄링(multilevel queue scheduling)

  • 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
  • 프로세스 유형별로 우선순위를 구분하여 실행할 수 있음
  • 큐마다 스케줄링 알고리즘을 다르게 하거나, 타임 슬라이스를 여러 개 지정할 수 있음
  • 기아 현상 발생 가능성 있음

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

  • 프로세스들이 큐 사이를 이동할 수 있음
  • CPU를 이용하지만 추가로 이용이 필요한 프로세스를 낮은 우선순위의 큐로 이동
  • 에이징으로 오래된 프로세스를 높은 우선순위의 큐로 이동
  • 가장 일반적인 CPU 스케줄링