Scheduling_2

스케줄링 [Scheduling]

 

 

■ 스케줄링 알고리즘: 단기 스케줄링 평가 기준

• 사용자 중심 관점

1. 프로세스가 요구한 작업 요청에 대해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간
2. 개별 사용자 or 개별 프로세스의 입장에서 자신들에게 긍정적 영향을 끼치는 스케줄러, 그렇지 못한 스케줄러를 평가 (ex: 응답시간 [Response Time]

• 시스템 중심 관점

1. 스케줄러가 처리기를 얼마나 효율적으로 활용했는가? (ex: 처리량 [Throughput]: 단위 시간 안에 실행을 완료시킬 수 있는 프로세서의 수)

 

- 어느 한 관점만을 중시하면 다른 관점이 안좋아짐.

- 모든 시스템에서 중시해야 할 관점 -> 사용자 중심

- 시스템 유형별로 중시해야할 관점이 다를 수 있음. (ex: 단일 처리기 시스템 -> 시스템 중심 관점이 상대적으로 덜 중요함)

 

 

• 성능 중심 관점

1. 대부분 정량적인 척도 -> 측정이 용이함.

• 성능 외적(기타) 관점

1. 대부분 정상적인 척도 -> 측정이 용이함 (ex: 예측 가능성 [Predictability])

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

■ 스케줄링 알고리즘: 우선순위 기반 스케줄링

• 우선 순위가 높은 프로세스를 먼저 실행한다.

1. 우선순위별 대기 큐를 별도로 둔다.
2. 높은 우선순위의 대기 큐에 있는 프로세스를 먼저 실행한다.

우선순위[RQi] > 우선순위[RQj] / for i < j

Q: 동일한 우선순위 큐 내에서는 어떤 정책을 써야하는가?

A: 스케줄링 방식을 혼용하여 사용한다.

 

Q2: 순수 우선순위 기반 스케줄링의 문제점은 무엇인가?

A: 기아현상 (Starvation)

 

Q3: Q2의 기아현상을 방지하기 위해 사용하는 기법은?

A: 에이징 기법을 사용한다.

 

 

※ 에이징 기법?

프로세스가 우선순위를 빼앗길때마다 해당 프로세스의 우선순위를 높여주는 것. -> 영영실행이 안될 수 있지만 기아 현상은 막을 수 있다.

 

 

 

■ 스케줄링 알고리즘: 다양한 스케줄링 정책

Selection Function: 다음번 실행을 위해 준비 큐에서 대기 중인 프로세스 중 하나를 고를 때 사용하는 알고리즘

• Function Factors

1. w= 대기한 시간과 실행한 시간을 모두 합쳐 시스템에 들어온 후 지금까지 경과한 시간.
2. e= 지금까지 실행하는데에만 걸린 시간
3. s= 프로세스가 시작해서 종료하기까지 걸린 총 서비스 시간

※ 선택함수의 예

max[w]: 시스템에 진입한지 가장 오랜 시간을 보낸 프로세스를 선택 -> FCFS를 의미.

 

 

 

Decision Mode: 선택 함수가 호출되는 시점이 언제인가?

• 비선점 [nonpreemptive]

1. 프로세스가 일단 실행상태 (Running State)에 진입하면 종료되거나 자발적으로 CPU를 놓을 때 까지는 CPU를 빼앗기지 않는다.

 

• 선점 [preemptive]

1. 현재 실행 중인 프로세스라 할지라도 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있다.
2. nonpreemptive 모드보다 문맥 교환 횟수가 많아진다.
3. 한 프로세스가 처리기 시간을 독점하는 것을 방지할 수 있어 효율적 인 스케줄링이 가능함!

 

FCFS [First Come First Served]

1. FIFO (First In First Out)이라고도 함.
2. 프로세스는 준비 상태가 되면 준비 큐에 들어감.
3. 현재 실행 중인 프로세스가 실행을 종료 -> 준비 큐에서 대기 중 이던 프로세스 중 가장 오랫동안 기다렸던 프로세스가 다음 번 실행 프로세스로 선정됨

프로세스	도착 시간	서비스 시간
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

 

• FCFS [First Come First Served]

1. FCFS는 짧은 프로세스보다는 긴 프로세스에게 유리 -> Nonpreemptive 모드로 동작하기 때문
2. FCFS는 결국 비효율적 스케줄링 기법 -> 우선순위 기법과 결합하면 성능이 많이 나아짐
3. 입출력 중심의 프로세스보다 처리기 중심 프로세스를 우대하는 경향이 나타남

 

 

라운드 로빈 [Round Robin]

1. FCFS에서 짧은 프로세스가 피해보는 현상 완화 방법

- 시간을 측정하다가 어떤 긴 프로세스가 일정 시간 이상을 넘는 순간 실행을 강제로 중단시킴 (Preemption: 선점)

 

2. 프로세스 실행 시간 측정 방법

- 클럭(Clock) 인터럽트 (또는 타이머 인터럽트)

- 클럭 인터럽트는 일정 간격으로 주기적으로 발생

 

3. 라운드 로빈 스케줄링 기법 동작 방식

- 시간 할당량 ( Time Slicing 혹은 Time Quantum ) 기법이라고도 함.

- 클럭 인터럽트가 발생하면 클럭 인터럽트 서비스 루틴이 실행. > 클럭 인터럽트 서비스 루틴은 현재 실행 중인 프로세스를 준비 큐로 이동 시킴 > 준비 큐에서 FCFS 방식으로 다음번 프로세스를 골라 실행시킴.

 

 

• 시간 할당량의 크기(q)가 라운드 로빈 성능에 미치는 영향

1. 시간 할당량이 너무 작은 경우 -> 문맥교환 오버헤드 증가
2. 시간 할당량이 너무 큰 경우 -> FCFS와 비슷해짐

• 시간 할당량의 권장 길이

1. 프로세스가 사용자와 최소한 한번 이상 대화하기에 충분함. -> 어느정도 대기가 이루어질 수 있겠지만, 실행은 이루어져야함.
2. 프로세스 내의 어떤 한 함수 정도는 실행을 마칠 수 있는 충분한 길이. -> 어떤 함수는 길고 어떤 함수는 작음. 

 

- 가상 라운드 로빈 (VRR) 스케줄러의 대기 큐 구조 -

라운드 로빈의 단점: 서비스 시간이 긴 프로세스들의 수행시간이 늘어나게된다 -> 수행시간이 커지면 커질수록 대기시간이 길어진다.

• 해결방법: 가상 라운드로빈 (VRR) 스케줄링 방식: 공통적 요구사항을 맞출 수 없으니 큐를 분리시킨다.

1. 입출력 중심 프로세스와 처 리기 중심 프로세스를 분리 하여 준비 큐를 둠.
2. 계산하던 중 시간할당량을 다 썼다면 그냥 준비 큐로 들어감.
3. 입출력 요청으로 CPU를 반 납했다면 입출력 대기 큐로 들어감.
4. 스케줄러는 입출력 대기 큐 에 있는 프로세스를 먼저 스 케줄링 함!

 

SPN [Shortest Process Next]

1. FCFS의 긴 프로세스 우대 편향성 완화방법
2. 가장 짧은 프로세스를 먼저 실행 시키는 정책
3. 종료 시까지 남아 있는 실행시간이 가장 짧은 프로세스를 다음번 프로세스로 선택
4. 비중단 (Nonpreemptive) 모드로 동작
5. 실행 시간이 짧은 프로세스가 (늦게 도착했더라도) 긴 프로세스들보다 먼저 스케줄링 될 수 있다.

※ 단점:

짧은 프로세스들이 지속적으로 시스템에 진입한다면, 이들보다 상대적으로 긴 프로세스가 기아 상태에 빠질 수 있다.

 

 

SPN 구현 상의 문제점

1. 각 프로세스가 요구하는 총 실행 시간을 미리 알아야한다.
2. 미리 알기가 어렵기 때문에 시스템은 이를 유추할 수 있어야 한다.

 

 

SRT [Shortest Remaining Time]

1. SPN의 중단 (Preemptive) 모드 버전에 해당.
2. 예상되는 남아 있는 실행 시간이 가장 짧은 프로세스가 다음번 프로세스로 선택됨.  if (“새로 도착한 프로세스의 예상되는 남아있는 실행 시간” < “현재 실행 중인 프로세스의 예상 실행 시간”) →  늦게 도착했더라도 현재 실행 중인 프로세스를 중단하고 곧장 선택됨.

※ 단점

매 스케줄링 때마다 프로세스들의 남아있는 실행 시간을 평가해야하는 부담감

긴 프로세스가 기아 상태에 빠질 가능성

 

※ 스케줄러의 근간

1. FCFS
2. FIFO
3. 선점
4. 비선점