Scheduling Algorithm

Nam Eun-Ji·2020년 11월 19일

프로세스의 스케쥴링

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은 시분할 시스템을 위한 기본 알고리즘