[LITMUS^RT] SRP -> PCP

[Björn Brandenburg]

On Apr 25, 2012, at 9:04 PM, Björn Brandenburg wrote:

> On Apr 25, 2012, at 8:37 PM, Glenn Elliott <gelliott at cs.unc.edu> wrote:
> 
>> I don't believe SRP can support suspensions, since it could violate stack constraints.  To be honest, I haven't throughly reviewed the Litmus SRP implementation, so maybe this really isn't an issue and I can just use SRP as-is.
>> 
> 
> Processes is Linux don't use the same stack, the constraint is irrelevant.  The important thing is that a resuming process must check the system ceiling since it may have been raised while the process was suspended. The current implementation *should* do that.

It was late last night (and there was a great soccer match on TV ;-) ); let me elaborate a bit. When a resource-holding job suspends, the system ceiling remains unchanged (i.e.,  elevated). Therefore, other jobs with priority equal or lower to the system ceiling will not be eligible to execute. Mutual exclusion is still ensured. LITMUS^RT *should* enforce this in the current implementation, but I don't think it has seen much testing recently. There's a call to srp_ceiling_block() at the end of schedule(); it *should* prevent lower-priority jobs from being scheduled while the system ceiling is elevated (again, this hasn't been tested in ages).

When a job suspends for any reason, the system ceiling may be raised while it is absent. In this case, it is not eligible to execute when it resumes until the ceiling is lowered, just as if it were a new release.  A job that suspends N times can thus incur pi-blocking due to the SRP for the duration of (N+1) critical sections (with included suspension lengths).

Note that higher-priority jobs that suspend during a critical section still prevent lower-priority jobs from executing. Under s-oblivious analysis, this is implicitly taken care of, but under s-aware analysis, you probably have to account for this explicitly. I'm not aware of any published analysis that takes self-suspensions in combination with the SRP into account.

Anyway, under the SRP, maximum pi-blocking incurred by a job that does not require shared resources is bounded by the maximum critical section length (including any suspensions). Under the PCP, the maximum pi-blocking incurred by independent jobs due to shared resources is bounded by the maximum CPU demand of any resource-holding job (i.e., suspensions of lower-priority resource-holding jobs do not cause pi-blocking). If you have both jobs that do not share *any* resources and jobs that suspend for (relatively) long times while holding shared resources, then you may be better served by the PCP. Note that this difference disappears for jobs that request *any* shared resource at all due to ceiling blocking.

I hope this helps a bit. Let me know if you have questions. A good way to get check out the current SRP implementation would be  to add a test case to liblitmus that checks if suspensions are handled correctly.

- Björn