운영체제 기본-3

다중 프로그래밍

메모리의 사용자영역에 프로그램이 여러개 탑재되어 있고, CPU가 이를 번갈아가며 수행한다.
어떤 프로그램을 수행하다 입출력이 발생하면 해당 입출력이 처리되는 동안 CPU가 다른 프로그램을 수행하는 방식이다.
여러 프로그램 중 어떤 프로그램을 선택할지는 ‘스케쥴링‘을 통해 해결한다. 이는 적절한 정책을 통해 다음 프로그램을 결정해준다.
이러한 프로세스는 각 프로그램이 입출력이 발생할 때만 발생된다. 즉, 다른 프로그램으로 작업이 이동되려면 하나의 프로그램이 입출력이 발생해야 한다.
만약 하나의 프로그램에서 무한 루프가 발생된다면 스케쥴링도 일어나지 않아 나머지 프로그램도 돌아가지 않는다. 즉, 다중 프로그래밍 방식에서는 프로그램 간 간섭이 존재한다.
대부분의 프로그램 실행시간에서 CPU의 사용시간은 극히 일부분이고, 입출력 시간이 대부분을 차지한다. 따라서 프로그램 1~N의 실행시간을 t1,t2,…,tn이라고 한다면, 일괄처리에서는 t1 + t2 + … + tn의 시간이 소요되던 것이, 다중 프로그래밍에서는 거의 max(t1,t2,…,tn)에 가까운 시간이 소요됨을 알 수 있다.

버퍼링과 스풀링

다중 프로그래밍이 가능해짐에 따라 출력과 동시에 다른 프로그램 수행이 가능해지면서 여러 프로그램에서 출력이 산발적으로 발생할 수 있게 되었다. 이러한 문제에 대한 해결이 필요해졌다.
Buffering : 입출력 시 CPU의 속도와 입출력 장치간의 속도 차이를 해소하기 위해 하드 디스크나 매모리 영역에 자료를 잠시 저장해놓는 것
Spooling : Buffering과 유사한 개념이지만 버퍼링은 속도의 차이를 해소하기 위한 것이었다면 Spooling은 순차적 사용장치(ex.프린터)를 병렬 수행 프로그램이 사용할 수 있도록 도와주는 방법이다. 속도가 빠르고 임의 접근이 가능한 디스크에 출력되는 자료를 임의도 모아놓고 처리한다.
프로그램1에서 1의 결과를 내고 프로그램2에서 2의 결과를 냈다. 그리고 다시 프로그램1에서 3의 결과를 냈다. 결과의 처리순서는 1-2-3으로 이루어 졌지만 올바른 순서로 프린트하려면 프로그램1에서 수행한 1,3이 프린트되고 프로그램2에서 수행한 2가 프린트되어야 할 것이다. 이를 도와주는 것이 Spooling이다. 디스크에 자료를 저장했다가 프린터로 그를 보냄으로서 이를 해결한다.
참고로 SPOOL은 Simultaneous Peripheral Operations On-Line의 약자이다.
cf. 다중 프로그래밍 방식은 여러 프로그램이 메모리가 탑재되어야 했기에 메모리 경영의 이슈를 파생시키기도 했다.

시분할 시스템

