시간-유틸리티함수

Time-utility function

시간/유틸리티 기능(TUF), née 시간/값 함수는 동작(예: 작업, 기계적 이동)이 완료 시간에 따라 산출하는 애플리케이션별 효용을 지정한다.[1][2]TUF와 그 효용 해석(항문), 척도 및 값은 응용 분야별 주제 지식에서 도출된다.효용성에 대한 해석의 예로는 행동의 상대적 중요성이 있으며, 그렇지 않으면 행동의 적시성과 무관하다.TUF로 대표되는 전통적인 마감일은 특별한 경우로서, 즉 마감 시간에 효용성이 1에서 0으로 낮아지는 단계, 즉 중요성이 없는 적시성이다.TUF는 더 일반적이다. 중요한 시간을 가지며, 애플리케이션별 모양과 효용 값이 양쪽에 있고, 이후에는 증가하지 않는다.확고하고 부드러운 실시간의 다양한 연구자 및 실무자 정의도 TUF 모델의 특별한 사례로 표현될 수 있다.

TUF 예시

복수의 TUF 구속력 있는 조치를 스케줄링하기 위한 최적성 기준은 역사적으로 최대 효용 발생(UA)(예: 개별 조치의 완료 효용에 대한 (아마도 예상) 가중 합계)에 불과했다.따라서 이것은 중요한 시기에 대한 시의성을 고려한다.추가 기준(예: 에너지, 예측 가능성), 제약 조건(예: 의존성), 시스템 모델, 스케줄링 알고리즘 및 보증은 TUF/UA 패러다임과 그 사용 사례가 진화함에 따라 추가되었다.좀 더 표현적으로, TUF/UA는 발생 효용성, 적시성, 예측 가능성 및 다른 스케줄링 기준과 제약조건이 상황 애플리케이션 QoS를[a] 산출하는 스케줄에 대해 서로 교환되도록 허용한다.

시간/유틸리티 기능

TUF/UA 패러다임은 원래 전통적인 실시간 개념과 관행이 충분히 표현되지 않는 다양한 군사 애플리케이션의 특정 조치 적시성, 적시성의 예측 가능성 및 애플리케이션 QoS 기반 스케줄링 요구를 해결하기 위해 만들어졌다(예를 들어, 마감일이 없는 동적 적시성 중요 시스템의 경우).부하 복원력(예: 일상적인 작업 과부하의 대상이 되는 시스템의 경우)그러한 응용의 중요한 일반적인 예는 미사일 방어(공증[3][4][5])이다.

이후, 원래의 TUF 모델, TUF/UA 패러다임의 시스템 모델, 그리고 따라서 스케줄링 기법과 알고리즘에 대한 수많은 변형이 학술 문헌(예: 예)[6][7][8][9][10]에서 연구되어 민간 문맥에 적용되었다.

후자의 예를 몇가지 들자면,cyber-physical systems,[11]AI,[12]multi-robot systems,[13]드론 scheduling,[14]자치 robots,[15]지적vehicle-to-cloud 데이터 산업 공정 control,[17]거래 transfers,[16]systems,[18]고성능 computing,[19]구름 systems,[20]이종 clusters,[21]서비스 관련 compu을 포함한다.Ting,[22]네트워킹 및 메모리 관리까지 항의라도[23].실제[24] 및 가상[25] 시스템.제철소의 예는 클라크의 박사학위 논문 소개에 간략히 설명되어 있다.[26]

TUF와 그 효용 해석(항문), 척도 및 값은 영역별 주제 지식에서 도출된다.[27][5]효용에 대한 역사적으로 빈번한 해석은 행동의 상대적 중요성이다.[b]시스템 모델에 대한 강력한 제약 조건을 따르는 정적 효용 값을 할당하기 위한 ar priori의 프레임워크가 고안되었지만,[8] 후속 (이전의 경우와 마찬가지로) TUF/UA 연구 개발은 더 일반적인 프레임워크를 만들려고 시도하기보다는 애플리케이션별 특수성을 이용하는 것에 의존하는 것을 선호해 왔다.그러나 그러한 틀과 도구는 중요한 연구 주제로 남아 있다.

전통적인 관습에 따르면, TUF는 선형 함수를 포함한 오목함수다.몇 가지 예시 TUF의 설명을 참조하십시오.

