[CPU스케쥴러]

※CPU스케줄링

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의 타임 슬라이스를
부여
- 짧은 작업에 유리, 입출력 위주의 작업에 우선권을 줌
- 하위단계 큐일수록 할당시간은 커진다



※프로레스 스케쥴링 기법
1. preemptive 기법(선점 기법)
하나의 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 빼앗을 수 있는 방법.
1) Round Robin 스케줄링: FIFO와 같은 방법이지만, 주어진 시간 할당량 안에 작업을
마쳐야 하며, 할당량을 다 소비하고도 작업이 끝나지 않은 프로세스는 다시 대기 큐의
맨 뒤로 돌아가는 방법.
2) SRT 스케줄링: 실행시간 추정치(남은 시간)가 가장 적은 프로세스에게 먼저
CPU를 할당하는 방법.
3) MFQ(다단계 피드백 큐) 스케줄링: 작업처리를 여러 단계로 나누어 처리하는 기법으로
높은 단계에서는 시간 할당량을 짧게 주고, 낮은 단계로 갈수록 시간 할당량을 많이
주고 마지막 단계는 RR기법으로 처리.

2. non-preemptive 기법(비선점 기법)
프로세스에게 이미 할당된 CPU를 강제로 빼앗을 수 없고, 사용이 끝날 때까지 또는
CPU를 할당 받은 프로세스가 스스로 넘길 때까지 기다려야 하는 방법.
1) FIFO 스케줄링: 대기 큐에 먼저 들어온 작업에게 CPU를 먼저 할당.
2) SJF 스케줄링: 작업 시간이 가장 적은 프로세스에게 CPU를 먼저 할당하는 기법.
3) HRN 스케줄링: 우선 순위에 의한 방법.