인트로
1) 비선점 스케쥴링 정의 & 특징
2) 비선점 스케쥴링 기법
3) 선점 스케쥴링 정의
4) 선점 스케쥴링 기법
1) 비선점 프로세서 스케쥴링 기법 정의& 특징
1-1) 비선점 스케쥴링(non-preemtive) 정의
이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케쥴링 기법이다.
프로세스가 CPU를 할당받으면 프로세스가 완료될때까지 CPU를 사용한다.
1-2) 비선점 스케쥴링의 특징
모든 프로세스에 대한 요구를 공정하게 처리한다.
응답 시간 예측이 용이하다.
2) 비선점 스케쥴링 기법
비선점 스케쥴링 기법에는, FCFS, SJF(shortest job first), 우선순위, HRN(High response-ratio next) 등의 알고리즘이 있다.
1) FCFS(First Come, First Service)
도착한 순서대로 CPU할당하는 스케쥴링 기법
2) SJF(Shortest Job First)
실행시간이 가장 짧은 프로세스에게 CPU 먼저 할당하는 스케쥴링 기법
3) HRN ( Hightest Response ration-next)
HRN 스케쥴링기법은,
우선순위를 계산하여 그 순위가 가장 높은 것부터 낮은것으로 우선순위가 부여된다.
서비스 시간이 짧거나 대기시간이 긴 프로세스 위주로 우선순위가 계산된다.
우선순위 = (대기시간 + 실행 시간) / (실행시간) = (대기시간+ 서비스시간)/ 서비스시간
P1 실행시간 : 20 , 대기시간 : 10
P2 실행시간 : 4 , 대기시간 : 20
P3 실행시간 : 6, 대기시간 : 10
P1 = (20 + 10) / 20 = 1.5
P2 = (4 + 20) / 4 = 6
P3 = (6 + 10) / 6 = 2.6
P2 --> P3 --> P1 의 순서로 진행된다.
* 에이징(Aging)이란 , 대기시간 등에 따라 우선순위를 높여주는 것을 말한다.
* 우선순위란, 준비상태 큐에서 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 CPU를 먼저 할당한다.
* 기아상태란, 우선순위에서 무한 연기되어 프로세스를 완료하지 못하는 상태. (SJF나 우선순위 기법은 이를 예방한다. )
3) 선점 스케쥴링(Preemtive) 정의와 특징
3-1) 선점 스케쥴링(Preemtive)이란,
하나의 프로세스가 CPU를 할당받아 실행하고 있을때,
우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케쥴링 기법이다.
3-2) 선점 스케쥴링 특징
(1) 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.
(2) 대화식 시분할 시스템에 많이 사용된다.
(3) 많은 오버헤드를 초래한다.
(4) 선접이 가능하도록 일정시간 배당에 대한 인터럽트용 타이머 클록이 필요하다.
타이머 클록이란,
하나의 시스템에서 동작하는 장치들을 감시하기 위해 주기적인 신호를 발생하는 것으로,
자원을 독점화하는 것을 방지한다.
4) 선점 스케쥴링 알고리즘
1) SRT(shortest Remaining time)
현재 실행 중인 프로세스의 남은 시간과 준비상태큐에 새로 도착한 프로세스의 실행시간을 비교하여
가장 짧은 실행을 요구하는 프로세스에게 CPU할당한다.
+) 오버헤드가 증가하는 단점이 있다.
2) RR(Round-Robin) : 선점형 스케쥴링 방식
시분할 시스템으로 고안된 방식으로, FCFS 알고리즘을 선점 형태로 변형된 기법이다.
먼저 CPU를 할당받지만, 시간할당량(time slice)만 실행한 후 실행이 완료되지 않으면
다음 프로세스에게 CPU를 넘겨주고 준비상태의 맨 뒤로 배치된다.
제한) time-slice : 4초
프로세스번호
P1 실행시간 : 20초
P2 실행시간 : 4초
P3 실행시간 : 6초
주어진 시간(time slice)동안 실행되지 못할 경우, 준비상태의 큐의 가장 마지막으로 재배치하여 차례를 기다린다.
| P1 | P2 | P3 | P1 | P3 | P1 | P1 | P1 |
| 4 | 4 | 4 | 4 | 2 | 4 | 4 | 4 |
P1의 반환시간 : 30
P2의 반환시간 : 8
P3의 반환시간 : 18
P1의 대기시간 : 18 - 4 - 4 = 10초
P2의 대기시간 : 4초
P3의 대기시간: 16- 4초
* 대기시간 : 가장 마지막 실행이 시작되기 전까지의 진행 시간을 이용하여 구한다 .
* 해당 프로세스가 앞에서 실행되었을 경우 실행된 시간은 제외한다.
3) 다단계 큐 스케쥴링(선점형 스케쥴링)
프로세스들을 우선순위에 따라
시스템프로세스, 대화형프로세스 , 일괄형 프로세스 등으로 상위, 하위 단계의 단계별로 준비큐를 배치하는 방식이다.
4) 다단계 피드백 큐 스케쥴링(선점형 스케쥴링)
마지막 단계의 큐에서 Round Robin방식을 사용한다 .