05. CPU Scheduling (2)

쓰레드란? )

• 여러개의 프로세서가 있는 시스템에서 보다 병렬적으로 잘 수행할 수 있는 구조로 만드는 것.
• 멀티플 프로세서 시스템에서 어떻게 하면 더 효율적으로 동작할 수 있을까? 에 대한 고민
• 하나의 context는 하나의 프로세싱 유닛에서 동작해야함. 만약 내 컴퓨터에 프로세싱 유닛이 100개가 있어도 이 작업의 속도는 똑같음. 이 작업을 스레드 4개로 나눠서 4개의 CPU에서 동작시키면 최대 4배의 성능.
  동기화(4개의 쓰레드가 협업)의 경우 4배보다 적은 성능을 보임

Multiple-Processor Scheduling

• 최근 컴퓨터는 대부분 프로세싱하는 코어가 하나가 아닌 여러개이다. 이전에도 서버 시스템은 멀티 프로세서를 사용했다. 그렇가면 이것을 어떻게 스케줄링 해야할까?
• 멀티 프로세서 등장배경) CPU엔 무조건 그 안에 싱글 프로세싱 유닛(context를 걸었을때 context를 프로세싱 해줄 수 있는 유닛. 쓰레드 형태로 관리하며 쓰레드 하나를 자기가 프로세싱 해줄 수 있는 유닛)이 있었다. 옛날엔 CPU당 하나였는데 듀얼코어 얘기가 나오면서 점점 2개.. 4개... 로 늘어난 것. 예전엔 클락 수가 많으면 CPU 성능이 좋다고 하였다. 그러나 4기가에서 더 이상 높히지 못하자 코어의 개수를 늘린 것이다. 클락수가 많아질 수록 열이 발생하여 엄청난 열을 처리할 수 있는 방법이 없었다.
• Multiple processor은 homogeneous(동일한 종류의 칩들이 여러개 꽂힌것으로 일반적인 경우)한 것과 heterogeneous(ISA가 다른 칩들이 꽂힘)한 것이 있다.
• BigLittle이란? 8개의 코어를 가진 것을 말한다. 4개는 강력한 코어(모든 연산을 처리), 4개는 작은 코어(덧셈, 뺄셈과 같은 간단한 연산을 처리)이다.
• Asymmetric multiprocessing) 대장 프로세스가 따로 있으며 이것은 기본적으로 데이터를 관리하고 다른 CPU를 관제한다. ex) cell processor
• Symmetric multiprocessing(SMP) 시스템데이터에 접근하는 형태로, 모든 코어가 평등한 위치에서 작업을 한다. 일반적인 것이다.
• 멀티 프로세서 구조는 Socket(=CPU), Core, SMT(일반적으로 쓰레드라고 표현함)로 이루어져 있는데 프로세싱 유닛의 개수는 socket개수*Core개수*SMT개수로 결정된다. ex) socket이 1개, core이 8개, SMT가 2개면 프로세싱 유닛은 16개.
• 물리적으로는 1개의 CPU이지만 컴퓨터 입장에서는 n개의 CPU와 같다.

Processor affinity

• 각각의 프로세스들은 자기가 동작하고 있는 프로세서에 붙어있으려고 하는 특성이 있다.(OS가 이 특성을 제공해야함)
  프로세스를 옮기게 되면 다른 구역에 access하면서 손해가 많이 생기기때문이다.
• Soft affinity) 가급적 옮기지 않겠다.
• Hard affinity) 절대 옮기지 않겠다.

NUMA and CPU Scheduling