다중 프로그래밍 방식은 입출력이 일어날 때만 스케쥴링이 일어나, 한 프로그램의 입출력 작업이 완료되더라도 해당 프로그램의 작업을 다시 시작할 수 없다는 단점이 있다. 이를 보완하기 위해 등장한 것이 시분할 시스템이다.
시분할 시스템의 핵심은 ‘타임슬라이스‘이다. 입출력 발생시에도 스케쥴링이 일어나지만 타임슬라이스에서 무조건 스케쥴링을 진행하는 것이다. 이에 따라 한 프로그램에서 입출력 완료 후 대기 시간이 적어졌다. 그에 따라 대화가 빈번한 프로그램도 자연스럽게 수행될 수 있게 되었다.
이러한 ‘타임슬라이스’는 타이머 인터럽트를 통해 구현된다. 보통 10ms의 인터벌로 타이머 인터럽트를 설정해 구현된다.
1960년 MTS의 CTSS가 시초가 되어 1970년에 하드웨어 상용화로 상용화되고 현재까지 운영체제의 기본 체계로 자리잡았다.
이러한 시분할 시스템은 사용자 사이를 재빠르게 전환해줌으로서 사용자로 하여금 컴퓨터를 독점하고 있다고 생각할 수 있게 했다. 실제로 하나의 전산시스템을 여러 개인 모니터에 띄우게 해서 각자의 연구실에서 각자의 작업을 할 수 있도록 했다.
다만 한정된 메모리에서 많은 프로그램을 돌려야 했기에 메모리 부족 현상이 일어났다. 이에 따라 ‘가상 메모리’ 기법이 대두되게 되는데 이에 대해서는 추후 자세히 알아볼 것이다.
CPU의 효율성과 사용자의 편의성 모두를 증대시켰다고 할 수 있다.
그 외에도 온라인 파일 시스템, 디스크 스케쥴링, CPU 스케쥴링,프로세스간 통신, 동기화 및 교착상태 처리 등 다양한 이슈가 대두되었다. 이 중 몇가지는 앞으로 알아보게 될 것이다.

스케줄러의 종류

cpu를 할당받을 프로세스를 잘 골라 실행시켜줌으로써 전체적으로 시스템의 성능을 높이자는 것이 목표
사실 스케줄링 작업을 수행하는 스케줄러는 다양하다.
장기 스케줄러(작업 스케줄러) : 어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가를 결정하는 것으로 작업 스케줄링이라고 한다. 오프라인과 연계되는 일괄처리 큐를 별도로 유지하는 경우에 사용한다. 또는 어떤 프로그램을 하드디스크로부터 메모리로 적재할 것인가를 결정한다.
단기 스케줄러(CPU 스케줄러) : 메모리 내의 준비 상태에 있는 프로세스 중에서 어떤 프로세스를 먼저 실행시킬지 결정해서 CPU를 할당하는 스케줄러이다. 프로세스 스케줄러 또는 디스패처에 의해 수행된다.
중기 스케줄러 : 보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가를 결정한다. 가상 메모리 체제에서 너무 많은 프로세스가 적재되면 하드디스크 입출력이 과대해져 시스템이 거의 멈추는 쓰레싱(Thrasing) 현상이 발생할 수 있다. 이 때 스와핑이라는 기술이 사용된다. 일부 프로세스 메모리를 디스크로 내보내고(swap-out), 시간이 흘러 여유가 생기면 다시 적재(swap-in)한다. 이 때 활용되는 것이 중기 스케줄러이다. 장기와 단기의 중간 단계
일반적으로 스케줄러라 하면 단기 스케줄러를 의미한다. 앞으로 ‘스케줄러’라고 하면 이 단기 스케줄러를 의미한다고 하자.

성능 평가 기준

스케줄링 알고리즘은 종류가 다양하다. 따라서 어떤 알고리즘을 활용해 스케줄링을 만들면 좋을지 판단하는 기준이 필요하다. 아래가 그러한 기준의 예이다.
CPU 사용율(CPU utilization) : = 주어진 시간 동안 특정 자원이 실제로 가동된 시간의 비율. CPU 활용 정도를 나타내는 비율. CPU가 비어있는 시간없이 많은 작업을 수행할 수 있도록 했는지를 나타낸다.
처리율(throughput) : 단위 시간당 완료되는 프로세스의 수.
반환 시간(turnaround time) : 프로세스가 생성되어 작업을 마치고 종료될 때까지 걸리는 시간. 일괄처리의 경우에는 반환 시간이 중요 지표
대기 시간(waiting time) : 프로세스가 생성되어 작업을 마치고 종료될 때까지 큐에서 기다리는 시간.
반응 시간(response time) : 대화형 시스템에서 임의 요구(예:키보드 입력)에 대하여 시스템이 반응을 시작하는 데까지 걸리는 시간. 프로세스의 요청에 대해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간.
예측가능성(Predictability)
공평성(Fairness)

성능 평가 기준의 활용

