강의 링크 : http://www.kocw.net/home/cview.do?mty=p&kemId=1046323

회고

CPU Burst Time 의 분포

CPU 스케줄링이 필요한 이유는 프로세스들의 CPU Burst Time 이 균등(Homogenous)하지 않고 각 Burst Time 이 다르기 때문에 스케줄링이 필요하다.

현재 사용하는 스케줄링 기법

Round Robin기법을 사용한다.

각 프로세스 별 동일한 크키의 할당 시간을 가지고 , 할당 시간이 지나면 프로세스 선점 당하고 레디 큐의 제일 뒤에 가서 다시 줄을 선다.

어떤 프로세스든 동일한 시간동안 CPU 를 선점하고 (same time quantum) 동일한 시간 동안 기다린다.

이 때 CPU 를 오랫동안 써야 하는 프로세스는 그만큼 오랫동안 라운드 로빈에 따라 원형 순환 구조 이동을 반복할 것이고 CPU 를 조금만 써야 하는 프로세스는 원형 순환 구조 이동을 조금만 반복하고 빠져나간다.

원형 순환 구조 이동이란 표현은 등장한 적 없지만 그냥 내가 이해하기 편하게 ><

라운드 로빈은 PCB가 있어서 행복해 :)

CPU 는 context switch 시 문맥을 기억하는 PCB 가 존재하기 때문에 잦은 context swtich 에도 대응이 가능하다.

만약 라운드 로빈으로 인해 사용 중 선점 당하여 레디큐에 들어갔다 왔는데 CPU 에서 문맥을 기억 못하면 라운드 로빈은 필요가 없다.

Multilevel Queue

레디큐는 어떻게 프로세스들을 줄세울까 ?

멀티 레벨 큐는 우선순위 별로 큐를 세운다.

가장 우선순위가 높은 프로세스를 가장 높은 우선순위로 둔다.

멀티레벨큐에서의 우선 순위는

종류	설명
시스템 프로세스	운영 체제(OS) 자체의 동작에 필요한 프로세스
사람하고 인터렉션을 갖는 인터렉티브 프로세스	사용자와 직접 상호작용하는 프로세스
덜 인터렉션 하는 인터렉티브 프로세스	사용자와 상호작용하지만 그 정도가 적은 프로세스
CPU 할당 시간이 높은 배치 프로세스	일괄 처리(batch processing) 환경에서 실행되며, CPU를 많이 사용하는 프로세스
스튜던트 프로세스	특별한 용어로서 정확한 컴퓨터 과학 용어로서의 의미가 불분명

다음과 같다.

foreground , background 형태로 분할 할 수 있다.

foreground queue 는 인터렉티브한 프로세스들을 담고

background queue 는 인터렉티브하지 않은 프로세스들을 담는다.

각 큐들은 독립적인 스케줄링 알고리즘을 갖는다.

사람과 인터렉티브한 프로세스들은 round robin 방식이 프로세스 별 대기시간을 균등하게 줄 수 있음으로 적절 할 것이다.

사람과 인터렉티브하게 적은 background queue 는 잦은 문맥 교환으로 인한 오버헤드를 줄이기 위한 FCFS (First Come First Served) 가 적절하다.

큐에 대한 스케줄링이 필요하다.

fixed priority schedulling : 어떤 프로세스 줄에게 CPU를 줄 것인가 (foreground queue , background queue 중 어떤 것에게 먼저 CPU 를 줄 것인가) => 하지만 이는 우선순위가 낮은 프로세스에게 starvation 을 초래 할 수 있다.

Time slice : 각 큐에 CPU time을 적절한 비율로 할당하는 방법이 있다.
예를 들어 인터렉티브한 줄에게는 80% , 배치 프로세스에겐 20% .. 와 같이 말이다.

멀티레벨 큐는 우선순위 별로 CPU 스케줄링을 하기 때문에 공정하다고 보기는 어렵다.
또한 이는 프로세스 별 평가된 우선순위는 변경되지 않기 때문에 한 번 우선순위가 낮은 프로세스는 영원히 우선순위가 낮은 프로세스로 남는다.

Multilevel Feedback Queue

멀티레벨 피드백 큐는 우선순위에 따라 줄을 세우지만, 어떤 사건들이 있으면 우선순위를 변경시키는 큐이다.

고려해야 할 사항들은 다음과 같다.

우선순위가 높은 큐일 수록 할당 시간을 짧게 주고 우선순위가 낮을 수록 할당 시간을 길게 주고 가장 낮은 우선순위에게는 FCFS 를 적용한다.

이유는 ?

