[OSTEP] 가상화 CH10-CH13

CH10 멀티프로세서 스케줄링 (고급)

멀티프로세서 스케줄링 Multiprocessor Scheduling 은 병행성 Concurrency 주제를 깊게 공부한 이후에 다루는 게 좋다 

멀티코어를 사용하는 다중 CPU 시대가 왔지만, 전통적 응용 프로그램은 오직 하나의 CPU만 사용하기 때문에 더 많은 CPU를 추가해도 더 빨리 실행되지 않는다 

이 문제를 해결하려면 응용 프로그램은 병렬 Parallel 로 실행되도록 다시 작성해야 하며, 보통 쓰레드를 이용한다 

멀티 쓰레드 응용 프로그램은 작업을 여러 CPU에 할당하며, 따라서 더 많은 수의 CPU가 주어지면 더 빠르게 실행된다 

핵심 질문 - 여러 CPU에 작업을 어떻게 스케줄해야 하는가 
운영체제는 어떻게 작업을 여러 CPU에 스케줄해야 하는가? 어떤 새로운 문제가 등장하는가?
예전 기술을 적용할 것인가 아니면 새로운 아이디어가 필요한가?

10.1 배경 - 멀티프로세서 구조 

단일 CPU 하드웨어와 멀티 CPU 하드웨어는 다수의 프로세서 간에 데이터의 공유,

하드웨어 캐시의 사용 방식에서 근본적인 차이가 발생한다 

단일 CPU 시스템에는 하드웨어 캐시 계층이 존재한다, 캐시는 프로그램을 빠르게 실행하기 위해 존재하고

메인 메모리에서 자주 사용되는 데이터의 복사본을 저장하는 작고 빠른 메모리이다 

 

프로그램이 처음 명령어를 실행할 때, 데이터가 메인 메모리에 존재하므로 데이터를 가져오는 데 긴 시간이 소모된다 

데이터가 다시 사용될 것으로 예상한 프로세서는 읽은 데이터의 복사본을 CPU 캐시에 저장한다 

프로그램이 나중에 다시 같은 데이터를 가지고 오려고 하면, CPU는 우선 해당 데이터가 캐시에 존재하는지 검사하고

캐시에 존재하기 때문에 데이터는 훨씬 빨리 접근되고 프로그램은 빨리 실행된다 

 

캐시는 지역성 Locality 에 기반하고, 지역성에는 시간 지역성 Temporal Locality 과 공간 지역성 Spatial Locality 가 있다 

시간적 지역성 - 데이터가 한 번 접근되면 가까운 미래에 다시 접근되기 쉽다 

공간적 지역성 - 주소 x 의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다 

하드웨어 시스템은 캐시에 어떤 데이터를 저장할지 비교적 정확하게 추측을 할 수 있고, 캐시는 잘 작동한다 

 

그림 13.2 처럼 하나의 시스템에 여러 프로세서가 존재하고 하나의 공유 메인 메모리가 있을 때,

CPU1 에 특정 값이 갱신된 상태에서 CPU2 에 갱신되지 않은 값을 가져오는 경우가 생길 수 있다 

이런 문제를 캐시 일관성 문제 Cache Coherence 라고 부른다 

기본적인 해결책은, 하드웨어가 메모리 주소를 계속 감시하고, 항상 "제대로"된 상황만 발생하도록 시스템을 관리한다 

 

특히 여러 개의 프로세스들이 하나의 메모리에 갱신할 때는 항상 공유되도록 

버스 기반 시스템에서는 버스 스누핑 Bus Snooping 이라는 오래된 기법을 사용한다 [Goo83] 

캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링하고 

캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효화 Invalidate 시키거나 갱신한다 

 

 

10.2 동기화를 잊지 마시오 

CPU들이 동일한 데이터 또는 구조체에 접근할 때 (특히, 갱신) 올바른 연산 결과를 보장하기 위해

락과 같은 상호 배제를 보장하는 동기화 기법이 많이 사용된다

락-프리 Lock Free 데이터 구조 등의 다른 방식은 복잡할 뿐 아니라 특별한 경우에만 사용된다 

 

여러 CPU가 동시에 사용하는 공유 큐가 있다고 가정할 때, 락이 없이는 항목의 추가나 삭제가 제대로 동작하지 않을 것이다

구조체를 원자적으로 갱신하기 위해서는 락이 필요하다 

두 CPU의 쓰레드가 동시에, 연결 리스트에서 원소 하나를 삭제하는 루틴으로 진입한다고 가정할 때 

쓰레드 1이 첫번째 행을 실행하면 head 의 현재 값을 tmp 에 저장하고, 그 후 쓰레드 2가 첫번째 행을 실행하면 

역시 head 의 현재 값을 tmp 에 저장한다, 각 쓰레드는 자신만의 스택을 가지고 있으며 tmp 는 스택에 할당된다 

