[CS] Process Scheduler

얄루얄루·2022년 9월 10일
Operating System
0

Computer Science

목록 보기
6/10

프로세스 스케쥴러

컴퓨터가 동작 중에는 여러 프로세스가 돌아가게 된다.

그래서 현 프로세스 다음에 어떤 프로세스를 실행시킬 것인가를 결정하는 여러 방법이 있다.

FCFS (FIFO) Scheduler

FIFO를 보자마자 Queue가 생갔났다면 맞다. FCFS는 First Come First Serve의 약자로 FIFO와 마찬가지로 먼저 온 녀석을 먼저 실행시킨다는 의미이다.

장점

  • 특정한 매커니즘이 필요가 없어 구현이 편하다
  • 먼저 들어온 순서대로 실행되어 Starvation은 발생하지 않는다.

Starvation이란?
특정 프로세스의 우선순위가 낮아서 원 하는 자원을 계속 할당 받지 못하는 상태를 말한다. 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때, 특정 프로세스는 영원히 자원 할당이 안되는 경우를 주로 의미한다.

단점

  • 하나의 프로세스가 실행 중에 다른 프로세스는 하염없이 기다려야 한다
  • Convoy Effect의 발생 가능성이 높다.

Convoy effect란?
하나의 프로세스의 처리가 지연되어 전체 프로세스의 실행 시간이 늦어지는 것을 말한다. FCFS에서 가장 처음에 들어온 프로세스가 100ms의 Burst time을 가지고 있을 때, 그 뒤에 온 프로세스들이 20ms, 30ms짜리라고 해도 먼저 실행되는 100ms짜리 때문에 전체적으로 프로세스들이 모두 늦게 끝나게 되는 현상을 말한다.

위의 표를 보면 P1, P2, P3는 모두 0초에 들어왔고, Order를 보아하니 P1, P2, P3 순으로 들어왔다.

스케쥴링 알고리즘에서 가장 중요한 것은 Average Waiting Time (AWT)이다.

Waiting time = Turn Around Time - Burst Time이고,

Turn Around Time = Completion Time - Arrival Time이다.

그러니 Waiting time = Completion Time - Arrival Time - Burst Time이라고도 할 수 있다.

Completion Time은 작업이 완전히 마쳐진 시간,

Arrival Time은 대기 큐에 들어온 시간,

Burst Time은 프로세스의 작업을 끝마치는데 걸리는 시간 (위 표에서의 Duration)을 뜻한다.

그래서 각각의 WT와 AWT까지 계산해보면,

WT1 = 24 - 0 - 24 = 0ms

WT2 = 27 - 0 - 3 = 24ms

WT3 = 31 - 0 - 4 = 27ms 가 되고,

AWT = (0 + 24 + 27) / 3 = 17ms가 된다.

SJF (Shortest Job First) Scheduler

이름 그대로 실행 시간이 가장 짧은 프로세스를 먼저 실행시키는 방법이다.

실행 시간을 미리 정확하게 아는 것은 불가능하지만, SJF는 Greedy Algorithm으로 실행 시간의 근사값을 예측한다.

SJF Scheduling 방식에는 Preemptive와 Non-preemptive 방식이 있는데,

Preemptive는 실행 도중에도 새로 들어온 프로세스의 Burst time이 현 프로세스의 Remaining time보다 작다면 Context Switching이 일어난다. 이 방식은 SRTF (Shortest Remaining Time First)라고도 불리운다.

반면, Non-preemptive는 실행 중인 프로세스는 전부 끝내고 나서, 다음 프로세스를 고를 때 Burst time이 가장 짧은 녀석을 고른다. 간단히 말해, Priority Queue를 사용햔 FCFS 방식이라고 봐도 좋다.

장점

  • 주어진 시간 내에 최대한 많은 여러가지 프로세스를 실행할 수 있다
  • 비교적 짧은 AWT를 제공한다
  • Convoy Effect를 피할 수 있다.

단점

  • 실행 시간이 긴 프로세스의 경우 계속해서 순위가 밀려 영영 실행되지 않을 수도 있다. (starvation)

위 그림은 Preemptive SJF 방식이다.

그림을 보면 0ms에 P2가 들어와 실행이 된다.

1ms에 P3가 들어온다. 그러면 P2의 Remaining time(5ms)과 P3의 Burst time(4ms)를 비교한다. P3가 더 짧으므로 갈아낀다.