• 동작하는 프로세스를 옮기는 것을 마일 그레이션이라고 한다. 실제로 CPU에서 다른 CPU로 옮기는 것이 아니고 레디큐를 바꿔주는 것.( ex) context switching할때 원래 1번 레디큐에 넣어줘야하는데 2번이 놀고 있으니 2번으로 넣어줌)
• 1번 CPU에서 2번 CPU로 넘어갔는데 원하는 데이터가 1번 메모리에 있다고 가정. 2번 CPU는 1번 메모리에게 데이터를 복사해줄 것을 요구하여 1번 메모리를 read하고 2번 메모리에 write해줌. 자신의 메모리가 아닌 곳에 접근하려면 시간이 오래 걸리기 때문에 두 메모리는 성능이 떨어짐. 첫번째 프로세스도 손해를 봐서 전체 시스템 성능이 떨어짐.
  => solution) 가급적 옮기지 말기 / 이런 구조가 되지 않도록 레디큐에 할당할때 잘보기 (프로세서의 작업부하를 최대한 균형있게 유지하도록 utilization이 더 낮은 곳에 새 프로세스를 비치함)

Load Balancing

두 프로세서의 utilization 차이가 심한데 affinity 하면 전체 시스템의 퍼포먼스는 떨어지겠지만, 강제로 migration 해야하는 상황을 예방하기 위해 덩치가 작은걸 옮기는 듯 미리 마일그레이션 작업을 한다. -> load balancing 맞추기

 

Multicore Processors

최근 추세는 하나의 피지컬 칩에 여러개의 프로세싱 코어를 다는 것이다. 소비전력이 낮아지는 동시에 빠르다.

multiple thread per core 역시 성장중이다. 하나의 코어에 여러개의 쓰레드를 다는 기술이다. (쓰레드가 여러개라고 해도 코어를 추가하는것보단 성능이 낮음) 프로세싱 유닛으로서 하나의 쓰레드를 처리하려고 하면 기본적으로 context의 정보를 저장할 레지스터가 필요하다. 쓰레드가 여러개라고 해도 코어를 추가하는것보단 성능이 낮다. 

레지스터에 접근하는 시간이 10이라면 메모리에 접근하는 시간은 100이다. 연산을 할 데이터를 메모리에서 가져와야 수행할 수 있는데 그렇지 못해서 회로가 놀고 있는 경우가 생긴다. 죽, context는 돌고 있는데 회로는 노는 것이다. 회로가 놀고 있는 동안 필수적인 레지스터 set을 추가로 장착하여 다른 context를 미리 쓰레드 레지스터 위에 올려놨다가 메모리 스톨(메모리에서 데이터를 가져오는 동안 걸리는 시간으로 어쩔 수 없이 발생함)이 발생했을때 이 쓰레드가 회로를 쓰게해주자! 이때 이 레지스터들이 요청하는 연산을 처리할 수 있는 유닛(ALU와 같은) 이 필요하다. 간단히 말하면, 연산하는 칩들이 옆에 붙어있어야한다는 뜻이다. 코어가 여러개라는건 이런게 4개씩 있다는 것이다. 캐시를 공유할뿐이지 서로 상관없는 별개의 프로세싱 유닛이다. 그런데 SMT는 기본적인 연산유닛은 그냥 둔다. 이때 코어를 두개 두면 돈이 많이 들지 않나? 하는 의문이 생길 수 있다. 정말 필수적인 레지스터 set만 두개를 꽂아두고 회로는 공유하는 것이다.

 

Multithreaded Multicore System

• 아주 작은 시간단위로 하나의 코어 안에서 쓰레드 두개가 스위칭한다. 하지만 필수적인 하드웨어들을 다 꽂아놨으므로 context switching은 발생하지 않는다. 1코어 2쓰레드는 코어는 하나지만 프로세싱 유닛은 두개인 것과 같은 효과를 보인다. 메모리 스톨, 쓰레드 작업의 타이밍이 잘 맞아떨어진다면 성능이 2배로 올라간다. But, 메모리 스톨이 거의 없는 경우는 성능이 저하됨. ex) 1번 프로세스가 작업할동안 2번 프로세스는 메모리 스톨을 한다고 가정. 작업시간과 메모리 스톨 시간이 비슷하면 맞아떨어지지만, 메모리 스톨 시간이 적다면, 진행중인 작업을 도중에 중단시킬 수 없으므로 2번 프로세스는 1번 프로세스의 작업이 끝날때까지 기다려야한다.

