CPU 가상화

CPU를 가상화한다는 건 쉽게 말해서 여러 작업들이 동시에 실행되는 것처럼 보이도록 cpu 공유하게 함. 기본적인 아이디어는 돌아가면서 CPU 시간 나눠 쓰면 되는 거다. 여기서 2가지 문제가 발생 성능 저하랑 , 제어 문제 제어권을 상실하게 되면 한 프로세스가 영원히 실행권을 가질 수가 있다. 그래서 제한적 직접 실행(LDE) 이라는 기법이 있다. 말 그대로 cpu상에서 그냥 실행하는 거임 근데 여기서 문제 한 프로그램이 운영체제가 원치 않는 일을 하지 않는다는 보장이 있나, 그리고 운영체제가 어떻게 알고 원래 프로그램 중단하고 다른 프로세스로 바뀌는가. 자 그럼 해결해보자 일단 제한된 연산이라는 것은 커널 모드랑 유저 레벨 모드를 두어서 커널 모드에서 특수한 명령어만 실행하게 함. 여기서 시스템 콜들이 등장하는데 시스템 콜을 통해 프로세스가 특수한 기능들을 할 수 있다. 시스템 콜 실행하면 trap 명령어를 실행해서 커널 모드로 바뀜. 그리고 커널에서 트랩 핸들러 처리하고 다시 return-from-trap 명령어 실행해서 사용자 모드로 돌아옴

자 그럼 이번에는 두 번째 문제 프로세스 간 전환이 어떻게 되냐? 운영체제는 실행 중인 프로세스를 멈출지 계속 실행할지 결정해야 되는데 cpu를 다른 프로세스가 점유하고 있다면 운영체제는 실행되지 않고 있다는 뜻이다 그럼 어떻게 알고 바꿔주나?  여기서 2가지가 있는데 cooperative 한 방법은 프로세스를 믿어서 그냥 기다리는 것이다. 이 방식은 잘못하면 무한루프에 빠질 수가 있음. 다른 방식으로는  운영체제가 전권을 행사하는데 타이머 인터럽트를 실행해서 일정 시간이 되면 바뀌게 하는 것이다. 여기까지가 저수준 기법이고 다음으로 고수준 정책을 알아보자

스케줄링: 개요

자 고수준 정책은 어떤것을 골라야 하는 문제다. 일단 가정을 몇 개 할 텐데 굉장히 비현실 적이다.

내용이 기니까 평가 항목 기준으로 보자. 크게 반환 시간과 응답 시간으로 나뉜다. 반환 시간을 기준으로 잡았을 때 선입선출을 먼저 생각해 보자. 선입 선출인 경우 문제는 긴 프로세스가 들어왔을 때 나머지 짧은 프로세스가 뒤에서 기다려야 된다. 그럼 당연히 평균 반환시간은 높다. 이를 해결하기 위한 정책이 최단 작업 우선이다 이건 가장 짧은 실행시간(SJF)을 먼저 스케줄링한다 그럼 당연히 반환시간이 낮을 것이다. 하지만 이것도 문제가 위의 가정을 바꿔서 도착시간이 다른 프로세스가 있을 때는 A가 먼저 들어왔을 때는 실행시간이 짧지만 늦게 들어온 B, C가 나중에 실행된다.

 그래서 나온 정책이 최단 잔여시간(SRTF) 우선 또는 선점형 최단 작업 우선인데 , 말 그대로 A가 먼저 들어와도 중간에 잔여 시 간 계산해서 B, C가 중간에 스케줄링될 수 있다. 이제 여기서 시분할 컴퓨터와 함께 응답 시간이라는 평가 기준이 나오는데 위의 정책들은 대화형 프로세스에서 응답이 너무 길어질 수밖에 없다 그래서 나온 게 라운드 로빈으로 주어진 타임 슬라이스만큼 프로그램을 돌려가며 실행한다 타임 슬라이스는 인터럽트의 배수로 설정할 수 있다. 마지막으로 입출력 연산을 고려한 가정까지 봐보자 만약 짧은 시간을 갖는  대화형 프로세스 A와 긴 시간 실행되는 B가 있을 때 A의 입출력이 끝나기를 기다리는 동안 CPU는 다른 프로세스에 의해 사용되어 연산 중첩이 가능하다. 하지만 위의 마지막 가정을 보면 현실적으로 보기 힘들다 따라서 가까운 과거를 사용하여 스케줄링하는 MLFQ를 알아보자.

MLFQ

MLFQ가 해결하려고 하는 기본적인 문제는 크게 2가지 첫째는 짧은 작업을 먼저해서 반환시간 최적화 또 대화형 사용자에게 빠른 응답 주어서 응답 시간 최적화. 위에서 봤듯이 둘 다 만족하는 정책은 없었다. 그렇다면 어떻게 그나마 MLFQ는 최적화를 했을까. MLFQ는  여러 개의 큐로 구성되어 우선순위가 배정되는데 하나의 프로세스는 이 중 하나의 큐에 들어가고 그 큐 안에서는 라운드 로빈 방식으로 스케줄링된다. MLFQ의 기본 규칙은 다음과 같다.

