가정은 비율 단조로운 예약 알고리즘?

Question

나는 물론 리얼 타임 시스템을하고 있어요, 그리고 수업 시간에 우리는 우리가 완전히 이해할 수없는 비율 단조 스케줄링에 대한 paper of Liu and Layland의 4 장에서 몇 가지 가정에 갇혀있다 :

만약 층 (T2를/T1)은 Task1이 Task2에서 방해하는 시간의 수입니다. T2/T1에 적용된 함수가 바닥이고 ceil이 아닌 이유는 무엇입니까?

또한,이 방정식있다 : 용지에 따르면

우리 명확 이미지에 보이는 바와 같이, 식 (1)와, 필요 조건이 아닌 충분한 인 반면 식 (2) 충분한 조건입니다. 이것은 나에게 감각을 제공하지만, 결론이 같은 저자의 상태를 할 이유 : T1 < T2 및 C1, C2보다 더 높은 우선 순위의 작업 스케줄링 Task2에 가능한되도록 때마다 즉

, Task1, Task1이 Task2보다 높은 우선 순위로도 가능합니다. (반대의 경우는 사실이 아닙니다.) [...] 특히 요청 률이 높은 작업의 우선 순위가 더 높습니다.

Task2가 가장 높은 우선 순위이 두 번째 방정식은, 충분 조건 인 경우

, 는 왜 우리가 작업 1 대신 Task2의 가장 높은 우선 순위가있는 경우 작업 예약이 가능하다고 가정 할 수 있을까?

나는 스스로를 잘 설명하기를 바랍니다. 제발 내가 틀린 기사 문장을 이해했다면 나에게 말해줘.

편집 : 요청에 따라 다음은 기사의 용어에 대한 약간의 설명이며이 질문에 표시됩니다. 문서에서

, T1 은 기간 (및 마감) Task2에 작업 1, 및 T2 기간 (마감 시간)을 의미한다. C1 및 C2는 와 작업 1의 런타임 각 Task2 참조.

Answer 1

우선, T와 C가 의미하는 것을 포함하지 않은 것은 나쁘지 않습니다. 나는 기사를 읽어야했다. 그러나 그것은 감사 그렇게 흥미있는 읽 혔다.

매우 간단합니다. 첫 번째 방정식 (1)은 가능한 가장 높은 T2 기간 값을 정의합니다. C2 (작업 2를 실행하는 데 필요한 시간)와 T2에 작업 1이 요청 된 횟수를 곱한 C1 (즉, floor T1/T2)) 완전히 실행할 수 있습니다. T1이 요청되면,이 경우 가장 우선 순위가 높은 작업 인 것처럼 실행됩니다. 작업 1이 현재 실행 중이면 작업 2를 실행할 수 없습니다.

방정식 (1)을 특정 값으로 간주하십시오. 이 기사에서 제안 된 값을 사용합시다. T2 = 5, T1 = 2, C1 = C2 = 1이다.바닥 (T2/T1)은 작업 2 기간 동안 발생하는 작업 1의 요청 수를 나타냅니다. 2 (바닥 (5/2))입니다. 그것이 세 번째 요청이 실제로 실행 되었기 때문에 (그림 2 에서처럼) 천장 (T2/T1)보다 결과가 3 일 것입니다. 그러나 기간은 끝나지 않았습니다. 이를 더 잘 이해하려면 같은 경우를 고려하지만 작업 1 실행 시간 C1을 1.5로 확장하십시오. 아래는 그러한 시스템에 대한 타임 라인입니다. 그것은 equaiton (1)을 수행합니다. 만약 우리가 천정 (T2/T1)을 사용한다면 방정식은 성취되지 않을 것입니다. 나는 이것이 당신이 그 차이를보고 이해하는 데 도움이 될 것이라고 생각합니다 - 우리는 작업이 요청 된 횟수가 아니라 더 높은 우선 순위의 작업의 전체 기간이 더 낮은 우선 순위의 기간에 맞을 수있는 횟수를 고려해야합니다 태스크). 내 대답의 첫 부분

Tasks timeline. Image made using Excel. One "column" is 0.5 unit of time

, 당신의 질문의 다른 부분에 대답 좀 더 시간이 걸릴해야합니다. 곧 업데이트를 게시하겠습니다.

어쨌든 재미있는 기사에 링크 해 주셔서 감사합니다.