효율성을 추구할 경우 : CPU 사용률과 처리율은 최대화하고 반환시간, 대기시간, 반응시간을 최소화하는 스케줄러를 선정
공평성을 추구할 경우 : 각 기준에 있어 최적의 평균값과 이들간의 편차의 최소화(공평성)을 함께 고려하여 스케줄러를 선정
대화형 시스템의 경우 반응시간(응답시간)이 중요한 지표, 반응시간 편차가 적은 스케줄러를 선정한다.
일괄처리 시스템에서는 처리량이 중요한 지표
시스템 용도에 따라 선정 기준은 달라질 수 있다.
cpu-bound 프로세스, i/o bound 프로세스중 어떤 것을 더 우대할지 생각해야된다.

CPU Burst Time

CPU Burst Time : CPU가 할당된 후 실행상태에 있다가 입출력 요구까지 걸리는 시간 (CPU를 사용하는 시간)
일반적으로 프로세스들은 CPU Burst와 I/O Burst를 번갈아가면서 수행한다.
이러한 CPU Burst Time을 히스토그램으로 나타내면 주로 hyperexponential 분포를 보인다. 이 히스토그램이 왼쪽으로 치우치면 입출력을 주로 수행하는 I/O-bound 프로세스이고 오른쪽으로 치우치거나 평균적인 Burst time이 크다면 계산을 주로 수행하는 CPU-bound 프로세스이다. 이처럼 CPU Burst Time의 hyperexponential 분포는 프로세스의 성격을 파악할 수 있도록 하여 스케줄링에 도움을 준다(프로세스의 특징을 파악하여 어떤 프로세스를 선정할지 고르는 데에 도움을 준다).

스케줄링 기법들

스케줄링이 언제 가동 되는가?

프로세스가 실행 상태에서 대기 상태로 전환될 때, 대표적인 예가 입출력 요청이다.(비선점)
프로세스가 실행 상태에서 준비 상태로 전환될 때, 시간 종료와 같은 인터럽트가 발생할 때가 종은예이다.(선점)
프로세스가 대기 상태에서 준비 상태로 전환 될 때, 입출력의 종료가 예가 되겠다.(선점)
프로세스가 수행을 마치고 종료될 때.(비선점)

비선점 vs 선점 스케줄링

비선점 스케줄링 : 프로세스가 입출력 요구 등으로 CPU를 자진 반납할 때까지 CPU에 의한 실행을 보장해주는 스케줄링이다. 작업 실행 시간 전체 또는 한번의 CPU 배당에 적용된다.
FCFS(First-Come-Fist-Served) / 최단 작업 우선(SJF, Shortest Job First) / 우선순위 스케줄링 (Priority Scheduling)이 이러한 비선점 스케줄링의 알고리즘이다.
선점 스케줄링 : 시분할 시스템에서 타임슬라이스가 소진되었거나 인터럽트 혹은 시스템 호출 종료로 인한 여파로 현 프로세스보다 높은 우선순위의 프로세스가 나타나는 스케줄링이다. 현 프로세스로부터 강제로 CPU를 회수한다.
라운드 로빈 스케줄링 / 다단계 큐 스케줄링 / 다단계 피드백 큐 스케줄링이 이러한 선점 스케줄링의 알고리즘이다.

비선점 알고리즘 1. FCFS(First-Come-Fist-Served) = FIFO

프로세스 도착순으로 CPU를 배정한다. 즉, 준비 큐에 도착한 순서대로 CPU를 배정한다. (실행 중 입출력을 요구하면 다시 다음 준비 상태에서 FCFS를 적용한다.)
도착 순서만이 실행 순서를 결정짓는다는 점에서 공평함
시분할 시스템에서는 백 그라운드 또는 실시간 프로세스 등의 타임 슬라이스를 적용하지 않는 프로세스에 대해서도 사용할 수 있다.
호위 효과(Convoy Effect) 문제가 있다. 즉, 수행 중인 긴 작업을 여러 개의 짧은 작업이 기다릴 수 있다. 이는 짧은 작업의 반환시간과 대기시간을 늘려 평균반환시간과 평균대기시간을 늘린다.
따라서 도착 순서 이외에 특별한 추가 정보를 얻을 수 없는 경우(배치 작업 등의 장기 스케줄러)에 주로 활용한다. 또, 다른 스케줄링 기법의 보조 장치로서 활용 가능, ex) 우선 순위가 동일할 경우의 차선책으로서 활용이 가능하다.

