운영체제-프로세스 스케줄링
프로세스 스케줄링
여러 가지 작업의 처리순서를 결정하는 것
예: 프로세스 스케줄링, 디스크 스케줄링 등
스케줄링 기본 목표
공정성- 모든 프로세스가 적정 수준에서 cpu 작업을 할 수 있게 함
균형-시스템 자원이 충분히 활용될 수 있게 함
일괄처리 운영체제
-처리량의 극대화
-반환시간의 최소화
-CPU활용의 극대화
시분할 운영체제
-빠른 응답시간
-과다한 대기시간 방지
실시간 운영체제
-처리기한 맞춤
스케줄링 단계
하위단계 스케줄링
준비 큐에 있는 프로세스를 선택하여 사용 가능한 cpu를 할당(디스패치) 하는 역할
수행 주체: 디스패처
스케줄링 정책 = 스케줄링의 목표에 따라 우선적으로 고려해야할 기본적인 정책
-선점 스케줄링 정책
실행 중인 프로세스에 인터럽트를 걸고 다른 프로세스에 cpu를 할당할 수 있는 스케줄링 방식
높은 우선순위의 프로세스를 우선 처리해야 하는 경우에 유용 (실시간 시스템, 시분할 시스템)
문맥 교환에 따른 오버헤드 발생 (문맥-context란 cpu의 모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스의 상태를 말함)
문맥 교환(context switching) = cpu가 현재 실행하고 있는 프로세스의 문맥을 pcb에 저장하고 다른 프로세스의 pcb로부터 문맥을 복원하는 작업
-비선점 스케줄링 정책
실행 중인 프로세스를 바로 준비상태로 전이시킬 수 없는 스케줄링 방식
cpu를 할당받아 실행이 시작된 프로세스는 대기상태나 종료상태로 전이될 때까지 계속 실행상태에 있게 됨
강제적인 문맥 교환이 없어 오버헤드가 발생하지 않음
긴 프로세스가 실행 중이라면 짧은 프로세스가 오래 기다리게 되는 경우 발생
스케줄링의 평가 기준
평균대기시간
-각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균 값
평균반환시간
-각 프로세스가 생성된 시점부터 수행이 완료된 시점까지의 소요시간의 평균 값
스케줄링 알고리즘의 종류
FCFS(First-come First-served)
비선점 방식
준비 큐에 도착한 순서에 따라 디스패치
장점
-가장 간단한 스케줄링 기법
단점
-짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수도 있음
*시분할 운영체제나 실시간 운영체제에는 부적합
-프로세스들의 도착순서에 따라 평균반환시간이 크게 변함
SJF 스케줄링 (Shortest Job first)
비선점 방식
준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치
장점
-일괄처리 환경에서 구현이 쉬움
단점
-실제로는 먼저 처리할 프로세스의 CPU 시간을 예상할 수 없음
새로 들어온 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수도 있음
(시분할 운영체제나 실시간 운영체제에는 부적합)
SRT 스케줄링 (Shortest Remaining Time)
SJF 알고리즘의 선점 방식
준비큐에서 기다리는 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치
장점
-SJF보다 평균대기시간이나 평균반환시간에서 효율적임
단점
-실제로는 프로세스의 CPU 시간을 예상할 수 없음
-각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환 등
SJF보다 오버헤드가 큼
RR 스케줄링 (Round Robin)
선점 방식
준비 큐에서 도착한 순소대로 디스패치하지만, 정해진 시간 할당량에 의해 실행 제한
시간 할당량 안에 종료하지 못한 프로세스는 준비 큐의 마지막에 배치됨
장점
-CPU를 독점하지 않고 공평하게 이용 (시분할 운영체제에 적합)
단점
-시간 할당량이 너무 크면 FCFS 스케줄링과 동일
-시간 할당량이 너무 작으면 너무 많은 문맥 교환 발생으로 오버헤드가 커짐
HRN (Highest Response Ratio Next)
비선점 방식
준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
장점
-SJF 스케줄링의 단점 (긴 작업과 짧은 작업 사이의 지나친 불평등) 보완
단점
-실제로는 프로세스의 CPU 시간을 예상할 수 없음