6. 스케쥴링 알고리즘

■ 선입선처리(FCFS) 스케줄링
- 비선점 방법으로 프로세서 스케줄링 알고리즘 중 가장 단순하고 프로세서 요청하는 순서대로 프로세서 할당, 선입선출FIFO 큐로 구현한다. 그리고 일괄 처리 시스템에서는 매우 효율적이나 빠른 응답을 요청하는 대화식 시스템에는 적합하지 않다.

- 먼저 들어온 작업에 대해 먼저 처리해줄게!

- 비선점 방식

- 빠른 응답이 필요한 대화식 시스템에서는 비효율적

 

■ FIFO 큐 : 자료구조에서 나온다. 먼저 들어온 거, 먼저 내보내겠다!

 

 

■ (b) 간트차트 : 각각의 프로세스들이 언제 들어왔고, 얼만큼의 시간을 가지고 프로세스를 사용했는지, 실행시간을 한눈에 볼 수 있는 차트

 

■ 반환시간, 대기시간 구하기

■ 반환 시간

- P2를 예로 들자.

- (38-1) = 37로 되어있다. 여기서 앞P1의 10초와 P2의 28초를 더해서 38이다. 거기서 도착한 시간이 1이니 38-1이 된다. 그래서 37이다.

 

■ 대기 시간

- P3를 예로 보자

- 실행시간 P1(10초)와 실행시간 P2(28)초를 더하면 38초이다. 거기서 P3본인이 도착시간 2를 빼면 된다. 그래서 36이다.

 

 

■ 반환 시간 대기 시간 빨리 보는 법

- 칸트차트를 참고하자

- P2를 예로 보자

- P2 반환시간 : 간트에서 P2의 끝 38 - 본인 도착시간 1 = 37

- P2 대기시간 : 간트에서 P1의 끝 10 - 본인 도착시간 1 = 9

 

 

 

■ 앞의 예시PPT와 다른점

- 실행시간이 짧은 것들이 앞에 몰려있다.

- 실행시간이 짧은 것이 앞으로 몰려있다보니 평균반환시간과 대기시간이 더 빠르다. 

 

■ 최소작업 우선(SJF) 스케줄링
- 각 작업의 프로세서 실행 시간 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업(프로세스)에 할당하는 방법이다.

- 짧은 놈부터 처리하자!

- 선점과 비선점 형태로 나뉜다. 여기서는 비선점부터 알아보자.

 

 

■ 들어온 순서대로가 아닌, 실행시간이 짧은 프로세스부터 해야한다.

■ 그럼 P1은 10초인데 왜 먼저했는가? 도착시간이 0초이다. 즉 먼저 실행되고 있었고, 나머지 P2,3,4,5는 P1이 실행되고 있는 중간에 들어왔기에, P1은 먼저한다. 다만 그 이후에는 최소작업을 우선순위로 시작하는 것이다.

 

 

■ 단점 : 왜 기아가 발생하는가? 결국은 대기시간이 긴 프로세스는 가장 후순위로 밀리기때문에 기아(자원을 할당받지 못하는 상태)가 발생한다.

■ 계속해서 자기보다 짧은 작업 프로세스가 들어오게되면, 긴 프로세스는 기다려야한다. 결국 불공정해진다! 

 

■ 선점 : 중간에 수행되는 프로세스의 자원을 뺏을 수 있다!

■ SRTF = SRT 라고도 함

 

■ 살펴보기

- P1(10초)이 실행되고 있음. 

- P2(28초)가 들어옴. 10초보다 실행시간이 기니까 선점이 안됨

- P3(6초)가 들어옴. 이때 P1은 2초가 지난 시점이라 10-2초. 즉 8초가 남은 상태임. 그래도 6초보다 짧으니까 뺏기게 된다!

-여기까지 총, 2초가 지난 시점의 이야기.

 

- 총 3초가 지난 시점에 P4가 들어옴.

- 이 시점에 자원을 뺏은 P3은 6-1초 해서 5초인 상태.

- 그러나 새로 들어온 P4(4초)가 더 실행시간이 작다. 그래서 또 뺏기게 된다.

 

- P4의 프로세스가 끝나면 남은 시간이 적은 녀석들부터 된다. 그래서 P3(6-1초) 이 된다. 이후는 P1(10-2초)

- P5(14초), P2(28초)도 순서대로 실행된다. 

 

■ 오른쪽표

여기서 시간을 빼줄때 잘해야한다. 앞서 실행한 시간이 있다면 반드시 빼줘야 한다.

 

 

■ 우선순위 스케줄링
우선순위가 동일한 프로세스들은 선입선처리 순서로 스케쥴링되는 것으로 실행 시간이 클수록 우선순위가 낮고, 우선순위는 0~7 또는 0~4,095 범위의 수 사용한다. 단, 0을 최상위나 최하위로 정하지는 않았다.

 

■ 여기서는 왜 P1부터? (비선점 방식)

- 일단 먼저 도착했으니까! 우선순위가 3이라고 해도 먼저 처리되는 것이다. 그다음 순위가 1등인 P3이 되는 것이다.

- 즉 해당 우선순위 스케쥴링은 비선점이다. 우선순위1이 있음에도 프로세스를 뺏지 않았으니까!