자 그럼 MLFQ가 어떻게 우선순위를 바꾸는지 부터 알아보자 그전에 규칙이 3가지가 있다

위의 규칙으로 가능한 경우들이 있는데 우리는 바로 문제점부터 알아보자

첫 번째는 기아상태가 발생할 수 있다. 예를 들어 시스템에 너무 많은 대화형 작업이 존재하면 그들이 cpu를 계속 점유하느라 긴 실행 시간을 가진 프로세스는 계속 기다려야 한다. 또 다른 문제로는 일부 사용자가 임의로 스케줄러의 특성을 이용해 우선순위를 높게 만들어 버릴 수 있다 예를 들면 입출력 요청을 일부러 내려서 타임 슬라이스를 소진하기 전에 양도해 계속 우선순위를 높게 둬버리는 것이다. 

위 문제들을 어떻게 해결할 것인가 먼저 전자의 문제는 일정 시간 S가 지나면 시스템 내의 모든 작업을 최상위 큐로 이동하는 것이다. 이 S는 부두 상수라고도 불리는데 결정하기 쉽지 않다

다음으로 후자의 문제는 사실 처음에 만든 법칙 4a와 4b 때문이다. 따라서 두 법칙을 그냥 합쳐서 새로 만든다.

무슨 말이냐면 그 순간에 시간 할당량을 초과하지 않았아도 지속적으로 사용량을 저장해둬서 만약 시간 할당량을 넘으면 언제가 되었든 그냥 아래 단계로 내리는 것이다.

사실 MLFQ에서는 정해야할 변수들이 많다 큐의 개수나 타임슬라이스 크기 등이 있다 보통 타임슬라이스는 우선순위와 반대로 높을수록 짧게 주어진다. 또한 CPU 사용을 시간이 지남에 따라 감쇠해서 우선순위 상향을 제공하기도 한다. 또한 일부 시스템은 nice라는 변수를 둬서 사용자가 임의로 우선순위를 정할 수 있다

이제 다른 방식도 알아보자

스케줄링: 비례 배분

개념은 간단하다 반환 시간 또는 응답 시간을 최적화하는데 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다.  여기에는 몇 가지 방식이 있는데 추첨 스케줄링과 보폭 스케줄링이 있다. 추첨 스케줄링은 비결정론적인 방법이고 보폭은 결정론적 방식이다. 그럼 추첨부터 알아보자. 추첨 스케줄링에서는 추첨권이라는 개념이 있는데 추첨권은 프로세스가 받아야 할 자원의 몫을 나타낸다.  프로세스가 소유한 티켓의 개수와 전체 티켓에 대한 비율이 자신의 몫을 나타낸다. 추첨 방식은 간단 한데 예를 들어 추첨권이 A, B에게 각각 70장, 30장 총 100장이 있다면 당연히 A가 뽑힐 확률이 높을 것이다. 확률이라 정확히 70과 30의 비율로 걸리지는 않지만 시간이 길어지면 보장하게 된다.

추첨 기법이 또 있는데 그중 하나가 추첨권 화폐이다 이건 부여받은 추첨 권에서 사용자가 임의로 자신만의 화폐가치로 각 작업에 주는 것이다. 이것을 각 프로세스 별로 환산되어서 전체랑 비교하게 된다. 다른 기법은 추첨권 양도가 있는데  , 예를 하나 들자면 웹서버에서 클라이언트가 서버에게 빠르게 해달라고 추첨권을 전달할 수 있다. 또 다른 방식은 추첨권 팽창이라고 일시적으로 추첨권의 수를 늘리거나 줄일 수 있다.

다음으로 구현을 한번 보자 예를 들어 400개의 추첨권 중에서 300이 선택되었고 작업 별로 돌면서 count개수를 늘려가며 300을 초과할 때를 찾는데 그럼 그게 당첨이 되는 것이다 물론 리스트가 내림차순이면 더 효율적일 것이다. 여기서 무작위성 때문에 생기는 문제를 정량화하기 위해 불공정 지표라는 개념이 있는데 첫 번째 작업이 종료된 시간을 두 번째 시간으로 나누면 된다 이게 1에 가까울수록 완벽하다 볼 수 있다. 추첨권 배분은 어떻게 하냐가 있는데 이건 사실 아직 정해지지 않았다 사용자가 임의로 배분한다고 한다.

그렇다면 이런 무작위성이 싫으면 결정론적으로 만들어 보는 방법이 있는데 그게 위에서 말한 보폭 스케줄링이다. 이건 각자 작업이 보폭을 갖는데 추첨권에 반비례하게 갖는다 보폭이 작을수록 작업이 끝나고 pass라는 값을 적게 증가시키니 다시 실행될 것이다.

정리해 보자 두 개념다 흥미롭지만 여러 이유로 CPU스케줄러에서 널리 사용되고 있지 않다. 한 가지 이유는 입출력과 맞물렸을 때, 제대로 동작하지 않는다는 것이고 또 다른 이유는 할당 문제 때문에 그렇다. 보통 이런 비례 배분 스케줄러는 할당량을 정확하게 결정할 수 있는 환경에서 유용하게 쓰인다. 가상화 데이터 센터 같은 곳이다. 

