[정보처리기사]4.프로그래밍 언어 활용/SW 운영체제의 활용/프로세스 스케줄링

프로세스 스케줄링

1. 프로세스 스케줄링(Scheduling)

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

1. 장기 스케줄링(작업, 상위 스케줄링) 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업 → 작업 스케줄러에 의해 수행됨

1. 중기 스케줄링 어떤 프로세스들이 CPU를 할당받을 것인지 결정하는 작업
2. 단기 스케줄링(프로세서,하위 스케줄링) 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업

→ 프로세서 스케줄링 및 '문맥 교환'은 프로세서 스케줄러에 의해 수행됨

문맥 교환(Context Switching): 하나의 프로세스에서 다른 프로세스로 CPU가 할당되는 과정에서 발생되는 것

• 다중 프로그래밍 시스템에서 OS에 의해 cPU가 할당되는 프로세스 변경하기 위함, 현재 CPU 사용하여 실행되고 있는 프로세스의 상태 정보 저장, 제어 권한을 ISR에게 넘기는 작업

 

1.1 스케줄링 목적

- 공정성: 모든 프로세스에 공정하게 할당

- 처리량 증가: 단위 시간당 프로세스 처리량 증가

- CPU 이용률 증가: CPU 낭비 시간 줄이고, 사용되는 시간 비율 증가

- 우선순위 제도: 우선순위가 높은 프로세스 먼저 실행

- 오버헤드 최소화

- 응답 시간(Response Time, 반응 시간) 최소화: 작업 지시 및 반응 시작 시간 최소화

- 반환 시간(Turn Around Time) 최소화: 제출한 시간부터 실행 완료 시간 최소화

- 대기 시간 최소화: 준비상태 큐에서 대기하는 시간 최소화

- 균형 있는 자원의 사용: 메모리, 입, 출력장치 등의 자원을 균형 있게 사용

- 무한 연기 회피: 자원을 사용하기 위해 무한정 연기되는 상태 회피

→ CPU이용률, 처리율, 반환 시간, 대기 시간, 응답 시간 , 공평성 유지 (오류 복구 아님)

 

1.2 프로세스 스케줄링의 기법 

스케줄링 기법	종류
선점(Preemptive) 스케줄링	Round Robin SRT(Shortest Remaining Time) MLQ(Multi-Level Queue) MFQ(다단계 피드백 큐), 선점 우선순위
비선점(Non-Preemptive) 스케줄링	우선순위(Priority) 기한부(Deadline) FCFS(FIFO) SJF(Shortest Job First) HRN(Highest Response-ratio Next)

(1) 선점(Preemptive) 스케줄링

- 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 선점할 수 있는 기법

- 빠른 응답 시간을 요구하는 대화식 시분할 시스템(Time Sharing System)에 사용됨

- 많은 오버헤드 발생

- 선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록 필요

(a) SRT(Shortest Remaining Time)

- SJF 기법을 선점 형태로 변경한 기법

- 현재 실행 중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에 CPU를 할당하는 기법, 시분할 시스템에 유용

- 준비상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가

​

(b) RR(Round Robin)

- 시분할 시스템을 위해 고안된 방식, FCFS 알고리즘을 선점 형태로 변형한 기법.

- FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 시간 할당량 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치

- 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 적을 경우 문맥 교환 및 오버헤드가 자주 발생되어 요청된 작업을 신속히 처리할 수 없음

- 할당되는 시간의 크기가 작으면 작은 프로세스들에게 유리

예. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, 평균 대기 시간, 평균 반환 시간을 구하시오. 타임 슬라이스(할당 시간)=4초

Process	P1	P2	P3
실행시간	20	4	6

* 주어진 시간 할당량 동안 실행되지 못할 경우 준비상태 큐의 가장 마지막으로 재배치하여 차례를 기다림

