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

내용출처 : http://info.plusmail.co.kr/study_6.htm
Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요