[운영체제] 5. 스케쥴링

 

---

스케쥴링이란 무엇이고 왜 해야하는 것일까?

 

우리가 현재 사용하고 있는 시스템에는 여러 개의 프로세스가 있다. 우리는 이런 환경을 다중 프로그래밍 환경이라고 부른다.

 

프로세스가 다수이기 때문에 한정된 자원을 나눠서 사용해야 하고, 운영체제는 프로세스에게 알맞게 자원을 할당해야 하는 의무가 있다.

 

운영체제가 자원을 관리하는 방법에는 크게 두 가지 방법이 있다.

 

• 시간 분할 관리 (Time Sharing)
  • 하나의 자원을 여러 스레드가 번갈아가며 사용
  • 하나의 프로세서는 하나의 프로세스만 실행시켜야 하기 때문에, 프로세스에게 프로세서 할당 시, 사용시간을 프로세스에게 분배
  • 옛날에 동생이랑 컴퓨터 한대로 게임할 때, 서로 번갈아가면서 게임했던 기억이 난다.

 

• 공간 분할 관리 (Space Sharing)
  • 하나의 자원을 분할하여 동시에 사용
  • 메모리 할당 시, 메모리의 공간을 여러 프로세스에게 분배

 

운영체제가 프로세스에게 자원을 알맞게 할당해주는 것을 우리는 스케쥴링(Scheduling)이라고 할 것이다.

 

운영체제가 스케쥴링을 잘해준다면, 시스템의 성능이 향상된다. 근데 성능이란 말은 굉장히 모호하다... 시스템의 성능?

 

 

 

시스템의 성능을 측정하는 지표는 대표적으로 3가지가 있다.

 

• 응답시간 (Response Time)
  • 작업 요청으로부터 응답 받을 때 까지의 시간
  • Interactive System이나 Realtime System과 같이 응답시간이 중요한 시스템에 중요한 성능지표

 

• 작업처리량 (Throughput)
  • 단위 시간동안 완료된 작업의 수
  • Batch System에 중요한 성능지표

 

• 자원 활용도 (Resource Utilization)
  • 주어진 시간 동안 자원이 활용된 시간
  • 비싼 System과 같이 자원이 최대한 놀면 안되는 시스템에 중요한 성능지표

 

 

이 외에도 공평성, 실행대기방지, 예측가능성 등 성능지표기준은 굉장히 많다.

 

각 시스템의 목적에 맞는 지표를 고려하여 스케쥴링 기법을 활용해야 한다.

 

 

 

우리는 이제 각 시스템들이 실제로 활용하고 있는 스케쥴링 알고리즘에 대해 알아볼 것이다.

 

하지만 그 전에 스케쥴링에 관련된 용어나 정책 등에 대해 짚고 넘어가자.

 

 

 

 

관련용어

• 대기시간 (Waiting Time) : 프로세스가 실행 준비된 상황부터 실제로 실행이 되기 까지의 시간
• 응답시간 (Response Time) : 프로세스가 실행 준비된 상황부터 첫번째 출력(응답)이 되기 까지의 시간
• 실행시간 (Burst Time) : 실행이 시작되고부터 실행이 종료될 때 까지의 시간
• 반환시간 (Turn-around Time) : 프로세스가 실행 준비된 상황부터 실행이 종료될 때 까지의 시간

 

 

 

스케쥴링 정책

• 비선점 (Non-preemptive)
  • 할당받은 자원을 스스로 반납할 때 까지 사용한다.
  • 단어 그대로, 할당받은 자원을 타의에 의해서 다른 프로세스로 부터 점유당하지 않는다.
  • Context Switch Overhead가 줄어드는 장점이 있다.
  • 프로세스가 스스로 반납할 때 까지 자원이 사용되기 때문에 평균 응답시간이 증가하는 단점이 있다.

 

• 선점 (Preemptive)
  • 비선점 방식과 반대로 타의에 의해서 자원을 뺏길 수 있다.
  • 운영체제의 판단하에 적절한 프로세스를 선택해 자원을 주고 빼앗기 때문에, 사용자 입장에선 응답성이 좋은 장점이 있다.
  • Context Switch Overhead가 큰 단점이 있다.

 

• 정적 우선순위 (Static Priority)
  • 처음 프로세스가 생성될 때, 우선순위가 정해짐
  • 구현이 쉽고, Overhead가 적음
  • 시스템 환경변화에 대한 대응이 어려움

 

• 동적 우선순위 (Dynamic Priority)
  • 프로세스의 상태에 따라 우선순위가 변경됨
  • 구현이 복잡하고 우선순위 계산의 Overhead가 크다.
  • 시스템 환경변화에 유리

 

 

 

