단일 CPU에서 멀티스레드 처리 개념은 병행성이다.
다중 CPU에서 멀티스레드 처리 개념은 병렬성이다.
스레드 모델에는 1:1 모델, n : 1 모델, n : m 모델이 있는데 모델에 따라 스케줄링 방식이 달라진다.
다중 프로세서 스케줄링에는 Asymmetric Multi Processing (AMP)와 Symmetric Multi Processing (SMP) 방식이 존재한다. AMP는 마스터 프로세서, 슬레이브 프로세서가 존재하며 마스터 프로세서가 스케줄링을 진행한다. SMP는 모든 프로세서가 동등하다.
SMP 스케줄링 알고리즘에서 4가지를 알아보겠다.
- 부하공유 스케줄링
- 전용 프로세서 할당 스케줄링
- 갱 스케줄링
- 동적 스케줄링
부하공유 스케줄링은 모든 CPU가 공유하는 1가지 큐가 존재한다. 큐 안의 일거리를 여러 개 CPU에게 분산해서 스케줄링한다. 문제는 CPU당 스케줄링 이벤트가 발생하는데, 현재 실행 중인 스레드가 일시적으로 중단될 수 있다. 스케줄러는 어떤 CPU에서든지 실행될 수 있으며 준비 큐를 사용할 수 있다.
전용 프로세서 할당 스케줄링은 CPU마다 해당하는 큐를 CPU 준비 큐를 가지고 있다. 스레드 생성 후 어떤 준비 큐에 삽입이 가능하며 로드 밸런싱이 가능하다. 물론 큐에 스레드를 넣으면 만약 어떤 큐에 스레드가 몰린다면 다른 CPU는 놀고 몰린 스레드는 매우 바빠진다. 이런 경우에는 로드 밸런싱을 실현하지 못한다.
갱 스케줄링은 한 프로세스에 속한 여러 스레드들을 동시에 스케줄링하는 기법이다.
스레드 간의 문맥 교환 횟수를 줄일 수 있어 효율적이다.
동적 스케줄링은 먼저 CPU 당 준비 큐의 크기가 같도록 관리되어야 한다.
2가지 기능이 존재한다. Push Migration과 Pull Migration 기능이다.
- Push Migration - 커널은 주기적으로 큐 사이즈를 점검하여 크기가 작은 큐로 스레드를 이동시킴.
- Pull Migration - CPU는 큐가 Empty가 되면 다른 큐에 있는 스레드를 가져옴.
동적 스케줄링의 문제점은 스레드가 다른 준비 큐로 마이그레이션 된다면 이전 CPU 내의 캐시에 저장해 놓았던
데이터(pre-fetch)들을 사용할 수 없게 되는 문제! -> 프로세서 연관성 문제
- Soft Affnity 기능 - Migration 일부 허용하는 경우. 리눅스, 윈도우 모두 지원
- Hard Affinity 기능 - Migration 을 강력하게 불허하는 경우. 리눅스, 윈도우 모두 지원
다음은 운영체제에 대한 프로세스 스케줄링 사례이다.
먼저 윈도우다. 윈도우는 마이크로커널이다. 윈도우 커널에는 Dispatcher object와 Control object가 존재한다.
윈도우의 스케줄링 특징은 쓰레드 스케줄링, 선점방식, Multilevel Feedback Queue + Priority 스케줄링이라는 것이다.
윈도우는 32레벨 우선순위 값을 가진다. 0은 메모리 관리용, 1 ~ 15는 Variable Class, 16 ~ 31은 Real-time Class이다.
인터랙티브한 일은 (클릭, 키보드)는 Real-Time class이다. (중간 값은 base priority)
리눅스 스케줄링이다.
리눅스 커널 1.0 버전은 Priority Scheduling 알고리즘이다.
리눅스 커널 2.6 버전은 Multilevel Queue 알고리즘을 사용한다.
리눅스 커널 2.6.23 버전은 Multilevel Feedback Queue + 가변 우선순위 스케줄링을 사용한다.
리눅스 커널 3.14 버전은 기존 스케줄링 알고리즘에서 데드라인 스케줄링을 추가했다.
Priority Scheduling은 단순하고, 명료하지만, 매번 스캐닝 & 스캐닝 시간 소요로 인한 오버헤드가 발생한다.
Multilevel Queue + 가변 Priority는 4개 클래스로 분류한다. DL, RT, Fair, Idle 각 클래스마다 다른 스케줄링 방법을 적용한다. Real Time 는 (1 ~ 99, 이건 우선순위를 바꿀 수 없다.)이며 Time-shared 는 (100 ~ 139,노말 배치, nice value로 우선순위 변화 가능)이다. 우선 순위를 가변화 시키는 방법으로는 nice value가 있다.
가변 우선 순위 알고리즘은 Completely Fair Scheduling라고 적는다. CFS라고도 부른다.
우선순위를 가변화 시키는 것과 Time Quantum을 가변화시키는 개념이 제일 중요하다.
Deadline 스케줄링 알고리즘
리눅스가 절대적인 real time 처리방식이 아니므로, 더 강력한 스케줄링이 필요.
-> Hard realtime(예 : 자동차 자율주행), Soft realtime(예 : 실시간 축구방송) 이런것들을 처리해야한다.
궁극적으로, 프로세스에게 CPU bandwidth 를 나눠주자.
보통 EDF 사용 - 데드라인 상황을 보고 우선순위를 동적으로 바꿔, 마감 내에 완료할 수 있도록 스케줄링하는 기법.
다음은 SMP Linux에서의 로드 밸런싱 기법이다.
부하가 균등한지 점검하는데 주기적으로 점검하거나, CPI idle time(CPU가 놀 때), 새로운 태스크 생성 시에 점검한다.
다음은 부하 균등 과정이다.
- 각 태스크는 Quad Core CPU에서 실행되며, 각 Core 당 부하(Load, L)가 따른다.
- 각 Core 끼리 Group으로 구성한다.
- 그룹 내의 Core 간 부하를 균등하게 점검하여, 균등하면 다음 그룹으로..
- 두 번째 그룹에서 부하를 균등하게 수정(태스크를 이동하여 부하를 균등하게 변경)
- 그룹 간 부하를 균등하게 점검하여, 균등하지 않으면 그룹간 태스크를 이동시켜 부하를 균등하게 처리.
댓글