정보처리기사 필기 ) 선점 스케줄링

* 준비상태 큐에 새로 들어온 프로세스의 순위가 높을 경우 현재의 프로세스를 보류하고 새로운 프로세스를 실행

​

1. SRT(Shortest Remaining Time)

- SJF 기법을 선점 형태로 변경한 기법

- 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에 CPU를 할당하는 기법, 시분할 시스템에 유용

- 준비상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가

​

2. RR(Round Robin)

- 시분할 시스템을 위해 고안된 방식, FCFS 알고리즘을 선점 형태로 변형한 기법.

- FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 시간 할당량 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치

- 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생되어 요청된 작업을 신속히 처리할 수 없음

- 할당되는 시간의 크기가 작으면 작은 프로세스들에게 유리

​

예) 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, 평균 대기 시간, 평균 반환 시간을 구하시오(단, Time Slice는 4초이다)

프로세스 번호/실행시간

P1/20 P2/4 P3/6

* 주어진 시간 할당량동안 실행되지 못할 경우 준비상태 큐의 가장 마지막으로 재배치하여 차례를 기다림

* 반환 시간 : 각 프로세스가 완료되는 시간을 이용하여 구함

* 대기 시간 : 대기 시간을 구하고자 하는 프로세스의 가장 마지막 실행이 시작되기 전까지의 진행 시간을 이용하여 구하되, 해당 프로세스가 앞에서 실행되었을 경우 실행된 시간은 제외

* 평균 반환 시간 : (30+8+18)/3 = 18.6

* 평균 대기 시간 : (10+4+12)/3 = 8.6

>> P1의 대기 시간 : (반환 시간전까지의 진행 시간 - 진행시간동안 해당 프로세스의 실행시간) > 26-16=10

 

 

프로세스 / 실행시간

A/17 B/4 C/5

* 평균 반환 시간 : (26+8+17)/3 = 17

​

​

3. 다단계 큐(MQ; Multi-level Queue)

- 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태큐를 사용하는 기법

- FCFS(FIFO) + RR 스케줄링 기법을 혼합한 것

- 상위 단계에서 완료되지 못한 작업은 하위 단계로 전단되며 마지막 단계에서는 RR 스케줄링 기법을 사용

- 프로세스 우선순위에 따라 시스템 프로세스, 대화형 프로세스, 편집 프로세스, 일괄 처리 프로레스 등으로 나누어 준비 상태 큐를 상위, 중위, 하위 단계로 배치함

- 각 준비상태 큐는 독자적인 스케줄링을 가지고 있으므로 각 그룹의 특성에 따라 서로 다른 스케줄링 기법을 사용할 수 있음

- 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없음

- 하위 단계 준비상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 단계 준비상태 큐에 프로세스가 들어오면 상위 단계 프로세스에게 CPU를 할당해야 함

​

* 이 게시물은 시나공 교재를 참고로 작성되었습니다.