스케쥴링 알고리즘

 

알고리즘 이름으로 약어가 표기되지만 풀네임을 보면 별거 없다.... 쫄지말자.

그리고 프로세스 = 똥 싸야하는 사람, 자원 = 변기 라고 상상하면 이해하기 되게 쉽다...

 

• FCFS (First Come First Service)
  • Non-preemptive 기법
  • Ready Queue에 도착한 프로세스 순서대로 서비스를 수행
  • 자원을 효율적으로 사용할 수 있다.
  • Batch System에 적합하고, Interactive System에 부적합하다.
  • 수행시간이 긴 하나의 프로세스 때문에 나머지 짧은 프로세스들이 기다려야하는 단점이 있다 -> 영어로 Convoy Effect...
  • 평균 응답시간이 길다.
  • 1차선 도로 혹은 하나의 변기에 일렬로 줄 서는 화장실과 비슷함 (변비 걸린 한 명 때문에 나머지가 기다려야함 ㅠㅠ)

[그림1] FCFS Scheduling

 

• RR (Round Robin)
  • Preemptive 기법
  • 위와 마찬가지로 Ready Queue에 도착한 프로세스 순서대로 서비스를 수행하지만, 각각의 프로세스들에게 제한시간(Time Quantum) 이 있다.
  • 프로세스는 할당된 시간이 지나면 자원을 반납해야 한다. 변비 걸린 놈의 변기 독점을 방지하기 위함이다.
  • Context Switch Overhead가 크다.
  • 응답시간이 짧기 때문에 Interactive System이나 Time Sharing System에 적합한 스케쥴링 기법이다.
  • 제한시간 (Time Quantum)이 성능에 큰 영향을 미칠 수 밖에 없다. Time Quantum이 너무 크면 위의 FCFS와 같아지고, 너무 짧으면 Context Switch Overhead가 커지기 때문이다.

[그림2] Round Robin Scheduling

 

• SPN (Shortest Process Next) or SJF (Shortest Job First)
  • Non-preemptive 기법
  • 프로세스의 실행시간이 가장 작은 프로세스를 먼저 수행시킨다. 똥을 빨리 쌀 수 있는 놈부터 변기에 앉히는 것...
  • 평균 대기시간이 최소화 됨
  • 시스템 내의 프로세스 수가 최소화되고, 스케쥴링 부하 감소, 메모리 절약 등 시스템 효율이 향상
  • 하지만 프로세스의 정확한 실행시간은 알 수 없기 때문에, 실행시간을 예측하는 기법이 필요하다.
  • 무한대기 (Starvation) 상황이 발생할 수 있다. 실행시간이 긴 프로세스는 계속해서 기다려야 하는 현상이다.

 

• SRTN ( Shortest Remaining Time Next)
  • Preemptive 기법
  • 위 SPN기법의 변형 기법으로, 잔여 시간이 적은 프로세스가 등장하면 자원을 선점한다.
  • SPN의 장점이 극대화된다.
  • 위와 마찬가지로 프로세스의 실행시간을 예측하는 기법이 필요하고, 잔여시간을 계속 추적해야 해서 Overhead가 너무 큼
  • 구현 및 사용이 비현실적이다.

 

• HRRN(High Response Ratio Next)
  • Non-preemptive 기법
  • 이것도 마찬가지로 SPN기법의 변형 기법이다.
  • 위 SPN기법의 무한대기 현상을 해결하기 위해 프로세스의 대기시간까지 고려하여 스케쥴링 함 -> 영어로 Aging 기법
  • 여전히 프로세스의 실행시간을 예측해야한다는 단점이 있다.

 

• MLQ (Multi Level Queue)
  • 작업이나 우선순위에 따라서 Ready Queue가 여러개 있다.
  • 프로세스는 최초 배정된 Queue를 벗어날 수 없고, 각각의 Queue는 자신만의 스케쥴링 기법을 사용
  • Queue들 사이에는 우선순위 기반의 스케쥴링 기법을 사용
  • 여러개의 Queue를 관리해야하기 때문에 스케쥴링 Overhead가 큼
  • 우선순위가 낮은 Queue는 무한대기 (Starving) 현상이 발생할 수 있다.

[그림3] MLQ Scheduling

 

• MFQ (Multi level Feedback Queue)
  • 프로세스의 Queue간 이동이 허용된 MLQ기법으로, Feedback을 통해 우선순위 조정
  • 프로세스에 대한 사전 정보없이 위의 SPN, SRTN, HRRN 기법과 같은 효과를 낼 수 있음.
  • 하지만 설계 및 구현이 복잡하고, 여전히 Starvation현상이 남아있다.