[CS] CPU 스케줄링

히수·2023년 5월 11일

CS

목록 보기

12/13

CPU 스케줄링

CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업이다.

스케줄링

처리율, CPU 이용률 ↑
오버헤드, 응답시간, 반환시간, 대기시간 ↓

CPU 스케줄링의 유형

선점형 스케줄링 (Preemptive Scheduling)

개념

하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식

장점

비교적 빠른 응답
대화식 시분할 시스템에 적합

단점

높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래함

알고리즘

라운드로빈 (RR)
SRT (Shortest Remaining Time First)
다단계 큐
다단계 피드백 큐

활용

실시간 응답환경, Deadline 응답환경

비선점형 스케줄링 (Non Preemptive Scheduling)

개념

하나의 프로세스가 CPU를 할당받으면 작업종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식

장점

응답시간 예상이 용이하다
모든 프로세스에 대한 요구를 공정하게 처리

단점

짧은 작업을 수행하는 프로세스가 긴 작업 종료시까지 대기

알고리즘

우선순위
기한부
FCFS
HRN (High Response Ratio Next)
SJF (Shortest Job First)

활용

처리시간 편차가 적은 특정 프로세스 환경

선점형 스케출링 알고리즘

라운드 로빈 (Round Robin)

프로세스는 같은 크기의 CPU 시간을 할당, 프로세스가 할당된 시간 내에 처리 완료를 못하면 준비 큐 리스트의 가장 뒤로 보내지고 CPU는 대기중인 다음 프로세스로 넘어간다.
```
	균등한 CPU 점유시간, 시분할 시스템을 사용
```

SRT (Shortest Remaining Time First)

가장 짧은 시간이 소요되는 프로세스를 먼저 수행하고, 남은 처리시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점된다.
```
	짧은 수행시간 프로세스 우선 수행
```

다단계 큐

작업들을 여러 종류 그룹으로 분할, 여러개의 큐를 이용하여 상위단계 작업에 의한 하위단계 작업이 선점당한다.
각 큐는 자신만의 독자적인 스케줄링을 가진다.
```
	독립된 스케줄링 큐
```

다단계 피드백 큐

입출력 위주와 CPU 위주인 프로세스의 특성에 따라 큐마다 서로 다른 CPU 시간 할당량을 부여한다
FCFS와 라운드 로빈 스케줄링 기법을 혼합한 것으로, 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동하고 마지막 단계는 라운드 로빈 방식을 적용한다.
```
	큐마다 다른시간 할당량, 마지막 단계는 라운드로빈 방식으로 처리
```

비선점형 스케줄링 알고리즘

우선순위

프로세스별로 우선순위가 주어지고, 우선순위에 따라 CPU를 할당한다.

동일 순위는 FCFS이다.

	주요/긴급 프로세스에 대한 우선 처리, 자원상황에 따른 우선순위 선정

기한부 (Deadline)

작업들이 명시된 시간이나 기한 내에 완료되도록 계획
```
	요청에 명시된 시간 내 처리를 보장
```

FCFS (First Come First Service)

프로세스가 대기 큐에 도착한 순서에 따라 CPU를 할당함
FIFO 알고리즘이라고도 함
```
	도착한 순서대로 처리
```

SJF (Shortest Job First)

프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 종료 시까지 자원 점유
준비 큐 작업 중 가장 짧은 작업부터 수행, 평균 대기시간 최소화
CPU요구 시간이 긴 작업과 짧은 작업간의 불평등이 심하기때문에 CPU 요구 시간이 긴 프로세스는 기아현상 발생
```
	기아 현상 발생 가능 ↑
```

HRN (High Response Ratio Next)