2 shunfurh shunfurh 于 2017.09.19 17:46 提问

Harmonic Periods

Description

In real-time scheduling, predictability is very important, i.e., we would like to know the whole schedule before we really run the tasks. Rate-monotonic scheduling is very popular in real-time scheduling for periodic tasks, where tasks with shorter periods have higher priority. However, it is still dicult to know the start time and finish time of each task and they might be dierent in each period, especially for tasks with low priority, i.e. long period. The hyperperiod, the least common multiple of all periods,is usually too big to be practical to describe the whole schedule. However, if the task periods are harmonic, i.e. are multiples, it is possible to find the start time and finish time of each task quickly because the schedule becomes more regular.


Figure 1 shows that periodic tasks T1, T2, T3, T4 with execution times 1, 1, 3, 1 and periods 2, 4, 16, 32 respectively are schedulable, each task finishes execution in its period, using the Rate-Monotonic scheduling algorithm since T1, T2, T3, T4 finish execution at time 1, 2, 12, 16 respectively. T3 is preempted by T1 and T2 at time 4 and time 8 and resume at time 7 and time 11.
Input

All the input numbers are positive integers, < 500000, separated by a space or new line. The first line is the number of task sets. Then, the task sets are listed set by set. Each task set is listed by a line of the number of tasks, <= 100, and lines of task execution time and period pairs, execution time < period. The periods are harmonic, not sorted, and are different in a task set.
Output

For each task set, find and print out the finish time of the task with the largest period using rate-monotonic scheduling, if schedulable; otherwise print out -1.
Sample Input

3
4
1 2
1 4
3 16
1 32
3
1 4
4 8
256 1024
3
1 2
3 8
1 4
Sample Output

16
1024
-1

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.05 09:28
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
POJ 1616 Harmonic Periods 笔记
实时系统上的可强占任务调度。给出每个任务的执行时间和周期(任务需在周期内完成)。周期越短优先级越高。求最大周期任务完成时间。
Harmonic function
转自:http://en.wikipedia.org/wiki/Harmonic_function This article is about harmonic functions in mathematics. For harmonic function in music, see diatonic functionality. In mathematics, mathemati
学习笔记--关于Spherical Harmonic
学习笔记--关于Spherical Harmonicxheartblue 2006-2-4关键字: Spherical Harmonic 球面调和函数 球面谐波函数 球形调和函数关联勒让德方程 勒让德多项式 正交多项式 正交函数系pdf : http://xreal.51.net/Download/SphericalHarmonic.pdfurl: http://xreal
Harmonic Number (II) LightOJ - 1245 (找规律)
I was trying to solve problem ‘1234 - Harmonic Number’, I wrote the following codelong long H( int n ) { long long res = 0; for( int i = 1; i <= n; i++ ) res = res + n / i; retu
LightOJ 1245 - Harmonic Number (II)(基础数论)
1245 - Harmonic Number (II) PDF (English) Statistics Forum Time Limit: 3 second(s) Memory Limit: 32 MB I was trying to solve problem '1234 - Harmonic Number',
总谐波失真(Total Harmonic Distortion,THD)
     总谐波失真(英文全称Total Harmonic Distortion,THD)是指用信号源输入时,输出信号比输入信号多出的额外谐波成分。功放工作时,由于电路不可避免的振荡或其他谐振产生的二次,三次谐波与实际输入信号叠加,在输出端输出的信号就不单纯是与输入信号完全相同的成分,而是包括了谐波成分的信号,这些多余出来的谐波成分与实际输入信号
Harmonic Number(暴力求解法)
题目链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=109329#problem/D; 题意:就是求解Harmonic Numbe值 即求    中的Hn; 分析:本题重在打表,因为个数很大(1亿),所以要分成小份进行存储(好不麻烦);剩下的就可以循环很少次数了。假设分成2500000分设为数组s,就是每隔40个数记录一次,接下
Posting only possible in periods 2011/01 and 2010/12 in company code 1000
今天在做PP练习时,需要在库存中增加一些物料的库存数量,我用MB1C,Movement Type为561,系统提示:Posting only possible in periods 2011/01 and 2010/12 in company code 1000原因是没有维护相应的会计期间导致运行TCODE:MMRV查看当前会计期间TCODE:MMPV 开启下一期间(当前期间是2011/01,因此period维护02)点运行后系统提示以下画面,表示开关期间成功
Codeforces 351D:Jeff and Removing Periods
D. Jeff and Removing Periods time limit per test 3 seconds memory limit per test 256 megabytes input standard input output standard output Cosider a sequence, consisting
CF 351D - Jeff and Removing Periods(离线 + 树状数组)
题目链接:Click here~~ 题意: 给一个长度为 n 的序列,Q 次询问,每次查询 [l,r] 中有多少个不同的数字,且是否存在一个数字,其出现的位置成等差数列。 解题思路: 接上篇继续刷离线查询题目。昨天想了1天,今天早上在床上想出思路了,2333333。 对于区间中不同数字的个数,可以用类似上篇的做法,c[j] 维护 [j,i] 中不同数字的个数,那么