프로세스 스케줄링

프로세스 스케줄링

 - CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 일이다.

 - CPU가 쉬지 않고, 계속 열심히 일할 수 있도로고 효율적인 계획을 잡아주는 것이다.

 

 

스케줄링의 목적 

 1. 시스템의 성능 향상

  가. CPU 처리율과 이용률 증가

  나. 오버헤드 최소화 

  다. 응답시간, 대기시간, 반환시간 최소화

 

 2. 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택하는 것이 필요 

 

스케줄링 기준

 1. 우선순위 ex) CPU Burst vs IO Burst(I/O 사용시간)

 2. 긴급성 

 3. 특성

 

스케줄링 단계 

 1. Long-term 스케줄링

  어떤 프로세스를 커널에 등록할 것인가를 결정하는 스케줄링

 2. Mid-term 스케줄링

  어떤 프로세스에게 메모리를 할당할 것인가를 결정하는 스케줄링

 

 

 3. Short-term 스케줄링

  어떤 프로세스에게 CPU를 할당할 것인가를 결정하는 스케줄링 

스케줄링 선점&비선점 

 스케줄링은 적용 시점에 따라 선점과 비선점형으로 구분한다. 

1. 선점

 다른 프로세스가 선점한 자원을 빼앗아 갈 수 있다.

 가. 타의에 의해 선점한 자원을 빼앗길 수가 있다. ex) 할당시간이 종료, 우선순위가 높은 프로세스의 등장

 나. Context switch overhead가 크다.

 다. 시분할 시스템, 리얼타임 시스템에 적합한 방법이다.  

2. 비선점

 다른 프로세스가 선점한 자원을 빼앗아 갈 수 없다.  

 가. 할당자원을 스스로 반납할때까지 사용한다. 

 나. Context switch overhead가 적다.

 다. 잦은 우선순위 역전, 평균 응답시간이 증가한다.

 

스케줄링의 우선순위 

 프로세스의 우선순위 변동 여부에 따라 정적 스케줄링과 동적 스케줄링으로 구분한다. 

1. 정적 우선순위 

 가. 프로세스에 부여된 우선순위가 바뀌지 않는다. 

 나. 구현이 쉽고 Overhead가 적다. 

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

 

2. 동적 우선순위

 가. 스케줄링 과정에서 프로세스의 우선순위를 변동시킨다. 

 나. 구현이 복잡하고, Overhead가 크다. 

 다. 시스템 환경 변화에 유연하게 대응이 가능하다. 

 

스케줄링 기법 

 스케줄링 기법은 선점형과 비선점형 스케줄링으로 나뉜다. 

1. 비선점형 스케줄링 

 가. FIFO(FCFS) - First In First Out

  1) 선입선출 방식(먼저 들어오면 먼저 나가는 방식)

  2) 우선순위에 상관없이 먼저 도착한 프로세스를 먼저 처리한다. 

  3) FIFO 단점

   가) 긴 평균 응답시간

   나) Convey effect 발생 

Convey effect: 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게 되는 현상
(대기시간 > 실행시간)

 

  나. SJF(SPN) - Shorst Job First

   1) CPU점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식이다. 

   2) SJF의 장점

    가) 평균 대기시간 최소화 

    나) 시스템 내 프로세스 수 최소화 

    다) 메모리 절약 -> 시스템 효율 향상 

   3) SJF의 단점 

    가) Starvation(무한대기) 현상 발생

Starvation(무한대기): CPU점유시간이 긴 프로세스가 짧은 프로세스에게 계속 밀려 자원을 할당 받지 못하는 상태 

    나) 정확한 실행시간을 알 수 없음  

 

  다. HRN - Highest Response-ratio Next)

   1) SJF기법을 보완하기 위한 것으로 대기 시간과 실행 시간을 이용하여 처리하는 방식이다.  

   2) Response-ratio의 에이징 기법을 이용하여 우선순위를 계산하여 우선순위가 높은 것부터 처리한다.

Response-ratio: 우선순위 = (대기시간+실행시간) / 실행시간

에이징 기법: 프로세스 자원을 기다리고 있는 시간에 비례하여 우선순위를 부여함으로써 무기한 연기의 문제를 방지하는 기법을 말한다.

   3) HRN의 장점

     가) Starvation 방지

   4) HRN의 단점

     가) 실행시간 예측 불가

 

2. 선점형 스케줄링

 가. RR - Round Robin

  1) 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU를 할당하는 방식이다. 

  2) 자원 사용에 제한된 시간이 있으며 할당된 시간이 지나면 자원을 반납(Time Quantum)해야 한다. 

  3) 실시간 시스템에 유리하다. 

  4) RR의 장점

   가) 특정 프로세스의 자원 독점을 방지

  5) RR의 단점 

   가) Context Switch Overhead가 큼

 

 나. SRTN - Shortest-Remaining Time Next)

  1) 비선점 스케줄링인 SJF기법을 선점형태로 변경한 방식이다. 

  2) SJF기법과 마찬가지로 CPU점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식이다. 

  3) 만약 중요한 프로세스가 있으면 점유시간이 길어도 먼저 실행시킬 수 있는 권한이 추가되었다. 

  4) SRTN의 장점 

   가) SJF 기법의 장점 극대화

  5) SRTN의 단점

   가) Context Switch Overhead가 큼 

 

 다. MLQ - Multi-Level Queue

  1) 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 Ready Queue를 사용하는 방법이다. 

  2) 각각의 Ready Queue는 자신만의 스케줄링 기법을 사용하되, 최초 배정된 Queue를 벗어나지 못한다. 

  3) 각각의 Ready Queue 사이에는 우선순위 기반의 스케줄링이 적용된다.

   ex) QueueA가 모두 완료되어야 QueueB의 작업이 실행된다. 

  4) MLQ의 단점 

   가) 여러개의 큐를 관리해야 하기 때문에 스케줄링 Overhead가 발생하기 쉬움 

   나) 우선순위가 낮은 Queue는 Starvation 현상이 발생

 

 라. MFQ - Multi-Level Feedback Queue

  1) MLQ에서 최초 배정된 Queue를 벗어나지 못하는 기법을 보완하여 프로세스 Queue들 간의 이동이 허용될 수 있도록 개선한 기법이다. 

  2) Feedback을 통해 우선순위를 조정한다.

Feedback: 현재까지의 프로세서가 사용되었던 정보(패턴)들을 활용 

  3) Feedback의 장점

   가) 프로세스에 대한 사전 정보없이 SJF, SRTN, HRN 기법의 효과를 볼 수 있음 

  4) Feedback의 단점

   가) 설계 및 구현이 복잡

   나) 우선순위가 낮은 큐는 Starvation 현상 발생 

   다) 스케줄링 Overhead가 큼 

 

스케줄링 기법 정리 

---

<참고자료>

 

https://www.youtube.com/watch?v=EdTtGv9w2sA&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

 

<Computer structures> chapter 7,  프로세서 스케줄링 end>

---