Prioritizing processes

[Ole Tange]

At my work we have programs that baloon in memory usage after running
for some time.

For this excersize I will assume a simplified setup:

* the program baloon takes upto 60 minutes to run
* the program baloon increases memory usage by 1 GB/minute
* the hardware has 60 GB usable RAM and enough swap

To play it safe we could simply run a single baloon at a time. But
since many baloons may not run for all 60 minutes and thus not take up
all the 60 GB it should be faster to run more of them a the same time
and suspend some of the baloons if we run out of memory.

For the first minute we can run 60 baloons, but then memory is
exhausted. So we need a way to tell some of the baloons to suspend.

I am thinking of this algorithm:

Assign a priority to each baloon 1..n in the order each baloon was
started. Baloon k will have assigned a parent k-1.

The goal is now to get baloon 1 to finish first and let as many
baloons as possible run on the spare capacity giving priority to the
lower numbered priorities.

while not me.dead:

  if parent.state == dead and not me.oldest:
    parent = find_older_parent
    if not parent exists:
      me.oldest = true

  if me.oldest:
    me.run
  else:
    if parent.state == run:
      if memfree > 1 GB:
        # Parent is running and there is memory free => run
        me.run
      else:
        # Parent is running, but no free mem
        # => Wait to be swapped out or for a job with lower priority to finish
        me.suspend
    else:
      # Parent is not running so neither should this
      me.suspend
  sleep 1

Can you see situations where this will not work?


/Ole