Real-Time CPU Scheduling

• SMT 시스템에서 OS는 각 프로세서마다 레디큐를 두고 관리한다.
• ex) 4번 CPU에 D라는 프로세스가 돌고 있음. D라는 프로세스가 동작하기 위한 데이터(동작하며 사용하는 데이터, 생성해낸 데이터)들은 OS가 기본적으로 메모리 슬롯에 저장함. 1번 CPU에는 A프로세스, 2번은 B, 3번은 C, 4번은 D가 돌고 있다고 가정했을때, 프로세스 E가 4번으로 새로 배치된다면?(D, E는 CPU sensitive한 작업) 1,2,3은 여유있고 4번만 바쁘니 D를 다른곳으로 옮기자!
• Soft real-time systems) 데드라인에 최대한 맞춰주는 것. 멀티미디어(동영상) 처리처럼 real time 처리가 조금 어긋나더라도 문제가 생기지 않는다. 보통 우리가 사용하는 방식으로, 예를들면 유튜브를 시청하다가 조금 버퍼링이 걸린다고 해서 큰 문제가 발생하지 않는다.
• Hard real-time systems) 무조건 데드라인에 맞춰줘야하는 것. 일반적인 OS에서는 다루지 않는다. ex)수술 로봇,무기
  real time 처리에서 발생하는 두가지 문제가 있는데 이 두개를 완전히 제거하는 방향으로 설계해야 hard real time을 만들 수 있다.
  1. interrupt latency) 작업 도중에 작업처리를 연장시키는 요인이다. ex) 집에서 구구단을 외우고 있는데 누가 초인종을 눌러서 누구인지 확인
  2. Dispatch latency) 스위칭을 하기 위한 레이턴시이다. hard real time에서는 허용하지 않는다. 하드 리얼타임에서는 하나의 프로세스만 돌린다. 어쩔 수 없이 두개를 돌려야하는 상황이 오면 공유하는 자원을 없앤다.
      ex) A와 B가 공유하는 파일이 있다. B가 파일을 써야하는데 A가 사용하다가 웨이팅 큐로 가버렸다(스케줄 아웃). 파일이 이미 열려있으니 B는 수정을 하지 못한다. 이때 B를 CPU에서 내리고 다시 A를 올려서 A가 파일을 닫을때까지 기다린다. 얼마나 많은 시간이 걸릴지 알 수 없다(데드라인 missing).
  
  task T running--(interrupt)-->determine interrupt type(고정적)---->context switching(고정적 or 가변적)---->ISR(가변적)
  
  하드 리얼타임에서는 얼마가 소요될지 모르므로 인터럽트를 받지 않는다. determine ~ ISR 과정이 고정적이라는 조건하에 인터럽트를 받는 경우도 있다. 가변길이를 만들지 않는게 핵심이다!
• 리얼타임 스케줄링의 예시 Priority-based Scheduling
  리얼타임 특성을 가진 프로세스에게 최우선순위를 부여해준다. 데드라인을 지키는지는 확신할 수 없지만 일단 CPU를 잡을 기회를 주는 것. 무책임하게 선택하는 스케줄링 기법으로 데드라인을 missing하지 않을 확률을 높여주겠다는 것이다. soft real time에서만 허용된다. 사실 리얼타임 스케줄링이라고 할 수 없음...
  ex) 1초에 10프레임을 동작시켜야하는 상황. 1프레임당 0.1초의 여유가 있으며 작업은 0.05초가 걸린다. 작업을 언제 시작하든지 상관없고 주기가 끝나기 전에 해결하면 된다. => 리얼타임 프로세스 동작방식
  

