스케줄링: 개요
컴퓨터 시스템 개발 이전에 생산 관리 분야에서 개발되었으며 컴퓨터에 적용된 스케줄링 원칙!
📌 배운 것
워크로드(workload)
프로세스들이 실행되는 상황
워크로드를 잘 알수록 그에 맞게 정책을 만들 수 있을 있다.
핵심 가정
- 모든 작업은 같은 시간 동안 실행된다.
- 모든 작업은 동시에 도착한다.
- 각 작업은 시작되면 완료될 때까지 실행된다.
- 모든 작업은 CPU만 사용한다.(즉, 입출력을 수행하지 않는다.)
- 각 작업의 실행 시간은 사전에 알려져 있다.
스케줄링 평가 항목(평가 기준)
반환시간(Trunaround time) = 완료시간 - 도착 시간
반환시간 ⇔ 성능 지표
하지만, 성능을 높이고자 몇몇 작업의 실행을 중지하면 공정성(fairness)이 떨어진다.
📌 기본접근법
비선점(non-preemptive)
프로세스 일괄처리
선입선출
FIFO, First In First Out
FCFS, First Come First Served
장점 : 단순하고 구현이 쉽다. 우리의 가정 하에서는 매우 잘 동작한다.
문제점: convoy effect 짧은 시간 동안 자원을 사용하는 프로세스들이 오랫동안 사용하는 프로세스의 종료를 기다리는 현상으로 인해 평균 반환 시간이 길다.
최단 작업 우선
SJF, Shortest Job First
고객 만족을 중요시 하는 마트라면, 적은 개수의 물건을 구매한 사람들은 계산대를 마냥 기다리지 않도록 소량 구매 계산대를 갖추고 있다. 이와 같이 가장 짧은 실행 시간을 가진 작업을 먼저 실행시키는 작업 스케줄링이다.
장점 : 모든 작업이 동시에 도착한다면, 최적(optimal)의 스케줄링 알고리즘이다.
단점 : 모든 작업이 동시에 도착하지 않는다면(즉, (B,C)가 10초 늦게 도착한다면) 평균 반환 시간은 103.33초((100+(110-10)+(120-10))/3)으로 성능이 나쁘다.
📌 선점형 스케줄러
preemptive
현재 프로세스의 실행을 중단하고 문맥교환을 수행해 다른 프로세를 재개 또는 시작 시킬 수 있음
최소 잔여시간 우선
STCF, Shortest Time-to-Completion First
장점 : 작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하며, 평가 기준이 반환 시간 하나라면, STCF는 최적의 스케줄링 정책이다.
문제점 : 시분할 컴퓨터의 등장으로 응답시간도 성능지표에 중요한 부분이 됨.
스케줄링 평가 항목(평가 기준)
- 반환시간(Trunaround time) = 완료시간 - 도착 시간
- 응답시간(response time) = 처음 스케줄 될 때까지의 시간 - 도착 시간
라운드 로빈
RR, Round-Robin
작업이 끝날 때까지 기다리지 않고 일정 시간동안 실행한 후 실행 큐에 다음 작업으로 전환한다.
타임 슬라이드(time slice) 또는 스케줄링 퀀덤(scheduling quantum)은 타이머 인터럽트 주기의 배수여야 한다.
장점 : 그림 10.6의 응답시간((0+5+10)/3 =) 5초, 그림 10.5의 응답시간은 ((0+1+2)/3 =) 1초로, 응답시간 기준으로 성능이 좋아진다.
문제점 : 타임 슬라이드를 너무 짧게 지정하면 문맥교환비용이 커져 전체 성능에 영향을 준다. 문맥교환 비용을 상쇄할 수 있는 만큼 길어야 하지만, 그렇다고 응답시간이 너무 길어지면 안된다.
비용의 상쇄
일반적 상쇄(amortization) 기술은 문맥교환이 차지하는 비용을 1% 미만으로 설정하는 것이다.
예를 들어, 문맥교환에 1 msec의 비용이 소요된다면 타임슬라이싱을 100msec이상으로 늘리는 방법
문맥교환 비용
레지스터를 저장, 복원하는 작업 뿐만 아니라, CPU 캐시, TLB, 분기 예측 등을 비롯하여 하드웨어에도 프로그램과 관련된 다양한 작업 정보들이 저장되어 있다. 작업이 전환되면 이 정보들은 모두 갱신되어야 하는데, 갱신 작업이 매우 큰 성능 비용을 유발한다.
정리
SJF, STCF : 반환 시간을 최적화하지만, 응답시간이 나쁘다.
RR : 응답시간을 최적화하지만, 반환시간이 나쁘다.
안타깝게도 반환시간과 응답시간 중 하나를 최적화하면 나머지 하나는 좋지 않은 특성을 나타낸다.
시스템에서 흔히 보이는 절충을 요구하는 상황!
다음 시간에 배우게 될 멀티 레벨 피드백 큐는 이러한 절충을 고려한 스케줄링 정책이다.
중첩
입출력 연산 고려
📌 회고
컴퓨터 성능의 지표인 반환시간, 응답시간으로 성능 개선을 위해 정말 많은 방식을 고민해봤구나!
하는 생각이 들었다.
시분할 컴퓨터 등장으로 인해 평가지표가 바뀐 것도 흥미롭게 다가왔다.
📌 개선 방향
각 챕터 개념을 공부하기 전 문제점을 제시하면서 스스로 생각할 시간을 주는데,
이 때, 바로 다음 장 내용을 읽기보다 더 깊숙히 생각해보고 넘어가야겠다.
📌 참고 문서
운영체제 : 아주 쉬운 세 가지 이야기
'CS(ComputerScience) > OSTEP' 카테고리의 다른 글
| 스케줄링 : 비례 배분 (0) | 2023.08.30 |
|---|---|
| 스케줄링: 멀티 레벨 피드백 큐 (0) | 2023.08.22 |
| 제한적 직접 실행 원리 (0) | 2023.08.08 |
| 프로세스 API (0) | 2023.07.31 |
| 가상화, 프로세스의 개념 (0) | 2023.07.25 |
