[정보처리기사] Process Scheduling

프로세스 스케줄링

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

프로세스 스케줄링의 목적

• CPU나 자원을 효율적으로 사용하기 위한 정책
• 처리율, CPU 이용률 증가
• 오버헤드, 응답시간, 반환시간, 대기시간 최소화
• 공정성(균형 있는 자원의 사용)
• 무한 연기 회피

비선점 / 선점 구분

의미

• 비선점 : CPU가 한 번 할당되면 다른 프로세스는 점유 불가
• 선점 : CPU를 차지하는 프로세스가 있어도 다른 프로세스가 빼앗아 사용 가능

장점

• 비선점
  • 프로세스 응답시간 예측 용이
  • 일괄 처리 방식에 적합
• 선점
  • 우선순위가 높은 프로세스를 빠르게 처리
  • 빠른 응답시간을 요하는 대화식 시분할 시스템에서 사용

단점

• 비선점 : 중요하지 않은 작업 때문에 중요한 작업이 기다리는 경우 발생 가능
• 선점 : 많은 오버헤드를 초래
  • 오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 처리시간 / 메모리

비선점 스케줄링

FCFS

• First Come First Service
• FIFO라고도 불린다.
• 준비상태 큐에 도착한 순서에 따라 차례로 CPU 할당
• 장점 : 공평성 유지
• 단점 : 중요하지 않은 작업을 기다리는 경우 발생

확장

• FCFS : 빨리 온 애들부터 순서대로 하자!
• SJF : 빨리 처리할 수 있는 애들부터 하자!
• HRN : 우선순위가 높은 애들부터 하자!

SJF

• Shortest Job First
• 실행시간이 가장 짧은 프로세스부터 CPU 할당
• 가장 적은 평균 대기시간
• 실행시간이 긴 프로세스에 불리!

HRN

• Hightest Response-ratio Next
• SJF의 단점을 보완하기 위한 기법
• 대기시간과 실행시간로 계산된 우선순위 이용
• 대기시간이 긴 프로세스일 경우 우선순위 결과값이 높다.

HRN 우선순위 계산

\[\frac{대기시간 + 서비스 시간}{서비스 시간}\]

선점 스케줄링

RR

• Round Robin
• 시분할 시스템을 위해 고안
• FCFS의 선점형태 변형

FCFS와의 비교

• 공통점 : 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU 할당
• FCFS : 뒤에 뭐가 오든 일단 들어온 것부터 끝내자.
• RR : 할당된 시간만 실행, 완료되지 않으면 다음 프로세스에 CPU 넘기고 다시 줄 서!
• 할당 시간 大 : FCFS와 다를 바가 없다.
• 할당 시간 小 : 오버헤드 자주 발생

SRT

• Shortest Remaining Time
• SJF의 선점형태 변형

SJF와의 비교

• 공통점 : 실행시간을 비교해서 가장 짧은 프로세스부터 처리
• SJF : 일단 하던 건 끝내고 이후에 가장 짧은 프로세스를 건드리자!
• SRT : 하던 건 알 바 아님. 새로운 들어온 프로세스가 더 빨리 끝나면 뺏어감. Ex. 30초 짜리 프로세스 처리해서 10초 남았는데 3초짜리 프로세스 들어오면 3초짜리부터 처리

MLQ

• 다단계 큐 스케줄링(Multi Level Queue)

동작 방식

1. 우선순위마다 준비상태 큐 형성
2. 가장 높은 우선순위 큐의 프로세스에 CPU 할당
3. 우선순위가 낮은 큐에서 작업 실행 중에도 상위 단계 큐에 프로세스 도착 시 CPU 뺏어감

특징

• 각 Queue는 RR, CSRF 등 독자적 스케줄링 가능
• Queue들 간의 프로세스 이동 불가 : 스케줄링 부담은 적지만 유연성이 떨어짐
• 우선순위가 낮은 프로세스는 기아현상 발생 가능
• 기아현상(Starvation) : 오랫동안 CPU 할당을 기다리는 것

MFQ

• 다단계 피드백 큐 스케줄링(MultiLevel Feedback Queue)
• 다단계 큐 + 동적인 프로세스 우선 순위 변화 적용

동작 방식

1. 프로세스 생성 시 가장 높은 우선 순위 준비 큐에 등록
2. 등록된 프로세스는 FCFS 순서로 CPU를 할당받아 실행
3. 해당 큐의 CPU 할당량(Time Quantum)이 끝나면 하위 준비상태 큐에 등록

특징

• 큐 사이의 프로세스 이동 가능
• 가장 하위 큐는 FCFS 스케줄링
• Aging 기법으로 기아현상 예방
• Aging 기법 : 최하위 큐에서 너무 오래 대기 시 다시 상위 큐로 이동

MLQ와 MFQ의 비교

차이점

• MLQ
  • 프로세스마다 우선순위 확정
  • 프로세스가 Queue마다 이동 불가
• MFQ
  • 프로세스의 우선순위가 CPU 할당량에 따라 변경
  • 프로세스가 Queue마다 이동 가능

장단점

• MLQ
  • 장점 : 단순 → 스케줄링 부담 X
  • 단점 : 낮은 유연성
• MFQ
  • 단점 : 복잡 → 스케줄링 부담 O
  • 장점 : 높은 유연성

특징

• MLQ : 하위 단계 큐에서 기아현상 발생 가능
• MFQ : Aging 기법을 이용한 기아 현상 예방

스터디 발표 화면

참고자료

• [정보처리기사] 프로세스 선점/비선점 스케줄링 기법

• [2020 정보처리기사 실기] 필수 암기 용어 정리 ★★