일반 프로세서 공유

GPS(일반화된 프로세서 공유)는 프로세스 스케줄러 및 네트워크 스케줄러에 이상적인 스케줄링 알고리즘이다.그것은 패킷을 등급으로 분류하고 그 사이의 서비스 용량을 공유하는 공정률 원칙과 관련이 있다.GPS는 일부 고정된 무게에 따라 이 용량을 공유한다.^[1]

공정 스케줄링에서 GPS는 "완벽한 공정성을 달성하는 이상화된 스케줄링 알고리즘"이다.실제 스케줄러는 모두 GPS에 근접해 공정성을 측정하기 위한 참고 자료로 활용한다."^[2]

일반화된 프로세서 공유는 트래픽이 유동적(적소 패킷 크기)이며 임의로 분할될 수 있다고 가정한다.PSGPS(Packet-By-Packet Generalized Processor Sharing)라고도 알려진 ^[3]가중 공정 대기열(WFQ)과 같이 GPS의 성능을 상당히 밀접하게 추적하는 여러 서비스 분야가 있다.

정당성

인터넷과 같은 네트워크에서, 다른 응용 프로그램 유형은 다른 수준의 성능을 요구한다.예를 들어, 이메일은 정말로 저장되고 전진적인 종류의 애플리케이션이지만, 화상 회의는 짧은 지연 시간을 필요로 하기 때문에 그렇지 않다.패킷이 정체된 링크의 한쪽 끝에 대기할 때, 노드는 일반적으로 대기 중인 패킷을 전송할 순서를 결정할 때 어느 정도 자유가 있다.한 가지 예제는 단순히 선착순이며, 대기열의 크기가 작을 경우 잘 작동하지만, 대기 시간에 민감한 패킷이 버스트성이 높고 대역폭이 높은 애플리케이션에서 패킷에 의해 차단되는 경우 문제가 발생할 수 있다.

세부 사항

