资源描述：
《用自动机建立操作系统模型.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、用自动机建立操作系统模型ao这篇文章用自动机理论的一些概念建立在一个多道程序的操作系统中进程间如何交互作用的模型。为了得到所需的模型采取的方法是,引进状态集合的结构和自动机转换规则。操作系统的一些概念,如限定性和死锁等,用自动机理论的术语加以形式化并进行细致的分析.为.读者方便文中提供了许多例子本文预备知识涉及有限自动机概念.(原提要)员班子写成的包含有许多概念的大型复杂的.91引论。程序这就使得对它们进行排错几乎是不可,。本文使用自动机理论的一些概念建立能的确保操作系统正确性的形式的或自动、。了程序该程序所定义
2、的进程以及在一个多化的工具是极其需要的其,道程序操作系统中这些进程之间交互作用的次操作系统明显地利用了并行处。,,方式的模型这个模型的着重点在于它把两理以便充分利用系统的资源并进而希望:。,个熟悉的领域框图形式的程序和自动机联提高作业完成的速度不幸的是并行处理。。系起来这里将该模型应用于个别程序和程是造成操作系统复杂性的主要因素有三个序、。,系统的正确性分析性能评价以及熟悉的方面的问题必须加以处理首先独立的任。。,操作系统术语的形式定义务必须避免彼此干扰其次彼此通讯的进“”。操作系统与通常的计算机程序之差程必须以
3、有规则的途径来进行通讯这两方。,,别有以下几方面首先操作系统是由程序面通常称为限定性它要求个别进程的行为..,2(aJ,mondTYeh编,1976我们的结果可进一步深入理解计算R)第十二章,、:理论中传统研究的各种概念(例如语言生张茂绩饶生忠校}。成器中上下文的作用)的性质3.计算理论的背景是解决我们尚未解参考文献,`..,。Ehrenfeueht气左GRozenberg决的问题的最好的准备“TheualityofEOLLanguagesand,Eq毫无疑问研究该课题的新高潮已经到,es”,Codingsof0
4、1LanguagInternational,。来并且已经完成了大量的有益的工作oouter“teaes,.本fCmpMhmti4(1974)pp95,.文所提到的都是近五年来的成果而且多数一104...,,-HermanGTGRozenergDeve。占b是近两年来的成果作者希望以目前的速度ontast:sananguaes,ortlPmelSymdLgNh,一oanusngCo二stera继续前进并且使形式语言理论和发育生物HlldPblihiAmdm.。1974学相辅相成地发展VonNeumann,J.The
5、oroe一er-了fSlfRp[王翰虎译自《AppliedCo二potation,·oduei皿9AutomataUniversityofIllinoeor:nass,esn,oen,..,.ThyAlyiDigMdlig>15PressUrbax一a1111966。?还?以后几第栈是一个有界或无界的带节将,,。三死锁问题它是为得到限定性而引进的提供适合于建立程序模型的Q的结构。.,P如何从“”互锁规则的付产品从直观上说当若干进输入和输出外部世界接,。“”?程互斥地和永久地互锁时就会出现死锁收信岂而又怎样向外部世
6、界发送信息,,.1丈第二节从顺序进程一般概念开始顺序在有待建立的模型中进程将通获得新的,进程是关于其状态集合和转换规则不加限制状态分量来接收输入并将通过释放分量来。。的一种自动机以下各节提出了把顺序进程产生输出。.,同程序联系起来的概念这些概念涉及把状初始和最后状态必要时在没有正式,,态构造成为对应于程序存储单元分量的直的说明之下将假定Q的子集Q(初始的)、,F。积进程的同态以及把状态变化信息压入和Q(最后的)的存在性。用作转换标号的原始操作以归纳断言和顺.。;3状态图序校验的应用结束单进程的讨论12节介绍了异步
7、操作的并行处理系。第一进程以释一图的个可解为个有向图。,,。统讨论从完全独立的进程开始使用它们顶点对应于状态而边对应于转换术语的“”,。,来定义限定性然后在不丧失限定性的条选择是任意的当想要有动态解释时这里,。,,件下讨论了允许进程间的相关性问题这将使用进程的术语而且在静态意义下将“”,“”。,个模型用来定义诸如临界区资源使用图的术语于是一个进程是遍历一个“”。,,和互斥这样一些术语最后简短地讨状态图的实体而且一个状态图就象一个程,,。论了在系统正确性实现互斥以及性能估价序它定义了一个进程可以做些什么。方面的一些
8、应用;.4边的标号由于有了关于并行处理的形式模型最新aer,,的和(见B[1])程序的程过这全面的综述在此由计算机定义进通执行些。,。不再赘述对于其它模型感兴趣的读者请程序中的指令而改变状态为此理所当然的。Bear的精彩的综述的是要对状态图的边用表征所包含指令的符号参看本文末尾文献。,目录仅仅包含同这里介绍的模型直接有关的标记来加上标号因此设L是原始操作的。,R的定义扩充
