CPU 스케줄링 - 싱글코어

CPU 스케줄링

* 최신 시스템에는 CPU 코어가 여러개이지만, 이 글에서는 싱글코어라고 가정한다.

 

프로세스는 수명주기 동안, 준비 큐와 대기 큐를 이동하며 CPU를 점유한다. CPU스케줄러는 준비 큐에 있는 프로세스 중에서 CPU를 할당할 프로세스를 선택하는 것이다. 이 작업은 짧은 시간동안 자주 일어난다. CPU를 점유하는 프로세스를 전환하기 위해서는 Context Switch ( 문맥교환) 이 필요하다.

 

스레드 스케줄링?

최신 OS에서는 실질적으로 스레드를 스케줄링한다. 그래서 프로세스 스케줄링을 스레드 스케줄링이라고도 한다.

 

왜 스케줄링?

어가 하나인 CPU가 하나이기 때문에 CPU는 한번에 하나의 작업만 수행할 수 있다. 멀티 프로그래밍의 목적은 CPU의 유휴시간을 최대한 줄이고, 이용률을 최대화하는 것이다. 그래서 스케줄링은 OS의 핵심 기능 중 하나이다,

 

CPU버스트

프로세스가 CPU를 사용하는 것을 의미한다. 프로세스의 실행은 CPU버스트와 I/O 버스트의 교차로 이루어진다. CPU버스트 시간은 프로세스가 CPU를 사용하는 시간이다.

 

---

디스패쳐 (Dispatcher)

CPU스케줄링 기능 중 하나이며, CPU를 점유하는 프로세스를 전환해주는 모듈이다.

디스패쳐는 모든 Context Switch 시 호출되며, 최대한 빨리 전환해줘야 한다. 전환해 주는 시간을 Dispatch Latency 라고 한다.

 

디스패처의 실행은 다음과 같다.

1. Context Switch

2. User Mode 로 전환

3. 프로그램 재시작 위해 사용자 프로그램의 적절한 위치로 Jump

 

Dispatch Latency 

하나의 프로세스 정지하고, 다른 프로세스 시작할 때 까지 걸리는 시간

 

Diaptch Latency VS Context Switch

Context Switch는 프로세스 상태를 저장하고, 불러오는 하나의 Process이고, Dispatch Latency는 시간이다. Context Switch 의 결과가 Dispatch Latency이다.

 

---

스케줄링 기준 (  Scheduling Criteria  )

• CPU 이용률 : 최대한 높여야 한다.
• 처리량 : 단위시간 내에 처리되는 프로세스 수가 많아야 한다.
• 총 처리시간 : 프로세스 실행에 소요된 시간은 짧아야 한다. ( 대기시간도 포함 )
• 대기 시간 : 준비 큐에서 기다리는 시간은 짧아야 한다. 길면 기아상태 된다.
• 응답 시간 : 최초로 응답하는 시간

상황에 따라, 편차를 줄이거나, 최적화하는 것이 바람직 할 수 있다.

---

비선점형 알고리즘

어떤 프로세스가 CPU 점유하고 있다면, 해당 프로세스가 CPU를 놓아줄 때 까지 CPU를 사용할 수 없다. 즉, 뺏을 수 없다. 단순하지만, 실시간 컴퓨팅에서는 좋지 않다.

 

 

FCFS ( First-Come, First-Served )

가장 간단한 선입 선처리 알고리즘이다. CPU를 가장 먼저 요청한 프로세스 부터 순서대로 처리한다. 준비큐는 FIFO 형태가 된다.

 * Convoy effect ( 호위효과 ) : 실행시간 짧은 프로세스가 실행시간 긴 프로세스 뒤에서 기다리는 효과. CPU 이용률이 저하된다.

 

ex )  아래처럼 프로세스가 있을 때, 준비큐에 P1,P2, P3 순서대로 들어온다면

• 프로세스      Burst 시간
• P1                       20
• P2                        4
• P3                       15

P1

P2

P3

간트차트로 위와 같이 나타낼 수 있다. Convoy Effect가 존재하는 걸 확인할 수 있다.

 

SJF ( Shortest Job First ) ( Shortest-next-cpu-burst Algorithm )

- CPU 버스트 시간, 즉 실행시간이 짧은 프로세스부터 CPU에 할당한다.

- 최적의 알고리즘이지만 CPU 버스트 시간을 알 수 없다. ( 미래 일을 예측하는 것이기 때문이다. )

 

CPU버스트 시간을 구하기 위해 과거의 실행 시간을 토대로 추측한다.

\({t}_n \)  : 프로세스의 n번째 실행시간

\({\tau }_{n+1} \) : 프로세스의 n+1 번째 실행 시간의 예측 값

\({\tau }_{n} \) : 프로세스의 n 번째 실행 시간의 예측 값

