Scheduling Algorithm

프로세스의 스케쥴링

CPU는 하나인데, 동시에 여러 프로세스가 실행되어야한다. CPU는 여러개의 프로세스를 번갈아가면서 실행하는데 매우 고속이기 때문에 우리 눈에는 동시에 실행되는 것처럼 보인다. 이러한 멀티프로세스 운영체제에서 프로세스의 CPU 할당 순서 및 방법을 결정짓는 것을 '스케줄링'이라 한다.

• 배치처리시스템, 시분할 시스템, 멀티태스킹과 같은 방식으로 여러가지 응용프로그램을 시간순서에 따라 cpu에 배치하는 방법

  

• 누가 프로세스 실행을 관리할까? 스케쥴러

• 스케쥴링 알고리즘이란?
  어느 순서대로 프로세스를 실행시킬까?
  - 시분할 시스템 : 예) 프로세스 응답시간을 가능한 짧게
  - 멀티프로그래밍: 예) CPU활용도를 최대로 높혀서, 프로세스를 빨리 실행

스케쥴러 종류

FIFO(FCFS) 스케쥴러

• 프로세스가 저장매체를 읽는다든지, 프린팅을 한다든지 하는 작업 없이 쭉 cpu를 처음부터 끝까지 사용한다는 가정하에.
• 가장 간단한 스케쥴러(배치 처리 시스템)
• 요청이 먼저 들어온 순서대로 실행
• First Come First Served

최단 작업 우선(SJF) 스케쥴러

• Shortest Job First
• 가장 프로세스 실행시간이 짧은 프로세스부터 먼저 실행을 시키는 알고리즘

우선 순위 기반 스케쥴러

• 프로세스에 우선순위를 매겨 프로세스에 먼저 실행시킨다는 뜻.
• 우선순위는 정의하기 나름
• Priority-Based 스케쥴러
  • 정적 우선순위 : 프로세스마다 우선순위를 미리 지정
  • 동적 우선순위 : 스케쥴러가 상황에 따라 우선순위를 동적으로 변경

Round Robin 스케쥴러

• 시분할 시스템 기반

프로세스 상태와 스케쥴러

멀티 프로그래밍과 Wait

• 멀티프로그래밍 : CPU 활용도를 극대화하는 스케쥴링 알고리즘
• Wait : 간단히 저장매체로부터 파일 읽기를 기다리는 시간으로 가정

프로세스 상태

• 스케쥴러가 프로세스 상태를 알아야 작업순서를 결정할 수 있음.

• CPU 활용 극대화

  

• 기본적인 스케쥴링 알고리즘에서 상태를 정의해놓음

  • ready 실행 가능 : 지금 CPU에 넣으면 CPU에서 바로 실행 가능한 상태
  • running 실행 중 : 현재 CPU에서 실행하고 있는 상태
    • 만약 싱글 코어 프로세서, 싱글 코어 CPU라면 어느 시점이던간에 최대 1개 이하일 것이다.
  • blocked 대기 : wait상태, 특정 이벤트 발생 대기 상태( 예: 프린팅이 다 되었다!)

프로세스 상태기반 스케쥴링 알고리즘

위와 같이 각각의 시점에 ready상태인 프로세스가 여러개일 때 어떤 것을 선택해야 하는지에 대한 의문점이 생긴다.

Queue

• 가장 먼저 들어온 프로세스가 먼저 실행되는 것
• 우선순위를 어떻게 정하느냐에 따라 달라질 수 있음.

ex) 위 그림에서 프로세스가 1,2,3 기준으로 들어왔을 때 아래와 같이 cpu에서 실행됨.

• Ready State Queue
• Running State Queue
• Block State Queue

※ CPU가 아무것도 실행하지 않는 상태 → idle 상태

선점형, 비선점형 스케쥴러

• 선점형 스케쥴러 (Preemptive Scheduling)
  • 하나의 프로세스가 다른 프로세스 대신에 프로세서(CPU)를 차지할 수 있음
  • 스케쥴러가 지금 CPU에 있는 프로세스를 선점해서 제어하는 형태
  • 시분할 시스템
  • 프로세스의 실행시간이 길더라도 특정시간에 교체해주기 때문에 응답시간이 짧아질 수 있음
• 비선점형 스케쥴러 (Non-Preemptive Scheduling)
  • 하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 차지할 수 없음
  • CPU에 있는 프로세스가 자체적으로 끝나거나 block되었을 때, 다른 프로세스로 교체 가능한 형태
  • 배치 처리 시스템
  • 기다리고 있는 프로세스의 응답시간이 길어질 수 있음
• 스케쥴러 구분(정책, policy)
  • 비선점형 스케쥴링에 가까운 스케쥴러
    • FIFO(FCFS), SJF, Priority-based는 어떤 프로세스를 먼저 실행시킬지에 대한 알고리즘
  • 선점형 스케쥴링
    • RoundRobin은 시분할 시스템을 위한 기본 알고리즘

스케쥴링 알고리즘 조합

예를 들면 ready state는 FIFO로, running state는 roundrobin 알고리즘으로 한다던가, 다양하게 알고리즘을 조합하여 사용할 수 있다.

ex)