APP下载
登录
RMS
RMS目录[隐藏]
RMS（Rate-Monotonic Scheduling）调度算法
有效值（root mean square）
Rights Management Services
Record Management System
Richard Matthew Stallman
[编辑本段]RMS（Rate-Monotonic Scheduling）调度算法
任务按单调速率优先级分配（RMPA）的调度算法，称为单调速率调度（RMS）。RMPA是指任务的优先级按任务周期T来分配。它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级，周期长的任务优先级低。
不考虑n=1的情况。RMS是单处理器下的最优静态调度算法。1973年Liu和Layland发表的这篇文章的前半部分首次提出了RM调度算法在静态调度中的最优性.它的一个特点是可通过对系统资源利用率的计算来进行任务可调度性分析, 算法简单、有效, 便于实现。不仅如此,他们还把系统的利用系数(utilization factor)和系统可调度性联系起来, 推导出用RM调度所能达到的最小系统利用率公式. 同时,这篇论文中透露出来的证明思想和方法也被人们所效仿. 下面就让我们来看看这篇文章中关于RM调度算法的重要结论。
任何一个结论都有一个模型假设, 让我们先列出这里的假设:
(A1) 所有的任务请求都是周期性的,必须在限定的时限内完成；
(A2) 任务的作业必须在该任务的下一个作业发生之前完成, 这样避免了考虑队列问题; 在这里, 我们对任务和作业不作特别的区分, 因为一个任务请求就是一个作业。
(A3) 任务之间都是独立的,每个任务的请求不依赖于其他任务请求的开始或完成；
(A4) 每个任务的运行时间是不变的,这里任务的运行时间是指处理器在无中断情况下用于处理该任务的时间；
(A5) 所有的非周期性任务都在特殊的情况下运行,比如系统初始化或系统非正常紧急处理程序。
(A6) 其它一些假设, 比如, 单处理器, 可抢占调度, 任务切换的时间忽略不计等等。
RMS算法：
(1) 任务T i (P i, Ci, D i) 模型: 周期为P i,计算时间为Ci, 时限D i 为周期终点。任务在周期起点释放, 高优先级任务可抢占低优先级任务的执行。
(2) 优先级分配方法: 静态固定分配。优先级与周期成反比, 周期越短优先级越高。
(3) 可调度性分析: 如果任务集满足下式, 则该任务集可调度。
定理1：n个独立的周期任务可以被RMPA调度，如果U<=n(2^(1/n)-1)。
一个任务的响应时间(response time)是指一个任务请求,这个任务实际完成的时间跨度. 在静态调度中, 任务的临界时刻(critical instant)这个概念被首先提出来.它被定义为一个特定的时刻, 如果在这个时刻有这个任务的请求, 那么这个任务就会需要最大的响应时间. 由此得出
定理1: 一个任务的临界时间就是比这个任务优先级高的所有任务同时发出请求的时刻.
证明: 由于一个任务的响应时间是它自己的负载时间加上被其它优先级高的任务所打断的时间.由于自己的负载时间是固定的, 我们考虑在什么时候任一高优先级的任务会有最长的打断时间. 显然,只有当这一高优先级的任务与该任务同时请求处理时, 才能可能产生最大的打断时间.
定理1的价值在于它找到了一个证明一个调度算法能否调度任一任务集充分必要条件, 那就是所有任务同时请求执行的时的情况下每个任务仍能满足各自的期限, 那么这个任务集就可以被这个调度算法调度.
有了这个推论, 我们就可以证明RM调度的最优性了.
定理2: 如果一个任务集能够被静态调度, 那么RMS算法就能够调度这个任务集. 从这个意义上说, RMS是最优的静态调度算法.
这个定理的证明方法就是有名的交换法. 证明思路如下:
假设一个任务集S采用其他静态优先级算法可以调度,那么总有这样两个优先级相邻的任务i和j,有Ti>Tj,而Pi≤Pj.把Ti和Tj的优先级Pi和Pj互换,明显可以看出这时S仍然可以调度, 因为在所有任务同时请求的情况下,交换这两个任务不会影响其它任务的完成时间, 同时这两个任务都可以在各自期限内完成.按照这样的方法,其他任何静态优先级调度最终都可以转换成RM调度.
RMS已被证明是静态最优调度算法, 开销小, 灵活性好,是实时调度的基础性理论。即使系统瞬时过载, 也完全可预测哪些任务丢失时限。缺点是处理机利用率较低, 最坏的情况下，当n→∞时, 不超过ln2(≈ 70%)。另外, RMS是充分但非必要条件。而在一般情况下，对于随机的任务集大约只有88%.70%或者88%的处理器利用率对于许多实时应用来说是一个严重的限制，动态调度算法如最早截止期最先（earliest deadlinefirst，EDF）或者最少空闲时间最先（least laxity first，LLF）已经被证明是最优的，并且能够实现100%的处理器利用率.
具有资源同步约束的RMS调度
当实时任务间共享资源时, 可能出现低优先级任务不可预测地阻塞高优先级任务执行的情况,叫优先级倒置。这时RMS 算法不能保证任务集的调度, 必须使用有关协议控制优先级的倒置时间。常用的协议有优先级顶级协议和堆资源协议,使用这些协议可使优先级的倒置时间最多为一个资源临界段的执行时间, 并且不会发生死锁。
基于RMS 的非周期任务的调度
实时系统中的非周期任务可采用延迟服务器算法或随机服务器算法进行调度。它们的最大特点是可在周期任务的实时调度环境下处理随机请求。两者的基本思想是将非周期任务转化成周期任务,再利用RMS算法进行调度。前者用一个或几个专用的周期任务执行所有非周期任务,这种周期任务叫非周期任务服务器。根据周期大小,服务器有固定优先级, 服务器的执行时间被称为预算, 它在每个服务器周期Ts的起点补充。只要服务器有充足的预算, 就可在其周期内为非周期任务服务。该算法实现简单, 但可调度性分析较难, 有时会出现抖动,可能发生一个非周期任务在相邻两个服务器周期中连续执行2倍预算的现象, 与RMS理论不符,需要适当修改RMS算法。随机服务器算法与延迟服务器算法相似, 但预算不是在每个周期起点补充,而是在预算消耗Ts时间之后再补充。该算法与RMS分析算法一致, 但实现复杂。
[编辑本段]有效值（root mean square）
RMS值实际就是有效值,就是一组统计数据的平方的平均值的平方根。
RMS＝（X1平方＋X2平方＋......＋Xn平方）/n 的1/2次方。
在直流（DC）电路中，电压或电流的定义很简单，但在交流（AC）电路中，其定义就较为复杂，有多种定义方式。均方根（rms）指的是定义AC波的有效电压或电流的一种最普遍的数学方法。
要得出rms值需要对表示AC波形的函数执行三个数学操作：
（1）计算波形函数（一般是正弦波）的平方值。
（2）对第一步得到的函数求时间平均值。
（3）求第二步得到的函数的平方根。
在一个阻抗由纯电阻组成的电路中，AC波的rms值通常称作有效值或DC等价值。比如，一个100V rms的AC源连接着一个电阻器，并且其电流产生50W热量，那么对于100V连接着这个电阻器的电源来说也将产生50W的热量。
对正弦波来说，rms值是峰值的0.707倍，或者是峰-峰值的0.354倍。家用电压是以rms来表示的。所谓的“117V”的交流电，其峰值（pk）约为165V，峰-峰值（pk-pk）约为330V。
[编辑本段]Rights Management Services
Microsoft Windows Rights Management 服务 (RMS)，是一种与应用程序协作来保护数字内容（不论其何去何从）的安全技术，专为那些需要保护敏感的 Web 内容、文档和电子邮件的用户而设计。用户可以严格规定哪些用户可以打开、读取、修改和重新分发特定内容。组织可以创建权限策略模板，以实施用户应用于内容的策略。
[编辑本段]Record Management System
是MIDP中一个非常重要的子系统.RMS是首先在MIDP1.0中提出的，它所在的包是javax.microedition.rms，在这个包里面总共包括四个接口、一个类和五个异常
Remote Monitoring System
远程监控系统
[编辑本段]Richard Matthew Stallman
（理查德·马修·斯托曼）
理查德·马修·斯托曼
理查德·马修·斯托曼（Richard Matthew Stallman, RMS，生于1953年），自由软件运动的精神领袖、GNU计划以及自由软件基金会（Free Software Foundation）的创立者、著名黑客。他最大的影响是为自由软件运动竖立了道德、政治以及法律框架。他被许多人誉为当今自由软件的斗士、伟大的理想主义者，但同时也有人批评他过于固执、观点落伍。
斯托曼1953年出生于美国纽约曼哈顿地区，1971年进入哈佛大学学习，同年受聘于麻省理工学院人工智能实验室（AI Laboratory），成为一名职业黑客。
在AI实验室工作期间，斯托曼开发了多种今后影响深远的软件，其中最著名的就是Emacs。斯托曼在AI是一名典型的黑客，是整个黑客文化的一份子。
然而进入八十年代后，黑客社群在软件工业商业化的强大压力下日渐土崩瓦解，甚至连AI实验室的许多黑客也组成了Symbolic公司，试图以专利软件来取代实验室中黑客文化的产物－－免费可自由流通的软件。
斯托曼对此感到气愤与无奈。在对Symbolic进行了一段时间的抗争后，他于1985年发表了著名的GNU宣言(GNU Manifesto)，正式宣布要开始进行一项宏伟的计划：创造一套完全自由免费，兼容于Unix的操作系统GNU（GNU's Not Unix!），目的是打破大型网络供应商的垄断。现今，GNU 已成为全球最受欢迎的自由软件许可证！之后他又建立了自由软件基金会来协助该划。
他于1989年与一群律师起草了广为使用的GNU通用公共协议证书（GNU General Public License, GNU GPL），创造性地提出了“反版权”（或“版权属左”，或“开权”，copyleft）的概念。 同时，GNU计划中除了最关键的Hurd操作系统内核之外，其他绝大多数软件已经完成。
1991年芬兰大学生李纳斯（Linus Torvalds）在GPL条例下发布他自己创作的Linux操作系统内核，至此GNU计划正式完成，操作系统被命名为GNU/Linux（或简称Linux）。
自 90 年代开始，斯托曼开始积极参加政治运动，到各间大学和场合主讲，宣扬推行自由软件的讯息，令他无论在电脑界或学术界都享负盛名！
斯托曼是一名坚定的自由软件运动倡导者，与其他提倡开放源代码的人不同，斯托曼并不是从软件质量的角度而是从道德的角度来看待自由软件。他认为使用专利软件是非常不道德的事，只有附带了源代码的程序才是符合其道德标准的。对此许多人表示异议，并也因此有了自由软件运动与开源软件运动之分
代表作︰
— 创立自由软件 GNU
— Emacs 文字编辑器
— GCC编译器
— GDB调试器
斯托曼还曾获得过多项荣誉
1990年度麦克阿瑟奖（MacArthur Fellowship）
1991年度美国计算机协会（Association for Computing Machinery）颁发的Grace Hopper Award以表彰他所开发的的Emacs文字编辑器
1996年获颁瑞典皇家技术学院荣誉博士学位
1998年度电子前线基金会（Electronic Frontier Foundation）先锋奖（Pioneer Award）
1999年Yuri Rubinsky纪念奖
2001年获颁格拉斯哥大学荣誉博士学位
2001年武田研究奖励赏（武田研究奨励赏）
2002年成为美国国家工程院院士
2003年获颁布鲁塞尔大学荣誉博士学位
Richard Stallman与中国“龙芯”
有开源社区精神领袖之称的Richard Stallman在多个场合呼吁开源社区大力支持基于龙芯电脑的软件开发，主要原因是在OLPC项目使用微软的操作系统，走商业化道路后，龙芯是目前唯一坚持开源的电脑CPU。
RMS(记录管理系统)是MIDP的一个子系统.为开发者提供了数据持久性存储的解决方案,应用程序的数据可以在MIDlet多次调用之后依然保持不变,即使重新启动设备或者更换电池也不会造成数据丢失。
RMS（Rate-Monotonic Scheduling）调度算法
有效值（root mean square）
Rights Management Services
Record Management System
Richard Matthew Stallman
[编辑本段]RMS（Rate-Monotonic Scheduling）调度算法
任务按单调速率优先级分配（RMPA）的调度算法，称为单调速率调度（RMS）。RMPA是指任务的优先级按任务周期T来分配。它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级，周期长的任务优先级低。
不考虑n=1的情况。RMS是单处理器下的最优静态调度算法。1973年Liu和Layland发表的这篇文章的前半部分首次提出了RM调度算法在静态调度中的最优性.它的一个特点是可通过对系统资源利用率的计算来进行任务可调度性分析, 算法简单、有效, 便于实现。不仅如此,他们还把系统的利用系数(utilization factor)和系统可调度性联系起来, 推导出用RM调度所能达到的最小系统利用率公式. 同时,这篇论文中透露出来的证明思想和方法也被人们所效仿. 下面就让我们来看看这篇文章中关于RM调度算法的重要结论。
任何一个结论都有一个模型假设, 让我们先列出这里的假设:
(A1) 所有的任务请求都是周期性的,必须在限定的时限内完成；
(A2) 任务的作业必须在该任务的下一个作业发生之前完成, 这样避免了考虑队列问题; 在这里, 我们对任务和作业不作特别的区分, 因为一个任务请求就是一个作业。
(A3) 任务之间都是独立的,每个任务的请求不依赖于其他任务请求的开始或完成；
(A4) 每个任务的运行时间是不变的,这里任务的运行时间是指处理器在无中断情况下用于处理该任务的时间；
(A5) 所有的非周期性任务都在特殊的情况下运行,比如系统初始化或系统非正常紧急处理程序。
(A6) 其它一些假设, 比如, 单处理器, 可抢占调度, 任务切换的时间忽略不计等等。
RMS算法：
(1) 任务T i (P i, Ci, D i) 模型: 周期为P i,计算时间为Ci, 时限D i 为周期终点。任务在周期起点释放, 高优先级任务可抢占低优先级任务的执行。
(2) 优先级分配方法: 静态固定分配。优先级与周期成反比, 周期越短优先级越高。
(3) 可调度性分析: 如果任务集满足下式, 则该任务集可调度。
定理1：n个独立的周期任务可以被RMPA调度，如果U<=n(2^(1/n)-1)。
一个任务的响应时间(response time)是指一个任务请求,这个任务实际完成的时间跨度. 在静态调度中, 任务的临界时刻(critical instant)这个概念被首先提出来.它被定义为一个特定的时刻, 如果在这个时刻有这个任务的请求, 那么这个任务就会需要最大的响应时间. 由此得出
定理1: 一个任务的临界时间就是比这个任务优先级高的所有任务同时发出请求的时刻.
证明: 由于一个任务的响应时间是它自己的负载时间加上被其它优先级高的任务所打断的时间.由于自己的负载时间是固定的, 我们考虑在什么时候任一高优先级的任务会有最长的打断时间. 显然,只有当这一高优先级的任务与该任务同时请求处理时, 才能可能产生最大的打断时间.
定理1的价值在于它找到了一个证明一个调度算法能否调度任一任务集充分必要条件, 那就是所有任务同时请求执行的时的情况下每个任务仍能满足各自的期限, 那么这个任务集就可以被这个调度算法调度.
有了这个推论, 我们就可以证明RM调度的最优性了.
定理2: 如果一个任务集能够被静态调度, 那么RMS算法就能够调度这个任务集. 从这个意义上说, RMS是最优的静态调度算法.
这个定理的证明方法就是有名的交换法. 证明思路如下:
假设一个任务集S采用其他静态优先级算法可以调度,那么总有这样两个优先级相邻的任务i和j,有Ti>Tj,而Pi≤Pj.把Ti和Tj的优先级Pi和Pj互换,明显可以看出这时S仍然可以调度, 因为在所有任务同时请求的情况下,交换这两个任务不会影响其它任务的完成时间, 同时这两个任务都可以在各自期限内完成.按照这样的方法,其他任何静态优先级调度最终都可以转换成RM调度.
RMS已被证明是静态最优调度算法, 开销小, 灵活性好,是实时调度的基础性理论。即使系统瞬时过载, 也完全可预测哪些任务丢失时限。缺点是处理机利用率较低, 最坏的情况下，当n→∞时, 不超过ln2(≈ 70%)。另外, RMS是充分但非必要条件。而在一般情况下，对于随机的任务集大约只有88%.70%或者88%的处理器利用率对于许多实时应用来说是一个严重的限制，动态调度算法如最早截止期最先（earliest deadlinefirst，EDF）或者最少空闲时间最先（least laxity first，LLF）已经被证明是最优的，并且能够实现100%的处理器利用率.
具有资源同步约束的RMS调度
当实时任务间共享资源时, 可能出现低优先级任务不可预测地阻塞高优先级任务执行的情况,叫优先级倒置。这时RMS 算法不能保证任务集的调度, 必须使用有关协议控制优先级的倒置时间。常用的协议有优先级顶级协议和堆资源协议,使用这些协议可使优先级的倒置时间最多为一个资源临界段的执行时间, 并且不会发生死锁。
基于RMS 的非周期任务的调度
实时系统中的非周期任务可采用延迟服务器算法或随机服务器算法进行调度。它们的最大特点是可在周期任务的实时调度环境下处理随机请求。两者的基本思想是将非周期任务转化成周期任务,再利用RMS算法进行调度。前者用一个或几个专用的周期任务执行所有非周期任务,这种周期任务叫非周期任务服务器。根据周期大小,服务器有固定优先级, 服务器的执行时间被称为预算, 它在每个服务器周期Ts的起点补充。只要服务器有充足的预算, 就可在其周期内为非周期任务服务。该算法实现简单, 但可调度性分析较难, 有时会出现抖动,可能发生一个非周期任务在相邻两个服务器周期中连续执行2倍预算的现象, 与RMS理论不符,需要适当修改RMS算法。随机服务器算法与延迟服务器算法相似, 但预算不是在每个周期起点补充,而是在预算消耗Ts时间之后再补充。该算法与RMS分析算法一致, 但实现复杂。
[编辑本段]有效值（root mean square）
RMS值实际就是有效值,就是一组统计数据的平方的平均值的平方根。
RMS＝（X1平方＋X2平方＋......＋Xn平方）/n 的1/2次方。
在直流（DC）电路中，电压或电流的定义很简单，但在交流（AC）电路中，其定义就较为复杂，有多种定义方式。均方根（rms）指的是定义AC波的有效电压或电流的一种最普遍的数学方法。
要得出rms值需要对表示AC波形的函数执行三个数学操作：
（1）计算波形函数（一般是正弦波）的平方值。
（2）对第一步得到的函数求时间平均值。
（3）求第二步得到的函数的平方根。
在一个阻抗由纯电阻组成的电路中，AC波的rms值通常称作有效值或DC等价值。比如，一个100V rms的AC源连接着一个电阻器，并且其电流产生50W热量，那么对于100V连接着这个电阻器的电源来说也将产生50W的热量。
对正弦波来说，rms值是峰值的0.707倍，或者是峰-峰值的0.354倍。家用电压是以rms来表示的。所谓的“117V”的交流电，其峰值（pk）约为165V，峰-峰值（pk-pk）约为330V。
[编辑本段]Rights Management Services
Microsoft Windows Rights Management 服务 (RMS)，是一种与应用程序协作来保护数字内容（不论其何去何从）的安全技术，专为那些需要保护敏感的 Web 内容、文档和电子邮件的用户而设计。用户可以严格规定哪些用户可以打开、读取、修改和重新分发特定内容。组织可以创建权限策略模板，以实施用户应用于内容的策略。
[编辑本段]Record Management System
是MIDP中一个非常重要的子系统.RMS是首先在MIDP1.0中提出的，它所在的包是javax.microedition.rms，在这个包里面总共包括四个接口、一个类和五个异常
Remote Monitoring System
远程监控系统
[编辑本段]Richard Matthew Stallman
（理查德·马修·斯托曼）
理查德·马修·斯托曼
理查德·马修·斯托曼（Richard Matthew Stallman, RMS，生于1953年），自由软件运动的精神领袖、GNU计划以及自由软件基金会（Free Software Foundation）的创立者、著名黑客。他最大的影响是为自由软件运动竖立了道德、政治以及法律框架。他被许多人誉为当今自由软件的斗士、伟大的理想主义者，但同时也有人批评他过于固执、观点落伍。
斯托曼1953年出生于美国纽约曼哈顿地区，1971年进入哈佛大学学习，同年受聘于麻省理工学院人工智能实验室（AI Laboratory），成为一名职业黑客。
在AI实验室工作期间，斯托曼开发了多种今后影响深远的软件，其中最著名的就是Emacs。斯托曼在AI是一名典型的黑客，是整个黑客文化的一份子。
然而进入八十年代后，黑客社群在软件工业商业化的强大压力下日渐土崩瓦解，甚至连AI实验室的许多黑客也组成了Symbolic公司，试图以专利软件来取代实验室中黑客文化的产物－－免费可自由流通的软件。
斯托曼对此感到气愤与无奈。在对Symbolic进行了一段时间的抗争后，他于1985年发表了著名的GNU宣言(GNU Manifesto)，正式宣布要开始进行一项宏伟的计划：创造一套完全自由免费，兼容于Unix的操作系统GNU（GNU's Not Unix!），目的是打破大型网络供应商的垄断。现今，GNU 已成为全球最受欢迎的自由软件许可证！之后他又建立了自由软件基金会来协助该划。
他于1989年与一群律师起草了广为使用的GNU通用公共协议证书（GNU General Public License, GNU GPL），创造性地提出了“反版权”（或“版权属左”，或“开权”，copyleft）的概念。 同时，GNU计划中除了最关键的Hurd操作系统内核之外，其他绝大多数软件已经完成。
1991年芬兰大学生李纳斯（Linus Torvalds）在GPL条例下发布他自己创作的Linux操作系统内核，至此GNU计划正式完成，操作系统被命名为GNU/Linux（或简称Linux）。
自 90 年代开始，斯托曼开始积极参加政治运动，到各间大学和场合主讲，宣扬推行自由软件的讯息，令他无论在电脑界或学术界都享负盛名！
斯托曼是一名坚定的自由软件运动倡导者，与其他提倡开放源代码的人不同，斯托曼并不是从软件质量的角度而是从道德的角度来看待自由软件。他认为使用专利软件是非常不道德的事，只有附带了源代码的程序才是符合其道德标准的。对此许多人表示异议，并也因此有了自由软件运动与开源软件运动之分
代表作︰
— 创立自由软件 GNU
— Emacs 文字编辑器
— GCC编译器
— GDB调试器
斯托曼还曾获得过多项荣誉
1990年度麦克阿瑟奖（MacArthur Fellowship）
1991年度美国计算机协会（Association for Computing Machinery）颁发的Grace Hopper Award以表彰他所开发的的Emacs文字编辑器
1996年获颁瑞典皇家技术学院荣誉博士学位
1998年度电子前线基金会（Electronic Frontier Foundation）先锋奖（Pioneer Award）
1999年Yuri Rubinsky纪念奖
2001年获颁格拉斯哥大学荣誉博士学位
2001年武田研究奖励赏（武田研究奨励赏）
2002年成为美国国家工程院院士
2003年获颁布鲁塞尔大学荣誉博士学位
Richard Stallman与中国“龙芯”
有开源社区精神领袖之称的Richard Stallman在多个场合呼吁开源社区大力支持基于龙芯电脑的软件开发，主要原因是在OLPC项目使用微软的操作系统，走商业化道路后，龙芯是目前唯一坚持开源的电脑CPU。
RMS(记录管理系统)是MIDP的一个子系统.为开发者提供了数据持久性存储的解决方案,应用程序的数据可以在MIDlet多次调用之后依然保持不变,即使重新启动设备或者更换电池也不会造成数据丢失。
相关数据
被浏览次数
编辑次数