제대로 된 상황에서는 각 쓰레드는 리스트의 첫번째 원소를 한 번씩 제거해야 하는데, 각 쓰레드는 동일한 헤드 원소를 제거하려고 하여,

4행의 헤드 원소를 두 번 삭제하고 같은 데이터 값을 두 번 반환하는 등의 문제를 야기할 수 있다 

 

해결책은 락 Lock 을 사용하여, 간단한 mutex 를 할당하고 (ex. pthread_mutex_t m;)

루틴의 시작에 lock(&m), 마지막에 unlock(&m) 을 추가하면 문제를 해결할 수 있다 

-> 락을 사용하여 여러 쓰레드가 동시에 같은 데이터에 접근하지 못하게 막는 방식, 코드의 특정 구간(예: 데이터 갱신 루틴)을 락으로 감싸고, 한 쓰레드가 작업을 마치기 전까지 다른 쓰레드가 이 구간에 진입하지 못하도록 제어한다 

하지만 이러한 접근 방식은 성능 측면에서 문제가 있으며, 

CPU의 개수가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느리게 된다 

-> 한 번에 하나의 프로세스/ 쓰레드만 자원에 접근할 수 있기 때문에, 다른 쓰레드들이 그 자원을 사용할 때까지 기다려야 하기 때문

10.3 마지막 문제점 - 캐시 친화성 Cache Affinity 

프로세스는 CPU에서 실행될 때 해당 CPU 캐시와 TLB에 상당한 양의 상태 정보를 올려 놓게 된다

프로세스가 실행될 때 지난 번과 동일한 CPU에서 실행되면, 해당 CPU 캐시에 

일부 정보가 이미 존재하고 있기 때문에 더 빨리 실행될 것이기 때문이다 

가능한 한 프로세스를 동일한 CPU에서 실행하려고 노력하는 방향으로 결정해야 한다 

-> 캐시 친화성을 높이면 캐시 히트율이 증가하여 전체적인 시스템 성능이 향상된다 

10.4 단일 큐 스케줄링 

멀티프로세서 시스템의 스케줄러 개발 방법의 가장 기본적인 방식은 단일 프로세서 스케줄링의 기본 프레임워크를 그대로 사용하는 것이고

이러한 방식을, 단일 큐 멀티프로세서 스케줄링 Single Queue Multiplrocessor Scheulding, SQMS 라고 부른다 

이 방식의 장점은 단순함이며, CPU가 2개라면 실행할 작업을 두 개 선택한다 

 

첫 번째 단점은 확장성 Scalability 결여이다, 스케줄러가 다수의 CPU에서 제대로 동작하게 하기 위해

코드에 일정 형태에 락을 삽입하는데 락은 SQMS 코드가 실행 시킬 다음 작업을 찾을 때 올바른 결과가 나오도록 한다 

하지만 락은 성능을 크게 저하시킬 수 있고, 시스템의 CPU 개수가 증가할수록 더욱 그렇다 [And90] 

단일 락에 대한 경쟁이 증가할수록 시스템은 락에 점점 더 많은 시간을 소모하게 되고 실제 필요한 일에 쓰는 시간은 줄어들게 된다 

-> 어떤 확장성일까? 확장성의 문제라는 건, CPU를 추가했는데 성능이 좋아지는 대신 오히려 락을 기다리는 시간이 늘어나서 전체적인 성능이 떨어질 수 있다 

 

두번째 문제는 캐시 친화성이다, 실행할 5개의 작업과 4개의 프로세스가 있다고 가정할 때 

시간이 흐르면서 각 작업은 주어진 타임 슬라이스 동안 실행되고, 다음 작업이 선택되었다고 하면 

각 CPU는 공유 큐에서 다음 작업을 선택하기 때문에 각 작업은 CPU를 옮겨 다니게 된다

 

이 문제를 해결하기 위해 SQMS 스케줄러는 특정 작업들에 대해서 캐시 친화성을 고려하여 스케줄링하고 

다른 작업들은 오버헤드를 균등하게 하기 위해 여러 군데로 분산시키는 정책을 사용하여 

A부터 D까지의 작업은 각각 자신의 프로세서에서 실행하고 E만 이동하여 대부분의 작업에게 친화성을 보존하고, 

다음에는 다른 작업을 이동시켜서 일종의 친화성에 대한 형평성도 추구할 수 있지만, 구현이 복잡해 질 수 있다. 

 

기존의 단일 CPU 스케줄러가 있다면 하나의 큐밖에 없기 때문에 구현이 간단하다는 장점이 있지만

동기화 오버헤드 때문에 확장성이 좋지 않고 캐시 친화성에 문제가 있다 

SQMS 스케줄러를 이용하기 전과 후의 작업 스케줄

10.5 멀티 큐 스케줄링

