CPU Scheduling 정리

Kang In Sung·2021년 2월 9일

운영체제

OS

목록 보기

3/6

CPU 스케쥴링

프로세스 스케쥴링

프로세서의 개수가 많아지면 각 프로세스들의 스케쥴링 방법은 다양해질 수 밖에 없다.
프로세스 스케쥴링은 운영체제에서 기본적으로 제공한다.
디스패치 (Dispatch) : 운영체제가 프로세스를 프로세서에 할당하는 작업. (ready -> running)
- CPU 스케쥴링 요소에 반드시 포함된다.
- 작업 중에 문맥 교환 (Context Switching) 작업이 일부 발생할 수 있다.
CPU 실행 시간 + 입/출력 대기 시간 = 프로세스 실행 시간
- 대부분 CPU 실행 시간 < 입/출력 대기 시간

스케쥴링 기준 요소

CPU 사용 : 사용률이 40 ~ 60 % 인 프로세스가 제일 적합하다.
처리량 : 단위 시간 당 실행 완료된 프로세스 개수.
총 처리 시간 : 대기 시간 + CPU 실행 시간 + 입/출력 대기 시간
- 대기 시간 : 대기 큐에서 머무른 시간
- 응답 시간 : 응답 시작 시간 (대화식 시스템에서 특히 요구)
최적화된 시간은 평균 측정 시간으로 가정을 한다.

선점 / 비선점 방식

선점 방식 : 프로세스의 사용권을 운영체제에게 맡기는 방식
- 프로세스 실행 중에 다른 프로세스를 실행할 수도 있다.
- 프로세스 상태가 (준비 -> 실행) / (인터럽트 발생) 으로 바뀌는 경우.
- 최신 운영체제의 CPU 스케쥴링 방식은 이를 채택한다.
- 다수의 프로세스가 경쟁하기 때문에 데이터의 일관성이 깨질 수도 있다.
- 문맥 교환이 운영체제에 의해 마음대로 이뤄지게 된다.
비선점 방식 : 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식
- 프로세스가 끝나야 다음 프로세스를 실행할 수 있다.
- 프로세스 상태가 (실행 -> 대기) / (프로세스 종료) 로 바뀌는 경우.
- 문맥 교환이 자발적으로 이뤄지게 된다.

FCFS (First Come, First Served)

Pn : (실행 시간 / 대기 시간)
|---------------| P1 : 15 ms / 0 ms 
|----------| P2 : 10 ms / 2 ms
|------------| P3 : 12 ms / 4 ms

|---------------|----------|------------|
       P1            P2          P3
0              15          25           37

Avg Wait Time : (0 + 13 + 21) / 3 = 약 11.3 ms

CPU 에 요청이 빠른 프로세스를 우선 할당하는 방식
Queue 만 사용하면 충분히 구현할 수 있음
호위 효과 (Convoy Effect) 발생
- 수행 시간이 긴 프로세스가 점령해서 오랫동안 기다려야 하는 현상.
- 프로세스의 순서에 따라 대기 시간의 차이가 천차만별이다.
비선점 스케쥴링 방식이다.

SJF (Shortest Job First)

Pn : (실행 시간 / 대기 시간)
|---------------| P1 : 15 ms / 0 ms 
|----------| P2 : 10 ms / 2 ms
|------------| P3 : 12 ms / 4 ms

|----------|------------|---------------|
     P1          P2            P3
0          10          22               37

Avg Wait Time : (0 + 8 + 16) / 3 = 8 ms

수행 시간이 짧은 프로세스를 우선 할당하는 방식
비선점 스케쥴링 방식이다.
FCFS 의 호위 효과를 해결할 수 있다.
CPU 측에선 수행 시간에 대하여 예측하기 힘들다.
실행 시간이 가장 긴 프로세스에 대한 기아 (Starvation) 현상이 발생한다.

SRTF (Shortest Remaining Time First)

Pn : (실행 시간 / 대기 시간)
|--------| P1 : 8 ms / 0 ms 
|----| P2 : 4 ms / 1 ms
|---------| P3 : 9 ms / 2 ms
|-----| P4 : 5 ms / 3 ms

|-|----|-----|-------|---------|
P1  P2    P4     P1       P3
0 1    5     10      17       26

Avg Wait Time : (0 + 8 + 16) / 3 = 8 ms

SJF 알고리즘의 기아 현상을 해결하기 위한 스케쥴링 기법
- 다만 선점형 스케쥴링 방식이다.
프로세스에서 남은 수행 시간이 짧은 순서에 따라 할당을 한다.
계산 과정이 SJF 보다 까다로울 수 밖에 없다.

RR (Round Robin)

Pn : (실행 시간 / 대기 시간)
Time Quantum : 4 ms
|---------------| P1 : 15 ms / 0 ms 
|----------| P2 : 10 ms / 2 ms
|------------| P3 : 12 ms / 4 ms