2ms에 P1이 들어온다. P3의 Remaining time(3ms)가 P1의 Burst time(4ms)보다 작으므로 그대로 P3를 수행한다.

3ms에 P0가 들어온다. 이번에는 P3(2ms)와 P0(2ms)가 동일하므로 FCFS 룰에 따라 먼저 온 P3를 계속 수행한다.

5ms에 P3가 끝나고, P0(2ms), P1(4ms), P2(5ms)가 대기중이다. 가장 짧은 P0를 수행한다.

7ms에 P0가 끝나고, 더 짧은 P1를 수행한다.

11ms에 P1이 끝나고 P2를 수행한다.

WT와 AWT를 계산해보자.

WT0 = 7 - 3 - 2 = 2ms
WT1 = 11 - 2 - 4 = 5ms
WT2 = 16 - 0 - 6 = 10ms
WT3 = 5 - 1 - 4 = 0ms

AWT = (2 + 5 + 10 + 0) / 4 = 4.25ms가 된다.

그럼 이게 FCFS였다면 어땠을까 비교해 보자.

들어온 순서가 명백히 P2, P3, P1, P0 순이므로,

WT0 = 16 - 3 - 2 = 11ms
WT1 = 14 - 2 - 4 = 8ms
WT2 = 6 - 0 - 6 = 0ms
WT3 = 10 - 1 - 4 = 5ms

AWT = (11 + 8 + 0 + 5) / 4 = 6ms가 된다.

SJF가 AWT를 더 짧게 만들어 주긴 한다는 것을 알 수 있다.

이번엔 Non-preemptive 방식을 살펴보자.

위 그림에서 표 밑에 시간 표시가 틀렸다. 신경쓰지말자.

말했다시피, Non-preemptive 방식은 새로 들어온 프로세스의 Burst time이 더 짧다고 해서 실행 중인 프로세스를 갈아끼지 않는다. 다만, 실행을 마친 후에 대기 중엔 프로세스 중에서 가장 빨리 끝날 수 있는 녀석을 선택하는 알고리즘이다.

0ms에서 P2가 들어오고 그대로 실행된다.

P2가 끝나는 시점인 6ms에 이미 P3(4ms), P1(4ms), P0(2ms)가 대기중에 있다. 가장 짧은 P0를 실행한다.

8ms에 P0가 끝나고, 남은 P3와 P1의 Burst time이 같으므로 먼저 온 P3를 실행한다.

12ms에 P3가 끝나고, P1를 실행한다.

WT0 = 8 - 3 - 2 = 3ms
WT1 = 16 - 2 - 4 = 10ms
WT2 = 6 - 0 - 6 = 0ms
WT3 = 12 - 1 - 4 = 7ms

AWT = (3 + 10 + 0 + 7) / 4 = 5ms이다.

위에서 같은 프로세스로 계산했던 SRTF의 4.25ms가 더 짧으므로 AWT를 줄이는 데에는 SRTF가 SJF보다 낫다는 것을 알 수 있다.

Priority Based Scheduler

각 프로세스에 우선순위를 배정하여 우선순위가 더 큰/작은 순으로 프로세스를 우선 배정하는 방식이다.

우선 순위를 결정하는 방법은 정적인 방법과 동적인 방법으로 나뉘는데,

  • 정적인 방법: 대기큐에 들어올 때 정해진 규칙에 따라 우선순위를 이미 부여 받고 들어온다.
  • 동적인 방법: 상황에 따라 프로세서가 우선순위를 flexible하게 변경한다.

장점

  • 중요한 작업을 먼저 처리할 수 있다.

단점

  • SJF와 비슷하게 우선순위가 밀리는 작업은 영영 실행되지 않을 수도 있다 (starvation)

이 방식도 Preemptive와 Non-preemptive가 있는데, 위 그림은 과연 무엇일까?

생각해 보자. 정답은 조금 밑에 있다.

아무튼, Priority가 낮을 수록 중요하다고 써져있으니 낮은 순으로 먼저 실행시키는 알고리즘이 되겠다. 이 부분은 설계에 따라 다르다.

프로세스 4개가 동시에 들어왔고 중요도는 P2 > P4 > P3 > P1이니 이대로 실행시키면 되겠다.

각 WT와 AWT는 그림을 참조하자.