비선점 알고리즘 2. 최단 작업우선(SJF, Shortest Job First) = SPN(Shortest Process Next)

대기하는 작업 중 CPU Burst Time이 가장 작은 작업에 CPU를 할당하는 기법
평균 대기 시간에 있어서는 최적의 알고리즘 (두번째 수행되는 작업이 가장 짧은 시간을 대기하려면 첫번째 작업이 전체 중 가장 짧은 작업이어야 한다. 이는 세번째, 네번째도 마찬가지이다. 결국엔 SJF와 동일하다.)
다만 도착시점(arrival time)을 고려하면 아직 도착하지 않은 프로세스는 스케줄링의 대상이 되지 않기 때문에 더 긴 프로세스가 먼저 할당될 수 있다.
Burst Time이 동일할 경우 FCFS로 도착순으로 처리한다.
문제점 : 사실상 CPU의 Burst Time은 미리 알기 어렵다. 장기 스케줄링에서는 작업시간 예측치를 함께 제출할 수 있다. 하지만 단기 스케줄링에서는 다음 CPU Burst Time을 미리 알 수 없어 사용하기 어렵다.
해결방안 : 에이징 기법(프로세스의 무한대기 가능성을 낮추는 방법으로 기다린 시간만큼 우선순위를 높여주는 것)

이전 Burst Time을 분석해 다음 Burst Time을 예측한다. 다음 Burst Time을 이전 Burst Time들의 지수적 평균으로 간주하는 방법이 주로 쓰인다.(비슷한 환경에서 반복적으로 실행되어지는 프로세스들에 대해서 적용할 만함)
cf. 실행한 시간을 바형태의 표로 그린 것은 간트차트(Gannt Chart)라고 한다.

최단 작업우선 예시

도착시간이 0,2,4,5이고 Burst Time이 7,4,1,4인 프로세스 1,2,3,4가 있다고 하자.
이 때는 프로세스1이 Burst Time과 상관없이 가장 먼저 처리되고, 프로세스3, 프로세스2, 프로세스4 순서대로 처리될 것이다.
평균 대기시간은 (0 + 6 + 3 + 7) / 4 = 4 가 된다.
반환시간은 (7 + 10 +4 + 11) / 4 = 8 인데, 이는 평균대기시간 4에서 평균 Burst Time값 4를 더한 값과 같다.
이러한 SJF는 선점 스케줄링에도 적용할 수 있다. 앞선 예시와 같은 상황에서 타임슬라이스가 더해졌다고 생각하면 된다. 타임슬라이스가 2마다 적용된다고 하자. 그러면 프로세스2가 도착하면서 CPU에는 프로세스2가 할당된다. 도착한 순간의 프로세스1의 남은 Burst Time은 5로 프로세스2의 Burst Time보다 길기 때문이다. 나머지도 마찬가지로 남은 Burst Time의 기준으로 작동된다. 그결과 프로세스1은 조금 뒤에 처리되지만 결국 평균 대기시간은 (9 + 1 + 0 + 2) / 4 = 3으로 더 짧아진다.

비선점 알고리즘 3. 우선 순위 스케줄링(Priority Scheduling)

프로세스 자체적으로 우선순위를 정해두고, 우선순위 값이 제일 큰 프로세스에게 CPU를 할당한다. 순위가 같을 경우 FCFS를 적용한다.
SJF도 결국엔 우선 순위 스케줄링에 포함된다고도 할 수 있다. (우선순위가 CPU Burst Time의 역수)
내부적 우선순위 고려 : 제한시간, 메모리 요구량, 사용하는 파일 수, 평균 CPU Burst에 대한 평균 I/O Burst 비율
외부적 우선순위 고려 : 사용료, 정책적 변수
일반적으로 연산 위주(CPU-Bound) 프로세스보다 입출력 위주(I/O-Bound) 프로세스에게 높은 우선순위를 부여하여 대화성을 증진시킨다.
기아 상태(Starvation)가 유발될 수 있다. 우선순위가 높은 작업이 계속적으로 들어올 경우 우선순위가 낮은 작업이 준비 상태에서 보장없이 머물 수 있다.
이러한 기아 상태는 에이징(Aging)으로 해결할 수 있다. 시스템에 머무는 시간이 증가하면 우선순위를 높여주는 것이다. 아무리 우선순위가 낮았던 프로세스라도 시간이 지나면서 우선순위가 높아져 결국은 CPU를 할당받을 수 있게 된다.

