ready 큐에 들어있는 PCB - 221p
CPU가 유휴 상태가 될 때 마다, 운영체제는 준비 큐에 있는 프로세스에서 하나를 선택해 실행해야 한다. 준비 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스제어블록(PCB)이다.
선점 스케줄링, 비선점 스케줄링 221~222p
CPU 스케줄링은 다음의 네 가지 상황에서 발생할 수 있다.
- running → waiting 로 전환될 때 (ex. I/O 요청, wait() 호출)
- running → terminate 로 전환 될 때 ( 프로세스 종료)
- running → ready 로 전환될 때 (ex. 인터럽트 발생)
- waiting → ready 로 전환될 때 (ex. I/O의 종료 시)
이 때, 스케줄링이 1,2번의 경우에서만 이루어지는 스케줄링 방법을 비선점 스케줄링이라고 한다.
스케줄링이 1번, 2번과 같이 실행중이던 프로세스가 waiting이나 terminate로 전환될 경우 스케줄링 면에서는 선택의 여지가 없다. 지금 실행중인 프로세스가 없으므로 빨리 CPU의 계속적인 실행을 위해 새로운 프로세스(준비 큐에 하나라도 존재할 경우)가 반드시 선택되어야 한다. 일단 CPU가 한 프로세스에 할당되면 프로세스가 자신을 종료하든지,또는 자신을 대기 상태로 전환하여 CPU를 자신이 직접 방출할 때까지 CPU를 점유하는 방식이다.
그리고, 스케줄링이 3번,4번에 경우에도 이루어지는 스케줄링 방법을 선점 스케줄링이라고 한다.
(Windows,macOS,Linux 및 UNIX를 포함한 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.)
불행하게도, 선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁조건(race condition)을 초래할 수 있다.
디스패처 - 223p
CPU 스케줄링 기능에 포함된 또 하나의 요소는 디스패처(dispatcher)이다. 디스패처는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈이며, 다음과 같은 작업을 포함한다.
- 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
- 사용자 모드로 전환하는 일
- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일.
디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 한 최고로 빨리 수행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간을 디스패치 지연이라고 한다.
스케줄링 알고리즘 종류 - 226~238p
선입 선처리 스케줄링(FCFS)
가장 간단한 CPU 스케줄링 알고리즘이다. 먼저 CPU를 요청한 프로세스가 먼저 CPU를 할당받는다.
비선점 스케줄링 방식에 해당한다.
선입선출에서 프로세스들의 평균 대기 시간은 일반적으로 최소가 아니다.
예를 들어, CPU-bound 프로세스 한 개와 I/O-bound 프로세스 여러 개가 있다고 해보자.
CPU-bound 프로세스가 실행 되고 있는 동안 IO-bound 프로세스들이 I/O를 다 끝내고 준비 큐에 들어가 있는 상황이다. (I/O-bound 프로세스들이 준비 큐에서 기다리고 있는 동안, I/O 장치들은 쉬고 있다. )
CPU-bound 프로세스가 자신의 CPU 버스트를 끝내고, I/O -bound 프로세스들이 선택되어 실행될 때, I/O -bound 프로세스들은 매우 짧은 CPU 버스트를 갖고 있기 때문에 CPU 작업을 신속하게 끝내고 다시 I/O 큐로 이동한다. 이 과정 동안 CPU가 쉬고 있는 시간이 많아진다. 이 후 다시 CPU-bound 프로세스가 CPU를 할당받고, I/O -bound 프로세스들은 다시 준비큐에서 기다리게 된다.
위 상황처럼, 모든 다른 프로세스들(ex. I/O -bound 프로세스들)이 하나의 긴 프로세스(ex. CPU-bound 프로세스)가 CPU를 양도하기를 기다리는 것을 호위효과(convoy effect)라고 한다. 이 효과는 짧은 프로세스들이 먼저 처리되도록 허용될 때 보다 CPU와 장치 이용률이 저하되는 결과를 낳는다.
최단 작업 우선 스케줄링 (SJF)
준비 큐에 있는 프로세스들 중에서 가장 작은 다음 CPU 버스트 길이를 가진 프로세스를 CPU에 할당한다. 만약 가장 작은 다음 CPU 버스트의 길이를 가진 프로세스가 여러 개라면 이 경우는 선입선처리 스케줄링을 적용한다.
SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균대기시간을 가진다는 점에서 최적임을 증명할 수 있다.
그러나, SJF 알고리즘이 최적이긴 하지만, 다음 CPU 버스트의 길이를 사실 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수가 없다. 한 가지 접근 방식은 다음 CPU 버스트의 길이를 예측한 후, 예측값을 사용하는 것이다.(다음 CPU 버스트가 이전의 버스트와 길이가 비슷하다고 예측한다.)
SJF 알고리즘은 선점형이거나 비선점형일 수 있다.
앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하면 선택이 발생한다. 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수도 있다. 선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스를 선점할 것이고,반면에 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 지켜낸다.
선점형 SJF 알고리즘은 최소 잔여시간 우선 스케줄링이라고도 불린다.
라운드 로빈 스케줄링(RR)
라운드 로빈 스케줄링 알고리즘은 선입 선처리 스케줄링과 유사하지만 선점이 추가되었다.
시간 할당량 또는 타임슬라이스라고 하는 작은 단위의 시간을 정의하고(일반적으로 10~100ms),
CPU 스케줄러가 준비 큐를 돌면서 한 프로세스에 한 번의 시간 할당량 동안만 CPU를 할당한다. 이때 준비 큐는 원형 큐로 동작한다. 할당을 뺏긴 프로세스는 준비 큐에 꼬리에 다시 넣어진다.
CPU 스케줄러는 준비 큐에서 첫 번째 프로세스를 선택해 한번의 시간 할당량 이후에는 인터럽트를 걸도록 타이머를 설정한 후, 프로세스를 디스패치한다.
RR 알고리즘의 성능은 시간 할당량의 크기에 매우 큰 영향을 받는다. 극단적인 경우, 시간 할당량이 매우 크면 RR 알고리즘은 FCFS와 같게 된다.
우선순위 스케줄링
각 프로세스마다 우선순위가 있을 때, CPU 스케줄러가 가장 높은 우선순위를 가진 프로세스부터 CPU를 할당하는 알고리즘이다.(SJF 는 다음 CPU 버스트를 우선순위로 이용하는 우선 순위 스케줄링의 한 예이다.)
우선 순위 스케줄링은 선점형이거나 비선점형이 될 수 있다. 프로세스가 준비 큐에 도착하면, 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선 순위와 비교한다. 선점형 우선 순위 스케줄링 알고리즘은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높다면 CPU를 선점한다. 비선점형 우선순위 알고리즘은 단순히 준비 큐의 머리에 새로운 프로세스를 넣는다.
우선 순위 스케줄링의 주요 문제는 indefinite blocking 또는 starvation이다.
우선 순위 스케줄링 알고리즘은 낮은 우선순위 프로세스들이 CPU를 할당받기를 무한히 기다리고 있는 경우가 발생한다.
이 문제에 대한 한가지 해결방한은 노화(aging)이다. 노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
다단계 큐 스케줄링
프로세스 유형에 따라 프로세스를 여러개의 개별 큐로 분할하기 위해 다단계 큐 스케줄링 알고리즘을 사용할 수도 있다. 이 때, 큐와 큐 사이에는 반드시 스케줄링이 있어야 하며, 개별 큐는 FCFS,RR 등 각기 다른 자체 스케줄링 알고리즘을 가질수도 있다.
다단계 피드백 큐 스케줄링
다단계 피드백 큐 스케줄링 알고리즘에서는 다단계 큐 스케줄링에서 프로세스가 큐들 사이를 이동하는 것을 허용한 스케줄링 알고리즘이다.
예를 들어 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동할 수 있다.
이러한 노화 형태는 starvation을 예방한다.
다단계 피드백 큐 스케줄링 알고리즘은 가장 일반적인 CPU 스케줄링 알고리즘이지만, 모든 매개변수들의 값들을 선정하는 특정 방법들이 필요하기 때문에 가장 복잡한 알고리즘이기도 하다.
스레드 스케줄링 - 프로세스 경쟁범위,시스템 경쟁 범위 - 239p
대부분의 최신 운영체제에서 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다. 사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고 커널은 그들의 존재를 알지 못한다.
CPU상에서 실행되기 위해서 LWP를 통한 간접적인 방식일지라도 사용자 수준 스레드는 궁극적으로 연관된 커널 수준 스레드에 사상되어야 한다.
프로세스 경쟁 범위(Process-contention scope, PCS)
동일한 프로세스에 속한 사용자 수준 스레드들 사이에서 어느 사용자 수준 스레드를 스케줄할 것인지 결정하기 위해서 LWP는 프로세스 경쟁 범위를 사용해서 사용자 수준 스레드를 스케줄링한다.
시스템 경쟁 범위(System-contention scope, SCS)
우리가 스레드 라이브러리가 사용자 수준 스레드를 가용한 LWP 상에서 스케줄 한다고 말하는 경우, 실제로 스레드가 CPU 상에서 실행중이라는 것을 의미하지 않는다. 실제로 CPU상에서 실행되기 위해서는 운영체제가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄링 하는 것을 필요로 한다.
이때, CPU상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템 경쟁 범위를 사용하여 커널 스레드를 스케줄링 한다.
멀티 프로세서 스케줄링 - 242~243p
만일 여러 개의 CPU가 동시에 사용 가능하다면, 여러개의 스레드가 병렬로 실행될 수 있으므로 부하공유가 가능해진다. 그러나 스케줄링 문제는 그에 상응하여 더욱 복잡해진다. 우리가 하나의 코어를 가진 CPU 스케줄링 방식에서 보았던 것처럼 여기에서도 최상의 해결책은 없다.
멀티 프로세서의 의미는 크게 발전했으며, 최신 컴퓨팅 시스템에서 이제 멀티 프로세서는 다음 시스템 아키텍처들에 사용할 수 있다.
- 멀티 코어 CPU
- 멀티 스레드 코어
- NUMA 시스템
- 이기종 다중 처리(HMP)
멀티 프로세서 스케줄링 접근 방법
비대칭 다중 처리 (AMP)
마스터 서버에 해당하는 오직 하나의 프로세서가 모든 스케줄링 결정과 I/O 처리 등을 담당하고 다른 프로세서들은 사용자 코드만을 수행하도록 하는 방법이다. 오직 마스터 프로세서에 해당하는 코어만이 시스템 자료 구조에 접근하기 때문에 자료 공유의 필요성이 배제되어 간단하다. 단점은 마스터 서버가 전체 시스템의 병목이 될 수 있다.
대칭 다중 처리 (SMP)
이 경우, 각 프로세서는 스스로 스케줄링 할 수 있다. 각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.
이 때, 하나의 준비 큐를 모든 프로세서가 공용으로 사용하는 방식으로 구현한다면, race condition이 생길 수 있으므로 락킹 기법이 필요하다.
각 프로세서마다 준비 큐가 있는 방식의 구현도 존재한다.
Windows,Linux 및 macOS 와 Android,iOS 등 거의 모든 최신 운영체제는 SMP를 지원한다.
멀티 코어 프로세서
현대의 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착하여 멀티 코어 프로세서가 된다.
각 코어는 구조적인 상태를 유지하고 있어서 운영체제 입장에서는 개별적인 논리적 CPU 처럼 보이게 된다. 멀티 코어 프로세서를 사용하는 SMP 시스템은 각 CPU가 자신의 물리 칩을 가지는 시스템과 비교했을 때 더 속도가 빠르고 더 적은 전력을 소모한다.
메모리스톨
프로세서가 메모리에 접근할 때 메모리의 데이터가 가용 상태가 되기를 기다리느라 많은 시간을 허비하게 되는 상황을 의미한다.
이 상황은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 주로 발생한다.(캐시 미스로 인해 메모리스톨이 발생할 수도 있다.)
이러한 경우, 프로세서는 메모리의 데이터를 사용할 수 있을 때까지 기다리느라 최대 50%의 시간을 허비할 수 있다.
멀티 스레드 코어
메모리 스톨 문제를 해결하기 위해 최근의 많은 하드웨어 설계는 멀티 스레드 코어를 구현하였다. 이러한 설계에서 하나의 코어에 2개 이상의 하드웨어 스레드가 할당된다. 이렇게 하면 메모리를 기다리느라 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.
운영체제 관점에서 각 하드웨어 스레드는 명령어 포인터 및 레지스터 집합과 같은 구조적 상태를 유지하므로 소프트웨어 스레드를 실행할 수 있는 논리적 CPU로 보인다.
이러한 기술은 칩 멀티 스레딩(Chip multi-threading,CMT)로 알려져 있다.
(Intel 프로세서는 단일 하드웨어 코어에 여러 하드웨어 스레드를 할당하는 것을 설명하기 위하여 하이퍼-스레딩이라는 용어를 사용한다.)
멀티 스레드 멀티 코어 프로세서
멀티 스레드 멀티 코어 프로세서는 위와 같이 두 개의 다른 스케줄링 단계가 필요하다.
1번째 단계에서는 운영체제가 각 하드웨어 스레드(논리적 CPU)에서 실행할 소프트웨어 스레드를 선택할 때 결정해야 하는 스케줄링 결정을 한다.
2번쨰 단계에서는 각 코어가 실행할 하드웨어 스레드를 결정하는 방법을 명시한다.