그림을 보면 SJF보다 안 좋다고 나와있는데, 그럼 한번 SJF라고 가정하고 계산해보자.

Burst time이 짧은 순은 P4 < P1 < P3 < P2이니, 이 순서로 실행이 될 것이고

WT4 = 3 - 0 - 3 = 0ms
WT1 = 9 - 0 - 6 = 3ms
WT3 = 16 - 0 - 7 = 9ms
WT2 = 24 - 0 - 8 = 16ms

AWT = (0 + 3 + 9 + 16) / 4 = 7ms가 된다.

확실히 SJF방식이 AWT가 더 작긴 하다.

다음으로 가기 전에 위 질문의 정답을 발표하자면,

저걸로는 알 수 없다이다. 실행 중에 Priority가 더 우선되는 작업이 들어왔어야 알지...저걸로는 알 방법이 없다. 다만 도중에 중단이 없었으므로 Non-preemptive와 동일한 결과이긴 한다.

Non-preemptive의 경우에는 어쨌거나 실행 중인 프로세스는 계속 실행하고, 다음 프로세스 선택 시에 Priority를 보고 가장 우선되는 것을, 같은 게 2개 이상 있다면 먼저 온 녀석을 선택한다.

Preemptive 방식의 예제로 가져 온 그림이다.

P1에서 P2로, P2에서 P3으로 계속 Context Switching이 일어나는 것을 볼 때, 이전 예제와 마찬가지로 Priority가 작을 수록 우선된다는 것을 알 수 있다.

그리고 Priority based 방식의 단점이 명확하게 나와있는데, P1이 가장 먼저 들어왔음에도 불구하고 가장 마지막에 종료가 되는 것을 확인 할 수 있다.

Round Robin Scheduler

시분할의 핵심인 RR scheduler이다. 기본적으로는 FCFS방식으로 작동하지만 프로세스의 CPU 사용 시간에 제한을 두어 해당 시간 안에 작업을 마치지 못하면 대기큐의 끝으로 다시 돌아가는 방식이다.

장점

  • 모든 프로세스가 동시에 돌아가는 것처럼 (시분할) 동작하게 할 수 있다
  • 보다 나은 AWT를 제공한다.
  • Convoy effect를 피할 수 있다.
  • Starvation을 피할 수 있다.

단점

  • 필연적으로 많은 Context Switching이 일어난다
  • 제한 시간을 너무 짧게 설정하면 CPU가 작업을 처리하는 것보다 Context Switching에 더 많은 시간을 소모하게 될 수 있다.
  • 우선 순위가 세팅되기 힘들다 -> 보다 중요한 작업을 먼저 실행하기 힘들다.

가장 긴 실행시간이 4ms이므로 Time Quantum = 4ms 라는 것을 알 수 있다.

기본적으로 주어진 시간만큼 실행을 하지만 Remaining Time이 더 짧은 경우에는 조기에 실행을 끝마치고 다음 프로세스를 실행한다.

HRRN (Highest Response Ratio Next) Scheduler

SJF의 단점을 보완한 알고리즘이다.

SJF의 단점이라 하면, 긴 실행시간을 가진 프로세스는 계속해서 우선 순위가 밀린다는 것이다.

이를 보완해 비교 시에 (대기시간 + 실행시간) / 실행시간을 기준으로 비교해서 오래 기다렸다면 실행시간이 길더라도 우선권을 부여하는 방식이다.

장점

  • SJF보다 나은 퍼포먼스를 제공한다
  • 보다 긴 작업의 대기시간이 감소한다
  • 여전히 보다 짧은 작업의 우선 실행을 권장해 보다 나은 AWT를 제공한다.

단점

  • 모든 작업의 Burst Time을 미리 아는 것은 불가능 하기 때문에 실질적으로 구현이 불가능하다
  • CPU overload가 발생할 수 있다.

1ms에는 P1 밖에 없으므로 P1을 실행한다.

4ms에도 P2 밖에 없으므로 P2를 실행한다.

10ms에 P2의 실행이 끝나면 3개의 프로세스가 있다. 이 때, 각각의 Response Ratio는

RR3 = (5 + 8) / 8 = 1.625
RR4 = (3 + 4) / 4 = 1.75
RR5 = (2 + 5) / 5 = 1.4

가 된다. RR4가 가장 크기 때문에 P4를 실행한다.

