[정보처리기사] 프로세스 선점/비선점 스케줄링 기법 (FCFS/SJF/HRN/RR/SRT/MLQ/MLFQ)

프로세스 스케줄링이란

프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에 할당하는 작업을 말한다.

 

- 프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거침

- 장기, 중기, 단기 스케줄링이 존재함

 

문맥교환 : 하나의 프로세스에서 다른 프로세스로 CPU가 할당되는 과정에서 발생하는 것으로 운영체제에서 오버헤드의 발생 요인 중 하나

 

 

프로세스 스케줄링의 목적

스케줄링은 CPU나 자원을 효율적으로 사용하기 위한 정책으로 다음과 같은 목적을 가짐

 

- 공정성

- 처리율 증가

- CPU 이용률 증가

- 우선순위 제도

- 오버헤드 최소화

- 응답시간 최소화

- 반환시간 최소화

- 대기시간 최소화

- 균형있는 자원의 사용

- 무한 연기 회피

 

 

프로세스 스케줄링 기법 - 비선점

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.

 

- 프로세스 응답시간 예측이 용이, 일괄 처리 방식에 적합

- 중요하지 않은 작업 때문에 중요한 작업이 기다리는 경우가 발생할 수 있음

- FCFS, SJF, HRM 등

 

FCFS (First Come First Service) 혹은 FIFO

- 준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당

- 공평성은 유지되지만 중요한 작업이 중요하지 않은 작업을 기다리게 되는 경우 발생

 

SJF (Shortest Job First)

- 실행시간이 짧은 프로세스에 먼저 CPU 할당

- 가장 적은 평균 대기시간을 제공함

 

HRN (Higtest Response-ratio Next)

- 실행시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 기법

- 대기시간과 실행시간을 이용함

- 우선순위 계산 결과값이 높은 것부터 우선순위를 부여, 대기시간이 긴 프로세스일 경우 계산 결과값이 높게 나옴

 

HRN 우선순위 계산공식 = (대기시간+서비스(실행)시간)/서비스시간

 

 

프로세스 스케줄링 기법 - 선점

하나의 프로세스가 CPU를 할당받아 사용하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.

 

- 우선순위가 높은 프로세스를 빠르게 처리 가능

- 빠른 응답시간을 요구하는 대화식 시분할 시스템에서 사용

- 많은 오버헤드를 초래

- 선점이 가능할도록 인터럽트용 타이머 클록이 필요

- RR, SRT, MLQ(다단계큐), MLFQ(다단계피드백큐) 등

 

RR (Round Robin)

- FCFS를 선점 형태로 변형한 기법

- 시분할 시스템을 위해 고안됨

- 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받는 것은 FCFS와 동일

- 각 프로세스는 할당된 시간 동안만 실행한 후 실행이 완료되자 않으면 다음 프로세스에 CPU를 넘겨주고 큐의 가장 뒤로 배치됨

- 할당되는 시간이 클 경우 FCFS와 같아지고 작을 경우 문맥교환 및 오버헤드가 자주 발생되게 됨

 

SRT (Shortest Remaining Time)

- SJF 알고리즘을 선점 형태로 변형한 기법

- 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실해 시간을 비교

- 가장 짧은 실행 시간을 요구하는 프로세스에 CPU를 할당함

 

MLQ (Multi Level Queue, 다단계큐)

- 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용

 

MLFQ (Multi Level Feedback Queue, 다단계 피드백큐)

- 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계큐 기법을 이동할 수 있도록 개선한 기법