라운드 로빈 스케줄링의 평균 대기 시간

Question

대기 시간은 각 프로세스가 시간 조각을 얻기까지 대기해야하는 시간으로 정의됩니다. Shorted Job First 및 First Come First Serve와 같은 스케줄링 알고리즘에서 우리는 작업 대기열을 만들고 대기열에 얼마나 오래 기다려야 대기하는지 확인할 수 있습니다.

Round Robin 또는 다른 선점 알고리즘의 경우, 장시간 실행되는 작업은 CPU에 약간의 시간을 소비하고 선점 한 후 실행을 위해 언젠가는 기다리고 그 중 일부 시점에서 기다립니다 , 완료 될 때까지 실행됩니다. 나는 그런 스케줄링 알고리즘에서 작업의 '대기 시간'을 이해하는 가장 좋은 방법을 찾고 싶었다.

나는대로 대기 시간을 제공하는 formula 발견

Waiting Time = (Final Start Time - Previous Time in CPU - Arrival Time) 

을하지만이 공식에 대한 이유를 이해하지 못한다. 예 : 버스트 시간이 30 단위이고 라운드 로빈이 5 단위마다 발생하는 작업 A를 생각해보십시오. B (10)과 C (15)의 작업이 두 개 더 있습니다.

이가 될 것이다 서비스되는 순서 : A의 대기 시간

0 A 5 B 10 C 15 A 20 B 25 C 30 A 35 C 40 A 45 A 50 A 55 

은 = 40 - 5-40 A는 결코 기다리지 않는다 후, 때문에 0

• 나는 40를 선택합니다. 그것은 단지 시간 조각을 얻고 계속해서 나아 간다.
• A가 30에서 35 사이의 이전에 소비 되었기 때문에 5를 선택하십시오.
• 0은 시작 시간입니다.

글쎄, 나는이 공식에서 왜 15 A 20이 고려되지 않았는가? 직관적으로 말하자면, 우리가 A를 기다리는 시간을 어떻게 얻는 지 알 수 없습니다. 두 번째로 두 번째 실행 만 계산하고 도착 시간을 빼는 경우입니다.

날에 따르면, A의 대기 시간이 있어야한다 :

• 최종 시작 시간 - (이 처리에서 보내는 모든 시간의 합).

이 수식이 잘못되면 왜 그렇습니까?

이 개념에 대한 이해를 돕기 위해

Answer 1

수식이 "CPU의 이전 시간"에 의해 무엇을 의미하는지 오해했습니다. 이것은 실제로 "처리에 소비하는 모든 시간의 합"이라고 부르는 것과 같은 것을 의미합니다. (나는 "CPU에서 이전 시간"은 "이전에 CPU에서 실행 한 총 시간"에 대해 짧다 고 가정합니다. "이전"은 "최종 시작 전"을 의미합니다)

여전히 도착을 뺄 필요가 있습니다 왜냐하면 프로세스가 도착하기 전에 분명히 기다리지 않았기 때문입니다. "도착 시간"은 작업이 스케줄러에 제출 된 시간입니다. 예에서 모든 프로세스의 도착 시간은 0이므로이 값은 차이가 없지만 일반적으로 도착 시간을 고려해야합니다.

편집 : 링크 된 웹 페이지의 예를 보면 프로세스 P1은 최종 시작 전에 각각 네 시간 단위의 두 시간 조각을 사용하며 "CPU의 이전 시간"은 8로 계산됩니다. 위의 해석.

Answer 2

마지막 대기

부가가치 (시간 양자 ×는 (N-1))

여기

n는 시간의 어떤 프로세스가 간트 차트 도착을 의미하지 않는다.