이론 3) - 2 스케줄링 알고리즘

!! 스케줄링 알고리즘 !!

 

1. 선입선처리 스케줄링(FCFS)

: 프로세스를 요구 순서대로 할당합니다.(First Come First Served)

 

- 비선점 기법 으로 스케줄링 알고리즘 중에 가장 간단합니다.

- 선입선출 큐로 구현합니다.

- 일괄처리에는 효율적, 대화식 시스템에서는 사용자의 빠른 응답 요구에 부적합

 

1) 평균 반환시간 : (24 + 27 + 30) / 3 = 27

2) 평균 대기시간 : (0 + 24 + 27) / 3 = 17 

3) CPU이용률 : 100%

4) 처리량(작업처리율) : 3 / 30 = 10%

5) 평균 반응시간(응답시간) : (0 + 24 + 27) / 3 = 17

 

 

 

 

1) 평균 반환시간 : (3 + 6 + 30) / 3 = 13

2) 평균 대기시간 : (0 + 3 + 6) / 3 = 9 

3) CPU이용률 : 100%

4) 처리량(작업처리율) : 3 / 30 = 10%

5) 평균 반응시간(응답시간) : (0 + 3 + 6) / 3 = 3

 

 

 

 

 

 

 

 

 

 

 

 

2. 최단 작업 우선 스케줄링

: CPU 버스트 시간이 가장 짧은 작업에 CPU를 할당합니다.

 

- 평균 대기시간을 최소화하는 알고리즘입니다.

- 문제점 : 실행 시간의 길이 예측이 힘듭니다. -> 실제로 실행하면 실행시간이 달라질수도 있기 때문입니다.

 

1) 평균 반환시간 : (3 + 9 + 16 + 24) / 4 = 13

2) 평균 대기시간 : (0 + 3 + 9 + 16) / 4 = 7

3) CPU이용률 : 100%

4) 처리량(작업처리율) : 4 / 24 = 0.167

5) 평균 반응시간(응답시간) : (0 + 3 + 9 + 16) / 4 = 7

 

 

 

 

- 최단 작업 우선 스케줄링은 선점 또는 비선점 모두 가능합니다.

(선점 : 매번 프로세스가 도착할 때마다 최단 작업을 비교하여 더 짧은 작업이 있다면 해당 작업으로 변경합니다.)

(비선점 : 한 프로세스가 끝난 뒤에 남은 것들끼리 비교하여 할당합니다.)

 

 

 

(a) 선점 -> 문맥교환하는 데 시간이 소요됨

- 평균 반환시간 : { (17-0) + (5-1) + (26-2) + (10-3) } / 4 = 13

- 평균 대기시간 : { (10-1) + (1-1) + (17-2) + (5-3) } / 4 = 6.5

- CPU이용률 : 100%

- 처리량(작업처리율) : 4 / 26 = 

- 평균 반응시간(응답시간) : (0 + 0 + (17-2) + (5-3)) / 4 = 

 

(b) 비선점

- 평균 반환시간 : { (8-0) + (12-1) + (26-2) + (17-3) } / 4 = 14.25

- 평균 대기시간 : { 0 + (8-1) + (17-2) + (12-3) } / 4 = 7.75

- CPU이용률 : 100%

- 처리량(작업처리율) : 4 / 26 = 

- 평균 반응시간(응답시간) : (0 + (8-1) + (17-2) + (5-3)) / 4 = 7.75 

 

 

 

 

 

 

 

 

 

 

3. 우선순위 스케줄링

: 최고 우선순위 프로세스를 CPU에 할당합니다.

: 최단 작업 우선 스케줄링은 우선순위 스케줄링에 해당합니다.

: 선점, 비선점에 모두 적용 가능합니다.

 

문제)

: 기아 상태가 발생가능합니다.

(기아 상태란? 우선순위가 높은 프로세스들이 계속 들어오면 우선순위 낮은 프로세스들은 무한정 기다려야 하는 상태)

해결법)

: 에이징(Aging) - 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법입니다.

 

 

-> 선점과 비선점 모두 같은 그림이 나옵니다.

1) 평균 대기시간 : (0 + 1 + 6 + 16 + 18) / 5 = 8.2

 

 

 

 

 

 

 

 

 

 

 

4. 라운드 로빈 스케줄링 [ 순환 할당 스케줄링 ]

: 시분할 시스템을 위해 설계되었습니다.

: 규정 시간량이 지나면 인터럽트가 발생하며 문맥교환을 수행합니다.

: 준비큐는 FIFO 큐이면 순환큐로 설계합니다.

 

순환큐 예시

라운드 로빈 스케줄링

 

평균 반환시간 = { (16-1) + (8-1) + (26-2) + (25-3) } / 4

 

 

 

- 순환 할당 스케줄링은 선점 알고리즘입니다.

- 성능은 규정 시간량에 영향을 받습니다.

if 규정 시간량이 아주 클 경우, 평균 대기시간이 길어집니다.

if 규정 시간량이 매우 작을 경우, 문맥교환 횟수가 증가합니다.

-> 최적 규정 시간량은 시스템 특성 및 오버헤드, 프로세스에 따라 다릅니다.

 

- 반환시간도 규정 시간량에 영향을 받습니다.

if 규정 시간량이 매우 작을 경우, 반환시간이 증가합니다.

but 반환시간과 규정 시간량이 항상 반비례한 것은 아닙니다.

 

 

 

 

 

 

 

 

 

5. 다단계 큐 스케줄링

: 각 작업들을 서로 다른 묶음으로 분류할 수 있을 때 사용합니다.

: 준비상태의 큐를 종류별로 여러 단계로 분할합니다.

: 각 큐는 자신만의 독자적인 스케줄링 알고리즘을 가집니다.

: 큐들 사이에 시간을 나누어 사용가능합니다.

 

큐 5개를 가진 다단계 큐 스케줄링 알고리즘

 

- 각 큐는 순서대로 절대적인 우선순위를 가집니다.

- 앞의 세 가지 큐가 비어있어야, 네 번째 일과 처리 큐에 있는 프로세스가 실행이 됩니다.

 

 

 

 

 

 

 

 

 

 

 

6. 다단계 피드백큐 스케줄링

 

다단계 큐 : 작업이 시스템에 들어가면 한 큐에서만 고정

다단계 피드백큐 : 작업이 큐 사이를 이동 가능

 

-> 기아 상태 예방을 위해 에이징 방법을 활용합니다.

: 특정 큐에서 오래 기다린 프로세스를 우선순위가 높은 큐로 이동합니다.

 

 

 

 

 

 

 

 

 

7. HRN 스케줄링(Highest Response-rate Next)

: 단기 작업 우선 스케줄링의 약점인 긴 작업과 짧은 작업 간의 불평등을 보완한 기법입니다.

: 가변적인 우선순위를 갖는 단기 작업 우선 스케줄링입니다.

가변적 우선순위 계산법

- 비선점 알고리즘입니다.

 

 

 

 

 

* 정보처리기사 문제풀어보기 *

 

1. 선점 기법 : 문맥교환으로 인해 많은 오버헤드 초래

2. 비선점 기법 : 모든 프로세스 요구 공정히 처리, 응답시간예측 용이,

CPU 사용시간 짧은 프로세스가 긴 프로세스들로 인해 오래기다림

3. 라운드 로빈 -> 시분할 시스템

4. HRN 방식 : 서비스 시간이 짧고, 대기 시간이 긴 순서대로

5. 응답시간 줄이고 CPU 이용률 높이고