09 Uniprocessor Scheduling(2)

2. Scheduling algorithm (시험 반드시 출제)

Process Scheduling Example

- Arrival Time : 프로세스가 ready queue에 도착한 시간

- Service Time : 프로세스 실행 시작 후 종료되거나 I/O 함수호출로 대기 큐에 이동하기 전까지의 실행 예상 시간

  스스로 blocking 될 때까지의 시간

 Frist-Come-First-Served [FCFS]

: Ready queue에 들어 온 순서대로 실행 (FIFO)

- Ready queue에서 가장 오랫동안 있었던 (대기시간이 가장 긴) 프로세스가 가장 우선순위가 높음

- 비선점형 스케줄링 

- 짧은 작업의 프포레스가 긴 작업의 프로세스 때문에 오랫동안 Ready Queue에서 기다려야 하는 경우

1) CPU-bound processes (유리)

 - I/O가 거의 없는 계산 위주의 프로세스

 - 10억 개의 linked list 또는 tree 노드 처리

2) I/O - bound processes (불리)

 - 워드프로세서처럼 I/O 위주의 프로세스 (키보드/모니터 작업) 

 

Shortest Process Next 

: 짧은 실행 시간을 가진 프로세스를 우선적으로 실행

- 실행 시간이 짧은 프로세스가 가장 우선순위 높음

- 비선점형 스케줄링

- 실행 중인 프로세스가 완료된 후에 새로 스케줄링 시작

- 실행 시간이 큰 프로세스는 starvation (불리)

- 프로그램의 서비스 시간을 예측하기 쉽지 않다 (그래서 실제로 쓰이지는 않는 알고리즘)

 

Shortest Remaining Time

: 짧은 실행 시간을 가진 프로세스를 우선적으로 실행 (SPN의 선점형 버전)

- 선점형 스케줄링 : 새로운 프로세스가 등장할 때마다 다시 새로 스케줄링 시작

- 남아 있는 시간이 같을 경우 먼저 들어온 프로세스가 우선순위 높음

 

Highest Response Ratio Next [HRRN]

 : 프로그램 내에서 상대적으로 대기 시간이 큰 프로세스가 우선적으로 실행

- 비선점형 스케줄링

- 최대 반응 비율(R) = (프로세스의 서비스 시간 + 대기 시간) / 프로세스의 서비스 시간

 

Feedback

1) 이전의 알고리즘

- SPN, SRT, HRRN 알고리즘은 짧은 작업의 프로세스를 우선적으로 실행하고자 하는 전략

- 문제점 : 실행시간을 미리 알아야하기 때문에 현실에서 적용하기 힘듦

2) feedback 알고리즘

: 실행시간이 긴 알고리즘에게 패널티 부여

- 실제 실행시간을 몰라도 SRT와 비슷한 효과

- 종료되거나 주어진 time quantum을 소진한 후에만 다시 스케줄링 함 (새 작업이 도착했다고 바로 스케줄링하지 않음)

실행

3) feedback 알고리즘 실행 순서

① 위쪽 레디 큐에 있다가 한 번 실행된 후 아래 레디 큐로 이동 (FIFO 방식)

    레디 큐에 자기 혼자 있을 경우 아래 레디 큐로 내려가지 않음

② 실제로 processor은 하나만 존재함,

     하나의 CPU가 여러 레디 큐에 있는 프로세스를 실행, 위쪽 레디 큐가 비면 아래 쪽 레디 큐에서 프로세스를 선택하여 실행함

③  아래로 내려갈 수록 실행 시 주어지는 time quantum은 길어진다(2ⁱ). 프로세스의 우선순위는 낮아짐

 

Round-Robin

: time quantum에 기반을 둔 선점형 알고리즘

- 종료되거나 주어진 time quantum을 소진한 후에만 다시 스케줄링 함 (새 작업이 도착했다고 바로 스케줄링하지 않음)

- 새로 도착한 프로세스를 먼저 RQ에 넣고 time quantum을 소진한 프로세스를 그 뒤에 넣는다.

- CPU 바인딩 프로세스 선호 (I/O 프로세스는 자기에게 주어진 time quantum을 다 사용하지 못한 채 중단되는 경우가 자주 발생)

1) 구현 전략

① Clock interrupt 가 주기적으로 생성됩니다.
②  interrupt 가 발생하면 현재 실행 중인 프로세스가 읽기 대기열에 배치됩니다.
③ 다음 프로세스 준비 작업이 선택됩니다.

 

Virtual Round-Robin

: Round-Robin에서 주어진 time quantum을 다 사용하지 못한 점을 보완

- 대기 큐에서 깨어난 프로세스를 레디 큐로 옯기지 않고 보조 큐로 옮김

- 스케줄러는 보조 큐에 프로세스가 있을 경우 항상 보조 큐 프로세스를 먼저 실행함

- 이 경우 실행된 프로세스는 앞 전에 다 사용하지 못한 time quantum만큼 실행한 후 다시 레디 큐로 이동

- 스케줄러는 보조 큐가 빈 경우에만 레디 큐에서 다음 프로세스 선택

 

Various Scheduling Policies

	우선순위 측정 함수	Decision Mode	Response Time
FCFS	max [𝑤]	비선점형	실행시간 긴 프로세스 있을 경우 응답 시간 길어짐
Round Robin	max [𝑤]	선점형 (at time quantum)	실행시간이 짧은 프로세스의 경우 좋은 응답 시간 제공
SPN	min[𝑠]	비선점형	서비스 시간을 알아야 함
SRT	min[𝑠-𝑒]	선점형 (at arrival)	서비스 시간을 알아야 함
HRRN	max[(𝑤+𝑠)/𝑠]	비선점형	서비스 시간을 알아야 함
Feedback	(see text)	선점형 (at time quantum)	괜찮은 응답 시간

𝑤 : 대기 시간

𝑒 : 지금까지 실행된 시간

𝑠 : 프로그램 실행하는데 필요한 서비스 시간