GPS에서 $N$ $N$ 흐름 $N$ ("classes" 또는 "sessions"라고도 함)을 처리하는 스케줄러는 각 흐름에 대해 $w_{i}$ 하나의 가중치 w $w_{i}$ ${\$ 로 구성된다.그런 다음 GPS는 하나의 $흐름$ i $i$ 및 특정 시간 간격 $(s,t]$ , $(s,t]$ $(s,t]$ ${\displaystyle(s,t)$ 을 $(s,t]$ 고려하여 흐름 $i$ $i$ 이 $i$ (가) 이 간격에 연속적으로 백로그됨(즉, 대기열이 비어 있지 않음 $j$ 을 확인한 후 다른 $흐름$ j ${\d$ .

w_{j}O_{i}(s,t)\geq w_{i}O_{j}(s,t)

여기서 $O_{k}(s,t)$ $s$ $O_{k}(s,t)$ , $O_{k}(s,t)$ ) ${\displaystyle O_{k}(s$ $,t$ $)}$ 은 간격 $(s,t]$ , $(s,t]$ $(s,t]$ ${\displaystyle$ $k$ $}$ 에서 출력된 $k$ 흐름 $k$ ${\displaystyle$ $(s,t]$ k}의 비트 양을 의미한다 $O_{k}(s,t)$ $(s,t]$

그러면 각 흐름 $i$ $i$ 이(가) 최소한 비율을 수신한다는 $i$ 것을 증명할 수 있다.

R_{i}={\frac {w_{i}}{\sum _{j=1}^{N}w_{j}R

여기서 $R$ $R$ 은 $R$ (는) 서버의 비율이다.^[1]

이것은 최소한의 요금이다.어떤 흐름에서 일정 기간 동안 대역폭을 사용하지 않는 경우, 이 남은 용량은 각각의 가중치와 관련하여 활성 흐름으로 공유된다.예를 들어 w $w_{1}=2,w_{2}=w_{3}=1$ = $w_{1}=2,w_{2}=w_{3}=1$ , $w_{1}=2,w_{2}=w_{3}=1$ $w_{1}=2,w_{2}=w_{3}=1$ = $w_{1}=2,w_{2}=w_{3}=1$ $w_{1}=2,w_{2}=w_{3}=1$ = $w_{1}=2,w_{2}=w_{3}=1$ $w_{1}=2,w_{2}=w_{3}=1$ 가 있는 GPS 서버를 생각해 보십시오 $w_{1}=2,w_{2}=w_{3}=1$ 첫 번째 흐름은 용량의 절반 이상을 받는 반면, 다른 두 흐름은 1/ $4만$ 받는다.그럼에도 불구하고 어느 정도의 시간 간격 $(s,t]$ , $(s,t]$ $(s,t]$ ${\displaystyle (s,t$ 에서 두 번째와 세 번째 흐름만 활성 상태인 경우, 각각 용량의 절반씩을 받게 된다.

구현, 매개 변수화 및 공정성

GPS, 그리고 GPS에서 영감을 받은 모든 프로토콜에서, 가중치의 선택은 네트워크 관리자에게 맡겨진다.

일반화된 프로세서 공유는 트래픽이 유동적이라고 가정한다. 즉, 애플리케이션 유형이 패킷을 대기열에 포함할 때마다, 그것은 위의 공식에 의해 주어진 서버의 분율을 정확히 수신할 것이다.그러나 트래픽은 유동적이지 않고 패킷으로 구성되며, 가변 크기일 수 있다.따라서 GPS는 대부분 이론적인 발상이며, 이러한 GPS 이상에 근접한 몇 가지 스케줄링 알고리즘이 개발되었다: 가중 공정 대기열이라고 불리는 PGPS는 GPS의 가장 잘 알려진 구현이지만, 약간의 단점이 있으며, 적자 라운드 로빈 또는 WF2Q로서 여러 가지 다른 구현이 제안되었다.^[4]

GPS는 공정한 이상으로 간주되며, 그것의 모든 근사치는 "공정성을 측정하기 위한 참고 자료로 사용"^[2]된다.그럼에도 불구하고 몇 가지 공정성 조치가 존재한다.

GPS는 유체 모델을 가정하기 때문에 패킷 크기에 민감하지 않다.

참고 항목

참조

^ ^a ^b Parekh, A. K.; Gallager, R. G. (1993). "A generalized processor sharing approach to flow control in integrated services networks: The single-node case" (PDF). IEEE/ACM Transactions on Networking. 1 (3): 344. doi:10.1109/90.234856.
^ ^a ^b Li, T.; Baumberger, D.; Hahn, S. (2009). "Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin" (PDF). ACM SIGPLAN Notices. 44 (4): 65. CiteSeerX 10.1.1.567.2170. doi:10.1145/1594835.1504188.
^ Demers, A.; Keshav, S.; Shenker, S. (1989). "Analysis and simulation of a fair queueing algorithm". ACM SIGCOMM Computer Communication Review. 19 (4): 1. doi:10.1145/75247.75248.
^ Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. Vol. 1. p. 120. doi:10.1109/INFCOM.1996.497885. ISBN 978-0-8186-7293-4.

[parekh-1] Parekh, A. K.; Gallager, R. G. (1993). "A generalized processor sharing approach to flow control in integrated services networks: The single-node case" (PDF). IEEE/ACM Transactions on Networking. 1 (3): 344. doi:10.1109/90.234856.

[doi10.1145/1594835.1504188-2] Li, T.; Baumberger, D.; Hahn, S. (2009). "Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin" (PDF). ACM SIGPLAN Notices. 44 (4): 65. CiteSeerX 10.1.1.567.2170. doi:10.1145/1594835.1504188.

[demers-3] Demers, A.; Keshav, S.; Shenker, S. (1989). "Analysis and simulation of a fair queueing algorithm". ACM SIGCOMM Computer Communication Review. 19 (4): 1. doi:10.1145/75247.75248.

[WF2Q-4] Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. Vol. 1. p. 120. doi:10.1109/INFCOM.1996.497885. ISBN 978-0-8186-7293-4.

[1]

[2]

[3]

[4]

Search

일반 프로세서 공유

네임스페이스

더

목차

정당성

세부 사항

구현, 매개 변수화 및 공정성

참고 항목

참조