CPU 스케줄링 알고리즘

프로세스들에게 자원을 분배하는 방식인 CPU 스케줄링

 

∎  스케줄링  특징

• 공정하고 합리적으로 CPU 자원을 배분하는 것은 컴퓨터 성능과 직결된다.
• 우선순위에 따라 순서를 정해야 한다.
• PCB를 기반으로 결정한다.
• PCB를 일일이 열어보는 것은 비효율적이기 때문에, 프로세스들을 스케줄링 큐에 넣는다.
  ( * 큐를 이용하지만 선입선출 방식은 아니다.)
• 큐에는 준비 큐와 대기 큐가 있다.
  
  • 준비큐 : CPU 사용 원할 때 줄서는 곳
  • 대기큐 : 입출력장치 이용 원할 때 줄서는 곳

 

스케줄링은 인터럽트가 가능한 선점형 스케줄링과 독점되어 인터럽트가 불가능한 비선점형 스케줄링이 있다.(선점형은 오버헤드 발생 가능)

 

 

∎  스케줄링 알고리즘

(아이디어를 공부하자)

 

✔ 선입 선처리 스케줄링(FCFS)

First Come First Served, 먼저 큐에 삽입된 프로세스가 독점하는 비선점 스케줄링, 호위 효과(매우 오래 기다림) 부작용 있음

 

✔ 최단 작업 우선 스케줄링(SJF)

Shortest Job First, 호위 효과를 방지하기 위해 최단 작업을 우선으로 처리하는 방법

 

✔ 라운드 로빈 스케줄링 (Round Robin)

FCFS에 타임을 정해줌. 프로세스마다 타임 슬라이스를 정해 선점형으로 문맥 교환

 

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

(Shortest Job First + Round Robin)
타임에 맞춰 돌아가되, 남은 시간이 짧은 것을 먼저 실행 시킨다.

 

✔ 우선순위 스케줄링

• 우선순위를 부여하고 그 순서대로 처리.
• 우선순위가 같으면 FCFS로 처리
• 우선순위가 낮으면 먼저 큐에 있었음에도 불구하고 순서가 계속 밀리는 기아 현상이 발생하기 때문에, 에이징 기법을 이용하여 오래된 만큼 우선순위를 조금씩 올려주는 방법을 쓴다.
  (*에이징 기법 : 오래되면 우선순위를 올려준다.)

 

 

✔ 다단계 큐 스케줄링 (Multilevel queue)

• 우선순위 별로 큐를 따로 생성하여 종류별로 분리시킨다.
• 큐마다 스케줄링 알고리즘을 달리할 수 있다.
• 큐마다 이동이 불가하기 때문에 기아 현상을 초래할 수 있다.

 

✔ 다단계 피드백 큐 스케줄링

• 다단계 큐 스케줄링의 문제 해결
• 기아 현상을 막기 위해 실행을 시켜도 작업이 계속 끝나지 않는다면 우선순위가 낮은 큐로 점점 밀려난다.
• 너무 밀려있는 프로세스에게 에이징 기법 적용
• CPU 스케줄링 중 일반적으로 사용됨