Requesting multiple resources simultaneously

[nkz]

Dear all,

I am using Python and Simpy for a simulation. In the simulation jobs are processed by resources. Some jobs require a single resource, other jobs require multiple resources at the same time. I would like to retrieve (get / request) multiple resources at the same time. I've asked a similar question on stack overflow, but received no response. 

In the example below resources are requested sequentially. As a consequence, job 3 is started before job 2 at time 5 even though job 2 could have started at time 4 because resource 2 became available at time 4. 

I am trying to achieved the desired sequence [1, 3, 2, 4]. 

I am able achieve the desired sequence by prioritizing jobs which request fewer resources (e.g. priority=len(resources_required)). However, that would mean that jobs which require fewer resources get prioritized over jobs which require more resources even if these jobs were generated earlier. I am looking for a solution which preserves the first-come, first served (fcfs) sequence. I only want to prioritize the job that requires fewer resources if jobs that were generated earlier still have to wait for other resources.

I thought about delaying the requests, as suggested here, but I don't know how to go about this.

Thanks,

nkz

Code:

import simpy

import random

def source(env, jobs):

    count = 0

    for i in jobs:

        env.process(job(env, count, i))

        yield env.timeout(1)

        count += 1

def job(env, count, resources_required):

    print('job: {} requests resources: {} at time: {}'.format(count, resources_required, env.now))

    resources_needed = []

    for i in resources_required:

        for j in resources:

            if i == j['id']:

                resources_needed.append(j['resource'].request())

    yield env.all_of(resources_needed)

    print('job: {} retrieved resources: {} at time: {}'.format(count, resources_required, env.now))

    yield env.timeout(4)

    for i in resources_needed:

        i.resource.release(i)

    print('job: {} released resources: {} completed at time: {}'.format(count, resources_required, env.now))

    sequence.append(count)

env = simpy.Environment()

resources = []

capacity = 1

for i in range(5):

    resource = {

        'id': i,

        'resource': simpy.PriorityResource(env, capacity=capacity)

    }

    resources.append(resource)

jobs = [

    [2],

    [0],

    [2, 0],

    [2]

]

sequence = []

random.seed(1234567890)

env.process(source(env, jobs))

env.run(until=50)

print('...')

print('current sequence: {}'.format(sequence))

Output:

job: 0 requests resources: [2] at time: 0

job: 0 retrieved resources: [2] at time: 0

job: 1 requests resources: [0] at time: 1

job: 1 retrieved resources: [0] at time: 1

job: 2 requests resources: [2, 0] at time: 2

job: 3 requests resources: [2] at time: 3

job: 0 released resources: [2] completed at time: 4

job: 1 released resources: [0] completed at time: 5

job: 2 retrieved resources: [2, 0] at time: 5

job: 2 released resources: [2, 0] completed at time: 9

job: 3 retrieved resources: [2] at time: 9

job: 3 released resources: [2] completed at time: 13

...

current sequence: [0, 1, 2, 3]

...

desired sequence: [0, 1, 3, 2]

[Peter Grayson]

What you are seeking is an optimal scheduling of jobs, but in this implementation, each job schedules itself based on simple a first-come first-served queueing mechanism.

I believe that to get the optimal job schedule that you desire, your model will need to have an active scheduler process that matches jobs to resources in an optimal fashion. Neither an individual job nor an individual resource has enough [local] information to determine when a job should be scheduled out of its queued order. A scheduler process that has [global] knowledge of the complete job queue and resource state can make that kind of decision.

It may be that you want something like the stable marriage algorithm [1] to do this optimal matching. Or perhaps you can get away with a simpler application specific scheduler.

I notice that jobs have a fixed processing time (of 4). If jobs really have predetermined and fixed durations, that makes the scheduler's job easier than if jobs' durations are either variable or variable and indeterminant. Suffice that this characteristic of the jobs is an important consideration.

[1] https://en.wikipedia.org/wiki/Stable_marriage_problem

Cheers,

Pete