선점과 동적 우선순위

선점(Preemption) : 현 프로세스로부터 CPU를 회수하여 다른 프로세스에게 할당하는 행위
동적 우선순위 : 프로세스 실행 중 시스템의 성능, 프로세스의 특성을 고려해 우선순위를 재조정할 수 있다. 결과적으로 스케줄링에 의해 선점이 발생할 수 있다.
동적 우선순위 스케줄링은 dynamic priority scheduling이라 하고 고정 우선순위 스케줄링은 fixed priority scheduling이라 한다.
전체적인 시스템 성능의 향상 및 프로세스 속성을 고려하여 커널의 여러 곳에서 우선 순위를 조정하는 원칙과 기법이 필요하다. (커널 개발자가 담당해야 하는 부분이다.)
시분할 시스템마다 타임슬라이스의 양(길이)는 다르다. 이 역시 동적으로 변할 수 있다. 우선순위의 동적 변화에 따라 타임슬라이스의 양이 변하는 것이다. 즉, 타임슬라이스는 가변성을 가지고 있다.
가변적인 타임슬라이스는 일률적인 Clock Interrupt Interval로 구성된다. 이는 타임슬라이스보다 미세하게 구성되어 있다.
타임슬라이스의 소진 여부는 이러한 Clock Interrupt Interval을 기준으로 계산된다.
Clock Interrupt Interval은 보통 10ms, 타임 슬라이스는 10~200ms이다. Clock Interrupt Interval을 10ms보다 작게할 경우 오버헤드가 과다 발생할 위험이 있다.

리눅스 2.4v을 예로 생각해보면 인터랙티브(대화성) 정도가 높을 수록 우선순위가 높아지고 타임 슬라이스가 높아진다. (참고: 우선순위는 -20~19까지 40단계로 표현하며 수가 작을수록 우선순위가 높다.) 대화성이 높은 프로세스(I/O Bound)라면 CPU를 할당해주어도 입출력이 일어나면서 CPU를 자진반납할 수 있다. 따라서 그냥 타임 슬라이스를 충분히 주는 것이다. CPU Bound 프로세스는 그 반대이다.

SRT(Shortest Remaining Time)

최단 잔여시간(완료까지 남은 cpu 요구량이 가장 짧은 것)을 우선으로 하는 스케줄링.
진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 sleep시키고 짧은 프로세스를 먼저 할당한다.
선점형 SJF 스케줄링이라 불린다.
남은 실행 시간의 계산, 실행 시간이 짧은 프로세스가 자주 도착할 경우의 잦은 선점을 인한 컨텍스트 스위칭의 부담이 있다.
starvation문제가 여전히 남아있음.

프로세스	도착시간	Burst Time	종료시간	Waiting Time	Turnaround Time
P1	0	8	17	9	17
P2	1	4	5	0	4
P3	2	9	26	15	24
P4	3	5	10	2	7

P1 → P2 → P3 → P4 순서대로 왔어도 도착시간에서의 잔여 시간을 비교해 CPU를 할당한다.
<HRRN(Highest Respone Ratio Next) 스케줄링>
수행 시간이 긴 프로세스의 무한 대기 현상을 방지하기 위한 기법이다.
준비 큐에 있는 프로세스들 중에서 응답률(Response Ratio)이 가장 높은 프로세스에게 높은 우선순위를 주며, 비선점식 방식이다.
응답률 = (대기시간 + CPU요구량) / CPU요구량
즉, 대기시간이 올라갈 수록 응답률이 높아진다.
이 기법을 사용하면 프로세스가 기다리는 시간이 길어질수록 우선순위가 높아지므로 수행시간이 긴 프로세스도 머지않아 CPU를 할당받을 수 있게 된다. cpu요구량이 높을 수록 우선순위가 낮아지므로 평균 응답 시간의 단축된다.
[프로세스에 대해 응답률을 구하는 방법]
그래서 P1 -> P2 -> P3순으로 실행시키는 것이다.

