[OS] 5. Process Scheduling 1

왜 프로세스 스케줄링을 해야할까?

하나의 프로세스가 아닌 다중 프로세스를 운영하게 될 경우, 프로세스들의 우선 순위를 조정해주는 일은 매우 중요하다. 중요한 일이라면 우선순위를 높여 자원을 할당해주어 먼저 처리해야하고, 상대적으로 우선순위가 낮은 프로세스는 후순위로 처리하여 효율적/효과적으로 업무를 수행할 필요가 있다. 즉, 프로세스 스케줄링은 다중 프로그래밍(프로세스가 여러 개) 환경에서 필요한 것이다.

 

스케줄링 : 자원을 할당할 프로세스를 선택하는 행위

 

자원을 관리하는데에는 두 가지 방법이 있다.

시간 분할(time sharing) 관리

• 하나의 자원을 여러 스레드들이 번갈아가며 사용 (ex. CPU(프로세서))
• 프로세스 스케줄링 : 프로세서 사용시간을 프로세스들에게 분배.
  • ex. 1 ~ 10초 까지는 Pa 프로세스, 11 ~ 20초 까지는 Pb 프로세스.

공간 분할(space sharing) 관리

• 하나의 자원을 분할하여 동시에 사용
• ex. 메모리

스케줄링의 목적

스케줄링의 목적은 당연히 "시스템의 성능을 향상" 시키는데 있다. 이러한 성능은 정성적인 평가가 아닌 수치로의 평가가 필요하기 때문에, 정량적으로 측정하기 위해 사용되는 지표가 있다. 또한 모든 지표를 우선적으로 고려하여 평가할 수 없으니, 목적에 맞는 지표를 고려하여 스케줄링 기법을 선택할 필요가 있다.

• 응답시간
  • 작업 요청으로부터 응답을 받을 때 까지의 시간
  • ex) interactive, realtime system같은 상황에 중요한 성능 지표가 된다.
• 작업 처리량
  • 단위 시간 동안 완료된 작업의 수
  • ex) 일괄 처리(batch) 시스템
• 자원 활용도
  • 주어진 시간(Tc)동안 자원이 활용된 시간(Tr) (= Tr/Tc)
  • ex) 비싼 장비일 경우 활용도가 중요.

위 3개 뿐만 아니라 다양한 성능 지표들이 존재한다. (ex. 반환 시간, 예측 가능성, 공정성 등등)

대기 시간, 실행 시간, 응답 시간, 반환 시간

프로세스가 도착했을 때 기다리고 있다가 실행이 시작하기 전까지의 시간을 "대기 시간"

프로세스 도착 이후 작업이 수행되다가 첫 응답이 오기까지의 시간을 "응답 시간"

실제로 프로세스가 실행된 시간을 "실행 시간"

프로세스 도착 이후 원하는 일이 모두 끝난 시간을 "반환 시간"이라고 한다.

스케줄링의 기준

기준이라고 하면 스케줄링 기법이 고려하는 항목들을 말한다. 즉, 스케줄러가 어떠한 결정을 해야할 때 해당 기준들을 가지고 선택을 하게 된다.

• 프로세스의 특성
  • I/O bounded 또는 compute-bounded
• 시스템 특성
  • Batch system 또는 interactive system
• 프로세스의 긴급성(urgency)
  • Hard / Soft Real-time , non Real-time
• 프로세스 우선순위 (priority)
• 프로세스 총 실행 시간 (total service time)

CPU burst VS I/O burst (feat. 프로세스의 특성)

프로세스는 입출력을 받기도 하고, 프로세서(CPU)를 할당 받아 연산하는 업무를 수행하기도 한다.

이를 수행 흐름으로 표기하면 아래와 같이 볼 수 있다.

 

A 연산 > B 입출력 대기 > B 연산 > C 입출력 대기 > C연산

 

이와 같이 반복되면서 프로세스가 수행되어 프로세스는 CPU사용 + I/O 대기로 이루어져 있음을 알 수 있다.

 

• CPU burst (=CPU 사용 시간)
• I/O burst (= I/O 대기 시간)

여기서 CPU를 더 많이 사용하는 것, CPU 사용시간이 더 긴 것을 Compute Bounded라고 하고, I/O 대기 시간이 더 긴 것을 I/O Bounded라고 한다.

 

