[정보처리기사 실기] 스케줄링(Scheduling)

Scheduling

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

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

 

스케줄링의 종류

• 장기 스케줄링 : 어떤 프로세스에게 시스템 자원을 할당할지 결정 → 준비상태 큐로 보내는 작업
• 중기 스케줄링 : 어떤 프로세스들이 CPU를 할당받을 것인지 결정
• 단기 스케줄링 : 프로세스 실행을 위해 CPU 할당시기, 특정 프로세스 지정

 

스케줄링의 목적

• 공정성 : 모든 프로세스에 공정하게 할당
• 처리율 증가 : 단위 시간당 프로세스를 처리하는 비율 증가
• CPU 이용률 증가 : CPU가 순수하게 프로세스를 실행하는 소요시간 비율 증가
• 우선순위 제도 : 우선순위가 높은 프로세스 먼저 실행
• 오버헤드 최소화 : 오버헤드 최소화
• 응답 시간 최소화 : 작업을 지시하고, 반응하기 시작하는 시간 최소화
• 반환 시간 최소화 : 프로세스를 제출한 시간부터 실행이 완료될 때까지 걸리는 시간을 최소화함
• 대기 시간 최소화 : 프로세스가 준비상태 큐에서 대기하는 시간 최소화
• 균형 있는 자원의 사용 : 메모리, 입·출력 장치 등의 자원을 균형 있게 사용
• 무한 연기 회피 : 자원을 사용하기 위해 무한정 연기되는 상태 회피 가능

 

비선점(Non-Preemptive) 스케줄링

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

• 프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.
• 프로세스 응답 시간 예측 용이
• 일괄 처리 방식에 적합

종류

• FCFS (First Come Frist Service) : 프로세스가 준비상태 큐에 도착한 순서에 따라 CPU 할당. 가장 간단한 알고리즘.
• SJF (Shortest Job First) : 준비상태 큐에서 대기중인 프로세스 중 실행시간이 가장 짧은 프로세스가 종료 시까지 자원 점유. 가장 적은 평균 대기시간을 제공하는 최적 알고리즘. 기아 현상 발생
• 우선순위 (Priority) : 프로세스별 우선순위가 주어지고, 우선순위에 따라 CPU 할당
• HRN (Highest Response-ratio Next) : 현재 응답률이 가장 높은 것을 선택 → 우선순위 계산식 = ( 대기시간 + 서비스(실행)시간 ) / 서비스 시간. 기아 현상 최소화 기법
• 기한부 (Deadline) : 작업들이 명시된 시간이나 기한 내에 완료되도록 계획

 

선점(Preemptive) 스케줄링

한 프로세스가 CPU를 할당받아 실행 중일 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법

• 우선순위가 높은 프로세스를 빠르게 처리 가능
• 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용
• 많은 오버헤드(Overhead) 초래 (*오버헤드 : 처리에 드는 간접적 처리시간·메모리)

종류

• 라운드 로빈(Round Robin) : 같은 크기의 CPU 시간 할당
• SRT(Shortest Remaining Time First) : 가장 짧은 시간이 소요되는 프로세스를 먼저 수행하고, 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점됨
• 다단계 큐(Multi Level Queue) : 작업들을 여러 종류 그룹 분할
• 다단계 피드백 큐 : 큐마다 서로 다른 CPU시간 할당량 부여, FIFO와 라운드 로빈 스케줄링 기법을 혼합한 것