[운영체제] 스케줄러와 운영체제의 성능 지표

스케줄러란?

여러 프로세스와 스레드가 동시에 실행되는데,
스케줄러는 이들 중 어느 것이 CPU를 사용할지 결정한다.

스케줄러는 공정하게 처리하고, 시스템 성능을 최적화하며,
사용자에게 반응적인 시스템을 제공하는데 목적을 준다.

스케줄링을 하기 위한 Queue

Job Queue

한재 시스템 내에 있는 모든 프로세스의 집합

Ready Queue

현재 메모리 내에 있으면서 CPU에 할당 받기를 기다리는 프로세스의 집합

Device Queue

Device I/O 작업을 대기하고 있는 프로세스의 집합

운영체제를 평가하기 위한 지표

다음 요소들은 운영체제들을 평가하기 위한 지표이다.
스케줄링 방식에 따라 운영체제의 성능이 달라진다.

CPU 사용률

CPU 가 idle 이 나지 않을 수록 높은 성능으로 취급한다.

처리율(Throughput)

단위 시간당 완료하는 작업의 수가 많을 수록 높은 취급한다.

반환시간(Turnaround Time)

프로세스가 Ready Queue에 진입한 순간부터 완료되기까지 걸린시간
= Waiting Time + BurstTime(CPU에 할당된 시간) + I/O Time

대기시간 (Waiting Time)

프로세스가 CPU를 점유하기 위해 대기한 총 시간

Ready Queue에서 있었던 총 시간을 의미한다.

반응시간 (Response Time)

프로세스가 CPU를 첫 점유하기 까지 Ready Queue에서 대기한 시간

스케줄러의 종류

장기스케줄러(Long-term scheduler or job scheduler)

메모리는 한정적인데 이 용량이 넘도록 많은 프로세스들이 한꺼번에 메모리에 올라온 경우
대용량 메모리(일반적으로 디스크)에 임시로 저장된다.

이 pool 에 저장되어 있는 프로세스 중
어떤 프로세스에 메모리를 할당하여 Ready Queue 로 보낼지 결정하는 역할을 한다.

• 메모리와 디스크 사이의 스케줄링을 담당
• 프로세스에 메모리 및 각종 리소스를 할당(admit)
• degree of Multiprogramming 제어
• 프로세스 상태 new -> ready (in memory)

참고로 time sharing system 에서는 장기 스케줄러가 없다.
그냥 곧바로 메모리에 올라가 ready 상태가 된다.

단기 스케줄러(Short-term scheduler or CPU scheduler)

• CPU 와 메모리 사이의 스케줄링을 담당.
• Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.
• 프로세스에 CPU 를 할당(scheduler dispatch)
• 프로세스의 상태 ready -> running -> waiting -> ready

중기 스케줄러(Medium-term scheduler or Swapper)

• 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
• 프로세스에게서 memory 를 deallocate
• degree of Multiprogramming 제어
• 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.
• 프로세스의 상태 ready -> suspended

Process state - suspended

Suspended(stopped)
외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미한다.
프로세스 전부 디스크로 swap out 된다.
blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에
스스로 ready 로 돌아갈 수 있지만
이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없다.

CPU 스케줄러

단기 스케줄러(Short-term scheduler or CPU scheduler) 를 CPU 스케줄러라도 한다.
Ready Queue에 있는 것을 CPU에 할당한다.

알고 들어가야할 개념

Convey Effect

긴 작업을 필요로하는 프로세스가 오래 점유하게 되면
짧은 작업을 처리하는 프로세스 가 오랫동안 기다리는 문제

Starvation

특정 프로세스가 무한정 기다리는 현상

예를들어 priority를 기다려서 실행할 순서가 되었지만,
또다시 자신보다 높은 priority를 가진 프로세스가 들어온다면 계속 기다려야 한다.

해결책 : aging 기법

일정 시간이 지나면 프로세스의 우선순위를 높여주는 aging 기법 등이 사용된다.

