스케줄링, Scheduling
컴퓨터 시스템의 모든 자원을 효율적으로 사용하기 위한 프로세스 관리 정책
하나의 프로세스가 끝나고 다음으로 수행할 프로세스를 선택할 때, 어떤 프로세스를 선택할지에 대한 기준이 되는 알고리즘을 CPU 스케줄링 알고리즘 이라 함
Schduling Criteria
스케줄링의 성능을 비교하는 지표들
CPU 스케줄링의 기본적인 목표 중 하나는 프로세스들의 기다리는 시간을 줄여, 가능한 한 신속하게 처리될 수 있도록 하는 것이다. 그 외에도 CPU 스케줄링의 목표 및 기준이 되는 지표들이 있다!
사용자 관점
-
Turnaround Time (반환 시간)
프로세스의 처음 시작 시간 부터 모든 작업을 끝내고 종료할 때 까지 걸린 시간
(CPU, waiting, I/O 등 모든 시간을 포함) -
Waiting Time (대기 시간)
CPU를 점유하기 위해 대기 열 (ready queue)에서 기다린 시간
(다른 큐에서 기다린 시간은 제외) -
Response Time (응답 시간)
일반적으로 대화형 시스템에서 입력에 대한 반응 시간
시스템 관점
-
CPU Utilization (CPU 이용률)
총 경과 시간 대비 프로세스에 CPU가 이용되는 시간의 비율 -
Throughout (처리율)
단위 시간당 처리하는 작업의 수
CPU 스케줄링 알고리즘
구체적인 CPU 스케줄링 알고리즘을 알아보기 전 선점, 비선점의 개념을 잡고 가자!
💡선점
현재 CPU 시간을 할당 받아서 특정 프로세스가 실행 중일지라도, 필요에 의해 다른 프로세스가 CPU 시간을 강제적으로 빼앗을 수 있음
💡비선점
현재 어떠한 프로세스가 CPU 시간을 할당받아 실행 되고 있다면 다른 프로세스는 현재 프로세스가 완료될 때 까지 CPU 시간을 할당 받을 수 없음
1. FCFS, First Come First Served
- 먼저 요청 된 순서대로 프로세스 실행
- 비선점
- 장점
- 높은 자원 사용 효율
- 일괄 처리 시스템에 적합
- 단점
- 평균 응답 시간이 길어짐 (앞에서 장시간 cpu를 사용하는 경우 기다려야 함)
- 대화형 시스템에 적합하지 않음
case 1과 같은 경우를 Convoy Effect라 함!
💡 Convoy Effect
CPU 시간을 오래 사용하는 프로세스가 먼저 수행되는 동안, 나머지 프로세스들은 그 만큼 오래 기다리는 것
2. SJF, Shortest Job First
- 작업 시간이 짧은 순서대로 프로세스 실행
- 작업 시간이 동일하다면 먼저 요청된 프로세스 부터
- 선점, 비선점 모두 사용 가능
- 장점
- 평균 대기 시간과 시스템 내의 대기 프로세스 수를 최소화하고, 다수의 프로세스에게 빠른 응답 제공됨
- 단점
- 무한 대기가 발생할 수 있음, 프로세스 생성 시 총 실행 시간에 대한 정확한 계산이 불가능
평균 대기 시간은 SJF 알고리즘이 가장 짧은 것이 이미 수학적으로 증명되어 있다.
하지만 사실은 비현실적인 알고리즘인데, 실제 컴퓨터 환경에서는 프로세스의 CPU 점유 시간을 알 수 없기 때문이다.
프로세스 실행 중에는 여러가지 변수가 존재하기 때문에 프로세스의 CPU 점유 시간을 알기 위해서는 실제로 실행하는 방법 뿐이다. 실제로 측정한 시간을 이용해 알고리즘을 이용할 수도 있지만 이는 오버헤드가 매우 크다!
3. Priority, 우선 순위
- 우선순위가 높은 순서대로 CPU를 할당
- 우선순위가 같다면 FCFS로 결정
- 우선순위는 일반적으로 정수 값으로 나타내어지고, 작은 값이 우선순위가 높다! (Linux/Unix)
- 선점, 비선점
- 단점
- 우선순위가 낮은 프로세스는 영구 대기 또는 기아 현상이 발생 가능
💡 우선순위를 정하는 방법
- Internal (내부적 요소)
time limit, memory requirement, I/O to CPU burst (I/O 작업을 길고, CPU 작업은 짧은 프로세스 우선) 등- External (외부적 요소)
amount of funds being paid, political factors 등
💡 Starvation, 기아 현상
CPU의 점유를 오랫동안 하지 못하는 현상
Priority 스케줄링 방식에서 우선순위가 매우 낮은 프로세스가 ready queue에서 대기할 경우 오랫동안 기다려도 CPU를 점유하지 못할 가능성이 큼
-> 기아 현상을 해결하는 방법 중 하나는 Aging!
💡 Aging, 에이징
프로세스가 ready queue에서 대기 중 일정 시간이 지나면 우선 순위를 일정량 높여주는 방법
4. RR, Round Robin
- 모든 프로세스가 돌아가며 스케줄링 됨
- 시간 조각 (time slice, time quantum) 이라는 작은 시간을 정의하고 이 시간이 경과 하면 현재 프로세스를 대기 상태로 보내고 다음 프로세스를 수행
- 시분할 시스템에서 사용
- 응답 시간이 짧아 대화형 시스템에 적합
- 선점 (한 프로세스가 종료되기 전에 time slice가 끝나면 다음 프로세스로 CPU를 넘겨줌)
- 단점
- 알고리즘 성능이 time-slice 에 의존적
- 시간 조각의 크기가 크면 FCFS 와 유사하지만, 크기가 작으면 잦은 context switching 에 따른 오버헤드 발생
5. 다단계 큐
- 프로세스를 성격에 따라 여러 그룹으로 나누어 각 그룹별로 큐를 두어 사용
- 큐마다 우선 순위 지정 가능
💡 프로세스 그룹
- System Process : 운영체제 커널 수준의 프로세스
- Interactive Process : 유저 수준의 대화형 프로세스
- Batch Process : 대화형 프로세스의 반대, 일정량을 한번에 처리하는 프로세스 (ex, 컴파일러)
- Student Process
- Interactive Editing Process
ex) system process는 커널 수준에서 중요한 작업이므로 우선 순위 높음, batch process 는 운영 체제의 개입이 매우 적으므로 우선 순위가 가장 낮다고 볼 수 있음
6. 다단계 피드백 큐
- 모든 프로세스는 가장 위 쪽 큐에서 대기
- 기다리는 시간이 너무 길어지면 아래의 큐로 프로세스를 옮겨서 대기 시간을 조정
- 각 큐마다 다른 스케줄링, 다른 우선순위 등을 사용할 수 있음
- 만약 우선순위가 낮은 아래의 큐에 있는 프로세스에 기아 현상이 발생하면 우선순위가 높은 위쪽 큐로 옮길 수 있음
대부분의 상용 운영체제는 여러개의 큐를 사용, 각 큐마다 다른 스케줄링 방식을 사용한다. 프로세스의 성격에 맞는 스케줄링 방식을 사용하여 최대한 효율적으로 CPU를 운영한다.
그 외 알고리즘
💡 SRTF, Shortest Remaining Time First
- SJF 알고리즘의 선점 방식
- 새로운 프로세스가 들어오면, 각 task들의 남은 수행 시간을 비교하여 가장 짧은 프로세스에게 CPU를 할당
- 단점
- 프로세스 생성 시 총 실행 시간 추정에 대한 작업이 필요함
- 잦은 선점이 발생하여 context switching 에 따른 오버헤드 발생 -> 프로세스들의 응답 시간 길어짐
- 현실적으로 구현하여 사용하기가 어렵다
Reference