14ms에 다시한번 RR을 비교한다.

RR3 = (9 + 8) / 8 = 2.125
RR5 = (6 + 5) / 5 = 2.2

가 되어, 더 큰 P5를 실행한다.

마지막으로 P3를 실행한다.

어쩌다 보니 위 예시가 평범한 SJF를 쓴 것과 다를 바 없는 결과가 나오게 됐는데,

P5의 AT를 9로 바꿔서 생각해보자.

P4의 실행까지는 동일할 것이고, 14ms의 시점에 RR를 계산하면

RR3 = (9 + 8) / 8 = 2.125
RR5 = (5 + 5) / 5 = 2

이렇게 나오게 된다. 이 경우에 RR3이 더 크기 때문에 P3가 실행되게 된다.

Multiple Queue Scheduling

프로세스를 종류별로 구분해 각각의 큐를 두고, 각 큐마다 우선순위를 부여한 방식이다.

장점

  • Scheduling overhead의 발생 가능성이 낮다.

단점

  • Starvation 발생 가능성이 있다.
  • 큐 사이의 이동이 불가능하다 -> 실상황에서 유연하지 못하다.
  • 구현이 복잡하다.

보통 위 그림의 3가지로 구분하는데,

System processes: System에 연관된 것이니 만큼, 이게 처리가 안되면 다른 모든 작업이 다 망할 수 있기 때문에 가장 중요하다.

Interative Processes: Foreground Processes라고도 한다. 사용자와 상호작용 하는 프로세스이기 때문에 응답이 빨라야 한다. 다시 말해, 처리 우선순위가 높아야 한다.

Batch Processes: Background Processes라고도 한다. System에서 쓰는 것도 아니고, 빠른 응답이 필요한 것도 아니기 때문에 상대적으로 우선순위가 떨어진다.

이렇게만 보면, Priority Based Scheduler의 큐를 그냥 3등분 해놓을 것으로 밖에 보이지 않는데, 이 방식의 핵심은 각각의 큐가 각각의 스케쥴링 방식을 가지고 있다는 것에 있다.

중요하니까 다시 말한다.

각각의 큐가 각각의 스케쥴링 방식을 가지고 있다

예를 들어, System queue는 Priority based Scheduling을, Interative queue는 RR Scheduling을, Batch queue는 FCFS Scheduling을 할 수 있다는 것이다.

동시에 큐끼리는 Priority based Scheduling이 적용되기 때문에 보다 빠른 처리가 필요한 작업을 우선처리 할 수 있다.

Multilevel Feedback Queue Scheduling

MQS의 단점을 보완한 방식으로, 큐 사이의 이동이 가능해졌다.

장점

  • 프로세스들의 큐 간 이동이 가능하다 -> 실상황에서 유연하다
  • Starvation 방지에 유효하다.

단점

  • CPU overhead 발생 가능성이 있다.
  • 구현 시 가장 복잡한 알고리즘이다.

그림에 없는 부분이 조금 있다. 글로 설명하겠다.

MFQS의 특징은 다음과 같다.

  • 각 큐 사이에는 우선 순위가 있다.
  • 각 큐는 자기만의 Scheduling Algorithm을 가지고 있다.
  • 주어진 시간 내에 실행을 마치지 못한 프로세스는 하위 큐로 이동한다.
  • 대기 시간이 길어진 프로세스는 상위 큐로 이동한다 -> Starvation 방지.
  • 각 프로세스의 중요도에 따라 처음 삽입되는 큐가 다르다 (그림에 없는 부분).

하여, 위 그림을 해석하자면 가장 우선되는 큐에 들어온 프로세스는 TQ=9 즉, 9ms의 CPU 이용시간을 가진다. 그 안에 작업을 끝마쳤다면 탈출하고, 그러지 못했다면 TQ=18짜리 하위 큐의 끝으로 이동한다. 한 마디로 RR의 변형 버전이다.

거기서도 작업을 끝내지 못했다면 마지막 큐인 FCFS 큐에 들어간다. 이 때, Convey Effect 등이 발생해 대기시간이 너무 길어지면 다시 상위큐로 올라간다.

이 과정을 반복한다.

References

profile
얄루얄루
시간아 늘어라 하루 48시간으로!
이전 포스트

[CS] OS와 Process

다음 포스트

[CS] IPC

0개의 댓글