[CPU 스케줄링 #2] 비례배분, 추첨 스케줄링, 보폭 스케줄링

 

 

스케줄링 : 비례 배분

• 반환 시간이나 응답 시간을 최적화하는 대신 스케줄러가 각 작에게 CPU 의 일정 비율을 보장하는 것이 목적
• 대표적인 예시가 추첨 스케줄링(lottery scheduling) - Waldspurger and Wdihl
  • 다음 실행될 프로세스를 추첨을 통해 결정한다.
  • 더 자주 수행되어야 하는 프로세스는 당첨 기회를 더 많이 준다.

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

• 추첨권(티켓)이라는 개념 도입
  • 추첨권은 프로세스가 받아야 할 자원의 몫을 나타내는 데 사용된다.
  • 프로세스가 소유한 티켓의 개수와 전체 티켓에 대한 비율이 자신의 몫을 나타낸다.
• 예를 들어,,
  • A와 B 두 프로세스가 있다고 가정하자.
  • A는 75장의 추첨권을, B 는 25장의 추첨권을 가지고 있다.
  • A에게 75%의 CPU를, B에게 남은 25%를 할당하는 것이 목적이다.
  • 추첨 스케줄링은 타임 슬라이스가 끝날 때마다 확률적으로 추첨권(0에서 99의 숫자)을 선택한다.
  • A는 0에서 74까지의 티켓을, B는 75에서 99까지의 추첨권을 가지고 있다.
  • 뽑힌 추첨권 값에 따라 실행할 프로세스가 결정된다. 스케줄러는 당첨된 프로세스를 실행한다.
• 두 작업이 장시간 실행될수록, 원하는 비율을 달성할 가능성이 높아진다.

추첨권 화폐 : ticket currency

• 사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당
• 시스템은 자동적으로 화폐 가치를 변환
• 예를들어,,
  • 사용자 A, B가 각각 100장의 추첨권을 받았다고 가정하자,
  • 사용자 A는 A1과 A2의 두개의 작업을 진행 중 ( 자신이 정한 화폐로 1000장 중 각각 500장의 추첨권을 할당 )
  • 사용자 B는 하나의 작업을 실행 중 (10장 중에 10장을 할당)
  • 시스템은 A1과 A2의 몫을 A의 기준 화폐에서 전역 추첨권 화폐량(50)으로 변환
  • 마찬가지로 B1의 추첨권 또한 전역 추첨권 화폐량(100)으로 변환

추첨권 양도 : ticket transfer

• 양도를 통해 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨질 수 있다.
• 클라이언트/서버 환경에서 특히 유용함
  • 클라이언트 프로세스는 서버에게 메시지를 보내 자신을 대신해 특정 작업을 해달라고 요청한다.
  • 작업이 빨리 완료될 수 있도록 클라이언트는 서버에게 추첨권을 전달
  • 서버가 자신의 요청을 수행하는 동안 서버의 성능을 극대화하려고 함.
  • 요청을 완수하면 추첨권을 다시 클라이언트에게 되돌려 준다.

추첨권 팽창 ( ticket inflation )

• 프로세스는 일시적으로 자신이 소유한 추첨권 수를 늘이거나 줄일 수 이싿.
• 서로 신뢰하지 않는 프로세스 들이 상호 경쟁하는 시나리오에서는 의미 X
  • 욕심 많은 프로세스 하나가 많은 양의 추첨권을 자신에게 할당하고 컴퓨터를 장악할 수 있기 떄문
• 많은 CPU 시간이 필요한 프로세스가 시스템에게 알리고, 다른 프로세스들과 통신하지 않고 혼자 추첨권의 가치를 상향 조정한다.

예제

• 추첨 스케줄링의 무작위성 때문에 한 작업이 다른 작업 보다 먼저 종류 될 수 있다.
• 작업의 길이가 길지 않은 경우 평균 불공정 정도는 심각하다.
• 작업이 충분한 기간 동안 실행 되어야 추첨 스케줄러는 원하는 결과에 가까워 진다.

추첨권 배분 방식

• 추첨권을 작업들에게 몇개씩 배분해야하는가 ?
  • 주어진 작업 집합에 대한“추첨권 할당 문제”는 여전히 미해결 상태다.

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

• 무작위 성을 이용하면 단순하게 만들 수 있지만, 정확한 비율을 보장할 수 없다. (짧은 기간만 실행되는 경우는 더 그렇다.)
• Waldspuger는 결정론적 공적 배분 스케줄러인 **보폭 스케줄링(Stride Scheduling)**을 고안

보폭 스케줄링 ( Stride Scheduling )

• 보폭은 자신이 가지고 있는 추첨권 수에 반비례 하는 값
• 예를들어 ,,
  • A, B, C는 각각 100, 50, 250의 추첨권을 가지고 있으며, 임의의 큰 값을 각자의 추첨권 개수로 나누어 보폭을 계산할 수 있다.
  • 10000을 각자의 추첨권 개수로 나누면 각 작업의 보폭은 100, 200, 40이 된다.
  • 이 보폭을 프로세스가 실행될 때 마다 pass라는 값을 보폭만큼 증가시켜 얼마나 CPU를 사용했는지 추적한다.
  • 스케줄러는 보폭과 pass 값을 사용하여 가장 작은 pass 값을 가진 프로세스를 선택한다.
  • 프로세스를 실행 시킬 때 마다 pass 값을 보폭 만큼 씩 증가 시킨다.

• 그림에서 알 수 있듯이, C는 5번, A는 2번, B는 한 번만 실행된다.
• 이 횟수는 각자 가진 추첨권의 개수 250, 100, 50과 정확히 비례한다. 추첨 스케줄링은 정해진 비율에 따라 확률적으로 CPU 를 배분한다. 보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 CPU를 배분한다.

왜 보폭 스케줄링을 사용하지 않고, 추첨 스케줄링을 사용하는가?

• 보폭 스케줄링에서 중간에 프로세스가 도착한다면, pass값을 얼마가 되어야 하는가?
  • 0으로 지정한다면 CPU를 독점할 것이다.
• 추첨 스케줄링에서는 프로세스 상태 ( CPU 사용 현황, pass 값) 을 유지할 필요 없다.
  • 새로운 프로세스를 쉽게 추가할 수 있다.

결론

• 사실 추첨권 및 보폭 스케줄링 이라는 두가지 구현 방식은 개념적으로 흥미롭 지만 여러 이유로 CPU 스케줄러로서 널리 사용되지 않고 있다.
  • 이러한 접근 방식이 특히 입출력과 맞물렸을 때 제대로 동작하지 않는다는 것.
  • 프로세스에 얼마나 추첨권을 할당해야하는 지가 미해결 상태로 남아있다.

 

출처 : 운영체제: 아주 쉬운 세 가지 이야기