연구 문헌의 TUF/UA 논문은, 예를 들어,[28][6][29][30][8][10] 거의 예외 없이, 지정과 일정이 더 용이하기 때문에 선형 또는 부분 선형[31](기존 마감 기반 포함) TUF만을 위한 것이다.많은 경우에 TUF는 단조롭게 감소하고 있을 뿐이다.

상수함수는 조치의 완료 시간과 관련이 없는 조치의 효용(예: 조치의 상수 상대적 중요도)을 나타낸다.이것은 시간 의존적 조치와 시간 독립적 조치 모두를 일관성 있게 스케줄링할 수 있게 한다.

TUF는 전지구적으로 중요한 시간을 가지며 그 이후에는 효용이 증가하지 않는다.TUF가 절대 감소하지 않는다면, TUF의 글로벌 임계 시간은 TUF의 최대 효용에 도달하는 첫 번째 시간이다.상수 TUF는 조치의 릴리스 시간 또는 TUF 종료 시간과 같은 스케줄링 목적을 위해 임의의 중요 시간을 갖는다.글로벌 임계 시간은 현지 임계 시간[2] 뒤에 따를 수 있다. 예를 들어, 하향 평준화 단계를 가진 TUF를 대략적인 하향 곡선으로 간주한다.[c]

TUF 효용 값은 일반적으로 정수 또는 합리적인 숫자 중 하나이다.

TUF 유틸리티는 음의 값을 포함할 수 있다. (범위 내에서 음의 값을 갖는 TUF가 스케줄링 고려에서 반드시 삭제되거나 작업 중에 중단되는 것은 아니다. 이 결정은 스케줄링 알고리즘에 따라 결정된다.)

TUF로 대표되는 통상적인 마감 시간(d)은 특별한 경우로서 단위 벌점이 있는 하향 단계[d] TUF(즉, 임계 시간 이전과 이후 효용 값 0을 갖는 경우)이다.

보다 일반적으로, TUF는 하향(과 상향) 단계 기능을 모든 임계 전/후 시간 유틸리티를 가질 수 있도록 허용한다.

TUF로 표시되는 지각은[32] 0이 아닌 효용이 선형 함수 C - d인 특별한 경우로, 여기서 C는 동작의 완료 시간(전류, 예상 또는 믿음)이다.[e]보다 일반적으로, TUF는 제로 경각과 지각은 비선형(예를 들어, 지각의 증가로 위협 탐지 시와 같이 비선형적으로 효용이 감소할 수 있다)을 허용한다.

그러므로, TUF는 실시간 컴퓨팅에서 전통적인 조치 완료 시간 제약의 풍부한 일반화를 제공한다.

대안적으로, TUF/UA 패러다임을 채택하여, 글로벌 중요 시간에 관한 적시성을 그 자체로 종료되는 적시성 대신 유틸리티 종료(즉, 애플리케이션 수준 서비스 품질(QoS))의 수단으로 사용할 수 있다.(아래 참조).

TUF(형태 및 값)는 현재 대기 중이거나 작동 중인 모든 조치에 대해 독립적으로 애플리케이션 또는 그 운영 환경에 의해 동적으로 조정될 수 있다.[2][f]

이러한 적응은 일반적으로 개별 이벤트(예: 탄도 미사일 비행 단계와 같은 적용 모드 변경)에서 발생한다.[5]

대안적으로, 이러한 적응은 동작 기간과 TUF가 동작이 해제되거나 작동을 시작할 때의 애플리케이션별 기능인 동작과 같이 연속적으로 발생할 수 있다.작동 지속시간은 증가하거나 감소하거나 둘 다일 수 있으며, 비단조적일 수 있다.이 연속적인 경우를 시간 의존적 스케줄링이라고 한다.[33][34]레이더 추적 시스템과 같은 특정 실시간 군사 애플리케이션에 대해 시간 의존적 스케줄링이 도입되었지만 이에 국한되지는 않는다.[35][36][g]

유틸리티 누적 스케줄링