α : 0이상 1이하의 매개변수. 1이면 최근의 시간만 중요시, 0이면 최근 측정시간 무시

 

과거값이 점진적으로 줄어든다.

 

Prioriy Scheduling (우선순위 스케줄링)

대기중인 프로세스에 우선순위를 부여한다. 제한 시간,  사용파일 수 등에 따라 우선순위가 매겨진다. CPU버스트 시간을 기준으로 우선순위가 매겨지면 SJF 이다. 우선순위가 동일하면 FCFS로 처리한다.

 

그러나, 문제점이 있다.우선순위 낮은 Process는 CPU사용을 하지 못해 계속해서 기다리기 때문이다. 이 현상을 Starvation ( 기아 ) 현상이라고 한다. 그래서., Aging이라는 기법을 이용한다. 대기시간이 긴 프로세스의 우선순위를 높이는 것이다.

 

---

선점형 알고리즘

대부분의 OS에서 사용하고 있는 방법이다. 급하게 처리해야 할 프로세스를 처리할 수 있다. 그러나, 2개의 프로세스가 하나의 데이터를 공유한다고 하면, 선점에 의해 데이터의 일관성이 깨질 수 있다. 그러므로 Mutex 락과 같은 방법이 필요하다.

 

Round Robin ( RR )

FCFS 에 선점스케줄링과 Time Quantum 개념을 추가.

• Time Quantum ( 시간할당량) 혹은 Time slice라는 작은 시간단위를 정의
• Time Quantum은 하나의 프로세스가 한번에 최대 실행될 수 있는 시간이다. 즉, 할당된 시간이 끝나면 준비큐에 넣어준다.
• Time Quantum 시간 만큼 타이머를 설정해서 Dispatch한다. 타이머를 초과하면 인터럽트가 발생되어 현재 프로세스가 준비 큐에 들어간다.
• 일반적으로 평균 Turnaround time이 SJF보다 길다. 응답시간은 더 좋다.

만약 N개의 프로세스가 있다면 최대 대기시간은 (N-1) X Time Quantum 이 된다. Time Quantum 값은 너무 크면 대기시간이 길기 때문에 안된다.

 너무 작으면 Context Switching 이 자주일어나기 때문에 오버헤드가 커진다.프로세스의 평균 응답시간은 짧아지지만, 전체 작업시간은 길어진다.

 

그래서 일반적으로 Time Quantum은 Context Switch 시간보다 길게 설정한다.

경험적으로 ( Rules Of Thumb ) CPU 버스트의 80%는 Time Quantum보다 짧아야 한다.

SRF ( Shortest Remaining Time First )

선점형 SJF 스케줄링이다.

중간에 준비 큐에 더 짧은 프로세스가 들어온다면, 더 짧은 프로세스가 CPU를 점유한다. 

그러나, 종료시간 예측어렵고, 기아 현상 발생할 수 있다.

 

Prioriy Scheduling (우선순위 스케줄링)

선점형방식으로 구현될 경우, 중간에 우선순위 더 높은 프로세스 들어온다면, 해당 프로세스가 CPU 점유한다.

선점되기 때문에 Indefinite Blocking ( 기아 현상 ) 이 발생할 수 있다.

 

* 기아현상 해결 위해 RR + Priority Scheduling을 사용할 수 있다. 우선순위 스케줄링 내에서, 우선순위가 같다면 RR을 사용한다. 우선순위 다르면 우선순위 스케줄링을 사용.

Multilevel Queue ( 다단계 큐 )

• 우선순위 별도의 큐를 만들어 유지한다.
• 큐마다 서로 다른 스케줄링 알고리즘 사용할 수 있다.
• 우선순위 가장 높은 큐가 전부 다 실행될 때 까지 우선순위 낮은 큐는 실행되지 않는다, 혹은 큐에 따라 Time Slice를 배정해준다, 우선순위 낮은 큐에는 Time Slice를 배정하면 기아현상을 막을 수 있다. 
• 프로세스 종류에 따라 우선순위 나눈다.
• 큐 간의 프로세스 이동이 불가능. 그래서 오버헤드가 장점이 있다.

Multilevel Feedack Queue ( 다단계 피드백 큐 )

• 큐 간의 프로세스 이동이 가능하다.
• 구현하기 위해 여러가지를 정의해야 한다. 큐의 개수, 각 큐의 스케줄링 알고리즘, 우선순위 높아지는 시기, 우선순위 낮아지는 시기, 새로운 프로세스가 어디 큐에 들어갈지 등등. 그래서 복잡하다. 하지만 만능이다.

 

 

참고

https://www.geeksforgeeks.org/difference-between-dispatch-latency-and-context-switch-in-operating-systems/
Operating System Concepts, 10th Edition (Abraham Silberschatz 외 2명 )