반환 시간 : 각 프로세스가 완료되는 시간을 이용하여 구함
대기 시간 : 대기 시간을 구하고자 하는 프로세스의 가장 마지막 실행이 시작되기 전까지의 진행 시간을 이용하여 구하되, 해당 프로세스가 앞에서 실행되었을 경우 실행된 시간은 제외

풀이.

* 평균 반환 시간 : (30+8+18)/3 = 18.6

* 평균 대기 시간 : (10+4+12)/3 = 8.6

>> P1의 대기 시간 =반환 시간 전까지의 진행 시간 - 진행시간 동안 해당 프로세스의 실행시간) = 26-16=10

평균 반환 시간 : (26+8+17)/3 = 17

~4초	~8	~12	~16	~18	~22	~26	~30
P1 16	P2 0	P3 2	P1 12	P3 0	P1 8	P1 4	P1 0

P2 8초, P3 18초, P1 30초에 프로세스 완료

(c) 다단계 큐(MQ; Multi-level Queue)

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

- FCFS(FIFO) + RR 스케줄링 기법을 혼합한 것

- 상위 단계에서 완료되지 못한 작업은 하위 단계로 전단되며 마지막 단계에서는 RR 스케줄링 기법을 사용

- 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로레스 등으로 나누어 준비 상태 큐를 상위, 중위, 하위 단계로 배치함

- 각 준비상태 큐는 독자적인 스케줄링을 가지고 있으므로 각 그룹의 특성에 따라 서로 다른 스케줄링 기법을 사용할 수 있음

- 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없음

- 하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당해야 함

 

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

- 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 선점할 수 없는 기법

- CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU 사용

- 모든 프로세스에 대한 요구를 공정하게 처리 가능

- 프로세스 응답 시간의 예측 용이

- 일괄 처리 방식에 적합

-  가뭄 현상: 중요한 작업(짧은 작업)이 중요하지 않은 작업(긴 작업)을 기다리는 경우 발

(a) FCFS(FIFO): 준비 상태 큐에 도착 순서

- 반환 시간 = 대기시간 실행시간 

- 최소 평균 반환 시간 계산 : {P1 +(P1+P2) +(P1+P2+P3) } / 3    *P1 <P2 <P3

- 최대 평균 반환 시간 계산 : {P3 +(P3+P2) +(P3+P2+P1) } / 3    *P1 <P2 <P3

(b) SJF( 실행시간 추정치 가장 짧은 프로세스)  : 도착시간에 따른 작업 완료 시간

(c) HRN(Highest Response-ratio Next) 20년 1, 2, 3회 기출문제

- SJF 기법의 가뭄 현상을 보완하기 위한 방식

- 대기 시간이 긴 프로세스일 경우 우선순위가 높아지기 때문에(우선순위 계산식의 수치가 가장 높은 것부터 낮은 순으로 우선순위를 부여) 긴 작업과 짧은 작업 간의 지나친 불평등을 해소함

→ HRN 우선순위 계산식: (대기시간 + 서비스 시간) / 서비스시간 (내림차순)

​*기한부 제한된 시간 내에 완료

Aging 프로세스가 자원을 기다리는 시간에 비례하여 우선순위를 부여함으로써 무기한 연기 문제 방지

예. 비선점 기법에 따른 평균 실행시간, 평균 대기시간, 평균 반환시간 계산, HRN은 우선순위

Process	P1	P2	P3
실행시간	20	4	6
대기시간	10	20	10

풀이

	평균 실행 시간	평균 대기 시간	평균 반환 시간
FCFS	(20+4+6)/3=10	(6+20+24)/3=14.6	(20+24+30)/3=24.6
SJF	(4+6+20)/3=10	(0+4+10)/3=4.6	(4+10+30)/3=14.6

HRN

P1:(20+10)/20=1.5s

P2:(4+20)/4=6s

P3:(6+10)/6=2.6s

-> 우선순위  순서: P2, P3, P1

 

 

 [정보처리기사] 개정된 정보처리기사 필기 목차

[정보처리기사] 개정된 정보처리기사 필기 목차