• Compute-bounded : CPU burst > I/O burst (= 연산에 의해서 성능이 결정된다)
• I/O-bounded : CPU burst < I/O burst (= I/O에 의해 성능이 결정된다)

스케줄링의 단계

발생하는 빈도 및 할당 자원에 따라 그 단계를 구분하게 된다.

Long-term Scheduling

빈도가 가끔 있는 정도의 작업을 말한다.

대표적으로 job scheduling이 long-term에 속한다.

• Job scheduling
  • 커널에 등록할 작업(job)을 결정한다.

일전에 프로세스 관리에서 job을 등록하면 프로세스가 생성된다고 했었다. 이 때문에 시스템 내의 프로세스들의 수를 조절할 수 있게 되고, 크게 봤을 때는 다중 프로그래밍의 degree를 조절하는 것과 같게 된다.

 

또한 위에서 봤던 I/O-bounded와 Compute-bound 프로세스들을 적절하게 섞어서 선택해줘야 한다. CPU 연산만 열심히 한다면 I/O를 받을 수가 없게 되고, I/O만 너무 받게 되면 연산이 일어나지 않아 모두 비효율적인 상황을 초래할 수 있다. 그렇기에 잘 섞어서 작업을 처리해줘야 한다!

 

아까 봤던 시분할 시스템 같은 경우는 그 자체가 시간 단위로 나뉘어 있기 때문에, 모든 작업을 시스템에 등록하여도 무방하다. 즉 long-term 스케줄링이 덜 중요하다고도 볼 수 있다.

Mid-term Scheduling

메모리 할당을 결정하는 것이 mid-term scheduling이다. 프로세스 관리에서 swap-in 하여 supended-ready 상태의 프로세스에 메모리를 할당하여 ready 상태로 만들어 주는 것 과 같다.

 

입출력보다는, 메모리가 swapping(swap-in/out)되는 빈도가 조금 더 잦기 때문에 mid-term scheduling이 되는 것이다.

하지만 이보다 더 빈번하게 발생하는 것을 short-term scheduling이라고 하는데, 이 또한 프로세스 상태 관점에서 봐보자.

Short-term Scheduling

• Process scheduling
  • 저수준의 스케줄링
  • 프로세서(cpu)를 할당할 프로세스를 결정한다.
  • 즉 ready 상태에서 cpu를 할당하여 running 상태로 만들어주는 것과 같다.

가장 빈번하게 발생하기 때문에, 가장 빨라야 한다. 

스케줄링 단계를 프로세스 상태 변화 다이어그램에서 보면 아래와 같다.

스케줄링 단계

스케줄링 정책

스케줄링 방법에 대한 것이다!

선점(preemptive) VS 비선점(Non-preemptive) 

선점과 비선점의 차이는 누군가 빼앗을 수 있는지 여부에 그 차이가 있다.

Non-preemptive scheduling

• 할당 받을 자원을 스스로 반납할 때 까지 사용 (뺏기지 않는다)
  • system call, I/O 등
• 장점
  • Context switch overhead가 적다
• 단점
  • 평균 응답 시간 증가, 잦은 우선순위 역전
  • 하나가 끝날 때 까지 진행되기에, 다른 것들은 응답 시간이 길어지게 되고, 갑자기 급한 일이 생기더라도 기존의 작업 때문에 우선순위를 반영할 수 없다.

Preemptive scheduling

• 타의에 의해 자원을 빼앗길 수 있다
  • 할당 시간 종료, 우선 순위가 높은 프로세스의 등장
• 장점
  • 응답성이 높아진다.
  • 시분할 시스템, 실시간 시스템에 적합하다
• 단점
  • Context switch overhead가 크다 = 시스템 부하가 크다

우선순위(priority)

말 그대로 프로세스의 중요도를 의미한다. 프로세스 생성시 우선순위 정책을 어떻게 가져갈지 아래 두 가지 중에 선택하여 적용 가능하다.

Static Priority(정적 우선순위)

• 프로세스 생성시 한 번 우선순위가 정해지면 바뀌지 않는다.
• 장점
  • 구현이 쉽다
  • overhead가 적다
• 단점
  • 시스템 환경 변화에 대응이 어렵다

Dynamic Priority(동적 우선순위)

• 프로세스 상태 변화에 따라 priority 변경이 가능하다
• 장점
  • 시스템 환경 변화에 유연하게 대응 가능하다
• 단점
  • 구현이 복잡하다
  • 우선순위 재계산에 따른 overhead가 크다.