Operating Systems 5. CPU Scheduling - (1)

 

Basic Concepts

- multiprogramming 의 목적은 CPU 이용률을 최대화 하는 것이다. 

- 프로세스 실행은 CPU 실행 (CPU burst) 와 I/O 대기 (I/O burst) 의 사이클로 구성된다.

- CPU burst 시간의 분포도는 다음과 같다. 대부분 10ms 이하에 CPU 를 사용하고, 나머지는 I/O 또는 응답을 기다리는 시간이다.

 

 

CPU Scheduler

-Short-term scheduler 은 ready queue 에 있는 프로세스들 중 하나를 선택하여 그 프로세스에게 CPU 를 할당해준다. CPU scheduling 결정은 process가 다음 상황일 때 발생 가능하다.

 

1. running 상태에서 waiting 상태로 전환 (I/O wait, child termination wait)

2. running 상태에서 ready 상태로 전환 (time-out)

3. waiting 상태에서 ready 상태로 전환 (I/O completion, event occur)

4. Terminate

 

여기서 1번과 4번의 경우는 nonpreemptive 하다. 즉, 하나의 프로세스가 CPU 를 계속해서 독점하는 것이다. 이런 case는 구현이 간단하지만 비효율적이다. 

반대로 2번과 3번의 경우는 preemptive 한 것으로, 프로세스간에 context switching 이 발생하는 것이다. 이런 case는 구현이 복잡하지만 효율적이다.

 

nonpreemptive-secheduling 이란 비선점 스케쥴링으로, 일단 CPU가 하나의 프로세스에 할당되면, 그 프로세스가 CPU를 놓을 때까지 계속 CPU를 점유하는 방법이다. 즉, 종료되거나 대기 상태로 전환된 경우에만 스케쥴링이 필요하다. 즉, 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식이다.

 

preemptive-scheduling 이란 선점 스케쥴링으로, 현재 수행되고 있는 프로세스는 언제든지 다른 프로세스로 교환 가능하다. 왜냐하면 인터럽트가 언제든지 발생할 수 있기 때문이다. 보통 CPU 독점을 방지하거나(timer 사용), 프로세스 우선순위를 반영하고자 할 때 스케쥴링을 할 수 있다. (2, 3 번의 경우 ready queue가 변화한다.) 즉, 운영체제가 강제로 프로세스의 사용권을 통제하는 방식이다.

 

그러나 선점 스케쥴링은 공유 데이터의 일관성 유지에 따른 관련 비용이 발생한다.

1. 프로세스는 데이터를 변경하는 도중에 다른 프로세스에게 선점되어 변경된 데이터를 저장하기 전에 CPU를 내어놓을 수 있다.

또한, 다수의 프로세스가 데이터를 공유할 때 경쟁적으로 데이터를 변경하면, 데이터 일관성이 유지되지 않을 수 있다.

따라서 공유 데이터 접근에 대한 조정이 필요하며 이는 동기화 방식으로 해결할 수 있다.

 

2. 모든 커널 루틴은 커널 데이터를 공유한다.

커널은 system call을 통하여 요청된 프로세스의 작업을 처리할 수 있으며, 공유 데이터를 접근하는 커널 루틴이 실행 되는 동안에, 인터럽트로 인해서 다른 커널 루틴에게 선점되면 공유 데이터 일관성 유지가 되지 않을 수 있다.

따라서 중요한 코드의 시작 부분에서는 인터럽트를 비활성화 시키고, 끝 부분에는 활성화 시킴으로써 중요한 커널 코드를 보호할 수 있다.

 

 

 

Dispatch Latency

Dispatcher 란 CPU의 제어권을 CPU 스케쥴러가 선택한 프로세스에게 주는 모듈이다.

즉, context switching 이 일어나고, CPU 동작 모드를 user mode 로 전환하며, 선택한 프로세스가 다시 시작하도록, user program의 적절한 위치로 이동한다. 

 

Dispatch Latency(지연) 는 한 프로세스를 정지하고, 다른 프로세스의 수행을 시작할 때까지 소요되는 시간으로, 가능한 한 작아야 빠르게 동작할 수 있다.

 

 

 

Scheduling Criteria

