공정한 작업 처리 알고리즘

Question

사용자 업로드를 허용하고 처리를 수행 한 다음 그 결과를 반환하는 컴퓨터가 있습니다. 받은 각 업로드를 처리하는 데 일반적으로 몇 분이 걸립니다.

일부 사용자는 기본적으로 다른 사용자에게 오랫동안 처리를 거부하는 많은 작업을 업로드 할 수 있습니다. 하드 캡을 설정하고 우선 순위 대기열을 사용하는 것으로 생각했습니다. 1 시간에 5 번 업로드 한 후 모든 새 업로드의 처리 우선 순위가 낮아집니다. 나는 기본적으로 모든 작업을 처리하고 싶지만 1000 명의 작업을 업로드 한 사용자가 모두 기다리게하지 않으려 고합니다.

제 질문은, 더 좋은 방법이 있습니까?

내 목표는 업로드와 결과가 반환되는 시간을 최소화하는 것입니다. 알고리즘이 분산 된 방식으로 작동 할 수 있다면 이상적입니다. 과정에서 치명적인 오류가있을 가능성이 얼마나되는지로

감사

Answer 1

구현뿐만 아니라, 이러한 작업이 무엇인지에 어떻게 그들이 가지고 어떻게 다양한 처리 시간이 따라 크게 달라집니다.

사용자가 작업을 균일하게 배포하는 쉬운 방법은 작업을 제출 한 모든 사용자의 목록을 유지하는 것입니다. 새로운 작업을 할 준비가되었을 때, 임의의 대기열에서 다음 작업을 수행하는 것보다는 매번 사용자마다 가장 많이 수행하는 작업을 반복하십시오.

다시 말하지만, 여러 가지 방법으로 수행 할 수 있습니다. 사용자의 제출 된 작업 목록으로 맵을 추천합니다. 새로운 작업을 준비 할 때마다지도의 키를 순환하십시오. 당신이있는 키에 상관없이 작업 목록을 얻고 첫 번째 작업을하십시오.

이것은 하나의 작업이 제출 된 작업 옆에서 실행되는 것에 의존하지 않는다는 점에서 각 작업이 "원 자성"이라고 가정합니다.

도움이되는 희망은 당연히 내가 요구하는 것을 완전히 오해했을 수 있습니다.

Answer 2

사용자가 제출할 수있는 최대 작업 수는 얼마나됩니까? 사용자가 한 번에 한 가지 작업을 제출할 수 있습니까 아니면 일자리일까요?

그래서 알고리즘 당신은 롤 - 네 - 자신을하지 않아도이

If the User has submitted jobs Then 
Check how many jobs per hour 
If the jobs per hour > than the average Then 
Modify the users profile to a lower priority 
Else 
Check Users priority level and restore 
End If 

If the priority = HIGH 
process right away 
Else If priority = MEDIUM 
Check Queue for High Priority 
If High Priority Found (rerun this loop) 
Else Process 
Else If priority = LOW 
Check Queue for High Priority 
If High Priority Found (rerun this loop) 
Else Process 
Check Queue for Medium Priority 
If Medium Priority Found (rerun this loop) 
Else Process 
Process Queue 
End If 

Answer 3

처럼 뭔가를 갈 것입니다. Sun Grid Engine이 있습니다. 이런 종류의 일을 할 수 있도록 만들어진 오픈 소스 도구이며, 지불 할 의사가 있다면 직장에서 사용하는 Platform LSF이 있습니다.

Answer 4

Edmond Blossom V와 같은 그래프 알고리즘을 사용하여 모든 사용자와 작업을 프로세스에 할당 할 수 있습니다. 사용자가 다른 사용자를 더 업로드 할 수 있다면 프로세스를 찾는 것이 더 간단 할 것입니다. Blossom V 알고리즘을 사용하면 서버가 처리 할 수있는 최대 프로세스를 초과하지 않도록 임계 값을 정의 할 수 있습니다.