선점 알고리즘 1. 라운드 로빈(Round Robin) 스케줄링

FCFS스케줄링을 기반으로 하여 CPU할당하되, 각 프로세스는 한 번에 쓸 수 있는 CPU 시간 크기 즉, 시간할당량(Time Quantum)이 지나면 시간 종료 인터럽트에 의해 cpu를 뺏기게 되는 선점 방식
준비 큐를 원형 큐로 간주하고 순환식으로 각 프로세스에게 작은 단위의 시간량(타임퀀텀)만큼씩 CPU를 할당한다.
실행상태의 프로세스는 타임퀀텀이 지나면 선점된다. (타임퀀텀은 타임슬라이스와 마찬가지의 개념이다.) CPU를 반납한 프로세스는 다시 레디 큐의 끝에 들어가게 된다.
새로운 프로세스가 부가될 때는 큐의 맨 뒤에 덧붙여 진다.
물론 입출력이 발생하면 CPU를 자진반납한다.
이론상 N개의 프로세스가 1/N 속도로 동시에 실행되는 셈이다. 준비 큐에 N개의 프로세스가 있고, 타임슬라이스가 Q이면 각 프로세스는 (N-1)* Q 시간 이내에 다음 슬라이스를 받게된다. (문맥교환 시간은 고려하지 않았다.)
아무리 짧은 작업이라도 앞선 다른 작업이 큐 앞에 있다면 한 번이라도 각각의 타임퀀텀을 거쳐야하기 때문에 일반적으로 평균반환시간이 SJF보단 크다. 하지만 모든 프로세스가 공정하게 기회를 얻게되어 기아상태가 발생하지 않는다는 장점이 있다.
타임퀀텀의 크기에 따라 성능이 큰 영향을 받는다. 타임퀀텀이 매우 커지면 FCFS와 유사해진다. 매우 작아지면 잦은 문맥교환에 따라 오버헤드가 커져 처리율이 감소한다. => 적절한 타임퀀텀 선정 중요!, 일반적으로 10 ~ 100ms적당
일반적으로 타임퀀텀이 커지면 평균 반환시간이 개선될 수 있다. 많은 작업이 한번에 처리될 확률이 증가되기 때문이다. 다만 많은 짧은 작업이 긴 작업들보다 순서상 늦게 처리되는 경우가 발생할 수 있어 무조건 그런 것은 아니다. 만약 대부분의 프로세스가 타임퀀텀내에 하나의 CPU Burst를 처리한다면 평균반환시간이 개선될 것이다. 따라서 80% 정도의 CPU Burst Time은 타임퀀텀보다 짧도록 조정하는 것이 가장 적절하다.
cpu-bound 프로세스가 더 우대받는 문제가 발생하는데, 이 문제를 해결하기 위해 입출력 프로세스용 레디큐를 따로 두고 우선순위를 더 높게 하되, 이 큐에서 cpu를 받을 때는 이전 입출력이 발생했을 때 쓰지 못하고 남긴 시간 할당량 만큼만 주는 방법(virtual round robin)이 있다.

선점 알고리즘 2. 다단계 큐 스케줄링

목적에 맞도록 우선순위들을 정하고, 그 우선순위마다 준비 큐를 따로 설정하는 것이다.
가장 높은 우선 순위 큐의 프로세스에 CPU를 할당한다.
각 큐는 독자적으로 라운드로빈이나 FCFS같은 알고리즘을 사용할 수 있다.
큐들 간에 이동 불가능
대화형, 배치 등 프로세스의 성격에 따라 우선 순위를 부여한다. (예 : 시스템작업 / 대화형 작업 / 대화형 편집 / 일괄 처리 / 학생 작업)

선점 알고리즘 3. 다단계 피드백 큐 스케줄링

