[OSTEP 가상화(virtualization)]Chapter 9 비례 배분

 

비례 배분 스케줄러, 혹은 공정 배분 스케줄러에 대해 알아봅시다.

비례 배분의 개념은 간단합니다. 반환 시간이나 응답 시간을  최적화하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것입니다. 즉 공정성 문제입니다.

 

비례 배분의 예는 추첨 스케줄링입니다. 이 아이디어는 다음 실행될 프로세스를 추첨을 통해 결정합니다. 

 

📝12.1 기본 개념 : 추첨권이 당신의 몫을 나타낸다.

추첨권은 쉽게 말해 CPU를 사용할 수 있는 권리입니다. 

• 추첨권(티켓)
  • 프로세스가 받아야 할 자원의 몫
  • 프로세스가 소유한 티켓의 개수와 전체 티켓에 대한 비율이 자신의 몫을 나타낸다.

추첨 스케줄링의 핵심은 이러한 목적을 무작위성을 이용합니다. 무작위가 뭐가 좋냐? 사실 무작위성의 장점이 있습니다.

1. 특이 상황에 대응이 쉬움
2. 매우 가벼운 알고리즘
3. 매우 빠르게 변경 상대를 지정할 수 있다.

📝12.2 추첨 기법

추첨권을 다루는 다양한 기법이 있습니다.

• 추첨권 화폐(ticket currency)
  • 사용자가 추첨권을 자신의 화폐 가치로 자유롭게 할당할 수 있도록 허용한다.
  • 시스템은 자동적으로 화폐 가치를 변환한다.
• 추첨권 양도(ticket transfer)
  • 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다.
  • 이 기능은 클라이언트-서버 환경에서 특히 유용하다.
• 추첨권 팽창(ticket inflation)
  • 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘리거나 줄일 수 있다.
  • 서로 신뢰하지 않는 프로세스들이 상호 경쟁하는 시나리오에서는 의미가 없다.(욕심 많은 프로세스가 팽창으로 완전 장악이 가능하기 때문입니다.)

 

📝12.3 구현

추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 것입니다. 단순 난수 발생과 프로세스 집합을 표현하는 자료구조, 추첨권의 전체 개수만 있으면 됩니다. 

리스트를 이용해서 프로세스를 관리한다고 가정하면 A,B,C 세 개의 프로세스가 몇 장의 추첨권을 가지는 것으로 만드는 것입니다.

 

그러나 추첨 스케줄링은 무작위성에 의존하기에 평균적으로 불공정할 확률이 매우 높습니다. 

작업이 충분한 기간 동안 실행되면 공정에 가까워질 수 있지만 무작위성에 의존한 결과입니다.

📝12.4 왜 결정론적(Deterministic) 방법을 사용하지 않는가

위와 같이 무작위성을 이용하면 단순하게 스케줄러를 만들 수 있지만 정확한 비율 보장은 불가능합니다. 짧은 기간 실행 중에는 더욱 심각합니다. 이때문에 결정론적 공정 배분 스케줄러인 보폭 스케줄링이 고안되었습니다.

 

보폭 스케줄링 역시 이해가 쉽습니다. 시스템의 각 작업이 보폭을 가지고 보폭은 자신이 가지고 있는 추첨권 수에 반비례하는 값입니다. 이 값을 이용해서 프로세스 실행이 될 때마다 보폭 만큼 값을 증가시켜 얼마나 CPU를 사용했는지 추적 합니다.

이것을 이용해 어느 프로세스를 실행시킬지 결정하는 것입니다. 

 

그렇다고 무조건 보폭 스케줄링이 좋을까요? 사실 보폭 스케줄리은 공정성이 더 좋은 것이고 추첨 스케줄링의 가장 큰 장점은 심플입니다. 보폭 스케줄링은 따로 PASS와 보폭이라는 값을 유지시켜야 합니다. 

 

그렇기에 새 프로세스를 추가할 때 보폭 스케줄링은 여러가지 상태 정보가 필요하지만, 추첨 스케줄링은 추첨권의 개수, 전체 추첨권의 개수만 갱신하면 되기 때문에 새로운 프로세스를 쉽게 추가할 수 있습니다.