선점 스케쥴링

비선점 스케쥴링과 다른점은 우선순위를 뺏을수 있느냐, 없느냐 이다

어떤 프로세스가 점유하고 있을때, 우선순위가 더 높은 프로세스가 레디큐에 존재한다면
현재 점유하고 잇는 프로세스의 우선순위를 뺏을 수 있다

장점

빠른 대처가 가능하다

프로세스의 요청 I/O, 응답 I/O, Interupt 발생, 작업완료 등의 특별한 상황에서 일어남
긴급하게 처리해야 할 프로세스가 있다면 빠른 대처가 가능하다

단점

비선점 스케쥴링에 비해 Context Switching이 자주 일어날 수 있다

SRT ( Shortest Remaining Time )

비선점 스케쥴링인 SJF ( Shortest Job First ) 방식을 선점 스케쥴링에 적용한 것으로,
SRT역시 처리시간이 짧은 순서대로 처리하지만, Ready Queue에 처리시간이
더 짧은 프로세스가 들어올 경우, 자리를 뺏을 수 있다

이렇게 되면 많은 Context Switching이 일어날 수가 있다

라운드 로빈 ( Round Robin )

FCFS방식에 선점 스케쥴링 + Time Quantum 방식을 추가한 방식

Time Quantum

CPU가 연속적으로 사용할 수 있는 시간에 제한을 두는데,
이 시간을 Time Quantum 이라고 한다

어떤 프로세스가 CPU를 사용한 시간이 Time Quantum만큼 지나게 되면
Ready Queue의 가장 뒤쪽으로 보내준다

라운드 로빈방식의 스케쥴링에서는 Time Quantum 설정이 중요하다

시간이 너무 길 경우

CPU 처리시간이 긴 프로세스가 오래 점유하고 있을 가능성이 있음
우선순위가 높은 프로세스가 Ready Queue에 들어왔을때, 기다리게 되는
호위현상이 발생할 수 있다

시간이 너무 짧을 경우

Context Swtching이 너무 자주 일어나 오버헤드가 커질 수 있다

다단계 큐 ( Multi Level Queue )

프로세스의 종류에 따라 Queue를 나누어 관리하는 방식

백그라운드에서 돌아가는 프로세스의 중요도를 다르게 결정한다

Foreground

사람들을 내가 보고 있는 프로세스가 빠르게 처리되길 원하기 때문데,
뒤에 나오는 Background에 비해 우선순위를 높게 잡는다

Foreground Queue 에서는 응답시간을 줄이기 위하여, 라운드 로빈 방식을 사용한다

Background

백그라운드에서 일괄처리되는 프로세스는 덜 빠르게 처리해도 괜찮다고 분류한다

Background Queue 에서는 응답시간이 큰 의미가 없기 때문에, FCFS방식을 이용한다

고정 우선순위 ( Fixed Priority )

Queue마다 우선순위를 주는 방식이다

우선순위가 높은 Queue에 처리해야 할 프로세스가 있다면
무조건 그 Queue를 처리한 뒤에 다음 우선순위의 Queue를 처리한다

이 방식은 사용자가 직접 설정하기 때문에 좋아보이지만
SJF처럼 우선순위가 낮은 Queue는 기아상태가 될 수 있다

타임 슬라이스 ( Time Slice )

고정 우선순위를 해결하기 위해 등장한 방식

운영체제가 Time Slice를 두고, 이 시간의 비율에 따라
Queue를 서비스 하게 된다

예를들면, Foreground는 75%, Background는 25% 이런식으로 사용한다

다단계 피드백큐 ( Multi Level Feedback Queue )

다단계 큐 스케쥴링 방식에 에이징 기법을 추가해준 것이다

많이 기다린 프로세스를 우선순위가 높은 큐로 이동하여 기아상태를 어느정도 완화 해준다

스케쥴러

Context Switching이 자주 일어나게 되면 CPU가 일을 하지 못하게되면서
오버헤드가 발생하게 된다

이러한 오버헤드를 줄이기 위해 필요한 것이 *운영체제의 스케쥴러 *이다

비선점 스케쥴링

어떤 프로세스가 CPU를 점유하고 있다면 작업이 완료될 때까지
다른 프로세스가 CPU를 사용하지 못하게 하는 방식

장점

프로세스가 CPU할당이 끝날때 까지 다른 프로세스가 선점을 할 수 없으므로
Context Swtching이 최소한으로 일어나게 된다

단점

긴급하게 처리되어야 할 프로세스가 늦게 처리되는 경우가 발생한다

FCFS ( First Come First Service )

먼저 Ready Queue에 도착한 순서부터 CPU에 할당될 수 있도록 하는 알고리즘

작업시간을 예측하기 쉽다는 장점이 있지만

처리시간은 긴데 중요하지 않을 작업때문에 처리시간은 짧지만 중요한 작업이
뒤로 밀려나는 경우가 생긴다

이런 상태를 호위상태 ( Convoy Effect ) 라고 한다

SJF ( Shortest Job First )

이름 그대로 처리시간이 짧은 프로세스 순서대로 처리하는 방식이다

모든 방식을 통틀어서 처리 시간이 가장 짧다 = 가장 빠르게 처리가 가능하다

이러한 경우에도 단점은 존재하는데
CPU처리시간이 긴경우 대기시간이 언제까지 될지 모른다
이렇게 되면 무한정으로 기다리게 되는 경우가 생기는데

이를 ** 기아상태 ( Starvation ) ** 이라고 한다

HRN ( Highest Response Ration Next )

SJF 방식에서 기아상태를 해결하기 위해 만들어진 방식

우선순위를 단순히 처리시간만으로 처리하지 않고, Ready Queue에서 대기한 시간을 고려한다

우선순위 정하는 공식

( 대기시간 / CPU 처리시간 ) / CPU 처리시간

대부분 위의 공식으로 처리하게 된다

이처럼 기다린 시간에 비례해서 우선순위를 높이는 방식을 ** 에이징 ( aging ) ** 기법이다 한다

HRN 방식의 경우 선점형식에서 처리하게 될경우 Context Swtching이 너무 많이 일어나기 떄문에
비선점일때, 사용하게 된다

여기서 문제점이 발생한다

SJF 방식과 HRN 방식의 경우 대기시간과 처리시간을 기준으로 순서를 정하게 되는데
현실적으로 프로세스마다 CPU 처리시간이 얼마나 걸릴지 알기가 어려워 문제가 사용이 어렵다

우선순위 ( Priority )

우선순위는 높은곳에서 낮은곳으로 향하게 된다

운영체제에서는 우선순위를 숫자로 표현을 하게되는데,
숫자가 낮을 수록 우선순위가 높다

여기서도 에이징 기법이 사용되게 되는데
우선순위가 낮을 경우 앞에 우선순위가 높은 프로세스가 계속 가게되면
무한정 기다리게 되는 기아현상이 발생하기 때문이다

동적 우선순위

특징이 있다면 동적 우선순위의 경우는

1. 구현방법이 어렵다
2. 시스템의 반응속도가 빠르다

정적 우선순위

동적 우선순위와는 반대이다

1. 구현방법이 비교적 쉽다
2. 시스템의 반응속도가 느리다