다단계 큐에 동적인 프로세스 우선 순위 변화를 적용한다.
즉, 단계별 큐를 이동할 수 있도록 한 것이다.
우선순위가 높은 큐일수록 시간 할당량은 작게한다.
타임 슬라이스를 계속 모두 소진하는 경우 하위 큐의 뒤로 삽입한다. (하위 큐일수록 CPU-bound 프로세스가 된다.)
가장 하위 큐는 FCFS로 스케줄링한다.
맨 아래 큐에서 너무 오래 대기 시 에이징 기법을 사용하여 상위로 이동시킨다.
가장 일반적인 방법이지만, 적용하기엔 매우 복잡하다. (큐의 수, 각 큐에 대한 스케줄링 알고리즘, 순위를 변경하는 시기 결정법, 프로세스들이 어느 큐에 들어갈지 결정하는 방법 등을 모두 결정해야 한다.)

****

프로세스들의 특성이나 중요도에 따라 몇 개의 그룹으로 나누고, 각각의 그룹에 할애된 일정량의 CPU 시간은 그 그룹에만 영향을 미치도록 하는 스케줄링 기법이다.

그룹별로 일정량의 CPU 시간을 할애했을 때, 특정 그룹에 속한 프로세스의 과도한 CPU 사용은 그 그룹 내의 다른 프로세스들에게만 불이익을 줄 뿐, 다른 그룹으로까지 파급되지 않도록 하겠다는 것이다.

예) 전체 프로세스 : A, B, C, D ,E, F

A, B : 1그룹 -> CPU 시간의 50% 할애

C, D : 2그룹 -> CPU 시간의 25% 할애

E, F : 3그룹 -> CPU 시간의 25% 할애

시분할을 기본으로 ACBEADBF의 순서대로 스케줄을 할 경우, 1그룹은 CPU 시간의 50%를 그리고 나머지 그룹은 각각 25%를 사용하게 될 것이므로 의도대로 됨을 알 수 있다. (A, B는 2번씩, C, D, E, F는 1번씩)

만약 A에게 더 많은 CPU 시간을 주어야 할 경우에는 ACAEADBF와 같은 예의 순서로 스케줄을 함으로써, A가 B보다 더 사용한 CPU 시간은 B의 CPU 시간 축소를 초래하되 타 그룹의 프로세스들은 영향받지 않게 하는 것이다.

실시간 시스템

모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템
연성 실시간 시스템 : 데드라인을 만족한다는 것이 90%같은 확률로 표현된다. 데드라인 내에 종료되지 않으면 데이터 손실등 피해가 발생하지만 시스템은 계속해서 운영 가능한 시스템. 중요한 실시간 프로세스가 그렇지 않은 프로세스에 비해 우선권만 가지고 있다.
ex)동영상
경성 실시간 시스템 : 데드라인을 100% 만족한다는 엄격한 요구조건을 만족시켜야 한다. 데르라인 내에 완료되지 않으면 치명적인 결과를 초래하는 시스템. 데드라인이 지난 후에 서비스를 받는 것은 서비스를 전혀 받지 않는 것과 동일하다.
ex)무기 제어, 발전소 제어, 철도자동제어, 미사일 자동조준, 의료 시스템 등
정적인 방법: 프로세스들의 특징과 개수를 알 수 있는 경우에 유용하다
동적인 방법: 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용한다.

실시간 스케줄링 (두 개 헷갈리지 말기!)

동시에 여러 개의 실시간 태스크들이 존재할 때 각 테스크 간의 작업의 수행 순서를 결정해주는 것이다.
모든 태스크의 모든 작업이 매번 주기가 끝나기 전에 실행이 완료되는 스케줄을 구하는 것은 쉽지 않을 것이다.
따라서 이러한 문제를 원리적 차원에서 풀어가기로 했다.
이에는 정적우선순위 스케줄링과 동적 우선순위 스케줄링이 있다.

RM(Rate Monotonic) 스케줄링 : 선점 정적 우선순위 스케줄링