높은 우선순위를 갖는 프로세스(인터렉션이 많은 프로세스) 들의 할당 시간을 짧게 하는 이유는 Round Robin 스케줄링 기법을 따를 때 빠른 응답 시간을 보장 할 수 있기 때문이다.

빠른 응답 시간이란 한 번 레디큐에서 대기하는 시간이 짧다는 것을 의미한다.

낮은 우선순위의 큐에는 FCFS 를 사용하는 이유는 우선순위가 낮아 CPU를 적은 수로 할당 받더라도 할당 받으면 본인의 프로세스를 끝낼 수 있게 하기 위함이다.

멀티레벨 피드백 큐는 들어오는 프로세스들의 CPU burst time 을 예측 할 필요가 없다.

들어온 프로세스는 무조건 순차적으로 가장 높은 선의 프로세스부터 다시 레디큐로 돌아 올 때는 한 단계 낮은 선의 레디큐로 들어간다.

그렇기 때문에 CPU Burst time 이 짧은 인터렉티브한 프로세스들은 짧은 할당 시간만으로도 프로세스가 끝나기 때문에 낮은 우선순위 레디큐 까지 갈 필요가 없다. (만약에 가게 된다면 이는 더 긴 할당 시간을 필요로 하는 프로세스이기 때문에 우선순위를 낮출 필요가 있다.)

CPU Burst time 이 긴 프로세스들은 차례대로 우선순위가 높은 큐 ---> 우선순위가 낮은 큐 로 이동한다.

이 때 우선순위가 낮은 큐에는 프로세스들이 대기하고 있고 우선순위가 높은 큐들이 모두 비어있다면 비어있지 않은 우선순위가 낮은 큐의 프로세스를 할당한다.
마지막 큐까지 밀려 나간 프로세스들은 현재 starvation 을 겪고 있었기 때문에 FCFS 를 사용하여 오랫동안 실행되지 않았던 만큼, 확실하게 프로세스를 끝낸다.

자세한 설명이 적힌 벨로그 글을 첨부해두겠다.

멀티 레벨 피드백 큐(우선순위 스케쥴링)

Mltiple - processor Scheduling

Real time

정해진 시간 안에 무조건적으로 실행되어야 하는 job 들을 reatime job 이라 한다.

미사일 발사 프로세스나 반도체 공장 프로세스 등 매우 중요한 프로세스들을 일컫는다.

real time job 과 같은 경우엔 스케줄링을 개별적으로 맞춰줘야 한다.

Thread Scheduling

user level thread 라는 것은 스레드가 있다는 것을 운영체제가 모르고 있고, 사용자의 프로세스가 직접 어떤 스레드에게 스케줄링 할 것인가를 결정한다.

user level thread

커널이 개입하지 않고 사용자 수준의 라이브러리나 응용프로그램 자체가 완전히 관리하는 스레드이다. ㅓ널은 스레드의 존재를 알지 못하며 전체 프로세스를 단일 개체로 취급한다.

장점

커널 개입이 필요하지 않으며 스레드 별 문맥 교환은 커널 문맥 교환보다 빠르기 때문에 가볍다.

이는 응용 프로그램 자체가 스레드 관리에 더 많은 통제를 갖고 있어, 스케줄링을 잘 하는 응용 프래그램의 경우에는 더욱 뛰어난효과를 보일 수 있다.

또한 커널의 개입이 적기 때문에 CPU 에게 오버헤드가 적다.

단점

프로세스 내 하나의 스레드가 차단되면 모든 프로세스가 차단된다 .

Global scheduling (Kernel level thread)

Global scheduling 의 경우에는 커널 스케줄러가 직접 어떤 스레드를 스케줄링 할지 결정한다.

커널 스케줄러는 시스템 내의 모든 스레드의 존재를 알고 있기 때문에 스레드의 상태를 고려하여 스케줄링 한다.

또한 스케줄러는 모든 스레드에게 공정하게 분배하기 위해 노력한다.

장점

시스템 내의 모든 스레드가 공정하게 리소스를 할당을 보장 받는다.

단점

커널이 여러 스레드의 스케줄링에 관여하기 때문에 복잡하며 오버헤드가 크다.

Algorithm Evaluation

Queueing models

프로세스가 도착하고 처리되는 확률 분포들을 가지고 성능 척도를 계산하는 방법이 존재한다.

Implementation & Measurement

실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교 한다.

알고리즘을 이론적으로 평가하기보다 실제로 사용하여 성능을 측정한다.

Simulation

실제 운영체제에서 알고리즘을 적용하고 성능을 측정하는 것이 어려울 수 있기 때문에

모의 프로그램을 이용해 결과를 비교한다 .