시스템에서 여러 동작이 순차적으로 독점적으로[h] 공유되는 리소스(프로세서, 네트워크, 외부 애플리케이션 장치(센서, 액추에이터 등)에 대한 액세스를 다투게 될 수 있다.- 싱크로나이저, 데이터 등의 논리적인 것.

TUF/UA 패러다임은 스케줄링 이벤트(예: 조치 도착 또는 완료) 또는 상태(예: 시간)에서 스케줄을 생성(또는 업데이트)하는 애플리케이션별 알고리즘 기법을 사용하여 이 경합의 각 인스턴스를 해결한다.인스턴스의 경합된 작업은 일정의 전면에서 순서대로 자원 접근을 위해 순차적으로 파견된다.따라서 액션 UA 시퀀싱은 탐욕스럽지 않다.[i]

알고리즘 기법은 하나 이상의 애플리케이션별 목표(즉, 최적성 기준)에 기초하여 일정을 만든다.

TUF가 있는 작업을 스케줄링하는 주요 목표는 UA(최대 효용 발생)이다.누적 효용은 스케줄이 완료된 조치의 효용에 대한 애플리케이션별 다항식 합이다.작용에 하나 이상의 확률적 매개변수(예: 운전기간)가 있는 경우, 발생 효용도 역시 확률적이다(예: 기대 다항식 합계).

효용과 발생 효용은 일반적이며, 그 해석(항법)과 척도는 응용 프로그램마다 다르다.[27]

조치의 작동 지속시간은 시스템 구성 시간에 고정되고 알 수 있다.더 일반적으로, 그것은 고정적이거나 확률적일 수 있지만, 그것이 도착하거나 출시될 때까지 (확실히 또는 기대적으로) 알려져 있지 않다.

작동 지속시간은 동작 시작 시간의 애플리케이션별 기능일 수 있다. 증가하거나 감소하거나 둘 다일 수 있으며, 비단조적일 수 있다.이 경우를 시간 의존적 스케줄링이라고 한다.[33][34][35][36]

메모들

  1. ^ 서비스 품질(QoS)이라는 용어는 처음에는 통신망의 맥락에서 생겨났지만, 이후 애플리케이션 수준에서 공통적으로 적용되었다.
  2. ^ 중요도에 따른 일정은 중요도에 따른 욕심 많은 파견과 같지 않다.
  3. ^ 이것은 로크가 로크 86에서 임계 시간이라는 용어를 소개한 것보다 더 일반적인 것이다.
  4. ^ 함수 또는 첫 번째 또는 두 번째 파생상품에 불연속성이 있다.
  5. ^ 예를 들어, 인식론적 불확실성이 있는 특정 시스템 모델에는 뎀스터-샤퍼 이론, 부정확한 확률 이론 등과 같은 수학적 근거 이론을 사용할 수 있다.
  6. ^ 연산(operating)은 비컴퓨터(예: 메카트로닉) 작용뿐만 아니라 실행하는 연산 작업을 포함하는 일반적인 사례로 사용된다.
  7. ^ 시간 의존적 스케줄링(즉, 일부 조치의 작동 지속 시간은 시작 시간의 함수)은 마감 시간(또는 중요한 시간)이 있는 조치의 관점에서 실시간 스케줄링과 구별되며 이에 국한되지 않는다.
  8. ^ 순차적 배타성은 공유 접속의 특별한 경우로서 일반성의 손실 없이 단순성을 위해 사용된다.
  9. ^ 일부 UA 스케줄러는 과부하를 욕심 많은 방식으로 제거할 수 있다(cf).로크 86의 제7.5.1조.

참조

  1. ^ E. 더글러스 젠슨, C.더글러스 로크, 그리고 토쿠다 히데유키.실시간 운영 체제를 위한 시간 가치 기반 스케줄링 모델, Proc.실시간 시스템 심포지엄, IEEE, 1985.
  2. ^ a b c E. 더글러스 젠슨.비동기 분산형 컴퓨터 시스템의 적시성 모델, Proc.국제 분권형 시스템 국제 심포지엄, IEEE, 1993
  3. ^ E. 더글러스 젠슨.제3장 레이더 스케줄링, 제1절 Gouda+77 (미분류 버전)의 스케줄링 문제.
  4. ^ 모하메드 G. 고다, 이우 한, E. 더글러스 젠슨, 웨슬리 D.존슨, 리처드 Y. 케인 (편집자)분산 데이터 처리 기술, Vol. IV, BMD에 DDP 기술의 적용: 아키텍처 및 알고리즘, 미분류 버전, 국방 기술 정보 센터 a0477, Honeywell Systems and Research Center, MN, 1977.
  5. ^ a b c 데이비드 P.메이너드, 새뮤얼 E.선장, 레이먼드 K.클라크, J. 듀안 노스컷, E. 더글러스 젠슨, 러셀 B.케글리, 벳시 A. 짐머만, 피터 J. 켈러.알파에 대한 실시간 전투 관리 명령 및 제어 응용 사례, 섹션 8.2.1, Archons 프로젝트 기술 보고서, 1988 및 공개 버전 2008.
  6. ^ a b 비노이 라빈드란, E. 더글러스 젠슨, 펑리.최근 시간/유틸리티 기능 실시간 스케줄링 및 리소스 관리, Proc.2005년 제8회 객체 지향 실시간 분산 컴퓨팅 국제 심포지엄.
  7. ^ Saud A. Aldami와 Alan Burns.실시간 시스템 스케줄링을 위한 동적 가치 밀도, Proc. 제11차 Euromicro Conference on Real-Time 시스템s, IEEE, 1999.
  8. ^ a b c 앨런 번즈, D.프라사드, A. 본다발리, F.디 잔도메니코, K. 라마미담, J. 스탄코비치, L. 스트리그니.유연한 실시간 시스템 스케줄링에서 가치의 의미와 역할, 2000년 시스템 아키텍처 저널, 엘시비에.
  9. ^ 디비야 프라사드, 앨런 번즈, 마틴 앳킨스.Adaptive Real-Time 시스템에서 유효한 유틸리티 사용.Real-Time Systems, Kluwer, 2003.
  10. ^ a b 켄 첸과 폴 뮬레탈러.시간 값 함수를 이용한 실시간 시스템의 스케줄링 알고리즘 패밀리.Real-Time Systems, vol. 10 No. 3, Kluwer, 1996.
  11. ^ 테리 티드웰, 로버트 글라우비우스, 크리스토퍼 D.길과 윌리엄 D.스마트. Cyber-Physical System Scheduler, Proc.의 기대 시간 유틸리티 최적화.IEEE 실시간 시스템 심포지엄, 2010.
  12. ^ 야길 로넨, 다니엘 모세, 그리고 마르타 E. 폴락.ACM SIGART 게시판, 제7권 제2호, 1996년 심의-일정 문제를 위한 가치밀도 알고리즘
  13. ^ 미하와 바르시스, 아가타 바르시스, 헤르만 헬워그너.다중로봇시스템, 센서의 정보분포를 위한 평가모형, 2020년 1월
  14. ^ 시린 시크호아 킹, 폴 발라지, 니콜라스 트라마 알바레스, 윌리엄 J. 노텐벨트.시간에 민감한 서비스 수준 계약을 체결한 드론 전달 네트워크의 수익 기반 스케줄링, Proc. 제 12회 EAI 국제 성능 평가 방법론 및 도구 회의, ACM, 2019.
  15. ^ 알디스 바움스자동 제어 및 컴퓨터 과학, 제46권, 제6호, 앨러튼 프레스, 2012.
  16. ^ 장 이바르츠, 마이클 라우어, 마티외 로이, 장 샤를 파브르, 올리비에 플레부스.Soft Real-Time Scheduling Concepts, Proc. 28차 Real-Time Networks and Systems 국제회의, ACM, 2020을 통한 차량 대 클라우드 데이터 전송 최적화
  17. ^ 러거 하베츠.하이네켄 Zoeterwoude의 포장 라인 41 라인 성능 개선, 과학 학사 프로젝트 논문, 산업 엔지니어링 및 관리, 2019년 20대 대학.
  18. ^ 자얀트 R.하리차, 자얀트 R, 마이클 J. 캐리, 미론 리브니.VLDB Journal, 1993년 실시간 데이터베이스의 가치 기반 스케줄링.
  19. ^ 루이스 디에고 브리체뇨, 바베쉬 켐카, 하워드 제이 시겔, 앤서니 A.마키예프스키, 크리스토퍼 그로어, 그레고리 코닉, 진 오콘스키, 스티브 풀.이기종 컴퓨팅 시스템에서 리소스 할당 모델링 및 평가를 위한 시간 유틸리티 기능, Proc.IEEE 국제 병렬 및 분산 처리 심포지엄, 2011.
  20. ^ 시한 툰크, 니르말쿰바레, 알리 아코글루, 살림 하리리, 딜런 마코벡, 하워드 제이 시겔.클라우드 컴퓨팅 시스템에 대한 서비스 기반 작업 스케줄링의 가치, Proc.클라우드 및 자율 컴퓨팅에 관한 국제 컨퍼런스,
  21. ^ 비그네시 T. 라비1, 미켈라 베치2, 가간 아그라왈1, 시리마트 차크라다르.ValuePack: CPU-GPU 클러스터의 가치 기반 스케줄링 프레임워크, Proc.고성능 컴퓨팅, 네트워킹, 스토리지 및 분석에 관한 IEEE 국제 컨퍼런스, 2012.
  22. ^ 앨빈 아우영, 로라 그리트, 자넷 위너, 존 윌크스.서비스 계약 및 종합 유틸리티 기능, Proc. 15회 고성능 분산 컴퓨팅 국제 심포지엄, 2006.
  23. ^ 징강왕과 비노이 라빈드란.시간-유틸리티 기능 기반 스위칭 이더넷: 패킷 스케줄링 알고리즘, 구현 및 타당성 분석, 병렬 및 분산 시스템에 대한 IEEE 거래, 제15권, 제2호, 2004년 2월.
  24. ^ 조현중, 비노이 라빈드란, 체우나. 동적, 다중 프로세서 실시간 시스템의 가비지 수집기 스케줄링, IEEE 병렬 및 분산 시스템 20(6), 2009년 6월.
  25. ^ 샤로오즈 페이자바디와 고드마르 백.가비지 수집 인식 유틸리티 2007년 7월 Real-Time 시스템s Journal, Volume 36, Issue 1–2, 2007.
  26. ^ 레이먼드 K.Clark. 스케줄링 의존적 실시간 활동, 박사.논문, CMU-CS-90-155, 컴퓨터 과학부 카네기 멜론 유니브, 1990.
  27. ^ a b 레이먼드 K.클라크, E. 더글러스 젠슨, 아르카디 케네프스키, 존 모어, 폴 월리스, 톰 휠러, 윤장, 더글러스 M.웰스, 톰 로렌스, 팻 헐리.적응형, 분산형 항공 추적 시스템, IEEE 병렬 및 분산형 실시간 시스템, LNCS 제1586권, Springer-Verlag, 1999.
  28. ^ C. 더글러스 로크실시간 스케줄링을 위한 최상의 의사 결정, 박사.논문 CMU-CS-86-134, 카네기-멜론 대학교 컴퓨터 과학부, 1986.
  29. ^ 펑리.유틸리티에 따른 실시간 예약: 모델과 알고리즘, 박사 논문, 버지니아 폴리테크닉 연구소와 주립대학교, 2004.
  30. ^ 펑리, 하이상 우, 비노이 라빈드란, E.더글러스 젠슨상호 배제 자원 제약이 있는 실시간 활동을 위한 유틸리티 스케줄링 알고리즘, 컴퓨터에서의 IEEE 트랜잭션, 제55권, 제4호, 2006년 4월.
  31. ^ 지산 궈와 산조이 부루아.Maximizing Pitswise Linear Utility, IEEE Transactions on Neural Networks and Learning Systems, vol. 27 no. 2016년 2월.
  32. ^ 제러미 P.에릭슨.Soft Real-Time Systems의 Taddity Bound and Overload 관리, 박사 논문, 2014년 노스캐롤라이나 대학교(University of North Carolina, University of North Carolina, University.
  33. ^ a b 스타니슬로 가위즈노비츠40년간의 시간 의존적 스케줄링에 대한 검토: 주요 결과, 새로운 주제 및 개방형 문제, Journal of Scheduling 23, 3–47, Springer, 2020.
  34. ^ a b K. D. 글레이즈브룩.노후화 또는 지연될 수 있는 확률적인 일자리의 단일 기계 스케줄링, 해군 연구 물류 39호, 1992년 와일리.
  35. ^ a b 우무트 발리, 하이상 우, 비노이 라빈드란, 조나단 스티븐 앤더슨, E. 더글러스 젠슨.가변 비용 함수에 따른 유틸리티 실시간 스케줄링, IEEE 컴퓨터 트랜잭션, 56권, 3번, 2007년 3월.
  36. ^ a b 케빈 I-J호, 요셉 Y-T. 렁과 W-D.Wei. 시간 의존적인 실행 시간을 갖는 스케줄링 작업의 복잡성, 정보 처리 편지 48 (1993) No. 6, Exvier, 1993년 12월 20일.

외부 링크