[출처] http://park1020.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%9D%B4%EB%A1%A0%EC%A4%91%EC%97%90%EC%84%9C-CPU%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EA%B8%B0%EB%B2%95
CPU스케줄링
■ CPU 스케줄링의 개념: 프로세스들의 수행 순서를 정해 주는 것. - 준비 상태에 있는 프로세스 중에서 어느 프로세스에게 CPU를 할당할 것인지 결정.
■ CPU 스케줄링의 필요성: 여러 프로세스가 한 job을 수행하는데 CPU가 줄 곧 필요하지 않다. 계산을 할 때는 CPU가 필요하지만, I/O를 할 때는 필요 없다. 이때 CPU를 다른 프로세스가 이용하면 전체적인 시스템의 효율은 올라간다.
프로세스 A 처리 I/O 처리 I/O
프로세스 B 처리 I/O 처리 I/O
이렇게 CPU를 여러 프로세스가 번갈아 가면서 사용하면 효율적이다.
■ 스케줄링의 분류: ‧ 단기 스케줄링(short-term scheduling) : 준비 상태 프로세스중에서 한 프로세스를 선택하여 CPU 할당. ‧ 중기 스케줄링(medium-term scheduling) : 메모리에 프로세스가 너무 많은 경우, 메모리에 있는 프로세스를 선정하여 디스크로 보낸다. 나중에 다시 올 수 있다(swapping). ‧ 장기 스케줄링(long-term scheduling) : 생성(상태)에 있는 프로그램들 중에서 필요한 프로세스를 생성하여 준비에 넣는다.
■ 스케줄링 기준(용어): ‧ CPU 사용률 : 실제 CPU 사용 시간 / 전체 시간 ‧ 처리율(throughput) : 단위 시간당 완료되는 작업 수 ‧ 반환시간(turnaround time) : 시스템에 들어가서 마치고 나온 시간 간격 메모리에 들어가기 위해 기다리는 시간, 준비 큐에서 기다리는 시간, 프로세서에서 실행되는 시간, 입출력 시간을 합친 것 (I/O에 영향 多) ‧ 대기시간(waiting time) : 준비 큐에서 기다린 시간 ‧ 응답시간(response time) : 제출 --> 첫 번째 응답까지의 시간. 1) 정의
- 작업을 처리하기 위해 프로세스들에게 중앙처리 장치나 각종 처리기들 을 할당하기 위한 정책을 계획하는 것
2) 방법별 분류
① 선점(preemptive) 스케쥴링 - 한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세 스를 중지시키고 자신이 CPU를 차지할 수 있는 경우 - 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용 - 빠른 응답시간을 요구하는 시분할 시스템에 유용 - 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래
② 비선점(nonpreemptive) 스케쥴링 - 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 점유못함 - 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야 함 - 모든 프로세스들에게 공정하고 응답시간의 예측이 가능
3) CPU 스케쥴링 알고리즘별 분류
① 우선순위(priority) 스케줄링 - nonpreemptive - 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리
ㄱ) 정적(static) 우선순위 방법 - 주변 환경 변화에 적응하지 못하여 실행중 우선순위를 바꾸지 않음, 구현이 쉽고 오버헤드가 적다 ㄴ) 동적(dynamic) 우선순위 방법 - 상황 변화에 적응하여 우선순위를 변경, 구현이 복잡, 오버헤드 많다, 시스템의 응답속도를 증가시켜 효율적
② 기한부(deadline) 스케줄링 - nonpreemptive - 작업을 명시된 시간이나 기한내에 완료되도록 계획 - 작업시간이나 상황등 정보를 미리 예측하기가 어렵다
③ FIFO 스케줄링 - nonpreemptive - 프로세스들은 대기 큐에 도착한 순서대로 CPU를 할당 받는다 - 일괄처리 시스템에서 주로 사용, 작업 완료 시간을 예측하기 용이 - 짧은 작업이 긴 작업을 기다리게 됨 - 중요하지 않은 작업이 중요한 작업을 기다리게하여 불합리
④ 라운드로빈(round robin) 스케줄링 - preemptive - FCFS에 의해서 프로세스들이 보내지며 - 각 프로세스는 같은 크기의 CPU 시간을 할당 받는다 - 시분할 방식에 효과적, 할당시간의 크기가 매우 중요 - 할당시간이 크면 FCFS와 같게되고, 작으면 문맥교환이 자주 일어난다
⑤ SJF(shortest job first) 스케줄링 - nonpreemptive - 준비큐내의 작업중 수행시간이 가장 짧다고 판단되는 것을 먼저 수행 - FCFS보다 평균 대기 시간을 감소, 큰 작업은 시간 예측이 어렵다 - 짧은 작업에 유리
⑥ SRT(short remaining time) 스케줄링 - preemptive - 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행 - 남은 처리 시간이 더 짧다고 판단는 프로세스가 준비큐에 생기면 언제라도 실행중인 프로세스가 선점됨 - 긴 작업은 SJF보다 대기 시간이 길다
⑦ HRN(highest response ratio next) 스케줄링 - nonpreemptive - 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법 - 짧은 작업이나 대기시간이 긴 작업은 우선순위가 높아진다
⑧ 다단계 큐(multilevel queue) 스케줄링 - preemptive - 작업들을 여러 종류의 그룹으로 나누어 여러개의 큐를 이용하는 기법
⑨ 다단계 피드백 큐(multilevel feedback queue) 스케줄링 - preemptive - 입출력 위주와 CPU 위주인 프로세스의 특성에 따라 서로 다른 CPU의 타임 슬라이스를 부여 - 짧은 작업에 유리, 입출력 위주의 작업에 우선권을 줌 - 하위단계 큐일수록 할당시간은 커진다 |