[정처산기] 응용SW기초 기술 활용 (스케줄링)

오늘은 응용 SW기초 기술 활용 과목의 스케줄링에 대해 요점정리를 해봤어요.

---

 

스케줄링

 

1. 스케줄링의 개요

• 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미
• 프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거치게 됨

 

2. 프로세서(스) 스케줄링의 기법

비선점(Non-preemptive)	- 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법 - 비선점 스케줄링의 종류에는 FCFS(FIFO), SJF, 우선순위, HRN, 기한부 등의 알고리즘이 있음
선점(preemptive)	- 하나의 프로세스가 CPU를 항당받아 실행하고 있을 때는 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법 - 선점 스케줄링의 종류에는 Round Robin, SRT, 선점 우선순위, 다단계 큐(MQ), 다단계 피드백 큐(MFQ) 등의 알고리즘이 있음

 

 

3. 주요 스케줄링 기법

 

1) FCFS(First Come First Service, 선입 선출) = FIFO(First In First Out)
FCFS는 준비상태 큐(대기 큐, 준비 완료 리스트, 작업준비 큐, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 항당하는 기법으로 가장 간단한 알고리즘

 

[ 예제 ]

다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, FCFS 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오.(제출 시간은 없으며 시간의 단위는 초)

출처 : 2024 시나공 정보처리산업기사 필기 기본서

 

* 평균 실행 시간 : 각 프로세스 실행 시간의 합 / 프로세스 개수 [ (20+4+6) / 3 = 10 ]  
* 평균 대기 시간 : 바로 앞 프로세스까지의 진행 시간(대기한 시간) / 프로세스 개수 [ (0+20+24) / 3 = 14.6 ]
* 평균 반환 시간 : 실행 시간 + 대기 시간 / 프로세스 개수  [ (20 + 24 + 30) / 3 = 24.6 ]

	P1		P2		P3		평균
실행시간	20	+	4	+	6	/ 3 =	10
	+		+		+
대기시간	0	+	20	+	24	/ 3 =	14.6
	+		+		+
반환시간	20	+	24	+	30	/ 3 =	24.6

 

 

2) SJF(Shortest Job First, 단기 작업 우선)
준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법

SJF의 계산법은 FCFS와 동일하나, 우선순위가 프로세스들 중 가장 짧은 프로세스먼저 계산

 

[ 예제 1 ]

다음과 같은 포르세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, SJF 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오 (제출 시간이 없을 경우)

출처 : 2024 시나공 정보처리산업기사 필기 기본서

 

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

 

[ 예제 2 ]

다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, SJF 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오(제출 시간이 있을 경우)
(도착시간이 있을 경우 가정 먼저 도착한 프로세스를 먼저 실행하고, 먼저 실행한 프로세시의 실행 시간이 다음 프로세스의 도착시간 보다 길 경우 실행시간이 짧은 시간으로 계산)

출처 : 2024 시나공 정보처리산업기사 필기 기본서

 

* 평균  실행 시간 : (20 + 4 + 7) / 3 = 10.3
* 평균  대기 시간 : (0 + 20(-2) + 24(-1)) / 3 = 13.6
* 평균  반환 시간 : (20 + 22 + 30) / 3 = 24

 

 

3) HRN(Highest Response-Ratio Next)
실행 시간이 긴 프로세스에 불리한 SJF 기번을 보완하기 위한 것으로 대기 시간과 서비스(실행) 시간을 이용하는 기법
* 우선순위 계산식 : 대기시간 + 서비스(실행) 시간 / 서비스(실행) 시간

 

[ 예제 ]

다음과 같은 프로세스가 HRN 기법으로 스케줄링 될 때 우선순위를 계산하시오.

출처 : 2024 시나공 정보처리산업기사 필기 기본서

 

 

4) RR(Round Robin)
RR(Round Robin)은 시분할 시스템(Time Sharing System)을 위해 고안된 방식으로, FCFS 알고리즘 선점(Preemptive) 형태로 변형한 기법임
- 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생함

 

[ 예제 ]

다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, 평균 대기 시간, 평균 반환 시간을 구하시오(단,Time Slice는 4초)

출처 : 2024 시나공 정보처리산업기사 필기 기본서

 

1. 주어진 시간 할당량(Time Slice) 동안 실행되지 못할 경우 준비상태 큐의 가장 마지막으로 재배치하여 차례를 기다리므로 다음과 같이 표시할 수 있음

출처 : 2024 시나공 정보처리산업기사 필기 기본서

 

2. 반환시간 : 각 프로세스가 완료되는 시간을 이용하여 구한다.

3. 대기시간 : 대기 시간을 구하고자 하는 프로새스의 가장 마지막 실행이 시작되기 전까지의 진행 시간을 이용하여 구하되, 해당 프로세스가 앞에서 여러 번 실행되었을 경우 실행된 시간은 제외한다.

출처 : 2024 시나공 정보처리산업기사 필기 기본서

 

 

 

---

공부하면서 유용했던 부분 메모겸 공유하고자 끄적입니다.

고쳐야하는 부분있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)