운영체제 Ch.3 CPU 스케쥴링

3-1. CPU 스케쥴링 개요

• CPU스케쥴링 : 운영체제가 프로세스들에게 공정하고 합리적으로 CPU자원을 배분하는 것
• 프로세스 우선순위
  • 프로세스마다 우선순위가 다름.
    
    
  • 입출력 집중 프로세스 (I/O bound process)
    • 입출력 작업이 많은 프로세스.
    • 실행 상태보다 입출력을 위한 대기시간이 김. (CPU의 속도보다, 입출력장치의 속도가 느린 경우가 대부분이기 때문)
      
      
  • CPU 집중 프로세스 (CPU bound porcess) CPU 작업이 많은 프로세스
  • 운영체제는 각 프로세스에 PCB에 우선순위를 기록함.
    
    
• 스케쥴링 큐(Scheduling queue)
  • CPU가 PCB를 일일히 탐색하는 것은 비효율적이기 때문에, 스케쥴링 큐에 각 프로세스의 목록을 적재.
  • 준비 큐 (ready queue) : CPU를 이용하고싶은 프로세스를 적재하는 큐.
  • 대기 큐 (waiting queue) : 입출력장치를 이용하기 위해 대기상태로 접어든 프로세스를 적재하는 큐.
    
    
  • 선점형 스케쥴링 (preemptive scheduling)
    • 다른 프로세스가 CPU와 같은 자원을 할당받아 사용하더라도, 운영체제가 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케쥴링 방식.
    • 현재 대부분의 운영체제 차용 방식.
    • 자원의 효율적인 배분 가능.
    • 문맥 교환 과정에서 오버헤드 발생 가능성 있음.
      
      
  • 비선점형 스케쥴링 (non-preemptive scheduling)
    • 다른 프로세스가 CPU와 같은 자원을 할당받아 사용하면, 해당 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전에 다른 프로세스가 끼어들 수 없는 스케쥴링 방식.
    • 자원 배분의 비효율성
    • 문맥 교환의 횟수가 적기 때문에, 오버헤드 발생 가능성이 적다.

3-2. CPU 스케쥴링 알고리즘

• 스케쥴링 알고리즘 종류
  • 선입 선처리 스케쥴링 (FCFS Scheduling)
    • 삽입 순서대로 처리하는 비선점형 스케쥴링 방식
      
      
    • 호위 효과 (convoy effect)
      • CPU를 오래 사용하는 프로세스가 먼저 도착시, 나머지 프로세스의 대기시간이 길어지는 효과.
        
        
  • 최단 작업 우선 스케쥴링 (ShortTest Job First Scheduling)
    • 큐에 삽입된 프로세스 중, CPU이용시간의 길이가 가장 짧은 프로세스부터 실행하는 스케쥴링 방식.
    • 기본적으로 비선점형 스케쥴링 알고리즘이나, 선점형으로 구현될 수도 있음.
      
      
  • 라운드 로빈 스케쥴링 (round robin scheduling)
    • 선입 선처리 스케쥴링 + 타임 슬라이스.
    • 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간.
    • 타임 슬라이스의 크기가 매우 중요. (너무 크면 FCFS 스케쥴링과 다를게 없어 호위효과 발생, 너무 작으면 프로세스 전환이 너무 잦아 비효율적.)
      
      
  • 최소 잔여 시간 우선 스케쥴링 (Shortest Remaining Time Scheduling)
    • 최단 작업 우선 스케쥴링 + 라운드 로빈 알고리즘
    • 잔여 작업 시간이 가장 짧은 프로세스를 우선으로 실행, 한번에 타임 슬라이스 만큼만 실행.
      
      
  • 우선순위 스케쥴링 (priority scheduling)
    • 프로세스에 부여한 우선순위대로 실행하는 스케쥴링.
    • ~ 우선 스케쥴링은 광의의 우선순위 스케쥴링. (우선순위 기준만 다름)
    • 기아 현상
      • 우선순위가 높은 프로세스가 계속해서 실행되면서, 우선순위가 낮은 프로세스들의 실행이 계속해서 연기되는 현상.
        
        
  • 다단계 큐 스케쥴링 (multilelvel queue scheduling)
    • 우선순위별로 준비 큐를 여러 개 사용하는 스케쥴링 방식.
    • 큐별로 설정을 다르게 할 수 있음.
      
      
  • 다단계 피드백 큐 스케쥴링
    • 다단계 큐 스케쥴링에서, 프로세스들이 큐 사이를 이동할 수 있는 스케쥴링 방식.
    • 실행 후 완료되지 않은 프로세스는, 다음순위의 큐로 옮겨가면서 점점 우선순위가 낮아진다.
    • 구현이 복잡하나, 가장 일반적인 CPU 스케쥴링 알고리즘.

 

참고 : 혼자 공부하는 컴퓨터구조 + 운영체제 (강민철 저)