5. 프로세스 스케쥴링

`

스케쥴링 

한 시스템 내에는 여러 개의 프로세스가 존재한다. 이 각각의 프로세스에게 어떻게 자원을 할당해줘야 효율적이며 문제가 발생하지 않는지 OS가 관리해준다. 

자원을 할당할 프로세를 선택해 주는 것을 스케줄링이라고 한다.

 

자원의 관리는 크게 두 가지 방법으로 나뉜다. 

1. 시간 분할 (time sharing) 관리

시간 분할 관리를 하는 대표적 자원의 예로는  프로세서가 있다. 프로세서(CPU)는 한 번에 하나의 프로세스만 들어가서 작업할 수 있는 자원이다. 따라서 언제 누가 들어갈지 시간을 분할하여 관리가 필요하다.->프로세스 스케쥴링

프로세서 사용시간을 프로세스들에게 분배한다는 것이다. 

 

2. 공간분할 (space sharing) 관리

공간분할 관리를 하는 대표적 예는 메모리이다 메모리는 Space를 분할하여 각 프로세스에게 할당이 가능하다 (하나의 자원이 분할하여 동시에 사용 가능) 

 

스케줄링(Scheduling의 목적)

시스템의 성능(performance) 향상

- 스케쥴링은 한정된 자원 둘을 효율적으로 관리하는 것으로 그 목표는 근본적으로 시스템의 성능 향상이다.

 

그렇다면 어떻게 성능이 향상되었는지 알 수 있는가?

 

대표적인 시스템의 성능지표는 아래와 같다.

 

1. 응답 시간(response time)

> 작업 요청이 들어온 시간으로부터 응답을 받을 때까지의 시간

 

2. 작업 처리량(throughput)  

> 단위 시간 내에 완료한 작업의 수

 

3. 자원 활용도(resource Utilization)

> 주어지 시간 동안 자원이 활용된 시간 (얼마나 놀리지 않고 활용하였는가)

위 세 가지 시스템의 성능 지표가 있으며 각 사용자의 목적에 맞는 지표를 고려해 프로세스 스케줄링 기법을 선택하여 운용한다.

응답 시간 지표의 경우 대화형 시스템 (realtime, interactive system)에서 중요한 지표가 될 것이고

작업 처리량의 겨우 batch system에서 중요한 지표가 될 것이며

자원 활용도의 경우 비싼 슈퍼컴퓨터를 사용하는 곳에서 중요한 지표가 될 것이다.

 

<기타 성능지표들>

 

<성능을 측정하기 위해 알고 가야 할 용어 정리 >

1. Waiting time(대기시간)

> 프로세스 요청이 들어온 시간부터 실제 실행을 하기까지 기다린 시간

2. Response Time(응답 시간)

> 프로세스의 요청부터 첫 번째 출력까지의 시간

3. Burst time(실행시간)

> 실제 프로세스가 실행되고 종료되기까지의 시간

4. Turn-around time(반환시간)

> 프로세스의 요청부터 실행이 종료되기까지의 총 시간

 

스케줄링 기준

기준은 어떠한 항목을 결정해야 할 때 고려하는 항목이다.

 

스케줄링 기법을 선택해야 할 때도 고려해야 할 사항들이 있다.

. 프로세스의 특성

> I/O-bounded / Compute-bounded

 

. 시스템의 특성

> 시스템의 특성에 따라 목적이 다르기 때문에 특성을 고려해 스케줄링 기법을 선택한다.

 

. 프로세스의 긴급성

> Hard, soft -real time, non-real time systems

 

. 프로세스 우선순위(priority)

 

. 프로세스 총 실행 시간 등

 

 

 I/O-bounded / Compute-bounded

프로세스 수행 =  CPU 사용 + I/O대기이다. 어떤 프로그램은 CPU 사용시간(CPU burst)이 많고 어떤 프로그램은 I/O 대기시간(I/O burst)이 더 많을 수 있다.

그중  CPU burst가 더 많은 프로세스를 Coumpute-bounded 프로세스 라 하고

I/O burst 가 더 많은 프로세스를 I/O-bounded 프로 세스라고 한다.

 

BT(Burst time)는 스케줄링의 중요한 기준 중 하나이다.

 

스케줄링의 단계

발생빈도와 할당 자원에 따른 구분(long term, mid term, short term)

1.Long-term Scheduling

> 가끔 일어나는 스케줄링으로 job  scheduling 이 이에 속한다. 

시스템 내의 프로세스 수를 조절하는 것을 Multiprograming degree라 하며

I/O-bounded와 Compute-bounded 프로세스들을 잘 섞어서 선택해야 한다. 이유는 당연히 한쪽으로 몰리면 효율적이지 않기 때문

 

시분할 시스템에서는 모든 작업을 시스템에 등록하기 때문에 Long-term scheduling 은 다소 덜 중요하다.

 

2.Mid-term Scheduling

> 종종 일어나는 스케줄링으로 memory allocation 이 이에 속한다.

메모리를 할당받지 못한 체 기다리고 있던 프로세스들에게 메모리를 할당해주는 작업으로 job 스케줄링보다는 자주 일어나는 스케줄링이다. 

 

 

 

 

 

 

 

 

3. Short-term Scheduling

> 가장 빈번하게 일어나는 스케줄링으로 ready 상태에서 프로세서를 기다리는 애들에게 할당할 프로세서를 결정하는 Processor scheduling이 이에 속한다.

가장 빈 전하게 발생하므로 가장 중요한 스케줄링이다.

많이 발생하므로 빠르게 처리해줘야 한다.

scheduling decision이 느리면 문제가 된다.

 

스케줄링 단계

프로세스 트렌지션 다이어그램에 각 스케줄링의 위치를 표시한 것이므로 기억해두면 좋다.

 

스케줄링 정책(Policy)

정책은 어떠한 목적을 달성하기 위한 수단/방법을 말한다.

스케줄링을 효율적으로 하기 위한 방법으로 보자

1.Preemptive/Non-preemprive scheduling(선점, 비선점 스케줄링)

선점이란 자원을 뺏길 수 있는 스케쥴링을 말하고 비선점 은 한번 자원을 할당받으면 스스로 내놓기 전까지 뺏기지 않는 스케쥴링을 말한다.

 

어떤 정책을 선택할 것인가?

비선점 스케쥴링은 어떤 프로세스가 자원을 할당받으면 스스로 반납 전까지는 다른 프로세스가 사용하지 못한다.

장점은 : 한번 자원을 할당받으면 다른 프로세스로의 Context Swich가 일어나지 않아 overhead가 적다.

단점은 : 한번 자원받으면 내놓지를 않으니 현재 프로세스보다 우선순위가 높은 게 있더라도 앞선 프로세스가 자원을 내놓지 않으면 일을 하지 못해 우선순위 역전현상이 일어나고, 평균 응답 시간이 증가한다.

 

 

 

 

선점 스케쥴링은 앞서 설명한 대로 다른 프로세스에게 자원을 뻇길수 있다. 우선순위가 높은 프로세스가 오거나 할당된 시간이 종료되면 강제로 자원을 뱉어야 한다. 

이러한 스케쥴링 정책의 단점은 Context switch가 자주 발생하여 overhead가 크다는 것이다. 

하지만 Time-sharing system, real-time system 등 응답성이 중요한 시스템에서는 적합하다.

 

 

 

 

 

2. 우선순위 정책 (Priority Policy)

프로세스의 중요도에 따른 스케쥴링으로

한번 우선순위가 정해지면 순위가 변하지 않는 Static Priority(정적 우선순위)와

프로세스의 상태변화에 따라 Priority가 변경되는 Dynamic Priority(동적 우선순위)가 있다.

 

정적 우선순위 장점은 프로세스 생성 시 우선순위를 결정하고 변하지 않기 때문에 구현이 쉽고 system의 overhead가 적다는 것이다 

하지만 시스템 환경의 변화에 대한 대응이 어렵다.

 

동적 우선순위 정책은 프로세스 상태 변화에 따라 Priority가 변하기 때문에 환경 변화에 대해 유연한 대응이 가능하다.

하지만 그만큼 구현이 복잡하고  Priority를 변화가 일어날 때마다 재계산하여야 하므로 system overhead가 크다.

 

ㅡ 

 

기본 스케쥴링 알고리즘

1) FCFS(First-Come-First-Service)

비선점 스케쥴링 정책을 따른다

스케줄링 기준

> 도착시간 기준(Ready queue에 먼저 와있는 것), 선착순으로 프로세스 처리

 

장점은 Resource Utilixzation이 높다.

이유는 오는 대로 프로세스에게 자원을 던져주면 되기 때문에 스케줄링에 대한 부하가 적고 프로세서는 그냥 계속 일하면 되기 때문에 자원을 효율적으로 사용 가능하다.

 

이러한 방식의 스케쥴링은 일괄처리 시스템(Batch system)에 적합하다. 이유는 일괄처리 시스템은 작업 퍼포먼스를 높이는 게 목적이 기 때문이다.

 

그러나 입력을 넣었을 때 빠른 반응을 원하는 대화형 시스템(interactive system)에는 부적합하다. 앞의 작업이 끝나기 전에 응답을 못 받기 때문에 평균 응답 시간이 길기 때문이다.

 

단점은 앞서 말한 대로 긴 평균 응답 시간이 있고 이처럼 긴 처리시간이 필요한 프로세스에 의해 나머지 프로세스들의 대기시간이 길어지는 (대기시간>>실행시간) 현상을 Conboy Effect 라 한다.

2) RR(Round-Robin)

그렇다면 사용시간에 제한을 두고 돌아가면서 쓰자! 

preemptive(선점) 스케쥴링 정책을 따른다(타의에 의해 자원 반납)

스케줄링 기준
> 도착시간(Ready queue) 기준이고 먼저 도착한 프로세스를 먼저 저리 하나 자원의 사용에 제한시간이 있다.

제한 시간은 시스템 파라미터로 정할 수 있고 프로세스 할당된 시간이 지나면 자원을 반납해야 한다.

 

이시스 템의 장점은 자원 독점을 방지할 수 있지만  제한시간이 지날 경우 프로세스가 바뀌어야 하므로 Context switch가 자주 발생하고 이는 overhead로 이어진다.

 

RR시스템은 응답이 빨라야 하는 대화형, 시분할 시스템에 적합하다.

 

RR시스템에서는 Time quantum(제한시간의 파라미터 값)의 설정이 시스템 성능을 결정하는 핵심 요소이다. 

타임 퀀텀이 너무 크다면 FCFS와 다를 바 없다.

반면 너무 작으면  프로세서는 함께 공유되는 것처럼 느껴져 작업이 동시에 실행되는 것처럼 느껴지나 프로세서의 체감 속도는 n개의 프로세서가 진행될 경우 1/n의 속도로 느껴질 수 있다.

또한  잦은 Context switch로 인해 overhaead문제가 발생한다. 

 

3) SPN(Shortest-Process-Next)

Shortest-Process-next 방법은 SJF(shortest job First) scheduling으로서  Burst time 이 작은 프로세스 먼저 처리를 시켜주는 것이다. 

위의 사진에서 처럼 우리 실생활에도 이와 비슷한 방법이 적용되고 있다. 휴지만 계산하면 되는데 앞에 줄 서있는 많은 사람들 때문에 시간낭비가 되므로 한쪽에 소량 구매고객을 위한 셀프 계산대 라인이 따로 있다. 

 

이 알고리즘의 장점은 평균 대기시간(Wait time)과 시스템 내의 프로세스 수를 최소화할 수 있다. 

이렇게 하면 메모리 절약과 동시에 스케줄링 부하에 대한 감소도 기대할 수 있어 시스템 효율을 향상해준다.

 

하지만 Starvation(무한 대기) 현상이 발생할 수 있다.  Starvation은 실행시간(Burst time)이 긴 시스템은 무한 대기를 해야 해서 굶어가는 현상이다.

 

 

또한 어떤 프로세스가 실행도 전에 해당 프로세의 Burst time이 얼마나 될지 정확한 실행시간을 알 수 없다. 따라서 짧을지 길지 미리 예측하는 기법이 필요하다.

4) SRTN(Shrtest-Remaining-Time-Next)

SPN의 장점을 극대화 한 알고리즘으로 Preemprive Scheduling 정책을 따라 잔여(Remaining) 실행 시간이 더 적은 프로세스가 ready가 되면 선점되는 방식이다.

 

이 알고리즘의 단점은 프로세스 생성 시 역시 총 실행시간(BT)을 예약해야 하고 잔여 실행을 계속해서 추적해야 하기 때문에 overhead문제가 있다.

선점 정책을 따르기 때문에 잦은 Context switching 또한 overhead를 가중한다.

-> 구현 및 사용이 비현실적이다.

5) HRRN(High-Response-Ratio-Next)

SPN의 변형으로 SPN의 단점 중 하나인 Starvation 문제를 Aging기법으로 처리한다 Aging기법이란 경로우대라고 이해하면 쉽다. 나이가 많은 사람에게 자리를 양보하는 것이다.

 

HRRN은 Non-Preemptive Scheduling이며 스케줄링의 기준은 Responce Ratio가 높은 프로세스를 우선적으로 처리한다.

SPN의 장점과  Starvation을 방지해 주나 실행시간 예측 기법이 필요하다

실행시간을 예측하기 위해서는 이전에 작업 후 종료될 때 커널이 분석한 자료를 바탕으로 예측하게 되며 이는 Overhead로 이어진다.

6) MLQ(Multi-Level-Queue)

SPN, SRTN, HPRN방식은 효율성은 좋으나 실행시간을 예측하는데 부하가 걸린다는 단점이 있었다. 이 단점을 극복하고자 고안된 방식이 MLQ와 MLFQ이다.

 

MLQ는 여러 개의 Ready Queue를 가지고 각각 작업/우선순위를 배정하는 방식이다.

특징은 최초에 배정된 Queue를 벗어나지 못한다는 것과 각각의 Queue는 자신만의 스케줄링 기법을 사용한다.

Queue사이에는 우선순위 기반의 스케줄링(fixed priority, Preemptive Scheduling...)을 사용한다.

 

우선순위가 높은 Queue에 있는 것들이 처리되므로 빠른 응답 시간을 기대할 수 있지만 우선순위가 낮은 Queue는 Starvation이 발생하는 문제가 있을 수 있다.

또한 다수의 Queue를 관리하고 스케줄링해주어야 하므로 overhead가 발생된다는 단점이 있다.

 

7) MLFQ(Multi-Level-Feedback-Queue)

MLQ의 단점을 극복하고자 나온 알고리즘으로 프로세스의 Queue 간 이동이 가능한 MLQ라고 보면 된다.

 

현재까지의 프로세서 사용 정보(패턴)를 활용하여 받은 Feedback을 통해 우선순위를 재조정하여 Queue에 넣어주는 방식이다.

 

프로세스에 대한 사전 정보 없이 SPN, SRTN, HRRN 기법과 비슷한 효과를 볼 수 있다.

 

MLFQ의 특성으로는 Dynamic Priority, Preemprive scheduling, Favor short burst-time process, Faver I/O bounded Process, Improve adaptability 등이 있다.

 

단점으로는 설계와 구현이 복잡하고 우선순위가 낮은 큐들은 Starvation문제가 남아있고 동적으로 우선순위 변경이 일어나  스케줄링 overhead가 크다는 것이다.

 

MLFQ의 변형으로 각 큐마다 시간 할당량을 다르게 배정해서 프로세스의 특성에 맞는 형태로 시스템을 운영하는 것이 가능하고 

입출력 위주 프로세스들은 대부분 잠깐만 작업을 하면 되기 때문에 프로세스가 block 될 때 상위의 레디 큐로 진입하게 하여 시스템 전체의 평균 응답 시간을 줄일 수 있다.

또한 starvation문제를 해결하기 위해 일정 시간을 초과하여 기다린 프로세스들은 상위 큐로 이동시키는 에이징 기법도 적용하여 MLFQ를 변형할 수 있다.