[운영체제 #07] CPU Scheduling

Bound Job

 

CPU Scheduling : ready 상태에 있는 프로세스 혹은 스레드 중 어느 것을 할당할 것인지 결정하는 문제

• CPU 스케쥴러가 스케쥴링을 수행한다.
• I/O bound job : 짧은 실행시간, 많은 실행 수 → 주로 사람과 상호작용하는 task가 많다.
• CPU bound job : 긴 실행시간, 적은 실행 수
• Dispatcher : 스케쥴러가 선택한 프로세스로 전환해주는 역할
  • Context Switch를 한 뒤 CPU를 커널모드에서 유저모드로 바꾼다. 여기서 PCB를 꼭 사용한다.

Process State Diagram

 

running 상태인 프로세스가 CPU 할당 해제가 되었을 때 (1,2,4의 경우) 새로운 프로세스를 할당하는데,

1,4번의 경우에만 스케쥴링을 하는 방식을 nonpreemptive(비선점방식), 아니면 preemptive(선점방식)라고 한다.

• 비선점 방식 : 실행 중인 프로세스가 자발적으로 CPU를 내보내거나 실행이 완료될 때까지 어떤 프로세스도 CPU를 점유할 수 없는 방식
• 선점 방식 : 프로세스가 실행 중일때도 더 높은 우선순위의 프로세스가 도착하면 현재 프로세스를 중단하고 새로운 프로세스에게 CPU 할당이 가능한 방식

이때 어느 스케쥴링이 가장 최선의 방법인지 정하는 기준은 크게 5가지를 볼 수 있다.

여기서 대기시간을 줄이는 것이 가장 핵심이다. running과 waiting 시간을 줄이기는 힘들기 때문이다.

• CPU Utilization : CPU를 얼마나 활용하는지에 대한 비율
• 처리량 : 단위 시간당 처리된 프로세스 수
• 반환시간 : 프로세스가 new 상태부터 terminated 상태까지 가는 총 시간
• 대기시간 : 프로세스가 ready 상태에서 CPU를 할당받기까지 기다린 시간
• 응답시간 : 첫번째 response가 오기 전까지의 시간, 즉 처음으로 CPU를 할당받을때까지의 시간

---

Nonpreemptive Scheduling

FCFS Concept

 

FCFS(First-Come, First-Served) : CPU를 먼저 요청한 프로세스가 먼저 CPU를 배정받는 스케쥴링 방법

• 위의 경우 발생하는 문제 : 대기시간이 긴 프로세스가 앞에 오면 convoy effect가 발생
• 예를 들면, 1차선에서 큰 트럭이 천천히 갈때, 뒤에 있는 승용차들도 천천히 갈수밖에 없다.

SJF Concept

 

SJF(Shortest-Job-First) : 실행할 CPU 주기가 짧은거부터 처리, FCFS 단점을 개선

• 평균 대기시간이 획기적으로 줄인 방법으로 최적의 방법으로 여겨진다.
• 짧은 시간 = 높은 우선순위
• 그러나 다음에 CPU를 실행할때 얼마나 걸릴지 예측한 값을 사용하여 정확하지 않을 수 있다는 문제가 있다.
• 그럼 이 Burst-time 값을 예측하는 방법은 뭐가 있을까?

Static Techniques : 프로세스의 종류에 따라 정해진 값을 사용

Dynamic Techniques : 과거의 데이터를 이용하여 미래의 값을 예측

• simple averaging : 시점들의 가중치가 모두 같게 설정
• exponential averaging : 과거보다 최근 시점의 가중치가 더 높게 설정

alpha 값이 0에 가까울수록 더 멀리 있는 시점까지 고려하고, 1에 가까울수록 가까운 시점만 고려한다.

Exponential averaging 계산법

 

Priority Scheduling : 각 프로세스들에게 우선순위 정수를 부과

• 그러나 우선순위가 낮으면 실행되지 않는 경우도 존재한다. (Starvation)
• 그래서 시간이 지남에 따라 우선순위를 높여주는 기법(Aging)을 사용하기도 한다.

---

Preemptive Scheduling

SRT Concept

 

SRT(Shortest-Remaining-Time-first) : SJF에 선점 방식을 도입하여 우선순위가 높은 프로세스가 들어오면 바로 할당한다.

RR Concept (Time Quantum = 4)

 

RR(Round Robin) : 프로세스들은 time quantum q만큼만 running하고 지나면 ready queue 맨 뒤로 가는 방식

• 맨 첫 프로세스의 응답시간은 0, 가장 마지막 프로세스의 응답시간은 (n-1)q인데,
  마지막 프로세스 응답시간도 그리 길지 않다는 장점이 있다.
• 대기시간은 프로세스 실행시간에 비례한다.
• 그래서 RR은 논리적이고 합당한 방법으로 여겨진다.
• 여기서는 time quantum을 몇으로 설정하는지가 중요한 문제이다
  • time quantum q가 커지면 문맥 교환 할 일이 거의 없어져 FCFS와 다를게 없어진다.
  • time quantum q가 작아지면 문맥 교환 횟수가 증가한다.

이 RR을 같이 사용한 Priority Scheduling 방식도 존재한다. 크게는 우선순위 순으로 작동하되 같은 우선순위 프로세스들 사이에서는 RR을 사용하는 방법이다.

RR and PS Hybrid Method

---

Multilevel Queue Scheduling

Multilevel Queue Scheduling Concept

 

프로세스 타입에 따라 몇 가지의 큐로 나누어서 분류하고, 각 큐마다 우선순위를 갖는다. 그럼 우선순위가 높은 큐부터 처리한다. 보통 foreground(interactive)가 RR을 사용하고 CPU를 80%정도 점유하지만, background(batch)는 FCFS를 사용하고 CPU를 20%정도만 점유한다.

Example of Multilevel Feedback Queue Scheduling

 

또한 위 그림처럼 피드백 과정을 넣어줄 수도 있다. 우선 모든 프로세스들을 1순위 큐로 들여보냈다가 running 시간에 따라 다음 큐로 이동시키고 프로세스를 분류해서 큐를 결정하는 방식이다.

위 예시에서는, A부터 C까지를 모두 우선순위가 가장 높은 Q0에 집어 넣었다가, 실행시간이 8미만의 프로세스인 A는 8만큼 실행하고 waiting상태로 바뀐다. 대게 이 프로세스들은 I/O bound 프로세스로, I/O가 끝나면 다시 Q0의 맨 끝으로 가서 ready상태가 된다.

B와 C는 8만큼 실행하고 timeout으로 ready상태가 되었지만 강등되어 Q1로 이동한 것이다. 이때 B들은 Q1에서 나머지를 모두 실행할 수 있어서 계속 Q1에 상주하게 되고, C는 또다시 강등되서 Q2에서 동일한 방식으로 작동한다. 이때 C들을 대게 CPU bound 프로세스라 한다.

---

Thread Scheduling

Thread Scheduling user level vs. kernel level

1) User-level thread scheduling

• 스레드 관리와 스케쥴링이 user space에서 이루어짐
• user level의 스레드 라이브러리에서 스케쥴링
• PCS(process-contention scope) 환경이기에 같은 프로세스 내의 스레드들끼리만 리소스를 경쟁하여 스케쥴링 속도가 빠르고 오버헤드가 낮음
• 그러나 병렬 처리에 한계가 있고 블로킹 문제가 존재

2) Kernel-level thread scheduling

• 스레드 관리와 스케쥴링이 커널에서 이루어짐
• SCS(system-contention scope)환경이기에 시스템 전체 스레드들끼리 리소스를 경쟁하여 복잡하고 오버 헤드가 높다.
• 대신 스레드 병렬 실행이 가능하고 블로킹 문제가 없음