04 CPU 스케줄링 CPU Scheduling

Presentation on theme: "04 CPU 스케줄링 CPU Scheduling"— Presentation transcript:

1 04 CPU 스케줄링 CPU Scheduling
컴퓨터소프트웨어 B반 (남)이성연

2 1. CPU스케줄링이란? 스케줄링은 다중 프로그래밍을 가능하게 하는 운영체제의 동작 기법이다.

3 2. 스케줄링의 개념 스케쥴되는 프로세스 스케쥴되지 않는 작업 사용자 프로세스 시스템 호출에 의해 발생되는 시스템 프로세스
인터럽트 처리 오류 처리 사용자의 시스템 호출에 있어서의 사전 처리

4 3. 방법 분류 1. 선점(preemptive) 스케쥴링 2. 비선점(nonpreemptive) 스케쥴링
한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 경우 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용 빠른 응답시간을 요구하는 시분할 시스템에 유용 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래 2. 비선점(nonpreemptive) 스케쥴링 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 점유 못함 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야 함 모든 프로세스들에게 공정하고 응답시간의 예측이 가능

5 4. 동적/정적 스케줄링 프로세스의 우선순위 변동 여부에 따라 정적 스케줄링과 동적 스케줄링으로 구분할 수 있다.
정적 스케줄링(Static Scheduling)  프로세스에 부여된 우선순위가 바뀌지 않는다. 고정우선순위 스케줄링이라고도 한다. 동적 스케줄링(Dynamic Scheduling)  스케줄링 과정에서 프로세스의 우선순위를 변동시킨다. 유동우선순위 스케줄링이라고도 한다

6 5. 단계(1) 1단계 스케줄링 2단계 스케줄링 3단계 스케줄링
작업 스케줄링(Job schuduling)이라고도 한다. 어느 작업부터 시스템 내의 자원들을 실제로 사용할 수 있도록 할지를 결정한다. 작업들이 시스템에 들어오는 것을 승인하는 것이기 때문에 승인 스케줄링(Admission scheduling)이라고도 한다. 2단계 스케줄링 어느 프로세스부터 CPU를 차지할 수 있게 할지를 결정한다. 프로세스들을 보류시키고 다시 활성화시키는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절한다. 그렇게 함으로써 시스템을 적절히 운영할 수 있다. 작업 승인(1단계)와 CPU 배당(3단계) 사이의 완충 작용을 한다. 3단계 스케줄링 CPU가 사용가능한 경우 어느 프로세스에게 배당할지를 결정한다.

7 중단(block) 또는 시간만기(timer round)
6. 단계(2) 스케줄링에 있어서 세 개의 중요한 단계가 고려된다. 활성화 (activation) 시스템에서 들어오려 대기하는 작업 작업입력 작업개시 보류 중단(block) 또는 시간만기(timer round) 디스패치 1 단계 스케줄링 2 단계 스케줄링 3 단계 스케줄링

8 7. CPU 스케줄링 알고리즘 비실시간 프로세스 스케줄링 실시간 프로세스 스케줄링
FCFS 스케줄링(First Come First Served Scheduling) SJF 스케줄링(Shortest Job First Scheduling) SRTF 스케줄링(Shortest Remaining-Time First Scheduling) RR 스케줄링(Round Robin Scheduling) HRN 스케줄링 다단계 큐 스케줄링(Multilevel Queue Scheduling) 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling) 실시간 프로세스 스케줄링 RM 스케줄링(Rate Monotonic Scheduling) EDF 스케줄링(Earliest Deadline First Scheduling)

9 8. 프로세스 스케줄링 방법/비교 선점 스케줄링 종류 방법 특징 라운드 로빈 스케줄링
FIFO 방식의 변형으로 일정한 시간을 부여하는 작업 ① 시분할 방식에 효과적 ② 할당 시간이 크면 FIFO와 같다 ③ 할당 시간이 작으면 문맥 교환이 자주 발생 SRT 스케줄링 수행 중 나머지 수행 시간이 적은 작업을 우선 처리하는 방법 작업처리는 SJF와 같으나 이론적으로 가장 작은 대기 시간이 걸린다 MLQ 스케줄링 서로 다른 작업을 각각의 큐에서 시간 할당에 의해 처리하는 방법 각각의 큐는 독자적인 스케줄링 알고리즘 사용 MFQ 스케줄링 하나의 준비 상태 큐를 통해 여러 개의 귀환 큐를 걸쳐 일을 처리하는 것 CPU와 I/O 장치의 효율을 높일 수 있다 FSS 스케줄링 설 관련된 다양한 프로세스 집합을 지원하는 알고리즘 UNIX 환경에 적합

10 9. 프로세스 스케줄링 방법/비교 비선점 스케줄링 종류 방법 특징 우선순위 스케줄링
우선순위를 할당해 우선순위가 높은 순서대로 처리하는 기법 ① 고정적 우선순위 ② 가변적 우선순위 ③ 구입된 우선순위 기한부 스케줄링 프로세스가 주어진 시간 내에 작업이 끝나도록 계획한다 ① 마감 시간을 계산해 야하기 때문에 막대한 오버헤드와 복잡성이 발생 FIFO 스케줄링 작업이 컴퓨터에 들온 순서대로 수행하는 방법 ① 대화형에 부적합 ② 간단하고 공평하다 ③ 반응 속도를 예측 가능 SJF 스케줄링 수행 시간이 적은 작업을 우선적으로 처리하는 방법 작은 작업에 유리하고 큰 작업은 상당한 시간이 많이 걸린다 HRN 스케줄링 SRT의 큰 작업이 시간이 많이 걸리는 점을 보완한 방법 우선순위=(대기시간+수행시간)/수행시간

11 10. 평가 기준 스케줄링 알고리즘은 다음과 같은 기준을 통해 평가할 수 있다.
CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율. 처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수. 응답 시간(Response Time) : 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간. 대기 시간(Waiting Time) : 프로세스가 준비 큐 내에서 대기하는 시간의 총합. 턴어라운드 시간(Turnaround Time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간.