운영체제 | CPU 스케줄링 알고리즘 | RR, SJF, STCF

 

협조적이든 비협조적이든 프로세스(쓰레드) 전환을 한다고 쳐. 그럼 지금 실행 중인 애는 ready list에 가겠지?

아니면 I/O 인터럽트로 blocked가 된다고 쳐. 

 

이제 그 다음에 실행할 녀석을 어떻게 고르냐가 문제임.

무조건 ready list에 들어온대로 처리할까? 그것도 초기에 쓰였던 방법 중 하나임. FIFO 또는 FCFS(First Come First Serve)라고 불리는 방식. 

 

이런 걸 스케줄링 알고리즘이라고 함. 어떻게 스케줄링을 할지에 대한 이야기. 

 

스케줄링 평가 기준: 평균 반환시간

 

스케줄링의 평가 항목: 어떤 스케줄링 알고리즘이 얼마나 좋은지를 어떻게 평가할까? 기준은 두가지임. 

 

1. 반환 시간(turnaround time): 작업 완료시간 - 시작시간 (대략 작업 리스트에 들어왔을 때부터 작업이 완료되기까지 걸린 시간)

2. 공정성(fairness) - 대표적으로 Jain's Fairness Index라는 지표가 있음. 

 

이 두가지는 trade off 관계가 되는 경우가 많음.

 

대략적으로 두 가지를 모두 반영하려면 n개의 작업이 있다고 했을 때, 전체 반환시간을 n으로 나눈 평균 반환 시간을 쓰면 어느정도 반영이 됨. 

 

FIFO 방식은 모든 작업이 짧을 때는 효율적임. 그러나 문제가 있음. 다음과 같은 상황을 가정해보자. 

예를 들어 A, B, C 3가지 작업이 있다고 치고, A는 100, B와 C는 10초간 실행되면 평균 반환시간은 

(100 + 110 + 120)/3 = 110이 된다. 

기회만 주어지면 금방 처리될 (CPU를 많이 필요로 하지 않는) B와 C가, 앞에서 A가 막고 있어서 늦게 처리되는 문제임. 이를 Convoy effect라고 함. 

 

책에서는 마트에서 계산 줄에 섰는데, 나는 콜라 한 병을 들고 있는데 앞 사람이 카트 3개치를 계산하고 있는 경우로 빗댐. 

 

그럼 FIFO보다 발전된 여러 스케줄링 알고리즘을 살펴보자. 

 

1. 최단 작업 우선 (SJF, Shortest Job First) 방식

모든 작업이 동시에 도착한다면, SJF가 최적의 스케줄링 알고리즘임. 

그러나 이는 비현실적임. 임의의 시간에 작업들이 도착한다면? 

만약 위 상황(A, B, C 예시)에서, A가 먼저 도착했다고 하자. 

그 당시엔 A가 최단 시간 작업임. 그래서 얘를 실행하고 있었어.

근데 A가 작업에 들어간 직후(약 10초 후)에 B와 C가 들어왔어. 

그럼 평균 반환시간은 A, B = 100, C = 110 / 3 으로 310/3 = 103.33 임. 

FIFO랑 큰 차이 없는 결과로 이어지게 됨. 

 

2. 최소 잔여시간 우선 (STCF, Shortest Time-to-Completion First) 방식

 

이는 선점형 최단 작업 우선(PSJF) 방식이라고 부르기도 함. 

왜냐하면 늦게 들어온 놈이 갑자기 선점할 수 있기 때문. 

 

새로운 작업이 도착하면, 현재 실행중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행 시간을 비교하여, 잔여 실행 시간이 가장 작은 작업을 스케줄한다. 

이는 SJF의 예외상황들을 잘 커버해준다. 때문에 똑같은 예시 상황에서 

10초 경과: A 10초 실행 (잔여 시간 90초)

20초 경과: B 10초 실행 (B: 20초 반환 - 10초에 들어옴 = 10)

30초 경과: C 10초 실행 (C: 30초 반환 - 10초에 들어옴 = 20)

120초 경과 :A 90초 실행 (A: 120초 반환 - 0초에 들어옴 = 120)

 

-> 150/3  = 50초로 평균 반환시간이 극적으로 개선됐다. 

 

 

 

새로운 평가기준: 응답 시간(Response time)

time sharing 컴퓨터의 등장 -> 단순히 프로그램을 쭉 처리하는게 아니라 컴퓨터와 상호작용 니즈 -> 응답 시간(response time) 이라는 새로운 평가 기준이 생김 

응답 시간 = 처음으로 스케줄된 시간 - 작업 도착 시간

 

그러니까, 사용자가 어떤 거 실행하면 빨리 실행된 화면 보고싶다 이거야. 

계속 기다리고 있는건 싫다는 것!

 

 

앞에서 모든 작업이 동시에 도착했다는 가정하에, SJF가 최적이라고 했지? 사실 여기서는 그렇지 않음. 

 

 

 

 

만약 C 작업이 내가 터미널에 무언가를 입력해서 응답을 기다리는 작업이라고 해보자.

A, B, C 전체가 끝나는데까지는 효율적이지만, 정작 사용자인 나는 A, B 작업이 빨리 끝나든 말든 관심없고, 이 두 작업이 끝나는 몇초간 기다리고 있어야 하는게 답답한 거임.

 

이제 응답 시간까지 최소화하는 스케줄러가 등장할 차례이다. 

 

3. 라운드 로빈(RR, Round Robin) 방식

 

기본 FIFO 베이스에서, 타임 슬라이스(time slice, 또는 스케줄링 퀀텀) 마다 다음 스케줄로 전환하는 메커니즘이 추가되었다. 

타임 슬라이스는 타이머 인터럽트 주기의 배수여야 한다. 만약 타이머 인터럽트가 10 ms마다 발생한다면, time slice는 10, 20, 30.. 으로 정해진다. 

 

time slice가 짧을 수록 응답 시간은 우수해짐(짧아짐). 그러나 문맥 교환 비용이 너무 커져서 전체 시스템 성능에 영향을 미치게 된다.

 

또한 단순히 평균 반환시간만을 고려하게 된다면 RR은 최악에 가까운 성능을 보이게 된다. 

 

 

 

4. 우선순위 스케줄링 (Priority scheduling) 방식

• 프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스는 FIFO(선입 선처리)로 스케줄링
• SJS(최단 작업 우선 스케줄링), SRT(최소 잔여 시간 우선 스케줄링)도 우선순위 스케줄링에 속하는 개념이라 볼 수 있다
• 문제점
  • 우선순위 스케줄링의 문제점: 기아 현상(Starvation)
  • 우선순위 높은 프로세스만 주구장창 실행시키고, 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었음에도 불구하고) 실행이 연기될 수 있다개선책
• Starvation을 개선하기 위한 기법: 에이징(Aging)
  • 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다
  • 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법이다. 이를 통해 우선순위가 매우 낮은 프로세스도 언젠가는 우선순위가 높아진다.