크기와 개수가 알려진 프로세스들이 각자 독립적이고 주기적으로 발생되는 환경에서 사용된다.
각각의 주기 태스크들은 시스템에 진입하면서 주기에 따라 우선순위가 결정된다. 각 프로세스의 마감시한은 각자의 주기와 같다고 가정하고 주기가 짧을수록 우선순위가 높다. 즉, CPU를 더 자주 필요로 하는 태스크에게 더 높은 우선순위를 준다.
예를 들어 두 태스크 P1(50,20)과 P2(100,35)가 있으면, P1이 우선순위를 갖는다. P2가 처리되다가도 P1이 들어오면 작업을 멈추고 P1이 우선처리된다. (P(주기,수행시간))
태스크가 두 개일 때 RM 스케줄링의 이용률 상한선은 83%이다. 두 태스크의 CPU 이용률을 구해보면 각각 0.40과 0.35로 합치면 약 75%가 된다. 마감시간을 다음 주기가 되기 이전이라고 가정하면, 두 태스크는 모두 마감시간을 충족시킬 수 있다.
RM기법은 스케줄링 비용이 적게 드는 대신, 새로운 프로세스가 추가되는 환경에 바로 적응하지 못하고 전체 스케줄링을 다시 해야하는 단점이 있다.
n개로 구성된 프로세스 집합이 있다. cpu사용률(U)는 다음과 같고, 이 값이 오른쪽값 보다 작으면 RM기법으로 스케줄링이 가능하다. P는 주기 D는 마감시한(D<=P), C는 수행시간을 나타낸다.
RM 스케줄링은 정적 우선순위 스케줄링의 최적이라고 할 수 있다. 해당 기법으로 스케쥴 할 수 없는 태스크의 집합이 있다면 다른 정적 우선순위를 사용하는 알고리즘들 역시 이 집합을 스케쥴링 할 수 없기 때문이다.
태스크의 개수가 N일 때, N(2^(1/N) - 1)이 태스크들의 CPU 이용률의 합보다 크다면 일반적으로 스케줄링이 가능하다. 이 공식에 무한대를 취해보면 약 0.69 정도로 수렴하는데, 이는 태스크의 개수가 많아지면 CPU의 69%정도밖에 사용할 수 없다는 의미이다. 해당 공식을 만족시키지 못하면 deadline missing이 발생할 수 있다.

EDF(Earliest Deadline First) 스케줄링 : 선점 동적 우선순위 스케줄링

마감시간에 따라 우선순위를 동적으로 부여한다. 스케줄링이 일어나는 시점에서 마감시간이 빠를수록 우선순위가 높아진다. 실행해야 될 태스크가 정해지면 그 태스크의 마감시간에 맞추어 우선순위가 재조정된다.
마감시간만 스케줄러에게 알려주면 수행시간도 특별히 정해질 필요가 없다. (마감시간만으로 우선순위를 판단하기 때문)
새로운 프로세스의 동적인 수용이 가능하나, 그때마다 가능한 스케줄을 찾기위해 계산을 해야하는 부담이 있다.
n개의 프로세스가 있을 때 다음 조건을 성립하면 EDF기법으로 가능한 스케줄이 존재함을 의미.
EDF 스케줄링에서는 CPU 이용률의 합이 100%보다 작기만 하면 수행이 가능하다. 즉, EDF 스케줄링을 사용하면 RM 스케줄링에서 deadline missing이 발생하던 케이스도 해결할 수 있다는 것이다.
하지만 이는 이론상 가능한 것이고, 실제로는 문맥교환의 비용 때문에 사실상 100%는 불가능하다.
만약 EDF 이용 중 태스크의 CPU이용률 합이 100%보다 큰 과부하가 일어날 경우 연속으로 Deadline missing이 발생하는 Domino effect가 발생할 수 있다. 몇가지 태스크를 포기하는 알고리즘을 추가하는 것으로 도미노 현상을 막을 수 있다.

RM vs EDF

RM : 구현이 상대적으로 단순하고, 우선순위가 고정되기 때문에 예측성이 좋다. 하지만 CPU의 이용률이 좋지 않다는 단점이 있다.
따라서 태스크의 개수가 정해져 있고, 주기와 수행시간 등이 정확히 파악되어 있다면 RM을 사용하는 것이 유리할 수 있다.
EDF : 이론적으로 최적이고, CPU이용률이 거의 100%에 수렴한다. 하지만 과부하시 도미노 현상이 발생할 위험이 있다.
EDF는 분명 RM보다 뛰어나지만, 실제로 실시간 시스템을 개발하는 엔지니어들은 어느 한가지를 특별히 선호하지는 않는다.

SRT(Shortest Remaining Time)

CATEGORY