정보처리기사 필기 ) 비선점 스케줄링

1. FCFS(First Come First Service, 선입 선출)

= FIFO(First In First Out)

- 준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법 ( 가장 간단한 알고리즘 )

- 대기 시간 : 프로세스가 대기한 시간으로, 바로 앞 프로세스까지의 진행 시간으로 계산

- 반환 시간 : 프로세스의 대기 시간과 실행 시간의 합

​

예) FCFS 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오

(제출시간은 없으며 시간의 단위는 초임)

​

1. 프로세스 번호/실행시간

P1/20 P2/4 P3/6

* 평균 실행 시간 : (20+4+6)/3 = 10

* 평균 대기 시간 : (0+20+24)/3 = 14.6

* 평균 반환 시간 : (20+24+30)/3 = 26.6

​

2. 작업번호 / 도착시간/ CPU 사용 시간

JOB1 / 0 / 13

JOB2 / 3 / 35

JOB3 / 8 / 25

* 대기 시간 : 0, 10, 40

* 평균 반환 시간 : (13+45+65)/3 = 41

​

2. SJF(Shortest Job First, 단기 작업 우선)

- 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법 ( 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘 )

- 무한 연기 상태가 발생될 수 있음

​

예) SJF기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오

1. 제출 시간이 없는 경우

프로세스 번호/실행시간

P1/20 P2/4 P3/6

* 평균 실행 시간 : (4+6+20)/3 = 10 >> (P2+P3+P1)/3

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

* 평균 반환 시간 : (4+10+30)/3 = 14.6

​

2. 제출 시간이 있는 경우

프로세스 번호/실행시간/제출시간

P1/20/0 P2/7/1 P3/4/2

* 평균 실행 시간 : (20+4+7)/3 = 10.3

* 평균 대기 시간 : (0+18+23)/3 = 13.6

>> P2 대기 시간 : (P1 실행시간 - P2 도착시간) + P3 실행시간

* 평균 반환 시간 : (20+22+30)/3 = 24

* 제출시간(도착시간)이 제시된 경우 가장 먼저 도착한 것 부터 수행하고

그 이후부터 들어온 작업들의 실행 시간을 확인해서 짧은 순으로 수행

P1의 제출시간은 0이므로 다른 작업과 비교대상이 되지 않고 바로 수행

P1이 수행되는 동안 P2, P3이 들어오면 이 중 실행시간을 파악해서 짧은 것부터 수행될 수 있도록 순서를 정함

그래서 P1 다음 P3 > P2 순으로 진행됨

 

 

3. 작업 2의 종료 시간 ( 오버헤드 무시 )

작업번호 / 도착시간/ 실행 시간

JOB1 / 0 / 6

JOB2 / 1 / 3

JOB3 / 2 / 4

* JOB 1 실행 후 작업 시간이 짧은 JOB2 실행됨 그래서 JOB2의 종료 시간은 9

​

3. HRN(Highest Response-ratio Next)

- SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행) 시간을 이용하는 기법

- 우선순위 계산 공식을 이용하여 서비스(실행) 시간이 짧은 프로세스나 대기 시간이 긴 프로세스에게 우선순위를 주어 CPU를 할당

- 우선순위 계산식 = (대기시간+서비스시간)/서비스시간

​

예) HRN 기법으로 스케줄링될 때 우선순위를 계산하시오.

프로세스 번호/실행시간/대기시간

P1/20/10 P2/4/20 P3/6/10

* 우선순위 계산

P1 : (20+10)/20 = 1.5

P2 : (4+20)/4 = 6

P3 : (6+10)/6 = 2.6

* 우선순위 : P2 -> P3 -> P1

​

작업/대기시간/서비스시간

A/5/5

B/10/6

C/15/7

D/20/8

* A : (5+5)/5 = 2

* B : (10+6)/6 = 2.6

* C : (15+7)/7 = 3.1

* D : (20+8)/8 = 3.5

​

4. 기한부(Deadline)

- 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법

- 프로세스가 제한된 시간 안에 완료되지 않을 경우 제거되거나 처음부터 다시 실행해야 함

​

5. 우선순위(Priority)

- 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

- 우선순위가 동일할 경우 FCFS 기법으로 CPU 할당함

- 가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아상태가 발생할 수 있음.

​

* 에이징(Aging) 기법

- 시스템에서 특정 프로세스의 우선순위가 낮아 무한정 기다리게 되는 경우, 한 번 양보하거나 기다린 시간에 비례하여 일정 시간이 지나면 우선순위를 한 단계씩 높여 가까운 시간 안에 자원을 할당받도록 하는 기법

- SJF나 우선 순위 기법에서 발생할 수 있는 무한 연기 상태, 기아 상태를 예방할 수 있다.

​

​

* 2020년 1,2회 통합 정보처리기사 필기 기출 문제

HRN 스케줄링 방식에 대한 설명으로 옳지 않은 것은?

1. 대기 시간이 긴 프로세스일 경우 우선순위가 높아진다.

2. SJF 기법을 보완하기 위한 방식이다.

3. 긴 작업과 짧은 작업 간의 지나친 불평등을 해소할 수 있다.

4. 우선순위를 계산하여 그 수치가 가장 낮은 것부터 높은 순으로 우선순위가 부여된다.

* HRN 스케줄링 방식은 우선순위를 계산하여 그 수치가 높을수록 높은 우선순위가 부여된다.

​

* 이 게시물은 시나공 책을 참고로 작성되었습니다.