--
You received this message because you are subscribed to the Google Groups "python-simpy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to python-simpy+unsubscribe@googlegroups.com.
To post to this group, send email to python...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/python-simpy/59c8c3b0-7934-41f6-a3fe-18a6a3643da3%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[nkz]

Hi Pete,

Thank you for your response. 

The example I posted is simplified. I am looking to extend the model and include random processing times for jobs. The processing time (of 4) is just an example used to demonstrate the sequencing problem. 

I will look into the stable marriage problem. It will take me a bit of time. Thank you for the suggestion. Although, I would prefer a more 'on the fly' option. Perhaps checking the request queue after each resource is released would be a viable option.

Would it not be possible to use and event to delay the request until a resource becomes available by triggering an event every time a resource becomes available? 

Pseudo code:

yield 'until resource becomes' available:

for i in resource.queue:

    job = i.process # retrieve job that made the request (see also stackoverflow).

    resources_required_for_job = [list of resources]

    number_of_resources_available_for_job = 0

    for j in resources_required_for_job:

         if j.users < j.capacity:

              number_of_resources_available + 1

    if len(resource_required_for_job) == number_of_resources_available_for_job:

        for k in resources_required_for_job:

             k.request()

        break: #the break should ensure fcfs if requests are appended to the queue in order

I tried the above, but couldn't make it work. I don't know how to set and reset the events needed to make the jobs wait for a resource. 

I am looking for a solution which allows me to check, and wait if necessary, when requests might succeed. If they don't succeed then wait, if they do succeed then request the resources. 

The old version (2) of Simpy had a wait until option which check the state after each event. This might be what I am looking for. A stackoverflow suggests that the waituntil option was not included in SimPy 3 because it was very cpu intensive. 

I've also found a batchget method on stackoverflow for the store. However, this method relies on creating a subclass of the store. I don't know how to subclass the resource or if it would be necessary to do so. 

Thanks,

nkz

To unsubscribe from this group and stop receiving emails from it, send an email to python-simpy...@googlegroups.com.

[jpgr...@gmail.com]

Consider this example with a simple scheduler:

from contextlib import ExitStack
import simpy

class Job:
    def __init__(self, env, name, timeout, resources):
        self.env = env
        self.name = name
        self.timeout = timeout
        self.resources = resources
        self.completion = env.event()

    def is_runnable(self):
        return all(res.count < res.capacity
                   for res in self.resources)

    def run(self):
        with ExitStack() as stack:
            reqs = [stack.enter_context(res.request())
                    for res in self.resources]
            yield self.env.all_of(reqs)
            print(self.env.now, self.name, 'running')
            yield self.env.timeout(self.timeout)
            print(self.env.now, self.name, 'completed')
            self.completion.succeed()

def scheduler(env, jobs):
    running = []
    while jobs:
        runnable = [job for job in jobs if job.is_runnable()]
        if runnable:
            job = runnable[0]
            print(env.now, 'schedule', job.name)
            env.process(job.run())
            jobs.remove(job)
            running.append(job)
            # Allow job to acquire resources before rebuilding
            # the runnable jobs list.
            yield env.timeout(1)
        else:
            yield env.any_of(job.completion for job in running)
            running = [job for job in running
                       if not job.completion.triggered]

if __name__ == '__main__':
    env = simpy.Environment()
    res = [simpy.Resource(env, 1)
           for _ in range(4)]
    jobs = [
        Job(env, 'a', 4, [res[2]]),
        Job(env, 'b', 4, [res[0]]),
        Job(env, 'c', 4, [res[2], res[0]]),
        Job(env, 'd', 4, [res[2]]),
    ]
    env.process(scheduler(env, jobs))
    env.run()

Note that the four jobs complete in order [a, b, c, d]. You originally indicated that you desired a completion order of [a, b, d, c], but given this list of jobs, the former both orderings seem equally optimal, but the former is also FIFO. This scheduler could be modified to give priority to jobs requiring more resources, but anytime there is prioritization, the door is opened to starvation.

Hope this helps.

Cheers,
Pete

[jpgr...@gmail.com]

Oops, in the last example, `scheduler()` should `yield env.timeout(0)` (not 1) after scheduling a job.

Pete