스케줄링 계산

학습 목표

간트 차트로 실행 구간을 확정한 뒤 시간을 계산한다.

본문

핵심 이론

FCFS는 도착 순서, 비선점 SJF는 준비된 작업 중 짧은 서비스 시간, SRT는 가장 짧은 잔여시간을 기준으로 선점한다. 아직 도착하지 않은 작업은 후보가 아니다.

RR은 시간 할당량마다 준비 큐 뒤로 보내며 종료된 작업은 다시 넣지 않는다. 같은 시각의 새 도착과 재삽입 순서는 문항 조건을 따른다.

HRN의 응답비율은 (대기시간+서비스시간)/서비스시간이며 가장 큰 값을 고른다. 선택할 때마다 현재까지의 대기시간을 다시 계산한다.

반환시간=완료−도착, 최초 응답시간=최초 실행−도착이다. I/O가 없는 기본 문제에서 대기시간=반환−CPU 서비스시간이다. I/O 대기까지 포함된 문제는 준비 큐 대기와 따로 분리한다.

완료 시각을 구한 다음 시간을 계산한다

반환시간은 완료−도착, 대기시간은 반환−CPU 실행시간으로 계산한다. 지문에 별도 입출력 시간이 없는 기본 스케줄링 모델의 식이다. 준비 큐에 없는 작업을 미래의 짧은 실행시간만 보고 먼저 고르지 않는다.

도착이 모두 0이고 실행시간이 A=5, B=2, C=1인 비선점 SJF는 C→B→A 순서다.

평균 대기는 (0+1+3)/3이다. SRT는 새 작업이 도착할 때 남은 실행시간을 비교해 선점할 수 있다. RR은 시간 할당량이 끝나면 남은 작업을 큐 뒤로 보내며 도착·재삽입이 같은 시각일 때 지문의 순서를 따른다. HRN은 (대기+실행)/실행의 값이 큰 작업을 고른다.

간트 차트에 각 종료·도착·선점 시점을 표시하고 그때마다 준비 큐를 다시 적는다. 마지막에 완료 시각 표로부터 요구한 대기·반환·평균을 계산한다. 실행 순서만 맞고 물은 시간 종류를 잘못 쓰는 실수를 막을 수 있다.

풀이 예시

단일 CPU에서 SRT(최단 잔여시간 우선)로 다음 프로세스를 실행한다. 잔여시간이 같으면 현재 실행 중인 프로세스를 계속 실행하고, 그 외 동률은 도착 순서로 정한다. 문맥교환 비용과 I/O는 없다. A,B,C의 완료 시각을 순서대로 쓰시오.

① 10, ② 5, ③ 3