구분법

Convey Effect는 CPU에 할당된 프로세스 때문에
Ready Queue의 다수 프로세스가 오래 기다리는 현상

Starvation은 특정 프로세스가 본인의 문제(ex.우선운쉬 낮음) 때문에 오래 기다리는 현상

비선점 스케줄링

프로세스에게 CPU가 할당되면 그 프로세스가 종료되거나,
입출력 같은 이벤트가 발생하여 실행을 멈출 때까지
CPU를 계속 점유하도록 허용하는 스케줄링 전략

구현이 간단하고 Context Switching 이 적어서 오버헤드가 적지만
공정성이나 효율성 면에서는 선점 스케줄링 방식보다 떨어진다.

FCFS (First Come First Start) 스케줄링

먼저 Ready Queue에 온 순서대로 처리한다.

Convey Effect 우려
먼저 들어온 프로세스의 실행시간이 극한으로 긴 경우, 뒤에 들어온 프로세스들이 할당되기까지 오래걸림

예제

ABCD가 거의 동시에 입력되었다고 가정

SJF (Shortest Job First) 스케줄링

Ready Queue에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을
우선적으로 CPU에 할당하는 방식이다.

Starvation 우려
특정 프로세스의 실행 시간이 극한으로 긴 경우 할당되기까지 오래 걸림

예제 1

ABCD가 거의 동시에 입력되었다고 가정

에제 2

4개의 프로세스가 1단위의 CPU 사이클 시간의 차이를 두고 연속적으로 입력된다고 가정

Priority 스케줄링

우선순위가 가장 높은 프로세스부터 CPU에 할당한다.

우선순위를 정하는 기준은
프로세스의 연산량, 메모리 요구량, 입출력 요구량 등 다양하다.

Starvation
높은 우선순위의 프로세스가 지속적으로 들어오는 경우 낮은 프로세스들의 응답시간이 느려진다.

우선순위 역전(priority inversion)

우선순위가 높은 프로세스가 공유자원의 접근 권한을 확득하는 동안
낮은 순위의 프로세스가 먼저 종료되어서 우선순위가 높음에도 불구하고 나중에 종료되는 문제

발생 시나리오 설명과 그림의 순서는 관계없다.

P3, P1, P2 프로세스가 순서대로 들어왔다고 가정하자. (숫자는 우선순위를 의미한다.)
이때 P3 과 P1 은 공유 자원을 필요로한다.
P1은 실행 중간에 공유 자원을 필요로한다.

1. P3 이 우선 실행된다. 공유자원 접근권한을 획득한다.
2. P1 이 들어와서 CPU에 할당되고 중간에 공유자원을 필요로한다.
3. P3가 공유자원 접근 권한을 반환해야하므로 CPU에 할당된다.
   이때 P1는 Waiting(또는 Blocking) 상태가 된다.
4. 반환 과정 중 P2 가 들어오는데 P1이 Waiting 상태이므로 P2가 CPU에 할당된다. 우선순위의 역전
5. P2 종료
6. P3가 다시 공유자원 반환을 위해 CPU에 할당된다.
7. p3 종료
8. P1 가 CPU에 할당된다.
9. P1 종료

---

해결책 1: 우선순위 상속

공유자원을 반납하는 과정에 있는 프로세스(p3)의 우선순위를
공유자원을 필요로하는 프로세스(p1)의 우선순위로 변경한다.

공유자원 반납 도중 중간 우선순위의 프로세스(p2) 가 들어온다고 해도
우선순위 역전 현상이 발생하지 않는다.

해결책 2: 우선순위 올림
공유자원 접근 권한을 소유하는 동안 지정된 우선순위로 올린다.
지정된 우선순위로 올린다.

원래 우선 순위가 올림값보다 작은 경우에만 우선순위를 변경한다.
예를 들어 프로세스의 원래 우선순위가 3 이고 올림값이 5 이면 유지한다.