Rate Monotonic Scheduling 이 부분 ppt 예시 잘보기

• 'Rate' 이 한가지만 보고 리얼타임 스케줄링하는 것. 역주기를 보고 스케줄링한다. 주기가 1/10이라면 10.
• 주기가 더 짧은걸 먼저 스케줄링한다. 더 높은 숫자가 우선순위를 가진다고 가정함.
• Rate monotonic만 신경쓰고 데드라인은 신경 안 써서 작업을 끝내지 못하는 문제가 발생할 수 있음.

Earliest Deadline First Scheduling(EDF) 이 부분 ppt 예시 잘보기

• '데드라인'이 얼마나 남았는지 체크하며 스케줄링하자. 각자의 데드라인만 신경쓰면 됨.
• 급한 데드라인일수록 높은 우선순위를 가진다. 

 

Concurrency vs Parallelism (동시성과 병렬성)
n개의 쓰레드가 동시에 움직이는 것처럼 보이게 하는 것으로, RR 스케줄링의 목표중 하나이다.

• 동시성) Single core에 네개의 쓰레드가 동작하는 모습을 보면 1-2-3-4-1-2-3-4-1... 이렇게 아주 빠르게 돌아간다. 따라서 동시에 진행되는 것처럼 보이며 이 과정에서 context switching overhead가 발생하여 시스템 퍼포먼스는 줄어든다. 하지만 동시성을 보장하기 위한 어쩔 수 없는 trade-off다.
• 병렬성) 쓰레드들이 병렬적으로 수행하는 것을 말한다. 동시성은 single core system에서 이루어지지만 병렬성은 multiple-core system이어야한다. 두 코어가 n개의 쓰레드를 절반으로 나누어 담당한다.
  ex) 첫번째 코어는 1-3-1-3-1.... 두번째 코어는 2-4-2-4-2..... (동시성도 나타남)
• 두 특성의 차이) 동시성은 동시 동작하는 척이고 병렬성은 실제로 동시동작 한다.

 

Amdahl's Law (암달의 법칙)

실제 프로세스를 쪼개면 얼마나 성능이 좋아질까? 에 대한 이야기. (싱글 프로세서와 멀티프로세서의 성능 비교)

 

식은   speedup <= 1/{S+(1-S)/N}  이다.

여기서 S는 serial portion(↔parallel. 한번에 하나만 처리할 수 있다는 뜻)을 말하고 N은 코어의 개수이다.

ex) 어플리케이션이 75%는 parallel하고 25%는 serial하다고 했을때 코어의 개수를 하나에서 두개로 늘렸다. 속도는 얼마나 더 좋아지는가? 1/(0.25+0.75/2)=1.6 으로 1.6배 더 좋아진다. -> 프로그램 구조를 최대한 parallel하게 만드는게 좋다!

 

 

Thread: Benefits

Resource Sharing에서 가장 중요한 것은 address space(AS)이다.

AS라는 메모리를 공유하고 있기 때문에 쓰레드는 훨씬 더 빠르게 parallel processing할 수 있다.(쓰레드 스위칭이 context 스위칭보다 훨씬 빠른 이유)

 

 

Algorithm Evaluation

criteria를 결정하고 이를 기반으로 알고리즘을 평가함. 항상 동일한 결과가 나오는 입.출력 set으로 스케줄링 기법을 평가한다.

 

Simulations

• 실제적인 여러가지 요소를 간단히 만들어서 프로그램을 돌림.
• 스케줄링의 핵심적인 부분만 구현해서 스케줄링의 차이점을 분석함.
• 보고자하는 초점에 따라 시뮬레이터 구성이 달라짐

Implementation

리눅스에 실제로 스케줄링을 만드는 것.

앞의 시뮬레이터에서 걷어낸 부수적인 것들이 실제로는 스케줄링에 영향을 줄 수 있음 (실제와의 차이)