스케줄링(Scheduling)

스케줄링(Scheduling)이란?

스케줄링이란 CPU 등의 자원을 프로세스들에게 적절히 부여하는 다중 프로그래밍을 가능케하는 운영체제의 동작기법이다. 시스템 자원의 적절한 배분을 통해 시스템의 성능을 개선할 수 있다.

스케줄링의 목적

- 작업 처리량 극대화

- 응답 시간과 자원 활용 간의 조화

- 프로세스 교착상태 배제

- 시스템의 과부하 방지

스케줄링의 성능 기준

- CPU 활용률

- 처리율

- 반환 시간

- 대기 시간

- 응답 시간

선점 / 비선점 스케줄링

선점 스케줄링이란 인터럽트와 같이 현 프로세스보다 더 높은 우선순위 프로세스가 발생되었음을 알았을 때, 실행중인 프로세스로부터 강제로 CPU를 회수하는 것을 말한다. 이와 반대로 비선점 스케줄링은 자원을 한번 점유하게 되면 스스로 반납하기 전까지 계속 해당 자원을 사용하도록 허용하는 것을 말한다. 

CPU 스케줄링 기법

FCFS(First-Come First-Served)

준비 리스트에 먼저 도착한 순서대로 CPU를 할당하는 비선점 방식

RR(Round Robin)

FCFS 기법으로 처리하되, 프로세스마다 동일한 CPU 시간제약을 설정하는 선점 방식. 시간제약 내에 처리를 완료하지 못하면 운영체제의 Clock 인터럽트에 의해 '할당시간 종료(Timeout)' 상태전이가 일어나 준비 리스트의 맨 뒤로 이동한다.

SJF(Shortest Job First)

준비 리스트에서 대기하고 있는 프로세스 중 예상 실행 시간이 가장 짧은 것을 우선 처리하는 비선점 방식을 말한다.

SRT(Shortest Remaining Time)

준비 리스트에서 대기하고 있는 프로세스 중 잔여 실행 시간이 가장 짧은 것을 우선 처리하는 선점 방식을 말한다. SJF방식과의 차이점은 우선처리 기준이 '잔여 실행시간' 이라는 점과 '선점방식'이라는 점이다. 즉, 준비 리스트에 도착한 시간차이까지 계산을 해서 프로세스가 실행중이라고 하더라도 가장 먼저 처리가 끝날 수 있는 프로세스의 우선순위가 높아 먼저 처리하게된다. 간단하게 SJF 방식을 선점형으로 바꾼 방식이라고 하면 이해가 편할듯 하다.

HRN

실행 시간이 짧은 작업을 우선 처리하기 때문에 긴 작업의 대기시간이 길어졌던 SJF의 단점을 보완한 비선점 방식이며, 우선순위를 계산하여 처리하게된다. 우선순위는 다음과 같은 공식에 의해 정해진다.

(wait_Time + service_Time) / service_Time

우선순위

프로세스마다 부여된 우선순위를 통해 처리 순서를 판단하는 비선점 방식

MLQ(Multi-Level Queue)

작업의 중요도에 따라 3개의 큐를 구성하여 중요 작업부터 각 큐에 해당하는 스케줄링 방식으로 처리 선점형 방식이다.

상 : 시스템 프로세스

중 : 대화형 프로세스

하 : 일괄처리 프로세스

MFQ(Multi-level Feedback Queue)

작업의 중요도에 따라 3개의 큐를 구성하고, 각 큐별로 시간제약을 다르게 설정한 후 Clock 인터럽트 발생시 한단계 아래 준비 리스트로 내려가 처리를 대기하는 선점 방식. 즉, 시간내에 작업을 완료하지 못하면 '상' 프로세스는 '중' 준비 리스트에 붙고, '중' 프로세스였다면 '하' 준비 리스트에 붙게되는 방식이다.