2022年操作系统课程设计任务书 .pdf
.专业整理 . .学习帮手 . 2016-2017 学年第一学期操作系统课程设计任务书依照大纲和课程内容实践特点,结合操作系统、LINUX操作系统和嵌入式程序设计课程主要内容,课设的具体要求及任务如下:一、设计成果的要求课程设计应严格按照要求完成,在系统调试成功后, 需要提供操作系统课程设计报告,具体包括:(1) 设计目的(1) 设计内容(3)设计准备(理论、技术)(4)设计过程(设计思想、代码实现)(5)设计结果并分析(6)系统的结构、原理框图和模块等的详细说明(7) 用户使用说明书和参考资料(8)设计体会。注:1. (1)- (7)项可以打印,( 8)设计体会必须手写。 2. 报告的封皮、封底,采用给定的模板;报告的内容,在教师的指导下,独立完成,自主排版,不做统一要求。二、设计任务(每名同学选一题,独立完成)题目一 :进程与线程 Linux 进程与线程通讯1. 设计目的深刻理解线程和进程的概念, 掌握线程与进程在组成成分上的差别以及与其相适应的通讯方式和应用目标。Linux 系统的 fork()保持了 UNIX的经典语义,被创建的进程具有独立于父进程的地址空间,二者之间的通讯通常可采用pipe 机制, clone ()是 Linux系统特有的系统调用,可以通过参数确定父子进程之间是否共享存储空间等资源。在地址空间等资源共享的情况下,clone 实质相当于创建了一个轻进程或线程, 这是 clone 的通常用法。实际在 Linux 系统中,fork 以及用户级线程 pthread都是基于 clone 实现的。2. 设计内容以 Linux 系统进程和线程机制为背景, 掌握 fork()和 clone()系统调用的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 形式和功能以及与其相适应的高级通讯方式。由fork 派生的子进程之间通过pipe 通讯,由 clone 创建的线程之间通过共享内存通讯,对于后者需要考虑互斥问题。以生产者 - 消费者问题为例,通过实验理解fork ()和 clone ()两个系统调用的区别。 程序要求能够创建4 个进程或线程, 其中包括两个生产者和两个消费者,生产者和消费者之间能够传递数据。题目二 :处理机调度实时调度算法EDF和 RMS 1. 设计目的深入理解处理机调度算法, 了解硬实时概念, 掌握最早截止期优先调度算法EDF(Earliest Deadline First)和速率单调调度算法RMS (Rate Monotonic Scheduling )的可调度条件,并能在可调度情况下给出具体调度结果。2. 设计内容在 Linux 环境中采用用户级线程模拟实现EDF和 RMS 两种实时调度算法。 给定一组实时任务, 按照 EDF算法和 RMS 算法分别判断是否可调度。 在可调度的情况下,创建一组用户级线程, 分别代表各个实时任务, 并按算法所确定的调度次序安排各个线程运行, 运行时在终端上画出其Gantt 图。为避免图形绘制冲淡算法,Gantt 图可用字符表示。题目三 :存储管理动态异长存储资源分配算法1. 设计目的理解动态异长存储分区资源管理,掌握所需数据结构和管理程序, 了解各种存储分配算法的优点和缺点。2. 设计内容(1)分析 UNIX最先适应( First Fit,FF)存储分配算法,即map数据结构、存储分配函数 malloc() 和存储释放函数 mfree() ,找出与算法有关的成分。(2) 修改上述与算法有关的成分,使其分别体现BF (Best Fit,最佳适应)分配原则和 WF(Worst Fit ,最环适应 )分配原则。题目四:文件系统 Hash结构文件名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 1. 设计目的理解 Linux 文件系统的内部技术,掌握Linux 与文件有关的系统调用命令,并在此基础上建立面向随机检索的Hash结构文件。 Linux系统保持 UNIX文件系统的风格,提供流式文件界面,这种结构具有简洁灵活的特点,但并不直接支持记录式文件和关键字检索。本设计在Linux文件系统基础上,设计一组库函数,以提供对随机检索的支持。2. 设计内容(1)参考教程中 Hash文件构造算法,设计一组Hash文件函数,包括 Hash文件创建、打开、关闭、读、写等。(2)编写一个测试程序,通过记录保存、查找、删除等操作,检查上述Hash文件是否实现相关功能。题目五:设备管理 Linux 设备驱动程序安装1. 设计目的认识 Linux 设备的种类和设备工作方式, 理解设备驱动程序的工作原理, 掌握设备驱动程序的编写规范,能编写并安装简单的设备驱动程序。2. 设计内容在 Linux 系统中,编写一个简单的字符型设备驱动程序模块,设备具有独占特性,可执行读和写操作,相关系统调用为open,close,read,write。Open和 close 分别相当于请求和释放设备,read 和 write将内容保存在设备模块内的绥冲区中。设备模块可动态注册和卸载,并建立与之对应的特殊文件/dev/mydev 。题目六: Bootloader 引导程序设计与实现1. 设计目的认识 Bootloader的作用,深入理解 Bootloader 的编程思想。 以典型的引导程序 vivi为例,对 vivi程序的架构, vivi的启动流程,使用vivi完成系统引导程序的设计方法形成深刻的理解和认识。2. 设计内容名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 在嵌入式操作系统中, Bootloader 的作用与 PC机上的 BIOS类似,通过Bootloader 可以完成对系统板上的主要部件如CPU 、SDRAM、Flash 、串行口等进行初始化。当运行操作系统时,它会在操作系统内核运行之前运行,通过它,可以分配内存空间的映射, 从而将系统的软硬件环境带到一个合适的状态,以便为最终调用操作系统准备好正确的环境。本设计要求同学首先分析老师提供的vivi程序源代码,理清 vivi程序的架构分为哪几个模块,然后根据分析vivi程序的执行流程具体分为哪几个阶段,各阶段的主要任务是什么。最后要求同学编写内存映射初始化函数mem_map_init() 和内存管理单元初始化函数mmu_init() 。题目七:嵌入式linux下键盘驱动程序的设计与实现1. 设计目的通过完成对嵌入式linux下键盘驱动程序的设计和调试,掌握嵌入式 linux驱动程序的编写方法, 理解驱动程序动态模块的调试方法,掌握驱动程序添加到内核的流程。2. 设计内容设备驱动程序是操作系统内核和机器硬件之间的接口。设备驱动程序为应用程序屏蔽了硬件的细节, 故在应用程序看来, 硬件设备只是一个设备文件,应用程序可以像操作普通文件一样对硬件设备进行操作。本设计要求同学按照标准设备驱动程序的步骤编写驱动程序。由于键盘的设备驱动程序属于字符设备的驱动,因此,应当按照字符设备的规则编写。要求同学编写键盘设备文件file_operations结构,以及以下几个键盘操作函数: 键盘控制函数 Kbd_Ioctl()、关闭键盘设备函数Kbd_Close() 、打开键盘设备函数Kbd_Open()、获取键值函数 Kbd_Getkey() 、键盘服务子程序Kbd_ISR()、键盘设备的硬件初始化函数Setup_Kbd() 、注册键盘设备使用函数KbdInit()和卸载键盘设备函数 Kbd_Exit() 。题目八:首次适应算法的动态分区分配方式模拟1. 设计目的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 了解动态分区分配中使用的数据结构和分配算法,并进一步加深对动态分区存储管理方式及其实现过程的理解。2. 设计内容1)用 C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中,空闲分区通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲区低端的空间。2)假设初始状态如下,可用的内存空间为640KB ,并有下列的请求序列;作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 作业 7 申请 50KB 作业 6 释放 60 KB 请采用首次适应算法进行内存块的分配和回收,同时显示内存块分配和回收后空闲内存分区链的情况。题目九:循环首次适应算法的动态分区分配方式模拟1. 设计目的了解动态分区分配中使用的数据结构和分配算法,并进一步加深对动态分区存储管理方式及其实现过程的理解。2. 设计内容1)用 C语言实现采用循环首次适应算法的动态分区分配过程alloc()和回收过程 free()。其中,空闲分区通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲区低端的空间。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 2)假设初始状态如下,可用的内存空间为640KB ,并有下列的请求序列;作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 作业 7 申请 50KB 作业 6 释放 60 KB 请采用循环首次适应算法进行内存块的分配和回收,同时显示内存块分配和回收后空闲内存分区链的情况。题目十:最佳适应算法的动态分区分配方式模拟1设计目的了解动态分区分配中使用的数据结构和分配算法,并进一步加深对动态分区存储管理方式及其实现过程的理解。2设计内容1)用 C语言分别实现采用最佳适应算法的动态分区分配过程alloc()和回收过程 free()。其中,空闲分区通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲区低端的空间。2)假设初始状态如下,可用的内存空间为640KB ,并有下列的请求序列;作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 作业 7 申请 50KB 作业 6 释放 60 KB 请采用最佳适应算法进行内存块的分配和回收,同时显示内存块分配和回收后空闲内存分区链的情况。题目十一:最坏适应算法的动态分区分配方式模拟1设计目的了解动态分区分配中使用的数据结构和分配算法,并进一步加深对动态分区存储管理方式及其实现过程的理解。2设计内容1)用 C语言分别实现采用最坏适应算法的动态分区分配过程alloc()和回收过程 free()。其中,空闲分区通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲区低端的空间。2)假设初始状态如下,可用的内存空间为640KB ,并有下列的请求序列;作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200 KB 作业 3 释放 100 KB 作业 1 释放 130 KB 作业 5 申请 140 KB 作业 6 申请 60 KB 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 作业 7 申请 50KB 作业 6 释放 60 KB 请采用最坏适应算法进行内存块的分配和回收,同时显示内存块分配和回收后空闲内存分区链的情况。题目十二:进程调度模拟算法1设计目的通过算法的模拟加深对进程概念和进程调度过程的理解,掌握进程状态之间的切换,同时掌握进程调度算法的实现方法和技巧。2设计内容(1) 用 C语言来实现对 N个进程采用动态优先权优先算法的进程调度。(2) 每个用来标识进程的进程控制块PCB用结构来描述,包括以下字段:进程标识数 ID;进程优先数 PRIORITY ,并规定优先数越大的进程,其优先权越高;进程已占用的 CPU 时间 CPUTIME ;进程还需占用的CPU 时间 ALLTIME 。当进程运行完毕时, ALLTIME变为 0;进程的阻塞时间STARTBLOCK, 表示当进程再运行STARTBLOCK个时间片后,进程将进入阻塞状态;进程被阻塞的时间BLOCKTIME,表示已阻塞的进程再等待BLOCKTIME个时间片后,进程将转换成就绪状态;进程状态 STATE ;队列指针 NEXT ,用来将 PCB排成队列。(3) 优先数改变的原则:进程在就绪队列中呆一个时间片,优先数增加1;进程每运行一个时间片,优先数减3。(4) 假设在调度前,系统中有5 个进程,它们的初始状态如下:ID 0 1 2 3 4 PRIORITY 9 38 30 29 0 CPUTIME 0 0 0 0 0 ALLTIME 3 3 6 3 4 STARTBLOCK 2 -1 -1 -1 -1 BLOCKTIME 3 0 0 0 0 STATE READY READY READY READY READY (5) 为了清楚地观察进程的调度过程,程序应将每个时间片内的进程的情况显示出来,参照的具体格式如下:RUNNING PROG: i READY_QUEUE:-id1-id2 BLOCK_QUEUE:-id3-id4 = ID 0 1 2 3 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . PRIORITY P0 P1 P2 P3 P4 CPUTIME C0 C1 C2 C3 C4 ALLTIME A0 A1 A2 A3 A4 STARTBLOCK T0 T1 T2 T3 T4BLOCKTIME B0 B1 B2 B3 B4 STATE S0 S1 S2 S3 S4 题目十三:请求调页存储管理方式的模拟1 1设计目的通过对页面、 页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。2设计内容 1 )假设每个页面中可存放10 条指令,分配给作业的内存块数为4。 2 )用 c 语言模拟一个作业的执行过程,该作业共有320 条指令,即它的地址空间为 32 页,目前它的所有页都还未调入内存。在模拟过程中,如果所访问的指令已在内存, 则显示其物理地址, 并转下一条指令。 如果所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。如果4个内存块均已装入该作业, 则需进行页面置换, 最后显示其物理地址, 并转下一条指令。在所有 320 指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。 3 )置换算法:采用先进先出(FIFO)置换算法。提示: (1)通过随机数产生一个指令序列,共320 条指令。指令的地址按下述原则生成: 50%的指令是顺序执行的; 25%的指令是均匀分布在前地址部分; 25%的指令是均匀分布在后地址部分;具体的实施方法是: 在0 ,319的指令地址之间随机选取一起点m ; 顺序执行一条指令,即执行地址为m+1的指令; 在前地址 0 ,m+1中随机选取一条指令并执行,该指令的地址为m ; 顺序执行一条指令,其地址为m +1 的指令; 在后地址 m+2,319 中随机选取一条指令并执行; 重复上述步骤,直到执行320 次指令。(2)将指令序列变换为页地址流名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 设页面大小为 1K; 用户内存容量为 4 页到 32 页; 用户虚存容里为 32K。在用户虚存中,按每K存放 10 条指令排列虚存地址,即320 条指令在虚存中的存放方式为:第 0 条第 9 条指令为第 0 页(对应虚存地址为 0 ,9 );第 10 条第 19 条指令为第 1 页(对应虚存地址为 10 ,19 );第 310 条第 319 条指令为第 31 页(对应虚存地址为 310,319)。按以上方式,用户指令可组成32 页。(3)计算先进先出( FIFO)算法在不同内存容量下的命中率。其中,命中率 =1-页面失效次数 / 页地址流长度题目十四:请求调页存储管理方式的模拟2 1设计目的通过对页面、 页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。2设计内容 1 )假设每个页面中可存放10 条指令,分配给作业的内存块数为4。 2 )用 C语言模拟一个作业的执行过程,该作业共有320 条指令,即它的地址空间为 32 页,目前它的所有页都还未调入内存。在模拟过程中,如果所访问的指令已在内存, 则显示其物理地址, 并转下一条指令。 如果所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。如果4个内存块均已装入该作业, 则需进行页面置换, 最后显示其物理地址, 并转下一条指令。在所有 320 指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。 3 )置换算法:最近最久未使用(LRU )算法。提示: (1)通过随机数产生一个指令序列,共320 条指令。指令的地址按下述原则生成: 50%的指令是顺序执行的;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 25%的指令是均匀分布在前地址部分; 25%的指令是均匀分布在后地址部分;具体的实施方法是: 在0 ,319的指令地址之间随机选取一起点m ; 顺序执行一条指令,即执行地址为m+1的指令; 在前地址 0 ,m+1中随机选取一条指令并执行,该指令的地址为m ; 顺序执行一条指令,其地址为m +1 的指令; 在后地址 m+2,319 中随机选取一条指令并执行; 重复上述步骤,直到执行320 次指令。(2)将指令序列变换为页地址流 设页面大小为 1K; 用户内存容量为 4 页到 32 页; 用户虚存容里为 32K。在用户虚存中,按每K存放 10 条指令排列虚存地址,即320 条指令在虚存中的存放方式为:第 0 条第 9 条指令为第 0 页(对应虚存地址为 0 ,9 );第 10 条第 19 条指令为第 1 页(对应虚存地址为 10 ,19 );第 310 条第 319 条指令为第 31 页(对应虚存地址为 310,319)。按以上方式,用户指令可组成32 页。(3)计算最近最少使用( LRU )算法在不同内存容量下的命中率。其中,命中率 =1-页面失效次数 / 页地址流长度题目十五:请求调页存储管理方式的模拟3 1设计目的通过对页面、 页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。2设计内容 1 )假设每个页面中可存放10 条指令,分配给作业的内存块数为4。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 2 )用 C语言模拟一个作业的执行过程,该作业共有320 条指令,即它的地址空间为 32 页,目前它的所有页都还未调入内存。在模拟过程中,如果所访问的指令已在内存, 则显示其物理地址, 并转下一条指令。 如果所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。如果4个内存块均已装入该作业, 则需进行页面置换, 最后显示其物理地址, 并转下一条指令。在所有 320 指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。 3 )置换算法:最佳置换(OPT )算法。提示: (1)通过随机数产生一个指令序列,共320 条指令。指令的地址按下述原则生成: 50%的指令是顺序执行的; 25%的指令是均匀分布在前地址部分; 25%的指令是均匀分布在后地址部分;具体的实施方法是: 在0 ,319的指令地址之间随机选取一起点m ; 顺序执行一条指令,即执行地址为m+1的指令; 在前地址 0 ,m+1中随机选取一条指令并执行,该指令的地址为m ; 顺序执行一条指令,其地址为m +1 的指令; 在后地址 m+2,319 中随机选取一条指令并执行; 重复上述步骤,直到执行320 次指令。(2)将指令序列变换为页地址流 设页面大小为 1K; 用户内存容量为 4 页到 32 页; 用户虚存容里为 32K。在用户虚存中,按每K存放 10 条指令排列虚存地址,即320 条指令在虚存中的存放方式为:第 0 条第 9 条指令为第 0 页(对应虚存地址为 0 ,9 );第 10 条第 19 条指令为第 1 页(对应虚存地址为 10 ,19 );名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 第 310 条第 319 条指令为第 31 页(对应虚存地址为 310,319)。按以上方式,用户指令可组成32 页。(3)计算最佳置换( OPT )算法在不同内存容量下的命中率。其中,命中率 =1-页面失效次数 / 页地址流长度题目十六:请求调页存储管理方式的模拟4 1设计目的通过对页面、 页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。2设计内容 1 )假设每个页面中可存放10 条指令,分配给作业的内存块数为4。 2 )用 C语言模拟一个作业的执行过程,该作业共有320 条指令,即它的地址空间为 32 页,目前它的所有页都还未调入内存。在模拟过程中,如果所访问的指令已在内存, 则显示其物理地址, 并转下一条指令。 如果所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。如果4个内存块均已装入该作业, 则需进行页面置换, 最后显示其物理地址, 并转下一条指令。在所有 320 指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。 3 )置换算法:最少访问(LFU )算法。提示: (1)通过随机数产生一个指令序列,共320 条指令。指令的地址按下述原则生成: 50%的指令是顺序执行的; 25%的指令是均匀分布在前地址部分; 25%的指令是均匀分布在后地址部分;具体的实施方法是: 在0 ,319的指令地址之间随机选取一起点m ; 顺序执行一条指令,即执行地址为m+1的指令; 在前地址 0 ,m+1中随机选取一条指令并执行,该指令的地址为m ; 顺序执行一条指令,其地址为m +1 的指令; 在后地址 m+2,319 中随机选取一条指令并执行; 重复上述步骤,直到执行320 次指令。(2)将指令序列变换为页地址流名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 设页面大小为 1K; 用户内存容量为 4 页到 32 页; 用户虚存容里为 32K。在用户虚存中,按每K存放 10 条指令排列虚存地址,即320 条指令在虚存中的存放方式为:第 0 条第 9 条指令为第 0 页(对应虚存地址为 0 ,9 );第 10 条第 19 条指令为第 1 页(对应虚存地址为 10 ,19 );第 310 条第 319 条指令为第 31 页(对应虚存地址为 310,319)。按以上方式,用户指令可组成32 页。(3)计算最少访问( LFU )算法在不同内存容量下的命中率。其中,命中率 =1-页面失效次数 / 页地址流长度题目十七:请求调页存储管理方式的模拟51设计目的通过对页面、 页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。2设计内容 1 )假设每个页面中可存放10 条指令,分配给作业的内存块数为4。 2 )用 C语言模拟一个作业的执行过程,该作业共有320 条指令,即它的地址空间为 32 页,目前它的所有页都还未调入内存。在模拟过程中,如果所访问的指令已在内存, 则显示其物理地址, 并转下一条指令。 如果所访问的指令还未装入内存,则发生缺页,此时需记录缺页的次数,并将相应页调入内存。如果4个内存块均已装入该作业, 则需进行页面置换, 最后显示其物理地址, 并转下一条指令。在所有 320 指令执行完毕后,请计算并显示作业运行过程中发生的缺页率。 3 )置换算法:最近最不经常使用(NRU )算法。提示: (1)通过随机数产生一个指令序列,共320 条指令。指令的地址按下述原则生成: 50%的指令是顺序执行的;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 25%的指令是均匀分布在前地址部分; 25%的指令是均匀分布在后地址部分;具体的实施方法是: 在0 ,319的指令地址之间随机选取一起点m ; 顺序执行一条指令,即执行地址为m+1的指令; 在前地址 0 ,m+1中随机选取一条指令并执行,该指令的地址为m ; 顺序执行一条指令,其地址为m +1 的指令; 在后地址 m+2,319 中随机选取一条指令并执行; 重复上述步骤,直到执行320 次指令。(2)将指令序列变换为页地址流 设页面大小为 1K; 用户内存容量为 4 页到 32 页; 用户虚存容里为 32K。在用户虚存中,按每K存放 10 条指令排列虚存地址,即320 条指令在虚存中的存放方式为:第 0 条第 9 条指令为第 0 页(对应虚存地址为 0 ,9 );第 10 条第 19 条指令为第 1 页(对应虚存地址为 10 ,19 );第 310 条第 319 条指令为第 31 页(对应虚存地址为 310,319)。按以上方式,用户指令可组成32 页。(3)计算最近最不经常使用(NRU )算法在不同内存容量下的命中率。其中,命中率 =1-页面失效次数 / 页地址流长度题目十八: P、V操作及进程同步的实现1 1设计目的掌握信号量通信方式的一般方法, 了解系统实现“阻塞”和“唤醒”功能的方法和技巧。同时掌握进程同步和互斥的概念及实现技术。2设计内容名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 1)用语言编程实现 P、V原语并用 P、V原语描述如下理发师 -顾客问题:有一个理发师, 一把理发椅和 n 把提供给等候理发的顾客座的椅子。如果没有顾客,则理发师便在理发椅子上睡觉;当第一个顾客到来时, 必须唤醒该理发师进行理发; 如果理发师正在理发时又有顾客到来,则如果有空椅子可坐, 他就坐下来等待,如果没有空椅子,他就离开理发店。为理发师和顾客各编一段程序描述他们的行为,要求不能带有竞争条件, 试用 P、V操作实现。2)实验要求及说明 定义信号量并将 P、V操作定义为带参数 以输出字符串的形式表示理发师和顾客的行为。 设计适当的数据结构和函数描述顾客等待队列和“唤醒”理发师理发过程,以及没有顾客时的“阻塞”理发师过程。 编程时需考虑理发师和顾客对应的程序是并发操作的。提示:可利用随机函数模拟并发操作。 理发师和顾客两个进程各自调用一个函数模拟生产及消费的操作。题目十九: P、V操作及进程同步的实现2 1设计目的掌握信号量通信方式的一般方法, 了解系统实现“阻塞”和“唤醒”功能的方法和技巧。同时掌握进程同步和互斥的概念及实现技术。2设计内容用语言编程实现 P、V原语并用 P、V原语哲学家就餐问题:为每个哲学家各编一段程序描述他们的行为,试用P、V操作实现。题目二十:银行家算法1设计目的1)了解多道程序系统中,多个进程并发执行的资源分配。2)掌握银行家算法,了解资源在进程并发执行中的资源分配情况。3)掌握预防死锁的方法,系统安全状态的基本概念。2设计内容设计一个 n 个并发进程共享 m个系统资源的程序以实现银行家算法。要求:1)简单的选择界面;2)能显示当前系统资源的占用和剩余情况。3)为进程分配资源,如果进程要求的资源大于系统剩余的资源,不与分配并且提示分配不成功;4)撤销作业,释放资源。编写和调试一个系统动态分配资源的简单模拟程序,观察死锁产生的条件,并采用适当的算法,有效地防止和避免死锁的发生。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . 银行家算法分配资源的原则是:系统掌握每个进程对资源的最大需求量,当进程要求申请资源时, 系统就测试该进程尚需资源的最大量,如果系统中现存的资源数大于或等于该进程尚需求资源最大量时,就满足进程的当前申请。 这样就可以保证至少有一个进程可能得到全部资源而执行到结束,然后归还它所占有的全部资源供其它进程使用。银行家算法中的数据结构(1) 可利用资源向量 Available(一维数组 ) 是一个含有 m个元素,其中的每一个元素代表一类可利用的资源数目,其初值是系统中所配置的该类全部可用资源数目。如果Availablej=k,表示系统中现有 Rj类资源 k 个。(2) 最大需求矩阵 Max(二维数组 ) m的矩阵, 它定义了系统中 n 个进程中的每一个进程对m类资源的最大需求。如果 Max(i,j)=k,表示进程 i 需要 Rj类资源的最大数目为k。(3) 分配矩阵 Allocation(二维数组 ) m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation(i,j)=k,表示进程 i 当前已分得 Rj类资源 k 个。(4) 需求矩阵 Need ( 二维数组 ) 是一个含有 n*m的矩阵,用以表示每一个进程尚需的各类资源数。如果 Need(i,j)=k,表示进程 i 还需要 Rj类资源 k 个,方能完成其任务。Need(i,j)= Max(i,j)-Allocation(i,j) 题目二十一: SPOOLING 技术1设计目的设计一个 SPOOLING 假脱机输出的模拟程序,更好地理解和掌握SPOOLING技术的实现原理。2设计内容SPOOLING 技术广泛地应用于各种计算机的I/O 。 该技术通过预输出和缓输出的方法,使用共享设备的一部分来模拟独占设备。1)设计一个实现 SPOOLING 技术的进程设计一个 SPOOLING 输出服务进程、 一个 SPOOLING 输出进程、两个用户请求进程。用户进程请求输出一系列信息,调用输出服务进程, 由输出服务进程将该信息送入输出井。等待SPOOLING 进程进行输出。 SPOOLING 输出进程工作时,根据请求块记录的各进程要输出的信息将其输出。2)设计进程调度算法进程调度采用随机算法,两个请求输出的用户进程的调度概率各为45% ,SPOOLING 输出进程为 10% ,这由随机数发生器产生的随机数来模拟决定。1)进程状态2)进程基本状态有可执行、 等待、结束三种。 可执行状态就是进程正在运行或等待调度的状态;等待状态又分为等待状态1、等待状态 2、等待状态3。状态变化的条件为 : 进程执行完成时,置为“结束”态。 服务程序在将输出信息送输出井时,如发现输出井已满, 将调用进程置为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页,共 27 页 - - - - - - - - - .专业整理 . .学习帮手 . “等待状态 1”。 SPOOLING 进程在进行输出时,若输出井空,则进入“等待状态2”。 SPOOLING 进程输出一个信息块后,应立即释放该信息块所占的输出井空间,并将正在等待输出的进程置为“可执行状态”。 服务程序在输出信息到输出井并形成输出请求信息块后,若SPOOLING 进程处于等待态,则将其置为“可执行态”。 当用户进程申请请求输出块时,若没有可用请求时, 调用进程进入 “等待状态 3”。题目二十二:进程间通信1设计目的Linux 系统的进程通信机构 (IPC)允许在任意进程间大批量的交换数据。本实验的目的是了解和熟悉Linux 支持的通信机制、 共享存储区机制及信号量机制。2设计内容(1) 共享存储区的创建,链接和断开(2) 消息的创建,发送和接收(3) 编写程序1,实现利用共享存储区进行进程通信。使用系统调用shmget() ,shmat() , shmdt() 及 shmctl() 编制一长度为 1k 的消息发送和接收程序。(4) 编写程序2,实现利用消息队列进行进程通信。使用系统调用shmget() ,shmat() , shmdt() 及 shmctl() 编制一长度为 1k 的消息发送和接收程序。 (1) 为了便于操作和观察结果,用一个程序作为“引子”,先后fork ()两个子进程, SERVER 和 CLIENT ,进行通信。(2) SERVER 端建立一个 Key为 75的共享区,并将第一个字节置为-1,作为数据空的标志,等待其他进程发来的消息。当该字节的值发生变化时,表示收到了消息,进行处理。然后再次把它的值设为-1。如果遇到的值为 0,则视为结束信号,取消该队列,并退出SERVER。SERVER每接收到一