[LITMUS^RT] Job Quantity Issue

[Björn Brandenburg]

> On 31 Aug 2015, at 18:27, Geoffrey Tran <gtran at isi.edu> wrote:
> 
> 
> So if I understand this correctly,

To get an authoritative answer, I suggest you study the kernel source code; this part is not very complicated at all. The kernel basically just records timestamps.

> from the kernel perspective, deadlines only occur when
> a kernel job does not consume it's budget totally.

No.

>  If that is the case, the actual job 
> being executed shouldn't affect the deadlines being missed, besides factors such as 
> causing cache misses and context switches?

Not sure what you mean by this.

First, the kernel does not interpret job completion times. It just records when a job completes and what its deadline was. In the userspace tool that you used, "completion time” > “deadline” is interpreted as a deadline miss.

What “job completion” means depends whether you use budget enforcement or not.

Without budget enforcement: a job completion is recorded only if
	a) the app calls complete_job() = sleep_next_period().

With budget enforcement: a job completion is recorded if either
	a) the app calls complete_job() = sleep_next_period().
	b) the budget is exhausted.

Case b) ensures rate-limiting.

> I can think of four cases (period=deadline>execution time): 
> short computation: task-view job() takes less than execution time
> long computation: task-view job() takes much longer than execution time
> 	With budget enforcement
> 		Long computation:
> 			The task would run out of budget, so it would be suspended
> 			until the next period. 

Correct.

> 		Short computation:
> 			The task would sleep_next_period() and therefore throw away the
> 			remaining budget. 

Correct.

> 	Without enforcement:
> 		Long computation:
> 			The task keeps running even though the budget has run out? 

Yes. Jobs run for as long as they “want" to without budget enforcement.

> 		Short computation:
> 			The task would sleep_next_period() and therefore throw away the
> 			remaining budget. 

Basically correct. Since there is no budget enforcement, there is no budget to “throw away”.

> What happens in the case with no budget enforcement?  Does each job just keep running
> even after the budget is exhausted?

Yes.

> Furthermore, does that mean that the job number
> is not incremented until sleep_next_period() is called?

Yes.

> Stated another way, if budget
> enforcement is not enabled, when is a job completed?

When userspace indicates job completion per sleep_next_period() or wait_for_job_release(), which both cause the active plugin’s complete_job() handler to be called.

> Therefore, in these following cases, I do not see how a deadline could be missed.  
> I ran some quick tests and came up with the following:
> 
> execution 	period 				Deadlines missed?
> 1			100
> 	With enforcement
> 		Long computation		No 						
> 		Short computation		No
> 	Without enforcement
> 		Long computation		No
> 		Short computation		No
> 
> 90			100
> 	With enforcement
> 		Long computation		Yes
> 		Short computation		No
> 	Without enforcement
> 		Long computation		Yes
> 		Short computation		No
> 
> These results seem strange, as this is the only task, so it should be able to get all 
> the budget that is required.

Deadline miss is defined — in userspace, by st_job_stats — as “job completion time” > “deadline”. 

Without enforcement, you can execute for as long as you want, and hence satisfy that condition if you run for long enough. 

With enforcement, your task will be cut off and your computation will be chopped automatically into job-sized budget allocations. Let’s call these allocations “server jobs”. In the trace, these will be simply called “jobs”. The tool st_job_stats (not the kernel) reports these as having met their deadline because the budget exhaustion event (recorded as a job completion) occurs before the deadline of server job. 

Your (90,100) w/ enforcement result seems very odd. With enforcement, if you have only one task, you should see no deadline misses.

> On the other hand, at least with budget enforcement off,
> the number of jobs is nearer to expected.

Please note that the tool st_job_stats is not part of the “official” LITMUS^RT toolset.  It’s just a tool that I wrote for myself because I needed a job stats summary for a paper. I did not use budget enforcement in that paper. Thus, it may not do what you want or expect if budgets are enforced… I’m happy to take patches. :-)

Best regards,
Björn