操作系统应用设计实验指导1

计算机类实验系列自编教材操作系统应用设计实验指导张莉编武汉大学珞珈学院计算机科学系二0一三年四月操作系统应用设计实验指导前言操作系统是计算机系统的核心，《操作系统》课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。操作系统应用设计是操作系统课程的重要组成部分，属于学科基础实验范畴。作为与相关教学内容配合的实践性教学环节，应在操作系统理论课教学过程中开设。操作系统是计算机科学与技术专业、软件工程等专业必修的专业基础课程，其配套实验课操作系统应用设计的作用是：理解操作系统的设计和实现思路，掌握典型算法。学生应具有高级语言编程能力、具有数据结构等基础知识。操作系统应用设计实验指导共有六个实验项目。其中，实验一是处理器调度实验；实验二是银行家算法模拟；实验三是分区存储管理算法模拟；实验四是分页存储管理算法模拟；实验五是请求页式存储管理算法模拟；实验六是磁盘存储空间的分配和回收。这本操作系统应用设计实验指导书是在近几年来的教学实验基础上编写的。参考了有关操作系统实验的实验指导，在此向有关编者表示感谢，同时本指导书仅供内部学生学习使用。由于时间仓促，编者水平有限，不足之处在所难免，恳请读者批评指正。编者张莉二0一三年四月目录实验一处理器调度实验........................................................................1实验二银行家算法模拟........................................................................5实验三分区存储管理算法模拟............................................................8实验四分页存储管理算法模拟..........................................................12实验五请求页式存储管理算法模拟..................................................14实验六磁盘存储空间的分配和回收..................................................16附录.......................................................................................................22一参考实例.......................................................................................................22二实验报告格式...............................................................................................22操作系统应用设计实验指导1实验一处理器调度实验实验内容：选择一个调度算法，实现处理器调度。实验目的：在采用多道程序设计的系统中，往往若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定那些进程优先占有处理器。本实习模拟在单处理器情况下的处理器调度，加深了解处理器调度的工作。实验题目：本实验有两题，可任选一题。第一题：设计一个按优先数调度算法实现处理器调度的程序。[提示]：(1)假定系统有5个进程，每个进程用一个PCB来代表。PCB的格式为：进程名、指针、要求运行时间、优先数、状态。进程名——P1~P5。指针——按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。要求运行时间——假设进程需要运行的单位时间数。优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态——假设两种状态，就绪，用R表示，和结束，用E表示。初始状态都为就绪状态。如图1.1所示。进程名指针要求运行时间优先数状态图1.1进程控制块结构(2)每次运行之前，为每个进程任意确定它的“优先数”和“要求运行时间”。(3)为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例如，当前轮到P2执行，则如下图1.2所示。操作系统应用设计实验指导2队首标志K2K1P1K2P2K3P3K4P4K5P50K4K5K3K12312415342RRRRRPCB1PCB2PCB3PCB4PCB5图1.2PCB队列(4)处理器总是选队首进程运行。采用动态改变优先数的办法，进程每运行1次，优先数减1，要求运行时间减1。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：优先数-1要求运行时间-1来模拟进程的一次运行。提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。(5)进程运行一次后，若要求运行时间不等于0，则将它加入队列（按优先数大小插入，且置队首标志）；否则，将状态改为“结束”（E），退出队列。(6)若就绪队列为空，结束，否则，重复上面（4）和（5）的步骤，直到所有进程都成为“结束”状态。(7)在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。(8)为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。第二题：设计一个按时间片轮转法实现处理器调度的程序。[提示]：(1)假定系统有5个进程，每个进程用一个PCB来代表。PCB的格式为：进程名、指针、要求运行时间、已运行时间、状态。进程名——Q1~Q5。指针——按创建时间把5个进程连成队列，用指针指出下一个进程PCB的首地址。要求运行时间——假设进程需要运行的单位时间数。已运行时间——假设进程已运行的单位时间，初始值为0。操作系统应用设计实验指导3状态——假设两种状态，就绪，用R表示，和结束，用E表示。初始状态都为就绪状态。如图1.3所示。进程名指针要求运行时间已运行时间状态图1.3进程控制块结构(2)每次运行之前，为每个进程任意确定它的“要求运行时间”。(3)把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如，当前轮到Q2执行，则如下图1.4所示。标志单元K2K1Q1K2Q2K3Q3K4Q4K5Q5K2K3K4K5K12312410000RRRRRPCB1PCB2PCB3PCB4PCB5图1.4PCB队列(4)处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。请同学注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“已运行时间+1”来表示进程已经运行满一个时间片。(5)进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。(6)若“就绪”状态的进程队列不为空，则重复上面的（4）和（5）的步骤，操作系统应用设计实验指导4直到所有的进程都成为“结束”状态。(7)在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。(8)为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。实验环境：不限制编程语言及环境，建议采用C语言。实验预习要求、实验条件、方法及步骤：1．理解本实验中调度算法的说明。2．根据调度算法的说明，画出相应的程序流程图。3．按照程序流程图，编程并实现。思考题：1．逻辑时间片该如何实现？2．如果不使用指针操作，是否也可以使用数组实现进程就绪队列的组织？操作系统应用设计实验指导5实验二银行家算法模拟实验内容：编写和调试一个简单的银行家算法程序。实验目的：银行家算法是避免死锁的一种重要方法，要求编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，理解和掌握安全序列、安全性算法，并体会和了解死锁和避免死锁的具体实施方法。实验题目：1．数据结构假设有M个进程N类资源，则有如下数据结构：MAX[M*N]M个进程对N类资源的最大需求量AVAILABLE[N]系统可用资源数ALLOCATION[M*N]M个进程已经得到N类资源的资源量NEED[M*N]M个进程还需要N类资源的资源量2．银行家算法设进程I提出请求Request[N]，则银行家算法按如下规则进行判断。(1)如果Request[N]=NEED[I，N]，则转(2)；否则，出错。(2)如果Request[N]=AVAILABLE，则转(3)；否则，出错。(3)系统试探分配资源，修改相关数据：AVAILABLE=AVAILABLE-REQUESTALLOCATION=ALLOCATION+REQUESTNEED=NEED-REQUEST(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。3．安全性检查(1)设置两个工作向量WORK=AVAILABLE；FINISH[M]=FALSE(2)从进程集合中找到一个满足下述条件的进程，FINISH[i]=FALSENEED=WORK如找到，执行(3)；否则，执行(4)(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。WORK=WORK+ALLOCATIONFINISH=TRUEGOTO2(4)如所有的进程Finish[M]=true，则表示安全；否则系统不安全。操作系统应用设计实验指导6实验环境：不限制编程语言及环境，建议采用C语言。实验预习要求、实验条件、方法及步骤：1．理解本实验中关于银行家算法的说明。2．参考图2.1所示流程图编写安全性算法。3．编写统一的输出格式。每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列。4．参考图2.2所示流程图编写银行家算法。5.编写主函数来循环调用银行家算法。思考题：1．安全序列是否唯一？为什么？2．在编程中遇到了哪些问题？你是如何解决的？3．在安全性算法中，为什么不用变量Available，而又定义一个临时变量work？Y所有finish都为true？输出安全序列NYN存在Finish[i]=false&&Need[i][j]Available[j]初始化Work和FinishFinish[i]=true，Work[j]=Work[j]+Allocation[j]所有进程都找完了？Y开始图2.1安全性算法流程图操作系统应用设计实验指导7结束否是申请失败。以上分配作废，恢复原来的分配状态：Available[j]=Available[j]+Request[i][j]Allocation[i][j]=Allocation[i][j]－Request[i][j]Need[i][j]=Need[i][j]+Request[i][j]NYNYRequest[i][j]Need[i][j]出错返回：return(error)R