SJF
- First-Come, First-Served (FCFS) Scheduling
- 간트차트 : 프로젝트 관리에 사용하는 가로축(시간축)에 따른 일의 진행을 표시한 것
- ex)프로젝트(캡스턴)의 진행상황 기록 - 몇 개월간의 계획(시간 순)
- 한 프로젝트에 대한 전체 일들이 시간순으로 연결될 수도 있음 - 팀장들이 체크할 것들을 확인 할 수 있음
- 선입선출의 방식으로 먼저 들어온 것이 먼저 실행되는 스케줄링 기법
- 대기시간을 구해보자
- P1은 오자마자 실행 되었으므로 0초를 기다림
- P2는 P1의 실행시간동안 기다림 - 24초
- P3는 P1과 P2의 실행시간을 모두 기다림 - 27초
- 만약 순서를 달리한다면?
- P2 -> P3 -> P1순으로 처리한다면 평균 대기시간이 줄어듦
- 여기서 알 수 있는 사실은 실행시간이 짧은 프로세스를 먼저 처리한다면 더 효율적이라는 것을 알 수 있음
- 비선점 방식의 스케줄링이 발생하는 경우
- 한 프로세스가 모두 실행되어 종료 됐을 때(termination)
- I/O 입출력을 기다릴 때 -> waiting으로 갈 때
- Shortest-Jop-First(SJF) Scheduling
- CPU가 비어있을 경우 가장 서비스 시간이 짧은 프로세스를 할당
- 비선점형방식과 선점형방식의 차이가 있음
- 비선점형
- 가장 짧은 수행시간을 가진 P4가 가장먼저 실행
- P4가 모두 실행되고 termination되고 스케줄링이 발생
- P1이 수행 -> termination -> P3 -> termination -> P2
- 총 24초가 걸리고 평균 대기시간은 (0 + 3 + 9 + 16)/4 = 7초
- 선점형에서 스케줄링이 발생하는 경우 - ready queue에 상태가 변했을 경우
- 프로세스가 running상태에서 ready상태로 전환 - 할당된 시간이 끝났을 경우, 다른 시스템 콜(interrupt)이 발생했을 경우, 더 우선순위의 프로세스가 ready queue에 들어왔을 경우 ready상태로 들어가 스케줄링이 발생
- 프로세스가 waiting상태에서 ready로 전환 - waiting에서 I/O를 끝내고 ready로 가서 스케줄링이 발생
- 도착시간이 각기 다른 4개의 프로세스를 보았을 때 P1은 0초에서 먼저 실행되기 시작
- 2초가 지난 후 P2가 들어오게 되고 P2는 4초의 시간이 걸리므로 우선순위가 더 높음 -> P1이 멈추고 ready queue로 들어오고 다시 스케줄링이 발생(SJF - 짧은 시간의 작업이 먼저 실행)
- P2가 실행되는 중 2초가 흐른 후 P3가 ready queue에 들어오고 스케줄링이 다시 발생
- P3가 가장 짧은 작업시간을 가지므로 P3가 실행됨
- P4가 들어왔을 때, P3가 종료되고 CPU가 비어서 자연스럽게 스케줄링이 발생 - 선점형, 비선점형 둘 다 해당
- P2 -> P4 -> P1의 순서로 종료됨
- P1의 waiting time : 9, P2 의 waiting time : 1, P3 waiting time : 0, P4 waiting time : 2
- Determining Length of Next CPU Burst
- 실제로 진행한, 방금 지나간 실제 길이 tn
- 예측하는 다음 시간(타우 n+1), 예측된 이전 시간(타우 n)
- 0에서 1사이의 값 - 보통 0.5
- 공식
- Shortest-remaining-time-first(SRTF) - 선점형 방식
- 남은시간이 가장 짧은 작업부터 실행 - SJF 방식에서 발전
- P1이 수행중에 1초 후 P2가 들어와서 P1의 남은시간 7초와 P2의 4초를 비교 후 스케줄링
- P2를 실행, 2초째에 P3가 도착하지만 스케줄링 결과 여전히 P2가 1위이기 때문에 P2계속 진행
- P4가 도착해도 마찬가지이고 P2가 모두 실행된 후 스케줄링에 의해 P4 -> P1 -> P3순으로 진행
- 대기시간은 P1 : 9, P2 : 0, P3 : 15, P4 : 2
- 평균 대기시간은 26/4 = 6.5
- Priority Scheduling - 우선순위 스케줄링
- 우선순위가 프로세스들에게 할당됨 -> 우선순위를 비교하여 스케줄링
- ready queue에 도착한 순간 실행중인 프로세스와 우선순위를 비교, 더 높으면 실행중인 프로세스를 빼내는 선점형, 기다려주는 비선점형의 두 가지가 있음
- 문제 : 우선순위가 높은 프로세스가 계속 들어오게 되면 우선순위가 낮은 프로세스는 계속 기다리게 되는 무한정지(Starvation) 발생
- Aging : 스케줄링이 생길때마다 우선순위를 한단계씩 높여줌
- 우선순위의 숫자가 낮을수록 우선순위가 높다고 생각하자
- P2 -> P5 -> P1 -> P3 -> P4
- 어느정도의 적당한 시간 크기를 가지는 할당량을 줌
- 이 시간동안 프로세스를 실행한 후 끝나지 않으면 ready queue의 가장 뒤로 보냄
- 원형 큐의 형태로 구현
- CPU 스케줄러는 돌아가면서 시간을 할당
- (n-1)*q이상은 기다리지 않는다.
- 20초가 Time Quantum이라고 했을 때의 간트 차트이다.
- P1이 20실행 후 P2가 17초, P3 20초, P4 20초.... 이렇게 순서대로 수행한다.
- 평균적으로 SJF방식보다 평균 소요시간은 높지만 응답은 높다.
- Quantum을 너무 길게하면 FCFS와 같아지고 너무 짧게하면 지연시간이 많이 발생한다.
- Priority Scheduling w/ Round-Robin
- RR과 우선순위 스케줄링을 묶은 방식
- 우선순위가 같은 경우 RR형식으로 수행, 그 외에는 그냥 우선순위가 높은 것을 먼저 처리