Scheduler job matchmaking

Currently the scheduler's work-sending algorithm is:

• if host is reliable, scan entire job array, looking for retries
• if using HR, scan entire job array, looking for jobs committed to this HR class
• if still need work, scan entire job array with no restrictions

This is bad for several reasons:

• inefficient: repeated array scans
• inflexible policy: why should reliable be more important than HR?
• hard to add new policies, like sending "hard" jobs to fasts hosts

To solve these problems we're going to change this part of the scheduler. Basic idea: given a job J and a host H, there is a function V(J, H) that represents the value of sending J to H. V(J, H) might reflect various factors:

• the computational "hardness" of J
  • CPU/deadline ratio
  • RAM or disk requirements
• H already has files required by J(or jobs already planned for sending have such files)
• J is a retry and H is a fast/reliable host
• J has already been committed to H's HR class

BOINC includes a default value function. Projects can tweak its weights, or define their own value function.

Details

functions:

fast_filter()

feasibility checks that can be done with no DB access

slow_filter()

feasibility checks that need DB access

When we scan a slot, the possibilities are:

• slot is empty
• slot is locked by another scheduler
• job fails fast filter
• job fails slow filter
• none of the above

Parameters:

N

scan at least this many slots (if scan N slots and have enough jobs to send, stop)

M

scan at most this many slots (even if don't have enough jobs to send yet)

L

if scan this many locked slots, print warning msg (should increase shmem size)

logic:

acquire semaphore
i = random index in shmem
x = ordered list of jobs to send (empty)
slots_scanned = 0
slots_locked = 0
loop
	i = i+1 % array_size
	slots_scanned++
	if slots_scanned > M
		break
	if shmem[i] is empty
		continue
	if shmem[i] is locked
		slots_locked++
		continue
	j = shmem[i]
	if !fast_filter(j) continue;
	v = v(h, j)
	if v > lowest score in x
		lock j
		release semaphore
		if !slow_filter(j)
			acquire semaphore
			unlock j
			continue
		acquire semaphore
		if x satisfies client's work request
			unlock and remove lowest-score element of x
		add j to x
	if x satisfies client's work request and slots_scanned >= N
		break;
for each job j in x
	mark slot j as empty
release semaphore
if slots_locked > L
	print "need bigger array" message