멀티 큐 멀티프로세서 스케줄링 Multi-queue Multiprocessor Scehduling, MQMS - 멀티 큐 (CPU마다 큐를 하나씩) 를 둔다

MQMS에서 기본적인 스케줄링 프레임워크는 여러 개의 스케줄링 큐로 구성된다 

작업이 시스템에 들어가면 하나의 스케줄링 큐에 배치되고, 배치될 큐의 결정은 적당한 방법을 따른다,

그 후에는 각각이 독립적으로 스케줄 되기 때문에 단일 큐 방식에서 보았던 정보의 공유 및 동기화 문제를 피할 수 있다 

 

MQMS가 SQMS에 비해 가지는 명확한 이점

1) 확장성이 좋다는 것이다 

2) 락과 캐시 경합 Cache Contention 은 더 이상 문제가 되지 않는다 - CPU 개수가 증가할수록 큐의 개수도 증가하므로

3) 캐시 친화적이다 - 작업이 같은 CPU에서 계속 실행되기 때문에

 

MQMS의 근본적인 문제는 워크로드의 불균형 Load Imbalance 이다 

2개의 CPU에 3개의 작업을 가지고 있고 Q0 - A/ Q1 -> B, D에 배치되어 RR 정책을 실행할 때 A가 B와 D보다 2배의 CPU를 차지한다

그리고 A가 종료하면 스케줄링 큐는 Q0 -   / Q2 -> B, C 가 되어, CPU 0 은 유휴 상태가 된다 

 

 

 

이런 오버헤드 불균형 문제를 해결하기 위해서는 작업을 이동시키면 된다 

이주 Migration 으로, 작업을 한 CPU에서 다른 CPU로 이주시킴으로써 워크로드 균형을 달성한다 

Q0 - A/ Q1 -> B, D에 배치된 상태에서 작업을 지속적으로 이주하여 워크로드의 균형을 맞춘다 

 

 

이주의 필요 여부 결정 접근 방식 중 하나는 작업 훔치기 Work Stealing [FLR88] 라는 기술이다 

작업 훔치기에서는 작업의 개수가 낮은 (소스) 큐가 가끔 다른 (대상) 큐에 훨씬 많은 수의 작업이 있는지를 검사하고

대상 큐가 소스 큐보다 더 가득 차 있다면 워크로드 균형을 맞추기 위해 소스는 대상에서 하나 이상의 작업을 가져온다 

 

큐를 너무 자주 검사하게 되면 높은 오버헤드로 확장성에 문제가 생길 수 있다 

반면 다른 큐를 자주 검사하지 않으면 심각한 워크로드 불균형을 초래할 가능성이 있다 

13.6 Linux 멀티프로세서 스케줄러 

Linux 커뮤니티에서 등장한 멀티프로세서 스케줄러

1) O(1) 스케줄러 

우선순위 기반 스케줄러, 프로세스의 우선순위를 시간에 따라 변경하여 우선순위가 가장 높은 작업을 선택한다 

상호 작용을 가장 우선시한다 

2) Completely Fair Sheduler (CFS)

결정론적 Deteministic, 비례배분 Proportional Share 방식 (전에 논의했던 보폭 스케줄링에 가까움) 

3) BF 스케줄러 (BFS) 

단일 큐 방식, 비례배분 방식 

13.7 요약

	단일 큐 방식 SQMS	멀티 큐 방식 MQMS
장점	구현이 용이하다	확장성이 좋다
	워크로드의 균형을 맞추기 용이하다	캐시 친화성을 잘 처리한다
단점	확장성이 좋지 못 하다	워크로드에 불균형이 있다
	캐시 친화성이 좋지 못 하다	구현이 복잡하다

 

CH11 CPU 가상화에 관한 마무리 대화 

운영체제는 프로그램이 가능한 효율적으로 실행되길 원하면서도 (제한적 직접 실행을 하는 이유임)

잘못되거나 악성 프로세스에게는 너무 빨리는 말고 라고 말하길 원한다 

운영체제는 자신이 컴퓨터를 장악하고 있다는 것을 확인하려고 하는 자원 관리자이다 

CH12 메모리 가상화에 관한 대화 

메모리 가상화는 복잡하고 하드웨어와 운영체제의 상호작용에 관해 더 많은 상세 사항들을 이해해야 하다 

사용자 프로그램이 생성하는 모든 주소는 가상 주소이고,

운영체제는 각 프로세스에게 자신만의 커다란 전용 메모리를 가진다는 환상을 제공한다 

하드웨어의 도움을 받아 이 가장된 가상 주소를 실제 물리 주소로 변환하고 원하는 정보의 위치를 찾을 수 있다 

 

WHY? 1) 사용하기 쉬운 시스템을 제공하기 위해 2) 고립 Isoliation 3) 보호 Protection 

