프로세스 스케줄링 유형을 살펴보면 다음과 같다.
1. 장기(long-term) 스케줄링
프로세스를 시스템으로 진입시킬지 여부 결정한다. 다중 프로그래밍 정도를 제어한다.
2. 중기(midium-term)
스케줄링 swapping 기능의 일부로 어떤 프로세스를 스왑 공간에서 주 기억장치로 불러들이는 일을 한다.
다중 프로그래밍 정도 제어한다.
3. 단기(short-term) 스케줄링
dispatcher. 이전 두 스케줄러보다 매우 자주 실행한다.
다음번에 실행시킬 프로세스 선정하는 기능이다.
우리가 여기서 관심가질 것은 단기 스케줄링이다. 보통 스케줄링 알고리즘을 말하면 단기 스케줄링 알고리즘을 말한다.
- 사용자 관점에선 response time(응답시간), 시스템 관점에선 throughput(처리량)에 관심이 있다.
* 우선순위 기반 스케줄링 : 우선순위가 가장 높은 프로세스를 다음번 프로세스로 선택한다.
낮은 우선순위의 프로세스가 계속 cpu할당 받지 못하는 Starvation(기아) 가능성.
⇒Aging : 시간이 지남에 따라 우선순위 낮은 프로세스의 우선순위 높여줌.
* 비선점(non-preemptive)모드 : 프로세스가 일단 실행 상태 진입하면 종료되거나 자발적으로 cpu 놓을 때까지
cpu 빼앗기지 않는다.
선점(preemptive)모드 : 현재 실행중인 프로세스라 할지라도 OS에 의해 인터럽트가 걸려 비자발적으로
준비큐로 이동 될 수 있다.
- 선점모드는 비선점모드 스케줄링에 비해 프로세스 간 context switching 자주 발생하므로 overhead가 크다.
하지만 프로세스가 처리기를 오랫동안 독점하는 현상 방지하므로 프로세스 전체에 보다 나는 서비스 제공한다.
* TAT(반환시간) : 대기시간 + 서비스시간 → TAT/서비스시간이 1이면 한 번도 대기한적 없음 의미한다.
그럼 이제 실제로 스케줄링 알고리즘을 살펴보자.
1. FCFS
FIFO. 준비큐에서 가장 오래 기다렸던 프로세스 선정한다. 비선점 모드.
짧은 프로세스, 입출력 프로세스에 불리
2. Round-Robin
시간을 측정하다가 (clock interrupt 주기적 발생) 일정 시간 넘어가는 순간 선점시킨다.
준비큐에서 FCFS 방식으로 다음 프로세스 선정한다. time slicing, time quantum 기법.
모든 프로세스에 공정한 방식이다.
⦁ 시간 할당량이 매우 작다면 짧은 프로세스 일수록 상대적으로 일찍 종료할 수 있으나,
스케줄링 횟수, 문맥교환 횟수 늘어나 오버헤드 커진다.
⦁ 시간 할당량이 너무 길면 FCFS와 같은 효과.
* Virtual Round-Robin : 입출력 중심 프로세스가 시간할당량 다 못 채우고 블록되고 다시 수행될 때 차별받지 않기 위해
준비큐로 들어가지 않고 보조큐라는 별도의 큐로 들어간다.스케줄러는 준비큐 보다 보조큐에 있는
프로세스를 먼저 수행해 지난번 못 채운 시간 할당량만큼 다시 수행 후 준비큐로 보낸다.
3. SJF(Shortest job first)
예상되는 전체 실행시간 가장 짧은 프로세스를 먼저 수행한다. 비선점모드
프로세스가 요구하는 총 실행시간 미리 알아야 한다. 긴 프로세스에게 불리하다(기아 가능성)
4. SRT(Shortest remaining time)
예상되는 남아있는 실행시간 가장 짧은 프로세스를 먼저 수행한다. SJF의 선점모드.
클록 인터럽트 필요 없지만, 각 프로세스의 전체 요구시간 중 얼마나 서비스 받았는지 기억해야 하는 오버헤드가 있다.
SJF에 비해 성능 좋다.
5. HRRN
R(응답비율) = W(대기시간) + S(서비스시간) / S 값이 가장 큰 프로세스 선정한다
전체 프로세스에 대해 평균 값 최소화 시키는 방향으로 진행한다.
비선점모드. 공정성이 좋음.
6. Feedback
예상되는 서비스시간 알 수 없는 경우. 지금까지 실행한 시간에 관심.
오랫동안 실행하고 있는 작업을 단계적으로 불이익 받도록 한다. 선점모드.
선점점 후 다시 준비큐로 들어갈 때 한 단계 우선순위 낮은 큐로. 모든 큐는 FCFS 방식이고, 가장 낮은 단계 큐는 Round-Robin.
새로 도착한 프로세스, 짧은 프로세스일수록 유리한다.
'OS' 카테고리의 다른 글
| hit rate 메모리 효율 (0) | 2014.11.30 |
|---|---|
| 디스크 스케쥴링 방법 (0) | 2014.11.30 |
| 프로그램, 프로세스, 스레드 (0) | 2014.11.28 |
| 스레드 간 통신 (0) | 2014.11.28 |
| IPC (0) | 2014.11.28 |