Chapter 5. CPU 스케줄링 - 2부

안녕하세요 조엘입니다! 운영체제 5단원에 대해 공부해 보았습니다. 1부에 이어서 2부 포스팅합니다!

Abraham Silberschatz의 Operating System Concepts 10th edition과 학부 수업을 듣고 정리한 내용입니다. 오개념이 있다면 알려주세요~~

 

<다중 처리기 스케줄링>

1부에서 살펴본 스케줄링은 단일 처리기 코어를 가진 시스템을 가정하고 설명했었다. 근데 현실은 핸드폰에서도 멀티코어를 지원한다... 우리는 이제 다중코어의 세상에 살고 있다! 이 친구는 무엇을 다르게 고려해야할까?

 

<다중 처리기 스케줄링 접근방법>

다중 처리기는 두가지 방식으로 구현될 수 있다. AMP와 SMP가 바로 그것이다. 

AMP (Asymmetric Multi-Processing)

 - 마스터 처리기: 모든 스케줄링 결정, I/O 처리, 타 시스템의 활동 취급

 - 다른 처리기들: 사용자 코드 수행

오직 하나의 코어만 시스템 데이터 구조에 접근한다. 마스터 처리기가 병목이 되면 성능 저하로 이어진다. 

 

SMP (Symmetric Multi-Processing)

가장 표준으로 쓰이는 다중 처리기 방식으로, 각 프로세서는 스스로 스케줄링이 가능하다. 준비 큐를 구현하는 방법은 두 가지 방법이 있다. 

 - 공통 준비 큐에 쓰레드 투입: Race Condition을 조심할 것!

 - 각 프로세서 마다 고유 쓰레드 큐에 넣기: Load Balancing을 잘 해줄 것!

 

<Load Balancing>

처리기가 다중인 것을 잘 써먹기 위해서는 Load Balancing을 잘 해주어야 한다! Push&Pull로 구현한다. 

 - Push: 특정 태스크가 주기적으로 각 처리기의 부하를 검사한다. 불균형 상태 시 과부하 걸린 처리기의 태스크를 놀고 있는 처리기에게 넘겨준다. 

 - Pull: 놀고 있는 처리기가 바쁜 처리기를 기다리고 있는 쓰레드를 끌어온다. 

 

여기서 또 고려해야 할 부분은, 쓰레드를 이주 시키게 되면 실행중이던 코어에서 캐시의 혜택을 받지 못한다는 것이다. SMP를 지원하는 대부분의 OS는 쓰레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 같은 프로세서에서 계속 실행시키며 warm cache를 이용하려 한다. 이를 Processor Affinity라고 부른다. 

 - Soft Affinity: 웬만하면 쓰레드를 안 옮기려고 노력하지만, 이주가 가능은 하다. 

 - Hard Affinity: 쓰레드 입장에서 실행될 CPU의 집합을 아예 명시한다. 

 

<실시간 CPU 스케줄링>

이번에는 CPU 스케줄링 작업 중에 주기적인 작업이 이루어지며, 해당 작업의 데드라인을 필수적으로 보장해야 하는 시스템에서 쓰이는 실시간 CPU 스케줄링 알고리즘을 알아보자. 

해당 작업의 데드라인을 무조건 보장해야 할 때 쓰이는 알고리즘으로, 임베디드에서 많이 쓰인다고 한다. 

 

일반적으로 연성/경성 실시간 시스템으로 구분한다. 

 - 연성: 오직 더 중요한 프로세스가 우선권을 가진다라는 것을 보장하는 시스템

 - 경성: 태스크에 해당하는 마감 시간까지 서비스를 받아야하며, 마감 시간이 지나면 전혀 서비스를 받지 않은 것과 동일한 결과를 초래한다. 

 

시간이 더더욱 중요해진 만큼, 이벤트 지연시간을 최소화 해야한다. 여기서 이벤트 지연시간은 2가지를 뜻한다. 

 - 인터럽트 지연시간: CPU에 인터럽트가 발생한 시점부터 해당 인터럽트의 처리 루틴이 시작되는 시간

 - 디스패치 지연시간: 스케줄링 디스패처가 하나의 프로세스 블록 시킨 후, 다른 프로세스 시작할 때까지의 시간

 

<Rate-Monotonic Scheduling>

프로세스의 주기가 짧을 수록 우선 순위가 높다. 즉, CPU를 자주 필요로 하는 프로세스에게 우선권을 준다. 

해당 알고리즘의 특징으로는 프로세스 N개의 기준으로 최대의 CPU utilization이 N(2^(1/N)-1) 이라는 점이다. 

 

<Earliest-Deadline-First Scheduling>

마감 시간에 따라서 우선 순위를 부여한다. 따라서 프로세스가 실행 가능한 상태가 되면, 자신의 마감 시간을 시스템에게 알려야 한다.