操作系统原理A实验指导书.doc

淮海工学院操作系统原理A 实验指导书计算机工程学院实验1 进程调度实验目的进程是操作系统最重要的概念之一，进程调度是操作系统内核的重要功能，本实验要求用Java或C/C+语言编写一个进程调度模拟程序，至少使用先来先服务、短进程优先、最高优先权优先或时间片轮转法四种算法中的两种算法来实现进程调度。通过本实验可加深对进程调度算法的理解。实验环境Turbo C 2.0/3.0或VC+6.0或Java语言实验学时 4学时，必做实验。实验内容1、设计有5个进程并发执行的模拟调度程序，每个程序由一个PCB表示。2、模拟调度程序至少使用先来先服务、短进程优先、最高优先权优先或时间片轮转法四种算法中的两种算法来实现进程调度。3、程序执行中应能在屏幕上显示出各进程的状态变化，以便于观察调度的整个过程。实验说明1、优先级算法说明（1）PCB的结构：IdSpanUsedNeedSatusNext优先级算法中，设PCB的结构如右图所示，其中各数据项的含义如下：Id：进程标识符号，取值15。Prior：优先级，随机产生，范围15。Used：目前已占用的CPU时间数，初值为0；当该进程被调用执行时，每执行一个时间片，Used加1。Need：进程尚需的CPU时间数，初值表示该进程需要运行的总时间，取值范围为510。并随机产生，每运行一个时间片need减1；need为0则进程结束。Status：进程状态R（运行），J（就绪），F（完成）；初始时都处于就绪状态。Next：指向就绪队列中下一个进程的PCB的指针。（2）初始状态及就绪队列组织：5个进程初始都处于就绪状态，进程标识15，used初值都为0。各进程的优先级随机产生，范围15。处于就绪状态的进程，用队列加以组织，队列按优先级由高到低依次排列，队首指针设为head，队尾指针设为tail。（3）调度原则以及运行时间的处理：正在执行的进程每执行一个时间片，其优先级减1（允许优先级为负）。进程调度将在以下情况发生：当正在运行的程序其优先级小于就绪队列队首进程的优先级时。程序中进程的运行时间以逻辑时间片为单位。2、时间片轮转算法说明（1）PCB的结构（如下图所示）：轮转法中，设PCB的结构如右图所示，其中各数据项的含义如下：IdSpanUsedNeedSatusNextId：进程标识符号，取值15。Span：在某一轮中，分配给先运行进程的时间片数，取值13。Used：现运行进程在本轮执行过程已用的时间片数。Need：进程尚需的CPU时间数，初值表示该进程需要运行的总时间，取值范围510。并随机产生，每运行一个时间片need减1；need为0则进程结束。Status：进程状态R（运行），J（就绪），F（完成）；初始时所有进程处于就绪状态。Next：指向就绪队列中下一个进程的PCB的指针。（2）初始状态及就绪队列组织：Span、Used在每轮开始时赋初值，Used初值值为0，Span初值要求随机产生。（3）调度原则：当一个进程被调度程序执行时，每经过一个时间片，Need减1，Used加1，如果Need为0，表示该进程结束，如果Need不为0，并且Used小于本轮Span值，则该进程可继续运行，若Need不为0，且Used等于Span值，则该进程本轮运行时间已到，应调度下一个队首进程运行。实验步骤1、 理解本实验中有关调度算法的说明。2、 根据调度算法的说明，画出相应的程序流程图。3、 按照程序流程图，用Java/C/C+语言编程并实现。分析与思考1、 逻辑时间片该如何实现？2、 如果不使用指针操作，是否也可以使用数组实现进程就绪队列的组织？实验2 银行家算法实验目的银行家算法是操作系统中避免死锁的典型算法，用Java或C/C+语言编写一个银行家算法的模拟程序。通过本实验可以加深对银行家算法的步骤和相关数据结构用法的更好理解。实验环境Turbo C 2.0/3.0或VC+6.0或Java语言实验学时 4学时，必做实验。实验内容用Java或C/C+语言编写一个简单的银行家算法模拟程序，用银行家算法实现资源分配。程序能模拟多个进程共享多种资源的情形。进程可动态地申请资源，系统按各进程的申请动态地分配资源。要求程序具有显示和打印各进程的某一时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源数量以及为某进程分配资源后的有关资源数据的情况。实验说明实验中进程的数量、资源的种类以及每种资源的总量Totalj最好允许动态指定。初始时每个进程运行过程中的最大资源需求量Maxi,j和系统已分配给该进程的资源量Allocationi,j均为已知（这些数值可以在程序运行时动态输入），而算法中其他数据结构的值（包括Needi,j、Availablej）则需要由程序根据已知量的值计算产生。实验步骤1 认真理解好课本中银行家算法的实例。2 根据课本中银行家算法的描述，画出程序流程图。3 按照程序流程图，用Java或C/C+语言编程并实现。分析与思考1 要找出某一状态下所有可能的安全序列，程序该如何实现？2 银行家算法的局限性有哪些？实验3 虚拟存储器管理实验目的本实验模拟请求页式虚存管理系统的页面置换情况。实验程序能模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用OPT、FIFO和LRU算法进行页面置换的情形。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。并通过为该进程分配不同的实页数，来比较几种算法的稳定性。实验环境 Turbo C 2.0/3.0或VC+6.0或Java语言实验学时 4学时，必做实验实验内容本实验要求使用C/C+/Java语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用OPT、FIFO和LRU算法进行页面置换的情形。其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。实验说明1设计中虚页和实页的表示本设计利用C/C+/Java语言的结构体来描述虚页和实页的结构。pnpfntimepnpfnnext 虚页结构 实页结构在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是09。pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。pfn代表实页号，取值范围（0n-1）由动态指派的实页数n所决定。next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。2关于缺页次数的统计为计算命中率，需要统计在20次的虚页访问中命中的次数。为此，程序应设置一个计数器count，来统计虚页命中发生的次数。每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。最终命中率=count/20*100%。3LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。当LRU算法需要置换时，从所有已分配实页的虚页中找出time值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。4算法中实页的组织因为能分配的实页数n是在程序运行时由用户动态指派的，所以应使用链表组织动态产生的多个实页。为了调度算法实现的方便，可以考虑引入free和busy两个链表：free链表用于组织未分配出去的实页，首指针为free_head，初始时n个实页都处于free链表中；busy链表用于组织已分配出去的实页，首指针为busy_head，尾指针为busy_tail，初始值都为null。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若free链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若free链表为空，则说明n个实页已全部分配出去，此时应进行页面置换：对于FIFO算法要将busy_head 所指的实页从busy链表中取下，分配给该虚页，然后再将该实页插入到busy链表尾部；对于LRU算法则要从所有已分配实页的虚页中找出time值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。实验步骤1、理解好相关实验说明。2、根据实验说明，画出相应的程序流程图。3、按照程序流程图，用C/C+/Java语言编程并实现。分析与思考比较不同实页数下的页面命中率，FIFO和LRU两种置换算法的稳定性方面可以得出何种结论？ 实验4 文件管理实验目的文件系统是操作系统的一个重要组成部分，它向用户提供了对文件进行打开、读写、修改等操作的编程接口。本实验的目的就是熟悉与操作文件有关的函数调用，加深对文件管理的理解，为灵活处理文件及利用文件存储信息打下基础。实验环境Turbo C 2.0/3.0或VC+6.0或Java语言实验学时 4学时，选做实验实验内容本实验要求使用C/C+/Java语言编写一个学生成绩管理程序。要求学生成绩信息（包括学号、姓名、语文、数学、外语五个方面）通过键盘录入，并以文件的形式保存。程序能实现学生成绩文件的创建、打开、删除以及对文件中成绩记录的排序、添加、查询和修改操作。通过本实验可以熟悉与操作文件有关的函数调用，加深对文件管理的理解，为灵活处理文件及利用文件存储信息打下基础。实验步骤1 复习C/C+