HRRN (Hightest Response Ratio Next) 스케줄링

Ready Queue의 프로세스 중 응답 비율이 가장 큰 것을 먼저 CPU 에 할당한다.
즉, 대기시간이 길고 예상 실행시간이 짧을수록 먼저 할당된다.

응답 비율을 다음과 같이 계산한다.

SJF 스케줄링에서 일어나는 Starvation을 해결한 전략이다.
실행 시간이 긴 프로세스라도 대기시간이 길어지면 우선순위가 높아진다.

---

선점형 스케줄링

하나의 프로세스가 CPU를 점유하고 있을 때,
다른 우선순위가 더 높은 프로세스가 도착하면
현재 실행 중인 프로세스를 중단하고 새로운 프로세스에게 CPU를 넘겨주는 방식의 스케줄링

SRTF (Shortest Remaining Time First) 스케줄링

SJF 스케줄링의 선점(preemptive) 개선 버전

새로 들어오는 프로세스를 포함하여
예상 실행시간이 가장 짧은 프로세스를 먼저 CPU 에 할당

SRT가 SJF 보다 평균 대기 시간(Average waiting time)이나
평균 반환 시간(Average response time)에서 효율적이다.

새로운 프로세스가 들어올때마다 스케줄링을 다시하기 때문에 구현이 어렵다.

Starvation
예상 실행시간이 극한으로 긴 경우, 실행되기까지 오래걸린다.

예제 1

4개의 프로세스가 1단위의 CPU 사이클 시간의 차이를 두고 연속적으로 입력된다고 가정

RR (Round Robin) 스케줄링

프로세스가 도착한 순서대로 프로세스를 CPU에 할당하지만
정해진 시간 할당량(Time Slice)에 이해 실행을 제한한다.

Time Slice 안에 완료하지 못한 프로세스는
Ready Queue 맨 뒤에 배치되도록하여 공정성을 보장한다.

Time Slice 가 너무 길면 FCFS와 다를게 없다.
Time Slice 가 너무 짧으면 Context Switching이 많이 일어나서 과한 오버헤드가 발생한다.

예제

4개의 프로세스가 주어지고 시간 할댱량은 3이라고 가정

MLQ (MultiLevel Queue Scheduling) 스케줄링

대화형, 배치 등 프로세스 성격에 따라 배치할 여러 Queue 들를 형성한다.
각 큐는 항상 가장 높은 우선순위의 큐의 프로세스를 CPU에 할당한다.

각 Queue에는 독자적인 스케줄링 기법을 적용할 수 있다.
큐들 간의 프로세스 이동이 불가능하기 때문에 스케줄링 부담이 적지만 유연성이 떨어진다.

starvation
우선 순위가 낮은 프로세스는 오래 기다린다.

MFQ (MultiLevel Feedback Queue Scheduling) 스케줄링

MLQ의 단점인, 큐들 간의 프로세스 이동이 불가능해 유연성이 떨어진다는 것을 해결한 스케줄링

MFQ도 MLQ 처럼 각 큐마다 스케줄링 방식이다르다.
그리고 각 큐는 프로세스를 실행할 수 있는 단위 시간이 정해져있다. * 스케줄링 + RR
단계가 내려갈 수록 단위시간은 커진다.

해당 단계에서 할당받은 시간동안 모든 작업을 끝내지 못하면
다음 단계의 큐로 이동한다.

마지막 단계의 스케줄링 은 FCFS 또는 RR 스케줄링을 사용한다.

Starvation: FCFS
가장 마지막 단계에서 더이상 이동할 단계가 없기 때문에 피할 수 없다.

Time Slice
가장 마지막 단계의 할당 시간이 길기 때문에 Context Switching 오버헤드가 많이 발생한다.
따라서 긴 작업시간을 요구하는 프로세스들이 다수 존재한다면 위 현상이 발생할 수 있다.