- 멀티 프로그래밍 : 프로세스가 대기상태가 되었을 때 CPU를 놀리지 않으려고 여러 개의 프로세스를 메모리에 미리 로딩해 놓고 실행하는 방식이다.
프로세스가 대기상태가 되면, 다른 준비 상태의 프로세스를 즉시 실행하게 된다. - 멀티 프로세서 : 하나의 컴퓨터에 여러 개의 CPU가 있는 컴퓨터, 하나의 운영체제가 여러 개의 CPU를 동시에 관리함. CPU 개수만큼의 프로세스가 동시에 실행 상태에 있을 수 있음
- 멀티 프로세싱 : 하나의 작업을 여러 개의 프로세스로 구현해서 서로 IPC를 통해 협업하는 방식
- 멀티 코어 : CPU안에 여러 개의 core가 있음, SW의 입장에서는 멀티프로세서와 똑같음
- 멀티코어 프로그래밍 == 멀티스레드 프로그래밍
멀티코어 CPU가 대세가 되며 멀티 프로세서-스케줄링이 필요하게 되었다.
- 멀티코어 : 여러 개의 CPU가 하나의 chip에 묶여 있는 것
프로그램 하나는 여러개의 코어에서 실행된다.
코어가 늘어난다 해서 단일 프로그램의 속도가 빨라지는 것은 아니다.
하나 이상의 CPU를 사용하게 되면 몇가지 문제가 발생할 수 있다.
일반적인 프로그램은 단일 CPU만 사용하기 때문에 여러 개의 CPU가 존재한다고 하더라도 더 빨리 실행되는 것이 아니다.
따라서 병렬 프로그램을 수행이 되도록 스레드를 사용해서 새로 작성해야 한다.
이렇게 나뉘어진 다중 스레드 프로그램은 작업을 여러 CPU로 나누기 때문에 CPU가 여러 개라면 더 빠른 속도를 낼 수 있다.
📌Single CPU with cache
싱글 프로세서에는 빠른 속도를 내는 캐시가 하나 존재한다.
캐시에는 메인 메모리에 있는 현재 프로그램에서 자주 사용되는 데이터들이 저장되어 있다.
자주 사용하는 데이터를 캐시에 저장하여 느린 메모리를 빠른 것처럼 보이게 한다.
따라서 느린 속도를 가진 메인 메모리에서 데이터를 가져올 때 오랜 시간이 걸리겠지만 다음에 동일한 데이터를 또 다시 가져온다면 캐시에 저장해둬서 필요할 때마다 데이터를 빠른 속도로 가져와서 빠르게 실행할 수 있다.
그렇다면 캐시에는 어떤 데이터가 저장되어야 할까?
- Temporal(시간) 지역성 : 지금 사용한 데이터는 곧 다시 사용될 가능성이 높다
- Spatial(공간) 지역성 : 어떤 데이터가 사용되었다면 그 근처에 존재하는 데이터들도 사용될 가능성이 높다.
이러한 지역성이라는 특성을 활용하여 캐시에 데이터를 저장할 수 있다.
📌Two CPUs with cache sharing memory
이렇게 하나의 메모리를 공유하는 시스템에서 프로세서가 여러개라면 캐시 또한 여러개가 된 것을 볼 수 있다.
만약 첫번째 CPU에서 실행되는 프로그램이 메모리에서 데이터를 가지고 왔다고 가정해보자.
이때, 가져온 데이터를 수정하여 첫번째 CPU에 쓰려 한다. 그런데 컴퓨터는 메모리에 수정된 값을 바로 저장하지 않는다.
-> 메모리는 속도가 최대한 접근을 조금만 하려고 하는 것이다.
그 뒤 동일한 프로그램을 두번째 CPU에서 실행하여 데이터를 메모리에서 가져온다.
근데 여기서 가져온 데이터는 첫번째 CPU에서 수정되지 않은 데이터를 가져온 것이다.
이를 캐시 일관성(Cache coherence)이라고 한다.
그렇다면 이 캐시 일관성 문제를 어떻게 해결해야 할까?
- 가장 기본적인 해결 방법은 하드웨어로 방지하는 것이다.
각각의 캐시는 버스를 감시하며 누가 메모리를 수정하는지 지켜본다.
어떤 CPU가 자기 캐시의 데이터가 다른 CPU에서 수정된 것을 발견하면, 자기 데이터를 무효화 또는 갱신한다.
📌동기화를 잊지 마시오
CPU에서 공유 데이터에 접근할 때에는 상호 배제(Lock)등을 사용하여 올바른 결과를 얻을 수 있다.
멀티코어에서는 동시에 읽고 업데이트 하는 코드를 주의하여야 하는데 예를 들어 리스트에서 동시에 head를 읽으면 안된다.
따라서 여기에 Lock을 사용하게 되면 다른 코어에서 읽을 수 없게된다.
📌캐시 친화성(Affinity)
다음 문제는 캐시 친화성이다. 특정 CPU에서 프로그램을 수행시 해당 프로그램은 그 CPU의 캐시에 여러 가지 데이터를 저장한다. 따라서 다음 수행 될 때 캐시에 저장된 정보로 더 빠르게 수행한다. 그러나 만약 CPU가 여러개라 다른 CPU에서 수행된다면 또 다시 필요한 데이터를 가져와야 한다. 즉 성능이 나빠지게 된다. 따라서 멀티 프로세서 스케줄링을 통해 가능하면 같은 CPU에서 계속 실행해야 한다.
📌단일 큐 스케쥴링(SQMS)
하나의 큐에 작업들을 넣어 처리하는 방식을 SQMS(Single Queue MultProcessor Scheduling)라고 한다.
각각의 CPU는 모두 공유하는 큐에서 다음 작업을 선택한다
그러나 문제가 있다.
- 단점 1: 확장성 결여
앞서 언급하였던 Lock을 사용하면 캐시 일관성 문제를 해결할 수 있으나 성능을 크게 저하시킨다. - 단점 2: 친화성 결여
위 그림과 같이 CPU가 4개 있다고 하였을 때, CPU0이 타임 슬라이스를 모두 사용하여 Ready 상태로 돌아간다. 그 후 다음 스케줄링 될 때, CPU1에서 수행된다고 하면 캐시 친화성이 결여된 것을 볼 수 있다.
캐시 친화성을 고려하여 별도의 메커니즘으로 캐시 친화도를 다음과 같이 구현한다.
그러나 여기서도 E프로세스는 캐시 친화도가 전혀 적용되고 있지 않다.
따라서 이제 CPU마다 큐를 가진 멀티 큐 스케줄링이 등장한다
📌멀티 큐 스케쥴링(MQMS)
멀티 큐 스케쥴링에서는 작업이 들어오면 하나의 큐에만 배치된다.
각각의 큐는 독립적으로 스케줄링 되며 각자의 스케줄링 규칙을 따른다.
따라서 큐의 공유로 인한 동기화 문제를 피할 수 있다.
다음과 같이 CPU가 2개 존재할 때, 각각의 CPU는 자신이 맡은 작업만 처리하기 때문에 캐시 친화성과 확장성을 만족한다.
그러나 이러한 MQMS도 문제는 있다.
다음과 같이 C가 종료되면 A가 혼자서 프로세스를 독점하게 된다.
결국 A가 종료되면 CPU0은 놀고 CPU1만 일하는 부하 불균형 문제가 일어나게 된다.
이러한 부하 불균형 문제의 해결 방법은 매우 간단하다.
- 이주 (Migration) : CPU1에 위치한 B나 D중 하나를 CPU 0으로 이주 시키는 것이다.
그렇다면 또 다른 경우는 어떨까
위와 같은 경우에는 B, D중 하나를 옮기더라도 해결되진 않는다.
결국 B와 A를 번갈아 가며 계속 이동시키면 해결이 된다.
이렇게 되면 부하 불균형문제가 해결되며 이렇게 프로세스를 이동 시킬 때, 이동 시키는 방법에는 작업 훔치기(Work Stealing)이 있다.
📌작업 훔치기(Work Stealing)
앞서 설명했듯이 큐 사이 작업을 이동시키기 위해서는 작업 훔치기를 구현해야한다.
- 작업이 적은 큐를 선택한다.
- 선택된 큐는 가끔씩 다른큐를 살펴본다.
- 살펴본 큐가 선택 큐보다 작업이 많으면 몇 개의 작업을 훔쳐 온다.
그러나! 이러한 방법에도 또 단점이 있다.
- 단점 : 높은 부하와 확장성의 저하
근본적인 문제로 너무 자주 작업을 훔치게 되면 높은 부하와 확정성이 떨어진다.
📌리눅스 멀티 프로세서 스케줄러
- O(1) 스케줄러
우선순위 기반 스케줄러로 여러 개의 큐를 가진다.
일정 주기로 프로세스의 우선순위를 변경한다.
따라서 대화형 작업에 집중된다. - Completely Fair Scheduler (CFS)
결정론적 비례 배분 스케쥴링
여러 개의 큐를 사용한다. - BF Scheduler (BFS)
한 개의 큐를 사용한다.
비례 배분