자 여기가 기본적인 스케줄링들에 대한 이야기 였고 그럼 멀티 프로세서 시스템일 때는 어떻게 되는가 를 알아보자

먼저 단일 cpu 와 멀티 cpu 하드웨어의 근본적인 차이에 대한 이해가 필요하다. 다수의 프로세서간에 데이터의 공유, 그리고 하드웨어 캐시의 사용 방식에서 근본적인 차이가 발생한다. 단일 cpu시스템에서는 하드웨어 캐시층이 존재하는데 계속 메모리에 왔다 갔다 하면서 데이터 가져오면 느리니까 캐시에 저장해놓고 쓰는 거다.

여기서 문제가 발생하는데 캐시는 지역성에 기반을 하는데 공간 지역성 시간 지역성으로 나뉜다. 간단히 예를 들면 시간 지역성은 같은 것을 다음에 또 접근할 거라는 거고 공간 지역성은 이미 접근한 것 주변을 접근할 것이라는 거다. 반복문이랑 배열을 생각하면 쉬울 거다.

아무튼 그래서 하나의 시스템에 여러 프로세서가 존재하고 공유 메모리를 쓰면 cpu1이 주소 A를 읽고 변경한 뒤 A를 변경한 뒤 캐시에 저장하고 나중에 메모리에 기록하는데 이때 cpu2가 또 메모리에서 읽어오면 그냥 예전 것을 읽어오게 된다. 이 문제를 캐시 일관성 문제라고 한다. 기본적인 해결책은 하드웨어에서 제공하는데 지속적으로 항상 공유되도록 하는 것이다. 캐시는 자신과 메모리를 연결하는 버스의 통신 상황을 계속 모니터링한다(버스 스누핑이라고 함). 캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효화하거나, 갱신한다. 나중에 쓰기 , 즉 write-back 방식은 메모리에 쓰기 연산이 지연되기 때문에 일관성 문제를 복잡하게 만든다. 그리고 이렇게 캐시에서 일관성을 담당한다 해도 운영체제는 공유 데이터에 대해 관리를 해줘야 한다. 락을 통해 동기화를 하는데 구조체를 원자적으로 갱신하기 위해서는 필수다. 그럼 이제 마지막 문제를 이야기해보면 캐시 친화성이라는 문제이다. 위에서도 비슷한 이야기를 했듯이 cpu에서 작업이 실행될 때 프로세스는 캐시와 TLB에 상당한 양의 상태 정보를 올리기 때문에 당연히 다음번에도 같은 cpu에서 실행하는 것이 유리하다. 만약 그렇지 않으면 실행될 때마다 계속 탑재해야 할 것이다.  그럼 이제 스케줄링 방식을 알아보자. 먼저 단일 큐 스케줄링은 우리가 딘일 프로세서 스케줄링의 기본 프레임워크를 그대로 사용하는 방식이다. 하지만 역시 문제가 생기는데 확장성도 안 좋고, 캐시 친화성도 안 좋다. 왜냐? 확장성의 문제는  다수의 CPU에서 제대로 동작하기 위해 락을 삽입하는데  락은 성능을 저하시킬 수 있다 또한 cpu 개수가 증가할수록 더욱 그렇다. 단일 락에 대한 경쟁이 증가할수록 시스템은 락에 점점 더 많은 시간을 소모하게 된다.

캐시 친화문제는 cpu들이 공유 큐에서 작업을 선택하기 때문에 cpu들을 옮겨 다니게 된다.

캐시친화적이지 않다

그래서 작업들의 오버헤드를 균등하게 하기 위해 여러 군대로 분산시키는 정책을 사용한다. 각 cpu에 한 작업만을 처리하게 하고 다른 하나의 작업을 돌려가면서 실행한다. 

 

다음으로 멀티 큐 스케줄링이다. cpu마다 큐를 하나씩 둔다. 직관적으로 이해되겠지만 하나씩 큐를 둠으로써 캐시 친화성도 올라가고 확장성도 좋다. cpu개수가 증가할수록 큐의 개수가 증가하니까 락과 캐시 경합은 더 이상 문제 되지 않는다. 다만 근본적인 문제는 워크 로그의 불균형이다. 한 큐에 여러 작업이 몰릴 수도 , 또 다른 큐는 작업이 너무 적게 스케줄링될 수 있다.  이를 해결하는 방법으로 이주와 작업 훔치기다. 이주는 지속적으로 작업량이 적은 다른 큐로 이동시키면서 진행해 나가는 것이다.  작업 훔치기는 작업의 개수가 낮은 큐가 많은 작업을 가진 큐를 검사하여 가져온다.  물론 검사를 자주 하는 것도 오버헤드로 확장성에 문제가 생길 수 있다. 근데  또 검사를 너무 안하면 워크로드 불균형을 가져온다. 이렇게 중간 지점 찾기는 쉽지 않다.