운영체제는 각 프로세스에게 코드와 데이터를 저장할 수 있는 대용량의 연속된 주소 공간 Address Space 을 가지고 있다는 시각을 제공한다 (덧, 프로세스의 잘못된 행동에 대해 운영체제의 올바른 대응은 해당 프로세스를 죽이는 것이다)

CH13 주소 공간의 개념 

13.1 초기 시스템

메모리 관점에서 초기 컴퓨터는 많은 개념을 사용자에게 제공하지 않았다 

운영체제는 메모리에서 (여기에서 물리 주소 0부터) 상주하는 루틴 (실제로는 라이브러리) 의 집합이었다 

물리 메모리에 하나의 실행 중인 프로그램 (프로세스) 이 존재하였고 운영체제 부분을 제외한 나머지 메모리를 사용하였다 

13.2 멀티프로그래밍과 시분할 

멀티프로그래밍 Multi-Programming 시대에서 CPU의 이용률이 증가했고 효율성의 개선이 중요해지면서 

시분할 Time-Sharing 시대가 시작되었다, 여러 사용자가 동시에 컴퓨터를 사용하고 

현재 실행 중인 작업으로부터 즉시 응답을 원하기 때문에 대화식 이용 Interacitivity 의 개념이 중요하게 되었다

 

시분할을 구현하는 한 가지 방법은 하나의 프로세스를 짧은 시간 동안 실행 시키는 것이고

해당 기간 동안 프로세스에게 모든 메모리에 접근할 권한을 주는 것이다, 그런 후에 이 프로세스를 중단하고

중단 시점의 모든 상태를 디스크 종류의 장치에 저장하고 다른 프로세스의 상태를 탑재하여 또 짧은 시간 동안 실행시킨다 

이 방법은, 메모리가 커질수록 느리게 동작한다는 커다란 단점이 있다 

레지스터 상태를 저장하고 복원하는 것은 빠르지만 메모리의 내용 전체를 디스크에 저장하는 것은 엄청나게 느리다 

 

그리고 시분할 시스템이 대중화되면서, 여러 프로그램이 메모리에 동시에 존재하려면 보호 Protection 가 중요한 문제가 된다 

 

13.3 주소 공간 

사용자의 위험한 행위에 대비하여 운영 체제는 사용하기 쉬운 easy to use 메모리 개념의 주소 공간 Address Space 을 만들었다 

주소 공간은 실행 프로그램의 모든 메모리 상태를 가지고 있다 

프로그램의 코드 Code, 명령어는 반드시 메모리에 존재해야 하고 주소 공간에 존재한다 

스택은 함수 호출 체인 상의 현재 위치, 지역 변수, 함수 인자, 반환 값 등을 저장하는 데 사용된다 

힙 Heap 은 동적으로 할당되는 메모리를 위해 사용된다 

C 언어의 malloc(), C++ 나 Java 같은 객체 지향 언어의 new 를 통해 메모리를 동적으로 할당 받는다 

 

프로그램 코드는 주소 공간의 위쪽에 정적으로 위치하고 있고 주소 공간의 첫 1KB를 차지한다 

힙은 코드 바로 뒤 1KB부터 시작해서 아래 방향으로 확장하고, 스택은 16KB에서 시작해서 위쪽 방향으로 확장한다 

나중에 보겠지만 이런 식으로 공간을 나누게 되면 주소 공간에 여러 쓰레드가 공존할 때는 동작하지 않는다 

실제로 프로그램은 임의의 물리 주소에 탑재된다 

-> (실제 구현) 물리적으로는 메모리의 여러 부분에 분산되어 있지만, 프로세스는 연속적인 공간으로 인식 

 

13.4 목표

가상 메모리 시스템 VM 의 주요 목표 

1) 투명성 Transparency 

운영체제는 실행 중인 프로그램이 가상 메모리의 존재를 인지하지 못 하도록 가상 메모리 시스템을 구현해야 한다 

(일반적인 사용에서 투명한 시스템은 인지하기 어려운 시스템이다)

오히려 프로그램은 자신이 전용 물리 메모리를 소유한 것처럼 행동해야 한다 

2) 효율성 Efficiency 

운영체제는 가상화가 시간과 공간 측면에서 효율적이도록 해야 한다 

시간-효율적인 가상화를 구현할 때, 운영체제는 TLB 등의 하드웨어 기능을 포함하여 하드웨어 지원을 받아야 한다 

(TLB - 가상 주소를 물리 주소로 변환할 때 사용하는 하드웨어, 페이지 테이블이 있다, 좀 더 공부 필요)

3) 보호 Protection 

운영체제는 프로세스를 다른 프로세스로부터 보호해야 하고 운영체제 자신도 프로세스로부터 보호해야 한다 

보호 성질을 이용해서 프로세스를 서로 격리 Isolate 시킬 수 있다