|----|----|----|----|----|----|----|--|----|---|  
  P1   P2   P3   P1   P2   P3   P1  P2  P3   P1
0    4    8    12   16   20   24  28  30  34   37

Avg Wait Time : (0 + 2 + 4) / 3 = 2 ms

시간 할당을 위한 Time Quantum (할당량) 이 존재한다.
- 이에 따라 문맥 교환 횟수가 달라질 수 있다.
- 문맥 교환 시간이 약 10 ms 이라 짧진 않은 편이다.
초창기 시분할 시스템을 위해 설계되었다.
선점형 스케쥴링 방식이다.
- 운영체제가 시간 할당량에 따라 개입을 하기 때문이다.

우선순위 (Priority)

Pn : (실행 시간 / 대기 시간 / 우선 순위)
Time Quantum : 4 ms
|---------------| P1 : 15 ms / 8 ms / 3rd
|----------| P2 : 10 ms / 0 ms / 1st
|------------| P3 : 12 ms / 4 ms / 2nd

|----------|------------|---------------|
     P2          P3            P1
0          10           22              37

Avg Wait Time : (0 + 6 + 14) / 3 = 약 6.6 ms

특정 정보를 기준으로 우선 순위를 두어 프로세스 스케쥴링을 결정하는 기법이다.
- 순위 요소 : 시간, 메모리, 입/출력 빈도, 파일 개수 등.
- 우선 순위는 자격증 같이 숫자가 낮아야 높은 우선 순위이다.
에이징 (Aging) 기법을 활용해 실행하지 않은 프로세스에 대하여 정리 가능하다.
선점형, 비선점형 스케쥴링이 가능하다.
특정 스케쥴링에 대해 몰리는 현상이 일어나 기아 상태를 고려해야 한다.

다단계 큐 스케쥴링

일반적인 스케쥴링에 비해 여러 개의 큐를 사용하는 스케쥴링 기법.
우선 순위에 따라 큐를 준비해둔다.
- 우선 순위라기 보다 용도 별로 나뉘어둔 것일 수도 있다.
- 다만 스케쥴링은 큐 사이를 이동할 수 없다.
큐들을 주기 별 선형 탐색을 병행하면서 스케쥴링을 진행한다.
- 초반에는 각 큐 별로 스케쥴링이 있는지를 판단한다.
- 큐 안에서 사용하는 스케쥴링은 우선순위에 따라 달라질 수 있다.
대화형 및 배치 프로세스는 낮은 순위로 설정한다.
실시간 및 시스템 프로세스는 높은 순위로 설정한다.

다단계 피드백 큐 스케쥴링

다단계 큐 스케쥴링에 동적으로 우선 순위를 변화할 수 있게 하는 기법.
가장 하위 큐는 FCFS 스케쥴링 기법을 사용한다.
큐 단계가 오를수록 시간 할당량 (Time Quantum) 이 줄어든다.
에이징 (Aging) 기법을 제공하여 기아 상태를 방지할 수 있다.

쓰레드 스케쥴링

대부분 쓰레드 스케쥴링 기법은 프로세스와 크게 다르지 않음.
쓰레드의 스케쥴링을 위한 경쟁 구도는 아래와 같다.
- 프로세스 경쟁 범위 : 동알한 프로세스에 속한 쓰레드 사이의 경쟁. 우선 순위에 따라 스케쥴링이 결정된다.
- 시스템 경쟁 범위 : 커널이 CPU 상의 어느 커널 쓰레드에게 스케쥴 기회를 줄지 결정한다.

다중 프로세서 스케쥴링

비대칭 다중처리
- 1개의 CPU 코어만 다른 시스템에 접근한다.
- Master - Slave 관계를 형성하게 된다.
- Master 가 각 프로세서에게 특정 태스크를 할당 시킨다.
- Master 만이 스케쥴링을 관리하게 된다.
  - Master 가 Slave 보다 성능 저하의 영향을 많이 받는다.
대칭 다중처리
- 여러 프로세서들이 1개의 공유된 메모리를 사용하는 구조.
- 각 프로세서들은 평등한 관계를 형성하게 된다.
  - 경쟁 구도가 생겨 기아 현상이 발생할 수도 있다.
로드 밸런싱 (Load Balancing) : 여러 CPU 혹은 메모리를 사용하여 진행 중인 작업을 나누는 기법.
- 분산 처리 시스템을 예로 들 수 있다.
- Scale-Out 개념과 매우 관련되어 있다.
- 대칭 다중처리의 기아 현상을 방지할 수 있다.
- Push / Pull 마이그레이션을 사용한다.
이기종 다중처리 (Heterogeneous Multiprocessing)
- 모바일 시스템의 전력 소비를 최소화하여 CPU 클록 속도를 향상 시키기 위한 기법.