스케쥴링을 하는 기준은 다음과 같다.

최대화 해야 할 것 : CPU 이용률, 처리량

최소화 해야 할 것 : Turnaround time (프로세스를 실행하는 데 소요된 시간),

Waiting time (ready queue 에서 대기하는 시간),

Response time (요청을 한 후에 첫 번째 응답을 받을 때까지의 소요시간)

 

 

CPU 스케쥴링 알고리즘

스케줄링 알고리즘 비교를 위한 측정 요소는 평균 대기시간을 주로 사용한다.

OS 스케쥴러는 Dynamic 과 Static으로 구분할 수 있는데, Dynamic 스케쥴링은 기준이 그때그때 변하는 것으로 구현이 복잡하고 오버헤드가 생길 수 있지만 성능이 좋다.

Static 스케쥴링은 기준이 계속해서 고정된 상태로 구현이 쉽고 오버헤드가 거의 생기지 않는다.

 

-선입선처리(First-Come First-Serve : FCFS) 스케줄링

-최단작업우선(Shortest Shortest-Job-First : SJF) 스케줄링

-우선순위(Priority) 스케줄링

-라운드로빈(Round Robin:RR) 스케줄링

-다단계 큐(Multilevel Queue) 스케줄링

 

 

 

First-Come First-Serve (선입선출)

먼저 들어온 프로세스를 먼저 프로세서에 할당하는 방식으로, Queue 의 FIFO 와 동일하다. 이 방식은 프로세스 처리 순서에 따라 성능이 크게 달라질 수 있으며, 먼저 온 프로세스가 끝날 때까지 운영체제가 개입하지 않는 비선점형 스케줄링 방식이다.

 

Convoy 효과 - 수행 시간이 큰 프로세스가 먼저 들어오면, 뒤에 들어온 프로세스들은 불필요하게 오랜 시간을 기다려야 한다. 결론적으로 낮은 CPU 와 장치 사용률을 보이게 된다. 

 

 

 

Shortest Shortest-Job-First

최단작업 우선 스케줄링은 static 스케쥴링 중에 평균 waiting time 이 가장 최적화된다. CPU burst 시간이 짧은 순서에 따라 프로세서에 할당한다.

따라서 FCFS 에서 발생하는 콘보이 효과를 해결할 수 있다. 그러나 프로세스의 실행 시간을 정확히 미리 아는 것이 어렵고 불가능하다는 단점이 존재한다.

또한, CPU  burst 시간이 큰 프로세스는 계속 뒤로 밀려나는 기아(starvation)현상 이 발생한다.

또한, FCFS 와 마찬가지로 프로세스가 끝날 때 까지 운영체제가 개입하지 않는 비선점형 스케줄링이다. 

 

 

또한 다음 CPU burst 길이를 미리 알 수 없기 때문에 이전 CPU burst 길이를 사용하여 예측하는 방법을 사용한다. 예측값은 지수 평균을 사용하여 계산한다.

 

 

 

Shortest-remaining-time-frst

SJF 의 선점형 버전이다. 프로세스의 남은 수행 시간이 짧은 순서대로 프로세서에 할당되는 것으로, 선점형 스케줄링이다.

수행 중 다른 프로세스보다 남은 수행 시간이 적어지면 운영체제가 개입해 자리를 바꿔준다. 따라서 비선점형 SJF 보다 평균 대기시간이 짧게 걸린다.

 

 

 

Priority Scheduling

우선순위 스케쥴링은 가장 높은 우선순위를 가진 프로세스에게 CPU 를 할당한다.

우선순위가 높을 수록 작은 우선순위 번호를 가지고, 선점형과 비선점형 방식이 있다. 또한, SJF 스케쥴링은 우선순위 스케쥴링의 특별한 경우인데 다음 CPU burst time의 예측값이 작을수록 높은 우선순위를 갖기 때문이다. 

 

이 스케쥴링의 문제점은 낮은 우선순위의 프로세스가 무한히 대기하여 수행되지 못할 수도 있기 때문이다. 이를 기아 상태(Starvation) 이라 하고, 해결책으로는 오랫동안 대기하는 프로세서의 우선순위를 점진적으로 증가시키는 Aging 이 있다.