Skip to content

add preemption functionality #34

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
bart6114 opened this issue Dec 8, 2015 · 10 comments
Closed

add preemption functionality #34

bart6114 opened this issue Dec 8, 2015 · 10 comments
Milestone

Comments

@bart6114
Copy link
Member

bart6114 commented Dec 8, 2015

Let's use this for further discussion on the preemption topic.

Maybe we should start with trying to settle on a definition, a suggestion:

If arrival A has seized 1 unit of resource X (with capacity 1) and arrival B - with a higher priority and a preempt attribute set to TRUE - tries to seize resource X:

  • processing of A is interrupted
  • resource X is released
  • resource X is immediately seized by arrival B (if no other arrivals with higher priority and preempt set to TRUE tries to seize it)
  • once arrival B releases resource X, arrival A re-seizes resource X (if no other arrivals with higher priority and preempt set to TRUE tries to seize it)
  • once arrival A has re-seized resource X, it continues processing (or restarts processing - debatable)
@Enchufa2
Copy link
Member

Enchufa2 commented Dec 8, 2015

👍 Comments inline:

If arrival A has seized 1 unit of resource X (with capacity 1) and arrival B - with a higher priority and a preempt attribute set to TRUE - tries to seize resource X:

First of all, the resource needs to support preemption. I mean, I would create a flag in add_resource to enable preemption, because this is a time consuming feature (from the simulator point of view, because you need to do a lot more things) and it should not be activated if it's not required.

env <- simmer() %>%
  add_resource("CPU", preemptive=TRUE)

Said that, I don't know if it is fair that any arrival can be preempted (debatable). I'm thinking about an operating system: some kernel tasks are not preemptible. In this scenario, the preemption depends on the task being served, not on the arriving one.

So what if we define an attribute preemptible for the arrival A? Thus, an arrival B with a higher priority would gain access to the server if the arrival A had performed a preemptible seize AND (and this is important, I think) A had seized the same amount (or more) than B requests.

  • processing of A is interrupted
  • resource X is released
  • resource X is immediately seized by arrival B (if no other arrivals with higher priority and preempt set to TRUE tries to seize it)

The scenario between parentheses cannot happen, because the preemption has been triggered by B and these steps occur instantaneously.

  • once arrival B releases resource X, arrival A re-seizes resource X (if no other arrivals with higher priority and preempt set to TRUE tries to seize it)

If we implement A as preemptible instead of B with preempt, this would become if no other arrivals with higher priority had been enqueued).

  • once arrival A has re-seized resource X, it continues processing (or restarts processing - debatable)

It could be another argument for seize:

task <- create_trajectory() %>%
  seize("CPU", priority=1, preemptible=TRUE, restart=FALSE) %>%
  timeout(function() runif(1, 5, 10)) %>%
  release("CPU")

@Enchufa2 Enchufa2 added this to the v3.1.0 milestone Dec 8, 2015
@Enchufa2
Copy link
Member

Enchufa2 commented Dec 9, 2015

Another issue. Suppose the following:

task0 <- create_trajectory() %>%
  seize("CPU", 1, priority=0, preemptible=TRUE) %>%
  timeout(10) %>%
  release("CPU", 1)

task1 <- create_trajectory() %>%
  seize("CPU", 1, priority=1) %>%
  timeout(10) %>%
  release("CPU", 1)

env <- simmer() %>%
  add_resource("CPU", 2, preemptive=TRUE) %>%
  add_generator("low_priority", task0, at(0, 1)) %>%
  add_generator("high_priority", task1, at(2)) %>%
  run()

When the high priority task arrives at 2, which task should be postponed?

@bart6114
Copy link
Member Author

bart6114 commented Dec 9, 2015

Comments inline:

If arrival A has seized 1 unit of resource X (with capacity 1) and arrival B - with a higher priority and a preempt attribute set to TRUE - tries to seize resource X:
First of all, the resource needs to support preemption. I mean, I would create a flag in add_resource to enable preemption, because this is a time consuming feature (from the simulator point of view, because you need to do a lot more things) and it should not be activated if it's not required.

env <- simmer() %>%
add_resource("CPU", preemptive=TRUE)

Completely agree.

Said that, I don't know if it is fair that any arrival can be preempted (debatable). I'm thinking about an operating system: some kernel tasks are not preemptible. In this scenario, the preemption depends on the task being served, not on the arriving one.

So what if we define an attribute preemptible for the arrival A? Thus, an arrival B with a higher priority would gain access to the server if the arrival A had performed a preemptible seize

This is a tricky one I guess. I'm reasoning the other way around. What if you have an ER with n types of patients (each their own trajectory) but only 1 type of patient (e.g. severe trauma) can preempt a resource. If you would want to simulate this using your suggestion, you should set n-1 trajectories' seize activity to preemtible. I guess the question is: in what scenario would the simulator most likely find himself?

AND (and this is important, I think) A had seized the same amount (or more) than B requests.

Good point. What if B requires two units of resource Y, while A has seized 1 unit and C has seized 1 unit (assuming A and C are preemptible)?

processing of A is interrupted
resource X is released
resource X is immediately seized by arrival B (if no other arrivals with higher priority and preempt set to TRUE tries to seize it)
The scenario between parentheses cannot happen, because the preemption has been triggered by B and these steps occur instantaneously.