- P1(먼저도착했으니까) > P3(우선순위1) >  P2(우선순위2)

 

■ 그러나 선점방식도 가능하다.

- P1 도착 > 3초후 > P2가 뺏음 > 6초후 > P3이 뺏음 > P3프로세스 끝 > P2의 남은 프로세스 > P1의 남은 프로세스

 

 

■ 고정 운선순위 알고리즘: 비효율적, 단순함, 우선순위가 고정

■ 변동 우선순위 알고리즘 : 효율적, 복잡함, 우선순위가 계속 바뀜

 

■ 우선선위 스케쥴링의 문제점

- 우선순위가 높은 프로세스가 계속 들어오면? 후순위 프로세스는 계속 기아!

 

■ 해결법? 에이징!

- 오래기다리는 프로세스에게 우선순위를 증가시켜줌! 

 

 

 

■ 단점의 극복방법 : 에이징을 잊지말자!

 

 

■ 라운드 로빈 = RR 이라고 함.

- 작은 단위의 시간인 규정 시간량을 주어서 프로세스가 정의된 규정 시간만큼만 CPU를 사용하도록 구성된 스케쥴링

 

■ 타임슬라이스 : 

- 모든 프로세스들이 CPU를 사용할 수 있는 시간을 모두 동일하게 주는 것. 시험시간과 같다고 생각하자.

- 주어진 같은 시간 내에 문제풀이하듯, 시간을 공평하게 주는것

 

 

 

 

■ 간트 도표 해석

- 모든 프로세스들에게 5초씩 시간을 줌. 

- 다만 P4의 경우는 실행시간이 4초다. 즉 보면 15-19-24-29초로, 이후 전체 시간이 1초씩 줄어든다. 이 점을 잊지말자.

 

■ 라운드 로빈 = RR 방식의 장단점

 

 

■ 다단계 큐의 개념 : 준비 큐를 종류별로 여러개의 단계로 분할. 작업을 메모리의 크기나 프로세스의 형태에 따라서 특정 큐에 지정

 

 

■ 다단계 피드백 큐의 개념 : 프로세스가 실행될 때마다 우선순위가 낮아진다

 

■ 다단계 피드백 큐의 장단점

 

■ HRN 스케쥴링 개념 : 

- 선입선처리(FCFS), 최소작업 우선(SJF) 스케쥴링의 약점을 보완해서 나온 스케쥴링 기법

- 비선점 방식

 

■ 우선순위 공식은 외워두자. 중요하다.

- 우선순위가 높을 수록 먼저 CPU를 배정을 받게 됨.

- 대기한 시간이 길수록 우선순위가 높다. 왜? 오래기다렸으니까! 그 시간만큼 더해주기 때문에 우선순위가 높아진다.

 

■ P1, P2 비교 : 서비스 시간이 20초로 둘다 같다. 그러나 대기시간이 차이가 있다. 그래서 P2가 우선이다.

 

■ 대기시간이 긴 프로세스도 고려한 방식이기에 기아가 발생하지 않음

■ 서비스 시간, 대기시간을 체크해야하기 때문에 메모리와 프로세서 낭비가 있을 수 있다.

 

 

 

 

■ 학습정리

선입 선출, 최소 작업 우선 스케쥴링

• 선입선처리 스케줄링은 비선점 방법으로 프로세서 스케줄링 알고리즘 중 가장 단순하며 프로세서 요청하는 순서대로 프로세서 할당, 선입선출FIFO 큐로 구현한다. 일괄 처리 시스템에서는 매우 효율적이나 빠른 응답을 요청하는 대화식 시스템에는 적합하지 않다.
• 최소작업 우선 스케줄링은 각 작업의 프로세서 실행 시간 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업(프로세스)에 할당하는 방법이다.

 

우선순위, 순환 할당 스케쥴링

• 우선순위 스케쥴링은 우선순위가 동일한 프로세스들은 선입선처리 순서로 스케쥴링 한다.실행 시간이 클수록 우선순위가 낮고, 우선순위는 0~7 또는 0~4,095 범위의 수를 사용한다. 단, 0을 최상위나 최하위로 정하지는 않았다.
• 라운드 로빈 스케쥴링은 특별히 시분할 시스템을 위해 설계하는데 작은 단위의 시간인 규정 시간량(Time quantum) 또는 시간 할당량(Time slice)로 정의된다. 준비 큐를 순환 큐(Circular queue)로 설계하여 스케줄러가 준비 큐를 돌아가면서 한 번에 한 프로세스에 정의된 규정 시간량 만큼 프로세서 제공한다.

 

다단계 큐, HRN 스케쥴링

• 다단계 큐 스케쥴링은 각 작업을 서로 다른 묶음으로 분류할 수 있을 때 사용한다. 준비 상태 큐를 종류별로 여러 단계로 분할하고 작업을 메모리의 크기나 프로세스의 형태에 따라 특정 큐에 지정한다. 각 큐는 자신만의 독자적인 스케줄링 갖는다.
• HRN 스케쥴링은 최소작업 우선 스케줄링의 약점인 긴 작업과 짧은 작업 간의 지나친 불평 등을 보완하며 비 점 스케줄링이며 우선순위 스케줄링의 또 다른 예로 선입선처리 스케줄링과 최소작업 우선 스케줄링의 약점을 해결을 위해 제안한다.