Indeed!

once arrival B releases resource X, arrival A re-seizes resource X (if no other arrivals with higher priority and preempt set to TRUE tries to seize it)
If we implement A as preemptible instead of B with preempt, this would become if no other arrivals with higher priority had been enqueued).

once arrival A has re-seized resource X, it continues processing (or restarts processing - debatable)
It could be another argument for seize:

task <- create_trajectory() %>%
seize("CPU", priority=1, preemptible=TRUE, restart=FALSE) %>%
timeout(function() runif(1, 5, 10)) %>%
release("CPU")

Agree, making it a choice allows for the most flexibility.

@Enchufa2
Copy link
Member

Enchufa2 commented Dec 9, 2015

This is a tricky one I guess. I'm reasoning the other way around. What if you have an ER with n types of patients (each their own trajectory) but only 1 type of patient (e.g. severe trauma) can preempt a resource. If you would want to simulate this using your suggestion, you should set n-1 trajectories' seize activity to preemtible. I guess the question is: in what scenario would the simulator most likely find himself?

Well, this is a kind of philosophical question. 😄 If I would want to simulate your use case with my suggestion, the preemptible flag would be not a simple flag, but a level, i.e., preemptible=10 means this arrival is preemptible when the incoming priority is 10 or more. And that's it: common patients have priorities between 0 and 9 and are preemptible with a level of 10. If a severe trauma arrives (priority 10 or more), it is immediately assisted.

But what if you want to simulate my use case with your suggestion? 😉

What if B requires two units of resource Y, while A has seized 1 unit and C has seized 1 unit (assuming A and C are preemptible)?

Easy. A and C are preemptible, so both are preempted at the same time in favour of B. More challenging is the question of my last comment: #34 (comment).

@bart6114
Copy link
Member Author

This is a tricky one I guess. I'm reasoning the other way around. What if you have an ER with n types of patients (each their own trajectory) but only 1 type of patient (e.g. severe trauma) can preempt a resource. If you would want to simulate this using your suggestion, you should set n-1 trajectories' seize activity to preemtible. I guess the question is: in what scenario would the simulator most likely find himself?

Well, this is a kind of philosophical question. If I would want to simulate your use case with my suggestion, the preemptible flag would be not a simple flag, but a level, i.e., preemptible=10 means this arrival is preemptible when the incoming priority is 10 or more. And that's it: common patients have priorities between 0 and 9 and are preemptible with a level of 10. If a severe trauma arrives (priority 10 or more), it is immediately assisted.

But what if you want to simulate my use case with your suggestion?

I agree that your suggestion would allow for more flexibility. As an in-between solution, maybe we could set preemptible=TRUE as default (which should be documented very well).

What if B requires two units of resource Y, while A has seized 1 unit and C has seized 1 unit (assuming A and C are preemptible)?

Easy. A and C are preemptible, so both are preempted at the same time in favour of B.

Agree

More challenging is the question of my last comment: #34 (comment).

Regarding #34 (comment); I would say the arrival that started processing last. But I guess there aren't any strict rules for this and it comes down on us making a decision 😉

@Enchufa2
Copy link
Member

I agree that your suggestion would allow for more flexibility. As an in-between solution, maybe we could set preemptible=TRUE as default (which should be documented very well).

Agree.

Regarding #34 (comment); I would say the arrival that started processing last. But I guess there aren't any strict rules for this and it comes down on us making a decision 😉

Again, this is a sort of philosophical question. Maybe I would preempt:

  1. The preemptible arrival with the lowest priority.
  2. If there are more than one with the lowest priority, the one that has enjoyed the resource for a longer time. A kind of FIFO: first in, first to be preempted.

What do you think?

@bart6114
Copy link
Member Author

Again, this is a sort of philosophical question. Maybe I would preempt:

The preemptible arrival with the lowest priority.

👍

If there are more than one with the lowest priority, the one that has enjoyed the resource for a longer time. A kind of FIFO: first in, first to be preempted.

Pff. This is difficult. What if being preempted means starting over again? If so, it would make more sense that the last one in gets preempted (as he has less to lose). What about going the FIFO route for now and possibly make it a choice later one?

@Enchufa2
Copy link
Member

Pff. This is difficult. What if being preempted means starting over again?

Touché. What if we make restart a parameter of the resource?

env <- simmer() %>%
  add_resource("CPU", preemptive=TRUE, restart=FALSE)

Then restart=FALSE means FIFO preemption and restart=TRUE means LIFO preemption.

@bart6114
Copy link
Member Author

Touché. What if we make restart a parameter of the resource?

👍

env <- simmer() %>%
add_resource("CPU", preemptive=TRUE, restart=FALSE)
Then restart=FALSE means FIFO preemption and restart=TRUE means LIFO preemption.

Whether or not there is a restart could potentially be defined in the seize: #34 (comment). I would suggest adding a preempt_order parameter to the add_resource which e.g. defaults to fifo, which IMO is a bit more transparent.

@Enchufa2
Copy link
Member

👍

@Enchufa2 Enchufa2 modified the milestones: v3.2.0, v3.1.0 Dec 15, 2015
@Enchufa2 Enchufa2 removed this from the v3.2.0 milestone Dec 27, 2015
@Enchufa2 Enchufa2 added this to the v3.2.0 milestone Mar 5, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants